diff options
Diffstat (limited to 'fs/reiserfs/bitmap.c')
| -rw-r--r-- | fs/reiserfs/bitmap.c | 1476 |
1 files changed, 0 insertions, 1476 deletions
diff --git a/fs/reiserfs/bitmap.c b/fs/reiserfs/bitmap.c deleted file mode 100644 index bf708ac287b4..000000000000 --- a/fs/reiserfs/bitmap.c +++ /dev/null @@ -1,1476 +0,0 @@ -/* - * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README - */ -/* Reiserfs block (de)allocator, bitmap-based. */ - -#include <linux/time.h> -#include "reiserfs.h" -#include <linux/errno.h> -#include <linux/buffer_head.h> -#include <linux/kernel.h> -#include <linux/pagemap.h> -#include <linux/vmalloc.h> -#include <linux/quotaops.h> -#include <linux/seq_file.h> - -#define PREALLOCATION_SIZE 9 - -/* different reiserfs block allocator options */ - -#define SB_ALLOC_OPTS(s) (REISERFS_SB(s)->s_alloc_options.bits) - -#define _ALLOC_concentrating_formatted_nodes 0 -#define _ALLOC_displacing_large_files 1 -#define _ALLOC_displacing_new_packing_localities 2 -#define _ALLOC_old_hashed_relocation 3 -#define _ALLOC_new_hashed_relocation 4 -#define _ALLOC_skip_busy 5 -#define _ALLOC_displace_based_on_dirid 6 -#define _ALLOC_hashed_formatted_nodes 7 -#define _ALLOC_old_way 8 -#define _ALLOC_hundredth_slices 9 -#define _ALLOC_dirid_groups 10 -#define _ALLOC_oid_groups 11 -#define _ALLOC_packing_groups 12 - -#define concentrating_formatted_nodes(s) test_bit(_ALLOC_concentrating_formatted_nodes, &SB_ALLOC_OPTS(s)) -#define displacing_large_files(s) test_bit(_ALLOC_displacing_large_files, &SB_ALLOC_OPTS(s)) -#define displacing_new_packing_localities(s) test_bit(_ALLOC_displacing_new_packing_localities, &SB_ALLOC_OPTS(s)) - -#define SET_OPTION(optname) \ - do { \ - reiserfs_info(s, "block allocator option \"%s\" is set", #optname); \ - set_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s)); \ - } while(0) -#define TEST_OPTION(optname, s) \ - test_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s)) - -static inline void get_bit_address(struct super_block *s, - b_blocknr_t block, - unsigned int *bmap_nr, - unsigned int *offset) -{ - /* - * It is in the bitmap block number equal to the block - * number divided by the number of bits in a block. - */ - *bmap_nr = block >> (s->s_blocksize_bits + 3); - /* Within that bitmap block it is located at bit offset *offset. */ - *offset = block & ((s->s_blocksize << 3) - 1); -} - -int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value) -{ - unsigned int bmap, offset; - unsigned int bmap_count = reiserfs_bmap_count(s); - - if (block == 0 || block >= SB_BLOCK_COUNT(s)) { - reiserfs_error(s, "vs-4010", - "block number is out of range %lu (%u)", - block, SB_BLOCK_COUNT(s)); - return 0; - } - - get_bit_address(s, block, &bmap, &offset); - - /* - * Old format filesystem? Unlikely, but the bitmaps are all - * up front so we need to account for it. - */ - if (unlikely(test_bit(REISERFS_OLD_FORMAT, - &REISERFS_SB(s)->s_properties))) { - b_blocknr_t bmap1 = REISERFS_SB(s)->s_sbh->b_blocknr + 1; - if (block >= bmap1 && - block <= bmap1 + bmap_count) { - reiserfs_error(s, "vs-4019", "bitmap block %lu(%u) " - "can't be freed or reused", - block, bmap_count); - return 0; - } - } else { - if (offset == 0) { - reiserfs_error(s, "vs-4020", "bitmap block %lu(%u) " - "can't be freed or reused", - block, bmap_count); - return 0; - } - } - - if (bmap >= bmap_count) { - reiserfs_error(s, "vs-4030", "bitmap for requested block " - "is out of range: block=%lu, bitmap_nr=%u", - block, bmap); - return 0; - } - - if (bit_value == 0 && block == SB_ROOT_BLOCK(s)) { - reiserfs_error(s, "vs-4050", "this is root block (%u), " - "it must be busy", SB_ROOT_BLOCK(s)); - return 0; - } - - return 1; -} - -/* - * Searches in journal structures for a given block number (bmap, off). - * If block is found in reiserfs journal it suggests next free block - * candidate to test. - */ -static inline int is_block_in_journal(struct super_block *s, unsigned int bmap, - int off, int *next) -{ - b_blocknr_t tmp; - - if (reiserfs_in_journal(s, bmap, off, 1, &tmp)) { - if (tmp) { /* hint supplied */ - *next = tmp; - PROC_INFO_INC(s, scan_bitmap.in_journal_hint); - } else { - (*next) = off + 1; /* inc offset to avoid looping. */ - PROC_INFO_INC(s, scan_bitmap.in_journal_nohint); - } - PROC_INFO_INC(s, scan_bitmap.retry); - return 1; - } - return 0; -} - -/* - * Searches for a window of zero bits with given minimum and maximum - * lengths in one bitmap block - */ -static int scan_bitmap_block(struct reiserfs_transaction_handle *th, - unsigned int bmap_n, int *beg, int boundary, - int min, int max, int unfm) -{ - struct super_block *s = th->t_super; - struct reiserfs_bitmap_info *bi = &SB_AP_BITMAP(s)[bmap_n]; - struct buffer_head *bh; - int end, next; - int org = *beg; - - BUG_ON(!th->t_trans_id); - RFALSE(bmap_n >= reiserfs_bmap_count(s), "Bitmap %u is out of " - "range (0..%u)", bmap_n, reiserfs_bmap_count(s) - 1); - PROC_INFO_INC(s, scan_bitmap.bmap); - - if (!bi) { - reiserfs_error(s, "jdm-4055", "NULL bitmap info pointer " - "for bitmap %d", bmap_n); - return 0; - } - - bh = reiserfs_read_bitmap_block(s, bmap_n); - if (bh == NULL) - return 0; - - while (1) { -cont: - if (bi->free_count < min) { - brelse(bh); - return 0; /* No free blocks in this bitmap */ - } - - /* search for a first zero bit -- beginning of a window */ - *beg = reiserfs_find_next_zero_le_bit - ((unsigned long *)(bh->b_data), boundary, *beg); - - /* - * search for a zero bit fails or the rest of bitmap block - * cannot contain a zero window of minimum size - */ - if (*beg + min > boundary) { - brelse(bh); - return 0; - } - - if (unfm && is_block_in_journal(s, bmap_n, *beg, beg)) - continue; - /* first zero bit found; we check next bits */ - for (end = *beg + 1;; end++) { - if (end >= *beg + max || end >= boundary - || reiserfs_test_le_bit(end, bh->b_data)) { - next = end; - break; - } - - /* - * finding the other end of zero bit window requires - * looking into journal structures (in case of - * searching for free blocks for unformatted nodes) - */ - if (unfm && is_block_in_journal(s, bmap_n, end, &next)) - break; - } - - /* - * now (*beg) points to beginning of zero bits window, - * (end) points to one bit after the window end - */ - - /* found window of proper size */ - if (end - *beg >= min) { - int i; - reiserfs_prepare_for_journal(s, bh, 1); - /* - * try to set all blocks used checking are - * they still free - */ - for (i = *beg; i < end; i++) { - /* Don't check in journal again. */ - if (reiserfs_test_and_set_le_bit - (i, bh->b_data)) { - /* - * bit was set by another process while - * we slept in prepare_for_journal() - */ - PROC_INFO_INC(s, scan_bitmap.stolen); - - /* - * we can continue with smaller set - * of allocated blocks, if length of - * this set is more or equal to `min' - */ - if (i >= *beg + min) { - end = i; - break; - } - - /* - * otherwise we clear all bit - * were set ... - */ - while (--i >= *beg) - reiserfs_clear_le_bit - (i, bh->b_data); - reiserfs_restore_prepared_buffer(s, bh); - *beg = org; - - /* - * Search again in current block - * from beginning - */ - goto cont; - } - } - bi->free_count -= (end - *beg); - journal_mark_dirty(th, bh); - brelse(bh); - - /* free block count calculation */ - reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s), - 1); - PUT_SB_FREE_BLOCKS(s, SB_FREE_BLOCKS(s) - (end - *beg)); - journal_mark_dirty(th, SB_BUFFER_WITH_SB(s)); - - return end - (*beg); - } else { - *beg = next; - } - } -} - -static int bmap_hash_id(struct super_block *s, u32 id) -{ - char *hash_in = NULL; - unsigned long hash; - unsigned bm; - - if (id <= 2) { - bm = 1; - } else { - hash_in = (char *)(&id); - hash = keyed_hash(hash_in, 4); - bm = hash % reiserfs_bmap_count(s); - if (!bm) - bm = 1; - } - /* this can only be true when SB_BMAP_NR = 1 */ - if (bm >= reiserfs_bmap_count(s)) - bm = 0; - return bm; -} - -/* - * hashes the id and then returns > 0 if the block group for the - * corresponding hash is full - */ -static inline int block_group_used(struct super_block *s, u32 id) -{ - int bm = bmap_hash_id(s, id); - struct reiserfs_bitmap_info *info = &SB_AP_BITMAP(s)[bm]; - - /* - * If we don't have cached information on this bitmap block, we're - * going to have to load it later anyway. Loading it here allows us - * to make a better decision. This favors long-term performance gain - * with a better on-disk layout vs. a short term gain of skipping the - * read and potentially having a bad placement. - */ - if (info->free_count == UINT_MAX) { - struct buffer_head *bh = reiserfs_read_bitmap_block(s, bm); - brelse(bh); - } - - if (info->free_count > ((s->s_blocksize << 3) * 60 / 100)) { - return 0; - } - return 1; -} - -/* - * the packing is returned in disk byte order - */ -__le32 reiserfs_choose_packing(struct inode * dir) -{ - __le32 packing; - if (TEST_OPTION(packing_groups, dir->i_sb)) { - u32 parent_dir = le32_to_cpu(INODE_PKEY(dir)->k_dir_id); - /* - * some versions of reiserfsck expect packing locality 1 to be - * special - */ - if (parent_dir == 1 || block_group_used(dir->i_sb, parent_dir)) - packing = INODE_PKEY(dir)->k_objectid; - else - packing = INODE_PKEY(dir)->k_dir_id; - } else - packing = INODE_PKEY(dir)->k_objectid; - return packing; -} - -/* - * Tries to find contiguous zero bit window (given size) in given region of - * bitmap and place new blocks there. Returns number of allocated blocks. - */ -static int scan_bitmap(struct reiserfs_transaction_handle *th, - b_blocknr_t * start, b_blocknr_t finish, - int min, int max, int unfm, sector_t file_block) -{ - int nr_allocated = 0; - struct super_block *s = th->t_super; - unsigned int bm, off; - unsigned int end_bm, end_off; - unsigned int off_max = s->s_blocksize << 3; - - BUG_ON(!th->t_trans_id); - PROC_INFO_INC(s, scan_bitmap.call); - - /* No point in looking for more free blocks */ - if (SB_FREE_BLOCKS(s) <= 0) - return 0; - - get_bit_address(s, *start, &bm, &off); - get_bit_address(s, finish, &end_bm, &end_off); - if (bm > reiserfs_bmap_count(s)) - return 0; - if (end_bm > reiserfs_bmap_count(s)) - end_bm = reiserfs_bmap_count(s); - - /* - * When the bitmap is more than 10% free, anyone can allocate. - * When it's less than 10% free, only files that already use the - * bitmap are allowed. Once we pass 80% full, this restriction - * is lifted. - * - * We do this so that files that grow later still have space close to - * their original allocation. This improves locality, and presumably - * performance as a result. - * - * This is only an allocation policy and does not make up for getting a - * bad hint. Decent hinting must be implemented for this to work well. - */ - if (TEST_OPTION(skip_busy, s) - && SB_FREE_BLOCKS(s) > SB_BLOCK_COUNT(s) / 20) { - for (; bm < end_bm; bm++, off = 0) { - if ((off && (!unfm || (file_block != 0))) - || SB_AP_BITMAP(s)[bm].free_count > - (s->s_blocksize << 3) / 10) - nr_allocated = - scan_bitmap_block(th, bm, &off, off_max, - min, max, unfm); - if (nr_allocated) - goto ret; - } - /* we know from above that start is a reasonable number */ - get_bit_address(s, *start, &bm, &off); - } - - for (; bm < end_bm; bm++, off = 0) { - nr_allocated = - scan_bitmap_block(th, bm, &off, off_max, min, max, unfm); - if (nr_allocated) - goto ret; - } - - nr_allocated = - scan_bitmap_block(th, bm, &off, end_off + 1, min, max, unfm); - -ret: - *start = bm * off_max + off; - return nr_allocated; - -} - -static void _reiserfs_free_block(struct reiserfs_transaction_handle *th, - struct inode *inode, b_blocknr_t block, - int for_unformatted) -{ - struct super_block *s = th->t_super; - struct reiserfs_super_block *rs; - struct buffer_head *sbh, *bmbh; - struct reiserfs_bitmap_info *apbi; - unsigned int nr, offset; - - BUG_ON(!th->t_trans_id); - PROC_INFO_INC(s, free_block); - rs = SB_DISK_SUPER_BLOCK(s); - sbh = SB_BUFFER_WITH_SB(s); - apbi = SB_AP_BITMAP(s); - - get_bit_address(s, block, &nr, &offset); - - if (nr >= reiserfs_bmap_count(s)) { - reiserfs_error(s, "vs-4075", "block %lu is out of range", - block); - return; - } - - bmbh = reiserfs_read_bitmap_block(s, nr); - if (!bmbh) - return; - - reiserfs_prepare_for_journal(s, bmbh, 1); - - /* clear bit for the given block in bit map */ - if (!reiserfs_test_and_clear_le_bit(offset, bmbh->b_data)) { - reiserfs_error(s, "vs-4080", - "block %lu: bit already cleared", block); - } - apbi[nr].free_count++; - journal_mark_dirty(th, bmbh); - brelse(bmbh); - - reiserfs_prepare_for_journal(s, sbh, 1); - /* update super block */ - set_sb_free_blocks(rs, sb_free_blocks(rs) + 1); - - journal_mark_dirty(th, sbh); - if (for_unformatted) { - int depth = reiserfs_write_unlock_nested(s); - dquot_free_block_nodirty(inode, 1); - reiserfs_write_lock_nested(s, depth); - } -} - -void reiserfs_free_block(struct reiserfs_transaction_handle *th, - struct inode *inode, b_blocknr_t block, - int for_unformatted) -{ - struct super_block *s = th->t_super; - - BUG_ON(!th->t_trans_id); - RFALSE(!s, "vs-4061: trying to free block on nonexistent device"); - if (!is_reusable(s, block, 1)) - return; - - if (block > sb_block_count(REISERFS_SB(s)->s_rs)) { - reiserfs_error(th->t_super, "bitmap-4072", - "Trying to free block outside file system " - "boundaries (%lu > %lu)", - block, sb_block_count(REISERFS_SB(s)->s_rs)); - return; - } - /* mark it before we clear it, just in case */ - journal_mark_freed(th, s, block); - _reiserfs_free_block(th, inode, block, for_unformatted); -} - -/* preallocated blocks don't need to be run through journal_mark_freed */ -static void reiserfs_free_prealloc_block(struct reiserfs_transaction_handle *th, - struct inode *inode, b_blocknr_t block) -{ - BUG_ON(!th->t_trans_id); - RFALSE(!th->t_super, - "vs-4060: trying to free block on nonexistent device"); - if (!is_reusable(th->t_super, block, 1)) - return; - _reiserfs_free_block(th, inode, block, 1); -} - -static void __discard_prealloc(struct reiserfs_transaction_handle *th, - struct reiserfs_inode_info *ei) -{ - unsigned long save = ei->i_prealloc_block; - int dirty = 0; - struct inode *inode = &ei->vfs_inode; - - BUG_ON(!th->t_trans_id); -#ifdef CONFIG_REISERFS_CHECK - if (ei->i_prealloc_count < 0) - reiserfs_error(th->t_super, "zam-4001", - "inode has negative prealloc blocks count."); -#endif - while (ei->i_prealloc_count > 0) { - b_blocknr_t block_to_free; - - /* - * reiserfs_free_prealloc_block can drop the write lock, - * which could allow another caller to free the same block. - * We can protect against it by modifying the prealloc - * state before calling it. - */ - block_to_free = ei->i_prealloc_block++; - ei->i_prealloc_count--; - reiserfs_free_prealloc_block(th, inode, block_to_free); - dirty = 1; - } - if (dirty) - reiserfs_update_sd(th, inode); - ei->i_prealloc_block = save; - list_del_init(&ei->i_prealloc_list); -} - -/* FIXME: It should be inline function */ -void reiserfs_discard_prealloc(struct reiserfs_transaction_handle *th, - struct inode *inode) -{ - struct reiserfs_inode_info *ei = REISERFS_I(inode); - - BUG_ON(!th->t_trans_id); - if (ei->i_prealloc_count) - __discard_prealloc(th, ei); -} - -void reiserfs_discard_all_prealloc(struct reiserfs_transaction_handle *th) -{ - struct list_head *plist = &SB_JOURNAL(th->t_super)->j_prealloc_list; - - BUG_ON(!th->t_trans_id); - while (!list_empty(plist)) { - struct reiserfs_inode_info *ei; - ei = list_entry(plist->next, struct reiserfs_inode_info, - i_prealloc_list); -#ifdef CONFIG_REISERFS_CHECK - if (!ei->i_prealloc_count) { - reiserfs_error(th->t_super, "zam-4001", - "inode is in prealloc list but has " - "no preallocated blocks."); - } -#endif - __discard_prealloc(th, ei); - } -} - -void reiserfs_init_alloc_options(struct super_block *s) -{ - set_bit(_ALLOC_skip_busy, &SB_ALLOC_OPTS(s)); - set_bit(_ALLOC_dirid_groups, &SB_ALLOC_OPTS(s)); - set_bit(_ALLOC_packing_groups, &SB_ALLOC_OPTS(s)); -} - -/* block allocator related options are parsed here */ -int reiserfs_parse_alloc_options(struct super_block *s, char *options) -{ - char *this_char, *value; - - /* clear default settings */ - REISERFS_SB(s)->s_alloc_options.bits = 0; - - while ((this_char = strsep(&options, ":")) != NULL) { - if ((value = strchr(this_char, '=')) != NULL) - *value++ = 0; - - if (!strcmp(this_char, "concentrating_formatted_nodes")) { - int temp; - SET_OPTION(concentrating_formatted_nodes); - temp = (value - && *value) ? simple_strtoul(value, &value, - 0) : 10; - if (temp <= 0 || temp > 100) { - REISERFS_SB(s)->s_alloc_options.border = 10; - } else { - REISERFS_SB(s)->s_alloc_options.border = - 100 / temp; - } - continue; - } - if (!strcmp(this_char, "displacing_large_files")) { - SET_OPTION(displacing_large_files); - REISERFS_SB(s)->s_alloc_options.large_file_size = - (value - && *value) ? simple_strtoul(value, &value, 0) : 16; - continue; - } - if (!strcmp(this_char, "displacing_new_packing_localities")) { - SET_OPTION(displacing_new_packing_localities); - continue; - } - - if (!strcmp(this_char, "old_hashed_relocation")) { - SET_OPTION(old_hashed_relocation); - continue; - } - - if (!strcmp(this_char, "new_hashed_relocation")) { - SET_OPTION(new_hashed_relocation); - continue; - } - - if (!strcmp(this_char, "dirid_groups")) { - SET_OPTION(dirid_groups); - continue; - } - if (!strcmp(this_char, "oid_groups")) { - SET_OPTION(oid_groups); - continue; - } - if (!strcmp(this_char, "packing_groups")) { - SET_OPTION(packing_groups); - continue; - } - if (!strcmp(this_char, "hashed_formatted_nodes")) { - SET_OPTION(hashed_formatted_nodes); - continue; - } - - if (!strcmp(this_char, "skip_busy")) { - SET_OPTION(skip_busy); - continue; - } - - if (!strcmp(this_char, "hundredth_slices")) { - SET_OPTION(hundredth_slices); - continue; - } - - if (!strcmp(this_char, "old_way")) { - SET_OPTION(old_way); - continue; - } - - if (!strcmp(this_char, "displace_based_on_dirid")) { - SET_OPTION(displace_based_on_dirid); - continue; - } - - if (!strcmp(this_char, "preallocmin")) { - REISERFS_SB(s)->s_alloc_options.preallocmin = - (value - && *value) ? simple_strtoul(value, &value, 0) : 4; - continue; - } - - if (!strcmp(this_char, "preallocsize")) { - REISERFS_SB(s)->s_alloc_options.preallocsize = - (value - && *value) ? simple_strtoul(value, &value, - 0) : - PREALLOCATION_SIZE; - continue; - } - - reiserfs_warning(s, "zam-4001", "unknown option - %s", - this_char); - return 1; - } - - reiserfs_info(s, "allocator options = [%08x]\n", SB_ALLOC_OPTS(s)); - return 0; -} - -static void print_sep(struct seq_file *seq, int *first) -{ - if (!*first) - seq_puts(seq, ":"); - else - *first = 0; -} - -void show_alloc_options(struct seq_file *seq, struct super_block *s) -{ - int first = 1; - - if (SB_ALLOC_OPTS(s) == ((1 << _ALLOC_skip_busy) | - (1 << _ALLOC_dirid_groups) | (1 << _ALLOC_packing_groups))) - return; - - seq_puts(seq, ",alloc="); - - if (TEST_OPTION(concentrating_formatted_nodes, s)) { - print_sep(seq, &first); - if (REISERFS_SB(s)->s_alloc_options.border != 10) { - seq_printf(seq, "concentrating_formatted_nodes=%d", - 100 / REISERFS_SB(s)->s_alloc_options.border); - } else - seq_puts(seq, "concentrating_formatted_nodes"); - } - if (TEST_OPTION(displacing_large_files, s)) { - print_sep(seq, &first); - if (REISERFS_SB(s)->s_alloc_options.large_file_size != 16) { - seq_printf(seq, "displacing_large_files=%lu", - REISERFS_SB(s)->s_alloc_options.large_file_size); - } else - seq_puts(seq, "displacing_large_files"); - } - if (TEST_OPTION(displacing_new_packing_localities, s)) { - print_sep(seq, &first); - seq_puts(seq, "displacing_new_packing_localities"); - } - if (TEST_OPTION(old_hashed_relocation, s)) { - print_sep(seq, &first); - seq_puts(seq, "old_hashed_relocation"); - } - if (TEST_OPTION(new_hashed_relocation, s)) { - print_sep(seq, &first); - seq_puts(seq, "new_hashed_relocation"); - } - if (TEST_OPTION(dirid_groups, s)) { - print_sep(seq, &first); - seq_puts(seq, "dirid_groups"); - } - if (TEST_OPTION(oid_groups, s)) { - print_sep(seq, &first); - seq_puts(seq, "oid_groups"); - } - if (TEST_OPTION(packing_groups, s)) { - print_sep(seq, &first); - seq_puts(seq, "packing_groups"); - } - if (TEST_OPTION(hashed_formatted_nodes, s)) { - print_sep(seq, &first); - seq_puts(seq, "hashed_formatted_nodes"); - } - if (TEST_OPTION(skip_busy, s)) { - print_sep(seq, &first); - seq_puts(seq, "skip_busy"); - } - if (TEST_OPTION(hundredth_slices, s)) { - print_sep(seq, &first); - seq_puts(seq, "hundredth_slices"); - } - if (TEST_OPTION(old_way, s)) { - print_sep(seq, &first); - seq_puts(seq, "old_way"); - } - if (TEST_OPTION(displace_based_on_dirid, s)) { - print_sep(seq, &first); - seq_puts(seq, "displace_based_on_dirid"); - } - if (REISERFS_SB(s)->s_alloc_options.preallocmin != 0) { - print_sep(seq, &first); - seq_printf(seq, "preallocmin=%d", - REISERFS_SB(s)->s_alloc_options.preallocmin); - } - if (REISERFS_SB(s)->s_alloc_options.preallocsize != 17) { - print_sep(seq, &first); - seq_printf(seq, "preallocsize=%d", - REISERFS_SB(s)->s_alloc_options.preallocsize); - } -} - -static inline void new_hashed_relocation(reiserfs_blocknr_hint_t * hint) -{ - char *hash_in; - - if (hint->formatted_node) { - hash_in = (char *)&hint->key.k_dir_id; - } else { - if (!hint->inode) { - /*hint->search_start = hint->beg;*/ - hash_in = (char *)&hint->key.k_dir_id; - } else - if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super)) - hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id); - else - hash_in = - (char *)(&INODE_PKEY(hint->inode)->k_objectid); - } - - hint->search_start = - hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg); -} - -/* - * Relocation based on dirid, hashing them into a given bitmap block - * files. Formatted nodes are unaffected, a separate policy covers them - */ -static void dirid_groups(reiserfs_blocknr_hint_t * hint) -{ - unsigned long hash; - __u32 dirid = 0; - int bm = 0; - struct super_block *sb = hint->th->t_super; - - if (hint->inode) - dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id); - else if (hint->formatted_node) - dirid = hint->key.k_dir_id; - - if (dirid) { - bm = bmap_hash_id(sb, dirid); - hash = bm * (sb->s_blocksize << 3); - /* give a portion of the block group to metadata */ - if (hint->inode) - hash += sb->s_blocksize / 2; - hint->search_start = hash; - } -} - -/* - * Relocation based on oid, hashing them into a given bitmap block - * files. Formatted nodes are unaffected, a separate policy covers them - */ -static void oid_groups(reiserfs_blocknr_hint_t * hint) -{ - if (hint->inode) { - unsigned long hash; - __u32 oid; - __u32 dirid; - int bm; - - dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id); - - /* - * keep the root dir and it's first set of subdirs close to - * the start of the disk - */ - if (dirid <= 2) - hash = (hint->inode->i_sb->s_blocksize << 3); - else { - oid = le32_to_cpu(INODE_PKEY(hint->inode)->k_objectid); - bm = bmap_hash_id(hint->inode->i_sb, oid); - hash = bm * (hint->inode->i_sb->s_blocksize << 3); - } - hint->search_start = hash; - } -} - -/* - * returns 1 if it finds an indirect item and gets valid hint info - * from it, otherwise 0 - */ -static int get_left_neighbor(reiserfs_blocknr_hint_t * hint) -{ - struct treepath *path; - struct buffer_head *bh; - struct item_head *ih; - int pos_in_item; - __le32 *item; - int ret = 0; - - /* - * reiserfs code can call this function w/o pointer to path - * structure supplied; then we rely on supplied search_start - */ - if (!hint->path) - return 0; - - path = hint->path; - bh = get_last_bh(path); - RFALSE(!bh, "green-4002: Illegal path specified to get_left_neighbor"); - ih = tp_item_head(path); - pos_in_item = path->pos_in_item; - item = tp_item_body(path); - - hint->search_start = bh->b_blocknr; - - /* - * for indirect item: go to left and look for the first non-hole entry - * in the indirect item - */ - if (!hint->formatted_node && is_indirect_le_ih(ih)) { - if (pos_in_item == I_UNFM_NUM(ih)) - pos_in_item--; - while (pos_in_item >= 0) { - int t = get_block_num(item, pos_in_item); - if (t) { - hint->search_start = t; - ret = 1; - break; - } - pos_in_item--; - } - } - - /* does result value fit into specified region? */ - return ret; -} - -/* - * should be, if formatted node, then try to put on first part of the device - * specified as number of percent with mount option device, else try to put - * on last of device. This is not to say it is good code to do so, - * but the effect should be measured. - */ -static inline void set_border_in_hint(struct super_block *s, - reiserfs_blocknr_hint_t * hint) -{ - b_blocknr_t border = - SB_BLOCK_COUNT(s) / REISERFS_SB(s)->s_alloc_options.border; - - if (hint->formatted_node) - hint->end = border - 1; - else - hint->beg = border; -} - -static inline void displace_large_file(reiserfs_blocknr_hint_t * hint) -{ - if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super)) - hint->search_start = - hint->beg + - keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_dir_id), - 4) % (hint->end - hint->beg); - else - hint->search_start = - hint->beg + - keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_objectid), - 4) % (hint->end - hint->beg); -} - -static inline void hash_formatted_node(reiserfs_blocknr_hint_t * hint) -{ - char *hash_in; - - if (!hint->inode) - hash_in = (char *)&hint->key.k_dir_id; - else if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super)) - hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id); - else - hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid); - - hint->search_start = - hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg); -} - -static inline int -this_blocknr_allocation_would_make_it_a_large_file(reiserfs_blocknr_hint_t * - hint) -{ - return hint->block == - REISERFS_SB(hint->th->t_super)->s_alloc_options.large_file_size; -} - -#ifdef DISPLACE_NEW_PACKING_LOCALITIES -static inline void displace_new_packing_locality(reiserfs_blocknr_hint_t * hint) -{ - struct in_core_key *key = &hint->key; - - hint->th->displace_new_blocks = 0; - hint->search_start = - hint->beg + keyed_hash((char *)(&key->k_objectid), - 4) % (hint->end - hint->beg); -} -#endif - -static inline int old_hashed_relocation(reiserfs_blocknr_hint_t * hint) -{ - b_blocknr_t border; - u32 hash_in; - - if (hint->formatted_node || hint->inode == NULL) { - return 0; - } - - hash_in = le32_to_cpu((INODE_PKEY(hint->inode))->k_dir_id); - border = - hint->beg + (u32) keyed_hash(((char *)(&hash_in)), - 4) % (hint->end - hint->beg - 1); - if (border > hint->search_start) - hint->search_start = border; - - return 1; -} - -static inline int old_way(reiserfs_blocknr_hint_t * hint) -{ - b_blocknr_t border; - - if (hint->formatted_node || hint->inode == NULL) { - return 0; - } - - border = - hint->beg + - le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id) % (hint->end - - hint->beg); - if (border > hint->search_start) - hint->search_start = border; - - return 1; -} - -static inline void hundredth_slices(reiserfs_blocknr_hint_t * hint) -{ - struct in_core_key *key = &hint->key; - b_blocknr_t slice_start; - - slice_start = - (keyed_hash((char *)(&key->k_dir_id), 4) % 100) * (hint->end / 100); - if (slice_start > hint->search_start - || slice_start + (hint->end / 100) <= hint->search_start) { - hint->search_start = slice_start; - } -} - -static void determine_search_start(reiserfs_blocknr_hint_t * hint, - int amount_needed) -{ - struct super_block *s = hint->th->t_super; - int unfm_hint; - - hint->beg = 0; - hint->end = SB_BLOCK_COUNT(s) - 1; - - /* This is former border algorithm. Now with tunable border offset */ - if (concentrating_formatted_nodes(s)) - set_border_in_hint(s, hint); - -#ifdef DISPLACE_NEW_PACKING_LOCALITIES - /* - * whenever we create a new directory, we displace it. At first - * we will hash for location, later we might look for a moderately - * empty place for it - */ - if (displacing_new_packing_localities(s) - && hint->th->displace_new_blocks) { - displace_new_packing_locality(hint); - - /* - * we do not continue determine_search_start, - * if new packing locality is being displaced - */ - return; - } -#endif - - /* - * all persons should feel encouraged to add more special cases - * here and test them - */ - - if (displacing_large_files(s) && !hint->formatted_node - && this_blocknr_allocation_would_make_it_a_large_file(hint)) { - displace_large_file(hint); - return; - } - - /* - * if none of our special cases is relevant, use the left - * neighbor in the tree order of the new node we are allocating for - */ - if (hint->formatted_node && TEST_OPTION(hashed_formatted_nodes, s)) { - hash_formatted_node(hint); - return; - } - - unfm_hint = get_left_neighbor(hint); - - /* - * Mimic old block allocator behaviour, that is if VFS allowed for - * preallocation, new blocks are displaced based on directory ID. - * Also, if suggested search_start is less than last preallocated - * block, we start searching from it, assuming that HDD dataflow - * is faster in forward direction - */ - if (TEST_OPTION(old_way, s)) { - if (!hint->formatted_node) { - if (!reiserfs_hashed_relocation(s)) - old_way(hint); - else if (!reiserfs_no_unhashed_relocation(s)) - old_hashed_relocation(hint); - - if (hint->inode - && hint->search_start < - REISERFS_I(hint->inode)->i_prealloc_block) - hint->search_start = - REISERFS_I(hint->inode)->i_prealloc_block; - } - return; - } - - /* This is an approach proposed by Hans */ - if (TEST_OPTION(hundredth_slices, s) - && !(displacing_large_files(s) && !hint->formatted_node)) { - hundredth_slices(hint); - return; - } - - /* old_hashed_relocation only works on unformatted */ - if (!unfm_hint && !hint->formatted_node && - TEST_OPTION(old_hashed_relocation, s)) { - old_hashed_relocation(hint); - } - - /* new_hashed_relocation works with both formatted/unformatted nodes */ - if ((!unfm_hint || hint->formatted_node) && - TEST_OPTION(new_hashed_relocation, s)) { - new_hashed_relocation(hint); - } - - /* dirid grouping works only on unformatted nodes */ - if (!unfm_hint && !hint->formatted_node && TEST_OPTION(dirid_groups, s)) { - dirid_groups(hint); - } -#ifdef DISPLACE_NEW_PACKING_LOCALITIES - if (hint->formatted_node && TEST_OPTION(dirid_groups, s)) { - dirid_groups(hint); - } -#endif - - /* oid grouping works only on unformatted nodes */ - if (!unfm_hint && !hint->formatted_node && TEST_OPTION(oid_groups, s)) { - oid_groups(hint); - } - return; -} - -static int determine_prealloc_size(reiserfs_blocknr_hint_t * hint) -{ - /* make minimum size a mount option and benchmark both ways */ - /* we preallocate blocks only for regular files, specific size */ - /* benchmark preallocating always and see what happens */ - - hint->prealloc_size = 0; - - if (!hint->formatted_node && hint->preallocate) { - if (S_ISREG(hint->inode->i_mode) && !IS_PRIVATE(hint->inode) - && hint->inode->i_size >= - REISERFS_SB(hint->th->t_super)->s_alloc_options. - preallocmin * hint->inode->i_sb->s_blocksize) - hint->prealloc_size = - REISERFS_SB(hint->th->t_super)->s_alloc_options. - preallocsize - 1; - } - return CARRY_ON; -} - -static inline int allocate_without_wrapping_disk(reiserfs_blocknr_hint_t * hint, - b_blocknr_t * new_blocknrs, - b_blocknr_t start, - b_blocknr_t finish, int min, - int amount_needed, - int prealloc_size) -{ - int rest = amount_needed; - int nr_allocated; - - while (rest > 0 && start <= finish) { - nr_allocated = scan_bitmap(hint->th, &start, finish, min, - rest + prealloc_size, - !hint->formatted_node, hint->block); - - if (nr_allocated == 0) /* no new blocks allocated, return */ - break; - - /* fill free_blocknrs array first */ - while (rest > 0 && nr_allocated > 0) { - *new_blocknrs++ = start++; - rest--; - nr_allocated--; - } - - /* do we have something to fill prealloc. array also ? */ - if (nr_allocated > 0) { - /* - * it means prealloc_size was greater that 0 and - * we do preallocation - */ - list_add(&REISERFS_I(hint->inode)->i_prealloc_list, - &SB_JOURNAL(hint->th->t_super)-> - j_prealloc_list); - REISERFS_I(hint->inode)->i_prealloc_block = start; - REISERFS_I(hint->inode)->i_prealloc_count = - nr_allocated; - break; - } - } - - return (amount_needed - rest); -} - -static inline int blocknrs_and_prealloc_arrays_from_search_start - (reiserfs_blocknr_hint_t * hint, b_blocknr_t * new_blocknrs, - int amount_needed) { - struct super_block *s = hint->th->t_super; - b_blocknr_t start = hint->search_start; - b_blocknr_t finish = SB_BLOCK_COUNT(s) - 1; - int passno = 0; - int nr_allocated = 0; - int depth; - - determine_prealloc_size(hint); - if (!hint->formatted_node) { - int quota_ret; -#ifdef REISERQUOTA_DEBUG - reiserfs_debug(s, REISERFS_DEBUG_CODE, - "reiserquota: allocating %d blocks id=%u", - amount_needed, hint->inode->i_uid); -#endif - depth = reiserfs_write_unlock_nested(s); - quota_ret = - dquot_alloc_block_nodirty(hint->inode, amount_needed); - if (quota_ret) { /* Quota exceeded? */ - reiserfs_write_lock_nested(s, depth); - return QUOTA_EXCEEDED; - } - if (hint->preallocate && hint->prealloc_size) { -#ifdef REISERQUOTA_DEBUG - reiserfs_debug(s, REISERFS_DEBUG_CODE, - "reiserquota: allocating (prealloc) %d blocks id=%u", - hint->prealloc_size, hint->inode->i_uid); -#endif - quota_ret = dquot_prealloc_block_nodirty(hint->inode, - hint->prealloc_size); - if (quota_ret) - hint->preallocate = hint->prealloc_size = 0; - } - /* for unformatted nodes, force large allocations */ - reiserfs_write_lock_nested(s, depth); - } - - do { - switch (passno++) { - case 0: /* Search from hint->search_start to end of disk */ - start = hint->search_start; - finish = SB_BLOCK_COUNT(s) - 1; - break; - case 1: /* Search from hint->beg to hint->search_start */ - start = hint->beg; - finish = hint->search_start; - break; - case 2: /* Last chance: Search from 0 to hint->beg */ - start = 0; - finish = hint->beg; - break; - default: - /* We've tried searching everywhere, not enough space */ - /* Free the blocks */ - if (!hint->formatted_node) { -#ifdef REISERQUOTA_DEBUG - reiserfs_debug(s, REISERFS_DEBUG_CODE, - "reiserquota: freeing (nospace) %d blocks id=%u", - amount_needed + - hint->prealloc_size - - nr_allocated, - hint->inode->i_uid); -#endif - /* Free not allocated blocks */ - depth = reiserfs_write_unlock_nested(s); - dquot_free_block_nodirty(hint->inode, - amount_needed + hint->prealloc_size - - nr_allocated); - reiserfs_write_lock_nested(s, depth); - } - while (nr_allocated--) - reiserfs_free_block(hint->th, hint->inode, - new_blocknrs[nr_allocated], - !hint->formatted_node); - - return NO_DISK_SPACE; - } - } while ((nr_allocated += allocate_without_wrapping_disk(hint, - new_blocknrs + - nr_allocated, - start, finish, - 1, - amount_needed - - nr_allocated, - hint-> - prealloc_size)) - < amount_needed); - if (!hint->formatted_node && - amount_needed + hint->prealloc_size > - nr_allocated + REISERFS_I(hint->inode)->i_prealloc_count) { - /* Some of preallocation blocks were not allocated */ -#ifdef REISERQUOTA_DEBUG - reiserfs_debug(s, REISERFS_DEBUG_CODE, - "reiserquota: freeing (failed prealloc) %d blocks id=%u", - amount_needed + hint->prealloc_size - - nr_allocated - - REISERFS_I(hint->inode)->i_prealloc_count, - hint->inode->i_uid); -#endif - - depth = reiserfs_write_unlock_nested(s); - dquot_free_block_nodirty(hint->inode, amount_needed + - hint->prealloc_size - nr_allocated - - REISERFS_I(hint->inode)-> - i_prealloc_count); - reiserfs_write_lock_nested(s, depth); - } - - return CARRY_ON; -} - -/* grab new blocknrs from preallocated list */ -/* return amount still needed after using them */ -static int use_preallocated_list_if_available(reiserfs_blocknr_hint_t * hint, - b_blocknr_t * new_blocknrs, - int amount_needed) -{ - struct inode *inode = hint->inode; - - if (REISERFS_I(inode)->i_prealloc_count > 0) { - while (amount_needed) { - - *new_blocknrs++ = REISERFS_I(inode)->i_prealloc_block++; - REISERFS_I(inode)->i_prealloc_count--; - - amount_needed--; - - if (REISERFS_I(inode)->i_prealloc_count <= 0) { - list_del(&REISERFS_I(inode)->i_prealloc_list); - break; - } - } - } - /* return amount still needed after using preallocated blocks */ - return amount_needed; -} - -int reiserfs_allocate_blocknrs(reiserfs_blocknr_hint_t *hint, - b_blocknr_t *new_blocknrs, - int amount_needed, - /* Amount of blocks we have already reserved */ - int reserved_by_us) -{ - int initial_amount_needed = amount_needed; - int ret; - struct super_block *s = hint->th->t_super; - - /* Check if there is enough space, taking into account reserved space */ - if (SB_FREE_BLOCKS(s) - REISERFS_SB(s)->reserved_blocks < - amount_needed - reserved_by_us) - return NO_DISK_SPACE; - /* should this be if !hint->inode && hint->preallocate? */ - /* do you mean hint->formatted_node can be removed ? - Zam */ - /* - * hint->formatted_node cannot be removed because we try to access - * inode information here, and there is often no inode associated with - * metadata allocations - green - */ - - if (!hint->formatted_node && hint->preallocate) { - amount_needed = use_preallocated_list_if_available - (hint, new_blocknrs, amount_needed); - - /* - * We have all the block numbers we need from the - * prealloc list - */ - if (amount_needed == 0) - return CARRY_ON; - new_blocknrs += (initial_amount_needed - amount_needed); - } - - /* find search start and save it in hint structure */ - determine_search_start(hint, amount_needed); - if (hint->search_start >= SB_BLOCK_COUNT(s)) - hint->search_start = SB_BLOCK_COUNT(s) - 1; - - /* allocation itself; fill new_blocknrs and preallocation arrays */ - ret = blocknrs_and_prealloc_arrays_from_search_start - (hint, new_blocknrs, amount_needed); - - /* - * We used prealloc. list to fill (partially) new_blocknrs array. - * If final allocation fails we need to return blocks back to - * prealloc. list or just free them. -- Zam (I chose second - * variant) - */ - if (ret != CARRY_ON) { - while (amount_needed++ < initial_amount_needed) { - reiserfs_free_block(hint->th, hint->inode, - *(--new_blocknrs), 1); - } - } - return ret; -} - -void reiserfs_cache_bitmap_metadata(struct super_block *sb, - struct buffer_head *bh, - struct reiserfs_bitmap_info *info) -{ - unsigned long *cur = (unsigned long *)(bh->b_data + bh->b_size); - - /* The first bit must ALWAYS be 1 */ - if (!reiserfs_test_le_bit(0, (unsigned long *)bh->b_data)) - reiserfs_error(sb, "reiserfs-2025", "bitmap block %lu is " - "corrupted: first bit must be 1", bh->b_blocknr); - - info->free_count = 0; - - while (--cur >= (unsigned long *)bh->b_data) { - /* 0 and ~0 are special, we can optimize for them */ - if (*cur == 0) - info->free_count += BITS_PER_LONG; - else if (*cur != ~0L) /* A mix, investigate */ - info->free_count += BITS_PER_LONG - hweight_long(*cur); - } -} - -struct buffer_head *reiserfs_read_bitmap_block(struct super_block *sb, - unsigned int bitmap) -{ - b_blocknr_t block = (sb->s_blocksize << 3) * bitmap; - struct reiserfs_bitmap_info *info = SB_AP_BITMAP(sb) + bitmap; - struct buffer_head *bh; - - /* - * Way old format filesystems had the bitmaps packed up front. - * I doubt there are any of these left, but just in case... - */ - if (unlikely(test_bit(REISERFS_OLD_FORMAT, - &REISERFS_SB(sb)->s_properties))) - block = REISERFS_SB(sb)->s_sbh->b_blocknr + 1 + bitmap; - else if (bitmap == 0) - block = (REISERFS_DISK_OFFSET_IN_BYTES >> sb->s_blocksize_bits) + 1; - - bh = sb_bread(sb, block); - if (bh == NULL) - reiserfs_warning(sb, "sh-2029: %s: bitmap block (#%u) " - "reading failed", __func__, block); - else { - if (buffer_locked(bh)) { - int depth; - PROC_INFO_INC(sb, scan_bitmap.wait); - depth = reiserfs_write_unlock_nested(sb); - __wait_on_buffer(bh); - reiserfs_write_lock_nested(sb, depth); - } - BUG_ON(!buffer_uptodate(bh)); - BUG_ON(atomic_read(&bh->b_count) == 0); - - if (info->free_count == UINT_MAX) - reiserfs_cache_bitmap_metadata(sb, bh, info); - } - - return bh; -} - -int reiserfs_init_bitmap_cache(struct super_block *sb) -{ - struct reiserfs_bitmap_info *bitmap; - unsigned int bmap_nr = reiserfs_bmap_count(sb); - - bitmap = vmalloc(array_size(bmap_nr, sizeof(*bitmap))); - if (bitmap == NULL) - return -ENOMEM; - - memset(bitmap, 0xff, sizeof(*bitmap) * bmap_nr); - - SB_AP_BITMAP(sb) = bitmap; - - return 0; -} - -void reiserfs_free_bitmap_cache(struct super_block *sb) -{ - if (SB_AP_BITMAP(sb)) { - vfree(SB_AP_BITMAP(sb)); - SB_AP_BITMAP(sb) = NULL; - } -} |