fs/ext2/balloc.c

   1 /*
   2  *  linux/fs/ext2/balloc.c
   3  *
   4  * Copyright (C) 1992, 1993, 1994, 1995
   5  * Remy Card (card@masi.ibp.fr)
   6  * Laboratoire MASI - Institut Blaise Pascal
   7  * Universite Pierre et Marie Curie (Paris VI)
   8  *
   9  *  Enhanced block allocation by Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
  10  *  Big-endian to little-endian byte-swapping/bitmaps by
  11  *        David S. Miller (davem@caip.rutgers.edu), 1995
  12  */
  13
  14 #include <linux/config.h>
  15 #include <linux/fs.h>
  16 #include <linux/ext2_fs.h>
  17 #include <linux/locks.h>
  18 #include <linux/quotaops.h>
  19
  20 /*
  21  * balloc.c contains the blocks allocation and deallocation routines
  22  */
  23
  24 /*
  25  * The free blocks are managed by bitmaps.  A file system contains several
  26  * blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
  27  * block for inodes, N blocks for the inode table and data blocks.
  28  *
  29  * The file system contains group descriptors which are located after the
  30  * super block.  Each descriptor contains the number of the bitmap block and
  31  * the free blocks count in the block.  The descriptors are loaded in memory
  32  * when a file system is mounted (see ext2_read_super).
  33  */
  34
  35
  36 #define in_range(b, first, len)         ((b) >= (first) && (b) <= (first) + (len) - 1)
  37
  38 struct ext2_group_desc * ext2_get_group_desc(struct super_block * sb,
  39                                              unsigned int block_group,
  40                                              struct buffer_head ** bh)
  41 {
  42         unsigned long group_desc;
  43         unsigned long desc;
  44         struct ext2_group_desc * gdp;
  45
  46         if (block_group >= sb->u.ext2_sb.s_groups_count) {
  47                 ext2_error (sb, "ext2_get_group_desc",
  48                             "block_group >= groups_count - "
  49                             "block_group = %d, groups_count = %lu",
  50                             block_group, sb->u.ext2_sb.s_groups_count);
  51
  52                 return NULL;
  53         }
  54
  55         group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
  56         desc = block_group % EXT2_DESC_PER_BLOCK(sb);
  57         if (!sb->u.ext2_sb.s_group_desc[group_desc]) {
  58                 ext2_error (sb, "ext2_get_group_desc",
  59                             "Group descriptor not loaded - "
  60                             "block_group = %d, group_desc = %lu, desc = %lu",
  61                              block_group, group_desc, desc);
  62                 return NULL;
  63         }
  64
  65         gdp = (struct ext2_group_desc *)
  66               sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
  67         if (bh)
  68                 *bh = sb->u.ext2_sb.s_group_desc[group_desc];
  69         return gdp + desc;
  70 }
  71
  72 /*
  73  * Read the bitmap for a given block_group, reading into the specified
  74  * slot in the superblock's bitmap cache.
  75  *
  76  * Return >=0 on success or a -ve error code.
  77  */
  78
  79 static int read_block_bitmap (struct super_block * sb,
  80                                unsigned int block_group,
  81                                unsigned long bitmap_nr)
  82 {
  83         struct ext2_group_desc * gdp;
  84         struct buffer_head * bh = NULL;
  85         int retval = -EIO;
  86
  87         gdp = ext2_get_group_desc (sb, block_group, NULL);
  88         if (!gdp)
  89                 goto error_out;
  90         retval = 0;
  91         bh = sb_bread(sb, le32_to_cpu(gdp->bg_block_bitmap));
  92         if (!bh) {
  93                 ext2_error (sb, "read_block_bitmap",
  94                             "Cannot read block bitmap - "
  95                             "block_group = %d, block_bitmap = %lu",
  96                             block_group, (unsigned long) gdp->bg_block_bitmap);
  97                 retval = -EIO;
  98         }
  99         /*
 100          * On IO error, just leave a zero in the superblock's block pointer for
 101          * this group.  The IO will be retried next time.
 102          */
 103 error_out:
 104         sb->u.ext2_sb.s_block_bitmap_number[bitmap_nr] = block_group;
 105         sb->u.ext2_sb.s_block_bitmap[bitmap_nr] = bh;
 106         return retval;
 107 }
 108
 109 /*
 110  * load_block_bitmap loads the block bitmap for a blocks group
 111  *
 112  * It maintains a cache for the last bitmaps loaded.  This cache is managed
 113  * with a LRU algorithm.
 114  *
 115  * Notes:
 116  * 1/ There is one cache per mounted file system.
 117  * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
 118  *    this function reads the bitmap without maintaining a LRU cache.
 119  *
 120  * Return the slot used to store the bitmap, or a -ve error code.
 121  */
 122 static int __load_block_bitmap (struct super_block * sb,
 123                                 unsigned int block_group)
 124 {
 125         int i, j, retval = 0;
 126         unsigned long block_bitmap_number;
 127         struct buffer_head * block_bitmap;
 128
 129         if (block_group >= sb->u.ext2_sb.s_groups_count)
 130                 ext2_panic (sb, "load_block_bitmap",
 131                             "block_group >= groups_count - "
 132                             "block_group = %d, groups_count = %lu",
 133                             block_group, sb->u.ext2_sb.s_groups_count);
 134
 135         if (sb->u.ext2_sb.s_groups_count <= EXT2_MAX_GROUP_LOADED) {
 136                 if (sb->u.ext2_sb.s_block_bitmap[block_group]) {
 137                         if (sb->u.ext2_sb.s_block_bitmap_number[block_group] ==
 138                             block_group)
 139                                 return block_group;
 140                         ext2_error (sb, "__load_block_bitmap",
 141                                     "block_group != block_bitmap_number");
 142                 }
 143                 retval = read_block_bitmap (sb, block_group, block_group);
 144                 if (retval < 0)
 145                         return retval;
 146                 return block_group;
 147         }
 148
 149         for (i = 0; i < sb->u.ext2_sb.s_loaded_block_bitmaps &&
 150                     sb->u.ext2_sb.s_block_bitmap_number[i] != block_group; i++)
 151                 ;
 152         if (i < sb->u.ext2_sb.s_loaded_block_bitmaps &&
 153             sb->u.ext2_sb.s_block_bitmap_number[i] == block_group) {
 154                 block_bitmap_number = sb->u.ext2_sb.s_block_bitmap_number[i];
 155                 block_bitmap = sb->u.ext2_sb.s_block_bitmap[i];
 156                 for (j = i; j > 0; j--) {
 157                         sb->u.ext2_sb.s_block_bitmap_number[j] =
 158                                 sb->u.ext2_sb.s_block_bitmap_number[j - 1];
 159                         sb->u.ext2_sb.s_block_bitmap[j] =
 160                                 sb->u.ext2_sb.s_block_bitmap[j - 1];
 161                 }
 162                 sb->u.ext2_sb.s_block_bitmap_number[0] = block_bitmap_number;
 163                 sb->u.ext2_sb.s_block_bitmap[0] = block_bitmap;
 164
 165                 /*
 166                  * There's still one special case here --- if block_bitmap == 0
 167                  * then our last attempt to read the bitmap failed and we have
 168                  * just ended up caching that failure.  Try again to read it.
 169                  */
 170                 if (!block_bitmap)
 171                         retval = read_block_bitmap (sb, block_group, 0);
 172         } else {
 173                 if (sb->u.ext2_sb.s_loaded_block_bitmaps < EXT2_MAX_GROUP_LOADED)
 174                         sb->u.ext2_sb.s_loaded_block_bitmaps++;
 175                 else
 176                         brelse (sb->u.ext2_sb.s_block_bitmap[EXT2_MAX_GROUP_LOADED - 1]);
 177                 for (j = sb->u.ext2_sb.s_loaded_block_bitmaps - 1; 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                 retval = read_block_bitmap (sb, block_group, 0);
 184         }
 185         return retval;
 186 }
 187
 188 /*
 189  * Load the block bitmap for a given block group.  First of all do a couple
 190  * of fast lookups for common cases and then pass the request onto the guts
 191  * of the bitmap loader.
 192  *
 193  * Return the slot number of the group in the superblock bitmap cache's on
 194  * success, or a -ve error code.
 195  *
 196  * There is still one inconsistency here --- if the number of groups in this
 197  * filesystems is <= EXT2_MAX_GROUP_LOADED, then we have no way of
 198  * differentiating between a group for which we have never performed a bitmap
 199  * IO request, and a group for which the last bitmap read request failed.
 200  */
 201 static inline int load_block_bitmap (struct super_block * sb,
 202                                      unsigned int block_group)
 203 {
 204         int slot;
 205
 206         /*
 207          * Do the lookup for the slot.  First of all, check if we're asking
 208          * for the same slot as last time, and did we succeed that last time?
 209          */
 210         if (sb->u.ext2_sb.s_loaded_block_bitmaps > 0 &&
 211             sb->u.ext2_sb.s_block_bitmap_number[0] == block_group &&
 212             sb->u.ext2_sb.s_block_bitmap[0]) {
 213                 return 0;
 214         }
 215         /*
 216          * Or can we do a fast lookup based on a loaded group on a filesystem
 217          * small enough to be mapped directly into the superblock?
 218          */
 219         else if (sb->u.ext2_sb.s_groups_count <= EXT2_MAX_GROUP_LOADED &&
 220                  sb->u.ext2_sb.s_block_bitmap_number[block_group] == block_group &&
 221                  sb->u.ext2_sb.s_block_bitmap[block_group]) {
 222                 slot = block_group;
 223         }
 224         /*
 225          * If not, then do a full lookup for this block group.
 226          */
 227         else {
 228                 slot = __load_block_bitmap (sb, block_group);
 229         }
 230
 231         /*
 232          * <0 means we just got an error
 233          */
 234         if (slot < 0)
 235                 return slot;
 236
 237         /*
 238          * If it's a valid slot, we may still have cached a previous IO error,
 239          * in which case the bh in the superblock cache will be zero.
 240          */
 241         if (!sb->u.ext2_sb.s_block_bitmap[slot])
 242                 return -EIO;
 243
 244         /*
 245          * Must have been read in OK to get this far.
 246          */
 247         return slot;
 248 }
 249
 250 /* Free given blocks, update quota and i_blocks field */
 251 void ext2_free_blocks (struct inode * inode, unsigned long block,
 252                        unsigned long count)
 253 {
 254         struct buffer_head * bh;
 255         struct buffer_head * bh2;
 256         unsigned long block_group;
 257         unsigned long bit;
 258         unsigned long i;
 259         int bitmap_nr;
 260         unsigned long overflow;
 261         struct super_block * sb;
 262         struct ext2_group_desc * gdp;
 263         struct ext2_super_block * es;
 264
 265         sb = inode->i_sb;
 266         if (!sb) {
 267                 printk ("ext2_free_blocks: nonexistent device");
 268                 return;
 269         }
 270         lock_super (sb);
 271         es = sb->u.ext2_sb.s_es;
 272         if (block < le32_to_cpu(es->s_first_data_block) ||
 273             (block + count) > le32_to_cpu(es->s_blocks_count)) {
 274                 ext2_error (sb, "ext2_free_blocks",
 275                             "Freeing blocks not in datazone - "
 276                             "block = %lu, count = %lu", block, count);
 277                 goto error_return;
 278         }
 279
 280         ext2_debug ("freeing block(s) %lu-%lu\n", block, block + count - 1);
 281
 282 do_more:
 283         overflow = 0;
 284         block_group = (block - le32_to_cpu(es->s_first_data_block)) /
 285                       EXT2_BLOCKS_PER_GROUP(sb);
 286         bit = (block - le32_to_cpu(es->s_first_data_block)) %
 287                       EXT2_BLOCKS_PER_GROUP(sb);
 288         /*
 289          * Check to see if we are freeing blocks across a group
 290          * boundary.
 291          */
 292         if (bit + count > EXT2_BLOCKS_PER_GROUP(sb)) {
 293                 overflow = bit + count - EXT2_BLOCKS_PER_GROUP(sb);
 294                 count -= overflow;
 295         }
 296         bitmap_nr = load_block_bitmap (sb, block_group);
 297         if (bitmap_nr < 0)
 298                 goto error_return;
 299
 300         bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
 301         gdp = ext2_get_group_desc (sb, block_group, &bh2);
 302         if (!gdp)
 303                 goto error_return;
 304
 305         if (in_range (le32_to_cpu(gdp->bg_block_bitmap), block, count) ||
 306             in_range (le32_to_cpu(gdp->bg_inode_bitmap), block, count) ||
 307             in_range (block, le32_to_cpu(gdp->bg_inode_table),
 308                       sb->u.ext2_sb.s_itb_per_group) ||
 309             in_range (block + count - 1, le32_to_cpu(gdp->bg_inode_table),
 310                       sb->u.ext2_sb.s_itb_per_group))
 311                 ext2_error (sb, "ext2_free_blocks",
 312                             "Freeing blocks in system zones - "
 313                             "Block = %lu, count = %lu",
 314                             block, count);
 315
 316         for (i = 0; i < count; i++) {
 317                 if (!ext2_clear_bit (bit + i, bh->b_data))
 318                         ext2_error (sb, "ext2_free_blocks",
 319                                       "bit already cleared for block %lu",
 320                                       block + i);
 321                 else {
 322                         DQUOT_FREE_BLOCK(inode, 1);
 323                         gdp->bg_free_blocks_count =
 324                                 cpu_to_le16(le16_to_cpu(gdp->bg_free_blocks_count)+1);
 325                         es->s_free_blocks_count =
 326                                 cpu_to_le32(le32_to_cpu(es->s_free_blocks_count)+1);
 327                 }
 328         }
 329
 330         mark_buffer_dirty(bh2);
 331         mark_buffer_dirty(sb->u.ext2_sb.s_sbh);
 332
 333         mark_buffer_dirty(bh);
 334         if (sb->s_flags & MS_SYNCHRONOUS) {
 335                 ll_rw_block (WRITE, 1, &bh);
 336                 wait_on_buffer (bh);
 337         }
 338         if (overflow) {
 339                 block += count;
 340                 count = overflow;
 341                 goto do_more;
 342         }
 343         sb->s_dirt = 1;
 344 error_return:
 345         unlock_super (sb);
 346         return;
 347 }
 348
 349 /*
 350  * ext2_new_block uses a goal block to assist allocation.  If the goal is
 351  * free, or there is a free block within 32 blocks of the goal, that block
 352  * is allocated.  Otherwise a forward search is made for a free block; within
 353  * each block group the search first looks for an entire free byte in the block
 354  * bitmap, and then for any free bit if that fails.
 355  * This function also updates quota and i_blocks field.
 356  */
 357 int ext2_new_block (struct inode * inode, unsigned long goal,
 358     u32 * prealloc_count, u32 * prealloc_block, int * err)
 359 {
 360         struct buffer_head * bh;
 361         struct buffer_head * bh2;
 362         char * p, * r;
 363         int i, j, k, tmp;
 364         int bitmap_nr;
 365         struct super_block * sb;
 366         struct ext2_group_desc * gdp;
 367         struct ext2_super_block * es;
 368 #ifdef EXT2FS_DEBUG
 369         static int goal_hits = 0, goal_attempts = 0;
 370 #endif
 371         *err = -ENOSPC;
 372         sb = inode->i_sb;
 373         if (!sb) {
 374                 printk ("ext2_new_block: nonexistent device");
 375                 return 0;
 376         }
 377
 378         lock_super (sb);
 379         es = sb->u.ext2_sb.s_es;
 380         if (le32_to_cpu(es->s_free_blocks_count) <= le32_to_cpu(es->s_r_blocks_count) &&
 381             ((sb->u.ext2_sb.s_resuid != current->fsuid) &&
 382              (sb->u.ext2_sb.s_resgid == 0 ||
 383               !in_group_p (sb->u.ext2_sb.s_resgid)) &&
 384              !capable(CAP_SYS_RESOURCE)))
 385                 goto out;
 386
 387         ext2_debug ("goal=%lu.\n", goal);
 388
 389 repeat:
 390         /*
 391          * First, test whether the goal block is free.
 392          */
 393         if (goal < le32_to_cpu(es->s_first_data_block) ||
 394             goal >= le32_to_cpu(es->s_blocks_count))
 395                 goal = le32_to_cpu(es->s_first_data_block);
 396         i = (goal - le32_to_cpu(es->s_first_data_block)) / EXT2_BLOCKS_PER_GROUP(sb);
 397         gdp = ext2_get_group_desc (sb, i, &bh2);
 398         if (!gdp)
 399                 goto io_error;
 400
 401         if (le16_to_cpu(gdp->bg_free_blocks_count) > 0) {
 402                 j = ((goal - le32_to_cpu(es->s_first_data_block)) % EXT2_BLOCKS_PER_GROUP(sb));
 403 #ifdef EXT2FS_DEBUG
 404                 if (j)
 405                         goal_attempts++;
 406 #endif
 407                 bitmap_nr = load_block_bitmap (sb, i);
 408                 if (bitmap_nr < 0)
 409                         goto io_error;
 410
 411                 bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
 412
 413                 ext2_debug ("goal is at %d:%d.\n", i, j);
 414
 415                 if (!ext2_test_bit(j, bh->b_data)) {
 416                         ext2_debug("goal bit allocated, %d hits\n",++goal_hits);
 417                         goto got_block;
 418                 }
 419                 if (j) {
 420                         /*
 421                          * The goal was occupied; search forward for a free
 422                          * block within the next XX blocks.
 423                          *
 424                          * end_goal is more or less random, but it has to be
 425                          * less than EXT2_BLOCKS_PER_GROUP. Aligning up to the
 426                          * next 64-bit boundary is simple..
 427                          */
 428                         int end_goal = (j + 63) & ~63;
 429                         j = ext2_find_next_zero_bit(bh->b_data, end_goal, j);
 430                         if (j < end_goal)
 431                                 goto got_block;
 432                 }
 433
 434                 ext2_debug ("Bit not found near goal\n");
 435
 436                 /*
 437                  * There has been no free block found in the near vicinity
 438                  * of the goal: do a search forward through the block groups,
 439                  * searching in each group first for an entire free byte in
 440                  * the bitmap and then for any free bit.
 441                  *
 442                  * Search first in the remainder of the current group; then,
 443                  * cyclicly search through the rest of the groups.
 444                  */
 445                 p = ((char *) bh->b_data) + (j >> 3);
 446                 r = memscan(p, 0, (EXT2_BLOCKS_PER_GROUP(sb) - j + 7) >> 3);
 447                 k = (r - ((char *) bh->b_data)) << 3;
 448                 if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
 449                         j = k;
 450                         goto search_back;
 451                 }
 452
 453                 k = ext2_find_next_zero_bit ((unsigned long *) bh->b_data,
 454                                         EXT2_BLOCKS_PER_GROUP(sb),
 455                                         j);
 456                 if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
 457                         j = k;
 458                         goto got_block;
 459                 }
 460         }
 461
 462         ext2_debug ("Bit not found in block group %d.\n", i);
 463
 464         /*
 465          * Now search the rest of the groups.  We assume that
 466          * i and gdp correctly point to the last group visited.
 467          */
 468         for (k = 0; k < sb->u.ext2_sb.s_groups_count; k++) {
 469                 i++;
 470                 if (i >= sb->u.ext2_sb.s_groups_count)
 471                         i = 0;
 472                 gdp = ext2_get_group_desc (sb, i, &bh2);
 473                 if (!gdp)
 474                         goto io_error;
 475                 if (le16_to_cpu(gdp->bg_free_blocks_count) > 0)
 476                         break;
 477         }
 478         if (k >= sb->u.ext2_sb.s_groups_count)
 479                 goto out;
 480         bitmap_nr = load_block_bitmap (sb, i);
 481         if (bitmap_nr < 0)
 482                 goto io_error;
 483
 484         bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
 485         r = memscan(bh->b_data, 0, EXT2_BLOCKS_PER_GROUP(sb) >> 3);
 486         j = (r - bh->b_data) << 3;
 487         if (j < EXT2_BLOCKS_PER_GROUP(sb))
 488                 goto search_back;
 489         else
 490                 j = ext2_find_first_zero_bit ((unsigned long *) bh->b_data,
 491                                          EXT2_BLOCKS_PER_GROUP(sb));
 492         if (j >= EXT2_BLOCKS_PER_GROUP(sb)) {
 493                 ext2_error (sb, "ext2_new_block",
 494                             "Free blocks count corrupted for block group %d", i);
 495                 goto out;
 496         }
 497
 498 search_back:
 499         /*
 500          * We have succeeded in finding a free byte in the block
 501          * bitmap.  Now search backwards up to 7 bits to find the
 502          * start of this group of free blocks.
 503          */
 504         for (k = 0; k < 7 && j > 0 && !ext2_test_bit (j - 1, bh->b_data); k++, j--);
 505
 506 got_block:
 507
 508         ext2_debug ("using block group %d(%d)\n", i, gdp->bg_free_blocks_count);
 509
 510         /*
 511          * Check quota for allocation of this block.
 512          */
 513         if(DQUOT_ALLOC_BLOCK(inode, 1)) {
 514                 *err = -EDQUOT;
 515                 goto out;
 516         }
 517
 518         tmp = j + i * EXT2_BLOCKS_PER_GROUP(sb) + le32_to_cpu(es->s_first_data_block);
 519
 520         if (tmp == le32_to_cpu(gdp->bg_block_bitmap) ||
 521             tmp == le32_to_cpu(gdp->bg_inode_bitmap) ||
 522             in_range (tmp, le32_to_cpu(gdp->bg_inode_table),
 523                       sb->u.ext2_sb.s_itb_per_group))
 524                 ext2_error (sb, "ext2_new_block",
 525                             "Allocating block in system zone - "
 526                             "block = %u", tmp);
 527
 528         if (ext2_set_bit (j, bh->b_data)) {
 529                 ext2_warning (sb, "ext2_new_block",
 530                               "bit already set for block %d", j);
 531                 DQUOT_FREE_BLOCK(inode, 1);
 532                 goto repeat;
 533         }
 534
 535         ext2_debug ("found bit %d\n", j);
 536
 537         /*
 538          * Do block preallocation now if required.
 539          */
 540 #ifdef EXT2_PREALLOCATE
 541         /* Writer: ->i_prealloc* */
 542         if (prealloc_count && !*prealloc_count) {
 543                 int     prealloc_goal;
 544                 unsigned long next_block = tmp + 1;
 545
 546                 prealloc_goal = es->s_prealloc_blocks ?
 547                         es->s_prealloc_blocks : EXT2_DEFAULT_PREALLOC_BLOCKS;
 548
 549                 *prealloc_block = next_block;
 550                 /* Writer: end */
 551                 for (k = 1;
 552                      k < prealloc_goal && (j + k) < EXT2_BLOCKS_PER_GROUP(sb);
 553                      k++, next_block++) {
 554                         if (DQUOT_PREALLOC_BLOCK(inode, 1))
 555                                 break;
 556                         /* Writer: ->i_prealloc* */
 557                         if (*prealloc_block + *prealloc_count != next_block ||
 558                             ext2_set_bit (j + k, bh->b_data)) {
 559                                 /* Writer: end */
 560                                 DQUOT_FREE_BLOCK(inode, 1);
 561                                 break;
 562                         }
 563                         (*prealloc_count)++;
 564                         /* Writer: end */
 565                 }
 566                 /*
 567                  * As soon as we go for per-group spinlocks we'll need these
 568                  * done inside the loop above.
 569                  */
 570                 gdp->bg_free_blocks_count =
 571                         cpu_to_le16(le16_to_cpu(gdp->bg_free_blocks_count) -
 572                                (k - 1));
 573                 es->s_free_blocks_count =
 574                         cpu_to_le32(le32_to_cpu(es->s_free_blocks_count) -
 575                                (k - 1));
 576                 ext2_debug ("Preallocated a further %lu bits.\n",
 577                                (k - 1));
 578         }
 579 #endif
 580
 581         j = tmp;
 582
 583         mark_buffer_dirty(bh);
 584         if (sb->s_flags & MS_SYNCHRONOUS) {
 585                 ll_rw_block (WRITE, 1, &bh);
 586                 wait_on_buffer (bh);
 587         }
 588
 589         if (j >= le32_to_cpu(es->s_blocks_count)) {
 590                 ext2_error (sb, "ext2_new_block",
 591                             "block(%d) >= blocks count(%d) - "
 592                             "block_group = %d, es == %p ",j,
 593                         le32_to_cpu(es->s_blocks_count), i, es);
 594                 goto out;
 595         }
 596
 597         ext2_debug ("allocating block %d. "
 598                     "Goal hits %d of %d.\n", j, goal_hits, goal_attempts);
 599
 600         gdp->bg_free_blocks_count = cpu_to_le16(le16_to_cpu(gdp->bg_free_blocks_count) - 1);
 601         mark_buffer_dirty(bh2);
 602         es->s_free_blocks_count = cpu_to_le32(le32_to_cpu(es->s_free_blocks_count) - 1);
 603         mark_buffer_dirty(sb->u.ext2_sb.s_sbh);
 604         sb->s_dirt = 1;
 605         unlock_super (sb);
 606         *err = 0;
 607         return j;
 608
 609 io_error:
 610         *err = -EIO;
 611 out:
 612         unlock_super (sb);
 613         return 0;
 614
 615 }
 616
 617 unsigned long ext2_count_free_blocks (struct super_block * sb)
 618 {
 619 #ifdef EXT2FS_DEBUG
 620         struct ext2_super_block * es;
 621         unsigned long desc_count, bitmap_count, x;
 622         int bitmap_nr;
 623         struct ext2_group_desc * gdp;
 624         int i;
 625
 626         lock_super (sb);
 627         es = sb->u.ext2_sb.s_es;
 628         desc_count = 0;
 629         bitmap_count = 0;
 630         gdp = NULL;
 631         for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
 632                 gdp = ext2_get_group_desc (sb, i, NULL);
 633                 if (!gdp)
 634                         continue;
 635                 desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
 636                 bitmap_nr = load_block_bitmap (sb, i);
 637                 if (bitmap_nr < 0)
 638                         continue;
 639
 640                 x = ext2_count_free (sb->u.ext2_sb.s_block_bitmap[bitmap_nr],
 641                                      sb->s_blocksize);
 642                 printk ("group %d: stored = %d, counted = %lu\n",
 643                         i, le16_to_cpu(gdp->bg_free_blocks_count), x);
 644                 bitmap_count += x;
 645         }
 646         printk("ext2_count_free_blocks: stored = %lu, computed = %lu, %lu\n",
 647                le32_to_cpu(es->s_free_blocks_count), desc_count, bitmap_count);
 648         unlock_super (sb);
 649         return bitmap_count;
 650 #else
 651         return le32_to_cpu(sb->u.ext2_sb.s_es->s_free_blocks_count);
 652 #endif
 653 }
 654
 655 static inline int block_in_use (unsigned long block,
 656                                 struct super_block * sb,
 657                                 unsigned char * map)
 658 {
 659         return ext2_test_bit ((block - le32_to_cpu(sb->u.ext2_sb.s_es->s_first_data_block)) %
 660                          EXT2_BLOCKS_PER_GROUP(sb), map);
 661 }
 662
 663 static inline int test_root(int a, int b)
 664 {
 665         if (a == 0)
 666                 return 1;
 667         while (1) {
 668                 if (a == 1)
 669                         return 1;
 670                 if (a % b)
 671                         return 0;
 672                 a = a / b;
 673         }
 674 }
 675
 676 int ext2_group_sparse(int group)
 677 {
 678         return (test_root(group, 3) || test_root(group, 5) ||
 679                 test_root(group, 7));
 680 }
 681
 682 /**
 683  *      ext2_bg_has_super - number of blocks used by the superblock in group
 684  *      @sb: superblock for filesystem
 685  *      @group: group number to check
 686  *
 687  *      Return the number of blocks used by the superblock (primary or backup)
 688  *      in this group.  Currently this will be only 0 or 1.
 689  */
 690 int ext2_bg_has_super(struct super_block *sb, int group)
 691 {
 692         if (EXT2_HAS_RO_COMPAT_FEATURE(sb,EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER)&&
 693             !ext2_group_sparse(group))
 694                 return 0;
 695         return 1;
 696 }
 697
 698 /**
 699  *      ext2_bg_num_gdb - number of blocks used by the group table in group
 700  *      @sb: superblock for filesystem
 701  *      @group: group number to check
 702  *
 703  *      Return the number of blocks used by the group descriptor table
 704  *      (primary or backup) in this group.  In the future there may be a
 705  *      different number of descriptor blocks in each group.
 706  */
 707 unsigned long ext2_bg_num_gdb(struct super_block *sb, int group)
 708 {
 709         if (EXT2_HAS_RO_COMPAT_FEATURE(sb,EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER)&&
 710             !ext2_group_sparse(group))
 711                 return 0;
 712         return EXT2_SB(sb)->s_gdb_count;
 713 }
 714
 715 #ifdef CONFIG_EXT2_CHECK
 716 /* Called at mount-time, super-block is locked */
 717 void ext2_check_blocks_bitmap (struct super_block * sb)
 718 {
 719         struct buffer_head * bh;
 720         struct ext2_super_block * es;
 721         unsigned long desc_count, bitmap_count, x, j;
 722         unsigned long desc_blocks;
 723         int bitmap_nr;
 724         struct ext2_group_desc * gdp;
 725         int i;
 726
 727         es = sb->u.ext2_sb.s_es;
 728         desc_count = 0;
 729         bitmap_count = 0;
 730         gdp = NULL;
 731         for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
 732                 gdp = ext2_get_group_desc (sb, i, NULL);
 733                 if (!gdp)
 734                         continue;
 735                 desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
 736                 bitmap_nr = load_block_bitmap (sb, i);
 737                 if (bitmap_nr < 0)
 738                         continue;
 739
 740                 bh = EXT2_SB(sb)->s_block_bitmap[bitmap_nr];
 741
 742                 if (ext2_bg_has_super(sb, i) && !ext2_test_bit(0, bh->b_data))
 743                         ext2_error(sb, __FUNCTION__,
 744                                    "Superblock in group %d is marked free", i);
 745
 746                 desc_blocks = ext2_bg_num_gdb(sb, i);
 747                 for (j = 0; j < desc_blocks; j++)
 748                         if (!ext2_test_bit(j + 1, bh->b_data))
 749                                 ext2_error(sb, __FUNCTION__,
 750                                            "Descriptor block #%ld in group "
 751                                            "%d is marked free", j, i);
 752
 753                 if (!block_in_use (le32_to_cpu(gdp->bg_block_bitmap), sb, bh->b_data))
 754                         ext2_error (sb, "ext2_check_blocks_bitmap",
 755                                     "Block bitmap for group %d is marked free",
 756                                     i);
 757
 758                 if (!block_in_use (le32_to_cpu(gdp->bg_inode_bitmap), sb, bh->b_data))
 759                         ext2_error (sb, "ext2_check_blocks_bitmap",
 760                                     "Inode bitmap for group %d is marked free",
 761                                     i);
 762
 763                 for (j = 0; j < sb->u.ext2_sb.s_itb_per_group; j++)
 764                         if (!block_in_use (le32_to_cpu(gdp->bg_inode_table) + j, sb, bh->b_data))
 765                                 ext2_error (sb, "ext2_check_blocks_bitmap",
 766                                             "Block #%ld of the inode table in "
 767                                             "group %d is marked free", j, i);
 768
 769                 x = ext2_count_free (bh, sb->s_blocksize);
 770                 if (le16_to_cpu(gdp->bg_free_blocks_count) != x)
 771                         ext2_error (sb, "ext2_check_blocks_bitmap",
 772                                     "Wrong free blocks count for group %d, "
 773                                     "stored = %d, counted = %lu", i,
 774                                     le16_to_cpu(gdp->bg_free_blocks_count), x);
 775                 bitmap_count += x;
 776         }
 777         if (le32_to_cpu(es->s_free_blocks_count) != bitmap_count)
 778                 ext2_error (sb, "ext2_check_blocks_bitmap",
 779                             "Wrong free blocks count in super block, "
 780                             "stored = %lu, counted = %lu",
 781                             (unsigned long) le32_to_cpu(es->s_free_blocks_count), bitmap_count);
 782 }
 783 #endif