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 38struct 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 79static 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 */ 103error_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 */ 122static 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 */ 201static 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 */ 251void 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 282do_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; 344error_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 */ 357int 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 389repeat: 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 498search_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 506got_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 609io_error: 610 *err = -EIO; 611out: 612 unlock_super (sb); 613 return 0; 614 615} 616 617unsigned 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 655static 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 663static 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 676int 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 */ 690int 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 */ 707unsigned 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 */ 717void 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 784