root/fs/ext2/ialloc.c

/* */

DEFINITIONS

1. find_first_zero_bit
2. read_inode_bitmap
3. load_inode_bitmap
4. set_inode_dtime
5. ext2_free_inode
6. inc_inode_version
7. get_group_desc
8. ext2_new_inode
9. ext2_count_free_inodes

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

/* */