Skip to contentSkip to conversation

A Summary of VMA scanning improvements explored

RFC PATCH New Raghavendra K T 2 participants 4 messages Mar 22, 2024 – Jun 26, 2024

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 A Summary of VMA scanning improvements explored

I am posting the summary of numa balancing improvements tried out.

(Intention is RFC and revisiting these in future when some one sees potential benefits with PATCH1 and PATCH2).

PATCH3 has more potential for workloads that needs aggressive scanning but may need migration ratelimiting.

Pathset details:
==================
PATCH 1. Increase the number of access PID (information of tasks accessing VMA) history windows from 2 to 4

Based on PeterZ's suggestion/patch.
Rationale:
- Increases the depth of historical access of tasks
- Get a better view of hot VMAs
- Get a better view of VMA which are widely shared amongst tasks with that we can take better decision in choosing the VMAs that needs to be scanned for introducing PROT_NONE.

PATCH 2. Increase the number of bit used to map tasks accessing VMA from 64 to 128bit

Based on suggestion by Ingo
Rationale:
Decrease the number of collisions (false positive), while whole information still fits in a cacheline

This is potentially helpful when workload involve more threads and thus,
- unnecessarily do VMA scan.
- create contention in scan path.

PATCH 3. Change the notion of scanning 256MB limit per scan to 64k PTE scan (for 4k). Extend the same logic to hugepages / THP pages.

Based on suggestion by Mel

Rationale: This helps to cover more memory especially when THP is involved or a hugepage is involved.

PS: Please note all 3 are independent patches. Apologies in advance if patchset confuses any patching script. Also more comment/details will be added for patches of interest.

Summary of results:
==================
PATCH1 and PATCH2 are giving benefit in some cases I ran but they may still need more convincing usecase / results (as on 6.9+ kernel).

PATCH3:
Some benchmarks such as XSBench Hashjoin are benefiting from more scanning But microbenchmarks (such as allocate on one node fault from other node to see how fast migration happen), suffer because of aggressive migration overhead.

Overall if we combine ratelimiting of migration (similar to CXL) or tune the scan rate when it is not necessary to scan (for e.g., I still see VMA scanning does not slow even when rate of migration slowed down or all migrations completed.)

Change stat for each of the patches
======================
PATCH 1:

Raghavendra K T (1):
sched/numa: Hot VMA and shared VMA optimization

 include/linux/mm.h       | 12 ++++++---
 include/linux/mm_types.h | 11 +++++---
 kernel/sched/fair.c      | 58 ++++++++++++++++++++++++++++++++++++----
 3 files changed, 69 insertions(+), 12 deletions(-)

base-commit: b0546776ad3f332e215cebc0b063ba4351971cca
============================
PATCH 2:

Raghavendra K T (1):
sched/numa: Increase the VMA accessing PID bits

 include/linux/mm.h       | 29 ++++++++++++++++++++++++++---
 include/linux/mm_types.h |  7 ++++++-
 kernel/sched/fair.c      | 21 ++++++++++++++++-----
 3 files changed, 48 insertions(+), 9 deletions(-)

base-commit: b0546776ad3f332e215cebc0b063ba4351971cca
===========================
PATCH 3:

Raghavendra K T (1):
sched/numa: Convert 256MB VMA scan limit notion

 include/linux/hugetlb.h |  3 +-
 include/linux/mm.h      | 16 +++++++-
 kernel/sched/fair.c     | 15 ++++---
 mm/hugetlb.c            |  9 +++++
 mm/mempolicy.c          | 11 +++++-
 mm/mprotect.c           | 87 +++++++++++++++++++++++++++++++++--------
 6 files changed, 115 insertions(+), 26 deletions(-)

base-commit: b0546776ad3f332e215cebc0b063ba4351971cca

Signature · 1 line
2.34.1
#1 lore raw

RFC PATCH 1/1 sched/numa: Hot VMA and shared VMA optimization

Optimizations are based on history of PIDs accessing VMA.

- Increase tasks' access history windows (PeterZ) from 2 to 4. ( This patch is from Peter Zijlstra <[email protected]>)

Idea: A task is allowed to scan a VMA if:
- VMA was very recently accessed as indicated by the latest access PIDs information (hot VMA).
- VMA is shared by more than 2 tasks. Here whole history of VMA's access PIDs is considered using bitmap_weight().

---
I will split the patset and post if we find this pathset useful going further. First patch is from PeterZ.

 include/linux/mm.h       | 12 ++++++---
 include/linux/mm_types.h | 11 +++++---
 kernel/sched/fair.c      | 58 ++++++++++++++++++++++++++++++++++++----
 3 files changed, 69 insertions(+), 12 deletions(-)
include/linux/mm.h +8 -4
index f5a97dec5169..1bf1df064b60 100644
@@ -1744,10 +1744,14 @@ static inline int folio_xchg_access_time(struct folio *folio, int time)
 static inline void vma_set_access_pid_bit(struct vm_area_struct *vma)
 {
 	unsigned int pid_bit;
-
-	pid_bit = hash_32(current->pid, ilog2(BITS_PER_LONG));
-	if (vma->numab_state && !test_bit(pid_bit, &vma->numab_state->pids_active[1])) {
-		__set_bit(pid_bit, &vma->numab_state->pids_active[1]);
+	unsigned long *pids, pid_idx;
+
+	if (vma->numab_state) {
+		pid_bit = hash_32(current->pid, ilog2(BITS_PER_LONG));
+		pid_idx = READ_ONCE(vma->numab_state->pids_active_idx);
+		pids = vma->numab_state->pids_active + pid_idx;
+		if (!test_bit(pid_bit, pids))
+			__set_bit(pid_bit, pids);
 	}
 }
 #else /* !CONFIG_NUMA_BALANCING */
include/linux/mm_types.h +8 -3
index 8b611e13153e..050ceef1e9d5 100644
@@ -574,6 +574,7 @@ struct vma_lock {
 	struct rw_semaphore lock;
 };
 
+#define NR_ACCESS_PID_HIST	4
 struct vma_numab_state {
 	/*
 	 * Initialised as time in 'jiffies' after which VMA
@@ -588,17 +589,21 @@ struct vma_numab_state {
 	 */
 	unsigned long pids_active_reset;
 
+	/* Points to current active PID tracking index. */
+	unsigned long pids_active_idx;
+
 	/*
 	 * Approximate tracking of PIDs that trapped a NUMA hinting
 	 * fault. May produce false positives due to hash collisions.
 	 *
-	 *   [0] Previous PID tracking
-	 *   [1] Current PID tracking
+	 *   [pids_active_idx - 1] Previous PID tracking
+	 *   [pids_active_idx] Current PID tracking
 	 *
+	 * Whole array is used in a rotating manner to track latest PIDs.
 	 * Window moves after next_pid_reset has expired approximately
 	 * every VMA_PID_RESET_PERIOD jiffies:
 	 */
-	unsigned long pids_active[2];
+	unsigned long pids_active[NR_ACCESS_PID_HIST];
 
 	/* MM scan sequence ID when scan first started after VMA creation */
 	int start_scan_seq;
kernel/sched/fair.c +53 -5

84 lines not on this page · raw message

Signature · 1 line
2.34.1
#2 lore raw

Re: [RFC PATCH 1 1/1] sched/numa: Hot VMA and shared VMA optimization

Hi Raghavendra,

Quoted 11 lines · Raghavendra K T

Optimizations are based on history of PIDs accessing VMA.

- Increase tasks' access history windows (PeterZ) from 2 to 4. ( This patch is from Peter Zijlstra <[email protected]>)

Idea: A task is allowed to scan a VMA if:
- VMA was very recently accessed as indicated by the latest access PIDs information (hot VMA).
- VMA is shared by more than 2 tasks. Here whole history of VMA's access PIDs is considered using bitmap_weight().

Quoted 5 lines

---
I will split the patset and post if we find this pathset useful going further. First patch is from PeterZ.

This is a good direction I think. We did an initial test using autonumabench THREADLOCAL on a 240 CPUs 2 nodes system. It seems that this patch does not show obvious difference, but it shows a more stable result(less run-to-run variance). We'll enable the Sub-Numa-Cluster to see if there is any difference. My understanding is that, if we can extend the NR_ACCESS_PID_HIST further, the THREADLOCAL could see more benefits, as each thread has its own VMA. Or maybe make the length of VMA access history adaptive(rather than a fixed 4) could be more flexible.
numa_scan_orig numa_scan_4_history

Min       syst-NUMA01_THREADLOCAL      388.47 (   0.00%)      397.43 (  -2.31%)
Min       elsp-NUMA01_THREADLOCAL       40.27 (   0.00%)       38.94 (   3.30%)
Amean     syst-NUMA01_THREADLOCAL      467.62 (   0.00%)      459.10 (   1.82%)
Amean     elsp-NUMA01_THREADLOCAL       42.20 (   0.00%)       44.84 (  -6.26%)
Stddev    syst-NUMA01_THREADLOCAL       74.11 (   0.00%)       60.90 (  17.81%)
CoeffVar  syst-NUMA01_THREADLOCAL       15.85 (   0.00%)       13.27 (  16.29%)
Max       syst-NUMA01_THREADLOCAL      535.36 (   0.00%)      519.21 (   3.02%)
Max       elsp-NUMA01_THREADLOCAL       43.96 (   0.00%)       56.33 ( -28.14%)
BAmean-50 syst-NUMA01_THREADLOCAL      388.47 (   0.00%)      397.43 (  -2.31%)
BAmean-50 elsp-NUMA01_THREADLOCAL       40.27 (   0.00%)       38.94 (   3.30%)
BAmean-95 syst-NUMA01_THREADLOCAL      433.75 (   0.00%)      429.05 (   1.08%)
BAmean-95 elsp-NUMA01_THREADLOCAL       41.31 (   0.00%)       39.09 (   5.39%)
BAmean-99 syst-NUMA01_THREADLOCAL      433.75 (   0.00%)      429.05 (   1.08%)
BAmean-99 elsp-NUMA01_THREADLOCAL       41.31 (   0.00%)       39.09 (   5.39%)

thanks,
Chenyu

#3 lore raw

Re: [RFC PATCH 1 1/1] sched/numa: Hot VMA and shared VMA optimization

Quoted 29 lines · Chen Yu

Hi Raghavendra,

Quoted 11 lines · Raghavendra K T

Optimizations are based on history of PIDs accessing VMA.

- Increase tasks' access history windows (PeterZ) from 2 to 4. ( This patch is from Peter Zijlstra <[email protected]>)

Idea: A task is allowed to scan a VMA if:
- VMA was very recently accessed as indicated by the latest access PIDs information (hot VMA).
- VMA is shared by more than 2 tasks. Here whole history of VMA's access PIDs is considered using bitmap_weight().

Quoted 5 lines

---
I will split the patset and post if we find this pathset useful going further. First patch is from PeterZ.

This is a good direction I think. We did an initial test using autonumabench THREADLOCAL on a 240 CPUs 2 nodes system. It seems that this patch does not show obvious difference, but it shows a more stable result(less run-to-run variance). We'll enable the Sub-Numa-Cluster to see if there is any difference. My understanding is that, if we can extend the NR_ACCESS_PID_HIST further, the THREADLOCAL could see more benefits, as each thread has its own VMA. Or maybe make the length of VMA access history adaptive(rather than a fixed 4) could be more flexible.
numa_scan_orig numa_scan_4_history

Quoted 15 lines
Min       syst-NUMA01_THREADLOCAL      388.47 (   0.00%)      397.43 (  -2.31%)
Min       elsp-NUMA01_THREADLOCAL       40.27 (   0.00%)       38.94 (   3.30%)
Amean     syst-NUMA01_THREADLOCAL      467.62 (   0.00%)      459.10 (   1.82%)
Amean     elsp-NUMA01_THREADLOCAL       42.20 (   0.00%)       44.84 (  -6.26%)
Stddev    syst-NUMA01_THREADLOCAL       74.11 (   0.00%)       60.90 (  17.81%)
CoeffVar  syst-NUMA01_THREADLOCAL       15.85 (   0.00%)       13.27 (  16.29%)
Max       syst-NUMA01_THREADLOCAL      535.36 (   0.00%)      519.21 (   3.02%)
Max       elsp-NUMA01_THREADLOCAL       43.96 (   0.00%)       56.33 ( -28.14%)
BAmean-50 syst-NUMA01_THREADLOCAL      388.47 (   0.00%)      397.43 (  -2.31%)
BAmean-50 elsp-NUMA01_THREADLOCAL       40.27 (   0.00%)       38.94 (   3.30%)
BAmean-95 syst-NUMA01_THREADLOCAL      433.75 (   0.00%)      429.05 (   1.08%)
BAmean-95 elsp-NUMA01_THREADLOCAL       41.31 (   0.00%)       39.09 (   5.39%)
BAmean-99 syst-NUMA01_THREADLOCAL      433.75 (   0.00%)      429.05 (   1.08%)
BAmean-99 elsp-NUMA01_THREADLOCAL       41.31 (   0.00%)       39.09 (   5.39%)

Thanks for the test and report. I will split the patches and also test for N=6,8. (on top of your patch perhaps to make sure we have benefits further).

Making adaptive may be little difficult. How to assess which size is doing better dynamically seems to be little hard to imagine for me. (/me Need to think here)

Thanks and Regards
- Raghu