1/* 2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README 3 */ 4/* Reiserfs block (de)allocator, bitmap-based. */ 5 6#include <linux/time.h> 7#include "reiserfs.h" 8#include <linux/errno.h> 9#include <linux/buffer_head.h> 10#include <linux/kernel.h> 11#include <linux/pagemap.h> 12#include <linux/vmalloc.h> 13#include <linux/quotaops.h> 14#include <linux/seq_file.h> 15 16#define PREALLOCATION_SIZE 9 17 18/* different reiserfs block allocator options */ 19 20#define SB_ALLOC_OPTS(s) (REISERFS_SB(s)->s_alloc_options.bits) 21 22#define _ALLOC_concentrating_formatted_nodes 0 23#define _ALLOC_displacing_large_files 1 24#define _ALLOC_displacing_new_packing_localities 2 25#define _ALLOC_old_hashed_relocation 3 26#define _ALLOC_new_hashed_relocation 4 27#define _ALLOC_skip_busy 5 28#define _ALLOC_displace_based_on_dirid 6 29#define _ALLOC_hashed_formatted_nodes 7 30#define _ALLOC_old_way 8 31#define _ALLOC_hundredth_slices 9 32#define _ALLOC_dirid_groups 10 33#define _ALLOC_oid_groups 11 34#define _ALLOC_packing_groups 12 35 36#define concentrating_formatted_nodes(s) test_bit(_ALLOC_concentrating_formatted_nodes, &SB_ALLOC_OPTS(s)) 37#define displacing_large_files(s) test_bit(_ALLOC_displacing_large_files, &SB_ALLOC_OPTS(s)) 38#define displacing_new_packing_localities(s) test_bit(_ALLOC_displacing_new_packing_localities, &SB_ALLOC_OPTS(s)) 39 40#define SET_OPTION(optname) \ 41 do { \ 42 reiserfs_info(s, "block allocator option \"%s\" is set", #optname); \ 43 set_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s)); \ 44 } while(0) 45#define TEST_OPTION(optname, s) \ 46 test_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s)) 47 48static inline void get_bit_address(struct super_block *s, 49 b_blocknr_t block, 50 unsigned int *bmap_nr, 51 unsigned int *offset) 52{ 53 /* 54 * It is in the bitmap block number equal to the block 55 * number divided by the number of bits in a block. 56 */ 57 *bmap_nr = block >> (s->s_blocksize_bits + 3); 58 /* Within that bitmap block it is located at bit offset *offset. */ 59 *offset = block & ((s->s_blocksize << 3) - 1); 60} 61 62int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value) 63{ 64 unsigned int bmap, offset; 65 unsigned int bmap_count = reiserfs_bmap_count(s); 66 67 if (block == 0 || block >= SB_BLOCK_COUNT(s)) { 68 reiserfs_error(s, "vs-4010", 69 "block number is out of range %lu (%u)", 70 block, SB_BLOCK_COUNT(s)); 71 return 0; 72 } 73 74 get_bit_address(s, block, &bmap, &offset); 75 76 /* 77 * Old format filesystem? Unlikely, but the bitmaps are all 78 * up front so we need to account for it. 79 */ 80 if (unlikely(test_bit(REISERFS_OLD_FORMAT, 81 &REISERFS_SB(s)->s_properties))) { 82 b_blocknr_t bmap1 = REISERFS_SB(s)->s_sbh->b_blocknr + 1; 83 if (block >= bmap1 && 84 block <= bmap1 + bmap_count) { 85 reiserfs_error(s, "vs-4019", "bitmap block %lu(%u) " 86 "can't be freed or reused", 87 block, bmap_count); 88 return 0; 89 } 90 } else { 91 if (offset == 0) { 92 reiserfs_error(s, "vs-4020", "bitmap block %lu(%u) " 93 "can't be freed or reused", 94 block, bmap_count); 95 return 0; 96 } 97 } 98 99 if (bmap >= bmap_count) { 100 reiserfs_error(s, "vs-4030", "bitmap for requested block " 101 "is out of range: block=%lu, bitmap_nr=%u", 102 block, bmap); 103 return 0; 104 } 105 106 if (bit_value == 0 && block == SB_ROOT_BLOCK(s)) { 107 reiserfs_error(s, "vs-4050", "this is root block (%u), " 108 "it must be busy", SB_ROOT_BLOCK(s)); 109 return 0; 110 } 111 112 return 1; 113} 114 115/* 116 * Searches in journal structures for a given block number (bmap, off). 117 * If block is found in reiserfs journal it suggests next free block 118 * candidate to test. 119 */ 120static inline int is_block_in_journal(struct super_block *s, unsigned int bmap, 121 int off, int *next) 122{ 123 b_blocknr_t tmp; 124 125 if (reiserfs_in_journal(s, bmap, off, 1, &tmp)) { 126 if (tmp) { /* hint supplied */ 127 *next = tmp; 128 PROC_INFO_INC(s, scan_bitmap.in_journal_hint); 129 } else { 130 (*next) = off + 1; /* inc offset to avoid looping. */ 131 PROC_INFO_INC(s, scan_bitmap.in_journal_nohint); 132 } 133 PROC_INFO_INC(s, scan_bitmap.retry); 134 return 1; 135 } 136 return 0; 137} 138 139/* 140 * Searches for a window of zero bits with given minimum and maximum 141 * lengths in one bitmap block 142 */ 143static int scan_bitmap_block(struct reiserfs_transaction_handle *th, 144 unsigned int bmap_n, int *beg, int boundary, 145 int min, int max, int unfm) 146{ 147 struct super_block *s = th->t_super; 148 struct reiserfs_bitmap_info *bi = &SB_AP_BITMAP(s)[bmap_n]; 149 struct buffer_head *bh; 150 int end, next; 151 int org = *beg; 152 153 BUG_ON(!th->t_trans_id); 154 RFALSE(bmap_n >= reiserfs_bmap_count(s), "Bitmap %u is out of " 155 "range (0..%u)", bmap_n, reiserfs_bmap_count(s) - 1); 156 PROC_INFO_INC(s, scan_bitmap.bmap); 157 158 if (!bi) { 159 reiserfs_error(s, "jdm-4055", "NULL bitmap info pointer " 160 "for bitmap %d", bmap_n); 161 return 0; 162 } 163 164 bh = reiserfs_read_bitmap_block(s, bmap_n); 165 if (bh == NULL) 166 return 0; 167 168 while (1) { 169cont: 170 if (bi->free_count < min) { 171 brelse(bh); 172 return 0; /* No free blocks in this bitmap */ 173 } 174 175 /* search for a first zero bit -- beginning of a window */ 176 *beg = reiserfs_find_next_zero_le_bit 177 ((unsigned long *)(bh->b_data), boundary, *beg); 178 179 /* 180 * search for a zero bit fails or the rest of bitmap block 181 * cannot contain a zero window of minimum size 182 */ 183 if (*beg + min > boundary) { 184 brelse(bh); 185 return 0; 186 } 187 188 if (unfm && is_block_in_journal(s, bmap_n, *beg, beg)) 189 continue; 190 /* first zero bit found; we check next bits */ 191 for (end = *beg + 1;; end++) { 192 if (end >= *beg + max || end >= boundary 193 || reiserfs_test_le_bit(end, bh->b_data)) { 194 next = end; 195 break; 196 } 197 198 /* 199 * finding the other end of zero bit window requires 200 * looking into journal structures (in case of 201 * searching for free blocks for unformatted nodes) 202 */ 203 if (unfm && is_block_in_journal(s, bmap_n, end, &next)) 204 break; 205 } 206 207 /* 208 * now (*beg) points to beginning of zero bits window, 209 * (end) points to one bit after the window end 210 */ 211 212 /* found window of proper size */ 213 if (end - *beg >= min) { 214 int i; 215 reiserfs_prepare_for_journal(s, bh, 1); 216 /* 217 * try to set all blocks used checking are 218 * they still free 219 */ 220 for (i = *beg; i < end; i++) { 221 /* Don't check in journal again. */ 222 if (reiserfs_test_and_set_le_bit 223 (i, bh->b_data)) { 224 /* 225 * bit was set by another process while 226 * we slept in prepare_for_journal() 227 */ 228 PROC_INFO_INC(s, scan_bitmap.stolen); 229 230 /* 231 * we can continue with smaller set 232 * of allocated blocks, if length of 233 * this set is more or equal to `min' 234 */ 235 if (i >= *beg + min) { 236 end = i; 237 break; 238 } 239 240 /* 241 * otherwise we clear all bit 242 * were set ... 243 */ 244 while (--i >= *beg) 245 reiserfs_clear_le_bit 246 (i, bh->b_data); 247 reiserfs_restore_prepared_buffer(s, bh); 248 *beg = org; 249 250 /* 251 * Search again in current block 252 * from beginning 253 */ 254 goto cont; 255 } 256 } 257 bi->free_count -= (end - *beg); 258 journal_mark_dirty(th, bh); 259 brelse(bh); 260 261 /* free block count calculation */ 262 reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s), 263 1); 264 PUT_SB_FREE_BLOCKS(s, SB_FREE_BLOCKS(s) - (end - *beg)); 265 journal_mark_dirty(th, SB_BUFFER_WITH_SB(s)); 266 267 return end - (*beg); 268 } else { 269 *beg = next; 270 } 271 } 272} 273 274static int bmap_hash_id(struct super_block *s, u32 id) 275{ 276 char *hash_in = NULL; 277 unsigned long hash; 278 unsigned bm; 279 280 if (id <= 2) { 281 bm = 1; 282 } else { 283 hash_in = (char *)(&id); 284 hash = keyed_hash(hash_in, 4); 285 bm = hash % reiserfs_bmap_count(s); 286 if (!bm) 287 bm = 1; 288 } 289 /* this can only be true when SB_BMAP_NR = 1 */ 290 if (bm >= reiserfs_bmap_count(s)) 291 bm = 0; 292 return bm; 293} 294 295/* 296 * hashes the id and then returns > 0 if the block group for the 297 * corresponding hash is full 298 */ 299static inline int block_group_used(struct super_block *s, u32 id) 300{ 301 int bm = bmap_hash_id(s, id); 302 struct reiserfs_bitmap_info *info = &SB_AP_BITMAP(s)[bm]; 303 304 /* 305 * If we don't have cached information on this bitmap block, we're 306 * going to have to load it later anyway. Loading it here allows us 307 * to make a better decision. This favors long-term performance gain 308 * with a better on-disk layout vs. a short term gain of skipping the 309 * read and potentially having a bad placement. 310 */ 311 if (info->free_count == UINT_MAX) { 312 struct buffer_head *bh = reiserfs_read_bitmap_block(s, bm); 313 brelse(bh); 314 } 315 316 if (info->free_count > ((s->s_blocksize << 3) * 60 / 100)) { 317 return 0; 318 } 319 return 1; 320} 321 322/* 323 * the packing is returned in disk byte order 324 */ 325__le32 reiserfs_choose_packing(struct inode * dir) 326{ 327 __le32 packing; 328 if (TEST_OPTION(packing_groups, dir->i_sb)) { 329 u32 parent_dir = le32_to_cpu(INODE_PKEY(dir)->k_dir_id); 330 /* 331 * some versions of reiserfsck expect packing locality 1 to be 332 * special 333 */ 334 if (parent_dir == 1 || block_group_used(dir->i_sb, parent_dir)) 335 packing = INODE_PKEY(dir)->k_objectid; 336 else 337 packing = INODE_PKEY(dir)->k_dir_id; 338 } else 339 packing = INODE_PKEY(dir)->k_objectid; 340 return packing; 341} 342 343/* 344 * Tries to find contiguous zero bit window (given size) in given region of 345 * bitmap and place new blocks there. Returns number of allocated blocks. 346 */ 347static int scan_bitmap(struct reiserfs_transaction_handle *th, 348 b_blocknr_t * start, b_blocknr_t finish, 349 int min, int max, int unfm, sector_t file_block) 350{ 351 int nr_allocated = 0; 352 struct super_block *s = th->t_super; 353 unsigned int bm, off; 354 unsigned int end_bm, end_off; 355 unsigned int off_max = s->s_blocksize << 3; 356 357 BUG_ON(!th->t_trans_id); 358 PROC_INFO_INC(s, scan_bitmap.call); 359 360 /* No point in looking for more free blocks */ 361 if (SB_FREE_BLOCKS(s) <= 0) 362 return 0; 363 364 get_bit_address(s, *start, &bm, &off); 365 get_bit_address(s, finish, &end_bm, &end_off); 366 if (bm > reiserfs_bmap_count(s)) 367 return 0; 368 if (end_bm > reiserfs_bmap_count(s)) 369 end_bm = reiserfs_bmap_count(s); 370 371 /* 372 * When the bitmap is more than 10% free, anyone can allocate. 373 * When it's less than 10% free, only files that already use the 374 * bitmap are allowed. Once we pass 80% full, this restriction 375 * is lifted. 376 * 377 * We do this so that files that grow later still have space close to 378 * their original allocation. This improves locality, and presumably 379 * performance as a result. 380 * 381 * This is only an allocation policy and does not make up for getting a 382 * bad hint. Decent hinting must be implemented for this to work well. 383 */ 384 if (TEST_OPTION(skip_busy, s) 385 && SB_FREE_BLOCKS(s) > SB_BLOCK_COUNT(s) / 20) { 386 for (; bm < end_bm; bm++, off = 0) { 387 if ((off && (!unfm || (file_block != 0))) 388 || SB_AP_BITMAP(s)[bm].free_count > 389 (s->s_blocksize << 3) / 10) 390 nr_allocated = 391 scan_bitmap_block(th, bm, &off, off_max, 392 min, max, unfm); 393 if (nr_allocated) 394 goto ret; 395 } 396 /* we know from above that start is a reasonable number */ 397 get_bit_address(s, *start, &bm, &off); 398 } 399 400 for (; bm < end_bm; bm++, off = 0) { 401 nr_allocated = 402 scan_bitmap_block(th, bm, &off, off_max, min, max, unfm); 403 if (nr_allocated) 404 goto ret; 405 } 406 407 nr_allocated = 408 scan_bitmap_block(th, bm, &off, end_off + 1, min, max, unfm); 409 410ret: 411 *start = bm * off_max + off; 412 return nr_allocated; 413 414} 415 416static void _reiserfs_free_block(struct reiserfs_transaction_handle *th, 417 struct inode *inode, b_blocknr_t block, 418 int for_unformatted) 419{ 420 struct super_block *s = th->t_super; 421 struct reiserfs_super_block *rs; 422 struct buffer_head *sbh, *bmbh; 423 struct reiserfs_bitmap_info *apbi; 424 unsigned int nr, offset; 425 426 BUG_ON(!th->t_trans_id); 427 PROC_INFO_INC(s, free_block); 428 rs = SB_DISK_SUPER_BLOCK(s); 429 sbh = SB_BUFFER_WITH_SB(s); 430 apbi = SB_AP_BITMAP(s); 431 432 get_bit_address(s, block, &nr, &offset); 433 434 if (nr >= reiserfs_bmap_count(s)) { 435 reiserfs_error(s, "vs-4075", "block %lu is out of range", 436 block); 437 return; 438 } 439 440 bmbh = reiserfs_read_bitmap_block(s, nr); 441 if (!bmbh) 442 return; 443 444 reiserfs_prepare_for_journal(s, bmbh, 1); 445 446 /* clear bit for the given block in bit map */ 447 if (!reiserfs_test_and_clear_le_bit(offset, bmbh->b_data)) { 448 reiserfs_error(s, "vs-4080", 449 "block %lu: bit already cleared", block); 450 } 451 apbi[nr].free_count++; 452 journal_mark_dirty(th, bmbh); 453 brelse(bmbh); 454 455 reiserfs_prepare_for_journal(s, sbh, 1); 456 /* update super block */ 457 set_sb_free_blocks(rs, sb_free_blocks(rs) + 1); 458 459 journal_mark_dirty(th, sbh); 460 if (for_unformatted) { 461 int depth = reiserfs_write_unlock_nested(s); 462 dquot_free_block_nodirty(inode, 1); 463 reiserfs_write_lock_nested(s, depth); 464 } 465} 466 467void reiserfs_free_block(struct reiserfs_transaction_handle *th, 468 struct inode *inode, b_blocknr_t block, 469 int for_unformatted) 470{ 471 struct super_block *s = th->t_super; 472 473 BUG_ON(!th->t_trans_id); 474 RFALSE(!s, "vs-4061: trying to free block on nonexistent device"); 475 if (!is_reusable(s, block, 1)) 476 return; 477 478 if (block > sb_block_count(REISERFS_SB(s)->s_rs)) { 479 reiserfs_error(th->t_super, "bitmap-4072", 480 "Trying to free block outside file system " 481 "boundaries (%lu > %lu)", 482 block, sb_block_count(REISERFS_SB(s)->s_rs)); 483 return; 484 } 485 /* mark it before we clear it, just in case */ 486 journal_mark_freed(th, s, block); 487 _reiserfs_free_block(th, inode, block, for_unformatted); 488} 489 490/* preallocated blocks don't need to be run through journal_mark_freed */ 491static void reiserfs_free_prealloc_block(struct reiserfs_transaction_handle *th, 492 struct inode *inode, b_blocknr_t block) 493{ 494 BUG_ON(!th->t_trans_id); 495 RFALSE(!th->t_super, 496 "vs-4060: trying to free block on nonexistent device"); 497 if (!is_reusable(th->t_super, block, 1)) 498 return; 499 _reiserfs_free_block(th, inode, block, 1); 500} 501 502static void __discard_prealloc(struct reiserfs_transaction_handle *th, 503 struct reiserfs_inode_info *ei) 504{ 505 unsigned long save = ei->i_prealloc_block; 506 int dirty = 0; 507 struct inode *inode = &ei->vfs_inode; 508 509 BUG_ON(!th->t_trans_id); 510#ifdef CONFIG_REISERFS_CHECK 511 if (ei->i_prealloc_count < 0) 512 reiserfs_error(th->t_super, "zam-4001", 513 "inode has negative prealloc blocks count."); 514#endif 515 while (ei->i_prealloc_count > 0) { 516 b_blocknr_t block_to_free; 517 518 /* 519 * reiserfs_free_prealloc_block can drop the write lock, 520 * which could allow another caller to free the same block. 521 * We can protect against it by modifying the prealloc 522 * state before calling it. 523 */ 524 block_to_free = ei->i_prealloc_block++; 525 ei->i_prealloc_count--; 526 reiserfs_free_prealloc_block(th, inode, block_to_free); 527 dirty = 1; 528 } 529 if (dirty) 530 reiserfs_update_sd(th, inode); 531 ei->i_prealloc_block = save; 532 list_del_init(&ei->i_prealloc_list); 533} 534 535/* FIXME: It should be inline function */ 536void reiserfs_discard_prealloc(struct reiserfs_transaction_handle *th, 537 struct inode *inode) 538{ 539 struct reiserfs_inode_info *ei = REISERFS_I(inode); 540 541 BUG_ON(!th->t_trans_id); 542 if (ei->i_prealloc_count) 543 __discard_prealloc(th, ei); 544} 545 546void reiserfs_discard_all_prealloc(struct reiserfs_transaction_handle *th) 547{ 548 struct list_head *plist = &SB_JOURNAL(th->t_super)->j_prealloc_list; 549 550 BUG_ON(!th->t_trans_id); 551 while (!list_empty(plist)) { 552 struct reiserfs_inode_info *ei; 553 ei = list_entry(plist->next, struct reiserfs_inode_info, 554 i_prealloc_list); 555#ifdef CONFIG_REISERFS_CHECK 556 if (!ei->i_prealloc_count) { 557 reiserfs_error(th->t_super, "zam-4001", 558 "inode is in prealloc list but has " 559 "no preallocated blocks."); 560 } 561#endif 562 __discard_prealloc(th, ei); 563 } 564} 565 566void reiserfs_init_alloc_options(struct super_block *s) 567{ 568 set_bit(_ALLOC_skip_busy, &SB_ALLOC_OPTS(s)); 569 set_bit(_ALLOC_dirid_groups, &SB_ALLOC_OPTS(s)); 570 set_bit(_ALLOC_packing_groups, &SB_ALLOC_OPTS(s)); 571} 572 573/* block allocator related options are parsed here */ 574int reiserfs_parse_alloc_options(struct super_block *s, char *options) 575{ 576 char *this_char, *value; 577 578 /* clear default settings */ 579 REISERFS_SB(s)->s_alloc_options.bits = 0; 580 581 while ((this_char = strsep(&options, ":")) != NULL) { 582 if ((value = strchr(this_char, '=')) != NULL) 583 *value++ = 0; 584 585 if (!strcmp(this_char, "concentrating_formatted_nodes")) { 586 int temp; 587 SET_OPTION(concentrating_formatted_nodes); 588 temp = (value 589 && *value) ? simple_strtoul(value, &value, 590 0) : 10; 591 if (temp <= 0 || temp > 100) { 592 REISERFS_SB(s)->s_alloc_options.border = 10; 593 } else { 594 REISERFS_SB(s)->s_alloc_options.border = 595 100 / temp; 596 } 597 continue; 598 } 599 if (!strcmp(this_char, "displacing_large_files")) { 600 SET_OPTION(displacing_large_files); 601 REISERFS_SB(s)->s_alloc_options.large_file_size = 602 (value 603 && *value) ? simple_strtoul(value, &value, 0) : 16; 604 continue; 605 } 606 if (!strcmp(this_char, "displacing_new_packing_localities")) { 607 SET_OPTION(displacing_new_packing_localities); 608 continue; 609 } 610 611 if (!strcmp(this_char, "old_hashed_relocation")) { 612 SET_OPTION(old_hashed_relocation); 613 continue; 614 } 615 616 if (!strcmp(this_char, "new_hashed_relocation")) { 617 SET_OPTION(new_hashed_relocation); 618 continue; 619 } 620 621 if (!strcmp(this_char, "dirid_groups")) { 622 SET_OPTION(dirid_groups); 623 continue; 624 } 625 if (!strcmp(this_char, "oid_groups")) { 626 SET_OPTION(oid_groups); 627 continue; 628 } 629 if (!strcmp(this_char, "packing_groups")) { 630 SET_OPTION(packing_groups); 631 continue; 632 } 633 if (!strcmp(this_char, "hashed_formatted_nodes")) { 634 SET_OPTION(hashed_formatted_nodes); 635 continue; 636 } 637 638 if (!strcmp(this_char, "skip_busy")) { 639 SET_OPTION(skip_busy); 640 continue; 641 } 642 643 if (!strcmp(this_char, "hundredth_slices")) { 644 SET_OPTION(hundredth_slices); 645 continue; 646 } 647 648 if (!strcmp(this_char, "old_way")) { 649 SET_OPTION(old_way); 650 continue; 651 } 652 653 if (!strcmp(this_char, "displace_based_on_dirid")) { 654 SET_OPTION(displace_based_on_dirid); 655 continue; 656 } 657 658 if (!strcmp(this_char, "preallocmin")) { 659 REISERFS_SB(s)->s_alloc_options.preallocmin = 660 (value 661 && *value) ? simple_strtoul(value, &value, 0) : 4; 662 continue; 663 } 664 665 if (!strcmp(this_char, "preallocsize")) { 666 REISERFS_SB(s)->s_alloc_options.preallocsize = 667 (value 668 && *value) ? simple_strtoul(value, &value, 669 0) : 670 PREALLOCATION_SIZE; 671 continue; 672 } 673 674 reiserfs_warning(s, "zam-4001", "unknown option - %s", 675 this_char); 676 return 1; 677 } 678 679 reiserfs_info(s, "allocator options = [%08x]\n", SB_ALLOC_OPTS(s)); 680 return 0; 681} 682 683static void print_sep(struct seq_file *seq, int *first) 684{ 685 if (!*first) 686 seq_puts(seq, ":"); 687 else 688 *first = 0; 689} 690 691void show_alloc_options(struct seq_file *seq, struct super_block *s) 692{ 693 int first = 1; 694 695 if (SB_ALLOC_OPTS(s) == ((1 << _ALLOC_skip_busy) | 696 (1 << _ALLOC_dirid_groups) | (1 << _ALLOC_packing_groups))) 697 return; 698 699 seq_puts(seq, ",alloc="); 700 701 if (TEST_OPTION(concentrating_formatted_nodes, s)) { 702 print_sep(seq, &first); 703 if (REISERFS_SB(s)->s_alloc_options.border != 10) { 704 seq_printf(seq, "concentrating_formatted_nodes=%d", 705 100 / REISERFS_SB(s)->s_alloc_options.border); 706 } else 707 seq_puts(seq, "concentrating_formatted_nodes"); 708 } 709 if (TEST_OPTION(displacing_large_files, s)) { 710 print_sep(seq, &first); 711 if (REISERFS_SB(s)->s_alloc_options.large_file_size != 16) { 712 seq_printf(seq, "displacing_large_files=%lu", 713 REISERFS_SB(s)->s_alloc_options.large_file_size); 714 } else 715 seq_puts(seq, "displacing_large_files"); 716 } 717 if (TEST_OPTION(displacing_new_packing_localities, s)) { 718 print_sep(seq, &first); 719 seq_puts(seq, "displacing_new_packing_localities"); 720 } 721 if (TEST_OPTION(old_hashed_relocation, s)) { 722 print_sep(seq, &first); 723 seq_puts(seq, "old_hashed_relocation"); 724 } 725 if (TEST_OPTION(new_hashed_relocation, s)) { 726 print_sep(seq, &first); 727 seq_puts(seq, "new_hashed_relocation"); 728 } 729 if (TEST_OPTION(dirid_groups, s)) { 730 print_sep(seq, &first); 731 seq_puts(seq, "dirid_groups"); 732 } 733 if (TEST_OPTION(oid_groups, s)) { 734 print_sep(seq, &first); 735 seq_puts(seq, "oid_groups"); 736 } 737 if (TEST_OPTION(packing_groups, s)) { 738 print_sep(seq, &first); 739 seq_puts(seq, "packing_groups"); 740 } 741 if (TEST_OPTION(hashed_formatted_nodes, s)) { 742 print_sep(seq, &first); 743 seq_puts(seq, "hashed_formatted_nodes"); 744 } 745 if (TEST_OPTION(skip_busy, s)) { 746 print_sep(seq, &first); 747 seq_puts(seq, "skip_busy"); 748 } 749 if (TEST_OPTION(hundredth_slices, s)) { 750 print_sep(seq, &first); 751 seq_puts(seq, "hundredth_slices"); 752 } 753 if (TEST_OPTION(old_way, s)) { 754 print_sep(seq, &first); 755 seq_puts(seq, "old_way"); 756 } 757 if (TEST_OPTION(displace_based_on_dirid, s)) { 758 print_sep(seq, &first); 759 seq_puts(seq, "displace_based_on_dirid"); 760 } 761 if (REISERFS_SB(s)->s_alloc_options.preallocmin != 0) { 762 print_sep(seq, &first); 763 seq_printf(seq, "preallocmin=%d", 764 REISERFS_SB(s)->s_alloc_options.preallocmin); 765 } 766 if (REISERFS_SB(s)->s_alloc_options.preallocsize != 17) { 767 print_sep(seq, &first); 768 seq_printf(seq, "preallocsize=%d", 769 REISERFS_SB(s)->s_alloc_options.preallocsize); 770 } 771} 772 773static inline void new_hashed_relocation(reiserfs_blocknr_hint_t * hint) 774{ 775 char *hash_in; 776 777 if (hint->formatted_node) { 778 hash_in = (char *)&hint->key.k_dir_id; 779 } else { 780 if (!hint->inode) { 781 /*hint->search_start = hint->beg;*/ 782 hash_in = (char *)&hint->key.k_dir_id; 783 } else 784 if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super)) 785 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id); 786 else 787 hash_in = 788 (char *)(&INODE_PKEY(hint->inode)->k_objectid); 789 } 790 791 hint->search_start = 792 hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg); 793} 794 795/* 796 * Relocation based on dirid, hashing them into a given bitmap block 797 * files. Formatted nodes are unaffected, a separate policy covers them 798 */ 799static void dirid_groups(reiserfs_blocknr_hint_t * hint) 800{ 801 unsigned long hash; 802 __u32 dirid = 0; 803 int bm = 0; 804 struct super_block *sb = hint->th->t_super; 805 806 if (hint->inode) 807 dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id); 808 else if (hint->formatted_node) 809 dirid = hint->key.k_dir_id; 810 811 if (dirid) { 812 bm = bmap_hash_id(sb, dirid); 813 hash = bm * (sb->s_blocksize << 3); 814 /* give a portion of the block group to metadata */ 815 if (hint->inode) 816 hash += sb->s_blocksize / 2; 817 hint->search_start = hash; 818 } 819} 820 821/* 822 * Relocation based on oid, hashing them into a given bitmap block 823 * files. Formatted nodes are unaffected, a separate policy covers them 824 */ 825static void oid_groups(reiserfs_blocknr_hint_t * hint) 826{ 827 if (hint->inode) { 828 unsigned long hash; 829 __u32 oid; 830 __u32 dirid; 831 int bm; 832 833 dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id); 834 835 /* 836 * keep the root dir and it's first set of subdirs close to 837 * the start of the disk 838 */ 839 if (dirid <= 2) 840 hash = (hint->inode->i_sb->s_blocksize << 3); 841 else { 842 oid = le32_to_cpu(INODE_PKEY(hint->inode)->k_objectid); 843 bm = bmap_hash_id(hint->inode->i_sb, oid); 844 hash = bm * (hint->inode->i_sb->s_blocksize << 3); 845 } 846 hint->search_start = hash; 847 } 848} 849 850/* 851 * returns 1 if it finds an indirect item and gets valid hint info 852 * from it, otherwise 0 853 */ 854static int get_left_neighbor(reiserfs_blocknr_hint_t * hint) 855{ 856 struct treepath *path; 857 struct buffer_head *bh; 858 struct item_head *ih; 859 int pos_in_item; 860 __le32 *item; 861 int ret = 0; 862 863 /* 864 * reiserfs code can call this function w/o pointer to path 865 * structure supplied; then we rely on supplied search_start 866 */ 867 if (!hint->path) 868 return 0; 869 870 path = hint->path; 871 bh = get_last_bh(path); 872 RFALSE(!bh, "green-4002: Illegal path specified to get_left_neighbor"); 873 ih = tp_item_head(path); 874 pos_in_item = path->pos_in_item; 875 item = tp_item_body(path); 876 877 hint->search_start = bh->b_blocknr; 878 879 /* 880 * for indirect item: go to left and look for the first non-hole entry 881 * in the indirect item 882 */ 883 if (!hint->formatted_node && is_indirect_le_ih(ih)) { 884 if (pos_in_item == I_UNFM_NUM(ih)) 885 pos_in_item--; 886 while (pos_in_item >= 0) { 887 int t = get_block_num(item, pos_in_item); 888 if (t) { 889 hint->search_start = t; 890 ret = 1; 891 break; 892 } 893 pos_in_item--; 894 } 895 } 896 897 /* does result value fit into specified region? */ 898 return ret; 899} 900 901/* 902 * should be, if formatted node, then try to put on first part of the device 903 * specified as number of percent with mount option device, else try to put 904 * on last of device. This is not to say it is good code to do so, 905 * but the effect should be measured. 906 */ 907static inline void set_border_in_hint(struct super_block *s, 908 reiserfs_blocknr_hint_t * hint) 909{ 910 b_blocknr_t border = 911 SB_BLOCK_COUNT(s) / REISERFS_SB(s)->s_alloc_options.border; 912 913 if (hint->formatted_node) 914 hint->end = border - 1; 915 else 916 hint->beg = border; 917} 918 919static inline void displace_large_file(reiserfs_blocknr_hint_t * hint) 920{ 921 if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super)) 922 hint->search_start = 923 hint->beg + 924 keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_dir_id), 925 4) % (hint->end - hint->beg); 926 else 927 hint->search_start = 928 hint->beg + 929 keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_objectid), 930 4) % (hint->end - hint->beg); 931} 932 933static inline void hash_formatted_node(reiserfs_blocknr_hint_t * hint) 934{ 935 char *hash_in; 936 937 if (!hint->inode) 938 hash_in = (char *)&hint->key.k_dir_id; 939 else if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super)) 940 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id); 941 else 942 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid); 943 944 hint->search_start = 945 hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg); 946} 947 948static inline int 949this_blocknr_allocation_would_make_it_a_large_file(reiserfs_blocknr_hint_t * 950 hint) 951{ 952 return hint->block == 953 REISERFS_SB(hint->th->t_super)->s_alloc_options.large_file_size; 954} 955 956#ifdef DISPLACE_NEW_PACKING_LOCALITIES 957static inline void displace_new_packing_locality(reiserfs_blocknr_hint_t * hint) 958{ 959 struct in_core_key *key = &hint->key; 960 961 hint->th->displace_new_blocks = 0; 962 hint->search_start = 963 hint->beg + keyed_hash((char *)(&key->k_objectid), 964 4) % (hint->end - hint->beg); 965} 966#endif 967 968static inline int old_hashed_relocation(reiserfs_blocknr_hint_t * hint) 969{ 970 b_blocknr_t border; 971 u32 hash_in; 972 973 if (hint->formatted_node || hint->inode == NULL) { 974 return 0; 975 } 976 977 hash_in = le32_to_cpu((INODE_PKEY(hint->inode))->k_dir_id); 978 border = 979 hint->beg + (u32) keyed_hash(((char *)(&hash_in)), 980 4) % (hint->end - hint->beg - 1); 981 if (border > hint->search_start) 982 hint->search_start = border; 983 984 return 1; 985} 986 987static inline int old_way(reiserfs_blocknr_hint_t * hint) 988{ 989 b_blocknr_t border; 990 991 if (hint->formatted_node || hint->inode == NULL) { 992 return 0; 993 } 994 995 border = 996 hint->beg + 997 le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id) % (hint->end - 998 hint->beg); 999 if (border > hint->search_start) 1000 hint->search_start = border; 1001 1002 return 1; 1003} 1004 1005static inline void hundredth_slices(reiserfs_blocknr_hint_t * hint) 1006{ 1007 struct in_core_key *key = &hint->key; 1008 b_blocknr_t slice_start; 1009 1010 slice_start = 1011 (keyed_hash((char *)(&key->k_dir_id), 4) % 100) * (hint->end / 100); 1012 if (slice_start > hint->search_start 1013 || slice_start + (hint->end / 100) <= hint->search_start) { 1014 hint->search_start = slice_start; 1015 } 1016} 1017 1018static void determine_search_start(reiserfs_blocknr_hint_t * hint, 1019 int amount_needed) 1020{ 1021 struct super_block *s = hint->th->t_super; 1022 int unfm_hint; 1023 1024 hint->beg = 0; 1025 hint->end = SB_BLOCK_COUNT(s) - 1; 1026 1027 /* This is former border algorithm. Now with tunable border offset */ 1028 if (concentrating_formatted_nodes(s)) 1029 set_border_in_hint(s, hint); 1030 1031#ifdef DISPLACE_NEW_PACKING_LOCALITIES 1032 /* 1033 * whenever we create a new directory, we displace it. At first 1034 * we will hash for location, later we might look for a moderately 1035 * empty place for it 1036 */ 1037 if (displacing_new_packing_localities(s) 1038 && hint->th->displace_new_blocks) { 1039 displace_new_packing_locality(hint); 1040 1041 /* 1042 * we do not continue determine_search_start, 1043 * if new packing locality is being displaced 1044 */ 1045 return; 1046 } 1047#endif 1048 1049 /* 1050 * all persons should feel encouraged to add more special cases 1051 * here and test them 1052 */ 1053 1054 if (displacing_large_files(s) && !hint->formatted_node 1055 && this_blocknr_allocation_would_make_it_a_large_file(hint)) { 1056 displace_large_file(hint); 1057 return; 1058 } 1059 1060 /* 1061 * if none of our special cases is relevant, use the left 1062 * neighbor in the tree order of the new node we are allocating for 1063 */ 1064 if (hint->formatted_node && TEST_OPTION(hashed_formatted_nodes, s)) { 1065 hash_formatted_node(hint); 1066 return; 1067 } 1068 1069 unfm_hint = get_left_neighbor(hint); 1070 1071 /* 1072 * Mimic old block allocator behaviour, that is if VFS allowed for 1073 * preallocation, new blocks are displaced based on directory ID. 1074 * Also, if suggested search_start is less than last preallocated 1075 * block, we start searching from it, assuming that HDD dataflow 1076 * is faster in forward direction 1077 */ 1078 if (TEST_OPTION(old_way, s)) { 1079 if (!hint->formatted_node) { 1080 if (!reiserfs_hashed_relocation(s)) 1081 old_way(hint); 1082 else if (!reiserfs_no_unhashed_relocation(s)) 1083 old_hashed_relocation(hint); 1084 1085 if (hint->inode 1086 && hint->search_start < 1087 REISERFS_I(hint->inode)->i_prealloc_block) 1088 hint->search_start = 1089 REISERFS_I(hint->inode)->i_prealloc_block; 1090 } 1091 return; 1092 } 1093 1094 /* This is an approach proposed by Hans */ 1095 if (TEST_OPTION(hundredth_slices, s) 1096 && !(displacing_large_files(s) && !hint->formatted_node)) { 1097 hundredth_slices(hint); 1098 return; 1099 } 1100 1101 /* old_hashed_relocation only works on unformatted */ 1102 if (!unfm_hint && !hint->formatted_node && 1103 TEST_OPTION(old_hashed_relocation, s)) { 1104 old_hashed_relocation(hint); 1105 } 1106 1107 /* new_hashed_relocation works with both formatted/unformatted nodes */ 1108 if ((!unfm_hint || hint->formatted_node) && 1109 TEST_OPTION(new_hashed_relocation, s)) { 1110 new_hashed_relocation(hint); 1111 } 1112 1113 /* dirid grouping works only on unformatted nodes */ 1114 if (!unfm_hint && !hint->formatted_node && TEST_OPTION(dirid_groups, s)) { 1115 dirid_groups(hint); 1116 } 1117#ifdef DISPLACE_NEW_PACKING_LOCALITIES 1118 if (hint->formatted_node && TEST_OPTION(dirid_groups, s)) { 1119 dirid_groups(hint); 1120 } 1121#endif 1122 1123 /* oid grouping works only on unformatted nodes */ 1124 if (!unfm_hint && !hint->formatted_node && TEST_OPTION(oid_groups, s)) { 1125 oid_groups(hint); 1126 } 1127 return; 1128} 1129 1130static int determine_prealloc_size(reiserfs_blocknr_hint_t * hint) 1131{ 1132 /* make minimum size a mount option and benchmark both ways */ 1133 /* we preallocate blocks only for regular files, specific size */ 1134 /* benchmark preallocating always and see what happens */ 1135 1136 hint->prealloc_size = 0; 1137 1138 if (!hint->formatted_node && hint->preallocate) { 1139 if (S_ISREG(hint->inode->i_mode) && !IS_PRIVATE(hint->inode) 1140 && hint->inode->i_size >= 1141 REISERFS_SB(hint->th->t_super)->s_alloc_options. 1142 preallocmin * hint->inode->i_sb->s_blocksize) 1143 hint->prealloc_size = 1144 REISERFS_SB(hint->th->t_super)->s_alloc_options. 1145 preallocsize - 1; 1146 } 1147 return CARRY_ON; 1148} 1149 1150static inline int allocate_without_wrapping_disk(reiserfs_blocknr_hint_t * hint, 1151 b_blocknr_t * new_blocknrs, 1152 b_blocknr_t start, 1153 b_blocknr_t finish, int min, 1154 int amount_needed, 1155 int prealloc_size) 1156{ 1157 int rest = amount_needed; 1158 int nr_allocated; 1159 1160 while (rest > 0 && start <= finish) { 1161 nr_allocated = scan_bitmap(hint->th, &start, finish, min, 1162 rest + prealloc_size, 1163 !hint->formatted_node, hint->block); 1164 1165 if (nr_allocated == 0) /* no new blocks allocated, return */ 1166 break; 1167 1168 /* fill free_blocknrs array first */ 1169 while (rest > 0 && nr_allocated > 0) { 1170 *new_blocknrs++ = start++; 1171 rest--; 1172 nr_allocated--; 1173 } 1174 1175 /* do we have something to fill prealloc. array also ? */ 1176 if (nr_allocated > 0) { 1177 /* 1178 * it means prealloc_size was greater that 0 and 1179 * we do preallocation 1180 */ 1181 list_add(&REISERFS_I(hint->inode)->i_prealloc_list, 1182 &SB_JOURNAL(hint->th->t_super)-> 1183 j_prealloc_list); 1184 REISERFS_I(hint->inode)->i_prealloc_block = start; 1185 REISERFS_I(hint->inode)->i_prealloc_count = 1186 nr_allocated; 1187 break; 1188 } 1189 } 1190 1191 return (amount_needed - rest); 1192} 1193 1194static inline int blocknrs_and_prealloc_arrays_from_search_start 1195 (reiserfs_blocknr_hint_t * hint, b_blocknr_t * new_blocknrs, 1196 int amount_needed) { 1197 struct super_block *s = hint->th->t_super; 1198 b_blocknr_t start = hint->search_start; 1199 b_blocknr_t finish = SB_BLOCK_COUNT(s) - 1; 1200 int passno = 0; 1201 int nr_allocated = 0; 1202 int depth; 1203 1204 determine_prealloc_size(hint); 1205 if (!hint->formatted_node) { 1206 int quota_ret; 1207#ifdef REISERQUOTA_DEBUG 1208 reiserfs_debug(s, REISERFS_DEBUG_CODE, 1209 "reiserquota: allocating %d blocks id=%u", 1210 amount_needed, hint->inode->i_uid); 1211#endif 1212 depth = reiserfs_write_unlock_nested(s); 1213 quota_ret = 1214 dquot_alloc_block_nodirty(hint->inode, amount_needed); 1215 if (quota_ret) { /* Quota exceeded? */ 1216 reiserfs_write_lock_nested(s, depth); 1217 return QUOTA_EXCEEDED; 1218 } 1219 if (hint->preallocate && hint->prealloc_size) { 1220#ifdef REISERQUOTA_DEBUG 1221 reiserfs_debug(s, REISERFS_DEBUG_CODE, 1222 "reiserquota: allocating (prealloc) %d blocks id=%u", 1223 hint->prealloc_size, hint->inode->i_uid); 1224#endif 1225 quota_ret = dquot_prealloc_block_nodirty(hint->inode, 1226 hint->prealloc_size); 1227 if (quota_ret) 1228 hint->preallocate = hint->prealloc_size = 0; 1229 } 1230 /* for unformatted nodes, force large allocations */ 1231 reiserfs_write_lock_nested(s, depth); 1232 } 1233 1234 do { 1235 switch (passno++) { 1236 case 0: /* Search from hint->search_start to end of disk */ 1237 start = hint->search_start; 1238 finish = SB_BLOCK_COUNT(s) - 1; 1239 break; 1240 case 1: /* Search from hint->beg to hint->search_start */ 1241 start = hint->beg; 1242 finish = hint->search_start; 1243 break; 1244 case 2: /* Last chance: Search from 0 to hint->beg */ 1245 start = 0; 1246 finish = hint->beg; 1247 break; 1248 default: 1249 /* We've tried searching everywhere, not enough space */ 1250 /* Free the blocks */ 1251 if (!hint->formatted_node) { 1252#ifdef REISERQUOTA_DEBUG 1253 reiserfs_debug(s, REISERFS_DEBUG_CODE, 1254 "reiserquota: freeing (nospace) %d blocks id=%u", 1255 amount_needed + 1256 hint->prealloc_size - 1257 nr_allocated, 1258 hint->inode->i_uid); 1259#endif 1260 /* Free not allocated blocks */ 1261 depth = reiserfs_write_unlock_nested(s); 1262 dquot_free_block_nodirty(hint->inode, 1263 amount_needed + hint->prealloc_size - 1264 nr_allocated); 1265 reiserfs_write_lock_nested(s, depth); 1266 } 1267 while (nr_allocated--) 1268 reiserfs_free_block(hint->th, hint->inode, 1269 new_blocknrs[nr_allocated], 1270 !hint->formatted_node); 1271 1272 return NO_DISK_SPACE; 1273 } 1274 } while ((nr_allocated += allocate_without_wrapping_disk(hint, 1275 new_blocknrs + 1276 nr_allocated, 1277 start, finish, 1278 1, 1279 amount_needed - 1280 nr_allocated, 1281 hint-> 1282 prealloc_size)) 1283 < amount_needed); 1284 if (!hint->formatted_node && 1285 amount_needed + hint->prealloc_size > 1286 nr_allocated + REISERFS_I(hint->inode)->i_prealloc_count) { 1287 /* Some of preallocation blocks were not allocated */ 1288#ifdef REISERQUOTA_DEBUG 1289 reiserfs_debug(s, REISERFS_DEBUG_CODE, 1290 "reiserquota: freeing (failed prealloc) %d blocks id=%u", 1291 amount_needed + hint->prealloc_size - 1292 nr_allocated - 1293 REISERFS_I(hint->inode)->i_prealloc_count, 1294 hint->inode->i_uid); 1295#endif 1296 1297 depth = reiserfs_write_unlock_nested(s); 1298 dquot_free_block_nodirty(hint->inode, amount_needed + 1299 hint->prealloc_size - nr_allocated - 1300 REISERFS_I(hint->inode)-> 1301 i_prealloc_count); 1302 reiserfs_write_lock_nested(s, depth); 1303 } 1304 1305 return CARRY_ON; 1306} 1307 1308/* grab new blocknrs from preallocated list */ 1309/* return amount still needed after using them */ 1310static int use_preallocated_list_if_available(reiserfs_blocknr_hint_t * hint, 1311 b_blocknr_t * new_blocknrs, 1312 int amount_needed) 1313{ 1314 struct inode *inode = hint->inode; 1315 1316 if (REISERFS_I(inode)->i_prealloc_count > 0) { 1317 while (amount_needed) { 1318 1319 *new_blocknrs++ = REISERFS_I(inode)->i_prealloc_block++; 1320 REISERFS_I(inode)->i_prealloc_count--; 1321 1322 amount_needed--; 1323 1324 if (REISERFS_I(inode)->i_prealloc_count <= 0) { 1325 list_del(&REISERFS_I(inode)->i_prealloc_list); 1326 break; 1327 } 1328 } 1329 } 1330 /* return amount still needed after using preallocated blocks */ 1331 return amount_needed; 1332} 1333 1334int reiserfs_allocate_blocknrs(reiserfs_blocknr_hint_t *hint, 1335 b_blocknr_t *new_blocknrs, 1336 int amount_needed, 1337 /* Amount of blocks we have already reserved */ 1338 int reserved_by_us) 1339{ 1340 int initial_amount_needed = amount_needed; 1341 int ret; 1342 struct super_block *s = hint->th->t_super; 1343 1344 /* Check if there is enough space, taking into account reserved space */ 1345 if (SB_FREE_BLOCKS(s) - REISERFS_SB(s)->reserved_blocks < 1346 amount_needed - reserved_by_us) 1347 return NO_DISK_SPACE; 1348 /* should this be if !hint->inode && hint->preallocate? */ 1349 /* do you mean hint->formatted_node can be removed ? - Zam */ 1350 /* 1351 * hint->formatted_node cannot be removed because we try to access 1352 * inode information here, and there is often no inode associated with 1353 * metadata allocations - green 1354 */ 1355 1356 if (!hint->formatted_node && hint->preallocate) { 1357 amount_needed = use_preallocated_list_if_available 1358 (hint, new_blocknrs, amount_needed); 1359 1360 /* 1361 * We have all the block numbers we need from the 1362 * prealloc list 1363 */ 1364 if (amount_needed == 0) 1365 return CARRY_ON; 1366 new_blocknrs += (initial_amount_needed - amount_needed); 1367 } 1368 1369 /* find search start and save it in hint structure */ 1370 determine_search_start(hint, amount_needed); 1371 if (hint->search_start >= SB_BLOCK_COUNT(s)) 1372 hint->search_start = SB_BLOCK_COUNT(s) - 1; 1373 1374 /* allocation itself; fill new_blocknrs and preallocation arrays */ 1375 ret = blocknrs_and_prealloc_arrays_from_search_start 1376 (hint, new_blocknrs, amount_needed); 1377 1378 /* 1379 * We used prealloc. list to fill (partially) new_blocknrs array. 1380 * If final allocation fails we need to return blocks back to 1381 * prealloc. list or just free them. -- Zam (I chose second 1382 * variant) 1383 */ 1384 if (ret != CARRY_ON) { 1385 while (amount_needed++ < initial_amount_needed) { 1386 reiserfs_free_block(hint->th, hint->inode, 1387 *(--new_blocknrs), 1); 1388 } 1389 } 1390 return ret; 1391} 1392 1393void reiserfs_cache_bitmap_metadata(struct super_block *sb, 1394 struct buffer_head *bh, 1395 struct reiserfs_bitmap_info *info) 1396{ 1397 unsigned long *cur = (unsigned long *)(bh->b_data + bh->b_size); 1398 1399 /* The first bit must ALWAYS be 1 */ 1400 if (!reiserfs_test_le_bit(0, (unsigned long *)bh->b_data)) 1401 reiserfs_error(sb, "reiserfs-2025", "bitmap block %lu is " 1402 "corrupted: first bit must be 1", bh->b_blocknr); 1403 1404 info->free_count = 0; 1405 1406 while (--cur >= (unsigned long *)bh->b_data) { 1407 /* 0 and ~0 are special, we can optimize for them */ 1408 if (*cur == 0) 1409 info->free_count += BITS_PER_LONG; 1410 else if (*cur != ~0L) /* A mix, investigate */ 1411 info->free_count += BITS_PER_LONG - hweight_long(*cur); 1412 } 1413} 1414 1415struct buffer_head *reiserfs_read_bitmap_block(struct super_block *sb, 1416 unsigned int bitmap) 1417{ 1418 b_blocknr_t block = (sb->s_blocksize << 3) * bitmap; 1419 struct reiserfs_bitmap_info *info = SB_AP_BITMAP(sb) + bitmap; 1420 struct buffer_head *bh; 1421 1422 /* 1423 * Way old format filesystems had the bitmaps packed up front. 1424 * I doubt there are any of these left, but just in case... 1425 */ 1426 if (unlikely(test_bit(REISERFS_OLD_FORMAT, 1427 &REISERFS_SB(sb)->s_properties))) 1428 block = REISERFS_SB(sb)->s_sbh->b_blocknr + 1 + bitmap; 1429 else if (bitmap == 0) 1430 block = (REISERFS_DISK_OFFSET_IN_BYTES >> sb->s_blocksize_bits) + 1; 1431 1432 bh = sb_bread(sb, block); 1433 if (bh == NULL) 1434 reiserfs_warning(sb, "sh-2029: %s: bitmap block (#%u) " 1435 "reading failed", __func__, block); 1436 else { 1437 if (buffer_locked(bh)) { 1438 int depth; 1439 PROC_INFO_INC(sb, scan_bitmap.wait); 1440 depth = reiserfs_write_unlock_nested(sb); 1441 __wait_on_buffer(bh); 1442 reiserfs_write_lock_nested(sb, depth); 1443 } 1444 BUG_ON(!buffer_uptodate(bh)); 1445 BUG_ON(atomic_read(&bh->b_count) == 0); 1446 1447 if (info->free_count == UINT_MAX) 1448 reiserfs_cache_bitmap_metadata(sb, bh, info); 1449 } 1450 1451 return bh; 1452} 1453 1454int reiserfs_init_bitmap_cache(struct super_block *sb) 1455{ 1456 struct reiserfs_bitmap_info *bitmap; 1457 unsigned int bmap_nr = reiserfs_bmap_count(sb); 1458 1459 bitmap = vmalloc(array_size(bmap_nr, sizeof(*bitmap))); 1460 if (bitmap == NULL) 1461 return -ENOMEM; 1462 1463 memset(bitmap, 0xff, sizeof(*bitmap) * bmap_nr); 1464 1465 SB_AP_BITMAP(sb) = bitmap; 1466 1467 return 0; 1468} 1469 1470void reiserfs_free_bitmap_cache(struct super_block *sb) 1471{ 1472 if (SB_AP_BITMAP(sb)) { 1473 vfree(SB_AP_BITMAP(sb)); 1474 SB_AP_BITMAP(sb) = NULL; 1475 } 1476} 1477