Skip to contentSkip to conversation

mm: multi-gen LRU: per-process heatmaps

RFC PATCH In review Yuanchu Xie 3 participants 9 messages Sep 11, 2022 – Jan 30, 2025

Subsystems (5)
Memory management BPF MM core MGLRU +1 more subsystems
lore
Share & tools
lore

Yuanchu Xie

author reviewer
#0 lore raw

cover mm: multi-gen LRU: per-process heatmaps

Today, the MGLRU debugfs interface (/sys/kernel/debug/lru_gen) provides a histogram counting the number of pages belonging to each generation, providing some data for memory coldness, but we don't actually know where the memory actually is. However, since MGLRU revamps the page reclaim mechanism to walk page tables, we can hook into MGLRU page table access bit harvesting with a BPF program to collect information on relative hotness and coldness, NUMA nodes, whether a page is anon/file, etc.

Using BPF programs to collect and aggregate page access information allows for the userspace agent to customize what to collect and how to aggregate. It could focus on a particular region of interest and count a moving average access frequency, or find allocations that are never accessed that could be eliminated all together. Currently MGLRU relies on heuristics with regards to what generation a page is assigned, for example, pages accessed through page tables are always assigned to the youngest generation. Exposing page access data can allow future work to customize page generation assignments (with more BPF).

We demonstrate feasibility with a proof-of-concept that prints a live heatmap of a process, with configurable MGLRU aging intervals and aggregation intervals. This is a very rough PoC that still needs a lot of work, but it shows a lot can be done by exposing page access information from MGLRU. I will be presenting this work at the coming LPC.

As an example. I ran the memtier benchmark[1] and captured a heatmap of memcached being populated and running the benchmark (similar to the one Yu posted for OpenWRT[2]):

$ cat ./run_memtier_benchmark.sh
    run_memtier_benchmark()
    {
        # populate dataset
        memtier_benchmark/memtier_benchmark -s 127.0.0.1 -p 11211 \
            -P memcache_binary -n allkeys -t 1 -c 1 --ratio 1:0 --pipeline 8 \
            --key-minimum=1 --key-maximum=$2 --key-pattern=P:P \
            -d 1000
        # access dataset using Guassian pattern
        memtier_benchmark/memtier_benchmark -s 127.0.0.1 -p 11211 \
            -P memcache_binary --test-time $1 -t 1 -c 1 --ratio 0:1 \
            --pipeline 8 --key-minimum=1 --key-maximum=$2 \
            --key-pattern=G:G --randomize --distinct-client-seed
        # collect results
    }
    run_duration_secs=3600
    max_key=8000000

    run_memtier_benchmark $run_duration_secs $max_key

In the following screenshot we can see the process of populating the dataset and accessing the dataset:
https://services.google.com/fh/files/events/memcached_memtier_startup.png

Patch 1 adds the infrastructure to enable BPF programs to monitor page access bit harvesting

Patch 2 includes a proof-of-concept python TUI program displaying online per-process heatmaps.

[1] https://github.com/RedisLabs/memtier_benchmark
[2] https://lore.kernel.org/all/[email protected]/

Yuanchu Xie (2):
mm: multi-gen LRU: support page access info harvesting with eBPF
mm: add a BPF-based per-process heatmap tool

 include/linux/mmzone.h          |   1 +
 mm/vmscan.c                     | 154 ++++++++
 tools/vm/heatmap/Makefile       |  30 ++
 tools/vm/heatmap/heatmap.bpf.c  | 123 +++++++
 tools/vm/heatmap/heatmap.user.c | 188 ++++++++++
 tools/vm/heatmap/heatmap_tui.py | 600 ++++++++++++++++++++++++++++++++
 6 files changed, 1096 insertions(+)
 create mode 100644 tools/vm/heatmap/Makefile
 create mode 100644 tools/vm/heatmap/heatmap.bpf.c
 create mode 100644 tools/vm/heatmap/heatmap.user.c
 create mode 100755 tools/vm/heatmap/heatmap_tui.py
Signature · 1 line
2.37.2.789.g6183377224-goog
author reviewer
#1 lore raw

RFC PATCH 1/2 mm: multi-gen LRU: support page access info harvesting with eBPF

Add the infrastructure to enable bpf programs to hook into MGLRU and capture the page access information as MGLRU walks page tables.

- Add empty functions as hook points to capture pte and pmd access bit harvesting of MGLRU page table walks.

- Add a kfunc to invoke MGLRU aging.

- Add a kfunc and hook point to enable the filtering of MGLRU aging by PIDs.

---
 include/linux/mmzone.h |   1 +
 mm/vmscan.c            | 154 +++++++++++++++++++++++++++++++++++++++++
 2 files changed, 155 insertions(+)
include/linux/mmzone.h +1 -0
index 710fc1d83bd0..f652b9473c6f 100644
@@ -481,6 +481,7 @@ struct lru_gen_mm_walk {
 	int mm_stats[NR_MM_STATS];
 	/* total batched items */
 	int batched;
+	pid_t pid;
 	bool can_swap;
 	bool force_scan;
 };
mm/vmscan.c +154 -0

208 lines not on this page · raw message

Signature · 1 line
2.37.2.789.g6183377224-goog
#2 lore raw

Re: [RFC PATCH 1/2] mm: multi-gen LRU: support page access info harvesting with eBPF

reproduce (this is a W=1 build): wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross #…

Hi Yuanchu,

[FYI, it's a private test report for your RFC patch.] [auto build test ERROR on akpm-mm/mm-everything]

url:    https://github.com/intel-lab-lkp/linux/commits/Yuanchu-Xie/mm-multi-gen-LRU-per-process-heatmaps/20220911-163720
base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-everything
config: i386-randconfig-a015-20220912 (https://download.01.org/0day-ci/archive/20220913/[email protected]/config)
compiler: clang version 14.0.6 (https://github.com/llvm/llvm-project f28c006a5895fc0e329fe15fead81e37457cb1d1)

reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# https://github.com/intel-lab-lkp/linux/commit/cf24b7f2ea91083cc7630500059db49811243805
git remote add linux-review https://github.com/intel-lab-lkp/linux
git fetch --no-tags linux-review Yuanchu-Xie/mm-multi-gen-LRU-per-process-heatmaps/20220911-163720 git checkout cf24b7f2ea91083cc7630500059db49811243805
# save the config file
mkdir build_dir && cp config build_dir/.config
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=i386 SHELL=/bin/bash

If you fix the issue, kindly add following tag where applicable

All errors (new ones prefixed by >>):

mm/vmscan.c:3416:6: warning: no previous prototype for function 'bpf_set_skip_mm' [-Wmissing-prototypes] void bpf_set_skip_mm(struct bpf_mglru_should_skip_mm_control *ctl)

        ^
   mm/vmscan.c:3416:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
   void bpf_set_skip_mm(struct bpf_mglru_should_skip_mm_control *ctl)
   ^
   static 
   mm/vmscan.c:3422:1: warning: no previous prototype for function 'bpf_mglru_should_skip_mm' [-Wmissing-prototypes]
   bpf_mglru_should_skip_mm(struct bpf_mglru_should_skip_mm_control *ctl)
   ^
   mm/vmscan.c:3421:17: note: declare 'static' if the function is not intended to be used outside of this translation unit
   __weak noinline void
                   ^
                   static 
   mm/vmscan.c:3906:22: warning: no previous prototype for function 'mglru_pte_probe' [-Wmissing-prototypes]
   __weak noinline void mglru_pte_probe(pid_t pid, unsigned int nid, unsigned long addr,
                        ^
   mm/vmscan.c:3906:17: note: declare 'static' if the function is not intended to be used outside of this translation unit
   __weak noinline void mglru_pte_probe(pid_t pid, unsigned int nid, unsigned long addr,
                   ^
                   static 
   mm/vmscan.c:3912:22: warning: no previous prototype for function 'mglru_pmd_probe' [-Wmissing-prototypes]
   __weak noinline void mglru_pmd_probe(pid_t pid, unsigned int nid, unsigned long addr,
                        ^
   mm/vmscan.c:3912:17: note: declare 'static' if the function is not intended to be used outside of this translation unit
   __weak noinline void mglru_pmd_probe(pid_t pid, unsigned int nid, unsigned long addr,
                   ^
                   static 
>> mm/vmscan.c:4219:18: error: no member named 'owner' in 'struct mm_struct'
           walk->pid = mm->owner->pid;
                       ~~  ^
   mm/vmscan.c:5706:5: warning: no previous prototype for function 'bpf_run_aging' [-Wmissing-prototypes]
   int bpf_run_aging(int memcg_id, bool can_swap,
       ^

mm/vmscan.c:5706:1: note: declare 'static' if the function is not intended to be used outside of this translation unit int bpf_run_aging(int memcg_id, bool can_swap,
^
static
5 warnings and 1 error generated.

vim +4219 mm/vmscan.c

4208
4209 static void walk_mm(struct lruvec *lruvec, struct mm_struct *mm, struct lru_gen_mm_walk *walk)
4210 {
4211 static const struct mm_walk_ops mm_walk_ops = {
4212 .test_walk = should_skip_vma,
4213 .p4d_entry = walk_pud_range,
4214 };
4215
4216 int err;
4217 struct mem_cgroup *memcg = lruvec_memcg(lruvec);
4218

> 4219		walk->pid = mm->owner->pid;

4220 walk->next_addr = FIRST_USER_ADDRESS;
4221
4222 do {
4223 err = -EBUSY;
4224
4225 /* folio_update_gen() requires stable folio_memcg() */
4226 if (!mem_cgroup_trylock_pages(memcg))
4227 break;
4228
4229 /* the caller might be holding the lock for write */
4230 if (mmap_read_trylock(mm)) {
4231 err = walk_page_range(mm, walk->next_addr, ULONG_MAX, &mm_walk_ops, walk);
4232
4233 mmap_read_unlock(mm);
4234 }
4235
4236 mem_cgroup_unlock_pages();
4237
4238 if (walk->batched) {
4239 spin_lock_irq(&lruvec->lru_lock);
4240 reset_batch_size(lruvec, walk);
4241 spin_unlock_irq(&lruvec->lru_lock);
4242 }
4243
4244 cond_resched();
4245 } while (err == -EAGAIN);
4246 }
4247

Signature · 2 lines
0-DAY CI Kernel Test Service
https://01.org/lkp
#3 lore raw

Re: [RFC PATCH 1/2] mm: multi-gen LRU: support page access info harvesting with eBPF

In reply to Yuanchu Xie
reproduce (this is a W=1 build): wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross #…

Hi Yuanchu,

[FYI, it's a private test report for your RFC patch.] [auto build test ERROR on akpm-mm/mm-everything]

url:    https://github.com/intel-lab-lkp/linux/commits/Yuanchu-Xie/mm-multi-gen-LRU-per-process-heatmaps/20220911-163720
base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-everything
config: x86_64-randconfig-r022-20220912 (https://download.01.org/0day-ci/archive/20220913/[email protected]/config)
compiler: clang version 14.0.6 (https://github.com/llvm/llvm-project f28c006a5895fc0e329fe15fead81e37457cb1d1)

reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# https://github.com/intel-lab-lkp/linux/commit/cf24b7f2ea91083cc7630500059db49811243805
git remote add linux-review https://github.com/intel-lab-lkp/linux
git fetch --no-tags linux-review Yuanchu-Xie/mm-multi-gen-LRU-per-process-heatmaps/20220911-163720 git checkout cf24b7f2ea91083cc7630500059db49811243805
# save the config file
mkdir build_dir && cp config build_dir/.config
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=x86_64 SHELL=/bin/bash

If you fix the issue, kindly add following tag where applicable

All error/warnings (new ones prefixed by >>):

>> mm/vmscan.c:3416:6: warning: no previous prototype for function 'bpf_set_skip_mm' [-Wmissing-prototypes]
   void bpf_set_skip_mm(struct bpf_mglru_should_skip_mm_control *ctl)
        ^
   mm/vmscan.c:3416:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
   void bpf_set_skip_mm(struct bpf_mglru_should_skip_mm_control *ctl)
   ^
   static 
>> mm/vmscan.c:3422:1: warning: no previous prototype for function 'bpf_mglru_should_skip_mm' [-Wmissing-prototypes]
   bpf_mglru_should_skip_mm(struct bpf_mglru_should_skip_mm_control *ctl)
   ^
   mm/vmscan.c:3421:17: note: declare 'static' if the function is not intended to be used outside of this translation unit
   __weak noinline void
                   ^
                   static 
>> mm/vmscan.c:3906:22: warning: no previous prototype for function 'mglru_pte_probe' [-Wmissing-prototypes]
   __weak noinline void mglru_pte_probe(pid_t pid, unsigned int nid, unsigned long addr,
                        ^
   mm/vmscan.c:3906:17: note: declare 'static' if the function is not intended to be used outside of this translation unit
   __weak noinline void mglru_pte_probe(pid_t pid, unsigned int nid, unsigned long addr,
                   ^
                   static 
>> mm/vmscan.c:3912:22: warning: no previous prototype for function 'mglru_pmd_probe' [-Wmissing-prototypes]
   __weak noinline void mglru_pmd_probe(pid_t pid, unsigned int nid, unsigned long addr,
                        ^
   mm/vmscan.c:3912:17: note: declare 'static' if the function is not intended to be used outside of this translation unit
   __weak noinline void mglru_pmd_probe(pid_t pid, unsigned int nid, unsigned long addr,
                   ^
                   static 
>> mm/vmscan.c:4219:18: error: no member named 'owner' in 'struct mm_struct'
           walk->pid = mm->owner->pid;
                       ~~  ^
>> mm/vmscan.c:5706:5: warning: no previous prototype for function 'bpf_run_aging' [-Wmissing-prototypes]
   int bpf_run_aging(int memcg_id, bool can_swap,
       ^

mm/vmscan.c:5706:1: note: declare 'static' if the function is not intended to be used outside of this translation unit int bpf_run_aging(int memcg_id, bool can_swap,
^
static
5 warnings and 1 error generated.

vim +4219 mm/vmscan.c

4208
4209 static void walk_mm(struct lruvec *lruvec, struct mm_struct *mm, struct lru_gen_mm_walk *walk)
4210 {
4211 static const struct mm_walk_ops mm_walk_ops = {
4212 .test_walk = should_skip_vma,
4213 .p4d_entry = walk_pud_range,
4214 };
4215
4216 int err;
4217 struct mem_cgroup *memcg = lruvec_memcg(lruvec);
4218

> 4219		walk->pid = mm->owner->pid;

4220 walk->next_addr = FIRST_USER_ADDRESS;
4221
4222 do {
4223 err = -EBUSY;
4224
4225 /* folio_update_gen() requires stable folio_memcg() */
4226 if (!mem_cgroup_trylock_pages(memcg))
4227 break;
4228
4229 /* the caller might be holding the lock for write */
4230 if (mmap_read_trylock(mm)) {
4231 err = walk_page_range(mm, walk->next_addr, ULONG_MAX, &mm_walk_ops, walk);
4232
4233 mmap_read_unlock(mm);
4234 }
4235
4236 mem_cgroup_unlock_pages();
4237
4238 if (walk->batched) {
4239 spin_lock_irq(&lruvec->lru_lock);
4240 reset_batch_size(lruvec, walk);
4241 spin_unlock_irq(&lruvec->lru_lock);
4242 }
4243
4244 cond_resched();
4245 } while (err == -EAGAIN);
4246 }
4247

Signature · 2 lines
0-DAY CI Kernel Test Service
https://01.org/lkp
author reviewer
#4 lore raw

RFC PATCH 2/2 mm: add a BPF-based per-process heatmap tool

In reply to Yuanchu Xie

The heatmap tool uses a bpf program integrated with a TUI as a proof of concept for consuming page access information from MGLRU. It displays heats, NUMA node, and anon/other with configurable aging intervals and aggregation intervals.

---
 tools/vm/heatmap/Makefile       |  30 ++
 tools/vm/heatmap/heatmap.bpf.c  | 123 +++++++
 tools/vm/heatmap/heatmap.user.c | 188 ++++++++++
 tools/vm/heatmap/heatmap_tui.py | 600 ++++++++++++++++++++++++++++++++
 4 files changed, 941 insertions(+)
 create mode 100644 tools/vm/heatmap/Makefile
 create mode 100644 tools/vm/heatmap/heatmap.bpf.c
 create mode 100644 tools/vm/heatmap/heatmap.user.c
 create mode 100755 tools/vm/heatmap/heatmap_tui.py
tools/vm/heatmap/Makefile new file +30 -0
new file mode 100644
index 000000000000..43ae4af67781
@@ -0,0 +1,30 @@
+# SPDX-License-Identifier: GPL-2.0
+include ../../build/Build.include
+
+MAKEFLAGS += --no-builtin-rules
+MAKEFLAGS += --no-builtin-variables
+
+CC := clang
+KERNEL_DIR := $(abspath ../../..)
+
+.PHONY: clean all
+
+all: heatmap.user heatmap.skel.h vmlinux.h
+
+%.user: %.user.o
+	$(CC) -g -O2 $^ -l:libbpf.a -lelf -lz -o $@ -static
+
+vmlinux.h: $(KERNEL_DIR)/vmlinux
+	bpftool btf dump file $(KERNEL_DIR)/vmlinux format c > vmlinux.h
+
+%.bpf.o: vmlinux.h %.bpf.c
+	$(CC) -g -D__TARGET_ARCH_x86 -O2 -target bpf -c $*.bpf.c -o $*.bpf.o
+
+%.skel.h: %.bpf.o
+	bpftool gen skeleton $*.bpf.o > $*.skel.h
+
+%.user.o: %.skel.h %.user.c
+	$(CC) -g -O2 -c $*.user.c -o $*.user.o
+
+clean:
+	rm -f *.o heatmap.user *.skel.h vmlinux.h
tools/vm/heatmap/heatmap.bpf.c new file +123 -0

123 lines not on this page · raw message

tools/vm/heatmap/heatmap.user.c new file +188 -0

188 lines not on this page · raw message

tools/vm/heatmap/heatmap_tui.py new file +600 -0

600 lines not on this page · raw message

Signature · 1 line
2.37.2.789.g6183377224-goog
author reviewer
#6 lore raw
Quoted 4 lines · Muyang Tian

Hi all,
It has been a long time since this patchset[0] submitted, and I've been doing something similar recently. I wonder why this patchset remains unmerged/uncommented? Is there any other similar work?

Hi Muyang,

I'd love to learn about your use case and your approach as well. The code here requires some polish and cleanup, but it's mostly bpf code in tooling. Happy to work on it.

Thanks,
Yuanchu

#7 lore raw

Hi Yuanchu,

I'm working on observability and the programmable page generation policy of MGLRU based on eBPF, using a similar approach to yours. I'd like to know if there is any related work, such as the application of eBPF in MGLRU?
Also, this RFC provides a user space interface to call run_aging(), which is called periodically in the demo. Do you plan to optimize this, perhaps by calling run_aging() based on page access observation results?

Thanks!

author reviewer
#8 lore raw
Quoted 5 lines · Muyang Tian

Hi Yuanchu,

I'm working on observability and the programmable page generation policy of MGLRU based on eBPF, using a similar approach to yours. I'd like to know if there is any related work, such as the application of eBPF in MGLRU?

Not that I'm aware of. There were some patches fiddling with the generation placement of pages but I can't seem to find them.

Quoted 2 lines

Also, this RFC provides a user space interface to call run_aging(), which is called periodically in the demo. Do you plan to optimize this, perhaps by calling run_aging() based on page access observation results?

Right now I don't have any plans to optimize this patch series. What are your use cases? All I cared about was one off observability of accesses and not much thought went into optimizing the tool.

Thanks,
Yuanchu