1 From 534bcc4a0bb5b24600891ce793f0295a142e9dae Mon Sep 17 00:00:00 2001
2 From: Yu Zhao <yuzhao@google.com>
3 Date: Mon, 5 Apr 2021 04:17:41 -0600
4 Subject: [PATCH 05/10] mm: multigenerational lru: mm_struct list
6 To scan PTEs for accessed pages, a mm_struct list is maintained for
7 each memcg. When multiple threads traverse the same memcg->mm_list,
8 each of them gets a unique mm_struct and therefore they can run
9 walk_page_range() concurrently to reach page tables of all processes
12 This infrastructure also provides the following optimizations:
13 1) it allows walkers to skip processes that have been sleeping since
14 the last walk by tracking the usage of mm_struct between context
16 2) it allows walkers to add interesting items they find during a
17 walk to a Bloom filter so that they can skip uninteresting items
18 during the next walk by testing whether an item is in this Bloom
21 Signed-off-by: Yu Zhao <yuzhao@google.com>
22 Tested-by: Konstantin Kharlamov <Hi-Angel@yandex.ru>
23 Change-Id: I25d9eda8c6bdc7c3653b9f210a159d6c247c81e8
26 include/linux/memcontrol.h | 4 +
27 include/linux/mm_inline.h | 6 +
28 include/linux/mm_types.h | 75 +++++++++
29 include/linux/mmzone.h | 63 +++++++
32 kernel/sched/core.c | 1 +
33 mm/memcontrol.c | 25 +++
34 mm/vmscan.c | 331 +++++++++++++++++++++++++++++++++++++
35 10 files changed, 517 insertions(+)
39 @@ -1013,6 +1013,7 @@ static int exec_mmap(struct mm_struct *m
40 active_mm = tsk->active_mm;
45 * This prevents preemption while active_mm is being loaded and
46 * it and mm are being updated, which could cause problems for
47 @@ -1023,6 +1024,7 @@ static int exec_mmap(struct mm_struct *m
48 if (!IS_ENABLED(CONFIG_ARCH_WANT_IRQS_OFF_ACTIVATE_MM))
50 activate_mm(active_mm, mm);
51 + lru_gen_activate_mm(mm);
52 if (IS_ENABLED(CONFIG_ARCH_WANT_IRQS_OFF_ACTIVATE_MM))
54 tsk->mm->vmacache_seqnum = 0;
55 --- a/include/linux/memcontrol.h
56 +++ b/include/linux/memcontrol.h
57 @@ -348,6 +348,10 @@ struct mem_cgroup {
58 struct deferred_split deferred_split_queue;
61 +#ifdef CONFIG_LRU_GEN
62 + struct lru_gen_mm_list mm_list;
65 struct mem_cgroup_per_node *nodeinfo[];
68 --- a/include/linux/mm_inline.h
69 +++ b/include/linux/mm_inline.h
70 @@ -100,6 +100,12 @@ static inline int lru_gen_from_seq(unsig
71 return seq % MAX_NR_GENS;
74 +/* Return a proper index regardless whether we keep stats for historical generations. */
75 +static inline int lru_hist_from_seq(unsigned long seq)
77 + return seq % NR_HIST_GENS;
80 /* The youngest and the second youngest generations are counted as active. */
81 static inline bool lru_gen_is_active(struct lruvec *lruvec, int gen)
83 --- a/include/linux/mm_types.h
84 +++ b/include/linux/mm_types.h
86 #define _LINUX_MM_TYPES_H
88 #include <linux/mm_types_task.h>
89 +#include <linux/sched.h>
91 #include <linux/auxvec.h>
92 #include <linux/list.h>
94 #include <linux/page-flags-layout.h>
95 #include <linux/workqueue.h>
96 #include <linux/seqlock.h>
97 +#include <linux/nodemask.h>
98 +#include <linux/mmdebug.h>
102 @@ -580,6 +583,18 @@ struct mm_struct {
103 #ifdef CONFIG_IOMMU_SUPPORT
106 +#ifdef CONFIG_LRU_GEN
108 + /* the node of a global or per-memcg mm_struct list */
109 + struct list_head list;
111 + /* points to the memcg of the owner task above */
112 + struct mem_cgroup *memcg;
114 + /* whether this mm_struct has been used since the last walk */
117 +#endif /* CONFIG_LRU_GEN */
118 } __randomize_layout;
121 @@ -606,6 +621,66 @@ static inline cpumask_t *mm_cpumask(stru
122 return (struct cpumask *)&mm->cpu_bitmap;
125 +#ifdef CONFIG_LRU_GEN
127 +struct lru_gen_mm_list {
128 + /* a global or per-memcg mm_struct list */
129 + struct list_head fifo;
130 + /* protects the list above */
134 +void lru_gen_add_mm(struct mm_struct *mm);
135 +void lru_gen_del_mm(struct mm_struct *mm);
137 +void lru_gen_migrate_mm(struct mm_struct *mm);
140 +static inline void lru_gen_init_mm(struct mm_struct *mm)
142 + INIT_LIST_HEAD(&mm->lrugen.list);
144 + mm->lrugen.memcg = NULL;
146 + nodes_clear(mm->lrugen.nodes);
149 +/* Track the usage of each mm_struct so that we can skip inactive ones. */
150 +static inline void lru_gen_activate_mm(struct mm_struct *mm)
152 + /* unlikely but not a bug when racing with lru_gen_migrate_mm() */
153 + VM_WARN_ON(list_empty(&mm->lrugen.list));
155 + if (!(current->flags & PF_KTHREAD) && !nodes_full(mm->lrugen.nodes))
156 + nodes_setall(mm->lrugen.nodes);
159 +#else /* !CONFIG_LRU_GEN */
161 +static inline void lru_gen_add_mm(struct mm_struct *mm)
165 +static inline void lru_gen_del_mm(struct mm_struct *mm)
170 +static inline void lru_gen_migrate_mm(struct mm_struct *mm)
175 +static inline void lru_gen_init_mm(struct mm_struct *mm)
179 +static inline void lru_gen_activate_mm(struct mm_struct *mm)
183 +#endif /* CONFIG_LRU_GEN */
186 extern void tlb_gather_mmu(struct mmu_gather *tlb, struct mm_struct *mm);
187 extern void tlb_gather_mmu_fullmm(struct mmu_gather *tlb, struct mm_struct *mm);
188 --- a/include/linux/mmzone.h
189 +++ b/include/linux/mmzone.h
190 @@ -318,6 +318,13 @@ struct lruvec;
191 #define MIN_NR_GENS 2
192 #define MAX_NR_GENS ((unsigned int)CONFIG_NR_LRU_GENS)
194 +/* Whether to keep stats for historical generations. */
195 +#ifdef CONFIG_LRU_GEN_STATS
196 +#define NR_HIST_GENS ((unsigned int)CONFIG_NR_LRU_GENS)
198 +#define NR_HIST_GENS 1U
202 /* the aging increments the max generation number */
203 unsigned long max_seq;
204 @@ -333,13 +340,63 @@ struct lrugen {
205 bool enabled[ANON_AND_FILE];
209 + MM_LEAF_TOTAL, /* total leaf entries */
210 + MM_LEAF_OLD, /* old leaf entries */
211 + MM_LEAF_YOUNG, /* young leaf entries */
212 + MM_NONLEAF_TOTAL, /* total non-leaf entries */
213 + MM_NONLEAF_PREV, /* previously worthy non-leaf entries */
214 + MM_NONLEAF_CUR, /* currently worthy non-leaf entries */
218 +/* mnemonic codes for the stats above */
219 +#define MM_STAT_CODES "toydpc"
221 +/* double buffering bloom filters */
222 +#define NR_BLOOM_FILTERS 2
224 +struct lru_gen_mm_walk {
225 + /* set to max_seq after each round of walk */
227 + /* the next mm_struct on the list to walk */
228 + struct list_head *head;
229 + /* the first mm_struct never walked before */
230 + struct list_head *tail;
231 + /* to wait for the last walker to finish */
232 + struct wait_queue_head wait;
233 + /* bloom filters flip after each round of walk */
234 + unsigned long *filters[NR_BLOOM_FILTERS];
235 + /* page table stats for debugging */
236 + unsigned long stats[NR_HIST_GENS][NR_MM_STATS];
237 + /* the number of concurrent walkers */
241 +#define MIN_BATCH_SIZE 64
242 #define MAX_BATCH_SIZE 8192
244 +struct mm_walk_args {
245 + struct mem_cgroup *memcg;
246 + unsigned long max_seq;
247 + unsigned long start_pfn;
248 + unsigned long end_pfn;
249 + unsigned long next_addr;
250 + unsigned long bitmap[BITS_TO_LONGS(MIN_BATCH_SIZE)];
254 + int nr_pages[MAX_NR_GENS][ANON_AND_FILE][MAX_NR_ZONES];
255 + int mm_stats[NR_MM_STATS];
259 void lru_gen_init_state(struct mem_cgroup *memcg, struct lruvec *lruvec);
260 void lru_gen_change_state(bool enable, bool main, bool swap);
263 void lru_gen_init_memcg(struct mem_cgroup *memcg);
264 +void lru_gen_free_memcg(struct mem_cgroup *memcg);
267 #else /* !CONFIG_LRU_GEN */
268 @@ -356,6 +413,10 @@ static inline void lru_gen_change_state(
269 static inline void lru_gen_init_memcg(struct mem_cgroup *memcg)
273 +static inline void lru_gen_free_memcg(struct mem_cgroup *memcg)
278 #endif /* CONFIG_LRU_GEN */
279 @@ -380,6 +441,8 @@ struct lruvec {
280 #ifdef CONFIG_LRU_GEN
281 /* unevictable pages are on LRU_UNEVICTABLE */
282 struct lrugen evictable;
283 + /* state for mm list and page table walks */
284 + struct lru_gen_mm_walk mm_walk;
287 struct pglist_data *pgdat;
290 @@ -422,6 +422,7 @@ assign_new_owner:
293 WRITE_ONCE(mm->owner, c);
294 + lru_gen_migrate_mm(mm);
300 @@ -1080,6 +1080,7 @@ static struct mm_struct *mm_init(struct
303 mm->user_ns = get_user_ns(user_ns);
304 + lru_gen_init_mm(mm);
308 @@ -1122,6 +1123,7 @@ static inline void __mmput(struct mm_str
311 module_put(mm->binfmt->module);
312 + lru_gen_del_mm(mm);
316 @@ -2617,6 +2619,13 @@ pid_t kernel_clone(struct kernel_clone_a
320 + if (IS_ENABLED(CONFIG_LRU_GEN) && !(clone_flags & CLONE_VM)) {
321 + /* lock the task to synchronize with memcg migration */
323 + lru_gen_add_mm(p->mm);
329 /* forking complete and child started to run, tell ptracer */
330 --- a/kernel/sched/core.c
331 +++ b/kernel/sched/core.c
332 @@ -4978,6 +4978,7 @@ context_switch(struct rq *rq, struct tas
333 * finish_task_switch()'s mmdrop().
335 switch_mm_irqs_off(prev->active_mm, next->mm, next);
336 + lru_gen_activate_mm(next->mm);
338 if (!prev->mm) { // from kernel
339 /* will mmdrop() in finish_task_switch(). */
340 --- a/mm/memcontrol.c
341 +++ b/mm/memcontrol.c
342 @@ -5163,6 +5163,7 @@ static void __mem_cgroup_free(struct mem
344 static void mem_cgroup_free(struct mem_cgroup *memcg)
346 + lru_gen_free_memcg(memcg);
347 memcg_wb_domain_exit(memcg);
348 __mem_cgroup_free(memcg);
350 @@ -6195,6 +6196,29 @@ static void mem_cgroup_move_task(void)
354 +#ifdef CONFIG_LRU_GEN
355 +static void mem_cgroup_attach(struct cgroup_taskset *tset)
357 + struct cgroup_subsys_state *css;
358 + struct task_struct *task = NULL;
360 + cgroup_taskset_for_each_leader(task, css, tset)
367 + if (task->mm && task->mm->owner == task)
368 + lru_gen_migrate_mm(task->mm);
372 +static void mem_cgroup_attach(struct cgroup_taskset *tset)
375 +#endif /* CONFIG_LRU_GEN */
377 static int seq_puts_memcg_tunable(struct seq_file *m, unsigned long value)
379 if (value == PAGE_COUNTER_MAX)
380 @@ -6538,6 +6562,7 @@ struct cgroup_subsys memory_cgrp_subsys
381 .css_reset = mem_cgroup_css_reset,
382 .css_rstat_flush = mem_cgroup_css_rstat_flush,
383 .can_attach = mem_cgroup_can_attach,
384 + .attach = mem_cgroup_attach,
385 .cancel_attach = mem_cgroup_cancel_attach,
386 .post_attach = mem_cgroup_move_task,
387 .dfl_cftypes = memory_files,
390 @@ -2929,6 +2929,306 @@ static bool __maybe_unused seq_is_valid(
393 /******************************************************************************
395 + ******************************************************************************/
397 +static struct lru_gen_mm_list *get_mm_list(struct mem_cgroup *memcg)
399 + static struct lru_gen_mm_list mm_list = {
400 + .fifo = LIST_HEAD_INIT(mm_list.fifo),
401 + .lock = __SPIN_LOCK_UNLOCKED(mm_list.lock),
406 + return &memcg->mm_list;
411 +void lru_gen_add_mm(struct mm_struct *mm)
414 + struct mem_cgroup *memcg = get_mem_cgroup_from_mm(mm);
415 + struct lru_gen_mm_list *mm_list = get_mm_list(memcg);
417 + VM_BUG_ON_MM(!list_empty(&mm->lrugen.list), mm);
419 + VM_BUG_ON_MM(mm->lrugen.memcg, mm);
420 + mm->lrugen.memcg = memcg;
422 + spin_lock(&mm_list->lock);
424 + list_add_tail(&mm->lrugen.list, &mm_list->fifo);
426 + for_each_node(nid) {
427 + struct lruvec *lruvec = get_lruvec(nid, memcg);
432 + if (lruvec->mm_walk.tail == &mm_list->fifo)
433 + lruvec->mm_walk.tail = lruvec->mm_walk.tail->prev;
436 + spin_unlock(&mm_list->lock);
439 +void lru_gen_del_mm(struct mm_struct *mm)
442 + struct lru_gen_mm_list *mm_list;
443 + struct mem_cgroup *memcg = NULL;
445 + if (list_empty(&mm->lrugen.list))
449 + memcg = mm->lrugen.memcg;
451 + mm_list = get_mm_list(memcg);
453 + spin_lock(&mm_list->lock);
455 + for_each_node(nid) {
456 + struct lruvec *lruvec = get_lruvec(nid, memcg);
461 + if (lruvec->mm_walk.tail == &mm->lrugen.list)
462 + lruvec->mm_walk.tail = lruvec->mm_walk.tail->next;
464 + if (lruvec->mm_walk.head != &mm->lrugen.list)
467 + lruvec->mm_walk.head = lruvec->mm_walk.head->next;
468 + if (lruvec->mm_walk.head == &mm_list->fifo)
469 + WRITE_ONCE(lruvec->mm_walk.seq, lruvec->mm_walk.seq + 1);
472 + list_del_init(&mm->lrugen.list);
474 + spin_unlock(&mm_list->lock);
477 + mem_cgroup_put(mm->lrugen.memcg);
478 + mm->lrugen.memcg = NULL;
483 +void lru_gen_migrate_mm(struct mm_struct *mm)
485 + struct mem_cgroup *memcg;
487 + lockdep_assert_held(&mm->owner->alloc_lock);
489 + if (mem_cgroup_disabled())
493 + memcg = mem_cgroup_from_task(mm->owner);
495 + if (memcg == mm->lrugen.memcg)
498 + VM_BUG_ON_MM(!mm->lrugen.memcg, mm);
499 + VM_BUG_ON_MM(list_empty(&mm->lrugen.list), mm);
501 + lru_gen_del_mm(mm);
502 + lru_gen_add_mm(mm);
506 +#define BLOOM_FILTER_SHIFT 15
508 +static inline int filter_gen_from_seq(unsigned long seq)
510 + return seq % NR_BLOOM_FILTERS;
513 +static void get_item_key(void *item, int *key)
515 + u32 hash = hash_ptr(item, BLOOM_FILTER_SHIFT * 2);
517 + BUILD_BUG_ON(BLOOM_FILTER_SHIFT * 2 > BITS_PER_TYPE(u32));
519 + key[0] = hash & (BIT(BLOOM_FILTER_SHIFT) - 1);
520 + key[1] = hash >> BLOOM_FILTER_SHIFT;
523 +static void clear_bloom_filter(struct lruvec *lruvec, unsigned long seq)
525 + unsigned long *filter;
526 + int gen = filter_gen_from_seq(seq);
528 + lockdep_assert_held(&get_mm_list(lruvec_memcg(lruvec))->lock);
530 + filter = lruvec->mm_walk.filters[gen];
532 + bitmap_clear(filter, 0, BIT(BLOOM_FILTER_SHIFT));
536 + filter = bitmap_zalloc(BIT(BLOOM_FILTER_SHIFT), GFP_ATOMIC);
537 + WRITE_ONCE(lruvec->mm_walk.filters[gen], filter);
540 +static void set_bloom_filter(struct lruvec *lruvec, unsigned long seq, void *item)
543 + unsigned long *filter;
544 + int gen = filter_gen_from_seq(seq);
546 + filter = READ_ONCE(lruvec->mm_walk.filters[gen]);
550 + get_item_key(item, key);
552 + if (!test_bit(key[0], filter))
553 + set_bit(key[0], filter);
554 + if (!test_bit(key[1], filter))
555 + set_bit(key[1], filter);
558 +static bool test_bloom_filter(struct lruvec *lruvec, unsigned long seq, void *item)
561 + unsigned long *filter;
562 + int gen = filter_gen_from_seq(seq);
564 + filter = READ_ONCE(lruvec->mm_walk.filters[gen]);
568 + get_item_key(item, key);
570 + return test_bit(key[0], filter) && test_bit(key[1], filter);
573 +static void reset_mm_stats(struct lruvec *lruvec, bool last, struct mm_walk_args *args)
576 + int hist = lru_hist_from_seq(args->max_seq);
578 + lockdep_assert_held(&get_mm_list(lruvec_memcg(lruvec))->lock);
580 + for (i = 0; i < NR_MM_STATS; i++) {
581 + WRITE_ONCE(lruvec->mm_walk.stats[hist][i],
582 + lruvec->mm_walk.stats[hist][i] + args->mm_stats[i]);
583 + args->mm_stats[i] = 0;
586 + if (!last || NR_HIST_GENS == 1)
589 + hist = lru_hist_from_seq(args->max_seq + 1);
590 + for (i = 0; i < NR_MM_STATS; i++)
591 + WRITE_ONCE(lruvec->mm_walk.stats[hist][i], 0);
594 +static bool should_skip_mm(struct mm_struct *mm, struct mm_walk_args *args)
597 + unsigned long size = 0;
599 + if (cpumask_empty(mm_cpumask(mm)) && !node_isset(args->node_id, mm->lrugen.nodes))
602 + if (mm_is_oom_victim(mm))
605 + for (type = !args->swappiness; type < ANON_AND_FILE; type++) {
606 + size += type ? get_mm_counter(mm, MM_FILEPAGES) :
607 + get_mm_counter(mm, MM_ANONPAGES) +
608 + get_mm_counter(mm, MM_SHMEMPAGES);
611 + if (size < MIN_BATCH_SIZE)
614 + if (!mmget_not_zero(mm))
617 + node_clear(args->node_id, mm->lrugen.nodes);
622 +/* To support multiple walkers that concurrently walk an mm_struct list. */
623 +static bool get_next_mm(struct lruvec *lruvec, struct mm_walk_args *args,
624 + struct mm_struct **iter)
626 + bool first = false;
628 + struct mm_struct *mm = NULL;
629 + struct lru_gen_mm_walk *mm_walk = &lruvec->mm_walk;
630 + struct lru_gen_mm_list *mm_list = get_mm_list(args->memcg);
633 + mmput_async(*iter);
634 + else if (args->max_seq <= READ_ONCE(mm_walk->seq))
637 + spin_lock(&mm_list->lock);
639 + VM_BUG_ON(args->max_seq > mm_walk->seq + 1);
640 + VM_BUG_ON(*iter && args->max_seq < mm_walk->seq);
641 + VM_BUG_ON(*iter && !mm_walk->nr_walkers);
643 + if (args->max_seq <= mm_walk->seq) {
649 + if (mm_walk->head == &mm_list->fifo) {
650 + VM_BUG_ON(mm_walk->nr_walkers);
651 + mm_walk->head = mm_walk->head->next;
655 + while (!mm && mm_walk->head != &mm_list->fifo) {
656 + mm = list_entry(mm_walk->head, struct mm_struct, lrugen.list);
658 + mm_walk->head = mm_walk->head->next;
660 + if (mm_walk->tail == &mm->lrugen.list) {
661 + mm_walk->tail = mm_walk->tail->next;
662 + args->use_filter = false;
665 + if (should_skip_mm(mm, args))
669 + if (mm_walk->head == &mm_list->fifo)
670 + WRITE_ONCE(mm_walk->seq, mm_walk->seq + 1);
673 + mm_walk->nr_walkers--;
675 + mm_walk->nr_walkers++;
677 + if (mm_walk->nr_walkers)
681 + clear_bloom_filter(lruvec, args->max_seq + 1);
684 + reset_mm_stats(lruvec, last, args);
686 + spin_unlock(&mm_list->lock);
693 +/******************************************************************************
695 ******************************************************************************/
697 @@ -3112,6 +3412,7 @@ void lru_gen_init_state(struct mem_cgrou
700 struct lrugen *lrugen = &lruvec->evictable;
701 + struct lru_gen_mm_list *mm_list = get_mm_list(memcg);
703 lrugen->max_seq = MIN_NR_GENS + 1;
704 lrugen->enabled[0] = lru_gen_enabled() && lru_gen_nr_swapfiles;
705 @@ -3122,6 +3423,17 @@ void lru_gen_init_state(struct mem_cgrou
707 for_each_gen_type_zone(gen, type, zone)
708 INIT_LIST_HEAD(&lrugen->lists[gen][type][zone]);
710 + if (IS_ENABLED(CONFIG_MEMORY_HOTPLUG) && !memcg)
711 + spin_lock(&mm_list->lock);
713 + lruvec->mm_walk.seq = MIN_NR_GENS;
714 + lruvec->mm_walk.head = &mm_list->fifo;
715 + lruvec->mm_walk.tail = &mm_list->fifo;
716 + init_waitqueue_head(&lruvec->mm_walk.wait);
718 + if (IS_ENABLED(CONFIG_MEMORY_HOTPLUG) && !memcg)
719 + spin_unlock(&mm_list->lock);
723 @@ -3129,18 +3441,37 @@ void lru_gen_init_memcg(struct mem_cgrou
727 + INIT_LIST_HEAD(&memcg->mm_list.fifo);
728 + spin_lock_init(&memcg->mm_list.lock);
731 struct lruvec *lruvec = get_lruvec(nid, memcg);
733 lru_gen_init_state(memcg, lruvec);
737 +void lru_gen_free_memcg(struct mem_cgroup *memcg)
741 + for_each_node(nid) {
743 + struct lruvec *lruvec = get_lruvec(nid, memcg);
745 + for (i = 0; i < NR_BLOOM_FILTERS; i++) {
746 + bitmap_free(lruvec->mm_walk.filters[i]);
747 + lruvec->mm_walk.filters[i] = NULL;
753 static int __init init_lru_gen(void)
755 BUILD_BUG_ON(MIN_NR_GENS + 1 >= MAX_NR_GENS);
756 BUILD_BUG_ON(BIT(LRU_GEN_WIDTH) <= MAX_NR_GENS);
757 + BUILD_BUG_ON(sizeof(MM_STAT_CODES) != NR_MM_STATS + 1);