fs/ext2/ialloc.c

/* */
This source file includes following definitions.
find_first_zero_bit
read_inode_bitmap
load_inode_bitmap
set_inode_dtime
ext2_free_inode
inc_inode_version
get_group_desc
ext2_new_inode
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 || inode->i_ino > sb->u.ext2_sb.s_inodes_count) {
 225                 printk("free_inode: inode 0 or nonexistent inode\n");
 226                 unlock_super (sb);
 227                 return;
 228         }
 229         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 230         block_group = (inode->i_ino - 1) / EXT2_INODES_PER_GROUP(sb);
 231         bit = (inode->i_ino - 1) % EXT2_INODES_PER_GROUP(sb);
 232         bitmap_nr = load_inode_bitmap (sb, block_group);
 233         bh = sb->u.ext2_sb.s_inode_bitmap[bitmap_nr];
 234         if (!bh) {
 235                 printk ("block_group = %d\n", block_group);
 236                 panic ("ext2_free_inode: Unable to load bitmap");
 237         }
 238         if (clear_bit (bit, bh->b_data))
 239                 printk ("ext2_free_inode (%04x:%d): bit already cleared\n",
 240                         sb->s_dev, inode->i_ino);
 241         else {
 242                 group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
 243                 desc = block_group % EXT2_DESC_PER_BLOCK(sb);
 244                 bh2 = sb->u.ext2_sb.s_group_desc[group_desc];
 245                 if (!bh2) {
 246                         printk ("group_desc = %d\n", group_desc);
 247                         panic ("ext2_free_inode: Group descriptor not loaded");
 248                 }
 249                 gdp = (struct ext2_group_desc *) bh2->b_data;
 250                 gdp[desc].bg_free_inodes_count ++;
 251                 if (S_ISDIR(inode->i_mode))
 252                         gdp[desc].bg_used_dirs_count --;
 253                 bh2->b_dirt = 1;
 254                 set_inode_dtime (inode, gdp, desc);
 255         }
 256         bh->b_dirt = 1;
 257         es->s_free_inodes_count ++;
 258         sb->u.ext2_sb.s_sbh->b_dirt = 1;
 259         sb->s_dirt = 1;
 260         unlock_super (sb);
 261         clear_inode (inode);
 262 }
 263 
 264 /*
 265  * This function increments the inode version number
 266  *
 267  * This may be used one day by the NFS server
 268  */
 269 static void inc_inode_version (struct inode * inode,
     /*  */
 270                                struct ext2_group_desc *gdp,
 271                                int mode)
 272 {
 273         unsigned long inode_block;
 274         struct buffer_head * bh;
 275         struct ext2_inode * raw_inode;
 276 
 277         inode_block = gdp->bg_inode_table + (((inode->i_ino - 1) %
 278                         EXT2_INODES_PER_GROUP(inode->i_sb)) /
 279                         EXT2_INODES_PER_BLOCK(inode->i_sb));
 280         bh = bread (inode->i_sb->s_dev, inode_block, inode->i_sb->s_blocksize);
 281         if (!bh) {
 282                 printk ("inode=%d, inode_block=%d\n",
 283                         inode->i_ino, inode_block);
 284                 printk ("inc_inode_version: Cannot load inode table block");
 285                 inode->u.ext2_i.i_version = 1;
 286                 return;
 287         }
 288         raw_inode = ((struct ext2_inode *) bh->b_data) +
 289                         (((inode->i_ino - 1) %
 290                         EXT2_INODES_PER_GROUP(inode->i_sb)) %
 291                         EXT2_INODES_PER_BLOCK(inode->i_sb));
 292         raw_inode->i_version++;
 293         inode->u.ext2_i.i_version = raw_inode->i_version;
 294         bh->b_dirt = 1;
 295         brelse (bh);
 296 }
 297 
 298 static struct ext2_group_desc * get_group_desc(struct super_block * sb,
     /*  */
 299                                                int group)
 300 {
 301         struct ext2_group_desc * gdp;
 302         if (group >= sb->u.ext2_sb.s_groups_count || group < 0 )
 303                 panic ("ext2: get_group_desc: Invalid group\n");
 304         if (!sb->u.ext2_sb.s_group_desc[group / EXT2_DESC_PER_BLOCK(sb)])
 305                 panic ("ext2: get_group_desc: Descriptor not loaded");
 306         gdp = (struct ext2_group_desc *)
 307                 sb->u.ext2_sb.s_group_desc[group / EXT2_DESC_PER_BLOCK(sb)]
 308                 ->b_data;
 309         return gdp + (group % EXT2_DESC_PER_BLOCK(sb));
 310 }
 311         
 312 /*
 313  * There are two policies for allocating an inode.  If the new inode is
 314  * a directory, then a forward search is made for a block group with both
 315  * free space and a low directory-to-inode ratio; if that fails, then of
 316  * the groups with above-average free space, that group with the fewest
 317  * directories already is chosen.
 318  *
 319  * For other inodes, search forward from the parent directory\'s block
 320  * group to find a free inode.
 321  */
 322 struct inode * ext2_new_inode (const struct inode * dir, int mode)
     /*  */
 323 {
 324         struct super_block * sb;
 325         struct buffer_head * bh;
 326         int i, j, avefreei;
 327         struct inode * inode;
 328         int bitmap_nr;
 329         struct ext2_group_desc * gdp, * tmp;
 330         struct ext2_super_block * es;
 331 
 332         if (!dir || !(inode = get_empty_inode ()))
 333                 return NULL;
 334         sb = dir->i_sb;
 335         inode->i_sb = sb;
 336         inode->i_flags = sb->s_flags;
 337         lock_super (sb);
 338         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 339 repeat:
 340         gdp = NULL; i=0;
 341         
 342         if (S_ISDIR(mode)) {
 343                 avefreei = es->s_free_inodes_count /
 344                         sb->u.ext2_sb.s_groups_count;
 345 /* I am not yet convinced that this next bit is necessary.
 346                 i = dir->u.ext2_i.i_block_group;
 347                 for (j = 0; j < sb->u.ext2_sb.s_groups_count; j++) {
 348                         tmp = get_group_desc(sb, i);
 349                         if ((tmp->bg_used_dirs_count << 8) < 
 350                             tmp->bg_free_inodes_count) {
 351                                 gdp = tmp;
 352                                 break;
 353                         }
 354                         else
 355                         i = ++i % sb->u.ext2_sb.s_groups_count;
 356                 }
 357 */
 358                 if (!gdp) {
 359                         for (j = 0; j < sb->u.ext2_sb.s_groups_count; j++) {
 360                                 tmp = get_group_desc(sb, j);
 361                                 if (tmp->bg_free_inodes_count &&
 362                                         tmp->bg_free_inodes_count >= avefreei) {
 363                                         if (!gdp || 
 364                                             (tmp->bg_free_inodes_count >
 365                                              gdp->bg_free_inodes_count)) {
 366                                                 i = j;
 367                                                 gdp = tmp;
 368                                         }
 369                                 }
 370                         }
 371                 }
 372         }
 373         else 
 374         { /* Try to place the inode in it\'s parent directory */
 375                 i = dir->u.ext2_i.i_block_group;
 376                 tmp = get_group_desc(sb, i);
 377                 if (tmp->bg_free_inodes_count)
 378                         gdp = tmp;
 379                 else
 380                 { /* Use a quadratic hash to find a group with a free inode */
 381                         for (j = 1; j < sb->u.ext2_sb.s_groups_count; j <<= 1) {
 382                                 i += j;
 383                                 if (i >= sb->u.ext2_sb.s_groups_count)
 384                                         i -= sb->u.ext2_sb.s_groups_count;
 385                                 tmp = get_group_desc(sb, i);
 386                                 if (tmp->bg_free_inodes_count) {
 387                                         gdp = tmp;
 388                                         break;
 389                                 }
 390                         }
 391                 }
 392                 if (!gdp) {
 393                         /* That failed: try linear search for a free inode */
 394                         i = dir->u.ext2_i.i_block_group + 2;
 395                         for (j = 2; j < sb->u.ext2_sb.s_groups_count; j++) {
 396                                 if (++i >= sb->u.ext2_sb.s_groups_count)
 397                                         i = 0;
 398                                 tmp = get_group_desc(sb,i);
 399                                 if (tmp->bg_free_inodes_count) {
 400                                         gdp = tmp;
 401                                         break;
 402                                 }
 403                         }
 404                 }
 405         }
 406         
 407         if (!gdp) {
 408                 unlock_super (sb);
 409                 iput(inode);
 410                 return NULL;
 411         }
 412         bitmap_nr = load_inode_bitmap (sb, i);
 413         bh = sb->u.ext2_sb.s_inode_bitmap[bitmap_nr];
 414         if (!bh) {
 415                 printk ("block_group = %d\n", i);
 416                 panic ("ext2_new_inode: Unable to load group inode bitmap");
 417         }
 418         if ((j = find_first_zero_bit ((unsigned long *) bh->b_data,
 419                                       EXT2_INODES_PER_GROUP(sb))) <
 420             EXT2_INODES_PER_GROUP(sb)) {
 421                 if (set_bit (j, bh->b_data)) {
 422                         printk ("ext2_new_inode: bit already set\n");
 423                         goto repeat;
 424                 }
 425                 bh->b_dirt = 1;
 426         } else
 427                 goto repeat;
 428         j += i * EXT2_INODES_PER_GROUP(sb) + 1;
 429         if (j > sb->u.ext2_sb.s_inodes_count) {
 430                 printk ("block_group = %d,inode=%d\n", i, j);
 431                 printk ("ext2_new_inode: inode > inodes count");
 432                 return NULL;
 433         }
 434         gdp->bg_free_inodes_count --;
 435         if (S_ISDIR(mode))
 436                 gdp->bg_used_dirs_count ++;
 437         sb->u.ext2_sb.s_group_desc[i / EXT2_DESC_PER_BLOCK(sb)]->b_dirt = 1;
 438         es->s_free_inodes_count --;
 439         sb->u.ext2_sb.s_sbh->b_dirt = 1;
 440         sb->s_dirt = 1;
 441         inode->i_sb = sb;
 442         inode->i_count = 1;
 443         inode->i_nlink = 1;
 444         inode->i_dev = sb->s_dev;
 445         inode->i_uid = current->euid;
 446         inode->i_gid = (dir->i_mode & S_ISGID) ? dir->i_gid : current->egid;
 447         inode->i_dirt = 1;
 448         inode->i_ino = j;
 449         inode->i_blksize = sb->s_blocksize;
 450         inode->i_blocks = 0;
 451         inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;
 452         inode->u.ext2_i.i_flags = 0;
 453         inode->u.ext2_i.i_faddr = 0;
 454         inode->u.ext2_i.i_frag = 0;
 455         inode->u.ext2_i.i_fsize = 0;
 456         inode->u.ext2_i.i_file_acl = 0;
 457         inode->u.ext2_i.i_dir_acl = 0;
 458         inode->u.ext2_i.i_dtime = 0;
 459         inode->u.ext2_i.i_block_group = i;
 460         inode->i_op = NULL;
 461         insert_inode_hash(inode);
 462         inc_inode_version (inode, gdp, mode);
 463 #ifdef EXT2FS_DEBUG
 464         printk ("ext2_new_inode : allocating inode %d\n", inode->i_ino);
 465 #endif
 466         unlock_super (sb);
 467         return inode;
 468 }
 469 
 470 unsigned long ext2_count_free_inodes (struct super_block *sb)
     /*  */
 471 {
 472         struct ext2_super_block * es;
 473 #ifdef EXT2FS_DEBUG
 474         unsigned long desc_count, bitmap_count, x;
 475         unsigned long group_desc;
 476         unsigned long desc;
 477         int bitmap_nr;
 478         struct ext2_group_desc * gdp;
 479         int i;
 480 
 481         lock_super (sb);
 482         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 483         desc_count = 0;
 484         bitmap_count = 0;
 485         group_desc = 0;
 486         desc = 0;
 487         gdp = NULL;
 488         for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
 489                 if (!gdp) {
 490                         if (!sb->u.ext2_sb.s_group_desc[group_desc]) {
 491                                 printk ("ext2_count_free_inodes: Descriptor not loaded\n");
 492                                 break;
 493                         }
 494                         gdp = (struct ext2_group_desc *) sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
 495                 }
 496                 desc_count += gdp[desc].bg_free_inodes_count;
 497                 bitmap_nr = load_inode_bitmap (sb, i);
 498                 if (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr])
 499                         x = ext2_count_free (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr],
 500                                                EXT2_INODES_PER_GROUP(sb) / 8);
 501                 else {
 502                         x = 0;
 503                         printk ("Cannot load inode bitmap for group %d (bitmap = %d)\n",
 504                                 i, bitmap_nr);
 505                 }
 506                 printk ("group %d: stored = %d, counted = %d\n",
 507                         i, gdp[desc].bg_free_inodes_count, x);
 508                 bitmap_count += x;
 509                 desc ++;
 510                 if (desc == EXT2_DESC_PER_BLOCK(sb)) {
 511                         group_desc ++;
 512                         desc = 0;
 513                         gdp = NULL;
 514                 }
 515         }
 516         printk("ext2_count_free_inodes: stored = %d, computed = %d, %d\n",
 517                 es->s_free_inodes_count, desc_count, bitmap_count);
 518         unlock_super (sb);
 519         return desc_count;
 520 #else
 521         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 522         return es->s_free_inodes_count;
 523 #endif
 524 }
/* */
root/fs/ext2/ialloc.c

DEFINITIONS
