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

DEFINITIONS
