X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;ds=sidebyside;f=fs%2Freiserfs%2Fbitmap.c;h=b5e4498fcfebffab88fb6be62577c29825f25ea8;hb=9bf4aaab3e101692164d49b7ca357651eb691cb6;hp=86639019d49e257022032c74f1dfb9ce996289c0;hpb=db216c3d5e4c040e557a50f8f5d35d5c415e8c1c;p=linux-2.6.git diff --git a/fs/reiserfs/bitmap.c b/fs/reiserfs/bitmap.c index 86639019d..b5e4498fc 100644 --- a/fs/reiserfs/bitmap.c +++ b/fs/reiserfs/bitmap.c @@ -30,6 +30,9 @@ #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)) @@ -150,11 +153,6 @@ static int scan_bitmap_block (struct reiserfs_transaction_handle *th, __wait_on_buffer (bi->bh); } - /* If we know that first zero bit is only one or first zero bit is - closer to the end of bitmap than our start pointer */ - if (bi->first_zero_hint > *beg || bi->free_count == 1) - *beg = bi->first_zero_hint; - while (1) { cont: if (bi->free_count < min) @@ -204,21 +202,12 @@ static int scan_bitmap_block (struct reiserfs_transaction_handle *th, while (--i >= *beg) reiserfs_test_and_clear_le_bit (i, bi->bh->b_data); reiserfs_restore_prepared_buffer (s, bi->bh); - *beg = max(org, (int)bi->first_zero_hint); + *beg = org; /* ... and search again in current block from beginning */ goto cont; } } bi->free_count -= (end - *beg); - - /* if search started from zero_hint bit, and zero hint have not - changed since, then we need to update first_zero_hint */ - if ( bi->first_zero_hint >= *beg) - /* no point in looking for free bit if there is not any */ - bi->first_zero_hint = (bi->free_count > 0 ) ? - reiserfs_find_next_zero_le_bit - ((unsigned long*)(bi->bh->b_data), s->s_blocksize << 3, end) : (s->s_blocksize << 3); - journal_mark_dirty (th, s, bi->bh); /* free block count calculation */ @@ -231,7 +220,57 @@ static int scan_bitmap_block (struct reiserfs_transaction_handle *th, *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 % SB_BMAP_NR(s); + if (!bm) + bm = 1; + } + 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; + bm = bmap_hash_id(s, id); + if (SB_AP_BITMAP(s)[bm].free_count > ((s->s_blocksize << 3) * 60 / 100) ) { + return 0; + } + return 1; +} + +/* + * the packing is returned in disk byte order + */ +u32 reiserfs_choose_packing(struct inode *dir) { + u32 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. */ @@ -255,8 +294,18 @@ static int scan_bitmap (struct reiserfs_transaction_handle *th, get_bit_address (s, *start, &bm, &off); get_bit_address (s, finish, &end_bm, &end_off); - // With this option set first we try to find a bitmap that is at least 10% - // free, and if that fails, then we fall back to old whole bitmap scanning + /* 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 ) @@ -314,9 +363,6 @@ static void _reiserfs_free_block (struct reiserfs_transaction_handle *th, "free_block (%s:%lu)[dev:blocknr]: bit already cleared", reiserfs_bdevname (s), block); } - if (offset < apbi[nr].first_zero_hint) { - apbi[nr].first_zero_hint = offset; - } apbi[nr].free_count ++; journal_mark_dirty (th, s, apbi[nr].bh); @@ -396,6 +442,14 @@ void reiserfs_discard_all_prealloc (struct reiserfs_transaction_handle *th) __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) { @@ -439,6 +493,18 @@ int reiserfs_parse_alloc_options(struct super_block * s, char * options) 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; @@ -481,6 +547,7 @@ int reiserfs_parse_alloc_options(struct super_block * s, char * options) return 1; } + reiserfs_warning (s, "allocator options = [%08x]\n", SB_ALLOC_OPTS(s)); return 0; } @@ -503,17 +570,76 @@ static inline void new_hashed_relocation (reiserfs_blocknr_hint_t * hint) hint->search_start = hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg); } -static inline void get_left_neighbor(reiserfs_blocknr_hint_t *hint) +/* + * Relocation based on dirid, hashing them into a given bitmap block + * files. Formatted nodes are unaffected, a seperate 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 seperate 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 path * path; struct buffer_head * bh; struct item_head * ih; int pos_in_item; __u32 * item; + int ret = 0; if (!hint->path) /* reiserfs code can call this function w/o pointer to path * structure supplied; then we rely on supplied search_start */ - return; + return 0; path = hint->path; bh = get_last_bh(path); @@ -534,15 +660,15 @@ static inline void get_left_neighbor(reiserfs_blocknr_hint_t *hint) int t=get_block_num(item,pos_in_item); if (t) { hint->search_start = t; + ret = 1; break; } pos_in_item --; } - } else { - } + } /* does result value fit into specified region? */ - return; + return ret; } /* should be, if formatted node, then try to put on first part of the device @@ -639,10 +765,12 @@ static inline void hundredth_slices (reiserfs_blocknr_hint_t * hint) } } -static inline void determine_search_start(reiserfs_blocknr_hint_t *hint, +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; @@ -673,19 +801,14 @@ static inline void determine_search_start(reiserfs_blocknr_hint_t *hint, return; } - /* attempt to copy a feature from old block allocator code */ - if (TEST_OPTION(old_hashed_relocation, s) && !hint->formatted_node) { - old_hashed_relocation(hint); - } - /* 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); + hash_formatted_node(hint); return; - } + } - get_left_neighbor(hint); + 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 @@ -710,10 +833,36 @@ static inline void determine_search_start(reiserfs_blocknr_hint_t *hint, return; } - if (TEST_OPTION(old_hashed_relocation, s)) + /* old_hashed_relocation only works on unformatted */ + if (!unfm_hint && !hint->formatted_node && + TEST_OPTION(old_hashed_relocation, s)) + { old_hashed_relocation(hint); - if (TEST_OPTION(new_hashed_relocation, s)) + } + /* 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; } @@ -738,13 +887,14 @@ static int determine_prealloc_size(reiserfs_blocknr_hint_t * hint) 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, 1, + nr_allocated = scan_bitmap (hint->th, &start, finish, min, rest + prealloc_size, !hint->formatted_node, hint->block); @@ -777,8 +927,9 @@ static inline int blocknrs_and_prealloc_arrays_from_search_start 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 second_pass = 0; + int passno = 0; int nr_allocated = 0; + int bigalloc = 0; determine_prealloc_size(hint); if (!hint->formatted_node) { @@ -797,32 +948,61 @@ static inline int blocknrs_and_prealloc_arrays_from_search_start if (quota_ret) hint->preallocate=hint->prealloc_size=0; } + /* for unformatted nodes, force large allocations */ + bigalloc = amount_needed; } - while((nr_allocated - += allocate_without_wrapping_disk(hint, new_blocknrs + nr_allocated, start, finish, - amount_needed - nr_allocated, hint->prealloc_size)) - < amount_needed) { - - /* not all blocks were successfully allocated yet*/ - if (second_pass) { /* it was a second pass; we must free all blocks */ + do { + /* in bigalloc mode, nr_allocated should stay zero until + * the entire allocation is filled + */ + if (unlikely(bigalloc && nr_allocated)) { + reiserfs_warning(s, "bigalloc is %d, nr_allocated %d\n", + bigalloc, nr_allocated); + /* reset things to a sane value */ + bigalloc = amount_needed - nr_allocated; + } + /* + * try pass 0 and pass 1 looking for a nice big + * contiguous allocation. Then reset and look + * for anything you can find. + */ + if (passno == 2 && bigalloc) { + passno = 0; + bigalloc = 0; + } + 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, "reiserquota: freeing (nospace) %d blocks id=%u", amount_needed + hint->prealloc_size - nr_allocated, hint->inode->i_uid); #endif DQUOT_FREE_BLOCK_NODIRTY(hint->inode, amount_needed + hint->prealloc_size - nr_allocated); /* Free not allocated blocks */ } - while (nr_allocated --) + while (nr_allocated --) reiserfs_free_block(hint->th, hint->inode, new_blocknrs[nr_allocated], !hint->formatted_node); return NO_DISK_SPACE; - } else { /* refine search parameters for next pass */ - second_pass = 1; - finish = start; - start = 0; - continue; } - } + } while ((nr_allocated += allocate_without_wrapping_disk (hint, + new_blocknrs + nr_allocated, start, finish, + bigalloc ? bigalloc : 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) {