fs/ext2/ialloc.c

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

DEFINITIONS
