sys/gnu/ext2fs/ext2_linux_ialloc.c

   1 /*
   2  *  modified for Lites 1.1
   3  *
   4  *  Aug 1995, Godmar Back (gback@cs.utah.edu)
   5  *  University of Utah, Department of Computer Science
   6  */
   7 /*
   8  *  linux/fs/ext2/ialloc.c
   9  *
  10  * Copyright (C) 1992, 1993, 1994, 1995
  11  * Remy Card (card@masi.ibp.fr)
  12  * Laboratoire MASI - Institut Blaise Pascal
  13  * Universite Pierre et Marie Curie (Paris VI)
  14  *
  15  *  BSD ufs-inspired inode and directory allocation by
  16  *  Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
  17  */
  18
  19 /*
  20  * The free inodes are managed by bitmaps.  A file system contains several
  21  * blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
  22  * block for inodes, N blocks for the inode table and data blocks.
  23  *
  24  * The file system contains group descriptors which are located after the
  25  * super block.  Each descriptor contains the number of the bitmap block and
  26  * the free blocks count in the block.  The descriptors are loaded in memory
  27  * when a file system is mounted (see ext2_read_super).
  28  */
  29
  30 #include <sys/param.h>
  31 #include <sys/systm.h>
  32 #include <sys/buf.h>
  33 #include <sys/proc.h>
  34 #include <sys/mount.h>
  35 #include <sys/vnode.h>
  36
  37 #include <ufs/ufs/quota.h>
  38 #include <ufs/ufs/inode.h>
  39 #include <ufs/ufs/ufsmount.h>
  40 #include <gnu/ext2fs/ext2_extern.h>
  41 #include <gnu/ext2fs/ext2_fs.h>
  42 #include <gnu/ext2fs/ext2_fs_sb.h>
  43 #include <gnu/ext2fs/fs.h>
  44 #include <sys/stat.h>
  45
  46 #ifdef __i386__
  47 #include <gnu/ext2fs/i386-bitops.h>
  48 #else
  49 #error please provide bit operation functions
  50 #endif
  51
  52 /* this is supposed to mark a buffer dirty on ready for delayed writing
  53  */
  54 void mark_buffer_dirty(struct buf *bh)
  55 {
  56         int s;
  57
  58         s = splbio();
  59         bh->b_flags |= B_DIRTY;
  60         splx(s);
  61 }
  62
  63 struct ext2_group_desc * get_group_desc (struct mount * mp,
  64                                                 unsigned int block_group,
  65                                                 struct buffer_head ** bh)
  66 {
  67         struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
  68         unsigned long group_desc;
  69         unsigned long desc;
  70         struct ext2_group_desc * gdp;
  71
  72         if (block_group >= sb->s_groups_count)
  73                 panic ("get_group_desc: "
  74                             "block_group >= groups_count - "
  75                             "block_group = %d, groups_count = %lu",
  76                             block_group, sb->s_groups_count);
  77
  78         group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
  79         desc = block_group % EXT2_DESC_PER_BLOCK(sb);
  80         if (!sb->s_group_desc[group_desc])
  81                 panic ( "get_group_desc:"
  82                             "Group descriptor not loaded - "
  83                             "block_group = %d, group_desc = %lu, desc = %lu",
  84                              block_group, group_desc, desc);
  85         gdp = (struct ext2_group_desc *)
  86                 sb->s_group_desc[group_desc]->b_data;
  87         if (bh)
  88                 *bh = sb->s_group_desc[group_desc];
  89         return gdp + desc;
  90 }
  91
  92 static void read_inode_bitmap (struct mount * mp,
  93                                unsigned long block_group,
  94                                unsigned int bitmap_nr)
  95 {
  96         struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
  97         struct ext2_group_desc * gdp;
  98         struct buffer_head * bh;
  99         int     error;
 100
 101         gdp = get_group_desc (mp, block_group, NULL);
 102         if ((error = bread (VFSTOUFS(mp)->um_devvp,
 103                             fsbtodb(sb, gdp->bg_inode_bitmap),
 104                             sb->s_blocksize,
 105                             NOCRED, &bh)) != 0)
 106                 panic ( "read_inode_bitmap:"
 107                             "Cannot read inode bitmap - "
 108                             "block_group = %lu, inode_bitmap = %lu",
 109                             block_group, (unsigned long) gdp->bg_inode_bitmap);
 110         sb->s_inode_bitmap_number[bitmap_nr] = block_group;
 111         sb->s_inode_bitmap[bitmap_nr] = bh;
 112         LCK_BUF(bh)
 113 }
 114
 115 /*
 116  * load_inode_bitmap loads the inode bitmap for a blocks group
 117  *
 118  * It maintains a cache for the last bitmaps loaded.  This cache is managed
 119  * with a LRU algorithm.
 120  *
 121  * Notes:
 122  * 1/ There is one cache per mounted file system.
 123  * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
 124  *    this function reads the bitmap without maintaining a LRU cache.
 125  */
 126 static int load_inode_bitmap (struct mount * mp,
 127                               unsigned int block_group)
 128 {
 129         struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
 130         int i, j;
 131         unsigned long inode_bitmap_number;
 132         struct buffer_head * inode_bitmap;
 133
 134         if (block_group >= sb->s_groups_count)
 135                 panic ("load_inode_bitmap:"
 136                             "block_group >= groups_count - "
 137                             "block_group = %d, groups_count = %lu",
 138                              block_group, sb->s_groups_count);
 139         if (sb->s_loaded_inode_bitmaps > 0 &&
 140             sb->s_inode_bitmap_number[0] == block_group)
 141                 return 0;
 142         if (sb->s_groups_count <= EXT2_MAX_GROUP_LOADED) {
 143                 if (sb->s_inode_bitmap[block_group]) {
 144                         if (sb->s_inode_bitmap_number[block_group] !=
 145                                 block_group)
 146                                 panic ( "load_inode_bitmap:"
 147                                     "block_group != inode_bitmap_number");
 148                         else
 149                                 return block_group;
 150                 } else {
 151                         read_inode_bitmap (mp, block_group, block_group);
 152                         return block_group;
 153                 }
 154         }
 155
 156         for (i = 0; i < sb->s_loaded_inode_bitmaps &&
 157                     sb->s_inode_bitmap_number[i] != block_group;
 158              i++)
 159                 ;
 160         if (i < sb->s_loaded_inode_bitmaps &&
 161             sb->s_inode_bitmap_number[i] == block_group) {
 162                 inode_bitmap_number = sb->s_inode_bitmap_number[i];
 163                 inode_bitmap = sb->s_inode_bitmap[i];
 164                 for (j = i; j > 0; j--) {
 165                         sb->s_inode_bitmap_number[j] =
 166                                 sb->s_inode_bitmap_number[j - 1];
 167                         sb->s_inode_bitmap[j] =
 168                                 sb->s_inode_bitmap[j - 1];
 169                 }
 170                 sb->s_inode_bitmap_number[0] = inode_bitmap_number;
 171                 sb->s_inode_bitmap[0] = inode_bitmap;
 172         } else {
 173                 if (sb->s_loaded_inode_bitmaps < EXT2_MAX_GROUP_LOADED)
 174                         sb->s_loaded_inode_bitmaps++;
 175                 else
 176                         ULCK_BUF(sb->s_inode_bitmap[EXT2_MAX_GROUP_LOADED - 1])
 177                 for (j = sb->s_loaded_inode_bitmaps - 1; j > 0; j--) {
 178                         sb->s_inode_bitmap_number[j] =
 179                                 sb->s_inode_bitmap_number[j - 1];
 180                         sb->s_inode_bitmap[j] =
 181                                 sb->s_inode_bitmap[j - 1];
 182                 }
 183                 read_inode_bitmap (mp, block_group, 0);
 184         }
 185         return 0;
 186 }
 187
 188
 189 void ext2_free_inode (struct inode * inode)
 190 {
 191         struct ext2_sb_info * sb;
 192         struct buffer_head * bh;
 193         struct buffer_head * bh2;
 194         unsigned long block_group;
 195         unsigned long bit;
 196         int bitmap_nr;
 197         struct ext2_group_desc * gdp;
 198         struct ext2_super_block * es;
 199
 200         if (!inode)
 201                 return;
 202
 203         if (inode->i_nlink) {
 204                 printf ("ext2_free_inode: inode has nlink=%d\n",
 205                         inode->i_nlink);
 206                 return;
 207         }
 208
 209         ext2_debug ("freeing inode %lu\n", inode->i_number);
 210
 211         sb = inode->i_e2fs;
 212         lock_super (DEVVP(inode));
 213         if (inode->i_number < EXT2_FIRST_INO ||
 214             inode->i_number > sb->s_es->s_inodes_count) {
 215                 printf ("free_inode reserved inode or nonexistent inode");
 216                 unlock_super (DEVVP(inode));
 217                 return;
 218         }
 219         es = sb->s_es;
 220         block_group = (inode->i_number - 1) / EXT2_INODES_PER_GROUP(sb);
 221         bit = (inode->i_number - 1) % EXT2_INODES_PER_GROUP(sb);
 222         bitmap_nr = load_inode_bitmap (ITOV(inode)->v_mount, block_group);
 223         bh = sb->s_inode_bitmap[bitmap_nr];
 224         if (!clear_bit (bit, bh->b_data))
 225                 printf ( "ext2_free_inode:"
 226                       "bit already cleared for inode %lu",
 227                       (unsigned long)inode->i_number);
 228         else {
 229                 gdp = get_group_desc (ITOV(inode)->v_mount, block_group, &bh2);
 230                 gdp->bg_free_inodes_count++;
 231                 if (S_ISDIR(inode->i_mode))
 232                         gdp->bg_used_dirs_count--;
 233                 mark_buffer_dirty(bh2);
 234                 es->s_free_inodes_count++;
 235         }
 236         mark_buffer_dirty(bh);
 237 /*** XXX
 238         if (sb->s_flags & MS_SYNCHRONOUS) {
 239                 ll_rw_block (WRITE, 1, &bh);
 240                 wait_on_buffer (bh);
 241         }
 242 ***/
 243         sb->s_dirt = 1;
 244         unlock_super (DEVVP(inode));
 245 }
 246
 247 #if linux
 248 /*
 249  * This function increments the inode version number
 250  *
 251  * This may be used one day by the NFS server
 252  */
 253 static void inc_inode_version (struct inode * inode,
 254                                struct ext2_group_desc *gdp,
 255                                int mode)
 256 {
 257         unsigned long inode_block;
 258         struct buffer_head * bh;
 259         struct ext2_inode * raw_inode;
 260
 261         inode_block = gdp->bg_inode_table + (((inode->i_number - 1) %
 262                         EXT2_INODES_PER_GROUP(inode->i_sb)) /
 263                         EXT2_INODES_PER_BLOCK(inode->i_sb));
 264         bh = bread (inode->i_sb->s_dev, inode_block, inode->i_sb->s_blocksize);
 265         if (!bh) {
 266                 printf ("inc_inode_version Cannot load inode table block - "
 267                             "inode=%lu, inode_block=%lu\n",
 268                             inode->i_number, inode_block);
 269                 inode->u.ext2_i.i_version = 1;
 270                 return;
 271         }
 272         raw_inode = ((struct ext2_inode *) bh->b_data) +
 273                         (((inode->i_number - 1) %
 274                         EXT2_INODES_PER_GROUP(inode->i_sb)) %
 275                         EXT2_INODES_PER_BLOCK(inode->i_sb));
 276         raw_inode->i_version++;
 277         inode->u.ext2_i.i_version = raw_inode->i_version;
 278         bdwrite (bh);
 279 }
 280
 281 #endif /* linux */
 282
 283 /*
 284  * There are two policies for allocating an inode.  If the new inode is
 285  * a directory, then a forward search is made for a block group with both
 286  * free space and a low directory-to-inode ratio; if that fails, then of
 287  * the groups with above-average free space, that group with the fewest
 288  * directories already is chosen.
 289  *
 290  * For other inodes, search forward from the parent directory\'s block
 291  * group to find a free inode.
 292  */
 293 /*
 294  * this functino has been reduced to the actual 'find the inode number' part
 295  */
 296 ino_t ext2_new_inode (const struct inode * dir, int mode)
 297 {
 298         struct ext2_sb_info * sb;
 299         struct buffer_head * bh;
 300         struct buffer_head * bh2;
 301         int i, j, avefreei;
 302         int bitmap_nr;
 303         struct ext2_group_desc * gdp;
 304         struct ext2_group_desc * tmp;
 305         struct ext2_super_block * es;
 306
 307         if (!dir)
 308                 return 0;
 309         sb = dir->i_e2fs;
 310
 311         lock_super (DEVVP(dir));
 312         es = sb->s_es;
 313 repeat:
 314         gdp = NULL; i=0;
 315
 316         if (S_ISDIR(mode)) {
 317                 avefreei = es->s_free_inodes_count /
 318                         sb->s_groups_count;
 319 /* I am not yet convinced that this next bit is necessary.
 320                 i = dir->u.ext2_i.i_block_group;
 321                 for (j = 0; j < sb->u.ext2_sb.s_groups_count; j++) {
 322                         tmp = get_group_desc (sb, i, &bh2);
 323                         if ((tmp->bg_used_dirs_count << 8) <
 324                             tmp->bg_free_inodes_count) {
 325                                 gdp = tmp;
 326                                 break;
 327                         }
 328                         else
 329                         i = ++i % sb->u.ext2_sb.s_groups_count;
 330                 }
 331 */
 332                 if (!gdp) {
 333                         for (j = 0; j < sb->s_groups_count; j++) {
 334                                 tmp = get_group_desc(ITOV(dir)->v_mount,j,&bh2);
 335                                 if (tmp->bg_free_inodes_count &&
 336                                         tmp->bg_free_inodes_count >= avefreei) {
 337                                         if (!gdp ||
 338                                             (tmp->bg_free_blocks_count >
 339                                              gdp->bg_free_blocks_count)) {
 340                                                 i = j;
 341                                                 gdp = tmp;
 342                                         }
 343                                 }
 344                         }
 345                 }
 346         }
 347         else
 348         {
 349                 /*
 350                  * Try to place the inode in its parent directory
 351                  */
 352                 i = dir->i_block_group;
 353                 tmp = get_group_desc (ITOV(dir)->v_mount, i, &bh2);
 354                 if (tmp->bg_free_inodes_count)
 355                         gdp = tmp;
 356                 else
 357                 {
 358                         /*
 359                          * Use a quadratic hash to find a group with a
 360                          * free inode
 361                          */
 362                         for (j = 1; j < sb->s_groups_count; j <<= 1) {
 363                                 i += j;
 364                                 if (i >= sb->s_groups_count)
 365                                         i -= sb->s_groups_count;
 366                                 tmp = get_group_desc(ITOV(dir)->v_mount,i,&bh2);
 367                                 if (tmp->bg_free_inodes_count) {
 368                                         gdp = tmp;
 369                                         break;
 370                                 }
 371                         }
 372                 }
 373                 if (!gdp) {
 374                         /*
 375                          * That failed: try linear search for a free inode
 376                          */
 377                         i = dir->i_block_group + 1;
 378                         for (j = 2; j < sb->s_groups_count; j++) {
 379                                 if (++i >= sb->s_groups_count)
 380                                         i = 0;
 381                                 tmp = get_group_desc(ITOV(dir)->v_mount,i,&bh2);
 382                                 if (tmp->bg_free_inodes_count) {
 383                                         gdp = tmp;
 384                                         break;
 385                                 }
 386                         }
 387                 }
 388         }
 389
 390         if (!gdp) {
 391                 unlock_super (DEVVP(dir));
 392                 return 0;
 393         }
 394         bitmap_nr = load_inode_bitmap (ITOV(dir)->v_mount, i);
 395         bh = sb->s_inode_bitmap[bitmap_nr];
 396         if ((j = find_first_zero_bit ((unsigned long *) bh->b_data,
 397                                       EXT2_INODES_PER_GROUP(sb))) <
 398             EXT2_INODES_PER_GROUP(sb)) {
 399                 if (set_bit (j, bh->b_data)) {
 400                         printf ( "ext2_new_inode:"
 401                                       "bit already set for inode %d", j);
 402                         goto repeat;
 403                 }
 404 /* Linux now does the following:
 405                 mark_buffer_dirty(bh);
 406                 if (sb->s_flags & MS_SYNCHRONOUS) {
 407                         ll_rw_block (WRITE, 1, &bh);
 408                         wait_on_buffer (bh);
 409                 }
 410 */
 411                 mark_buffer_dirty(bh);
 412         } else {
 413                 if (gdp->bg_free_inodes_count != 0) {
 414                         printf ( "ext2_new_inode:"
 415                                     "Free inodes count corrupted in group %d",
 416                                     i);
 417                         unlock_super (DEVVP(dir));
 418                         return 0;
 419                 }
 420                 goto repeat;
 421         }
 422         j += i * EXT2_INODES_PER_GROUP(sb) + 1;
 423         if (j < EXT2_FIRST_INO || j > es->s_inodes_count) {
 424                 printf ( "ext2_new_inode:"
 425                             "reserved inode or inode > inodes count - "
 426                             "block_group = %d,inode=%d", i, j);
 427                 unlock_super (DEVVP(dir));
 428                 return 0;
 429         }
 430         gdp->bg_free_inodes_count--;
 431         if (S_ISDIR(mode))
 432                 gdp->bg_used_dirs_count++;
 433         mark_buffer_dirty(bh2);
 434         es->s_free_inodes_count--;
 435         /* mark_buffer_dirty(sb->u.ext2_sb.s_sbh, 1); */
 436         sb->s_dirt = 1;
 437         unlock_super (DEVVP(dir));
 438         return j;
 439 }
 440
 441 #ifdef unused
 442 static unsigned long ext2_count_free_inodes (struct mount * mp)
 443 {
 444 #ifdef EXT2FS_DEBUG
 445         struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
 446         struct ext2_super_block * es;
 447         unsigned long desc_count, bitmap_count, x;
 448         int bitmap_nr;
 449         struct ext2_group_desc * gdp;
 450         int i;
 451
 452         lock_super (VFSTOUFS(mp)->um_devvp);
 453         es = sb->s_es;
 454         desc_count = 0;
 455         bitmap_count = 0;
 456         gdp = NULL;
 457         for (i = 0; i < sb->s_groups_count; i++) {
 458                 gdp = get_group_desc (mp, i, NULL);
 459                 desc_count += gdp->bg_free_inodes_count;
 460                 bitmap_nr = load_inode_bitmap (mp, i);
 461                 x = ext2_count_free (sb->s_inode_bitmap[bitmap_nr],
 462                                      EXT2_INODES_PER_GROUP(sb) / 8);
 463                 ext2_debug ("group %d: stored = %d, counted = %lu\n",
 464                         i, gdp->bg_free_inodes_count, x);
 465                 bitmap_count += x;
 466         }
 467         ext2_debug("stored = %lu, computed = %lu, %lu\n",
 468                 es->s_free_inodes_count, desc_count, bitmap_count);
 469         unlock_super (VFSTOUFS(mp)->um_devvp);
 470         return desc_count;
 471 #else
 472         return VFSTOUFS(mp)->um_e2fsb->s_free_inodes_count;
 473 #endif
 474 }
 475 #endif /* unused */
 476
 477 #ifdef LATER
 478 void ext2_check_inodes_bitmap (struct mount * mp)
 479 {
 480         struct ext2_super_block * es;
 481         unsigned long desc_count, bitmap_count, x;
 482         int bitmap_nr;
 483         struct ext2_group_desc * gdp;
 484         int i;
 485
 486         lock_super (sb);
 487         es = sb->u.ext2_sb.s_es;
 488         desc_count = 0;
 489         bitmap_count = 0;
 490         gdp = NULL;
 491         for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
 492                 gdp = get_group_desc (sb, i, NULL);
 493                 desc_count += gdp->bg_free_inodes_count;
 494                 bitmap_nr = load_inode_bitmap (sb, i);
 495                 x = ext2_count_free (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr],
 496                                      EXT2_INODES_PER_GROUP(sb) / 8);
 497                 if (gdp->bg_free_inodes_count != x)
 498                         printf ( "ext2_check_inodes_bitmap:"
 499                                     "Wrong free inodes count in group %d, "
 500                                     "stored = %d, counted = %lu", i,
 501                                     gdp->bg_free_inodes_count, x);
 502                 bitmap_count += x;
 503         }
 504         if (es->s_free_inodes_count != bitmap_count)
 505                 printf ( "ext2_check_inodes_bitmap:"
 506                             "Wrong free inodes count in super block, "
 507                             "stored = %lu, counted = %lu",
 508                             (unsigned long) es->s_free_inodes_count, bitmap_count);
 509         unlock_super (sb);
 510 }
 511 #endif