mm: multi-gen LRU: reduce memcg rotation overhead
Subsystems (5)
v3 cover mm: multi-gen LRU: reduce memcg rotation overhead
This series addresses excessive time spent rotating memcgs during MGLRU reclaim on systems with a large number of memcgs.
On some servers with tens of thousands of cgroups, we had repeated soft lockups and RCU stalls:
rcu: INFO: rcu_sched self-detected stall on CPU rcu: 60-...!: (1118 ticks this GP) idle=ca74/1/0x4000000000000000 softirq=140067260/140067260 fqs=10 rcu: (t=2101 jiffies g=180256409 q=94266 ncpus=96) rcu: rcu_sched kthread starved for 2073 jiffies! g180256409 f0x2 RCU_GP_WAIT_FQS(5) ->state=0x0 ->cpu=53 rcu: Unless rcu_sched kthread gets sufficient CPU time, OOM is now expected behavior. rcu: RCU grace-period kthread stack dump: task:rcu_sched state:R running task stack:0 pid:15 tgid:15 ppid:2 task_flags:0x208040 flags:0x00000010 Call trace: __switch_to+0xc4/0x108 (T) __schedule+0x2b4/0x978 schedule+0x2c/0xc0 schedule_timeout+0x7c/0x110 rcu_gp_fqs_loop+0xec/0x4e8 rcu_gp_kthread+0x12c/0x160 kthread+0x118/0x1e0 ret_from_fork+0x10/0x20 rcu: Stack dump where RCU GP kthread last ran: Sending NMI from CPU 60 to CPUs 53: NMI backtrace for cpu 53 CPU: 53 UID: 3758108211 PID: 4052395 Comm: php-cgi8.3 Tainted: G W L 6.18.52-i1-ampere #1203 NONE Tainted: [W]=WARN, [L]=SOFTLOCKUP Hardware name: Supermicro ARS-110M-NR/R12SPD-A, BIOS 1.1b 10/17/2023 pstate: 40400009 (nZcv daif +PAN -UAO -TCO -DIT -SSBS BTYPE=--) pc : handle_softirqs+0xa4/0x2e8 lr : __do_softirq+0x18/0x20 [...] Call trace: handle_softirqs+0xa4/0x2e8 (P) __do_softirq+0x18/0x20 ____do_softirq+0x14/0x28 call_on_irq_stack+0x30/0x48 do_softirq_own_stack+0x20/0x38 __irq_exit_rcu+0xc0/0x100 irq_exit_rcu+0x14/0x28 el1_interrupt+0x3c/0x58 el1h_64_irq_handler+0x14/0x20 el1h_64_irq+0x6c/0x70 lru_gen_rotate_memcg+0x210/0x280 (P) shrink_node+0xb14/0xcc8 do_try_to_free_pages+0xd0/0x508 try_to_free_pages+0x11c/0x230 __alloc_frozen_pages_noprof+0x4f8/0xe00 get_free_pages_noprof+0x20/0x60 ceph_alloc_readdir_reply_buffer+0xa4/0x160 ceph_readdir+0x248/0xeb0 wrap_directory_iterator+0x54/0x88 shared_ceph_readdir+0x1c/0x28
The problem was lru_gen_rotate_memcg(). Its memcg tail insertion walked the destination bin while holding the per-node memcg_lru.lock with interrupts disabled. With so many cgroups, the lock duration grew too long and thousands of concurrent reclaimers were contending for the spinlock all the time.
Reclaim can also repeatedly promote memcgs that are already in the young generation, and scans of empty or protected memcgs can bypass the rescheduling points in page reclaim.
This patch set contains three parts:
The first 3 patches add a cache for each bin's tail to make tail insertion constant time.
The fourth patch skips redundant YOUNG rotations when the memcg is already in the default segment of the current young generation.
The last patch adds rescheduling points between memcg reclaim attempts and at bin/retry boundaries to avoid potential remaining soft lockups under extreme pressure.
I ran a micro benchmark on branch 6.18 on a 12-core Xeon 5118: 8 concurrent workers repeatedly write 1024M swappiness=0 to the root cgroup's memory.reclaim for 60 seconds, against a previously prepared set of 1500 memory cgroups. Each worker issues its next request when the previous one returns. The test measures request throughput and latency under concurrent MGLRU reclaim. All requests returned EAGAIN, indicating that the requested reclaim target was not met; the reported throughput counts completed reclaim attempts, not reclaimed bytes.
Results:
Requests/sec Mean latency Maximum latency
Unpatched 4.56 1739.85 ms 4083.55 ms
Patches 1-3 43.42 183.53 ms 393.15 ms Patches 1-4 59.22 134.03 ms 393.44 ms Patches 1-5 57.80 137.63 ms 412.72 ms
Constant-time insertion increases request throughput by 9.5x. Avoiding redundant YOUNG rotations adds another 36.4%. The full patch series improves the unpatched throughput by a factor of 12.7.
All requests returned EAGAIN. These results measure reclaim attempts that did not meet their requested target.
I did not measure scheduling-latency improvements of the last patch.
This series is very similar to an earlier patch by Chen Ridong which I was not aware of at the time of writing:
https://lore.kernel.org/all/[email protected]/
---v1->v2: rebase after MEMCG_LRU_HEAD was removed by d5d1712c5928
("memcg: remove lru_gen_soft_reclaim()")v2->v3:
- rebase on mm-new (MEMCG_LRU_OLD removed, too)
- mention Chen Ridong's earlier patch
- defer the get_random_u32_below() call until it's really needed (suggested by Barry Song)
- rename hlist_nulls_add_behind_rcu() to hlist_nulls_add_behind_last_rcu() to avoid confusion about the function semantics
Max Kellermann (5):
include/linux/rculist_nulls: add hlist_nulls_add_behind_rcu() mm/vmscan: move code to lru_gen_{add,del}_memcg() mm/mglru: cache the last memcg node, make tail insertion constant time mm/mglru: avoid redundant rotations of young memcgs mm/mglru: reschedule between memcg reclaim attempts
include/linux/mmzone.h | 4 ++ include/linux/rculist_nulls.h | 36 +++++++++++++++--- mm/vmscan.c | 71 ++++++++++++++++++++++++++++++++--- 3 files changed, 99 insertions(+), 12 deletions(-)
Signature · 1 line
2.53.0
PATCH v3 1/5 include/linux/rculist_nulls: add hlist_nulls_add_behind_rcu()
Move some code from hlist_nulls_add_tail_rcu() to the new function hlist_nulls_add_behind_rcu() for callers that already know the last node of an hlist_nulls list, to allow constant-time appends.
--- include/linux/rculist_nulls.h | 36 +++++++++++++++++++++++++++++------ 1 file changed, 30 insertions(+), 6 deletions(-)
include/linux/rculist_nulls.h +30 -6
@@ -115,6 +115,33 @@ static inline void hlist_nulls_add_head_rcu(struct hlist_nulls_node *n,WRITE_ONCE (first->pprev, &n->next); } +/** +* hlist_nulls_add_behind_last_rcu - append after the last list entry +* @n: the new element to add to the hash list. +* @last: the last element in the list. +* +* Adds the specified element after @last while permitting racing RCU +* traversals. @last must be the last list entry, with its next +* pointer holding the terminating nulls marker. +* +* The caller must take whatever precautions are necessary +* (such as holding appropriate locks) to avoid racing +* with another list-mutation primitive, such as hlist_nulls_add_head_rcu() +* or hlist_nulls_del_rcu(), running on this same list. +* However, it is perfectly legal to run concurrently with +* the _rcu list-traversal primitives, such as +* hlist_nulls_for_each_entry_rcu(), used to prevent memory-consistency +* problems on Alpha CPUs. Regardless of the type of CPU, the +* list-traversal primitive must be guarded by rcu_read_lock(). +*/ +static inline void hlist_nulls_add_behind_last_rcu (struct hlist_nulls_node *n, +struct hlist_nulls_node *last) +{ +WRITE_ONCE (n->next, last->next); +WRITE_ONCE (n->pprev, &last->next); +rcu_assign_pointer (hlist_nulls_next_rcu (last), n); +} +/** * hlist_nulls_add_tail_rcu * @n: the element to add to the hash list.
@@ -143,13 +170,10 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,for (i = h->first; !is_a_nulls (i); i = i->next) last = i; -if (last) { -WRITE_ONCE (n->next, last->next); -WRITE_ONCE (n->pprev, &last->next); -rcu_assign_pointer (hlist_nulls_next_rcu (last), n); - }else { +if (last) +hlist_nulls_add_behind_last_rcu (n, last); +else hlist_nulls_add_head_rcu (n, h); - } }/* after that hlist_nulls_del will work */
Signature · 1 line
2.53.0
[email protected]
AI reviewRe: [PATCH v3 1/5] include/linux/rculist_nulls: add hlist_nulls_add_behind_rcu()
Thank you for your contribution! Sashiko AI review found 1 potential issue to consider: - [Low] rculist_nulls: commit message mismatches hlist_nulls_add_behind_last_rcu() --
Thank you for your contribution! Sashiko AI review found 1 potential issue to consider:
- [Low] rculist_nulls: commit message mismatches hlist_nulls_add_behind_last_rcu()
--
commit 8be860a8b1d9e4863e4165df073c841c355f9d25
Author: Max Kellermann <[email protected]>
Quoted 7 lines
include/linux/rculist_nulls: addhlist_nulls_add_behind_rcu()Move some code from
hlist_nulls_add_tail_rcu()to the new functionhlist_nulls_add_behind_rcu()for callers that already know the last node of anhlist_nullslist, to allow constant-time appends.Signed-off-by Max Kellermann <[email protected]>
[Severity: Low]
The commit subject and message refer to hlist_nulls_add_behind_rcu(), whereas the helper added by the patch is named hlist_nulls_add_behind_last_rcu().
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
PATCH v3 2/5 mm/vmscan: move code to lru_gen_{add,del}_memcg()
In reply to Max KellermannPreparation for the following patch that adds tail caching.
For simplicity, hlist_nulls_del_init_rcu() is now always used, which is also valid during rotation, because the entry is immediately reinserted under memcg_lru.lock.
--- mm/vmscan.c | 28 ++++++++++++++++++++++++---- 1 file changed, 24 insertions(+), 4 deletions(-)
mm/vmscan.c +24 -4
@@ -4429,6 +4429,26 @@ enum { MEMCG_LRU_YOUNG, }; +static void lru_gen_add_memcg (struct lru_gen_memcg *memcg_lru, +struct lru_gen_folio *lrugen, +int gen,int bin) +{ +struct hlist_nulls_head *head = &memcg_lru->fifo[gen][bin]; + +lockdep_assert_held (&memcg_lru->lock); + +hlist_nulls_add_tail_rcu (&lrugen->list, head); +} + +static void lru_gen_del_memcg (struct lru_gen_memcg *memcg_lru, +struct lru_gen_folio *lrugen, +int gen) +{ +lockdep_assert_held (&memcg_lru->lock); + +hlist_nulls_del_init_rcu (&lrugen->list); +} +static void lru_gen_rotate_memcg (struct lruvec *lruvec,int op) {int seg;
@@ -4455,8 +4475,8 @@ static void lru_gen_rotate_memcg(struct lruvec *lruvec, int op)WRITE_ONCE (lruvec->lrugen.seg, seg);WRITE_ONCE (lruvec->lrugen.gen, new); -hlist_nulls_del_rcu (&lruvec->lrugen.list); -hlist_nulls_add_tail_rcu (&lruvec->lrugen.list, &pgdat->memcg_lru.fifo[new][bin]); +lru_gen_del_memcg (&pgdat->memcg_lru, &lruvec->lrugen, old); +lru_gen_add_memcg (&pgdat->memcg_lru, &lruvec->lrugen, new, bin); pgdat->memcg_lru.nr_memcgs[old]--; pgdat->memcg_lru.nr_memcgs[new]++;
@@ -4487,7 +4507,7 @@ void lru_gen_online_memcg(struct mem_cgroup *memcg) lruvec->lrugen.gen = gen; -hlist_nulls_add_tail_rcu (&lruvec->lrugen.list, &pgdat->memcg_lru.fifo[gen][bin]); +lru_gen_add_memcg (&pgdat->memcg_lru, &lruvec->lrugen, gen, bin); pgdat->memcg_lru.nr_memcgs[gen]++;spin_unlock_irq (&pgdat->memcg_lru.lock);
@@ -4510,7 +4530,7 @@ void lru_gen_release_memcg(struct mem_cgroup *memcg) gen = lruvec->lrugen.gen; -hlist_nulls_del_init_rcu (&lruvec->lrugen.list); +lru_gen_del_memcg (&pgdat->memcg_lru, &lruvec->lrugen, gen); pgdat->memcg_lru.nr_memcgs[gen]--;if (!pgdat->memcg_lru.nr_memcgs[gen] && gen ==get_memcg_gen (pgdat->memcg_lru.seq))
Signature · 1 line
2.53.0
PATCH v3 3/5 mm/mglru: cache the last memcg node, make tail insertion constant time
In reply to Max KellermannRotating or onlining a memcg currently uses hlist_nulls_add_tail_rcu() which walks the destination bin to find its tail while holding memcg_lru.lock with interrupts disabled. With thousands of cgroups, this takes a long time and causes severe lock contention.
Cache a pointer to each bin's last node, making tail insertion O(1). This requires remembering the bin number (but the new struct field occupies a hole, so it does not grow).
In a micro benchmark that creates 1500 cgroups and repeatedly writes 1024M swappiness=0 to memory.reclaim in 8 threads, the request rate increases by a factor of 9.5 and the average duration of each write request is reduced by 89%.
All writes return EAGAIN in both runs; the benchmark measures the cost of reclaim attempts that cannot meet their requested target, not reclaimed throughput.
--- include/linux/mmzone.h | 4 ++++ mm/vmscan.c | 24 ++++++++++++++++++++++-- 2 files changed, 26 insertions(+), 2 deletions(-)
include/linux/mmzone.h +4 -0
@@ -570,6 +570,8 @@ struct lru_gen_folio {u8 gen;/* the list segment this lru_gen_folio belongs to */ u8 seg; +/* the memcg bin, protected by memcg_lru.lock */ +u8 bin;/* per-node lru_gen_folio list for global reclaim */ struct hlist_nulls_node list; };
@@ -661,6 +663,8 @@ struct lru_gen_memcg {unsigned long nr_memcgs[MEMCG_NR_GENS ];/* per-node lru_gen_folio list for global reclaim */ struct hlist_nulls_head fifo[MEMCG_NR_GENS ][MEMCG_NR_BINS ]; +/* last entry in each bin, or NULL if empty */ +struct hlist_nulls_node *tail[MEMCG_NR_GENS ][MEMCG_NR_BINS ];/* protects the above */ spinlock_t lock; };
mm/vmscan.c +22 -2
@@ -4434,18 +4434,36 @@ static void lru_gen_add_memcg(struct lru_gen_memcg *memcg_lru, int gen, int bin) {struct hlist_nulls_head *head = &memcg_lru->fifo[gen][bin]; +struct hlist_nulls_node *last = memcg_lru->tail[gen][bin];lockdep_assert_held (&memcg_lru->lock); -hlist_nulls_add_tail_rcu (&lrugen->list, head); + lrugen->bin = bin; + +if (!last) +hlist_nulls_add_head_rcu (&lrugen->list, head); +else +hlist_nulls_add_behind_last_rcu (&lrugen->list, last); + + memcg_lru->tail[gen][bin] = &lrugen->list; }static void lru_gen_del_memcg (struct lru_gen_memcg *memcg_lru,struct lru_gen_folio *lrugen,int gen) { +const int bin = lrugen->bin; +struct hlist_nulls_head *head = &memcg_lru->fifo[gen][bin]; +lockdep_assert_held (&memcg_lru->lock); +/* pprev points to head->first for the only entry, otherwise prev->next. */ +if (memcg_lru->tail[gen][bin] == &lrugen->list) + memcg_lru->tail[gen][bin] = lrugen->list.pprev == &head->first + ?NULL + : container_of(lrugen->list.pprev, struct hlist_nulls_node, next); + +/* Keep next intact for readers that still hold this entry. */ hlist_nulls_del_init_rcu (&lrugen->list); }
@@ -6106,8 +6124,10 @@ void lru_gen_init_pgdat(struct pglist_data *pgdat)spin_lock_init (&pgdat->memcg_lru.lock);for (i =0 ; i <MEMCG_NR_GENS ; i++) { -for (j =0 ; j <MEMCG_NR_BINS ; j++) +for (j =0 ; j <MEMCG_NR_BINS ; j++) {INIT_HLIST_NULLS_HEAD (&pgdat->memcg_lru.fifo[i][j], i); + pgdat->memcg_lru.tail[i][j] =NULL ; + } } }
Signature · 1 line
2.53.0
PATCH v3 4/5 mm/mglru: avoid redundant rotations of young memcgs
In reply to Max KellermannConcurrent reclaimers can request promotion after another reclaimer has already moved a memcg into the young generation. Requeueing it into a random bin again adds list mutations without advancing the old-generation scan.
Therefore, skip MEMCG_LRU_YOUNG when the memcg is already in the default segment of the current young generation.
In my micro benchmark, this increases the request rate by 36% and reduces the average duration of each write request by 27%.
--- mm/vmscan.c | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-)
mm/vmscan.c +10 -2
@@ -4472,7 +4472,6 @@ static void lru_gen_rotate_memcg(struct lruvec *lruvec, int op)int seg;int old, new;unsigned long flags; -int bin =get_random_u32_below (MEMCG_NR_BINS );struct pglist_data *pgdat =lruvec_pgdat (lruvec);spin_lock_irqsave (&pgdat->memcg_lru.lock, flags);
@@ -4490,11 +4489,19 @@ static void lru_gen_rotate_memcg(struct lruvec *lruvec, int op)else VM_WARN_ON_ONCE (true); +if (op ==MEMCG_LRU_YOUNG && old == new && lruvec->lrugen.seg == seg) +/* +* This memcg is already in the young generation and +* reshuffling it again cannot help the scan of the +* old generation. +*/ + goto unlock; +WRITE_ONCE (lruvec->lrugen.seg, seg);WRITE_ONCE (lruvec->lrugen.gen, new);lru_gen_del_memcg (&pgdat->memcg_lru, &lruvec->lrugen, old); -lru_gen_add_memcg (&pgdat->memcg_lru, &lruvec->lrugen, new, bin); +lru_gen_add_memcg (&pgdat->memcg_lru, &lruvec->lrugen, new,get_random_u32_below (MEMCG_NR_BINS )); pgdat->memcg_lru.nr_memcgs[old]--; pgdat->memcg_lru.nr_memcgs[new]++;
@@ -4502,6 +4509,7 @@ static void lru_gen_rotate_memcg(struct lruvec *lruvec, int op)if (!pgdat->memcg_lru.nr_memcgs[old] && old ==get_memcg_gen (pgdat->memcg_lru.seq))WRITE_ONCE (pgdat->memcg_lru.seq, pgdat->memcg_lru.seq +1 ); +unlock:spin_unlock_irqrestore (&pgdat->memcg_lru.lock, flags); }
Signature · 1 line
2.53.0
PATCH v3 5/5 mm/mglru: reschedule between memcg reclaim attempts
In reply to Max Kellermannshrink_one() can return immediately for empty or protected memcgs, and try_to_shrink_lruvec() can break out before reaching its cond_resched(). A scan through many memcgs can repeatedly rotate entries without giving other runnable tasks a scheduling opportunity.
Call cond_resched_tasks_rcu_qs() (as the existing shrink_lruvec() loop does) after shrink_one(), while the memcg reference still pins the cursor and before reacquiring the RCU read lock. Also call it between bins and nulls-marker retries, covering scans that skip every entry.
--- mm/vmscan.c | 11 +++++++++++ 1 file changed, 11 insertions(+)
mm/vmscan.c +11 -0
@@ -5400,6 +5400,9 @@ static void shrink_many(struct pglist_data *pgdat, struct scan_control *sc) gen =get_memcg_gen (READ_ONCE (pgdat->memcg_lru.seq)); bin = first_bin =get_random_u32_below (MEMCG_NR_BINS ); restart: +/* Yield between bins/retries that contain only skipped entries. */ +cond_resched_tasks_rcu_qs (); + op =0 ; memcg =NULL ;
@@ -5430,6 +5433,14 @@ static void shrink_many(struct pglist_data *pgdat, struct scan_control *sc) op =shrink_one (lruvec, sc); +/* +* Empty or protected memcgs can bypass the +* rescheduling points in page reclaim. The memcg +* reference pins our cursor while we yield outside +* the RCU read-side critical section. +*/ +cond_resched_tasks_rcu_qs (); +rcu_read_lock ();if (should_abort_scan (lruvec, sc))
Signature · 1 line
2.53.0