Multi-Gen LRU Framework
Subsystems (20)
v14 cover Multi-Gen LRU Framework
What's new
==========
Retested on v6.0-rc1; rebased to the latest mm-unstable.
TLDR
====
The current page reclaim is too expensive in terms of CPU usage and it often makes poor choices about what to evict. This patchset offers an alternative solution that is performant, versatile and straightforward.
Patchset overview
=================
The design and implementation overview is in patch 14:
https://lore.kernel.org/r/[email protected]/
01. mm: x86, arm64: add arch_has_hw_pte_young()
02. mm: x86: add CONFIG_ARCH_HAS_NONLEAF_PMD_YOUNG
Take advantage of hardware features when trying to clear the accessed bit in many PTEs.
03. mm/vmscan.c: refactor shrink_node()
04. Revert "include/linux/mm_inline.h: fold __update_lru_size() into its sole caller"
Minor refactors to improve readability for the following patches.
05. mm: multi-gen LRU: groundwork
Adds the basic data structure and the functions that insert pages to and remove pages from the multi-gen LRU (MGLRU) lists.
06. mm: multi-gen LRU: minimal implementation
A minimal implementation without optimizations.
07. mm: multi-gen LRU: exploit locality in rmap
Exploits spatial locality to improve efficiency when using the rmap.
08. mm: multi-gen LRU: support page table walks
Further exploits spatial locality by optionally scanning page tables.
09. mm: multi-gen LRU: optimize multiple memcgs Optimizes the overall performance for multiple memcgs running mixed types of workloads.
10. mm: multi-gen LRU: kill switch
Adds a kill switch to enable or disable MGLRU at runtime.
11. mm: multi-gen LRU: thrashing prevention
12. mm: multi-gen LRU: debugfs interface
Provide userspace with features like thrashing prevention, working set estimation and proactive reclaim.
13. mm: multi-gen LRU: admin guide
14. mm: multi-gen LRU: design doc
Add an admin guide and a design doc.
Benchmark results
=================
Independent lab results
-----------------------
Based on the popularity of searches [01] and the memory usage in Google's public cloud, the most popular open-source memory-hungry applications, in alphabetical order, are:
Apache Cassandra Memcached
Apache Hadoop MongoDB
Apache Spark PostgreSQL
MariaDB (MySQL) RedisAn independent lab evaluated MGLRU with the most widely used benchmark suites for the above applications. They posted 960 data points along with kernel metrics and perf profiles collected over more than 500 hours of total benchmark time. Their final reports show that, with 95% confidence intervals (CIs), the above applications all performed significantly better for at least part of their benchmark matrices.
On 5.14:
1. Apache Spark [02] took 95% CIs [9.28, 11.19]% and [12.20, 14.93]% less wall time to sort three billion random integers, respectively, under the medium- and the high-concurrency conditions, when overcommitting memory. There were no statistically significant changes in wall time for the rest of the benchmark matrix.
2. MariaDB [03] achieved 95% CIs [5.24, 10.71]% and [20.22, 25.97]% more transactions per minute (TPM), respectively, under the medium- and the high-concurrency conditions, when overcommitting memory. There were no statistically significant changes in TPM for the rest of the benchmark matrix.
3. Memcached [04] achieved 95% CIs [23.54, 32.25]%, [20.76, 41.61]% and [21.59, 30.02]% more operations per second (OPS), respectively, for sequential access, random access and Gaussian (distribution) access, when THP=always; 95% CIs [13.85, 15.97]% and [23.94, 29.92]% more OPS, respectively, for random access and Gaussian access, when THP=never. There were no statistically significant changes in OPS for the rest of the benchmark matrix.
4. MongoDB [05] achieved 95% CIs [2.23, 3.44]%, [6.97, 9.73]% and [2.16, 3.55]% more operations per second (OPS), respectively, for exponential (distribution) access, random access and Zipfian (distribution) access, when underutilizing memory; 95% CIs [8.83, 10.03]%, [21.12, 23.14]% and [5.53, 6.46]% more OPS, respectively, for exponential access, random access and Zipfian access, when overcommitting memory.
On 5.15:
5. Apache Cassandra [06] achieved 95% CIs [1.06, 4.10]%, [1.94, 5.43]% and [4.11, 7.50]% more operations per second (OPS), respectively, for exponential (distribution) access, random access and Zipfian (distribution) access, when swap was off; 95% CIs [0.50, 2.60]%, [6.51, 8.77]% and [3.29, 6.75]% more OPS, respectively, for exponential access, random access and Zipfian access, when swap was on.
6. Apache Hadoop [07] took 95% CIs [5.31, 9.69]% and [2.02, 7.86]% less average wall time to finish twelve parallel TeraSort jobs, respectively, under the medium- and the high-concurrency conditions, when swap was on. There were no statistically significant changes in average wall time for the rest of the benchmark matrix.
7. PostgreSQL [08] achieved 95% CI [1.75, 6.42]% more transactions per minute (TPM) under the high-concurrency condition, when swap was off; 95% CIs [12.82, 18.69]% and [22.70, 46.86]% more TPM, respectively, under the medium- and the high-concurrency conditions, when swap was on. There were no statistically significant changes in TPM for the rest of the benchmark matrix.
8. Redis [09] achieved 95% CIs [0.58, 5.94]%, [6.55, 14.58]% and [11.47, 19.36]% more total operations per second (OPS), respectively, for sequential access, random access and Gaussian (distribution) access, when THP=always; 95% CIs [1.27, 3.54]%, [10.11, 14.81]% and [8.75, 13.64]% more total OPS, respectively, for sequential access, random access and Gaussian access, when THP=never.
Our lab results
---------------
To supplement the above results, we ran the following benchmark suites on 5.16-rc7 and found no regressions [10].
fs_fio_bench_hdd_mq pft
fs_lmbench pgsql-hammerdb
fs_parallelio redis
fs_postmark stream
hackbench sysbenchthread
kernbench tpcc_spark
memcached unixbench
multichase vm-scalability
mutilate will-it-scalenginx
[01] https://trends.google.com
[02] https://lore.kernel.org/r/[email protected]/
[03] https://lore.kernel.org/r/[email protected]/
[04] https://lore.kernel.org/r/[email protected]/
[05] https://lore.kernel.org/r/[email protected]/
[06] https://lore.kernel.org/r/[email protected]/
[07] https://lore.kernel.org/r/[email protected]/
[08] https://lore.kernel.org/r/[email protected]/
[09] https://lore.kernel.org/r/[email protected]/
[10] https://lore.kernel.org/r/[email protected]/
Read-world applications
=======================
Third-party testimonials
------------------------
Konstantin reported [11]:
I have Archlinux with 8G RAM + zswap + swap. While developing, I have lots of apps opened such as multiple LSP-servers for different langs, chats, two browsers, etc... Usually, my system gets quickly to a point of SWAP-storms, where I have to kill LSP-servers, restart browsers to free memory, etc, otherwise the system lags heavily and is barely usable.
1.5 day ago I migrated from 5.11.15 kernel to 5.12 + the LRU patchset, and I started up by opening lots of apps to create memory pressure, and worked for a day like this. Till now I had not a single SWAP-storm, and mind you I got 3.4G in SWAP. I was never getting to the point of 3G in SWAP before without a single SWAP-storm.
Vaibhav from IBM reported [12]:
In a synthetic MongoDB Benchmark, seeing an average of ~19% throughput improvement on POWER10(Radix MMU + 64K Page Size) with MGLRU patches on top of 5.16 kernel for MongoDB + YCSB across three different request distributions, namely, Exponential, Uniform and Zipfan.
Shuang from U of Rochester reported [13]:
With the MGLRU, fio achieved 95% CIs [38.95, 40.26]%, [4.12, 6.64]% and [9.26, 10.36]% higher throughput, respectively, for random access, Zipfian (distribution) access and Gaussian (distribution) access, when the average number of jobs per CPU is 1; 95% CIs [42.32, 49.15]%, [9.44, 9.89]% and [20.99, 22.86]% higher throughput, respectively, for random access, Zipfian access and Gaussian access, when the average number of jobs per CPU is 2.
Daniel from Michigan Tech reported [14]:
With Memcached allocating ~100GB of byte-addressable Optante, performance improvement in terms of throughput (measured as queries per second) was about 10% for a series of workloads.
Large-scale deployments
-----------------------
We've rolled out MGLRU to tens of millions of Chrome OS users and about a million Android users. Google's fleetwide profiling [15] shows an overall 40% decrease in kswapd CPU usage, in addition to improvements in other UX metrics, e.g., an 85% decrease in the number of low-memory kills at the 75th percentile and an 18% decrease in app launch time at the 50th percentile.
The downstream kernels that have been using MGLRU include:
1. Android [16]
2. Arch Linux Zen [17]
3. Armbian [18]
4. Chrome OS [19]
5. Liquorix [20]
6. post-factum [21]
7. XanMod [22]
[11] https://lore.kernel.org/r/[email protected]/
[12] https://lore.kernel.org/r/[email protected]/
[13] https://lore.kernel.org/r/[email protected]/
[14] https://lore.kernel.org/r/CA+4-3vksGvKd18FgRinxhqHetBS1hQekJE2gwco8Ja-bJWKtFw@mail.gmail.com/
[15] https://dl.acm.org/doi/10.1145/2749469.2750392
[16] https://android.com
[17] https://archlinux.org
[18] https://armbian.com
[19] https://chromium.org
[20] https://liquorix.net
[21] https://codeberg.org/pf-kernel
[22] https://xanmod.org
Summery
=======
The facts are:
1. The independent lab results and the real-world applications indicate substantial improvements; there are no known regressions.
2. Thrashing prevention, working set estimation and proactive reclaim work out of the box; there are no equivalent solutions.
3. There is a lot of new code; no smaller changes have been demonstrated similar effects.
Our options, accordingly, are:
1. Given the amount of evidence, the reported improvements will likely materialize for a wide range of workloads.
2. Gauging the interest from the past discussions, the new features will likely be put to use for both personal computers and data centers.
3. Based on Google's track record, the new code will likely be well maintained in the long term. It'd be more difficult if not impossible to achieve similar effects with other approaches.
Yu Zhao (14):
mm: x86, arm64: add arch_has_hw_pte_young()
mm: x86: add CONFIG_ARCH_HAS_NONLEAF_PMD_YOUNG mm/vmscan.c: refactor shrink_node()
Revert "include/linux/mm_inline.h: fold __update_lru_size() into its
sole caller"
mm: multi-gen LRU: groundwork
mm: multi-gen LRU: minimal implementation
mm: multi-gen LRU: exploit locality in rmap
mm: multi-gen LRU: support page table walks
mm: multi-gen LRU: optimize multiple memcgs
mm: multi-gen LRU: kill switch
mm: multi-gen LRU: thrashing prevention
mm: multi-gen LRU: debugfs interface
mm: multi-gen LRU: admin guide
mm: multi-gen LRU: design doc
Documentation/admin-guide/mm/index.rst | 1 + Documentation/admin-guide/mm/multigen_lru.rst | 156 + Documentation/mm/index.rst | 1 + Documentation/mm/multigen_lru.rst | 159 + arch/Kconfig | 8 + arch/arm64/include/asm/pgtable.h | 15 +- arch/x86/Kconfig | 1 + arch/x86/include/asm/pgtable.h | 9 +- arch/x86/mm/pgtable.c | 5 +- fs/exec.c | 2 + fs/fuse/dev.c | 3 +- include/linux/cgroup.h | 15 +- include/linux/memcontrol.h | 36 + include/linux/mm.h | 5 + include/linux/mm_inline.h | 231 +- include/linux/mm_types.h | 77 + include/linux/mmzone.h | 214 ++ include/linux/nodemask.h | 1 + include/linux/page-flags-layout.h | 16 +- include/linux/page-flags.h | 4 +- include/linux/pgtable.h | 17 +- include/linux/sched.h | 4 + include/linux/swap.h | 4 + kernel/bounds.c | 7 + kernel/cgroup/cgroup-internal.h | 1 - kernel/exit.c | 1 + kernel/fork.c | 9 + kernel/sched/core.c | 1 + mm/Kconfig | 26 + mm/huge_memory.c | 3 +- mm/internal.h | 1 + mm/memcontrol.c | 28 + mm/memory.c | 39 +- mm/mm_init.c | 6 +- mm/mmzone.c | 2 + mm/rmap.c | 6 + mm/swap.c | 54 +- mm/vmscan.c | 2972 ++++++++++++++++- mm/workingset.c | 110 +- 39 files changed, 4095 insertions(+), 155 deletions(-) create mode 100644 Documentation/admin-guide/mm/multigen_lru.rst create mode 100644 Documentation/mm/multigen_lru.rst
base-commit: d2af7b221349ff6241e25fa8c67bcfae2b360700
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
PATCH v14 1/14 mm: x86, arm64: add arch_has_hw_pte_young()
Some architectures automatically set the accessed bit in PTEs, e.g., x86 and arm64 v8.2. On architectures that do not have this capability, clearing the accessed bit in a PTE usually triggers a page fault following the TLB miss of this PTE (to emulate the accessed bit).
Being aware of this capability can help make better decisions, e.g., whether to spread the work out over a period of time to reduce bursty page faults when trying to clear the accessed bit in many PTEs.
Note that theoretically this capability can be unreliable, e.g., hotplugged CPUs might be different from builtin ones. Therefore it should not be used in architecture-independent code that involves correctness, e.g., to determine whether TLB flushes are required (in combination with the accessed bit).
--- arch/arm64/include/asm/pgtable.h | 15 ++------------- arch/x86/include/asm/pgtable.h | 6 +++--- include/linux/pgtable.h | 13 +++++++++++++ mm/memory.c | 14 +------------- 4 files changed, 19 insertions(+), 29 deletions(-)
arch/arm64/include/asm/pgtable.h +2 -13
@@ -1082,24 +1082,13 @@ static inline void update_mmu_cache(struct vm_area_struct *vma,* page after fork() + CoW for pfn mappings. We don't always have a * hardware-managed access flag on arm64. */ -static inline bool arch_faults_on_old_pte (void ) -{ -/* The register read below requires a stable CPU to make any sense */ -cant_migrate (); - -return !cpu_has_hw_af (); -} -#define arch_faults_on_old_pte arch_faults_on_old_pte +#define arch_has_hw_pte_young cpu_has_hw_af/* * Experimentally, it's cheap to set the access flag in hardware and we * benefit from prefaulting mappings as 'old' to start with. */ -static inline bool arch_wants_old_prefaulted_pte (void ) -{ -return !arch_faults_on_old_pte (); -} -#define arch_wants_old_prefaulted_pte arch_wants_old_prefaulted_pte +#define arch_wants_old_prefaulted_pte cpu_has_hw_afstatic inline bool pud_sect_supported (void ) {
arch/x86/include/asm/pgtable.h +3 -3
@@ -1431,10 +1431,10 @@ static inline bool arch_has_pfn_modify_check(void)return boot_cpu_has_bug (X86_BUG_L1TF ); } -#define arch_faults_on_old_pte arch_faults_on_old_pte -static inline bool arch_faults_on_old_pte (void ) +#define arch_has_hw_pte_young arch_has_hw_pte_young +static inline bool arch_has_hw_pte_young (void ) { -return false; +return true; }#ifdef CONFIG_PAGE_TABLE_CHECK
include/linux/pgtable.h +13 -0
@@ -260,6 +260,19 @@ static inline int pmdp_clear_flush_young(struct vm_area_struct *vma,#endif /* CONFIG_TRANSPARENT_HUGEPAGE */ #endif +#ifndef arch_has_hw_pte_young +/* +* Return whether the accessed bit is supported on the local CPU. +* +* This stub assumes accessing through an old PTE triggers a page fault. +* Architectures that automatically set the access bit should overwrite it. +*/ +static inline bool arch_has_hw_pte_young (void ) +{ +return false; +} +#endif +#ifndef __HAVE_ARCH_PTEP_GET_AND_CLEAR static inline pte_t ptep_get_and_clear(struct mm_struct *mm, unsigned long address,
mm/memory.c +1 -13
@@ -126,18 +126,6 @@ int randomize_va_space __read_mostly =2 ;#endif -#ifndef arch_faults_on_old_pte -static inline bool arch_faults_on_old_pte (void ) -{ -/* -* Those arches which don't have hw access flag feature need to -* implement their own helper. By default, "true" means pagefault -* will be hit on old pte. -*/ -return true; -} -#endif -#ifndef arch_wants_old_prefaulted_ptestatic inline bool arch_wants_old_prefaulted_pte (void ) {
@@ -2871,7 +2859,7 @@ static inline bool __wp_page_copy_user(struct page *dst, struct page *src,* On architectures with software "accessed" bits, we would * take a double page fault, so mark it accessed here. */ -if (arch_faults_on_old_pte () && !pte_young (vmf->orig_pte)) { +if (!arch_has_hw_pte_young () && !pte_young (vmf->orig_pte)) {pte_t entry; vmf->pte =pte_offset_map_lock (mm, vmf->pmd, addr, &vmf->ptl);
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
PATCH v14 2/14 mm: x86: add CONFIG_ARCH_HAS_NONLEAF_PMD_YOUNG
In reply to Yu ZhaoSome architectures support the accessed bit in non-leaf PMD entries, e.g., x86 sets the accessed bit in a non-leaf PMD entry when using it as part of linear address translation [1]. Page table walkers that clear the accessed bit may use this capability to reduce their search space.
Note that:
1. Although an inline function is preferable, this capability is added as a configuration option for consistency with the existing macros.
2. Due to the little interest in other varieties, this capability was only tested on Intel and AMD CPUs.
Thanks to the following developers for their efforts [2][3].
Randy Dunlap <[email protected]>
Stephen Rothwell <[email protected]>
[1]: Intel 64 and IA-32 Architectures Software Developer's Manual
Volume 3 (June 2021), section 4.8
[2] https://lore.kernel.org/r/[email protected]/
[3] https://lore.kernel.org/r/[email protected]/
--- arch/Kconfig | 8 ++++++++ arch/x86/Kconfig | 1 + arch/x86/include/asm/pgtable.h | 3 ++- arch/x86/mm/pgtable.c | 5 ++++- include/linux/pgtable.h | 4 ++-- 5 files changed, 17 insertions(+), 4 deletions(-)
arch/Kconfig +8 -0
@@ -1416,6 +1416,14 @@ config DYNAMIC_SIGFRAME config HAVE_ARCH_NODE_DEV_GROUP bool +config ARCH_HAS_NONLEAF_PMD_YOUNG + bool + help + Architectures that select this option are capable of setting the + accessed bit in non-leaf PMD entries when using them as part of linear + address translations. Page table walkers that clear the accessed bit + may use this capability to reduce their search space. + source "kernel/gcov/Kconfig" source "scripts/gcc-plugins/Kconfig"
arch/x86/Kconfig +1 -0
@@ -85,6 +85,7 @@ config X86 select ARCH_HAS_PMEM_API if X86_64 select ARCH_HAS_PTE_DEVMAP if X86_64 select ARCH_HAS_PTE_SPECIAL + select ARCH_HAS_NONLEAF_PMD_YOUNG if PGTABLE_LEVELS > 2 select ARCH_HAS_UACCESS_FLUSHCACHE if X86_64 select ARCH_HAS_COPY_MC if X86_64 select ARCH_HAS_SET_MEMORY
arch/x86/include/asm/pgtable.h +2 -1
@@ -815,7 +815,8 @@ static inline unsigned long pmd_page_vaddr(pmd_t pmd)static inline int pmd_bad (pmd_t pmd) { -return (pmd_flags (pmd) & ~_PAGE_USER) != _KERNPG_TABLE; +return (pmd_flags (pmd) & ~(_PAGE_USER | _PAGE_ACCESSED)) != + (_KERNPG_TABLE & ~_PAGE_ACCESSED); }static inline unsigned long pages_to_mb (unsigned long npg)
arch/x86/mm/pgtable.c +4 -1
@@ -550,7 +550,7 @@ int ptep_test_and_clear_young(struct vm_area_struct *vma,return ret; } -#ifdef CONFIG_TRANSPARENT_HUGEPAGE +#if defined(CONFIG_TRANSPARENT_HUGEPAGE ) || defined(CONFIG_ARCH_HAS_NONLEAF_PMD_YOUNG )int pmdp_test_and_clear_young (struct vm_area_struct *vma,unsigned long addr,pmd_t *pmdp) {
@@ -562,6 +562,9 @@ int pmdp_test_and_clear_young(struct vm_area_struct *vma,return ret; } +#endif + +#ifdef CONFIG_TRANSPARENT_HUGEPAGE int pudp_test_and_clear_young (struct vm_area_struct *vma,unsigned long addr,pud_t *pudp) {
include/linux/pgtable.h +2 -2
@@ -213,7 +213,7 @@ static inline int ptep_test_and_clear_young(struct vm_area_struct *vma,#endif #ifndef __HAVE_ARCH_PMDP_TEST_AND_CLEAR_YOUNG -#ifdef CONFIG_TRANSPARENT_HUGEPAGE +#if defined(CONFIG_TRANSPARENT_HUGEPAGE ) || defined(CONFIG_ARCH_HAS_NONLEAF_PMD_YOUNG )static inline int pmdp_test_and_clear_young (struct vm_area_struct *vma,unsigned long address,pmd_t *pmdp)
@@ -234,7 +234,7 @@ static inline int pmdp_test_and_clear_young(struct vm_area_struct *vma,BUILD_BUG ();return 0 ; } -#endif /* CONFIG_TRANSPARENT_HUGEPAGE */ +#endif /* CONFIG_TRANSPARENT_HUGEPAGE || CONFIG_ARCH_HAS_NONLEAF_PMD_YOUNG */ #endif #ifndef __HAVE_ARCH_PTEP_CLEAR_YOUNG_FLUSH
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
PATCH v14 3/14 mm/vmscan.c: refactor shrink_node()
In reply to Yu ZhaoThis patch refactors shrink_node() to improve readability for the upcoming changes to mm/vmscan.c.
--- mm/vmscan.c | 198 +++++++++++++++++++++++++++------------------------- 1 file changed, 104 insertions(+), 94 deletions(-)
mm/vmscan.c +104 -94
@@ -2728,6 +2728,109 @@ enum scan_balance { SCAN_FILE, }; +static void prepare_scan_count (pg_data_t *pgdat,struct scan_control *sc) +{ +unsigned long file; +struct lruvec *target_lruvec; + + target_lruvec =mem_cgroup_lruvec (sc->target_mem_cgroup, pgdat); + +/* +* Flush the memory cgroup stats, so that we read accurate per-memcg +* lruvec stats for heuristics. +*/ +mem_cgroup_flush_stats (); + +/* +* Determine the scan balance between anon and file LRUs. +*/ +spin_lock_irq (&target_lruvec->lru_lock); + sc->anon_cost = target_lruvec->anon_cost; + sc->file_cost = target_lruvec->file_cost; +spin_unlock_irq (&target_lruvec->lru_lock); + +/* +* Target desirable inactive:active list ratios for the anon +* and file LRU lists. +*/ +if (!sc->force_deactivate) { +unsigned long refaults; + +/* +* When refaults are being observed, it means a new +* workingset is being established. Deactivate to get +* rid of any stale active pages quickly. +*/ + refaults =lruvec_page_state (target_lruvec, +WORKINGSET_ACTIVATE_ANON ); +if (refaults != target_lruvec->refaults[WORKINGSET_ANON ] || +inactive_is_low (target_lruvec,LRU_INACTIVE_ANON )) + sc->may_deactivate |=DEACTIVATE_ANON ; +else + sc->may_deactivate &= ~DEACTIVATE_ANON ; + + refaults =lruvec_page_state (target_lruvec, +WORKINGSET_ACTIVATE_FILE ); +if (refaults != target_lruvec->refaults[WORKINGSET_FILE ] || +inactive_is_low (target_lruvec,LRU_INACTIVE_FILE )) + sc->may_deactivate |=DEACTIVATE_FILE ; +else + sc->may_deactivate &= ~DEACTIVATE_FILE ; + }else + sc->may_deactivate =DEACTIVATE_ANON |DEACTIVATE_FILE ; + +/* +* If we have plenty of inactive file pages that aren't +* thrashing, try to reclaim those first before touching +* anonymous pages. +*/ + file =lruvec_page_state (target_lruvec,NR_INACTIVE_FILE ); +if (file >> sc->priority && !(sc->may_deactivate &DEACTIVATE_FILE )) + sc->cache_trim_mode =1 ; +else + sc->cache_trim_mode =0 ; + +/* +* Prevent the reclaimer from falling into the cache trap: as +* cache pages start out inactive, every cache fault will tip +* the scan balance towards the file LRU. And as the file LRU +* shrinks, so does the window for rotation from references. +* This means we have a runaway feedback loop where a tiny +* thrashing file LRU becomes infinitely more attractive than +* anon pages. Try to detect this based on file LRU size. +*/ +if (!cgroup_reclaim (sc)) { +unsigned long total_high_wmark =0 ; +unsigned long free, anon; +int z; + + free =sum_zone_node_page_state (pgdat->node_id,NR_FREE_PAGES ); + file =node_page_state (pgdat,NR_ACTIVE_FILE ) + +node_page_state (pgdat,NR_INACTIVE_FILE ); + +for (z =0 ; z <MAX_NR_ZONES ; z++) { +struct zone *zone = &pgdat->node_zones[z]; + +if (!managed_zone (zone)) +continue ; + + total_high_wmark +=high_wmark_pages (zone); + } + +/* +* Consider anon: if that's low too, this isn't a +* runaway file reclaim problem, but rather just +* extreme pressure. Reclaim as per usual then. +*/ + anon =node_page_state (pgdat,NR_INACTIVE_ANON ); + + sc->file_is_tiny = + file + free <= total_high_wmark && + !(sc->may_deactivate &DEACTIVATE_ANON ) && + anon >> sc->priority; + } +} +/* * Determine how aggressively the anon and file LRU lists should be * scanned.
@@ -3195,109 +3298,16 @@ static void shrink_node(pg_data_t *pgdat, struct scan_control *sc)unsigned long nr_reclaimed, nr_scanned;struct lruvec *target_lruvec;bool reclaimable = false; -unsigned long file; target_lruvec =mem_cgroup_lruvec (sc->target_mem_cgroup, pgdat); again: -/* -* Flush the memory cgroup stats, so that we read accurate per-memcg -* lruvec stats for heuristics. -*/ -mem_cgroup_flush_stats (); -memset (&sc->nr,0 ,sizeof (sc->nr)); nr_reclaimed = sc->nr_reclaimed; nr_scanned = sc->nr_scanned; -/* -* Determine the scan balance between anon and file LRUs. -*/ -spin_lock_irq (&target_lruvec->lru_lock); - sc->anon_cost = target_lruvec->anon_cost; - sc->file_cost = target_lruvec->file_cost; -spin_unlock_irq (&target_lruvec->lru_lock); - -/* -* Target desirable inactive:active list ratios for the anon -* and file LRU lists. -*/ -if (!sc->force_deactivate) { -unsigned long refaults; - -/* -* When refaults are being observed, it means a new -* workingset is being established. Deactivate to get -* rid of any stale active pages quickly. -*/ - refaults =lruvec_page_state (target_lruvec, -WORKINGSET_ACTIVATE_ANON ); -if (refaults != target_lruvec->refaults[WORKINGSET_ANON ] || -inactive_is_low (target_lruvec,LRU_INACTIVE_ANON )) - sc->may_deactivate |=DEACTIVATE_ANON ; -else - sc->may_deactivate &= ~DEACTIVATE_ANON ; - - refaults =lruvec_page_state (target_lruvec, -WORKINGSET_ACTIVATE_FILE ); -if (refaults != target_lruvec->refaults[WORKINGSET_FILE ] || -inactive_is_low (target_lruvec,LRU_INACTIVE_FILE )) - sc->may_deactivate |=DEACTIVATE_FILE ; -else - sc->may_deactivate &= ~DEACTIVATE_FILE ; - }else - sc->may_deactivate =DEACTIVATE_ANON |DEACTIVATE_FILE ; - -/* -* If we have plenty of inactive file pages that aren't -* thrashing, try to reclaim those first before touching -* anonymous pages. -*/ - file =lruvec_page_state (target_lruvec,NR_INACTIVE_FILE ); -if (file >> sc->priority && !(sc->may_deactivate &DEACTIVATE_FILE )) - sc->cache_trim_mode =1 ; -else - sc->cache_trim_mode =0 ; - -/* -* Prevent the reclaimer from falling into the cache trap: as -* cache pages start out inactive, every cache fault will tip -* the scan balance towards the file LRU. And as the file LRU -* shrinks, so does the window for rotation from references. -* This means we have a runaway feedback loop where a tiny -* thrashing file LRU becomes infinitely more attractive than -* anon pages. Try to detect this based on file LRU size. -*/ -if (!cgroup_reclaim (sc)) { -unsigned long total_high_wmark =0 ; -unsigned long free, anon; -int z; - - free =sum_zone_node_page_state (pgdat->node_id,NR_FREE_PAGES ); - file =node_page_state (pgdat,NR_ACTIVE_FILE ) + -node_page_state (pgdat,NR_INACTIVE_FILE ); - -for (z =0 ; z <MAX_NR_ZONES ; z++) { -struct zone *zone = &pgdat->node_zones[z]; -if (!managed_zone (zone)) -continue ; - - total_high_wmark +=high_wmark_pages (zone); - } - -/* -* Consider anon: if that's low too, this isn't a -* runaway file reclaim problem, but rather just -* extreme pressure. Reclaim as per usual then. -*/ - anon =node_page_state (pgdat,NR_INACTIVE_ANON ); - - sc->file_is_tiny = - file + free <= total_high_wmark && - !(sc->may_deactivate &DEACTIVATE_ANON ) && - anon >> sc->priority; - } +prepare_scan_count (pgdat, sc);shrink_node_memcgs (pgdat, sc);
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
PATCH v14 4/14 Revert "include/linux/mm_inline.h: fold __update_lru_size() into its sole caller"
In reply to Yu ZhaoThis patch undoes the following refactor:
commit 289ccba18af4 ("include/linux/mm_inline.h: fold __update_lru_size() into its sole caller")
The upcoming changes to include/linux/mm_inline.h will reuse __update_lru_size().
--- include/linux/mm_inline.h | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-)
include/linux/mm_inline.h +8 -1
@@ -34,7 +34,7 @@ static inline int page_is_file_lru(struct page *page)return folio_is_file_lru (page_folio (page)); } -static __always_inline void update_lru_size(struct lruvec *lruvec, +static __always_inline void __update_lru_size(struct lruvec *lruvec,enum lru_list lru,enum zone_type zid,long nr_pages) {
@@ -43,6 +43,13 @@ static __always_inline void update_lru_size(struct lruvec *lruvec,__mod_lruvec_state (lruvec,NR_LRU_BASE + lru, nr_pages);__mod_zone_page_state (&pgdat->node_zones[zid],NR_ZONE_LRU_BASE + lru, nr_pages); +} + +static __always_inline void update_lru_size(struct lruvec *lruvec, +enum lru_list lru,enum zone_type zid, +long nr_pages) +{ +__update_lru_size (lruvec, lru, zid, nr_pages);#ifdef CONFIG_MEMCG mem_cgroup_update_lru_size (lruvec, lru, zid, nr_pages);#endif
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
PATCH v14 5/14 mm: multi-gen LRU: groundwork
In reply to Yu ZhaoEvictable pages are divided into multiple generations for each lruvec. The youngest generation number is stored in lrugen->max_seq for both anon and file types as they are aged on an equal footing. The oldest generation numbers are stored in lrugen->min_seq[] separately for anon and file types as clean file pages can be evicted regardless of swap constraints. These three variables are monotonically increasing.
Generation numbers are truncated into order_base_2(MAX_NR_GENS+1) bits in order to fit into the gen counter in folio->flags. Each truncated generation number is an index to lrugen->lists[]. The sliding window technique is used to track at least MIN_NR_GENS and at most MAX_NR_GENS generations. The gen counter stores a value within [1, MAX_NR_GENS] while a page is on one of lrugen->lists[]. Otherwise it stores 0.
There are two conceptually independent procedures: "the aging", which produces young generations, and "the eviction", which consumes old generations. They form a closed-loop system, i.e., "the page reclaim". Both procedures can be invoked from userspace for the purposes of working set estimation and proactive reclaim. These techniques are commonly used to optimize job scheduling (bin packing) in data centers [1][2].
To avoid confusion, the terms "hot" and "cold" will be applied to the multi-gen LRU, as a new convention; the terms "active" and "inactive" will be applied to the active/inactive LRU, as usual.
The protection of hot pages and the selection of cold pages are based on page access channels and patterns. There are two access channels:
one through page tables and the other through file descriptors. The protection of the former channel is by design stronger because:
1. The uncertainty in determining the access patterns of the former channel is higher due to the approximation of the accessed bit.
2. The cost of evicting the former channel is higher due to the TLB flushes required and the likelihood of encountering the dirty bit.
3. The penalty of underprotecting the former channel is higher because applications usually do not prepare themselves for major page faults like they do for blocked I/O. E.g., GUI applications commonly use dedicated I/O threads to avoid blocking rendering threads.
There are also two access patterns: one with temporal locality and the other without. For the reasons listed above, the former channel is assumed to follow the former pattern unless VM_SEQ_READ or VM_RAND_READ is present; the latter channel is assumed to follow the latter pattern unless outlying refaults have been observed [3][4].
The next patch will address the "outlying refaults". Three macros, i.e., LRU_REFS_WIDTH, LRU_REFS_PGOFF and LRU_REFS_MASK, used later are added in this patch to make the entire patchset less diffy.
A page is added to the youngest generation on faulting. The aging needs to check the accessed bit at least twice before handing this page over to the eviction. The first check takes care of the accessed bit set on the initial fault; the second check makes sure this page has not been used since then. This protocol, AKA second chance, requires a minimum of two generations, hence MIN_NR_GENS.
[1] https://dl.acm.org/doi/10.1145/3297858.3304053
[2] https://dl.acm.org/doi/10.1145/3503222.3507731
[3] https://lwn.net/Articles/495543/
[4] https://lwn.net/Articles/815342/
--- fs/fuse/dev.c | 3 +- include/linux/mm_inline.h | 175 ++++++++++++++++++++++++++++++ include/linux/mmzone.h | 102 +++++++++++++++++ include/linux/page-flags-layout.h | 13 ++- include/linux/page-flags.h | 4 +- include/linux/sched.h | 4 + kernel/bounds.c | 5 + mm/Kconfig | 8 ++ mm/huge_memory.c | 3 +- mm/memcontrol.c | 2 + mm/memory.c | 25 +++++ mm/mm_init.c | 6 +- mm/mmzone.c | 2 + mm/swap.c | 11 +- mm/vmscan.c | 75 +++++++++++++ 15 files changed, 424 insertions(+), 14 deletions(-)
fs/fuse/dev.c +2 -1
@@ -776,7 +776,8 @@ static int fuse_check_page(struct page *page) 1 << PG_active | 1 << PG_workingset | 1 << PG_reclaim | - 1 << PG_waiters))) { + 1 << PG_waiters | + LRU_GEN_MASK | LRU_REFS_MASK))) {dump_page (page,"fuse: trying to steal weird page" );return 1 ; }
include/linux/mm_inline.h +175 -0
204 lines not on this page · raw message
include/linux/mmzone.h +102 -0
120 lines not on this page · raw message
include/linux/page-flags-layout.h +8 -5
@@ -55,7 +55,8 @@#define SECTIONS_WIDTH 0#endif -#if ZONES_WIDTH +SECTIONS_WIDTH +NODES_SHIFT <=BITS_PER_LONG -NR_PAGEFLAGS +#if ZONES_WIDTH +LRU_GEN_WIDTH +SECTIONS_WIDTH +NODES_SHIFT \ + <=BITS_PER_LONG -NR_PAGEFLAGS #define NODES_WIDTH NODES_SHIFT#elif defined(CONFIG_SPARSEMEM_VMEMMAP )#error "Vmemmap: No space for nodes field in page flags"
@@ -89,8 +90,8 @@#define LAST_CPUPID_SHIFT 0#endif -#if ZONES_WIDTH +SECTIONS_WIDTH +NODES_WIDTH +KASAN_TAG_WIDTH +LAST_CPUPID_SHIFT \ - <=BITS_PER_LONG -NR_PAGEFLAGS +#if ZONES_WIDTH +LRU_GEN_WIDTH +SECTIONS_WIDTH +NODES_WIDTH + \ +KASAN_TAG_WIDTH +LAST_CPUPID_SHIFT <=BITS_PER_LONG -NR_PAGEFLAGS #define LAST_CPUPID_WIDTH LAST_CPUPID_SHIFT#else #define LAST_CPUPID_WIDTH 0
@@ -100,10 +101,12 @@#define LAST_CPUPID_NOT_IN_PAGE_FLAGS #endif -#if ZONES_WIDTH +SECTIONS_WIDTH +NODES_WIDTH +KASAN_TAG_WIDTH +LAST_CPUPID_WIDTH \ - >BITS_PER_LONG -NR_PAGEFLAGS +#if ZONES_WIDTH +LRU_GEN_WIDTH +SECTIONS_WIDTH +NODES_WIDTH + \ +KASAN_TAG_WIDTH +LAST_CPUPID_WIDTH >BITS_PER_LONG -NR_PAGEFLAGS #error "Not enough bits in page flags"#endif +#define LRU_REFS_WIDTH 0 +#endif #endif /* _LINUX_PAGE_FLAGS_LAYOUT */
include/linux/page-flags.h +2 -2
@@ -1058,7 +1058,7 @@ static __always_inline void __ClearPageAnonExclusive(struct page *page)1UL << PG_private |1UL << PG_private_2 | \1UL << PG_writeback |1UL << PG_reserved | \1UL << PG_slab |1UL << PG_active | \ - 1UL << PG_unevictable | __PG_MLOCKED) + 1UL << PG_unevictable | __PG_MLOCKED | LRU_GEN_MASK)/* * Flags checked when a page is prepped for return by the page allocator.
@@ -1069,7 +1069,7 @@ static __always_inline void __ClearPageAnonExclusive(struct page *page)* alloc-free cycle to prevent from reusing the page. */ #define PAGE_FLAGS_CHECK_AT_PREP \ - (PAGEFLAGS_MASK & ~__PG_HWPOISON) + ((PAGEFLAGS_MASK & ~__PG_HWPOISON) | LRU_GEN_MASK | LRU_REFS_MASK)#define PAGE_FLAGS_PRIVATE \ (1UL << PG_private | 1UL << PG_private_2)
include/linux/sched.h +4 -0
@@ -914,6 +914,10 @@ struct task_struct {#ifdef CONFIG_MEMCG unsigned in_user_fault:1;#endif +#ifdef CONFIG_LRU_GEN +/* whether the LRU algorithm may apply to this access */ + unsigned in_lru_fault:1; +#endif #ifdef CONFIG_COMPAT_BRK unsigned brk_randomized:1;#endif
kernel/bounds.c +5 -0
@@ -22,6 +22,11 @@ int main(void)DEFINE (NR_CPUS_BITS ,ilog2 (CONFIG_NR_CPUS ));#endif DEFINE (SPINLOCK_SIZE ,sizeof (spinlock_t)); +#ifdef CONFIG_LRU_GEN +DEFINE (LRU_GEN_WIDTH ,order_base_2 (MAX_NR_GENS +1 )); +#else +DEFINE (LRU_GEN_WIDTH ,0 ); +#endif /* End of constants */ return 0 ;
mm/Kconfig +8 -0
@@ -1124,6 +1124,14 @@ config PTE_MARKER_UFFD_WP purposes. It is required to enable userfaultfd write protection on file-backed memory types like shmem and hugetlbfs. +config LRU_GEN + bool "Multi-Gen LRU" + depends on MMU + # make sure folio->flags has enough spare bits + depends on 64BIT || !SPARSEMEM || SPARSEMEM_VMEMMAP + help + A high performance LRU implementation to overcommit memory. + source "mm/damon/Kconfig" endmenu
mm/huge_memory.c +2 -1
@@ -2443,7 +2443,8 @@ static void __split_huge_page_tail(struct page *head, int tail,#ifdef CONFIG_64BIT (1L << PG_arch_2) | #endif - (1L << PG_dirty))); + (1L << PG_dirty) | + LRU_GEN_MASK | LRU_REFS_MASK));/* ->mapping in first tail page is compound_mapcount */ VM_BUG_ON_PAGE(tail > 2 && page_tail->mapping != TAIL_MAPPING,
mm/memcontrol.c +2 -0
@@ -5170,6 +5170,7 @@ static void __mem_cgroup_free(struct mem_cgroup *memcg)static void mem_cgroup_free (struct mem_cgroup *memcg) { +lru_gen_exit_memcg (memcg);memcg_wb_domain_exit (memcg);__mem_cgroup_free (memcg); }
@@ -5228,6 +5229,7 @@ static struct mem_cgroup *mem_cgroup_alloc(void) memcg->deferred_split_queue.split_queue_len =0 ;#endif idr_replace (&mem_cgroup_idr, memcg, memcg->id.id); +lru_gen_init_memcg (memcg);return memcg; fail:mem_cgroup_id_remove (memcg);
mm/memory.c +25 -0
@@ -5111,6 +5111,27 @@ static inline void mm_account_fault(struct pt_regs *regs,perf_sw_event (PERF_COUNT_SW_PAGE_FAULTS_MIN ,1 , regs, address); } +#ifdef CONFIG_LRU_GEN +static void lru_gen_enter_fault (struct vm_area_struct *vma) +{ +/* the LRU algorithm doesn't apply to sequential or random reads */ + current->in_lru_fault = !(vma->vm_flags & (VM_SEQ_READ |VM_RAND_READ )); +} + +static void lru_gen_exit_fault (void ) +{ + current->in_lru_fault = false; +} +#else +static void lru_gen_enter_fault (struct vm_area_struct *vma) +{ +} + +static void lru_gen_exit_fault (void ) +{ +} +#endif /* CONFIG_LRU_GEN */ +/* * By the time we get here, we already hold the mm semaphore *
@@ -5142,11 +5163,15 @@ vm_fault_t handle_mm_fault(struct vm_area_struct *vma, unsigned long address,if (flags &FAULT_FLAG_USER )mem_cgroup_enter_user_fault (); +lru_gen_enter_fault (vma); +if (unlikely (is_vm_hugetlb_page (vma))) ret =hugetlb_fault (vma->vm_mm, vma, address, flags);else ret =__handle_mm_fault (vma, address, flags); +lru_gen_exit_fault (); +if (flags &FAULT_FLAG_USER ) {mem_cgroup_exit_user_fault ();/*
mm/mm_init.c +4 -2
@@ -65,14 +65,16 @@ void __init mminit_verify_pageflags_layout(void) shift =8 *sizeof (unsigned long ); width = shift -SECTIONS_WIDTH -NODES_WIDTH -ZONES_WIDTH - -LAST_CPUPID_SHIFT -KASAN_TAG_WIDTH ; + -LAST_CPUPID_SHIFT -KASAN_TAG_WIDTH -LRU_GEN_WIDTH -LRU_REFS_WIDTH ;mminit_dprintk (MMINIT_TRACE ,"pageflags_layout_widths" , -"Section %d Node %d Zone %d Lastcpupid %d Kasantag %d Flags %d\n" , +"Section %d Node %d Zone %d Lastcpupid %d Kasantag %d Gen %d Tier %d Flags %d\n" ,SECTIONS_WIDTH ,NODES_WIDTH ,ZONES_WIDTH ,LAST_CPUPID_WIDTH ,KASAN_TAG_WIDTH , +LRU_GEN_WIDTH , +LRU_REFS_WIDTH ,NR_PAGEFLAGS ); mminit_dprintk(MMINIT_TRACE, "pageflags_layout_shifts", "Section %d Node %d Zone %d Lastcpupid %d Kasantag %d\n",
mm/mmzone.c +2 -0
@@ -88,6 +88,8 @@ void lruvec_init(struct lruvec *lruvec)* Poison its list head, so that any operations on it would crash. */ list_del (&lruvec->lists[LRU_UNEVICTABLE ]); + +lru_gen_init_lruvec (lruvec); }#if defined(CONFIG_NUMA_BALANCING ) && !defined(LAST_CPUPID_NOT_IN_PAGE_FLAGS )
mm/swap.c +8 -3
@@ -484,6 +484,11 @@ void folio_add_lru(struct folio *folio) folio_test_unevictable(folio), folio);VM_BUG_ON_FOLIO (folio_test_lru (folio), folio); +/* see the comment in lru_gen_add_folio() */ +if (lru_gen_enabled () && !folio_test_unevictable (folio) && +lru_gen_in_fault () && !(current->flags &PF_MEMALLOC )) +folio_set_active (folio); +folio_get (folio);local_lock (&cpu_fbatches.lock); fbatch =this_cpu_ptr (&cpu_fbatches.lru_add);
@@ -575,7 +580,7 @@ static void lru_deactivate_file_fn(struct lruvec *lruvec, struct folio *folio)static void lru_deactivate_fn (struct lruvec *lruvec,struct folio *folio) { -if (folio_test_active (folio) && !folio_test_unevictable (folio)) { +if (!folio_test_unevictable (folio) && (folio_test_active (folio) ||lru_gen_enabled ())) {long nr_pages =folio_nr_pages (folio);lruvec_del_folio (lruvec, folio);
@@ -688,8 +693,8 @@ void deactivate_page(struct page *page) {struct folio *folio =page_folio (page); -if (folio_test_lru (folio) &&folio_test_active (folio) && - !folio_test_unevictable (folio)) { +if (folio_test_lru (folio) && !folio_test_unevictable (folio) && + (folio_test_active (folio) ||lru_gen_enabled ())) {struct folio_batch *fbatch;folio_get (folio);
mm/vmscan.c +75 -0
81 lines not on this page · raw message
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
PATCH v14 6/14 mm: multi-gen LRU: minimal implementation
In reply to Yu ZhaoTo avoid confusion, the terms "promotion" and "demotion" will be applied to the multi-gen LRU, as a new convention; the terms "activation" and "deactivation" will be applied to the active/inactive LRU, as usual.
The aging produces young generations. Given an lruvec, it increments max_seq when max_seq-min_seq+1 approaches MIN_NR_GENS. The aging promotes hot pages to the youngest generation when it finds them accessed through page tables; the demotion of cold pages happens consequently when it increments max_seq. Promotion in the aging path does not involve any LRU list operations, only the updates of the gen counter and lrugen->nr_pages[]; demotion, unless as the result of the increment of max_seq, requires LRU list operations, e.g., lru_deactivate_fn(). The aging has the complexity O(nr_hot_pages), since it is only interested in hot pages.
The eviction consumes old generations. Given an lruvec, it increments min_seq when lrugen->lists[] indexed by min_seq%MAX_NR_GENS becomes empty. A feedback loop modeled after the PID controller monitors refaults over anon and file types and decides which type to evict when both types are available from the same generation.
The protection of pages accessed multiple times through file descriptors takes place in the eviction path. Each generation is divided into multiple tiers. A page accessed N times through file descriptors is in tier order_base_2(N). Tiers do not have dedicated lrugen->lists[], only bits in folio->flags. The aforementioned feedback loop also monitors refaults over all tiers and decides when to protect pages in which tiers (N>1), using the first tier (N=0,1) as a baseline. The first tier contains single-use unmapped clean pages, which are most likely the best choices. In contrast to promotion in the aging path, the protection of a page in the eviction path is achieved by moving this page to the next generation, i.e., min_seq+1, if the feedback loop decides so. This approach has the following advantages:
1. It removes the cost of activation in the buffered access path by inferring whether pages accessed multiple times through file descriptors are statistically hot and thus worth protecting in the eviction path.
2. It takes pages accessed through page tables into account and avoids overprotecting pages accessed multiple times through file descriptors. (Pages accessed through page tables are in the first tier, since N=0.)
3. More tiers provide better protection for pages accessed more than twice through file descriptors, when under heavy buffered I/O workloads.
Server benchmark results:
Single workload:
fio (buffered I/O): +[30, 32]%
IOPS BW
5.19-rc1: 2673k 10.2GiB/s
patch1-6: 3491k 13.3GiB/sSingle workload:
memcached (anon): -[4, 6]%
Ops/sec KB/sec
5.19-rc1: 1161501.04 45177.25
patch1-6: 1106168.46 43025.04Configurations:
CPU: two Xeon 6154
Mem: total 256G
Node 1 was only used as a ram disk to reduce the variance in the
results.
patch drivers/block/brd.c <<EOF
99,100c99,100
< gfp_flags = GFP_NOIO | __GFP_ZERO | __GFP_HIGHMEM;
< page = alloc_page(gfp_flags);
---
> gfp_flags = GFP_NOIO | __GFP_ZERO | __GFP_HIGHMEM | __GFP_THISNODE;
> page = alloc_pages_node(1, gfp_flags, 0);
EOF
cat >>/etc/systemd/system.conf <<EOF
CPUAffinity=numa
NUMAPolicy=bind
NUMAMask=0
EOF
cat >>/etc/memcached.conf <<EOF
-m 184320
-s /var/run/memcached/memcached.sock
-a 0766
-t 36
-B binary
EOF
cat fio.sh
modprobe brd rd_nr=1 rd_size=113246208
swapoff -a
mkfs.ext4 /dev/ram0
mount -t ext4 /dev/ram0 /mnt
mkdir /sys/fs/cgroup/user.slice/test
echo 38654705664 >/sys/fs/cgroup/user.slice/test/memory.max
echo $$ >/sys/fs/cgroup/user.slice/test/cgroup.procs
fio -name=mglru --numjobs=72 --directory=/mnt --size=1408m \
--buffered=1 --ioengine=io_uring --iodepth=128 \
--iodepth_batch_submit=32 --iodepth_batch_complete=32 \
--rw=randread --random_distribution=random --norandommap \
--time_based --ramp_time=10m --runtime=5m --group_reporting
cat memcached.sh
modprobe brd rd_nr=1 rd_size=113246208
swapoff -a
mkswap /dev/ram0
swapon /dev/ram0
memtier_benchmark -S /var/run/memcached/memcached.sock \
-P memcache_binary -n allkeys --key-minimum=1 \
--key-maximum=65000000 --key-pattern=P:P -c 1 -t 36 \
--ratio 1:0 --pipeline 8 -d 2000
memtier_benchmark -S /var/run/memcached/memcached.sock \
-P memcache_binary -n allkeys --key-minimum=1 \
--key-maximum=65000000 --key-pattern=R:R -c 1 -t 36 \
--ratio 0:1 --pipeline 8 --randomize --distinct-client-seedClient benchmark results:
kswapd profiles:
5.19-rc1
40.33% page_vma_mapped_walk (overhead)
21.80% lzo1x_1_do_compress (real work)
7.53% do_raw_spin_lock
3.95% _raw_spin_unlock_irq
2.52% vma_interval_tree_iter_next
2.37% folio_referenced_one
2.28% vma_interval_tree_subtree_search
1.97% anon_vma_interval_tree_iter_first
1.60% ptep_clear_flush
1.06% __zram_bvec_write
patch1-6
39.03% lzo1x_1_do_compress (real work)
18.47% page_vma_mapped_walk (overhead)
6.74% _raw_spin_unlock_irq
3.97% do_raw_spin_lock
2.49% ptep_clear_flush
2.48% anon_vma_interval_tree_iter_first
1.92% folio_referenced_one
1.88% __zram_bvec_write
1.48% memmove
1.31% vma_interval_tree_iter_next Configurations:
CPU: single Snapdragon 7c
Mem: total 4G
Chrome OS MemoryPressure [1]
[1] https://chromium.googlesource.com/chromiumos/platform/tast-tests/
--- include/linux/mm_inline.h | 36 ++ include/linux/mmzone.h | 41 ++ include/linux/page-flags-layout.h | 5 +- kernel/bounds.c | 2 + mm/Kconfig | 11 + mm/swap.c | 39 ++ mm/vmscan.c | 815 +++++++++++++++++++++++++++++- mm/workingset.c | 110 +++- 8 files changed, 1049 insertions(+), 10 deletions(-)
include/linux/mm_inline.h +36 -0
@@ -121,6 +121,33 @@ static inline int lru_gen_from_seq(unsigned long seq)return seq %MAX_NR_GENS ; } +static inline int lru_hist_from_seq (unsigned long seq) +{ +return seq %NR_HIST_GENS ; +} + +static inline int lru_tier_from_refs (int refs) +{ +VM_WARN_ON_ONCE (refs >BIT (LRU_REFS_WIDTH )); + +/* see the comment in folio_lru_refs() */ +return order_base_2 (refs +1 ); +} + +static inline int folio_lru_refs (struct folio *folio) +{ +unsigned long flags =READ_ONCE (folio->flags); +bool workingset = flags &BIT (PG_workingset); + +/* +* Return the number of accesses beyond PG_referenced, i.e., N-1 if the +* total number of accesses is N>1, since N=0,1 both map to the first +* tier. lru_tier_from_refs() will account for this off-by-one. Also see +* the comment on MAX_NR_TIERS. +*/ +return ((flags &LRU_REFS_MASK ) >>LRU_REFS_PGOFF ) + workingset; +} +static inline int folio_lru_gen (struct folio *folio) {unsigned long flags =READ_ONCE (folio->flags);
@@ -173,6 +200,15 @@ static inline void lru_gen_update_size(struct lruvec *lruvec, struct folio *foli__update_lru_size (lruvec, lru, zone, -delta);return ; } + +/* promotion */ +if (!lru_gen_is_active (lruvec, old_gen) &&lru_gen_is_active (lruvec, new_gen)) { +__update_lru_size (lruvec, lru, zone, -delta); +__update_lru_size (lruvec, lru +LRU_ACTIVE , zone, delta); + } + +/* demotion requires isolation, e.g., lru_deactivate_fn() */ +VM_WARN_ON_ONCE (lru_gen_is_active (lruvec, old_gen) && !lru_gen_is_active (lruvec, new_gen)); }static inline bool lru_gen_add_folio (struct lruvec *lruvec,struct folio *folio,bool reclaiming)
include/linux/mmzone.h +41 -0
59 lines not on this page · raw message
include/linux/page-flags-layout.h +4 -1
@@ -106,7 +106,10 @@#error "Not enough bits in page flags"#endif -#define LRU_REFS_WIDTH 0 +/* see the comment on MAX_NR_TIERS */ +#define LRU_REFS_WIDTH min(__LRU_REFS_WIDTH, BITS_PER_LONG - NR_PAGEFLAGS - \ + ZONES_WIDTH - LRU_GEN_WIDTH - SECTIONS_WIDTH - \ + NODES_WIDTH - KASAN_TAG_WIDTH - LAST_CPUPID_WIDTH)#endif #endif /* _LINUX_PAGE_FLAGS_LAYOUT */
kernel/bounds.c +2 -0
@@ -24,8 +24,10 @@ int main(void)DEFINE (SPINLOCK_SIZE ,sizeof (spinlock_t));#ifdef CONFIG_LRU_GEN DEFINE (LRU_GEN_WIDTH ,order_base_2 (MAX_NR_GENS +1 )); +DEFINE (__LRU_REFS_WIDTH,MAX_NR_TIERS -2 );#else DEFINE (LRU_GEN_WIDTH ,0 ); +DEFINE (__LRU_REFS_WIDTH,0 );#endif /* End of constants */
mm/Kconfig +11 -0
@@ -1124,6 +1124,7 @@ config PTE_MARKER_UFFD_WP purposes. It is required to enable userfaultfd write protection on file-backed memory types like shmem and hugetlbfs. +# multi-gen LRU { config LRU_GEN bool "Multi-Gen LRU" depends on MMU
@@ -1132,6 +1133,16 @@ config LRU_GEN help A high performance LRU implementation to overcommit memory. +config LRU_GEN_STATS + bool "Full stats for debugging" + depends on LRU_GEN + help + Do not enable this option unless you plan to look at historical stats + from evicted generations for debugging purpose. + + This option has a per-memcg and per-node memory overhead. +# } + source "mm/damon/Kconfig" endmenu
mm/swap.c +39 -0
@@ -428,6 +428,40 @@ static void __lru_cache_activate_folio(struct folio *folio)local_unlock (&cpu_fbatches.lock); } +#ifdef CONFIG_LRU_GEN +static void folio_inc_refs (struct folio *folio) +{ +unsigned long new_flags, old_flags =READ_ONCE (folio->flags); + +if (folio_test_unevictable (folio)) +return ; + +if (!folio_test_referenced (folio)) { +folio_set_referenced (folio); +return ; + } + +if (!folio_test_workingset (folio)) { +folio_set_workingset (folio); +return ; + } + +/* see the comment on MAX_NR_TIERS */ +do { + new_flags = old_flags &LRU_REFS_MASK ; +if (new_flags ==LRU_REFS_MASK ) +break ; + + new_flags +=BIT (LRU_REFS_PGOFF ); + new_flags |= old_flags & ~LRU_REFS_MASK ; + }while (!try_cmpxchg (&folio->flags, &old_flags, new_flags)); +} +#else +static void folio_inc_refs (struct folio *folio) +{ +} +#endif /* CONFIG_LRU_GEN */ +/* * Mark a page as having seen activity. *
@@ -440,6 +474,11 @@ static void __lru_cache_activate_folio(struct folio *folio)*/ void folio_mark_accessed (struct folio *folio) { +if (lru_gen_enabled ()) { +folio_inc_refs (folio); +return ; + } +if (!folio_test_referenced (folio)) {folio_set_referenced (folio); }else if (folio_test_unevictable (folio)) {
mm/vmscan.c +808 -7
877 lines not on this page · raw message
mm/workingset.c +108 -2
142 lines not on this page · raw message
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
PATCH v14 7/14 mm: multi-gen LRU: exploit locality in rmap
In reply to Yu ZhaoSearching the rmap for PTEs mapping each page on an LRU list (to test and clear the accessed bit) can be expensive because pages from different VMAs (PA space) are not cache friendly to the rmap (VA space). For workloads mostly using mapped pages, searching the rmap can incur the highest CPU cost in the reclaim path.
This patch exploits spatial locality to reduce the trips into the rmap. When shrink_page_list() walks the rmap and finds a young PTE, a new function lru_gen_look_around() scans at most BITS_PER_LONG-1 adjacent PTEs. On finding another young PTE, it clears the accessed bit and updates the gen counter of the page mapped by this PTE to (max_seq%MAX_NR_GENS)+1.
Server benchmark results:
Single workload:
fio (buffered I/O): no change
Single workload:
memcached (anon): +[3, 5]%
Ops/sec KB/sec
patch1-6: 1106168.46 43025.04
patch1-7: 1147696.57 44640.29 Configurations:
no change
Client benchmark results:
kswapd profiles:
patch1-6
39.03% lzo1x_1_do_compress (real work)
18.47% page_vma_mapped_walk (overhead)
6.74% _raw_spin_unlock_irq
3.97% do_raw_spin_lock
2.49% ptep_clear_flush
2.48% anon_vma_interval_tree_iter_first
1.92% folio_referenced_one
1.88% __zram_bvec_write
1.48% memmove
1.31% vma_interval_tree_iter_next
patch1-7
48.16% lzo1x_1_do_compress (real work)
8.20% page_vma_mapped_walk (overhead)
7.06% _raw_spin_unlock_irq
2.92% ptep_clear_flush
2.53% __zram_bvec_write
2.11% do_raw_spin_lock
2.02% memmove
1.93% lru_gen_look_around
1.56% free_unref_page_list
1.40% memset Configurations:
no change
--- include/linux/memcontrol.h | 31 +++++++ include/linux/mm.h | 5 + include/linux/mmzone.h | 6 ++ mm/internal.h | 1 + mm/memcontrol.c | 1 + mm/rmap.c | 6 ++ mm/swap.c | 4 +- mm/vmscan.c | 184 +++++++++++++++++++++++++++++++++++++ 8 files changed, 236 insertions(+), 2 deletions(-)
include/linux/memcontrol.h +31 -0
@@ -444,6 +444,7 @@ static inline struct obj_cgroup *__folio_objcg(struct folio *folio)* - LRU isolation * - lock_page_memcg() * - exclusive reference +* - mem_cgroup_trylock_pages() * * For a kmem folio a caller should hold an rcu read lock to protect memcg * associated with a kmem folio from being released.
@@ -505,6 +506,7 @@ static inline struct mem_cgroup *folio_memcg_rcu(struct folio *folio)* - LRU isolation * - lock_page_memcg() * - exclusive reference +* - mem_cgroup_trylock_pages() * * For a kmem page a caller should hold an rcu read lock to protect memcg * associated with a kmem page from being released.
@@ -959,6 +961,23 @@ void unlock_page_memcg(struct page *page);void __mod_memcg_state (struct mem_cgroup *memcg,int idx,int val); +/* try to stablize folio_memcg() for all the pages in a memcg */ +static inline bool mem_cgroup_trylock_pages (struct mem_cgroup *memcg) +{ +rcu_read_lock (); + +if (mem_cgroup_disabled () || !atomic_read (&memcg->moving_account)) +return true; + +rcu_read_unlock (); +return false; +} + +static inline void mem_cgroup_unlock_pages (void ) +{ +rcu_read_unlock (); +} +/* idx can be of type enum memcg_stat_item or node_stat_item */ static inline void mod_memcg_state (struct mem_cgroup *memcg,int idx,int val)
@@ -1422,6 +1441,18 @@ static inline void folio_memcg_unlock(struct folio *folio) { } +static inline bool mem_cgroup_trylock_pages (struct mem_cgroup *memcg) +{ +/* to match folio_memcg_rcu() */ +rcu_read_lock (); +return true; +} + +static inline void mem_cgroup_unlock_pages (void ) +{ +rcu_read_unlock (); +} +static inline void mem_cgroup_handle_over_high (void ) { }
include/linux/mm.h +5 -0
@@ -1490,6 +1490,11 @@ static inline unsigned long folio_pfn(struct folio *folio)return page_to_pfn (&folio->page); } +static inline struct folio *pfn_folio (unsigned long pfn) +{ +return page_folio (pfn_to_page (pfn)); +} +static inline atomic_t *folio_pincount_ptr (struct folio *folio) {return &folio_page (folio,1 )->compound_pincount;
include/linux/mmzone.h +6 -0
@@ -375,6 +375,7 @@ enum lruvec_flags {#ifndef __GENERATING_BOUNDS_Hstruct lruvec ; +struct page_vma_mapped_walk ;#define LRU_GEN_MASK ((BIT(LRU_GEN_WIDTH) - 1) << LRU_GEN_PGOFF)#define LRU_REFS_MASK ((BIT(LRU_REFS_WIDTH) - 1) << LRU_REFS_PGOFF)
@@ -430,6 +431,7 @@ struct lru_gen_struct { };void lru_gen_init_lruvec (struct lruvec *lruvec); +void lru_gen_look_around (struct page_vma_mapped_walk *pvmw);#ifdef CONFIG_MEMCG void lru_gen_init_memcg (struct mem_cgroup *memcg);
@@ -442,6 +444,10 @@ static inline void lru_gen_init_lruvec(struct lruvec *lruvec) { } +static inline void lru_gen_look_around (struct page_vma_mapped_walk *pvmw) +{ +} +#ifdef CONFIG_MEMCG static inline void lru_gen_init_memcg (struct mem_cgroup *memcg) {
mm/internal.h +1 -0
@@ -83,6 +83,7 @@ vm_fault_t do_swap_page(struct vm_fault *vmf);void folio_rotate_reclaimable (struct folio *folio);bool __folio_end_writeback (struct folio *folio);void deactivate_file_folio (struct folio *folio); +void folio_activate (struct folio *folio);void free_pgtables (struct mmu_gather *tlb,struct vm_area_struct *start_vma,unsigned long floor,unsigned long ceiling);
mm/memcontrol.c +1 -0
@@ -2789,6 +2789,7 @@ static void commit_charge(struct folio *folio, struct mem_cgroup *memcg)* - LRU isolation * - lock_page_memcg() * - exclusive reference +* - mem_cgroup_trylock_pages() */ folio->memcg_data = (unsigned long )memcg; }
mm/rmap.c +6 -0
@@ -825,6 +825,12 @@ static bool folio_referenced_one(struct folio *folio, }if (pvmw.pte) { +if (lru_gen_enabled () &&pte_young (*pvmw.pte) && + !(vma->vm_flags & (VM_SEQ_READ |VM_RAND_READ ))) { +lru_gen_look_around (&pvmw); + referenced++; + } +if (ptep_clear_flush_young_notify (vma, address, pvmw.pte)) {/*
mm/swap.c +2 -2
@@ -366,7 +366,7 @@ static void folio_activate_drain(int cpu)folio_batch_move_lru (fbatch, folio_activate_fn); } -static void folio_activate (struct folio *folio) +void folio_activate (struct folio *folio) {if (folio_test_lru (folio) && !folio_test_active (folio) && !folio_test_unevictable (folio)) {
@@ -385,7 +385,7 @@ static inline void folio_activate_drain(int cpu) { } -static void folio_activate (struct folio *folio) +void folio_activate (struct folio *folio) {struct lruvec *lruvec;
mm/vmscan.c +184 -0
220 lines not on this page · raw message
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
Re: [PATCH v14 07/14] mm: multi-gen LRU: exploit locality in rmap
Quoted 9 lines · Yu Zhao
Searching the rmap for PTEs mapping each page on an LRU list (to test and clear the accessed bit) can be expensive because pages from different VMAs (PA space) are not cache friendly to the rmap (VA space). For workloads mostly using mapped pages, searching the rmap can incur the highest CPU cost in the reclaim path.
Impressive work. Sorry if my feedback is not timely.
Just one minor point for thought, that can be left for a later cleanup.
Quoted 8 lines
mm/vmscan.c +7
-0+for (i =0 , addr = start; addr != end; i++, addr +=PAGE_SIZE ) { +unsigned long pfn; + + pfn =get_pte_pfn (pte[i], pvmw->vma, addr); +if (pfn ==-1 ) +continue ; +
mm/vmscan.c static void lru_gen_age_node(struct pglist_data *pgdat, struct scan_control *sc) · line 3578
Quoted 10 lines
mm/vmscan.c +10
-0+if (!pte_young (pte[i])) +continue ; + + folio =get_pfn_folio (pfn, memcg, pgdat); +if (!folio) +continue ; + +if (!ptep_test_and_clear_young (pvmw->vma, addr, pte + i)) +continue ; +
You have already checked that the PTE is old (not young), so this check seems redundant. I do not see a way in which the access-bit can be cleared since you hold the ptl. IOW, there is no need for the “if" and “continue".
Makes me also wonder whether having a separate ptep_clear_young() can slightly help, since anyhow the access-bit is more of an estimation, and having a separate ptep_clear_young() can enable optimizations.
On x86, for instance, if the PTE is dirty, we may be able to clear the access-bit without an atomic operation, which should be faster.
Re: [PATCH v14 07/14] mm: multi-gen LRU: exploit locality in rmap
Quoted 28 lines · Nadav Amit
Quoted 10 lines · Yu Zhao
Searching the rmap for PTEs mapping each page on an LRU list (to test and clear the accessed bit) can be expensive because pages from different VMAs (PA space) are not cache friendly to the rmap (VA space). For workloads mostly using mapped pages, searching the rmap can incur the highest CPU cost in the reclaim path.
Impressive work. Sorry if my feedback is not timely.
Just one minor point for thought, that can be left for a later cleanup.
Quoted 13 lines
mm/vmscan.c +12
-0+for (i =0 , addr = start; addr != end; i++, addr +=PAGE_SIZE ) { +unsigned long pfn; + + pfn =get_pte_pfn (pte[i], pvmw->vma, addr); +if (pfn ==-1 ) +continue ; + +if (!pte_young (pte[i])) +continue ; + + folio =get_pfn_folio (pfn, memcg, pgdat); +if (!folio)
Quoted 8 lines
mm/vmscan.c static void lru_gen_age_node(struct pglist_data *pgdat, struct scan_control *sc) · line 3578
Quoted 5 lines
mm/vmscan.c +5
-0+continue ; + +if (!ptep_test_and_clear_young (pvmw->vma, addr, pte + i)) +continue ; +You have already checked that the PTE is old (not young) so this check seems redundant.
You are right, for x86, which belongs to category 1: hardware and OS share the same paging data structure.
Quoted 2 lines
I do not see a way in which the access-bit can be cleared since you hold the ptl.
There is also category 2: the OS paging data structure is a shadow of what hardware actually uses, e.g., POWER9 radix.
To make both categories work, the general rule is that the OS paging data structure must be more strict, i.e., it can have A/D bits set while the hardware paging data structure may not. The opposite is not allowed, even for the A bit, because the A bit can also be used to determine whether a TLB flush is required. The Linux kernel doesn't do this but there are other OSes that do.
For prefaulted PTEs, we generally mark them young unless arch_wants_old_prefaulted_pte() returns true (currently only ARMv8.2+ do). On POWER9, we'd see those PTEs pass the first check but fail the second.
Quoted 8 lines
IOW, there is no need for the “if" and “continue".
Makes me also wonder whether having a separate
ptep_clear_young()can slightly help, since anyhow the access-bit is more of an estimation, and having a separateptep_clear_young()can enable optimizations.On x86, for instance, if the PTE is dirty, we may be able to clear the access-bit without an atomic operation, which should be faster.
Agreed.
Re: [PATCH v14 07/14] mm: multi-gen LRU: exploit locality in rmap
Quoted 7 lines · Yu Zhao
Quoted 5 lines · Nadav Amit
Quoted 5 lines · Yu Zhao
Quoted 7 lines
Quoted 7 lines
Quoted 5 lines
Searching the rmap for PTEs mapping each page on an LRU list (to test and clear the accessed bit) can be expensive because pages from different VMAs (PA space) are not cache friendly to the rmap (VA space). For workloads mostly using mapped pages, searching the rmap can incur the highest CPU cost in the reclaim path.
Impressive work.
Thanks.
Quoted 42 lines
Quoted 17 lines
Sorry if my feedback is not timely.
Just one minor point for thought, that can be left for a later cleanup.
Quoted 13 lines
mm/vmscan.c +12
-0+for (i =0 , addr = start; addr != end; i++, addr +=PAGE_SIZE ) { +unsigned long pfn; + + pfn =get_pte_pfn (pte[i], pvmw->vma, addr); +if (pfn ==-1 ) +continue ; + +if (!pte_young (pte[i])) +continue ; + + folio =get_pfn_folio (pfn, memcg, pgdat); +if (!folio)Quoted 8 lines
mm/vmscan.c static void lru_gen_age_node(struct pglist_data *pgdat, struct scan_control *sc) · line 3578
Quoted 5 lines
mm/vmscan.c +5
-0+continue ; + +if (!ptep_test_and_clear_young (pvmw->vma, addr, pte + i)) +continue ; +You have already checked that the PTE is old (not young) so this check seems redundant.
You are right, for x86, which belongs to category 1: hardware and OS share the same paging data structure.
Quoted 2 lines
I do not see a way in which the access-bit can be cleared since you hold the ptl.
There is also category 2: the OS paging data structure is a shadow of what hardware actually uses, e.g., POWER9 radix.
To make both categories work, the general rule is that the OS paging data structure must be more strict, i.e., it can have A/D bits set while the hardware paging data structure may not. The opposite is not allowed, even for the A bit, because the A bit can also be used to determine whether a TLB flush is required. The Linux kernel doesn't do this but there are other OSes that do.
Quoted 4 lines
For prefaulted PTEs, we generally mark them young unless
arch_wants_old_prefaulted_pte()returns true (currently only ARMv8.2+ do). On POWER9, we'd see those PTEs pass the first check but fail the second.
Because the first check (non-atomic) is allowed to fetch from the OS paging data structure (which is more strict) while the second check (atomic) must fetch from the hardware page data structure (which does not have the A bit because those PTEs are preffaulted).
Quoted 10 lines
Quoted 8 lines
IOW, there is no need for the “if" and “continue".
Makes me also wonder whether having a separate
ptep_clear_young()can slightly help, since anyhow the access-bit is more of an estimation, and having a separateptep_clear_young()can enable optimizations.On x86, for instance, if the PTE is dirty, we may be able to clear the access-bit without an atomic operation, which should be faster.
Agreed.
PATCH v14 8/14 mm: multi-gen LRU: support page table walks
In reply to Yu ZhaoTo further exploit spatial locality, the aging prefers to walk page tables to search for young PTEs and promote hot pages. A kill switch will be added in the next patch to disable this behavior. When disabled, the aging relies on the rmap only.
NB: this behavior has nothing similar with the page table scanning in the 2.4 kernel [1], which searches page tables for old PTEs, adds cold pages to swapcache and unmaps them.
To avoid confusion, the term "iteration" specifically means the traversal of an entire mm_struct list; the term "walk" will be applied to page tables and the rmap, as usual.
An mm_struct list is maintained for each memcg, and an mm_struct follows its owner task to the new memcg when this task is migrated. Given an lruvec, the aging iterates lruvec_memcg()->mm_list and calls walk_page_range() with each mm_struct on this list to promote hot pages before it increments max_seq.
When multiple page table walkers iterate the same list, each of them gets a unique mm_struct; therefore they can run concurrently. Page table walkers ignore any misplaced pages, e.g., if an mm_struct was migrated, pages it left in the previous memcg will not be promoted when its current memcg is under reclaim. Similarly, page table walkers will not promote pages from nodes other than the one under reclaim.
This patch uses the following optimizations when walking page tables:
1. It tracks the usage of mm_struct's between context switches so that page table walkers can skip processes that have been sleeping since the last iteration.
2. It uses generational Bloom filters to record populated branches so that page table walkers can reduce their search space based on the query results, e.g., to skip page tables containing mostly holes or misplaced pages.
3. It takes advantage of the accessed bit in non-leaf PMD entries when CONFIG_ARCH_HAS_NONLEAF_PMD_YOUNG=y.
4. It does not zigzag between a PGD table and the same PMD table spanning multiple VMAs. IOW, it finishes all the VMAs within the range of the same PMD table before it returns to a PGD table. This improves the cache performance for workloads that have large numbers of tiny VMAs [2], especially when CONFIG_PGTABLE_LEVELS=5.
Server benchmark results:
Single workload:
fio (buffered I/O): no change
Single workload:
memcached (anon): +[8, 10]%
Ops/sec KB/sec
patch1-7: 1147696.57 44640.29
patch1-8: 1245274.91 48435.66 Configurations:
no change
Client benchmark results:
kswapd profiles:
patch1-7
48.16% lzo1x_1_do_compress (real work)
8.20% page_vma_mapped_walk (overhead)
7.06% _raw_spin_unlock_irq
2.92% ptep_clear_flush
2.53% __zram_bvec_write
2.11% do_raw_spin_lock
2.02% memmove
1.93% lru_gen_look_around
1.56% free_unref_page_list
1.40% memset
patch1-8
49.44% lzo1x_1_do_compress (real work)
6.19% page_vma_mapped_walk (overhead)
5.97% _raw_spin_unlock_irq
3.13% get_pfn_folio
2.85% ptep_clear_flush
2.42% __zram_bvec_write
2.08% do_raw_spin_lock
1.92% memmove
1.44% alloc_zspage
1.36% memset Configurations:
no change
Thanks to the following developers for their efforts [3].
kernel test robot <[email protected]>
[1] https://lwn.net/Articles/23732/
[2] https://llvm.org/docs/ScudoHardenedAllocator.html
[3] https://lore.kernel.org/r/[email protected]/
--- fs/exec.c | 2 + include/linux/memcontrol.h | 5 + include/linux/mm_types.h | 77 +++ include/linux/mmzone.h | 56 +- include/linux/swap.h | 4 + kernel/exit.c | 1 + kernel/fork.c | 9 + kernel/sched/core.c | 1 + mm/memcontrol.c | 25 + mm/vmscan.c | 1012 +++++++++++++++++++++++++++++++++++- 10 files changed, 1175 insertions(+), 17 deletions(-)
fs/exec.c +2 -0
@@ -1014,6 +1014,7 @@ static int exec_mmap(struct mm_struct *mm) active_mm = tsk->active_mm; tsk->active_mm = mm; tsk->mm = mm; +lru_gen_add_mm (mm);/* * This prevents preemption while active_mm is being loaded and * it and mm are being updated, which could cause problems for
@@ -1029,6 +1030,7 @@ static int exec_mmap(struct mm_struct *mm) tsk->mm->vmacache_seqnum =0 ;vmacache_flush (tsk);task_unlock (tsk); +lru_gen_use_mm (mm);if (vfork)timens_on_fork (tsk->nsproxy, tsk);
include/linux/memcontrol.h +5 -0
@@ -350,6 +350,11 @@ struct mem_cgroup {struct deferred_split deferred_split_queue;#endif +#ifdef CONFIG_LRU_GEN +/* per-memcg mm_struct list */ +struct lru_gen_mm_list mm_list; +#endif +struct mem_cgroup_per_node *nodeinfo[]; };
include/linux/mm_types.h +77 -0
101 lines not on this page · raw message
include/linux/mmzone.h +55 -1
80 lines not on this page · raw message
include/linux/swap.h +4 -0
@@ -162,6 +162,10 @@ union swap_header {*/ struct reclaim_state {unsigned long reclaimed_slab; +#ifdef CONFIG_LRU_GEN +/* per-thread mm walk data */ +struct lru_gen_mm_walk *mm_walk; +#endif };#ifdef __KERNEL__
kernel/exit.c +1 -0
@@ -466,6 +466,7 @@ void mm_update_next_owner(struct mm_struct *mm) goto retry; }WRITE_ONCE (mm->owner, c); +lru_gen_migrate_mm (mm);task_unlock (c);put_task_struct (c); }
kernel/fork.c +9 -0
@@ -1152,6 +1152,7 @@ static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p, goto fail_nocontext; mm->user_ns =get_user_ns (user_ns); +lru_gen_init_mm (mm);return mm; fail_nocontext:
@@ -1194,6 +1195,7 @@ static inline void __mmput(struct mm_struct *mm) }if (mm->binfmt)module_put (mm->binfmt->module); +lru_gen_del_mm (mm);mmdrop (mm); }
@@ -2694,6 +2696,13 @@ pid_t kernel_clone(struct kernel_clone_args *args)get_task_struct (p); } +if (IS_ENABLED (CONFIG_LRU_GEN ) && !(clone_flags &CLONE_VM )) { +/* lock the task to synchronize with memcg migration */ +task_lock (p); +lru_gen_add_mm (p->mm); +task_unlock (p); + } +wake_up_new_task (p);/* forking complete and child started to run, tell ptracer */
kernel/sched/core.c +1 -0
@@ -5180,6 +5180,7 @@ context_switch(struct rq *rq, struct task_struct *prev,* finish_task_switch()'s mmdrop(). */ switch_mm_irqs_off (prev->active_mm, next->mm, next); +lru_gen_use_mm (next->mm);if (!prev->mm) {// from kernel /* will mmdrop() in finish_task_switch(). */
mm/memcontrol.c +25 -0
@@ -6199,6 +6199,30 @@ static void mem_cgroup_move_task(void) }#endif +#ifdef CONFIG_LRU_GEN +static void mem_cgroup_attach (struct cgroup_taskset *tset) +{ +struct task_struct *task; +struct cgroup_subsys_state *css; + +/* find the first leader if there is any */ +cgroup_taskset_for_each_leader (task, css, tset) +break ; + +if (!task) +return ; + +task_lock (task); +if (task->mm && task->mm->owner == task) +lru_gen_migrate_mm (task->mm); +task_unlock (task); +} +#else +static void mem_cgroup_attach (struct cgroup_taskset *tset) +{ +} +#endif /* CONFIG_LRU_GEN */ +static int seq_puts_memcg_tunable (struct seq_file *m,unsigned long value) {if (value ==PAGE_COUNTER_MAX )
@@ -6604,6 +6628,7 @@ struct cgroup_subsys memory_cgrp_subsys = { .css_reset = mem_cgroup_css_reset, .css_rstat_flush = mem_cgroup_css_rstat_flush, .can_attach = mem_cgroup_can_attach, + .attach = mem_cgroup_attach, .cancel_attach = mem_cgroup_cancel_attach, .post_attach = mem_cgroup_move_task, .dfl_cftypes = memory_files,
mm/vmscan.c +996 -16
1,196 lines not on this page · raw message
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
Peter Zijlstra
maintainerRe: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
mm/vmscan.c static struct folio *get_pfn_folio(unsigned long pfn, struct mem_cgroup *memcg, · line 4010
Quoted 5 lines · Yu Zhao
mm/vmscan.c +5
-0+for (i =pmd_index (start), addr = start; addr != end; i++, addr = next) { +pmd_t val =pmd_read_atomic (pmd + i); + +/* for pmd_read_atomic() */ +barrier ();
Please clarify the above. This is an entirely inadequate ordering comment.
Quoted 2 lines
mm/vmscan.c +2
-0+ + next =pmd_addr_end (addr, end);
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
Quoted 10 lines · Peter Zijlstra
mm/vmscan.c static struct folio *get_pfn_folio(unsigned long pfn, struct mem_cgroup *memcg, · line 4010
Quoted 5 lines · Yu Zhao
mm/vmscan.c +5
-0+for (i =pmd_index (start), addr = start; addr != end; i++, addr = next) { +pmd_t val =pmd_read_atomic (pmd + i); + +/* for pmd_read_atomic() */ +barrier ();Please clarify the above. This is an entirely inadequate ordering comment.
If it's acceptable, I'll copy what we have inpmd_none_or_clear_bad_unless_trans_huge():
pmd_t pmdval = pmd_read_atomic(pmd);
/* See pmd_none_or_trans_huge_or_clear_bad for info on barrier */
#ifdef CONFIG_TRANSPARENT_HUGEPAGE
barrier();#endif
if (pmd_none(pmdval))
return 1;pmd_read_atomic() should have a built-in READ_ONCE() in the first place. If we have to use pmd_read_atomic(), it means we are not under PMD PTL. So we can also race with pte_alloc(), regardless of THP split. In this case, compiler reordering probably won't cause any real damage, but technically not having barrier() is still a bug and will trigger KCSAN warnings, I think.
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
Quoted 3 lines · Yu Zhao
pmd_read_atomic()should have a built-inREAD_ONCE()in the first place.
I really think that is the right thing to do. Let's just move the barrier in *there* instead.
It really should use 'READ_ONCE()', but it sadly cannot do that portably, because 'pmd_t' may be a multi-word structure.
Of course, the x86-32 code does this all *almost* right, and implements its own version of pmd_read_atomic(), but then sadly does it _without_ actually using READ_ONCE() there.
So even when we could do it right, we don't.
But the x86-32 implementation of pmd_read_atomic() would be trivial to fix to just use READ_ATOMIC, and the generic implementation should just have a "barrier()" in it so that we wouldn't need crazy barriers in the users.
Because as you say, the function is already called "read_atomic", and it should damn well *act* that way then.
Hmm?
Linus
Peter Zijlstra
maintainerRe: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
Quoted 2 lines · Linus Torvalds
Because as you say, the function is already called "
read_atomic", and it should damn well *act* that way then.
So I've been sitting on these here patches (and never having time to repost them), which is how I noticed in the first place:
https://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git/log/?h=x86/mm.pae
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
Quoted 10 lines · Peter Zijlstra
Quoted 2 lines · Linus Torvalds
Because as you say, the function is already called "
read_atomic", and it should damn well *act* that way then.So I've been sitting on these here patches (and never having time to repost them), which is how I noticed in the first place:
https://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git/log/?h=x86/mm.pae
This looks good to me. It'll help get rid of all those open-coded barrier()s and fix a couple of missing barrier()s.
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
In reply to Peter ZijlstraQuoted 5 lines · Peter Zijlstra
So I've been sitting on these here patches (and never having time to repost them), which is how I noticed in the first place:
https://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git/log/?h=x86/mm.pae
Well, that seems an improvement. I don't love how GUP_GET_PTE_LOW_HIGH now affects the PMD too, but if it's ok for all the three users, I guess it's ok. Maybe rename it now that it's not just the PTE?
That said, I reacted to that cmpxchg loop:
} while (cmpxchg64(&pmdp->pmd, old.pmd, 0ULL) != old.pmd);
is this series just so old (but rebased) that it doesn't use "try_cmpxchg64()"?
Linus
Peter Zijlstra
maintainerRe: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
Quoted 11 lines · Linus Torvalds
Quoted 5 lines · Peter Zijlstra
So I've been sitting on these here patches (and never having time to repost them), which is how I noticed in the first place:
https://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git/log/?h=x86/mm.pae
Well, that seems an improvement. I don't love how
GUP_GET_PTE_LOW_HIGHnow affects the PMD too, but if it's ok for all the three users, I guess it's ok. Maybe rename it now that it's not just the PTE?
Quoted 5 lines
That said, I reacted to that cmpxchg loop:
} while (cmpxchg64(&pmdp->pmd, old.pmd, 0ULL) != old.pmd);is this series just so old (but rebased) that it doesn't use "
try_cmpxchg64()"?
Yep -- it's *that* old :-/ You're not in fact the first to point that out.
I'll make time tomorrow to fix it up and respin and send out. This is as good a time as any to get rid of carrying these patches myself.
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
Quoted 6 lines · Peter Zijlstra
Quoted 4 lines · Linus Torvalds
That said, I reacted to that cmpxchg loop:
} while (cmpxchg64(&pmdp->pmd, old.pmd, 0ULL) != old.pmd);
Quoted 7 lines
Quoted 1 line
is this series just so old (but rebased) that it doesn't use "
try_cmpxchg64()"?Yep -- it's *that* old :-/ You're not in fact the first to point that out.
I'll make time tomorrow to fix it up and respin and send out. This is as good a time as any to get rid of carrying these patches myself.
Hmm. Thinking some more about it, even if you do it as a try_cmpxchg64() loop, it ends up being duplicated twice.
Maybe we should just bite the bullet, and say that we only support x86-32 with 'cmpxchg8b' (ie Pentium and later).
Get rid of all the "emulate 64-bit atomics with cli/sti, knowing that nobody has SMP on those CPU's anyway", and implement a generic x86-32 xchg() setup using that try_cmpxchg64 loop.
I think most (all?) distros already enable X86_PAE anyway, which makes that X86_CMPXCHG64 be part of the base requirement.
Not that I'm convinced most distros even do 32-bit development anyway these days.
(Of course, if we require X86_CMPXCHG64, we'll also hit some of the odd clone CPU's that actually *do* support the instruction, but do not report it in cpuid due to an odd old Windows NT bug. IOW, things like the Cyrix and Transmeta CPU's did support the instruction, but had the CX8 bit clear because otherwise NT wouldn't boot. We may or may not get those cases right, but I doubt anybody really has any of those old CPUs).
We got rid of i386 support back in 2012. Maybe it's time to get rid of i486 support in 2022?
That way we could finally get rid of CONFIG_MATH_EMULATION too.
Linus
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
Quoted 21 lines · Linus Torvalds
Maybe we should just bite the bullet, and say that we only support x86-32 with 'cmpxchg8b' (ie Pentium and later).
Get rid of all the "emulate 64-bit atomics with cli/sti, knowing that nobody has SMP on those CPU's anyway", and implement a generic x86-32
xchg()setup using thattry_cmpxchg64loop.I think most (all?) distros already enable
X86_PAEanyway, which makes thatX86_CMPXCHG64be part of the base requirement.Not that I'm convinced most distros even do 32-bit development anyway these days.
(Of course, if we require
X86_CMPXCHG64, we'll also hit some of the odd clone CPU's that actually *do* support the instruction, but do not report it in cpuid due to an odd old Windows NT bug. IOW, things like the Cyrix and Transmeta CPU's did support the instruction, but had the CX8 bit clear because otherwise NT wouldn't boot. We may or may not get those cases right, but I doubt anybody really has any of those old CPUs).
Quoted 2 lines
We got rid of i386 support back in 2012. Maybe it's time to get rid of i486 support in 2022?
Arnd suggested removing i486 last year and got a bit of pushback. The most convincing to my mind was Maciej:
https://lore.kernel.org/lkml/[email protected]/
but you can see a few other responses indicating that people have shipped new 486-class hardware within the last few years (!)
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
Quoted 8 lines · Matthew Wilcox
Quoted 3 lines · Linus Torvalds
We got rid of i386 support back in 2012. Maybe it's time to get rid of i486 support in 2022?
Arnd suggested removing i486 last year and got a bit of pushback. The most convincing to my mind was Maciej:
Hmm. Maciej added to the cc.
I suspect we can just say "oh, well, use LTS kernels".
Quoted 2 lines
but you can see a few other responses indicating that people have shipped new 486-class hardware within the last few years (!)
Hmm.. I can only find references to PC104 boards with Bay Trail (Pentium-class Atom core, iirc), and some possible FPGA implementations through MISTer.
There's apparently also a Vortex86DX board too, and I don't know what core that is based off, but judging from the fact that it has a dual-core version, it had *better* support cmpxchg8b anyway, because without that our 64-bit atomics aren't actually atomic.
(Trying to google around, it looks like the older Vortex86SX was a 486-class CPU and did indeed lack CX8)
Intel had some embedded cores (Quark) that were based on the i486 pipeline (as can be seen from the timings), but they actually reported themselves as Pentium-class and supported all the classic (pre-MMX) Pentium features.
So I *really* don't think i486 class hardware is relevant any more. Yes, I'm sure it exists (Maciej being an example), but from a kernel development standpoint I don't think they are really relevant.
At some point, people have them as museum pieces. They might as well run museum kernels.
Moving up to requiring cmpxchg8b doesn't sound unreasonable to me.
Linus
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
Le 22/10/22 à 00:50, Linus Torvalds a écrit :
Quoted 10 lines · Matthew Wilcox
Quoted 5 lines · Linus Torvalds
Quoted 2 lines
We got rid of i386 support back in 2012. Maybe it's time to get rid of i486 support in 2022?
Arnd suggested removing i486 last year and got a bit of pushback. The most convincing to my mind was Maciej:
Hmm. Maciej added to the cc.
I suspect we can just say "oh, well, use LTS kernels".
To jump in early on the inevitable pile-on, I'm doing my occasional 32-bit x86 KUnit test runs on an old 486 DX/2. Now, this is _mostly_ just a party trick -- and there are lots of people running 32-bit builds under QEMU et al -- but personally, the only non-amd64-capable x86 machines I have lying around are all 486 class (including a new Vortex86 board).
(But, at the very least, I can confirm that the latest torvalds/master does build, run, and pass KUnit tests on a real 486 at the moment.)
So while dropping i486 wouldn't affect anything particularly important for me, it'd be a minor inconvenience and make me a bit sad.
That being said, I have no objection to dropping support for 486SX CPUs and CONFIG_MATH_EMULATION.
Cheers,
-- David
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
In reply to Linus TorvaldsQuoted 7 lines · Linus Torvalds
Quoted 5 lines
Quoted 2 lines
We got rid of i386 support back in 2012. Maybe it's time to get rid of i486 support in 2022?
Arnd suggested removing i486 last year and got a bit of pushback. The most convincing to my mind was Maciej:
Hmm. Maciej added to the cc.
Thanks!
Quoted 8 lines
So I *really* don't think i486 class hardware is relevant any more. Yes, I'm sure it exists (Maciej being an example), but from a kernel development standpoint I don't think they are really relevant.
At some point, people have them as museum pieces. They might as well run museum kernels.
Moving up to requiring cmpxchg8b doesn't sound unreasonable to me.
But is it really a problem? I mean unlike MIPS R2000/R3000 class gear
that has no atomics at all at the CPU level (SMP R3000 machines did exist and necessarily had atomics, actually via gating storage implemented by board hardware in systems we have never had support for even for UP) we have had atomics in x86 since forever. Just not 64-bit ones.
Given the presence of generic atomics we can emulate CMPXCHG8B easily
LL/SC-style using a spinlock with XCHG even on SMP let alone UP. So all the kernel code can just assume the presence of CMPXCHG8B, but any invocations of CMPXCHG8B would be diverted to the emulation, perhaps even at the assembly level via a GAS macro called `cmpxchg8b' (why not?). All the maintenance burden is then shifted to that macro and said emulation code.
Proof of concept wrapper:
#define LOCK_PREFIX ""
#define CC_SET(c) "\n\t/* output condition code " #c "*/\n" #define CC_OUT(c) "=@cc" #c
#define unlikely(x) __builtin_expect(!!(x), 0)
__extension__ typedef unsigned long long __u64;
typedef unsigned int __u32;
typedef __u64 u64;
typedef __u32 u32;
typedef _Bool bool;
__asm__(
".macro cmpxchg8b arg\n\t" "pushl %eax\n\t" "leal \\arg, %eax\n\t" "xchgl %eax, (%esp)\n\t" "call cmpxchg8b_emu\n\t" ".endm\n\t");
bool __try_cmpxchg64(volatile u64 *ptr, u64 *pold, u64 new)
{
bool success;
u64 old = *pold;
asm volatile(LOCK_PREFIX "cmpxchg8b %[ptr]"
CC_SET(z)
: CC_OUT(z) (success),
[ptr] "+m" (*ptr),
"+A" (old)
: "b" ((u32)new),
"c" ((u32)(new >> 32))
: "memory");
if (unlikely(!success))
*pold = old;
return success;
}This assembles to:
cmpxchg8b.o: file format elf32-i386
Disassembly of section .text:
00000000 <__try_cmpxchg64>:
0: 55 push %ebp 1: 89 e5 mov %esp,%ebp 3: 57 push %edi 4: 56 push %esi 5: 89 d7 mov %edx,%edi 7: 53 push %ebx 8: 89 c6 mov %eax,%esi a: 8b 4d 0c mov 0xc(%ebp),%ecx d: 8b 02 mov (%edx),%eax f: 8b 5d 08 mov 0x8(%ebp),%ebx 12: 8b 52 04 mov 0x4(%edx),%edx 15: 50 push %eax 16: 8d 06 lea (%esi),%eax 18: 87 04 24 xchg %eax,(%esp) 1b: e8 fc ff ff ff call 1c <__try_cmpxchg64+0x1c> 1c: R_386_PC32 cmpxchg8b_emu 20: 0f 94 c1 sete %cl 23: 75 0b jne 30 <__try_cmpxchg64+0x30> 25: 5b pop %ebx 26: 88 c8 mov %cl,%al 28: 5e pop %esi 29: 5f pop %edi 2a: 5d pop %ebp 2b: c3 ret 2c: 8d 74 26 00 lea 0x0(%esi,%eiz,1),%esi 30: 5b pop %ebx 31: 89 07 mov %eax,(%edi) 33: 5e pop %esi 34: 89 57 04 mov %edx,0x4(%edi) 37: 5f pop %edi 38: 88 c8 mov %cl,%al 3a: 5d pop %ebp 3b: c3 ret
Of course there's a minor ABI nit for cmpxchg8b_emu' to return a result in ZF and the wrapper relies on CONFIG_FRAME_POINTER for correct arg' evaluation in all cases. But that shouldn't be a big deal, should it?
Then long-term maintenance would be minimal to nil and all the code
except for the wrapper and the emulation handler need not be concerned about the 486 obscurity. I can volunteer to maintain said wrapper and emulation (and for that matter generic 486 support) if that helped to keep the 486 alive.
Eventually we may choose to drop 486 support after all, but CMPXCHG8B
alone seems too small a reason to me for that to happen right now.
NB MIPS R2000 dates back to 1985, solid 4 years before the 486, and we
continue supporting it with minimal effort. We do have atomic emulation for userland of course.
Maciej
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
Quoted 3 lines · Maciej W. Rozycki
Given the presence of generic atomics we can emulate CMPXCHG8B easily
LL/SC-style using a spinlock with XCHG even on SMP let alone UP.
We already do that (admittedly badly - it's not SMP safe, but 486-class SMP machines have never been supported even if they technically did exist), see
arch/x86/lib/cmpxchg8b_emu.S
arch/x86/lib/atomic64_386_32.S
for some pretty disgusting code.
But it's all the other infrastructure to support this that is just an unnecessary weight. Grep for CONFIG_X86_CMPXCHG64 and X86_FEATURE_CX8.
We already have increasingly bad coverage testing for x86-32 - and your example of MIPS really doesn't strengthen your argument all that much, because MIPS has never been very widely used in the first place, and doesn't affect any mainline development.
The odd features and CPU selection really do not help.
Honestly, I wouldn't mind upgrading the minimum requirements to at least M586TSC - leaving some of those early "fake Pentium" clones behind too. Because 'rdtsc' is probably an even worse issue than CMPXCHG8B.
In fact, I don't understand how current kernels work on an i486 at all, since it looks like
exit_to_user_mode_prepare ->
arch_exit_to_user_mode_prepare
ends up having an unconditional 'rdtsc' instruction in it.
I'm guessing that you don't have RANDOMIZE_KSTACK_OFFSET enabled?
In other words, our non-Pentium support is ACTIVELY BUGGY AND BROKEN right now.
This is not some theoretical issue, but very much a "look, ma, this has never been tested, and cannot actually work" issue, that nobody has ever noticed because nobody really cares.
It took me a couple of minutes of "let's go hunting" to find that thing, and it's just an example of how broken our current support is. That RANDOMIZE_KSTACK_OFFSET code *compiles* just fine. It just doesn't actually work.
That's the kind of maintenance burden we simply shouldn't have - no developer actually cares (correctly), nobody really tests that situation (also correctly - it's old and irrelevant hardware), but it also means that code just randomly doesn't actually work.
Linus
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
Quoted 5 lines · Linus Torvalds
Honestly, I wouldn't mind upgrading the minimum requirements to at least M586TSC - leaving some of those early "fake Pentium" clones behind too. Because 'rdtsc' is probably an even worse issue than CMPXCHG8B.
Kconfig treats X86_CMPXCHG64 as a strict subset of X86_TSC (except when enabling X86_PAE, which relies on cx8), so requiring both sounds like a good idea.
From the Kconfig history, I see you initially only enabled cx8 unconditionally for a couple of CPUs in 982d007a6eec ("x86:
Optimize cmpxchg64() at build-time some more"), and Matthew Whitehead extended that list in f960cfd12650 ("x86/Kconfig:
Add missing i586-class CPUs to the X86_CMPXCHG64 Kconfig group").
There are still a handful of CPUs that according to [1] claim cx8 support that we leave disabled, specifically the Kconfig symbols for MWINCHIP3D, MCRUSOE, MEFFICEON, MCYRIXIII, MVIAC3_2 and MVIAC7 should have both tsc and cx8, while the older MWINCHIPC6 and a small subset of M586 (Cyrix 6x86mx, C-II and AMD K5) apparently have cx8 but not tsc.
Would you drop support for the 686-class chips that currently don't use cmpxchg8b, or just remove CONFIG_X86_CMPXCHG64 and assume they work after all?
Arnd
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
In reply to Linus TorvaldsQuoted 11 lines · Linus Torvalds
Quoted 2 lines
Given the presence of generic atomics we can emulate CMPXCHG8B easily
LL/SC-style using a spinlock with XCHG even on SMP let alone UP.We already do that (admittedly badly - it's not SMP safe, but 486-class SMP machines have never been supported even if they technically did exist), see
arch/x86/lib/cmpxchg8b_emu.S
arch/x86/lib/atomic64_386_32.Sfor some pretty disgusting code.
I skimmed over these, yeah, before writing my previous reply and hence
my proposal to make the approach somewhat less disgusting.
FWIW Intel talks about 486 SMP systems in their MP spec, but even back 25
years ago I was unable to track down a single mention of a product name for an APIC-based 486 SMP system let alone a specimen. I guess the MP spec and the APIC simply came too late in the game for the 486.
Compaq did however make 486 SMP systems based on their proprietary
solution (I can't remember the name offhand), which they also propagated to their later Pentium products, some of which could be switched into the APIC mode instead via a BIOS setting. ISTR a 16-way brand new Xeon box still using the Compaq solution in early 2000s. Compaq never bothered to publish the spec for their solution and nobody was determined enough to reverse-engineer it, so we never had support for it.
Quoted 2 lines
But it's all the other infrastructure to support this that is just an unnecessary weight. Grep for
CONFIG_X86_CMPXCHG64andX86_FEATURE_CX8.
Some of these are syntactic sugar really, but I agree there seem to be
too many of them and I guess even that perhaps could be simplified at the expense of some performance loss with 486 systems, by assuming universal presence of CMPXCHG8B and emulating the instruction in #UD handler where unavailable. I could live with that, and that could get away with no conditionals (except maybe one to have the emulation handler optimised away where not needed based on a single CONFIG_X86_CMPXCHG64 instance).
Quoted 4 lines
We already have increasingly bad coverage testing for x86-32 - and your example of MIPS really doesn't strengthen your argument all that much, because MIPS has never been very widely used in the first place, and doesn't affect any mainline development.
TBH by the number of pieces of hardware I am fairly sure there have been
significantly more MIPS Linux deployments in the world than x86 ones, and second only to ARM ones, though indeed the diversity of configurations may have been smaller. And all of them seem to have survived having ancient MIPS CPU support alongside.
Quoted 10 lines
The odd features and CPU selection really do not help.
Honestly, I wouldn't mind upgrading the minimum requirements to at least M586TSC - leaving some of those early "fake Pentium" clones behind too. Because 'rdtsc' is probably an even worse issue than CMPXCHG8B.
In fact, I don't understand how current kernels work on an i486 at all, since it looks like
Quoted 6 lines
exit_to_user_mode_prepare->
arch_exit_to_user_mode_prepareends up having an unconditional 'rdtsc' instruction in it.
I'm guessing that you don't have
RANDOMIZE_KSTACK_OFFSETenabled?
I have checked and I have not moved past 5.11.0 yet for my 486 box, and
that's before the addition of RANDOMIZE_KSTACK_OFFSET.
Sigh, time flies by and there's been too much breakage around for me to
deal with to schedule an upgrade of what has been mostly a stable trouble-free configuration for me. E.g. after three unrelated bug fixes the parport_pc driver still does not work with my RISC-V box, and that's of course only once I figured out how to work around a hardware erratum with a pair of upstream PCIe switches that let the PCIe parallel port option card to be reachable in the first place. So I gave those issues priority over upgrading the 486 kernel, though obviously I'll get to it sooner or later.
The fix here is obviously and trivially:
select HAVE_ARCH_RANDOMIZE_KSTACK_OFFSET if !M486SX && !M486
Not all features have to be available everywhere and there are compromises to make. I can live with my 486 box being less secure: I don't intend to hand out accounts to people I don't trust or run a web server there.
I don't know offhand how much we rely on RDTSC and if necessary how much
a trivial emulation referring to jiffies plus maybe reading the 8254 PIT counter would suck. Maybe it's not a big deal. Again, it all depends on the application.
NB I have seen this in the logs appearing since a while ago with my dual
Pentium-MMX box:
clocksource: timekeeping watchdog on CPU0: Marking clocksource 'tsc-early' as unstable because the skew is too large: clocksource: 'refined-jiffies' wd_nsec: 500000000 wd_now:ffff8b3e wd_last: ffff8b0c mask: ffffffff clocksource: 'tsc-early' cs_nsec: 829966007 cs_now: 6049e0005 cs_last: 5f91b3cff mask: ffffffffffffffff clocksource: No current clocksource. tsc: Marking TSC unstable due to clocksource watchdog
so I guess this system would qualify as one without RDTSC too (even though it's M586MMX, i.e. a superset of M586TSC, so hardly early "fake Pentium"), right? It's interesting to see how we can't (anymore) make use of any of the various timers this system has (i.e. the PIT, the TSC, the APIC timer) for timekeeping.
Quoted 2 lines
In other words, our non-Pentium support is ACTIVELY BUGGY AND BROKEN right now.
We have plenty of bugs elsewhere too. I hit them all the time and try to
fix as my time permits; I guess other people do too. I think it's just a matter of willing to deal with issues. And we won't ever fix all the bugs we have. There will always be some remaining even if the exact set changes.
Quoted 3 lines
This is not some theoretical issue, but very much a "look, ma, this has never been tested, and cannot actually work" issue, that nobody has ever noticed because nobody really cares.
Same with parport_pc on RISC-V. That just happens with more rarely used
features, even if it's brand new hardware (I bought both pieces new in retail boxes last year or so).
Quoted 4 lines
It took me a couple of minutes of "let's go hunting" to find that thing, and it's just an example of how broken our current support is. That
RANDOMIZE_KSTACK_OFFSETcode *compiles* just fine. It just doesn't actually work.
Nobody tried it, and that's just it. We may have bots building random
configs, but not all will ever be tried at run time. Bugs creep in all the time, because nobody has the ability to foresee all the scenarios, or sometimes they are genuine human errors.
Quoted 4 lines
That's the kind of maintenance burden we simply shouldn't have - no developer actually cares (correctly), nobody really tests that situation (also correctly - it's old and irrelevant hardware), but it also means that code just randomly doesn't actually work.
I think this is a strawman's argument really. For various reasons there
are always combinations of hardware that do not work just because one cannot verify everything and the age of hardware may or may not be the culprit. It's more about the user base. Niche use gets less coverage. If something doesn't work and someone actually cares about it, they will come and fix it.
The only argument I buy is extra maintenance burden caused *elsewhere*,
so if support for old 486 systems staying around causes extra work for mainstream x86-64 systems, only then I will consider it a valid concern.
So what's the actual burden from keeping this support around? Would my
proposal to emulate CMPXCHG8B (and possibly RDTSC) in #UD handler help?
Getting the decoding of x86 address modes in software right is a pain and
tedious (I've seen fixes to get the corner cases right in the disassembler in binutils fly by quite recently, after so many years), but I guess we can try if we don't have it implemented already for another purpose (I haven't checked; I've been hardly involved with x86 recently).
Thoughts?
Maciej
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
Quoted 5 lines · Maciej W. Rozycki
Quoted 3 lines · Linus Torvalds
In fact, I don't understand how current kernels work on an i486 at all, since it looks like
Quoted 8 lines
Quoted 5 lines
exit_to_user_mode_prepare->
arch_exit_to_user_mode_prepareends up having an unconditional 'rdtsc' instruction in it.
Quoted 1 line
The fix here is obviously and trivially:
select HAVE_ARCH_RANDOMIZE_KSTACK_OFFSET if !M486SX && !M486
I think that would be "if X86_TSC", otherwise you still include the TSC-less 586-class (5x86, 6x86, Elan, Winchip C6, MediaGX, ...)
Quoted 2 lines
So what's the actual burden from keeping this support around? Would my proposal to emulate CMPXCHG8B (and possibly RDTSC) in #UD handler help?
That sounds worse to me than the current use of runtime alternatives for picking between cmpxchg8b_emu and the native instruction.
For arm32, we have a combination of two other approaches:
- On the oldest processors that never had SMP support (ARMv5 and earlier), it is not possible to enable support for SMP at all. Using a Kconfig 'depends on X86_CMPXCHG64' for CONFIG_SMP would still allow building 486 kernels, but completely avoid the problem of trying to make the same kernel work on later SMP machines.
- For the special case of early ARMv6 hardware that has 32-bit atomics but not 64-bit ones, the kernel just falls back to CONFIG_GENERIC_ATOMIC64 and no cmpxchg64(). The same should work for an i486+SMP kernel. It's obviously slower, but most users can trivially avoid this by either running an i686 SMP kernel or an i486 UP kernel.
Arnd
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
Quoted 6 lines · Arnd Bergmann
Quoted 6 lines
Quoted 6 lines
In fact, I don't understand how current kernels work on an i486 at all, since it looks like
exit_to_user_mode_prepare->
arch_exit_to_user_mode_prepare
Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
ends up having an unconditional 'rdtsc' instruction in it.
Quoted 1 line
The fix here is obviously and trivially:
select HAVE_ARCH_RANDOMIZE_KSTACK_OFFSET if !M486SX && !M486I think that would be "if
X86_TSC", otherwise you still include the TSC-less 586-class (5x86, 6x86, Elan, Winchip C6, MediaGX, ...)
Right, I tend to forget about these more exotic chips from the 1990s era.
I'll run some verification and come up with the actual fix in the next several days.
Quoted 5 lines
Quoted 2 lines
So what's the actual burden from keeping this support around? Would my proposal to emulate CMPXCHG8B (and possibly RDTSC) in #UD handler help?
That sounds worse to me than the current use of runtime alternatives for picking between
cmpxchg8b_emuand the native instruction.
Why is that so? Because of the trap-and-emulate technique? It's been
around since forever and specified in some processor ISAs even, where some machine instructions are explicitly allowed to be omitted from actual hardware and delegated to OS emulation without making affected hardware non-compliant. VAX had it back from 1970s and RISC-V has it now. We've been using it to retrofit operations ourselves, though maybe not with the x86 arch.
Or is it because of the complex address decoding x86 requires? Well, I
have actually realised we do have it already, in the x87 CR0.EM emulator. While IEEE-754 exceptions can make use of the address of the operand recorded in the FPU environment full emulation requires decoding by hand.
Quoted 7 lines
For arm32, we have a combination of two other approaches:
- On the oldest processors that never had SMP support (ARMv5 and earlier), it is not possible to enable support for SMP at all. Using a
Kconfig'depends onX86_CMPXCHG64' forCONFIG_SMPwould still allow building 486 kernels, but completely avoid the problem of trying to make the same kernel work on later SMP machines.
That would be fine with me of course.
Quoted 6 lines
- For the special case of early ARMv6 hardware that has 32-bit atomics but not 64-bit ones, the kernel just falls back to
CONFIG_GENERIC_ATOMIC64and nocmpxchg64(). The same should work for an i486+SMP kernel. It's obviously slower, but most users can trivially avoid this by either running an i686 SMP kernel or an i486 UP kernel.
You meant an M586TSC+ SMP kernel presumably (I have such a machine), but
otherwise I'd be fine with such an approach too.
So it looks to me like we have at least three options to keep 486 alive,
two of which seem fairly straightforward to deploy and maintain long-term. I like your last proposal the most, FWIW. Do we have a consensus here?
Maciej
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
Quoted 11 lines · Maciej W. Rozycki
Quoted 6 lines · Arnd Bergmann
- For the special case of early ARMv6 hardware that has 32-bit atomics but not 64-bit ones, the kernel just falls back to
CONFIG_GENERIC_ATOMIC64and nocmpxchg64(). The same should work for an i486+SMP kernel. It's obviously slower, but most users can trivially avoid this by either running an i686 SMP kernel or an i486 UP kernel.You meant an M586TSC+ SMP kernel presumably (I have such a machine), but
otherwise I'd be fine with such an approach too.
Sure. I just gave i686 as the example since that's already the baseline in 90% of the remaining x86-32 distros. Slackware, ALT and Mageia are notable exceptions that target i586, and some others already have separate installers for i486 and i686. The i586 distros all seem to have separate SMP/PAE kernels in addition to the minimal i586.
Arnd
Peter Zijlstra
maintainerRe: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
In reply to Linus TorvaldsQuoted 21 lines · Linus Torvalds
Maybe we should just bite the bullet, and say that we only support x86-32 with 'cmpxchg8b' (ie Pentium and later).
Get rid of all the "emulate 64-bit atomics with cli/sti, knowing that nobody has SMP on those CPU's anyway", and implement a generic x86-32
xchg()setup using thattry_cmpxchg64loop.I think most (all?) distros already enable
X86_PAEanyway, which makes thatX86_CMPXCHG64be part of the base requirement.Not that I'm convinced most distros even do 32-bit development anyway these days.
(Of course, if we require
X86_CMPXCHG64, we'll also hit some of the odd clone CPU's that actually *do* support the instruction, but do not report it in cpuid due to an odd old Windows NT bug. IOW, things like the Cyrix and Transmeta CPU's did support the instruction, but had the CX8 bit clear because otherwise NT wouldn't boot. We may or may not get those cases right, but I doubt anybody really has any of those old CPUs).
Quoted 4 lines
We got rid of i386 support back in 2012. Maybe it's time to get rid of i486 support in 2022?
That way we could finally get rid of
CONFIG_MATH_EMULATIONtoo.
Would love that; but as pointed out, there's still a few stragglers out there. OTOH, they *could* use one of the LTS kernels.
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
In reply to Linus TorvaldsAs someone who still regularly uses hardware from this era, and often runs Linux on it, this would definitely be a blow to which machines I can actively use. Linux support is a big part of how I use these machines, since DOS and Windows 95 really can’t keep up with modern networking standards.
I would be very disappointed, and impacted, if Linux dropped 486 support.
Quoted 43 lines · Linus Torvalds
Quoted 11 lines · Peter Zijlstra
Quoted 5 lines · Linus Torvalds
That said, I reacted to that cmpxchg loop:
} while (cmpxchg64(&pmdp->pmd, old.pmd, 0ULL) != old.pmd);is this series just so old (but rebased) that it doesn't use "
try_cmpxchg64()"?Yep -- it's *that* old :-/ You're not in fact the first to point that out.
I'll make time tomorrow to fix it up and respin and send out. This is as good a time as any to get rid of carrying these patches myself.
Hmm. Thinking some more about it, even if you do it as a
try_cmpxchg64()loop, it ends up being duplicated twice.Maybe we should just bite the bullet, and say that we only support x86-32 with 'cmpxchg8b' (ie Pentium and later).
Get rid of all the "emulate 64-bit atomics with cli/sti, knowing that nobody has SMP on those CPU's anyway", and implement a generic x86-32
xchg()setup using thattry_cmpxchg64loop.I think most (all?) distros already enable
X86_PAEanyway, which makes thatX86_CMPXCHG64be part of the base requirement.Not that I'm convinced most distros even do 32-bit development anyway these days.
(Of course, if we require
X86_CMPXCHG64, we'll also hit some of the odd clone CPU's that actually *do* support the instruction, but do not report it in cpuid due to an odd old Windows NT bug. IOW, things like the Cyrix and Transmeta CPU's did support the instruction, but had the CX8 bit clear because otherwise NT wouldn't boot. We may or may not get those cases right, but I doubt anybody really has any of those old CPUs).We got rid of i386 support back in 2012. Maybe it's time to get rid of i486 support in 2022?
That way we could finally get rid of
CONFIG_MATH_EMULATIONtoo.Linus
Re: [PATCH v14 08/14] mm: multi-gen LRU: support page table walks
In reply to Linus TorvaldsTrying sending again since I am not sure if it went through the first time. I’m not used to the mailing list.
As someone who still regularly uses hardware from this era, and often runs Linux on it, this would definitely be a blow to which machines I can actively use. Linux support is a big part of how I use these machines, since I usually have them connected to my LAN and the internet, and networking support on MS-DOS and Windows 9x rots more each year in terms of support for modern protocols and security. I would be very disappointed, and impacted, if Linux dropped 486 support.
PATCH v14 9/14 mm: multi-gen LRU: optimize multiple memcgs
In reply to Yu ZhaoWhen multiple memcgs are available, it is possible to make better choices based on generations and tiers and therefore improve the overall performance under global memory pressure. This patch adds a rudimentary optimization to select memcgs that can drop single-use unmapped clean pages first. Doing so reduces the chance of going into the aging path or swapping. These two decisions can be costly.
A typical example that benefits from this optimization is a server running mixed types of workloads, e.g., heavy anon workload in one memcg and heavy buffered I/O workload in the other.
Though this optimization can be applied to both kswapd and direct reclaim, it is only added to kswapd to keep the patchset manageable. Later improvements will cover the direct reclaim path.
Server benchmark results:
Mixed workloads:
fio (buffered I/O): +[19, 21]%
IOPS BW
patch1-8: 1880k 7343MiB/s
patch1-9: 2252k 8796MiB/s
memcached (anon): +[119, 123]%
Ops/sec KB/sec
patch1-8: 862768.65 33514.68
patch1-9: 1911022.12 74234.54Mixed workloads:
fio (buffered I/O): +[75, 77]%
IOPS BW
5.19-rc1: 1279k 4996MiB/s
patch1-9: 2252k 8796MiB/s
memcached (anon): +[13, 15]%
Ops/sec KB/sec
5.19-rc1: 1673524.04 65008.87
patch1-9: 1911022.12 74234.54Configurations:
(changes since patch 6)
cat mixed.sh
modprobe brd rd_nr=2 rd_size=56623104
swapoff -a
mkswap /dev/ram0
swapon /dev/ram0
mkfs.ext4 /dev/ram1
mount -t ext4 /dev/ram1 /mnt
memtier_benchmark -S /var/run/memcached/memcached.sock \
-P memcache_binary -n allkeys --key-minimum=1 \
--key-maximum=50000000 --key-pattern=P:P -c 1 -t 36 \
--ratio 1:0 --pipeline 8 -d 2000
fio -name=mglru --numjobs=36 --directory=/mnt --size=1408m \
--buffered=1 --ioengine=io_uring --iodepth=128 \
--iodepth_batch_submit=32 --iodepth_batch_complete=32 \
--rw=randread --random_distribution=random --norandommap \
--time_based --ramp_time=10m --runtime=90m --group_reporting &
pid=$!
sleep 200
memtier_benchmark -S /var/run/memcached/memcached.sock \
-P memcache_binary -n allkeys --key-minimum=1 \
--key-maximum=50000000 --key-pattern=R:R -c 1 -t 36 \
--ratio 0:1 --pipeline 8 --randomize --distinct-client-seed
kill -INT $pid
waitClient benchmark results:
no change (CONFIG_MEMCG=n)
--- mm/vmscan.c | 55 ++++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 46 insertions(+), 9 deletions(-)
mm/vmscan.c +46 -9
@@ -131,6 +131,13 @@ struct scan_control {/* Always discard instead of demoting to lower tier memory */ unsigned int no_demotion:1; +#ifdef CONFIG_LRU_GEN +/* help make better choices when multiple memcgs are available */ + unsigned int memcgs_need_aging:1; + unsigned int memcgs_need_swapping:1; + unsigned int memcgs_avoid_swapping:1; +#endif +/* Allocation order */ s8 order;
@@ -4437,6 +4444,22 @@ static void lru_gen_age_node(struct pglist_data *pgdat, struct scan_control *sc)VM_WARN_ON_ONCE (!current_is_kswapd ()); +/* +* To reduce the chance of going into the aging path or swapping, which +* can be costly, optimistically skip them unless their corresponding +* flags were cleared in the eviction path. This improves the overall +* performance when multiple memcgs are available. +*/ +if (!sc->memcgs_need_aging) { + sc->memcgs_need_aging = true; + sc->memcgs_avoid_swapping = !sc->memcgs_need_swapping; + sc->memcgs_need_swapping = true; +return ; + } + + sc->memcgs_need_swapping = true; + sc->memcgs_avoid_swapping = true; +set_mm_walk (pgdat); memcg =mem_cgroup_iter (NULL ,NULL ,NULL );
@@ -4846,7 +4869,8 @@ static int isolate_folios(struct lruvec *lruvec, struct scan_control *sc, int swreturn scanned; } -static int evict_folios (struct lruvec *lruvec,struct scan_control *sc,int swappiness) +static int evict_folios (struct lruvec *lruvec,struct scan_control *sc,int swappiness, +bool *need_swapping) {int type;int scanned;
@@ -4909,6 +4933,9 @@ static int evict_folios(struct lruvec *lruvec, struct scan_control *sc, int swap sc->nr_reclaimed += reclaimed; +if (type ==LRU_GEN_ANON && need_swapping) + *need_swapping = true; +return scanned; }
@@ -4918,10 +4945,9 @@ static int evict_folios(struct lruvec *lruvec, struct scan_control *sc, int swap* reclaim. */ static unsigned long get_nr_to_scan (struct lruvec *lruvec,struct scan_control *sc, -bool can_swap,unsigned long reclaimed) +bool can_swap,unsigned long reclaimed,bool *need_aging) {int priority; -bool need_aging;unsigned long nr_to_scan;struct mem_cgroup *memcg =lruvec_memcg (lruvec);DEFINE_MAX_SEQ (lruvec);
@@ -4936,7 +4962,7 @@ static unsigned long get_nr_to_scan(struct lruvec *lruvec, struct scan_control * (mem_cgroup_below_low(memcg) && !sc->memcg_low_reclaim))return 0 ; - nr_to_scan =get_nr_evictable (lruvec, max_seq, min_seq, can_swap, &need_aging); + nr_to_scan =get_nr_evictable (lruvec, max_seq, min_seq, can_swap, need_aging);if (!nr_to_scan)return 0 ;
@@ -4952,7 +4978,7 @@ static unsigned long get_nr_to_scan(struct lruvec *lruvec, struct scan_control *if (!nr_to_scan)return 0 ; -if (!need_aging) +if (!*need_aging)return nr_to_scan;/* skip the aging path at the default priority */
@@ -4972,6 +4998,8 @@ static unsigned long get_nr_to_scan(struct lruvec *lruvec, struct scan_control *static void lru_gen_shrink_lruvec (struct lruvec *lruvec,struct scan_control *sc) {struct blk_plug plug; +bool need_aging = false; +bool need_swapping = false;unsigned long scanned =0 ;unsigned long reclaimed = sc->nr_reclaimed;
@@ -4993,21 +5021,30 @@ static void lru_gen_shrink_lruvec(struct lruvec *lruvec, struct scan_control *scelse swappiness =0 ; - nr_to_scan =get_nr_to_scan (lruvec, sc, swappiness, reclaimed); + nr_to_scan =get_nr_to_scan (lruvec, sc, swappiness, reclaimed, &need_aging);if (!nr_to_scan) -break ; + goto done; - delta =evict_folios (lruvec, sc, swappiness); + delta =evict_folios (lruvec, sc, swappiness, &need_swapping);if (!delta) -break ; + goto done; scanned += delta;if (scanned >= nr_to_scan)break ; +if (sc->memcgs_avoid_swapping && swappiness <200 && need_swapping) +break ; +cond_resched (); } +/* see the comment in lru_gen_age_node() */ +if (!need_aging) + sc->memcgs_need_aging = false; +if (!need_swapping) + sc->memcgs_need_swapping = false; +done:clear_mm_walk ();blk_finish_plug (&plug);
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
PATCH v14 10/14 mm: multi-gen LRU: kill switch
In reply to Yu ZhaoAdd /sys/kernel/mm/lru_gen/enabled as a kill switch. Components that can be disabled include:
0x0001: the multi-gen LRU core
0x0002: walking page table, when arch_has_hw_pte_young() returns
true
0x0004: clearing the accessed bit in non-leaf PMD entries, when
CONFIG_ARCH_HAS_NONLEAF_PMD_YOUNG=y
[yYnN]: apply to all the components above
E.g.,
echo y >/sys/kernel/mm/lru_gen/enabled
cat /sys/kernel/mm/lru_gen/enabled
0x0007
echo 5 >/sys/kernel/mm/lru_gen/enabled
cat /sys/kernel/mm/lru_gen/enabled
0x0005
NB: the page table walks happen on the scale of seconds under heavy memory pressure, in which case the mmap_lock contention is a lesser concern, compared with the LRU lock contention and the I/O congestion. So far the only well-known case of the mmap_lock contention happens on Android, due to Scudo [1] which allocates several thousand VMAs for merely a few hundred MBs. The SPF and the Maple Tree also have provided their own assessments [2][3]. However, if walking page tables does worsen the mmap_lock contention, the kill switch can be used to disable it. In this case the multi-gen LRU will suffer a minor performance degradation, as shown previously.
Clearing the accessed bit in non-leaf PMD entries can also be disabled, since this behavior was not tested on x86 varieties other than Intel and AMD.
[1] https://source.android.com/devices/tech/debug/scudo
[2] https://lore.kernel.org/r/[email protected]/
[3] https://lore.kernel.org/r/[email protected]/
--- include/linux/cgroup.h | 15 ++- include/linux/mm_inline.h | 15 ++- include/linux/mmzone.h | 9 ++ kernel/cgroup/cgroup-internal.h | 1 - mm/Kconfig | 6 + mm/vmscan.c | 231 +++++++++++++++++++++++++++++++- 6 files changed, 268 insertions(+), 9 deletions(-)
include/linux/cgroup.h +14 -1
@@ -432,6 +432,18 @@ static inline void cgroup_put(struct cgroup *cgrp)css_put (&cgrp->self); } +extern struct mutex cgroup_mutex; + +static inline void cgroup_lock (void ) +{ +mutex_lock (&cgroup_mutex); +} + +static inline void cgroup_unlock (void ) +{ +mutex_unlock (&cgroup_mutex); +} +/** * task_css_set_check - obtain a task's css_set with extra access conditions * @task: the task to obtain css_set for
@@ -446,7 +458,6 @@ static inline void cgroup_put(struct cgroup *cgrp)* as locks used during the cgroup_subsys::attach() methods. */ #ifdef CONFIG_PROVE_RCU -extern struct mutex cgroup_mutex;extern spinlock_t css_set_lock;#define task_css_set_check (task, __c) \ rcu_dereference_check((task)->cgroups, \
@@ -708,6 +719,8 @@ struct cgroup;static inline u64 cgroup_id (const struct cgroup *cgrp) {return 1 ; }static inline void css_get (struct cgroup_subsys_state *css) {}static inline void css_put (struct cgroup_subsys_state *css) {} +static inline void cgroup_lock (void ) {} +static inline void cgroup_unlock (void ) {}static inline int cgroup_attach_task_all (struct task_struct *from,struct task_struct *t) {return 0 ; } static inline int cgroupstats_build(struct cgroupstats *stats,
include/linux/mm_inline.h +13 -2
@@ -106,10 +106,21 @@ static __always_inline enum lru_list folio_lru_list(struct folio *folio)#ifdef CONFIG_LRU_GEN +#ifdef CONFIG_LRU_GEN_ENABLED static inline bool lru_gen_enabled (void ) { -return true; +DECLARE_STATIC_KEY_TRUE (lru_gen_caps[NR_LRU_GEN_CAPS ]); + +return static_branch_likely (&lru_gen_caps[LRU_GEN_CORE ]); } +#else +static inline bool lru_gen_enabled (void ) +{ +DECLARE_STATIC_KEY_FALSE (lru_gen_caps[NR_LRU_GEN_CAPS ]); + +return static_branch_unlikely (&lru_gen_caps[LRU_GEN_CORE ]); +} +#endif static inline bool lru_gen_in_fault (void ) {
@@ -222,7 +233,7 @@ static inline bool lru_gen_add_folio(struct lruvec *lruvec, struct folio *folio,VM_WARN_ON_ONCE_FOLIO (gen !=-1 , folio); -if (folio_test_unevictable (folio)) +if (folio_test_unevictable (folio) || !lrugen->enabled)return false;/* * There are three common cases for this page:
include/linux/mmzone.h +9 -0
@@ -387,6 +387,13 @@ enum { LRU_GEN_FILE, }; +enum { +LRU_GEN_CORE , +LRU_GEN_MM_WALK , +LRU_GEN_NONLEAF_YOUNG , +NR_LRU_GEN_CAPS +}; +#define MIN_LRU_BATCH BITS_PER_LONG#define MAX_LRU_BATCH (MIN_LRU_BATCH * 128)
@@ -428,6 +435,8 @@ struct lru_gen_struct {/* can be modified without holding the LRU lock */ atomic_long_t evicted[NR_HIST_GENS ][ANON_AND_FILE ][MAX_NR_TIERS ];atomic_long_t refaulted[NR_HIST_GENS ][ANON_AND_FILE ][MAX_NR_TIERS ]; +/* whether the multi-gen LRU is enabled */ +bool enabled; };enum {
kernel/cgroup/cgroup-internal.h +0 -1
@@ -164,7 +164,6 @@ struct cgroup_mgctx {#define DEFINE_CGROUP_MGCTX (name) \ struct cgroup_mgctx name = CGROUP_MGCTX_INIT(name) -extern struct mutex cgroup_mutex;extern spinlock_t css_set_lock;extern struct cgroup_subsys *cgroup_subsys[];extern struct list_head cgroup_roots;
mm/Kconfig +6 -0
@@ -1133,6 +1133,12 @@ config LRU_GEN help A high performance LRU implementation to overcommit memory. +config LRU_GEN_ENABLED + bool "Enable by default" + depends on LRU_GEN + help + This option enables the multi-gen LRU by default. + config LRU_GEN_STATS bool "Full stats for debugging" depends on LRU_GEN
mm/vmscan.c +226 -5
280 lines not on this page · raw message
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
PATCH v14 11/14 mm: multi-gen LRU: thrashing prevention
In reply to Yu ZhaoAdd /sys/kernel/mm/lru_gen/min_ttl_ms for thrashing prevention, as requested by many desktop users [1].
When set to value N, it prevents the working set of N milliseconds from getting evicted. The OOM killer is triggered if this working set cannot be kept in memory. Based on the average human detectable lag (~100ms), N=1000 usually eliminates intolerable lags due to thrashing. Larger values like N=3000 make lags less noticeable at the risk of premature OOM kills.
Compared with the size-based approach [2], this time-based approach has the following advantages:
1. It is easier to configure because it is agnostic to applications and memory sizes.
2. It is more reliable because it is directly wired to the OOM killer.
[1] https://lore.kernel.org/r/Ydza%[email protected]/
[2] https://lore.kernel.org/r/[email protected]/
--- include/linux/mmzone.h | 2 ++ mm/vmscan.c | 75 +++++++++++++++++++++++++++++++++++++++--- 2 files changed, 73 insertions(+), 4 deletions(-)
include/linux/mmzone.h +2 -0
@@ -422,6 +422,8 @@ struct lru_gen_struct {unsigned long max_seq;/* the eviction increments the oldest generation numbers */ unsigned long min_seq[ANON_AND_FILE ]; +/* the birth time of each generation in jiffies */ +unsigned long timestamps[MAX_NR_GENS ];/* the multi-gen LRU lists, lazily sorted on eviction */ struct list_head lists[MAX_NR_GENS ][ANON_AND_FILE ][MAX_NR_ZONES ];/* the multi-gen LRU sizes, eventually consistent */
mm/vmscan.c +71 -4
141 lines not on this page · raw message
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
PATCH v14 12/14 mm: multi-gen LRU: debugfs interface
In reply to Yu ZhaoAdd /sys/kernel/debug/lru_gen for working set estimation and proactive reclaim. These techniques are commonly used to optimize job scheduling (bin packing) in data centers [1][2].
Compared with the page table-based approach and the PFN-based approach, this lruvec-based approach has the following advantages:
1. It offers better choices because it is aware of memcgs, NUMA nodes, shared mappings and unmapped page cache.
2. It is more scalable because it is O(nr_hot_pages), whereas the PFN-based approach is O(nr_total_pages).
Add /sys/kernel/debug/lru_gen_full for debugging.
[1] https://dl.acm.org/doi/10.1145/3297858.3304053
[2] https://dl.acm.org/doi/10.1145/3503222.3507731
--- include/linux/nodemask.h | 1 + mm/vmscan.c | 411 ++++++++++++++++++++++++++++++++++++++- 2 files changed, 402 insertions(+), 10 deletions(-)
include/linux/nodemask.h +1 -0
@@ -493,6 +493,7 @@ static inline int num_node_state(enum node_states state)#define first_online_node 0#define first_memory_node 0#define next_online_node (nid) (MAX_NUMNODES) +#define next_memory_node (nid) (MAX_NUMNODES)#define nr_node_ids 1U#define nr_online_nodes 1U
mm/vmscan.c +401 -10
489 lines not on this page · raw message
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
PATCH v14 13/14 mm: multi-gen LRU: admin guide
In reply to Yu ZhaoAdd an admin guide.
--- Documentation/admin-guide/mm/index.rst | 1 + Documentation/admin-guide/mm/multigen_lru.rst | 156 ++++++++++++++++++ mm/Kconfig | 3 +- mm/vmscan.c | 4 + 4 files changed, 163 insertions(+), 1 deletion(-) create mode 100644 Documentation/admin-guide/mm/multigen_lru.rst
Documentation/admin-guide/mm/index.rst +1 -0
@@ -32,6 +32,7 @@ the Linux memory management. idle_page_tracking ksm memory-hotplug + multigen_lru nommu-mmap numa_memory_policy numaperf
Documentation/admin-guide/mm/multigen_lru.rst new file +156 -0
156 lines not on this page · raw message
mm/Kconfig +2 -1
@@ -1131,7 +1131,8 @@ config LRU_GEN # make sure folio->flags has enough spare bits depends on 64BIT || !SPARSEMEM || SPARSEMEM_VMEMMAP help - A high performance LRU implementation to overcommit memory. + A high performance LRU implementation to overcommit memory. See + Documentation/admin-guide/mm/multigen_lru.rst for details. config LRU_GEN_ENABLED bool "Enable by default"
mm/vmscan.c +4 -0
@@ -5288,6 +5288,7 @@ static ssize_t show_min_ttl(struct kobject *kobj, struct kobj_attribute *attr, creturn sprintf (buf,"%u\n" ,jiffies_to_msecs (READ_ONCE (lru_gen_min_ttl))); } +/* see Documentation/admin-guide/mm/multigen_lru.rst for details */ static ssize_t store_min_ttl (struct kobject *kobj,struct kobj_attribute *attr,const char *buf,size_t len) {
@@ -5321,6 +5322,7 @@ static ssize_t show_enabled(struct kobject *kobj, struct kobj_attribute *attr, creturn snprintf (buf,PAGE_SIZE ,"0x%04x\n" , caps); } +/* see Documentation/admin-guide/mm/multigen_lru.rst for details */ static ssize_t store_enabled (struct kobject *kobj,struct kobj_attribute *attr,const char *buf,size_t len) {
@@ -5468,6 +5470,7 @@ static void lru_gen_seq_show_full(struct seq_file *m, struct lruvec *lruvec,seq_putc (m,'\n' ); } +/* see Documentation/admin-guide/mm/multigen_lru.rst for details */ static int lru_gen_seq_show (struct seq_file *m,void *v) {unsigned long seq;
@@ -5626,6 +5629,7 @@ static int run_cmd(char cmd, int memcg_id, int nid, unsigned long seq,return err; } +/* see Documentation/admin-guide/mm/multigen_lru.rst for details */ static ssize_t lru_gen_seq_write (struct file *file,const char __user *src,size_t len,loff_t *pos) {
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
Re: [PATCH v14 13/14] mm: multi-gen LRU: admin guide
Quoted 15 lines · Yu Zhao
Add an admin guide.
Signed-off-by Yu Zhao <[email protected]>Acked-by Brian Geffon <[email protected]>Acked-by Steven Barrett <[email protected]>Acked-by Suleiman Souhlal <[email protected]>Tested-by Daniel Byrne <[email protected]>Tested-by Donald Carr <[email protected]>Tested-by Holger Hoffstätte <[email protected]>Tested-by Konstantin Kharlamov <[email protected]>Tested-by Shuang Zhai <[email protected]>Tested-by Sofia Trinh <[email protected]>Tested-by Vaibhav Jain <[email protected]>
LGTM to me (no new warnings).
Signature · 1 line
An old man doll... just what I always wanted! - Clara
Re: [PATCH v14 13/14] mm: multi-gen LRU: admin guide
In reply to Yu ZhaoQuoted 15 lines · Yu Zhao
Add an admin guide.
Signed-off-by Yu Zhao <[email protected]>Acked-by Brian Geffon <[email protected]>Acked-by Steven Barrett <[email protected]>Acked-by Suleiman Souhlal <[email protected]>Tested-by Daniel Byrne <[email protected]>Tested-by Donald Carr <[email protected]>Tested-by Holger Hoffstätte <[email protected]>Tested-by Konstantin Kharlamov <[email protected]>Tested-by Shuang Zhai <[email protected]>Tested-by Sofia Trinh <[email protected]>Tested-by Vaibhav Jain <[email protected]>
A few formatting nits below, otherwise
Quoted 139 lines
--- Documentation/admin-guide/mm/index.rst | 1 + Documentation/admin-guide/mm/multigen_lru.rst | 156 ++++++++++++++++++ mm/Kconfig | 3 +- mm/vmscan.c | 4 + 4 files changed, 163 insertions(+), 1 deletion(-) create mode 100644 Documentation/admin-guide/mm/multigen_lru.rstDocumentation/admin-guide/mm/index.rst +1
-0@@ -32,6 +32,7 @@ the Linux memory management. idle_page_tracking ksm memory-hotplug + multigen_lru nommu-mmap numa_memory_policy numaperfDocumentation/admin-guide/mm/multigen_lru.rst new file +113
-0@@ -0,0 +1,156 @@ +.. SPDX-License-Identifier: GPL-2.0 + +============= +Multi-Gen LRU +============= +The multi-gen LRU is an alternative LRU implementation that optimizes +page reclaim and improves performance under memory pressure. Page +reclaim decides the kernel's caching policy and ability to overcommit +memory. It directly impacts the kswapd CPU usage and RAM efficiency. + +Quick start +=========== +Build the kernel with the following configurations. + +* ``CONFIG_LRU_GEN=y`` +* ``CONFIG_LRU_GEN_ENABLED=y`` + +All set! + +Runtime options +=============== +``/sys/kernel/mm/lru_gen/`` contains stable ABIs described in the +following subsections. + +Kill switch +----------- +``enabled`` accepts different values to enable or disable the +following components. Its default value depends on +``CONFIG_LRU_GEN_ENABLED``. All the components should be enabled +unless some of them have unforeseen side effects. Writing to +``enabled`` has no effect when a component is not supported by the +hardware, and valid values will be accepted even when the main switch +is off. + +====== =============================================================== +Values Components +====== =============================================================== +0x0001 The main switch for the multi-gen LRU. +0x0002 Clearing the accessed bit in leaf page table entries in large + batches, when MMU sets it (e.g., on x86). This behavior can + theoretically worsen lock contention (mmap_lock). If it is + disabled, the multi-gen LRU will suffer a minor performance + degradation for workloads that contiguously map hot pages, + whose accessed bits can be otherwise cleared by fewer larger + batches. +0x0004 Clearing the accessed bit in non-leaf page table entries as + well, when MMU sets it (e.g., on x86). This behavior was not + verified on x86 varieties other than Intel and AMD. If it is + disabled, the multi-gen LRU will suffer a negligible + performance degradation. +[yYnN] Apply to all the components above. +====== =============================================================== + +E.g., +:: + + echo y >/sys/kernel/mm/lru_gen/enabled + cat /sys/kernel/mm/lru_gen/enabled + 0x0007 + echo 5 >/sys/kernel/mm/lru_gen/enabled + cat /sys/kernel/mm/lru_gen/enabled + 0x0005 + +Thrashing prevention +-------------------- +Personal computers are more sensitive to thrashing because it can +cause janks (lags when rendering UI) and negatively impact user +experience. The multi-gen LRU offers thrashing prevention to the +majority of laptop and desktop users who do not have ``oomd``. + +Users can write ``N`` to ``min_ttl_ms`` to prevent the working set of +``N`` milliseconds from getting evicted. The OOM killer is triggered +if this working set cannot be kept in memory. In other words, this +option works as an adjustable pressure relief valve, and when open, it +terminates applications that are hopefully not being used. + +Based on the average human detectable lag (~100ms), ``N=1000`` usually +eliminates intolerable janks due to thrashing. Larger values like +``N=3000`` make janks less noticeable at the risk of premature OOM +kills. + +The default value ``0`` means disabled. + +Experimental features +===================== +``/sys/kernel/debug/lru_gen`` accepts commands described in the +following subsections. Multiple command lines are supported, so does +concatenation with delimiters ``,`` and ``;``. + +``/sys/kernel/debug/lru_gen_full`` provides additional stats for +debugging. ``CONFIG_LRU_GEN_STATS=y`` keeps historical stats from +evicted generations in this file. + +Working set estimation +---------------------- +Working set estimation measures how much memory an application needs +in a given time interval, and it is usually done with little impact on +the performance of the application. E.g., data centers want to +optimize job scheduling (bin packing) to improve memory utilizations. +When a new job comes in, the job scheduler needs to find out whether +each server it manages can allocate a certain amount of memory for +this new job before it can pick a candidate. To do so, the job +scheduler needs to estimate the working sets of the existing jobs. + +When it is read, ``lru_gen`` returns a histogram of numbers of pages +accessed over different time intervals for each memcg and node. +``MAX_NR_GENS`` decides the number of bins for each histogram. The +histograms are noncumulative. +:: + + memcg memcg_id memcg_path + node node_id + min_gen_nr age_in_ms nr_anon_pages nr_file_pages
Documentation/admin-guide/mm/multigen_lru.rst line 123
Quoted 10 lines
Documentation/admin-guide/mm/multigen_lru.rst new file +10
-0+ ... + max_gen_nr age_in_ms nr_anon_pages nr_file_pages + +Each bin contains an estimated number of pages that have been accessed +within ``age_in_ms``. E.g., ``min_gen_nr`` contains the coldest pages +and ``max_gen_nr`` contains the hottest pages, since ``age_in_ms`` of +the former is the largest and that of the latter is the smallest. + +Users can write ``+ memcg_id node_id max_gen_nr +[can_swap [force_scan]]`` to ``lru_gen`` to create a new generation
I think this would look nicer if the command would be a literal block, say
Users can write:
+ memcg_id node_id max_gen_nr [can swap [force_scan]]
to ``lru_gen`` ...
Quoted 11 lines
Documentation/admin-guide/mm/multigen_lru.rst new file +11
-0+``max_gen_nr+1``. ``can_swap`` defaults to the swap setting and, if it +is set to ``1``, it forces the scan of anon pages when swap is off, +and vice versa. ``force_scan`` defaults to ``1`` and, if it is set to +``0``, it employs heuristics to reduce the overhead, which is likely +to reduce the coverage as well. + +A typical use case is that a job scheduler writes to ``lru_gen`` at a +certain time interval to create new generations, and it ranks the +servers it manages based on the sizes of their cold pages defined by +this time interval. +
Documentation/admin-guide/mm/multigen_lru.rst line 144
Quoted 10 lines
Documentation/admin-guide/mm/multigen_lru.rst new file +10
-0+Proactive reclaim +----------------- +Proactive reclaim induces page reclaim when there is no memory +pressure. It usually targets cold pages only. E.g., when a new job +comes in, the job scheduler wants to proactively reclaim cold pages on +the server it selected to improve the chance of successfully landing +this new job. + +Users can write ``- memcg_id node_id min_gen_nr [swappiness +[nr_to_reclaim]]`` to ``lru_gen`` to evict generations less than or
Same here.
Quoted 65 lines
Documentation/admin-guide/mm/multigen_lru.rst new file +12
-0+equal to ``min_gen_nr``. Note that ``min_gen_nr`` should be less than +``max_gen_nr-1`` as ``max_gen_nr`` and ``max_gen_nr-1`` are not fully +aged and therefore cannot be evicted. ``swappiness`` overrides the +default value in ``/proc/sys/vm/swappiness``. ``nr_to_reclaim`` limits +the number of pages to evict. + +A typical use case is that a job scheduler writes to ``lru_gen`` +before it tries to land a new job on a server. If it fails to +materialize enough cold pages because of the overestimation, it +retries on the next server according to the ranking result obtained +from the working set estimation step. This less forceful approach +limits the impacts on the existing jobs.mm/Kconfig +2
-1@@ -1131,7 +1131,8 @@ config LRU_GEN # make sure folio->flags has enough spare bits depends on 64BIT || !SPARSEMEM || SPARSEMEM_VMEMMAP help - A high performance LRU implementation to overcommit memory. + A high performance LRU implementation to overcommit memory. See + Documentation/admin-guide/mm/multigen_lru.rst for details. config LRU_GEN_ENABLED bool "Enable by default"mm/vmscan.c +4
-0@@ -5288,6 +5288,7 @@ static ssize_t show_min_ttl(struct kobject *kobj, struct kobj_attribute *attr, creturn sprintf (buf,"%u\n" ,jiffies_to_msecs (READ_ONCE (lru_gen_min_ttl))); } +/* see Documentation/admin-guide/mm/multigen_lru.rst for details */ static ssize_t store_min_ttl (struct kobject *kobj,struct kobj_attribute *attr,const char *buf,size_t len) {@@ -5321,6 +5322,7 @@ static ssize_t show_enabled(struct kobject *kobj, struct kobj_attribute *attr, creturn snprintf (buf,PAGE_SIZE ,"0x%04x\n" , caps); } +/* see Documentation/admin-guide/mm/multigen_lru.rst for details */ static ssize_t store_enabled (struct kobject *kobj,struct kobj_attribute *attr,const char *buf,size_t len) {@@ -5468,6 +5470,7 @@ static void lru_gen_seq_show_full(struct seq_file *m, struct lruvec *lruvec,seq_putc (m,'\n' ); } +/* see Documentation/admin-guide/mm/multigen_lru.rst for details */ static int lru_gen_seq_show (struct seq_file *m,void *v) {unsigned long seq;@@ -5626,6 +5629,7 @@ static int run_cmd(char cmd, int memcg_id, int nid, unsigned long seq,return err; } +/* see Documentation/admin-guide/mm/multigen_lru.rst for details */ static ssize_t lru_gen_seq_write (struct file *file,const char __user *src,size_t len,loff_t *pos) {Signature · 1 line
2.37.1.595.g718a3a8f04-goog
Signature · 2 lines
Sincerely yours, Mike.
Re: [PATCH v14 13/14] mm: multi-gen LRU: admin guide
Quoted 3 lines · Mike Rapoport
Quoted 1 line · Yu Zhao
Add an admin guide.
...
Quoted 10 lines
Quoted 2 lines
+Users can write ``+
memcg_idnode_idmax_gen_nr+[can_swap [force_scan]]`` to ``lru_gen`` to create a new generationI think this would look nicer if the command would be a literal block, say
Users can write:
+
memcg_idnode_idmax_gen_nr[can swap [force_scan]]to ``lru_gen`` ...
Thanks. I have queued this and will refresh the series one more time probably around rc5.
Re: [PATCH v14 13/14] mm: multi-gen LRU: admin guide
In reply to Yu ZhaoQuoted 144 lines · Yu Zhao
+=============
(quoted diff) +143
-0+Multi-Gen LRU +============= +The multi-gen LRU is an alternative LRU implementation that optimizes +page reclaim and improves performance under memory pressure. Page +reclaim decides the kernel's caching policy and ability to overcommit +memory. It directly impacts the kswapd CPU usage and RAM efficiency. + +Quick start +=========== +Build the kernel with the following configurations. + +* ``CONFIG_LRU_GEN=y`` +* ``CONFIG_LRU_GEN_ENABLED=y`` + +All set! + +Runtime options +=============== +``/sys/kernel/mm/lru_gen/`` contains stable ABIs described in the +following subsections. + +Kill switch +----------- +``enabled`` accepts different values to enable or disable the +following components. Its default value depends on +``CONFIG_LRU_GEN_ENABLED``. All the components should be enabled +unless some of them have unforeseen side effects. Writing to +``enabled`` has no effect when a component is not supported by the +hardware, and valid values will be accepted even when the main switch +is off. + +====== =============================================================== +Values Components +====== =============================================================== +0x0001 The main switch for the multi-gen LRU. +0x0002 Clearing the accessed bit in leaf page table entries in large + batches, when MMU sets it (e.g., on x86). This behavior can + theoretically worsen lock contention (mmap_lock). If it is + disabled, the multi-gen LRU will suffer a minor performance + degradation for workloads that contiguously map hot pages, + whose accessed bits can be otherwise cleared by fewer larger + batches. +0x0004 Clearing the accessed bit in non-leaf page table entries as + well, when MMU sets it (e.g., on x86). This behavior was not + verified on x86 varieties other than Intel and AMD. If it is + disabled, the multi-gen LRU will suffer a negligible + performance degradation. +[yYnN] Apply to all the components above. +====== =============================================================== + +E.g., +:: + + echo y >/sys/kernel/mm/lru_gen/enabled + cat /sys/kernel/mm/lru_gen/enabled + 0x0007 + echo 5 >/sys/kernel/mm/lru_gen/enabled + cat /sys/kernel/mm/lru_gen/enabled + 0x0005 + +Thrashing prevention +-------------------- +Personal computers are more sensitive to thrashing because it can +cause janks (lags when rendering UI) and negatively impact user +experience. The multi-gen LRU offers thrashing prevention to the +majority of laptop and desktop users who do not have ``oomd``. + +Users can write ``N`` to ``min_ttl_ms`` to prevent the working set of +``N`` milliseconds from getting evicted. The OOM killer is triggered +if this working set cannot be kept in memory. In other words, this +option works as an adjustable pressure relief valve, and when open, it +terminates applications that are hopefully not being used. + +Based on the average human detectable lag (~100ms), ``N=1000`` usually +eliminates intolerable janks due to thrashing. Larger values like +``N=3000`` make janks less noticeable at the risk of premature OOM +kills. + +The default value ``0`` means disabled. + +Experimental features +===================== +``/sys/kernel/debug/lru_gen`` accepts commands described in the +following subsections. Multiple command lines are supported, so does +concatenation with delimiters ``,`` and ``;``. + +``/sys/kernel/debug/lru_gen_full`` provides additional stats for +debugging. ``CONFIG_LRU_GEN_STATS=y`` keeps historical stats from +evicted generations in this file. + +Working set estimation +---------------------- +Working set estimation measures how much memory an application needs +in a given time interval, and it is usually done with little impact on +the performance of the application. E.g., data centers want to +optimize job scheduling (bin packing) to improve memory utilizations. +When a new job comes in, the job scheduler needs to find out whether +each server it manages can allocate a certain amount of memory for +this new job before it can pick a candidate. To do so, the job +scheduler needs to estimate the working sets of the existing jobs. + +When it is read, ``lru_gen`` returns a histogram of numbers of pages +accessed over different time intervals for each memcg and node. +``MAX_NR_GENS`` decides the number of bins for each histogram. The +histograms are noncumulative. +:: + + memcg memcg_id memcg_path + node node_id + min_gen_nr age_in_ms nr_anon_pages nr_file_pages + ... + max_gen_nr age_in_ms nr_anon_pages nr_file_pages + +Each bin contains an estimated number of pages that have been accessed +within ``age_in_ms``. E.g., ``min_gen_nr`` contains the coldest pages +and ``max_gen_nr`` contains the hottest pages, since ``age_in_ms`` of +the former is the largest and that of the latter is the smallest. + +Users can write ``+ memcg_id node_id max_gen_nr +[can_swap [force_scan]]`` to ``lru_gen`` to create a new generation +``max_gen_nr+1``. ``can_swap`` defaults to the swap setting and, if it +is set to ``1``, it forces the scan of anon pages when swap is off, +and vice versa. ``force_scan`` defaults to ``1`` and, if it is set to +``0``, it employs heuristics to reduce the overhead, which is likely +to reduce the coverage as well. + +A typical use case is that a job scheduler writes to ``lru_gen`` at a +certain time interval to create new generations, and it ranks the +servers it manages based on the sizes of their cold pages defined by +this time interval. + +Proactive reclaim +----------------- +Proactive reclaim induces page reclaim when there is no memory +pressure. It usually targets cold pages only. E.g., when a new job +comes in, the job scheduler wants to proactively reclaim cold pages on +the server it selected to improve the chance of successfully landing +this new job. + +Users can write ``- memcg_id node_id min_gen_nr [swappiness +[nr_to_reclaim]]`` to ``lru_gen`` to evict generations less than or +equal to ``min_gen_nr``. Note that ``min_gen_nr`` should be less than +``max_gen_nr-1`` as ``max_gen_nr`` and ``max_gen_nr-1`` are not fully
Review
Quoted 10 lines
(quoted diff) +10
-0+aged and therefore cannot be evicted. ``swappiness`` overrides the +default value in ``/proc/sys/vm/swappiness``. ``nr_to_reclaim`` limits +the number of pages to evict. + +A typical use case is that a job scheduler writes to ``lru_gen`` +before it tries to land a new job on a server. If it fails to +materialize enough cold pages because of the overestimation, it +retries on the next server according to the ranking result obtained +from the working set estimation step. This less forceful approach +limits the impacts on the existing jobs.
The documentation can be improved, like:
---- >8 ----
Documentation/admin-guide/mm/multigen_lru.rst +20 -23
@@ -10,13 +10,11 @@ memory. It directly impacts the kswapd CPU usage and RAM efficiency. Quick start =========== -Build the kernel with the following configurations. +Build the kernel with the following configurations: * ``CONFIG_LRU_GEN=y`` * ``CONFIG_LRU_GEN_ENABLED=y`` -All set! - Runtime options =============== ``/sys/kernel/mm/lru_gen/`` contains stable ABIs described in the
@@ -51,8 +49,7 @@ Values Components [yYnN] Apply to all the components above. ====== =============================================================== -E.g., -:: +Below is the example of enabling multi-gen LRU:: echo y >/sys/kernel/mm/lru_gen/enabled cat /sys/kernel/mm/lru_gen/enabled
@@ -65,21 +62,21 @@ Thrashing prevention -------------------- Personal computers are more sensitive to thrashing because it can cause janks (lags when rendering UI) and negatively impact user -experience. The multi-gen LRU offers thrashing prevention to the +experience. The multi-gen LRU offers thrashing prevention for the majority of laptop and desktop users who do not have ``oomd``. Users can write ``N`` to ``min_ttl_ms`` to prevent the working set of ``N`` milliseconds from getting evicted. The OOM killer is triggered if this working set cannot be kept in memory. In other words, this -option works as an adjustable pressure relief valve, and when open, it -terminates applications that are hopefully not being used. +option works as an adjustable pressure relief valve; and when it is open, +it terminates applications that are hopefully not being used. Based on the average human detectable lag (~100ms), ``N=1000`` usually eliminates intolerable janks due to thrashing. Larger values like ``N=3000`` make janks less noticeable at the risk of premature OOM kills. -The default value ``0`` means disabled. +The default value is ``0`` which means disabled. Experimental features =====================
@@ -88,14 +85,14 @@ following subsections. Multiple command lines are supported, so does concatenation with delimiters ``,`` and ``;``. ``/sys/kernel/debug/lru_gen_full`` provides additional stats for -debugging. ``CONFIG_LRU_GEN_STATS=y`` keeps historical stats from -evicted generations in this file. +debugging. When ``CONFIG_LRU_GEN_STATS=y`` is configured, the kernel keeps +historical stats from evicted generations in this file. Working set estimation ---------------------- Working set estimation measures how much memory an application needs in a given time interval, and it is usually done with little impact on -the performance of the application. E.g., data centers want to +the performance of the application. For example, data centers want to optimize job scheduling (bin packing) to improve memory utilizations. When a new job comes in, the job scheduler needs to find out whether each server it manages can allocate a certain amount of memory for
@@ -115,19 +112,19 @@ histograms are noncumulative. max_gen_nr age_in_ms nr_anon_pages nr_file_pages Each bin contains an estimated number of pages that have been accessed -within ``age_in_ms``. E.g., ``min_gen_nr`` contains the coldest pages +within ``age_in_ms``. Here, ``min_gen_nr`` contains the coldest pages and ``max_gen_nr`` contains the hottest pages, since ``age_in_ms`` of the former is the largest and that of the latter is the smallest. Users can write the following command to ``lru_gen`` to create a new -generation ``max_gen_nr+1``: +generation ``max_gen_nr+1``:: - ``+ memcg_id node_id max_gen_nr [can_swap [force_scan]]`` + memcg_id node_id max_gen_nr [can_swap [force_scan]] -``can_swap`` defaults to the swap setting and, if it is set to ``1``, -it forces the scan of anon pages when swap is off, and vice versa. -``force_scan`` defaults to ``1`` and, if it is set to ``0``, it -employs heuristics to reduce the overhead, which is likely to reduce +``can_swap`` defaults to the swap setting. If it is set to ``1``, +it forces the scan of anon pages when swap is off and vice versa. +``force_scan`` defaults to ``1``. If it is set to ``0``, it +uses heuristics to reduce the overhead, which is likely to reduce the coverage as well. A typical use case is that a job scheduler runs this command at a
@@ -138,15 +135,15 @@ this time interval. Proactive reclaim ----------------- Proactive reclaim induces page reclaim when there is no memory -pressure. It usually targets cold pages only. E.g., when a new job +pressure. It usually targets cold pages only. For example, when a new job comes in, the job scheduler wants to proactively reclaim cold pages on the server it selected, to improve the chance of successfully landing this new job. Users can write the following command to ``lru_gen`` to evict -generations less than or equal to ``min_gen_nr``. +generations less than or equal to ``min_gen_nr``:: - ``- memcg_id node_id min_gen_nr [swappiness [nr_to_reclaim]]`` + memcg_id node_id min_gen_nr [swappiness [nr_to_reclaim]] ``min_gen_nr`` should be less than ``max_gen_nr-1``, since ``max_gen_nr`` and ``max_gen_nr-1`` are not fully aged (equivalent to
@@ -155,7 +152,7 @@ overrides the default value in ``/proc/sys/vm/swappiness``. ``nr_to_reclaim`` limits the number of pages to evict. A typical use case is that a job scheduler runs this command before it -tries to land a new job on a server. If it fails to materialize enough +tries to land a new job on a server. If it fails to get enough cold pages because of the overestimation, it retries on the next server according to the ranking result obtained from the working set estimation step. This less forceful approach limits the impacts on the
Quoted 21 lines
(quoted diff) +3
-0+/* see Documentation/admin-guide/mm/multigen_lru.rst for details */ static ssize_t store_min_ttl(struct kobject *kobj, struct kobj_attribute *attr, const char *buf, size_t len) {@@ -5321,6 +5322,7 @@ static ssize_t show_enabled(struct kobject *kobj, struct kobj_attribute *attr, c return snprintf(buf, PAGE_SIZE, "0x%04x\n", caps); } +/* see Documentation/admin-guide/mm/multigen_lru.rst for details */ static ssize_t store_enabled(struct kobject *kobj, struct kobj_attribute *attr, const char *buf, size_t len) {@@ -5468,6 +5470,7 @@ static void lru_gen_seq_show_full(struct seq_file *m, struct lruvec *lruvec, seq_putc(m, '\n'); } +/* see Documentation/admin-guide/mm/multigen_lru.rst for details */ static int lru_gen_seq_show(struct seq_file *m, void *v) { unsigned long seq;
Review static int run_cmd(char cmd, int memcg_id, int nid, unsigned long seq, · line 5635
Quoted 7 lines
(quoted diff) +1
-0@@ -5626,6 +5629,7 @@ static int run_cmd(char cmd, int memcg_id, int nid, unsigned long seq, return err; } +/* see Documentation/admin-guide/mm/multigen_lru.rst for details */ static ssize_t lru_gen_seq_write(struct file *file, const char __user *src, size_t len, loff_t *pos) {
Shouldn't these functions be described by writing kernel-doc comments? I don't see any mentions of these in multigen_lru.rst.
Thanks.
Signature · 1 line
An old man doll... just what I always wanted! - Clara
PATCH v14 14/14 mm: multi-gen LRU: design doc
In reply to Yu ZhaoAdd a design doc.
--- Documentation/mm/index.rst | 1 + Documentation/mm/multigen_lru.rst | 159 ++++++++++++++++++++++++++++++ 2 files changed, 160 insertions(+) create mode 100644 Documentation/mm/multigen_lru.rst
Documentation/mm/index.rst +1 -0
@@ -51,6 +51,7 @@ above structured documentation, or deleted if it has served its purpose. ksm memory-model mmu_notifier + multigen_lru numa overcommit-accounting page_migration
Documentation/mm/multigen_lru.rst new file +159 -0
159 lines not on this page · raw message
Signature · 1 line
2.37.1.595.g718a3a8f04-goog
Re: [PATCH v14 14/14] mm: multi-gen LRU: design doc
Quoted 15 lines · Yu Zhao
Add a design doc.
Signed-off-by Yu Zhao <[email protected]>Acked-by Brian Geffon <[email protected]>Acked-by Steven Barrett <[email protected]>Acked-by Suleiman Souhlal <[email protected]>Tested-by Daniel Byrne <[email protected]>Tested-by Donald Carr <[email protected]>Tested-by Holger Hoffstätte <[email protected]>Tested-by Konstantin Kharlamov <[email protected]>Tested-by Shuang Zhai <[email protected]>Tested-by Sofia Trinh <[email protected]>Tested-by Vaibhav Jain <[email protected]>
LGTM to me (no new warnings).
Signature · 1 line
An old man doll... just what I always wanted! - Clara
OpenWrt / MIPS benchmark with MGLRU
In reply to Yu ZhaoTLDR
====
RAM utilization Throughput (95% CI) P99 Latency (95% CI)
----------------------------------------------------------
~90% NS NS ~110% +[12, 16]% -[20, 22]%
Abbreviations
=============
CI: confidence interval NS: no statistically significant difference DUT: device under test ATE: automatic test equipment
Rational
========
1. OpenWrt is the most popular distro for WiFi routers; many of its targets use big endianness [1].
2. 4 out of the top 5 bestselling WiFi routers in the US use MIPS [2]; MIPS uses software-managed TLB.
3. Memcached is the best available memory benchmark on OpenWrt; admittedly such a use case is very limited in the real world.
Hardware
========
DUT: Ubiquiti EdgeRouter (ER-8) [3]
DUT # cat /proc/cpuinfo
system type : UBNT_E200 (CN6120p1.1-800-NSP)
machine : Unknown
processor : 0
cpu model : Cavium Octeon II V0.1
BogoMIPS : 1600.00
wait instruction : yes
microsecond timers : yestlb_entries : 128
extra interrupt vector : yes
hardware watchpoint : yes, count: 2, address/irw mask: [0x0ffc, 0x0ffb]
isa : mips1 mips2 mips3 mips4 mips5 mips32r1 mips32r2 mips64r1 mips64r2
ASEs implemented : Options implemented : tlb rixiex 4kex octeon_cache 32fpr prefetch mcheck ejtag llsc rixi lpa vtag_icache userlocal perf_cntr_intr_bit perf shadow register sets : 1 kscratch registers : 3 package : 0 core : 0 VCED exceptions : not available VCEI exceptions : not available
processor : 1
cpu model : Cavium Octeon II V0.1
BogoMIPS : 1600.00
wait instruction : yes
microsecond timers : yestlb_entries : 128
extra interrupt vector : yes
hardware watchpoint : yes, count: 2, address/irw mask: [0x0ffc, 0x0ffb]
isa : mips1 mips2 mips3 mips4 mips5 mips32r1 mips32r2 mips64r1 mips64r2
ASEs implemented : Options implemented : tlb rixiex 4kex octeon_cache 32fpr prefetch mcheck ejtag llsc rixi lpa vtag_icache userlocal perf_cntr_intr_bit perf shadow register sets : 1 kscratch registers : 3 package : 0 core : 1 VCED exceptions : not available VCEI exceptions : not available
DUT # cat /proc/meminfo
MemTotal: 1991964 kB MemFree: 1917304 kB MemAvailable: 1896856 kB Buffers: 4 kB Cached: 33464 kB SwapCached: 0 kB Active: 1316 kB Inactive: 33500 kB Active(anon): 1316 kB Inactive(anon): 33496 kB Active(file): 0 kB Inactive(file): 4 kB Unevictable: 0 kB Mlocked: 0 kB SwapTotal: 995324 kB SwapFree: 995324 kB Dirty: 0 kB Writeback: 0 kB AnonPages: 1360 kB Mapped: 2688 kB Shmem: 33464 kB KReclaimable: 8244 kB Slab: 19772 kB SReclaimable: 8244 kB SUnreclaim: 11528 kB KernelStack: 1056 kB PageTables: 336 kB NFS_Unstable: 0 kB Bounce: 0 kB WritebackTmp: 0 kB CommitLimit: 1991304 kB Committed_AS: 38916 kB VmallocTotal: 1069547512 kB VmallocUsed: 4856 kB VmallocChunk: 0 kB Percpu: 272 kB
Software
========
DUT # cat /etc/openwrt_release DISTRIB_ID='OpenWrt'
DISTRIB_RELEASE='22.03.0-rc6' DISTRIB_REVISION='r19590-042d558536' DISTRIB_TARGET='octeon/generic' DISTRIB_ARCH='mips64_octeonplus' DISTRIB_DESCRIPTION='OpenWrt 22.03.0-rc6 r19590-042d558536' DISTRIB_TAINTS='no-all no-ipv6'
DUT # uname -a
Linux OpenWrt 6.0.0-rc3+ #0 SMP Sun Jul 31 15:12:47 2022 mips64 GNU/Linux
DUT # cat /proc/swaps
Filename Type Size Used Priority /dev/zram0 partition 995324 0 100
DUT # memcached -V
memcached 1.6.9
DUT # cat /etc/config/memcached
config memcached
option user 'memcached'
option maxconn '1024'
option listen '0.0.0.0'
option port '11211'
option memory '6400'ATE $ memtier_benchmark -vmemtier_benchmark 1.3.0
Copyright (C) 2011-2022 Redis Ltd.
This is free software. You may redistribute copies of it under the terms of the GNU General Public License <http://www.gnu.org/licenses/gpl.html>.
There is NO WARRANTY, to the extent permitted by law.
Procedure
=========
ATE $ cat run_benchmark_matrix.shrun_memtier_benchmark()
{
# boot to kernel $3
# populate dataset
memtier_benchmark/memtier_benchmark -s $DUT_IP -p 11211 \
-P memcache_binary -n allkeys -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 $DUT_IP -p 11211 \
-P memcache_binary --test-time $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=1200
mem_utils_90_110=(1600000 2000000)
kernels=("baseline" "patched")
for mem_util in ${mem_utils_90_110[@]}; do
for kernel in ${kernels[@]}; do
run_memtier_benchmark $run_duration_secs $mem_util $kernel
done
done
Results
=======
Baseline 90% RAM utilization
------------------------------------------------------------
Ops/sec Avg. Lat. p50 Lat. p99 Lat. p99.9 Lat. KB/sec
------------------------------------------------------------
48550.71 0.65687 0.48700 2.84700 5.56700 1812.25 48600.55 0.65629 0.48700 2.86300 5.59900 1814.11 48562.37 0.65674 0.48700 2.84700 5.50300 1812.68 48556.66 0.65688 0.48700 2.84700 5.53500 1812.47 48619.50 0.65600 0.48700 2.87900 5.63100 1814.82 48579.74 0.65654 0.48700 2.84700 5.56700 1813.33 48593.25 0.65764 0.48700 2.86300 5.56700 1814.10 48535.52 0.65716 0.48700 2.86300 5.56700 1811.68 48587.24 0.65645 0.48700 2.83100 5.50300 1813.61 48541.92 0.65704 0.48700 2.81500 5.47100 1811.92
MGLRU 90% RAM utilization
------------------------------------------------------------
Ops/sec Avg. Lat. p50 Lat. p99 Lat. p99.9 Lat. KB/sec
------------------------------------------------------------
48622.38 0.65594 0.48700 2.81500 5.47100 1814.92 48537.74 0.65715 0.48700 2.84700 5.53500 1811.76 48586.82 0.65646 0.48700 2.84700 5.50300 1813.59 48552.44 0.65695 0.48700 2.83100 5.43900 1812.31 48557.35 0.65680 0.49500 2.83100 5.53500 1812.49 48625.48 0.65593 0.48700 2.81500 5.43900 1815.04 48655.75 0.65557 0.48700 2.84700 5.53500 1816.17 48625.67 0.65595 0.48700 2.84700 5.53500 1815.04 48622.22 0.65600 0.48700 2.84700 5.47100 1814.91 48617.10 0.65610 0.48700 2.84700 5.56700 1814.73
Baseline 110% RAM utilization
------------------------------------------------------------
Ops/sec Avg. Lat. p50 Lat. p99 Lat. p99.9 Lat. KB/sec
------------------------------------------------------------
19813.79 1.61245 0.63100 17.79100 31.74300 744.91 20328.29 1.57158 0.62300 17.27900 31.10300 764.25 20104.12 1.58913 0.62300 17.40700 31.10300 755.82 20342.03 1.57053 0.61500 17.27900 30.84700 764.77 19688.05 1.62268 0.62300 17.91900 31.35900 740.18 19607.31 1.62943 0.63900 17.91900 31.23100 737.15 19250.96 1.65963 0.65500 17.91900 31.10300 723.75 20182.79 1.58290 0.63100 17.40700 30.84700 758.78 20181.88 1.58299 0.63100 17.40700 30.84700 758.75 20615.90 1.54963 0.62300 17.02300 30.84700 775.06
MGLRU 110% RAM utilization
------------------------------------------------------------
Ops/sec Avg. Lat. p50 Lat. p99 Lat. p99.9 Lat. KB/sec
------------------------------------------------------------
22911.33 1.39405 0.61500 13.69500 28.79900 861.36 22339.08 1.42989 0.61500 14.07900 30.07900 839.85 23394.22 1.36521 0.59900 13.56700 29.05500 879.51 22521.48 1.41830 0.61500 13.88700 29.82300 846.70 22678.10 1.40818 0.61500 13.82300 29.69500 852.59 22344.50 1.42952 0.61500 14.07900 29.95100 840.05 23245.65 1.37406 0.60700 13.50300 28.92700 873.93 23140.17 1.38032 0.59900 13.69500 29.18300 869.96 23003.34 1.38856 0.61500 13.63100 29.05500 864.82 22937.52 1.39253 0.61500 13.69500 29.43900 862.35
Flame graphs
------------
Baseline: https://drive.google.com/file/d/1-Ac4HMPAyZIqxtvKerUTqNNAgBLhpX9R
MGLRU: https://drive.google.com/file/d/1-9x0W2yIYeiRvXWiYRzL6niTqW7zCVPX
References
==========
[1] https://openwrt.org/docs/platforms/start
[2] https://www.amazon.com/bestsellers/pc/300189
[3] https://openwrt.org/toh/ubiquiti/edgerouter
Re: OpenWrt / MIPS benchmark with MGLRU
Quoted 10 lines · Yu Zhao
Rational
========
1. OpenWrt is the most popular distro for WiFi routers; many of its targets use big endianness [1].
2. 4 out of the top 5 bestselling WiFi routers in the US use MIPS [2]; MIPS uses software-managed TLB.
3. Memcached is the best available memory benchmark on OpenWrt; admittedly such a use case is very limited in the real world.
Quoted 3 lines
Hardware
========
DUT: Ubiquiti EdgeRouter (ER-8) [3]
I don't know if it makes any difference to your findings, but I would point out the test hardware is neither representative of most devices supported by OpenWRT, nor those on the amazon best-seller list that I see looking from Germany:
Five of the top-10 devices on that list are arm64 (little-endian, hardware TLB walker, typically 512MB of RAM), the others are mips32 (typically only 128MB, mostly single-core) and only the oldest one (Archer C7) of them is big-endian. I would not expect endianness to make any difference, but the 16x smaller memory of typical mips devices (ath79, mt76) might.
Arnd
_______________________________________________
linux-arm-kernel mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel
Re: OpenWrt / MIPS benchmark with MGLRU
In reply to Yu ZhaoQuoted 10 lines · Yu Zhao
Rational
========
1. OpenWrt is the most popular distro for WiFi routers; many of its targets use big endianness [1].
2. 4 out of the top 5 bestselling WiFi routers in the US use MIPS [2]; MIPS uses software-managed TLB.
3. Memcached is the best available memory benchmark on OpenWrt; admittedly such a use case is very limited in the real world.
Quoted 3 lines
Hardware
========
DUT: Ubiquiti EdgeRouter (ER-8) [3]
I don't know if it makes any difference to your findings, but I would point out the test hardware is neither representative of most devices supported by OpenWRT, nor those on the amazon best-seller list that I see looking from Germany:
Five of the top-10 devices on that list are arm64 (little-endian, hardware TLB walker, typically 512MB of RAM), the others are mips32 (typically only 128MB, mostly single-core) and only the oldest one (Archer C7) of them is big-endian. I would not expect endianness to make any difference, but the 16x smaller memory of typical mips devices (ath79, mt76) might.
Arnd
Re: OpenWrt / MIPS benchmark with MGLRU
In reply to Yu ZhaoQuoted 6 lines · Yu Zhao
TLDR
====
RAM utilization Throughput (95% CI) P99 Latency (95% CI)
----------------------------------------------------------~90% NS NS ~110% +[12, 16]% -[20, 22]%
I'll give you points for thinking out of the box on this one. This is a piece of hardware where both latency and bandwidth theoretically matter.
I've got a slightly older but similar piece of Ubiquiti hardware with
512MB of RAM. It doesn't run OpenWRT, fwiw. Maybe my firmware is a bit outdated.
*But*, most of the heavy lifting for packet flow on these systems is done in hardware. They have some hardware acceleration to be able to _route_ at gigabit speeds, so they're probably not quite as sensitive to software hiccups as lower-end routers.
That said, my system at least does not typically have *any* memory pressure. Right now, it hasn't even filled free memory with page cache and it's been up for over a month:
# cat /proc/meminfo MemTotal: 491552 kB MemFree: 160188 kB MemAvailable: 373088 kB Cached: 151004 kB
I think a better tl;dr would be:
MGLRU doesn't help much or cause any regressions on this hardware. Under (atypical) synthetic memory pressure, MGLRU did show some modest but measurable throughput and latency benefits.
In other words, this provides more of a data point that MGLRU doesn't hurt medium-ish sized embedded systems. I think you could make an even stronger case with even smaller hardware or something that actually sees memory pressure on a regular basis in the wild.
Re: OpenWrt / MIPS benchmark with MGLRU
In reply to Yu ZhaoQuoted 15 lines · Yu Zhao
TLDR
====
RAM utilization Throughput (95% CI) P99 Latency (95% CI)
----------------------------------------------------------~90% NS NS ~110% +[12, 16]% -[20, 22]%Abbreviations
=============CI: confidence interval NS: no statistically significant difference DUT: device under test ATE: automatic test equipment
Quoted 8 lines
Rational
========
1. OpenWrt is the most popular distro for WiFi routers; many of its targets use big endianness [1].
2. 4 out of the top 5 bestselling WiFi routers in the US use MIPS [2]; MIPS uses software-managed TLB.
3. Memcached is the best available memory benchmark on OpenWrt; admittedly such a use case is very limited in the real world.
Thanks.
My goal is to encourage MM people to extend their test coverage to some commonly used but less tested configurations. I carefully constructed this benchmark with the balance between its representativeness and the effort to reproduce.
When I wear my MM hat, I see ER-8 as the ideal choice because it comes with a serial port, a replaceable memory DIMM and one of the two cores that can be disabled. The same SoC is also what the Debian MIPS port mainly uses for their testing [1]. So if I need help, I might be able to get it from them.
From OpenWrt's / MIPS OEMs' POVs, I do see ER-8 as an uninteresting platform. Currently the best selling WiFi router on Amazon US is Archer A7, a knockoff of Archer C7. The latter comes with not only the serial port header but also the JTAG header, and that's what I use. But I seriously doubt showing how I work on C7 would encourage MM people to try it. I snapped a pictures of it during lunch:
https://drive.google.com/file/d/1rYBwLOyMqBSr6WKUZd7Gbf9RfwA641X5/
And other boards I routinely test the MM performance on:
https://drive.google.com/file/d/1yBMx9OPWw-5czvz3maNUy6WBFwPvAqG5/
All the way dates back to this vintage:
https://drive.google.com/file/d/12N21qiWSoyJgZwVkwAhY8_5Fj4dKftqD/
Andrew Morton
maintainerI'd like to move mglru into the mm-stable branch late this week.
I'm not terribly happy about the level of review nor the carefulness of the code commenting (these things are related) and I have a note here that "mm: multi-gen LRU: admin guide" is due for an update and everyone is at conference anyway. But let's please try to push things along anyway.
Quoted 7 lines · Andrew Morton
I'd like to move mglru into the mm-stable branch late this week.
I'm not terribly happy about the level of review nor the carefulness of the code commenting (these things are related) and I have a note here that "mm: multi-gen LRU: admin guide" is due for an update and everyone is at conference anyway. But let's please try to push things along anyway.
Thanks for the heads-up. Will add as many comments as I can and wrap it up by the end of tomorrow.
Quoted 5 lines · Yu Zhao
Quoted 3 lines · Andrew Morton
I'd like to move mglru into the mm-stable branch late this week.
Quoted 7 lines
Quoted 4 lines
I'm not terribly happy about the level of review nor the carefulness of the code commenting (these things are related) and I have a note here that "mm: multi-gen LRU: admin guide" is due for an update and everyone is at conference anyway. But let's please try to push things along anyway.
Thanks for the heads-up. Will add as many comments as I can and wrap it up by the end of tomorrow.
I've posted v15 which can replace what mm-unstable currently has. Apologies for the delay: an unexpected lockdep warning from the maple tree forced me to restart all the tests [1].
Let me also post the incremental patches after this email, in case you strongly prefer to add them on top of v14.
[1] https://lore.kernel.org/r/CAOUHufZabH85CeUN-MEMgL8gJGzJEWUrkiM58JkTbBhh-jew0Q@mail.gmail.com/
PATCH 1/11 mm: multi-gen LRU: update admin guide
--- Documentation/admin-guide/mm/multigen_lru.rst | 50 +++++++++++-------- 1 file changed, 28 insertions(+), 22 deletions(-)
Documentation/admin-guide/mm/multigen_lru.rst +28 -22
@@ -119,15 +119,18 @@ within ``age_in_ms``. E.g., ``min_gen_nr`` contains the coldest pages and ``max_gen_nr`` contains the hottest pages, since ``age_in_ms`` of the former is the largest and that of the latter is the smallest. -Users can write ``+ memcg_id node_id max_gen_nr -[can_swap [force_scan]]`` to ``lru_gen`` to create a new generation -``max_gen_nr+1``. ``can_swap`` defaults to the swap setting and, if it -is set to ``1``, it forces the scan of anon pages when swap is off, -and vice versa. ``force_scan`` defaults to ``1`` and, if it is set to -``0``, it employs heuristics to reduce the overhead, which is likely -to reduce the coverage as well. +Users can write the following command to ``lru_gen`` to create a new +generation ``max_gen_nr+1``: -A typical use case is that a job scheduler writes to ``lru_gen`` at a + ``+ memcg_id node_id max_gen_nr [can_swap [force_scan]]`` + +``can_swap`` defaults to the swap setting and, if it is set to ``1``, +it forces the scan of anon pages when swap is off, and vice versa. +``force_scan`` defaults to ``1`` and, if it is set to ``0``, it +employs heuristics to reduce the overhead, which is likely to reduce +the coverage as well. + +A typical use case is that a job scheduler runs this command at a certain time interval to create new generations, and it ranks the servers it manages based on the sizes of their cold pages defined by this time interval.
@@ -137,20 +140,23 @@ Proactive reclaim Proactive reclaim induces page reclaim when there is no memory pressure. It usually targets cold pages only. E.g., when a new job comes in, the job scheduler wants to proactively reclaim cold pages on -the server it selected to improve the chance of successfully landing +the server it selected, to improve the chance of successfully landing this new job. -Users can write ``- memcg_id node_id min_gen_nr [swappiness -[nr_to_reclaim]]`` to ``lru_gen`` to evict generations less than or -equal to ``min_gen_nr``. Note that ``min_gen_nr`` should be less than -``max_gen_nr-1`` as ``max_gen_nr`` and ``max_gen_nr-1`` are not fully -aged and therefore cannot be evicted. ``swappiness`` overrides the -default value in ``/proc/sys/vm/swappiness``. ``nr_to_reclaim`` limits -the number of pages to evict. +Users can write the following command to ``lru_gen`` to evict +generations less than or equal to ``min_gen_nr``. -A typical use case is that a job scheduler writes to ``lru_gen`` -before it tries to land a new job on a server. If it fails to -materialize enough cold pages because of the overestimation, it -retries on the next server according to the ranking result obtained -from the working set estimation step. This less forceful approach -limits the impacts on the existing jobs. + ``- memcg_id node_id min_gen_nr [swappiness [nr_to_reclaim]]`` + +``min_gen_nr`` should be less than ``max_gen_nr-1``, since +``max_gen_nr`` and ``max_gen_nr-1`` are not fully aged (equivalent to +the active list) and therefore cannot be evicted. ``swappiness`` +overrides the default value in ``/proc/sys/vm/swappiness``. +``nr_to_reclaim`` limits the number of pages to evict. + +A typical use case is that a job scheduler runs this command before it +tries to land a new job on a server. If it fails to materialize enough +cold pages because of the overestimation, it retries on the next +server according to the ranking result obtained from the working set +estimation step. This less forceful approach limits the impacts on the +existing jobs.
Signature · 1 line
2.37.3.968.ga6b4b080e4-goog
PATCH 2/11 mm: multi-gen LRU: add comment in lru_gen_use_mm()
--- include/linux/mm_types.h | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)
include/linux/mm_types.h +5 -1
@@ -18,7 +18,6 @@#include <linux/page-flags-layout.h> #include <linux/workqueue.h> #include <linux/seqlock.h> -#include <linux/mmdebug.h> #include <asm/mmu.h>
@@ -770,6 +769,11 @@ static inline void lru_gen_init_mm(struct mm_struct *mm)static inline void lru_gen_use_mm (struct mm_struct *mm) { +/* +* When the bitmap is set, page reclaim knows this mm_struct has been +* used since the last time it cleared the bitmap. So it might be worth +* walking the page tables of this mm_struct to clear the accessed bit. +*/ WRITE_ONCE (mm->lru_gen.bitmap,-1 ); }
Signature · 1 line
2.37.3.968.ga6b4b080e4-goog
PATCH 3/11 mm: multi-gen LRU: warn on !ptep_test_and_clear_young()
In reply to Yu Zhao--- mm/vmscan.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
mm/vmscan.c +2 -2
@@ -3904,7 +3904,7 @@ static bool walk_pte_range(pmd_t *pmd, unsigned long start, unsigned long end,continue ;if (!ptep_test_and_clear_young (args->vma, addr, pte + i)) -continue ; +VM_WARN_ON_ONCE (true); young++; walk->mm_stats[MM_LEAF_YOUNG ]++;
@@ -4637,7 +4637,7 @@ void lru_gen_look_around(struct page_vma_mapped_walk *pvmw)continue ;if (!ptep_test_and_clear_young (pvmw->vma, addr, pte + i)) -continue ; +VM_WARN_ON_ONCE (true); young++;
Signature · 1 line
2.37.3.968.ga6b4b080e4-goog
Andrew Morton
maintainerRe: [PATCH v14-fix 03/11] mm: multi-gen LRU: warn on !ptep_test_and_clear_young()
Quoted 21 lines · On Sun, 18 Sep 2022 14:47:47 -0600 Yu Zhao <[email protected]> wrote:
Suggested-by Nadav Amit <[email protected]>Signed-off-by Yu Zhao <[email protected]>--- mm/vmscan.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)mm/vmscan.c +1
-1@@ -3904,7 +3904,7 @@ static bool walk_pte_range(pmd_t *pmd, unsigned long start, unsigned long end,continue ;if (!ptep_test_and_clear_young (args->vma, addr, pte + i)) -continue ; +VM_WARN_ON_ONCE (true); young++; walk->mm_stats[MM_LEAF_YOUNG ]++;
mm/vmscan.c void lru_gen_look_around(struct page_vma_mapped_walk *pvmw) · line 4641
Quoted 6 lines
mm/vmscan.c +1
-1@@ -4637,7 +4637,7 @@ void lru_gen_look_around(struct page_vma_mapped_walk *pvmw)continue ;if (!ptep_test_and_clear_young (pvmw->vma, addr, pte + i)) -continue ; +VM_WARN_ON_ONCE (true);
This is a functional change? More than the Subject: describes.
Re: [PATCH v14-fix 03/11] mm: multi-gen LRU: warn on !ptep_test_and_clear_young()
Quoted 26 lines · Andrew Morton
Quoted 23 lines · On Sun, 18 Sep 2022 14:47:47 -0600 Yu Zhao <[email protected]> wrote:
Suggested-by Nadav Amit <[email protected]>Signed-off-by Yu Zhao <[email protected]>--- mm/vmscan.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)mm/vmscan.c +1
-1@@ -3904,7 +3904,7 @@ static bool walk_pte_range(pmd_t *pmd, unsigned long start, unsigned long end,continue ;if (!ptep_test_and_clear_young (args->vma, addr, pte + i)) -continue ; +VM_WARN_ON_ONCE (true); young++; walk->mm_stats[MM_LEAF_YOUNG ]++;@@ -4637,7 +4637,7 @@ void lru_gen_look_around(struct page_vma_mapped_walk *pvmw)continue ;
Quoted 6 lines
mm/vmscan.c void lru_gen_look_around(struct page_vma_mapped_walk *pvmw) · line 4641
Quoted 4 lines
mm/vmscan.c +1
-1if (!ptep_test_and_clear_young (pvmw->vma, addr, pte + i)) -continue ; +VM_WARN_ON_ONCE (true);This is a functional change? More than the Subject: describes.
No, since ptep_test_and_clear_young() shouldn't fail here. We are under the PTL and ascertained (a few lines above) pte_young() is true. Neither the h/w nor another thread can clear the accessed bit under us.
PATCH 4/11 mm: multi-gen LRU: fix warning from __rcu
In reply to Yu Zhao--- mm/memcontrol.c | 2 +- mm/vmscan.c | 6 ++++-- 2 files changed, 5 insertions(+), 3 deletions(-)
mm/memcontrol.c +1 -1
@@ -6289,7 +6289,7 @@ static void mem_cgroup_attach(struct cgroup_taskset *tset)return ;task_lock (task); -if (task->mm && task->mm->owner == task) +if (task->mm &&READ_ONCE (task->mm->owner) == task)lru_gen_migrate_mm (task->mm);task_unlock (task); }
mm/vmscan.c +4 -2
@@ -3270,15 +3270,17 @@ void lru_gen_del_mm(struct mm_struct *mm)void lru_gen_migrate_mm (struct mm_struct *mm) {struct mem_cgroup *memcg; +struct task_struct *task =rcu_dereference_protected (mm->owner, true); -lockdep_assert_held (&mm->owner->alloc_lock); +VM_WARN_ON_ONCE (task->mm != mm); +lockdep_assert_held (&task->alloc_lock);/* for mm_update_next_owner() */ if (mem_cgroup_disabled ())return ;rcu_read_lock (); - memcg =mem_cgroup_from_task (rcu_dereference (mm->owner)); + memcg =mem_cgroup_from_task (task);rcu_read_unlock ();if (memcg == mm->lru_gen.memcg)return ;
Signature · 1 line
2.37.3.968.ga6b4b080e4-goog
PATCH 5/11 mm: multi-gen LRU: fix warning from seq_is_valid()
In reply to Yu Zhaov5 (link below) calls inc_min_seq() in the correct order but rewrites in the later versions broke it.
WARNING: CPU: 0 PID: 0 at ./include/linux/mm_types.h:613 context_switch+0x375/0x3e0 __schedule+0x443/0x610 schedule_idle+0x27/0x40 do_idle+0x322/0x360 cpu_startup_entry+0x65/0x70 rest_init+0x1e7/0x1f0 start_kernel+0x529/0x5a0 x86_64_start_reservations+0x13f/0x150 x86_64_start_kernel+0x1f2/0x200 secondary_startup_64+0xa6/0xb0
--- mm/vmscan.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
mm/vmscan.c +1 -1
@@ -4307,7 +4307,7 @@ static void inc_max_seq(struct lruvec *lruvec, bool can_swap, bool force_scan)VM_WARN_ON_ONCE (!seq_is_valid (lruvec)); -for (type =0 ; type <ANON_AND_FILE ; type++) { +for (type =ANON_AND_FILE -1 ; type >=0 ; type--) {if (get_nr_gens (lruvec, type) !=MAX_NR_GENS )continue ;
Signature · 1 line
2.37.3.968.ga6b4b080e4-goog
PATCH 6/11 mm: multi-gen LRU: delete overcautious VM_WARN_ON_ONCE()
In reply to Yu ZhaoAs commented, it is "unlikely but not a bug when reset_batch_size() is pending". This one was never reported but another similar one in lru_gen_use_mm(), which is already deleted, indeed happened.
kernel BUG at mm/vmscan.c:4592!
Call Trace: ? get_nr_to_scan+0x89/0x2a0 lru_gen_shrink_lruvec+0x1aa/0x2b0 shrink_node_memcg+0x68/0x450 shrink_node+0x25c/0x620 shrink_zones+0xf4/0x170 do_try_to_free_pages+0xa5/0x280 try_to_free_mem_cgroup_pages+0x161/0x1f0 try_charge+0x2b1/0x940 __mem_cgroup_try_charge+0x102/0x3d0 do_anonymous_page+0x152/0x440 handle_mm_fault+0x9d2/0x1030 __do_page_fault+0x388/0x550 do_page_fault+0x2b/0x60 page_fault+0x45/0x50
--- mm/vmscan.c | 3 --- 1 file changed, 3 deletions(-)
mm/vmscan.c +0 -3
@@ -5171,9 +5171,6 @@ static bool __maybe_unused state_is_valid(struct lruvec *lruvec)for_each_gen_type_zone (gen, type, zone) {if (!list_empty (&lrugen->lists[gen][type][zone]))return false; - -/* unlikely but not a bug when reset_batch_size() is pending */ -VM_WARN_ON_ONCE (lrugen->nr_pages[gen][type][zone]); } }
Signature · 1 line
2.37.3.968.ga6b4b080e4-goog
PATCH 7/11 mm: multi-gen LRU: dial down MAX_LRU_BATCH
In reply to Yu ZhaoA need_resched warning was reported and already fixed by adding a need_resched() check to walk_pud_range(). Dial down MAX_LRU_BATCH anyway in the interest of direct reclaim latency.
WARNING: CPU: 22 PID: 2771 at kernel/sched/core.c:3637 scheduler_tick+0x339/0x410 Call Trace: <IRQ> update_process_times+0x7b/0x90 tick_sched_timer+0x82/0xd0 __run_hrtimer+0x81/0x200 hrtimer_interrupt+0x192/0x450 smp_apic_timer_interrupt+0xac/0x1d0 apic_timer_interrupt+0x88/0x90 </IRQ> RIP: 0010:walk_pte_range+0x1c2/0x6a0 walk_pmd_range+0x1ed/0x490 walk_pud_range+0xe6/0x2b0 __walk_page_range+0x111/0x690 walk_page_range+0x4e/0x150 walk_mm+0x110/0x200 try_to_inc_max_seq+0xdb/0xb10 lru_gen_run_cmd+0x153/0x1c0 lru_gen_run+0x150/0x210 stale_page_run+0x62/0x730 kthread+0x148/0x1b0 ret_from_fork+0x54/0x60
--- include/linux/mmzone.h | 2 +- mm/vmscan.c | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-)
include/linux/mmzone.h +1 -1
@@ -381,7 +381,7 @@ enum { };#define MIN_LRU_BATCH BITS_PER_LONG -#define MAX_LRU_BATCH (MIN_LRU_BATCH * 128) +#define MAX_LRU_BATCH (MIN_LRU_BATCH * 64)/* whether to keep historical stats from evicted generations */ #ifdef CONFIG_LRU_GEN_STATS
mm/vmscan.c +1 -1
@@ -4400,7 +4400,7 @@ static bool try_to_inc_max_seq(struct lruvec *lruvec, unsigned long max_seq, }while (mm); done:if (!success) { -if (sc->priority <DEF_PRIORITY -2 ) +if (sc->priority <=DEF_PRIORITY -2 )wait_event_killable (lruvec->mm_state.wait, max_seq <READ_ONCE (lrugen->max_seq));
Signature · 1 line
2.37.3.968.ga6b4b080e4-goog
PATCH 8/11 mm: multi-gen LRU: delete newline in kswapd_age_node()
In reply to Yu Zhao--- mm/vmscan.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)
mm/vmscan.c +1 -2
@@ -6699,8 +6699,7 @@ unsigned long try_to_free_mem_cgroup_pages(struct mem_cgroup *memcg, }#endif -static void kswapd_age_node (struct pglist_data *pgdat, -struct scan_control *sc) +static void kswapd_age_node (struct pglist_data *pgdat,struct scan_control *sc) {struct mem_cgroup *memcg;struct lruvec *lruvec;
Signature · 1 line
2.37.3.968.ga6b4b080e4-goog
PATCH 9/11 mm: multi-gen LRU: add comment in lru_gen_look_around()
In reply to Yu Zhao--- mm/vmscan.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)
mm/vmscan.c +3 -1
@@ -4604,6 +4604,9 @@ void lru_gen_look_around(struct page_vma_mapped_walk *pvmw)if (spin_is_contended (pvmw->ptl))return ; +/* avoid taking the LRU lock under the PTL when possible */ + walk = current->reclaim_state ? current->reclaim_state->mm_walk :NULL ; + start =max (pvmw->address &PMD_MASK , pvmw->vma->vm_start); end =min (pvmw->address | ~PMD_MASK , pvmw->vma->vm_end -1 ) +1 ;
@@ -4619,7 +4622,6 @@ void lru_gen_look_around(struct page_vma_mapped_walk *pvmw) } pte = pvmw->pte - (pvmw->address - start) /PAGE_SIZE ; - walk = current->reclaim_state ? current->reclaim_state->mm_walk :NULL ;rcu_read_lock ();arch_enter_lazy_mmu_mode ();
Signature · 1 line
2.37.3.968.ga6b4b080e4-goog
PATCH 10/11 mm: multi-gen LRU: fixed long-tailed direct reclaim latency
In reply to Yu ZhaoLong-tailed direct reclaim latency was seen on high-memory (TBs)
machines: MGLRU is better at the 99th percentile but worse at the 99.9th.
It turned out the old direct reclaim backoff, which tries to enforce a minimum fairness among all eligible memcgs, over-swapped by about (total_mem>>DEF_PRIORITY)-nr_to_reclaim:
/* adjust priority if memcg is offline or the target is met */
if (!mem_cgroup_online(memcg))
priority = 0;
else if (sc->nr_reclaimed - reclaimed >= sc->nr_to_reclaim)
priority = DEF_PRIORITY;
else
priority = sc->priority;The new backoff, which pulls the plug on swapping once the target is met, trades some fairness for curtailed latency. Specifically, in should_abort_scan():
/* over-swapping can increase allocation latency */
if (sc->nr_reclaimed >= sc->nr_to_reclaim && need_swapping)
return true;The fundamental problem is that the backoff requires a sophisticated model and the previous one was oversimplified. The new one may still be, but at least it can handle a couple more corner cases on top of the above:
/* age each memcg once to ensure fairness */
if (max_seq - seq > 1)
return true;
The NR_FREE_PAGES check at the bottom of should_abort_scan().--- mm/vmscan.c | 105 ++++++++++++++++++++++++++++++++++------------------ 1 file changed, 70 insertions(+), 35 deletions(-)
mm/vmscan.c +70 -35
@@ -135,10 +135,9 @@ struct scan_control { unsigned int no_demotion:1;#ifdef CONFIG_LRU_GEN -/* help make better choices when multiple memcgs are available */ +/* help kswapd make better choices among multiple memcgs */ unsigned int memcgs_need_aging:1; - unsigned int memcgs_need_swapping:1; - unsigned int memcgs_avoid_swapping:1; +unsigned long last_reclaimed;#endif /* Allocation order */
@@ -4524,22 +4523,19 @@ static void lru_gen_age_node(struct pglist_data *pgdat, struct scan_control *sc)VM_WARN_ON_ONCE (!current_is_kswapd ()); + sc->last_reclaimed = sc->nr_reclaimed; +/* -* To reduce the chance of going into the aging path or swapping, which -* can be costly, optimistically skip them unless their corresponding -* flags were cleared in the eviction path. This improves the overall -* performance when multiple memcgs are available. +* To reduce the chance of going into the aging path, which can be +* costly, optimistically skip it if the flag below was cleared in the +* eviction path. This improves the overall performance when multiple +* memcgs are available. */ if (!sc->memcgs_need_aging) { sc->memcgs_need_aging = true; - sc->memcgs_avoid_swapping = !sc->memcgs_need_swapping; - sc->memcgs_need_swapping = true;return ; } - sc->memcgs_need_swapping = true; - sc->memcgs_avoid_swapping = true; -set_mm_walk (pgdat); memcg =mem_cgroup_iter (NULL ,NULL ,NULL );
@@ -5035,7 +5031,7 @@ static int evict_folios(struct lruvec *lruvec, struct scan_control *sc, int swap sc->nr_reclaimed += reclaimed; -if (type ==LRU_GEN_ANON && need_swapping) +if (need_swapping && type ==LRU_GEN_ANON ) *need_swapping = true;return scanned;
@@ -5047,19 +5043,13 @@ static int evict_folios(struct lruvec *lruvec, struct scan_control *sc, int swap* reclaim. */ static unsigned long get_nr_to_scan (struct lruvec *lruvec,struct scan_control *sc, -bool can_swap,unsigned long reclaimed,bool *need_aging) +bool can_swap,bool *need_aging) { -int priority;unsigned long nr_to_scan;struct mem_cgroup *memcg =lruvec_memcg (lruvec);DEFINE_MAX_SEQ (lruvec);DEFINE_MIN_SEQ (lruvec); -if (fatal_signal_pending (current)) { - sc->nr_reclaimed +=MIN_LRU_BATCH ; -return 0 ; - } -if (mem_cgroup_below_min (memcg) || (mem_cgroup_below_low (memcg) && !sc->memcg_low_reclaim))return 0 ;
@@ -5068,15 +5058,7 @@ static unsigned long get_nr_to_scan(struct lruvec *lruvec, struct scan_control *if (!nr_to_scan)return 0 ; -/* adjust priority if memcg is offline or the target is met */ -if (!mem_cgroup_online (memcg)) - priority =0 ; -else if (sc->nr_reclaimed - reclaimed >= sc->nr_to_reclaim) - priority =DEF_PRIORITY ; -else - priority = sc->priority; - - nr_to_scan >>= priority; + nr_to_scan >>=mem_cgroup_online (memcg) ? sc->priority :0 ;if (!nr_to_scan)return 0 ;
@@ -5084,7 +5066,7 @@ static unsigned long get_nr_to_scan(struct lruvec *lruvec, struct scan_control *return nr_to_scan;/* skip the aging path at the default priority */ -if (priority ==DEF_PRIORITY ) +if (sc->priority ==DEF_PRIORITY ) goto done;/* leave the work to lru_gen_age_node() */
@@ -5097,6 +5079,60 @@ static unsigned long get_nr_to_scan(struct lruvec *lruvec, struct scan_control *return min_seq[!can_swap] +MIN_NR_GENS <= max_seq ? nr_to_scan :0 ; } +static bool should_abort_scan (struct lruvec *lruvec,unsigned long seq, +struct scan_control *sc,bool need_swapping) +{ +int i; +DEFINE_MAX_SEQ (lruvec); + +if (!current_is_kswapd ()) { +/* age each memcg once to ensure fairness */ +if (max_seq - seq >1 ) +return true; + +/* over-swapping can increase allocation latency */ +if (sc->nr_reclaimed >= sc->nr_to_reclaim && need_swapping) +return true; + +/* give this thread a chance to exit and free its memory */ +if (fatal_signal_pending (current)) { + sc->nr_reclaimed +=MIN_LRU_BATCH ; +return true; + } + +if (cgroup_reclaim (sc)) +return false; + }else if (sc->nr_reclaimed - sc->last_reclaimed < sc->nr_to_reclaim) +return false; + +/* keep scanning at low priorities to ensure fairness */ +if (sc->priority >DEF_PRIORITY -2 ) +return false; + +/* +* A minimum amount of work was done under global memory pressure. For +* kswapd, it may be overshooting. For direct reclaim, the target isn't +* met, and yet the allocation may still succeed, since kswapd may have +* caught up. In either case, it's better to stop now, and restart if +* necessary. +*/ +for (i =0 ; i <= sc->reclaim_idx; i++) { +unsigned long wmark; +struct zone *zone =lruvec_pgdat (lruvec)->node_zones + i; + +if (!managed_zone (zone)) +continue ; + + wmark =current_is_kswapd () ?high_wmark_pages (zone) :low_wmark_pages (zone); +if (wmark >zone_page_state (zone,NR_FREE_PAGES )) +return false; + } + + sc->nr_reclaimed +=MIN_LRU_BATCH ; + +return true; +} +static void lru_gen_shrink_lruvec (struct lruvec *lruvec,struct scan_control *sc) {struct blk_plug plug;
@@ -5104,6 +5140,7 @@ static void lru_gen_shrink_lruvec(struct lruvec *lruvec, struct scan_control *scbool need_swapping = false;unsigned long scanned =0 ;unsigned long reclaimed = sc->nr_reclaimed; +DEFINE_MAX_SEQ (lruvec);lru_add_drain ();
@@ -5123,7 +5160,7 @@ static void lru_gen_shrink_lruvec(struct lruvec *lruvec, struct scan_control *scelse swappiness =0 ; - nr_to_scan =get_nr_to_scan (lruvec, sc, swappiness, reclaimed, &need_aging); + nr_to_scan =get_nr_to_scan (lruvec, sc, swappiness, &need_aging);if (!nr_to_scan) goto done;
@@ -5135,17 +5172,15 @@ static void lru_gen_shrink_lruvec(struct lruvec *lruvec, struct scan_control *scif (scanned >= nr_to_scan)break ; -if (sc->memcgs_avoid_swapping && swappiness <200 && need_swapping) +if (should_abort_scan (lruvec, max_seq, sc, need_swapping))break ;cond_resched (); }/* see the comment in lru_gen_age_node() */ -if (!need_aging) +if (sc->nr_reclaimed - reclaimed >=MIN_LRU_BATCH && !need_aging) sc->memcgs_need_aging = false; -if (!need_swapping) - sc->memcgs_need_swapping = false; done:clear_mm_walk ();
Signature · 1 line
2.37.3.968.ga6b4b080e4-goog
PATCH 11/11 mm: multi-gen LRU: refactor get_nr_evictable()
In reply to Yu ZhaoThe previous commit made this refactor possible: 28 insertions and 36 deletions.
--- mm/vmscan.c | 64 +++++++++++++++++++++++------------------------------ 1 file changed, 28 insertions(+), 36 deletions(-)
mm/vmscan.c +28 -36
@@ -4418,14 +4418,15 @@ static bool try_to_inc_max_seq(struct lruvec *lruvec, unsigned long max_seq,return true; } -static unsigned long get_nr_evictable (struct lruvec *lruvec,unsigned long max_seq, -unsigned long *min_seq,bool can_swap,bool *need_aging) +static bool should_run_aging (struct lruvec *lruvec,unsigned long max_seq,unsigned long *min_seq, +struct scan_control *sc,bool can_swap,unsigned long *nr_to_scan) {int gen, type, zone;unsigned long old =0 ;unsigned long young =0 ;unsigned long total =0 ;struct lru_gen_struct *lrugen = &lruvec->lrugen; +struct mem_cgroup *memcg =lruvec_memcg (lruvec);for (type = !can_swap; type <ANON_AND_FILE ; type++) {unsigned long seq;
@@ -4441,35 +4442,37 @@ static unsigned long get_nr_evictable(struct lruvec *lruvec, unsigned long max_s total += size;if (seq == max_seq) young += size; -if (seq +MIN_NR_GENS == max_seq) +else if (seq +MIN_NR_GENS == max_seq) old += size; } } +/* try to scrape all its memory if this memcg was deleted */ + *nr_to_scan =mem_cgroup_online (memcg) ? (total >> sc->priority) : total; +/* -* The aging tries to be lazy to reduce the overhead. On the other hand, -* the eviction stalls when the number of generations reaches -* MIN_NR_GENS. So ideally, there should be MIN_NR_GENS+1 generations, -* hence the first two if's. -* -* Also it's ideal to spread pages out evenly, meaning 1/(MIN_NR_GENS+1) +* The aging tries to be lazy to reduce the overhead, while the eviction +* stalls when the number of generations reaches MIN_NR_GENS. Hence, the +* ideal number of generations is MIN_NR_GENS+1. +*/ +if (min_seq[!can_swap] +MIN_NR_GENS > max_seq) +return true; +if (min_seq[!can_swap] +MIN_NR_GENS < max_seq) +return false; + +/* +* It's also ideal to spread pages out evenly, i.e., 1/(MIN_NR_GENS+1) * of the total number of pages for each generation. A reasonable range * for this average portion is [1/MIN_NR_GENS, 1/(MIN_NR_GENS+2)]. The -* eviction cares about the lower bound of cold pages, whereas the aging -* cares about the upper bound of hot pages. +* aging cares about the upper bound of hot pages, while the eviction +* cares about the lower bound of cold pages. */ -if (min_seq[!can_swap] +MIN_NR_GENS > max_seq) - *need_aging = true; -else if (min_seq[!can_swap] +MIN_NR_GENS < max_seq) - *need_aging = false; -else if (young *MIN_NR_GENS > total) - *need_aging = true; -else if (old * (MIN_NR_GENS +2 ) < total) - *need_aging = true; -else - *need_aging = false; +if (young *MIN_NR_GENS > total) +return true; +if (old * (MIN_NR_GENS +2 ) < total) +return true; -return total; +return false; }static bool age_lruvec (struct lruvec *lruvec,struct scan_control *sc,unsigned long min_ttl)
@@ -4488,11 +4491,7 @@ static bool age_lruvec(struct lruvec *lruvec, struct scan_control *sc, unsignedif (mem_cgroup_below_min (memcg))return false; - nr_to_scan =get_nr_evictable (lruvec, max_seq, min_seq, swappiness, &need_aging); -if (!nr_to_scan) -return false; - - nr_to_scan >>=mem_cgroup_online (memcg) ? sc->priority :0 ; + need_aging =should_run_aging (lruvec, max_seq, min_seq, sc, swappiness, &nr_to_scan);if (min_ttl) {int gen =lru_gen_from_seq (min_seq[LRU_GEN_FILE ]);
@@ -4506,7 +4505,7 @@ static bool age_lruvec(struct lruvec *lruvec, struct scan_control *sc, unsignedreturn false; } -if (nr_to_scan && need_aging) +if (need_aging)try_to_inc_max_seq (lruvec, max_seq, sc, swappiness, false);return true;
@@ -5054,14 +5053,7 @@ static unsigned long get_nr_to_scan(struct lruvec *lruvec, struct scan_control * (mem_cgroup_below_low(memcg) && !sc->memcg_low_reclaim))return 0 ; - nr_to_scan =get_nr_evictable (lruvec, max_seq, min_seq, can_swap, need_aging); -if (!nr_to_scan) -return 0 ; - - nr_to_scan >>=mem_cgroup_online (memcg) ? sc->priority :0 ; -if (!nr_to_scan) -return 0 ; - + *need_aging =should_run_aging (lruvec, max_seq, min_seq, sc, can_swap, &nr_to_scan);if (!*need_aging)return nr_to_scan;
Signature · 1 line
2.37.3.968.ga6b4b080e4-goog
Andrew Morton
maintainerQuoted 2 lines · On Sun, 18 Sep 2022 14:40:01 -0600 Yu Zhao <[email protected]> wrote:
Let me also post the incremental patches after this email, in case you strongly prefer to add them on top of v14.
Thanks, helpful.
I have one question regarding 03/11.
The final two updates look pretty substantial. I guess I'll do a series replacement and let this and mapletree sit another week.