Skip to contentSkip to conversation

New RT Balancing version 4

PATCH In review Steven Rostedt 3 participants 36 messages Nov 21, 2007

Subsystems (3)
MM core Scheduler exec and binfmt
lore
Share & tools
lore

Steven Rostedt

author reviewer
#0 lore raw

v4 cover New RT Balancing version 4

[
Changes since V3:

Updated to git tree 2ffbb8377c7a0713baf6644e285adc27a5654582

Removed cpumask_t from stacks (using per_cpu masks).

Optimized the searching for overloaded queues a bit.
(a lot of work in this area)

Run RT balance logic on waking of new tasks.

The tarball of these patches is also available at
http://rostedt.homelinux.com/rt/rt-balance-patches-v4.tar.bz2
]

Currently in mainline the balancing of multiple RT threads is quite broken. That is to say that a high priority thread that is scheduled on a CPU with a higher priority thread, may need to unnecessarily wait while it can easily run on another CPU that's running a lower priority thread.

Balancing (or migrating) tasks in general is an art. Lots of considerations must be taken into account. Cache lines, NUMA and more. This is true with general processes which expect high through put and migration can be done in batch. But when it comes to RT tasks, we really need to put them off to a CPU that they can run on as soon as possible. Even if it means a bit of cache line flushing.

Right now an RT task can wait several milliseconds before it gets scheduled to run. And perhaps even longer. The migration thread is not fast enough to take care of RT tasks.

To demonstrate this, I wrote a simple test.

http://rostedt.homelinux.com/rt/rt-migrate-test.c

(gcc -o rt-migrate-test rt-migrate-test.c -lpthread)

This test expects a parameter to pass in the number of threads to create. If you add the '-c' option (check) it will terminate if the test fails one of the iterations. If you add this, pass in +1 threads.

For example, on a 4 way box, I used

rt-migrate-test -c 5

What this test does is to create the number of threads specified (in this case 5). Each thread is set as an RT FIFO task starting at a specified prio (default 2) and each thread being one priority higher. So with this example the 5 threads created are at priorities 2, 3, 4, 5, and 6.

The parent thread sets its priority to one higher than the highest of the children (this example 7). It uses pthread_barrier_wait to synchronize the threads. Then it takes a time stamp and starts all the threads. The threads when woken up take a time stamp and compares it to the parent thread to see how long it took to be awoken. It then runs for an interval (20ms default) in a busy loop. The busy loop ends when it reaches the interval delta from the start time stamp. So if it is preempted, it may not actually run for the full interval. This is expected behavior of the test.

The numbers recorded are the delta from the thread's time stamp from the parent time stamp. The number of iterations it ran the busy loop for, and the delta from a thread time stamp taken at the end of the loop to the parent time stamp.

Sometimes a lower priority task might wake up before a higher priority, but this is OK, as long as the higher priority process gets the CPU when it is awoken.

At the end of the test, the iteration data is printed to stdout. If a higher priority task had to wait for a lower one to finish running, then this is considered a failure. Here's an example of the output from a run against git commit 4fa4d23fa20de67df919030c1216295664866ad7.

1: 36 33 20041 39 33
len: 20036 20033 40041 20039 20033
loops: 167789 167693 227167 167829 167814

On iteration 1 (starts at 0) the third task started at 20ms after the parent woke it up. We can see here that the first two tasks ran to completion before the higher priority task was even able to start. That is a 20ms latency for the higher priority task!!!

So people who think that their audio would lose most latencies by upping the priority, may be in for a surprise. Since some kernel threads (like the migration thread itself) may cause this latency.

To solve this issue, I've changed the RT task balancing from a passive method (migration thread) to an active method. This new method is to actively push or pull RT tasks when they are woken up or scheduled.

On wake up of a task if it is an RT task, and there's already an RT task of higher priority running on its runqueue, we initiate a push_rt_tasks algorithm. This algorithm looks at the highest non-running RT task and tries to find a CPU where it can run on. It only migrates the RT task if it finds a CPU (of lowest priority) where the RT task can run on and can preempt the currently running task on that CPU. We continue pushing RT tasks until we can't push anymore.

If a RT task fails to be migrated we stop the pushing. This is possible because we are always looking at the highest priority RT task on the run queue. And if it can't migrate, then most likely the lower RT tasks can not either.

There is one case that is not covered by this patch set. That is that when the highest priority non running RT task has its CPU affinity in such a way that it can not preempt any tasks on the CPUs running on CPUs of its affinity. But a lower priority task has a larger affinity to CPUs that it can run on. This is a case where the lower priority task will not be migrated to those CPUS (although those CPUs may pull that task). Currently this patch set ignores this scenario.

Another case where we push RT tasks is in the finish_task_switch. This is done since the running RT task can not be migrated while it is running. So if an RT task is preempted by a higher priority RT task, we can migrate the RT task being preempted at that moment.

We also actively pull RT tasks. Whenever a runqueue is about to lower its priority (schedule a lower priority task) a check is done to see if that runqueue can pull RT tasks to it to run instead. A search is made of all overloaded runqueues (runqueues with more than one RT task scheduled on it) and checked to see if they have an RT task that can run on the runqueue (affinity matches) and is of higher priority than the task the runqueue is about to schedule. The pull algorithm pulls all RT tasks that match this case.

With this patch set, I ran the rt-migrate-test over night in a while loop with the -c option (which terminates upon failure) and it passed over 6500 tests (each doing 50 wakeups each).

Here's an example of the output from the patched kernel. This is just to explain it a bit more.

1: 20060 61 55 56 61
len: 40060 20061 20055 20056 20061
loops: 227255 146050 168104 145965 168144

2: 40 46 31 35 42
len: 20040 20046 20031 20035 20042
loops: 28 167769 167781 167668 167804

The first iteration (really 2cd, since we start at zero), is a typical run. The lowest prio task didn't start executing until the other 4 tasks finished and gave up the CPU.

The second iteration seems at first like a failure. But this is actually fine. The lowest priority task just happen to schedule onto a CPU before the higher priority tasks were woken up. But as you can see from this example, the higher priority tasks still were able to get scheduled right away and in doing so preempted the lower priority task. This can be seen by the number of loops that the lower priority task was able to complete. Only 28. This is because the busy loop terminates when the time stamp reaches the time interval (20ms here) from the start time stamp. Since the lower priority task was able to sneak in and start, it's time stamp was low. So after it got preempted, and rescheduled, it was already past the run time interval so it simply ended the loop.

Finally, the CFS RT balancing had to be removed in order for this to work. Testing showed that the CFS RT balancing would actually pull RT tasks from runqueues already assigned to the proper runqueues, and again cause latencies. With this new approach, the CFS RT balancing is not needed, and I suggest that these patches replace the current CFS RT balancing.

Also, let me stress, that I made a great attempt to have this cause as little overhead (practically none) to the non RT cases. Most of these algorithms only take place when more than one RT task is scheduled on the same runqueue.

Special thanks goes to Gregory Haskins for his advice and back and forth on IRC with ideas. Although I didn't use his actual patches (his were against -rt) it did help me clean up some of my code. Also, thanks go to Ingo Molnar himself for taking some ideas from his RT balance code in the -rt patch.

Comments welcomed!

-- Steve

author reviewer
#1 lore raw

PATCH v4 1/20 Add rt_nr_running accounting

This patch adds accounting to keep track of the number of RT tasks running on a runqueue. This information will be used in later patches.

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

---

 kernel/sched.c    |    1 +
 kernel/sched_rt.c |   17 +++++++++++++++++
 2 files changed, 18 insertions(+)
kernel/sched.c +1 -0
Index: linux-compile.git/kernel/sched.c
===================================================================
@@ -266,6 +266,7 @@ struct rt_rq {
 	struct rt_prio_array active;
 	int rt_load_balance_idx;
 	struct list_head *rt_load_balance_head, *rt_load_balance_curr;
+	unsigned long rt_nr_running;
 };
 
 /*
kernel/sched_rt.c +17 -0
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -25,12 +25,27 @@ static void update_curr_rt(struct rq *rq
 	curr->se.exec_start = rq->clock;
 }
 
+static inline void inc_rt_tasks(struct task_struct *p, struct rq *rq)
+{
+	WARN_ON(!rt_task(p));
+	rq->rt.rt_nr_running++;
+}
+
+static inline void dec_rt_tasks(struct task_struct *p, struct rq *rq)
+{
+	WARN_ON(!rt_task(p));
+	WARN_ON(!rq->rt.rt_nr_running);
+	rq->rt.rt_nr_running--;
+}
+
 static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup)
 {
 	struct rt_prio_array *array = &rq->rt.active;
 
 	list_add_tail(&p->run_list, array->queue + p->prio);
 	__set_bit(p->prio, array->bitmap);
+
+	inc_rt_tasks(p, rq);
 }
 
 /*

@@ -45,6 +60,8 @@ static void dequeue_task_rt(struct rq *r
 	list_del(&p->run_list);
 	if (list_empty(array->queue + p->prio))
 		__clear_bit(p->prio, array->bitmap);
+
+	dec_rt_tasks(p, rq);
 }
 
 /*
author reviewer
#2 lore raw

PATCH v4 2/20 track highest prio queued on runqueue

In reply to Steven Rostedt

This patch adds accounting to each runqueue to keep track of the highest prio task queued on the run queue. We only care about RT tasks, so if the run queue does not contain any active RT tasks its priority will be considered MAX_RT_PRIO.

This information will be used for later patches.

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

---

 kernel/sched.c    |    3 +++
 kernel/sched_rt.c |   18 ++++++++++++++++++
 2 files changed, 21 insertions(+)
kernel/sched.c +3 -0
Index: linux-compile.git/kernel/sched.c
===================================================================
@@ -267,6 +267,8 @@ struct rt_rq {
 	int rt_load_balance_idx;
 	struct list_head *rt_load_balance_head, *rt_load_balance_curr;
 	unsigned long rt_nr_running;
+	/* highest queued rt task prio */
+	int highest_prio;
 };
 
 /*

@@ -6776,6 +6778,7 @@ void __init sched_init(void)
 		rq->cpu = i;
 		rq->migration_thread = NULL;
 		INIT_LIST_HEAD(&rq->migration_queue);
+		rq->rt.highest_prio = MAX_RT_PRIO;
 #endif
 		atomic_set(&rq->nr_iowait, 0);
kernel/sched_rt.c +18 -0
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -29,6 +29,10 @@ static inline void inc_rt_tasks(struct t
 {
 	WARN_ON(!rt_task(p));
 	rq->rt.rt_nr_running++;
+#ifdef CONFIG_SMP
+	if (p->prio < rq->rt.highest_prio)
+		rq->rt.highest_prio = p->prio;
+#endif /* CONFIG_SMP */
 }
 
 static inline void dec_rt_tasks(struct task_struct *p, struct rq *rq)

@@ -36,6 +40,20 @@ static inline void dec_rt_tasks(struct t
 	WARN_ON(!rt_task(p));
 	WARN_ON(!rq->rt.rt_nr_running);
 	rq->rt.rt_nr_running--;
+#ifdef CONFIG_SMP
+	if (rq->rt.rt_nr_running) {
+		struct rt_prio_array *array;
+
+		WARN_ON(p->prio < rq->rt.highest_prio);
+		if (p->prio == rq->rt.highest_prio) {
+			/* recalculate */
+			array = &rq->rt.active;
+			rq->rt.highest_prio =
+				sched_find_first_bit(array->bitmap);
+		} /* otherwise leave rq->highest prio alone */
+	} else
+		rq->rt.highest_prio = MAX_RT_PRIO;
+#endif /* CONFIG_SMP */
 }
 
 static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup)
author reviewer
#3 lore raw

PATCH v4 3/20 push RT tasks

In reply to Steven Rostedt

This patch adds an algorithm to push extra RT tasks off a run queue to other CPU runqueues.

When more than one RT task is added to a run queue, this algorithm takes an assertive approach to push the RT tasks that are not running onto other run queues that have lower priority. The way this works is that the highest RT task that is not running is looked at and we examine the runqueues on the CPUS for that tasks affinity mask. We find the runqueue with the lowest prio in the CPU affinity of the picked task, and if it is lower in prio than the picked task, we push the task onto that CPU runqueue.

We continue pushing RT tasks off the current runqueue until we don't push any more. The algorithm stops when the next highest RT task can't preempt any other processes on other CPUS.

TODO: The algorithm may stop when there are still RT tasks that can be
migrated. Specifically, if the highest non running RT task CPU affinity is restricted to CPUs that are running higher priority tasks, there may be a lower priority task queued that has an affinity with a CPU that is running a lower priority task that it could be migrated to. This patch set does not address this issue.

Note: checkpatch reveals two over 80 character instances. I'm not sure
that breaking them up will help visually, so I left them as is.

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

---

 kernel/sched.c    |    8 +
 kernel/sched_rt.c |  225 +++++++++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 231 insertions(+), 2 deletions(-)
kernel/sched.c +7 -1
Index: linux-compile.git/kernel/sched.c
===================================================================
@@ -1877,6 +1877,8 @@ static void finish_task_switch(struct rq
 	prev_state = prev->state;
 	finish_arch_switch(prev);
 	finish_lock_switch(rq, prev);
+	schedule_tail_balance_rt(rq);
+
 	fire_sched_in_preempt_notifiers(current);
 	if (mm)
 		mmdrop(mm);

@@ -2110,11 +2112,13 @@ static void double_rq_unlock(struct rq *
 /*
  * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
  */
-static void double_lock_balance(struct rq *this_rq, struct rq *busiest)
+static int double_lock_balance(struct rq *this_rq, struct rq *busiest)
 	__releases(this_rq->lock)
 	__acquires(busiest->lock)
 	__acquires(this_rq->lock)
 {
+	int ret = 0;
+
 	if (unlikely(!irqs_disabled())) {
 		/* printk() doesn't work good under rq->lock */
 		spin_unlock(&this_rq->lock);

@@ -2125,9 +2129,11 @@ static void double_lock_balance(struct r
 			spin_unlock(&this_rq->lock);
 			spin_lock(&busiest->lock);
 			spin_lock(&this_rq->lock);
+			ret = 1;
 		} else
 			spin_lock(&busiest->lock);
 	}
+	return ret;
 }
 
 /*
kernel/sched_rt.c +224 -1

237 lines not on this page · raw message

author reviewer
#4 lore raw

PATCH v4 4/20 RT overloaded runqueues accounting

In reply to Steven Rostedt

This patch adds an RT overload accounting system. When a runqueue has more than one RT task queued, it is marked as overloaded. That is that it is a candidate to have RT tasks pulled from it.

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

---

 kernel/sched_rt.c |   36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
kernel/sched_rt.c +36 -0
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -3,6 +3,38 @@
  * policies)
  */
 
+#ifdef CONFIG_SMP
+static cpumask_t rt_overload_mask;
+static atomic_t rto_count;
+static inline int rt_overloaded(void)
+{
+	return atomic_read(&rto_count);
+}
+static inline cpumask_t *rt_overload(void)
+{
+	return &rt_overload_mask;
+}
+static inline void rt_set_overload(struct rq *rq)
+{
+	cpu_set(rq->cpu, rt_overload_mask);
+	/*
+	 * Make sure the mask is visible before we set
+	 * the overload count. That is checked to determine
+	 * if we should look at the mask. It would be a shame
+	 * if we looked at the mask, but the mask was not
+	 * updated yet.
+	 */
+	wmb();
+	atomic_inc(&rto_count);
+}
+static inline void rt_clear_overload(struct rq *rq)
+{
+	/* the order here really doesn't matter */
+	atomic_dec(&rto_count);
+	cpu_clear(rq->cpu, rt_overload_mask);
+}
+#endif /* CONFIG_SMP */
+
 /*
  * Update the current task's runtime statistics. Skip current tasks that
  * are not in our scheduling class.

@@ -32,6 +64,8 @@ static inline void inc_rt_tasks(struct t
 #ifdef CONFIG_SMP
 	if (p->prio < rq->rt.highest_prio)
 		rq->rt.highest_prio = p->prio;
+	if (rq->rt.rt_nr_running > 1)
+		rt_set_overload(rq);
 #endif /* CONFIG_SMP */
 }
 

@@ -53,6 +87,8 @@ static inline void dec_rt_tasks(struct t
 		} /* otherwise leave rq->highest prio alone */
 	} else
 		rq->rt.highest_prio = MAX_RT_PRIO;
+	if (rq->rt.rt_nr_running < 2)
+		rt_clear_overload(rq);
 #endif /* CONFIG_SMP */
 }
author reviewer
#5 lore raw

PATCH v4 5/20 pull RT tasks

In reply to Steven Rostedt

This patch adds the algorithm to pull tasks from RT overloaded runqueues.

When a pull RT is initiated, all overloaded runqueues are examined for a RT task that is higher in prio than the highest prio task queued on the target runqueue. If another runqueue holds a RT task that is of higher prio than the highest prio task on the target runqueue is found it is pulled to the target runqueue.

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

---

 kernel/sched.c    |    2 
 kernel/sched_rt.c |  187 ++++++++++++++++++++++++++++++++++++++++++++++++++----
 2 files changed, 178 insertions(+), 11 deletions(-)
kernel/sched.c +2 -0
Index: linux-compile.git/kernel/sched.c
===================================================================
@@ -3646,6 +3646,8 @@ need_resched_nonpreemptible:
 		switch_count = &prev->nvcsw;
 	}
 
+	schedule_balance_rt(rq, prev);
+
 	if (unlikely(!rq->nr_running))
 		idle_balance(cpu, rq);
kernel/sched_rt.c +176 -11

242 lines not on this page · raw message

author reviewer
#6 lore raw

PATCH v4 6/20 wake up balance RT

In reply to Steven Rostedt

This patch adds pushing of overloaded RT tasks from a runqueue that is having tasks (most likely RT tasks) added to the run queue.

TODO: We don't cover the case of waking of new RT tasks (yet).

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

---

 kernel/sched.c    |    3 +++
 kernel/sched_rt.c |   10 ++++++++++
 2 files changed, 13 insertions(+)
kernel/sched.c +3 -0
Index: linux-compile.git/kernel/sched.c
===================================================================
@@ -22,6 +22,8 @@
  *              by Peter Williams
  *  2007-05-06  Interactivity improvements to CFS by Mike Galbraith
  *  2007-07-01  Group scheduling enhancements by Srivatsa Vaddagiri
+ *  2007-10-22  RT overload balancing by Steven Rostedt
+ *                 (with thanks to Gregory Haskins)
  */
 
 #include <linux/mm.h>

@@ -1635,6 +1637,7 @@ out_activate:
 
 out_running:
 	p->state = TASK_RUNNING;
+	wakeup_balance_rt(rq, p);
 out:
 	task_rq_unlock(rq, &flags);
kernel/sched_rt.c +10 -0
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -555,6 +555,15 @@ static void schedule_tail_balance_rt(str
 	}
 }
 
+
+static void wakeup_balance_rt(struct rq *rq, struct task_struct *p)
+{
+	if (unlikely(rt_task(p)) &&
+	    !task_running(rq, p) &&
+	    (p->prio >= rq->curr->prio))
+		push_rt_tasks(rq);
+}
+
 /*
  * Load-balancing iterator. Note: while the runqueue stays locked
  * during the whole iteration, the current task might be

@@ -662,6 +671,7 @@ move_one_task_rt(struct rq *this_rq, int
 #else /* CONFIG_SMP */
 # define schedule_tail_balance_rt(rq)	do { } while (0)
 # define schedule_balance_rt(rq, prev)	do { } while (0)
+# define wakeup_balance_rt(rq, p)	do { } while (0)
 #endif /* CONFIG_SMP */
 
 static void task_tick_rt(struct rq *rq, struct task_struct *p)
author reviewer
#7 lore raw

PATCH v4 7/20 disable CFS RT load balancing.

In reply to Steven Rostedt

Since we now take an active approach to load balancing, we don't need to balance RT tasks via CFS. In fact, this code was found to pull RT tasks away from CPUS that the active movement performed, resulting in large latencies.

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

---

 kernel/sched_rt.c |   95 ++----------------------------------------------------
 1 file changed, 4 insertions(+), 91 deletions(-)
kernel/sched_rt.c +4 -91
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -564,109 +564,22 @@ static void wakeup_balance_rt(struct rq 
 		push_rt_tasks(rq);
 }
 
-/*
- * Load-balancing iterator. Note: while the runqueue stays locked
- * during the whole iteration, the current task might be
- * dequeued so the iterator has to be dequeue-safe. Here we
- * achieve that by always pre-iterating before returning
- * the current task:
- */
-static struct task_struct *load_balance_start_rt(void *arg)
-{
-	struct rq *rq = arg;
-	struct rt_prio_array *array = &rq->rt.active;
-	struct list_head *head, *curr;
-	struct task_struct *p;
-	int idx;
-
-	idx = sched_find_first_bit(array->bitmap);
-	if (idx >= MAX_RT_PRIO)
-		return NULL;
-
-	head = array->queue + idx;
-	curr = head->prev;
-
-	p = list_entry(curr, struct task_struct, run_list);
-
-	curr = curr->prev;
-
-	rq->rt.rt_load_balance_idx = idx;
-	rq->rt.rt_load_balance_head = head;
-	rq->rt.rt_load_balance_curr = curr;
-
-	return p;
-}
-
-static struct task_struct *load_balance_next_rt(void *arg)
-{
-	struct rq *rq = arg;
-	struct rt_prio_array *array = &rq->rt.active;
-	struct list_head *head, *curr;
-	struct task_struct *p;
-	int idx;
-
-	idx = rq->rt.rt_load_balance_idx;
-	head = rq->rt.rt_load_balance_head;
-	curr = rq->rt.rt_load_balance_curr;
-
-	/*
-	 * If we arrived back to the head again then
-	 * iterate to the next queue (if any):
-	 */
-	if (unlikely(head == curr)) {
-		int next_idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1);
-
-		if (next_idx >= MAX_RT_PRIO)
-			return NULL;
-
-		idx = next_idx;
-		head = array->queue + idx;
-		curr = head->prev;
-
-		rq->rt.rt_load_balance_idx = idx;
-		rq->rt.rt_load_balance_head = head;
-	}
-
-	p = list_entry(curr, struct task_struct, run_list);
-
-	curr = curr->prev;
-
-	rq->rt.rt_load_balance_curr = curr;
-
-	return p;
-}
-
 static unsigned long
 load_balance_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
 		unsigned long max_load_move,
 		struct sched_domain *sd, enum cpu_idle_type idle,
 		int *all_pinned, int *this_best_prio)
 {
-	struct rq_iterator rt_rq_iterator;
-
-	rt_rq_iterator.start = load_balance_start_rt;
-	rt_rq_iterator.next = load_balance_next_rt;
-	/* pass 'busiest' rq argument into
-	 * load_balance_[start|next]_rt iterators
-	 */
-	rt_rq_iterator.arg = busiest;
-
-	return balance_tasks(this_rq, this_cpu, busiest, max_load_move, sd,
-			     idle, all_pinned, this_best_prio, &rt_rq_iterator);
+	/* don't touch RT tasks */
+	return 0;
 }
 
 static int
 move_one_task_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
 		 struct sched_domain *sd, enum cpu_idle_type idle)
 {
-	struct rq_iterator rt_rq_iterator;
-
-	rt_rq_iterator.start = load_balance_start_rt;
-	rt_rq_iterator.next = load_balance_next_rt;
-	rt_rq_iterator.arg = busiest;
-
-	return iter_move_one_task(this_rq, this_cpu, busiest, sd, idle,
-				  &rt_rq_iterator);
+	/* don't touch RT tasks */
+	return 0;
 }
 #else /* CONFIG_SMP */
 # define schedule_tail_balance_rt(rq)	do { } while (0)
author reviewer
#8 lore raw

PATCH v4 8/20 Cache cpus_allowed weight for optimizing migration

In reply to Steven Rostedt

From: Gregory Haskins <[email protected]>

Some RT tasks (particularly kthreads) are bound to one specific CPU. It is fairly common for two or more bound tasks to get queued up at the same time. Consider, for instance, softirq_timer and softirq_sched. A timer goes off in an ISR which schedules softirq_thread to run at RT50. Then the timer handler determines that it's time to smp-rebalance the system so it schedules softirq_sched to run. So we are in a situation where we have two RT50 tasks queued, and the system will go into rt-overload condition to request other CPUs for help.

This causes two problems in the current code:

1) If a high-priority bound task and a low-priority unbounded task queue up behind the running task, we will fail to ever relocate the unbounded task because we terminate the search on the first unmovable task.

2) We spend precious futile cycles in the fast-path trying to pull overloaded tasks over. It is therefore optimial to strive to avoid the overhead all together if we can cheaply detect the condition before overload even occurs.

This patch tries to achieve this optimization by utilizing the hamming weight of the task->cpus_allowed mask. A weight of 1 indicates that the task cannot be migrated. We will then utilize this information to skip non-migratable tasks and to eliminate uncessary rebalance attempts.

We introduce a per-rq variable to count the number of migratable tasks that are currently running. We only go into overload if we have more than one rt task, AND at least one of them is migratable.

In addition, we introduce a per-task variable to cache the cpus_allowed weight, since the hamming calculation is probably relatively expensive. We only update the cached value when the mask is updated which should be relatively infrequent, especially compared to scheduling frequency in the fast path.

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

---

 include/linux/init_task.h |    1 
 include/linux/sched.h     |    2 +
 kernel/fork.c             |    1 
 kernel/sched.c            |    9 +++++++-
 kernel/sched_rt.c         |   50 +++++++++++++++++++++++++++++++++++++++++-----
 5 files changed, 57 insertions(+), 6 deletions(-)
include/linux/init_task.h +1 -0
Index: linux-compile.git/include/linux/init_task.h
===================================================================
@@ -130,6 +130,7 @@ extern struct group_info init_groups;
 	.normal_prio	= MAX_PRIO-20,					\
 	.policy		= SCHED_NORMAL,					\
 	.cpus_allowed	= CPU_MASK_ALL,					\
+	.nr_cpus_allowed = NR_CPUS,					\
 	.mm		= NULL,						\
 	.active_mm	= &init_mm,					\
 	.run_list	= LIST_HEAD_INIT(tsk.run_list),			\
include/linux/sched.h +2 -0
Index: linux-compile.git/include/linux/sched.h
===================================================================
@@ -843,6 +843,7 @@ struct sched_class {
 	void (*set_curr_task) (struct rq *rq);
 	void (*task_tick) (struct rq *rq, struct task_struct *p);
 	void (*task_new) (struct rq *rq, struct task_struct *p);
+	void (*set_cpus_allowed)(struct task_struct *p, cpumask_t *newmask);
 };
 
 struct load_weight {

@@ -952,6 +953,7 @@ struct task_struct {
 
 	unsigned int policy;
 	cpumask_t cpus_allowed;
+	int nr_cpus_allowed;
 	unsigned int time_slice;
 
 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
kernel/fork.c +1 -0
Index: linux-compile.git/kernel/fork.c
===================================================================
@@ -1237,6 +1237,7 @@ static struct task_struct *copy_process(
 	 * parent's CPU). This avoids alot of nasty races.
 	 */
 	p->cpus_allowed = current->cpus_allowed;
+	p->nr_cpus_allowed = current->nr_cpus_allowed;
 	if (unlikely(!cpu_isset(task_cpu(p), p->cpus_allowed) ||
 			!cpu_online(task_cpu(p))))
 		set_task_cpu(p, smp_processor_id());
kernel/sched.c +8 -1
Index: linux-compile.git/kernel/sched.c
===================================================================
@@ -269,6 +269,7 @@ struct rt_rq {
 	int rt_load_balance_idx;
 	struct list_head *rt_load_balance_head, *rt_load_balance_curr;
 	unsigned long rt_nr_running;
+	unsigned long rt_nr_migratory;
 	/* highest queued rt task prio */
 	int highest_prio;
 };

@@ -5070,7 +5071,13 @@ int set_cpus_allowed(struct task_struct 
 		goto out;
 	}
 
-	p->cpus_allowed = new_mask;
+	if (p->sched_class->set_cpus_allowed)
+		p->sched_class->set_cpus_allowed(p, &new_mask);
+	else {
+		p->cpus_allowed    = new_mask;
+		p->nr_cpus_allowed = cpus_weight(new_mask);
+	}
+
 	/* Can the task run on the task's current CPU? If so, we're done */
 	if (cpu_isset(task_cpu(p), new_mask))
 		goto out;
kernel/sched_rt.c +45 -5

86 lines not on this page · raw message

author reviewer
#9 lore raw

PATCH v4 9/20 RT: Consistency cleanup for this_rq usage

In reply to Steven Rostedt

From: Gregory Haskins <[email protected]>

"this_rq" is normally used to denote the RQ on the current cpu (i.e. "cpu_rq(this_cpu)"). So clean up the usage of this_rq to be more consistent with the rest of the code.

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

---

 kernel/sched_rt.c |   22 +++++++++++-----------
 1 file changed, 11 insertions(+), 11 deletions(-)
kernel/sched_rt.c +11 -11
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -325,21 +325,21 @@ static struct rq *find_lock_lowest_rq(st
  * running task can migrate over to a CPU that is running a task
  * of lesser priority.
  */
-static int push_rt_task(struct rq *this_rq)
+static int push_rt_task(struct rq *rq)
 {
 	struct task_struct *next_task;
 	struct rq *lowest_rq;
 	int ret = 0;
 	int paranoid = RT_MAX_TRIES;
 
-	assert_spin_locked(&this_rq->lock);
+	assert_spin_locked(&rq->lock);
 
-	next_task = pick_next_highest_task_rt(this_rq, -1);
+	next_task = pick_next_highest_task_rt(rq, -1);
 	if (!next_task)
 		return 0;
 
  retry:
-	if (unlikely(next_task == this_rq->curr)) {
+	if (unlikely(next_task == rq->curr)) {
 		WARN_ON(1);
 		return 0;
 	}

@@ -349,24 +349,24 @@ static int push_rt_task(struct rq *this_
 	 * higher priority than current. If that's the case
 	 * just reschedule current.
 	 */
-	if (unlikely(next_task->prio < this_rq->curr->prio)) {
-		resched_task(this_rq->curr);
+	if (unlikely(next_task->prio < rq->curr->prio)) {
+		resched_task(rq->curr);
 		return 0;
 	}
 
-	/* We might release this_rq lock */
+	/* We might release rq lock */
 	get_task_struct(next_task);
 
 	/* find_lock_lowest_rq locks the rq if found */
-	lowest_rq = find_lock_lowest_rq(next_task, this_rq);
+	lowest_rq = find_lock_lowest_rq(next_task, rq);
 	if (!lowest_rq) {
 		struct task_struct *task;
 		/*
-		 * find lock_lowest_rq releases this_rq->lock
+		 * find lock_lowest_rq releases rq->lock
 		 * so it is possible that next_task has changed.
 		 * If it has, then try again.
 		 */
-		task = pick_next_highest_task_rt(this_rq, -1);
+		task = pick_next_highest_task_rt(rq, -1);
 		if (unlikely(task != next_task) && task && paranoid--) {
 			put_task_struct(next_task);
 			next_task = task;

@@ -377,7 +377,7 @@ static int push_rt_task(struct rq *this_
 
 	assert_spin_locked(&lowest_rq->lock);
 
-	deactivate_task(this_rq, next_task, 0);
+	deactivate_task(rq, next_task, 0);
 	set_task_cpu(next_task, lowest_rq->cpu);
 	activate_task(lowest_rq, next_task, 0);
author reviewer
#10 lore raw

PATCH v4 10/20 RT: Remove some CFS specific code from the wakeup path of RT tasks

In reply to Steven Rostedt

From: Gregory Haskins <[email protected]>

The current wake-up code path tries to determine if it can optimize the wake-up to "this_cpu" by computing load calculations. The problem is that these calculations are only relevant to CFS tasks where load is king. For RT tasks, priority is king. So the load calculation is completely wasted bandwidth.

Therefore, we create a new sched_class interface to help with pre-wakeup routing decisions and move the load calculation as a function of CFS task's class.

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

---

 include/linux/sched.h   |    1 
 kernel/sched.c          |  167 +++++++-----------------------------------------
 kernel/sched_fair.c     |  148 ++++++++++++++++++++++++++++++++++++++++++
 kernel/sched_idletask.c |    9 ++
 kernel/sched_rt.c       |   10 ++
 5 files changed, 195 insertions(+), 140 deletions(-)
include/linux/sched.h +1 -0
Index: linux-compile.git/include/linux/sched.h
===================================================================
@@ -823,6 +823,7 @@ struct sched_class {
 	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
 	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
 	void (*yield_task) (struct rq *rq);
+	int  (*select_task_rq)(struct task_struct *p, int sync);
 
 	void (*check_preempt_curr) (struct rq *rq, struct task_struct *p);
kernel/sched.c +27 -140

209 lines not on this page · raw message

kernel/sched_fair.c +148 -0

160 lines not on this page · raw message

kernel/sched_idletask.c +9 -0
Index: linux-compile.git/kernel/sched_idletask.c
===================================================================
@@ -5,6 +5,12 @@
  *  handled in sched_fair.c)
  */
 
+#ifdef CONFIG_SMP
+static int select_task_rq_idle(struct task_struct *p, int sync)
+{
+	return task_cpu(p); /* IDLE tasks as never migrated */
+}
+#endif /* CONFIG_SMP */
 /*
  * Idle tasks are unconditionally rescheduled:
  */

@@ -72,6 +78,9 @@ const struct sched_class idle_sched_clas
 
 	/* dequeue is not valid, we print a debug message there: */
 	.dequeue_task		= dequeue_task_idle,
+#ifdef CONFIG_SMP
+	.select_task_rq		= select_task_rq_idle,
+#endif /* CONFIG_SMP */
 
 	.check_preempt_curr	= check_preempt_curr_idle,
kernel/sched_rt.c +10 -0
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -147,6 +147,13 @@ yield_task_rt(struct rq *rq)
 	requeue_task_rt(rq, rq->curr);
 }
 
+#ifdef CONFIG_SMP
+static int select_task_rq_rt(struct task_struct *p, int sync)
+{
+	return task_cpu(p);
+}
+#endif /* CONFIG_SMP */
+
 /*
  * Preempt the current task with a newly woken task if needed:
  */

@@ -662,6 +669,9 @@ const struct sched_class rt_sched_class 
 	.enqueue_task		= enqueue_task_rt,
 	.dequeue_task		= dequeue_task_rt,
 	.yield_task		= yield_task_rt,
+#ifdef CONFIG_SMP
+	.select_task_rq		= select_task_rq_rt,
+#endif /* CONFIG_SMP */
 
 	.check_preempt_curr	= check_preempt_curr_rt,
author reviewer
#11 lore raw

PATCH v4 11/20 RT: Break out the search function

In reply to Steven Rostedt

From: Gregory Haskins <[email protected]>

Isolate the search logic into a function so that it can be used later in places other than find_locked_lowest_rq().

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

---

 kernel/sched_rt.c |   66 +++++++++++++++++++++++++++++++-----------------------
 1 file changed, 39 insertions(+), 27 deletions(-)
kernel/sched_rt.c +39 -27
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -260,54 +260,66 @@ static struct task_struct *pick_next_hig
 
 static DEFINE_PER_CPU(cpumask_t, local_cpu_mask);
 
-/* Will lock the rq it finds */
-static struct rq *find_lock_lowest_rq(struct task_struct *task,
-				      struct rq *this_rq)
+static int find_lowest_rq(struct task_struct *task)
 {
-	struct rq *lowest_rq = NULL;
 	int cpu;
-	int tries;
 	cpumask_t *cpu_mask = &__get_cpu_var(local_cpu_mask);
+	struct rq *lowest_rq = NULL;
 
 	cpus_and(*cpu_mask, cpu_online_map, task->cpus_allowed);
 
-	for (tries = 0; tries < RT_MAX_TRIES; tries++) {
-		/*
-		 * Scan each rq for the lowest prio.
-		 */
-		for_each_cpu_mask(cpu, *cpu_mask) {
-			struct rq *rq = &per_cpu(runqueues, cpu);
+	/*
+	 * Scan each rq for the lowest prio.
+	 */
+	for_each_cpu_mask(cpu, *cpu_mask) {
+		struct rq *rq = cpu_rq(cpu);
 
-			if (cpu == this_rq->cpu)
-				continue;
+		if (cpu == rq->cpu)
+			continue;
 
-			/* We look for lowest RT prio or non-rt CPU */
-			if (rq->rt.highest_prio >= MAX_RT_PRIO) {
-				lowest_rq = rq;
-				break;
-			}
+		/* We look for lowest RT prio or non-rt CPU */
+		if (rq->rt.highest_prio >= MAX_RT_PRIO) {
+			lowest_rq = rq;
+			break;
+		}
 
-			/* no locking for now */
-			if (rq->rt.highest_prio > task->prio &&
-			    (!lowest_rq || rq->rt.highest_prio > lowest_rq->rt.highest_prio)) {
-				lowest_rq = rq;
-			}
+		/* no locking for now */
+		if (rq->rt.highest_prio > task->prio &&
+		    (!lowest_rq || rq->rt.highest_prio > lowest_rq->rt.highest_prio)) {
+			lowest_rq = rq;
 		}
+	}
+
+	return lowest_rq ? lowest_rq->cpu : -1;
+}
+
+/* Will lock the rq it finds */
+static struct rq *find_lock_lowest_rq(struct task_struct *task,
+				      struct rq *rq)
+{
+	struct rq *lowest_rq = NULL;
+	int cpu;
+	int tries;
 
-		if (!lowest_rq)
+	for (tries = 0; tries < RT_MAX_TRIES; tries++) {
+		cpu = find_lowest_rq(task);
+
+		if (cpu == -1)
 			break;
 
+		lowest_rq = cpu_rq(cpu);
+
 		/* if the prio of this runqueue changed, try again */
-		if (double_lock_balance(this_rq, lowest_rq)) {
+		if (double_lock_balance(rq, lowest_rq)) {
 			/*
 			 * We had to unlock the run queue. In
 			 * the mean time, task could have
 			 * migrated already or had its affinity changed.
 			 * Also make sure that it wasn't scheduled on its rq.
 			 */
-			if (unlikely(task_rq(task) != this_rq ||
+			if (unlikely(task_rq(task) != rq ||
 				     !cpu_isset(lowest_rq->cpu, task->cpus_allowed) ||
-				     task_running(this_rq, task) ||
+				     task_running(rq, task) ||
 				     !task->se.on_rq)) {
 				spin_unlock(&lowest_rq->lock);
 				lowest_rq = NULL;
author reviewer
#12 lore raw

PATCH v4 12/20 RT: Allow current_cpu to be included in search

In reply to Steven Rostedt

From: Gregory Haskins <[email protected]>

It doesn't hurt if we allow the current CPU to be included in the search. We will just simply skip it later if the current CPU turns out to be the lowest.

We will use this later in the series

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

---

 kernel/sched_rt.c |    5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)
kernel/sched_rt.c +1 -4
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -274,9 +274,6 @@ static int find_lowest_rq(struct task_st
 	for_each_cpu_mask(cpu, *cpu_mask) {
 		struct rq *rq = cpu_rq(cpu);
 
-		if (cpu == rq->cpu)
-			continue;
-
 		/* We look for lowest RT prio or non-rt CPU */
 		if (rq->rt.highest_prio >= MAX_RT_PRIO) {
 			lowest_rq = rq;

@@ -304,7 +301,7 @@ static struct rq *find_lock_lowest_rq(st
 	for (tries = 0; tries < RT_MAX_TRIES; tries++) {
 		cpu = find_lowest_rq(task);
 
-		if (cpu == -1)
+		if ((cpu == -1) || (cpu == rq->cpu))
 			break;
 
 		lowest_rq = cpu_rq(cpu);
author reviewer
#13 lore raw

PATCH v4 13/20 RT: Pre-route RT tasks on wakeup

In reply to Steven Rostedt

From: Gregory Haskins <[email protected]>

In the original patch series that Steven Rostedt and I worked on together, we both took different approaches to low-priority wakeup path. I utilized "pre-routing" (push the task away to a less important RQ before activating) approach, while Steve utilized a "post-routing" approach. The advantage of my approach is that you avoid the overhead of a wasted activate/deactivate cycle and peripherally related burdens. The advantage of Steve's method is that it neatly solves an issue preventing a "pull" optimization from being deployed.

In the end, we ended up deploying Steve's idea. But it later dawned on me that we could get the best of both worlds by deploying both ideas together, albeit slightly modified.

The idea is simple: Use a "light-weight" lookup for pre-routing, since we only need to approximate a good home for the task. And we also retain the post-routing push logic to clean up any inaccuracies caused by a condition of "priority mistargeting" caused by the lightweight lookup. Most of the time, the pre-routing should work and yield lower overhead. In the cases where it doesnt, the post-router will bat cleanup.

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

---

 kernel/sched_rt.c |   19 +++++++++++++++++++
 1 file changed, 19 insertions(+)
kernel/sched_rt.c +19 -0
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -148,8 +148,27 @@ yield_task_rt(struct rq *rq)
 }
 
 #ifdef CONFIG_SMP
+static int find_lowest_rq(struct task_struct *task);
+
 static int select_task_rq_rt(struct task_struct *p, int sync)
 {
+	struct rq *rq = task_rq(p);
+
+	/*
+	 * If the task will not preempt the RQ, try to find a better RQ
+	 * before we even activate the task
+	 */
+	if ((p->prio >= rq->rt.highest_prio)
+	    && (p->nr_cpus_allowed > 1)) {
+		int cpu = find_lowest_rq(p);
+
+		return (cpu == -1) ? task_cpu(p) : cpu;
+	}
+
+	/*
+	 * Otherwise, just let it ride on the affined RQ and the
+	 * post-schedule router will push the preempted task away
+	 */
 	return task_cpu(p);
 }
 #endif /* CONFIG_SMP */
author reviewer
#14 lore raw

PATCH v4 14/20 RT: Optimize our cpu selection based on topology

In reply to Steven Rostedt

From: Gregory Haskins <[email protected]>

The current code base assumes a relatively flat CPU/core topology and will route RT tasks to any CPU fairly equally. In the real world, there are various toplogies and affinities that govern where a task is best suited to run with the smallest amount of overhead. NUMA and multi-core CPUs are prime examples of topologies that can impact cache performance.

Fortunately, linux is already structured to represent these topologies via the sched_domains interface. So we change our RT router to consult a combination of topology and affinity policy to best place tasks during migration.

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

---

 kernel/sched.c    |    1 
 kernel/sched_rt.c |  100 +++++++++++++++++++++++++++++++++++++++++++++++-------
 2 files changed, 89 insertions(+), 12 deletions(-)
kernel/sched.c +1 -0
Index: linux-compile.git/kernel/sched.c
===================================================================
@@ -24,6 +24,7 @@
  *  2007-07-01  Group scheduling enhancements by Srivatsa Vaddagiri
  *  2007-10-22  RT overload balancing by Steven Rostedt
  *                 (with thanks to Gregory Haskins)
+ *  2007-11-05  RT migration/wakeup tuning by Gregory Haskins
  */
 
 #include <linux/mm.h>
kernel/sched_rt.c +88 -12

123 lines not on this page · raw message

author reviewer
#15 lore raw

PATCH v4 15/20 RT: Optimize rebalancing

In reply to Steven Rostedt

From: Gregory Haskins <[email protected]>

We have logic to detect whether the system has migratable tasks, but we are not using it when deciding whether to push tasks away. So we add support for considering this new information.

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

---

 kernel/sched.c    |    2 ++
 kernel/sched_rt.c |   10 ++++++++--
 2 files changed, 10 insertions(+), 2 deletions(-)
kernel/sched.c +2 -0
Index: linux-compile.git/kernel/sched.c
===================================================================
@@ -273,6 +273,7 @@ struct rt_rq {
 	unsigned long rt_nr_migratory;
 	/* highest queued rt task prio */
 	int highest_prio;
+	int overloaded;
 };
 
 /*

@@ -6685,6 +6686,7 @@ void __init sched_init(void)
 		rq->migration_thread = NULL;
 		INIT_LIST_HEAD(&rq->migration_queue);
 		rq->rt.highest_prio = MAX_RT_PRIO;
+		rq->rt.overloaded = 0;
 #endif
 		atomic_set(&rq->nr_iowait, 0);
kernel/sched_rt.c +8 -2
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -16,6 +16,7 @@ static inline cpumask_t *rt_overload(voi
 }
 static inline void rt_set_overload(struct rq *rq)
 {
+	rq->rt.overloaded = 1;
 	cpu_set(rq->cpu, rt_overload_mask);
 	/*
 	 * Make sure the mask is visible before we set

@@ -32,6 +33,7 @@ static inline void rt_clear_overload(str
 	/* the order here really doesn't matter */
 	atomic_dec(&rto_count);
 	cpu_clear(rq->cpu, rt_overload_mask);
+	rq->rt.overloaded = 0;
 }
 
 static void update_rt_migration(struct rq *rq)

@@ -445,6 +447,9 @@ static int push_rt_task(struct rq *rq)
 
 	assert_spin_locked(&rq->lock);
 
+	if (!rq->rt.overloaded)
+		return 0;
+
 	next_task = pick_next_highest_task_rt(rq, -1);
 	if (!next_task)
 		return 0;

@@ -672,7 +677,7 @@ static void schedule_tail_balance_rt(str
 	 * the lock was owned by prev, we need to release it
 	 * first via finish_lock_switch and then reaquire it here.
 	 */
-	if (unlikely(rq->rt.rt_nr_running > 1)) {
+	if (unlikely(rq->rt.overloaded)) {
 		spin_lock_irq(&rq->lock);
 		push_rt_tasks(rq);
 		spin_unlock_irq(&rq->lock);

@@ -684,7 +689,8 @@ static void wakeup_balance_rt(struct rq 
 {
 	if (unlikely(rt_task(p)) &&
 	    !task_running(rq, p) &&
-	    (p->prio >= rq->curr->prio))
+	    (p->prio >= rq->rt.highest_prio) &&
+	    rq->rt.overloaded)
 		push_rt_tasks(rq);
 }
author reviewer
#16 lore raw

PATCH v4 16/20 Avoid overload

In reply to Steven Rostedt

This patch changes the searching for a run queue by a waking RT task to try to pick another runqueue if the currently running task is an RT task.

The reason is that RT tasks behave different than normal tasks. Preempting a normal task to run a RT task to keep its cache hot is fine, because the preempted non-RT task may wait on that same runqueue to run again unless the migration thread comes along and pulls it off.

RT tasks behave differently. If one is preempted, it makes an active effort to continue to run. So by having a high priority task preempt a lower priority RT task, that lower RT task will then quickly try to run on another runqueue. This will cause that lower RT task to replace its nice hot cache (and TLB) with a completely cold one. This is for the hope that the new high priority RT task will keep
its cache hot.

Remeber that this high priority RT task was just woken up. So it may likely have been sleeping for several milliseconds, and will end up with a cold cache anyway. RT tasks run till they voluntarily stop, or are preempted by a higher priority task. This means that it is unlikely that the woken RT task will have a hot cache to wake up to. So pushing off a lower RT task is just killing its cache for no good reason.

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

---

 kernel/sched_rt.c |   20 ++++++++++++++++----
 1 file changed, 16 insertions(+), 4 deletions(-)
kernel/sched_rt.c +16 -4
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -157,11 +157,23 @@ static int select_task_rq_rt(struct task
 	struct rq *rq = task_rq(p);
 
 	/*
-	 * If the task will not preempt the RQ, try to find a better RQ
-	 * before we even activate the task
+	 * If the current task is an RT task, then
+	 * try to see if we can wake this RT task up on another
+	 * runqueue. Otherwise simply start this RT task
+	 * on its current runqueue.
+	 *
+	 * We want to avoid overloading runqueues. Even if
+	 * the RT task is of higher priority than the current RT task.
+	 * RT tasks behave differently than other tasks. If
+	 * one gets preempted, we try to push it off to another queue.
+	 * So trying to keep a preempting RT task on the same
+	 * cache hot CPU will force the running RT task to
+	 * a cold CPU. So we waste all the cache for the lower
+	 * RT task in hopes of saving some of a RT task
+	 * that is just being woken and probably will have
+	 * cold cache anyway.
 	 */
-	if ((p->prio >= rq->rt.highest_prio)
-	    && (p->nr_cpus_allowed > 1)) {
+	if (unlikely(rt_task(rq->curr))) {
 		int cpu = find_lowest_rq(p);
 
 		return (cpu == -1) ? task_cpu(p) : cpu;
author reviewer
#17 lore raw

PATCH v4 17/20 RT: restore the migratable conditional

In reply to Steven Rostedt

From: Gregory Haskins <[email protected]>

We don't need to bother searching if the task cannot be migrated

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

---

 kernel/sched_rt.c |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
kernel/sched_rt.c +2 -1
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -173,7 +173,8 @@ static int select_task_rq_rt(struct task
 	 * that is just being woken and probably will have
 	 * cold cache anyway.
 	 */
-	if (unlikely(rt_task(rq->curr))) {
+	if (unlikely(rt_task(rq->curr)) &&
+	    (p->nr_cpus_allowed > 1)) {
 		int cpu = find_lowest_rq(p);
 
 		return (cpu == -1) ? task_cpu(p) : cpu;
author reviewer
#18 lore raw

PATCH v4 18/20 Optimize cpu search with hamming weight

In reply to Steven Rostedt

From: Gregory Haskins <[email protected]>

We can cheaply track the number of bits set in the cpumask for the lowest priority CPUs. Therefore, compute the mask's weight and use it to skip the optimal domain search logic when there is only one CPU available.

Signed-off-by Gregory Haskins <[email protected]>

---

 kernel/sched_rt.c |   25 ++++++++++++++++++-------
 1 file changed, 18 insertions(+), 7 deletions(-)
kernel/sched_rt.c +18 -7
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -300,7 +300,7 @@ static int find_lowest_cpus(struct task_
 	int       cpu;
 	cpumask_t *valid_mask = &__get_cpu_var(valid_cpu_mask);
 	int       lowest_prio = -1;
-	int       ret         = 0;
+	int       count       = 0;
 
 	cpus_clear(*lowest_mask);
 	cpus_and(*valid_mask, cpu_online_map, task->cpus_allowed);

@@ -313,7 +313,7 @@ static int find_lowest_cpus(struct task_
 
 		/* We look for lowest RT prio or non-rt CPU */
 		if (rq->rt.highest_prio >= MAX_RT_PRIO) {
-			if (ret)
+			if (count)
 				cpus_clear(*lowest_mask);
 			cpu_set(rq->cpu, *lowest_mask);
 			return 1;

@@ -325,14 +325,17 @@ static int find_lowest_cpus(struct task_
 			if (rq->rt.highest_prio > lowest_prio) {
 				/* new low - clear old data */
 				lowest_prio = rq->rt.highest_prio;
-				cpus_clear(*lowest_mask);
+				if (count) {
+					cpus_clear(*lowest_mask);
+					count = 0;
+				}
 			}
 			cpu_set(rq->cpu, *lowest_mask);
-			ret = 1;
+			count++;
 		}
 	}
 
-	return ret;
+	return count;
 }
 
 static inline int pick_optimal_cpu(int this_cpu, cpumask_t *mask)

@@ -356,9 +359,17 @@ static int find_lowest_rq(struct task_st
 	cpumask_t *lowest_mask = &__get_cpu_var(local_cpu_mask);
 	int this_cpu = smp_processor_id();
 	int cpu      = task_cpu(task);
+	int count    = find_lowest_cpus(task, lowest_mask);
 
-	if (!find_lowest_cpus(task, lowest_mask))
-		return -1;
+	if (!count)
+		return -1; /* No targets found */
+
+	/*
+	 * There is no sense in performing an optimal search if only one
+	 * target is found.
+	 */
+	if (count == 1)
+		return first_cpu(*lowest_mask);
 
 	/*
 	 * At this point we have built a mask of cpus representing the
author reviewer
#19 lore raw

PATCH v4 19/20 Optimize out cpu_clears

In reply to Steven Rostedt

This patch removes several cpumask operations by keeping track of the first of the CPUS that is of the lowest priority. When the search for the lowest priority runqueue is completed, all the bits up to the first CPU with the lowest priority runqueue is cleared.

Signed-off-by Steven Rostedt <[email protected]>
---
 kernel/sched_rt.c |   35 +++++++++++++++++++++++++----------
 1 file changed, 25 insertions(+), 10 deletions(-)
kernel/sched_rt.c +25 -10
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -293,22 +293,20 @@ static struct task_struct *pick_next_hig
 }
 
 static DEFINE_PER_CPU(cpumask_t, local_cpu_mask);
-static DEFINE_PER_CPU(cpumask_t, valid_cpu_mask);
 
 static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 {
-	int       cpu;
-	cpumask_t *valid_mask = &__get_cpu_var(valid_cpu_mask);
 	int       lowest_prio = -1;
+	int       lowest_cpu  = 0;
 	int       count       = 0;
+	int       cpu;
 
-	cpus_clear(*lowest_mask);
-	cpus_and(*valid_mask, cpu_online_map, task->cpus_allowed);
+	cpus_and(*lowest_mask, cpu_online_map, task->cpus_allowed);
 
 	/*
 	 * Scan each rq for the lowest prio.
 	 */
-	for_each_cpu_mask(cpu, *valid_mask) {
+	for_each_cpu_mask(cpu, *lowest_mask) {
 		struct rq *rq = cpu_rq(cpu);
 
 		/* We look for lowest RT prio or non-rt CPU */

@@ -325,13 +323,30 @@ static int find_lowest_cpus(struct task_
 			if (rq->rt.highest_prio > lowest_prio) {
 				/* new low - clear old data */
 				lowest_prio = rq->rt.highest_prio;
-				if (count) {
-					cpus_clear(*lowest_mask);
-					count = 0;
-				}
+				lowest_cpu = cpu;
+				count = 0;
 			}
 			cpu_set(rq->cpu, *lowest_mask);
 			count++;
+		} else
+			cpu_clear(cpu, *lowest_mask);
+	}
+
+	/*
+	 * Clear out all the set bits that represent
+	 * runqueues that were of higher prio than
+	 * the lowest_prio.
+	 */
+	if (lowest_cpu) {
+		/*
+		 * Perhaps we could add another cpumask op to
+		 * zero out bits. Like cpu_zero_bits(cpumask, nrbits);
+		 * Then that could be optimized to use memset and such.
+		 */
+		for_each_cpu_mask(cpu, *lowest_mask) {
+			if (cpu >= lowest_cpu)
+				break;
+			cpu_clear(cpu, *lowest_mask);
 		}
 	}
author reviewer
#20 lore raw

Re: [PATCH v4 19/20] Optimize out cpu_clears

Quoted 26 lines · Steven Rostedt

static DEFINE_PER_CPU(cpumask_t, local_cpu_mask);

(quoted diff) +4 -6
-static DEFINE_PER_CPU(cpumask_t, valid_cpu_mask);
 
 static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 {
-	int       cpu;
-	cpumask_t *valid_mask = &__get_cpu_var(valid_cpu_mask);
 	int       lowest_prio = -1;
+	int       lowest_cpu  = 0;
 	int       count       = 0;
+	int       cpu;
 
-	cpus_clear(*lowest_mask);
-	cpus_and(*valid_mask, cpu_online_map, task->cpus_allowed);
+	cpus_and(*lowest_mask, cpu_online_map, task->cpus_allowed);
 
 	/*
 	 * Scan each rq for the lowest prio.
 	 */
-	for_each_cpu_mask(cpu, *valid_mask) {
+	for_each_cpu_mask(cpu, *lowest_mask) {
 		struct rq *rq = cpu_rq(cpu);
 
 		/* We look for lowest RT prio or non-rt CPU */

Review static int find_lowest_cpus(struct task_ · line 331

Quoted 7 lines
(quoted diff) +0 -4
@@ -325,13 +323,30 @@ static int find_lowest_cpus(struct task_
 			if (rq->rt.highest_prio > lowest_prio) {
 				/* new low - clear old data */
 				lowest_prio = rq->rt.highest_prio;
-				if (count) {
-					cpus_clear(*lowest_mask);
-					count = 0;
-				}

Gregory Haskins pointed out to me that this logic is slightly wrong. I originally wrote this patch before adding his "count" patch optimization. I did not take into account that on finding a non RT queue, we may leave on some extra bits because the clear_cpus is not preformed if count is zero. And count gets set to zero here. Which means that we don't clean up.

The fix is to check for lowest_cpus > 0 instead of count on finding an non-RT runqueue. This lets us know that we need to clear the mask. Otherwise, if lowest_cpus == 0, then we can return the mask untouched. The proper bit would already be set, and the return of 1 will have the rest of the algorithm use the first bit.

Below is the updated patch. The full series is at:

http://rostedt.homelinux.com/rt/rt-balance-patches-v5.tar.bz2

Review static int find_lowest_cpus(struct task_ · line 330

Quoted 5 lines
(quoted diff) +2 -0
+				lowest_cpu = cpu;
+				count = 0;
 			}
 			cpu_set(rq->cpu, *lowest_mask);
 			count++;

From: Steven Rostedt <[email protected]>

This patch removes several cpumask operations by keeping track of the first of the CPUS that is of the lowest priority. When the search for the lowest priority runqueue is completed, all the bits up to the first CPU with the lowest priority runqueue is cleared.

Signed-off-by Steven Rostedt <[email protected]>
---
 kernel/sched_rt.c |   48 ++++++++++++++++++++++++++++++++++++------------
 1 file changed, 36 insertions(+), 12 deletions(-)
kernel/sched_rt.c +36 -12
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -293,29 +293,36 @@ static struct task_struct *pick_next_hig
 }
 
 static DEFINE_PER_CPU(cpumask_t, local_cpu_mask);
-static DEFINE_PER_CPU(cpumask_t, valid_cpu_mask);
 
 static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 {
-	int       cpu;
-	cpumask_t *valid_mask = &__get_cpu_var(valid_cpu_mask);
 	int       lowest_prio = -1;
+	int       lowest_cpu  = 0;
 	int       count       = 0;
+	int       cpu;
 
-	cpus_clear(*lowest_mask);
-	cpus_and(*valid_mask, cpu_online_map, task->cpus_allowed);
+	cpus_and(*lowest_mask, cpu_online_map, task->cpus_allowed);
 
 	/*
 	 * Scan each rq for the lowest prio.
 	 */
-	for_each_cpu_mask(cpu, *valid_mask) {
+	for_each_cpu_mask(cpu, *lowest_mask) {
 		struct rq *rq = cpu_rq(cpu);
 
 		/* We look for lowest RT prio or non-rt CPU */
 		if (rq->rt.highest_prio >= MAX_RT_PRIO) {
-			if (count)
+			/*
+			 * if we already found a low RT queue
+			 * and now we found this non-rt queue
+			 * clear the mask and set our bit.
+			 * Otherwise just return the queue as is
+			 * and the count==1 will cause the algorithm
+			 * to use the first bit found.
+			 */
+			if (lowest_cpu) {
 				cpus_clear(*lowest_mask);
-			cpu_set(rq->cpu, *lowest_mask);
+				cpu_set(rq->cpu, *lowest_mask);
+			}
 			return 1;
 		}
 

@@ -325,13 +332,30 @@ static int find_lowest_cpus(struct task_
 			if (rq->rt.highest_prio > lowest_prio) {
 				/* new low - clear old data */
 				lowest_prio = rq->rt.highest_prio;
-				if (count) {
-					cpus_clear(*lowest_mask);
-					count = 0;
-				}
+				lowest_cpu = cpu;
+				count = 0;
 			}
 			cpu_set(rq->cpu, *lowest_mask);
 			count++;
+		} else
+			cpu_clear(cpu, *lowest_mask);
+	}
+
+	/*
+	 * Clear out all the set bits that represent
+	 * runqueues that were of higher prio than
+	 * the lowest_prio.
+	 */
+	if (lowest_cpu) {
+		/*
+		 * Perhaps we could add another cpumask op to
+		 * zero out bits. Like cpu_zero_bits(cpumask, nrbits);
+		 * Then that could be optimized to use memset and such.
+		 */
+		for_each_cpu_mask(cpu, *lowest_mask) {
+			if (cpu >= lowest_cpu)
+				break;
+			cpu_clear(cpu, *lowest_mask);
 		}
 	}
#21 lore raw

PATCH 1/1 Fix optimized search

I spied a few more issues from http://lkml.org/lkml/2007/11/20/590.

Patch is below..

Regards,
-Greg

-----------------

Include cpu 0 in the search, and eliminate the redundant cpu_set since the bit should already be set in the mask.

Signed-off-by Gregory Haskins <[email protected]>

---

 kernel/sched_rt.c |    7 +++----
 1 files changed, 3 insertions(+), 4 deletions(-)
kernel/sched_rt.c +3 -4
index 28feeff..fbf4fb1 100644
@@ -297,7 +297,7 @@ static DEFINE_PER_CPU(cpumask_t, local_cpu_mask);
 static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 {
 	int       lowest_prio = -1;
-	int       lowest_cpu  = 0;
+	int       lowest_cpu  = -1;
 	int       count       = 0;
 	int       cpu;
 

@@ -319,7 +319,7 @@ static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 			 * and the count==1 will cause the algorithm
 			 * to use the first bit found.
 			 */
-			if (lowest_cpu) {
+			if (lowest_cpu != -1) {
 				cpus_clear(*lowest_mask);
 				cpu_set(rq->cpu, *lowest_mask);
 			}

@@ -335,7 +335,6 @@ static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 				lowest_cpu = cpu;
 				count = 0;
 			}
-			cpu_set(rq->cpu, *lowest_mask);
 			count++;
 		} else
 			cpu_clear(cpu, *lowest_mask);

@@ -346,7 +345,7 @@ static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 	 * runqueues that were of higher prio than
 	 * the lowest_prio.
 	 */
-	if (lowest_cpu) {
+	if (lowest_cpu != -1) {
 		/*
 		 * Perhaps we could add another cpumask op to
 		 * zero out bits. Like cpu_zero_bits(cpumask, nrbits);
#22 lore raw

Re: [PATCH] Fix optimized search

Quoted 3 lines · Gregory Haskins

I spied a few more issues from http://lkml.org/lkml/2007/11/20/590.

Patch is below..

Thanks, but I have one update...

Quoted 46 lines

Regards,
-Greg

-----------------

Include cpu 0 in the search, and eliminate the redundant cpu_set since the bit should already be set in the mask.

Signed-off-by Gregory Haskins <[email protected]>

---

 kernel/sched_rt.c |    7 +++----
 1 files changed, 3 insertions(+), 4 deletions(-)
kernel/sched_rt.c +2 -3
index 28feeff..fbf4fb1 100644
@@ -297,7 +297,7 @@ static DEFINE_PER_CPU(cpumask_t, local_cpu_mask);
 static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 {
 	int       lowest_prio = -1;
-	int       lowest_cpu  = 0;
+	int       lowest_cpu  = -1;
 	int       count       = 0;
 	int       cpu;
 

@@ -319,7 +319,7 @@ static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 			 * and the count==1 will cause the algorithm
 			 * to use the first bit found.
 			 */
-			if (lowest_cpu) {
+			if (lowest_cpu != -1) {
 				cpus_clear(*lowest_mask);
 				cpu_set(rq->cpu, *lowest_mask);
 			}

@@ -335,7 +335,6 @@ static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 				lowest_cpu = cpu;
 				count = 0;
 			}
-			cpu_set(rq->cpu, *lowest_mask);
 			count++;
 		} else
 			cpu_clear(cpu, *lowest_mask);

kernel/sched_rt.c static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask) · line 348

Quoted 5 lines
kernel/sched_rt.c +1 -1
@@ -346,7 +345,7 @@ static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 	 * runqueues that were of higher prio than
 	 * the lowest_prio.
 	 */
-	if (lowest_cpu) {
+	if (lowest_cpu != -1) {

We can change this to

  if (lowest_cpu > 0) {

because if lowest_cpu == 0, we don't need to bother with clearing any bits.

I'll apply this next.

Thanks.

-- Steve

Quoted 4 lines
kernel/sched_rt.c +0 -0
 		/*
 		 * Perhaps we could add another cpumask op to
 		 * zero out bits. Like cpu_zero_bits(cpumask, nrbits);
author reviewer
#23 lore raw

Re: [PATCH] Fix optimized search

Quoted 6 lines · Steven Rostedt
Quoted 2 lines · Gregory Haskins

I spied a few more issues from http://lkml.org/lkml/2007/11/20/590.
Patch is below..

Thanks, but I have one update...

Here's the updated patch.

Oh, and Gregory, please email me at my [email protected] account. It has better filters ;-)

This series is at:

http://rostedt.homelinux.com/rt/rt-balance-patches-v6.tar.bz2

===

This patch removes several cpumask operations by keeping track of the first of the CPUS that is of the lowest priority. When the search for the lowest priority runqueue is completed, all the bits up to the first CPU with the lowest priority runqueue is cleared.

Signed-off-by Steven Rostedt <[email protected]>
---
 kernel/sched_rt.c |   49 ++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 36 insertions(+), 13 deletions(-)
kernel/sched_rt.c +36 -13
Index: linux-compile.git/kernel/sched_rt.c
===================================================================
@@ -293,29 +293,36 @@ static struct task_struct *pick_next_hig
 }
 
 static DEFINE_PER_CPU(cpumask_t, local_cpu_mask);
-static DEFINE_PER_CPU(cpumask_t, valid_cpu_mask);
 
 static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 {
-	int       cpu;
-	cpumask_t *valid_mask = &__get_cpu_var(valid_cpu_mask);
 	int       lowest_prio = -1;
+	int       lowest_cpu  = -1;
 	int       count       = 0;
+	int       cpu;
 
-	cpus_clear(*lowest_mask);
-	cpus_and(*valid_mask, cpu_online_map, task->cpus_allowed);
+	cpus_and(*lowest_mask, cpu_online_map, task->cpus_allowed);
 
 	/*
 	 * Scan each rq for the lowest prio.
 	 */
-	for_each_cpu_mask(cpu, *valid_mask) {
+	for_each_cpu_mask(cpu, *lowest_mask) {
 		struct rq *rq = cpu_rq(cpu);
 
 		/* We look for lowest RT prio or non-rt CPU */
 		if (rq->rt.highest_prio >= MAX_RT_PRIO) {
-			if (count)
+			/*
+			 * if we already found a low RT queue
+			 * and now we found this non-rt queue
+			 * clear the mask and set our bit.
+			 * Otherwise just return the queue as is
+			 * and the count==1 will cause the algorithm
+			 * to use the first bit found.
+			 */
+			if (lowest_cpu != -1) {
 				cpus_clear(*lowest_mask);
-			cpu_set(rq->cpu, *lowest_mask);
+				cpu_set(rq->cpu, *lowest_mask);
+			}
 			return 1;
 		}
 

@@ -325,13 +332,29 @@ static int find_lowest_cpus(struct task_
 			if (rq->rt.highest_prio > lowest_prio) {
 				/* new low - clear old data */
 				lowest_prio = rq->rt.highest_prio;
-				if (count) {
-					cpus_clear(*lowest_mask);
-					count = 0;
-				}
+				lowest_cpu = cpu;
+				count = 0;
 			}
-			cpu_set(rq->cpu, *lowest_mask);
 			count++;
+		} else
+			cpu_clear(cpu, *lowest_mask);
+	}
+
+	/*
+	 * Clear out all the set bits that represent
+	 * runqueues that were of higher prio than
+	 * the lowest_prio.
+	 */
+	if (lowest_cpu > 0) {
+		/*
+		 * Perhaps we could add another cpumask op to
+		 * zero out bits. Like cpu_zero_bits(cpumask, nrbits);
+		 * Then that could be optimized to use memset and such.
+		 */
+		for_each_cpu_mask(cpu, *lowest_mask) {
+			if (cpu >= lowest_cpu)
+				break;
+			cpu_clear(cpu, *lowest_mask);
 		}
 	}
#24 lore raw

Re: [PATCH] Fix optimized search

Quoted 1 line
Quoted 1 line
Quoted 1 line

On Tue, Nov 20, 2007 at 11:26 PM, in message

<[email protected]>, Steven Rostedt <[email protected]>

Quoted 8 lines · wrote:
Quoted 6 lines · Steven Rostedt
Quoted 2 lines · Gregory Haskins

I spied a few more issues from http://lkml.org/lkml/2007/11/20/590.
Patch is below..

Thanks, but I have one update...

Quoted 8 lines

Here's the updated patch.

Oh, and Gregory, please email me at my [email protected] account. It has better filters ;-)

This series is at:

http://rostedt.homelinux.com/rt/rt-balance-patches-v6.tar.bz2

Ah..mails crossed. ;) Ignore my patch #1 from the 0/4 series I just sent out.

Regards,
-Greg

author reviewer
#25 lore raw

PATCH v4 20/20 balance RT tasks no new wake up

In reply to Steven Rostedt

Run the RT balancing code on wake up to an RT task.

Signed-off-by Steven Rostedt <[email protected]>
---
 kernel/sched.c |    1 +
 1 file changed, 1 insertion(+)
kernel/sched.c +1 -0
Index: linux-compile.git/kernel/sched.c
===================================================================
@@ -1650,6 +1650,7 @@ void fastcall wake_up_new_task(struct ta
 		inc_nr_running(p, rq);
 	}
 	check_preempt_curr(rq, p);
+	wakeup_balance_rt(rq, p);
 	task_rq_unlock(rq, &flags);
 }
#26 lore raw

cover more RT balancing enhancements

In reply to Steven Rostedt

These are patches that apply to the end of the v5 series annouced here:

http://lkml.org/lkml/2007/11/20/558

Steven,
These are patches that I could not finish in time to get in with the v4 release.

Ingo,
If you accept the prior work submitted by Steven and myself, please also consider this series.

Comments/feedback welcome!

Regards,
-Greg

#27 lore raw

PATCH 1/4 Fix optimized search

Include cpu 0 in the search, and eliminate the redundant cpu_set since the bit should already be set in the mask.

Signed-off-by Gregory Haskins <[email protected]>

---

 kernel/sched_rt.c |    7 +++----
 1 files changed, 3 insertions(+), 4 deletions(-)
kernel/sched_rt.c +3 -4
index 28feeff..fbf4fb1 100644
@@ -297,7 +297,7 @@ static DEFINE_PER_CPU(cpumask_t, local_cpu_mask);
 static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 {
 	int       lowest_prio = -1;
-	int       lowest_cpu  = 0;
+	int       lowest_cpu  = -1;
 	int       count       = 0;
 	int       cpu;
 

@@ -319,7 +319,7 @@ static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 			 * and the count==1 will cause the algorithm
 			 * to use the first bit found.
 			 */
-			if (lowest_cpu) {
+			if (lowest_cpu != -1) {
 				cpus_clear(*lowest_mask);
 				cpu_set(rq->cpu, *lowest_mask);
 			}

@@ -335,7 +335,6 @@ static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 				lowest_cpu = cpu;
 				count = 0;
 			}
-			cpu_set(rq->cpu, *lowest_mask);
 			count++;
 		} else
 			cpu_clear(cpu, *lowest_mask);

@@ -346,7 +345,7 @@ static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
 	 * runqueues that were of higher prio than
 	 * the lowest_prio.
 	 */
-	if (lowest_cpu) {
+	if (lowest_cpu != -1) {
 		/*
 		 * Perhaps we could add another cpumask op to
 		 * zero out bits. Like cpu_zero_bits(cpumask, nrbits);
#28 lore raw

PATCH 2/4 RT: Add sched-domain roots

In reply to Gregory Haskins

We add the notion of a root-domain which will be used later to rescope global variables to per-domain variables. Each exclusive cpuset essentially defines an island domain by fully partitioning the member cpus from any other cpuset. However, we currently still maintain some policy/state as global variables which transcend all cpusets. Consider, for instance, rt-overload state.

Whenever a new exclusive cpuset is created, we also create a new root-domain object and move each cpu member to the root-domain's span. By default the system creates a single root-domain with all cpus as members (mimicking the global state we have today).

We add some plumbing for storing class specific data in our root-domain. Whenever a RQ is switching root-domains (because of repartitioning) we give each sched_class the opportunity to remove any state from its old domain and add state to the new one. This logic doesn't have any clients yet but it will later in the series.

Signed-off-by Gregory Haskins <[email protected]>
CC Christoph Lameter <[email protected]>
CC Paul Jackson <[email protected]>
CC Simon Derr <[email protected]>

---

 include/linux/sched.h |    3 ++
 kernel/sched.c        |   89 +++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 89 insertions(+), 3 deletions(-)
include/linux/sched.h +3 -0
index 19d9f3f..0ba221e 100644
@@ -845,6 +845,9 @@ struct sched_class {
 	void (*task_tick) (struct rq *rq, struct task_struct *p);
 	void (*task_new) (struct rq *rq, struct task_struct *p);
 	void (*set_cpus_allowed)(struct task_struct *p, cpumask_t *newmask);
+
+	void (*join_domain)(struct rq *rq);
+	void (*leave_domain)(struct rq *rq);
 };
 
 struct load_weight {
kernel/sched.c +86 -3

153 lines not on this page · raw message

#29 lore raw

PATCH 3/4 RT: Only balance our RT tasks within our root-domain

In reply to Gregory Haskins

We move the rt-overload data as the first global to per-domain reclassification. This limits the scope of overload related cache-line bouncing to stay with a specified partition instead of affecting all cpus in the system.

Finally, we limit the scope of find_lowest_cpu searches to the domain instead of the entire system. Note that we would always respect domain boundaries even without this patch, but we first would scan potentially all cpus before whittling the list down. Now we can avoid looking at RQs that are out of scope, again reducing cache-line hits.

Note: In some cases, task->cpus_allowed will effectively reduce our search to within our domain. However, I believe there are cases where the cpus_allowed mask may be all ones and therefore we err on the side of caution. If it can be optimized later, so be it.

Signed-off-by Gregory Haskins <[email protected]>
CC Christoph Lameter <[email protected]>

---

 kernel/sched.c    |    2 ++
 kernel/sched_rt.c |   65 +++++++++++++++++++++++++++++++++++------------------
 2 files changed, 45 insertions(+), 22 deletions(-)
kernel/sched.c +2 -0
index fb619fb..578c186 100644
@@ -281,6 +281,8 @@ struct rt_rq {
 struct root_domain {
 	atomic_t refcount;
 	cpumask_t span;
+	cpumask_t rto_mask;
+	atomic_t  rto_count;
 };
 
 struct root_domain def_root_domain;
kernel/sched_rt.c +43 -22

119 lines not on this page · raw message

#30 lore raw

PATCH 4/4 RT: Use a 2-d bitmap for searching lowest-pri CPU

In reply to Gregory Haskins

The current code use a linear algorithm which causes scaling issues on larger SMP machines. This patch replaces that algorithm with a 2-dimensional bitmap to reduce latencies in the wake-up path.

In this past, this patch has maintained the priorties as a global property. It now has a per-root-domain scope to shield unrelated domains from unecessary cache collisions.

You may ask yourself why do we add logic to find_lowest_cpus() earlier in the series and then rip it out in this patch. The answer is that this current patch has been controversial, and is likely to not be accepted (at least in the short term). Therefore, it is in our best interest to optimize as much of the code prior to this patch as possible even if we ultimately rip it out here. That way, the system is still tuned even if this patch goes to /dev/null.

You may now be asking yourself why bother including this patch? The answer is that our own independent testing shows
(http://article.gmane.org/gmane.linux.rt.user/1889) this patch makes a significant performance improvement (at least for rt latencies) and doesnt appear to cause any regressions in other dimensions. However, I also understand the reservations raised by Steve Rostedt et. al. Therefore, I include this patch in the hopes that it is useful to someone, but with the understanding that it is not likely to be accepted without further demonstration of its benefits.

Signed-off-by Gregory Haskins <[email protected]>
CC Christoph Lameter <[email protected]>

---

 kernel/Makefile       |    1 
 kernel/sched.c        |    4 +
 kernel/sched_cpupri.c |  166 +++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched_cpupri.h |   35 ++++++++++
 kernel/sched_rt.c     |  104 +++++--------------------------
 5 files changed, 223 insertions(+), 87 deletions(-)
kernel/Makefile +1 -0
index dfa9695..c013a6c 100644
@@ -57,6 +57,7 @@ obj-$(CONFIG_SYSCTL) += utsname_sysctl.o
 obj-$(CONFIG_TASK_DELAY_ACCT) += delayacct.o
 obj-$(CONFIG_TASKSTATS) += taskstats.o tsacct.o
 obj-$(CONFIG_MARKERS) += marker.o
+obj-$(CONFIG_SMP) += sched_cpupri.o
 
 ifneq ($(CONFIG_SCHED_NO_NO_OMIT_FRAME_POINTER),y)
 # According to Alan Modra <[email protected]>, the -fno-omit-frame-pointer is
kernel/sched.c +4 -0
index 578c186..d6be7e6 100644
@@ -70,6 +70,8 @@
 #include <asm/tlb.h>
 #include <asm/irq_regs.h>
 
+#include "sched_cpupri.h"
+
 /*
  * Scheduler clock - returns current time in nanosec units.
  * This is default implementation.

@@ -283,6 +285,7 @@ struct root_domain {
 	cpumask_t span;
 	cpumask_t rto_mask;
 	atomic_t  rto_count;
+	struct cpupri cpupri;
 };
 
 struct root_domain def_root_domain;

@@ -5765,6 +5768,7 @@ static void init_rootdomain(struct root_domain *rd, cpumask_t *map)
 	memset(rd, 0, sizeof(*rd));
 
 	rd->span = *map;
+	cpupri_init(&rd->cpupri);
 }
 
 static void init_defrootdomain(void)
kernel/sched_cpupri.c new file +166 -0

166 lines not on this page · raw message

kernel/sched_cpupri.h new file +35 -0
new file mode 100644
index 0000000..1392c93
@@ -0,0 +1,35 @@
+#ifndef _LINUX_CPUPRI_H
+#define _LINUX_CPUPRI_H
+
+#include <linux/sched.h>
+
+#define CPUPRI_NR_PRIORITIES 2+MAX_RT_PRIO
+#define CPUPRI_NR_PRI_WORDS CPUPRI_NR_PRIORITIES/BITS_PER_LONG
+
+#define CPUPRI_INVALID -1
+#define CPUPRI_IDLE     0
+#define CPUPRI_NORMAL   1
+/* values 2-101 are RT priorities 0-99 */
+
+struct cpupri_vec
+{
+	spinlock_t lock;
+	cpumask_t  mask;
+};
+
+struct cpupri {
+	struct cpupri_vec pri_to_cpu[CPUPRI_NR_PRIORITIES];
+	long              pri_active[CPUPRI_NR_PRI_WORDS];
+	int               cpu_to_pri[NR_CPUS];
+};
+
+#ifdef CONFIG_SMP
+int  cpupri_find(struct cpupri *cp,
+		 struct task_struct *p, cpumask_t *lowest_mask);
+void cpupri_set(struct cpupri *cp, int cpu, int pri);
+void cpupri_init(struct cpupri *cp);
+#else
+#define cpupri_init() do { } while(0)
+#endif
+
+#endif /* _LINUX_CPUPRI_H */
kernel/sched_rt.c +17 -87

149 lines not on this page · raw message

#32 lore raw

PATCH 1/4 SCHED: Add sched-domain roots

We add the notion of a root-domain which will be used later to rescope global variables to per-domain variables. Each exclusive cpuset essentially defines an island domain by fully partitioning the member cpus from any other cpuset. However, we currently still maintain some policy/state as global variables which transcend all cpusets. Consider, for instance, rt-overload state.

Whenever a new exclusive cpuset is created, we also create a new root-domain object and move each cpu member to the root-domain's span. By default the system creates a single root-domain with all cpus as members (mimicking the global state we have today).

We add some plumbing for storing class specific data in our root-domain. Whenever a RQ is switching root-domains (because of repartitioning) we give each sched_class the opportunity to remove any state from its old domain and add state to the new one. This logic doesn't have any clients yet but it will later in the series.

Signed-off-by Gregory Haskins <[email protected]>
CC Christoph Lameter <[email protected]>
CC Paul Jackson <[email protected]>
CC Simon Derr <[email protected]>

---

 include/linux/sched.h |    3 ++
 kernel/sched.c        |   89 +++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 89 insertions(+), 3 deletions(-)
include/linux/sched.h +3 -0
index 19d9f3f..0ba221e 100644
@@ -845,6 +845,9 @@ struct sched_class {
 	void (*task_tick) (struct rq *rq, struct task_struct *p);
 	void (*task_new) (struct rq *rq, struct task_struct *p);
 	void (*set_cpus_allowed)(struct task_struct *p, cpumask_t *newmask);
+
+	void (*join_domain)(struct rq *rq);
+	void (*leave_domain)(struct rq *rq);
 };
 
 struct load_weight {
kernel/sched.c +86 -3

153 lines not on this page · raw message

#33 lore raw

PATCH 2/4 SCHED: Track online cpus in the root-domain

In reply to Gregory Haskins

We cache the subset of rd->span cpus that are online in rd->online to reduce the need for runtime computation.

Signed-off-by Gregory Haskins <[email protected]>

---

 kernel/sched.c |   22 ++++++++++++++++++++++
 1 files changed, 22 insertions(+), 0 deletions(-)
kernel/sched.c +22 -0
index e5c902c..c58d1bf 100644
@@ -281,6 +281,7 @@ struct rt_rq {
 struct root_domain {
 	atomic_t refcount;
 	cpumask_t span;
+	cpumask_t online;
 };
 
 static struct root_domain def_root_domain;

@@ -5491,6 +5492,15 @@ migration_call(struct notifier_block *nfb, unsigned long action, void *hcpu)
 	case CPU_ONLINE_FROZEN:
 		/* Strictly unnecessary, as first user will wake it. */
 		wake_up_process(cpu_rq(cpu)->migration_thread);
+
+		/* Update our root-domain */
+		rq = cpu_rq(cpu);
+		spin_lock_irqsave(&rq->lock, flags);
+		if (rq->rd) {
+			BUG_ON(!cpu_isset(cpu, rq->rd->span));
+			cpu_set(cpu, rq->rd->online);
+		}
+		spin_unlock_irqrestore(&rq->lock, flags);
 		break;
 
 #ifdef CONFIG_HOTPLUG_CPU

@@ -5539,6 +5549,17 @@ migration_call(struct notifier_block *nfb, unsigned long action, void *hcpu)
 		}
 		spin_unlock_irq(&rq->lock);
 		break;
+
+	case CPU_DOWN_PREPARE:
+		/* Update our root-domain */
+		rq = cpu_rq(cpu);
+		spin_lock_irqsave(&rq->lock, flags);
+		if (rq->rd) {
+			BUG_ON(!cpu_isset(cpu, rq->rd->span));
+			cpu_clear(cpu, rq->rd->online);
+		}
+		spin_unlock_irqrestore(&rq->lock, flags);	
+		break;
 #endif
 	case CPU_LOCK_RELEASE:
 		mutex_unlock(&sched_hotcpu_mutex);

@@ -5763,6 +5784,7 @@ static void init_rootdomain(struct root_domain *rd, cpumask_t *map)
 	memset(rd, 0, sizeof(*rd));
 
 	rd->span = *map;
+	cpus_and(rd->online, rd->span, cpu_online_map);
 }
 
 static void init_defrootdomain(void)
#34 lore raw

PATCH 3/4 SCHED: Only balance our RT tasks within our root-domain

In reply to Gregory Haskins

We move the rt-overload data as the first global to per-domain reclassification. This limits the scope of overload related cache-line bouncing to stay with a specified partition instead of affecting all cpus in the system.

Finally, we limit the scope of find_lowest_cpu searches to the domain instead of the entire system. Note that we would always respect domain boundaries even without this patch, but we first would scan potentially all cpus before whittling the list down. Now we can avoid looking at RQs that are out of scope, again reducing cache-line hits.

Note: In some cases, task->cpus_allowed will effectively reduce our search to within our domain. However, I believe there are cases where the cpus_allowed mask may be all ones and therefore we err on the side of caution. If it can be optimized later, so be it.

Signed-off-by Gregory Haskins <[email protected]>
CC Christoph Lameter <[email protected]>

---

 kernel/sched.c    |    2 ++
 kernel/sched_rt.c |   58 ++++++++++++++++++++++++++++++++---------------------
 2 files changed, 37 insertions(+), 23 deletions(-)
kernel/sched.c +2 -0
index c58d1bf..55a2a59 100644
@@ -282,6 +282,8 @@ struct root_domain {
 	atomic_t refcount;
 	cpumask_t span;
 	cpumask_t online;
+	cpumask_t rto_mask;
+	atomic_t  rto_count;
 };
 
 static struct root_domain def_root_domain;
kernel/sched_rt.c +35 -23

112 lines not on this page · raw message

#35 lore raw

PATCH 4/4 SCHED: Use a 2-d bitmap for searching lowest-pri CPU

In reply to Gregory Haskins

The current code use a linear algorithm which causes scaling issues on larger SMP machines. This patch replaces that algorithm with a 2-dimensional bitmap to reduce latencies in the wake-up path.

In this past, this patch has maintained the priorties as a global property. It now has a per-root-domain scope to shield unrelated domains from unecessary cache collisions.

You may ask yourself why do we add logic to find_lowest_cpus() earlier in the series and then rip it out in this patch. The answer is that this current patch has been controversial, and is likely to not be accepted (at least in the short term). Therefore, it is in our best interest to optimize as much of the code prior to this patch as possible even if we ultimately rip it out here. That way, the system is still tuned even if this patch goes to /dev/null.

You may now be asking yourself why bother including this patch? The answer is that our own independent testing shows
(http://article.gmane.org/gmane.linux.rt.user/1889) this patch makes a significant performance improvement (at least for rt latencies) and doesnt appear to cause any regressions in other dimensions. However, I also understand the reservations raised by Steve Rostedt et. al. Therefore, I include this patch in the hopes that it is useful to someone, but with the understanding that it is not likely to be accepted without further demonstration of its benefits.

Signed-off-by Gregory Haskins <[email protected]>
CC Christoph Lameter <[email protected]>

---

 kernel/Makefile       |    1 
 kernel/sched.c        |    4 +
 kernel/sched_cpupri.c |  166 +++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched_cpupri.h |   35 ++++++++++
 kernel/sched_rt.c     |   95 +++++-----------------------
 5 files changed, 223 insertions(+), 78 deletions(-)
kernel/Makefile +1 -0
index dfa9695..c013a6c 100644
@@ -57,6 +57,7 @@ obj-$(CONFIG_SYSCTL) += utsname_sysctl.o
 obj-$(CONFIG_TASK_DELAY_ACCT) += delayacct.o
 obj-$(CONFIG_TASKSTATS) += taskstats.o tsacct.o
 obj-$(CONFIG_MARKERS) += marker.o
+obj-$(CONFIG_SMP) += sched_cpupri.o
 
 ifneq ($(CONFIG_SCHED_NO_NO_OMIT_FRAME_POINTER),y)
 # According to Alan Modra <[email protected]>, the -fno-omit-frame-pointer is
kernel/sched.c +4 -0
index 55a2a59..436db58 100644
@@ -70,6 +70,8 @@
 #include <asm/tlb.h>
 #include <asm/irq_regs.h>
 
+#include "sched_cpupri.h"
+
 /*
  * Scheduler clock - returns current time in nanosec units.
  * This is default implementation.

@@ -284,6 +286,7 @@ struct root_domain {
 	cpumask_t online;
 	cpumask_t rto_mask;
 	atomic_t  rto_count;
+	struct cpupri cpupri;
 };
 
 static struct root_domain def_root_domain;

@@ -5787,6 +5790,7 @@ static void init_rootdomain(struct root_domain *rd, cpumask_t *map)
 
 	rd->span = *map;
 	cpus_and(rd->online, rd->span, cpu_online_map);
+	cpupri_init(&rd->cpupri);
 }
 
 static void init_defrootdomain(void)
kernel/sched_cpupri.c new file +166 -0

166 lines not on this page · raw message

kernel/sched_cpupri.h new file +35 -0
new file mode 100644
index 0000000..1392c93
@@ -0,0 +1,35 @@
+#ifndef _LINUX_CPUPRI_H
+#define _LINUX_CPUPRI_H
+
+#include <linux/sched.h>
+
+#define CPUPRI_NR_PRIORITIES 2+MAX_RT_PRIO
+#define CPUPRI_NR_PRI_WORDS CPUPRI_NR_PRIORITIES/BITS_PER_LONG
+
+#define CPUPRI_INVALID -1
+#define CPUPRI_IDLE     0
+#define CPUPRI_NORMAL   1
+/* values 2-101 are RT priorities 0-99 */
+
+struct cpupri_vec
+{
+	spinlock_t lock;
+	cpumask_t  mask;
+};
+
+struct cpupri {
+	struct cpupri_vec pri_to_cpu[CPUPRI_NR_PRIORITIES];
+	long              pri_active[CPUPRI_NR_PRI_WORDS];
+	int               cpu_to_pri[NR_CPUS];
+};
+
+#ifdef CONFIG_SMP
+int  cpupri_find(struct cpupri *cp,
+		 struct task_struct *p, cpumask_t *lowest_mask);
+void cpupri_set(struct cpupri *cp, int cpu, int pri);
+void cpupri_init(struct cpupri *cp);
+#else
+#define cpupri_init() do { } while(0)
+#endif
+
+#endif /* _LINUX_CPUPRI_H */
kernel/sched_rt.c +17 -78

140 lines not on this page · raw message