diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h index 84618c46f239..fd0f9054a5cc 100644 --- a/fs/ext4/ext4.h +++ b/fs/ext4/ext4.h @@ -213,12 +213,23 @@ enum criteria { #define EXT4_MB_USE_RESERVED 0x2000 /* Do strict check for free blocks while retrying block allocation */ #define EXT4_MB_STRICT_CHECK 0x4000 -/* Large fragment size list lookup succeeded at least once for cr = 0 */ +/* + * Large fragment size list lookup succeeded at least once for + * CR_POWER2_ALIGNED + */ #define EXT4_MB_CR_POWER2_ALIGNED_OPTIMIZED 0x8000 -/* Avg fragment size rb tree lookup succeeded at least once for cr = 1 */ +/* + * Avg fragment size rb tree lookup succeeded at least once for + * CR_GOAL_LEN_FAST + */ #define EXT4_MB_CR_GOAL_LEN_FAST_OPTIMIZED 0x00010000 -/* Avg fragment size rb tree lookup succeeded at least once for cr = 1.5 */ +/* + * Avg fragment size rb tree lookup succeeded at least once for + * CR_BEST_AVAIL_LEN + */ #define EXT4_MB_CR_BEST_AVAIL_LEN_OPTIMIZED 0x00020000 +/* Freelist lookup succeeded at least once for CR_GOAL_LEN_SLOW */ +#define EXT4_MB_CR_GOAL_LEN_SLOW_OPTIMIZED 0x00040000 struct ext4_allocation_request { /* target inode for block we're allocating */ @@ -1567,6 +1578,8 @@ struct ext4_sb_info { rwlock_t *s_mb_avg_fragment_size_locks; struct list_head *s_mb_largest_free_orders; rwlock_t *s_mb_largest_free_orders_locks; + struct list_head *s_mb_freelist; + rwlock_t *s_mb_freelist_locks; /* tunables */ unsigned long s_stripe; @@ -1599,6 +1612,7 @@ struct ext4_sb_info { atomic_t s_bal_p2_aligned_bad_suggestions; atomic_t s_bal_goal_fast_bad_suggestions; atomic_t s_bal_best_avail_bad_suggestions; + atomic_t s_bal_goal_slow_bad_suggestions; atomic64_t s_bal_cX_groups_considered[EXT4_MB_NUM_CRS]; atomic64_t s_bal_cX_hits[EXT4_MB_NUM_CRS]; atomic64_t s_bal_cX_failed[EXT4_MB_NUM_CRS]; /* cX loop didn't find blocks */ @@ -3397,6 +3411,10 @@ struct ext4_group_info { int bb_avg_fragment_size_order; /* order of average fragment in BG */ ext4_grpblk_t bb_largest_free_order;/* order of largest frag in BG */ + /* + * Determines which freelist will this group be added to + */ + ext4_grpblk_t bb_freelist_order; ext4_group_t bb_group; /* Group number */ struct list_head bb_prealloc_list; #ifdef DOUBLE_CHECK @@ -3405,6 +3423,7 @@ struct ext4_group_info { struct rw_semaphore alloc_sem; struct list_head bb_avg_fragment_size_node; struct list_head bb_largest_free_order_node; + struct list_head bb_freelist_node; ext4_grpblk_t bb_counters[]; /* Nr of free power-of-two-block * regions, index is order. * bb_counters[3] = 5 means diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c index c91db9f57524..885571f9be7a 100644 --- a/fs/ext4/mballoc.c +++ b/fs/ext4/mballoc.c @@ -866,6 +866,31 @@ mb_update_avg_fragment_size(struct super_block *sb, struct ext4_group_info *grp) grp->bb_avg_fragment_size_order]); } +static void mb_update_freelist(struct super_block *sb, + struct ext4_group_info *grp) +{ + struct ext4_sb_info *sbi = EXT4_SB(sb); + int new_order, prev_order; + + if (!test_opt2(sb, MB_OPTIMIZE_SCAN)) + return; + + new_order = fls(grp->bb_free); + prev_order = grp->bb_freelist_order; + if (new_order == prev_order) + return; + + if (prev_order != -1) { + write_lock(&sbi->s_mb_freelist_locks[prev_order]); + list_del(&grp->bb_freelist_node); + write_unlock(&sbi->s_mb_freelist_locks[prev_order]); + } + write_lock(&sbi->s_mb_freelist_locks[new_order]); + grp->bb_freelist_order = new_order; + list_add_tail(&grp->bb_freelist_node, &sbi->s_mb_freelist[new_order]); + write_unlock(&sbi->s_mb_freelist_locks[new_order]); +} + /* * Choose next group by traversing largest_free_order lists. Updates *new_cr if * cr level needs an update. @@ -1065,11 +1090,63 @@ static void ext4_mb_choose_next_group_best_avail(struct ext4_allocation_context *new_cr = CR_GOAL_LEN_SLOW; } +static void ext4_mb_choose_next_group_goal_slow(struct ext4_allocation_context *ac, + enum criteria *new_cr, + ext4_group_t *group, + ext4_group_t ngroups) +{ + struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb); + struct ext4_group_info *iter, *grp = NULL; + int i, order; + unsigned freelist_max_order = MB_FREELIST_NUM_ORDERS(ac->ac_sb); + + if (unlikely(ac->ac_flags & EXT4_MB_CR_GOAL_LEN_SLOW_OPTIMIZED)) { + if (sbi->s_mb_stats) + atomic_inc(&sbi->s_bal_goal_slow_bad_suggestions); + } + + order = fls(ac->ac_g_ex.fe_len); + for (i = order; i < freelist_max_order; i++) { + if (list_empty(&sbi->s_mb_freelist[i])) + continue; + + read_lock(&sbi->s_mb_freelist_locks[i]); + if (list_empty(&sbi->s_mb_freelist[i])) { + read_unlock(&sbi->s_mb_freelist_locks[i]); + continue; + } + grp = NULL; + list_for_each_entry(iter, &sbi->s_mb_freelist[i], + bb_freelist_node) { + if (sbi->s_mb_stats) + atomic64_inc(&sbi->s_bal_cX_groups_considered + [CR_GOAL_LEN_SLOW]); + + if (likely(ext4_mb_good_group(ac, iter->bb_group, + CR_GOAL_LEN_SLOW))) { + grp = iter; + break; + } + } + read_unlock(&sbi->s_mb_freelist_locks[i]); + + if (grp) + break; + } + + if (grp) { + *group = grp->bb_group; + ac->ac_flags |= EXT4_MB_CR_GOAL_LEN_SLOW_OPTIMIZED; + } else { + *new_cr = CR_ANY_FREE; + } +} + static inline int should_optimize_scan(struct ext4_allocation_context *ac) { if (unlikely(!test_opt2(ac->ac_sb, MB_OPTIMIZE_SCAN))) return 0; - if (ac->ac_criteria >= CR_GOAL_LEN_SLOW) + if (ac->ac_criteria >= CR_ANY_FREE) return 0; if (!ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)) return 0; @@ -1130,10 +1207,13 @@ static void ext4_mb_choose_next_group(struct ext4_allocation_context *ac, ext4_mb_choose_next_group_goal_fast(ac, new_cr, group, ngroups); } else if (*new_cr == CR_BEST_AVAIL_LEN) { ext4_mb_choose_next_group_best_avail(ac, new_cr, group, ngroups); + } else if (*new_cr == CR_GOAL_LEN_SLOW) { + ext4_mb_choose_next_group_goal_slow(ac, new_cr, group, ngroups); } else { /* - * TODO: For CR=2, we can arrange groups in an rb tree sorted by - * bb_free. But until that happens, we should never come here. + * We should never reach this point since should_opitimize_scan() + * will make sure we don't use mb_optimize_scan for the remaining + * CR_ANY_FREE criteria. */ WARN_ON(1); } @@ -1952,6 +2032,7 @@ static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b, done: mb_set_largest_free_order(sb, e4b->bd_info); mb_update_avg_fragment_size(sb, e4b->bd_info); + mb_update_freelist(e4b->bd_sb, e4b->bd_info); mb_check_buddy(e4b); } @@ -2096,6 +2177,7 @@ static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex) mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info); mb_update_avg_fragment_size(e4b->bd_sb, e4b->bd_info); + mb_update_freelist(e4b->bd_sb, e4b->bd_info); mb_set_bits(e4b->bd_bitmap, ex->fe_start, len0); mb_check_buddy(e4b); @@ -3125,6 +3207,8 @@ int ext4_seq_mb_stats_show(struct seq_file *seq, void *offset) atomic_read(&sbi->s_bal_cX_ex_scanned[CR_GOAL_LEN_SLOW])); seq_printf(seq, "\t\tuseless_loops: %llu\n", atomic64_read(&sbi->s_bal_cX_failed[CR_GOAL_LEN_SLOW])); + seq_printf(seq, "\t\tbad_suggestions: %u\n", + atomic_read(&sbi->s_bal_goal_slow_bad_suggestions)); /* CR_ANY_FREE stats */ seq_puts(seq, "\tcr_any_free_stats:\n"); @@ -3164,7 +3248,8 @@ __acquires(&EXT4_SB(sb)->s_mb_rb_lock) struct super_block *sb = pde_data(file_inode(seq->file)); unsigned long position; - if (*pos < 0 || *pos >= 2*MB_NUM_ORDERS(sb)) + if (*pos < 0 || + *pos >= 2 * MB_NUM_ORDERS(sb) + fls(EXT4_CLUSTERS_PER_GROUP(sb))) return NULL; position = *pos + 1; return (void *) ((unsigned long) position); @@ -3176,7 +3261,8 @@ static void *ext4_mb_seq_structs_summary_next(struct seq_file *seq, void *v, lof unsigned long position; ++*pos; - if (*pos < 0 || *pos >= 2*MB_NUM_ORDERS(sb)) + if (*pos < 0 || + *pos >= 2 * MB_NUM_ORDERS(sb) + fls(EXT4_CLUSTERS_PER_GROUP(sb))) return NULL; position = *pos + 1; return (void *) ((unsigned long) position); @@ -3191,6 +3277,23 @@ static int ext4_mb_seq_structs_summary_show(struct seq_file *seq, void *v) unsigned int count; position--; + + if (position >= 2*MB_NUM_ORDERS(sb)) { + position -= 2*MB_NUM_ORDERS(sb); + if (position == 0) + seq_puts(seq, "freelists:\n"); + + count = 0; + read_lock(&sbi->s_mb_freelist_locks[position]); + list_for_each_entry(grp, &sbi->s_mb_freelist[position], + bb_freelist_node) + count++; + read_unlock(&sbi->s_mb_freelist_locks[position]); + seq_printf(seq, "\tfreelist_order_%u_groups: %u\n", + (unsigned int)position, count); + return 0; + } + if (position >= MB_NUM_ORDERS(sb)) { position -= MB_NUM_ORDERS(sb); if (position == 0) @@ -3334,6 +3437,7 @@ int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group, ext4_free_group_clusters(sb, desc); } + INIT_LIST_HEAD(&meta_group_info[i]->bb_freelist_node); INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list); init_rwsem(&meta_group_info[i]->alloc_sem); meta_group_info[i]->bb_free_root = RB_ROOT; @@ -3341,8 +3445,10 @@ int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group, INIT_LIST_HEAD(&meta_group_info[i]->bb_avg_fragment_size_node); meta_group_info[i]->bb_largest_free_order = -1; /* uninit */ meta_group_info[i]->bb_avg_fragment_size_order = -1; /* uninit */ + meta_group_info[i]->bb_freelist_order = -1; /* uninit */ meta_group_info[i]->bb_group = group; + mb_update_freelist(sb, meta_group_info[i]); mb_group_bb_bitmap_alloc(sb, meta_group_info[i], group); return 0; @@ -3553,6 +3659,7 @@ int ext4_mb_init(struct super_block *sb) unsigned i, j; unsigned offset, offset_incr; unsigned max; + unsigned freelist_max_order = MB_FREELIST_NUM_ORDERS(sb); int ret; i = MB_NUM_ORDERS(sb) * sizeof(*sbi->s_mb_offsets); @@ -3627,6 +3734,23 @@ int ext4_mb_init(struct super_block *sb) INIT_LIST_HEAD(&sbi->s_mb_largest_free_orders[i]); rwlock_init(&sbi->s_mb_largest_free_orders_locks[i]); } + /* Empty block groups get an order of 0 */ + freelist_max_order = MB_FREELIST_NUM_ORDERS(sb); + sbi->s_mb_freelist = kmalloc_array(freelist_max_order, sizeof(struct list_head), GFP_KERNEL); + if (!sbi->s_mb_freelist) { + ret = -ENOMEM; + goto out; + } + sbi->s_mb_freelist_locks = + kmalloc_array(freelist_max_order, sizeof(rwlock_t), GFP_KERNEL); + if (!sbi->s_mb_freelist_locks) { + ret = -ENOMEM; + goto out; + } + for (i = 0; i < freelist_max_order; i++) { + INIT_LIST_HEAD(&sbi->s_mb_freelist[i]); + rwlock_init(&sbi->s_mb_freelist_locks[i]); + } spin_lock_init(&sbi->s_md_lock); sbi->s_mb_free_pending = 0; diff --git a/fs/ext4/mballoc.h b/fs/ext4/mballoc.h index d7aeb5da7d86..a3b53802899c 100644 --- a/fs/ext4/mballoc.h +++ b/fs/ext4/mballoc.h @@ -97,6 +97,11 @@ */ #define MB_NUM_ORDERS(sb) ((sb)->s_blocksize_bits + 2) +/* + * Number of valid freelist orders. One extra order for 0 blocks. + */ +#define MB_FREELIST_NUM_ORDERS(sb) (fls(EXT4_CLUSTERS_PER_GROUP(sb)) + 1) + struct ext4_free_data { /* this links the free block information from sb_info */ struct list_head efd_list;