* [PATCH 1/5] include/linux/rculist_nulls: add hlist_nulls_add_behind_rcu()
2026-10-12 20:54 [PATCH 0/5] mm: multi-gen LRU: reduce memcg rotation overhead Max Kellermann
@ 2026-10-12 20:54 ` Max Kellermann
2026-10-12 20:54 ` [PATCH 2/5] mm/vmscan: move code to lru_gen_{add,del}_memcg() Max Kellermann
` (3 subsequent siblings)
4 siblings, 0 replies; 6+ messages in thread
From: Max Kellermann @ 2026-10-12 20:54 UTC (permalink / raw)
To: akpm, kasong, qi.zheng, shakeel.butt, baohua, axelrasmussen,
yuanchu, weixugc, baoquan.he, baolin.wang, david, ljs, liam,
vbabka, rppt, surenb, mhocko, hannes, linux-mm, linux-kernel,
rcu
Cc: Max Kellermann
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.
Signed-off-by: Max Kellermann <max.kellermann@ionos.com>
---
include/linux/rculist_nulls.h | 36 +++++++++++++++++++++++++++++------
1 file changed, 30 insertions(+), 6 deletions(-)
diff --git a/include/linux/rculist_nulls.h b/include/linux/rculist_nulls.h
index a97c3bcb1656..054e477dd093 100644
--- a/include/linux/rculist_nulls.h
+++ b/include/linux/rculist_nulls.h
@@ -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_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_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_rcu(n, last);
+ else
hlist_nulls_add_head_rcu(n, h);
- }
}
/* after that hlist_nulls_del will work */
--
2.47.3
^ permalink raw reply [flat|nested] 6+ messages in thread* [PATCH 2/5] mm/vmscan: move code to lru_gen_{add,del}_memcg()
2026-10-12 20:54 [PATCH 0/5] mm: multi-gen LRU: reduce memcg rotation overhead Max Kellermann
2026-10-12 20:54 ` [PATCH 1/5] include/linux/rculist_nulls: add hlist_nulls_add_behind_rcu() Max Kellermann
@ 2026-10-12 20:54 ` Max Kellermann
2026-10-12 20:54 ` [PATCH 3/5] mm/mglru: cache the last memcg node, make tail insertion constant time Max Kellermann
` (2 subsequent siblings)
4 siblings, 0 replies; 6+ messages in thread
From: Max Kellermann @ 2026-10-12 20:54 UTC (permalink / raw)
To: akpm, kasong, qi.zheng, shakeel.butt, baohua, axelrasmussen,
yuanchu, weixugc, baoquan.he, baolin.wang, david, ljs, liam,
vbabka, rppt, surenb, mhocko, hannes, linux-mm, linux-kernel,
rcu
Cc: Max Kellermann
Preparation 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`.
Signed-off-by: Max Kellermann <max.kellermann@ionos.com>
---
mm/vmscan.c | 36 ++++++++++++++++++++++++++++--------
1 file changed, 28 insertions(+), 8 deletions(-)
diff --git a/mm/vmscan.c b/mm/vmscan.c
index f11491ee9ed5..3d4bc12cf18e 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -4379,6 +4379,29 @@ 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, bool at_head)
+{
+ struct hlist_nulls_head *head = &memcg_lru->fifo[gen][bin];
+
+ lockdep_assert_held(&memcg_lru->lock);
+
+ if (at_head)
+ hlist_nulls_add_head_rcu(&lrugen->list, head);
+ else
+ 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;
@@ -4409,12 +4432,9 @@ 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);
-
- if (op == MEMCG_LRU_HEAD || op == MEMCG_LRU_OLD)
- hlist_nulls_add_head_rcu(&lruvec->lrugen.list, &pgdat->memcg_lru.fifo[new][bin]);
- else
- 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,
+ op == MEMCG_LRU_HEAD || op == MEMCG_LRU_OLD);
pgdat->memcg_lru.nr_memcgs[old]--;
pgdat->memcg_lru.nr_memcgs[new]++;
@@ -4445,7 +4465,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, false);
pgdat->memcg_lru.nr_memcgs[gen]++;
spin_unlock_irq(&pgdat->memcg_lru.lock);
@@ -4479,7 +4499,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))
--
2.47.3
^ permalink raw reply [flat|nested] 6+ messages in thread* [PATCH 3/5] mm/mglru: cache the last memcg node, make tail insertion constant time
2026-10-12 20:54 [PATCH 0/5] mm: multi-gen LRU: reduce memcg rotation overhead Max Kellermann
2026-10-12 20:54 ` [PATCH 1/5] include/linux/rculist_nulls: add hlist_nulls_add_behind_rcu() Max Kellermann
2026-10-12 20:54 ` [PATCH 2/5] mm/vmscan: move code to lru_gen_{add,del}_memcg() Max Kellermann
@ 2026-10-12 20:54 ` Max Kellermann
2026-10-12 20:54 ` [PATCH 4/5] mm/mglru: avoid redundant rotations of young memcgs Max Kellermann
2026-10-12 20:54 ` [PATCH 5/5] mm/mglru: reschedule between memcg reclaim attempts Max Kellermann
4 siblings, 0 replies; 6+ messages in thread
From: Max Kellermann @ 2026-10-12 20:54 UTC (permalink / raw)
To: akpm, kasong, qi.zheng, shakeel.butt, baohua, axelrasmussen,
yuanchu, weixugc, baoquan.he, baolin.wang, david, ljs, liam,
vbabka, rppt, surenb, mhocko, hannes, linux-mm, linux-kernel,
rcu
Cc: Max Kellermann
Rotating 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.
Signed-off-by: Max Kellermann <max.kellermann@ionos.com>
---
include/linux/mmzone.h | 4 ++++
mm/vmscan.c | 24 +++++++++++++++++++++---
2 files changed, 25 insertions(+), 3 deletions(-)
diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
index 94f9c3ff5416..9c1c1f153d1f 100644
--- a/include/linux/mmzone.h
+++ b/include/linux/mmzone.h
@@ -586,6 +586,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;
};
@@ -683,6 +685,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;
};
diff --git a/mm/vmscan.c b/mm/vmscan.c
index 3d4bc12cf18e..69976df5d537 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -4384,21 +4384,37 @@ static void lru_gen_add_memcg(struct lru_gen_memcg *memcg_lru,
int gen, int bin, bool at_head)
{
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);
- if (at_head)
+ lrugen->bin = bin;
+
+ if (at_head || !last)
hlist_nulls_add_head_rcu(&lrugen->list, head);
else
- hlist_nulls_add_tail_rcu(&lrugen->list, head);
+ hlist_nulls_add_behind_rcu(&lrugen->list, last);
+
+ if (!at_head || !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);
}
@@ -5883,8 +5899,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;
+ }
}
}
--
2.47.3
^ permalink raw reply [flat|nested] 6+ messages in thread* [PATCH 4/5] mm/mglru: avoid redundant rotations of young memcgs
2026-10-12 20:54 [PATCH 0/5] mm: multi-gen LRU: reduce memcg rotation overhead Max Kellermann
` (2 preceding siblings ...)
2026-10-12 20:54 ` [PATCH 3/5] mm/mglru: cache the last memcg node, make tail insertion constant time Max Kellermann
@ 2026-10-12 20:54 ` Max Kellermann
2026-10-12 20:54 ` [PATCH 5/5] mm/mglru: reschedule between memcg reclaim attempts Max Kellermann
4 siblings, 0 replies; 6+ messages in thread
From: Max Kellermann @ 2026-10-12 20:54 UTC (permalink / raw)
To: akpm, kasong, qi.zheng, shakeel.butt, baohua, axelrasmussen,
yuanchu, weixugc, baoquan.he, baolin.wang, david, ljs, liam,
vbabka, rppt, surenb, mhocko, hannes, linux-mm, linux-kernel,
rcu
Cc: Max Kellermann
Concurrent 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%.
Signed-off-by: Max Kellermann <max.kellermann@ionos.com>
---
mm/vmscan.c | 9 +++++++++
1 file changed, 9 insertions(+)
diff --git a/mm/vmscan.c b/mm/vmscan.c
index 69976df5d537..922c59eb9629 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -4445,6 +4445,14 @@ 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);
@@ -4458,6 +4466,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);
}
--
2.47.3
^ permalink raw reply [flat|nested] 6+ messages in thread* [PATCH 5/5] mm/mglru: reschedule between memcg reclaim attempts
2026-10-12 20:54 [PATCH 0/5] mm: multi-gen LRU: reduce memcg rotation overhead Max Kellermann
` (3 preceding siblings ...)
2026-10-12 20:54 ` [PATCH 4/5] mm/mglru: avoid redundant rotations of young memcgs Max Kellermann
@ 2026-10-12 20:54 ` Max Kellermann
4 siblings, 0 replies; 6+ messages in thread
From: Max Kellermann @ 2026-10-12 20:54 UTC (permalink / raw)
To: akpm, kasong, qi.zheng, shakeel.butt, baohua, axelrasmussen,
yuanchu, weixugc, baoquan.he, baolin.wang, david, ljs, liam,
vbabka, rppt, surenb, mhocko, hannes, linux-mm, linux-kernel,
rcu
Cc: Max Kellermann
shrink_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.
Signed-off-by: Max Kellermann <max.kellermann@ionos.com>
---
mm/vmscan.c | 11 +++++++++++
1 file changed, 11 insertions(+)
diff --git a/mm/vmscan.c b/mm/vmscan.c
index 922c59eb9629..c9d53546dc10 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -5194,6 +5194,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;
@@ -5224,6 +5227,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))
--
2.47.3
^ permalink raw reply [flat|nested] 6+ messages in thread