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
  16 #define PREALLOCATION_SIZE 9
  17
  18 /* different reiserfs block allocator options */
  19
  20 #define SB_ALLOC_OPTS(s) (REISERFS_SB(s)->s_alloc_options.bits)
  21
  22 #define  _ALLOC_concentrating_formatted_nodes 0
  23 #define  _ALLOC_displacing_large_files 1
  24 #define  _ALLOC_displacing_new_packing_localities 2
  25 #define  _ALLOC_old_hashed_relocation 3
  26 #define  _ALLOC_new_hashed_relocation 4
  27 #define  _ALLOC_skip_busy 5
  28 #define  _ALLOC_displace_based_on_dirid 6
  29 #define  _ALLOC_hashed_formatted_nodes 7
  30 #define  _ALLOC_old_way 8
  31 #define  _ALLOC_hundredth_slices 9
  32
  33 #define  concentrating_formatted_nodes(s)       test_bit(_ALLOC_concentrating_formatted_nodes, &SB_ALLOC_OPTS(s))
  34 #define  displacing_large_files(s)              test_bit(_ALLOC_displacing_large_files, &SB_ALLOC_OPTS(s))
  35 #define  displacing_new_packing_localities(s)   test_bit(_ALLOC_displacing_new_packing_localities, &SB_ALLOC_OPTS(s))
  36
  37 #define SET_OPTION(optname) \
  38    do { \
  39         reiserfs_warning("reiserfs: option \"%s\" is set\n", #optname); \
  40         set_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s)); \
  41     } while(0)
  42 #define TEST_OPTION(optname, s) \
  43     test_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s))
  44
  45 static inline void get_bit_address (struct super_block * s,
  46                                     b_blocknr_t block, int * bmap_nr, int * offset)
  47 {
  48     /* It is in the bitmap block number equal to the block
  49      * number divided by the number of bits in a block. */
  50     *bmap_nr = block / (s->s_blocksize << 3);
  51     /* Within that bitmap block it is located at bit offset *offset. */
  52     *offset = block & ((s->s_blocksize << 3) - 1 );
  53     return;
  54 }
  55
  56 #ifdef CONFIG_REISERFS_CHECK
  57 int is_reusable (struct super_block * s, b_blocknr_t block, int bit_value)
  58 {
  59     int i, j;
  60
  61     if (block == 0 || block >= SB_BLOCK_COUNT (s)) {
  62         reiserfs_warning ("vs-4010: is_reusable: block number is out of range %lu (%u)\n",
  63                           block, SB_BLOCK_COUNT (s));
  64         return 0;
  65     }
  66
  67     /* it can't be one of the bitmap blocks */
  68     for (i = 0; i < SB_BMAP_NR (s); i ++)
  69         if (block == SB_AP_BITMAP (s)[i].bh->b_blocknr) {
  70             reiserfs_warning ("vs: 4020: is_reusable: "
  71                               "bitmap block %lu(%u) can't be freed or reused\n",
  72                               block, SB_BMAP_NR (s));
  73             return 0;
  74         }
  75
  76     get_bit_address (s, block, &i, &j);
  77
  78     if (i >= SB_BMAP_NR (s)) {
  79         reiserfs_warning ("vs-4030: is_reusable: there is no so many bitmap blocks: "
  80                           "block=%lu, bitmap_nr=%d\n", block, i);
  81         return 0;
  82     }
  83
  84     if ((bit_value == 0 &&
  85          reiserfs_test_le_bit(j, SB_AP_BITMAP(s)[i].bh->b_data)) ||
  86         (bit_value == 1 &&
  87          reiserfs_test_le_bit(j, SB_AP_BITMAP (s)[i].bh->b_data) == 0)) {
  88         reiserfs_warning ("vs-4040: is_reusable: corresponding bit of block %lu does not "
  89                           "match required value (i==%d, j==%d) test_bit==%d\n",
  90                 block, i, j, reiserfs_test_le_bit (j, SB_AP_BITMAP (s)[i].bh->b_data));
  91
  92         return 0;
  93     }
  94
  95     if (bit_value == 0 && block == SB_ROOT_BLOCK (s)) {
  96         reiserfs_warning ("vs-4050: is_reusable: this is root block (%u), "
  97                           "it must be busy\n", SB_ROOT_BLOCK (s));
  98         return 0;
  99     }
 100
 101     return 1;
 102 }
 103 #endif /* CONFIG_REISERFS_CHECK */
 104
 105 /* searches in journal structures for a given block number (bmap, off). If block
 106    is found in reiserfs journal it suggests next free block candidate to test. */
 107 static inline  int is_block_in_journal (struct super_block * s, int bmap, int
 108 off, int *next)
 109 {
 110     b_blocknr_t tmp;
 111
 112     if (reiserfs_in_journal (s, bmap, off, 1, &tmp)) {
 113         if (tmp) {              /* hint supplied */
 114             *next = tmp;
 115             PROC_INFO_INC( s, scan_bitmap.in_journal_hint );
 116         } else {
 117             (*next) = off + 1;          /* inc offset to avoid looping. */
 118             PROC_INFO_INC( s, scan_bitmap.in_journal_nohint );
 119         }
 120         PROC_INFO_INC( s, scan_bitmap.retry );
 121         return 1;
 122     }
 123     return 0;
 124 }
 125
 126 /* it searches for a window of zero bits with given minimum and maximum lengths in one bitmap
 127  * block; */
 128 static int scan_bitmap_block (struct reiserfs_transaction_handle *th,
 129                               int bmap_n, int *beg, int boundary, int min, int max, int unfm)
 130 {
 131     struct super_block *s = th->t_super;
 132     struct reiserfs_bitmap_info *bi=&SB_AP_BITMAP(s)[bmap_n];
 133     int end, next;
 134     int org = *beg;
 135
 136     RFALSE(bmap_n >= SB_BMAP_NR (s), "Bitmap %d is out of range (0..%d)\n",bmap_n, SB_BMAP_NR (s) - 1);
 137     PROC_INFO_INC( s, scan_bitmap.bmap );
 138 /* this is unclear and lacks comments, explain how journal bitmaps
 139    work here for the reader.  Convey a sense of the design here. What
 140    is a window? */
 141 /* - I mean `a window of zero bits' as in description of this function - Zam. */
 142
 143     if ( !bi ) {
 144         printk("Hey, bitmap info pointer is zero for bitmap %d!\n",bmap_n);
 145         return 0;
 146     }
 147     if (buffer_locked (bi->bh)) {
 148        PROC_INFO_INC( s, scan_bitmap.wait );
 149        __wait_on_buffer (bi->bh);
 150     }
 151
 152     /* If we know that first zero bit is only one or first zero bit is
 153        closer to the end of bitmap than our start pointer */
 154     if (bi->first_zero_hint > *beg || bi->free_count == 1)
 155         *beg = bi->first_zero_hint;
 156
 157     while (1) {
 158         cont:
 159         if (bi->free_count < min)
 160                 return 0; // No free blocks in this bitmap
 161
 162         /* search for a first zero bit -- beggining of a window */
 163         *beg = reiserfs_find_next_zero_le_bit
 164                 ((unsigned long*)(bi->bh->b_data), boundary, *beg);
 165
 166         if (*beg + min > boundary) { /* search for a zero bit fails or the rest of bitmap block
 167                                       * cannot contain a zero window of minimum size */
 168             return 0;
 169         }
 170
 171         if (unfm && is_block_in_journal(s,bmap_n, *beg, beg))
 172             continue;
 173         /* first zero bit found; we check next bits */
 174         for (end = *beg + 1;; end ++) {
 175             if (end >= *beg + max || end >= boundary || reiserfs_test_le_bit (end, bi->bh->b_data)) {
 176                 next = end;
 177                 break;
 178             }
 179             /* finding the other end of zero bit window requires looking into journal structures (in
 180              * case of searching for free blocks for unformatted nodes) */
 181             if (unfm && is_block_in_journal(s, bmap_n, end, &next))
 182                 break;
 183         }
 184
 185         /* now (*beg) points to beginning of zero bits window,
 186          * (end) points to one bit after the window end */
 187         if (end - *beg >= min) { /* it seems we have found window of proper size */
 188             int i;
 189             reiserfs_prepare_for_journal (s, bi->bh, 1);
 190             /* try to set all blocks used checking are they still free */
 191             for (i = *beg; i < end; i++) {
 192                 /* It seems that we should not check in journal again. */
 193                 if (reiserfs_test_and_set_le_bit (i, bi->bh->b_data)) {
 194                     /* bit was set by another process
 195                      * while we slept in prepare_for_journal() */
 196                     PROC_INFO_INC( s, scan_bitmap.stolen );
 197                     if (i >= *beg + min)        { /* we can continue with smaller set of allocated blocks,
 198                                            * if length of this set is more or equal to `min' */
 199                         end = i;
 200                         break;
 201                     }
 202                     /* otherwise we clear all bit were set ... */
 203                     while (--i >= *beg)
 204                         reiserfs_test_and_clear_le_bit (i, bi->bh->b_data);
 205                     reiserfs_restore_prepared_buffer (s, bi->bh);
 206                     *beg = max(org, (int)bi->first_zero_hint);
 207                     /* ... and search again in current block from beginning */
 208                     goto cont;
 209                 }
 210             }
 211             bi->free_count -= (end - *beg);
 212
 213             /* if search started from zero_hint bit, and zero hint have not
 214                 changed since, then we need to update first_zero_hint */
 215             if ( bi->first_zero_hint >= *beg)
 216                 /* no point in looking for free bit if there is not any */
 217                 bi->first_zero_hint = (bi->free_count > 0 ) ?
 218                         reiserfs_find_next_zero_le_bit
 219                         ((unsigned long*)(bi->bh->b_data), s->s_blocksize << 3, end) : (s->s_blocksize << 3);
 220
 221             journal_mark_dirty (th, s, bi->bh);
 222
 223             /* free block count calculation */
 224             reiserfs_prepare_for_journal (s, SB_BUFFER_WITH_SB(s), 1);
 225             PUT_SB_FREE_BLOCKS(s, SB_FREE_BLOCKS(s) - (end - *beg));
 226             journal_mark_dirty (th, s, SB_BUFFER_WITH_SB(s));
 227
 228             return end - (*beg);
 229         } else {
 230             *beg = next;
 231         }
 232     }
 233   }
 234
 235 /* Tries to find contiguous zero bit window (given size) in given region of
 236  * bitmap and place new blocks there. Returns number of allocated blocks. */
 237 static int scan_bitmap (struct reiserfs_transaction_handle *th,
 238                         b_blocknr_t *start, b_blocknr_t finish,
 239                         int min, int max, int unfm, unsigned long file_block)
 240 {
 241     int nr_allocated=0;
 242     struct super_block * s = th->t_super;
 243     /* find every bm and bmap and bmap_nr in this file, and change them all to bitmap_blocknr
 244      * - Hans, it is not a block number - Zam. */
 245
 246     int bm, off;
 247     int end_bm, end_off;
 248     int off_max = s->s_blocksize << 3;
 249
 250     PROC_INFO_INC( s, scan_bitmap.call );
 251     if ( SB_FREE_BLOCKS(s) <= 0)
 252         return 0; // No point in looking for more free blocks
 253
 254     get_bit_address (s, *start, &bm, &off);
 255     get_bit_address (s, finish, &end_bm, &end_off);
 256
 257     // With this option set first we try to find a bitmap that is at least 10%
 258     // free, and if that fails, then we fall back to old whole bitmap scanning
 259     if ( TEST_OPTION(skip_busy, s) && SB_FREE_BLOCKS(s) > SB_BLOCK_COUNT(s)/20 ) {
 260         for (;bm < end_bm; bm++, off = 0) {
 261             if ( ( off && (!unfm || (file_block != 0))) || SB_AP_BITMAP(s)[bm].free_count > (s->s_blocksize << 3) / 10 )
 262                 nr_allocated = scan_bitmap_block(th, bm, &off, off_max, min, max, unfm);
 263             if (nr_allocated)
 264                 goto ret;
 265         }
 266         get_bit_address (s, *start, &bm, &off);
 267     }
 268
 269     for (;bm < end_bm; bm++, off = 0) {
 270         nr_allocated = scan_bitmap_block(th, bm, &off, off_max, min, max, unfm);
 271         if (nr_allocated)
 272             goto ret;
 273     }
 274
 275     nr_allocated = scan_bitmap_block(th, bm, &off, end_off + 1, min, max, unfm);
 276
 277  ret:
 278     *start = bm * off_max + off;
 279     return nr_allocated;
 280
 281 }
 282
 283 static void _reiserfs_free_block (struct reiserfs_transaction_handle *th,
 284                                   b_blocknr_t block)
 285 {
 286     struct super_block * s = th->t_super;
 287     struct reiserfs_super_block * rs;
 288     struct buffer_head * sbh;
 289     struct reiserfs_bitmap_info *apbi;
 290     int nr, offset;
 291
 292     PROC_INFO_INC( s, free_block );
 293
 294     rs = SB_DISK_SUPER_BLOCK (s);
 295     sbh = SB_BUFFER_WITH_SB (s);
 296     apbi = SB_AP_BITMAP(s);
 297
 298     get_bit_address (s, block, &nr, &offset);
 299
 300     if (nr >= sb_bmap_nr (rs)) {
 301         reiserfs_warning ("vs-4075: reiserfs_free_block: "
 302                           "block %lu is out of range on %s\n",
 303                           block, reiserfs_bdevname (s));
 304         return;
 305     }
 306
 307     reiserfs_prepare_for_journal(s, apbi[nr].bh, 1 ) ;
 308
 309     /* clear bit for the given block in bit map */
 310     if (!reiserfs_test_and_clear_le_bit (offset, apbi[nr].bh->b_data)) {
 311         reiserfs_warning ("vs-4080: reiserfs_free_block: "
 312                           "free_block (%s:%lu)[dev:blocknr]: bit already cleared\n",
 313                           reiserfs_bdevname (s), block);
 314     }
 315     if (offset < apbi[nr].first_zero_hint) {
 316       apbi[nr].first_zero_hint = offset;
 317     }
 318     apbi[nr].free_count ++;
 319     journal_mark_dirty (th, s, apbi[nr].bh);
 320
 321     reiserfs_prepare_for_journal(s, sbh, 1) ;
 322     /* update super block */
 323     set_sb_free_blocks( rs, sb_free_blocks(rs) + 1 );
 324
 325     journal_mark_dirty (th, s, sbh);
 326   s->s_dirt = 1;
 327 }
 328
 329 void reiserfs_free_block (struct reiserfs_transaction_handle *th,
 330                           b_blocknr_t block)
 331 {
 332     struct super_block * s = th->t_super;
 333
 334     RFALSE(!s, "vs-4061: trying to free block on nonexistent device");
 335     RFALSE(is_reusable (s, block, 1) == 0, "vs-4071: can not free such block");
 336     /* mark it before we clear it, just in case */
 337     journal_mark_freed(th, s, block) ;
 338     _reiserfs_free_block(th, block) ;
 339 }
 340
 341 /* preallocated blocks don't need to be run through journal_mark_freed */
 342 void reiserfs_free_prealloc_block (struct reiserfs_transaction_handle *th,
 343                           b_blocknr_t block) {
 344     RFALSE(!th->t_super, "vs-4060: trying to free block on nonexistent device");
 345     RFALSE(is_reusable (th->t_super, block, 1) == 0, "vs-4070: can not free such block");
 346     _reiserfs_free_block(th, block) ;
 347 }
 348
 349 static void __discard_prealloc (struct reiserfs_transaction_handle * th,
 350                                 struct reiserfs_inode_info *ei)
 351 {
 352     unsigned long save = ei->i_prealloc_block ;
 353 #ifdef CONFIG_REISERFS_CHECK
 354     if (ei->i_prealloc_count < 0)
 355         reiserfs_warning("zam-4001:%s: inode has negative prealloc blocks count.\n", __FUNCTION__ );
 356 #endif
 357     while (ei->i_prealloc_count > 0) {
 358         reiserfs_free_prealloc_block(th,ei->i_prealloc_block);
 359         ei->i_prealloc_block++;
 360         ei->i_prealloc_count --;
 361     }
 362     ei->i_prealloc_block = save;
 363     list_del_init(&(ei->i_prealloc_list));
 364 }
 365
 366 /* FIXME: It should be inline function */
 367 void reiserfs_discard_prealloc (struct reiserfs_transaction_handle *th,
 368                                 struct inode * inode)
 369 {
 370     struct reiserfs_inode_info *ei = REISERFS_I(inode);
 371     if (ei->i_prealloc_count) {
 372         __discard_prealloc(th, ei);
 373     }
 374 }
 375
 376 void reiserfs_discard_all_prealloc (struct reiserfs_transaction_handle *th)
 377 {
 378     struct list_head * plist = &SB_JOURNAL(th->t_super)->j_prealloc_list;
 379
 380     while (!list_empty(plist)) {
 381         struct reiserfs_inode_info *ei;
 382         ei = list_entry(plist->next, struct reiserfs_inode_info, i_prealloc_list);
 383 #ifdef CONFIG_REISERFS_CHECK
 384         if (!ei->i_prealloc_count) {
 385             reiserfs_warning("zam-4001:%s: inode is in prealloc list but has no preallocated blocks.\n", __FUNCTION__);
 386         }
 387 #endif
 388         __discard_prealloc(th, ei);
 389     }
 390 }
 391 /* block allocator related options are parsed here */
 392 int reiserfs_parse_alloc_options(struct super_block * s, char * options)
 393 {
 394     char * this_char, * value;
 395
 396     REISERFS_SB(s)->s_alloc_options.bits = 0; /* clear default settings */
 397
 398     while ( (this_char = strsep (&options, ":")) != NULL ) {
 399         if ((value = strchr (this_char, '=')) != NULL)
 400             *value++ = 0;
 401
 402         if (!strcmp(this_char, "concentrating_formatted_nodes")) {
 403             int temp;
 404             SET_OPTION(concentrating_formatted_nodes);
 405             temp = (value && *value) ? simple_strtoul (value, &value, 0) : 10;
 406             if (temp <= 0 || temp > 100) {
 407                 REISERFS_SB(s)->s_alloc_options.border = 10;
 408             } else {
 409                 REISERFS_SB(s)->s_alloc_options.border = 100 / temp;
 410            }
 411             continue;
 412         }
 413         if (!strcmp(this_char, "displacing_large_files")) {
 414             SET_OPTION(displacing_large_files);
 415             REISERFS_SB(s)->s_alloc_options.large_file_size =
 416                 (value && *value) ? simple_strtoul (value, &value, 0) : 16;
 417             continue;
 418         }
 419         if (!strcmp(this_char, "displacing_new_packing_localities")) {
 420             SET_OPTION(displacing_new_packing_localities);
 421             continue;
 422         };
 423
 424         if (!strcmp(this_char, "old_hashed_relocation")) {
 425             SET_OPTION(old_hashed_relocation);
 426             continue;
 427         }
 428
 429         if (!strcmp(this_char, "new_hashed_relocation")) {
 430             SET_OPTION(new_hashed_relocation);
 431             continue;
 432         }
 433
 434         if (!strcmp(this_char, "hashed_formatted_nodes")) {
 435             SET_OPTION(hashed_formatted_nodes);
 436             continue;
 437         }
 438
 439         if (!strcmp(this_char, "skip_busy")) {
 440             SET_OPTION(skip_busy);
 441             continue;
 442         }
 443
 444         if (!strcmp(this_char, "hundredth_slices")) {
 445             SET_OPTION(hundredth_slices);
 446             continue;
 447         }
 448
 449         if (!strcmp(this_char, "old_way")) {
 450             SET_OPTION(old_way);
 451             continue;
 452         }
 453
 454         if (!strcmp(this_char, "displace_based_on_dirid")) {
 455             SET_OPTION(displace_based_on_dirid);
 456             continue;
 457         }
 458
 459         if (!strcmp(this_char, "preallocmin")) {
 460             REISERFS_SB(s)->s_alloc_options.preallocmin =
 461                 (value && *value) ? simple_strtoul (value, &value, 0) : 4;
 462             continue;
 463         }
 464
 465         if (!strcmp(this_char, "preallocsize")) {
 466             REISERFS_SB(s)->s_alloc_options.preallocsize =
 467                 (value && *value) ? simple_strtoul (value, &value, 0) : PREALLOCATION_SIZE;
 468             continue;
 469         }
 470
 471         reiserfs_warning("zam-4001: %s : unknown option - %s\n", __FUNCTION__ , this_char);
 472         return 1;
 473       }
 474
 475     return 0;
 476 }
 477
 478 static inline void new_hashed_relocation (reiserfs_blocknr_hint_t * hint)
 479 {
 480     char * hash_in;
 481     if (hint->formatted_node) {
 482             hash_in = (char*)&hint->key.k_dir_id;
 483     } else {
 484         if (!hint->inode) {
 485             //hint->search_start = hint->beg;
 486             hash_in = (char*)&hint->key.k_dir_id;
 487         } else
 488             if ( TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
 489                 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
 490             else
 491                 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid);
 492       }
 493
 494     hint->search_start = hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
 495 }
 496
 497 static inline void get_left_neighbor(reiserfs_blocknr_hint_t *hint)
 498 {
 499     struct path * path;
 500     struct buffer_head * bh;
 501     struct item_head * ih;
 502     int pos_in_item;
 503     __u32 * item;
 504
 505     if (!hint->path)            /* reiserfs code can call this function w/o pointer to path
 506                                  * structure supplied; then we rely on supplied search_start */
 507         return;
 508
 509     path = hint->path;
 510     bh = get_last_bh(path);
 511     RFALSE( !bh, "green-4002: Illegal path specified to get_left_neighbor\n");
 512     ih = get_ih(path);
 513     pos_in_item = path->pos_in_item;
 514     item = get_item (path);
 515
 516     hint->search_start = bh->b_blocknr;
 517
 518     if (!hint->formatted_node && is_indirect_le_ih (ih)) {
 519         /* for indirect item: go to left and look for the first non-hole entry
 520            in the indirect item */
 521         if (pos_in_item == I_UNFM_NUM (ih))
 522             pos_in_item--;
 523 //          pos_in_item = I_UNFM_NUM (ih) - 1;
 524         while (pos_in_item >= 0) {
 525             int t=get_block_num(item,pos_in_item);
 526             if (t) {
 527                 hint->search_start = t;
 528                 break;
 529             }
 530             pos_in_item --;
 531         }
 532     } else {
 533       }
 534
 535     /* does result value fit into specified region? */
 536     return;
 537 }
 538
 539 /* should be, if formatted node, then try to put on first part of the device
 540    specified as number of percent with mount option device, else try to put
 541    on last of device.  This is not to say it is good code to do so,
 542    but the effect should be measured.  */
 543 static inline void set_border_in_hint(struct super_block *s, reiserfs_blocknr_hint_t *hint)
 544 {
 545     b_blocknr_t border = SB_BLOCK_COUNT(s) / REISERFS_SB(s)->s_alloc_options.border;
 546
 547     if (hint->formatted_node)
 548         hint->end = border - 1;
 549     else
 550         hint->beg = border;
 551 }
 552
 553 static inline void displace_large_file(reiserfs_blocknr_hint_t *hint)
 554 {
 555     if ( TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
 556         hint->search_start = hint->beg + keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_dir_id), 4) % (hint->end - hint->beg);
 557     else
 558         hint->search_start = hint->beg + keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_objectid), 4) % (hint->end - hint->beg);
 559 }
 560
 561 static inline void hash_formatted_node(reiserfs_blocknr_hint_t *hint)
 562 {
 563    char * hash_in;
 564
 565    if (!hint->inode)
 566         hash_in = (char*)&hint->key.k_dir_id;
 567     else if ( TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
 568         hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
 569     else
 570         hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid);
 571
 572         hint->search_start = hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
 573 }
 574
 575 static inline int this_blocknr_allocation_would_make_it_a_large_file(reiserfs_blocknr_hint_t *hint)
 576 {
 577     return hint->block == REISERFS_SB(hint->th->t_super)->s_alloc_options.large_file_size;
 578 }
 579
 580 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
 581 static inline void displace_new_packing_locality (reiserfs_blocknr_hint_t *hint)
 582 {
 583     struct key * key = &hint->key;
 584
 585     hint->th->displace_new_blocks = 0;
 586     hint->search_start = hint->beg + keyed_hash((char*)(&key->k_objectid),4) % (hint->end - hint->beg);
 587 }
 588   #endif
 589
 590 static inline int old_hashed_relocation (reiserfs_blocknr_hint_t * hint)
 591 {
 592     b_blocknr_t border;
 593     u32 hash_in;
 594
 595     if (hint->formatted_node || hint->inode == NULL) {
 596         return 0;
 597       }
 598
 599     hash_in = le32_to_cpu((INODE_PKEY(hint->inode))->k_dir_id);
 600     border = hint->beg + (u32) keyed_hash(((char *) (&hash_in)), 4) % (hint->end - hint->beg - 1);
 601     if (border > hint->search_start)
 602         hint->search_start = border;
 603
 604     return 1;
 605   }
 606
 607 static inline int old_way (reiserfs_blocknr_hint_t * hint)
 608 {
 609     b_blocknr_t border;
 610
 611     if (hint->formatted_node || hint->inode == NULL) {
 612         return 0;
 613     }
 614
 615       border = hint->beg + le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id) % (hint->end  - hint->beg);
 616     if (border > hint->search_start)
 617         hint->search_start = border;
 618
 619     return 1;
 620 }
 621
 622 static inline void hundredth_slices (reiserfs_blocknr_hint_t * hint)
 623 {
 624     struct key * key = &hint->key;
 625     b_blocknr_t slice_start;
 626
 627     slice_start = (keyed_hash((char*)(&key->k_dir_id),4) % 100) * (hint->end / 100);
 628     if ( slice_start > hint->search_start || slice_start + (hint->end / 100) <= hint->search_start) {
 629         hint->search_start = slice_start;
 630     }
 631 }
 632
 633 static inline void determine_search_start(reiserfs_blocknr_hint_t *hint,
 634                                           int amount_needed)
 635 {
 636     struct super_block *s = hint->th->t_super;
 637     hint->beg = 0;
 638     hint->end = SB_BLOCK_COUNT(s) - 1;
 639
 640     /* This is former border algorithm. Now with tunable border offset */
 641     if (concentrating_formatted_nodes(s))
 642         set_border_in_hint(s, hint);
 643
 644 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
 645     /* whenever we create a new directory, we displace it.  At first we will
 646        hash for location, later we might look for a moderately empty place for
 647        it */
 648     if (displacing_new_packing_localities(s)
 649         && hint->th->displace_new_blocks) {
 650         displace_new_packing_locality(hint);
 651
 652         /* we do not continue determine_search_start,
 653          * if new packing locality is being displaced */
 654         return;
 655     }
 656 #endif
 657
 658     /* all persons should feel encouraged to add more special cases here and
 659      * test them */
 660
 661     if (displacing_large_files(s) && !hint->formatted_node
 662         && this_blocknr_allocation_would_make_it_a_large_file(hint)) {
 663         displace_large_file(hint);
 664         return;
 665     }
 666
 667     /* attempt to copy a feature from old block allocator code */
 668     if (TEST_OPTION(old_hashed_relocation, s) && !hint->formatted_node) {
 669         old_hashed_relocation(hint);
 670     }
 671
 672     /* if none of our special cases is relevant, use the left neighbor in the
 673        tree order of the new node we are allocating for */
 674     if (hint->formatted_node && TEST_OPTION(hashed_formatted_nodes,s)) {
 675         hash_formatted_node(hint);
 676         return;
 677     }
 678
 679     get_left_neighbor(hint);
 680
 681     /* Mimic old block allocator behaviour, that is if VFS allowed for preallocation,
 682        new blocks are displaced based on directory ID. Also, if suggested search_start
 683        is less than last preallocated block, we start searching from it, assuming that
 684        HDD dataflow is faster in forward direction */
 685     if ( TEST_OPTION(old_way, s)) {
 686         if (!hint->formatted_node) {
 687             if ( !reiserfs_hashed_relocation(s))
 688                 old_way(hint);
 689             else if (!reiserfs_no_unhashed_relocation(s))
 690                 old_hashed_relocation(hint);
 691
 692             if ( hint->inode && hint->search_start < REISERFS_I(hint->inode)->i_prealloc_block)
 693                 hint->search_start = REISERFS_I(hint->inode)->i_prealloc_block;
 694         }
 695         return;
 696     }
 697
 698     /* This is an approach proposed by Hans */
 699     if ( TEST_OPTION(hundredth_slices, s) && ! (displacing_large_files(s) && !hint->formatted_node)) {
 700         hundredth_slices(hint);
 701         return;
 702     }
 703
 704     if (TEST_OPTION(old_hashed_relocation, s))
 705         old_hashed_relocation(hint);
 706     if (TEST_OPTION(new_hashed_relocation, s))
 707         new_hashed_relocation(hint);
 708     return;
 709 }
 710
 711 static int determine_prealloc_size(reiserfs_blocknr_hint_t * hint)
 712 {
 713     /* make minimum size a mount option and benchmark both ways */
 714     /* we preallocate blocks only for regular files, specific size */
 715     /* benchmark preallocating always and see what happens */
 716
 717     hint->prealloc_size = 0;
 718
 719     if (!hint->formatted_node && hint->preallocate) {
 720         if (S_ISREG(hint->inode->i_mode)
 721             && hint->inode->i_size >= REISERFS_SB(hint->th->t_super)->s_alloc_options.preallocmin * hint->inode->i_sb->s_blocksize)
 722             hint->prealloc_size = REISERFS_SB(hint->th->t_super)->s_alloc_options.preallocsize - 1;
 723     }
 724     return CARRY_ON;
 725 }
 726
 727 /* XXX I know it could be merged with upper-level function;
 728    but may be result function would be too complex. */
 729 static inline int allocate_without_wrapping_disk (reiserfs_blocknr_hint_t * hint,
 730                                          b_blocknr_t * new_blocknrs,
 731                                          b_blocknr_t start, b_blocknr_t finish,
 732                                          int amount_needed, int prealloc_size)
 733 {
 734     int rest = amount_needed;
 735     int nr_allocated;
 736
 737     while (rest > 0 && start <= finish) {
 738         nr_allocated = scan_bitmap (hint->th, &start, finish, 1,
 739                                     rest + prealloc_size, !hint->formatted_node,
 740                                     hint->block);
 741
 742         if (nr_allocated == 0)  /* no new blocks allocated, return */
 743             break;
 744
 745         /* fill free_blocknrs array first */
 746         while (rest > 0 && nr_allocated > 0) {
 747             * new_blocknrs ++ = start ++;
 748             rest --; nr_allocated --;
 749         }
 750
 751         /* do we have something to fill prealloc. array also ? */
 752         if (nr_allocated > 0) {
 753             /* it means prealloc_size was greater that 0 and we do preallocation */
 754             list_add(&REISERFS_I(hint->inode)->i_prealloc_list,
 755                      &SB_JOURNAL(hint->th->t_super)->j_prealloc_list);
 756             REISERFS_I(hint->inode)->i_prealloc_block = start;
 757             REISERFS_I(hint->inode)->i_prealloc_count = nr_allocated;
 758             break;
 759         }
 760     }
 761
 762     return (amount_needed - rest);
 763 }
 764
 765 static inline int blocknrs_and_prealloc_arrays_from_search_start
 766     (reiserfs_blocknr_hint_t *hint, b_blocknr_t *new_blocknrs, int amount_needed)
 767 {
 768     struct super_block *s = hint->th->t_super;
 769     b_blocknr_t start = hint->search_start;
 770     b_blocknr_t finish = SB_BLOCK_COUNT(s) - 1;
 771     int second_pass = 0;
 772     int nr_allocated = 0;
 773
 774     determine_prealloc_size(hint);
 775     while((nr_allocated
 776           += allocate_without_wrapping_disk(hint, new_blocknrs + nr_allocated, start, finish,
 777                                           amount_needed - nr_allocated, hint->prealloc_size))
 778           < amount_needed) {
 779
 780         /* not all blocks were successfully allocated yet*/
 781         if (second_pass) {      /* it was a second pass; we must free all blocks */
 782             while (nr_allocated --)
 783                 reiserfs_free_block(hint->th, new_blocknrs[nr_allocated]);
 784
 785             return NO_DISK_SPACE;
 786         } else {                /* refine search parameters for next pass */
 787             second_pass = 1;
 788             finish = start;
 789             start = 0;
 790             continue;
 791         }
 792       }
 793     return CARRY_ON;
 794 }
 795
 796 /* grab new blocknrs from preallocated list */
 797 /* return amount still needed after using them */
 798 static int use_preallocated_list_if_available (reiserfs_blocknr_hint_t *hint,
 799                                                b_blocknr_t *new_blocknrs, int amount_needed)
 800 {
 801     struct inode * inode = hint->inode;
 802
 803     if (REISERFS_I(inode)->i_prealloc_count > 0) {
 804         while (amount_needed) {
 805
 806             *new_blocknrs ++ = REISERFS_I(inode)->i_prealloc_block ++;
 807             REISERFS_I(inode)->i_prealloc_count --;
 808
 809             amount_needed --;
 810
 811             if (REISERFS_I(inode)->i_prealloc_count <= 0) {
 812                 list_del(&REISERFS_I(inode)->i_prealloc_list);
 813                 break;
 814             }
 815         }
 816       }
 817     /* return amount still needed after using preallocated blocks */
 818     return amount_needed;
 819 }
 820
 821 int reiserfs_allocate_blocknrs(reiserfs_blocknr_hint_t *hint,
 822                                b_blocknr_t * new_blocknrs, int amount_needed,
 823                                int reserved_by_us /* Amount of blocks we have
 824                                                       already reserved */)
 825 {
 826     int initial_amount_needed = amount_needed;
 827     int ret;
 828
 829     /* Check if there is enough space, taking into account reserved space */
 830     if ( SB_FREE_BLOCKS(hint->th->t_super) - REISERFS_SB(hint->th->t_super)->reserved_blocks <
 831          amount_needed - reserved_by_us)
 832         return NO_DISK_SPACE;
 833     /* should this be if !hint->inode &&  hint->preallocate? */
 834     /* do you mean hint->formatted_node can be removed ? - Zam */
 835     /* hint->formatted_node cannot be removed because we try to access
 836        inode information here, and there is often no inode assotiated with
 837        metadata allocations - green */
 838
 839     if (!hint->formatted_node && hint->preallocate) {
 840         amount_needed = use_preallocated_list_if_available
 841             (hint, new_blocknrs, amount_needed);
 842         if (amount_needed == 0) /* all blocknrs we need we got from
 843                                    prealloc. list */
 844             return CARRY_ON;
 845         new_blocknrs += (initial_amount_needed - amount_needed);
 846     }
 847
 848     /* find search start and save it in hint structure */
 849     determine_search_start(hint, amount_needed);
 850
 851     /* allocation itself; fill new_blocknrs and preallocation arrays */
 852     ret = blocknrs_and_prealloc_arrays_from_search_start
 853         (hint, new_blocknrs, amount_needed);
 854
 855     /* we used prealloc. list to fill (partially) new_blocknrs array. If final allocation fails we
 856      * need to return blocks back to prealloc. list or just free them. -- Zam (I chose second
 857      * variant) */
 858
 859     if (ret != CARRY_ON) {
 860         while (amount_needed ++ < initial_amount_needed) {
 861             reiserfs_free_block(hint->th, *(--new_blocknrs));
 862         }
 863     }
 864     return ret;
 865 }
 866
 867 /* These 2 functions are here to provide blocks reservation to the rest of kernel */
 868 /* Reserve @blocks amount of blocks in fs pointed by @sb. Caller must make sure
 869    there are actually this much blocks on the FS available */
 870 void reiserfs_claim_blocks_to_be_allocated(
 871                                       struct super_block *sb, /* super block of
 872                                                                 filesystem where
 873                                                                 blocks should be
 874                                                                 reserved */
 875                                       int blocks /* How much to reserve */
 876                                           )
 877 {
 878
 879     /* Fast case, if reservation is zero - exit immediately. */
 880     if ( !blocks )
 881         return;
 882
 883     spin_lock(&REISERFS_SB(sb)->bitmap_lock);
 884     REISERFS_SB(sb)->reserved_blocks += blocks;
 885     spin_unlock(&REISERFS_SB(sb)->bitmap_lock);
 886 }
 887
 888 /* Unreserve @blocks amount of blocks in fs pointed by @sb */
 889 void reiserfs_release_claimed_blocks(
 890                                 struct super_block *sb, /* super block of
 891                                                           filesystem where
 892                                                           blocks should be
 893                                                           reserved */
 894                                 int blocks /* How much to unreserve */
 895                                           )
 896 {
 897
 898     /* Fast case, if unreservation is zero - exit immediately. */
 899     if ( !blocks )
 900         return;
 901
 902     spin_lock(&REISERFS_SB(sb)->bitmap_lock);
 903     REISERFS_SB(sb)->reserved_blocks -= blocks;
 904     spin_unlock(&REISERFS_SB(sb)->bitmap_lock);
 905     RFALSE( REISERFS_SB(sb)->reserved_blocks < 0, "amount of blocks reserved became zero?");
 906 }
 907
 908 /* This function estimates how much pages we will be able to write to FS
 909    used for reiserfs_file_write() purposes for now. */
 910 int reiserfs_can_fit_pages ( struct super_block *sb /* superblock of filesystem
 911                                                        to estimate space */ )
 912 {
 913         int space;
 914
 915         spin_lock(&REISERFS_SB(sb)->bitmap_lock);
 916         space = (SB_FREE_BLOCKS(sb) - REISERFS_SB(sb)->reserved_blocks) >> ( PAGE_CACHE_SHIFT - sb->s_blocksize_bits);
 917         spin_unlock(&REISERFS_SB(sb)->bitmap_lock);
 918
 919         return space>0?space:0;
 920 }