sched/numa: Enhance vma scanning
Subsystems (5)
v2 cover sched/numa: Enhance vma scanning
The patchset proposes one of the enhancements to numa vma scanning
suggested by Mel. This is continuation of [2]. Though I have removed RFC, I do think some parts need more feedback and refinement.
Existing mechanism of scan period involves, scan period derived from per-thread stats. Process Adaptive autoNUMA [1] proposed to gather NUMA fault stats at per-process level to capture aplication behaviour better.
During that course of discussion, Mel proposed several ideas to enhance current numa balancing. One of the suggestion was below
Track what threads access a VMA. The suggestion was to use an unsigned long pid_mask and use the lower bits to tag approximately what threads access a VMA. Skip VMAs that did not trap a fault. This would be approximate because of PID collisions but would reduce scanning of areas the thread is not interested in. The above suggestion intends not to penalize threads that has no interest in the vma, thus reduce scanning overhead.
About Patchset:
Patch1:
1) VMA scan delay logic added (Mel) where during initial phase of VMA, we delay the scanning by sysctl_numa_balancing_scan_delay.
2) A new status structure is added (vma_numab) so as to not grow the vm_area_struct in !NUMA_BALANCING case.
Patch2:
3) last 6 Bits of PID is used as index to remember which PIDs accessed VMA in fault path. This is further used to restrict scanning of VMA in scan path.
Please note that first two times scanning is unconditionally allowed (using numa_scan_seq). But this may need some potential change since numa_scan_seq is per mm.
Patch3:
4) Introduce basic patch clearing of accessed PIDs. This is as of now done at every 4 * sysctl_numa_balancing_scan_delay interval.
This logic may need more experiment/refinement.
Things to ponder over (and Future TODO):
==========================================
- Improvement to clearing accessing PIDs logic (discussed in-detail in patch3 itself)
- Current scan period is not changed in the patchset, so we do see frequent tries to scan. Relaxing scan period dynamically could improve results
further.
Result Summary:
================
The result is obtained by running mmtests with below configs config-numa-autonumabench
There is a significant reduction in AutoNuma cost from the benchmark runs, But some of the results need improvement. I hope working on the potential changes mentioned in patch3 and hopefuly numa_scan_period tuning depending on current scanning efiiciency would help. will be working on that..
SUT:
2 socket AMD Milan System
Thread(s) per core: 2 Core(s) per socket: 64 Socket(s): 2
256GB memory per socket amounting to 512GB in total NPS1 NUMA configuration where each socket is a NUMA node
autonumabench
6.1.0 6.1.0 BAmean-99 syst-NUMA01 195.84 ( 0.00%) 17.79 ( 90.91%) BAmean-99 syst-NUMA01_THREADLOCAL 0.19 ( 0.00%) 0.19 ( 2.56%) BAmean-99 syst-NUMA02 0.85 ( 0.00%) 0.85 ( 0.00%) BAmean-99 syst-NUMA02_SMT 0.62 ( 0.00%) 0.65 ( -4.30%) BAmean-99 elsp-NUMA01 254.95 ( 0.00%) 322.69 ( -26.57%) BAmean-99 elsp-NUMA01_THREADLOCAL 1.04 ( 0.00%) 1.05 ( -1.29%) BAmean-99 elsp-NUMA02 3.08 ( 0.00%) 3.29 ( -6.94%) BAmean-99 elsp-NUMA02_SMT 3.49 ( 0.00%) 3.43 ( 1.91%)
6.1.0 6.1.0 Ops NUMA alloc hit 59210941.00 50772531.00 Ops NUMA alloc miss 0.00 0.00 Ops NUMA interleave hit 0.00 0.00 Ops NUMA alloc local 59200395.00 50771359.00 Ops NUMA base-page range updates 90670863.00 10952.00 Ops NUMA PTE updates 90670863.00 10952.00 Ops NUMA PMD updates 0.00 0.00 Ops NUMA hint faults 92069634.00 9501.00 Ops NUMA hint local faults % 69966984.00 9213.00
Ops NUMA hint local percent 75.99 96.97
Ops NUMA pages migrated 8424631.00 287.00
Ops AutoNUMA cost 461142.93 47.59
[1] sched/numa: Process Adaptive autoNUMA
[2] RFC V1:
Changes since RFC V1:
- Include Mel's vma scan delay patch
- Change the accessing pid store logic (Thanks Mel)
- Fencing structure / code to NUMA_BALANCING (David, Mel)
- Adding clearing access PID logic (Mel)
- Descriptive change log ( Mike Rapoport)
Mel Gorman (1):
sched/numa: Apply the scan delay to every vma instead of tasks
Raghavendra K T (2):
sched/numa: Enhance vma scanning logic
sched/numa: Reset the accessing PID information periodically
include/linux/mm.h | 23 +++++++++++++++++++ include/linux/mm_types.h | 9 ++++++++ kernel/fork.c | 2 ++ kernel/sched/fair.c | 49 ++++++++++++++++++++++++++++++++++++++++ mm/huge_memory.c | 1 + mm/memory.c | 1 + 6 files changed, 85 insertions(+)
Signature · 1 line
2.34.1
PATCH v2 1/3 sched/numa: Apply the scan delay to every vma instead of tasks
From: Mel Gorman <[email protected]>
Avoid scanning new or very short-lived VMAs.
(Raghavendra: Add initialization in vm_area_dup())
--- include/linux/mm.h | 9 +++++++++ include/linux/mm_types.h | 7 +++++++ kernel/fork.c | 2 ++ kernel/sched/fair.c | 17 +++++++++++++++++ 4 files changed, 35 insertions(+)
include/linux/mm.h +9 -0
@@ -611,6 +611,14 @@ struct vm_operations_struct { unsigned long addr); }; +#ifdef CONFIG_NUMA_BALANCING +#define vma_numab_init (vma) do { (vma)->numab = NULL; } while (0) +#define vma_numab_free (vma) do { kfree((vma)->numab); } while (0) +#else +static inline void vma_numab_init (struct vm_area_struct *vma) {} +static inline void vma_numab_free (struct vm_area_struct *vma) {} +#endif /* CONFIG_NUMA_BALANCING */ +static inline void vma_init (struct vm_area_struct *vma,struct mm_struct *mm) {static const struct vm_operations_struct dummy_vm_ops = {};
@@ -619,6 +627,7 @@ static inline void vma_init(struct vm_area_struct *vma, struct mm_struct *mm) vma->vm_mm = mm; vma->vm_ops = &dummy_vm_ops;INIT_LIST_HEAD (&vma->anon_vma_chain); +vma_numab_init (vma); }static inline void vma_set_anonymous (struct vm_area_struct *vma)
include/linux/mm_types.h +7 -0
@@ -435,6 +435,10 @@ struct anon_vma_name {char name[]; }; +struct vma_numab { +unsigned long next_scan; +}; +/* * This struct describes a virtual memory area. There is one of these * per VM-area/task. A VM area is any part of the process virtual memory
@@ -504,6 +508,9 @@ struct vm_area_struct {#endif #ifdef CONFIG_NUMA struct mempolicy *vm_policy;/* NUMA policy for the VMA */ +#endif +#ifdef CONFIG_NUMA_BALANCING +struct vma_numab *numab;/* NUMA Balancing state */ #endif struct vm_userfaultfd_ctx vm_userfaultfd_ctx; } __randomize_layout;
kernel/fork.c +2 -0
@@ -474,6 +474,7 @@ struct vm_area_struct *vm_area_dup(struct vm_area_struct *orig)*/ *new =data_race (*orig);INIT_LIST_HEAD (&new->anon_vma_chain); +vma_numab_init (new);dup_anon_vma_name (orig, new); }return new;
@@ -481,6 +482,7 @@ struct vm_area_struct *vm_area_dup(struct vm_area_struct *orig)void vm_area_free (struct vm_area_struct *vma) { +vma_numab_free (vma);free_anon_vma_name (vma);kmem_cache_free (vm_area_cachep, vma); }
kernel/sched/fair.c +17 -0
@@ -3015,6 +3015,23 @@ static void task_numa_work(struct callback_head *work)if (!vma_is_accessible (vma))continue ; +/* Initialise new per-VMA NUMAB state. */ +if (!vma->numab) { + vma->numab =kzalloc (sizeof (struct vma_numab ),GFP_KERNEL ); +if (!vma->numab) +continue ; + + vma->numab->next_scan = now + +msecs_to_jiffies (sysctl_numa_balancing_scan_delay); + } + +/* +* After the first scan is complete, delay the balancing scan +* for new VMAs. +*/ +if (mm->numa_scan_seq &&time_before (jiffies, vma->numab->next_scan)) +continue ; + do { start = max(start, vma->vm_start); end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);
Signature · 1 line
2.34.1
PATCH v2 2/3 sched/numa: Enhance vma scanning logic
In reply to Raghavendra K T During the Numa scanning make sure only relevant vmas of the
tasks are scanned.
Before:
All the tasks of a process participate in scanning the vma
even if they do not access vma in it's lifespan.
Now:
Except cases of first few unconditional scans, if a process do
not touch vma (exluding false positive cases of PID collisions) tasks no longer scan all vma.
Logic used:
1) 6 bits of PID used to mark active bit in vma numab status during fault to remember PIDs accessing vma. (Thanks Mel)
2) Subsequently in scan path, vma scanning is skipped if current PID had not accessed vma.
3) First two times we do allow unconditional scan to preserve earlier behaviour of scanning.
Acknowledgement to Bharata B Rao <[email protected]> for initial patch to store pid information.
--- include/linux/mm.h | 14 ++++++++++++++ include/linux/mm_types.h | 1 + kernel/sched/fair.c | 15 +++++++++++++++ mm/huge_memory.c | 1 + mm/memory.c | 1 + 5 files changed, 32 insertions(+)
include/linux/mm.h +14 -0
@@ -1381,6 +1381,16 @@ static inline int xchg_page_access_time(struct page *page, int time) last_time =page_cpupid_xchg_last (page, time >>PAGE_ACCESS_TIME_BUCKETS ); return last_time << PAGE_ACCESS_TIME_BUCKETS; } + +static inline void vma_set_active_pid_bit (struct vm_area_struct *vma) +{ +unsigned int active_pid_bit; + +if (vma->numab) { + active_pid_bit = current->pid %BITS_PER_LONG ; + vma->numab->accessing_pids |=1UL << active_pid_bit; + } +}#else /* !CONFIG_NUMA_BALANCING */ static inline int page_cpupid_xchg_last (struct page *page,int cpupid) {
@@ -1430,6 +1440,10 @@ static inline bool cpupid_match_pid(struct task_struct *task, int cpupid) {return false; } + +static inline void vma_set_active_pid_bit (struct vm_area_struct *vma) +{ +}#endif /* CONFIG_NUMA_BALANCING */ #if defined(CONFIG_KASAN_SW_TAGS ) || defined(CONFIG_KASAN_HW_TAGS )
include/linux/mm_types.h +1 -0
@@ -437,6 +437,7 @@ struct anon_vma_name {struct vma_numab {unsigned long next_scan; +unsigned long accessing_pids; };/*
kernel/sched/fair.c +15 -0
@@ -2916,6 +2916,18 @@ static void reset_ptenuma_scan(struct task_struct *p) p->mm->numa_scan_offset =0 ; } +static bool vma_is_accessed (struct vm_area_struct *vma) +{ +unsigned int active_pid_bit; + +if (READ_ONCE (current->mm->numa_scan_seq) <2 ) +return true; + + active_pid_bit = current->pid %BITS_PER_LONG ; + +return vma->numab->accessing_pids & (1UL << active_pid_bit); +} +/* * The expensive part of numa migration is done from task_work context. * Triggered from task_tick_numa().
@@ -3032,6 +3044,9 @@ static void task_numa_work(struct callback_head *work)if (mm->numa_scan_seq &&time_before (jiffies, vma->numab->next_scan))continue ; +if (!vma_is_accessed (vma)) +continue ; + do { start = max(start, vma->vm_start); end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);
mm/huge_memory.c +1 -0
@@ -1485,6 +1485,7 @@ vm_fault_t do_huge_pmd_numa_page(struct vm_fault *vmf)bool was_writable =pmd_savedwrite (oldpmd);int flags =0 ; +vma_set_active_pid_bit (vma); vmf->ptl =pmd_lock (vma->vm_mm, vmf->pmd);if (unlikely (!pmd_same (oldpmd, *vmf->pmd))) {spin_unlock (vmf->ptl);
mm/memory.c +1 -0
@@ -4718,6 +4718,7 @@ static vm_fault_t do_numa_page(struct vm_fault *vmf)bool was_writable =pte_savedwrite (vmf->orig_pte);int flags =0 ; +vma_set_active_pid_bit (vma);/* * The "pte" at this point cannot be used safely without * validation through pte_unmap_same(). It's of NUMA type but
Signature · 1 line
2.34.1
PATCH v2 3/3 sched/numa: Reset the accessing PID information periodically
In reply to Raghavendra K T This helps to ensure, only recently accessed PIDs scan the
VMAs.
Current implementation:
Reset accessing PIDs every (4 * sysctl_numa_balancing_scan_delay)
interval after initial scan delay period expires. The reset logic is implemented in scan path
---
Some of the potential ideas for clearing the accessing PIDs
1) Flag to indicate phase in life cycle of vma and tie with timestamp (reuse next_scan or so)
VMA life cycle
t1 t2 t3 t4 t5 t6 |<- DS ->|<- US ->|<- CS ->|<- US ->|<- CS ->|
flags used to indicate whether we are in DS/CS/US phase
DS (delay scan): Initial phase where scan is avoided for new VMA
US (unconditional scan): Brief period where scanning is allowed irrespective of task faulting the VMA CS (conditional scan) : Longer conditiona scanning phase where task scanning is allowed only for VMA of interest
2) Maintain duplicate list of accessing PIDs to keep track of history of access. and switch/reset. use OR operation during iteration
Two lists of PIDs maintained. At regular interval old list is reset and we make current list as old list
At any point of time tracking of PIDs accessing VMA is determined by ORing list1 and list2
accessing_pids_list1 <- current listaccessing_pids_list2 <- old list
3) Maintain per vma numa_seq also
Currently numa_seq (how many times we are scanning entire set of VMAs) is maintained at mm level. Having numa_seq (almost like how many times the current VMA considered for scanning) per VMA may be helpful in some context (for e.g., whether we need to allow VMA scanning unconditionally for a newly created VMA).
4) Reset accessing PIDs at regular intervals (current implementation)
t1 t2 t3 t4 t5 t6 |<- DS ->|<- CS ->|<- CS ->|<- CS ->|<- CS ->|
The current implementation resets accessing PIDs every 4*scan_delay intervals after initial scan delay time expires. The reset logic is implemented in scan path
include/linux/mm_types.h | 1 + kernel/sched/fair.c | 17 +++++++++++++++++ 2 files changed, 18 insertions(+)
include/linux/mm_types.h +1 -0
@@ -437,6 +437,7 @@ struct anon_vma_name {struct vma_numab {unsigned long next_scan; +unsigned long next_pid_reset;unsigned long accessing_pids; };
kernel/sched/fair.c +17 -0
@@ -2928,6 +2928,8 @@ static bool vma_is_accessed(struct vm_area_struct *vma)return vma->numab->accessing_pids & (1UL << active_pid_bit); } +#define VMA_PID_RESET_PERIOD (4 * sysctl_numa_balancing_scan_delay) +/* * The expensive part of numa migration is done from task_work context. * Triggered from task_tick_numa().
@@ -3035,6 +3037,10 @@ static void task_numa_work(struct callback_head *work) vma->numab->next_scan = now +msecs_to_jiffies (sysctl_numa_balancing_scan_delay); + +/* Reset happens after 4 times scan delay of scan start */ + vma->numab->next_pid_reset = vma->numab->next_scan + +msecs_to_jiffies (VMA_PID_RESET_PERIOD ); }/*
@@ -3047,6 +3053,17 @@ static void task_numa_work(struct callback_head *work)if (!vma_is_accessed (vma))continue ; +/* +* RESET accessing PIDs regularly for old VMAs. Resetting after checking +* vma for recent access to avoid clearing PID info before access.. +*/ +if (mm->numa_scan_seq && +time_after (jiffies, vma->numab->next_pid_reset)) { + vma->numab->next_pid_reset = vma->numab->next_pid_reset + +msecs_to_jiffies (VMA_PID_RESET_PERIOD ); + vma->numab->accessing_pids =0 ; + } + do { start = max(start, vma->vm_start); end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);
Signature · 1 line
2.34.1
Peter Zijlstra
maintainerRe: [PATCH V2 1/3] sched/numa: Apply the scan delay to every vma instead of tasks
In reply to Raghavendra K TQuoted 5 lines · Raghavendra K T
From: Mel Gorman <[email protected]>
Avoid scanning new or very short-lived VMAs.
(Raghavendra: Add initialization in
vm_area_dup())
Given this is a performance centric patch -- some sort of qualification / justification would be much appreciated.
Also, perhaps explain the rationale for the actual heuristics chosen.
Quoted 14 lines
Signed-off-by Mel Gorman <[email protected]>Signed-off-by Raghavendra K T <[email protected]>--- include/linux/mm.h | 9 +++++++++ include/linux/mm_types.h | 7 +++++++ kernel/fork.c | 2 ++ kernel/sched/fair.c | 17 +++++++++++++++++ 4 files changed, 35 insertions(+)include/linux/mm.h +0
-0
include/linux/mm.h struct vm_operations_struct { · line 620
Quoted 10 lines
include/linux/mm.h +7
-0@@ -611,6 +611,14 @@ struct vm_operations_struct { unsigned long addr); }; +#ifdef CONFIG_NUMA_BALANCING +#define vma_numab_init (vma) do { (vma)->numab = NULL; } while (0) +#define vma_numab_free (vma) do { kfree((vma)->numab); } while (0) +#else +static inline void vma_numab_init (struct vm_area_struct *vma) {} +static inline void vma_numab_free (struct vm_area_struct *vma) {} +#endif /* CONFIG_NUMA_BALANCING */
I'm tripping over the inconsistency of macros and functions here. I'd suggest making both cases functions.
include/linux/mm_types.h struct anon_vma_name { · line 440
Quoted 11 lines
include/linux/mm_types.h +3
-0@@ -435,6 +435,10 @@ struct anon_vma_name {char name[]; }; +struct vma_numab { +unsigned long next_scan; +};
I'm not sure what a numab is; contraction of new-kebab, something else?
While I appreciate short names, they'd ideally also make sense. If we cannot come up with a better one, perhaps elucidate the reader with a comment.
Quoted 20 lines
include/linux/mm_types.h +1
-0+/* * This struct describes a virtual memory area. There is one of these * per VM-area/task. A VM area is any part of the process virtual memory @@ -504,6 +508,9 @@ struct vm_area_struct {kernel/sched/fair.c +6
-0@@ -3015,6 +3015,23 @@ static void task_numa_work(struct callback_head *work)if (!vma_is_accessible (vma))continue ; +/* Initialise new per-VMA NUMAB state. */ +if (!vma->numab) { + vma->numab =kzalloc (sizeof (struct vma_numab ),GFP_KERNEL ); +if (!vma->numab) +continue ; +
kernel/sched/fair.c static void task_numa_work(struct callback_head *work) · line 3033
Quoted 10 lines
kernel/sched/fair.c +10
-0+ vma->numab->next_scan = now + +msecs_to_jiffies (sysctl_numa_balancing_scan_delay); + } + +/* +* After the first scan is complete, delay the balancing scan +* for new VMAs. +*/ +if (mm->numa_scan_seq &&time_before (jiffies, vma->numab->next_scan)) +continue ;
I think I sorta see why, but I'm thinking it would be good to include more of the why in that comment.
Peter Zijlstra
maintainerRe: [PATCH V2 2/3] sched/numa: Enhance vma scanning logic
In reply to Raghavendra K TQuoted 43 lines · Raghavendra K T
During the Numa scanning make sure only relevant vmas of the
tasks are scanned.Before:
All the tasks of a process participate in scanning the vma
even if they do not access vma in it's lifespan.Now:
Except cases of first few unconditional scans, if a process do
not touch vma (exluding false positive cases of PID collisions) tasks no longer scan all vma.Logic used:
1) 6 bits of PID used to mark active bit in vma numab status during fault to remember PIDs accessing vma. (Thanks Mel)2) Subsequently in scan path, vma scanning is skipped if current PID had not accessed vma.
3) First two times we do allow unconditional scan to preserve earlier behaviour of scanning.
Acknowledgement to Bharata B Rao <[email protected]> for initial patch to store pid information.
Suggested-by Mel Gorman <[email protected]>Signed-off-by Raghavendra K T <[email protected]>--- include/linux/mm.h | 14 ++++++++++++++ include/linux/mm_types.h | 1 + kernel/sched/fair.c | 15 +++++++++++++++ mm/huge_memory.c | 1 + mm/memory.c | 1 + 5 files changed, 32 insertions(+)include/linux/mm.h +0
-0@@ -1381,6 +1381,16 @@ static inline int xchg_page_access_time(struct page *page, int time) last_time =page_cpupid_xchg_last (page, time >>PAGE_ACCESS_TIME_BUCKETS );return last_time <<PAGE_ACCESS_TIME_BUCKETS ; }
include/linux/mm.h static inline int xchg_page_access_time(struct page *page, int time) · line 1393
Quoted 10 lines
include/linux/mm.h +10
-0+ +static inline void vma_set_active_pid_bit (struct vm_area_struct *vma) +{ +unsigned int active_pid_bit; + +if (vma->numab) { + active_pid_bit = current->pid %BITS_PER_LONG ; + vma->numab->accessing_pids |=1UL << active_pid_bit; + } +}
Perhaps:
if (vma->numab) __set_bit(current->pid % BITS_PER_LONG, &vma->numab->pids);
?
Or maybe even:
bit = current->pid % BITS_PER_LONG; if (vma->numab && !__test_bit(bit, &vma->numab->pids)) __set_bit(bit, &vma->numab->pids);
kernel/sched/fair.c static void reset_ptenuma_scan(struct task_struct *p) · line 2922
Quoted 12 lines
kernel/sched/fair.c +4
-0@@ -2916,6 +2916,18 @@ static void reset_ptenuma_scan(struct task_struct *p) p->mm->numa_scan_offset =0 ; } +static bool vma_is_accessed (struct vm_area_struct *vma) +{ +unsigned int active_pid_bit; +
/* * Tell us why 2.... */
kernel/sched/fair.c static void reset_ptenuma_scan(struct task_struct *p) · line 2928
Quoted 6 lines
kernel/sched/fair.c +6
-0+if (READ_ONCE (current->mm->numa_scan_seq) <2 ) +return true; + + active_pid_bit = current->pid %BITS_PER_LONG ; + +return vma->numab->accessing_pids & (1UL << active_pid_bit);
return __test_bit(current->pid % BITS_PER_LONG, &vma->numab->pids)
kernel/sched/fair.c static void task_numa_work(struct callback_head *work) · line 3046
Quoted 9 lines
kernel/sched/fair.c +2
-0+} +/* * The expensive part of numa migration is done from task_work context. * Triggered from task_tick_numa(). @@ -3032,6 +3044,9 @@ static void task_numa_work(struct callback_head *work)if (mm->numa_scan_seq &&time_before (jiffies, vma->numab->next_scan))continue ;
/* * tell us more... */
kernel/sched/fair.c static void task_numa_work(struct callback_head *work) · line 3052
Quoted 6 lines
kernel/sched/fair.c +3
-0+if (!vma_is_accessed (vma)) +continue ; + do { start = max(start, vma->vm_start); end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);
This feels wrong, specifically we track numa_scan_offset per mm, now, if we divide the threads into two dis-joint groups each only using their own set of vmas (in fact quite common for workloads with proper data partitioning) it is possible to consistently sample one set of threads and thus not scan the other set of vmas.
It seems somewhat unlikely, but not impossible to create significant unfairness.
Quoted 17 lines
mm/huge_memory.c +1
-0@@ -1485,6 +1485,7 @@ vm_fault_t do_huge_pmd_numa_page(struct vm_fault *vmf)bool was_writable =pmd_savedwrite (oldpmd);int flags =0 ; +vma_set_active_pid_bit (vma); vmf->ptl =pmd_lock (vma->vm_mm, vmf->pmd);if (unlikely (!pmd_same (oldpmd, *vmf->pmd))) {spin_unlock (vmf->ptl);mm/memory.c +0
-0
mm/memory.c static vm_fault_t do_numa_page(struct vm_fault *vmf) · line 4724
Quoted 7 lines
mm/memory.c +1
-0@@ -4718,6 +4718,7 @@ static vm_fault_t do_numa_page(struct vm_fault *vmf)bool was_writable =pte_savedwrite (vmf->orig_pte);int flags =0 ; +vma_set_active_pid_bit (vma);/* * The "pte" at this point cannot be used safely without * validation through pte_unmap_same(). It's of NUMA type but
Urghh... do_*numa_page() is two near identical functions.. is there really no sane way to de-duplicate at least some of that?
Also, is this placement right, you're marking the thread even before we know there's even a page there. I would expect this somewhere around where we track lastpid.
Maybe numa_migrate_prep() ?
Peter Zijlstra
maintainerRe: [PATCH V2 2/3] sched/numa: Enhance vma scanning logic
Quoted 15 lines · Peter Zijlstra
include/linux/mm.h static inline int xchg_page_access_time(struct page *page, int time) · line 1393
Quoted 9 lines
include/linux/mm.h +9
-0+static inline void vma_set_active_pid_bit (struct vm_area_struct *vma) +{ +unsigned int active_pid_bit; + +if (vma->numab) { + active_pid_bit = current->pid %BITS_PER_LONG ; + vma->numab->accessing_pids |=1UL << active_pid_bit; + } +}Perhaps:
if (vma->numab) __set_bit(current->pid % BITS_PER_LONG, &vma->numab->pids);
Quoted 8 lines
?
Or maybe even:
bit = current->pid % BITS_PER_LONG; if (vma->numab && !__test_bit(bit, &vma->numab->pids)) __set_bit(bit, &vma->numab->pids);
The alternative to just taking the low n bits is to use:
hash_32(current->pid, BITS_PER_LONG)
That mixes things up a bit.
Peter Zijlstra
maintainerRe: [PATCH V2 3/3] sched/numa: Reset the accessing PID information periodically
In reply to Raghavendra K TQuoted 7 lines · Raghavendra K T
2) Maintain duplicate list of accessing PIDs to keep track of history of access. and switch/reset. use OR operation during iteration
Two lists of PIDs maintained. At regular interval old list is reset and we make current list as old list
At any point of time tracking of PIDs accessing VMA is determined by ORing list1 and list2
accessing_pids_list1<- current listaccessing_pids_list2<- old list
( I'm not sure why you think this part of the email doesn't need to be
nicely wrapped at 76 chars.. )
This seems simple enough to me and can be trivially extended to N if needed.
The typical implementation would looks something like:
unsigned long pids[N]; unsigned int pid_idx;
set:
unsigned long *pids = numab->pids + pid_idx; if (!__test_bit(bit, pids)) __set_bit(bit, pids);
test:
unsigned long pids = 0; for (int i = 0; i < N; i++) pids |= numab->pids[i]; return __test_bit(bit, &pids);
rotate:
idx = READ_ONCE(numab->pid_idx); WRITE_ONCE(numab->pid_idx, (idx + 1) % N); numab->pids[idx] = 0;
Note the actual rotate can be simplified to ^1 for N:=2.
Re: [PATCH V2 1/3] sched/numa: Apply the scan delay to every vma instead of tasks
In reply to Peter ZijlstraQuoted 10 lines · Peter Zijlstra
Quoted 5 lines · Raghavendra K T
From: Mel Gorman <[email protected]>
Avoid scanning new or very short-lived VMAs.
(Raghavendra: Add initialization in
vm_area_dup())Given this is a performance centric patch -- some sort of qualification / justification would be much appreciated.
Thank you Peter for the review.
Sure will add more detailed result in cover and summary for the patch commit message.
Quoted 2 lines
Also, perhaps explain the rationale for the actual heuristics chosen.
Sure will add more detail in the V3
Quoted 17 lines
Quoted 17 lines
Signed-off-by Mel Gorman <[email protected]>Signed-off-by Raghavendra K T <[email protected]>--- include/linux/mm.h | 9 +++++++++ include/linux/mm_types.h | 7 +++++++ kernel/fork.c | 2 ++ kernel/sched/fair.c | 17 +++++++++++++++++ 4 files changed, 35 insertions(+)include/linux/mm.h +0
-0@@ -611,6 +611,14 @@ struct vm_operations_struct { unsigned long addr); };
Quoted 12 lines
include/linux/mm.h struct vm_operations_struct { · line 620
Quoted 7 lines
include/linux/mm.h +7
-0+#ifdef CONFIG_NUMA_BALANCING +#define vma_numab_init (vma) do { (vma)->numab = NULL; } while (0) +#define vma_numab_free (vma) do { kfree((vma)->numab); } while (0) +#else +static inline void vma_numab_init (struct vm_area_struct *vma) {} +static inline void vma_numab_free (struct vm_area_struct *vma) {} +#endif /* CONFIG_NUMA_BALANCING */ I'm tripping over the inconsistency of macros and functions here. I'd suggest making both cases functions.
Sure will do that
Quoted 14 lines
include/linux/mm_types.h struct anon_vma_name { · line 440
Quoted 11 lines
include/linux/mm_types.h +3
-0@@ -435,6 +435,10 @@ struct anon_vma_name {char name[]; }; +struct vma_numab { +unsigned long next_scan; +};I'm not sure what a numab is; contraction of new-kebab, something else?
Quoted 3 lines
While I appreciate short names, they'd ideally also make sense. If we cannot come up with a better one, perhaps elucidate the reader with a comment.
Agree.. How about vma_nuamb vma_numab_state or vma_numab_info as abbreviation for vma_numa_balancing_info /state?
Quoted 26 lines
Quoted 26 lines
include/linux/mm_types.h +1
-0+/* * This struct describes a virtual memory area. There is one of these * per VM-area/task. A VM area is any part of the process virtual memory @@ -504,6 +508,9 @@ struct vm_area_struct {kernel/sched/fair.c +11
-0@@ -3015,6 +3015,23 @@ static void task_numa_work(struct callback_head *work)if (!vma_is_accessible (vma))continue ; +/* Initialise new per-VMA NUMAB state. */ +if (!vma->numab) { + vma->numab =kzalloc (sizeof (struct vma_numab ),GFP_KERNEL ); +if (!vma->numab) +continue ; + + vma->numab->next_scan = now + +msecs_to_jiffies (sysctl_numa_balancing_scan_delay); + } + +/*
Quoted 8 lines
kernel/sched/fair.c static void task_numa_work(struct callback_head *work) · line 3033
Quoted 5 lines
kernel/sched/fair.c +5
-0+* After the first scan is complete, delay the balancing scan +* for new VMAs. +*/ +if (mm->numa_scan_seq &&time_before (jiffies, vma->numab->next_scan)) +continue ;I think I sorta see why, but I'm thinking it would be good to include more of the why in that comment.
Sure. Will add something in the lines of.. "scanning the VMA's of short lived tasks add more overhead than benefit...."
Re: [PATCH V2 2/3] sched/numa: Enhance vma scanning logic
In reply to Peter ZijlstraQuoted 60 lines · Peter Zijlstra
Quoted 43 lines · Raghavendra K T
During the Numa scanning make sure only relevant vmas of the
tasks are scanned.Before:
All the tasks of a process participate in scanning the vma
even if they do not access vma in it's lifespan.Now:
Except cases of first few unconditional scans, if a process do
not touch vma (exluding false positive cases of PID collisions) tasks no longer scan all vma.Logic used:
1) 6 bits of PID used to mark active bit in vma numab status during fault to remember PIDs accessing vma. (Thanks Mel)2) Subsequently in scan path, vma scanning is skipped if current PID had not accessed vma.
3) First two times we do allow unconditional scan to preserve earlier behaviour of scanning.
Acknowledgement to Bharata B Rao <[email protected]> for initial patch to store pid information.
Suggested-by Mel Gorman <[email protected]>Signed-off-by Raghavendra K T <[email protected]>--- include/linux/mm.h | 14 ++++++++++++++ include/linux/mm_types.h | 1 + kernel/sched/fair.c | 15 +++++++++++++++ mm/huge_memory.c | 1 + mm/memory.c | 1 + 5 files changed, 32 insertions(+)include/linux/mm.h +0
-0@@ -1381,6 +1381,16 @@ static inline int xchg_page_access_time(struct page *page, int time) last_time =page_cpupid_xchg_last (page, time >>PAGE_ACCESS_TIME_BUCKETS );return last_time <<PAGE_ACCESS_TIME_BUCKETS ; }include/linux/mm.h static inline int xchg_page_access_time(struct page *page, int time) · line 1393
Quoted 10 lines
include/linux/mm.h +10
-0+ +static inline void vma_set_active_pid_bit (struct vm_area_struct *vma) +{ +unsigned int active_pid_bit; + +if (vma->numab) { + active_pid_bit = current->pid %BITS_PER_LONG ; + vma->numab->accessing_pids |=1UL << active_pid_bit; + } +}Perhaps:
if (vma->numab) __set_bit(current->pid % BITS_PER_LONG, &vma->numab->pids);
Quoted 9 lines
?
Or maybe even:
bit = current->pid % BITS_PER_LONG; if (vma->numab && !__test_bit(bit, &vma->numab->pids)) __set_bit(bit, &vma->numab->pids);
Sure ..will use one of the above.
Quoted 8 lines
Quoted 8 lines
kernel/sched/fair.c +0
-0@@ -2916,6 +2916,18 @@ static void reset_ptenuma_scan(struct task_struct *p) p->mm->numa_scan_offset =0 ; }
Quoted 7 lines
kernel/sched/fair.c static void reset_ptenuma_scan(struct task_struct *p) · line 2922
Quoted 4 lines
kernel/sched/fair.c +4
-0+static bool vma_is_accessed (struct vm_area_struct *vma) +{ +unsigned int active_pid_bit; +/* * Tell us why 2.... */
Agree. The logic is more towards allowing unconditional scan first two times to build task/page relation. I will experiment if we further need to allow for two full passes if "multi-stage node selection" (=4), to take care of early migration.
But only doubt I have is numa_scan_seq is per mm and thus will it create corner cases or we need to have a per vma count separately when a new VMA is created..
Quoted 7 lines
kernel/sched/fair.c static void reset_ptenuma_scan(struct task_struct *p) · line 2928
Quoted 6 lines
kernel/sched/fair.c +6
-0+if (READ_ONCE (current->mm->numa_scan_seq) <2 ) +return true; + + active_pid_bit = current->pid %BITS_PER_LONG ; + +return vma->numab->accessing_pids & (1UL << active_pid_bit);return __test_bit(current->pid % BITS_PER_LONG, &vma->numab->pids)
Quoted 12 lines
kernel/sched/fair.c static void task_numa_work(struct callback_head *work) · line 3046
Quoted 9 lines
kernel/sched/fair.c +2
-0+} +/* * The expensive part of numa migration is done from task_work context. * Triggered from task_tick_numa(). @@ -3032,6 +3044,9 @@ static void task_numa_work(struct callback_head *work)if (mm->numa_scan_seq &&time_before (jiffies, vma->numab->next_scan))continue ;/* * tell us more... */
Sure. Since this is the core of the whole logic where we want to confine VMA scan to PIDs of interest mostly.
Quoted 14 lines
kernel/sched/fair.c static void task_numa_work(struct callback_head *work) · line 3052
Quoted 6 lines
kernel/sched/fair.c +3
-0+if (!vma_is_accessed (vma)) +continue ; + do { start = max(start, vma->vm_start); end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);This feels wrong, specifically we track
numa_scan_offsetper mm, now, if we divide the threads into two dis-joint groups each only using their own set of vmas (in fact quite common for workloads with proper data partitioning) it is possible to consistently sample one set of threads and thus not scan the other set of vmas.
Quoted 3 lines
It seems somewhat unlikely, but not impossible to create significant unfairness.
Agree, But that is the reason why we want to allow first few unconditional scans Or am I missing something?
Quoted 20 lines
Quoted 20 lines
mm/huge_memory.c +1
-0@@ -1485,6 +1485,7 @@ vm_fault_t do_huge_pmd_numa_page(struct vm_fault *vmf)bool was_writable =pmd_savedwrite (oldpmd);int flags =0 ; +vma_set_active_pid_bit (vma); vmf->ptl =pmd_lock (vma->vm_mm, vmf->pmd);if (unlikely (!pmd_same (oldpmd, *vmf->pmd))) {spin_unlock (vmf->ptl);mm/memory.c +0
-0@@ -4718,6 +4718,7 @@ static vm_fault_t do_numa_page(struct vm_fault *vmf)bool was_writable =pte_savedwrite (vmf->orig_pte);int flags =0 ;
Quoted 8 lines
mm/memory.c static vm_fault_t do_numa_page(struct vm_fault *vmf) · line 4724
Quoted 4 lines
mm/memory.c +1
-0+vma_set_active_pid_bit (vma);/* * The "pte" at this point cannot be used safely without * validation through pte_unmap_same(). It's of NUMA type but Urghh... do_*numa_page() is two near identical functions.. is there really no sane way to de-duplicate at least some of that?
Agree. I will explore and will take that as a separate TODO.
Quoted 4 lines
Also, is this placement right, you're marking the thread even before we know there's even a page there. I would expect this somewhere around where we track lastpid.
Good point. I will check this again
Quoted 1 line
Maybe
numa_migrate_prep()?
yes.. there was no hurry to record accessing pid early above...
Re: [PATCH V2 2/3] sched/numa: Enhance vma scanning logic
In reply to Peter ZijlstraQuoted 26 lines · Peter Zijlstra
Quoted 15 lines · Peter Zijlstra
include/linux/mm.h static inline int xchg_page_access_time(struct page *page, int time) · line 1393
Quoted 9 lines
include/linux/mm.h +9
-0+static inline void vma_set_active_pid_bit (struct vm_area_struct *vma) +{ +unsigned int active_pid_bit; + +if (vma->numab) { + active_pid_bit = current->pid %BITS_PER_LONG ; + vma->numab->accessing_pids |=1UL << active_pid_bit; + } +}Perhaps:
if (vma->numab) __set_bit(current->pid % BITS_PER_LONG, &vma->numab->pids);Quoted 8 lines
?
Or maybe even:
bit = current->pid % BITS_PER_LONG; if (vma->numab && !__test_bit(bit, &vma->numab->pids)) __set_bit(bit, &vma->numab->pids);
Quoted 5 lines
The alternative to just taking the low n bits is to use:
hash_32(current->pid, BITS_PER_LONG)That mixes things up a bit.
Good idea, when we have workloads that creates lesser number of threads
faster, current solution might have been simpler, but with thread creation that happens over period of time hash function mixes and avoids collision. will experiment with this option.
Re: [PATCH V2 3/3] sched/numa: Reset the accessing PID information periodically
In reply to Peter ZijlstraQuoted 4 lines · Peter Zijlstra
Quoted 2 lines · Raghavendra K T
2) Maintain duplicate list of accessing PIDs to keep track of history of access. and switch/reset. use OR operation during iteration
Quoted 9 lines
Quoted 5 lines
Two lists of PIDs maintained. At regular interval old list is reset and we make current list as old list
At any point of time tracking of PIDs accessing VMA is determined by ORing list1 and list2
accessing_pids_list1<- current listaccessing_pids_list2<- old list( I'm not sure why you think this part of the email doesn't need to be
nicely wrapped at 76 chars.. )
Sorry.. copy pasted from my "idea" notes then word wrap fooled me..
Quoted 18 lines
This seems simple enough to me and can be trivially extended to N if needed.
Quoted 1 line
The typical implementation would looks something like:
unsigned long pids[N]; unsigned int pid_idx;set:
unsigned long *pids = numab->pids + pid_idx; if (!__test_bit(bit, pids)) __set_bit(bit, pids);test:
unsigned long pids = 0; for (int i = 0; i < N; i++) pids |= numab->pids[i]; return __test_bit(bit, &pids);
Quoted 6 lines
rotate:
idx = READ_ONCE(numab->pid_idx); WRITE_ONCE(numab->pid_idx, (idx + 1) % N); numab->pids[idx] = 0;Note the actual rotate can be simplified to ^1 for N:=2.
Thanks good idea. This will be very helpful when we want to differentiate accessing PIDs in more granular way. Perhaps we can go with N=2 and stick to below simplification of your code above?
something like:
unsigned long pids[2]
// Assume pids[1] has latest detail always
set:
if (!__test_bit(bit, pids[1])
__set_bit(bit, pids[1])
test:
unsigned long pids = pids[0] | pids[1];
return __test_bit(bit, &pids);
rotate:
pids[0] = pids[1];
pids[1] = 0;
Re: [PATCH V2 2/3] sched/numa: Enhance vma scanning logic
In reply to Raghavendra K TQuoted 2 lines · Raghavendra K T
Quoted 1 line · Peter Zijlstra
On Wed, Feb 01, 2023 at 01:32:21PM +0530, Raghavendra K T wrote:
[...]
Quoted 15 lines
Quoted 15 lines
Quoted 7 lines
+ if (!vma_is_accessed(vma))
+ continue;
+
do {
start =max(start, vma->vm_start);
end =ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);This feels wrong, specifically we track
numa_scan_offsetper mm, now, if we divide the threads into two dis-joint groups each only using their own set of vmas (in fact quite common for workloads with proper data partitioning) it is possible to consistently sample one set of threads and thus not scan the other set of vmas.
Quoted 7 lines
Quoted 3 lines
It seems somewhat unlikely, but not impossible to create significant unfairness.
Agree, But that is the reason why we want to allow first few unconditional scans Or am I missing something?
Thinking further, may be we can summarize the different aspects of thread/ two disjoint set case itself into:
1) Unfairness because of way in which threads gets opportunity to scan.
2) Disjoint set of vmas in the partition set could be of different sizes
3) Disjoint set of vmas could be associated with different number of threads
Each of above can potentially help or make some thread do heavy lifting
but (2), and (3). is what I think we are trying to be Okay with by making sure tasks mostly do not scan others' vmas
(1) could be a real issue (though I know that there are many places we have corrected the issue by introducing offset in p->numa_next_scan)
but how the distribution looks now practically, I take it as a TODO and post.
Re: [PATCH V2 2/3] sched/numa: Enhance vma scanning logic
Quoted 39 lines · Raghavendra K T
Quoted 2 lines · Raghavendra K T
Quoted 1 line · Peter Zijlstra
On Wed, Feb 01, 2023 at 01:32:21PM +0530, Raghavendra K T wrote:
[...]
Quoted 15 lines
Quoted 15 lines
Quoted 7 lines
+ if (!vma_is_accessed(vma))
+ continue;
+
do {
start =max(start, vma->vm_start);
end =ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);This feels wrong, specifically we track
numa_scan_offsetper mm, now, if we divide the threads into two dis-joint groups each only using their own set of vmas (in fact quite common for workloads with proper data partitioning) it is possible to consistently sample one set of threads and thus not scan the other set of vmas.Quoted 7 lines
Quoted 3 lines
It seems somewhat unlikely, but not impossible to create significant unfairness.
Agree, But that is the reason why we want to allow first few unconditional scans Or am I missing something?
Thinking further, may be we can summarize the different aspects of thread/ two disjoint set case itself into:
1) Unfairness because of way in which threads gets opportunity to scan.
2) Disjoint set of vmas in the partition set could be of different sizes
3) Disjoint set of vmas could be associated with different number of threads
Each of above can potentially help or make some thread do heavy lifting
Quoted 7 lines
but (2), and (3). is what I think we are trying to be Okay with by making sure tasks mostly do not scan others' vmas
(1) could be a real issue (though I know that there are many places we have corrected the issue by introducing offset in
p->numa_next_scan)
but how the distribution looks now practically, I take it as a TODO and post.
Hello PeterZ,
Sorry to come back little late with Data for how unfair are we when we have two disjoint set of groups mentioned above:
Program I tested with:
1. 128/256 thread program divided into two sets each accessing different set of memory (set0, set1) from node1 and node2 to induce migration (8GB divided into 4GB each].
Total iteration per thread was around 2048 to make sure for 128 thread: program ran around 8 min
256 thread: program ran around 17/18 min
SUT: 128 core 256 CPU Milan with 2 nodes
Some of the observations:
1) Total number of threads which gets access to scan in the entire program span was around 50-62%
for e.g. 128 thread case total tasks got access to scan was around 74-84 for 256 thread range was 123-146
2) There was a little bias towards set 1 always (the threads from where remote faults occurred)
In summary: I do see that access to VMAs from disjoint sets is not fully
fair, But on the other hand it is not very bad too. There is definitely
some scope or possibility to explore/improve fairness in this area further.
Posting result for one of the 128 threads: (base 6.1.0 vanilla)
column1: frequency
column2: PID
set 0 threads
1 5906
1 5908
2 5912
1 5914
1 5916
1 5918
1 5926
2 5928
3 5932
3 5938
1 5940
1 5944
2 5948
2 5950
1 5956
1 5962
1 5974
1 5978
1 5992
1 6004
1 6006
1 6008
1 6012
3 6014
1 6016
2 6026
2 6028
1 6030set 1 threads
3 5907
5 5909
2 5911
4 5913
7 5915
2 5917
3 5919
5 5921
3 5923
2 5925
4 5927
4 5929
3 5931
3 5933
2 5935
7 5937
4 5939
3 5941
4 5943
1 5945
2 5947
1 5949
1 5951
2 5953
1 5955
1 5957
1 5959
1 5961
1 5963
1 5965
1 5967
1 5969
1 5971
2 5975
2 5979
2 5981
2 5983
5 5993
5 5995
11 5997
1 5999
6 6003
4 6005
3 6007
1 6013
1 6015
3 6017
1 6019
1 6021
1 6023
6 6027
4 6029
4 6031
1 6033PS: I have also tested above applying V3 patch (which incorporates your suggestions), have not seen much deviation in observation with patch.
Thanks
- Raghu
Peter Zijlstra
maintainerRe: [PATCH V2 2/3] sched/numa: Enhance vma scanning logic
Quoted 4 lines · Raghavendra K T
In summary: I do see that access to VMAs from disjoint sets is not fully
fair, But on the other hand it is not very bad too. There is definitely
some scope or possibility to explore/improve fairness in this area further.
Ok, might be good to summarize some of this in a comment near here, so that readers are aware of the caveat of this code.
Quoted 2 lines
PS: I have also tested above applying V3 patch (which incorporates your suggestions), have not seen much deviation in observation with patch.
I'll see if I can find it in this dumpester fire I call inbox :-)
Re: [PATCH V2 2/3] sched/numa: Enhance vma scanning logic
Quoted 9 lines · Peter Zijlstra
Quoted 4 lines · Raghavendra K T
In summary: I do see that access to VMAs from disjoint sets is not fully
fair, But on the other hand it is not very bad too. There is definitely
some scope or possibility to explore/improve fairness in this area further.Ok, might be good to summarize some of this in a comment near here, so that readers are aware of the caveat of this code.
Sure will do.
Quoted 4 lines
Quoted 2 lines
PS: I have also tested above applying V3 patch (which incorporates your suggestions), have not seen much deviation in observation with patch.
I'll see if I can find it in this dumpester fire I call inbox :-)
Sorry I wasn't clear there.. Still in inbox and am about to post.. It was a heads up.
Re: [PATCH V2 2/3] sched/numa: Enhance vma scanning logic
In reply to Raghavendra K TQuoted 2 lines · Raghavendra K T
Quoted 1 line · Peter Zijlstra
On Wed, Feb 01, 2023 at 01:32:21PM +0530, Raghavendra K T wrote:
[...]>>> diff --git a/mm/memory.c b/mm/memory.c
Quoted 16 lines
Quoted 6 lines
Quoted 6 lines
index
8c8420934d60..2ec3045cb8b3100644mm/memory.c +0
-0@@ -4718,6 +4718,7 @@ static vm_fault_t do_numa_page(struct vm_fault *vmf) bool was_writable = pte_savedwrite(vmf->orig_pte);Quoted 9 lines
mm/memory.c static vm_fault_t do_numa_page(struct vm_fault *vmf) · line 4724
Quoted 5 lines
mm/memory.c +1
-0int flags = 0; + vma_set_active_pid_bit(vma); /** The "pte" at this point cannot be used safely without * validation through pte_unmap_same(). It's of NUMA type but Urghh... do_*numa_page() is two near identical functions.. is there really no sane way to de-duplicate at least some of that?
Quoted 2 lines
Agree. I will explore and will take that as a separate TODO.
Did spend some time to look at if there is a better way of merging these
two.
code looks similar as you noted, with very subtle changes (pte vs pmd
and difference in unlock).
But I thought only some part of the code can be changed easily, but changing whole code did not look to be worth as of now. (unless we come up with better idea)
This is the only comment perhaps not addressed rightly I feel :(
Thanks