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):"c" ((size+31)>>5), "D" (addr), "b" (addr)
  55         :"ax", "bx", "cx", "di");
  56         return res;
  57 }
  58 
  59 static void read_inode_bitmap (struct super_block * sb,
     /*  */
  60                                unsigned long block_group,
  61                                unsigned int bitmap_nr)
  62 {
  63         unsigned long group_desc;
  64         unsigned long desc;
  65         struct ext2_group_desc * gdp;
  66         struct buffer_head * bh;
  67 
  68         group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
  69         desc = block_group % EXT2_DESC_PER_BLOCK(sb);
  70         if (!sb->u.ext2_sb.s_group_desc[group_desc]) {
  71                 printk ("block_group = %d,group_desc = %d,desc = %d\n",
  72                          block_group, group_desc, desc);
  73                 panic ("read_inode_bitmap: Group descriptor not loaded");
  74         }
  75         gdp = (struct ext2_group_desc *) sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
  76         bh = bread (sb->s_dev, gdp[desc].bg_inode_bitmap, sb->s_blocksize);
  77         if (!bh) {
  78                 printk ("block_group = %d,group_desc = %d,desc = %d,inode_bitmap = %d\n",
  79                         block_group, group_desc, desc, gdp[desc].bg_inode_bitmap);
  80                 panic ("read_inode_bitmap: Cannot read inode bitmap");
  81         }
  82         sb->u.ext2_sb.s_inode_bitmap_number[bitmap_nr] = block_group;
  83         sb->u.ext2_sb.s_inode_bitmap[bitmap_nr] = bh;
  84 }
  85 
  86 /*
  87  * load_inode_bitmap loads the inode bitmap for a blocks group
  88  *
  89  * It maintains a cache for the last bitmaps loaded.  This cache is managed
  90  * with a LRU algorithm.
  91  *
  92  * Notes:
  93  * 1/ There is one cache per mounted file system.
  94  * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
  95  *    this function reads the bitmap without maintaining a LRU cache.
  96  */
  97 static int load_inode_bitmap (struct super_block * sb,
     /*  */
  98                               unsigned int block_group)
  99 {
 100         int i, j;
 101         unsigned long inode_bitmap_number;
 102         struct buffer_head * inode_bitmap;
 103 
 104         if (block_group >= sb->u.ext2_sb.s_groups_count) {
 105                 printk ("block_group = %d, groups_count = %d\n",
 106                         block_group, sb->u.ext2_sb.s_groups_count);
 107                 panic ("load_inode_bitmap: block_group >= groups_count");
 108         }
 109         if (sb->u.ext2_sb.s_loaded_inode_bitmaps > 0 &&
 110             sb->u.ext2_sb.s_inode_bitmap_number[0] == block_group)
 111                 return 0;
 112         if (sb->u.ext2_sb.s_groups_count <= EXT2_MAX_GROUP_LOADED) {
 113                 if (sb->u.ext2_sb.s_inode_bitmap[block_group]) {
 114                         if (sb->u.ext2_sb.s_inode_bitmap_number[block_group] != block_group)
 115                                 panic ("load_inode_bitmap: block_group != inode_bitmap_number");
 116                         else
 117                                 return block_group;
 118                 } else {
 119                         read_inode_bitmap (sb, block_group, block_group);
 120                         return block_group;
 121                 }
 122         }
 123 
 124         for (i = 0; i < sb->u.ext2_sb.s_loaded_inode_bitmaps &&
 125                     sb->u.ext2_sb.s_inode_bitmap_number[i] != block_group;
 126              i++)
 127                 ;
 128         if (i < sb->u.ext2_sb.s_loaded_inode_bitmaps &&
 129             sb->u.ext2_sb.s_inode_bitmap_number[i] == block_group) {
 130                 inode_bitmap_number = sb->u.ext2_sb.s_inode_bitmap_number[i];
 131                 inode_bitmap = sb->u.ext2_sb.s_inode_bitmap[i];
 132                 for (j = i; j > 0; j--) {
 133                         sb->u.ext2_sb.s_inode_bitmap_number[j] =
 134                                 sb->u.ext2_sb.s_inode_bitmap_number[j - 1];
 135                         sb->u.ext2_sb.s_inode_bitmap[j] =
 136                                 sb->u.ext2_sb.s_inode_bitmap[j - 1];
 137                 }
 138                 sb->u.ext2_sb.s_inode_bitmap_number[0] = inode_bitmap_number;
 139                 sb->u.ext2_sb.s_inode_bitmap[0] = inode_bitmap;
 140         } else {
 141                 if (sb->u.ext2_sb.s_loaded_inode_bitmaps < EXT2_MAX_GROUP_LOADED)
 142                         sb->u.ext2_sb.s_loaded_inode_bitmaps++;
 143                 else
 144                         brelse (sb->u.ext2_sb.s_inode_bitmap[EXT2_MAX_GROUP_LOADED - 1]);
 145                 for (j = sb->u.ext2_sb.s_loaded_inode_bitmaps - 1; j > 0; j--) {
 146                         sb->u.ext2_sb.s_inode_bitmap_number[j] =
 147                                 sb->u.ext2_sb.s_inode_bitmap_number[j - 1];
 148                         sb->u.ext2_sb.s_inode_bitmap[j] =
 149                                 sb->u.ext2_sb.s_inode_bitmap[j - 1];
 150                 }
 151                 read_inode_bitmap (sb, block_group, 0);
 152         }
 153         return 0;
 154 }
 155 
 156 /*
 157  * This function sets the deletion time for the inode
 158  *
 159  * This may be used one day by an 'undelete' program
 160  */
 161 static void set_inode_dtime (struct inode * inode,
     /*  */
 162                              struct ext2_group_desc *gdp, unsigned long desc)
 163 {
 164         unsigned long inode_block;
 165         struct buffer_head * bh;
 166         struct ext2_inode * raw_inode;
 167 
 168         inode_block = gdp[desc].bg_inode_table + (((inode->i_ino - 1) %
 169                         EXT2_INODES_PER_GROUP(inode->i_sb)) /
 170                         EXT2_INODES_PER_BLOCK(inode->i_sb));
 171         bh = bread (inode->i_sb->s_dev, inode_block, inode->i_sb->s_blocksize);
 172         if (!bh) {
 173                 printk ("inode=%d, inode_block=%d\n", inode->i_ino, inode_block);
 174                 panic ("set_inode_dtime: Cannot load inode table block");
 175         }
 176         raw_inode = ((struct ext2_inode *) bh->b_data) +
 177                         (((inode->i_ino - 1) %
 178                         EXT2_INODES_PER_GROUP(inode->i_sb)) %
 179                         EXT2_INODES_PER_BLOCK(inode->i_sb));
 180         raw_inode->i_dtime = CURRENT_TIME;
 181         bh->b_dirt = 1;
 182         brelse (bh);
 183 }
 184 
 185 void ext2_free_inode (struct inode * inode)
     /*  */
 186 {
 187         struct super_block * sb;
 188         struct buffer_head * bh;
 189         struct buffer_head * bh2;
 190         unsigned long block_group;
 191         unsigned long bit;
 192         unsigned long group_desc;
 193         unsigned long desc;
 194         int bitmap_nr;
 195         struct ext2_group_desc * gdp;
 196         struct ext2_super_block * es;
 197 
 198         if (!inode)
 199                 return;
 200         if (!inode->i_dev) {
 201                 printk ("ext2_free_inode: inode has no device\n");
 202                 return;
 203         }
 204         if (inode->i_count > 1) {
 205                 printk ("ext2_free_inode: inode has count=%d\n",
 206                         inode->i_count);
 207                 return;
 208         }
 209         if (inode->i_nlink) {
 210                 printk ("ext2_free_inode: inode has nlink=%d\n",
 211                         inode->i_nlink);
 212                 return;
 213         }
 214         if (!inode->i_sb) {
 215                 printk("ext2_free_inode: inode on nonexistent device\n");
 216                 return;
 217         }
 218 #ifdef EXT2FS_DEBUG
 219         printk ("ext2_free_inode: freeing inode %d\n", inode->i_ino);
 220 #endif
 221         sb = inode->i_sb;
 222         lock_super (sb);
 223         if (inode->i_ino < 1 || inode->i_ino > sb->u.ext2_sb.s_inodes_count) {
 224                 printk("free_inode: inode 0 or nonexistent inode\n");
 225                 unlock_super (sb);
 226                 return;
 227         }
 228         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 229         block_group = (inode->i_ino - 1) / EXT2_INODES_PER_GROUP(sb);
 230         bit = (inode->i_ino - 1) % EXT2_INODES_PER_GROUP(sb);
 231         bitmap_nr = load_inode_bitmap (sb, block_group);
 232         bh = sb->u.ext2_sb.s_inode_bitmap[bitmap_nr];
 233         if (!bh) {
 234                 printk ("block_group = %d\n", block_group);
 235                 panic ("ext2_free_inode: Unable to load bitmap");
 236         }
 237         if (clear_bit (bit, bh->b_data))
 238                 printk ("ext2_free_inode (%04x:%d): bit already cleared\n",
 239                         sb->s_dev, inode->i_ino);
 240         else {
 241                 group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
 242                 desc = block_group % EXT2_DESC_PER_BLOCK(sb);
 243                 bh2 = sb->u.ext2_sb.s_group_desc[group_desc];
 244                 if (!bh2) {
 245                         printk ("group_desc = %d\n", group_desc);
 246                         panic ("ext2_free_inode: Group descriptor not loaded");
 247                 }
 248                 gdp = (struct ext2_group_desc *) bh2->b_data;
 249                 gdp[desc].bg_free_inodes_count ++;
 250                 if (S_ISDIR(inode->i_mode))
 251                         gdp[desc].bg_used_dirs_count --;
 252                 bh2->b_dirt = 1;
 253                 set_inode_dtime (inode, gdp, desc);
 254         }
 255         bh->b_dirt = 1;
 256         es->s_free_inodes_count ++;
 257         sb->u.ext2_sb.s_sbh->b_dirt = 1;
 258         sb->s_dirt = 1;
 259         unlock_super (sb);
 260         clear_inode (inode);
 261 }
 262 
 263 /*
 264  * This function increments the inode version number
 265  *
 266  * This may be used one day by the NFS server
 267  */
 268 static void inc_inode_version (struct inode * inode,
     /*  */
 269                                struct ext2_group_desc *gdp,
 270                                int mode)
 271 {
 272         unsigned long inode_block;
 273         struct buffer_head * bh;
 274         struct ext2_inode * raw_inode;
 275 
 276         inode_block = gdp->bg_inode_table + (((inode->i_ino - 1) %
 277                         EXT2_INODES_PER_GROUP(inode->i_sb)) /
 278                         EXT2_INODES_PER_BLOCK(inode->i_sb));
 279         bh = bread (inode->i_sb->s_dev, inode_block, inode->i_sb->s_blocksize);
 280         if (!bh) {
 281                 printk ("inode=%d, inode_block=%d\n",
 282                         inode->i_ino, inode_block);
 283                 printk ("inc_inode_version: Cannot load inode table block");
 284                 inode->u.ext2_i.i_version = 1;
 285                 return;
 286         }
 287         raw_inode = ((struct ext2_inode *) bh->b_data) +
 288                         (((inode->i_ino - 1) %
 289                         EXT2_INODES_PER_GROUP(inode->i_sb)) %
 290                         EXT2_INODES_PER_BLOCK(inode->i_sb));
 291         raw_inode->i_version++;
 292         if (!S_ISFIFO(mode))
 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 * 
 299 get_group_desc(struct super_block *sb, 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         if (!S_ISFIFO(mode))
 458                 inode->u.ext2_i.i_block_group = i;
 459         inode->i_op = NULL;
 460         inc_inode_version (inode, gdp, mode);
 461 #ifdef EXT2FS_DEBUG
 462         printk ("ext2_new_inode : allocating inode %d\n", inode->i_ino);
 463 #endif
 464         unlock_super (sb);
 465         return inode;
 466 }
 467 
 468 unsigned long ext2_count_free_inodes (struct super_block *sb)
     /*  */
 469 {
 470         struct ext2_super_block * es;
 471 #ifdef EXT2FS_DEBUG
 472         unsigned long desc_count, bitmap_count, x;
 473         unsigned long group_desc;
 474         unsigned long desc;
 475         int bitmap_nr;
 476         struct ext2_group_desc * gdp;
 477         int i;
 478 
 479         lock_super (sb);
 480         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 481         desc_count = 0;
 482         bitmap_count = 0;
 483         group_desc = 0;
 484         desc = 0;
 485         gdp = NULL;
 486         for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
 487                 if (!gdp) {
 488                         if (!sb->u.ext2_sb.s_group_desc[group_desc]) {
 489                                 printk ("ext2_count_free_inodes: Descriptor not loaded\n");
 490                                 break;
 491                         }
 492                         gdp = (struct ext2_group_desc *) sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
 493                 }
 494                 desc_count += gdp[desc].bg_free_inodes_count;
 495                 bitmap_nr = load_inode_bitmap (sb, i);
 496                 if (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr])
 497                         x = ext2_count_free (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr],
 498                                                EXT2_INODES_PER_GROUP(sb) / 8);
 499                 else {
 500                         x = 0;
 501                         printk ("Cannot load inode bitmap for group %d (bitmap = %d)\n",
 502                                 i, bitmap_nr);
 503                 }
 504                 printk ("group %d: stored = %d, counted = %d\n",
 505                         i, gdp[desc].bg_free_inodes_count, x);
 506                 bitmap_count += x;
 507                 desc ++;
 508                 if (desc == EXT2_DESC_PER_BLOCK(sb)) {
 509                         group_desc ++;
 510                         desc = 0;
 511                         gdp = NULL;
 512                 }
 513         }
 514         printk("ext2_count_free_inodes: stored = %d, computed = %d, %d\n",
 515                 es->s_free_inodes_count, desc_count, bitmap_count);
 516         unlock_super (sb);
 517         return desc_count;
 518 #else
 519         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 520         return es->s_free_inodes_count;
 521 #endif
 522 }
/* */
root/fs/ext2/ialloc.c

DEFINITIONS
