fs/reiserfs/bitmap.c

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