Skip to contentSkip to conversation

sched,numa cap pte scanning overhead to 3% of run time

PATCH In review Rik van Riel 2 participants 4 messages Nov 4, 2015 – Nov 5, 2015 Scheduler

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched,numa cap pte scanning overhead to 3% of run time

There is a fundamental mismatch between the runtime based NUMA scanning at the task level, and the wall clock time NUMA scanning at the mm level. On a severely overloaded system, with very large processes, this mismatch can cause the system to spend all of its time in change_prot_numa().

This can happen if the task spends at least two ticks in change_prot_numa(), and only gets two ticks of CPU time in the real time between two scan intervals of the mm.

This patch ensures that if the system is so busy that the task got rescheduled during change_prot_numa(), we never spend more than 3% of run time scanning PTEs.

This patch does nothing if the CPU is not overloaded at all, and the task is not rescheduled during change_prot_numa().

All of the above only works if we fix the math underflow issue in task_numa_tick, so do that as well (Jan Stancek).

---
 kernel/sched/fair.c | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)
kernel/sched/fair.c +16 -1
index 824aa9f501a3..e9b9ac424a76 100644
@@ -2155,6 +2155,7 @@ void task_numa_work(struct callback_head *work)
 	unsigned long migrate, next_scan, now = jiffies;
 	struct task_struct *p = current;
 	struct mm_struct *mm = p->mm;
+	u64 runtime = p->se.sum_exec_runtime;
 	struct vm_area_struct *vma;
 	unsigned long start, end;
 	unsigned long nr_pte_updates = 0;
@@ -2277,6 +2278,20 @@ void task_numa_work(struct callback_head *work)
 	else
 		reset_ptenuma_scan(p);
 	up_read(&mm->mmap_sem);
+
+	/*
+	 * There is a fundamental mismatch between the runtime based
+	 * NUMA scanning at the task level, and the wall clock time
+	 * NUMA scanning at the mm level. On a severely overloaded
+	 * system, with very large processes, this mismatch can cause
+	 * the system to spend all of its time in change_prot_numa().
+	 * Limit NUMA PTE scanning to 3% of the task's run time, if
+	 * we spent so much time scanning we got rescheduled.
+	 */
+	if (unlikely(p->se.sum_exec_runtime != runtime)) {
+		u64 diff = p->se.sum_exec_runtime - runtime;
+		p->node_stamp += 32 * diff;
+	}
 }
 
 /*
@@ -2302,7 +2317,7 @@ void task_tick_numa(struct rq *rq, struct task_struct *curr)
 	now = curr->se.sum_exec_runtime;
 	period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;
 
-	if (now - curr->node_stamp > period) {
+	if (now > curr->node_stamp + period) {
 		if (!curr->node_stamp)
 			curr->numa_scan_period = task_scan_min(curr);
 		curr->node_stamp += period;
maintainer
#1 lore raw
Quoted 17 lines · Rik van Riel

+++ b/kernel/sched/fair.c

kernel/sched/fair.c +5 -0
@@ -2155,6 +2155,7 @@ void task_numa_work(struct callback_head *work)
 	unsigned long migrate, next_scan, now = jiffies;
 	struct task_struct *p = current;
 	struct mm_struct *mm = p->mm;
+	u64 runtime = p->se.sum_exec_runtime;
 	struct vm_area_struct *vma;
 	unsigned long start, end;
 	unsigned long nr_pte_updates = 0;
@@ -2277,6 +2278,20 @@ void task_numa_work(struct callback_head *work)
 	else
 		reset_ptenuma_scan(p);
 	up_read(&mm->mmap_sem);
+
+	/*
+	 * There is a fundamental mismatch between the runtime based
+	 * NUMA scanning at the task level, and the wall clock time

kernel/sched/fair.c void task_numa_work(struct callback_head *work) · line 2294

Quoted 10 lines
kernel/sched/fair.c +10 -0
+	 * NUMA scanning at the mm level. On a severely overloaded
+	 * system, with very large processes, this mismatch can cause
+	 * the system to spend all of its time in change_prot_numa().
+	 * Limit NUMA PTE scanning to 3% of the task's run time, if
+	 * we spent so much time scanning we got rescheduled.
+	 */
+	if (unlikely(p->se.sum_exec_runtime != runtime)) {
+		u64 diff = p->se.sum_exec_runtime - runtime;
+		p->node_stamp += 32 * diff;
+	}

I don't actually see how this does what it says it does.

kernel/sched/fair.c void task_tick_numa(struct rq *rq, struct task_struct *curr) · line 2323

Quoted 12 lines
kernel/sched/fair.c +1 -1
 }
 
 /*
@@ -2302,7 +2317,7 @@ void task_tick_numa(struct rq *rq, struct task_struct *curr)
 	now = curr->se.sum_exec_runtime;
 	period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;
 
-	if (now - curr->node_stamp > period) {
+	if (now > curr->node_stamp + period) {
 		if (!curr->node_stamp)
 			curr->numa_scan_period = task_scan_min(curr);
 		curr->node_stamp += period;

And this really should be an independent patch. Although the fix I had in mind looked like:

	if ((s64)(now - curr->node_stamp) > period)

But I suppose this works too.

#2 lore raw
Quoted 22 lines · Peter Zijlstra
Quoted 21 lines · Rik van Riel

+++ b/kernel/sched/fair.c

kernel/sched/fair.c +9 -0
@@ -2155,6 +2155,7 @@ void task_numa_work(struct callback_head *work)
 	unsigned long migrate, next_scan, now = jiffies;
 	struct task_struct *p = current;
 	struct mm_struct *mm = p->mm;
+	u64 runtime = p->se.sum_exec_runtime;
 	struct vm_area_struct *vma;
 	unsigned long start, end;
 	unsigned long nr_pte_updates = 0;
@@ -2277,6 +2278,20 @@ void task_numa_work(struct callback_head *work)
 	else
 		reset_ptenuma_scan(p);
 	up_read(&mm->mmap_sem);
+
+	/*
+	 * There is a fundamental mismatch between the runtime based
+	 * NUMA scanning at the task level, and the wall clock time
+	 * NUMA scanning at the mm level. On a severely overloaded
+	 * system, with very large processes, this mismatch can cause
+	 * the system to spend all of its time in change_prot_numa().
+	 * Limit NUMA PTE scanning to 3% of the task's run time, if
Quoted 8 lines

kernel/sched/fair.c void task_numa_work(struct callback_head *work) · line 2294

Quoted 6 lines
kernel/sched/fair.c +6 -0
+	 * we spent so much time scanning we got rescheduled.
+	 */
+	if (unlikely(p->se.sum_exec_runtime != runtime)) {
+		u64 diff = p->se.sum_exec_runtime - runtime;
+		p->node_stamp += 32 * diff;
+	}

I don't actually see how this does what it says it does

If we got rescheduled during the assigning of runtime above, and this point, the scheduler should have updated the p->se.sum_exec_runtime statistic, given that update_curr is called from both dequeue_entity and enqueue_entity in fair.c

Advancing the node_stamp by 32x the amount of time the task consumed between entering task_numa_work and this point should ensure task_numa_work does not get queued again until we have used 32x as much time doing something else.

That should limit the CPU time used by task_numa_work.

What am I missing?

Quoted 13 lines

kernel/sched/fair.c void task_tick_numa(struct rq *rq, struct task_struct *curr) · line 2323

Quoted 9 lines
kernel/sched/fair.c +1 -1
@@ -2302,7 +2317,7 @@ void task_tick_numa(struct rq *rq, struct task_struct *curr)
 	now = curr->se.sum_exec_runtime;
 	period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;
 
-	if (now - curr->node_stamp > period) {
+	if (now > curr->node_stamp + period) {
 		if (!curr->node_stamp)
 			curr->numa_scan_period = task_scan_min(curr);
 		curr->node_stamp += period;

And this really should be an independent patch. Although the fix I had in mind looked like:

Quoted 3 lines
	if ((s64)(now - curr->node_stamp) > period)

But I suppose this works too.

I can resend this as a separate patch if you prefer.

maintainer
#3 lore raw
Quoted 32 lines · Rik van Riel
Quoted 22 lines · Peter Zijlstra
Quoted 21 lines · Rik van Riel

+++ b/kernel/sched/fair.c

kernel/sched/fair.c +9 -0
@@ -2155,6 +2155,7 @@ void task_numa_work(struct callback_head *work)
 	unsigned long migrate, next_scan, now = jiffies;
 	struct task_struct *p = current;
 	struct mm_struct *mm = p->mm;
+	u64 runtime = p->se.sum_exec_runtime;
 	struct vm_area_struct *vma;
 	unsigned long start, end;
 	unsigned long nr_pte_updates = 0;
@@ -2277,6 +2278,20 @@ void task_numa_work(struct callback_head *work)
 	else
 		reset_ptenuma_scan(p);
 	up_read(&mm->mmap_sem);
+
+	/*
+	 * There is a fundamental mismatch between the runtime based
+	 * NUMA scanning at the task level, and the wall clock time
+	 * NUMA scanning at the mm level. On a severely overloaded
+	 * system, with very large processes, this mismatch can cause
+	 * the system to spend all of its time in change_prot_numa().
+	 * Limit NUMA PTE scanning to 3% of the task's run time, if
Quoted 8 lines

kernel/sched/fair.c void task_numa_work(struct callback_head *work) · line 2294

Quoted 6 lines
kernel/sched/fair.c +6 -0
+	 * we spent so much time scanning we got rescheduled.
+	 */
+	if (unlikely(p->se.sum_exec_runtime != runtime)) {
+		u64 diff = p->se.sum_exec_runtime - runtime;
+		p->node_stamp += 32 * diff;
+	}

I don't actually see how this does what it says it does

Quoted 1 line

If we got rescheduled during the assigning of runtime

Or just had a tick. Even if the whole thing took a fraction of a ms but we got unlucky and got hit by a tick the sum_exec_runtime would get updated and not match here.

Quoted 7 lines

Advancing the node_stamp by 32x the amount of time the task consumed between entering task_numa_work and this point should ensure task_numa_work does not get queued again until we have used 32x as much time doing something else.

What am I missing?

The above, issue and the fact that I'm really tired and didn't do 1:32 ~ 3%.

So the tick scenario can cause a 32*TICK_NSEC delay even though we spend much less than TICK_NSEC time scanning, dropping th effective rate much below the 3%.

Not sure it makes sense to do more accurate accounting, but I suppose we should mention it somewhere.

Quoted 11 lines
Quoted 9 lines

kernel/sched/fair.c void task_tick_numa(struct rq *rq, struct task_struct *curr) · line 2323

Quoted 9 lines
kernel/sched/fair.c +1 -1
@@ -2302,7 +2317,7 @@ void task_tick_numa(struct rq *rq, struct task_struct *curr)
 	now = curr->se.sum_exec_runtime;
 	period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;
 
-	if (now - curr->node_stamp > period) {
+	if (now > curr->node_stamp + period) {
 		if (!curr->node_stamp)
 			curr->numa_scan_period = task_scan_min(curr);
 		curr->node_stamp += period;

I can resend this as a separate patch if you prefer.

Yes, its an unrelated fix.