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