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 --- 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 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 --- 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 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 --- 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 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 --- 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 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 --- 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