ext4: Replace linear search with array of lists in CR_GOAL_LEN_SLOW

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/[email protected]/

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

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/[email protected]/

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

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

index 84618c46f239..fd0f9054a5cc 100644
@@ -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

index d7aeb5da7d86..a3b53802899c 100644
@@ -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