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