Multigenerational LRU Framework
Subsystems (21)
v5 cover Multigenerational LRU Framework
What's new in v5
================
1) Rebased to v5.15 per users' requests
2) Performance benchmark reports on the previous version:
https://patchwork.kernel.org/project/linux-mm/cover/[email protected]/#24506153
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.
Problems
========
Active/inactive
---------------
Data centers need to predict whether a job can successfully land on a machine without actually impacting the existing jobs. The granularity of the active/inactive is too coarse to be useful for job schedulers to make such decisions. In addition, data centers need to monitor their memory utilization for horizontal scaling. The active/inactive are relative terms and therefore cannot give any insight into a pool of machines, e.g., aggregating the active/inactive across multiple machines without a common frame of reference yields no meaningful results.
Phones and laptops need to make good choices about what to evict because they are more sensitive to major faults and power consumption. Major faults can cause janks, i.e., slow UI renderings, and negatively impact user experience. The selection between anon and file types has been suboptimal because it is difficult to compare the access patterns of the two types. On phones and laptops, executable pages are frequently evicted despite the fact that there are many less frequently used anon pages. Conversely, on workstations building large projects, anon pages are sometimes swapped out while there are many less recently used file pages.
Fundamentally, the notion of active/inactive has very limited ability to measure temporal locality.
Rmap walk
---------
Traversing a list of pages and searching the rmap for PTEs mapping each page can be very expensive because those pages are likely to be unrelated. For workloads using a high percentage of anon memory, the rmap becomes a bottleneck in page reclaim. For example, kswapd can easily spend more CPU time in the rmap than in anything else on laptops running Chrome. And the kernel can spend more CPU time in the rmap than in any other functions on servers that heavily overcommit anon memory.
Simply put, it does not take advantage of spatial locality when using the rmap to test the accessed bit over a large number of pages.
Solutions
=========
Generations
-----------
This solution introduces a temporal dimension. Each generation is a dot on the timeline and its population includes all mapped pages that have been accessed since the birth of this generation.
All eviction choices are made based on generation numbers, which are simple and yet effective. A large number of pages can be spread out across many generations. Since each generation is timestamped at birth, its population is aggregatable across different machines. This is especially useful for data centers that require working set estimation and proactive reclaim.
Page table walk
---------------
Each walk traverses an mm_struct list to scan PTEs for accessed pages only. Processes that have been sleeping since the last walk are skipped. The cost of this solution is roughly proportional to the number of accessed pages. Since page tables usually have good spatial locality for workloads using a high percentage of anon memory, the end result is generally a significant reduction in kswapd CPU usage.
Note that page table walks are conditional and therefore do not replace the rmap. For workloads that have sparse mappings, this solution falls back to the rmap.
Use cases
=========
Page cache overcommit
---------------------
Tiers within each generation are specifically designed to improve the performance of page cache under memory pressure. The fio/io_uring benchmark shows 14% increase in IOPS for buffered I/O.
Without this patchset, the profile of fio/io_uring looks like:
12.03% __page_cache_alloc 6.53% shrink_active_list 2.53% mark_page_accessed
With this patchset, it looks like:
9.45% __page_cache_alloc
0.52% mark_page_accessed
Essentially, the idea of tiers is a feedback loop based on trial and error. Instead of unconditionally moving file pages to the active list upon the second access, this solution monitors refaults and conditionally protects file pages with outlying refaults.
Anon memory overcommit
----------------------
Our real-world benchmark that browses popular websites in multiple Chrome tabs demonstrates 51% less CPU usage from kswapd and 52% (full) less PSI.
Without this patchset, the profile of kswapd looks like:
31.03% page_vma_mapped_walk 25.59% lzo1x_1_do_compress 4.63% do_raw_spin_lock 3.89% vma_interval_tree_iter_next 3.33% vma_interval_tree_subtree_search
With this patchset, it looks like:
49.36% lzo1x_1_do_compress 4.54% page_vma_mapped_walk 4.45% memset_erms 3.47% walk_pte_range 2.88% zram_bvec_rw
In addition, direct reclaim latency is reduced by 22% at 99th percentile and the number of refaults is reduced by 7%. Both metrics are important to phones and laptops as they are highly correlated to user experience.
Working set estimation
----------------------
Userspace can invoke the aging by writing "+ memcg_id node_id max_gen [swappiness]" to /sys/kernel/debug/lru_gen. Reading this debugfs interface returns the birth time and the population of each generation.
Given a pool of machines, by periodically invoking the aging, a job scheduler is able to rank these machines based on the sizes of their working sets and in turn selects the most ideal ones to land new jobs.
Proactive reclaim
-----------------
Userspace can invoke the eviction by writing "- memcg_id node_id min_gen [swappiness] [nr_to_reclaim]" to /sys/kernel/debug/lru_gen. Multiple command lines are supported, as is concatenation with delimiters "," and ";".
A typical use case is that a job scheduler invokes the eviction in anticipation of new jobs. The savings from proactive reclaim can provide certain SLA to landing these new jobs.
Yu Zhao (10):
mm: x86, arm64: add arch_has_hw_pte_young()
mm: x86: add CONFIG_ARCH_HAS_NONLEAF_PMD_YOUNG
mm/vmscan.c: refactor shrink_node()
mm: multigenerational lru: groundwork
mm: multigenerational lru: mm_struct list
mm: multigenerational lru: aging
mm: multigenerational lru: eviction
mm: multigenerational lru: user interface
mm: multigenerational lru: Kconfig
mm: multigenerational lru: documentation
Documentation/vm/index.rst | 1 + Documentation/vm/multigen_lru.rst | 132 ++ arch/Kconfig | 9 + arch/arm64/include/asm/cpufeature.h | 5 + arch/arm64/include/asm/pgtable.h | 13 +- arch/arm64/kernel/cpufeature.c | 10 + arch/arm64/tools/cpucaps | 1 + 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 | 7 + include/linux/mm.h | 36 + include/linux/mm_inline.h | 198 ++ include/linux/mm_types.h | 106 ++ include/linux/mmzone.h | 175 ++ include/linux/nodemask.h | 1 + include/linux/oom.h | 16 + include/linux/page-flags-layout.h | 19 +- include/linux/page-flags.h | 4 +- include/linux/pgtable.h | 17 +- include/linux/sched.h | 3 + include/linux/swap.h | 3 + kernel/bounds.c | 3 + kernel/cgroup/cgroup-internal.h | 1 - kernel/exit.c | 1 + kernel/fork.c | 10 + kernel/kthread.c | 1 + kernel/sched/core.c | 2 + mm/Kconfig | 59 + mm/huge_memory.c | 3 +- mm/memcontrol.c | 31 + mm/memory.c | 21 +- mm/mm_init.c | 6 +- mm/oom_kill.c | 4 +- mm/page_alloc.c | 1 + mm/rmap.c | 8 + mm/swap.c | 51 +- mm/swapfile.c | 2 + mm/vmscan.c | 2697 ++++++++++++++++++++++++++- mm/workingset.c | 120 +- 43 files changed, 3679 insertions(+), 133 deletions(-) create mode 100644 Documentation/vm/multigen_lru.rst
Signature · 1 line
2.34.0.rc0.344.g81b53c2807-goog
PATCH v5 1/10 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 triggers a page fault following the TLB miss of this PTE.
Being aware of this capability can help make better decisions, i.e., whether to limit the size of each batch of PTEs and the burst of batches when clearing the accessed bit.
--- arch/arm64/include/asm/cpufeature.h | 5 +++++ arch/arm64/include/asm/pgtable.h | 13 ++++++++----- arch/arm64/kernel/cpufeature.c | 10 ++++++++++ arch/arm64/tools/cpucaps | 1 + arch/x86/include/asm/pgtable.h | 6 +++--- include/linux/pgtable.h | 13 +++++++++++++ mm/memory.c | 14 +------------- 7 files changed, 41 insertions(+), 21 deletions(-)
arch/arm64/include/asm/cpufeature.h +5 -0
@@ -779,6 +779,11 @@ static inline bool system_supports_tlb_range(void)cpus_have_const_cap (ARM64_HAS_TLB_RANGE ); } +static inline bool system_has_hw_af (void ) +{ +return IS_ENABLED (CONFIG_ARM64_HW_AFDBM ) &&cpus_have_const_cap (ARM64_HW_AF ); +} +extern int do_emulate_mrs (struct pt_regs *regs,u32 sys_reg,u32 rt);static inline u32 id_aa64mmfr0_parange_to_phys_shift (int parange)
arch/arm64/include/asm/pgtable.h +8 -5
@@ -993,13 +993,16 @@ 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 ) +static inline bool arch_has_hw_pte_young (bool local) { -WARN_ON (preemptible ()); +if (local) { +WARN_ON (preemptible ()); +return cpu_has_hw_af (); + } -return !cpu_has_hw_af (); +return system_has_hw_af (); } -#define arch_faults_on_old_pte arch_faults_on_old_pte +#define arch_has_hw_pte_young arch_has_hw_pte_young/* * Experimentally, it's cheap to set the access flag in hardware and we
@@ -1007,7 +1010,7 @@ static inline bool arch_faults_on_old_pte(void)*/ static inline bool arch_wants_old_prefaulted_pte (void ) { -return !arch_faults_on_old_pte (); +return arch_has_hw_pte_young (true); }#define arch_wants_old_prefaulted_pte arch_wants_old_prefaulted_pte
arch/arm64/kernel/cpufeature.c +10 -0
@@ -2157,6 +2157,16 @@ static const struct arm64_cpu_capabilities arm64_features[] = { .matches = has_hw_dbm, .cpu_enable = cpu_enable_hw_dbm, }, + { + .desc = "Hardware update of the Access flag", + .type = ARM64_CPUCAP_SYSTEM_FEATURE, + .capability = ARM64_HW_AF, + .sys_reg = SYS_ID_AA64MMFR1_EL1, + .sign = FTR_UNSIGNED, + .field_pos = ID_AA64MMFR1_HADBS_SHIFT, + .min_field_value = 1, + .matches = has_cpuid_feature, + }, #endif { .desc = "CRC32 instructions",
arch/arm64/tools/cpucaps +1 -0
@@ -35,6 +35,7 @@ HAS_STAGE2_FWB HAS_SYSREG_GIC_CPUIF HAS_TLB_RANGE HAS_VIRT_HOST_EXTN +HW_AF HW_DBM KVM_PROTECTED_MODE MISMATCHED_CACHE_TYPE
arch/x86/include/asm/pgtable.h +3 -3
@@ -1397,10 +1397,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 (bool local) { -return false; +return true; }#endif /* __ASSEMBLY__ */
include/linux/pgtable.h +13 -0
@@ -258,6 +258,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 by the local CPU or all CPUs. +* +* Those arches which have hw access flag feature need to implement their own +* helper. By default, "false" means pagefault will be hit on old pte. +*/ +static inline bool arch_has_hw_pte_young (bool local) +{ +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
@@ -121,18 +121,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 ) {
@@ -2769,7 +2757,7 @@ static inline bool cow_user_page(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 (true) && !pte_young (vmf->orig_pte)) {pte_t entry; vmf->pte =pte_offset_map_lock (mm, vmf->pmd, addr, &vmf->ptl);
Signature · 1 line
2.34.0.rc0.344.g81b53c2807-goog
Will Deacon
maintainerRe: [PATCH v5 01/10] mm: x86, arm64: add arch_has_hw_pte_young()
Quoted 11 lines · Yu Zhao
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 triggers a page fault following the TLB miss of this PTE.
Being aware of this capability can help make better decisions, i.e., whether to limit the size of each batch of PTEs and the burst of batches when clearing the accessed bit.
Signed-off-by Yu Zhao <[email protected]>Tested-by Konstantin Kharlamov <[email protected]>
Quoted 9 lines
--- arch/arm64/include/asm/cpufeature.h | 5 +++++ arch/arm64/include/asm/pgtable.h | 13 ++++++++----- arch/arm64/kernel/cpufeature.c | 10 ++++++++++ arch/arm64/tools/cpucaps | 1 + arch/x86/include/asm/pgtable.h | 6 +++--- include/linux/pgtable.h | 13 +++++++++++++ mm/memory.c | 14 +------------- 7 files changed, 41 insertions(+), 21 deletions(-)
*Please* cc the maintainers on arch patches. I asked you that last time, too:
https://lore.kernel.org/r/20210819091923.GA15467@willie-the-truck
Quoted 8 lines
arch/arm64/kernel/cpufeature.c +0
-0@@ -2157,6 +2157,16 @@ static const struct arm64_cpu_capabilities arm64_features[] = { .matches = has_hw_dbm, .cpu_enable = cpu_enable_hw_dbm, },
arch/arm64/kernel/cpufeature.c static const struct arm64_cpu_capabilities arm64_features[] = { · line 2169
Quoted 10 lines
arch/arm64/kernel/cpufeature.c +10
-0+ { + .desc = "Hardware update of the Access flag", + .type = ARM64_CPUCAP_SYSTEM_FEATURE, + .capability = ARM64_HW_AF, + .sys_reg = SYS_ID_AA64MMFR1_EL1, + .sign = FTR_UNSIGNED, + .field_pos = ID_AA64MMFR1_HADBS_SHIFT, + .min_field_value = 1, + .matches = has_cpuid_feature, + },
As before, please don't make this a system feature as it will prohibit onlining of late CPUs with mismatched access flag support and I really don't see that being necessary.
You should just be able to use arch_faults_on_old_pte() as-is.
Will
Re: [PATCH v5 01/10] mm: x86, arm64: add arch_has_hw_pte_young()
Quoted 51 lines · Will Deacon
Quoted 11 lines · Yu Zhao
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 triggers a page fault following the TLB miss of this PTE.
Being aware of this capability can help make better decisions, i.e., whether to limit the size of each batch of PTEs and the burst of batches when clearing the accessed bit.
Signed-off-by Yu Zhao <[email protected]>Tested-by Konstantin Kharlamov <[email protected]>Quoted 9 lines
--- arch/arm64/include/asm/cpufeature.h | 5 +++++ arch/arm64/include/asm/pgtable.h | 13 ++++++++----- arch/arm64/kernel/cpufeature.c | 10 ++++++++++ arch/arm64/tools/cpucaps | 1 + arch/x86/include/asm/pgtable.h | 6 +++--- include/linux/pgtable.h | 13 +++++++++++++ mm/memory.c | 14 +------------- 7 files changed, 41 insertions(+), 21 deletions(-)*Please* cc the maintainers on arch patches. I asked you that last time, too:
https://lore.kernel.org/r/20210819091923.GA15467@willie-the-truck
Quoted 8 lines
arch/arm64/kernel/cpufeature.c +0
-0@@ -2157,6 +2157,16 @@ static const struct arm64_cpu_capabilities arm64_features[] = { .matches = has_hw_dbm, .cpu_enable = cpu_enable_hw_dbm, },arch/arm64/kernel/cpufeature.c static const struct arm64_cpu_capabilities arm64_features[] = { · line 2169
Quoted 10 lines
arch/arm64/kernel/cpufeature.c +10
-0+ { + .desc = "Hardware update of the Access flag", + .type = ARM64_CPUCAP_SYSTEM_FEATURE, + .capability = ARM64_HW_AF, + .sys_reg = SYS_ID_AA64MMFR1_EL1, + .sign = FTR_UNSIGNED, + .field_pos = ID_AA64MMFR1_HADBS_SHIFT, + .min_field_value = 1, + .matches = has_cpuid_feature, + },As before, please don't make this a system feature as it will prohibit onlining of late CPUs with mismatched access flag support and I really don't see that being necessary.
Quoted 1 line
You should just be able to use
arch_faults_on_old_pte()as-is.
Well, I did explain why last time and there weren't any pushbacks after I listed my reasons:
1) there is no known hardware that does this, i.e., having mismatching accessed bit capabilities.
2) there are no foreseeable benefits in supporting such a theoretical use case
There are many other opportunities ARM could explore, e.g., supporting the accessed bit on non-leaf entries as x86 has been for decades. Dwelling on this theoretical use case, IMO, is just a typical example of overengineering.
But I do hear you -- as I mentioned last time, I don't have a problem with doing it your way. Please touch on the two points I raised so that I know where we stand. Otherwise I might again assume I've convinced you to do it my way :)
Also why should I be able to use arch_faults_on_old_pte() as-is? This implies we can make the following decisions based on the same information.
1) set the accessed bit since the CPU we are running on won't do it for us
2) don't clear the accessed bit on too many entries since the CPU we are running on will have a page fault upon seeing cleared accessed bit on an entry
Are there conditions equivalent? Technically no, but it probably would make no difference anyway.
My real problem with arch_faults_on_old_pte() is that it needs to be called with preemption disabled. Again, IMO, a static branch for such a common capability (from x86 perspective) is a no-brainer, because there is zero return on investment in leaving the door open for mismatching accessed bit capabilities.
PATCH v5 2/10 mm: x86: add CONFIG_ARCH_HAS_NONLEAF_PMD_YOUNG
In reply to Yu ZhaoSome architectures support the accessed bit on non-leaf PMD entries, e.g., x86_64 sets the accessed bit on a non-leaf PMD entry when using it as part of linear address translation [1]. As an optimization, page table walkers who are interested in the accessed bit can skip the PTEs under a non-leaf PMD entry if the accessed bit is cleared on this PMD entry.
Although an inline function may be preferable, this capability is added as a configuration option to look consistent when used with the existing macros.
[1]: Intel 64 and IA-32 Architectures Software Developer's Manual
Volume 3 (June 2021), section 4.8
--- arch/Kconfig | 9 +++++++++ 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, 18 insertions(+), 4 deletions(-)
arch/Kconfig +9 -0
@@ -1288,6 +1288,15 @@ config ARCH_HAS_ELFCORE_COMPAT config ARCH_HAS_PARANOID_L1D_FLUSH bool +config ARCH_HAS_NONLEAF_PMD_YOUNG + bool + depends on PGTABLE_LEVELS > 2 + help + Architectures that select this are able to set the accessed bit on + non-leaf PMD entries in addition to leaf PTE entries where pages are + mapped. For them, page table walkers that clear the accessed bit may + stop at non-leaf PMD entries if they do not see the accessed bit. + source "kernel/gcov/Kconfig" source "scripts/gcc-plugins/Kconfig"
arch/x86/Kconfig +1 -0
@@ -84,6 +84,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 X86_64 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
@@ -817,7 +817,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
@@ -211,7 +211,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)
@@ -232,7 +232,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.34.0.rc0.344.g81b53c2807-goog
PATCH v5 3/10 mm/vmscan.c: refactor shrink_node()
In reply to Yu ZhaoThis patch refactors shrink_node(). This will make the upcoming changes to mm/vmscan.c more readable.
--- mm/vmscan.c | 186 +++++++++++++++++++++++++++------------------------- 1 file changed, 98 insertions(+), 88 deletions(-)
mm/vmscan.c +98 -88
@@ -2562,6 +2562,103 @@ 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); + +/* +* 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; + + refaults =lruvec_page_state (target_lruvec, +WORKINGSET_ACTIVATE_ANON ); +if (refaults != target_lruvec->refaults[0 ] || +inactive_is_low (target_lruvec,LRU_INACTIVE_ANON )) + sc->may_deactivate |=DEACTIVATE_ANON ; +else + sc->may_deactivate &= ~DEACTIVATE_ANON ; + +/* +* 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_FILE ); +if (refaults != target_lruvec->refaults[1 ] || +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. The relative value of each set of LRU lists is determined
@@ -3032,7 +3129,6 @@ 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);
@@ -3048,93 +3144,7 @@ static void shrink_node(pg_data_t *pgdat, struct scan_control *sc) 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; - - refaults =lruvec_page_state (target_lruvec, -WORKINGSET_ACTIVATE_ANON ); -if (refaults != target_lruvec->refaults[0 ] || -inactive_is_low (target_lruvec,LRU_INACTIVE_ANON )) - sc->may_deactivate |=DEACTIVATE_ANON ; -else - sc->may_deactivate &= ~DEACTIVATE_ANON ; - -/* -* 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_FILE ); -if (refaults != target_lruvec->refaults[1 ] || -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.34.0.rc0.344.g81b53c2807-goog
PATCH v5 4/10 mm: multigenerational lru: groundwork
In reply to Yu ZhaoFor each lruvec, evictable pages are divided into multiple generations. 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 page->flags. The sliding window technique is used to prevent truncated generation numbers from overlapping. Each truncated generation number is an index to lrugen->lists[MAX_NR_GENS][ANON_AND_FILE][MAX_NR_ZONES].
The framework comprises two conceptually independent components: the aging, which produces young generations, and the eviction, which consumes old generations. Both can be invoked independently from user space for the purpose of working set estimation and proactive reclaim.
The protection of hot pages and the selection of cold pages are based on page access types and patterns. There are two access types: one via page tables and the other via file descriptors. The protection of the former type is by design stronger because:
1) The uncertainty in determining the access patterns of the former type is higher due to the coalesced nature of the accessed bit.
2) The cost of evicting the former type is higher due to the TLB flushes required and the likelihood of involving I/O.
3) The penalty of under-protecting the former type is higher because applications usually do not prepare themselves for major faults like they do for blocked I/O. For example, client applications commonly dedicate blocked I/O to separate threads to avoid UI janks that negatively affect user experience.
There are also two access patterns: one with temporal locality and the other without. The latter pattern, e.g., random and sequential, needs to be explicitly excluded to avoid weakening the protection of the former pattern. Generally the former type follows the former pattern unless MADV_SEQUENTIAL is specified and the latter type follows the latter pattern unless outlying refaults have been observed.
Upon faulting, a page is added to the youngest generation, which provides the strongest protection as the eviction will not consider this page before the aging has scanned it at least twice. The first scan clears the accessed bit set during the initial fault. And the second scan makes sure this page has not been used since the first scan. A page from any other generations is brought back to the youngest generation whenever the aging finds the accessed bit set on any of the PTEs mapping this page.
Unmapped pages are initially added to the oldest generation and then conditionally protected by tiers. This is done later [PATCH 07/10].
--- fs/fuse/dev.c | 3 +- include/linux/cgroup.h | 15 +- include/linux/mm.h | 36 ++++ include/linux/mm_inline.h | 182 +++++++++++++++++++++ include/linux/mmzone.h | 70 ++++++++ include/linux/page-flags-layout.h | 19 ++- include/linux/page-flags.h | 4 +- include/linux/sched.h | 3 + kernel/bounds.c | 3 + kernel/cgroup/cgroup-internal.h | 1 - mm/huge_memory.c | 3 +- mm/memcontrol.c | 1 + mm/memory.c | 7 + mm/mm_init.c | 6 +- mm/page_alloc.c | 1 + mm/swap.c | 9 +- mm/swapfile.c | 2 + mm/vmscan.c | 262 ++++++++++++++++++++++++++++++ 18 files changed, 612 insertions(+), 15 deletions(-)
fs/fuse/dev.c +2 -1
@@ -785,7 +785,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/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, \
@@ -707,6 +718,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.h +36 -0
@@ -1093,6 +1093,8 @@ vm_fault_t finish_mkwrite_fault(struct vm_fault *vmf);#define ZONES_PGOFF (NODES_PGOFF - ZONES_WIDTH)#define LAST_CPUPID_PGOFF (ZONES_PGOFF - LAST_CPUPID_WIDTH)#define KASAN_TAG_PGOFF (LAST_CPUPID_PGOFF - KASAN_TAG_WIDTH) +#define LRU_GEN_PGOFF (KASAN_TAG_PGOFF - LRU_GEN_WIDTH) +#define LRU_REFS_PGOFF (LRU_GEN_PGOFF - LRU_REFS_WIDTH)/* * Define the bit shifts to access each section. For non-existent
@@ -1800,6 +1802,40 @@ static inline void unmap_mapping_range(struct address_space *mapping, loff_t const holebegin, loff_t const holelen, int even_cows) { } #endif +#ifdef CONFIG_LRU_GEN +static inline void task_enter_nonseq_fault(void) +{ + WARN_ON(current->in_nonseq_fault); + + current->in_nonseq_fault =1 ; +} + +static inline void task_exit_nonseq_fault (void ) +{ +WARN_ON (!current->in_nonseq_fault); + + current->in_nonseq_fault =0 ; +} + +static inline bool task_in_nonseq_fault (void ) +{ +return current->in_nonseq_fault; +} +#else +static inline void task_enter_nonseq_fault (void ) +{ +} + +static inline void task_exit_nonseq_fault (void ) +{ +} + +static inline bool task_in_nonseq_fault (void ) +{ +return false; +} +#endif /* CONFIG_LRU_GEN */ +static inline void unmap_shared_mapping_range (struct address_space *mapping,loff_t const holebegin,loff_t const holelen) {
include/linux/mm_inline.h +182 -0
205 lines not on this page · raw message
include/linux/mmzone.h +70 -0
82 lines not on this page · raw message
include/linux/page-flags-layout.h +14 -5
@@ -26,6 +26,14 @@#define ZONES_WIDTH ZONES_SHIFT +#ifdef CONFIG_LRU_GEN +/* LRU_GEN_WIDTH is generated from order_base_2(CONFIG_NR_LRU_GENS + 1). */ +#define LRU_REFS_WIDTH (CONFIG_TIERS_PER_GEN - 2) +#else +#define LRU_GEN_WIDTH 0 +#define LRU_REFS_WIDTH 0 +#endif /* CONFIG_LRU_GEN */ +#ifdef CONFIG_SPARSEMEM #include <asm/sparsemem.h> #define SECTIONS_SHIFT (MAX_PHYSMEM_BITS - SECTION_SIZE_BITS)
@@ -55,7 +63,8 @@#define SECTIONS_WIDTH 0#endif -#if ZONES_WIDTH +SECTIONS_WIDTH +NODES_SHIFT <=BITS_PER_LONG -NR_PAGEFLAGS +#if ZONES_WIDTH +LRU_GEN_WIDTH +LRU_REFS_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 +98,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 +LRU_REFS_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,8 +109,8 @@#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 +LRU_REFS_WIDTH +SECTIONS_WIDTH +NODES_WIDTH + \ +KASAN_TAG_WIDTH +LAST_CPUPID_WIDTH >BITS_PER_LONG -NR_PAGEFLAGS #error "Not enough bits in page flags"#endif
include/linux/page-flags.h +2 -2
@@ -845,7 +845,7 @@ static inline void ClearPageSlabPfmemalloc(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.
@@ -856,7 +856,7 @@ static inline void ClearPageSlabPfmemalloc(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 +3 -0
@@ -911,6 +911,9 @@ struct task_struct {#ifdef CONFIG_MEMCG unsigned in_user_fault:1;#endif +#ifdef CONFIG_LRU_GEN + unsigned in_nonseq_fault:1; +#endif #ifdef CONFIG_COMPAT_BRK unsigned brk_randomized:1;#endif
kernel/bounds.c +3 -0
@@ -22,6 +22,9 @@ 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 (CONFIG_NR_LRU_GENS +1 )); +#endif /* End of constants */ return 0 ;
kernel/cgroup/cgroup-internal.h +0 -1
@@ -146,7 +146,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/huge_memory.c +2 -1
@@ -2364,7 +2364,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 +1 -0
@@ -5173,6 +5173,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 +7 -0
@@ -4762,6 +4762,7 @@ vm_fault_t handle_mm_fault(struct vm_area_struct *vma, unsigned long address, unsigned int flags, struct pt_regs *regs) { vm_fault_t ret; +bool nonseq_fault = !(vma->vm_flags &VM_SEQ_READ );__set_current_state (TASK_RUNNING );
@@ -4783,11 +4784,17 @@ vm_fault_t handle_mm_fault(struct vm_area_struct *vma, unsigned long address,if (flags &FAULT_FLAG_USER )mem_cgroup_enter_user_fault (); +if (nonseq_fault) +task_enter_nonseq_fault (); +if (unlikely (is_vm_hugetlb_page (vma))) ret =hugetlb_fault (vma->vm_mm, vma, address, flags);else ret =__handle_mm_fault (vma, address, flags); +if (nonseq_fault) +task_exit_nonseq_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/page_alloc.c +1 -0
@@ -7405,6 +7405,7 @@ static void __meminit pgdat_init_internals(struct pglist_data *pgdat)pgdat_page_ext_init (pgdat);lruvec_init (&pgdat->__lruvec); +lru_gen_init_state (NULL , &pgdat->__lruvec); } static void __meminit zone_init_internals(struct zone *zone, enum zone_type idx, int nid,
mm/swap.c +7 -2
@@ -446,6 +446,11 @@ void lru_cache_add(struct page *page)VM_BUG_ON_PAGE (PageActive (page) &&PageUnevictable (page), page);VM_BUG_ON_PAGE (PageLRU (page), page); +/* see the comment in lru_gen_add_page() */ +if (lru_gen_enabled () && !PageUnevictable (page) && +task_in_nonseq_fault () && !(current->flags &PF_MEMALLOC )) +SetPageActive (page); +get_page (page);local_lock (&lru_pvecs.lock); pvec =this_cpu_ptr (&lru_pvecs.lru_add);
@@ -547,7 +552,7 @@ static void lru_deactivate_file_fn(struct page *page, struct lruvec *lruvec)static void lru_deactivate_fn (struct page *page,struct lruvec *lruvec) { -if (PageActive (page) && !PageUnevictable (page)) { +if (!PageUnevictable (page) && (PageActive (page) ||lru_gen_enabled ())) {int nr_pages =thp_nr_pages (page);del_page_from_lru_list (page, lruvec);
@@ -661,7 +666,7 @@ void deactivate_file_page(struct page *page)*/ void deactivate_page (struct page *page) { -if (PageLRU (page) &&PageActive (page) && !PageUnevictable (page)) { +if (PageLRU (page) && !PageUnevictable (page) && (PageActive (page) ||lru_gen_enabled ())) {struct pagevec *pvec;local_lock (&lru_pvecs.lock);
mm/swapfile.c +2 -0
@@ -2688,6 +2688,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile) err =0 ;atomic_inc (&proc_poll_event);wake_up_interruptible (&proc_poll_wait); +lru_gen_change_state (false, false, true); out_dput:filp_close (victim,NULL );
@@ -3349,6 +3350,7 @@ SYSCALL_DEFINE2(swapon, const char __user *, specialfile, int, swap_flags)mutex_unlock (&swapon_mutex);atomic_inc (&proc_poll_event);wake_up_interruptible (&proc_poll_wait); +lru_gen_change_state (true, false, true); error =0 ; goto out;
mm/vmscan.c +262 -0
274 lines not on this page · raw message
Signature · 1 line
2.34.0.rc0.344.g81b53c2807-goog
PATCH v5 5/10 mm: multigenerational lru: mm_struct list
In reply to Yu ZhaoTo scan PTEs for accessed pages, a mm_struct list is maintained for each memcg. When multiple threads traverse the same memcg->mm_list, each of them gets a unique mm_struct and therefore they can run walk_page_range() concurrently to reach page tables of all processes of this memcg.
This infrastructure also provides the following optimizations:
1) it allows walkers to skip processes that have been sleeping since the last walk by tracking the usage of mm_struct between context switches.
2) it allows walkers to add interesting items they find during a walk to a Bloom filter so that they can skip uninteresting items during the next walk by testing whether an item is in this Bloom filter.
--- fs/exec.c | 2 + include/linux/memcontrol.h | 4 + include/linux/mm_inline.h | 6 + include/linux/mm_types.h | 106 ++++++++++++ include/linux/mmzone.h | 63 +++++++ kernel/exit.c | 1 + kernel/fork.c | 10 ++ kernel/kthread.c | 1 + kernel/sched/core.c | 2 + mm/memcontrol.c | 25 +++ mm/vmscan.c | 331 +++++++++++++++++++++++++++++++++++++ 11 files changed, 551 insertions(+)
fs/exec.c +2 -0
@@ -1007,6 +1007,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
@@ -1017,6 +1018,7 @@ static int exec_mmap(struct mm_struct *mm)if (!IS_ENABLED (CONFIG_ARCH_WANT_IRQS_OFF_ACTIVATE_MM ))local_irq_enable ();activate_mm (active_mm, mm); +lru_gen_switch_mm (active_mm, mm);if (IS_ENABLED (CONFIG_ARCH_WANT_IRQS_OFF_ACTIVATE_MM ))local_irq_enable (); tsk->mm->vmacache_seqnum =0 ;
include/linux/memcontrol.h +4 -0
@@ -347,6 +347,10 @@ struct mem_cgroup {struct deferred_split deferred_split_queue;#endif +#ifdef CONFIG_LRU_GEN +struct lru_gen_mm_list mm_list; +#endif +struct mem_cgroup_per_node *nodeinfo[]; };
include/linux/mm_inline.h +6 -0
@@ -100,6 +100,12 @@ static inline int lru_gen_from_seq(unsigned long seq)return seq %MAX_NR_GENS ; } +/* Return a proper index regardless whether we keep stats for historical generations. */ +static inline int lru_hist_from_seq (unsigned long seq) +{ +return seq %NR_HIST_GENS ; +} +/* The youngest and the second youngest generations are counted as active. */ static inline bool lru_gen_is_active (struct lruvec *lruvec,int gen) {
include/linux/mm_types.h +106 -0
124 lines not on this page · raw message
include/linux/mmzone.h +63 -0
94 lines not on this page · raw message
kernel/exit.c +1 -0
@@ -422,6 +422,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 +10 -0
@@ -681,6 +681,7 @@ static void check_mm(struct mm_struct *mm)#if defined(CONFIG_TRANSPARENT_HUGEPAGE ) && !USE_SPLIT_PMD_PTLOCKS VM_BUG_ON_MM (mm->pmd_huge_pte, mm);#endif +VM_BUG_ON_MM (lru_gen_mm_is_active (mm), mm); }#define allocate_mm () (kmem_cache_alloc(mm_cachep, GFP_KERNEL))
@@ -1080,6 +1081,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:
@@ -1122,6 +1124,7 @@ static inline void __mmput(struct mm_struct *mm) }if (mm->binfmt)module_put (mm->binfmt->module); +lru_gen_del_mm (mm);mmdrop (mm); }
@@ -2605,6 +2608,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/kthread.c +1 -0
@@ -1361,6 +1361,7 @@ void kthread_use_mm(struct mm_struct *mm) tsk->mm = mm;membarrier_update_current_mm (mm);switch_mm_irqs_off (active_mm, mm, tsk); +lru_gen_switch_mm (active_mm, mm);local_irq_enable ();task_unlock (tsk);#ifdef finish_arch_post_lock_switch
kernel/sched/core.c +2 -0
@@ -4924,6 +4924,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_switch_mm (prev->active_mm, next->mm);if (!prev->mm) {// from kernel /* will mmdrop() in finish_task_switch(). */
@@ -8792,6 +8793,7 @@ void idle_task_exit(void)if (mm != &init_mm) {switch_mm (mm, &init_mm, current); +lru_gen_switch_mm (mm, &init_mm);finish_arch_post_lock_switch (); }
mm/memcontrol.c +25 -0
@@ -5110,6 +5110,7 @@ static void __mem_cgroup_free(struct mem_cgroup *memcg)static void mem_cgroup_free (struct mem_cgroup *memcg) { +lru_gen_free_memcg (memcg);memcg_wb_domain_exit (memcg);__mem_cgroup_free (memcg); }
@@ -6157,6 +6158,29 @@ static void mem_cgroup_move_task(void) }#endif +#ifdef CONFIG_LRU_GEN +static void mem_cgroup_attach (struct cgroup_taskset *tset) +{ +struct cgroup_subsys_state *css; +struct task_struct *task =NULL ; + +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 )
@@ -6500,6 +6524,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 +331 -0
367 lines not on this page · raw message
Signature · 1 line
2.34.0.rc0.344.g81b53c2807-goog
PATCH v5 6/10 mm: multigenerational lru: aging
In reply to Yu ZhaoThe aging produces young generations. Given an lruvec, the aging traverses lruvec_memcg()->mm_list and calls walk_page_range() to scan PTEs for accessed pages. Upon finding one, the aging updates its generation number to max_seq (modulo MAX_NR_GENS). After each round of traversal, the aging increments max_seq. The aging is due when min_seq[] reaches max_seq-1.
The aging uses the following optimizations when walking page tables:
1) It skips non-leaf PMD entries that have the accessed bit cleared when CONFIG_ARCH_HAS_NONLEAF_PMD_YOUNG=y.
2) It does not zigzag between a PGD table and the same PMD or PTE table spanning multiple VMAs. In other words, it finishes all the VMAs within the range of the same PMD or PTE table before it returns to this PGD table. This optimizes workloads that have large numbers of tiny VMAs, especially when CONFIG_PGTABLE_LEVELS=5.
--- include/linux/memcontrol.h | 3 + include/linux/mmzone.h | 9 + include/linux/oom.h | 16 + include/linux/swap.h | 3 + mm/memcontrol.c | 5 + mm/oom_kill.c | 4 +- mm/rmap.c | 8 + mm/vmscan.c | 948 +++++++++++++++++++++++++++++++++++++ 8 files changed, 994 insertions(+), 2 deletions(-)
include/linux/memcontrol.h +3 -0
@@ -1354,10 +1354,13 @@ mem_cgroup_print_oom_meminfo(struct mem_cgroup *memcg)static inline void lock_page_memcg (struct page *page) { +/* to match page_memcg_rcu() */ +rcu_read_lock (); }static inline void unlock_page_memcg (struct page *page) { +rcu_read_unlock (); }static inline void mem_cgroup_handle_over_high (void )
include/linux/mmzone.h +9 -0
@@ -295,6 +295,7 @@ enum lruvec_flags { };struct 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)
@@ -393,6 +394,7 @@ struct mm_walk_args {void lru_gen_init_state (struct mem_cgroup *memcg,struct lruvec *lruvec);void lru_gen_change_state (bool enable,bool main,bool swap); +void lru_gen_look_around (struct page_vma_mapped_walk *pvmw);#ifdef CONFIG_MEMCG void lru_gen_init_memcg (struct mem_cgroup *memcg);
@@ -409,6 +411,10 @@ static inline void lru_gen_change_state(bool enable, bool main, bool swap) { } +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) {
@@ -1028,6 +1034,9 @@ typedef struct pglist_data {unsigned long flags; +#ifdef CONFIG_LRU_GEN +struct mm_walk_args mm_walk_args; +#endif ZONE_PADDING (_pad2_)/* Per-node vmstats */
include/linux/oom.h +16 -0
@@ -57,6 +57,22 @@ struct oom_control {extern struct mutex oom_lock;extern struct mutex oom_adj_mutex; +#ifdef CONFIG_MMU +extern struct task_struct *oom_reaper_list; +extern struct wait_queue_head oom_reaper_wait; + +static inline bool oom_reaping_in_progress (void ) +{ +/* racy check to see if oom reaping could be in progress */ +return READ_ONCE (oom_reaper_list) || !waitqueue_active (&oom_reaper_wait); +} +#else +static inline bool oom_reaping_in_progress (void ) +{ +return false; +} +#endif +static inline void set_current_oom_origin (void ) { current->signal->oom_flag_origin = true;
include/linux/swap.h +3 -0
@@ -137,6 +137,9 @@ union swap_header {*/ struct reclaim_state {unsigned long reclaimed_slab; +#ifdef CONFIG_LRU_GEN +struct mm_walk_args *mm_walk_args; +#endif };#ifdef __KERNEL__
mm/memcontrol.c +5 -0
@@ -1239,12 +1239,17 @@ void mem_cgroup_update_lru_size(struct lruvec *lruvec, enum lru_list lru, *lru_size += nr_pages; size = *lru_size; +#ifdef CONFIG_LRU_GEN +/* unlikely but not a bug when reset_batch_size() is pending */ +VM_WARN_ON (size +MAX_BATCH_SIZE <0 ); +#else if (WARN_ONCE (size <0 ,"%s(%p, %d, %d): lru_size %ld\n" , __func__, lruvec, lru, nr_pages, size)) {VM_BUG_ON (1 ); *lru_size =0 ; } +#endif if (nr_pages >0 ) *lru_size += nr_pages;
mm/oom_kill.c +2 -2
@@ -508,8 +508,8 @@ bool process_shares_mm(struct task_struct *p, struct mm_struct *mm)* victim (if that is possible) to help the OOM killer to move on. */ static struct task_struct *oom_reaper_th; -static DECLARE_WAIT_QUEUE_HEAD (oom_reaper_wait); -static struct task_struct *oom_reaper_list; +DECLARE_WAIT_QUEUE_HEAD (oom_reaper_wait); +struct task_struct *oom_reaper_list;static DEFINE_SPINLOCK (oom_reaper_lock);bool __oom_reap_task_mm (struct mm_struct *mm)
mm/rmap.c +8 -0
@@ -73,6 +73,7 @@#include <linux/page_idle.h> #include <linux/memremap.h> #include <linux/userfaultfd_k.h> +#include <linux/mm_inline.h> #include <asm/tlbflush.h>
@@ -790,6 +791,13 @@ static bool page_referenced_one(struct page *page, struct vm_area_struct *vma, }if (pvmw.pte) { +/* the multigenerational lru exploits the spatial locality */ +if (lru_gen_enabled () &&pte_young (*pvmw.pte) && + !(vma->vm_flags &VM_SEQ_READ )) { +lru_gen_look_around (&pvmw); + referenced++; + } +if (ptep_clear_flush_young_notify (vma, address, pvmw.pte)) {/*
mm/vmscan.c +948 -0
984 lines not on this page · raw message
Signature · 1 line
2.34.0.rc0.344.g81b53c2807-goog
PATCH v5 7/10 mm: multigenerational lru: eviction
In reply to Yu ZhaoThe eviction consumes old generations. Given an lruvec, the eviction scans pages on lrugen->lists indexed by anon and file min_seq[] (modulo MAX_NR_GENS). It first tries to select a type based on the values of min_seq[]. If they are equal, it selects the type that has a lower refaulted %. The eviction sorts a page according to its updated generation number if the aging has found this page accessed. It also moves a page to the next generation if this page is from an upper tier that has a higher refaulted % than the base tier. The eviction increments min_seq[] of a selected type when it finds lrugen->lists indexed by min_seq[] of this selected type are empty.
Each generation is divided into multiple tiers. Tiers represent different ranges of numbers of accesses from file descriptors only. Pages accessed N times via file descriptors belong to tier order_base_2(N). Each generation contains at most MAX_NR_TIERS tiers, and they require additional MAX_NR_TIERS-2 bits in page->flags. In contrast to moving between generations which requires list operations, moving between tiers only involves operations on page->flags and therefore has a negligible cost. A feedback loop modeled after the PID controller monitors refaulted % across all tiers and decides when to protect pages from which tiers.
Unmapped pages are initially added to the oldest generation and then conditionally protected by tiers. Each tier keeps track of how many pages from it have refaulted. Tier 0 is the base tier and pages from it are evicted unconditionally because there are no better candidates. Pages from an upper tier are either evicted or moved to the next generation, depending on whether this upper tier has a higher refaulted % than the base tier. This model has the following advantages:
1) It removes the cost in the buffered access path and reduces the overall cost of protection because pages are conditionally protected in the reclaim path.
2) It takes mapped pages into account and avoids overprotecting pages accessed multiple times via file descriptors.
3 Additional tiers improve the protection of pages accessed more than twice.
--- include/linux/mm_inline.h | 10 + include/linux/mmzone.h | 33 +++ mm/swap.c | 42 +++ mm/vmscan.c | 555 +++++++++++++++++++++++++++++++++++++- mm/workingset.c | 120 ++++++++- 5 files changed, 757 insertions(+), 3 deletions(-)
include/linux/mm_inline.h +10 -0
@@ -106,6 +106,14 @@ static inline int lru_hist_from_seq(unsigned long seq)return seq %NR_HIST_GENS ; } +/* Convert the number of accesses to a tier. See the comment on MAX_NR_TIERS. */ +static inline int lru_tier_from_refs (int refs) +{ +VM_BUG_ON (refs >BIT (LRU_REFS_WIDTH )); + +return order_base_2 (refs +1 ); +} +/* The youngest and the second youngest generations are counted as active. */ static inline bool lru_gen_is_active (struct lruvec *lruvec,int gen) {
@@ -226,6 +234,8 @@ static inline bool lru_gen_del_page(struct page *page, struct lruvec *lruvec, bo gen = ((new_flags &LRU_GEN_MASK ) >>LRU_GEN_PGOFF ) -1 ; new_flags &= ~LRU_GEN_MASK ; +if ((new_flags &LRU_REFS_FLAGS ) !=LRU_REFS_FLAGS ) + new_flags &= ~(LRU_REFS_MASK |LRU_REFS_FLAGS );/* for shrink_page_list() */ if (reclaiming) new_flags &= ~(BIT (PG_referenced) |BIT (PG_reclaim));
include/linux/mmzone.h +33 -0
@@ -319,6 +319,30 @@ struct page_vma_mapped_walk;#define MIN_NR_GENS 2#define MAX_NR_GENS ((unsigned int)CONFIG_NR_LRU_GENS) +/* +* Each generation is divided into multiple tiers. Tiers represent different +* ranges of numbers of accesses from file descriptors, i.e., +* mark_page_accessed(). In contrast to moving between generations which +* requires the lru lock, moving between tiers only involves an atomic +* operation on page->flags and therefore has a negligible cost. +* +* The purposes of tiers are to: +* 1) estimate whether pages accessed multiple times via file descriptors are +* more active than pages accessed only via page tables by separating the two +* access types into upper tiers and the base tier, and comparing refaulted % +* across all tiers. +* 2) improve buffered io performance by deferring the protection of pages +* accessed multiple times until the eviction. That is the protection happens +* in the reclaim path, not the access path. +* +* Pages accessed N times via file descriptors belong to tier order_base_2(N). +* The base tier may be marked by PageReferenced(). All upper tiers are marked +* by PageReferenced() && PageWorkingset(). Additional bits from page->flags are +* used to support more than one upper tier. +*/ +#define MAX_NR_TIERS ((unsigned int)CONFIG_TIERS_PER_GEN) +#define LRU_REFS_FLAGS (BIT(PG_referenced) | BIT(PG_workingset)) +/* Whether to keep stats for historical generations. */ #ifdef CONFIG_LRU_GEN_STATS #define NR_HIST_GENS ((unsigned int)CONFIG_NR_LRU_GENS)
@@ -337,6 +361,15 @@ struct lrugen {struct list_head lists[MAX_NR_GENS ][ANON_AND_FILE ][MAX_NR_ZONES ];/* the sizes of the multigenerational lru lists in pages */ unsigned long sizes[MAX_NR_GENS ][ANON_AND_FILE ][MAX_NR_ZONES ]; +/* the exponential moving average of refaulted */ +unsigned long avg_refaulted[ANON_AND_FILE ][MAX_NR_TIERS ]; +/* the exponential moving average of protected+evicted */ +unsigned long avg_total[ANON_AND_FILE ][MAX_NR_TIERS ]; +/* the base tier isn't protected, hence the minus one */ +unsigned long protected[NR_HIST_GENS ][ANON_AND_FILE ][MAX_NR_TIERS -1 ]; +/* incremented 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 multigenerational lru is enabled */ bool enabled[ANON_AND_FILE ]; };
mm/swap.c +42 -0
54 lines not on this page · raw message
mm/vmscan.c +554 -1
641 lines not on this page · raw message
mm/workingset.c +118 -2
152 lines not on this page · raw message
Signature · 1 line
2.34.0.rc0.344.g81b53c2807-goog
PATCH v5 8/10 mm: multigenerational lru: user interface
In reply to Yu ZhaoAdd /sys/kernel/mm/lru_gen/enabled to enable and disable the multigenerational lru at runtime.
Add /sys/kernel/mm/lru_gen/min_ttl_ms to protect the working set of a given number of milliseconds. The OOM killer is invoked if this working set cannot be kept in memory.
Add /sys/kernel/debug/lru_gen to monitor the multigenerational lru and invoke the aging and the eviction. This file has the following output:
memcg memcg_id memcg_path
node node_id
min_gen birth_time anon_size file_size
...
max_gen birth_time anon_size file_size
min_gen is the oldest generation number and max_gen is the youngest generation number. birth_time is in milliseconds. anon_size and file_size are in pages.
This file takes the following input:
+ memcg_id node_id max_gen [swappiness] [use_bloom_filter]
- memcg_id node_id min_gen [swappiness] [nr_to_reclaim]
The first command line invokes the aging, which scans PTEs for accessed pages and then creates the next generation max_gen+1. A swap file and a non-zero swappiness, which overrides vm.swappiness, are required to scan PTEs mapping anon pages. The second command line invokes the eviction, which evicts generations less than or equal to min_gen. min_gen should be less than max_gen-1 as max_gen and max_gen-1 are not fully aged and therefore cannot be evicted. Setting nr_to_reclaim to N limits the number of pages to evict. Setting use_bloom_filter to 0 overrides the default behavior which only scans PTE tables found populated. Multiple command lines are supported, as is concatenation with delimiters "," and ";".
--- include/linux/nodemask.h | 1 + mm/vmscan.c | 415 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 416 insertions(+)
include/linux/nodemask.h +1 -0
@@ -486,6 +486,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 +415 -0
433 lines not on this page · raw message
Signature · 1 line
2.34.0.rc0.344.g81b53c2807-goog
PATCH v5 9/10 mm: multigenerational lru: Kconfig
In reply to Yu ZhaoAdd configuration options for the multigenerational lru.
--- mm/Kconfig | 59 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+)
mm/Kconfig +59 -0
@@ -896,4 +896,63 @@ config SECRETMEM source "mm/damon/Kconfig" +# the multigenerational lru { +config LRU_GEN + bool "Multigenerational LRU" + depends on MMU + # the following options may leave not enough spare bits in page->flags + depends on !MAXSMP && (64BIT || !SPARSEMEM || SPARSEMEM_VMEMMAP) + help + A high performance LRU implementation to heavily overcommit workloads + that are not IO bound. See Documentation/vm/multigen_lru.rst for + details. + + Warning: do not enable this option unless you plan to use it because + it introduces a small per-process and per-memcg and per-node memory + overhead. + +config LRU_GEN_ENABLED + bool "Turn on by default" + depends on LRU_GEN + help + The default value of /sys/kernel/mm/lru_gen/enabled is 0. This option + changes it to 1. + + Warning: the default value is the fast path. See + Documentation/static-keys.txt for details. + +config LRU_GEN_STATS + bool "Full stats for debugging" + depends on LRU_GEN + help + This option keeps full stats for each generation, which can be read + from /sys/kernel/debug/lru_gen_full. + + Warning: do not enable this option unless you plan to use it because + it introduces an additional small per-process and per-memcg and + per-node memory overhead. + +config NR_LRU_GENS + int "Max number of generations" + depends on LRU_GEN + range 4 31 + default 7 + help + This will use order_base_2(N+1) spare bits from page flags. + + Warning: do not use numbers larger than necessary because each + generation introduces a small per-node and per-memcg memory overhead. + +config TIERS_PER_GEN + int "Number of tiers per generation" + depends on LRU_GEN + range 2 5 + default 4 + help + This will use N-2 spare bits from page flags. + + Larger values generally offer better protection to active pages under + heavy buffered I/O workloads. +# } + endmenu
Signature · 1 line
2.34.0.rc0.344.g81b53c2807-goog
PATCH v5 10/10 mm: multigenerational lru: documentation
In reply to Yu ZhaoAdd Documentation/vm/multigen_lru.rst.
--- Documentation/vm/index.rst | 1 + Documentation/vm/multigen_lru.rst | 132 ++++++++++++++++++++++++++++++ 2 files changed, 133 insertions(+) create mode 100644 Documentation/vm/multigen_lru.rst
Documentation/vm/index.rst +1 -0
@@ -17,6 +17,7 @@ various features of the Linux memory management swap_numa zswap + multigen_lru Kernel developers MM documentation ==================================
Documentation/vm/multigen_lru.rst new file +132 -0
132 lines not on this page · raw message
Signature · 1 line
2.34.0.rc0.344.g81b53c2807-goog
Kernel / Redis benchmark with MGLRU
Kernel / Redis benchmark with MGLRU
TLDR
====
With the MGLRU, Redis achieved 95% CIs [0.58, 5.94]%, [6.55, 14.58]%, [11.47, 19.36]%, [1.27, 3.54]%, [10.11, 14.81]% and [8.75, 13.64]% more operations per second (OPS), respectively, for sequential access w/ THP=always, random access w/ THP=always, Gaussian (distribution) access w/ THP=always, sequential access w/ THP=never, random access w/ THP=never and Gaussian access w/ THP=never.
Background
==========
Memory overcommit can increase utilization and, if carried out properly, can also increase throughput. The challenges are to improve working set estimation and to optimize page reclaim. The risks are performance degradation and OOM kills. Short of overcoming the challenges, the only way to reduce the risks is to underutilize memory.
Redis is one of the most popular open-source in-memory KV stores. memtier_benchmark is the leading open-source KV store benchmarking software that supports multiple access patterns. THP can have a negative effect under memory pressure, due to internal and/or external fragmentations.
Matrix
======
Kernels: version [+ patchset]
* Baseline: 5.15
* Patched: 5.15 + MGLRU
Memory utilization: % of memory size
* Underutilizing: N/A
* Overcommitting: ~10% swapped out (zram)
THP (2MB Transparent Huge Pages):
* Always
* Never
Access patterns (4kB objects, 100% read):
* Parallel sequential
* Uniform random
* Gaussian (SD = 1/6 of key range)
Concurrency: average # of users per CPU
* Low: 1
Total configurations: 12
Data points per configuration: 10
Total run duration (minutes) per data point: ~25
Note that the goal of this benchmark is to compare the performance for the same key range, object size, and hit ratio. Since Redis does not support eviction to backing storage, it would require fewer in-memory objects to underutilize memory, which reduces the hit ratio and therefore is not applicable in this case.
Procedure
=========
The latest MGLRU patchset for the 5.15 kernel is available at
git fetch https://linux-mm.googlesource.com/page-reclaim \ refs/changes/30/1430/2
Baseline and patched 5.15 kernel images are available at
https://drive.google.com/drive/folders/1eMkQleAFGkP2vzM_JyRA21oKE0ESHBqp
<install and configure OS>
<duplicate Redis service>
<for each kernel>
grub-set-default <baseline, patched>
<for each THP setting>
echo <always, never> >/sys/kernel/mm/transparent_hugepage/enabled <for each access pattern>
<update run_memtier.sh>
<for each data point>
reboot
run_memtier.sh
<collect total OPS>
Note that the OSS version of Redis does not support sharding, i.e., one service uses a single thread to serve all connections. Therefore, on larger machines, multiple Redis services are required to achieve better throughput.
Hardware
========
Memory (GB): 256
CPU (total #): 48
NVMe SSD (GB): 1024
OS
==
$ cat /etc/lsb-release DISTRIB_ID=Ubuntu DISTRIB_RELEASE=21.10 DISTRIB_CODENAME=impish DISTRIB_DESCRIPTION="Ubuntu 21.10"
$ cat /proc/swaps Filename Type Size Used Priority /dev/zram0 partition 10485756 0 1 /dev/zram1 partition 10485756 0 1 /dev/zram2 partition 10485756 0 1 /dev/zram3 partition 10485756 0 1
$ cat /sys/fs/cgroup/user.slice/memory.min 4294967296
$ cat /proc/sys/vm/overcommit_memory 1
Redis
=====
$ redis-server -v Redis server v=6.0.15 sha=00000000:0 malloc=jemalloc-5.2.1 bits=64 build=4610f4c3acf7fb25
$ cat /etc/redis/redis.conf <existing parameters> save "" unixsocket /var/run/redis/redis-server.sock
memtier_benchmark
=================
$ memtier_benchmark -v memtier_benchmark 1.3.0 Copyright (C) 2011-2020 Redis Labs 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.
$ cat run_memtier.sh
# load objects
for ((i = 0; i < 12; i++))
do
memtier_benchmark -S /var/run/redis$i/redis-server.sock -P redis \
-n allkeys -c 4 -t 4 --ratio 1:0 --pipeline 8 -d 4000 \
--key-minimum=1 --key-maximum=5300000 --key-pattern=P:P &
donewait
# run benchmark
for ((i = 0; i < 12; i++))
do
memtier_benchmark -S /var/run/redis$i/redis-server.sock -P redis \
--test-time=1200 -c 4 -t 4 --ratio 0:1 --pipeline 8 \
--randomize --distinct-client-seed --key-minimum=1 \
--key-maximum=5300000 --key-pattern=<P:P, R:R, G:G> &
donewait
Results
=======
Comparing the patched with the baseline kernel, Redis achieved 95% CIs [0.58, 5.94]%, [6.55, 14.58]%, [11.47, 19.36]%, [1.27, 3.54]%, [10.11, 14.81]% and [8.75, 13.64]% more OPS, respectively, for sequential access w/ THP=always, random access w/ THP=always, Gaussian access w/ THP=always, sequential access w/ THP=never, random access w/ THP=never and Gaussian access w/ THP=never.
+---------------------------+------------------+------------------+ | Mean million OPS [95% CI] | THP=always | THP=never | +---------------------------+------------------+------------------+ | Sequential access | 1.84 / 1.9 | 1.702 / 1.743 | | | [0.01, 0.109] | [0.021, 0.06] | +---------------------------+------------------+------------------+ | Random access | 1.742 / 1.926 | 1.493 / 1.679 | | | [0.114, 0.253] | [0.15, 0.221] | +---------------------------+------------------+------------------+ | Gaussian access | 1.771 / 2.044 | 1.635 / 1.818 | | | [0.203, 0.342] | [0.143, 0.222] | +---------------------------+------------------+------------------+
Table 1. Comparison between the baseline and patched kernels
Comparing THP=never with THP=always, Redis achieved 95% CIs [-8.66, -6.34]%, [-17.6, -10.98]% and [-10.92, -4.44]% more OPS, respectively, for sequential access, random access and Gaussian access when using the baseline kernel; 95% CIs [-10.83, -5.7]%, [-15.72, -9.93]% and [-13.92, -8.19]% more OPS, respectively, for sequential access, random access and Gaussian access when using the patched kernel.
+---------------------------+------------------+------------------+ | Mean million OPS [95% CI] | Baseline kernel | Patched kernel | +---------------------------+------------------+------------------+ | Sequential access | 1.84 / 1.702 | 1.9 / 1.743 | | | [-0.159, -0.116] | [-0.205, -0.108] | +---------------------------+------------------+------------------+ | Random access | 1.742 / 1.493 | 1.926 / 1.679 | | | [-0.306, -0.191] | [-0.302, -0.191] | +---------------------------+------------------+------------------+ | Gaussian access | 1.771 / 1.635 | 2.044 / 1.818 | | | [-0.193, -0.078] | [-0.284, -0.167] | +---------------------------+------------------+------------------+
Table 2. Comparison between THP=always and THP=never
Metrics collected during each run are available at
https://github.com/ediworks/KernelPerf/tree/master/mglru/redis/5.15
Appendix
========
$ cat raw_data_redis.r
v <- c(
# baseline THP=always sequential
1.81, 1.81, 1.82, 1.84, 1.84, 1.84, 1.84, 1.85, 1.87, 1.88,
# baseline THP=always random
1.66, 1.67, 1.69, 1.69, 1.72, 1.75, 1.75, 1.77, 1.84, 1.88,
# baseline THP=always Gaussian
1.69, 1.70, 1.72, 1.76, 1.76, 1.76, 1.76, 1.78, 1.84, 1.94,
# baseline THP=never sequential
1.68, 1.68, 1.69, 1.69, 1.69, 1.69, 1.71, 1.72, 1.72, 1.75,
# baseline THP=never random
1.45, 1.45, 1.46, 1.47, 1.47, 1.47, 1.50, 1.53, 1.55, 1.58,
# baseline THP=never Gaussian
1.59, 1.60, 1.60, 1.60, 1.61, 1.63, 1.65, 1.66, 1.70, 1.71,
# patched THP=always sequential
1.79, 1.81, 1.85, 1.88, 1.90, 1.91, 1.96, 1.96, 1.96, 1.98,
# patched THP=always random
1.81, 1.86, 1.88, 1.89, 1.91, 1.94, 1.95, 1.96, 1.97, 2.09,
# patched THP=always Gaussian
1.95, 1.95, 1.98, 2.00, 2.04, 2.05, 2.08, 2.09, 2.12, 2.18,
# patched THP=never sequential
1.71, 1.73, 1.73, 1.74, 1.74, 1.74, 1.75, 1.75, 1.77, 1.77,
# patched THP=never random
1.65, 1.65, 1.65, 1.67, 1.68, 1.68, 1.69, 1.69, 1.71, 1.72,
# patched THP=never Gaussian
1.76, 1.76, 1.78, 1.81, 1.82, 1.83, 1.83, 1.84, 1.87, 1.88
)a <- array(v, dim = c(10, 3, 2, 2))
# baseline vs patched
for (thp in 1:2) {
for (dist in 1:3) {
r <- t.test(a[, dist, thp, 1], a[, dist, thp, 2])
print(r) p <- r$conf.int * 100 / r$estimate[1]
if ((p[1] > 0 && p[2] < 0) || (p[1] < 0 && p[2] > 0)) {
s <- sprintf("thp%d dist%d: no significance", thp, dist)
} else {
s <- sprintf("thp%d dist%d: [%.2f, %.2f]%%", thp, dist, -p[2], -p[1])
}
print(s)
}
}# THP=always vs THP=never
for (kern in 1:2) {
for (dist in 1:3) {
r <- t.test(a[, dist, 1, kern], a[, dist, 2, kern])
print(r)
p <- r$conf.int * 100 / r$estimate[1]
if ((p[1] > 0 && p[2] < 0) || (p[1] < 0 && p[2] > 0)) {
s <- sprintf("kern%d dist%d: no significance", kern, dist)
} else {
s <- sprintf("kern%d dist%d: [%.2f, %.2f]%%", kern, dist, -p[2], -p[1])
}
print(s)
}
}$ R -q -s -f raw_data_redis.r
Welch Two Sample t-test
data: a[, dist, thp, 1] and a[, dist, thp, 2]
t = -2.6773, df = 11.109, p-value = 0.02135
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-0.10926587 -0.01073413
sample estimates:
mean of x mean of y
1.84 1.90
[1] "thp1 dist1: [0.58, 5.94]%"
Welch Two Sample t-test
data: a[, dist, thp, 1] and a[, dist, thp, 2]
t = -5.5311, df = 17.957, p-value = 3.011e-05 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-0.2539026 -0.1140974
sample estimates:
mean of x mean of y
1.742 1.926
[1] "thp1 dist2: [6.55, 14.58]%"
Welch Two Sample t-test
data: a[, dist, thp, 1] and a[, dist, thp, 2]
t = -8.2093, df = 17.98, p-value = 1.707e-07 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-0.3428716 -0.2031284
sample estimates:
mean of x mean of y
1.771 2.044
[1] "thp1 dist3: [11.47, 19.36]%"
Welch Two Sample t-test
data: a[, dist, thp, 1] and a[, dist, thp, 2]
t = -4.4705, df = 17.276, p-value = 0.0003243 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-0.06032607 -0.02167393
sample estimates:
mean of x mean of y
1.702 1.743
[1] "thp2 dist1: [1.27, 3.54]%"
Welch Two Sample t-test
data: a[, dist, thp, 1] and a[, dist, thp, 2]
t = -11.366, df = 13.885, p-value = 2.038e-08 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-0.2211244 -0.1508756
sample estimates:
mean of x mean of y
1.493 1.679
[1] "thp2 dist2: [10.11, 14.81]%"
Welch Two Sample t-test
data: a[, dist, thp, 1] and a[, dist, thp, 2]
t = -9.6138, df = 17.962, p-value = 1.663e-08 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-0.2229972 -0.1430028
sample estimates:
mean of x mean of y
1.635 1.818
[1] "thp2 dist3: [8.75, 13.64]%"
Welch Two Sample t-test
data: a[, dist, 1, kern] and a[, dist, 2, kern]
t = 13.532, df = 17.988, p-value = 7.194e-11 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
0.1165737 0.1594263
sample estimates:
mean of x mean of y
1.840 1.702
[1] "kern1 dist1: [-8.66, -6.34]%"
Welch Two Sample t-test
data: a[, dist, 1, kern] and a[, dist, 2, kern]
t = 9.197, df = 15.127, p-value = 1.386e-07
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
0.1913354 0.3066646
sample estimates:
mean of x mean of y
1.742 1.493
[1] "kern1 dist2: [-17.60, -10.98]%"
Welch Two Sample t-test
data: a[, dist, 1, kern] and a[, dist, 2, kern]
t = 5.0552, df = 14.669, p-value = 0.0001523 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
0.07854452 0.19345548
sample estimates:
mean of x mean of y
1.771 1.635
[1] "kern1 dist3: [-10.92, -4.44]%"
Welch Two Sample t-test
data: a[, dist, 1, kern] and a[, dist, 2, kern]
t = 7.1487, df = 10.334, p-value = 2.614e-05 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
0.1082788 0.2057212
sample estimates:
mean of x mean of y
1.900 1.743
[1] "kern2 dist1: [-10.83, -5.70]%"
Welch Two Sample t-test
data: a[, dist, 1, kern] and a[, dist, 2, kern]
t = 9.7525, df = 10.871, p-value = 1.042e-06 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
0.1911754 0.3028246
sample estimates:
mean of x mean of y
1.926 1.679
[1] "kern2 dist2: [-15.72, -9.93]%"
Welch Two Sample t-test
data: a[, dist, 1, kern] and a[, dist, 2, kern]
t = 8.2831, df = 13.988, p-value = 9.168e-07 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
0.167476 0.284524
sample estimates:
mean of x mean of y
2.044 1.818
[1] "kern2 dist3: [-13.92, -8.19]%"
Kernel / Apache Cassandra benchmark with MGLRU
Kernel / Apache Cassandra benchmark with MGLRU
TLDR
====
With the MGLRU, Apache Cassandra 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 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 set to minimum (vm.swappiness=1).
Background
==========
Memory overcommit can increase utilization and, if carried out properly, can also increase throughput. The challenges are to improve working set estimation and to optimize page reclaim. The risks are performance degradation and OOM kills. Short of overcoming the challenges, the only way to reduce the risks is to underutilize memory.
Apache Cassandra is one of the most popular open-source NoSQL databases. YCSB is the leading open-source NoSQL database benchmarking software that supports multiple access distributions. Swap can have a negative effect, as Apache Cassandra cautions "Do never allow your system to swap" [1].
[1]: https://github.com/apache/cassandra/blob/trunk/conf/cassandra.yaml#L394
Matrix
======
Kernels: version [+ patchset]
* Baseline: 5.15
* Patched: 5.15 + MGLRU
Swap configurations:
* Off
* Minimum (vm.swappiness=1)
Concurrency: average # of users per CPU
* Medium: 3
Access distributions (2kB objects, 10% update):
* Exponential
* Uniform random
* Zipfian
Total configurations: 12
Data points per configuration: 10
Total run duration (minutes) per data point: ~40
Note that Apache Cassandra reached the peak performance for this benchmark with 2-3 users per CPU, i.e., its performance started degrading with fewer or more users.
Procedure
=========
The latest MGLRU patchset for the 5.15 kernel is available at
git fetch https://linux-mm.googlesource.com/page-reclaim \ refs/changes/30/1430/2
Baseline and patched 5.15 kernel images are available at
https://drive.google.com/drive/folders/1eMkQleAFGkP2vzM_JyRA21oKE0ESHBqp
<install and configure OS>ycsb_load.sh
systemctl stop cassandra
e2image <backup /mnt/data>
<for each kernel>
grub-set-default <baseline, patched>
<for each swap configuration>
<swapoff, swapon>
<for each access distribution>
<update ycsb_run.sh>
<for each data point>
systemctl stop cassandra
e2image <restore /mnt/data>
reboot
ycsb_run.sh
<collect OPS>
Hardware
========
Memory (GB): 256
CPU (total #): 48
NVMe SSD (GB): 1024
OS
==
$ cat /etc/lsb-release DISTRIB_ID=Ubuntu DISTRIB_RELEASE=21.10 DISTRIB_CODENAME=impish DISTRIB_DESCRIPTION="Ubuntu 21.10"
$ cat /proc/swaps Filename Type Size Used Priority /dev/nvme0n1p3 partition 32970748 0 -2
$ cat /sys/fs/cgroup/user.slice/memory.min 4294967296
$ cat /proc/sys/vm/overcommit_memory 1
$ cat /proc/sys/vm/swappiness 1
$ cat /proc/sys/vm/max_map_count 1048575
Apache Cassandra
================
$ nodetool version ReleaseVersion: 4.0.1
$ cat jvm8-server.options <existing parameters>
#-XX:+UseParNewGC
#-XX:+UseConcMarkSweepGC
#-XX:+CMSParallelRemarkEnabled
#-XX:SurvivorRatio=8
#-XX:MaxTenuringThreshold=1
#-XX:CMSInitiatingOccupancyFraction=75
#-XX:+UseCMSInitiatingOccupancyOnly
#-XX:CMSWaitDuration=10000
#-XX:+CMSParallelInitialMarkEnabled
#-XX:+CMSEdenChunksRecordAlways
#-XX:+CMSClassUnloadingEnabled
-XX:+UseG1GC
-XX:+ParallelRefProcEnabled
-XX:MaxGCPauseMillis=400
<existing parameters>
$ cat cassandra.yaml <existing parameters>
data_file_directories: /mnt/data/key_cache_size_in_mb: 5000file_cache_enabled: truefile_cache_size_in_mb: 10000buffer_pool_use_heap_if_exhausted: falsememtable_offheap_space_in_mb: 10000memtable_allocation_type: offheap_buffers
<existing parameters>
YCSB
====
$ git log commit ce3eb9ce51c84ee9e236998cdd2cefaeb96798a8 (HEAD -> master, origin/master, origin/HEAD) Author: Ivan <[email protected]> Date: Tue Feb 16 17:38:00 2021 +0200
[scylla] enable token aware LB by default, improve the docs (#1507)
$ cat ycsb_load.sh
# load objects
cqlsh -e "create keyspace ycsb WITH REPLICATION = {'class' : \
'SimpleStrategy', 'replication_factor': 1};"
cqlsh -k ycsb -e "create table usertable (y_id varchar primary key, \
field0 varchar, field1 varchar, field2 varchar, field3 varchar, \
field4 varchar, field5 varchar ,field6 varchar, field7 varchar, \
field8 varchar, field9 varchar);"
ycsb load cassandra-cql -s -threads 24 -p hosts=localhost \
-p workload=site.ycsb.workloads.CoreWorkload -p fieldlength=200 \
-p recordcount=130000000$ cat ycsb_run.sh
# run benchmark
ycsb run cassandra-cql -s -threads 144 -p hosts=localhost \
-p workload=site.ycsb.workloads.CoreWorkload \
-p recordcount=130000000 -p operationcount=130000000 \
-p readproportion=0.9 -p updateproportion=0.1 \
-p maxexecutiontime=1800 \
-p requestdistribution=<exponential, uniform, zipfian>Results
=======
Comparing the patched with the baseline kernel, Apache Cassandra achieved 95% CIs [1.06, 4.10]%, [1.94, 5.43]% and [4.11, 7.50]% more OPS, respectively, for exponential access, random access and Zipfian 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 set to minimum (vm.swappiness=1).
+--------------------+--------------------+---------------------+ | Mean OPS [95% CI] | No swap | Minimum swap | +--------------------+--------------------+---------------------+ | Exponential access | 71084.9 / 72917.5 | 71499.6 / 72607.9 | | | [751.42, 2913.77] | [358.40, 1858.19] | +--------------------+--------------------+---------------------+ | Random access | 47127.2 / 48862.8 | 47585.4 / 51220.1 | | | [912.68, 2558.51] | [3097.39, 4172.00] | +--------------------+--------------------+---------------------+ | Zipfian access | 70271.5 / 74348.8 | 70698.2 / 74248.3 | | | [2887.20, 5267.39] | [2326.69, 4773.50] | +--------------------+--------------------+---------------------+
Table 1. Comparison between the baseline and the patched kernels
Comparing minimum swap with no swap, Apache Cassandra achieved 95% CIs [4.05, 5.60]% more OPS for random access, when using the patched kernel. There were no statistically significant changes in OPS under other conditions.
+--------------------+--------------------+---------------------+ | Mean OPS [95% CI] | Baseline kernel | Patched kernel | +--------------------+--------------------+---------------------+ | Exponential access | 71084.9 / 71499.6 | 72917.5 / 72607.9 | | | [-358.97, 1188.37] | [-1376.93, 757.73] | +--------------------+--------------------+---------------------+ | Random access | 47127.2 / 47585.4 | 48862.8 / 51220.1 | | | [-424.55, 1340.95] | [1977.09, 2737.50] | +--------------------+--------------------+---------------------+ | Zipfian access | 70271.5 / 70698.2 | 74348.8 / 74248.3 | | | [-749.39, 1602.79] | [-1337.07, 1136.07] | +--------------------+--------------------+---------------------+
Table 2. Comparison between no swap and minimum swap
Metrics collected during each run are available at
https://github.com/ediworks/KernelPerf/tree/master/mglru/cassandra/5.15
Appendix
========
$ cat raw_data_cassandra.r
v <- c(
# baseline swapoff exp
69952, 70274, 70286, 70818, 70946, 71202, 71244, 71615, 71787, 72725,
# baseline swapoff uni
45309, 46056, 46086, 46188, 47275, 47524, 47797, 48243, 48329, 48465,
# baseline swapoff zip
69096, 69194, 69386, 69408, 69412, 70795, 70890, 71170, 71232, 72132,
# baseline swapon exp
69836, 70783, 70951, 71188, 71521, 71764, 72035, 72166, 72287, 72465,
# baseline swapon uni
46089, 46963, 47308, 47599, 47776, 47822, 47952, 48042, 48092, 48211,
# baseline swapon zip
68986, 69279, 69290, 69805, 70146, 70913, 71462, 71978, 72370, 72753,
# patched swapoff exp
70701, 71328, 71458, 72846, 72885, 73078, 73702, 74077, 74415, 74685,
# patched swapoff uni
48275, 48460, 48735, 48813, 48902, 48969, 48996, 49007, 49213, 49258,
# patched swapoff zip
71829, 72909, 73259, 73835, 74200, 74544, 75318, 75514, 76031, 76049,
# patched swapon exp
71169, 71968, 72208, 72374, 72401, 72755, 72861, 72942, 73469, 73932,
# patched swapon uni
50292, 50529, 50981, 51224, 51414, 51420, 51480, 51608, 51625, 51628,
# patched swapon zip
72032, 72325, 73834, 74366, 74482, 74573, 74810, 75044, 75371, 75646
)a <- array(v, dim = c(10, 3, 2, 2))
# baseline vs patched
for (swap in 1:2) {
for (dist in 1:3) {
r <- t.test(a[, dist, swap, 1], a[, dist, swap, 2])
print(r) p <- r$conf.int * 100 / r$estimate[1]
if ((p[1] > 0 && p[2] < 0) || (p[1] < 0 && p[2] > 0)) {
s <- sprintf("swap%d dist%d: no significance", swap, dist)
} else {
s <- sprintf("swap%d dist%d: [%.2f, %.2f]%%", swap, dist, -p[2], -p[1])
}
print(s)
}
}# swapoff vs swapon
for (kern in 1:2) {
for (dist in 1:3) {
r <- t.test(a[, dist, 1, kern], a[, dist, 2, kern])
print(r) p <- r$conf.int * 100 / r$estimate[1]
if ((p[1] > 0 && p[2] < 0) || (p[1] < 0 && p[2] > 0)) {
s <- sprintf("kern%d dist%d: no significance", kern, dist)
} else {
s <- sprintf("kern%d dist%d: [%.2f, %.2f]%%", kern, dist, -p[2], -p[1])
}
print(s)
}
}$ R -q -s -f raw_data_cassandra.r
Welch Two Sample t-test
data: a[, dist, swap, 1] and a[, dist, swap, 2]
t = -3.6172, df = 14.793, p-value = 0.002585 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-2913.7703 -751.4297
sample estimates:
mean of x mean of y
71084.9 72917.5
[1] "swap1 dist1: [1.06, 4.10]%"
Welch Two Sample t-test
data: a[, dist, swap, 1] and a[, dist, swap, 2]
t = -4.679, df = 10.331, p-value = 0.0007961 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-2558.5199 -912.6801
sample estimates:
mean of x mean of y
47127.2 48862.8
[1] "swap1 dist2: [1.94, 5.43]%"
Welch Two Sample t-test
data: a[, dist, swap, 1] and a[, dist, swap, 2]
t = -7.2315, df = 16.902, p-value = 1.452e-06 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-5267.396 -2887.204
sample estimates:
mean of x mean of y
70271.5 74348.8
[1] "swap1 dist3: [4.11, 7.50]%"
Welch Two Sample t-test
data: a[, dist, swap, 1] and a[, dist, swap, 2]
t = -3.1057, df = 17.95, p-value = 0.006118
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-1858.191 -358.409
sample estimates:
mean of x mean of y
71499.6 72607.9
[1] "swap2 dist1: [0.50, 2.60]%"
Welch Two Sample t-test
data: a[, dist, swap, 1] and a[, dist, swap, 2]
t = -14.307, df = 16.479, p-value = 1.022e-10 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-4172.006 -3097.394
sample estimates:
mean of x mean of y
47585.4 51220.1
[1] "swap2 dist2: [6.51, 8.77]%"
Welch Two Sample t-test
data: a[, dist, swap, 1] and a[, dist, swap, 2]
t = -6.1048, df = 17.664, p-value = 9.877e-06 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-4773.504 -2326.696
sample estimates:
mean of x mean of y
70698.2 74248.3
[1] "swap2 dist3: [3.29, 6.75]%"
Welch Two Sample t-test
data: a[, dist, 1, kern] and a[, dist, 2, kern]
t = -1.1261, df = 17.998, p-value = 0.2749
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-1188.3785 358.9785
sample estimates:
mean of x mean of y
71084.9 71499.6
[1] "kern1 dist1: no significance"
Welch Two Sample t-test
data: a[, dist, 1, kern] and a[, dist, 2, kern]
t = -1.1108, df = 14.338, p-value = 0.2849
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-1340.9555 424.5555
sample estimates:
mean of x mean of y
47127.2 47585.4
[1] "kern1 dist2: no significance"
Welch Two Sample t-test
data: a[, dist, 1, kern] and a[, dist, 2, kern]
t = -0.76534, df = 17.035, p-value = 0.4545
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-1602.7926 749.3926
sample estimates:
mean of x mean of y
70271.5 70698.2
[1] "kern1 dist3: no significance"
Welch Two Sample t-test
data: a[, dist, 1, kern] and a[, dist, 2, kern]
t = 0.62117, df = 14.235, p-value = 0.5443
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-757.7355 1376.9355
sample estimates:
mean of x mean of y
72917.5 72607.9
[1] "kern2 dist1: no significance"
Welch Two Sample t-test
data: a[, dist, 1, kern] and a[, dist, 2, kern]
t = -13.18, df = 15.466, p-value = 8.07e-10
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-2737.509 -1977.091
sample estimates:
mean of x mean of y
48862.8 51220.1
[1] "kern2 dist2: [4.05, 5.60]%"
Welch Two Sample t-test
data: a[, dist, 1, kern] and a[, dist, 2, kern]
t = 0.17104, df = 17.575, p-value = 0.8661
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-1136.076 1337.076
sample estimates:
mean of x mean of y
74348.8 74248.3
[1] "kern2 dist3: no significance"
Kernel / Apache Hadoop benchmark with MGLRU
Kernel / Apache Hadoop benchmark with MGLRU
TLDR
====
With the MGLRU, Apache Hadoop took 95% CIs [5.31, 9.69]% and [2.02, 7.86]% less wall time to finish TeraSort, respectively, under the medium- and the high-concurrency conditions, when swap was on. There were no statistically significant changes in wall time for the rest of the test matrix.
Background
==========
Memory overcommit can increase utilization and, if carried out properly, can also increase throughput. The challenges are to improve working set estimation and to optimize page reclaim. The risks are performance degradation and OOM kills. Short of overcoming the challenges, the only way to reduce the risks is to underutilize memory.
Apache Hadoop is one of the most popular open-source big-data frameworks. TeraSort is the most widely used benchmark for Apache Hadoop.
Matrix
======
Kernels: version [+ patchset]
* Baseline: 5.15
* Patched: 5.15 + MGLRU
Swap configurations:
* Off
* On
Concurrency conditions: average # of tasks per CPU
* Low: 1/2
* Medium: 1
* High: 2
Cluster mode: local (12 concurrent jobs)
Dataset size: 100 million records from TeraGen
Total configurations: 12
Data points per configuration: 10
Total run duration (minutes) per data point: ~20
Procedure
=========
The latest MGLRU patchset for the 5.15 kernel is available at
git fetch https://linux-mm.googlesource.com/page-reclaim \ refs/changes/30/1430/2
Baseline and patched 5.15 kernel images are available at
https://drive.google.com/drive/folders/1eMkQleAFGkP2vzM_JyRA21oKE0ESHBqp
<install and configure OS>
teragen 100000000 /mnt/data/raw
e2image <backup /mnt/data>
<for each kernel>
grub-set-default <baseline, patched>
<for each swap configuration>
<swapoff, swapon>
<update run_terasort.sh>
<for each concurrency condition>
<update run_terasort.sh>
<for each data point>
e2image <restore /mnt/data>
reboot
run_terasort.sh
<collect wall time>
Hardware
========
Memory (GB): 256
CPU (total #): 48
NVMe SSD (GB): 2048
OS
==
$ cat /etc/lsb-release DISTRIB_ID=Ubuntu DISTRIB_RELEASE=21.10 DISTRIB_CODENAME=impish DISTRIB_DESCRIPTION="Ubuntu 21.10"
$ cat /proc/swaps Filename Type Size Used Priority /swap.img partition 67108860 0 -2
$ cat /proc/sys/vm/overcommit_memory 1
$ cat /proc/sys/vm/swappiness 1
Apache Hadoop
=============
$ hadoop version Hadoop 3.3.1 Source code repository https://github.com/apache/hadoop.git -r a3b9c37a397ad4188041dd80621bdeefc46885f2 Compiled by ubuntu on 2021-06-15T05:13Z Compiled with protoc 3.7.1 From source with checksum 88a4ddb2299aca054416d6b7f81ca55 This command was run using /root/hadoop-3.3.1/share/hadoop/common/hadoop-common-3.3.1.jar
$ cat run_terasort.sh export HADOOP_ROOT_LOGGER="WARN,DRFA" export HADOOP_HEAPSIZE_MAX=<swapoff: 20G, swapon: 22G>
for ((i = 0; i < 12; i++))
do
/usr/bin/time -f "%e" hadoop jar \
hadoop-mapreduce-examples-3.3.1.jar terasort \
-Dfile.stream-buffer-size=8388608 \
-Dio.file.buffer.size=8388608 \
-Dmapreduce.job.heap.memory-mb.ratio=1.0 \
-Dmapreduce.reduce.input.buffer.percent=1.0 \
-Dmapreduce.reduce.merge.inmem.threshold=0 \
-Dmapreduce.task.io.sort.factor=100 \
-Dmapreduce.task.io.sort.mb=1000 \
-Dmapreduce.terasort.final.sync=false \
-Dmapreduce.terasort.num.partitions=100 \
-Dmapreduce.terasort.partitions.sample=1000000 \
-Dmapreduce.local.map.tasks.maximum=<2, 4, 8> \
-Dmapreduce.local.reduce.tasks.maximum=<2, 4, 8> \
-Dmapreduce.reduce.shuffle.parallelcopies=<2, 4, 8> \
-Dhadoop.tmp.dir=/mnt/data/tmp$i \
/mnt/data/raw /mnt/data/sorted$idone
wait
Results
=======
Comparing the patched with the baseline kernel, Apache Hadoop took 95% CIs [5.31, 9.69]% and [2.02, 7.86]% less wall time to finish TeraSort, respectively, under the medium- and the high-concurrency conditions, when swap was on. There were no statistically significant changes in wall time for the rest of the test matrix.
+--------------------+------------------+------------------+ | Mean wall time (s) | Swap off | Swap on | | [95% CI] | | | +--------------------+------------------+------------------+ | Low concurrency | 758.43 / 746.83 | 740.78 / 733.42 | | | [-26.80, 3.60] | [-18.07, 3.35] | +--------------------+------------------+------------------+ | Medium concurrency | 911.81 / 910.19 | 911.53 / 843.15 | | | [-26.70, 23.46] | [-88.35, -48.39] | +--------------------+------------------+------------------+ | High concurrency | 921.17 / 929.51 | 1042.85 / 991.33 | | | [-25.50, 42.18] | [-81.94, -21.08] | +--------------------+------------------+------------------+
Table 1. Comparison between the baseline and the patched kernels
Comparing swap on with swap off, Apache Hadoop took 95% CIs [-3.39, -1.27]% and [10.69, 15.73]% more wall time to finish TeraSort, respectively, under the low- and the high-concurrency conditions, when using the baseline kernel; 95% CIs [-9.34, -5.39]% and [2.52, 10.78]% more wall time, respectively, under the medium- and the high-concurrency conditions, when using the patched kernel. There were no statistically significant changes in wall time for the rest of the test matrix.
+--------------------+------------------+------------------+ | Mean wall time (s) | Baseline kernel | Patched kernel | | [95% CI] | | | +--------------------+------------------+------------------+ | Low concurrency | 758.43 / 740.78 | 746.83 / 733.42 | | | [-25.67, -9.64] | [-29.80, 2.97] | +--------------------+------------------+------------------+ | Medium concurrency | 911.81 / 911.53 | 910.19 / 843.15 | | | [-26.62, 26.06] | [-84.98, -49.09] | +--------------------+------------------+------------------+ | High concurrency | 921.17 / 1042.85 | 929.51 / 991.33 | | | [98.51, 144.85] | [23.43, 100.21] | +--------------------+------------------+------------------+
Table 2. Comparison between swap off and on
Metrics collected during each run are available at
https://github.com/ediworks/KernelPerf/tree/master/mglru/hadoop/5.15
Appendix
========
$ cat raw_data_hadoop.r
v <- c(
# baseline swapoff 2mr
742.83, 751.91, 755.75, 757.50, 757.83, 758.16, 758.25, 763.58, 766.58, 772.00,
# baseline swapoff 4mr
863.25, 868.08, 886.58, 894.66, 901.16, 918.25, 940.91, 944.08, 949.66, 951.50,
# baseline swapoff 8mr
892.16, 895.75, 909.25, 922.58, 922.91, 922.91, 923.16, 926.00, 935.33, 961.66,
# baseline swapon 2mr
731.58, 732.08, 736.66, 737.75, 738.00, 738.08, 740.08, 740.33, 752.58, 760.66,
# baseline swapon 4mr
878.83, 886.33, 902.75, 904.83, 907.25, 918.50, 921.33, 925.50, 927.58, 942.41,
# baseline swapon 8mr
1016.58, 1017.33, 1019.33, 1019.50, 1026.08, 1030.50, 1065.16, 1070.50, 1075.25, 1088.33,
# patched swapoff 2mr
720.41, 724.58, 727.41, 732.00, 745.41, 748.00, 754.50, 767.91, 773.16, 775.00,
# patched swapoff 4mr
887.16, 887.50, 906.66, 907.41, 915.00, 915.58, 915.66, 916.91, 925.00, 925.08,
# patched swapoff 8mr
857.08, 864.41, 910.25, 918.58, 921.91, 933.75, 949.50, 966.75, 984.00, 988.91,
# patched swapon 2mr
719.33, 721.91, 724.41, 724.83, 725.75, 728.75, 737.83, 743.91, 749.41, 758.08,
# patched swapon 4mr
813.33, 819.00, 821.91, 829.33, 839.50, 846.75, 850.25, 857.00, 875.83, 878.66,
# patched swapon 8mr
929.41, 955.83, 961.16, 974.66, 988.75, 1004.00, 1009.08, 1019.91, 1030.58, 1040.00
)a <- array(v, dim = c(10, 3, 2, 2))
# baseline vs patched
for (swap in 1:2) {
for (mr in 1:3) {
r <- t.test(a[, mr, swap, 1], a[, mr, swap, 2])
print(r) p <- r$conf.int * 100 / r$estimate[1]
if ((p[1] > 0 && p[2] < 0) || (p[1] < 0 && p[2] > 0)) {
s <- sprintf("swap%d mr%d: no significance", swap, mr)
} else {
s <- sprintf("swap%d mr%d: [%.2f, %.2f]%%", swap, mr, -p[2], -p[1])
}
print(s)
}
}# swapoff vs swapon
for (kern in 1:2) {
for (mr in 1:3) {
r <- t.test(a[, mr, 1, kern], a[, mr, 2, kern])
print(r) p <- r$conf.int * 100 / r$estimate[1]
if ((p[1] > 0 && p[2] < 0) || (p[1] < 0 && p[2] > 0)) {
s <- sprintf("kern%d mr%d: no significance", kern, mr)
} else {
s <- sprintf("kern%d mr%d: [%.2f, %.2f]%%", kern, mr, -p[2], -p[1])
}
print(s)
}
}$ R -q -s -f raw_data_hadoop.r
Welch Two Sample t-test
data: a[, mr, swap, 1] and a[, mr, swap, 2]
t = 1.6677, df = 11.658, p-value = 0.122
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-3.604753 26.806753
sample estimates:
mean of x mean of y
758.439 746.838
[1] "swap1 mr1: no significance"
Welch Two Sample t-test
data: a[, mr, swap, 1] and a[, mr, swap, 2]
t = 0.14071, df = 11.797, p-value = 0.8905
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-23.4695 26.7035
sample estimates:
mean of x mean of y
911.813 910.196
[1] "swap1 mr2: no significance"
Welch Two Sample t-test
data: a[, mr, swap, 1] and a[, mr, swap, 2]
t = -0.53558, df = 12.32, p-value = 0.6018
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-42.18602 25.50002
sample estimates:
mean of x mean of y
921.171 929.514
[1] "swap1 mr3: no significance"
Welch Two Sample t-test
data: a[, mr, swap, 1] and a[, mr, swap, 2]
t = 1.4568, df = 15.95, p-value = 0.1646
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-3.352318 18.070318
sample estimates:
mean of x mean of y
740.780 733.421
[1] "swap2 mr1: no significance"
Welch Two Sample t-test
data: a[, mr, swap, 1] and a[, mr, swap, 2]
t = 7.204, df = 17.538, p-value = 1.229e-06
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
48.39677 88.35323
sample estimates:
mean of x mean of y
911.531 843.156
[1] "swap2 mr2: [-9.69, -5.31]%"
Welch Two Sample t-test
data: a[, mr, swap, 1] and a[, mr, swap, 2]
t = 3.5698, df = 17.125, p-value = 0.002336
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
21.08655 81.94945
sample estimates:
mean of x mean of y
1042.856 991.338
[1] "swap2 mr3: [-7.86, -2.02]%"
Welch Two Sample t-test
data: a[, mr, 1, kern] and a[, mr, 2, kern]
t = 4.6319, df = 17.718, p-value = 0.0002153 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
9.640197 25.677803
sample estimates:
mean of x mean of y
758.439 740.780
[1] "kern1 mr1: [-3.39, -1.27]%"
Welch Two Sample t-test
data: a[, mr, 1, kern] and a[, mr, 2, kern]
t = 0.0229, df = 14.372, p-value = 0.982
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-26.06533 26.62933
sample estimates:
mean of x mean of y
911.813 911.531
[1] "kern1 mr2: no significance"
Welch Two Sample t-test
data: a[, mr, 1, kern] and a[, mr, 2, kern]
t = -11.129, df = 16.051, p-value = 5.874e-09 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-144.8574 -98.5126
sample estimates:
mean of x mean of y
921.171 1042.856
[1] "kern1 mr3: [10.69, 15.73]%"
Welch Two Sample t-test
data: a[, mr, 1, kern] and a[, mr, 2, kern]
t = 1.7413, df = 15.343, p-value = 0.1016
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-2.974529 29.808529
sample estimates:
mean of x mean of y
746.838 733.421
[1] "kern2 mr1: no significance"
Welch Two Sample t-test
data: a[, mr, 1, kern] and a[, mr, 2, kern]
t = 7.9839, df = 14.571, p-value = 1.073e-06 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
49.09637 84.98363
sample estimates:
mean of x mean of y
910.196 843.156
[1] "kern2 mr2: [-9.34, -5.39]%"
Welch Two Sample t-test
data: a[, mr, 1, kern] and a[, mr, 2, kern]
t = -3.3962, df = 17.1, p-value = 0.003413
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-100.21425 -23.43375
sample estimates:
mean of x mean of y
929.514 991.338
[1] "kern2 mr3: [2.52, 10.78]%"
Kernel / PostgreSQL benchmark with MGLRU
Kernel / PostgreSQL benchmark with MGLRU
TLDR
====
With the MGLRU, PostgreSQL achieved 95% CI [1.75, 6.42]% more transactions per minute (TPM) under the high-concurrency conditions, 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 test matrix.
Background
==========
Memory overcommit can increase utilization and, if carried out properly, can also increase throughput. The challenges are to improve working set estimation and to optimize page reclaim. The risks are performance degradation and OOM kills. Short of overcoming the challenges, the only way to reduce the risks is to underutilize memory.
PostgreSQL is one of the most popular open-source RDBMSs. HammerDB is the leading open-source benchmarking software derived from the TPC specifications. OLTP is the most important use case for RDBMSs.
Matrix
======
Kernels: version [+ patchset]
* Baseline: 5.15
* Patched: 5.15 + MGLRU
Swap configurations:
* Off
* On (vm.swappiness=1)
Concurrency conditions: average # of users per CPU
* Low: ~4
* Medium: ~8
* High: ~12
Total configurations: 12
Data points per configuration: 10
Total run duration (minutes) per data point: ~50
Procedure
=========
The latest MGLRU patchset for the 5.15 kernel is available at
git fetch https://linux-mm.googlesource.com/page-reclaim \ refs/changes/30/1430/2
The baseline and the patched 5.15 kernel images are available at
https://drive.google.com/drive/folders/1eMkQleAFGkP2vzM_JyRA21oKE0ESHBqp
<install and configure OS>
hammerdbcli auto prep_tpcc.tcl
systemctl stop postgresql
e2image <backup /mnt/data>
<for each kernel>
grub-set-default <baseline, patched>
<for each swap configuration>
<swapoff, swapon>
<update /etc/postgresql/13/main/postgresql.conf> <for each concurrency condition>
<update run_tpcc.tcl>
<for each data point>
systemctl stop postgresql e2image <restore /mnt/data> reboot
hammerdbcli auto run_tpcc.tcl <collect TPM>
Hardware
========
Memory (GB): 256
CPU (total #): 48
NVMe SSD (GB): 2048
OS
==
$ cat /etc/lsb-release DISTRIB_ID=Ubuntu DISTRIB_RELEASE=21.10 DISTRIB_CODENAME=impish DISTRIB_DESCRIPTION="Ubuntu 21.10"
$ cat /proc/swaps Filename Type Size Used Priority /swap.img partition 67108860 0 -2
$ cat /proc/sys/vm/overcommit_memory 1
$ cat /proc/sys/vm/swappiness 1
$ cat /sys/fs/cgroup/user.slice/memory.min 4294967296
PostgreSQL
==========
$ pg_config --version PostgreSQL 13.5 (Ubuntu 13.5-0ubuntu0.21.10.1)
$ cat /etc/postgresql/13/main/postgresql.conf <existing parameters>
data_directory = '/mnt/data'max_connections = 1000shared_buffers = <swapoff: 120GB, swapon: 150GB>temp_buffers = 1GBwork_mem = 1GBmaintenance_work_mem = 1GBlogical_decoding_work_mem = 1GBbgwriter_delay = 1000msbgwriter_lru_maxpages = 100000bgwriter_lru_multiplier = 1.0bgwriter_flush_after = 0effective_io_concurrency = 1000wal_compression = onwal_writer_delay = 1000mswal_writer_flush_after = 128MBmax_wal_size = 100GBmin_wal_size = 10GBcheckpoint_flush_after = 0effective_cache_size = 150GB
<existing parameters>
HammerDB
========
$ hammerdbcli -h HammerDB CLI v4.3 Copyright (C) 2003-2021 Steve Shaw Type "help" for a list of commands Usage: hammerdbcli [ auto [ script_to_autoload.tcl ] ]
$ cat prep_tpcc.tcl dbset db pg diset connection pg_host /var/run/postgresql diset tpcc pg_count_ware 2400 diset tpcc pg_num_vu 48 buildschema waittocomplete quit
$ cat run_tpcc.tcl dbset db pg diset connection pg_host /var/run/postgresql diset tpcc pg_total_iterations 20000000 diset tpcc pg_driver timed diset tpcc pg_rampup 30 diset tpcc pg_duration 10 diset tpcc pg_allwarehouse true vuset logtotemp 1 vuset unique 1 loadscript vuset vu <200, 400, 600> vucreate vurun runtimer 3000 vudestroy
Results
=======
Comparing the patched with the baseline kernel, PostgreSQL achieved 95% CI [1.75, 6.42]% more TPM under the high-concurrency conditions, 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 test matrix.
+--------------------+--------------------+--------------------+ | Mean TPM [95% CI] | Swap off | Swap on | +--------------------+--------------------+--------------------+ | Low concurrency | 466430 / 467521 | 475060 / 475047 | | | [-6931, 9112] | [-7431, 7405] | +--------------------+--------------------+--------------------+ | Medium concurrency | 453871 / 459592 | 388245 / 449409 | | | [-774, 12216] | [49755, 72572] | +--------------------+--------------------+--------------------+ | High concurrency | 443014 / 461112 | 157106 / 211752 | | | [7771, 28423] | [35664, 73627] | +--------------------+--------------------+--------------------+
Table 1. Comparison between the baseline and the patched kernels
Comparing swap on with swap off, PostgreSQL achieved 95% CIs [0.46, 3.24]%, [-16.91, -12.01]% and [-68.64, -60.43]% more TPM, respectively, under the low-, the medium- and the high-concurrency conditions, when using the baseline kernel; 95% CIs [-3.76, -0.67]% and [-56.70, -51.46]% more TPM, respectively, under the medium- and the high-concurrency conditions, when using the patched kernel. There were no statistically significant changes in TPM for the rest of the test matrix.
+--------------------+--------------------+--------------------+ | Mean TPM [95% CI] | Baseline kernel | Patched kernel | +--------------------+--------------------+--------------------+ | Low concurrency | 466430 / 475060 | 467521 / 475047 | | | [2160, 15100] | [-1204, 16256] | +--------------------+--------------------+--------------------+ | Medium concurrency | 453871 / 388245 | 459592 / 449409 | | | [-76757, -54494] | [-17292, -3073] | +--------------------+--------------------+--------------------+ | High concurrency | 443014 / 157106 | 461112 / 211752 | | | [-304097, -267718] | [-261442, -237275] | +--------------------+--------------------+--------------------+
Table 2. Comparison between swap off and swap on
Metrics collected during each run are available at
https://github.com/ediworks/KernelPerf/tree/master/mglru/postgres/5.15
Appendix
========
$ cat raw_data_postgres.r
v <- c(
# baseline swapoff 200vu
462379, 462998, 463363, 464949, 465605, 466977, 467290, 468658, 469682, 472404,
# baseline swapoff 400vu
446111, 446305, 447339, 448043, 450604, 452160, 453846, 461309, 465101, 467893,
# baseline swapoff 600vu
434061, 435645, 435974, 436026, 436581, 439138, 442121, 445990, 454687, 469926,
# baseline swapon 200vu
466546, 467298, 467882, 469185, 472114, 473868, 475217, 481319, 483246, 493931,
# baseline swapon 400vu
367605, 371855, 373991, 380763, 388456, 389768, 395270, 403536, 404457, 406749,
# baseline swapon 600vu
123036, 127174, 131863, 150724, 155572, 158938, 170892, 179302, 183783, 189785,
# patched swapoff 200vu
456088, 457197, 457341, 458069, 459630, 472291, 474782, 475727, 478015, 486071,
# patched swapoff 400vu
452681, 453758, 455800, 457675, 458812, 459304, 460897, 461252, 465269, 470475,
# patched swapoff 600vu
448009, 452465, 453655, 454333, 456111, 456304, 465371, 471431, 475092, 478351,
# patched swapon 200vu
465540, 468681, 471682, 473134, 473148, 474015, 475734, 476691, 481974, 489873,
# patched swapon 400vu
436300, 440202, 441955, 445214, 445817, 452176, 452379, 456931, 457724, 465393,
# patched swapon 600vu
195315, 197186, 199332, 199667, 209630, 211162, 214787, 222783, 230000, 237667
)a <- array(v, dim = c(10, 3, 2, 2))
# baseline vs patched
for (swap in 1:2) {
for (vu in 1:3) {
r <- t.test(a[, vu, swap, 1], a[, vu, swap, 2])
print(r) p <- r$conf.int * 100 / r$estimate[1]
if ((p[1] > 0 && p[2] < 0) || (p[1] < 0 && p[2] > 0)) {
s <- sprintf("swap%d vu%d: no significance", swap, vu)
} else {
s <- sprintf("swap%d vu%d: [%.2f, %.2f]%%", swap, vu, -p[2], -p[1])
}
print(s)
}
}# swapoff vs swapon
for (kern in 1:2) {
for (vu in 1:3) {
r <- t.test(a[, vu, 1, kern], a[, vu, 2, kern])
print(r) p <- r$conf.int * 100 / r$estimate[1]
if ((p[1] > 0 && p[2] < 0) || (p[1] < 0 && p[2] > 0)) {
s <- sprintf("kern%d vu%d: no significance", kern, vu)
} else {
s <- sprintf("kern%d vu%d: [%.2f, %.2f]%%", kern, vu, -p[2], -p[1])
}
print(s)
}
}$ R -q -s -f raw_data_postgres.r
Welch Two Sample t-test
data: a[, vu, swap, 1] and a[, vu, swap, 2]
t = -0.3009, df = 10.521, p-value = 0.7694
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-9112.559 6931.359
sample estimates:
mean of x mean of y
466430.5 467521.1
[1] "swap1 vu1: no significance"
Welch Two Sample t-test
data: a[, vu, swap, 1] and a[, vu, swap, 2]
t = -1.8711, df = 15.599, p-value = 0.08021
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-12216.64 774.24
sample estimates:
mean of x mean of y
453871.1 459592.3
[1] "swap1 vu2: no significance"
Welch Two Sample t-test
data: a[, vu, swap, 1] and a[, vu, swap, 2]
t = -3.6832, df = 17.919, p-value = 0.001712 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-28423.515 -7771.085
sample estimates:
mean of x mean of y
443014.9 461112.2
[1] "swap1 vu3: [1.75, 6.42]%"
Welch Two Sample t-test
data: a[, vu, swap, 1] and a[, vu, swap, 2]
t = 0.0038109, df = 17.001, p-value = 0.997
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-7405.094 7431.894
sample estimates:
mean of x mean of y
475060.6 475047.2
[1] "swap2 vu1: no significance"
Welch Two Sample t-test
data: a[, vu, swap, 1] and a[, vu, swap, 2]
t = -11.413, df = 15.222, p-value = 7.301e-09 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-72572.5 -49755.7
sample estimates:
mean of x mean of y
388245.0 449409.1
[1] "swap2 vu2: [12.82, 18.69]%"
Welch Two Sample t-test
data: a[, vu, swap, 1] and a[, vu, swap, 2]
t = -6.1414, df = 14.853, p-value = 1.97e-05 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-73627.83 -35664.17
sample estimates:
mean of x mean of y
157106.9 211752.9
[1] "swap2 vu3: [22.70, 46.86]%"
Welch Two Sample t-test
data: a[, vu, 1, kern] and a[, vu, 2, kern]
t = -2.9241, df = 11.372, p-value = 0.0134
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-15100.107 -2160.093
sample estimates:
mean of x mean of y
466430.5 475060.6
[1] "kern1 vu1: [0.46, 3.24]%"
Welch Two Sample t-test
data: a[, vu, 1, kern] and a[, vu, 2, kern]
t = 12.629, df = 14.192, p-value = 4.129e-09 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
54494.92 76757.28
sample estimates:
mean of x mean of y
453871.1 388245.0
[1] "kern1 vu2: [-16.91, -12.01]%"
Welch Two Sample t-test
data: a[, vu, 1, kern] and a[, vu, 2, kern]
t = 34.005, df = 12.822, p-value = 5.981e-14 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
267718.5 304097.5
sample estimates:
mean of x mean of y
443014.9 157106.9
[1] "kern1 vu3: [-68.64, -60.43]%"
Welch Two Sample t-test
data: a[, vu, 1, kern] and a[, vu, 2, kern]
t = -1.8367, df = 15.057, p-value = 0.08607
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
-16256.986 1204.786
sample estimates:
mean of x mean of y
467521.1 475047.2
[1] "kern2 vu1: no significance"
Welch Two Sample t-test
data: a[, vu, 1, kern] and a[, vu, 2, kern]
t = 3.061, df = 14.554, p-value = 0.008153
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
3073.49 17292.91
sample estimates:
mean of x mean of y
459592.3 449409.1
[1] "kern2 vu2: [-3.76, -0.67]%"
Welch Two Sample t-test
data: a[, vu, 1, kern] and a[, vu, 2, kern]
t = 43.656, df = 16.424, p-value < 2.2e-16
alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval:
237275.9 261442.7
sample estimates:
mean of x mean of y
461112.2 211752.9
[1] "kern2 vu3: [-56.70, -51.46]%"