multiblock allocator improvements

There will be changes coming in future patches which will introduce a new criteria for block allocation. This removes the useless setting of ac_criteria. AFAIU, this might be only used to differentiate between whether a preallocated blocks was allocated or was regular allocator called for allocating blocks. Hence this also adds the debug prints to identify what type of block allocation was done in ext4_mb_show_ac().

Signed-off-by Ritesh Harjani (IBM) <[email protected]>

Signed-off-by Ojaswin Mujoo <[email protected]>

---
 fs/ext4/mballoc.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

fs/ext4/mballoc.c +4 -2

index 5b2ae37a8b80..572e79a698d4 100644
@@ -4391,7 +4391,6 @@ ext4_mb_use_preallocated(struct ext4_allocation_context *ac)
 			atomic_inc(&pa->pa_count);
 			ext4_mb_use_inode_pa(ac, pa);
 			spin_unlock(&pa->pa_lock);
-			ac->ac_criteria = 10;
 			rcu_read_unlock();
 			return true;
 		}

@@ -4434,7 +4433,6 @@ ext4_mb_use_preallocated(struct ext4_allocation_context *ac)
 	}
 	if (cpa) {
 		ext4_mb_use_group_pa(ac, cpa);
-		ac->ac_criteria = 20;
 		return true;
 	}
 	return false;

@@ -5131,6 +5129,10 @@ static void ext4_mb_show_ac(struct ext4_allocation_context *ac)
 			(unsigned long)ac->ac_b_ex.fe_logical,
 			(int)ac->ac_criteria);
 	mb_debug(sb, "%u found", ac->ac_found);
+	mb_debug(sb, "used pa: %s, ", ac->ac_pa ? "yes" : "no");
+	if (ac->ac_pa)
+		mb_debug(sb, "pa_type %s\n", ac->ac_pa->pa_type == MB_GROUP_PA ?
+			 "group pa" : "inode pa");
 	ext4_mb_show_pa(sb);
 }
 #else

Signature · 1 line

2.31.1

ext4_mb_stats & ext4_mb_max_to_scan are never used. We use sbi->s_mb_stats and sbi->s_mb_max_to_scan instead. Hence kill these extern declarations.

Signed-off-by Ritesh Harjani (IBM) <[email protected]>

Signed-off-by Ojaswin Mujoo <[email protected]>

---
 fs/ext4/ext4.h    | 2 --
 fs/ext4/mballoc.h | 2 +-
 2 files changed, 1 insertion(+), 3 deletions(-)

fs/ext4/ext4.h +0 -2

index 140e1eb300d1..b8b00457da8d 100644
@@ -2903,8 +2903,6 @@ int ext4_fc_record_regions(struct super_block *sb, int ino,
 /* mballoc.c */
 extern const struct seq_operations ext4_mb_seq_groups_ops;
 extern const struct seq_operations ext4_mb_seq_structs_summary_ops;
-extern long ext4_mb_stats;
-extern long ext4_mb_max_to_scan;
 extern int ext4_seq_mb_stats_show(struct seq_file *seq, void *offset);
 extern int ext4_mb_init(struct super_block *);
 extern int ext4_mb_release(struct super_block *);

fs/ext4/mballoc.h +1 -1

index dcda2a943cee..165a17893c81 100644
@@ -49,7 +49,7 @@
 #define MB_DEFAULT_MIN_TO_SCAN		10
 
 /*
- * with 'ext4_mb_stats' allocator will collect stats that will be
+ * with 's_mb_stats' allocator will collect stats that will be
  * shown at umount. The collecting costs though!
  */
 #define MB_DEFAULT_STATS		0

Signature · 1 line

2.31.1

group descriptor and group info are not of the same group in ext4_mb_prefetch_fini(). This problem was found during code review/walkthrough and seems like a bug, so fix it.

Signed-off-by Ritesh Harjani (IBM) <[email protected]>

Signed-off-by Ojaswin Mujoo <[email protected]>

---
 fs/ext4/mballoc.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

fs/ext4/mballoc.c +4 -4

index 572e79a698d4..8b22cc07b054 100644
@@ -2569,14 +2569,14 @@ ext4_group_t ext4_mb_prefetch(struct super_block *sb, ext4_group_t group,
 void ext4_mb_prefetch_fini(struct super_block *sb, ext4_group_t group,
 			   unsigned int nr)
 {
-	while (nr-- > 0) {
-		struct ext4_group_desc *gdp = ext4_get_group_desc(sb, group,
-								  NULL);
-		struct ext4_group_info *grp = ext4_get_group_info(sb, group);
+	struct ext4_group_desc *gdp;
+	struct ext4_group_info *grp;
 
+	while (nr-- > 0) {
 		if (!group)
 			group = ext4_get_groups_count(sb);
 		group--;
+		gdp = ext4_get_group_desc(sb, group, NULL);
 		grp = ext4_get_group_info(sb, group);
 
 		if (EXT4_MB_GRP_NEED_INIT(grp) &&

Signature · 1 line

2.31.1

Convert criteria to be an enum so it easier to maintain. This change also makes it easier to insert new criterias in the future.

Signed-off-by Ojaswin Mujoo <[email protected]>

Reviewed-by Ritesh Harjani (IBM) <[email protected]>

Quoted 5 lines · Ojaswin Mujoo

Convert criteria to be an enum so it easier to maintain. This change also makes it easier to insert new criterias in the future.

Signed-off-by Ojaswin Mujoo <[email protected]>

Reviewed-by Ritesh Harjani (IBM) <[email protected]>

Just two small comments below:

fs/ext4/ext4.h enum SHIFT_DIRECTION { · line 131

Quoted 12 lines

fs/ext4/ext4.h +3 -0

index b8b00457da8d..6037b8e0af86 100644
@@ -126,6 +126,14 @@ enum SHIFT_DIRECTION {
 	SHIFT_RIGHT,
 };
 
+/*
+ * Number of criterias defined. For each criteria, mballoc has slightly
+ * different way of finding the required blocks nad usually, higher the

						   ^^^ and

fs/ext4/ext4.h enum SHIFT_DIRECTION { · line 136

Quoted 5 lines

fs/ext4/ext4.h +5 -0

+ * criteria the slower the allocation. We start at lower criterias and keep
+ * falling back to higher ones if we are not able to find any blocks.
+ */
+#define EXT4_MB_NUM_CRS 4
+

So defining this in a different header than the enum itself is fragile. I understand you need it in ext4_sb_info declaration so probably I'd move the enum declaration to ext4.h. Alternatively I suppose we could move a lot of

mballoc stuff out of ext4_sb_info into a separate struct because there's a lot of it. But that would be much larger undertaking.

Also when going for symbolic allocator scan names maybe we could actually make names sensible instead of CR[0-4]? Perhaps like CR_ORDER2_ALIGNED, CR_BEST_LENGHT_FAST, CR_BEST_LENGTH_ALL, CR_ANY_FREE. And probably we could deal with ordered comparisons like in:

                if (cr < 2 &&
                    (!sbi->s_log_groups_per_flex ||
                     ((group & ((1 << sbi->s_log_groups_per_flex) - 1)) != 0)) &
                    !(ext4_has_group_desc_csum(sb) &&
                      (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))))
                        return 0;

to declare CR_FAST_SCAN = 2, or something like that. What do you think?

Honza

Signature · 2 lines

Jan Kara <[email protected]>
SUSE Labs, CR

Quoted 4 lines · Jan Kara

Also when going for symbolic allocator scan names maybe we could actually make names sensible instead of CR[0-4]? Perhaps like CR_ORDER2_ALIGNED, CR_BEST_LENGHT_FAST, CR_BEST_LENGTH_ALL, CR_ANY_FREE. And probably we could deal with ordered comparisons like in:

I like this idea, it should make the code a bit more easier to understand. However just wondering if I should do it as a part of this series or a separate patch since we'll be touching code all around and I don't want to confuse people with the noise :)

Quoted 8 lines

                if (cr < 2 &&
                    (!sbi->s_log_groups_per_flex ||
                     ((group & ((1 << sbi->s_log_groups_per_flex) - 1)) != 0)) &
                    !(ext4_has_group_desc_csum(sb) &&
                      (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))))
                        return 0;

Quoted 1 line

to declare CR_FAST_SCAN = 2, or something like that. What do you think?

About this, wont it be better to just use something like

cr < CR_BEST_LENGTH_ALL

instead of defining a new CR_FAST_SCAN = 2.

The only concern is that if we add a new "fast" CR (say between CR_BEST_LENGTH_FAST and CR_BEST_LENGTH_ALL) then we'll need to make sure we also update CR_FAST_SCAN to 3 which is easy to miss.

Quoted 5 lines · Ojaswin Mujoo

Quoted 4 lines · Jan Kara

Also when going for symbolic allocator scan names maybe we could actually make names sensible instead of CR[0-4]? Perhaps like CR_ORDER2_ALIGNED, CR_BEST_LENGHT_FAST, CR_BEST_LENGTH_ALL, CR_ANY_FREE. And probably we could deal with ordered comparisons like in:

Quoted 4 lines

I like this idea, it should make the code a bit more easier to understand. However just wondering if I should do it as a part of this series or a separate patch since we'll be touching code all around and I don't want to confuse people with the noise :)

I guess a mechanical rename should not be really confusing. It just has to be a separate patch.

Quoted 9 lines

Quoted 9 lines

                if (cr < 2 &&
                    (!sbi->s_log_groups_per_flex ||
                     ((group & ((1 << sbi->s_log_groups_per_flex) - 1)) != 0)) &
                    !(ext4_has_group_desc_csum(sb) &&
                      (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))))
                        return 0;

Quoted 6 lines

Quoted 1 line

to declare CR_FAST_SCAN = 2, or something like that. What do you think?

About this, wont it be better to just use something like

cr < CR_BEST_LENGTH_ALL

instead of defining a new CR_FAST_SCAN = 2.

Yeah, that works as well.

Quoted 3 lines

The only concern is that if we add a new "fast" CR (say between CR_BEST_LENGTH_FAST and CR_BEST_LENGTH_ALL) then we'll need to make sure we also update CR_FAST_SCAN to 3 which is easy to miss.

Well, you have that problem with any naming scheme (and even with numbers). So as long as names are all defined together, there's reasonable chance you'll remember to verify the limits still hold :)

Honza

Signature · 2 lines

Jan Kara <[email protected]>
SUSE Labs, CR

Quoted 6 lines · Jan Kara

Quoted 5 lines · Ojaswin Mujoo

Quoted 4 lines · Jan Kara

Also when going for symbolic allocator scan names maybe we could actually make names sensible instead of CR[0-4]? Perhaps like CR_ORDER2_ALIGNED, CR_BEST_LENGHT_FAST, CR_BEST_LENGTH_ALL, CR_ANY_FREE. And probably we could deal with ordered comparisons like in:

Quoted 7 lines

Quoted 4 lines

I like this idea, it should make the code a bit more easier to understand. However just wondering if I should do it as a part of this series or a separate patch since we'll be touching code all around and I don't want to confuse people with the noise :)

I guess a mechanical rename should not be really confusing. It just has to be a separate patch.

Alright, got it.

Quoted 22 lines

Quoted 9 lines

Quoted 9 lines

                if (cr < 2 &&
                    (!sbi->s_log_groups_per_flex ||
                     ((group & ((1 << sbi->s_log_groups_per_flex) - 1)) != 0)) &
                    !(ext4_has_group_desc_csum(sb) &&
                      (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))))
                        return 0;

Quoted 6 lines

Quoted 1 line

to declare CR_FAST_SCAN = 2, or something like that. What do you think?

About this, wont it be better to just use something like

cr < CR_BEST_LENGTH_ALL

instead of defining a new CR_FAST_SCAN = 2.

Yeah, that works as well.

Quoted 3 lines

The only concern is that if we add a new "fast" CR (say between CR_BEST_LENGTH_FAST and CR_BEST_LENGTH_ALL) then we'll need to make sure we also update CR_FAST_SCAN to 3 which is easy to miss.

Quoted 3 lines

Well, you have that problem with any naming scheme (and even with numbers). So as long as names are all defined together, there's reasonable chance you'll remember to verify the limits still hold :)

haha that's true. Anyways, I'll try a few things and see what looks good. Thanks for the suggestions.

Regards,
ojaswin

Quoted 5 lines

Honza

Signature · 2 lines

Jan Kara <[email protected]>
SUSE Labs, CR

Quoted 37 lines · Ojaswin Mujoo

Quoted 6 lines · Jan Kara

Quoted 5 lines · Ojaswin Mujoo

Quoted 4 lines · Jan Kara

Also when going for symbolic allocator scan names maybe we could actually make names sensible instead of CR[0-4]? Perhaps like CR_ORDER2_ALIGNED, CR_BEST_LENGHT_FAST, CR_BEST_LENGTH_ALL, CR_ANY_FREE. And probably we could deal with ordered comparisons like in:

Quoted 7 lines

Quoted 4 lines

I like this idea, it should make the code a bit more easier to understand. However just wondering if I should do it as a part of this series or a separate patch since we'll be touching code all around and I don't want to confuse people with the noise :)

I guess a mechanical rename should not be really confusing. It just has to be a separate patch.

Alright, got it.

Quoted 22 lines

Quoted 9 lines

Quoted 9 lines

                if (cr < 2 &&
                    (!sbi->s_log_groups_per_flex ||
                     ((group & ((1 << sbi->s_log_groups_per_flex) - 1)) != 0)) &
                    !(ext4_has_group_desc_csum(sb) &&
                      (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))))
                        return 0;

Quoted 6 lines

Quoted 1 line

to declare CR_FAST_SCAN = 2, or something like that. What do you think?

About this, wont it be better to just use something like

cr < CR_BEST_LENGTH_ALL

instead of defining a new CR_FAST_SCAN = 2.

Yeah, that works as well.

Quoted 3 lines

The only concern is that if we add a new "fast" CR (say between CR_BEST_LENGTH_FAST and CR_BEST_LENGTH_ALL) then we'll need to make sure we also update CR_FAST_SCAN to 3 which is easy to miss.

Quoted 5 lines

Quoted 3 lines

Well, you have that problem with any naming scheme (and even with numbers). So as long as names are all defined together, there's reasonable chance you'll remember to verify the limits still hold :)

haha that's true. Anyways, I'll try a few things and see what looks good. Thanks for the suggestions.

Hey Jan,

So I was playing around with this and I prepare a patch to convert CR numbers to symbolic names and it looks good as far as things like these are concerned:

if (cr < CR_POWER2_ALIGNED)

		...

However there's one problem that this numeric naming scheme is used in several places like struct member names, function names, traces and comments. The issue is that replacing it everywhere is making some of the names very long for example:

	atomic_read(&sbi->s_bal_cr0_bad_suggestions));

becomes:

	atomic_read(&sbi->s_bal_cr_power2_aligned_bad_suggestions));

And this is kind of making the code look messy at a lot of places. So right now there are a few options we can consider:

1. Use symbolic names everywhere at the cost of readability

This gives better visibility into the number of extents scanned in each particular CR. For example, this information can be used to see how out block group scanning logic is performing when the BG is fragmented.

Signed-off-by Ojaswin Mujoo <[email protected]>

Reviewed-by Ritesh Harjani (IBM) <[email protected]>

---
 fs/ext4/ext4.h    |  1 +
 fs/ext4/mballoc.c | 12 ++++++++++++
 fs/ext4/mballoc.h |  1 +
 3 files changed, 14 insertions(+)

fs/ext4/ext4.h +1 -0

index 6037b8e0af86..4ba2c95915eb 100644
@@ -1633,6 +1633,7 @@ struct ext4_sb_info {
 	atomic_t s_bal_success;	/* we found long enough chunks */
 	atomic_t s_bal_allocated;	/* in blocks */
 	atomic_t s_bal_ex_scanned;	/* total extents scanned */
+	atomic_t s_bal_cX_ex_scanned[EXT4_MB_NUM_CRS];	/* total extents scanned */
 	atomic_t s_bal_groups_scanned;	/* number of groups scanned */
 	atomic_t s_bal_goals;	/* goal hits */
 	atomic_t s_bal_breaks;	/* too long searches */

fs/ext4/mballoc.c +12 -0

index 323604a2ff45..07a50a13751c 100644
@@ -2077,6 +2077,7 @@ static void ext4_mb_measure_extent(struct ext4_allocation_context *ac,
 	BUG_ON(ac->ac_status != AC_STATUS_CONTINUE);
 
 	ac->ac_found++;
+	ac->ac_cX_found[ac->ac_criteria]++;
 
 	/*
 	 * The special case - take what you catch first

@@ -2249,6 +2250,7 @@ void ext4_mb_simple_scan_group(struct ext4_allocation_context *ac,
 			break;
 		}
 		ac->ac_found++;
+		ac->ac_cX_found[ac->ac_criteria]++;
 
 		ac->ac_b_ex.fe_len = 1 << i;
 		ac->ac_b_ex.fe_start = k << i;

@@ -2362,6 +2364,7 @@ void ext4_mb_scan_aligned(struct ext4_allocation_context *ac,
 			max = mb_find_extent(e4b, i, sbi->s_stripe, &ex);
 			if (max >= sbi->s_stripe) {
 				ac->ac_found++;
+				ac->ac_cX_found[ac->ac_criteria]++;
 				ex.fe_logical = 0xDEADF00D; /* debug value */
 				ac->ac_b_ex = ex;
 				ext4_mb_use_best_found(ac, e4b);

@@ -2894,6 +2897,7 @@ int ext4_seq_mb_stats_show(struct seq_file *seq, void *offset)
 	seq_printf(seq, "\t\thits: %llu\n", atomic64_read(&sbi->s_bal_cX_hits[CR0]));
 	seq_printf(seq, "\t\tgroups_considered: %llu\n",
 		   atomic64_read(&sbi->s_bal_cX_groups_considered[CR0]));
+	seq_printf(seq, "\t\textents_scanned: %u\n", atomic_read(&sbi->s_bal_cX_ex_scanned[CR0]));
 	seq_printf(seq, "\t\tuseless_loops: %llu\n",
 		   atomic64_read(&sbi->s_bal_cX_failed[CR0]));
 	seq_printf(seq, "\t\tbad_suggestions: %u\n",

@@ -2903,6 +2907,7 @@ int ext4_seq_mb_stats_show(struct seq_file *seq, void *offset)
 	seq_printf(seq, "\t\thits: %llu\n", atomic64_read(&sbi->s_bal_cX_hits[CR1]));
 	seq_printf(seq, "\t\tgroups_considered: %llu\n",
 		   atomic64_read(&sbi->s_bal_cX_groups_considered[CR1]));
+	seq_printf(seq, "\t\textents_scanned: %u\n", atomic_read(&sbi->s_bal_cX_ex_scanned[CR1]));
 	seq_printf(seq, "\t\tuseless_loops: %llu\n",
 		   atomic64_read(&sbi->s_bal_cX_failed[CR1]));
 	seq_printf(seq, "\t\tbad_suggestions: %u\n",

@@ -2912,6 +2917,7 @@ int ext4_seq_mb_stats_show(struct seq_file *seq, void *offset)
 	seq_printf(seq, "\t\thits: %llu\n", atomic64_read(&sbi->s_bal_cX_hits[CR2]));
 	seq_printf(seq, "\t\tgroups_considered: %llu\n",
 		   atomic64_read(&sbi->s_bal_cX_groups_considered[CR2]));
+	seq_printf(seq, "\t\textents_scanned: %u\n", atomic_read(&sbi->s_bal_cX_ex_scanned[CR2]));
 	seq_printf(seq, "\t\tuseless_loops: %llu\n",
 		   atomic64_read(&sbi->s_bal_cX_failed[CR2]));
 

@@ -2919,6 +2925,7 @@ int ext4_seq_mb_stats_show(struct seq_file *seq, void *offset)
 	seq_printf(seq, "\t\thits: %llu\n", atomic64_read(&sbi->s_bal_cX_hits[CR3]));
 	seq_printf(seq, "\t\tgroups_considered: %llu\n",
 		   atomic64_read(&sbi->s_bal_cX_groups_considered[CR3]));
+	seq_printf(seq, "\t\textents_scanned: %u\n", atomic_read(&sbi->s_bal_cX_ex_scanned[CR3]));
 	seq_printf(seq, "\t\tuseless_loops: %llu\n",
 		   atomic64_read(&sbi->s_bal_cX_failed[CR3]));
 	seq_printf(seq, "\textents_scanned: %u\n", atomic_read(&sbi->s_bal_ex_scanned));

@@ -4216,7 +4223,12 @@ static void ext4_mb_collect_stats(struct ext4_allocation_context *ac)
 		atomic_add(ac->ac_b_ex.fe_len, &sbi->s_bal_allocated);
 		if (ac->ac_b_ex.fe_len >= ac->ac_o_ex.fe_len)
 			atomic_inc(&sbi->s_bal_success);
+
 		atomic_add(ac->ac_found, &sbi->s_bal_ex_scanned);
+		for (int i=0; i<EXT4_MB_NUM_CRS; i++) {
+			atomic_add(ac->ac_cX_found[i], &sbi->s_bal_cX_ex_scanned[i]);
+		}
+
 		atomic_add(ac->ac_groups_scanned, &sbi->s_bal_groups_scanned);
 		if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&
 				ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)

fs/ext4/mballoc.h +1 -0

index f0087a85e366..004b8d163cc9 100644
@@ -193,6 +193,7 @@ struct ext4_allocation_context {
 	__u16 ac_groups_scanned;
 	__u16 ac_groups_linear_remaining;
 	__u16 ac_found;
+	__u16 ac_cX_found[EXT4_MB_NUM_CRS];
 	__u16 ac_tail;
 	__u16 ac_buddy;
 	__u8 ac_status;

Signature · 1 line

2.31.1

Track number of allocations where the length of blocks allocated is equal to the length of goal blocks (post normalization). This metric could be useful if making changes to the allocator logic in the future as it could give us visibility into how often do we trim our requests.

PS: ac_b_ex.fe_len might get modified due to preallocation efforts and hence we use ac_f_ex.fe_len instead since we want to compare how much the allocator was able to actually find.

Signed-off-by Ojaswin Mujoo <[email protected]>

Reviewed-by Ritesh Harjani (IBM) <[email protected]>

---
 fs/ext4/ext4.h    | 1 +
 fs/ext4/mballoc.c | 3 +++
 2 files changed, 4 insertions(+)

fs/ext4/ext4.h +1 -0

index 4ba2c95915eb..d8fa01e54e81 100644
@@ -1636,6 +1636,7 @@ struct ext4_sb_info {
 	atomic_t s_bal_cX_ex_scanned[EXT4_MB_NUM_CRS];	/* total extents scanned */
 	atomic_t s_bal_groups_scanned;	/* number of groups scanned */
 	atomic_t s_bal_goals;	/* goal hits */
+	atomic_t s_bal_len_goals;	/* len goal hits */
 	atomic_t s_bal_breaks;	/* too long searches */
 	atomic_t s_bal_2orders;	/* 2^order hits */
 	atomic_t s_bal_cr0_bad_suggestions;

fs/ext4/mballoc.c +3 -0

index 07a50a13751c..c4ab8f412d32 100644
@@ -2930,6 +2930,7 @@ int ext4_seq_mb_stats_show(struct seq_file *seq, void *offset)
 		   atomic64_read(&sbi->s_bal_cX_failed[CR3]));
 	seq_printf(seq, "\textents_scanned: %u\n", atomic_read(&sbi->s_bal_ex_scanned));
 	seq_printf(seq, "\t\tgoal_hits: %u\n", atomic_read(&sbi->s_bal_goals));
+	seq_printf(seq, "\t\tlen_goal_hits: %u\n", atomic_read(&sbi->s_bal_len_goals));
 	seq_printf(seq, "\t\t2^n_hits: %u\n", atomic_read(&sbi->s_bal_2orders));
 	seq_printf(seq, "\t\tbreaks: %u\n", atomic_read(&sbi->s_bal_breaks));
 	seq_printf(seq, "\t\tlost: %u\n", atomic_read(&sbi->s_mb_lost_chunks));

@@ -4233,6 +4234,8 @@ static void ext4_mb_collect_stats(struct ext4_allocation_context *ac)
 		if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&
 				ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)
 			atomic_inc(&sbi->s_bal_goals);
+		if (ac->ac_f_ex.fe_len == ac->ac_g_ex.fe_len)
+			atomic_inc(&sbi->s_bal_len_goals);
 		if (ac->ac_found > sbi->s_mb_max_to_scan)
 			atomic_inc(&sbi->s_bal_breaks);
 	}

Signature · 1 line

2.31.1

When we are inside ext4_mb_complex_scan_group() in CR1, we can be sure that this group has atleast 1 big enough continuous free extent to satisfy our request because (free / fragments) > goal length.

Hence, instead of wasting time looping over smaller free extents, only try to consider the free extent if we are sure that it has enough continuous free space to satisfy goal length. This is particularly useful when scanning highly fragmented BGs in CR1 as, without this patch, the allocator might stop scanning early before reaching the big enough free extent (due to ac_found > mb_max_to_scan) which causes us to uncessarily trim the request.

Signed-off-by Ojaswin Mujoo <[email protected]>

Reviewed-by Ritesh Harjani (IBM) <[email protected]>

---
 fs/ext4/mballoc.c | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

fs/ext4/mballoc.c +18 -1

index c4ab8f412d32..14529d2fe65f 100644
@@ -2279,7 +2279,7 @@ void ext4_mb_complex_scan_group(struct ext4_allocation_context *ac,
 	struct super_block *sb = ac->ac_sb;
 	void *bitmap = e4b->bd_bitmap;
 	struct ext4_free_extent ex;
-	int i;
+	int i, j, freelen;
 	int free;
 
 	free = e4b->bd_info->bb_free;

@@ -2306,6 +2306,23 @@ void ext4_mb_complex_scan_group(struct ext4_allocation_context *ac,
 			break;
 		}
 
+		if (ac->ac_criteria < CR2) {
+			/*
+			 * In CR1, we are sure that this group will
+			 * have a large enough continuous free extent, so skip
+			 * over the smaller free extents
+			 */
+			j = mb_find_next_bit(bitmap,
+						EXT4_CLUSTERS_PER_GROUP(sb), i);
+			freelen = j - i;
+
+			if (freelen < ac->ac_g_ex.fe_len) {
+				i = j;
+				free -= freelen;
+				continue;
+			}
+		}
+
 		mb_find_extent(e4b, i, ac->ac_g_ex.fe_len, &ex);
 		if (WARN_ON(ex.fe_len <= 0))
 			break;

Signature · 1 line

2.31.1

Currently, ext4_mb_prefetch() and ext4_mb_prefetch_fini() skip BLOCK_UNINIT groups since fetching their bitmaps doesn't need disk IO. As a consequence, we end not initializing the buddy structures and CR0/1 lists for these BGs, even though it can be done without any disk IO overhead. Hence, don't skip such BGs during prefetch and prefetch_fini.

This improves the accuracy of CR0/1 allocation as earlier, we could have essentially empty BLOCK_UNINIT groups being ignored by CR0/1 due to their buddy not being initialized, leading to slower CR2 allocations. With this patch CR0/1 will be able to discover these groups as well, thus improving performance.

Signed-off-by Ojaswin Mujoo <[email protected]>

Reviewed-by Ritesh Harjani (IBM) <[email protected]>

---
 fs/ext4/mballoc.c | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

fs/ext4/mballoc.c +2 -6

index 14529d2fe65f..48726a831264 100644
@@ -2557,9 +2557,7 @@ ext4_group_t ext4_mb_prefetch(struct super_block *sb, ext4_group_t group,
 		 */
 		if (!EXT4_MB_GRP_TEST_AND_SET_READ(grp) &&
 		    EXT4_MB_GRP_NEED_INIT(grp) &&
-		    ext4_free_group_clusters(sb, gdp) > 0 &&
-		    !(ext4_has_group_desc_csum(sb) &&
-		      (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)))) {
+		    ext4_free_group_clusters(sb, gdp) > 0 ) {
 			bh = ext4_read_block_bitmap_nowait(sb, group, true);
 			if (bh && !IS_ERR(bh)) {
 				if (!buffer_uptodate(bh) && cnt)

@@ -2600,9 +2598,7 @@ void ext4_mb_prefetch_fini(struct super_block *sb, ext4_group_t group,
 		grp = ext4_get_group_info(sb, group);
 
 		if (EXT4_MB_GRP_NEED_INIT(grp) &&
-		    ext4_free_group_clusters(sb, gdp) > 0 &&
-		    !(ext4_has_group_desc_csum(sb) &&
-		      (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)))) {
+		    ext4_free_group_clusters(sb, gdp) > 0) {
 			if (ext4_mb_init_group(sb, group, GFP_NOFS))
 				break;
 		}

Signature · 1 line

2.31.1

Quoted 6 lines · Ojaswin Mujoo

Currently, ext4_mb_prefetch() and ext4_mb_prefetch_fini() skip BLOCK_UNINIT groups since fetching their bitmaps doesn't need disk IO. As a consequence, we end not initializing the buddy structures and CR0/1 lists for these BGs, even though it can be done without any disk IO overhead. Hence, don't skip such BGs during prefetch and prefetch_fini.

Quoted 7 lines

This improves the accuracy of CR0/1 allocation as earlier, we could have essentially empty BLOCK_UNINIT groups being ignored by CR0/1 due to their buddy not being initialized, leading to slower CR2 allocations. With this patch CR0/1 will be able to discover these groups as well, thus improving performance.

Signed-off-by Ojaswin Mujoo <[email protected]>

Reviewed-by Ritesh Harjani (IBM) <[email protected]>

The patch looks good. I just somewhat wonder - this change may result in uninitialized groups being initialized and used earlier (previously we'd rather search in other already initialized groups) which may spread allocations more. But I suppose that's fine and uninit groups are not really a feature meant to limit fragmentation and as the filesystem ages the differences should be minimal. So feel free to add:

Reviewed-by Jan Kara <[email protected]>

Honza

Quoted 34 lines

---
 fs/ext4/mballoc.c | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

fs/ext4/mballoc.c +2 -6

index 14529d2fe65f..48726a831264 100644
@@ -2557,9 +2557,7 @@ ext4_group_t ext4_mb_prefetch(struct super_block *sb, ext4_group_t group,
 		 */
 		if (!EXT4_MB_GRP_TEST_AND_SET_READ(grp) &&
 		    EXT4_MB_GRP_NEED_INIT(grp) &&
-		    ext4_free_group_clusters(sb, gdp) > 0 &&
-		    !(ext4_has_group_desc_csum(sb) &&
-		      (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)))) {
+		    ext4_free_group_clusters(sb, gdp) > 0 ) {
 			bh = ext4_read_block_bitmap_nowait(sb, group, true);
 			if (bh && !IS_ERR(bh)) {
 				if (!buffer_uptodate(bh) && cnt)

@@ -2600,9 +2598,7 @@ void ext4_mb_prefetch_fini(struct super_block *sb, ext4_group_t group,
 		grp = ext4_get_group_info(sb, group);
 
 		if (EXT4_MB_GRP_NEED_INIT(grp) &&
-		    ext4_free_group_clusters(sb, gdp) > 0 &&
-		    !(ext4_has_group_desc_csum(sb) &&
-		      (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)))) {
+		    ext4_free_group_clusters(sb, gdp) > 0) {
 			if (ext4_mb_init_group(sb, group, GFP_NOFS))
 				break;
 		}

Signature · 1 line

2.31.1

Signature · 2 lines

Jan Kara <[email protected]>
SUSE Labs, CR

Quoted 22 lines · Jan Kara

Quoted 6 lines · Ojaswin Mujoo

Currently, ext4_mb_prefetch() and ext4_mb_prefetch_fini() skip BLOCK_UNINIT groups since fetching their bitmaps doesn't need disk IO. As a consequence, we end not initializing the buddy structures and CR0/1 lists for these BGs, even though it can be done without any disk IO overhead. Hence, don't skip such BGs during prefetch and prefetch_fini.

Quoted 7 lines

This improves the accuracy of CR0/1 allocation as earlier, we could have essentially empty BLOCK_UNINIT groups being ignored by CR0/1 due to their buddy not being initialized, leading to slower CR2 allocations. With this patch CR0/1 will be able to discover these groups as well, thus improving performance.

Signed-off-by Ojaswin Mujoo <[email protected]>

Reviewed-by Ritesh Harjani (IBM) <[email protected]>

The patch looks good. I just somewhat wonder - this change may result in uninitialized groups being initialized and used earlier (previously we'd rather search in other already initialized groups) which may spread allocations more. But I suppose that's fine and uninit groups are not really a feature meant to limit fragmentation and as the filesystem ages the differences should be minimal. So feel free to add:

Quoted 3 lines

Reviewed-by Jan Kara <[email protected]>

Honza

Thanks for the review. As for the allocation spread, I agree that it should be something our goal determination logic should take care of rather than limiting the BGs available to the allocator.

Another point I wanted to discuss wrt this patch series was why were the BLOCK_UNINIT groups not being prefetched earlier. One point I can think of is that this might lead to memory pressure when we have too many empty BGs in a very large (say terabytes) disk.

But i'd still like to know if there's some history behind not prefetching block uninit.

Quoted 35 lines · Ojaswin Mujoo

Quoted 22 lines · Jan Kara

Quoted 6 lines · Ojaswin Mujoo

Currently, ext4_mb_prefetch() and ext4_mb_prefetch_fini() skip BLOCK_UNINIT groups since fetching their bitmaps doesn't need disk IO. As a consequence, we end not initializing the buddy structures and CR0/1 lists for these BGs, even though it can be done without any disk IO overhead. Hence, don't skip such BGs during prefetch and prefetch_fini.

Quoted 7 lines

This improves the accuracy of CR0/1 allocation as earlier, we could have essentially empty BLOCK_UNINIT groups being ignored by CR0/1 due to their buddy not being initialized, leading to slower CR2 allocations. With this patch CR0/1 will be able to discover these groups as well, thus improving performance.

Signed-off-by Ojaswin Mujoo <[email protected]>

Reviewed-by Ritesh Harjani (IBM) <[email protected]>

The patch looks good. I just somewhat wonder - this change may result in uninitialized groups being initialized and used earlier (previously we'd rather search in other already initialized groups) which may spread allocations more. But I suppose that's fine and uninit groups are not really a feature meant to limit fragmentation and as the filesystem ages the differences should be minimal. So feel free to add:

Quoted 3 lines

Reviewed-by Jan Kara <[email protected]>

Honza

Thanks for the review. As for the allocation spread, I agree that it should be something our goal determination logic should take care of rather than limiting the BGs available to the allocator.

Another point I wanted to discuss wrt this patch series was why were the BLOCK_UNINIT groups not being prefetched earlier. One point I can think of is that this might lead to memory pressure when we have too many empty BGs in a very large (say terabytes) disk.

Quoted 2 lines

But i'd still like to know if there's some history behind not prefetching block uninit.

Hum, I don't remember anything. Maybe Ted will. You can ask him today on a call.

Honza

Signature · 2 lines

Jan Kara <[email protected]>
SUSE Labs, CR

Quoted 11 lines

Quoted 4 lines

This improves the accuracy of CR0/1 allocation as earlier, we could have essentially empty BLOCK_UNINIT groups being ignored by CR0/1 due to their buddy not being initialized, leading to slower CR2 allocations. With this patch CR0/1 will be able to discover these groups as well, thus improving performance.

The patch looks good. I just somewhat wonder - this change may result in uninitialized groups being initialized and used earlier (previously we'd rather search in other already initialized groups) which may spread allocations more. But I suppose that's fine and uninit groups are not really a feature meant to limit fragmentation and as the filesystem ages the differences should be minimal. So feel free to add:

Another point I wanted to discuss wrt this patch series was why were the BLOCK_UNINIT groups not being prefetched earlier. One point I can think of is that this might lead to memory pressure when we have too many empty BGs in a very large (say terabytes) disk.

Before this patch, the call stack in ext4_run_li_request is as follows:

/*
* nr = no. of BGs we want to fetch (=s_mb_prefetch)
* prefetch_ios = no. of BGs not uptodate after
* ext4_read_block_bitmap_nowait()
*/
next_group = ext4_mb_prefetch(sb, group, nr, prefetch_ios); ext4_mb_prefetch_fini(sb, next_group prefetch_ios);

ext4_mb_prefetch_fini() will only try to initialize buddies for BGs in range [next_group - prefetch_ios, next_group). This is incorrect since sometimes (prefetch_ios < nr), which causes ext4_mb_prefetch_fini() to incorrectly ignore some of the BGs that might need initialization. This issue is more notable now with the previous patch enabling "fetching" of BLOCK_UNINIT BGs which are marked buffer_uptodate by default.

Fix this by passing nr to ext4_mb_prefetch_fini() instead of prefetch_ios so that it considers the right range of groups.

Similarly, make sure we don't pass nr=0 to ext4_mb_prefetch_fini() in ext4_mb_regular_allocator() since we might have prefetched BLOCK_UNINIT groups that would need buddy initialization.

Signed-off-by Ojaswin Mujoo <[email protected]>

Reviewed-by Ritesh Harjani (IBM) <[email protected]>

---
 fs/ext4/mballoc.c |  4 ----
 fs/ext4/super.c   | 11 ++++-------
 2 files changed, 4 insertions(+), 11 deletions(-)

fs/ext4/mballoc.c +0 -4

index 48726a831264..410c9636907b 100644
@@ -2702,8 +2702,6 @@ ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
 			if ((prefetch_grp == group) &&
 			    (cr > CR1 ||
 			     prefetch_ios < sbi->s_mb_prefetch_limit)) {
-				unsigned int curr_ios = prefetch_ios;
-
 				nr = sbi->s_mb_prefetch;
 				if (ext4_has_feature_flex_bg(sb)) {
 					nr = 1 << sbi->s_log_groups_per_flex;

@@ -2712,8 +2710,6 @@ ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
 				}
 				prefetch_grp = ext4_mb_prefetch(sb, group,
 							nr, &prefetch_ios);
-				if (prefetch_ios == curr_ios)
-					nr = 0;
 			}
 
 			/* This now checks without needing the buddy page */

fs/ext4/super.c +4 -7

index 72ead3b56706..9dbb09cfc8f7 100644
@@ -3636,16 +3636,13 @@ static int ext4_run_li_request(struct ext4_li_request *elr)
 	ext4_group_t group = elr->lr_next_group;
 	unsigned int prefetch_ios = 0;
 	int ret = 0;
+	int nr = EXT4_SB(sb)->s_mb_prefetch;
 	u64 start_time;
 
 	if (elr->lr_mode == EXT4_LI_MODE_PREFETCH_BBITMAP) {
-		elr->lr_next_group = ext4_mb_prefetch(sb, group,
-				EXT4_SB(sb)->s_mb_prefetch, &prefetch_ios);
-		if (prefetch_ios)
-			ext4_mb_prefetch_fini(sb, elr->lr_next_group,
-					      prefetch_ios);
-		trace_ext4_prefetch_bitmaps(sb, group, elr->lr_next_group,
-					    prefetch_ios);
+		elr->lr_next_group = ext4_mb_prefetch(sb, group, nr, &prefetch_ios);
+		ext4_mb_prefetch_fini(sb, elr->lr_next_group, nr);
+		trace_ext4_prefetch_bitmaps(sb, group, elr->lr_next_group, nr);
 		if (group >= elr->lr_next_group) {
 			ret = 1;
 			if (elr->lr_first_not_zeroed != ngroups &&

Signature · 1 line

2.31.1

Make the logic of searching average fragment list of a given order reusable by abstracting it out to a differnet function. This will also avoid code duplication in upcoming patches.

No functional changes.

Signed-off-by Ojaswin Mujoo <[email protected]>

Reviewed-by Ritesh Harjani (IBM) <[email protected]>

---
 fs/ext4/mballoc.c | 51 ++++++++++++++++++++++++++++++-----------------
 1 file changed, 33 insertions(+), 18 deletions(-)

fs/ext4/mballoc.c +33 -18

index 410c9636907b..1ce1174aea52 100644
@@ -902,6 +902,37 @@ static void ext4_mb_choose_next_group_cr0(struct ext4_allocation_context *ac,
 	}
 }
 
+/*
+ * Find a suitable group of given order from the average fragments list.
+ */
+static struct ext4_group_info *
+ext4_mb_find_good_group_avg_frag_lists(struct ext4_allocation_context *ac, int order)
+{
+	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
+	struct list_head *frag_list = &sbi->s_mb_avg_fragment_size[order];
+	rwlock_t *frag_list_lock = &sbi->s_mb_avg_fragment_size_locks[order];
+	struct ext4_group_info *grp = NULL, *iter;
+	enum criteria cr = ac->ac_criteria;
+
+	if (list_empty(frag_list))
+		return NULL;
+	read_lock(frag_list_lock);
+	if (list_empty(frag_list)) {
+		read_unlock(frag_list_lock);
+		return NULL;
+	}
+	list_for_each_entry(iter, frag_list, bb_avg_fragment_size_node) {
+		if (sbi->s_mb_stats)
+			atomic64_inc(&sbi->s_bal_cX_groups_considered[cr]);
+		if (likely(ext4_mb_good_group(ac, iter->bb_group, cr))) {
+			grp = iter;
+			break;
+		}
+	}
+	read_unlock(frag_list_lock);
+	return grp;
+}
+
 /*
  * Choose next group by traversing average fragment size list of suitable
  * order. Updates *new_cr if cr level needs an update.

@@ -910,7 +941,7 @@ static void ext4_mb_choose_next_group_cr1(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 *grp = NULL, *iter;
+	struct ext4_group_info *grp = NULL;
 	int i;
 
 	if (unlikely(ac->ac_flags & EXT4_MB_CR1_OPTIMIZED)) {

@@ -920,23 +951,7 @@ static void ext4_mb_choose_next_group_cr1(struct ext4_allocation_context *ac,
 
 	for (i = mb_avg_fragment_size_order(ac->ac_sb, ac->ac_g_ex.fe_len);
 	     i < MB_NUM_ORDERS(ac->ac_sb); i++) {
-		if (list_empty(&sbi->s_mb_avg_fragment_size[i]))
-			continue;
-		read_lock(&sbi->s_mb_avg_fragment_size_locks[i]);
-		if (list_empty(&sbi->s_mb_avg_fragment_size[i])) {
-			read_unlock(&sbi->s_mb_avg_fragment_size_locks[i]);
-			continue;
-		}
-		list_for_each_entry(iter, &sbi->s_mb_avg_fragment_size[i],
-				    bb_avg_fragment_size_node) {
-			if (sbi->s_mb_stats)
-				atomic64_inc(&sbi->s_bal_cX_groups_considered[CR1]);
-			if (likely(ext4_mb_good_group(ac, iter->bb_group, CR1))) {
-				grp = iter;
-				break;
-			}
-		}
-		read_unlock(&sbi->s_mb_avg_fragment_size_locks[i]);
+		grp = ext4_mb_find_good_group_avg_frag_lists(ac, i);
 		if (grp)
 			break;
 	}

Signature · 1 line

2.31.1

CR1_5 aims to optimize allocations which can't be satisfied in CR1. The fact that we couldn't find a group in CR1 suggests that it would be difficult to find a continuous extent to compleltely satisfy our allocations. So before falling to the slower CR2, in CR1.5 we proactively trim the the preallocations so we can find a group with (free / fragments) big enough. This speeds up our allocation at the cost of slightly reduced preallocation.

The patch also adds a new sysfs tunable:

* /sys/fs/ext4/<partition>/mb_cr1_5_max_trim_order

This controls how much CR1.5 can trim a request before falling to CR2. For example, for a request of order 7 and max trim order 2, CR1.5 can trim this upto order 5.

Signed-off-by Ojaswin Mujoo <[email protected]>

Reviewed-by Ritesh Harjani (IBM) <[email protected]>

fs/ext4/mballoc.c +19 -0

+/*
+ * We couldn't find a group in CR1 so try to find the highest free fragment
+ * order we have and proactively trim the goal request length to that order to
+ * find a suitable group faster.
+ *
+ * This optimizes allocation speed at the cost of slightly reduced
+ * preallocations. However, we make sure that we don't trim the request too
+ * much and fall to CR2 in that case.
+ */
+static void ext4_mb_choose_next_group_cr1_5(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 *grp = NULL;
+	int i, order, min_order;
+
+	if (unlikely(ac->ac_flags & EXT4_MB_CR1_5_OPTIMIZED)) {
+		if (sbi->s_mb_stats)
+			atomic_inc(&sbi->s_bal_cr1_5_bad_suggestions);

fs/ext4/mballoc.c +10 -0

+		} else {
+			break;
+		}
+
+		grp = ext4_mb_find_good_group_avg_frag_lists(ac,
+							     mb_avg_fragment_size_order(ac->ac_sb,
+							     ac->ac_g_ex.fe_len));
+		if (grp)
+			break;
+	}

Quoted 10 lines · Ojaswin Mujoo

CR1_5 aims to optimize allocations which can't be satisfied in CR1. The fact that we couldn't find a group in CR1 suggests that it would be difficult to find a continuous extent to compleltely satisfy our allocations. So before falling to the slower CR2, in CR1.5 we proactively trim the the preallocations so we can find a group with (free / fragments) big enough. This speeds up our allocation at the cost of slightly reduced preallocation.

The patch also adds a new sysfs tunable:

Quoted 8 lines

* /sys/fs/ext4/<partition>/mb_cr1_5_max_trim_order

This controls how much CR1.5 can trim a request before falling to CR2. For example, for a request of order 7 and max trim order 2, CR1.5 can trim this upto order 5.

Signed-off-by Ojaswin Mujoo <[email protected]>

Reviewed-by Ritesh Harjani (IBM) <[email protected]>

The idea looks good. Couple of questions below...

Quoted 26 lines

fs/ext4/mballoc.c +26 -0

+/*
+ * We couldn't find a group in CR1 so try to find the highest free fragment
+ * order we have and proactively trim the goal request length to that order to
+ * find a suitable group faster.
+ *
+ * This optimizes allocation speed at the cost of slightly reduced
+ * preallocations. However, we make sure that we don't trim the request too
+ * much and fall to CR2 in that case.
+ */
+static void ext4_mb_choose_next_group_cr1_5(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 *grp = NULL;
+	int i, order, min_order;
+
+	if (unlikely(ac->ac_flags & EXT4_MB_CR1_5_OPTIMIZED)) {
+		if (sbi->s_mb_stats)
+			atomic_inc(&sbi->s_bal_cr1_5_bad_suggestions);
+	}
+
+	/*
+	 * mb_avg_fragment_size_order() returns order in a way that makes
+	 * retrieving back the length using (1 << order) inaccurate. Hence, use
+	 * fls() instead since we need to know the actual length while modifying
+	 * goal length.

fs/ext4/mballoc.c static void ext4_mb_choose_next_group_cr1(struct ext4_allocation_context *ac, · line 995

Quoted 3 lines

fs/ext4/mballoc.c +3 -0

+	 */
+	order = fls(ac->ac_g_ex.fe_len);
+	min_order = order - sbi->s_mb_cr1_5_max_trim_order;

Given we still require the allocation contains at least originally requested blocks, is it ever the case that goal size would be 8 times larger than original alloc size? Otherwise the sbi->s_mb_cr1_5_max_trim_order logic seems a bit pointless...

fs/ext4/mballoc.c static void ext4_mb_choose_next_group_cr1(struct ext4_allocation_context *ac, · line 997

Quoted 3 lines

fs/ext4/mballoc.c +2 -0

+	if (min_order < 0)
+		min_order = 0;

Perhaps add:

	if (1 << min_order < ac->ac_o_ex.fe_len)
		min_order = fls(ac->ac_o_ex.fe_len) + 1;

and then you can drop the condition from the loop below...

fs/ext4/mballoc.c static void ext4_mb_choose_next_group_cr1(struct ext4_allocation_context *ac, · line 1006

Quoted 10 lines

fs/ext4/mballoc.c +9 -0

+
+	for (i = order; i >= min_order; i--) {
+		if (ac->ac_o_ex.fe_len <= (1 << i)) {
+			/*
+			 * Scale down goal len to make sure we find something
+			 * in the free fragments list. Basically, reduce
+			 * preallocations.
+			 */
+			ac->ac_g_ex.fe_len = 1 << i;

When scaling down the size with sbi->s_stripe > 1, it would be better to choose multiple of sbi->s_stripe and not power of two. But our stripe support is fairly weak anyway (e.g. initial goal size does not reflect it at all AFAICT) so probably we don't care here either.

Quoted 11 lines

fs/ext4/mballoc.c +10 -0

+		} else {
+			break;
+		}
+
+		grp = ext4_mb_find_good_group_avg_frag_lists(ac,
+							     mb_avg_fragment_size_order(ac->ac_sb,
+							     ac->ac_g_ex.fe_len));
+		if (grp)
+			break;
+	}

fs/ext4/mballoc.c static void ext4_mb_choose_next_group_cr1(struct ext4_allocation_context *ac, · line 1026

Quoted 10 lines

fs/ext4/mballoc.c +7 -0

+
+	if (grp) {
+		*group = grp->bb_group;
+		ac->ac_flags |= EXT4_MB_CR1_5_OPTIMIZED;
+	} else {
+		/* Reset goal length to original goal length before falling into CR2 */
+		ac->ac_g_ex.fe_len = ac->ac_orig_goal_len;
 		*new_cr = CR2;
 	}
 }

Honza

Signature · 2 lines

Jan Kara <[email protected]>
SUSE Labs, CR

Quoted 27 lines · Jan Kara

Quoted 26 lines · Ojaswin Mujoo

fs/ext4/mballoc.c +26 -0

+/*
+ * We couldn't find a group in CR1 so try to find the highest free fragment
+ * order we have and proactively trim the goal request length to that order to
+ * find a suitable group faster.
+ *
+ * This optimizes allocation speed at the cost of slightly reduced
+ * preallocations. However, we make sure that we don't trim the request too
+ * much and fall to CR2 in that case.
+ */
+static void ext4_mb_choose_next_group_cr1_5(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 *grp = NULL;
+	int i, order, min_order;
+
+	if (unlikely(ac->ac_flags & EXT4_MB_CR1_5_OPTIMIZED)) {
+		if (sbi->s_mb_stats)
+			atomic_inc(&sbi->s_bal_cr1_5_bad_suggestions);
+	}
+
+	/*
+	 * mb_avg_fragment_size_order() returns order in a way that makes
+	 * retrieving back the length using (1 << order) inaccurate. Hence, use
+	 * fls() instead since we need to know the actual length while modifying
+	 * goal length.

Quoted 8 lines

fs/ext4/mballoc.c static void ext4_mb_choose_next_group_cr1(struct ext4_allocation_context *ac, · line 995

Quoted 3 lines

fs/ext4/mballoc.c +3 -0

+	 */
+	order = fls(ac->ac_g_ex.fe_len);
+	min_order = order - sbi->s_mb_cr1_5_max_trim_order;

Given we still require the allocation contains at least originally requested blocks, is it ever the case that goal size would be 8 times larger than original alloc size? Otherwise the sbi->s_mb_cr1_5_max_trim_order logic seems a bit pointless...

Yes that is possible. In ext4_mb_normalize_request, for orignal request len < 8MB we actually determine the goal length based on the length of the file (i_size) rather than the length of the original request. For eg:

	if (size <= 16 * 1024) {
		size = 16 * 1024;
	} else if (size <= 32 * 1024) {
		size = 32 * 1024;
	} else if (size <= 64 * 1024) {
		size = 64 * 1024;

and this goes all the way upto size = 8MB. So for a case where the file is >8MB, even if the original len is of 1 block(4KB), the goal len would be of 2048 blocks(8MB). That's why we decided to add a tunable depending on the user's preference.

Quoted 48 lines · Ojaswin Mujoo

Quoted 27 lines · Jan Kara

Quoted 26 lines · Ojaswin Mujoo

fs/ext4/mballoc.c +26 -0

+/*
+ * We couldn't find a group in CR1 so try to find the highest free fragment
+ * order we have and proactively trim the goal request length to that order to
+ * find a suitable group faster.
+ *
+ * This optimizes allocation speed at the cost of slightly reduced
+ * preallocations. However, we make sure that we don't trim the request too
+ * much and fall to CR2 in that case.
+ */
+static void ext4_mb_choose_next_group_cr1_5(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 *grp = NULL;
+	int i, order, min_order;
+
+	if (unlikely(ac->ac_flags & EXT4_MB_CR1_5_OPTIMIZED)) {
+		if (sbi->s_mb_stats)
+			atomic_inc(&sbi->s_bal_cr1_5_bad_suggestions);
+	}
+
+	/*
+	 * mb_avg_fragment_size_order() returns order in a way that makes
+	 * retrieving back the length using (1 << order) inaccurate. Hence, use
+	 * fls() instead since we need to know the actual length while modifying
+	 * goal length.

Quoted 8 lines

fs/ext4/mballoc.c static void ext4_mb_choose_next_group_cr1(struct ext4_allocation_context *ac, · line 995

Quoted 3 lines

fs/ext4/mballoc.c +3 -0

+	 */
+	order = fls(ac->ac_g_ex.fe_len);
+	min_order = order - sbi->s_mb_cr1_5_max_trim_order;

Given we still require the allocation contains at least originally requested blocks, is it ever the case that goal size would be 8 times larger than original alloc size? Otherwise the sbi->s_mb_cr1_5_max_trim_order logic seems a bit pointless...

Yes that is possible. In ext4_mb_normalize_request, for orignal request len < 8MB we actually determine the goal length based on the length of the file (i_size) rather than the length of the original request. For eg:

	if (size <= 16 * 1024) {
		size = 16 * 1024;
	} else if (size <= 32 * 1024) {
		size = 32 * 1024;
	} else if (size <= 64 * 1024) {
		size = 64 * 1024;

Quoted 4 lines

and this goes all the way upto size = 8MB. So for a case where the file is >8MB, even if the original len is of 1 block(4KB), the goal len would be of 2048 blocks(8MB). That's why we decided to add a tunable depending on the user's preference.

Ah, I see. The problem with these tunables is that nobody knows to which value tune them :). But yeah, the default value looks sane so I don't object.

Honza

Signature · 2 lines

Jan Kara <[email protected]>
SUSE Labs, CR