multiblock allocator improvements
Subsystems (4)
Ojaswin Mujoo
reviewercover multiblock allocator improvements
** Changes since RFC [1] **
[1] https://lore.kernel.org/linux-ext4/[email protected]/
1. Patch 1 reverts the commit 32c08693
Lore link:
https://lore.kernel.org/linux-ext4/[email protected]/
So this patch was intended to remove a dead if-condition but it was not actually dead code and removing it was causing a performance regression. Unfortunately I somehow missed that when I was reviewing his patchset and it already went in so I had to revert the commit. I've added details of the regression and root cause in the revert commit. Also attaching the performance numbers I observer:
Workload: fsmark - 100GiB ramdisk, 64 threads writing ~42000 files nodelalloc
-----
Baseline kernel: ~5000 files/sec, ~9,000,000 extents scanned
This patchset rebased on
ted/dev w/o revert patch: ~8000 files/sec, ~7,000,000 ex scanned (+40-50%)
This patchset on ted/dev
with revert patch: ~30000 files/sec, ~800,000 ex scanned (+500%)
-----
2. Added Patch 13 which introduces symbolic names for criterias
3. In CR1.5 patch (Patch 12), in ext4_mb_choose_next_group_cr1_5(), while trimming we also consider stripe size now. If specified, we round up the goal length to stripe size. Here, with bigalloc I've made an assumption that stripe size in fs blocks is always a multiple of cluster_ratio. This assumption is based on a yet unmerged patch:
https://lore.kernel.org/linux-ext4/[email protected]/
4. In CR1.5 patch, slight optimization in ext4_mb_choose_next_group_cr1_5() based on Jan's feedback.
I've run xfstests quick on the patchset and plan to run auto overnight. Would report if anything is breaking.
** Original Cover letter **
This patchset intends to improve some of the shortcomings of mb allocator that we had noticed while running various tests and workloads in a POWERPC machine with 64k block size.
** Problems **
More specifically, we were seeing a sharp drop in performance when the FS was highly fragmented (64K bs). We noticed that:
Problem 1: prefetch logic seemed to be skipping BLOCK_UNINIT groups which was resulting in buddy and CR0/1 cache not being initialized for these even though it could be done without any IO. (Not sure if there was any history behind this design, do let me know if so).
Problem 2: With a 64K bs FS, we were commonly seeing cases where CR1 would correctly identify a good group but due to very high fragmentation, complex scan would exit early due to ac->ac_found > s_mb_max_to_scan, resulting in trimming of the allocated len.
Problem 3: Even though our avg free extent was say 4MB and original request was merely 1 block of data, mballoc noramlization kept adding PAs and requesting 8MB chunks. This led to almost all the requests falling into slower CR 2 and with increased threads, we started seeing lots of CR3 requests as well.
** How did we address them **
Problem 1 (Patch 8,9): Make ext4_mb_prefetch also call ext4_read_block_bitmap_nowait() in case of BLOCK_UNINIT, so it can init the BG and exit early without an IO. Next, fix the calls to prefetch_fini so these newly init BGs can have their buddy initialised.
Problem 2 (Patch 7): When we come to complex_scan after CR1, my understanding is that due to free/frag > goal_len, we can be sure that there is atleast one chunk big enough to accomodate the goal request. Hence, we can skip the overhead of mb_find_extent() other accounting for each free extent and just process extents that are big enough.
Problem 3 (Patch 11): To solve this problem, this patchset implements a new allocation criteria (CR1.5 or CR1_5 in code). The idea is that if CR1 fails to find a BG, it will jump to CR1.5. Here the flow is as follows:
* We make an assumption that if CR1 has failed that means none of the currently cached BGs have a big enough continuous extent to satisfy our request In this case we fall to CR1.5.
* In CR 1.5, we find the highest available free/frag BGs (from CR1 lists) and trim the PAs to this order so that we can find a BG without IO overhead of CR2.
* Parallely, prefetch will get in more groups in memory, and as more and more groups are cached, CR1.5 becomes a better replacement of CR2. This is because, for example, if all BGs are cahced and we couldn't find anything in CR0/1, we can assume that no BG has a big enough continuous free extent and hence CR1.5 can directly trim and find the next biggest extent we could get. In this scenario, without CR1.5, we would have continued scanning in CR2 which would have most probably trimmed the request after scanning for ~200 extents.
CR1.5 results in improved allocation speed at the cost of slightly increased trimming of the len of blocks allocated.
** Performance Numbers **
Unless stated otherwise, these numbers are from fsmark and fio tests with 64k BS, 64K pagesize on 100Gi nvme0n1 with nodelalloc. There tests were performed after the FS was fragmented till Avg Fragment Size == 4MB.
* Test 1: Writing ~40000 files of 64K each in a single directory (64 threads, fsmark)
* Test 2: Same as Test 1 on a 500GiB pmem device with dax
* Test 3: 5Gi write with mix of random and seq writes (fio)
* Test 4: 5Gi sequential writes (fio)
Here:
e = extents scanned
c = cr0 / cr1 / cr1.5 / cr2 / cr3 hits
+─────────+───────────────────────────────────+────────────────────────────────+ | | Unpatched | Patched | +─────────+───────────────────────────────────+────────────────────────────────+ | Test 1 | 6866 files/s | 13527 files/s | | | e: 8,188,644 | e: 1,719,725 | | | c: 381 / 330 / - / 4779 / 35534 | c: 381/ 280 / 33299/ 1000/ 6064| +─────────+───────────────────────────────────+────────────────────────────────+ | Test 2 | 6927 files/s | 8422 files/s | | | e: 8,055,911 | e: 261,268 | | | cr: 1011 / 999 / - / 6153 / 32861 | c: 1721 / 1210 / 38093 / 0 / 0 | +─────────+───────────────────────────────────+────────────────────────────────+ | Test 3 | 387 MiB/s | 443 MiB/s | +─────────+───────────────────────────────────+────────────────────────────────+ | Test 4 | 3139 MiB/s | 3180 MiB/s | +─────────+───────────────────────────────────+────────────────────────────────+
The numbers of same tests with 4k bs 64k pagesize are:
+─────────+────────────────────────────────────+────────────────────────────────+ | | Unpatched | Patched | +─────────+────────────────────────────────────+────────────────────────────────+ | Test 1 | 21618 files/s | 23528 files/s | | | e: 8,149,272 | e: 223,013 | | | c: 34 / 1380 / - / 5624 / 34710 | 34 / 1341 / 40387 / 0 / 0 | +─────────+───────────────────────────────────+─────────────────────────────────+ | Test 2 | 30739 files/s | 30946 files/s | | | e: 7,742,853 | e: 2,176,475 | | | c: 1131 / 2244 / - / 3914 / 34468 | c: 1596/1079/28425/1098/8547 | +─────────+───────────────────────────────────+─────────────────────────────────+ | Test 3 | 200 MiB/s | 186MiB/s | +─────────+───────────────────────────────────+─────────────────────────────────+ | Test 4 | 621 MiB/s | 632 MiB/s | +─────────+────────────────────────────────────+────────────────────────────────+
** Some Observations **
1. In the case of highly fragmented 64k blocksize most of the performance is lost since we hold the BG lock while scanning a block group for best extent. As our goal len is 8MB and we only have 4MB blocks, we are taking a long time to scan causing other threads to wait on the BG lock. This can be seen in perf diff of unpatched vs patched:
83.14% -24.89% [kernel.vmlinux] [k] do_raw_spin_lock
Using lockstat and perf call graph I was able to confirm that this lock was the BG lock taken in ext4_mb_regular_allocator, contending with other processes trying to take the same BG's lock in ext4_mb_regular_allocator() and __ext4_new_inode()
2. Currently, I do see some increase in fragmentation, I can take this up as future work. Below are the e2freefrag results after Test 1 with 64k BS:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Unpatched:
Min. free extent: 128 KB
Max. free extent: 8000 KB
Avg. free extent: 4096 KB
Num. free extent: 12630
HISTOGRAM OF FREE EXTENT SIZES:
Extent Size Range : Free extents Free Blocks Percent
128K... 256K- : 1 2 0.00%
256K... 512K- : 1 6 0.00%
512K... 1024K- : 4 48 0.01%
1M... 2M- : 5 120 0.01%
2M... 4M- : 11947 725624 85.31%
4M... 8M- : 672 83796 9.85%Patched:
Min. free extent: 64 KB
Max. free extent: 11648 KB
Avg. free extent: 2688 KB
Num. free extent: 18847
HISTOGRAM OF FREE EXTENT SIZES:
Extent Size Range : Free extents Free Blocks Percent
64K... 128K- : 1 1 0.00%
128K... 256K- : 2 5 0.00%
256K... 512K- : 1 5 0.00%
512K... 1024K- : 297 3909 0.48%
1M... 2M- : 11221 341065 42.13%
2M... 4M- : 4940 294260 36.35%
4M... 8M- : 2384 170169 21.02%
8M... 16M- : 1 182 0.02%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
-------------------------------------
Since these changes are looking good to me from my end, so posting for a feedback from ext4 community.
(gcexfstests -c all quick went fine with no new failures reported)
Any thoughts/suggestions are welcome!!
Regards,
Ojaswin
Ojaswin Mujoo (11):
Revert "ext4: remove ac->ac_found > sbi->s_mb_min_to_scan dead check
in ext4_mb_check_limits"
ext4: Fix a small typo in ext4_mb_prefetch_fini()
ext4: Convert mballoc cr (criteria) to enum
ext4: Add per CR extent scanned counter
ext4: Add counter to track successful allocation of goal length
ext4: Avoid scanning smaller extents in BG during CR1
ext4: Don't skip prefetching BLOCK_UNINIT groups
ext4: Ensure ext4_mb_prefetch_fini() is called for all prefetched BGs
ext4: Abstract out logic to search average fragment list
ext4: Add allocation criteria 1.5 (CR1_5)
ext4: Give symbolic names to mballoc criterias
Ritesh Harjani (IBM) (2):
ext4: mballoc: Remove useless setting of ac_criteria
ext4: Remove unused extern variables declaration
fs/ext4/ext4.h | 70 +++++- fs/ext4/mballoc.c | 455 ++++++++++++++++++++++++++---------- fs/ext4/mballoc.h | 16 +- fs/ext4/super.c | 11 +- fs/ext4/sysfs.c | 2 + include/trace/events/ext4.h | 18 +- 6 files changed, 428 insertions(+), 144 deletions(-)
Signature · 1 line
2.31.1
Ojaswin Mujoo
reviewerPATCH 1/13 Revert "ext4: remove ac->ac_found > sbi->s_mb_min_to_scan dead check in ext4_mb_check_limits"
This reverts commit 32c0869370194ae5ac9f9f501953ef693040f6a1.
The reverted commit was intended to remove a dead check however it was observed that this check was actually being used to exit early instead of looping sbi->s_mb_max_to_scan times when we are able to find a free extent bigger than the goal extent. Due to this, a my performance tests (fsmark, parallel file writes in a highly fragmented FS) were seeing a 2x-3x regression.
Example, the default value of the following variables is:
sbi->s_mb_max_to_scan = 200sbi->s_mb_min_to_scan = 10
In ext4_mb_check_limits() if we find an extent smaller than goal, then we return early and try again. This loop will go on until we have processed sbi->s_mb_max_to_scan(=200) number of free extents at which point we exit and just use whatever we have even if it is smaller than goal extent.
Now, the regression comes when we find an extent bigger than goal. Earlier, in this case we would loop only sbi->s_mb_min_to_scan(=10) times and then just use the bigger extent. However with commit 32c08693 that check was removed and hence we would loop sbi->s_mb_max_to_scan(=200) times even though we have a big enough free extent to satisfy the request. The only time we would exit early would be when the free extent is *exactly* the size of our goal, which is pretty uncommon occurrence and so we would almost always end up looping 200 times.
Hence, revert the commit by adding the check back to fix the regression. Also add a comment to outline this policy.
--- fs/ext4/mballoc.c | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-)
fs/ext4/mballoc.c +15 -1
@@ -2062,7 +2062,7 @@ static void ext4_mb_check_limits(struct ext4_allocation_context *ac,if (bex->fe_len < gex->fe_len)return ; -if (finish_group) +if (finish_group || ac->ac_found > sbi->s_mb_min_to_scan)ext4_mb_use_best_found (ac, e4b); }
@@ -2074,6 +2074,20 @@ static void ext4_mb_check_limits(struct ext4_allocation_context *ac,* in the context. Later, the best found extent will be used, if * mballoc can't find good enough extent. * +* The algorithm used is roughly as follows: +* +* * If free extent found is exactly as big as goal, then +* stop the scan and use it immediately +* +* * If free extent found is smaller than goal, then keep retrying +* upto a max of sbi->s_mb_max_to_scan times (default 200). After +* that stop scanning and use whatever we have. +* +* * If free extent found is bigger than goal, then keep retrying +* upto a max of sbi->s_mb_min_to_scan times (default 10) before +* stopping the scan and using the extent. +* +* * FIXME: real allocation policy is to be designed yet! */ static void ext4_mb_measure_extent(struct ext4_allocation_context *ac,
Signature · 1 line
2.31.1
Ojaswin Mujoo
reviewerPATCH 2/13 ext4: mballoc: Remove useless setting of ac_criteria
In reply to Ojaswin MujooFrom: "Ritesh Harjani (IBM)" <[email protected]>
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().
--- fs/ext4/mballoc.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)
fs/ext4/mballoc.c +4 -2
@@ -4582,7 +4582,6 @@ ext4_mb_use_preallocated(struct ext4_allocation_context *ac)atomic_inc (&tmp_pa->pa_count);ext4_mb_use_inode_pa (ac, tmp_pa);spin_unlock (&tmp_pa->pa_lock); - ac->ac_criteria =10 ;read_unlock (&ei->i_prealloc_lock);return true; }
@@ -4625,7 +4624,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;
@@ -5407,6 +5405,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
Ojaswin Mujoo
reviewerPATCH 4/13 ext4: Fix a small typo in ext4_mb_prefetch_fini()
In reply to Ojaswin MujooFix a small typo in the if condition introduced in the commit b6bef1b5.
--- fs/ext4/mballoc.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
fs/ext4/mballoc.c +1 -1
@@ -2609,7 +2609,7 @@ void ext4_mb_prefetch_fini(struct super_block *sb, ext4_group_t group, gdp =ext4_get_group_desc (sb, group,NULL ); grp =ext4_get_group_info (sb, group); -if (grp && grp &&EXT4_MB_GRP_NEED_INIT (grp) && +if (gdp && 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 )))) {
Signature · 1 line
2.31.1
Ojaswin Mujoo
reviewerPATCH 5/13 ext4: Convert mballoc cr (criteria) to enum
In reply to Ojaswin MujooConvert criteria to be an enum so it easier to maintain and update the tracefiles to use enum names. This change also makes it easier to insert new criterias in the future.
There is no functional change in this patch.
--- fs/ext4/ext4.h | 23 +++++++-- fs/ext4/mballoc.c | 96 ++++++++++++++++++------------------- include/trace/events/ext4.h | 16 ++++++- 3 files changed, 82 insertions(+), 53 deletions(-)
fs/ext4/ext4.h +20 -3
@@ -127,6 +127,23 @@ 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 +* 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 +/* +* All possible allocation criterias for mballoc +*/ +enum criteria { +CR0 , +CR1 , +CR2 , +CR3 , +}; +/* * Flags used in mballoc's allocation_context flags field. *
@@ -1542,9 +1559,9 @@ struct ext4_sb_info {atomic_t s_bal_2orders;/* 2^order hits */ atomic_t s_bal_cr0_bad_suggestions;atomic_t s_bal_cr1_bad_suggestions; -atomic64_t s_bal_cX_groups_considered[4 ]; -atomic64_t s_bal_cX_hits[4 ]; -atomic64_t s_bal_cX_failed[4 ];/* cX loop didn't find blocks */ +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 */ atomic_t s_mb_buddies_generated;/* number of buddies generated */ atomic64_t s_mb_generation_time;atomic_t s_mb_lost_chunks;
fs/ext4/mballoc.c +48 -48
283 lines not on this page · raw message
include/trace/events/ext4.h +14 -2
@@ -120,6 +120,18 @@ TRACE_DEFINE_ENUM(EXT4_FC_REASON_MAX); { EXT4_FC_REASON_INODE_JOURNAL_DATA, "INODE_JOURNAL_DATA"}, \ { EXT4_FC_REASON_ENCRYPTED_FILENAME, "ENCRYPTED_FILENAME"}) +TRACE_DEFINE_ENUM (CR0 ); +TRACE_DEFINE_ENUM (CR1 ); +TRACE_DEFINE_ENUM (CR2 ); +TRACE_DEFINE_ENUM (CR3 ); + +#define show_criteria (cr) \ + __print_symbolic(cr, \ + { CR0, "CR0" }, \ + { CR1, "CR1" }, \ + { CR2, "CR2" }, \ + { CR3, "CR3" }) + TRACE_EVENT(ext4_other_inode_update_time, TP_PROTO(struct inode *inode, ino_t orig_ino),
@@ -1063,7 +1075,7 @@ TRACE_EVENT(ext4_mballoc_alloc, ), TP_printk("dev %d,%d inode %lu orig %u/%d/%u@%u goal %u/%d/%u@%u " - "result %u/%d/%u@%u blks %u grps %u cr %u flags %s " + "result %u/%d/%u@%u blks %u grps %u cr %s flags %s " "tail %u broken %u", MAJOR(__entry->dev), MINOR(__entry->dev), (unsigned long) __entry->ino,
@@ -1073,7 +1085,7 @@ TRACE_EVENT(ext4_mballoc_alloc, __entry->goal_len, __entry->goal_logical, __entry->result_group, __entry->result_start, __entry->result_len, __entry->result_logical, - __entry->found, __entry->groups, __entry->cr, + __entry->found, __entry->groups,show_criteria (__entry->cr),show_mballoc_flags (__entry->flags), __entry->tail, __entry->buddy ? 1 << __entry->buddy : 0) );
Signature · 1 line
2.31.1
Ojaswin Mujoo
reviewerPATCH 6/13 ext4: Add per CR extent scanned counter
In reply to Ojaswin MujooThis 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.
--- 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
@@ -1553,6 +1553,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
@@ -2103,6 +2103,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
@@ -2277,6 +2278,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;
@@ -2390,6 +2392,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);
@@ -2926,6 +2929,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",
@@ -2935,6 +2939,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",
@@ -2944,6 +2949,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 ]));
@@ -2951,6 +2957,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));
@@ -4390,7 +4397,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
@@ -184,6 +184,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
Ojaswin Mujoo
reviewerPATCH 8/13 ext4: Avoid scanning smaller extents in BG during CR1
In reply to Ojaswin MujooWhen 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.
--- fs/ext4/mballoc.c | 19 ++++++++++++++++++- 1 file changed, 18 insertions(+), 1 deletion(-)
fs/ext4/mballoc.c +18 -1
@@ -2307,7 +2307,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;
@@ -2334,6 +2334,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
Ojaswin Mujoo
reviewerPATCH 7/13 ext4: Add counter to track successful allocation of goal length
In reply to Ojaswin MujooTrack 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.
--- fs/ext4/ext4.h | 1 + fs/ext4/mballoc.c | 3 +++ 2 files changed, 4 insertions(+)
fs/ext4/ext4.h +1 -0
@@ -1556,6 +1556,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
@@ -2962,6 +2962,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));
@@ -4407,6 +4408,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
Ojaswin Mujoo
reviewerPATCH 10/13 ext4: Ensure ext4_mb_prefetch_fini() is called for all prefetched BGs
In reply to Ojaswin MujooBefore 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.
--- fs/ext4/mballoc.c | 4 ---- fs/ext4/super.c | 11 ++++------- 2 files changed, 4 insertions(+), 11 deletions(-)
fs/ext4/mballoc.c +0 -4
@@ -2732,8 +2732,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;
@@ -2742,8 +2740,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
@@ -3694,16 +3694,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
Ojaswin Mujoo
reviewerPATCH 9/13 ext4: Don't skip prefetching BLOCK_UNINIT groups
In reply to Ojaswin MujooCurrently, 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.
--- fs/ext4/mballoc.c | 8 ++------ 1 file changed, 2 insertions(+), 6 deletions(-)
fs/ext4/mballoc.c +2 -6
@@ -2587,9 +2587,7 @@ ext4_group_t ext4_mb_prefetch(struct super_block *sb, ext4_group_t group,*/ if (gdp && grp && !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)
@@ -2630,9 +2628,7 @@ void ext4_mb_prefetch_fini(struct super_block *sb, ext4_group_t group, grp =ext4_get_group_info (sb, group);if (gdp && 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 ) {if (ext4_mb_init_group (sb, group,GFP_NOFS ))break ; }
Signature · 1 line
2.31.1
Ojaswin Mujoo
reviewerPATCH 11/13 ext4: Abstract out logic to search average fragment list
In reply to Ojaswin MujooMake 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.
--- fs/ext4/mballoc.c | 51 ++++++++++++++++++++++++++++++----------------- 1 file changed, 33 insertions(+), 18 deletions(-)
fs/ext4/mballoc.c +33 -18
@@ -904,6 +904,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.
@@ -912,7 +943,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 )) {
@@ -922,23 +953,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
Ojaswin Mujoo
reviewerPATCH 12/13 ext4: Add allocation criteria 1.5 (CR1_5)
In reply to Ojaswin MujooCR1_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.
ext4 squash
--- fs/ext4/ext4.h | 8 ++- fs/ext4/mballoc.c | 137 +++++++++++++++++++++++++++++++++--- fs/ext4/mballoc.h | 13 ++++ fs/ext4/sysfs.c | 2 + include/trace/events/ext4.h | 2 + 5 files changed, 151 insertions(+), 11 deletions(-)
fs/ext4/ext4.h +7 -1
@@ -133,13 +133,14 @@ enum SHIFT_DIRECTION {* 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 +#define EXT4_MB_NUM_CRS 5/* * All possible allocation criterias for mballoc */ enum criteria {CR0 ,CR1 , +CR1_5 ,CR2 ,CR3 , };
@@ -185,6 +186,9 @@ enum criteria {#define EXT4_MB_CR0_OPTIMIZED 0x8000/* Avg fragment size rb tree lookup succeeded at least once for cr = 1 */ #define EXT4_MB_CR1_OPTIMIZED 0x00010000 +/* Avg fragment size rb tree lookup succeeded at least once for cr = 1.5 */ +#define EXT4_MB_CR1_5_OPTIMIZED 0x00020000 +struct ext4_allocation_request {/* target inode for block we're allocating */ struct inode *inode;
@@ -1547,6 +1551,7 @@ struct ext4_sb_info {unsigned long s_mb_last_start;unsigned int s_mb_prefetch;unsigned int s_mb_prefetch_limit; +unsigned int s_mb_cr1_5_max_trim_order;/* stats for buddy allocator */ atomic_t s_bal_reqs;/* number of reqs with len > 1 */
@@ -1561,6 +1566,7 @@ struct ext4_sb_info {atomic_t s_bal_2orders;/* 2^order hits */ atomic_t s_bal_cr0_bad_suggestions;atomic_t s_bal_cr1_bad_suggestions; +atomic_t s_bal_cr1_5_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 */
fs/ext4/mballoc.c +127 -10
239 lines not on this page · raw message
fs/ext4/mballoc.h +13 -0
@@ -85,6 +85,13 @@*/ #define MB_DEFAULT_LINEAR_SCAN_THRESHOLD 16 +/* +* The maximum order upto which CR1.5 can trim a particular allocation request. +* Example, if we have an order 7 request and max trim order of 3, CR1.5 can +* trim this upto order 4. +*/ +#define MB_DEFAULT_CR1_5_TRIM_ORDER 3 +/* * Number of valid buddy orders */
@@ -179,6 +186,12 @@ struct ext4_allocation_context {/* copy of the best found extent taken before preallocation efforts */ struct ext4_free_extent ac_f_ex; +/* +* goal len can change in CR1.5, so save the original len. This is +* used while adjusting the PA window and for accounting. +*/ +ext4_grpblk_t ac_orig_goal_len; +__u32 ac_groups_considered;__u32 ac_flags;/* allocation hints */ __u16 ac_groups_scanned;
fs/ext4/sysfs.c +2 -0
@@ -223,6 +223,7 @@ EXT4_RW_ATTR_SBI_UI(warning_ratelimit_interval_ms, s_warning_ratelimit_state.intEXT4_RW_ATTR_SBI_UI (warning_ratelimit_burst, s_warning_ratelimit_state.burst);EXT4_RW_ATTR_SBI_UI (msg_ratelimit_interval_ms, s_msg_ratelimit_state.interval);EXT4_RW_ATTR_SBI_UI (msg_ratelimit_burst, s_msg_ratelimit_state.burst); +EXT4_RW_ATTR_SBI_UI (mb_cr1_5_max_trim_order, s_mb_cr1_5_max_trim_order);#ifdef CONFIG_EXT4_DEBUG EXT4_RW_ATTR_SBI_UL (simulate_fail, s_simulate_fail);#endif
@@ -273,6 +274,7 @@ static struct attribute *ext4_attrs[] = {ATTR_LIST (warning_ratelimit_burst),ATTR_LIST (msg_ratelimit_interval_ms),ATTR_LIST (msg_ratelimit_burst), +ATTR_LIST (mb_cr1_5_max_trim_order),ATTR_LIST (errors_count),ATTR_LIST (warning_count), ATTR_LIST(msg_count),
include/trace/events/ext4.h +2 -0
@@ -122,6 +122,7 @@ TRACE_DEFINE_ENUM(EXT4_FC_REASON_MAX);TRACE_DEFINE_ENUM (CR0 );TRACE_DEFINE_ENUM (CR1 ); +TRACE_DEFINE_ENUM (CR1_5 );TRACE_DEFINE_ENUM (CR2 );TRACE_DEFINE_ENUM (CR3 );
@@ -129,6 +130,7 @@ TRACE_DEFINE_ENUM(CR3); __print_symbolic(cr, \ { CR0, "CR0" }, \ { CR1, "CR1" }, \ + { CR1_5, "CR1.5" } \ { CR2, "CR2" }, \ { CR3, "CR3" })
Signature · 1 line
2.31.1
Ojaswin Mujoo
reviewerPATCH 13/13 ext4: Give symbolic names to mballoc criterias
In reply to Ojaswin Mujoomballoc criterias have historically been called by numbers like CR0, CR1... however this makes it confusing to understand what each criteria is about.
Change these criterias from numbers to symbolic names and add relevant comments. While we are at it, also reformat and add some comments to ext4_seq_mb_stats_show() for better readability.
Additionally, define CR_FAST which signifies the criteria below which we can make quicker decisions like:
* quitting early if (free block < requested len)
* avoiding to scan free extents smaller than required len.
* avoiding to initialize buddy cache and work with existing cache
* limiting prefetches
--- fs/ext4/ext4.h | 55 ++++++-- fs/ext4/mballoc.c | 269 ++++++++++++++++++++---------------- fs/ext4/mballoc.h | 8 +- fs/ext4/sysfs.c | 4 +- include/trace/events/ext4.h | 26 ++-- 5 files changed, 212 insertions(+), 150 deletions(-)
fs/ext4/ext4.h +42 -13
@@ -135,16 +135,45 @@ enum SHIFT_DIRECTION {*/ #define EXT4_MB_NUM_CRS 5/* -* All possible allocation criterias for mballoc +* All possible allocation criterias for mballoc. Lower are faster. */ enum criteria { -CR0 , -CR1 , -CR1_5 , -CR2 , -CR3 , +/* +* Used when number of blocks needed is a power of 2. This doesn't +* trigger any disk IO except prefetch and is the fastest criteria. +*/ +CR_POWER2_ALIGNED , + +/* +* Tries to lookup in-memory data structures to find the most suitable +* group that satisfies goal request. No disk IO except block prefetch. +*/ +CR_GOAL_LEN_FAST , + +/* +* Same as CR_GOAL_LEN_FAST but is allowed to reduce the goal length to +* the best available length for faster allocation. +*/ +CR_BEST_AVAIL_LEN , + +/* +* Reads each block group sequentially, performing disk IO if necessary, to +* find find_suitable block group. Tries to allocate goal length but might trim +* the request if nothing is found after enough tries. +*/ +CR_GOAL_LEN_SLOW , + +/* +* Finds the first free set of blocks and allocates those. This is only +* used in rare cases when CR_GOAL_LEN_SLOW also fails to allocate +* anything. +*/ +CR_ANY_FREE , }; +/* criteria below which we use fast block scanning and avoid unnecessary IO */ +#define CR_FAST CR_GOAL_LEN_SLOW +/* * Flags used in mballoc's allocation_context flags field. *
@@ -183,11 +212,11 @@ enum criteria {/* 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 */ -#define EXT4_MB_CR0_OPTIMIZED 0x8000 +#define EXT4_MB_CR_POWER2_ALIGNED_OPTIMIZED 0x8000/* Avg fragment size rb tree lookup succeeded at least once for cr = 1 */ -#define EXT4_MB_CR1_OPTIMIZED 0x00010000 +#define EXT4_MB_CR_GOAL_LEN_FAST_OPTIMIZED 0x00010000/* Avg fragment size rb tree lookup succeeded at least once for cr = 1.5 */ -#define EXT4_MB_CR1_5_OPTIMIZED 0x00020000 +#define EXT4_MB_CR_BEST_AVAIL_LEN_OPTIMIZED 0x00020000struct ext4_allocation_request {/* target inode for block we're allocating */
@@ -1551,7 +1580,7 @@ struct ext4_sb_info {unsigned long s_mb_last_start;unsigned int s_mb_prefetch;unsigned int s_mb_prefetch_limit; -unsigned int s_mb_cr1_5_max_trim_order; +unsigned int s_mb_best_avail_max_trim_order;/* stats for buddy allocator */ atomic_t s_bal_reqs;/* number of reqs with len > 1 */
@@ -1564,9 +1593,9 @@ struct ext4_sb_info {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; -atomic_t s_bal_cr1_bad_suggestions; -atomic_t s_bal_cr1_5_bad_suggestions; +atomic_t s_bal_p2_aligned_bad_suggestions; +atomic_t s_bal_goal_fast_bad_suggestions; +atomic_t s_bal_best_avail_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 */
fs/ext4/mballoc.c +151 -118
496 lines not on this page · raw message
fs/ext4/mballoc.h +4 -4
@@ -86,11 +86,11 @@#define MB_DEFAULT_LINEAR_SCAN_THRESHOLD 16/* -* The maximum order upto which CR1.5 can trim a particular allocation request. -* Example, if we have an order 7 request and max trim order of 3, CR1.5 can -* trim this upto order 4. +* The maximum order upto which CR_BEST_AVAIL_LEN can trim a particular +* allocation request. Example, if we have an order 7 request and max trim order +* of 3, we can trim this request upto order 4. */ -#define MB_DEFAULT_CR1_5_TRIM_ORDER 3 +#define MB_DEFAULT_BEST_AVAIL_TRIM_ORDER 3/* * Number of valid buddy orders
fs/ext4/sysfs.c +2 -2
@@ -223,7 +223,7 @@ EXT4_RW_ATTR_SBI_UI(warning_ratelimit_interval_ms, s_warning_ratelimit_state.intEXT4_RW_ATTR_SBI_UI (warning_ratelimit_burst, s_warning_ratelimit_state.burst);EXT4_RW_ATTR_SBI_UI (msg_ratelimit_interval_ms, s_msg_ratelimit_state.interval);EXT4_RW_ATTR_SBI_UI (msg_ratelimit_burst, s_msg_ratelimit_state.burst); -EXT4_RW_ATTR_SBI_UI (mb_cr1_5_max_trim_order, s_mb_cr1_5_max_trim_order); +EXT4_RW_ATTR_SBI_UI (mb_best_avail_max_trim_order, s_mb_best_avail_max_trim_order);#ifdef CONFIG_EXT4_DEBUG EXT4_RW_ATTR_SBI_UL (simulate_fail, s_simulate_fail);#endif
@@ -274,7 +274,7 @@ static struct attribute *ext4_attrs[] = {ATTR_LIST (warning_ratelimit_burst),ATTR_LIST (msg_ratelimit_interval_ms),ATTR_LIST (msg_ratelimit_burst), -ATTR_LIST (mb_cr1_5_max_trim_order), +ATTR_LIST (mb_best_avail_max_trim_order),ATTR_LIST (errors_count),ATTR_LIST (warning_count), ATTR_LIST(msg_count),
include/trace/events/ext4.h +13 -13
@@ -120,19 +120,19 @@ TRACE_DEFINE_ENUM(EXT4_FC_REASON_MAX); { EXT4_FC_REASON_INODE_JOURNAL_DATA, "INODE_JOURNAL_DATA"}, \ { EXT4_FC_REASON_ENCRYPTED_FILENAME, "ENCRYPTED_FILENAME"}) -TRACE_DEFINE_ENUM (CR0 ); -TRACE_DEFINE_ENUM (CR1 ); -TRACE_DEFINE_ENUM (CR1_5 ); -TRACE_DEFINE_ENUM (CR2 ); -TRACE_DEFINE_ENUM (CR3 ); - -#define show_criteria (cr) \ - __print_symbolic(cr, \ - { CR0, "CR0" }, \ - { CR1, "CR1" }, \ - { CR1_5, "CR1.5" } \ - { CR2, "CR2" }, \ - { CR3, "CR3" }) +TRACE_DEFINE_ENUM (CR_POWER2_ALIGNED ); +TRACE_DEFINE_ENUM (CR_GOAL_LEN_FAST ); +TRACE_DEFINE_ENUM (CR_BEST_AVAIL_LEN ); +TRACE_DEFINE_ENUM (CR_GOAL_LEN_SLOW ); +TRACE_DEFINE_ENUM (CR_ANY_FREE ); + +#define show_criteria (cr) \ + __print_symbolic(cr, \ + { CR_POWER2_ALIGNED, "CR_POWER2_ALIGNED" }, \ + { CR_GOAL_LEN_FAST, "CR_GOAL_LEN_FAST" }, \ + { CR_BEST_AVAIL_LEN, "CR_BEST_AVAIL_LEN" }, \ + { CR_GOAL_LEN_SLOW, "CR_GOAL_LEN_SLOW" }, \ + { CR_ANY_FREE, "CR_ANY_FREE" }) TRACE_EVENT(ext4_other_inode_update_time, TP_PROTO(struct inode *inode, ino_t orig_ino),
Signature · 1 line
2.31.1
Ojaswin Mujoo
reviewerPATCH 3/13 ext4: Remove unused extern variables declaration
In reply to Ojaswin MujooFrom: "Ritesh Harjani (IBM)" <[email protected]>
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.
--- fs/ext4/ext4.h | 2 -- fs/ext4/mballoc.h | 2 +- 2 files changed, 1 insertion(+), 3 deletions(-)
fs/ext4/ext4.h +0 -2
@@ -2815,8 +2815,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
@@ -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
Re: [PATCH 01/13] Revert "ext4: remove ac->ac_found > sbi->s_mb_min_to_scan dead check in ext4_mb_check_limits"
In reply to Ojaswin MujooQuoted 60 lines · Ojaswin Mujoo
This reverts commit
32c0869370194ae5ac9f9f501953ef693040f6a1.The reverted commit was intended to remove a dead check however it was observed that this check was actually being used to exit early instead of looping
sbi->s_mb_max_to_scantimes when we are able to find a free extent bigger than the goal extent. Due to this, a my performance tests (fsmark, parallel file writes in a highly fragmented FS) were seeing a 2x-3x regression.Example, the default value of the following variables is:
sbi->s_mb_max_to_scan= 200sbi->s_mb_min_to_scan= 10In
ext4_mb_check_limits()if we find an extent smaller than goal, then we return early and try again. This loop will go on until we have processedsbi->s_mb_max_to_scan(=200)number of free extents at which point we exit and just use whatever we have even if it is smaller than goal extent.Now, the regression comes when we find an extent bigger than goal. Earlier, in this case we would loop only
sbi->s_mb_min_to_scan(=10)times and then just use the bigger extent. However with commit32c08693that check was removed and hence we would loopsbi->s_mb_max_to_scan(=200)times even though we have a big enough free extent to satisfy the request. The only time we would exit early would be when the free extent is *exactly* the size of our goal, which is pretty uncommon occurrence and so we would almost always end up looping 200 times.Hence, revert the commit by adding the check back to fix the regression. Also add a comment to outline this policy.
Signed-off-by Ojaswin Mujoo <[email protected]>Reviewed-by Ritesh Harjani (IBM) <[email protected]>--- fs/ext4/mballoc.c | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-)fs/ext4/mballoc.c +8
-1@@ -2062,7 +2062,7 @@ static void ext4_mb_check_limits(struct ext4_allocation_context *ac,if (bex->fe_len < gex->fe_len)return ; -if (finish_group) +if (finish_group || ac->ac_found > sbi->s_mb_min_to_scan)ext4_mb_use_best_found (ac, e4b); }@@ -2074,6 +2074,20 @@ static void ext4_mb_check_limits(struct ext4_allocation_context *ac,* in the context. Later, the best found extent will be used, if * mballoc can't find good enough extent. * +* The algorithm used is roughly as follows: +* +* * If free extent found is exactly as big as goal, then +* stop the scan and use it immediately +* +* * If free extent found is smaller than goal, then keep retrying +* upto a max of sbi->s_mb_max_to_scan times (default 200). After
fs/ext4/mballoc.c static void ext4_mb_check_limits(struct ext4_allocation_context *ac, · line 2093
Quoted 10 lines
fs/ext4/mballoc.c +7
-0+* that stop scanning and use whatever we have. +* +* * If free extent found is bigger than goal, then keep retrying +* upto a max of sbi->s_mb_min_to_scan times (default 10) before +* stopping the scan and using the extent. +* +* * FIXME: real allocation policy is to be designed yet! */ static void ext4_mb_measure_extent(struct ext4_allocation_context *ac,
My bad, it seems that I mixed up with s_mb_min_to_scan and s_mb_max_to_scan in previous patch which will make s_mb_min_to_scan not work. Thanks for the fix. It looks goot to me. Feel free to add my first reviewed-by :)
Signature · 2 lines
Best wishes Kemeng Shi
Re: [PATCH 01/13] Revert "ext4: remove ac->ac_found > sbi->s_mb_min_to_scan dead check in ext4_mb_check_limits"
In reply to Ojaswin Mujoo[CCing the regression list, as it should be in the loop for regressions:
https://docs.kernel.org/admin-guide/reporting-regressions.html]
[TLDR: I'm adding this report to the list of tracked Linux kernel regressions; the text you find below is based on a few templates paragraphs you might have encountered already in similar form. See link in footer if these mails annoy you.]
Quoted 26 lines · Ojaswin Mujoo
This reverts commit
32c0869370194ae5ac9f9f501953ef693040f6a1.The reverted commit was intended to remove a dead check however it was observed that this check was actually being used to exit early instead of looping
sbi->s_mb_max_to_scantimes when we are able to find a free extent bigger than the goal extent. Due to this, a my performance tests (fsmark, parallel file writes in a highly fragmented FS) were seeing a 2x-3x regression.Example, the default value of the following variables is:
sbi->s_mb_max_to_scan= 200sbi->s_mb_min_to_scan= 10In
ext4_mb_check_limits()if we find an extent smaller than goal, then we return early and try again. This loop will go on until we have processedsbi->s_mb_max_to_scan(=200)number of free extents at which point we exit and just use whatever we have even if it is smaller than goal extent.Now, the regression comes when we find an extent bigger than goal. Earlier, in this case we would loop only
sbi->s_mb_min_to_scan(=10)times and then just use the bigger extent. However with commit32c08693that check was removed and hence we would loopsbi->s_mb_max_to_scan(=200)times even though we have a big enough free extent to satisfy the request. The only time we would exit early would be when the free extent is *exactly* the size of our goal, which is pretty uncommon occurrence and so we would almost always end up looping 200 times.
Quoted 6 lines
Hence, revert the commit by adding the check back to fix the regression. Also add a comment to outline this policy.
Signed-off-by Ojaswin Mujoo <[email protected]>Reviewed-by Ritesh Harjani (IBM) <[email protected]>[...]
Thanks for the report. To be sure the issue doesn't fall through the cracks unnoticed, I'm adding it to regzbot, the Linux kernel regression tracking bot:
#regzbot ^introduced 32c0869370194ae5ac
#regzbot title ext4: 2x-3x regression in performance tests #regzbot monitor:
https://lore.kernel.org/all/ddcae9658e46880dfec2fb0aa61d01fb3353d202.1685449706.git.ojaswin@linux.ibm.com/
#regzbot fix: Revert "ext4: remove ac->ac_found > sbi->s_mb_min_to_scan dead check in ext4_mb_check_limits"
#regzbot ignore-activity
This isn't a regression? This issue or a fix for it are already discussed somewhere else? It was fixed already? You want to clarify when the regression started to happen? Or point out I got the title or something else totally wrong? Then just reply and tell me -- ideally while also telling regzbot about it, as explained by the page listed in the footer of this mail.
Developers: When fixing the issue, remember to add 'Link:' tags pointing to the report (the parent of this mail). See page linked in footer for details.
Ciao, Thorsten (wearing his 'the Linux kernel's regression tracker' hat) --
Everything you wanna know about Linux kernel regression tracking:
https://linux-regtracking.leemhuis.info/about/#tldr
That page also explains what to do if mails like this annoy you.