diff options
Diffstat (limited to 'fs/reiserfs/bitmap.c')
| -rw-r--r-- | fs/reiserfs/bitmap.c | 1476 |
1 files changed, 1476 insertions, 0 deletions
diff --git a/fs/reiserfs/bitmap.c b/fs/reiserfs/bitmap.c new file mode 100644 index 0000000000..bf708ac287 --- /dev/null +++ b/fs/reiserfs/bitmap.c @@ -0,0 +1,1476 @@ +/* + * 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; + } +} |