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