fs/reiserfs/bitmap.c

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