#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))
__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)
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 */
*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. */
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 )
"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);
__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)
{
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;
return 1;
}
+ reiserfs_warning (s, "allocator options = [%08x]\n", SB_ALLOC_OPTS(s));
return 0;
}
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);
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
}
}
-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;
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
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;
}
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);
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) {
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) {
git://git.onelab.eu / linux-2.6.git / blobdiff