[RFC 0/1] ext4: Replace linear search with array of lists in CR_GOAL_LEN_SLOW

[RFC 0/1] ext4: Replace linear search with array of lists in CR_GOAL_LEN_SLOW

[Ojaswin Mujoo]

Hello all!

This patch changes the linear searching in CR_GOAL_LEN_SLOW to use an array of
lists based on the order of requested length. The list array itself holds one
list for each possible order of free blocks in a block group.

While running some performance tests on my setup, I noticed that although the
groups we were considering before finding a good group in CR_GOAL_LEN_SLOW did
improve however there was not much improvement (or regression) in performance
as such, which I believe could be partly because my test disk was not
big enough to highlight the issues of linear traversal in
CR_GOAL_LEN_SLOW.  Unfortunately, I currently don't have a disk that
might be big enough for this however I think theoretically we should see
improvement when we have a very large disk and most of the BGs are near
full. Suggestions on alternate ways to test this or help in getting some
performance numbers is welcome.

That being said, I do believe that other than performance, having such a design
in CR_GOAL_LEN_SLOW is beneficial because:

1. We'll be able to select a BG whose free block order matches our goal length
and hence we won't be filling up bigger holes for small requests. This can
improve fragmentation in the longer run.

2. We'll have more control in what block groups we want to allocate from,
making CR_GOAL_LEN_SLOW more flexible. For example, the ongoing discussions
around introducing new types of BGs marked w/ IOPS flag [1]  which we only want
to use for metadata allocation. With the current design of linear search, we'll
have to check for this flag everytime and skip the BG if we have a data
allocation.  However, with the proposed design, we can easily set up our
freelist to ignore IOPS BGs, which is much more inline with how that patch
handles other criterias.

Now, with this patch, we'll no longer look for BGs linearly and hence this has a
chance of increasing the spread of allocation however I think that shouldn't be
a problem since we still have the MB_DEFAULT_LINEAR_LIMIT for rotational devices
combined with Jan's (merged) patchset that fixed several issues related to
allocation spread [2].

This seems to pass quick xfstests and several iterations for the generic/269
test that stresses the mballoc code. However, there's still some todos in the
patchset eg more testing, refactoring code, bug hunting etc. I wanted to
get the RFC out to check what the community feels about this and for any
suggestions and ideas.

Thanks!

[1] https://lore.kernel.org/linux-ext4/OS3P286MB056789DF4EBAA7363A4346B5AF06A@OS3P286MB0567.JPNP286.PROD.OUTLOOK.COM/
[2] https://lore.kernel.org/all/20220908091301.147-1-jack@suse.cz/

Ojaswin Mujoo (1):
  ext4: Replace linear search with array of lists in CR_GOAL_LEN_SLOW

 fs/ext4/ext4.h    |  25 +++++++--
 fs/ext4/mballoc.c | 134 ++++++++++++++++++++++++++++++++++++++++++++--
 fs/ext4/mballoc.h |   5 ++
 3 files changed, 156 insertions(+), 8 deletions(-)

-- 
2.31.1

[RFC 1/1] ext4: Replace linear search with array of lists in CR_GOAL_LEN_SLOW

[Ojaswin Mujoo]

Originally, in CR_GOAL_LEN_SLOW, we start at goal block group and
keep looking at each BG linearly till we find one with
free blocks > requested blocks and then we allocate from there.

However, due to the linear nature of search we can end up unnecessarily
looping through BGs when none of them have enough free blocks. To avoid
this use an array of lists structure similar to ones used by the faster
CRs. Call this array of lists as freelists as the array has one list for
each possible order of free blocks in a block group.

* Design *

- Calculate freelist order of each BG as fls(grp->bb_free) with empty
  groups having an order of 0.

- Create 1 linked list for each order and place each BG in the respective
  order. Since we have free block data of all BGs on mount, we can classify
  all BGs in one of these lists.

- Upon allocation, if we enter CR_GOAL_LEN_SLOW, we use these freelists
  to quickly find the next group to use based on the request order.

- We update freelist order of a BG after every allocation or free operation
  on it.

* Motivation *

Having such a design in CR_GOAL_LEN_SLOW is beneficial because:

1. Theoretically, if we have a very large disk with large number of filled up
block groups, we'll be able to find the good group faster than linear searching.

2. We'll be able to select a BG whose free block order matches our goal length
and hence we won't be filling up bigger holes for small requests. This can
improve fragmentation in the longer run.

3. We'll have more control in what block groups we want to allocate from,
making CR_GOAL_LEN_SLOW more flexible.

NOTE: With this patch, we'll no longer look for BGs linearly and hence this has a
chance of increasing the spread of allocation however I think that shouldn't be
a problem since we still have the MB_DEFAULT_LINEAR_LIMIT for rotational devices
combined with Jan's (merged) patchset that fixed several issues related to
allocation spread [1].

[1] https://lore.kernel.org/all/20220908091301.147-1-jack@suse.cz/

(Also cleanup some comments to reflect the new symbolic names of criterias)

Signed-off-by: Ojaswin Mujoo <ojaswin@linux.ibm.com>
---
 fs/ext4/ext4.h    |  25 +++++++--
 fs/ext4/mballoc.c | 134 ++++++++++++++++++++++++++++++++++++++++++++--
 fs/ext4/mballoc.h |   5 ++
 3 files changed, 156 insertions(+), 8 deletions(-)

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;
-- 
2.31.1