fs/reiserfs/bitmap.c

   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
  48 static 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
  62 int 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  */
 120 static 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  */
 143 static 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) {
 169 cont:
 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
 274 static 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  */
 299 static 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  */
 347 static 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
 410 ret:
 411         *start = bm * off_max + off;
 412         return nr_allocated;
 413
 414 }
 415
 416 static 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
 467 void 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 */
 491 static 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
 502 static 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 */
 536 void 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
 546 void 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
 566 void 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 */
 574 int 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
 683 static void print_sep(struct seq_file *seq, int *first)
 684 {
 685         if (!*first)
 686                 seq_puts(seq, ":");
 687         else
 688                 *first = 0;
 689 }
 690
 691 void 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
 773 static 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  */
 799 static 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  */
 825 static 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  */
 854 static 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  */
 907 static 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
 919 static 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
 933 static 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
 948 static inline int
 949 this_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
 957 static 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
 968 static 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
 987 static 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
1005 static 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
1018 static 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
1130 static 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
1150 static 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
1194 static 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 */
1310 static 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
1334 int 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
1393 void 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
1415 struct 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
1454 int 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
1470 void 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 }