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 * 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 >= avefreei) {
 362                                         if (!gdp || 
 363                                             (tmp->bg_free_inodes_count >
 364                                              gdp->bg_free_inodes_count)) {
 365                                                 i = j;
 366                                                 gdp = tmp;
 367                                         }
 368                                 }
 369                         }
 370                 }
 371         }
 372         else 
 373         { /* Try to place the inode in it\'s parent directory */
 374                 i = dir->u.ext2_i.i_block_group;
 375                 tmp = get_group_desc(sb, i);
 376                 if (tmp->bg_free_inodes_count)
 377                         gdp = tmp;
 378                 else
 379                 { /* Use a quadratic hash to find a group with a free inode */
 380                         for (j = 1; j < sb->u.ext2_sb.s_groups_count; j <<= 1) {
 381                                 i += j;
 382                                 if (i >= sb->u.ext2_sb.s_groups_count)
 383                                         i -= sb->u.ext2_sb.s_groups_count;
 384                                 tmp = get_group_desc(sb, i);
 385                                 if (tmp->bg_free_inodes_count) {
 386                                         gdp = tmp;
 387                                         break;
 388                                 }
 389                         }
 390                 }
 391                 if (!gdp) {
 392                         /* That failed: try linear search for a free inode */
 393                         i = dir->u.ext2_i.i_block_group + 2;
 394                         for (j = 2; j < sb->u.ext2_sb.s_groups_count; j++) {
 395                                 if (++i >= sb->u.ext2_sb.s_groups_count)
 396                                         i = 0;
 397                                 tmp = get_group_desc(sb,i);
 398                                 if (tmp->bg_free_inodes_count) {
 399                                         gdp = tmp;
 400                                         break;
 401                                 }
 402                         }
 403                 }
 404         }
 405         
 406         if (!gdp) {
 407                 unlock_super (sb);
 408                 return NULL;
 409         }
 410         bitmap_nr = load_inode_bitmap (sb, i);
 411         bh = sb->u.ext2_sb.s_inode_bitmap[bitmap_nr];
 412         if (!bh) {
 413                 printk ("block_group = %d\n", i);
 414                 panic ("ext2_new_inode: Unable to load group inode bitmap");
 415         }
 416         if ((j = find_first_zero_bit ((unsigned long *) bh->b_data,
 417                                       EXT2_INODES_PER_GROUP(sb))) <
 418             EXT2_INODES_PER_GROUP(sb)) {
 419                 if (set_bit (j, bh->b_data)) {
 420                         printk ("ext2_new_inode: bit already set\n");
 421                         goto repeat;
 422                 }
 423                 bh->b_dirt = 1;
 424         } else
 425                 goto repeat;
 426         j += i * EXT2_INODES_PER_GROUP(sb) + 1;
 427         if (j > sb->u.ext2_sb.s_inodes_count) {
 428                 printk ("block_group = %d,inode=%d\n", i, j);
 429                 printk ("ext2_new_inode: inode > inodes count");
 430                 return NULL;
 431         }
 432         gdp->bg_free_inodes_count --;
 433         if (S_ISDIR(mode))
 434                 gdp->bg_used_dirs_count ++;
 435         sb->u.ext2_sb.s_group_desc[i / EXT2_DESC_PER_BLOCK(sb)]->b_dirt = 1;
 436         es->s_free_inodes_count --;
 437         sb->u.ext2_sb.s_sbh->b_dirt = 1;
 438         sb->s_dirt = 1;
 439         inode->i_sb = sb;
 440         inode->i_count = 1;
 441         inode->i_nlink = 1;
 442         inode->i_dev = sb->s_dev;
 443         inode->i_uid = current->euid;
 444         inode->i_gid = (dir->i_mode & S_ISGID) ? dir->i_gid : current->egid;
 445         inode->i_dirt = 1;
 446         inode->i_ino = j;
 447         inode->i_blksize = sb->s_blocksize;
 448         inode->i_blocks = 0;
 449         inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;
 450         inode->u.ext2_i.i_flags = 0;
 451         inode->u.ext2_i.i_faddr = 0;
 452         inode->u.ext2_i.i_frag = 0;
 453         inode->u.ext2_i.i_fsize = 0;
 454         inode->u.ext2_i.i_file_acl = 0;
 455         inode->u.ext2_i.i_dir_acl = 0;
 456         inode->u.ext2_i.i_dtime = 0;
 457         inode->u.ext2_i.i_block_group = i;
 458         inode->i_op = NULL;
 459         inc_inode_version (inode, gdp, mode);
 460 #ifdef EXT2FS_DEBUG
 461         printk ("ext2_new_inode : allocating inode %d\n", inode->i_ino);
 462 #endif
 463         unlock_super (sb);
 464         return inode;
 465 }
 466 
 467 unsigned long ext2_count_free_inodes (struct super_block *sb)
     /*  */
 468 {
 469         struct ext2_super_block * es;
 470 #ifdef EXT2FS_DEBUG
 471         unsigned long desc_count, bitmap_count, x;
 472         unsigned long group_desc;
 473         unsigned long desc;
 474         int bitmap_nr;
 475         struct ext2_group_desc * gdp;
 476         int i;
 477 
 478         lock_super (sb);
 479         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 480         desc_count = 0;
 481         bitmap_count = 0;
 482         group_desc = 0;
 483         desc = 0;
 484         gdp = NULL;
 485         for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
 486                 if (!gdp) {
 487                         if (!sb->u.ext2_sb.s_group_desc[group_desc]) {
 488                                 printk ("ext2_count_free_inodes: Descriptor not loaded\n");
 489                                 break;
 490                         }
 491                         gdp = (struct ext2_group_desc *) sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
 492                 }
 493                 desc_count += gdp[desc].bg_free_inodes_count;
 494                 bitmap_nr = load_inode_bitmap (sb, i);
 495                 if (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr])
 496                         x = ext2_count_free (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr],
 497                                                EXT2_INODES_PER_GROUP(sb) / 8);
 498                 else {
 499                         x = 0;
 500                         printk ("Cannot load inode bitmap for group %d (bitmap = %d)\n",
 501                                 i, bitmap_nr);
 502                 }
 503                 printk ("group %d: stored = %d, counted = %d\n",
 504                         i, gdp[desc].bg_free_inodes_count, x);
 505                 bitmap_count += x;
 506                 desc ++;
 507                 if (desc == EXT2_DESC_PER_BLOCK(sb)) {
 508                         group_desc ++;
 509                         desc = 0;
 510                         gdp = NULL;
 511                 }
 512         }
 513         printk("ext2_count_free_inodes: stored = %d, computed = %d, %d\n",
 514                 es->s_free_inodes_count, desc_count, bitmap_count);
 515         unlock_super (sb);
 516         return desc_count;
 517 #else
 518         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 519         return es->s_free_inodes_count;
 520 #endif
 521 }
/* */
root/fs/ext2/ialloc.c

DEFINITIONS
