Back to home page

OSCL-LXR
 
 

     

0001 /*
0002  * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
0003  */
0004 /* Reiserfs block (de)allocator, bitmap-based. */
0005 
0006 #include <linux/time.h>
0007 #include "reiserfs.h"
0008 #include <linux/errno.h>
0009 #include <linux/buffer_head.h>
0010 #include <linux/kernel.h>
0011 #include <linux/pagemap.h>
0012 #include <linux/vmalloc.h>
0013 #include <linux/quotaops.h>
0014 #include <linux/seq_file.h>
0015 
0016 #define PREALLOCATION_SIZE 9
0017 
0018 /* different reiserfs block allocator options */
0019 
0020 #define SB_ALLOC_OPTS(s) (REISERFS_SB(s)->s_alloc_options.bits)
0021 
0022 #define  _ALLOC_concentrating_formatted_nodes 0
0023 #define  _ALLOC_displacing_large_files 1
0024 #define  _ALLOC_displacing_new_packing_localities 2
0025 #define  _ALLOC_old_hashed_relocation 3
0026 #define  _ALLOC_new_hashed_relocation 4
0027 #define  _ALLOC_skip_busy 5
0028 #define  _ALLOC_displace_based_on_dirid 6
0029 #define  _ALLOC_hashed_formatted_nodes 7
0030 #define  _ALLOC_old_way 8
0031 #define  _ALLOC_hundredth_slices 9
0032 #define  _ALLOC_dirid_groups 10
0033 #define  _ALLOC_oid_groups 11
0034 #define  _ALLOC_packing_groups 12
0035 
0036 #define  concentrating_formatted_nodes(s)   test_bit(_ALLOC_concentrating_formatted_nodes, &SB_ALLOC_OPTS(s))
0037 #define  displacing_large_files(s)      test_bit(_ALLOC_displacing_large_files, &SB_ALLOC_OPTS(s))
0038 #define  displacing_new_packing_localities(s)   test_bit(_ALLOC_displacing_new_packing_localities, &SB_ALLOC_OPTS(s))
0039 
0040 #define SET_OPTION(optname) \
0041    do { \
0042     reiserfs_info(s, "block allocator option \"%s\" is set", #optname); \
0043     set_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s)); \
0044     } while(0)
0045 #define TEST_OPTION(optname, s) \
0046     test_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s))
0047 
0048 static inline void get_bit_address(struct super_block *s,
0049                    b_blocknr_t block,
0050                    unsigned int *bmap_nr,
0051                    unsigned int *offset)
0052 {
0053     /*
0054      * It is in the bitmap block number equal to the block
0055      * number divided by the number of bits in a block.
0056      */
0057     *bmap_nr = block >> (s->s_blocksize_bits + 3);
0058     /* Within that bitmap block it is located at bit offset *offset. */
0059     *offset = block & ((s->s_blocksize << 3) - 1);
0060 }
0061 
0062 int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value)
0063 {
0064     unsigned int bmap, offset;
0065     unsigned int bmap_count = reiserfs_bmap_count(s);
0066 
0067     if (block == 0 || block >= SB_BLOCK_COUNT(s)) {
0068         reiserfs_error(s, "vs-4010",
0069                    "block number is out of range %lu (%u)",
0070                    block, SB_BLOCK_COUNT(s));
0071         return 0;
0072     }
0073 
0074     get_bit_address(s, block, &bmap, &offset);
0075 
0076     /*
0077      * Old format filesystem? Unlikely, but the bitmaps are all
0078      * up front so we need to account for it.
0079      */
0080     if (unlikely(test_bit(REISERFS_OLD_FORMAT,
0081                   &REISERFS_SB(s)->s_properties))) {
0082         b_blocknr_t bmap1 = REISERFS_SB(s)->s_sbh->b_blocknr + 1;
0083         if (block >= bmap1 &&
0084             block <= bmap1 + bmap_count) {
0085             reiserfs_error(s, "vs-4019", "bitmap block %lu(%u) "
0086                        "can't be freed or reused",
0087                        block, bmap_count);
0088             return 0;
0089         }
0090     } else {
0091         if (offset == 0) {
0092             reiserfs_error(s, "vs-4020", "bitmap block %lu(%u) "
0093                        "can't be freed or reused",
0094                        block, bmap_count);
0095             return 0;
0096         }
0097     }
0098 
0099     if (bmap >= bmap_count) {
0100         reiserfs_error(s, "vs-4030", "bitmap for requested block "
0101                    "is out of range: block=%lu, bitmap_nr=%u",
0102                    block, bmap);
0103         return 0;
0104     }
0105 
0106     if (bit_value == 0 && block == SB_ROOT_BLOCK(s)) {
0107         reiserfs_error(s, "vs-4050", "this is root block (%u), "
0108                    "it must be busy", SB_ROOT_BLOCK(s));
0109         return 0;
0110     }
0111 
0112     return 1;
0113 }
0114 
0115 /*
0116  * Searches in journal structures for a given block number (bmap, off).
0117  * If block is found in reiserfs journal it suggests next free block
0118  * candidate to test.
0119  */
0120 static inline int is_block_in_journal(struct super_block *s, unsigned int bmap,
0121                       int off, int *next)
0122 {
0123     b_blocknr_t tmp;
0124 
0125     if (reiserfs_in_journal(s, bmap, off, 1, &tmp)) {
0126         if (tmp) {  /* hint supplied */
0127             *next = tmp;
0128             PROC_INFO_INC(s, scan_bitmap.in_journal_hint);
0129         } else {
0130             (*next) = off + 1;  /* inc offset to avoid looping. */
0131             PROC_INFO_INC(s, scan_bitmap.in_journal_nohint);
0132         }
0133         PROC_INFO_INC(s, scan_bitmap.retry);
0134         return 1;
0135     }
0136     return 0;
0137 }
0138 
0139 /*
0140  * Searches for a window of zero bits with given minimum and maximum
0141  * lengths in one bitmap block
0142  */
0143 static int scan_bitmap_block(struct reiserfs_transaction_handle *th,
0144                  unsigned int bmap_n, int *beg, int boundary,
0145                  int min, int max, int unfm)
0146 {
0147     struct super_block *s = th->t_super;
0148     struct reiserfs_bitmap_info *bi = &SB_AP_BITMAP(s)[bmap_n];
0149     struct buffer_head *bh;
0150     int end, next;
0151     int org = *beg;
0152 
0153     BUG_ON(!th->t_trans_id);
0154     RFALSE(bmap_n >= reiserfs_bmap_count(s), "Bitmap %u is out of "
0155            "range (0..%u)", bmap_n, reiserfs_bmap_count(s) - 1);
0156     PROC_INFO_INC(s, scan_bitmap.bmap);
0157 
0158     if (!bi) {
0159         reiserfs_error(s, "jdm-4055", "NULL bitmap info pointer "
0160                    "for bitmap %d", bmap_n);
0161         return 0;
0162     }
0163 
0164     bh = reiserfs_read_bitmap_block(s, bmap_n);
0165     if (bh == NULL)
0166         return 0;
0167 
0168     while (1) {
0169 cont:
0170         if (bi->free_count < min) {
0171             brelse(bh);
0172             return 0;   /* No free blocks in this bitmap */
0173         }
0174 
0175         /* search for a first zero bit -- beginning of a window */
0176         *beg = reiserfs_find_next_zero_le_bit
0177             ((unsigned long *)(bh->b_data), boundary, *beg);
0178 
0179         /*
0180          * search for a zero bit fails or the rest of bitmap block
0181          * cannot contain a zero window of minimum size
0182          */
0183         if (*beg + min > boundary) {
0184             brelse(bh);
0185             return 0;
0186         }
0187 
0188         if (unfm && is_block_in_journal(s, bmap_n, *beg, beg))
0189             continue;
0190         /* first zero bit found; we check next bits */
0191         for (end = *beg + 1;; end++) {
0192             if (end >= *beg + max || end >= boundary
0193                 || reiserfs_test_le_bit(end, bh->b_data)) {
0194                 next = end;
0195                 break;
0196             }
0197 
0198             /*
0199              * finding the other end of zero bit window requires
0200              * looking into journal structures (in case of
0201              * searching for free blocks for unformatted nodes)
0202              */
0203             if (unfm && is_block_in_journal(s, bmap_n, end, &next))
0204                 break;
0205         }
0206 
0207         /*
0208          * now (*beg) points to beginning of zero bits window,
0209          * (end) points to one bit after the window end
0210          */
0211 
0212         /* found window of proper size */
0213         if (end - *beg >= min) {
0214             int i;
0215             reiserfs_prepare_for_journal(s, bh, 1);
0216             /*
0217              * try to set all blocks used checking are
0218              * they still free
0219              */
0220             for (i = *beg; i < end; i++) {
0221                 /* Don't check in journal again. */
0222                 if (reiserfs_test_and_set_le_bit
0223                     (i, bh->b_data)) {
0224                     /*
0225                      * bit was set by another process while
0226                      * we slept in prepare_for_journal()
0227                      */
0228                     PROC_INFO_INC(s, scan_bitmap.stolen);
0229 
0230                     /*
0231                      * we can continue with smaller set
0232                      * of allocated blocks, if length of
0233                      * this set is more or equal to `min'
0234                      */
0235                     if (i >= *beg + min) {
0236                         end = i;
0237                         break;
0238                     }
0239 
0240                     /*
0241                      * otherwise we clear all bit
0242                      * were set ...
0243                      */
0244                     while (--i >= *beg)
0245                         reiserfs_clear_le_bit
0246                             (i, bh->b_data);
0247                     reiserfs_restore_prepared_buffer(s, bh);
0248                     *beg = org;
0249 
0250                     /*
0251                      * Search again in current block
0252                      * from beginning
0253                      */
0254                     goto cont;
0255                 }
0256             }
0257             bi->free_count -= (end - *beg);
0258             journal_mark_dirty(th, bh);
0259             brelse(bh);
0260 
0261             /* free block count calculation */
0262             reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s),
0263                              1);
0264             PUT_SB_FREE_BLOCKS(s, SB_FREE_BLOCKS(s) - (end - *beg));
0265             journal_mark_dirty(th, SB_BUFFER_WITH_SB(s));
0266 
0267             return end - (*beg);
0268         } else {
0269             *beg = next;
0270         }
0271     }
0272 }
0273 
0274 static int bmap_hash_id(struct super_block *s, u32 id)
0275 {
0276     char *hash_in = NULL;
0277     unsigned long hash;
0278     unsigned bm;
0279 
0280     if (id <= 2) {
0281         bm = 1;
0282     } else {
0283         hash_in = (char *)(&id);
0284         hash = keyed_hash(hash_in, 4);
0285         bm = hash % reiserfs_bmap_count(s);
0286         if (!bm)
0287             bm = 1;
0288     }
0289     /* this can only be true when SB_BMAP_NR = 1 */
0290     if (bm >= reiserfs_bmap_count(s))
0291         bm = 0;
0292     return bm;
0293 }
0294 
0295 /*
0296  * hashes the id and then returns > 0 if the block group for the
0297  * corresponding hash is full
0298  */
0299 static inline int block_group_used(struct super_block *s, u32 id)
0300 {
0301     int bm = bmap_hash_id(s, id);
0302     struct reiserfs_bitmap_info *info = &SB_AP_BITMAP(s)[bm];
0303 
0304     /*
0305      * If we don't have cached information on this bitmap block, we're
0306      * going to have to load it later anyway. Loading it here allows us
0307      * to make a better decision. This favors long-term performance gain
0308      * with a better on-disk layout vs. a short term gain of skipping the
0309      * read and potentially having a bad placement.
0310      */
0311     if (info->free_count == UINT_MAX) {
0312         struct buffer_head *bh = reiserfs_read_bitmap_block(s, bm);
0313         brelse(bh);
0314     }
0315 
0316     if (info->free_count > ((s->s_blocksize << 3) * 60 / 100)) {
0317         return 0;
0318     }
0319     return 1;
0320 }
0321 
0322 /*
0323  * the packing is returned in disk byte order
0324  */
0325 __le32 reiserfs_choose_packing(struct inode * dir)
0326 {
0327     __le32 packing;
0328     if (TEST_OPTION(packing_groups, dir->i_sb)) {
0329         u32 parent_dir = le32_to_cpu(INODE_PKEY(dir)->k_dir_id);
0330         /*
0331          * some versions of reiserfsck expect packing locality 1 to be
0332          * special
0333          */
0334         if (parent_dir == 1 || block_group_used(dir->i_sb, parent_dir))
0335             packing = INODE_PKEY(dir)->k_objectid;
0336         else
0337             packing = INODE_PKEY(dir)->k_dir_id;
0338     } else
0339         packing = INODE_PKEY(dir)->k_objectid;
0340     return packing;
0341 }
0342 
0343 /*
0344  * Tries to find contiguous zero bit window (given size) in given region of
0345  * bitmap and place new blocks there. Returns number of allocated blocks.
0346  */
0347 static int scan_bitmap(struct reiserfs_transaction_handle *th,
0348                b_blocknr_t * start, b_blocknr_t finish,
0349                int min, int max, int unfm, sector_t file_block)
0350 {
0351     int nr_allocated = 0;
0352     struct super_block *s = th->t_super;
0353     unsigned int bm, off;
0354     unsigned int end_bm, end_off;
0355     unsigned int off_max = s->s_blocksize << 3;
0356 
0357     BUG_ON(!th->t_trans_id);
0358     PROC_INFO_INC(s, scan_bitmap.call);
0359 
0360     /* No point in looking for more free blocks */
0361     if (SB_FREE_BLOCKS(s) <= 0)
0362         return 0;
0363 
0364     get_bit_address(s, *start, &bm, &off);
0365     get_bit_address(s, finish, &end_bm, &end_off);
0366     if (bm > reiserfs_bmap_count(s))
0367         return 0;
0368     if (end_bm > reiserfs_bmap_count(s))
0369         end_bm = reiserfs_bmap_count(s);
0370 
0371     /*
0372      * When the bitmap is more than 10% free, anyone can allocate.
0373      * When it's less than 10% free, only files that already use the
0374      * bitmap are allowed. Once we pass 80% full, this restriction
0375      * is lifted.
0376      *
0377      * We do this so that files that grow later still have space close to
0378      * their original allocation. This improves locality, and presumably
0379      * performance as a result.
0380      *
0381      * This is only an allocation policy and does not make up for getting a
0382      * bad hint. Decent hinting must be implemented for this to work well.
0383      */
0384     if (TEST_OPTION(skip_busy, s)
0385         && SB_FREE_BLOCKS(s) > SB_BLOCK_COUNT(s) / 20) {
0386         for (; bm < end_bm; bm++, off = 0) {
0387             if ((off && (!unfm || (file_block != 0)))
0388                 || SB_AP_BITMAP(s)[bm].free_count >
0389                 (s->s_blocksize << 3) / 10)
0390                 nr_allocated =
0391                     scan_bitmap_block(th, bm, &off, off_max,
0392                               min, max, unfm);
0393             if (nr_allocated)
0394                 goto ret;
0395         }
0396         /* we know from above that start is a reasonable number */
0397         get_bit_address(s, *start, &bm, &off);
0398     }
0399 
0400     for (; bm < end_bm; bm++, off = 0) {
0401         nr_allocated =
0402             scan_bitmap_block(th, bm, &off, off_max, min, max, unfm);
0403         if (nr_allocated)
0404             goto ret;
0405     }
0406 
0407     nr_allocated =
0408         scan_bitmap_block(th, bm, &off, end_off + 1, min, max, unfm);
0409 
0410 ret:
0411     *start = bm * off_max + off;
0412     return nr_allocated;
0413 
0414 }
0415 
0416 static void _reiserfs_free_block(struct reiserfs_transaction_handle *th,
0417                  struct inode *inode, b_blocknr_t block,
0418                  int for_unformatted)
0419 {
0420     struct super_block *s = th->t_super;
0421     struct reiserfs_super_block *rs;
0422     struct buffer_head *sbh, *bmbh;
0423     struct reiserfs_bitmap_info *apbi;
0424     unsigned int nr, offset;
0425 
0426     BUG_ON(!th->t_trans_id);
0427     PROC_INFO_INC(s, free_block);
0428     rs = SB_DISK_SUPER_BLOCK(s);
0429     sbh = SB_BUFFER_WITH_SB(s);
0430     apbi = SB_AP_BITMAP(s);
0431 
0432     get_bit_address(s, block, &nr, &offset);
0433 
0434     if (nr >= reiserfs_bmap_count(s)) {
0435         reiserfs_error(s, "vs-4075", "block %lu is out of range",
0436                    block);
0437         return;
0438     }
0439 
0440     bmbh = reiserfs_read_bitmap_block(s, nr);
0441     if (!bmbh)
0442         return;
0443 
0444     reiserfs_prepare_for_journal(s, bmbh, 1);
0445 
0446     /* clear bit for the given block in bit map */
0447     if (!reiserfs_test_and_clear_le_bit(offset, bmbh->b_data)) {
0448         reiserfs_error(s, "vs-4080",
0449                    "block %lu: bit already cleared", block);
0450     }
0451     apbi[nr].free_count++;
0452     journal_mark_dirty(th, bmbh);
0453     brelse(bmbh);
0454 
0455     reiserfs_prepare_for_journal(s, sbh, 1);
0456     /* update super block */
0457     set_sb_free_blocks(rs, sb_free_blocks(rs) + 1);
0458 
0459     journal_mark_dirty(th, sbh);
0460     if (for_unformatted) {
0461         int depth = reiserfs_write_unlock_nested(s);
0462         dquot_free_block_nodirty(inode, 1);
0463         reiserfs_write_lock_nested(s, depth);
0464     }
0465 }
0466 
0467 void reiserfs_free_block(struct reiserfs_transaction_handle *th,
0468              struct inode *inode, b_blocknr_t block,
0469              int for_unformatted)
0470 {
0471     struct super_block *s = th->t_super;
0472 
0473     BUG_ON(!th->t_trans_id);
0474     RFALSE(!s, "vs-4061: trying to free block on nonexistent device");
0475     if (!is_reusable(s, block, 1))
0476         return;
0477 
0478     if (block > sb_block_count(REISERFS_SB(s)->s_rs)) {
0479         reiserfs_error(th->t_super, "bitmap-4072",
0480                    "Trying to free block outside file system "
0481                    "boundaries (%lu > %lu)",
0482                    block, sb_block_count(REISERFS_SB(s)->s_rs));
0483         return;
0484     }
0485     /* mark it before we clear it, just in case */
0486     journal_mark_freed(th, s, block);
0487     _reiserfs_free_block(th, inode, block, for_unformatted);
0488 }
0489 
0490 /* preallocated blocks don't need to be run through journal_mark_freed */
0491 static void reiserfs_free_prealloc_block(struct reiserfs_transaction_handle *th,
0492                      struct inode *inode, b_blocknr_t block)
0493 {
0494     BUG_ON(!th->t_trans_id);
0495     RFALSE(!th->t_super,
0496            "vs-4060: trying to free block on nonexistent device");
0497     if (!is_reusable(th->t_super, block, 1))
0498         return;
0499     _reiserfs_free_block(th, inode, block, 1);
0500 }
0501 
0502 static void __discard_prealloc(struct reiserfs_transaction_handle *th,
0503                    struct reiserfs_inode_info *ei)
0504 {
0505     unsigned long save = ei->i_prealloc_block;
0506     int dirty = 0;
0507     struct inode *inode = &ei->vfs_inode;
0508 
0509     BUG_ON(!th->t_trans_id);
0510 #ifdef CONFIG_REISERFS_CHECK
0511     if (ei->i_prealloc_count < 0)
0512         reiserfs_error(th->t_super, "zam-4001",
0513                    "inode has negative prealloc blocks count.");
0514 #endif
0515     while (ei->i_prealloc_count > 0) {
0516         b_blocknr_t block_to_free;
0517 
0518         /*
0519          * reiserfs_free_prealloc_block can drop the write lock,
0520          * which could allow another caller to free the same block.
0521          * We can protect against it by modifying the prealloc
0522          * state before calling it.
0523          */
0524         block_to_free = ei->i_prealloc_block++;
0525         ei->i_prealloc_count--;
0526         reiserfs_free_prealloc_block(th, inode, block_to_free);
0527         dirty = 1;
0528     }
0529     if (dirty)
0530         reiserfs_update_sd(th, inode);
0531     ei->i_prealloc_block = save;
0532     list_del_init(&ei->i_prealloc_list);
0533 }
0534 
0535 /* FIXME: It should be inline function */
0536 void reiserfs_discard_prealloc(struct reiserfs_transaction_handle *th,
0537                    struct inode *inode)
0538 {
0539     struct reiserfs_inode_info *ei = REISERFS_I(inode);
0540 
0541     BUG_ON(!th->t_trans_id);
0542     if (ei->i_prealloc_count)
0543         __discard_prealloc(th, ei);
0544 }
0545 
0546 void reiserfs_discard_all_prealloc(struct reiserfs_transaction_handle *th)
0547 {
0548     struct list_head *plist = &SB_JOURNAL(th->t_super)->j_prealloc_list;
0549 
0550     BUG_ON(!th->t_trans_id);
0551     while (!list_empty(plist)) {
0552         struct reiserfs_inode_info *ei;
0553         ei = list_entry(plist->next, struct reiserfs_inode_info,
0554                 i_prealloc_list);
0555 #ifdef CONFIG_REISERFS_CHECK
0556         if (!ei->i_prealloc_count) {
0557             reiserfs_error(th->t_super, "zam-4001",
0558                        "inode is in prealloc list but has "
0559                        "no preallocated blocks.");
0560         }
0561 #endif
0562         __discard_prealloc(th, ei);
0563     }
0564 }
0565 
0566 void reiserfs_init_alloc_options(struct super_block *s)
0567 {
0568     set_bit(_ALLOC_skip_busy, &SB_ALLOC_OPTS(s));
0569     set_bit(_ALLOC_dirid_groups, &SB_ALLOC_OPTS(s));
0570     set_bit(_ALLOC_packing_groups, &SB_ALLOC_OPTS(s));
0571 }
0572 
0573 /* block allocator related options are parsed here */
0574 int reiserfs_parse_alloc_options(struct super_block *s, char *options)
0575 {
0576     char *this_char, *value;
0577 
0578     /* clear default settings */
0579     REISERFS_SB(s)->s_alloc_options.bits = 0;
0580 
0581     while ((this_char = strsep(&options, ":")) != NULL) {
0582         if ((value = strchr(this_char, '=')) != NULL)
0583             *value++ = 0;
0584 
0585         if (!strcmp(this_char, "concentrating_formatted_nodes")) {
0586             int temp;
0587             SET_OPTION(concentrating_formatted_nodes);
0588             temp = (value
0589                 && *value) ? simple_strtoul(value, &value,
0590                                 0) : 10;
0591             if (temp <= 0 || temp > 100) {
0592                 REISERFS_SB(s)->s_alloc_options.border = 10;
0593             } else {
0594                 REISERFS_SB(s)->s_alloc_options.border =
0595                     100 / temp;
0596             }
0597             continue;
0598         }
0599         if (!strcmp(this_char, "displacing_large_files")) {
0600             SET_OPTION(displacing_large_files);
0601             REISERFS_SB(s)->s_alloc_options.large_file_size =
0602                 (value
0603                  && *value) ? simple_strtoul(value, &value, 0) : 16;
0604             continue;
0605         }
0606         if (!strcmp(this_char, "displacing_new_packing_localities")) {
0607             SET_OPTION(displacing_new_packing_localities);
0608             continue;
0609         }
0610 
0611         if (!strcmp(this_char, "old_hashed_relocation")) {
0612             SET_OPTION(old_hashed_relocation);
0613             continue;
0614         }
0615 
0616         if (!strcmp(this_char, "new_hashed_relocation")) {
0617             SET_OPTION(new_hashed_relocation);
0618             continue;
0619         }
0620 
0621         if (!strcmp(this_char, "dirid_groups")) {
0622             SET_OPTION(dirid_groups);
0623             continue;
0624         }
0625         if (!strcmp(this_char, "oid_groups")) {
0626             SET_OPTION(oid_groups);
0627             continue;
0628         }
0629         if (!strcmp(this_char, "packing_groups")) {
0630             SET_OPTION(packing_groups);
0631             continue;
0632         }
0633         if (!strcmp(this_char, "hashed_formatted_nodes")) {
0634             SET_OPTION(hashed_formatted_nodes);
0635             continue;
0636         }
0637 
0638         if (!strcmp(this_char, "skip_busy")) {
0639             SET_OPTION(skip_busy);
0640             continue;
0641         }
0642 
0643         if (!strcmp(this_char, "hundredth_slices")) {
0644             SET_OPTION(hundredth_slices);
0645             continue;
0646         }
0647 
0648         if (!strcmp(this_char, "old_way")) {
0649             SET_OPTION(old_way);
0650             continue;
0651         }
0652 
0653         if (!strcmp(this_char, "displace_based_on_dirid")) {
0654             SET_OPTION(displace_based_on_dirid);
0655             continue;
0656         }
0657 
0658         if (!strcmp(this_char, "preallocmin")) {
0659             REISERFS_SB(s)->s_alloc_options.preallocmin =
0660                 (value
0661                  && *value) ? simple_strtoul(value, &value, 0) : 4;
0662             continue;
0663         }
0664 
0665         if (!strcmp(this_char, "preallocsize")) {
0666             REISERFS_SB(s)->s_alloc_options.preallocsize =
0667                 (value
0668                  && *value) ? simple_strtoul(value, &value,
0669                              0) :
0670                 PREALLOCATION_SIZE;
0671             continue;
0672         }
0673 
0674         reiserfs_warning(s, "zam-4001", "unknown option - %s",
0675                  this_char);
0676         return 1;
0677     }
0678 
0679     reiserfs_info(s, "allocator options = [%08x]\n", SB_ALLOC_OPTS(s));
0680     return 0;
0681 }
0682 
0683 static void print_sep(struct seq_file *seq, int *first)
0684 {
0685     if (!*first)
0686         seq_puts(seq, ":");
0687     else
0688         *first = 0;
0689 }
0690 
0691 void show_alloc_options(struct seq_file *seq, struct super_block *s)
0692 {
0693     int first = 1;
0694 
0695     if (SB_ALLOC_OPTS(s) == ((1 << _ALLOC_skip_busy) |
0696         (1 << _ALLOC_dirid_groups) | (1 << _ALLOC_packing_groups)))
0697         return;
0698 
0699     seq_puts(seq, ",alloc=");
0700 
0701     if (TEST_OPTION(concentrating_formatted_nodes, s)) {
0702         print_sep(seq, &first);
0703         if (REISERFS_SB(s)->s_alloc_options.border != 10) {
0704             seq_printf(seq, "concentrating_formatted_nodes=%d",
0705                 100 / REISERFS_SB(s)->s_alloc_options.border);
0706         } else
0707             seq_puts(seq, "concentrating_formatted_nodes");
0708     }
0709     if (TEST_OPTION(displacing_large_files, s)) {
0710         print_sep(seq, &first);
0711         if (REISERFS_SB(s)->s_alloc_options.large_file_size != 16) {
0712             seq_printf(seq, "displacing_large_files=%lu",
0713                 REISERFS_SB(s)->s_alloc_options.large_file_size);
0714         } else
0715             seq_puts(seq, "displacing_large_files");
0716     }
0717     if (TEST_OPTION(displacing_new_packing_localities, s)) {
0718         print_sep(seq, &first);
0719         seq_puts(seq, "displacing_new_packing_localities");
0720     }
0721     if (TEST_OPTION(old_hashed_relocation, s)) {
0722         print_sep(seq, &first);
0723         seq_puts(seq, "old_hashed_relocation");
0724     }
0725     if (TEST_OPTION(new_hashed_relocation, s)) {
0726         print_sep(seq, &first);
0727         seq_puts(seq, "new_hashed_relocation");
0728     }
0729     if (TEST_OPTION(dirid_groups, s)) {
0730         print_sep(seq, &first);
0731         seq_puts(seq, "dirid_groups");
0732     }
0733     if (TEST_OPTION(oid_groups, s)) {
0734         print_sep(seq, &first);
0735         seq_puts(seq, "oid_groups");
0736     }
0737     if (TEST_OPTION(packing_groups, s)) {
0738         print_sep(seq, &first);
0739         seq_puts(seq, "packing_groups");
0740     }
0741     if (TEST_OPTION(hashed_formatted_nodes, s)) {
0742         print_sep(seq, &first);
0743         seq_puts(seq, "hashed_formatted_nodes");
0744     }
0745     if (TEST_OPTION(skip_busy, s)) {
0746         print_sep(seq, &first);
0747         seq_puts(seq, "skip_busy");
0748     }
0749     if (TEST_OPTION(hundredth_slices, s)) {
0750         print_sep(seq, &first);
0751         seq_puts(seq, "hundredth_slices");
0752     }
0753     if (TEST_OPTION(old_way, s)) {
0754         print_sep(seq, &first);
0755         seq_puts(seq, "old_way");
0756     }
0757     if (TEST_OPTION(displace_based_on_dirid, s)) {
0758         print_sep(seq, &first);
0759         seq_puts(seq, "displace_based_on_dirid");
0760     }
0761     if (REISERFS_SB(s)->s_alloc_options.preallocmin != 0) {
0762         print_sep(seq, &first);
0763         seq_printf(seq, "preallocmin=%d",
0764                 REISERFS_SB(s)->s_alloc_options.preallocmin);
0765     }
0766     if (REISERFS_SB(s)->s_alloc_options.preallocsize != 17) {
0767         print_sep(seq, &first);
0768         seq_printf(seq, "preallocsize=%d",
0769                 REISERFS_SB(s)->s_alloc_options.preallocsize);
0770     }
0771 }
0772 
0773 static inline void new_hashed_relocation(reiserfs_blocknr_hint_t * hint)
0774 {
0775     char *hash_in;
0776 
0777     if (hint->formatted_node) {
0778         hash_in = (char *)&hint->key.k_dir_id;
0779     } else {
0780         if (!hint->inode) {
0781             /*hint->search_start = hint->beg;*/
0782             hash_in = (char *)&hint->key.k_dir_id;
0783         } else
0784             if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
0785             hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
0786         else
0787             hash_in =
0788                 (char *)(&INODE_PKEY(hint->inode)->k_objectid);
0789     }
0790 
0791     hint->search_start =
0792         hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
0793 }
0794 
0795 /*
0796  * Relocation based on dirid, hashing them into a given bitmap block
0797  * files. Formatted nodes are unaffected, a separate policy covers them
0798  */
0799 static void dirid_groups(reiserfs_blocknr_hint_t * hint)
0800 {
0801     unsigned long hash;
0802     __u32 dirid = 0;
0803     int bm = 0;
0804     struct super_block *sb = hint->th->t_super;
0805 
0806     if (hint->inode)
0807         dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id);
0808     else if (hint->formatted_node)
0809         dirid = hint->key.k_dir_id;
0810 
0811     if (dirid) {
0812         bm = bmap_hash_id(sb, dirid);
0813         hash = bm * (sb->s_blocksize << 3);
0814         /* give a portion of the block group to metadata */
0815         if (hint->inode)
0816             hash += sb->s_blocksize / 2;
0817         hint->search_start = hash;
0818     }
0819 }
0820 
0821 /*
0822  * Relocation based on oid, hashing them into a given bitmap block
0823  * files. Formatted nodes are unaffected, a separate policy covers them
0824  */
0825 static void oid_groups(reiserfs_blocknr_hint_t * hint)
0826 {
0827     if (hint->inode) {
0828         unsigned long hash;
0829         __u32 oid;
0830         __u32 dirid;
0831         int bm;
0832 
0833         dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id);
0834 
0835         /*
0836          * keep the root dir and it's first set of subdirs close to
0837          * the start of the disk
0838          */
0839         if (dirid <= 2)
0840             hash = (hint->inode->i_sb->s_blocksize << 3);
0841         else {
0842             oid = le32_to_cpu(INODE_PKEY(hint->inode)->k_objectid);
0843             bm = bmap_hash_id(hint->inode->i_sb, oid);
0844             hash = bm * (hint->inode->i_sb->s_blocksize << 3);
0845         }
0846         hint->search_start = hash;
0847     }
0848 }
0849 
0850 /*
0851  * returns 1 if it finds an indirect item and gets valid hint info
0852  * from it, otherwise 0
0853  */
0854 static int get_left_neighbor(reiserfs_blocknr_hint_t * hint)
0855 {
0856     struct treepath *path;
0857     struct buffer_head *bh;
0858     struct item_head *ih;
0859     int pos_in_item;
0860     __le32 *item;
0861     int ret = 0;
0862 
0863     /*
0864      * reiserfs code can call this function w/o pointer to path
0865      * structure supplied; then we rely on supplied search_start
0866      */
0867     if (!hint->path)
0868         return 0;
0869 
0870     path = hint->path;
0871     bh = get_last_bh(path);
0872     RFALSE(!bh, "green-4002: Illegal path specified to get_left_neighbor");
0873     ih = tp_item_head(path);
0874     pos_in_item = path->pos_in_item;
0875     item = tp_item_body(path);
0876 
0877     hint->search_start = bh->b_blocknr;
0878 
0879     /*
0880      * for indirect item: go to left and look for the first non-hole entry
0881      * in the indirect item
0882      */
0883     if (!hint->formatted_node && is_indirect_le_ih(ih)) {
0884         if (pos_in_item == I_UNFM_NUM(ih))
0885             pos_in_item--;
0886         while (pos_in_item >= 0) {
0887             int t = get_block_num(item, pos_in_item);
0888             if (t) {
0889                 hint->search_start = t;
0890                 ret = 1;
0891                 break;
0892             }
0893             pos_in_item--;
0894         }
0895     }
0896 
0897     /* does result value fit into specified region? */
0898     return ret;
0899 }
0900 
0901 /*
0902  * should be, if formatted node, then try to put on first part of the device
0903  * specified as number of percent with mount option device, else try to put
0904  * on last of device.  This is not to say it is good code to do so,
0905  * but the effect should be measured.
0906  */
0907 static inline void set_border_in_hint(struct super_block *s,
0908                       reiserfs_blocknr_hint_t * hint)
0909 {
0910     b_blocknr_t border =
0911         SB_BLOCK_COUNT(s) / REISERFS_SB(s)->s_alloc_options.border;
0912 
0913     if (hint->formatted_node)
0914         hint->end = border - 1;
0915     else
0916         hint->beg = border;
0917 }
0918 
0919 static inline void displace_large_file(reiserfs_blocknr_hint_t * hint)
0920 {
0921     if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
0922         hint->search_start =
0923             hint->beg +
0924             keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_dir_id),
0925                    4) % (hint->end - hint->beg);
0926     else
0927         hint->search_start =
0928             hint->beg +
0929             keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_objectid),
0930                    4) % (hint->end - hint->beg);
0931 }
0932 
0933 static inline void hash_formatted_node(reiserfs_blocknr_hint_t * hint)
0934 {
0935     char *hash_in;
0936 
0937     if (!hint->inode)
0938         hash_in = (char *)&hint->key.k_dir_id;
0939     else if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
0940         hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
0941     else
0942         hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid);
0943 
0944     hint->search_start =
0945         hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
0946 }
0947 
0948 static inline int
0949 this_blocknr_allocation_would_make_it_a_large_file(reiserfs_blocknr_hint_t *
0950                            hint)
0951 {
0952     return hint->block ==
0953         REISERFS_SB(hint->th->t_super)->s_alloc_options.large_file_size;
0954 }
0955 
0956 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
0957 static inline void displace_new_packing_locality(reiserfs_blocknr_hint_t * hint)
0958 {
0959     struct in_core_key *key = &hint->key;
0960 
0961     hint->th->displace_new_blocks = 0;
0962     hint->search_start =
0963         hint->beg + keyed_hash((char *)(&key->k_objectid),
0964                    4) % (hint->end - hint->beg);
0965 }
0966 #endif
0967 
0968 static inline int old_hashed_relocation(reiserfs_blocknr_hint_t * hint)
0969 {
0970     b_blocknr_t border;
0971     u32 hash_in;
0972 
0973     if (hint->formatted_node || hint->inode == NULL) {
0974         return 0;
0975     }
0976 
0977     hash_in = le32_to_cpu((INODE_PKEY(hint->inode))->k_dir_id);
0978     border =
0979         hint->beg + (u32) keyed_hash(((char *)(&hash_in)),
0980                      4) % (hint->end - hint->beg - 1);
0981     if (border > hint->search_start)
0982         hint->search_start = border;
0983 
0984     return 1;
0985 }
0986 
0987 static inline int old_way(reiserfs_blocknr_hint_t * hint)
0988 {
0989     b_blocknr_t border;
0990 
0991     if (hint->formatted_node || hint->inode == NULL) {
0992         return 0;
0993     }
0994 
0995     border =
0996         hint->beg +
0997         le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id) % (hint->end -
0998                                   hint->beg);
0999     if (border > hint->search_start)
1000         hint->search_start = border;
1001 
1002     return 1;
1003 }
1004 
1005 static inline void hundredth_slices(reiserfs_blocknr_hint_t * hint)
1006 {
1007     struct in_core_key *key = &hint->key;
1008     b_blocknr_t slice_start;
1009 
1010     slice_start =
1011         (keyed_hash((char *)(&key->k_dir_id), 4) % 100) * (hint->end / 100);
1012     if (slice_start > hint->search_start
1013         || slice_start + (hint->end / 100) <= hint->search_start) {
1014         hint->search_start = slice_start;
1015     }
1016 }
1017 
1018 static void determine_search_start(reiserfs_blocknr_hint_t * hint,
1019                    int amount_needed)
1020 {
1021     struct super_block *s = hint->th->t_super;
1022     int unfm_hint;
1023 
1024     hint->beg = 0;
1025     hint->end = SB_BLOCK_COUNT(s) - 1;
1026 
1027     /* This is former border algorithm. Now with tunable border offset */
1028     if (concentrating_formatted_nodes(s))
1029         set_border_in_hint(s, hint);
1030 
1031 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
1032     /*
1033      * whenever we create a new directory, we displace it.  At first
1034      * we will hash for location, later we might look for a moderately
1035      * empty place for it
1036      */
1037     if (displacing_new_packing_localities(s)
1038         && hint->th->displace_new_blocks) {
1039         displace_new_packing_locality(hint);
1040 
1041         /*
1042          * we do not continue determine_search_start,
1043          * if new packing locality is being displaced
1044          */
1045         return;
1046     }
1047 #endif
1048 
1049     /*
1050      * all persons should feel encouraged to add more special cases
1051      * here and test them
1052      */
1053 
1054     if (displacing_large_files(s) && !hint->formatted_node
1055         && this_blocknr_allocation_would_make_it_a_large_file(hint)) {
1056         displace_large_file(hint);
1057         return;
1058     }
1059 
1060     /*
1061      * if none of our special cases is relevant, use the left
1062      * neighbor in the tree order of the new node we are allocating for
1063      */
1064     if (hint->formatted_node && TEST_OPTION(hashed_formatted_nodes, s)) {
1065         hash_formatted_node(hint);
1066         return;
1067     }
1068 
1069     unfm_hint = get_left_neighbor(hint);
1070 
1071     /*
1072      * Mimic old block allocator behaviour, that is if VFS allowed for
1073      * preallocation, new blocks are displaced based on directory ID.
1074      * Also, if suggested search_start is less than last preallocated
1075      * block, we start searching from it, assuming that HDD dataflow
1076      * is faster in forward direction
1077      */
1078     if (TEST_OPTION(old_way, s)) {
1079         if (!hint->formatted_node) {
1080             if (!reiserfs_hashed_relocation(s))
1081                 old_way(hint);
1082             else if (!reiserfs_no_unhashed_relocation(s))
1083                 old_hashed_relocation(hint);
1084 
1085             if (hint->inode
1086                 && hint->search_start <
1087                 REISERFS_I(hint->inode)->i_prealloc_block)
1088                 hint->search_start =
1089                     REISERFS_I(hint->inode)->i_prealloc_block;
1090         }
1091         return;
1092     }
1093 
1094     /* This is an approach proposed by Hans */
1095     if (TEST_OPTION(hundredth_slices, s)
1096         && !(displacing_large_files(s) && !hint->formatted_node)) {
1097         hundredth_slices(hint);
1098         return;
1099     }
1100 
1101     /* old_hashed_relocation only works on unformatted */
1102     if (!unfm_hint && !hint->formatted_node &&
1103         TEST_OPTION(old_hashed_relocation, s)) {
1104         old_hashed_relocation(hint);
1105     }
1106 
1107     /* new_hashed_relocation works with both formatted/unformatted nodes */
1108     if ((!unfm_hint || hint->formatted_node) &&
1109         TEST_OPTION(new_hashed_relocation, s)) {
1110         new_hashed_relocation(hint);
1111     }
1112 
1113     /* dirid grouping works only on unformatted nodes */
1114     if (!unfm_hint && !hint->formatted_node && TEST_OPTION(dirid_groups, s)) {
1115         dirid_groups(hint);
1116     }
1117 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
1118     if (hint->formatted_node && TEST_OPTION(dirid_groups, s)) {
1119         dirid_groups(hint);
1120     }
1121 #endif
1122 
1123     /* oid grouping works only on unformatted nodes */
1124     if (!unfm_hint && !hint->formatted_node && TEST_OPTION(oid_groups, s)) {
1125         oid_groups(hint);
1126     }
1127     return;
1128 }
1129 
1130 static int determine_prealloc_size(reiserfs_blocknr_hint_t * hint)
1131 {
1132     /* make minimum size a mount option and benchmark both ways */
1133     /* we preallocate blocks only for regular files, specific size */
1134     /* benchmark preallocating always and see what happens */
1135 
1136     hint->prealloc_size = 0;
1137 
1138     if (!hint->formatted_node && hint->preallocate) {
1139         if (S_ISREG(hint->inode->i_mode) && !IS_PRIVATE(hint->inode)
1140             && hint->inode->i_size >=
1141             REISERFS_SB(hint->th->t_super)->s_alloc_options.
1142             preallocmin * hint->inode->i_sb->s_blocksize)
1143             hint->prealloc_size =
1144                 REISERFS_SB(hint->th->t_super)->s_alloc_options.
1145                 preallocsize - 1;
1146     }
1147     return CARRY_ON;
1148 }
1149 
1150 static inline int allocate_without_wrapping_disk(reiserfs_blocknr_hint_t * hint,
1151                          b_blocknr_t * new_blocknrs,
1152                          b_blocknr_t start,
1153                          b_blocknr_t finish, int min,
1154                          int amount_needed,
1155                          int prealloc_size)
1156 {
1157     int rest = amount_needed;
1158     int nr_allocated;
1159 
1160     while (rest > 0 && start <= finish) {
1161         nr_allocated = scan_bitmap(hint->th, &start, finish, min,
1162                        rest + prealloc_size,
1163                        !hint->formatted_node, hint->block);
1164 
1165         if (nr_allocated == 0)  /* no new blocks allocated, return */
1166             break;
1167 
1168         /* fill free_blocknrs array first */
1169         while (rest > 0 && nr_allocated > 0) {
1170             *new_blocknrs++ = start++;
1171             rest--;
1172             nr_allocated--;
1173         }
1174 
1175         /* do we have something to fill prealloc. array also ? */
1176         if (nr_allocated > 0) {
1177             /*
1178              * it means prealloc_size was greater that 0 and
1179              * we do preallocation
1180              */
1181             list_add(&REISERFS_I(hint->inode)->i_prealloc_list,
1182                  &SB_JOURNAL(hint->th->t_super)->
1183                  j_prealloc_list);
1184             REISERFS_I(hint->inode)->i_prealloc_block = start;
1185             REISERFS_I(hint->inode)->i_prealloc_count =
1186                 nr_allocated;
1187             break;
1188         }
1189     }
1190 
1191     return (amount_needed - rest);
1192 }
1193 
1194 static inline int blocknrs_and_prealloc_arrays_from_search_start
1195     (reiserfs_blocknr_hint_t * hint, b_blocknr_t * new_blocknrs,
1196      int amount_needed) {
1197     struct super_block *s = hint->th->t_super;
1198     b_blocknr_t start = hint->search_start;
1199     b_blocknr_t finish = SB_BLOCK_COUNT(s) - 1;
1200     int passno = 0;
1201     int nr_allocated = 0;
1202     int depth;
1203 
1204     determine_prealloc_size(hint);
1205     if (!hint->formatted_node) {
1206         int quota_ret;
1207 #ifdef REISERQUOTA_DEBUG
1208         reiserfs_debug(s, REISERFS_DEBUG_CODE,
1209                    "reiserquota: allocating %d blocks id=%u",
1210                    amount_needed, hint->inode->i_uid);
1211 #endif
1212         depth = reiserfs_write_unlock_nested(s);
1213         quota_ret =
1214             dquot_alloc_block_nodirty(hint->inode, amount_needed);
1215         if (quota_ret) {    /* Quota exceeded? */
1216             reiserfs_write_lock_nested(s, depth);
1217             return QUOTA_EXCEEDED;
1218         }
1219         if (hint->preallocate && hint->prealloc_size) {
1220 #ifdef REISERQUOTA_DEBUG
1221             reiserfs_debug(s, REISERFS_DEBUG_CODE,
1222                        "reiserquota: allocating (prealloc) %d blocks id=%u",
1223                        hint->prealloc_size, hint->inode->i_uid);
1224 #endif
1225             quota_ret = dquot_prealloc_block_nodirty(hint->inode,
1226                              hint->prealloc_size);
1227             if (quota_ret)
1228                 hint->preallocate = hint->prealloc_size = 0;
1229         }
1230         /* for unformatted nodes, force large allocations */
1231         reiserfs_write_lock_nested(s, depth);
1232     }
1233 
1234     do {
1235         switch (passno++) {
1236         case 0: /* Search from hint->search_start to end of disk */
1237             start = hint->search_start;
1238             finish = SB_BLOCK_COUNT(s) - 1;
1239             break;
1240         case 1: /* Search from hint->beg to hint->search_start */
1241             start = hint->beg;
1242             finish = hint->search_start;
1243             break;
1244         case 2: /* Last chance: Search from 0 to hint->beg */
1245             start = 0;
1246             finish = hint->beg;
1247             break;
1248         default:
1249             /* We've tried searching everywhere, not enough space */
1250             /* Free the blocks */
1251             if (!hint->formatted_node) {
1252 #ifdef REISERQUOTA_DEBUG
1253                 reiserfs_debug(s, REISERFS_DEBUG_CODE,
1254                            "reiserquota: freeing (nospace) %d blocks id=%u",
1255                            amount_needed +
1256                            hint->prealloc_size -
1257                            nr_allocated,
1258                            hint->inode->i_uid);
1259 #endif
1260                 /* Free not allocated blocks */
1261                 depth = reiserfs_write_unlock_nested(s);
1262                 dquot_free_block_nodirty(hint->inode,
1263                     amount_needed + hint->prealloc_size -
1264                     nr_allocated);
1265                 reiserfs_write_lock_nested(s, depth);
1266             }
1267             while (nr_allocated--)
1268                 reiserfs_free_block(hint->th, hint->inode,
1269                             new_blocknrs[nr_allocated],
1270                             !hint->formatted_node);
1271 
1272             return NO_DISK_SPACE;
1273         }
1274     } while ((nr_allocated += allocate_without_wrapping_disk(hint,
1275                                  new_blocknrs +
1276                                  nr_allocated,
1277                                  start, finish,
1278                                  1,
1279                                  amount_needed -
1280                                  nr_allocated,
1281                                  hint->
1282                                  prealloc_size))
1283          < amount_needed);
1284     if (!hint->formatted_node &&
1285         amount_needed + hint->prealloc_size >
1286         nr_allocated + REISERFS_I(hint->inode)->i_prealloc_count) {
1287         /* Some of preallocation blocks were not allocated */
1288 #ifdef REISERQUOTA_DEBUG
1289         reiserfs_debug(s, REISERFS_DEBUG_CODE,
1290                    "reiserquota: freeing (failed prealloc) %d blocks id=%u",
1291                    amount_needed + hint->prealloc_size -
1292                    nr_allocated -
1293                    REISERFS_I(hint->inode)->i_prealloc_count,
1294                    hint->inode->i_uid);
1295 #endif
1296 
1297         depth = reiserfs_write_unlock_nested(s);
1298         dquot_free_block_nodirty(hint->inode, amount_needed +
1299                      hint->prealloc_size - nr_allocated -
1300                      REISERFS_I(hint->inode)->
1301                      i_prealloc_count);
1302         reiserfs_write_lock_nested(s, depth);
1303     }
1304 
1305     return CARRY_ON;
1306 }
1307 
1308 /* grab new blocknrs from preallocated list */
1309 /* return amount still needed after using them */
1310 static int use_preallocated_list_if_available(reiserfs_blocknr_hint_t * hint,
1311                           b_blocknr_t * new_blocknrs,
1312                           int amount_needed)
1313 {
1314     struct inode *inode = hint->inode;
1315 
1316     if (REISERFS_I(inode)->i_prealloc_count > 0) {
1317         while (amount_needed) {
1318 
1319             *new_blocknrs++ = REISERFS_I(inode)->i_prealloc_block++;
1320             REISERFS_I(inode)->i_prealloc_count--;
1321 
1322             amount_needed--;
1323 
1324             if (REISERFS_I(inode)->i_prealloc_count <= 0) {
1325                 list_del(&REISERFS_I(inode)->i_prealloc_list);
1326                 break;
1327             }
1328         }
1329     }
1330     /* return amount still needed after using preallocated blocks */
1331     return amount_needed;
1332 }
1333 
1334 int reiserfs_allocate_blocknrs(reiserfs_blocknr_hint_t *hint,
1335                    b_blocknr_t *new_blocknrs,
1336                    int amount_needed,
1337                    /* Amount of blocks we have already reserved */
1338                    int reserved_by_us)
1339 {
1340     int initial_amount_needed = amount_needed;
1341     int ret;
1342     struct super_block *s = hint->th->t_super;
1343 
1344     /* Check if there is enough space, taking into account reserved space */
1345     if (SB_FREE_BLOCKS(s) - REISERFS_SB(s)->reserved_blocks <
1346         amount_needed - reserved_by_us)
1347         return NO_DISK_SPACE;
1348     /* should this be if !hint->inode &&  hint->preallocate? */
1349     /* do you mean hint->formatted_node can be removed ? - Zam */
1350     /*
1351      * hint->formatted_node cannot be removed because we try to access
1352      * inode information here, and there is often no inode associated with
1353      * metadata allocations - green
1354      */
1355 
1356     if (!hint->formatted_node && hint->preallocate) {
1357         amount_needed = use_preallocated_list_if_available
1358             (hint, new_blocknrs, amount_needed);
1359 
1360         /*
1361          * We have all the block numbers we need from the
1362          * prealloc list
1363          */
1364         if (amount_needed == 0)
1365             return CARRY_ON;
1366         new_blocknrs += (initial_amount_needed - amount_needed);
1367     }
1368 
1369     /* find search start and save it in hint structure */
1370     determine_search_start(hint, amount_needed);
1371     if (hint->search_start >= SB_BLOCK_COUNT(s))
1372         hint->search_start = SB_BLOCK_COUNT(s) - 1;
1373 
1374     /* allocation itself; fill new_blocknrs and preallocation arrays */
1375     ret = blocknrs_and_prealloc_arrays_from_search_start
1376         (hint, new_blocknrs, amount_needed);
1377 
1378     /*
1379      * We used prealloc. list to fill (partially) new_blocknrs array.
1380      * If final allocation fails we need to return blocks back to
1381      * prealloc. list or just free them. -- Zam (I chose second
1382      * variant)
1383      */
1384     if (ret != CARRY_ON) {
1385         while (amount_needed++ < initial_amount_needed) {
1386             reiserfs_free_block(hint->th, hint->inode,
1387                         *(--new_blocknrs), 1);
1388         }
1389     }
1390     return ret;
1391 }
1392 
1393 void reiserfs_cache_bitmap_metadata(struct super_block *sb,
1394                                     struct buffer_head *bh,
1395                                     struct reiserfs_bitmap_info *info)
1396 {
1397     unsigned long *cur = (unsigned long *)(bh->b_data + bh->b_size);
1398 
1399     /* The first bit must ALWAYS be 1 */
1400     if (!reiserfs_test_le_bit(0, (unsigned long *)bh->b_data))
1401         reiserfs_error(sb, "reiserfs-2025", "bitmap block %lu is "
1402                    "corrupted: first bit must be 1", bh->b_blocknr);
1403 
1404     info->free_count = 0;
1405 
1406     while (--cur >= (unsigned long *)bh->b_data) {
1407         /* 0 and ~0 are special, we can optimize for them */
1408         if (*cur == 0)
1409             info->free_count += BITS_PER_LONG;
1410         else if (*cur != ~0L)   /* A mix, investigate */
1411             info->free_count += BITS_PER_LONG - hweight_long(*cur);
1412     }
1413 }
1414 
1415 struct buffer_head *reiserfs_read_bitmap_block(struct super_block *sb,
1416                                                unsigned int bitmap)
1417 {
1418     b_blocknr_t block = (sb->s_blocksize << 3) * bitmap;
1419     struct reiserfs_bitmap_info *info = SB_AP_BITMAP(sb) + bitmap;
1420     struct buffer_head *bh;
1421 
1422     /*
1423      * Way old format filesystems had the bitmaps packed up front.
1424      * I doubt there are any of these left, but just in case...
1425      */
1426     if (unlikely(test_bit(REISERFS_OLD_FORMAT,
1427                   &REISERFS_SB(sb)->s_properties)))
1428         block = REISERFS_SB(sb)->s_sbh->b_blocknr + 1 + bitmap;
1429     else if (bitmap == 0)
1430         block = (REISERFS_DISK_OFFSET_IN_BYTES >> sb->s_blocksize_bits) + 1;
1431 
1432     bh = sb_bread(sb, block);
1433     if (bh == NULL)
1434         reiserfs_warning(sb, "sh-2029: %s: bitmap block (#%u) "
1435                          "reading failed", __func__, block);
1436     else {
1437         if (buffer_locked(bh)) {
1438             int depth;
1439             PROC_INFO_INC(sb, scan_bitmap.wait);
1440             depth = reiserfs_write_unlock_nested(sb);
1441             __wait_on_buffer(bh);
1442             reiserfs_write_lock_nested(sb, depth);
1443         }
1444         BUG_ON(!buffer_uptodate(bh));
1445         BUG_ON(atomic_read(&bh->b_count) == 0);
1446 
1447         if (info->free_count == UINT_MAX)
1448             reiserfs_cache_bitmap_metadata(sb, bh, info);
1449     }
1450 
1451     return bh;
1452 }
1453 
1454 int reiserfs_init_bitmap_cache(struct super_block *sb)
1455 {
1456     struct reiserfs_bitmap_info *bitmap;
1457     unsigned int bmap_nr = reiserfs_bmap_count(sb);
1458 
1459     bitmap = vmalloc(array_size(bmap_nr, sizeof(*bitmap)));
1460     if (bitmap == NULL)
1461         return -ENOMEM;
1462 
1463     memset(bitmap, 0xff, sizeof(*bitmap) * bmap_nr);
1464 
1465     SB_AP_BITMAP(sb) = bitmap;
1466 
1467     return 0;
1468 }
1469 
1470 void reiserfs_free_bitmap_cache(struct super_block *sb)
1471 {
1472     if (SB_AP_BITMAP(sb)) {
1473         vfree(SB_AP_BITMAP(sb));
1474         SB_AP_BITMAP(sb) = NULL;
1475     }
1476 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!