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