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@redhat.com), 1993 10 * Big-endian to little-endian byte-swapping/bitmaps by 11 * David S. Miller (davem@caip.rutgers.edu), 1995 12 */ 13 14#include "ext2.h" 15#include <linux/quotaops.h> 16#include <linux/slab.h> 17#include <linux/sched.h> 18#include <linux/buffer_head.h> 19#include <linux/capability.h> 20 21/* 22 * balloc.c contains the blocks allocation and deallocation routines 23 */ 24 25/* 26 * The free blocks are managed by bitmaps. A file system contains several 27 * blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap 28 * block for inodes, N blocks for the inode table and data blocks. 29 * 30 * The file system contains group descriptors which are located after the 31 * super block. Each descriptor contains the number of the bitmap block and 32 * the free blocks count in the block. The descriptors are loaded in memory 33 * when a file system is mounted (see ext2_fill_super). 34 */ 35 36 37#define in_range(b, first, len) ((b) >= (first) && (b) <= (first) + (len) - 1) 38 39struct ext2_group_desc * ext2_get_group_desc(struct super_block * sb, 40 unsigned int block_group, 41 struct buffer_head ** bh) 42{ 43 unsigned long group_desc; 44 unsigned long offset; 45 struct ext2_group_desc * desc; 46 struct ext2_sb_info *sbi = EXT2_SB(sb); 47 48 if (block_group >= sbi->s_groups_count) { 49 ext2_error (sb, "ext2_get_group_desc", 50 "block_group >= groups_count - " 51 "block_group = %d, groups_count = %lu", 52 block_group, sbi->s_groups_count); 53 54 return NULL; 55 } 56 57 group_desc = block_group >> EXT2_DESC_PER_BLOCK_BITS(sb); 58 offset = block_group & (EXT2_DESC_PER_BLOCK(sb) - 1); 59 if (!sbi->s_group_desc[group_desc]) { 60 ext2_error (sb, "ext2_get_group_desc", 61 "Group descriptor not loaded - " 62 "block_group = %d, group_desc = %lu, desc = %lu", 63 block_group, group_desc, offset); 64 return NULL; 65 } 66 67 desc = (struct ext2_group_desc *) sbi->s_group_desc[group_desc]->b_data; 68 if (bh) 69 *bh = sbi->s_group_desc[group_desc]; 70 return desc + offset; 71} 72 73static int ext2_valid_block_bitmap(struct super_block *sb, 74 struct ext2_group_desc *desc, 75 unsigned int block_group, 76 struct buffer_head *bh) 77{ 78 ext2_grpblk_t offset; 79 ext2_grpblk_t next_zero_bit; 80 ext2_fsblk_t bitmap_blk; 81 ext2_fsblk_t group_first_block; 82 83 group_first_block = ext2_group_first_block_no(sb, block_group); 84 85 /* check whether block bitmap block number is set */ 86 bitmap_blk = le32_to_cpu(desc->bg_block_bitmap); 87 offset = bitmap_blk - group_first_block; 88 if (!ext2_test_bit(offset, bh->b_data)) 89 /* bad block bitmap */ 90 goto err_out; 91 92 /* check whether the inode bitmap block number is set */ 93 bitmap_blk = le32_to_cpu(desc->bg_inode_bitmap); 94 offset = bitmap_blk - group_first_block; 95 if (!ext2_test_bit(offset, bh->b_data)) 96 /* bad block bitmap */ 97 goto err_out; 98 99 /* check whether the inode table block number is set */ 100 bitmap_blk = le32_to_cpu(desc->bg_inode_table); 101 offset = bitmap_blk - group_first_block; 102 next_zero_bit = ext2_find_next_zero_bit(bh->b_data, 103 offset + EXT2_SB(sb)->s_itb_per_group, 104 offset); 105 if (next_zero_bit >= offset + EXT2_SB(sb)->s_itb_per_group) 106 /* good bitmap for inode tables */ 107 return 1; 108 109err_out: 110 ext2_error(sb, __func__, 111 "Invalid block bitmap - " 112 "block_group = %d, block = %lu", 113 block_group, bitmap_blk); 114 return 0; 115} 116 117/* 118 * Read the bitmap for a given block_group,and validate the 119 * bits for block/inode/inode tables are set in the bitmaps 120 * 121 * Return buffer_head on success or NULL in case of failure. 122 */ 123static struct buffer_head * 124read_block_bitmap(struct super_block *sb, unsigned int block_group) 125{ 126 struct ext2_group_desc * desc; 127 struct buffer_head * bh = NULL; 128 ext2_fsblk_t bitmap_blk; 129 130 desc = ext2_get_group_desc(sb, block_group, NULL); 131 if (!desc) 132 return NULL; 133 bitmap_blk = le32_to_cpu(desc->bg_block_bitmap); 134 bh = sb_getblk(sb, bitmap_blk); 135 if (unlikely(!bh)) { 136 ext2_error(sb, __func__, 137 "Cannot read block bitmap - " 138 "block_group = %d, block_bitmap = %u", 139 block_group, le32_to_cpu(desc->bg_block_bitmap)); 140 return NULL; 141 } 142 if (likely(bh_uptodate_or_lock(bh))) 143 return bh; 144 145 if (bh_submit_read(bh) < 0) { 146 brelse(bh); 147 ext2_error(sb, __func__, 148 "Cannot read block bitmap - " 149 "block_group = %d, block_bitmap = %u", 150 block_group, le32_to_cpu(desc->bg_block_bitmap)); 151 return NULL; 152 } 153 154 ext2_valid_block_bitmap(sb, desc, block_group, bh); 155 /* 156 * file system mounted not to panic on error, continue with corrupt 157 * bitmap 158 */ 159 return bh; 160} 161 162static void release_blocks(struct super_block *sb, int count) 163{ 164 if (count) { 165 struct ext2_sb_info *sbi = EXT2_SB(sb); 166 167 percpu_counter_add(&sbi->s_freeblocks_counter, count); 168 sb->s_dirt = 1; 169 } 170} 171 172static void group_adjust_blocks(struct super_block *sb, int group_no, 173 struct ext2_group_desc *desc, struct buffer_head *bh, int count) 174{ 175 if (count) { 176 struct ext2_sb_info *sbi = EXT2_SB(sb); 177 unsigned free_blocks; 178 179 spin_lock(sb_bgl_lock(sbi, group_no)); 180 free_blocks = le16_to_cpu(desc->bg_free_blocks_count); 181 desc->bg_free_blocks_count = cpu_to_le16(free_blocks + count); 182 spin_unlock(sb_bgl_lock(sbi, group_no)); 183 sb->s_dirt = 1; 184 mark_buffer_dirty(bh); 185 } 186} 187 188/* 189 * The reservation window structure operations 190 * -------------------------------------------- 191 * Operations include: 192 * dump, find, add, remove, is_empty, find_next_reservable_window, etc. 193 * 194 * We use a red-black tree to represent per-filesystem reservation 195 * windows. 196 * 197 */ 198 199/** 200 * __rsv_window_dump() -- Dump the filesystem block allocation reservation map 201 * @rb_root: root of per-filesystem reservation rb tree 202 * @verbose: verbose mode 203 * @fn: function which wishes to dump the reservation map 204 * 205 * If verbose is turned on, it will print the whole block reservation 206 * windows(start, end). Otherwise, it will only print out the "bad" windows, 207 * those windows that overlap with their immediate neighbors. 208 */ 209static void __rsv_window_dump(struct rb_root *root, int verbose, 210 const char *fn) 211{ 212 struct rb_node *n; 213 struct ext2_reserve_window_node *rsv, *prev; 214 int bad; 215 216restart: 217 n = rb_first(root); 218 bad = 0; 219 prev = NULL; 220 221 printk("Block Allocation Reservation Windows Map (%s):\n", fn); 222 while (n) { 223 rsv = rb_entry(n, struct ext2_reserve_window_node, rsv_node); 224 if (verbose) 225 printk("reservation window 0x%p " 226 "start: %lu, end: %lu\n", 227 rsv, rsv->rsv_start, rsv->rsv_end); 228 if (rsv->rsv_start && rsv->rsv_start >= rsv->rsv_end) { 229 printk("Bad reservation %p (start >= end)\n", 230 rsv); 231 bad = 1; 232 } 233 if (prev && prev->rsv_end >= rsv->rsv_start) { 234 printk("Bad reservation %p (prev->end >= start)\n", 235 rsv); 236 bad = 1; 237 } 238 if (bad) { 239 if (!verbose) { 240 printk("Restarting reservation walk in verbose mode\n"); 241 verbose = 1; 242 goto restart; 243 } 244 } 245 n = rb_next(n); 246 prev = rsv; 247 } 248 printk("Window map complete.\n"); 249 BUG_ON(bad); 250} 251#define rsv_window_dump(root, verbose) \ 252 __rsv_window_dump((root), (verbose), __func__) 253 254/** 255 * goal_in_my_reservation() 256 * @rsv: inode's reservation window 257 * @grp_goal: given goal block relative to the allocation block group 258 * @group: the current allocation block group 259 * @sb: filesystem super block 260 * 261 * Test if the given goal block (group relative) is within the file's 262 * own block reservation window range. 263 * 264 * If the reservation window is outside the goal allocation group, return 0; 265 * grp_goal (given goal block) could be -1, which means no specific 266 * goal block. In this case, always return 1. 267 * If the goal block is within the reservation window, return 1; 268 * otherwise, return 0; 269 */ 270static int 271goal_in_my_reservation(struct ext2_reserve_window *rsv, ext2_grpblk_t grp_goal, 272 unsigned int group, struct super_block * sb) 273{ 274 ext2_fsblk_t group_first_block, group_last_block; 275 276 group_first_block = ext2_group_first_block_no(sb, group); 277 group_last_block = group_first_block + EXT2_BLOCKS_PER_GROUP(sb) - 1; 278 279 if ((rsv->_rsv_start > group_last_block) || 280 (rsv->_rsv_end < group_first_block)) 281 return 0; 282 if ((grp_goal >= 0) && ((grp_goal + group_first_block < rsv->_rsv_start) 283 || (grp_goal + group_first_block > rsv->_rsv_end))) 284 return 0; 285 return 1; 286} 287 288/** 289 * search_reserve_window() 290 * @rb_root: root of reservation tree 291 * @goal: target allocation block 292 * 293 * Find the reserved window which includes the goal, or the previous one 294 * if the goal is not in any window. 295 * Returns NULL if there are no windows or if all windows start after the goal. 296 */ 297static struct ext2_reserve_window_node * 298search_reserve_window(struct rb_root *root, ext2_fsblk_t goal) 299{ 300 struct rb_node *n = root->rb_node; 301 struct ext2_reserve_window_node *rsv; 302 303 if (!n) 304 return NULL; 305 306 do { 307 rsv = rb_entry(n, struct ext2_reserve_window_node, rsv_node); 308 309 if (goal < rsv->rsv_start) 310 n = n->rb_left; 311 else if (goal > rsv->rsv_end) 312 n = n->rb_right; 313 else 314 return rsv; 315 } while (n); 316 /* 317 * We've fallen off the end of the tree: the goal wasn't inside 318 * any particular node. OK, the previous node must be to one 319 * side of the interval containing the goal. If it's the RHS, 320 * we need to back up one. 321 */ 322 if (rsv->rsv_start > goal) { 323 n = rb_prev(&rsv->rsv_node); 324 rsv = rb_entry(n, struct ext2_reserve_window_node, rsv_node); 325 } 326 return rsv; 327} 328 329/* 330 * ext2_rsv_window_add() -- Insert a window to the block reservation rb tree. 331 * @sb: super block 332 * @rsv: reservation window to add 333 * 334 * Must be called with rsv_lock held. 335 */ 336void ext2_rsv_window_add(struct super_block *sb, 337 struct ext2_reserve_window_node *rsv) 338{ 339 struct rb_root *root = &EXT2_SB(sb)->s_rsv_window_root; 340 struct rb_node *node = &rsv->rsv_node; 341 ext2_fsblk_t start = rsv->rsv_start; 342 343 struct rb_node ** p = &root->rb_node; 344 struct rb_node * parent = NULL; 345 struct ext2_reserve_window_node *this; 346 347 while (*p) 348 { 349 parent = *p; 350 this = rb_entry(parent, struct ext2_reserve_window_node, rsv_node); 351 352 if (start < this->rsv_start) 353 p = &(*p)->rb_left; 354 else if (start > this->rsv_end) 355 p = &(*p)->rb_right; 356 else { 357 rsv_window_dump(root, 1); 358 BUG(); 359 } 360 } 361 362 rb_link_node(node, parent, p); 363 rb_insert_color(node, root); 364} 365 366/** 367 * rsv_window_remove() -- unlink a window from the reservation rb tree 368 * @sb: super block 369 * @rsv: reservation window to remove 370 * 371 * Mark the block reservation window as not allocated, and unlink it 372 * from the filesystem reservation window rb tree. Must be called with 373 * rsv_lock held. 374 */ 375static void rsv_window_remove(struct super_block *sb, 376 struct ext2_reserve_window_node *rsv) 377{ 378 rsv->rsv_start = EXT2_RESERVE_WINDOW_NOT_ALLOCATED; 379 rsv->rsv_end = EXT2_RESERVE_WINDOW_NOT_ALLOCATED; 380 rsv->rsv_alloc_hit = 0; 381 rb_erase(&rsv->rsv_node, &EXT2_SB(sb)->s_rsv_window_root); 382} 383 384/* 385 * rsv_is_empty() -- Check if the reservation window is allocated. 386 * @rsv: given reservation window to check 387 * 388 * returns 1 if the end block is EXT2_RESERVE_WINDOW_NOT_ALLOCATED. 389 */ 390static inline int rsv_is_empty(struct ext2_reserve_window *rsv) 391{ 392 /* a valid reservation end block could not be 0 */ 393 return (rsv->_rsv_end == EXT2_RESERVE_WINDOW_NOT_ALLOCATED); 394} 395 396/** 397 * ext2_init_block_alloc_info() 398 * @inode: file inode structure 399 * 400 * Allocate and initialize the reservation window structure, and 401 * link the window to the ext2 inode structure at last 402 * 403 * The reservation window structure is only dynamically allocated 404 * and linked to ext2 inode the first time the open file 405 * needs a new block. So, before every ext2_new_block(s) call, for 406 * regular files, we should check whether the reservation window 407 * structure exists or not. In the latter case, this function is called. 408 * Fail to do so will result in block reservation being turned off for that 409 * open file. 410 * 411 * This function is called from ext2_get_blocks_handle(), also called 412 * when setting the reservation window size through ioctl before the file 413 * is open for write (needs block allocation). 414 * 415 * Needs truncate_mutex protection prior to calling this function. 416 */ 417void ext2_init_block_alloc_info(struct inode *inode) 418{ 419 struct ext2_inode_info *ei = EXT2_I(inode); 420 struct ext2_block_alloc_info *block_i = ei->i_block_alloc_info; 421 struct super_block *sb = inode->i_sb; 422 423 block_i = kmalloc(sizeof(*block_i), GFP_NOFS); 424 if (block_i) { 425 struct ext2_reserve_window_node *rsv = &block_i->rsv_window_node; 426 427 rsv->rsv_start = EXT2_RESERVE_WINDOW_NOT_ALLOCATED; 428 rsv->rsv_end = EXT2_RESERVE_WINDOW_NOT_ALLOCATED; 429 430 /* 431 * if filesystem is mounted with NORESERVATION, the goal 432 * reservation window size is set to zero to indicate 433 * block reservation is off 434 */ 435 if (!test_opt(sb, RESERVATION)) 436 rsv->rsv_goal_size = 0; 437 else 438 rsv->rsv_goal_size = EXT2_DEFAULT_RESERVE_BLOCKS; 439 rsv->rsv_alloc_hit = 0; 440 block_i->last_alloc_logical_block = 0; 441 block_i->last_alloc_physical_block = 0; 442 } 443 ei->i_block_alloc_info = block_i; 444} 445 446/** 447 * ext2_discard_reservation() 448 * @inode: inode 449 * 450 * Discard(free) block reservation window on last file close, or truncate 451 * or at last iput(). 452 * 453 * It is being called in three cases: 454 * ext2_release_file(): last writer closes the file 455 * ext2_clear_inode(): last iput(), when nobody links to this file. 456 * ext2_truncate(): when the block indirect map is about to change. 457 */ 458void ext2_discard_reservation(struct inode *inode) 459{ 460 struct ext2_inode_info *ei = EXT2_I(inode); 461 struct ext2_block_alloc_info *block_i = ei->i_block_alloc_info; 462 struct ext2_reserve_window_node *rsv; 463 spinlock_t *rsv_lock = &EXT2_SB(inode->i_sb)->s_rsv_window_lock; 464 465 if (!block_i) 466 return; 467 468 rsv = &block_i->rsv_window_node; 469 if (!rsv_is_empty(&rsv->rsv_window)) { 470 spin_lock(rsv_lock); 471 if (!rsv_is_empty(&rsv->rsv_window)) 472 rsv_window_remove(inode->i_sb, rsv); 473 spin_unlock(rsv_lock); 474 } 475} 476 477/** 478 * ext2_free_blocks_sb() -- Free given blocks and update quota and i_blocks 479 * @inode: inode 480 * @block: start physcial block to free 481 * @count: number of blocks to free 482 */ 483void ext2_free_blocks (struct inode * inode, unsigned long block, 484 unsigned long count) 485{ 486 struct buffer_head *bitmap_bh = NULL; 487 struct buffer_head * bh2; 488 unsigned long block_group; 489 unsigned long bit; 490 unsigned long i; 491 unsigned long overflow; 492 struct super_block * sb = inode->i_sb; 493 struct ext2_sb_info * sbi = EXT2_SB(sb); 494 struct ext2_group_desc * desc; 495 struct ext2_super_block * es = sbi->s_es; 496 unsigned freed = 0, group_freed; 497 498 if (block < le32_to_cpu(es->s_first_data_block) || 499 block + count < block || 500 block + count > le32_to_cpu(es->s_blocks_count)) { 501 ext2_error (sb, "ext2_free_blocks", 502 "Freeing blocks not in datazone - " 503 "block = %lu, count = %lu", block, count); 504 goto error_return; 505 } 506 507 ext2_debug ("freeing block(s) %lu-%lu\n", block, block + count - 1); 508 509do_more: 510 overflow = 0; 511 block_group = (block - le32_to_cpu(es->s_first_data_block)) / 512 EXT2_BLOCKS_PER_GROUP(sb); 513 bit = (block - le32_to_cpu(es->s_first_data_block)) % 514 EXT2_BLOCKS_PER_GROUP(sb); 515 /* 516 * Check to see if we are freeing blocks across a group 517 * boundary. 518 */ 519 if (bit + count > EXT2_BLOCKS_PER_GROUP(sb)) { 520 overflow = bit + count - EXT2_BLOCKS_PER_GROUP(sb); 521 count -= overflow; 522 } 523 brelse(bitmap_bh); 524 bitmap_bh = read_block_bitmap(sb, block_group); 525 if (!bitmap_bh) 526 goto error_return; 527 528 desc = ext2_get_group_desc (sb, block_group, &bh2); 529 if (!desc) 530 goto error_return; 531 532 if (in_range (le32_to_cpu(desc->bg_block_bitmap), block, count) || 533 in_range (le32_to_cpu(desc->bg_inode_bitmap), block, count) || 534 in_range (block, le32_to_cpu(desc->bg_inode_table), 535 sbi->s_itb_per_group) || 536 in_range (block + count - 1, le32_to_cpu(desc->bg_inode_table), 537 sbi->s_itb_per_group)) { 538 ext2_error (sb, "ext2_free_blocks", 539 "Freeing blocks in system zones - " 540 "Block = %lu, count = %lu", 541 block, count); 542 goto error_return; 543 } 544 545 for (i = 0, group_freed = 0; i < count; i++) { 546 if (!ext2_clear_bit_atomic(sb_bgl_lock(sbi, block_group), 547 bit + i, bitmap_bh->b_data)) { 548 ext2_error(sb, __func__, 549 "bit already cleared for block %lu", block + i); 550 } else { 551 group_freed++; 552 } 553 } 554 555 mark_buffer_dirty(bitmap_bh); 556 if (sb->s_flags & MS_SYNCHRONOUS) 557 sync_dirty_buffer(bitmap_bh); 558 559 group_adjust_blocks(sb, block_group, desc, bh2, group_freed); 560 freed += group_freed; 561 562 if (overflow) { 563 block += count; 564 count = overflow; 565 goto do_more; 566 } 567error_return: 568 brelse(bitmap_bh); 569 release_blocks(sb, freed); 570 dquot_free_block_nodirty(inode, freed); 571} 572 573/** 574 * bitmap_search_next_usable_block() 575 * @start: the starting block (group relative) of the search 576 * @bh: bufferhead contains the block group bitmap 577 * @maxblocks: the ending block (group relative) of the reservation 578 * 579 * The bitmap search --- search forward through the actual bitmap on disk until 580 * we find a bit free. 581 */ 582static ext2_grpblk_t 583bitmap_search_next_usable_block(ext2_grpblk_t start, struct buffer_head *bh, 584 ext2_grpblk_t maxblocks) 585{ 586 ext2_grpblk_t next; 587 588 next = ext2_find_next_zero_bit(bh->b_data, maxblocks, start); 589 if (next >= maxblocks) 590 return -1; 591 return next; 592} 593 594/** 595 * find_next_usable_block() 596 * @start: the starting block (group relative) to find next 597 * allocatable block in bitmap. 598 * @bh: bufferhead contains the block group bitmap 599 * @maxblocks: the ending block (group relative) for the search 600 * 601 * Find an allocatable block in a bitmap. We perform the "most 602 * appropriate allocation" algorithm of looking for a free block near 603 * the initial goal; then for a free byte somewhere in the bitmap; 604 * then for any free bit in the bitmap. 605 */ 606static ext2_grpblk_t 607find_next_usable_block(int start, struct buffer_head *bh, int maxblocks) 608{ 609 ext2_grpblk_t here, next; 610 char *p, *r; 611 612 if (start > 0) { 613 /* 614 * The goal was occupied; search forward for a free 615 * block within the next XX blocks. 616 * 617 * end_goal is more or less random, but it has to be 618 * less than EXT2_BLOCKS_PER_GROUP. Aligning up to the 619 * next 64-bit boundary is simple.. 620 */ 621 ext2_grpblk_t end_goal = (start + 63) & ~63; 622 if (end_goal > maxblocks) 623 end_goal = maxblocks; 624 here = ext2_find_next_zero_bit(bh->b_data, end_goal, start); 625 if (here < end_goal) 626 return here; 627 ext2_debug("Bit not found near goal\n"); 628 } 629 630 here = start; 631 if (here < 0) 632 here = 0; 633 634 p = ((char *)bh->b_data) + (here >> 3); 635 r = memscan(p, 0, ((maxblocks + 7) >> 3) - (here >> 3)); 636 next = (r - ((char *)bh->b_data)) << 3; 637 638 if (next < maxblocks && next >= here) 639 return next; 640 641 here = bitmap_search_next_usable_block(here, bh, maxblocks); 642 return here; 643} 644 645/* 646 * ext2_try_to_allocate() 647 * @sb: superblock 648 * @handle: handle to this transaction 649 * @group: given allocation block group 650 * @bitmap_bh: bufferhead holds the block bitmap 651 * @grp_goal: given target block within the group 652 * @count: target number of blocks to allocate 653 * @my_rsv: reservation window 654 * 655 * Attempt to allocate blocks within a give range. Set the range of allocation 656 * first, then find the first free bit(s) from the bitmap (within the range), 657 * and at last, allocate the blocks by claiming the found free bit as allocated. 658 * 659 * To set the range of this allocation: 660 * if there is a reservation window, only try to allocate block(s) 661 * from the file's own reservation window; 662 * Otherwise, the allocation range starts from the give goal block, 663 * ends at the block group's last block. 664 * 665 * If we failed to allocate the desired block then we may end up crossing to a 666 * new bitmap. 667 */ 668static int 669ext2_try_to_allocate(struct super_block *sb, int group, 670 struct buffer_head *bitmap_bh, ext2_grpblk_t grp_goal, 671 unsigned long *count, 672 struct ext2_reserve_window *my_rsv) 673{ 674 ext2_fsblk_t group_first_block; 675 ext2_grpblk_t start, end; 676 unsigned long num = 0; 677 678 /* we do allocation within the reservation window if we have a window */ 679 if (my_rsv) { 680 group_first_block = ext2_group_first_block_no(sb, group); 681 if (my_rsv->_rsv_start >= group_first_block) 682 start = my_rsv->_rsv_start - group_first_block; 683 else 684 /* reservation window cross group boundary */ 685 start = 0; 686 end = my_rsv->_rsv_end - group_first_block + 1; 687 if (end > EXT2_BLOCKS_PER_GROUP(sb)) 688 /* reservation window crosses group boundary */ 689 end = EXT2_BLOCKS_PER_GROUP(sb); 690 if ((start <= grp_goal) && (grp_goal < end)) 691 start = grp_goal; 692 else 693 grp_goal = -1; 694 } else { 695 if (grp_goal > 0) 696 start = grp_goal; 697 else 698 start = 0; 699 end = EXT2_BLOCKS_PER_GROUP(sb); 700 } 701 702 BUG_ON(start > EXT2_BLOCKS_PER_GROUP(sb)); 703 704repeat: 705 if (grp_goal < 0) { 706 grp_goal = find_next_usable_block(start, bitmap_bh, end); 707 if (grp_goal < 0) 708 goto fail_access; 709 if (!my_rsv) { 710 int i; 711 712 for (i = 0; i < 7 && grp_goal > start && 713 !ext2_test_bit(grp_goal - 1, 714 bitmap_bh->b_data); 715 i++, grp_goal--) 716 ; 717 } 718 } 719 start = grp_goal; 720 721 if (ext2_set_bit_atomic(sb_bgl_lock(EXT2_SB(sb), group), grp_goal, 722 bitmap_bh->b_data)) { 723 /* 724 * The block was allocated by another thread, or it was 725 * allocated and then freed by another thread 726 */ 727 start++; 728 grp_goal++; 729 if (start >= end) 730 goto fail_access; 731 goto repeat; 732 } 733 num++; 734 grp_goal++; 735 while (num < *count && grp_goal < end 736 && !ext2_set_bit_atomic(sb_bgl_lock(EXT2_SB(sb), group), 737 grp_goal, bitmap_bh->b_data)) { 738 num++; 739 grp_goal++; 740 } 741 *count = num; 742 return grp_goal - num; 743fail_access: 744 *count = num; 745 return -1; 746} 747 748/** 749 * find_next_reservable_window(): 750 * find a reservable space within the given range. 751 * It does not allocate the reservation window for now: 752 * alloc_new_reservation() will do the work later. 753 * 754 * @search_head: the head of the searching list; 755 * This is not necessarily the list head of the whole filesystem 756 * 757 * We have both head and start_block to assist the search 758 * for the reservable space. The list starts from head, 759 * but we will shift to the place where start_block is, 760 * then start from there, when looking for a reservable space. 761 * 762 * @size: the target new reservation window size 763 * 764 * @group_first_block: the first block we consider to start 765 * the real search from 766 * 767 * @last_block: 768 * the maximum block number that our goal reservable space 769 * could start from. This is normally the last block in this 770 * group. The search will end when we found the start of next 771 * possible reservable space is out of this boundary. 772 * This could handle the cross boundary reservation window 773 * request. 774 * 775 * basically we search from the given range, rather than the whole 776 * reservation double linked list, (start_block, last_block) 777 * to find a free region that is of my size and has not 778 * been reserved. 779 * 780 */ 781static int find_next_reservable_window( 782 struct ext2_reserve_window_node *search_head, 783 struct ext2_reserve_window_node *my_rsv, 784 struct super_block * sb, 785 ext2_fsblk_t start_block, 786 ext2_fsblk_t last_block) 787{ 788 struct rb_node *next; 789 struct ext2_reserve_window_node *rsv, *prev; 790 ext2_fsblk_t cur; 791 int size = my_rsv->rsv_goal_size; 792 793 /* TODO: make the start of the reservation window byte-aligned */ 794 /* cur = *start_block & ~7;*/ 795 cur = start_block; 796 rsv = search_head; 797 if (!rsv) 798 return -1; 799 800 while (1) { 801 if (cur <= rsv->rsv_end) 802 cur = rsv->rsv_end + 1; 803 804 /* TODO? 805 * in the case we could not find a reservable space 806 * that is what is expected, during the re-search, we could 807 * remember what's the largest reservable space we could have 808 * and return that one. 809 * 810 * For now it will fail if we could not find the reservable 811 * space with expected-size (or more)... 812 */ 813 if (cur > last_block) 814 return -1; /* fail */ 815 816 prev = rsv; 817 next = rb_next(&rsv->rsv_node); 818 rsv = rb_entry(next,struct ext2_reserve_window_node,rsv_node); 819 820 /* 821 * Reached the last reservation, we can just append to the 822 * previous one. 823 */ 824 if (!next) 825 break; 826 827 if (cur + size <= rsv->rsv_start) { 828 /* 829 * Found a reserveable space big enough. We could 830 * have a reservation across the group boundary here 831 */ 832 break; 833 } 834 } 835 /* 836 * we come here either : 837 * when we reach the end of the whole list, 838 * and there is empty reservable space after last entry in the list. 839 * append it to the end of the list. 840 * 841 * or we found one reservable space in the middle of the list, 842 * return the reservation window that we could append to. 843 * succeed. 844 */ 845 846 if ((prev != my_rsv) && (!rsv_is_empty(&my_rsv->rsv_window))) 847 rsv_window_remove(sb, my_rsv); 848 849 /* 850 * Let's book the whole avaliable window for now. We will check the 851 * disk bitmap later and then, if there are free blocks then we adjust 852 * the window size if it's larger than requested. 853 * Otherwise, we will remove this node from the tree next time 854 * call find_next_reservable_window. 855 */ 856 my_rsv->rsv_start = cur; 857 my_rsv->rsv_end = cur + size - 1; 858 my_rsv->rsv_alloc_hit = 0; 859 860 if (prev != my_rsv) 861 ext2_rsv_window_add(sb, my_rsv); 862 863 return 0; 864} 865 866/** 867 * alloc_new_reservation()--allocate a new reservation window 868 * 869 * To make a new reservation, we search part of the filesystem 870 * reservation list (the list that inside the group). We try to 871 * allocate a new reservation window near the allocation goal, 872 * or the beginning of the group, if there is no goal. 873 * 874 * We first find a reservable space after the goal, then from 875 * there, we check the bitmap for the first free block after 876 * it. If there is no free block until the end of group, then the 877 * whole group is full, we failed. Otherwise, check if the free 878 * block is inside the expected reservable space, if so, we 879 * succeed. 880 * If the first free block is outside the reservable space, then 881 * start from the first free block, we search for next available 882 * space, and go on. 883 * 884 * on succeed, a new reservation will be found and inserted into the list 885 * It contains at least one free block, and it does not overlap with other 886 * reservation windows. 887 * 888 * failed: we failed to find a reservation window in this group 889 * 890 * @rsv: the reservation 891 * 892 * @grp_goal: The goal (group-relative). It is where the search for a 893 * free reservable space should start from. 894 * if we have a goal(goal >0 ), then start from there, 895 * no goal(goal = -1), we start from the first block 896 * of the group. 897 * 898 * @sb: the super block 899 * @group: the group we are trying to allocate in 900 * @bitmap_bh: the block group block bitmap 901 * 902 */ 903static int alloc_new_reservation(struct ext2_reserve_window_node *my_rsv, 904 ext2_grpblk_t grp_goal, struct super_block *sb, 905 unsigned int group, struct buffer_head *bitmap_bh) 906{ 907 struct ext2_reserve_window_node *search_head; 908 ext2_fsblk_t group_first_block, group_end_block, start_block; 909 ext2_grpblk_t first_free_block; 910 struct rb_root *fs_rsv_root = &EXT2_SB(sb)->s_rsv_window_root; 911 unsigned long size; 912 int ret; 913 spinlock_t *rsv_lock = &EXT2_SB(sb)->s_rsv_window_lock; 914 915 group_first_block = ext2_group_first_block_no(sb, group); 916 group_end_block = group_first_block + (EXT2_BLOCKS_PER_GROUP(sb) - 1); 917 918 if (grp_goal < 0) 919 start_block = group_first_block; 920 else 921 start_block = grp_goal + group_first_block; 922 923 size = my_rsv->rsv_goal_size; 924 925 if (!rsv_is_empty(&my_rsv->rsv_window)) { 926 /* 927 * if the old reservation is cross group boundary 928 * and if the goal is inside the old reservation window, 929 * we will come here when we just failed to allocate from 930 * the first part of the window. We still have another part 931 * that belongs to the next group. In this case, there is no 932 * point to discard our window and try to allocate a new one 933 * in this group(which will fail). we should 934 * keep the reservation window, just simply move on. 935 * 936 * Maybe we could shift the start block of the reservation 937 * window to the first block of next group. 938 */ 939 940 if ((my_rsv->rsv_start <= group_end_block) && 941 (my_rsv->rsv_end > group_end_block) && 942 (start_block >= my_rsv->rsv_start)) 943 return -1; 944 945 if ((my_rsv->rsv_alloc_hit > 946 (my_rsv->rsv_end - my_rsv->rsv_start + 1) / 2)) { 947 /* 948 * if the previously allocation hit ratio is 949 * greater than 1/2, then we double the size of 950 * the reservation window the next time, 951 * otherwise we keep the same size window 952 */ 953 size = size * 2; 954 if (size > EXT2_MAX_RESERVE_BLOCKS) 955 size = EXT2_MAX_RESERVE_BLOCKS; 956 my_rsv->rsv_goal_size= size; 957 } 958 } 959 960 spin_lock(rsv_lock); 961 /* 962 * shift the search start to the window near the goal block 963 */ 964 search_head = search_reserve_window(fs_rsv_root, start_block); 965 966 /* 967 * find_next_reservable_window() simply finds a reservable window 968 * inside the given range(start_block, group_end_block). 969 * 970 * To make sure the reservation window has a free bit inside it, we 971 * need to check the bitmap after we found a reservable window. 972 */ 973retry: 974 ret = find_next_reservable_window(search_head, my_rsv, sb, 975 start_block, group_end_block); 976 977 if (ret == -1) { 978 if (!rsv_is_empty(&my_rsv->rsv_window)) 979 rsv_window_remove(sb, my_rsv); 980 spin_unlock(rsv_lock); 981 return -1; 982 } 983 984 /* 985 * On success, find_next_reservable_window() returns the 986 * reservation window where there is a reservable space after it. 987 * Before we reserve this reservable space, we need 988 * to make sure there is at least a free block inside this region. 989 * 990 * Search the first free bit on the block bitmap. Search starts from 991 * the start block of the reservable space we just found. 992 */ 993 spin_unlock(rsv_lock); 994 first_free_block = bitmap_search_next_usable_block( 995 my_rsv->rsv_start - group_first_block, 996 bitmap_bh, group_end_block - group_first_block + 1); 997 998 if (first_free_block < 0) { 999 /* 1000 * no free block left on the bitmap, no point 1001 * to reserve the space. return failed. 1002 */ 1003 spin_lock(rsv_lock); 1004 if (!rsv_is_empty(&my_rsv->rsv_window)) 1005 rsv_window_remove(sb, my_rsv); 1006 spin_unlock(rsv_lock); 1007 return -1; /* failed */ 1008 } 1009 1010 start_block = first_free_block + group_first_block; 1011 /* 1012 * check if the first free block is within the 1013 * free space we just reserved 1014 */ 1015 if (start_block >= my_rsv->rsv_start && start_block <= my_rsv->rsv_end) 1016 return 0; /* success */ 1017 /* 1018 * if the first free bit we found is out of the reservable space 1019 * continue search for next reservable space, 1020 * start from where the free block is, 1021 * we also shift the list head to where we stopped last time 1022 */ 1023 search_head = my_rsv; 1024 spin_lock(rsv_lock); 1025 goto retry; 1026} 1027 1028/** 1029 * try_to_extend_reservation() 1030 * @my_rsv: given reservation window 1031 * @sb: super block 1032 * @size: the delta to extend 1033 * 1034 * Attempt to expand the reservation window large enough to have 1035 * required number of free blocks 1036 * 1037 * Since ext2_try_to_allocate() will always allocate blocks within 1038 * the reservation window range, if the window size is too small, 1039 * multiple blocks allocation has to stop at the end of the reservation 1040 * window. To make this more efficient, given the total number of 1041 * blocks needed and the current size of the window, we try to 1042 * expand the reservation window size if necessary on a best-effort 1043 * basis before ext2_new_blocks() tries to allocate blocks. 1044 */ 1045static void try_to_extend_reservation(struct ext2_reserve_window_node *my_rsv, 1046 struct super_block *sb, int size) 1047{ 1048 struct ext2_reserve_window_node *next_rsv; 1049 struct rb_node *next; 1050 spinlock_t *rsv_lock = &EXT2_SB(sb)->s_rsv_window_lock; 1051 1052 if (!spin_trylock(rsv_lock)) 1053 return; 1054 1055 next = rb_next(&my_rsv->rsv_node); 1056 1057 if (!next) 1058 my_rsv->rsv_end += size; 1059 else { 1060 next_rsv = rb_entry(next, struct ext2_reserve_window_node, rsv_node); 1061 1062 if ((next_rsv->rsv_start - my_rsv->rsv_end - 1) >= size) 1063 my_rsv->rsv_end += size; 1064 else 1065 my_rsv->rsv_end = next_rsv->rsv_start - 1; 1066 } 1067 spin_unlock(rsv_lock); 1068} 1069 1070/** 1071 * ext2_try_to_allocate_with_rsv() 1072 * @sb: superblock 1073 * @group: given allocation block group 1074 * @bitmap_bh: bufferhead holds the block bitmap 1075 * @grp_goal: given target block within the group 1076 * @count: target number of blocks to allocate 1077 * @my_rsv: reservation window 1078 * 1079 * This is the main function used to allocate a new block and its reservation 1080 * window. 1081 * 1082 * Each time when a new block allocation is need, first try to allocate from 1083 * its own reservation. If it does not have a reservation window, instead of 1084 * looking for a free bit on bitmap first, then look up the reservation list to 1085 * see if it is inside somebody else's reservation window, we try to allocate a 1086 * reservation window for it starting from the goal first. Then do the block 1087 * allocation within the reservation window. 1088 * 1089 * This will avoid keeping on searching the reservation list again and 1090 * again when somebody is looking for a free block (without 1091 * reservation), and there are lots of free blocks, but they are all 1092 * being reserved. 1093 * 1094 * We use a red-black tree for the per-filesystem reservation list. 1095 */ 1096static ext2_grpblk_t 1097ext2_try_to_allocate_with_rsv(struct super_block *sb, unsigned int group, 1098 struct buffer_head *bitmap_bh, ext2_grpblk_t grp_goal, 1099 struct ext2_reserve_window_node * my_rsv, 1100 unsigned long *count) 1101{ 1102 ext2_fsblk_t group_first_block, group_last_block; 1103 ext2_grpblk_t ret = 0; 1104 unsigned long num = *count; 1105 1106 /* 1107 * we don't deal with reservation when 1108 * filesystem is mounted without reservation 1109 * or the file is not a regular file 1110 * or last attempt to allocate a block with reservation turned on failed 1111 */ 1112 if (my_rsv == NULL) { 1113 return ext2_try_to_allocate(sb, group, bitmap_bh, 1114 grp_goal, count, NULL); 1115 } 1116 /* 1117 * grp_goal is a group relative block number (if there is a goal) 1118 * 0 <= grp_goal < EXT2_BLOCKS_PER_GROUP(sb) 1119 * first block is a filesystem wide block number 1120 * first block is the block number of the first block in this group 1121 */ 1122 group_first_block = ext2_group_first_block_no(sb, group); 1123 group_last_block = group_first_block + (EXT2_BLOCKS_PER_GROUP(sb) - 1); 1124 1125 /* 1126 * Basically we will allocate a new block from inode's reservation 1127 * window. 1128 * 1129 * We need to allocate a new reservation window, if: 1130 * a) inode does not have a reservation window; or 1131 * b) last attempt to allocate a block from existing reservation 1132 * failed; or 1133 * c) we come here with a goal and with a reservation window 1134 * 1135 * We do not need to allocate a new reservation window if we come here 1136 * at the beginning with a goal and the goal is inside the window, or 1137 * we don't have a goal but already have a reservation window. 1138 * then we could go to allocate from the reservation window directly. 1139 */ 1140 while (1) { 1141 if (rsv_is_empty(&my_rsv->rsv_window) || (ret < 0) || 1142 !goal_in_my_reservation(&my_rsv->rsv_window, 1143 grp_goal, group, sb)) { 1144 if (my_rsv->rsv_goal_size < *count) 1145 my_rsv->rsv_goal_size = *count; 1146 ret = alloc_new_reservation(my_rsv, grp_goal, sb, 1147 group, bitmap_bh); 1148 if (ret < 0) 1149 break; /* failed */ 1150 1151 if (!goal_in_my_reservation(&my_rsv->rsv_window, 1152 grp_goal, group, sb)) 1153 grp_goal = -1; 1154 } else if (grp_goal >= 0) { 1155 int curr = my_rsv->rsv_end - 1156 (grp_goal + group_first_block) + 1; 1157 1158 if (curr < *count) 1159 try_to_extend_reservation(my_rsv, sb, 1160 *count - curr); 1161 } 1162 1163 if ((my_rsv->rsv_start > group_last_block) || 1164 (my_rsv->rsv_end < group_first_block)) { 1165 rsv_window_dump(&EXT2_SB(sb)->s_rsv_window_root, 1); 1166 BUG(); 1167 } 1168 ret = ext2_try_to_allocate(sb, group, bitmap_bh, grp_goal, 1169 &num, &my_rsv->rsv_window); 1170 if (ret >= 0) { 1171 my_rsv->rsv_alloc_hit += num; 1172 *count = num; 1173 break; /* succeed */ 1174 } 1175 num = *count; 1176 } 1177 return ret; 1178} 1179 1180/** 1181 * ext2_has_free_blocks() 1182 * @sbi: in-core super block structure. 1183 * 1184 * Check if filesystem has at least 1 free block available for allocation. 1185 */ 1186static int ext2_has_free_blocks(struct ext2_sb_info *sbi) 1187{ 1188 ext2_fsblk_t free_blocks, root_blocks; 1189 1190 free_blocks = percpu_counter_read_positive(&sbi->s_freeblocks_counter); 1191 root_blocks = le32_to_cpu(sbi->s_es->s_r_blocks_count); 1192 if (free_blocks < root_blocks + 1 && !capable(CAP_SYS_RESOURCE) && 1193 sbi->s_resuid != current_fsuid() && 1194 (sbi->s_resgid == 0 || !in_group_p (sbi->s_resgid))) { 1195 return 0; 1196 } 1197 return 1; 1198} 1199 1200/* 1201 * ext2_new_blocks() -- core block(s) allocation function 1202 * @inode: file inode 1203 * @goal: given target block(filesystem wide) 1204 * @count: target number of blocks to allocate 1205 * @errp: error code 1206 * 1207 * ext2_new_blocks uses a goal block to assist allocation. If the goal is 1208 * free, or there is a free block within 32 blocks of the goal, that block 1209 * is allocated. Otherwise a forward search is made for a free block; within 1210 * each block group the search first looks for an entire free byte in the block 1211 * bitmap, and then for any free bit if that fails. 1212 * This function also updates quota and i_blocks field. 1213 */ 1214ext2_fsblk_t ext2_new_blocks(struct inode *inode, ext2_fsblk_t goal, 1215 unsigned long *count, int *errp) 1216{ 1217 struct buffer_head *bitmap_bh = NULL; 1218 struct buffer_head *gdp_bh; 1219 int group_no; 1220 int goal_group; 1221 ext2_grpblk_t grp_target_blk; /* blockgroup relative goal block */ 1222 ext2_grpblk_t grp_alloc_blk; /* blockgroup-relative allocated block*/ 1223 ext2_fsblk_t ret_block; /* filesyetem-wide allocated block */ 1224 int bgi; /* blockgroup iteration index */ 1225 int performed_allocation = 0; 1226 ext2_grpblk_t free_blocks; /* number of free blocks in a group */ 1227 struct super_block *sb; 1228 struct ext2_group_desc *gdp; 1229 struct ext2_super_block *es; 1230 struct ext2_sb_info *sbi; 1231 struct ext2_reserve_window_node *my_rsv = NULL; 1232 struct ext2_block_alloc_info *block_i; 1233 unsigned short windowsz = 0; 1234 unsigned long ngroups; 1235 unsigned long num = *count; 1236 int ret; 1237 1238 *errp = -ENOSPC; 1239 sb = inode->i_sb; 1240 if (!sb) { 1241 printk("ext2_new_blocks: nonexistent device"); 1242 return 0; 1243 } 1244 1245 /* 1246 * Check quota for allocation of this block. 1247 */ 1248 ret = dquot_alloc_block(inode, num); 1249 if (ret) { 1250 *errp = ret; 1251 return 0; 1252 } 1253 1254 sbi = EXT2_SB(sb); 1255 es = EXT2_SB(sb)->s_es; 1256 ext2_debug("goal=%lu.\n", goal); 1257 /* 1258 * Allocate a block from reservation only when 1259 * filesystem is mounted with reservation(default,-o reservation), and 1260 * it's a regular file, and 1261 * the desired window size is greater than 0 (One could use ioctl 1262 * command EXT2_IOC_SETRSVSZ to set the window size to 0 to turn off 1263 * reservation on that particular file) 1264 */ 1265 block_i = EXT2_I(inode)->i_block_alloc_info; 1266 if (block_i) { 1267 windowsz = block_i->rsv_window_node.rsv_goal_size; 1268 if (windowsz > 0) 1269 my_rsv = &block_i->rsv_window_node; 1270 } 1271 1272 if (!ext2_has_free_blocks(sbi)) { 1273 *errp = -ENOSPC; 1274 goto out; 1275 } 1276 1277 /* 1278 * First, test whether the goal block is free. 1279 */ 1280 if (goal < le32_to_cpu(es->s_first_data_block) || 1281 goal >= le32_to_cpu(es->s_blocks_count)) 1282 goal = le32_to_cpu(es->s_first_data_block); 1283 group_no = (goal - le32_to_cpu(es->s_first_data_block)) / 1284 EXT2_BLOCKS_PER_GROUP(sb); 1285 goal_group = group_no; 1286retry_alloc: 1287 gdp = ext2_get_group_desc(sb, group_no, &gdp_bh); 1288 if (!gdp) 1289 goto io_error; 1290 1291 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count); 1292 /* 1293 * if there is not enough free blocks to make a new resevation 1294 * turn off reservation for this allocation 1295 */ 1296 if (my_rsv && (free_blocks < windowsz) 1297 && (free_blocks > 0) 1298 && (rsv_is_empty(&my_rsv->rsv_window))) 1299 my_rsv = NULL; 1300 1301 if (free_blocks > 0) { 1302 grp_target_blk = ((goal - le32_to_cpu(es->s_first_data_block)) % 1303 EXT2_BLOCKS_PER_GROUP(sb)); 1304 bitmap_bh = read_block_bitmap(sb, group_no); 1305 if (!bitmap_bh) 1306 goto io_error; 1307 grp_alloc_blk = ext2_try_to_allocate_with_rsv(sb, group_no, 1308 bitmap_bh, grp_target_blk, 1309 my_rsv, &num); 1310 if (grp_alloc_blk >= 0) 1311 goto allocated; 1312 } 1313 1314 ngroups = EXT2_SB(sb)->s_groups_count; 1315 smp_rmb(); 1316 1317 /* 1318 * Now search the rest of the groups. We assume that 1319 * group_no and gdp correctly point to the last group visited. 1320 */ 1321 for (bgi = 0; bgi < ngroups; bgi++) { 1322 group_no++; 1323 if (group_no >= ngroups) 1324 group_no = 0; 1325 gdp = ext2_get_group_desc(sb, group_no, &gdp_bh); 1326 if (!gdp) 1327 goto io_error; 1328 1329 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count); 1330 /* 1331 * skip this group (and avoid loading bitmap) if there 1332 * are no free blocks 1333 */ 1334 if (!free_blocks) 1335 continue; 1336 /* 1337 * skip this group if the number of 1338 * free blocks is less than half of the reservation 1339 * window size. 1340 */ 1341 if (my_rsv && (free_blocks <= (windowsz/2))) 1342 continue; 1343 1344 brelse(bitmap_bh); 1345 bitmap_bh = read_block_bitmap(sb, group_no); 1346 if (!bitmap_bh) 1347 goto io_error; 1348 /* 1349 * try to allocate block(s) from this group, without a goal(-1). 1350 */ 1351 grp_alloc_blk = ext2_try_to_allocate_with_rsv(sb, group_no, 1352 bitmap_bh, -1, my_rsv, &num); 1353 if (grp_alloc_blk >= 0) 1354 goto allocated; 1355 } 1356 /* 1357 * We may end up a bogus ealier ENOSPC error due to 1358 * filesystem is "full" of reservations, but 1359 * there maybe indeed free blocks avaliable on disk 1360 * In this case, we just forget about the reservations 1361 * just do block allocation as without reservations. 1362 */ 1363 if (my_rsv) { 1364 my_rsv = NULL; 1365 windowsz = 0; 1366 group_no = goal_group; 1367 goto retry_alloc; 1368 } 1369 /* No space left on the device */ 1370 *errp = -ENOSPC; 1371 goto out; 1372 1373allocated: 1374 1375 ext2_debug("using block group %d(%d)\n", 1376 group_no, gdp->bg_free_blocks_count); 1377 1378 ret_block = grp_alloc_blk + ext2_group_first_block_no(sb, group_no); 1379 1380 if (in_range(le32_to_cpu(gdp->bg_block_bitmap), ret_block, num) || 1381 in_range(le32_to_cpu(gdp->bg_inode_bitmap), ret_block, num) || 1382 in_range(ret_block, le32_to_cpu(gdp->bg_inode_table), 1383 EXT2_SB(sb)->s_itb_per_group) || 1384 in_range(ret_block + num - 1, le32_to_cpu(gdp->bg_inode_table), 1385 EXT2_SB(sb)->s_itb_per_group)) { 1386 ext2_error(sb, "ext2_new_blocks", 1387 "Allocating block in system zone - " 1388 "blocks from "E2FSBLK", length %lu", 1389 ret_block, num); 1390 /* 1391 * ext2_try_to_allocate marked the blocks we allocated as in 1392 * use. So we may want to selectively mark some of the blocks 1393 * as free 1394 */ 1395 goto retry_alloc; 1396 } 1397 1398 performed_allocation = 1; 1399 1400 if (ret_block + num - 1 >= le32_to_cpu(es->s_blocks_count)) { 1401 ext2_error(sb, "ext2_new_blocks", 1402 "block("E2FSBLK") >= blocks count(%d) - " 1403 "block_group = %d, es == %p ", ret_block, 1404 le32_to_cpu(es->s_blocks_count), group_no, es); 1405 goto out; 1406 } 1407 1408 group_adjust_blocks(sb, group_no, gdp, gdp_bh, -num); 1409 percpu_counter_sub(&sbi->s_freeblocks_counter, num); 1410 1411 mark_buffer_dirty(bitmap_bh); 1412 if (sb->s_flags & MS_SYNCHRONOUS) 1413 sync_dirty_buffer(bitmap_bh); 1414 1415 *errp = 0; 1416 brelse(bitmap_bh); 1417 dquot_free_block_nodirty(inode, *count-num); 1418 mark_inode_dirty(inode); 1419 *count = num; 1420 return ret_block; 1421 1422io_error: 1423 *errp = -EIO; 1424out: 1425 /* 1426 * Undo the block allocation 1427 */ 1428 if (!performed_allocation) { 1429 dquot_free_block_nodirty(inode, *count); 1430 mark_inode_dirty(inode); 1431 } 1432 brelse(bitmap_bh); 1433 return 0; 1434} 1435 1436ext2_fsblk_t ext2_new_block(struct inode *inode, unsigned long goal, int *errp) 1437{ 1438 unsigned long count = 1; 1439 1440 return ext2_new_blocks(inode, goal, &count, errp); 1441} 1442 1443#ifdef EXT2FS_DEBUG 1444 1445static const int nibblemap[] = {4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0}; 1446 1447unsigned long ext2_count_free (struct buffer_head * map, unsigned int numchars) 1448{ 1449 unsigned int i; 1450 unsigned long sum = 0; 1451 1452 if (!map) 1453 return (0); 1454 for (i = 0; i < numchars; i++) 1455 sum += nibblemap[map->b_data[i] & 0xf] + 1456 nibblemap[(map->b_data[i] >> 4) & 0xf]; 1457 return (sum); 1458} 1459 1460#endif /* EXT2FS_DEBUG */ 1461 1462unsigned long ext2_count_free_blocks (struct super_block * sb) 1463{ 1464 struct ext2_group_desc * desc; 1465 unsigned long desc_count = 0; 1466 int i; 1467#ifdef EXT2FS_DEBUG 1468 unsigned long bitmap_count, x; 1469 struct ext2_super_block *es; 1470 1471 es = EXT2_SB(sb)->s_es; 1472 desc_count = 0; 1473 bitmap_count = 0; 1474 desc = NULL; 1475 for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) { 1476 struct buffer_head *bitmap_bh; 1477 desc = ext2_get_group_desc (sb, i, NULL); 1478 if (!desc) 1479 continue; 1480 desc_count += le16_to_cpu(desc->bg_free_blocks_count); 1481 bitmap_bh = read_block_bitmap(sb, i); 1482 if (!bitmap_bh) 1483 continue; 1484 1485 x = ext2_count_free(bitmap_bh, sb->s_blocksize); 1486 printk ("group %d: stored = %d, counted = %lu\n", 1487 i, le16_to_cpu(desc->bg_free_blocks_count), x); 1488 bitmap_count += x; 1489 brelse(bitmap_bh); 1490 } 1491 printk("ext2_count_free_blocks: stored = %lu, computed = %lu, %lu\n", 1492 (long)le32_to_cpu(es->s_free_blocks_count), 1493 desc_count, bitmap_count); 1494 return bitmap_count; 1495#else 1496 for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) { 1497 desc = ext2_get_group_desc (sb, i, NULL); 1498 if (!desc) 1499 continue; 1500 desc_count += le16_to_cpu(desc->bg_free_blocks_count); 1501 } 1502 return desc_count; 1503#endif 1504} 1505 1506static inline int test_root(int a, int b) 1507{ 1508 int num = b; 1509 1510 while (a > num) 1511 num *= b; 1512 return num == a; 1513} 1514 1515static int ext2_group_sparse(int group) 1516{ 1517 if (group <= 1) 1518 return 1; 1519 return (test_root(group, 3) || test_root(group, 5) || 1520 test_root(group, 7)); 1521} 1522 1523/** 1524 * ext2_bg_has_super - number of blocks used by the superblock in group 1525 * @sb: superblock for filesystem 1526 * @group: group number to check 1527 * 1528 * Return the number of blocks used by the superblock (primary or backup) 1529 * in this group. Currently this will be only 0 or 1. 1530 */ 1531int ext2_bg_has_super(struct super_block *sb, int group) 1532{ 1533 if (EXT2_HAS_RO_COMPAT_FEATURE(sb,EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER)&& 1534 !ext2_group_sparse(group)) 1535 return 0; 1536 return 1; 1537} 1538 1539/** 1540 * ext2_bg_num_gdb - number of blocks used by the group table in group 1541 * @sb: superblock for filesystem 1542 * @group: group number to check 1543 * 1544 * Return the number of blocks used by the group descriptor table 1545 * (primary or backup) in this group. In the future there may be a 1546 * different number of descriptor blocks in each group. 1547 */ 1548unsigned long ext2_bg_num_gdb(struct super_block *sb, int group) 1549{ 1550 return ext2_bg_has_super(sb, group) ? EXT2_SB(sb)->s_gdb_count : 0; 1551} 1552