fs/ext2/ialloc.c

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

DEFINITIONS
