[RFC][PATCH RT 0/4 v2] sched/rt: Lower rq lock contention latencies on many CPU boxes

Steven Rostedt

author reviewer

2012-12-12 19:27 UTC #0 lore raw

v2 cover sched/rt: Lower rq lock contention latencies on many CPU boxes

This version I rearranged the patches a little so that the IPI patch comes last. As the first 3 patches are less controversal, and should probably be added now.

The difference in this version was that I added more comments, but more importantly I also added a sched feature called RT_PUSH_IPI. When this feature is enabled, it switches the pull logic to send an IPI to the RT overloaded CPU to do a push instead of doing the pull locally.

When the feature is disabled, the push/pull logic stays the same as it always has (with rq lock contention).

Now I've discussed this with Clark, and we noticed that the contention didn't show up until we tried it on a 24 CPU machine. On a 16 CPU machine it ran fine. Thus, by default, machines with 16 or less CPUs will have the RT_PUSH_IPI feature disabled. Machines with 17 or more possible CPUs will have the feature enabled at boot up. Note, we haven't tried it on a machine with 17 to 23 CPUs.

It is safe to enable or disable this feature at run time, although you may cause latencies in doing so, but there shouldn't be any missed wakeups or anything else that is serious. The worse that can happen is that you miss a pull, and an RT task will stay on its CPU when it could have migrated to another CPU that just lowered its priority. Well, if you are worried about that, don't change it when you care :-)

The 16 CPUs is just a heuristic, and people may debate it. And perhaps you may not like how the push/pull default changes between different machines. I could also add a command line switch to force enable/disable at boot, and/or I could add a config as well.

Right now, by default <= 16 CPU machines are as it always was, and 17 or more CPU machines have this new logic enabled. Either one can change it at run time via the debugfs directory (unfortunately it's not a sysctl).

Comments?

-- Steve

Steven Rostedt

author reviewer

2012-12-12 19:27 UTC #1 lore raw

RFC PATCH v2 1/4 sched/rt: Fix push_rt_task() to have the same checks as the caller did

Currently, the push_rt_task() only pushes the task if it is lower priority than the currently running task.

But this is not the only check. If the currently running task is also pinned, we may want to push as well, and we do this check when we wake up a task, but then we are guaranteed to fail pushing the task because the internal checks may fail.

Make the check the same as the wakeup checks. We could remove the check in the wake up and just let the push_rt_task() do the work, but this makes the wake up exit this check on the likely case that "ok_to_push_task()" will fail, and that we don't need to do the iterative loop of checks on the pushable task list.

Signed-off-by Steven Rostedt <[email protected]>

kernel/sched/rt.c +11 -5

Index: linux-rt.git/kernel/sched/rt.c
===================================================================
@@ -1615,6 +1615,15 @@ static struct task_struct *pick_next_pus
 	return p;
 }
 
+static int ok_to_push_task(struct task_struct *p, struct task_struct *curr)
+{
+	return p->nr_cpus_allowed > 1 &&
+		rt_task(curr) &&
+		(curr->migrate_disable ||
+		 curr->nr_cpus_allowed < 2 ||
+		 curr->prio <= p->prio);
+}
+
 /*
  * If the current CPU has more than one RT task, see if the non
  * running task can migrate over to a CPU that is running a task

@@ -1649,7 +1658,7 @@ retry:
 	 * higher priority than current. If that's the case
 	 * just reschedule current.
 	 */
-	if (unlikely(next_task->prio < rq->curr->prio)) {
+	if (!ok_to_push_task(next_task, rq->curr)) {
 		resched_task(rq->curr);
 		return 0;
 	}

@@ -1814,10 +1823,7 @@ static void task_woken_rt(struct rq *rq,
 	if (!task_running(rq, p) &&
 	    !test_tsk_need_resched(rq->curr) &&
 	    has_pushable_tasks(rq) &&
-	    p->nr_cpus_allowed > 1 &&
-	    rt_task(rq->curr) &&
-	    (rq->curr->nr_cpus_allowed < 2 ||
-	     rq->curr->prio <= p->prio))
+	    ok_to_push_task(p, rq->curr))
 		push_rt_tasks(rq);
 }

Steven Rostedt

author reviewer

2012-12-12 19:27 UTC #2 lore raw

RFC PATCH v2 2/4 sched/rt: Try to migrate task if preempting pinned rt task

In reply to Steven Rostedt

If a higher priority task is about to preempt a task that has been pinned to a CPU. Try to first see if the higher priority task can preempt another task instead.

That is, a high priority process wakes up on a CPU while a currently running task can still migrate, it will miss pushing that high priority task to another CPU. If by the time the task schedules, the task that it's about to preempt could have changed its affinity and is pinned. At this time, it may be better to move the task to another CPU if one exists that is currently running a lower priority task than the one about to be preempted.

Signed-off-by Steven Rostedt <[email protected]>

kernel/sched/rt.c +15 -1

Index: linux-rt.git/kernel/sched/rt.c
===================================================================
@@ -1804,8 +1804,22 @@ skip:
 
 static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
 {
+	struct task_struct *p = prev;
+
+	/*
+	 * If we are preempting a pinned task see if we can push
+	 * the higher priority task first.
+	 */
+	if (prev->on_rq && (prev->nr_cpus_allowed <= 1 || prev->migrate_disable) &&
+	    has_pushable_tasks(rq) && rq->rt.highest_prio.next < prev->prio) {
+		p = _pick_next_task_rt(rq);
+
+		if (p != prev && p->nr_cpus_allowed > 1 && push_rt_task(rq))
+			p = _pick_next_task_rt(rq);
+	}
+
 	/* Try to pull RT tasks here if we lower this rq's prio */
-	if (rq->rt.highest_prio.curr > prev->prio)
+	if (rq->rt.highest_prio.curr > p->prio)
 		pull_rt_task(rq);
 }

Steven Rostedt

author reviewer

2012-12-12 19:27 UTC #3 lore raw

RFC PATCH v2 3/4 sched/rt: Initiate a pull when the priority of a task is lowered

In reply to Steven Rostedt

If a task lowers its priority (say by losing priority inheritance) if a higher priority task is waiting on another CPU, initiate a pull.

Signed-off-by Steven Rostedt <[email protected]>

kernel/sched/rt.c +6 -0

Index: linux-rt.git/kernel/sched/rt.c
===================================================================
@@ -997,6 +997,8 @@ inc_rt_prio(struct rt_rq *rt_rq, int pri
 	inc_rt_prio_smp(rt_rq, prio, prev_prio);
 }
 
+static int pull_rt_task(struct rq *this_rq);
+
 static void
 dec_rt_prio(struct rt_rq *rt_rq, int prio)
 {

@@ -1021,6 +1023,10 @@ dec_rt_prio(struct rt_rq *rt_rq, int pri
 		rt_rq->highest_prio.curr = MAX_RT_PRIO;
 
 	dec_rt_prio_smp(rt_rq, prio, prev_prio);
+
+	/* Try to pull RT tasks here if we lower this rq's prio */
+	if (prev_prio < rt_rq->highest_prio.curr)
+		pull_rt_task(rq_of_rt_rq(rt_rq));
 }
 
 #else

Steven Rostedt

author reviewer

2012-12-12 19:27 UTC #4 lore raw

RFC PATCH v2 4/4 sched/rt: Use IPI to trigger RT task push migration instead of pulling

In reply to Steven Rostedt

When debugging the latencies on a 40 core box, where we hit 300 to 500 microsecond latencies, I found there was a huge contention on the runqueue locks.

Investigating it further, running ftrace, I found that it was due to the pulling of RT tasks.

The test that was run was the following:

cyclictest --numa -p95 -m -d0 -i100

This created a thread on each CPU, that would set its wakeup in interations of 100 microseconds. The -d0 means that all the threads had the same interval (100us). Each thread sleeps for 100us and wakes up and measures its latencies.

What happened was another RT task would be scheduled on one of the CPUs that was running our test, when the other CPUS test went to sleep and scheduled idle. This cause the "pull" operation to execute on all these CPUs. Each one of these saw the RT task that was overloaded on the CPU of the test that was still running, and each one tried to grab that task in a thundering herd way.

To grab the task, each thread would do a double rq lock grab, grabbing its own lock as well as the rq of the overloaded CPU. As the sched domains on this box was rather flat for its size, I saw up to 12 CPUs block on this lock at once. This caused a ripple affect with the rq locks. As these locks were blocked, any wakeups or load balanceing on these CPUs would also block on these locks, and the wait time escalated.

I've tried various methods to lesson the load, but things like an atomic counter to only let one CPU grab the task wont work, because the task may have a limited affinity, and we may pick the wrong CPU to take that lock and do the pull, to only find out that the CPU we picked isn't in the task's affinity.

Instead of doing the PULL, I now have the CPUs that want the pull to send over an IPI to the overloaded CPU, and let that CPU pick what CPU to push the task to. No more need to grab the rq lock, and the push/pull algorithm still works fine.

With this patch, the latency dropped to just 150us over a 20 hour run. Without the patch, the huge latencies would trigger in seconds.

Now, this issue only seems to apply to boxes with greater than 16 CPUs. We noticed this on a 24 CPU box, and things got much worse on 40 (and presumably more CPUs would get even worse yet). But running with 16 CPUs and below, the lock contention caused by the pulling of RT tasks is not noticable.

I've created a new sched feature called RT_PUSH_IPI, which by default on 16 and less core CPUs is disabled, and on 17 or more CPUs it is enabled. That seems to be heuristic limit where the pulling logic causes higher latencies than IPIs. Of course with all heuristics, things could be different with different architectures.

When RT_PUSH_IPI is not enabled, the old method of grabbing the rq locks and having the pulling CPU do the work is implemented. When RT_PUSH_IPI is enabled, the IPI is sent to the overloaded CPU to do a push.

To enabled or disable this at run time:

 # mount -t debugfs nodev /sys/kernel/debug
 # echo RT_PUSH_IPI > /sys/kernel/debug/sched_features
or
 # echo NO_RT_PUSH_IPI > /sys/kernel/debug/sched_features

Signed-off-by Steven Rostedt <[email protected]>

kernel/sched/core.c +16 -0

Index: linux-rt.git/kernel/sched/core.c
===================================================================
@@ -1538,6 +1538,9 @@ static void sched_ttwu_pending(void)
 
 void scheduler_ipi(void)
 {
+	if (sched_feat(RT_PULL_IPI))
+		sched_rt_push_check();
+
 	if (llist_empty(&this_rq()->wake_list) && !got_nohz_idle_kick())
 		return;

@@ -7533,6 +7536,19 @@ void __init sched_init_smp(void)
 	free_cpumask_var(non_isolated_cpus);
 
 	init_sched_rt_class();
+
+	/*
+	 * To avoid heavy contention on large CPU boxes,
+	 * when there is an RT overloaded CPU (two or more RT tasks
+	 * queued to run on a CPU and one of the waiting RT tasks
+	 * can migrate) and another CPU lowers its priority, instead
+	 * of grabbing both rq locks of the CPUS (as many CPUs lowering
+	 * their priority at the same time may create large latencies)
+	 * send an IPI to the CPU that is overloaded so that it can
+	 * do an efficent push.
+	 */
+	if (num_possible_cpus() > 16)
+		sched_feat_enable(__SCHED_FEAT_RT_PUSH_IPI);
 }
 #else
 void __init sched_init_smp(void)

kernel/sched/rt.c +37 -0

Index: linux-rt.git/kernel/sched/rt.c
===================================================================
@@ -1729,6 +1729,31 @@ static void push_rt_tasks(struct rq *rq)
 		;
 }
 
+/**
+ * sched_rt_push_check - check if we can push waiting RT tasks
+ *
+ * Called from sched IPI when sched feature RT_PUSH_IPI is enabled.
+ *
+ * Checks if there is an RT task that can migrate and there exists
+ * a CPU in its affinity that only has tasks lower in priority than
+ * the waiting RT task. If so, then it will push the task off to that
+ * CPU.
+ */
+void sched_rt_push_check(void)
+{
+	struct rq *rq = cpu_rq(smp_processor_id());
+
+	if (WARN_ON_ONCE(!irqs_disabled()))
+		return;
+
+	if (!has_pushable_tasks(rq))
+		return;
+
+	raw_spin_lock(&rq->lock);
+	push_rt_tasks(rq);
+	raw_spin_unlock(&rq->lock);
+}
+
 static int pull_rt_task(struct rq *this_rq)
 {
 	int this_cpu = this_rq->cpu, ret = 0, cpu;

@@ -1756,6 +1781,18 @@ static int pull_rt_task(struct rq *this_
 			continue;
 
 		/*
+		 * When the RT_PUSH_IPI sched feature is enabled, instead
+		 * of trying to grab the rq lock of the RT overloaded CPU
+		 * send an IPI to that CPU instead. This prevents heavy
+		 * contention from several CPUs lowering its priority
+		 * and all trying to grab the rq lock of that overloaded CPU.
+		 */
+		if (sched_feat(RT_PUSH_IPI)) {
+			smp_send_reschedule(cpu);
+			continue;
+		}
+
+		/*
 		 * We can potentially drop this_rq's lock in
 		 * double_lock_balance, and another CPU could
 		 * alter this_rq

kernel/sched/sched.h +5 -0

Index: linux-rt.git/kernel/sched/sched.h
===================================================================
@@ -1111,6 +1111,8 @@ static inline void double_rq_unlock(stru
 		__release(rq2->lock);
 }
 
+void sched_rt_push_check(void);
+
 #else /* CONFIG_SMP */
 
 /*

@@ -1144,6 +1146,9 @@ static inline void double_rq_unlock(stru
 	__release(rq2->lock);
 }
 
+void sched_rt_push_check(void)
+{
+}
 #endif
 
 extern struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq);

kernel/sched/features.h +14 -0

Index: linux-rt.git/kernel/sched/features.h
===================================================================
@@ -73,6 +73,20 @@ SCHED_FEAT(PREEMPT_LAZY, true)
 # endif
 #endif
 
+/*
+ * In order to avoid a thundering herd attack of CPUS that are
+ * lowering their priorities at the same time, and there being
+ * a single CPU that has an RT task that can migrate and is waiting
+ * to run, where the other CPUs will try to take that CPUs
+ * rq lock and possibly create a large contention, sending an
+ * IPI to that CPU and let that CPU push the RT task to where
+ * it should go may be a better scenario.
+ *
+ * This is default off for machines with <= 16 CPUs, and will
+ * be turned on at boot up for machines with > 16 CPUs.
+ */
+SCHED_FEAT(RT_PUSH_IPI, false)
+
 SCHED_FEAT(FORCE_SD_OVERLAP, false)
 SCHED_FEAT(RT_RUNTIME_SHARE, true)
 SCHED_FEAT(LB_MIN, false)

Steven Rostedt

author reviewer

2012-12-12 20:44 UTC #5 lore raw

Re: [RFC][PATCH RT 4/4 v2] sched/rt: Use IPI to trigger RT task push migration instead of pulling

I'm doing these changes in quilt and not git. Thus, I'm hitting some of the silly old quilt bugs, like forgetting to do a quilt refresh :-p

This one will actually compile and boot.

-- Steve

sched/rt: Use IPI to trigger RT task push migration instead of pulling