fs/ext2/balloc.c

/* */
This source file includes following definitions.
find_first_zero_bit
find_next_zero_bit
find_first_zero_byte
read_block_bitmap
load__block_bitmap
load_block_bitmap
ext2_free_block
ext2_new_block
ext2_count_free_blocks
   1 /*
   2  *  linux/fs/ext2/balloc.c
   3  *
   4  *  Copyright (C) 1992, 1993  Remy Card (card@masi.ibp.fr)
   5  *
   6  *  Enhanced block allocation by Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
   7  */
   8 
   9 /* balloc.c contains the blocks allocation and deallocation routines */
  10 
  11 /*
  12 
  13    The free blocks are managed by bitmaps.  A file system contains several
  14    blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
  15    block for inodes, N blocks for the inode table and data blocks.
  16 
  17    The file system contains group descriptors which are located after the
  18    super block.  Each descriptor contains the number of the bitmap block and
  19    the free blocks count in the block.  The descriptors are loaded in memory
  20    when a file system is mounted (see ext2_read_super).
  21 
  22 */
  23 
  24 #include <linux/sched.h>
  25 #include <linux/ext2_fs.h>
  26 #include <linux/stat.h>
  27 #include <linux/kernel.h>
  28 #include <linux/string.h>
  29 #include <linux/locks.h>
  30 
  31 #include <asm/bitops.h>
  32 
  33 #define clear_block(addr,size) \
  34         __asm__("cld\n\t" \
  35                 "rep\n\t" \
  36                 "stosl" \
  37                 : \
  38                 :"a" (0), "c" (size/4), "D" ((long) (addr)) \
  39                 :"cx", "di")
  40 
  41 static inline int find_first_zero_bit(unsigned *addr, unsigned size)
     /*  */
  42 {
  43         int res;
  44         if (!size)
  45                 return 0;
  46         __asm__("
  47         cld
  48         movl $-1,%%eax
  49         repe; scasl
  50         je 1f
  51         subl $4,%%edi
  52         movl (%%edi),%%eax
  53         notl %%eax
  54         bsfl %%eax,%%edx
  55         jmp 2f
  56 1:      xorl %%edx,%%edx
  57 2:      subl %%ebx,%%edi
  58         shll $3,%%edi
  59         addl %%edi,%%edx"
  60         :"=d" (res):"c" ((size+31)>>5), "D" (addr), "b" (addr)
  61         :"ax", "bx", "cx", "di");
  62         return res;
  63 }
  64 
  65 static inline int find_next_zero_bit(unsigned *addr, int size, int offset)
     /*  */
  66 {
  67         unsigned *p = ((unsigned *) addr) + (offset >> 5);
  68         int set = 0, bit = offset & 31, res;
  69         
  70         if (bit) {
  71                 /* Look for zero in first byte */
  72                 __asm__("
  73                 bsfl %1,%0
  74                 jne 1f
  75                 movl $32, %0
  76 1:              " : "=r" (set) : "r" (~(*p >> bit)));
  77                 if (set < (32-bit))
  78                         return set + offset;
  79                 set = 32-bit;
  80                 p++;
  81         }
  82         /* No zero yet, search remaining full bytes for a zero */
  83         res = find_first_zero_bit(p, size-32*(p-addr));
  84         return (offset + set + res);
  85 }
  86 
  87 static inline char * find_first_zero_byte(char *addr,int size)
     /*  */
  88 {
  89         char *res;
  90         if (!size)
  91                 return 0;
  92         __asm__("
  93         cld
  94         mov $0,%%eax
  95         repnz; scasb
  96         jnz 1f
  97         dec %%edi
  98 1:      " : "=D" (res) : "0" (addr), "c" (size) : "ax");
  99         return res;
 100 }
 101 
 102 static void read_block_bitmap (struct super_block * sb,
     /*  */
 103                                unsigned int block_group,
 104                                unsigned long bitmap_nr)
 105 {
 106         unsigned long group_desc;
 107         unsigned long desc;
 108         struct ext2_group_desc * gdp;
 109         struct buffer_head * bh;
 110         
 111         group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
 112         desc = block_group % EXT2_DESC_PER_BLOCK(sb);
 113         if (!sb->u.ext2_sb.s_group_desc[group_desc]) {
 114                 printk ("block_group = %d,group_desc = %d,desc = %d\n",
 115                          block_group, group_desc, desc);
 116                 panic ("read_block_bitmap: Group descriptor not loaded");
 117         }
 118         gdp = (struct ext2_group_desc *) 
 119                 sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
 120         bh = bread (sb->s_dev, gdp[desc].bg_block_bitmap, sb->s_blocksize);
 121         if (!bh) {
 122                 printk ("block_group = %d,group_desc = %d,"
 123                         "desc = %d,block_bitmap = %d\n",
 124                         block_group, group_desc, desc,
 125                         gdp[desc].bg_block_bitmap);
 126                 panic ("read_block_bitmap: Cannot read block bitmap");
 127         }
 128         sb->u.ext2_sb.s_block_bitmap_number[bitmap_nr] = block_group;
 129         sb->u.ext2_sb.s_block_bitmap[bitmap_nr] = bh;
 130 }
 131 
 132 /*
 133  * load_block_bitmap loads the block bitmap for a blocks group
 134  *
 135  * It maintains a cache for the last bitmaps loaded.  This cache is managed
 136  * with a LRU algorithm.
 137  *
 138  * Notes:
 139  * 1/ There is one cache per mounted file system.
 140  * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
 141  *    this function reads the bitmap without maintaining a LRU cache.
 142  */
 143 static int load__block_bitmap (struct super_block * sb,
     /*  */
 144                                unsigned int block_group)
 145 {
 146         int i, j;
 147         unsigned long block_bitmap_number;
 148         struct buffer_head * block_bitmap;
 149 
 150         if (block_group >= sb->u.ext2_sb.s_groups_count) {
 151                 printk ("block_group = %d, groups_count = %d\n",
 152                         block_group, sb->u.ext2_sb.s_groups_count);
 153                 panic ("load_block_bitmap: block_group >= groups_count");
 154         }
 155 
 156         if (sb->u.ext2_sb.s_groups_count <= EXT2_MAX_GROUP_LOADED) {
 157                 if (sb->u.ext2_sb.s_block_bitmap[block_group]) {
 158                         if (sb->u.ext2_sb.s_block_bitmap_number[block_group] 
 159                             != block_group)
 160                                 panic ("load_block_bitmap: "
 161                                        "block_group != block_bitmap_number");
 162                         else
 163                                 return block_group;
 164                 } else {
 165                         read_block_bitmap (sb, block_group, block_group);
 166                         return block_group;
 167                 }
 168         }
 169 
 170         for (i = 0; i < sb->u.ext2_sb.s_loaded_block_bitmaps &&
 171                     sb->u.ext2_sb.s_block_bitmap_number[i] != block_group; i++)
 172                 ;
 173         if (i < sb->u.ext2_sb.s_loaded_block_bitmaps &&
 174             sb->u.ext2_sb.s_block_bitmap_number[i] == block_group) {
 175                 block_bitmap_number = sb->u.ext2_sb.s_block_bitmap_number[i];
 176                 block_bitmap = sb->u.ext2_sb.s_block_bitmap[i];
 177                 for (j = i; j > 0; j--) {
 178                         sb->u.ext2_sb.s_block_bitmap_number[j] =
 179                                 sb->u.ext2_sb.s_block_bitmap_number[j - 1];
 180                         sb->u.ext2_sb.s_block_bitmap[j] =
 181                                 sb->u.ext2_sb.s_block_bitmap[j - 1];
 182                 }
 183                 sb->u.ext2_sb.s_block_bitmap_number[0] = block_bitmap_number;
 184                 sb->u.ext2_sb.s_block_bitmap[0] = block_bitmap;
 185         } else {
 186                 if (sb->u.ext2_sb.s_loaded_block_bitmaps < 
 187                     EXT2_MAX_GROUP_LOADED)
 188                         sb->u.ext2_sb.s_loaded_block_bitmaps++;
 189                 else
 190                         brelse (sb->u.ext2_sb.s_block_bitmap
 191                                 [EXT2_MAX_GROUP_LOADED - 1]);
 192                 for (j = sb->u.ext2_sb.s_loaded_block_bitmaps-1; j>0;  j--) {
 193                         sb->u.ext2_sb.s_block_bitmap_number[j] =
 194                                 sb->u.ext2_sb.s_block_bitmap_number[j - 1];
 195                         sb->u.ext2_sb.s_block_bitmap[j] =
 196                                 sb->u.ext2_sb.s_block_bitmap[j - 1];
 197                 }
 198                 read_block_bitmap (sb, block_group, 0);
 199         }
 200         return 0;
 201 }
 202 
 203 static inline int load_block_bitmap (struct super_block * sb,
     /*  */
 204                                      unsigned int block_group)
 205 {
 206         if (sb->u.ext2_sb.s_loaded_block_bitmaps > 0 &&
 207             sb->u.ext2_sb.s_block_bitmap_number[0] == block_group)
 208                 return 0;
 209         
 210         if (sb->u.ext2_sb.s_groups_count <= EXT2_MAX_GROUP_LOADED && 
 211             sb->u.ext2_sb.s_block_bitmap_number[block_group] == block_group &&
 212             sb->u.ext2_sb.s_block_bitmap[block_group]) 
 213                 return block_group;
 214 
 215         return load__block_bitmap (sb, block_group);
 216 }
 217 
 218 void ext2_free_block (struct super_block * sb, unsigned long block)
     /*  */
 219 {
 220         struct buffer_head * bh;
 221         struct buffer_head * bh2;
 222         unsigned long block_group;
 223         unsigned long bit;
 224         unsigned long group_desc;
 225         unsigned long desc;
 226         int bitmap_nr;
 227         struct ext2_group_desc * gdp;
 228         struct ext2_super_block * es;
 229 
 230         if (!sb) {
 231                 printk ("ext2_free_block: nonexistant device");
 232                 return;
 233         }
 234         lock_super (sb);
 235         if (block < sb->u.ext2_sb.s_first_data_block ||
 236             block >= sb->u.ext2_sb.s_blocks_count) {
 237                 printk ("ext2_free_block: block not in datazone\n");
 238                 unlock_super (sb);
 239                 return;
 240         }
 241         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 242 #ifdef EXT2FS_DEBUG
 243         printk ("ext2_free_block: freeing block %d\n", block);
 244 #endif
 245         bh = get_hash_table (sb->s_dev, block, sb->s_blocksize);
 246         if (bh)
 247                 bh->b_dirt = 0;
 248         brelse (bh);
 249         block_group = (block - sb->u.ext2_sb.s_first_data_block) /
 250                       EXT2_BLOCKS_PER_GROUP(sb);
 251         bit = (block - sb->u.ext2_sb.s_first_data_block) %
 252                 EXT2_BLOCKS_PER_GROUP(sb);
 253         bitmap_nr = load_block_bitmap (sb, block_group);
 254         bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
 255         if (!bh) {
 256                 printk ("block_group = %d\n", block_group);
 257                 panic ("ext2_free_block: Unable to load group bitmap");
 258         }
 259         if (clear_bit (bit, bh->b_data))
 260                 printk ("ext2_free_block (%04x:%d): bit already cleared\n",
 261                         sb->s_dev, block);
 262         else {
 263                 group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
 264                 desc = block_group % EXT2_DESC_PER_BLOCK(sb);
 265                 bh2 = sb->u.ext2_sb.s_group_desc[group_desc];
 266                 if (!bh2) {
 267                         printk ("group_desc = %d\n", group_desc);
 268                         panic ("ext2_free_block: Group descriptor not loaded");
 269                 }
 270                 gdp = (struct ext2_group_desc *) bh2->b_data;
 271                 gdp[desc].bg_free_blocks_count ++;
 272                 bh2->b_dirt = 1;
 273         }
 274         bh->b_dirt = 1;
 275         es->s_free_blocks_count ++;
 276         sb->u.ext2_sb.s_sbh->b_dirt = 1;
 277         sb->s_dirt = 1;
 278         unlock_super (sb);
 279         return;
 280 }
 281 
 282 /*
 283  * ext2_new_block uses a goal block to assist allocation.  If the goal is
 284  * free, or there is a free block within 32 blocks of the goal, that block
 285  * is allocated.  Otherwise a forward search is made for a free block; within 
 286  * each block group the search first looks for an entire free byte in the block
 287  * bitmap, and then for any free bit if that fails.
 288  */
 289 int ext2_new_block (struct super_block * sb, unsigned long goal)
     /*  */
 290 {
 291         struct buffer_head * bh;
 292         char *p, *r;
 293         int i, j, k;
 294         unsigned long lmap;
 295         unsigned long group_desc;
 296         unsigned long desc;
 297         int bitmap_nr;
 298         struct ext2_group_desc * gdp;
 299         struct ext2_super_block * es;
 300 
 301 #ifdef EXT2FS_DEBUG
 302         static int goal_hits = 0, goal_attempts = 0;
 303 #endif
 304         if (!sb) {
 305                 printk ("ext2_new_block: nonexistant device");
 306                 return 0;
 307         }
 308         lock_super (sb);
 309         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 310         if (es->s_free_blocks_count <= es->s_r_blocks_count && !suser()) {
 311                 unlock_super (sb);
 312                 return 0;
 313         }
 314 
 315 #ifdef EXT2FS_DEBUG
 316         printk ("ext2_new_block: goal=%d.\n", goal);
 317 #endif
 318         
 319 repeat:
 320         /* First, test whether the goal block is free. */
 321         i = ((goal - sb->u.ext2_sb.s_first_data_block) /
 322              EXT2_BLOCKS_PER_GROUP(sb));
 323         group_desc = i / EXT2_DESC_PER_BLOCK(sb);
 324         desc = i % EXT2_DESC_PER_BLOCK(sb);
 325         gdp = (struct ext2_group_desc *) 
 326                 sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
 327         if (!gdp) {
 328                 panic ("ext2_new_block: Descriptor not loaded");
 329         }
 330         if (gdp[desc].bg_free_blocks_count > 0) {
 331                 j = ((goal - sb->u.ext2_sb.s_first_data_block) %
 332                        EXT2_BLOCKS_PER_GROUP(sb));
 333 #ifdef EXT2FS_DEBUG
 334                 if (j)
 335                         goal_attempts++;
 336 #endif
 337                 bitmap_nr = load_block_bitmap (sb, i);
 338                 bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
 339                 if (!bh) {
 340                         printk ("Cannot load bitmap_nr %d.\n",
 341                                 bitmap_nr);
 342                         unlock_super (sb);
 343                         return 0;
 344                 }
 345 #ifdef EXT2FS_DEBUG
 346                 printk ("goal is at %d[%d,%d]:%d.\n", 
 347                         i, group_desc, desc, j);
 348 #endif
 349                 if (!test_bit(j, bh->b_data)) {
 350 #ifdef EXT2FS_DEBUG
 351                         goal_hits++;
 352                         printk ("ext2_new_block: goal bit allocated.\n");
 353 #endif
 354                         goto got_block;
 355                 }
 356                 if (j) {
 357                         /* The goal was occupied; search forward for a free 
 358                            block within the next 32 blocks */
 359                         lmap = (((((unsigned long *) bh->b_data)[j >> 5]) 
 360                                  >> ((j&31)+1)) |
 361                                 ((((unsigned long *) bh->b_data)[(j>>5)+1])
 362                                  <<(31-(j&31))));
 363                         if (lmap != 0xffffffffl) {
 364                                 __asm__ ("bsfl %1,%0" :
 365                                          "=r" (k) :
 366                                          "r" (~lmap)); k++;
 367                                 if ((j + k) < EXT2_BLOCKS_PER_GROUP(sb)) {
 368                                         j += k;
 369                                         goto got_block;
 370                                 }
 371                         }
 372                 }
 373         
 374 #ifdef EXT2FS_DEBUG
 375                 printk ("Bit not found near goal\n");
 376 #endif
 377                 /* There has been no free block found in the near vicinity
 378                    of the goal: do a search forward through the block groups,
 379                    searching in each group first for an entire free byte in
 380                    the bitmap and then for any free bit.
 381                    
 382                    Search first in the remainder of the current group; then,
 383                    cyclicly search throught the rest of the groups. */
 384                 p = ((char *) bh->b_data) + (j>>3);
 385                 r = find_first_zero_byte (p, 
 386                                           (EXT2_BLOCKS_PER_GROUP(sb)-j+7)>>3);
 387                 k = (r - ((char *) bh->b_data)) << 3;
 388                 if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
 389                         j = k;
 390                         goto got_block;
 391                 }
 392                 k = find_next_zero_bit ((unsigned long *) bh->b_data, 
 393                                         EXT2_BLOCKS_PER_GROUP(sb),
 394                                         j);
 395                 if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
 396                         j = k;
 397                         goto got_block;
 398                 }
 399         }
 400 
 401 #ifdef EXT2FS_DEBUG
 402         printk ("Bit not found in block group %d.\n", i);
 403 #endif
 404         /* Now search the rest of the groups.  We assume that group_desc, desc,
 405            i and gdp correctly point to the last group visited. */
 406         for (k = 0; k < sb->u.ext2_sb.s_groups_count; k++) {
 407                 i++;
 408                 if (i >= sb->u.ext2_sb.s_groups_count) {
 409                         i = 0;
 410                         group_desc = 0;
 411                         desc = 0;
 412                         gdp = (struct ext2_group_desc *) 
 413                                 sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
 414                 }
 415                 else {
 416                         desc++;
 417                         if (desc >= EXT2_DESC_PER_BLOCK(sb)) {
 418                                 group_desc++;
 419                                 desc = 0;
 420                                 gdp = (struct ext2_group_desc *) 
 421                                         sb->u.ext2_sb.s_group_desc[group_desc]
 422                                         ->b_data;
 423                         }
 424                 }
 425                 if (!gdp) {
 426                         panic ("ext2_new_block: Descriptor not loaded");
 427                 }
 428                 if (gdp[desc].bg_free_blocks_count > 0)
 429                         break;
 430         }
 431         if (k >= sb->u.ext2_sb.s_groups_count) {
 432                 unlock_super (sb);
 433                 return 0;
 434         }
 435         bitmap_nr = load_block_bitmap (sb, i);
 436         bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
 437         if (!bh) {
 438                 printk ("block_group = %d\n", i);
 439                 panic ("ext2_new_block: Unable to load group bitmap");
 440         }
 441         r = find_first_zero_byte (bh->b_data, 
 442                                   EXT2_BLOCKS_PER_GROUP(sb) >> 3);
 443         j = (r-bh->b_data) << 3;
 444         if (j >= EXT2_BLOCKS_PER_GROUP(sb))
 445                 j = find_first_zero_bit ((unsigned long *) bh->b_data,
 446                                          EXT2_BLOCKS_PER_GROUP(sb));
 447         if (j >= EXT2_BLOCKS_PER_GROUP(sb)) {
 448                 printk ("ext2_new_block: "
 449                         "Unable to locate free bit in block group %d.\n",i);
 450                 unlock_super (sb);
 451                 return 0;
 452         }
 453                 
 454 got_block:
 455 #ifdef EXT2FS_DEBUG
 456         printk ("ext2_new_block: using block group %d(%d,%d,%d)\n", 
 457                 i, group_desc, desc, gdp[desc].bg_free_blocks_count);
 458 #endif
 459 
 460         if (set_bit (j, bh->b_data)) {
 461                 printk ("ext2_new_block: bit already set\n");
 462                 goto repeat;
 463         }
 464         bh->b_dirt = 1;
 465         
 466 #ifdef EXT2FS_DEBUG
 467         printk ("ext2_new_block: found bit %d\n", j);
 468 #endif
 469         j += i * EXT2_BLOCKS_PER_GROUP(sb) +
 470                 sb->u.ext2_sb.s_first_data_block;
 471         if (j >= sb->u.ext2_sb.s_blocks_count) {
 472                 printk ("block_group = %d,block=%d\n", i, j);
 473                 printk ("ext2_new_block: block >= blocks count");
 474                 unlock_super (sb);
 475                 return 0;
 476         }
 477         if (!(bh = getblk (sb->s_dev, j, sb->s_blocksize))) {
 478                 printk ("ext2_new_block: cannot get block");
 479                 unlock_super (sb);
 480                 return 0;
 481         }
 482         clear_block (bh->b_data, sb->s_blocksize);
 483         bh->b_uptodate = 1;
 484         bh->b_dirt = 1;
 485         brelse (bh);
 486 #ifdef EXT2FS_DEBUG
 487         printk("ext2_new_block: allocating block %d. "
 488                "Goal hits %d of %d.\n", j, goal_hits, goal_attempts);
 489 #endif
 490         gdp[desc].bg_free_blocks_count --;
 491         sb->u.ext2_sb.s_group_desc[group_desc]->b_dirt = 1;
 492         es->s_free_blocks_count --;
 493         sb->u.ext2_sb.s_sbh->b_dirt = 1;
 494         sb->s_dirt = 1;
 495         unlock_super (sb);
 496         return j;
 497 }
 498 
 499 unsigned long ext2_count_free_blocks (struct super_block *sb)
     /*  */
 500 {
 501         struct ext2_super_block * es;
 502 #ifdef EXT2FS_DEBUG
 503         unsigned long desc_count, bitmap_count, x;
 504         unsigned long group_desc;
 505         unsigned long desc;
 506         int bitmap_nr;
 507         struct ext2_group_desc * gdp;
 508         int i;
 509         
 510         lock_super (sb);
 511         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 512         desc_count = 0;
 513         bitmap_count = 0;
 514         group_desc = 0;
 515         desc = 0;
 516         gdp = NULL;
 517         for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
 518                 if (!gdp) {
 519                         if (!sb->u.ext2_sb.s_group_desc[group_desc]) {
 520                                 printk ("ext2_count_free_block: "
 521                                         "Descriptor not loaded\n");
 522                                 break;
 523                         }
 524                         gdp = (struct ext2_group_desc *) 
 525                                 sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
 526                 }
 527                 desc_count += gdp[desc].bg_free_blocks_count;
 528                 bitmap_nr = load_block_bitmap (sb, i);
 529                 if (sb->u.ext2_sb.s_block_bitmap[bitmap_nr])
 530                         x = ext2_count_free 
 531                                 (sb->u.ext2_sb.s_block_bitmap[bitmap_nr],
 532                                  sb->s_blocksize);
 533                 else {
 534                         x = 0;
 535                         printk ("Cannot load bitmap for group %d\n", i);
 536                 }
 537                 printk ("group %d: stored = %d, counted = %d\n",
 538                         i, gdp[desc].bg_free_blocks_count, x);
 539                 bitmap_count += x;
 540                 desc ++;
 541                 if (desc == EXT2_DESC_PER_BLOCK(sb)) {
 542                         group_desc ++;
 543                         desc = 0;
 544                         gdp = NULL;
 545                 }
 546         }
 547         printk("ext2_count_free_blocks: stored = %d, computed = %d, %d\n",
 548                es->s_free_blocks_count, desc_count, bitmap_count);
 549         unlock_super (sb);
 550         return bitmap_count;
 551 #else
 552         es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
 553         return es->s_free_blocks_count;
 554 #endif
 555 }
/* */
root/fs/ext2/balloc.c

DEFINITIONS
