Skip to contentSkip to conversation

sched: misc rt fixes for tip/sched/devel

PATCH Superseded Gregory Haskins 8 participants 51 messages Aug 25, 2008 – Sep 4, 2008 Scheduler

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

cover sched: misc rt fixes for tip/sched/devel

Hi Ingo,

The following repositories

git://git.kernel.org/pub/scm/linux/kernel/git/ghaskins/linux-2.6-hacks.git tip/sched/devel/rtbalance

ftp://ftp.novell.com/dev/ghaskins/tip-rt-fixes.tar.bz2

apply to tip/sched/devel to pick up the following fixes for the RT scheduler.

---

Gregory Haskins (5):
sched: create "pushable_tasks" list to limit pushing to one attempt
sched: add sched_class->needs_post_schedule() member
sched: make double-lock-balance fair
sched: pull only one task during NEWIDLE balancing to limit critical section
sched: only try to push a task on wakeup if it is migratable

 include/linux/init_task.h |    1 
 include/linux/sched.h     |    2 +
 kernel/sched.c            |   37 +++++++-----
 kernel/sched_rt.c         |  139 ++++++++++++++++++++++++++++++++++++++-------
 4 files changed, 143 insertions(+), 36 deletions(-)
Signature · 11 lines
These patches were developed in the interest of shorting latencies in
PREEMPT_RT, but they apply to the mainline scheduler as well, so I am
offering them here first.

This has been tested under both 26.3-rt3 and tip/sched/devel on x86_64 for
both CONFIG_SMP and !CONFIG_SMP.

Comments/bug-fixes welcome!

Regards,
-Greg
#1 lore raw

PATCH 1/5 sched: only try to push a task on wakeup if it is migratable

There is no sense in wasting time trying to push a task away that cannot move anywhere else. We gain no benefit from trying to push other tasks at this point, so if the task being woken up is non migratable, just skip the whole operation. This reduces overhead in the wakeup path for certain tasks.

---

 kernel/sched_rt.c |    8 +++++---
 1 files changed, 5 insertions(+), 3 deletions(-)
kernel/sched_rt.c +5 -3
index 6163e4c..196c024 100644
@@ -1229,14 +1229,16 @@ static void post_schedule_rt(struct rq *rq)
 }
 
 /*
- * If we are not running and we are not going to reschedule soon, we should
- * try to push tasks away now
+ * If we are not running, we are not going to reschedule soon,
+ * and we have tasks that could be pushed, we should try to push tasks
+ * away now
  */
 static void task_wake_up_rt(struct rq *rq, struct task_struct *p)
 {
 	if (!task_running(rq, p) &&
 	    !test_tsk_need_resched(rq->curr) &&
-	    rq->rt.overloaded)
+	    rq->rt.overloaded &&
+	    p->rt.nr_cpus_allowed > 1)
 		push_rt_tasks(rq);
 }
 
#2 lore raw

PATCH 2/5 sched: pull only one task during NEWIDLE balancing to limit critical section

In reply to Gregory Haskins

git-id c4acb2c0669c5c5c9b28e9d02a34b5c67edf7092 attempted to limit newidle critical section length by stopping after at least one task was moved. Further investigation has shown that there are other paths nested further inside the algorithm which still remain that allow long latencies to occur with newidle balancing. This patch applies the same technique inside balance_tasks() to limit the duration of this optional balancing operation.

---

 kernel/sched.c |    6 ++++--
 1 files changed, 4 insertions(+), 2 deletions(-)
kernel/sched.c +4 -2
index 6a43c89..6e0bde6 100644
@@ -2963,9 +2963,11 @@ next:
 	rem_load_move -= p->se.load.weight;
 
 	/*
-	 * We only want to steal up to the prescribed amount of weighted load.
+	 * We only want to steal up to the prescribed amount of weighted load
+	 * and we don't want to take more than one task if we are NEWLY idle
+	 * since this can cause unbounded latencies
 	 */
-	if (rem_load_move > 0) {
+	if (idle != CPU_NEWLY_IDLE && rem_load_move > 0) {
 		if (p->prio < *this_best_prio)
 			*this_best_prio = p->prio;
 		p = iterator->next(iterator->arg);
#8 lore raw

PATCH 3/5 sched: make double-lock-balance fair

In reply to Gregory Haskins

double_lock balance() currently favors logically lower cpus since they often do not have to release their own lock to acquire a second lock. The result is that logically higher cpus can get starved when there is a lot of pressure on the RQs. This can result in higher latencies on higher cpu-ids.

This patch makes the algorithm more fair by forcing all paths to have to release both locks before acquiring them again. Since callsites to double_lock_balance already consider it a potential preemption/reschedule point, they have the proper logic to recheck for atomicity violations.

---

 kernel/sched.c |   17 +++++------------
 1 files changed, 5 insertions(+), 12 deletions(-)
kernel/sched.c +0 -1
index 6e0bde6..b7326cd 100644
@@ -2790,23 +2790,16 @@ static int double_lock_balance(struct rq *this_rq, struct rq *busiest)
 	__acquires(busiest->lock)
 	__acquires(this_rq->lock)
 {
-	int ret = 0;
#15 lore raw

PATCH 4/5 sched: add sched_class->needs_post_schedule() member

In reply to Gregory Haskins

We currently run class->post_schedule() outside of the rq->lock, which means that we need to test for the need to post_schedule outside of the lock to avoid a forced reacquistion. This is currently not a problem as we only look at rq->rt.overloaded. However, we want to enhance this going forward to look at more state to reduce the need to post_schedule to a bare minimum set. Therefore, we introduce a new member-func called needs_post_schedule() which tests for the post_schedule condtion without actually performing the work. Therefore it is safe to call this function before the rq->lock is released, because we are guaranteed not to drop the lock at an intermediate point (such as what post_schedule() may do).

We will use this later in the series

---

 include/linux/sched.h |    1 +
 kernel/sched.c        |   10 +++++++++-
 kernel/sched_rt.c     |   24 ++++++++++++++----------
 3 files changed, 24 insertions(+), 11 deletions(-)
include/linux/sched.h +1 -0
index 08a87b5..cf8cd8c 100644
@@ -912,6 +912,7 @@ struct sched_class {
 			      struct rq *busiest, struct sched_domain *sd,
 			      enum cpu_idle_type idle);
 	void (*pre_schedule) (struct rq *this_rq, struct task_struct *task);
+	int (*needs_post_schedule) (struct rq *this_rq);
 	void (*post_schedule) (struct rq *this_rq);
 	void (*task_wake_up) (struct rq *this_rq, struct task_struct *task);
 #endif
kernel/sched.c +9 -1
index b7326cd..78fae75 100644
@@ -2525,6 +2525,14 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
 {
 	struct mm_struct *mm = rq->prev_mm;
 	long prev_state;
+#ifdef CONFIG_SMP
+	int post_schedule = 0;
+
+	if (current->sched_class->needs_post_schedule) {
+		BUG_ON(!current->sched_class->post_schedule);
+		post_schedule = current->sched_class->needs_post_schedule(rq);
+	}
+#endif
 
 	rq->prev_mm = NULL;
 
@@ -2543,7 +2551,7 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
 	finish_arch_switch(prev);
 	finish_lock_switch(rq, prev);
 #ifdef CONFIG_SMP
-	if (current->sched_class->post_schedule)
+	if (post_schedule)
 		current->sched_class->post_schedule(rq);
 #endif
 
kernel/sched_rt.c +14 -10
index 196c024..a3d695b 100644
@@ -1212,20 +1212,23 @@ static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
 		pull_rt_task(rq);
 }
 
+/*
+ * assumes rq->lock is held
+ */
+static int needs_post_schedule_rt(struct rq *rq)
+{
+	return rq->rt.overloaded ? 1 : 0;
+}
+
 static void post_schedule_rt(struct rq *rq)
 {
 	/*
-	 * If we have more than one rt_task queued, then
-	 * see if we can push the other rt_tasks off to other CPUS.
-	 * Note we may release the rq lock, and since
-	 * the lock was owned by prev, we need to release it
-	 * first via finish_lock_switch and then reaquire it here.
+	 * This is only called if needs_post_schedule_rt() indicates that
+	 * we need to push tasks away
 	 */
-	if (unlikely(rq->rt.overloaded)) {
-		spin_lock_irq(&rq->lock);
-		push_rt_tasks(rq);
-		spin_unlock_irq(&rq->lock);
-	}
+	spin_lock_irq(&rq->lock);
+	push_rt_tasks(rq);
+	spin_unlock_irq(&rq->lock);
 }
 
 /*
@@ -1473,6 +1476,7 @@ static const struct sched_class rt_sched_class = {
 	.rq_online              = rq_online_rt,
 	.rq_offline             = rq_offline_rt,
 	.pre_schedule		= pre_schedule_rt,
+	.needs_post_schedule	= needs_post_schedule_rt,
 	.post_schedule		= post_schedule_rt,
 	.task_wake_up		= task_wake_up_rt,
 	.switched_from		= switched_from_rt,
#16 lore raw

PATCH 5/5 sched: create "pushable_tasks" list to limit pushing to one attempt

In reply to Gregory Haskins

The RT scheduler employs a "push/pull" design to actively balance tasks within the system (on a per disjoint cpuset basis). When a task is awoken, it is immediately determined if there are any lower priority cpus which should be preempted. This is opposed to the way normal SCHED_OTHER tasks behave, which will wait for a periodic rebalancing operation to occur before spreading out load.

When a particular RQ has more than 1 active RT task, it is said to be in an "overloaded" state. Once this occurs, the system enters the active balancing mode, where it will try to push the task away, or persuade a different cpu to pull it over. The system will stay in this state until the system falls back below the <= 1 queued RT task per RQ.

However, the current implementation suffers from a limitation in the push logic. Once overloaded, all tasks (other than current) on the RQ are analyzed on every push operation, even if it was previously unpushable (due to affinity, etc). Whats more, the operation stops at the first task that is unpushable and will not look at items lower in the queue. This causes two problems:

1) We can have the same tasks analyzed over and over again during each push, which extends out the fast path in the scheduler for no gain. Consider a RQ that has dozens of tasks that are bound to a core. Each one of those tasks will be encountered and skipped for each push operation while they are queued.

2) There may be lower-priority tasks under the unpushable task that could have been successfully pushed, but will never be considered until either the unpushable task is cleared, or a pull operation succeeds. The net result is a potential latency source for mid priority tasks.

This patch aims to rectify these two conditions by introducing a new priority sorted list: "pushable_tasks". A task is added to the list each time a task is activated or preempted. It is removed from the list any time it is deactivated, made current, or fails to push.

This works because a task only needs to be attempted to push once. After an initial failure to push, the other cpus will eventually try to pull the task when the conditions are proper. This also solves the problem that we don't completely analyze all tasks due to encountering an unpushable tasks. Now every task will have a push attempted (when appropriate).

This reduces latency both by shorting the critical section of the rq->lock for certain workloads, and by making sure the algorithm considers all eligible tasks in the system.

---

 include/linux/init_task.h |    1 
 include/linux/sched.h     |    1 
 kernel/sched.c            |    4 ++
 kernel/sched_rt.c         |  111 +++++++++++++++++++++++++++++++++++++++++----
 4 files changed, 107 insertions(+), 10 deletions(-)
include/linux/init_task.h +1 -0
index 021d8e7..7f910f4 100644
@@ -140,6 +140,7 @@ extern struct group_info init_groups;
 		.nr_cpus_allowed = NR_CPUS,				\
 	},								\
 	.tasks		= LIST_HEAD_INIT(tsk.tasks),			\
+	.pushable_tasks = PLIST_NODE_INIT(tsk.pushable_tasks, MAX_PRIO), \
 	.ptraced	= LIST_HEAD_INIT(tsk.ptraced),			\
 	.ptrace_entry	= LIST_HEAD_INIT(tsk.ptrace_entry),		\
 	.real_parent	= &tsk,						\
include/linux/sched.h +1 -0
index cf8cd8c..3480c8a 100644
@@ -1078,6 +1078,7 @@ struct task_struct {
 #endif
 
 	struct list_head tasks;
+	struct plist_node pushable_tasks;
 
 	struct mm_struct *mm, *active_mm;
 
kernel/sched.c +4 -0
index 78fae75..6ac9aa8 100644
@@ -447,6 +447,7 @@ struct rt_rq {
 #ifdef CONFIG_SMP
 	unsigned long rt_nr_migratory;
 	int overloaded;
+	struct plist_head pushable_tasks;
 #endif
 	int rt_throttled;
 	u64 rt_time;
@@ -2383,6 +2384,8 @@ void sched_fork(struct task_struct *p, int clone_flags)
 	/* Want to start with kernel preemption disabled. */
 	task_thread_info(p)->preempt_count = 1;
 #endif
+	plist_node_init(&p->pushable_tasks, MAX_PRIO);
+
 	put_cpu();
 }
 
@@ -7846,6 +7849,7 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
 #ifdef CONFIG_SMP
 	rt_rq->rt_nr_migratory = 0;
 	rt_rq->overloaded = 0;
+	plist_head_init(&rq->rt.pushable_tasks, &rq->lock);
 #endif
 
 	rt_rq->rt_time = 0;
kernel/sched_rt.c +101 -10

220 lines not on this page · raw message

#9 lore raw

Re: [PATCH 3/5] sched: make double-lock-balance fair

In reply to Gregory Haskins
Quoted 35 lines · Gregory Haskins

double_lock balance() currently favors logically lower cpus since they often do not have to release their own lock to acquire a second lock. The result is that logically higher cpus can get starved when there is a lot of pressure on the RQs. This can result in higher latencies on higher cpu-ids.

This patch makes the algorithm more fair by forcing all paths to have to release both locks before acquiring them again. Since callsites to double_lock_balance already consider it a potential preemption/reschedule point, they have the proper logic to recheck for atomicity violations.

---

 kernel/sched.c |   17 +++++------------
 1 files changed, 5 insertions(+), 12 deletions(-)
kernel/sched.c +0 -5
index 6e0bde6..b7326cd 100644
@@ -2790,23 +2790,16 @@ static int double_lock_balance(struct rq *this_rq,
 struct rq *busiest) __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);
 		BUG_ON(1);
 	}
-	if (unlikely(!spin_trylock(&busiest->lock))) {
-		if (busiest < this_rq) {
-			spin_unlock(&this_rq->lock);

kernel/sched.c static int double_lock_balance(struct rq *this_rq, · line 2800

Quoted 10 lines
kernel/sched.c +3 -7
-			spin_lock(&busiest->lock);
-			spin_lock_nested(&this_rq->lock, SINGLE_DEPTH_NESTING);
-			ret = 1;
-		} else
-			spin_lock_nested(&busiest->lock, SINGLE_DEPTH_NESTING);
-	}
-	return ret;
+
+	spin_unlock(&this_rq->lock);
+	double_rq_lock(this_rq, busiest);

Rather than adding the extra atomic operation, can't you just put this into the unlikely spin_trylock failure path rather than the unfair logic there?

FWIW, this is always going to be a *tiny* bit unfair, because of double rq lock taking the lower lock first. I guess to fix that you need to just have a single lock to take before taking 2 rq locks. But that's not really appropriate for mainline (and maybe not -rt either).

#3 lore raw

Re: [PATCH 2/5] sched: pull only one task during NEWIDLE balancing to limit critical section

In reply to Gregory Haskins
Quoted 10 lines · Gregory Haskins

git-id c4acb2c0669c5c5c9b28e9d02a34b5c67edf7092 attempted to limit newidle critical section length by stopping after at least one task was moved. Further investigation has shown that there are other paths nested further inside the algorithm which still remain that allow long latencies to occur with newidle balancing. This patch applies the same technique inside balance_tasks() to limit the duration of this optional balancing operation.

Hmm, this (andc4acb2c0669c5c5c9b28e9d02a34b5c67edf7092) still could increase the amount of work to do significantly for workloads where the CPU is going idle and pulling tasks over frequently. I don't really like either of them too much.

Maybe increasing the limit would effectively amortize most of the problem (say, limit to move 16 tasks at most).

#4 lore raw

Re: [PATCH 2/5] sched: pull only one task during NEWIDLE balancing to limit critical section

Quoted 10 lines · Nick Piggin
Quoted 8 lines · Gregory Haskins

git-id c4acb2c0669c5c5c9b28e9d02a34b5c67edf7092 attempted to limit newidle critical section length by stopping after at least one task was moved. Further investigation has shown that there are other paths nested further inside the algorithm which still remain that allow long latencies to occur with newidle balancing. This patch applies the same technique inside balance_tasks() to limit the duration of this optional balancing operation.

Quoted 9 lines
Quoted 3 lines

Hmm, this (andc4acb2c0669c5c5c9b28e9d02a34b5c67edf7092) still could increase the amount of work to do significantly for workloads where the CPU is going idle and pulling tasks over frequently. I don't really like either of them too much.

I had a feeling you may object to this patch based on your comments on the first one. Thats why I CC'd you so you wouldnt think I was trying to sneak something past ;)

Quoted 3 lines

Maybe increasing the limit would effectively amortize most of the problem (say, limit to move 16 tasks at most).

The problem I was seeing was that even moving 2 was too many in the ftraces traces I looked at. I think the idea of making a variable limit (set via a sysctl, etc) here is a good one, but I would recommend we have the default be "1" for CONFIG_PREEMPT (or at least
CONFIG_PREEMPT_RT) based on what I know right now. I know last time
you objected to any kind of special cases for the preemptible kernels, but I think this is a good compromise. Would this be acceptable?

Thanks Nick,

-Greg

#10 lore raw

Re: [PATCH 3/5] sched: make double-lock-balance fair

In reply to Nick Piggin
Quoted 44 lines · Nick Piggin
Quoted 42 lines · Gregory Haskins

double_lock balance() currently favors logically lower cpus since they often do not have to release their own lock to acquire a second lock. The result is that logically higher cpus can get starved when there is a lot of pressure on the RQs. This can result in higher latencies on higher cpu-ids.

This patch makes the algorithm more fair by forcing all paths to have to release both locks before acquiring them again. Since callsites to double_lock_balance already consider it a potential preemption/reschedule point, they have the proper logic to recheck for atomicity violations.

---

 kernel/sched.c |   17 +++++------------
 1 files changed, 5 insertions(+), 12 deletions(-)
kernel/sched.c +0 -12
index 6e0bde6..b7326cd 100644
@@ -2790,23 +2790,16 @@ static int double_lock_balance(struct rq *this_rq,
 struct rq *busiest) __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);
 		BUG_ON(1);
 	}
-	if (unlikely(!spin_trylock(&busiest->lock))) {
-		if (busiest < this_rq) {
-			spin_unlock(&this_rq->lock);
-			spin_lock(&busiest->lock);
-			spin_lock_nested(&this_rq->lock, SINGLE_DEPTH_NESTING);
-			ret = 1;
-		} else
-			spin_lock_nested(&busiest->lock, SINGLE_DEPTH_NESTING);
-	}
-	return ret;
Quoted 9 lines

kernel/sched.c static int double_lock_balance(struct rq *this_rq, · line 2801

Quoted 4 lines
kernel/sched.c +3 -0
+
+	spin_unlock(&this_rq->lock);
+	double_rq_lock(this_rq, busiest);
 

Rather than adding the extra atomic operation, can't you just put this into the unlikely spin_trylock failure path rather than the unfair logic there?

The trick is that we *must* first release this_rq before proceeding or the new proposal doesn't work as intended. This patch effectively breaks up the this_rq->lock critical section evenly across all CPUs as if it hit the case common for higher cpus. This modification decreased latency by over 800% (went from > 400us to < 50us) on cpus 6 and 7 in my 8-way box namely because they were not forced to wait for all the other lower cores to finish, but rather completions of double_lock_balance were handled in true FIFO w.r.t. to other calls to double_lock_balance(). It has to do with the positioning within your FIFO ticket locks (though even if ticket locks are not present on a given architecture we should still see an improvement.)

When a low cpu wants to double lock, it tends to hold this_rq and gets in line for busiest_rq with no bearing on how long it held this_rq. Therefore the following scenario can occur:

cpu 0 cpu N
----------------------------------
rq[0] locked
..
..
..
double_lock(N, 0)
rq[N] released
blocked on rq[0]
..
..
..
..
double_lock(0, N)
rq[N] locked
double_lock returns
..
..
..
..
rq[0] released rq[0] locked

                                  double_lock returns
                                  ...
                                  ...
                                  ...

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

So double lock acquisition favors the lower cpus unfairly. They will always win, even if they were not first. Now with the combination of my patch plus your ticket locks, entry into the double lock becomes FIFO because the "blocked on rq[0]" would have inserted it in the time-ordered head of rq[0]. The later call to double_lock(0, N) performed by cpu0 would be forced to queue up behind cpuN trying to reacquire its own lock.

Effectively, double_lock_balance becomes as fair as the underlying spinlock governing the RQ. If we have ticket locks, double_lock_balance is FIFO. Lack of ticket locks means we have arbitrary fairness. And lack of this patch means we have favor for the lower cpus.

To your point about the extra atomic ops: Perhaps I should predicate this change on CONFIG_PREEMPT so as to not slow down mainline where throughput is more valued.

Quoted 2 lines

FWIW, this is always going to be a *tiny* bit unfair, because of double rq lock taking the lower lock first.

While this is technically true, I am not as concerned about the fairness while acquiring the locks.

#17 lore raw

v2 cover Series short description

In reply to Gregory Haskins

Hi Ingo,

The following repositories

git://git.kernel.org/pub/scm/linux/kernel/git/ghaskins/linux-2.6-hacks.git tip/sched/devel/rtbalance

ftp://ftp.novell.com/dev/ghaskins/tip-rt-fixes.tar.bz2

apply to tip/sched/devel to pick up fixes for the RT scheduler.

[
Changelog:

v2:
*) predicated newidle and double_lock changes on
CONFIG_PREEMPT to address a concern by Nick Piggin

*) fixed a build issue when DEBUG_PI_LIST is defined

v1:
*) initial release
]

These patches were developed in the interest of shorting latencies in PREEMPT_RT, but they apply to the mainline scheduler as well, so I am offering them here first.

This has been tested under both 26.3-rt3 and tip/sched/devel on x86_64 for both CONFIG_SMP and !CONFIG_SMP.

Comments/bug-fixes welcome!

Regards,
-Greg

---

Gregory Haskins (6):
sched: create "pushable_tasks" list to limit pushing to one attempt
plist: fix PLIST_NODE_INIT to work with debug enabled
sched: add sched_class->needs_post_schedule() member
sched: make double-lock-balance fair
sched: pull only one task during NEWIDLE balancing to limit critical section
sched: only try to push a task on wakeup if it is migratable

 include/linux/init_task.h |    1 
 include/linux/plist.h     |    9 ++-
 include/linux/sched.h     |    2 +
 kernel/sched.c            |   84 ++++++++++++++++++++++++---
 kernel/sched_rt.c         |  139 ++++++++++++++++++++++++++++++++++++++-------
 5 files changed, 202 insertions(+), 33 deletions(-)
#18 lore raw

PATCH v2 1/6 sched: only try to push a task on wakeup if it is migratable

There is no sense in wasting time trying to push a task away that cannot move anywhere else. We gain no benefit from trying to push other tasks at this point, so if the task being woken up is non migratable, just skip the whole operation. This reduces overhead in the wakeup path for certain tasks.

---

 kernel/sched_rt.c |    8 +++++---
 1 files changed, 5 insertions(+), 3 deletions(-)
kernel/sched_rt.c +5 -3
index 6163e4c..196c024 100644
@@ -1229,14 +1229,16 @@ static void post_schedule_rt(struct rq *rq)
 }
 
 /*
- * If we are not running and we are not going to reschedule soon, we should
- * try to push tasks away now
+ * If we are not running, we are not going to reschedule soon,
+ * and we have tasks that could be pushed, we should try to push tasks
+ * away now
  */
 static void task_wake_up_rt(struct rq *rq, struct task_struct *p)
 {
 	if (!task_running(rq, p) &&
 	    !test_tsk_need_resched(rq->curr) &&
-	    rq->rt.overloaded)
+	    rq->rt.overloaded &&
+	    p->rt.nr_cpus_allowed > 1)
 		push_rt_tasks(rq);
 }
 
#19 lore raw

PATCH v2 2/6 sched: pull only one task during NEWIDLE balancing to limit critical section

In reply to Gregory Haskins

git-id c4acb2c0669c5c5c9b28e9d02a34b5c67edf7092 attempted to limit newidle critical section length by stopping after at least one task was moved. Further investigation has shown that there are other paths nested further inside the algorithm which still remain that allow long latencies to occur with newidle balancing. This patch applies the same technique inside balance_tasks() to limit the duration of this optional balancing operation.

---

 kernel/sched.c |   18 +++++++++++++++++-
 1 files changed, 17 insertions(+), 1 deletions(-)
kernel/sched.c +16 -0
index 6a43c89..df6b447 100644
@@ -2962,6 +2962,16 @@ next:
 	pulled++;
 	rem_load_move -= p->se.load.weight;
 
+#ifdef CONFIG_PREEMPT
+	/*
+	 * NEWIDLE balancing is a source of latency, so preemptible kernels
+	 * will stop after the first task is pulled to minimize the critical
+	 * section.
+	 */
+	if (idle == CPU_NEWLY_IDLE)
+		goto out;
+#endif
+
 	/*
 	 * We only want to steal up to the prescribed amount of weighted load.
 	 */
@@ -3008,9 +3018,15 @@ static int move_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
 				sd, idle, all_pinned, &this_best_prio);
 		class = class->next;
 
+#ifdef CONFIG_PREEMPT
+		/*
+		 * NEWIDLE balancing is a source of latency, so preemptible
+		 * kernels will stop after the first task is pulled to minimize
+		 * the critical section.
+		 */
 		if (idle == CPU_NEWLY_IDLE && this_rq->nr_running)
 			break;
#20 lore raw

PATCH v2 3/6 sched: make double-lock-balance fair

In reply to Gregory Haskins

double_lock balance() currently favors logically lower cpus since they often do not have to release their own lock to acquire a second lock. The result is that logically higher cpus can get starved when there is a lot of pressure on the RQs. This can result in higher latencies on higher cpu-ids.

This patch makes the algorithm more fair by forcing all paths to have to release both locks before acquiring them again. Since callsites to double_lock_balance already consider it a potential preemption/reschedule point, they have the proper logic to recheck for atomicity violations.

---

 kernel/sched.c |   52 +++++++++++++++++++++++++++++++++++++++++++++-------
 1 files changed, 45 insertions(+), 7 deletions(-)
kernel/sched.c +45 -7
index df6b447..850b454 100644
@@ -2782,21 +2782,43 @@ static void double_rq_unlock(struct rq *rq1, struct rq *rq2)
 		__release(rq2->lock);
 }
 
+#ifdef CONFIG_PREEMPT
+
 /*
- * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
+ * fair double_lock_balance: Safely acquires both rq->locks in a fair
+ * way at the expense of forcing extra atomic operations in all
+ * invocations.  This assures that the double_lock is acquired using the
+ * same underlying policy as the spinlock_t on this architecture, which
+ * reduces latency compared to the unfair variant below.  However, it
+ * also adds more overhead and therefore may reduce throughput.
  */
-static int double_lock_balance(struct rq *this_rq, struct rq *busiest)
+static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
+	__releases(this_rq->lock)
+	__acquires(busiest->lock)
+	__acquires(this_rq->lock)
+{
+	spin_unlock(&this_rq->lock);
+	double_rq_lock(this_rq, busiest);
+
+	return 1;
+}
+
+#else
+
+/*
+ * Unfair double_lock_balance: Optimizes throughput at the expense of
+ * latency by eliminating extra atomic operations when the locks are
+ * already in proper order on entry.  This favors lower cpu-ids and will
+ * grant the double lock to lower cpus over higher ids under contention,
+ * regardless of entry order into the function.
+ */
+static inline 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);
-		BUG_ON(1);
-	}
 	if (unlikely(!spin_trylock(&busiest->lock))) {
 		if (busiest < this_rq) {
 			spin_unlock(&this_rq->lock);
@@ -2809,6 +2831,22 @@ static int double_lock_balance(struct rq *this_rq, struct rq *busiest)
 	return ret;
 }
 
+#endif /* CONFIG_PREEMPT */
+
+/*
+ * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
+ */
+static int double_lock_balance(struct rq *this_rq, struct rq *busiest)
+{
+	if (unlikely(!irqs_disabled())) {
+		/* printk() doesn't work good under rq->lock */
+		spin_unlock(&this_rq->lock);
+		BUG_ON(1);
+	}
+
+	return _double_lock_balance(this_rq, busiest);
+}
+
 static void double_unlock_balance(struct rq *this_rq, struct rq *busiest)
 	__releases(busiest->lock)
 {
#34 lore raw

PATCH v2 4/6 sched: add sched_class->needs_post_schedule() member

In reply to Gregory Haskins

We currently run class->post_schedule() outside of the rq->lock, which means that we need to test for the need to post_schedule outside of the lock to avoid a forced reacquistion. This is currently not a problem as we only look at rq->rt.overloaded. However, we want to enhance this going forward to look at more state to reduce the need to post_schedule to a bare minimum set. Therefore, we introduce a new member-func called needs_post_schedule() which tests for the post_schedule condtion without actually performing the work. Therefore it is safe to call this function before the rq->lock is released, because we are guaranteed not to drop the lock at an intermediate point (such as what post_schedule() may do).

We will use this later in the series

---

 include/linux/sched.h |    1 +
 kernel/sched.c        |   10 +++++++++-
 kernel/sched_rt.c     |   24 ++++++++++++++----------
 3 files changed, 24 insertions(+), 11 deletions(-)
include/linux/sched.h +1 -0
index 08a87b5..cf8cd8c 100644
@@ -912,6 +912,7 @@ struct sched_class {
 			      struct rq *busiest, struct sched_domain *sd,
 			      enum cpu_idle_type idle);
 	void (*pre_schedule) (struct rq *this_rq, struct task_struct *task);
+	int (*needs_post_schedule) (struct rq *this_rq);
 	void (*post_schedule) (struct rq *this_rq);
 	void (*task_wake_up) (struct rq *this_rq, struct task_struct *task);
 #endif
kernel/sched.c +9 -1
index 850b454..c5b4459 100644
@@ -2525,6 +2525,14 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
 {
 	struct mm_struct *mm = rq->prev_mm;
 	long prev_state;
+#ifdef CONFIG_SMP
+	int post_schedule = 0;
+
+	if (current->sched_class->needs_post_schedule) {
+		BUG_ON(!current->sched_class->post_schedule);
+		post_schedule = current->sched_class->needs_post_schedule(rq);
+	}
+#endif
 
 	rq->prev_mm = NULL;
 
@@ -2543,7 +2551,7 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
 	finish_arch_switch(prev);
 	finish_lock_switch(rq, prev);
 #ifdef CONFIG_SMP
-	if (current->sched_class->post_schedule)
+	if (post_schedule)
 		current->sched_class->post_schedule(rq);
 #endif
 
kernel/sched_rt.c +14 -10
index 196c024..a3d695b 100644
@@ -1212,20 +1212,23 @@ static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
 		pull_rt_task(rq);
 }
 
+/*
+ * assumes rq->lock is held
+ */
+static int needs_post_schedule_rt(struct rq *rq)
+{
+	return rq->rt.overloaded ? 1 : 0;
+}
+
 static void post_schedule_rt(struct rq *rq)
 {
 	/*
-	 * If we have more than one rt_task queued, then
-	 * see if we can push the other rt_tasks off to other CPUS.
-	 * Note we may release the rq lock, and since
-	 * the lock was owned by prev, we need to release it
-	 * first via finish_lock_switch and then reaquire it here.
+	 * This is only called if needs_post_schedule_rt() indicates that
+	 * we need to push tasks away
 	 */
-	if (unlikely(rq->rt.overloaded)) {
-		spin_lock_irq(&rq->lock);
-		push_rt_tasks(rq);
-		spin_unlock_irq(&rq->lock);
-	}
+	spin_lock_irq(&rq->lock);
+	push_rt_tasks(rq);
+	spin_unlock_irq(&rq->lock);
 }
 
 /*
@@ -1473,6 +1476,7 @@ static const struct sched_class rt_sched_class = {
 	.rq_online              = rq_online_rt,
 	.rq_offline             = rq_offline_rt,
 	.pre_schedule		= pre_schedule_rt,
+	.needs_post_schedule	= needs_post_schedule_rt,
 	.post_schedule		= post_schedule_rt,
 	.task_wake_up		= task_wake_up_rt,
 	.switched_from		= switched_from_rt,
#35 lore raw

PATCH v2 5/6 plist: fix PLIST_NODE_INIT to work with debug enabled

In reply to Gregory Haskins

It seems that PLIST_NODE_INIT breaks if used and DEBUG_PI_LIST is defined. Since there are no current users of PLIST_NODE_INIT, this has gone undetected. This patch fixes the build issue that enables the DEBUG_PI_LIST later in the series when we use it in init_task.h

---

 include/linux/plist.h |    9 ++++++---
 1 files changed, 6 insertions(+), 3 deletions(-)
include/linux/plist.h +6 -3
index 85de2f0..2b65483 100644
@@ -96,6 +96,10 @@ struct plist_node {
 # define PLIST_HEAD_LOCK_INIT(_lock)
 #endif
 
+#define _PLIST_HEAD_INIT(head)				\
+	.prio_list = LIST_HEAD_INIT((head).prio_list),	\
+	.node_list = LIST_HEAD_INIT((head).node_list)
+
 /**
  * PLIST_HEAD_INIT - static struct plist_head initializer
  * @head:	struct plist_head variable name
@@ -103,8 +107,7 @@ struct plist_node {
  */
 #define PLIST_HEAD_INIT(head, _lock)			\
 {							\
-	.prio_list = LIST_HEAD_INIT((head).prio_list),	\
-	.node_list = LIST_HEAD_INIT((head).node_list),	\
+	_PLIST_HEAD_INIT(head),                         \
 	PLIST_HEAD_LOCK_INIT(&(_lock))			\
 }
 
@@ -116,7 +119,7 @@ struct plist_node {
 #define PLIST_NODE_INIT(node, __prio)			\
 {							\
 	.prio  = (__prio),				\
-	.plist = PLIST_HEAD_INIT((node).plist, NULL),	\
+	.plist = { _PLIST_HEAD_INIT((node).plist) }, 	\
 }
 
 /**
#36 lore raw

PATCH v2 6/6 sched: create "pushable_tasks" list to limit pushing to one attempt

In reply to Gregory Haskins

The RT scheduler employs a "push/pull" design to actively balance tasks within the system (on a per disjoint cpuset basis). When a task is awoken, it is immediately determined if there are any lower priority cpus which should be preempted. This is opposed to the way normal SCHED_OTHER tasks behave, which will wait for a periodic rebalancing operation to occur before spreading out load.

When a particular RQ has more than 1 active RT task, it is said to be in an "overloaded" state. Once this occurs, the system enters the active balancing mode, where it will try to push the task away, or persuade a different cpu to pull it over. The system will stay in this state until the system falls back below the <= 1 queued RT task per RQ.

However, the current implementation suffers from a limitation in the push logic. Once overloaded, all tasks (other than current) on the RQ are analyzed on every push operation, even if it was previously unpushable (due to affinity, etc). Whats more, the operation stops at the first task that is unpushable and will not look at items lower in the queue. This causes two problems:

1) We can have the same tasks analyzed over and over again during each push, which extends out the fast path in the scheduler for no gain. Consider a RQ that has dozens of tasks that are bound to a core. Each one of those tasks will be encountered and skipped for each push operation while they are queued.

2) There may be lower-priority tasks under the unpushable task that could have been successfully pushed, but will never be considered until either the unpushable task is cleared, or a pull operation succeeds. The net result is a potential latency source for mid priority tasks.

This patch aims to rectify these two conditions by introducing a new priority sorted list: "pushable_tasks". A task is added to the list each time a task is activated or preempted. It is removed from the list any time it is deactivated, made current, or fails to push.

This works because a task only needs to be attempted to push once. After an initial failure to push, the other cpus will eventually try to pull the task when the conditions are proper. This also solves the problem that we don't completely analyze all tasks due to encountering an unpushable tasks. Now every task will have a push attempted (when appropriate).

This reduces latency both by shorting the critical section of the rq->lock for certain workloads, and by making sure the algorithm considers all eligible tasks in the system.

---

 include/linux/init_task.h |    1 
 include/linux/sched.h     |    1 
 kernel/sched.c            |    4 ++
 kernel/sched_rt.c         |  111 +++++++++++++++++++++++++++++++++++++++++----
 4 files changed, 107 insertions(+), 10 deletions(-)
include/linux/init_task.h +1 -0
index 021d8e7..7f910f4 100644
@@ -140,6 +140,7 @@ extern struct group_info init_groups;
 		.nr_cpus_allowed = NR_CPUS,				\
 	},								\
 	.tasks		= LIST_HEAD_INIT(tsk.tasks),			\
+	.pushable_tasks = PLIST_NODE_INIT(tsk.pushable_tasks, MAX_PRIO), \
 	.ptraced	= LIST_HEAD_INIT(tsk.ptraced),			\
 	.ptrace_entry	= LIST_HEAD_INIT(tsk.ptrace_entry),		\
 	.real_parent	= &tsk,						\
include/linux/sched.h +1 -0
index cf8cd8c..3480c8a 100644
@@ -1078,6 +1078,7 @@ struct task_struct {
 #endif
 
 	struct list_head tasks;
+	struct plist_node pushable_tasks;
 
 	struct mm_struct *mm, *active_mm;
 
kernel/sched.c +4 -0
index c5b4459..d0b189d 100644
@@ -447,6 +447,7 @@ struct rt_rq {
 #ifdef CONFIG_SMP
 	unsigned long rt_nr_migratory;
 	int overloaded;
+	struct plist_head pushable_tasks;
 #endif
 	int rt_throttled;
 	u64 rt_time;
@@ -2383,6 +2384,8 @@ void sched_fork(struct task_struct *p, int clone_flags)
 	/* Want to start with kernel preemption disabled. */
 	task_thread_info(p)->preempt_count = 1;
 #endif
+	plist_node_init(&p->pushable_tasks, MAX_PRIO);
+
 	put_cpu();
 }
 
@@ -7905,6 +7908,7 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
 #ifdef CONFIG_SMP
 	rt_rq->rt_nr_migratory = 0;
 	rt_rq->overloaded = 0;
+	plist_head_init(&rq->rt.pushable_tasks, &rq->lock);
 #endif
 
 	rt_rq->rt_time = 0;
kernel/sched_rt.c +101 -10

220 lines not on this page · raw message

#38 lore raw

Re: [PATCH v2 0/6] sched: misc rt fixes for tip/sched/devel (was: Series short description)

In reply to Gregory Haskins
Quoted 10 lines · Gregory Haskins

Hi Ingo,

The following repositories

git://git.kernel.org/pub/scm/linux/kernel/git/ghaskins/linux-2.6-hacks.git tip/sched/devel/rtbalance

ftp://ftp.novell.com/dev/ghaskins/tip-rt-fixes.tar.bz2

apply to tip/sched/devel to pick up fixes for the RT scheduler.

[ It would help if I remembered to rename the default subject ;) ]

I just wanted to add that these are not urgent fixes. .28 at the earliest. Thanks

-Greg

Quoted 50 lines

[
Changelog:

v2:
*) predicated newidle and double_lock changes on
CONFIG_PREEMPT to address a concern by Nick Piggin

*) fixed a build issue when DEBUG_PI_LIST is defined

v1:
*) initial release
]

These patches were developed in the interest of shorting latencies in PREEMPT_RT, but they apply to the mainline scheduler as well, so I am offering them here first.

This has been tested under both 26.3-rt3 and tip/sched/devel on x86_64 for both CONFIG_SMP and !CONFIG_SMP.

Comments/bug-fixes welcome!

Regards,
-Greg

---

Gregory Haskins (6):
sched: create "pushable_tasks" list to limit pushing to one attempt
plist: fix PLIST_NODE_INIT to work with debug enabled
sched: add sched_class->needs_post_schedule() member
sched: make double-lock-balance fair
sched: pull only one task during NEWIDLE balancing to limit critical section
sched: only try to push a task on wakeup if it is migratable

 include/linux/init_task.h |    1 
 include/linux/plist.h     |    9 ++-
 include/linux/sched.h     |    2 +
 kernel/sched.c            |   84 ++++++++++++++++++++++++---
 kernel/sched_rt.c         |  139 ++++++++++++++++++++++++++++++++++++++-------
 5 files changed, 202 insertions(+), 33 deletions(-)

--
To unsubscribe from this list: send the line "unsubscribe linux-rt-users" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#11 lore raw

Re: [PATCH 3/5] sched: make double-lock-balance fair

In reply to Gregory Haskins
Quoted 53 lines · Gregory Haskins
Quoted 43 lines · Nick Piggin
Quoted 42 lines · Gregory Haskins

double_lock balance() currently favors logically lower cpus since they often do not have to release their own lock to acquire a second lock. The result is that logically higher cpus can get starved when there is a lot of pressure on the RQs. This can result in higher latencies on higher cpu-ids.

This patch makes the algorithm more fair by forcing all paths to have to release both locks before acquiring them again. Since callsites to double_lock_balance already consider it a potential preemption/reschedule point, they have the proper logic to recheck for atomicity violations.

---

 kernel/sched.c |   17 +++++------------
 1 files changed, 5 insertions(+), 12 deletions(-)
kernel/sched.c +0 -11
index 6e0bde6..b7326cd 100644
@@ -2790,23 +2790,16 @@ static int double_lock_balance(struct rq
 *this_rq, struct rq *busiest) __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);
 		BUG_ON(1);
 	}
-	if (unlikely(!spin_trylock(&busiest->lock))) {
-		if (busiest < this_rq) {
-			spin_unlock(&this_rq->lock);
-			spin_lock(&busiest->lock);
-			spin_lock_nested(&this_rq->lock, SINGLE_DEPTH_NESTING);
-			ret = 1;
-		} else
-			spin_lock_nested(&busiest->lock, SINGLE_DEPTH_NESTING);
-	}
Quoted 8 lines

kernel/sched.c static int double_lock_balance(struct rq · line 2800

Quoted 4 lines
kernel/sched.c +3 -1
-	return ret;
+
+	spin_unlock(&this_rq->lock);
+	double_rq_lock(this_rq, busiest);

Rather than adding the extra atomic operation, can't you just put this into the unlikely spin_trylock failure path rather than the unfair logic there?

Quoted 4 lines

The trick is that we *must* first release this_rq before proceeding or the new proposal doesn't work as intended. This patch effectively breaks up the this_rq->lock critical section evenly across all CPUs as if it hit the case common for higher cpus.

I don't exactly see why my proposal would introduce any more latency, because we only trylock while holding the existing lock -- this is will only ever add a small ~constant time to the critical section, regardless of whether it is a high or low CPU runqueue.

Quoted 39 lines

This modification decreased
latency by over 800% (went from > 400us to < 50us) on cpus 6 and 7 in my 8-way box namely because they were not forced to wait for all the other lower cores to finish, but rather completions of double_lock_balance were handled in true FIFO w.r.t. to other calls to double_lock_balance(). It has to do with the positioning within your FIFO ticket locks (though even if ticket locks are not present on a given architecture we should still see an improvement.)

When a low cpu wants to double lock, it tends to hold this_rq and gets in line for busiest_rq with no bearing on how long it held this_rq. Therefore the following scenario can occur:

cpu 0 cpu N
----------------------------------
rq[0] locked
..
..
..
double_lock(N, 0)
rq[N] released
blocked on rq[0]
..
..
..
..
double_lock(0, N)
rq[N] locked
double_lock returns
..
..
..
..
rq[0] released rq[0] locked

                                  double_lock returns
                                  ...
                                  ...
                                  ...
Quoted 7 lines

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

So double lock acquisition favors the lower cpus unfairly. They will always win, even if they were not first. Now with the combination of my patch plus your ticket locks, entry into the double lock becomes FIFO because the "blocked on rq[0]" would have inserted it in the time-ordered head of rq[0].

Right, but I don't think it is particularly wrong to allow a given CPU to double_lock_balance ahead of another guy if we're already holding the lock. _So long as_ the lock we are trying to acquire is uncontended, and we don't introduce this skewed unfairness due to lower CPUs being allowed to hold their lower lock while higher CPUs have to release their lock and first queue on the lower.

The difference is that with my patch, there is a small window where the guy who asks for the double lock first will go through second. I don't think this really adds a fundamental amount of latency, and the performance benefit should not be ignored.

Linux's traditional and I suppose much largest user base does not require realtime or really strict fairness, so IMO it is always questionable to make changes like this.

Quoted 4 lines

The later call to double_lock(0, N)
performed by cpu0 would be forced to queue up behind cpuN trying to reacquire its own lock.

Quoted 8 lines

Effectively, double_lock_balance becomes as fair as the underlying spinlock governing the RQ. If we have ticket locks, double_lock_balance is FIFO. Lack of ticket locks means we have arbitrary fairness. And lack of this patch means we have favor for the lower cpus.

To your point about the extra atomic ops: Perhaps I should predicate this change on CONFIG_PREEMPT so as to not slow down mainline where throughput is more valued.

I am happy with that. Actually, I think we should have a CONFIG_ to trade off throughput for latency, and have that config select PREEMPT as well as enable small misc changes like this one and the tlb flushing latency reduction. But for the moment, CONFIG_PREEMPT is the traditional placeholder for such a config option.

#5 lore raw

Re: [PATCH 2/5] sched: pull only one task during NEWIDLE balancing to limit critical section

In reply to Gregory Haskins
Quoted 13 lines · Gregory Haskins
Quoted 12 lines · Nick Piggin
Quoted 10 lines · Gregory Haskins

git-id c4acb2c0669c5c5c9b28e9d02a34b5c67edf7092 attempted to limit newidle critical section length by stopping after at least one task was moved. Further investigation has shown that there are other paths nested further inside the algorithm which still remain that allow long latencies to occur with newidle balancing. This patch applies the same technique inside balance_tasks() to limit the duration of this optional balancing operation.

Quoted 8 lines
Quoted 4 lines

Hmm, this (andc4acb2c0669c5c5c9b28e9d02a34b5c67edf7092) still could increase the amount of work to do significantly for workloads where the CPU is going idle and pulling tasks over frequently. I don't really like either of them too much.

I had a feeling you may object to this patch based on your comments on the first one. Thats why I CC'd you so you wouldnt think I was trying to sneak something past ;)

Appreciated.

Quoted 10 lines
Quoted 2 lines

Maybe increasing the limit would effectively amortize most of the problem (say, limit to move 16 tasks at most).

The problem I was seeing was that even moving 2 was too many in the ftraces traces I looked at. I think the idea of making a variable limit (set via a sysctl, etc) here is a good one, but I would recommend we have the default be "1" for CONFIG_PREEMPT (or at least
CONFIG_PREEMPT_RT) based on what I know right now. I know last time
you objected to any kind of special cases for the preemptible kernels, but I think this is a good compromise. Would this be acceptable?

Well I _prefer_ not to have a special case for preemptible kernels, but we already have similar arbitrary kind of changes like in tlb flushing, so...

I understand and accept there are some places where fundamentally you have to trade latency for throughput, so at some point we have to have a config and/or sysctl for that.

I'm surprised 2 is too much but 1 is OK. Seems pretty fragile to me. Are you just running insane tests that load up the runqueues heaps and tests latency? -rt users will have to understand that some algorithms scale linearly or so with the number of a particular resource allocated, so they aren't going to get a constant low latency under arbitrary conditions.

FWIW, if you haven't already, then for -rt you might want to look at a more advanced data structure than simple run ordered list for moving tasks from one rq to the other. A simple one I was looking at is a time ordered list to pull the most cache cold tasks (and thus we can stop searching when we encounter the first cache hot task, in situations where it is appropriate, etc).

Anyway... yeah I'm OK with this if it is under a config option.

maintainer
#21 lore raw

Re: [PATCH v2 3/6] sched: make double-lock-balance fair

In reply to Gregory Haskins
Quoted 37 lines · Gregory Haskins

double_lock balance() currently favors logically lower cpus since they often do not have to release their own lock to acquire a second lock. The result is that logically higher cpus can get starved when there is a lot of pressure on the RQs. This can result in higher latencies on higher cpu-ids.

This patch makes the algorithm more fair by forcing all paths to have to release both locks before acquiring them again. Since callsites to double_lock_balance already consider it a potential preemption/reschedule point, they have the proper logic to recheck for atomicity violations.

---

 kernel/sched.c |   52 +++++++++++++++++++++++++++++++++++++++++++++-------
 1 files changed, 45 insertions(+), 7 deletions(-)
kernel/sched.c +8 -2
index df6b447..850b454 100644
@@ -2782,21 +2782,43 @@ static void double_rq_unlock(struct rq *rq1, struct rq *rq2)
 		__release(rq2->lock);
 }
 
+#ifdef CONFIG_PREEMPT
+
 /*
- * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
+ * fair double_lock_balance: Safely acquires both rq->locks in a fair
+ * way at the expense of forcing extra atomic operations in all
+ * invocations.  This assures that the double_lock is acquired using the
+ * same underlying policy as the spinlock_t on this architecture, which
+ * reduces latency compared to the unfair variant below.  However, it
+ * also adds more overhead and therefore may reduce throughput.
  */
-static int double_lock_balance(struct rq *this_rq, struct rq *busiest)

kernel/sched.c static void double_rq_unlock(struct rq *rq1, struct rq *rq2) · line 2804

Quoted 10 lines
kernel/sched.c +10 -0
+static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
+	__releases(this_rq->lock)
+	__acquires(busiest->lock)
+	__acquires(this_rq->lock)
+{
+	spin_unlock(&this_rq->lock);
+	double_rq_lock(this_rq, busiest);
+
+	return 1;
+}

Right - so to belabour Nick's point:

  if (!spin_trylock(&busiest->lock)) {
    spin_unlock(&this_rq->lock);
    double_rq_lock(this_rq, busiest);
  }

might unfairly treat someone who is waiting on this_rq if I understand it right?

I suppose one could then write it like:

  if (spin_is_contended(&this_rq->lock) || !spin_trylock(&busiest->lock)) {
    spin_unlock(&this_rq->lock);
    double_rq_lock(this_rq, busiest);
  }

But, I'm not sure that's worth the effort at that point..

Anyway - I think all this is utterly defeated on CONFIG_PREEMPT by the spin with IRQs enabled logic in kernel/spinlock.c.

Making this an -rt only patch...

maintainer
#22 lore raw

Re: [PATCH v2 3/6] sched: make double-lock-balance fair

Quoted 66 lines · Peter Zijlstra
Quoted 37 lines · Gregory Haskins

double_lock balance() currently favors logically lower cpus since they often do not have to release their own lock to acquire a second lock. The result is that logically higher cpus can get starved when there is a lot of pressure on the RQs. This can result in higher latencies on higher cpu-ids.

This patch makes the algorithm more fair by forcing all paths to have to release both locks before acquiring them again. Since callsites to double_lock_balance already consider it a potential preemption/reschedule point, they have the proper logic to recheck for atomicity violations.

---

 kernel/sched.c |   52 +++++++++++++++++++++++++++++++++++++++++++++-------
 1 files changed, 45 insertions(+), 7 deletions(-)
kernel/sched.c +8 -2
index df6b447..850b454 100644
@@ -2782,21 +2782,43 @@ static void double_rq_unlock(struct rq *rq1, struct rq *rq2)
 		__release(rq2->lock);
 }
 
+#ifdef CONFIG_PREEMPT
+
 /*
- * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
+ * fair double_lock_balance: Safely acquires both rq->locks in a fair
+ * way at the expense of forcing extra atomic operations in all
+ * invocations.  This assures that the double_lock is acquired using the
+ * same underlying policy as the spinlock_t on this architecture, which
+ * reduces latency compared to the unfair variant below.  However, it
+ * also adds more overhead and therefore may reduce throughput.
  */
-static int double_lock_balance(struct rq *this_rq, struct rq *busiest)

kernel/sched.c static void double_rq_unlock(struct rq *rq1, struct rq *rq2) · line 2804

Quoted 10 lines
kernel/sched.c +10 -0
+static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
+	__releases(this_rq->lock)
+	__acquires(busiest->lock)
+	__acquires(this_rq->lock)
+{
+	spin_unlock(&this_rq->lock);
+	double_rq_lock(this_rq, busiest);
+
+	return 1;
+}

Right - so to belabour Nick's point:

  if (!spin_trylock(&busiest->lock)) {
    spin_unlock(&this_rq->lock);
    double_rq_lock(this_rq, busiest);
  }

might unfairly treat someone who is waiting on this_rq if I understand it right?

I suppose one could then write it like:

  if (spin_is_contended(&this_rq->lock) || !spin_trylock(&busiest->lock)) {
    spin_unlock(&this_rq->lock);
    double_rq_lock(this_rq, busiest);
  }
Quoted 6 lines

But, I'm not sure that's worth the effort at that point..

Anyway - I think all this is utterly defeated on CONFIG_PREEMPT by the spin with IRQs enabled logic in kernel/spinlock.c.

Making this an -rt only patch...

n/m my last bit, that's only for spin_lock_irq*() which we're not using here, so yes, it ought to work.

maintainer Acked-by on the v2 series
#39 lore raw

Re: [PATCH v2 0/6] Series short description

In reply to Gregory Haskins
Quoted 23 lines · Gregory Haskins

Hi Ingo,

The following repositories

git://git.kernel.org/pub/scm/linux/kernel/git/ghaskins/linux-2.6-hacks.git tip/sched/devel/rtbalance

ftp://ftp.novell.com/dev/ghaskins/tip-rt-fixes.tar.bz2

apply to tip/sched/devel to pick up fixes for the RT scheduler.

[
Changelog:

v2:
*) predicated newidle and double_lock changes on
CONFIG_PREEMPT to address a concern by Nick Piggin

*) fixed a build issue when DEBUG_PI_LIST is defined

v1:
*) initial release
]

Quoted 8 lines

These patches were developed in the interest of shorting latencies in PREEMPT_RT, but they apply to the mainline scheduler as well, so I am offering them here first.

This has been tested under both 26.3-rt3 and tip/sched/devel on x86_64 for both CONFIG_SMP and !CONFIG_SMP.

Comments/bug-fixes welcome!

Looks good to me,

Ingo please consider.

Quoted 19 lines

---

Gregory Haskins (6):
sched: create "pushable_tasks" list to limit pushing to one attempt
plist: fix PLIST_NODE_INIT to work with debug enabled
sched: add sched_class->needs_post_schedule() member
sched: make double-lock-balance fair
sched: pull only one task during NEWIDLE balancing to limit critical section
sched: only try to push a task on wakeup if it is migratable

 include/linux/init_task.h |    1 
 include/linux/plist.h     |    9 ++-
 include/linux/sched.h     |    2 +
 kernel/sched.c            |   84 ++++++++++++++++++++++++---
 kernel/sched_rt.c         |  139 ++++++++++++++++++++++++++++++++++++++-------
 5 files changed, 202 insertions(+), 33 deletions(-)
#23 lore raw

Re: [PATCH v2 3/6] sched: make double-lock-balance fair

In reply to Peter Zijlstra
Quoted 59 lines · Peter Zijlstra
Quoted 37 lines · Gregory Haskins

double_lock balance() currently favors logically lower cpus since they often do not have to release their own lock to acquire a second lock. The result is that logically higher cpus can get starved when there is a lot of pressure on the RQs. This can result in higher latencies on higher cpu-ids.

This patch makes the algorithm more fair by forcing all paths to have to release both locks before acquiring them again. Since callsites to double_lock_balance already consider it a potential preemption/reschedule point, they have the proper logic to recheck for atomicity violations.

---

 kernel/sched.c |   52 +++++++++++++++++++++++++++++++++++++++++++++-------
 1 files changed, 45 insertions(+), 7 deletions(-)
kernel/sched.c +8 -2
index df6b447..850b454 100644
@@ -2782,21 +2782,43 @@ static void double_rq_unlock(struct rq *rq1, struct rq *rq2)
 		__release(rq2->lock);
 }
 
+#ifdef CONFIG_PREEMPT
+
 /*
- * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
+ * fair double_lock_balance: Safely acquires both rq->locks in a fair
+ * way at the expense of forcing extra atomic operations in all
+ * invocations.  This assures that the double_lock is acquired using the
+ * same underlying policy as the spinlock_t on this architecture, which
+ * reduces latency compared to the unfair variant below.  However, it
+ * also adds more overhead and therefore may reduce throughput.
  */
-static int double_lock_balance(struct rq *this_rq, struct rq *busiest)

kernel/sched.c static void double_rq_unlock(struct rq *rq1, struct rq *rq2) · line 2804

Quoted 10 lines
kernel/sched.c +10 -0
+static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
+	__releases(this_rq->lock)
+	__acquires(busiest->lock)
+	__acquires(this_rq->lock)
+{
+	spin_unlock(&this_rq->lock);
+	double_rq_lock(this_rq, busiest);
+
+	return 1;
+}

Right - so to belabour Nick's point:

  if (!spin_trylock(&busiest->lock)) {
    spin_unlock(&this_rq->lock);
    double_rq_lock(this_rq, busiest);
  }

might unfairly treat someone who is waiting on this_rq if I understand it right?

Quoted 8 lines

I suppose one could then write it like:

  if (spin_is_contended(&this_rq->lock) || !spin_trylock(&busiest->lock)) {
    spin_unlock(&this_rq->lock);
    double_rq_lock(this_rq, busiest);
  }

But, I'm not sure that's worth the effort at that point..

Yeah, that could work, but hmm it might cause 2 cache coherency transactions anyway even in the fastpath, so it might even be slower than just unlocking unconditionally and taking both locks :(

Quoted 4 lines

Anyway - I think all this is utterly defeated on CONFIG_PREEMPT by the spin with IRQs enabled logic in kernel/spinlock.c.

Making this an -rt only patch...

Hmm, and also on x86 with ticket locks we don't spin with preempt or interrupts enabled any more (although we still do of course on other architectures)

maintainer
#24 lore raw

Re: [PATCH v2 3/6] sched: make double-lock-balance fair

Quoted 9 lines · Nick Piggin
Quoted 7 lines · Peter Zijlstra

I suppose one could then write it like:

  if (spin_is_contended(&this_rq->lock) || !spin_trylock(&busiest->lock)) {
    spin_unlock(&this_rq->lock);
    double_rq_lock(this_rq, busiest);
  }
Quoted 5 lines
Quoted 1 line

But, I'm not sure that's worth the effort at that point..

Yeah, that could work, but hmm it might cause 2 cache coherency transactions anyway even in the fastpath, so it might even be slower than just unlocking unconditionally and taking both locks :(

right,..

Quoted 8 lines
Quoted 4 lines

Anyway - I think all this is utterly defeated on CONFIG_PREEMPT by the spin with IRQs enabled logic in kernel/spinlock.c.

Making this an -rt only patch...

Hmm, and also on x86 with ticket locks we don't spin with preempt or interrupts enabled any more (although we still do of course on other architectures)

Aah, we don't do CONFIG_GENERIC_LOCKBREAK anymore?

Does it make sense to make this _double_lock_balance() thing depend on that too?

#25 lore raw

Re: [PATCH v2 3/6] sched: make double-lock-balance fair

Quoted 10 lines · Peter Zijlstra
Quoted 9 lines · Nick Piggin
Quoted 7 lines · Peter Zijlstra

I suppose one could then write it like:

  if (spin_is_contended(&this_rq->lock) || !spin_trylock(&busiest->lock)) {
    spin_unlock(&this_rq->lock);
    double_rq_lock(this_rq, busiest);
  }
Quoted 7 lines
Quoted 5 lines
Quoted 1 line

But, I'm not sure that's worth the effort at that point..

Yeah, that could work, but hmm it might cause 2 cache coherency transactions anyway even in the fastpath, so it might even be slower than just unlocking unconditionally and taking both locks :(

right,..

Although I guess we could prefetch it... But OTOH I don't know exactly what Intel CPUs do with prefetch -- I don't think they have a prefetchw.

I would support your idea if it is faster, of course ;)

Quoted 10 lines
Quoted 8 lines
Quoted 4 lines

Anyway - I think all this is utterly defeated on CONFIG_PREEMPT by the spin with IRQs enabled logic in kernel/spinlock.c.

Making this an -rt only patch...

Hmm, and also on x86 with ticket locks we don't spin with preempt or interrupts enabled any more (although we still do of course on other architectures)

Aah, we don't do CONFIG_GENERIC_LOCKBREAK anymore?

Right. My reasoning said that if our critical sections are short enough, *and not subject to starvation*, then we should not really need it, and at any rate often it is just luck if it helps because in other cases we might be taking the lock under an irq save region so it wouldn't help there...

Quoted 2 lines

Does it make sense to make this _double_lock_balance() thing depend on that too?

Hmm, you might have a good point there. Greg?

BTW. I wonder about other architectures that are of interest to -rt? Like mips or arm perhaps... Any plans to implement ticket locks on those, or do they not tend to be used in SMP configurations on -rt yte?

#26 lore raw

Re: [PATCH v2 3/6] sched: make double-lock-balance fair

Quoted 9 lines · Nick Piggin
Quoted 2 lines · Peter Zijlstra

Does it make sense to make this _double_lock_balance() thing depend on that too?

Hmm, you might have a good point there. Greg?

BTW. I wonder about other architectures that are of interest to -rt? Like mips or arm perhaps... Any plans to implement ticket locks on those, or do they not tend to be used in SMP configurations on -rt yte?

Oh, or maybe I guess again: -rt might be using Greg's generic ticket lock implementation?

maintainer
#28 lore raw

Re: [PATCH v2 3/6] sched: make double-lock-balance fair

In reply to Nick Piggin
Quoted 3 lines · Nick Piggin

BTW. I wonder about other architectures that are of interest to -rt? Like mips or arm perhaps... Any plans to implement ticket locks on those, or do they not tend to be used in SMP configurations on -rt yte?

I think both are starting to show more and more SMP machines, so yes, eventually we'll want ticket locks for them too.

That said, I'm not aware of anyone working on it - I suppose we could poke the regular arch maintainers.. Ralf, Russell ?

#29 lore raw

Re: [PATCH v2 3/6] sched: make double-lock-balance fair

Quoted 11 lines · Peter Zijlstra
Quoted 3 lines · Nick Piggin

BTW. I wonder about other architectures that are of interest to -rt? Like mips or arm perhaps... Any plans to implement ticket locks on those, or do they not tend to be used in SMP configurations on -rt yte?

I think both are starting to show more and more SMP machines, so yes, eventually we'll want ticket locks for them too.

That said, I'm not aware of anyone working on it - I suppose we could poke the regular arch maintainers.. Ralf, Russell ?

I've no idea; SMP on ARM as far as I've been involved has been silent for well over a year with very little visible interest from anyone. That's situation normal for things that "just work" though.

Signature · 3 lines
Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:
#12 lore raw

Re: [PATCH 3/5] sched: make double-lock-balance fair

In reply to Nick Piggin
Quoted 63 lines · Nick Piggin
Quoted 55 lines · Gregory Haskins
Quoted 44 lines · Nick Piggin
Quoted 42 lines · Gregory Haskins

double_lock balance() currently favors logically lower cpus since they often do not have to release their own lock to acquire a second lock. The result is that logically higher cpus can get starved when there is a lot of pressure on the RQs. This can result in higher latencies on higher cpu-ids.

This patch makes the algorithm more fair by forcing all paths to have to release both locks before acquiring them again. Since callsites to double_lock_balance already consider it a potential preemption/reschedule point, they have the proper logic to recheck for atomicity violations.

---

 kernel/sched.c |   17 +++++------------
 1 files changed, 5 insertions(+), 12 deletions(-)
kernel/sched.c +0 -11
index 6e0bde6..b7326cd 100644
@@ -2790,23 +2790,16 @@ static int double_lock_balance(struct rq
 *this_rq, struct rq *busiest) __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);
 		BUG_ON(1);
 	}
-	if (unlikely(!spin_trylock(&busiest->lock))) {
-		if (busiest < this_rq) {
-			spin_unlock(&this_rq->lock);
-			spin_lock(&busiest->lock);
-			spin_lock_nested(&this_rq->lock, SINGLE_DEPTH_NESTING);
-			ret = 1;
-		} else
-			spin_lock_nested(&busiest->lock, SINGLE_DEPTH_NESTING);
-	}
Quoted 9 lines

kernel/sched.c static int double_lock_balance(struct rq · line 2801

Quoted 5 lines
kernel/sched.c +3 -1
-	return ret;
+
+	spin_unlock(&this_rq->lock);
+	double_rq_lock(this_rq, busiest);
 

Rather than adding the extra atomic operation, can't you just put this into the unlikely spin_trylock failure path rather than the unfair logic there?

Quoted 5 lines

The trick is that we *must* first release this_rq before proceeding or the new proposal doesn't work as intended. This patch effectively breaks up the this_rq->lock critical section evenly across all CPUs as if it hit the case common for higher cpus.

Quoted 5 lines

I don't exactly see why my proposal would introduce any more latency, because we only trylock while holding the existing lock -- this is will only ever add a small ~constant time to the critical section, regardless of whether it is a high or low CPU runqueue.

Its because we are trying to create a break in the critical section of this_rq->lock, not improve the acquisition of busiest->lock. So whether you do spin_lock or spin_trylock on busiest does not matter. Busiest will not be contended in the case that I am concerned with. If you use my example below: rq[N] will not be contended because cpuN is blocked on rq[0] after already having released rq[N]. So its the contention against this_rq that is the problem.

Or am I missing your point completely?

Quoted 50 lines
Quoted 41 lines

This modification decreased
latency by over 800% (went from > 400us to < 50us) on cpus 6 and 7 in my 8-way box namely because they were not forced to wait for all the other lower cores to finish, but rather completions of double_lock_balance were handled in true FIFO w.r.t. to other calls to double_lock_balance(). It has to do with the positioning within your FIFO ticket locks (though even if ticket locks are not present on a given architecture we should still see an improvement.)

When a low cpu wants to double lock, it tends to hold this_rq and gets in line for busiest_rq with no bearing on how long it held this_rq. Therefore the following scenario can occur:

cpu 0 cpu N
----------------------------------
rq[0] locked
..
..
..
double_lock(N, 0)
rq[N] released
blocked on rq[0]
..
..
..
..
double_lock(0, N)
rq[N] locked
double_lock returns
..
..
..
..
rq[0] released rq[0] locked

                                  double_lock returns
                                  ...
                                  ...
                                  ...
Quoted 8 lines

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

So double lock acquisition favors the lower cpus unfairly. They will always win, even if they were not first. Now with the combination of my patch plus your ticket locks, entry into the double lock becomes FIFO because the "blocked on rq[0]" would have inserted it in the time-ordered head of rq[0].

Quoted 3 lines

Right, but I don't think it is particularly wrong to allow a given CPU to double_lock_balance ahead of another guy if we're already holding the lock.

Its not "wrong". Its just a latency source ;)

Quoted 5 lines

_So long as_ the lock we are trying to acquire is uncontended,
and we don't introduce this skewed unfairness due to lower CPUs being allowed to hold their lower lock while higher CPUs have to release their lock and first queue on the lower.

Quoted 9 lines

The difference is that with my patch, there is a small window where the guy who asks for the double lock first will go through second. I don't think this really adds a fundamental amount of latency, and the performance benefit should not be ignored.

Linux's traditional and I suppose much largest user base does not require realtime or really strict fairness, so IMO it is always questionable to make changes like this.

Please take a look at the v2 series that I sent out yesterday. I have now predicated this on CONFIG_PREEMPT, per your comments.

-Greg

#6 lore raw

Re: [PATCH 2/5] sched: pull only one task during NEWIDLE balancing to limit critical section

In reply to Nick Piggin
Quoted 47 lines · Nick Piggin
Quoted 15 lines · Gregory Haskins
Quoted 13 lines · Nick Piggin
Quoted 11 lines · Gregory Haskins

git-id c4acb2c0669c5c5c9b28e9d02a34b5c67edf7092 attempted to limit newidle critical section length by stopping after at least one task was moved. Further investigation has shown that there are other paths nested further inside the algorithm which still remain that allow long latencies to occur with newidle balancing. This patch applies the same technique inside balance_tasks() to limit the duration of this optional balancing operation.

Quoted 9 lines
Quoted 5 lines

Hmm, this (andc4acb2c0669c5c5c9b28e9d02a34b5c67edf7092) still could increase the amount of work to do significantly for workloads where the CPU is going idle and pulling tasks over frequently. I don't really like either of them too much.

I had a feeling you may object to this patch based on your comments on the first one. Thats why I CC'd you so you wouldnt think I was trying to sneak something past ;)

Appreciated.

Quoted 11 lines
Quoted 3 lines

Maybe increasing the limit would effectively amortize most of the problem (say, limit to move 16 tasks at most).

The problem I was seeing was that even moving 2 was too many in the ftraces traces I looked at. I think the idea of making a variable limit (set via a sysctl, etc) here is a good one, but I would recommend we have the default be "1" for CONFIG_PREEMPT (or at least
CONFIG_PREEMPT_RT) based on what I know right now. I know last time
you objected to any kind of special cases for the preemptible kernels, but I think this is a good compromise. Would this be acceptable?

Well I _prefer_ not to have a special case for preemptible kernels, but we already have similar arbitrary kind of changes like in tlb flushing, so...

Quoted 5 lines

I understand and accept there are some places where fundamentally you have to trade latency for throughput, so at some point we have to have a config and/or sysctl for that.

I'm surprised 2 is too much but 1 is OK. Seems pretty fragile to me.

Its not that 1 is magically "ok". Its simply that newidle balancing hurts latency, and 1 is the minimum to pull to reasonably reduce the critical section. I already check if we NEEDS_RESCHED before taking the rq->lock in newidle, so waiting for one task to pull is the first opportunity I have to end the section as quickly as possible. It would be nice if I could just keep going if I could detect whether there was not any real contention. Let me give this angle some more thought.

Quoted 7 lines

Are
you just running insane tests that load up the runqueues heaps and tests latency? -rt users will have to understand that some algorithms scale linearly or so with the number of a particular resource allocated, so they aren't going to get a constant low latency under arbitrary conditions.

Quoted 7 lines

FWIW, if you haven't already, then for -rt you might want to look at a more advanced data structure than simple run ordered list for moving tasks from one rq to the other. A simple one I was looking at is a time ordered list to pull the most cache cold tasks (and thus we can stop searching when we encounter the first cache hot task, in situations where it is appropriate, etc).

Im not sure I follow your point, but if I do note that the RT scheduler uses a completely different load balancer (that is priority ordered).

Quoted 2 lines

Anyway... yeah I'm OK with this if it is under a config option.

Cool.. See v2 ;)

Thanks Nick,
-Greg

#13 lore raw

Re: [PATCH 3/5] sched: make double-lock-balance fair

In reply to Gregory Haskins
Quoted 73 lines · Gregory Haskins
Quoted 59 lines · Nick Piggin
Quoted 53 lines · Gregory Haskins
Quoted 43 lines · Nick Piggin
Quoted 42 lines · Gregory Haskins

double_lock balance() currently favors logically lower cpus since they often do not have to release their own lock to acquire a second lock. The result is that logically higher cpus can get starved when there is a lot of pressure on the RQs. This can result in higher latencies on higher cpu-ids.

This patch makes the algorithm more fair by forcing all paths to have to release both locks before acquiring them again. Since callsites to double_lock_balance already consider it a potential preemption/reschedule point, they have the proper logic to recheck for atomicity violations.

---

 kernel/sched.c |   17 +++++------------
 1 files changed, 5 insertions(+), 12 deletions(-)
kernel/sched.c +0 -11
index 6e0bde6..b7326cd 100644
@@ -2790,23 +2790,16 @@ static int double_lock_balance(struct rq
 *this_rq, struct rq *busiest) __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);
 		BUG_ON(1);
 	}
-	if (unlikely(!spin_trylock(&busiest->lock))) {
-		if (busiest < this_rq) {
-			spin_unlock(&this_rq->lock);
-			spin_lock(&busiest->lock);
-			spin_lock_nested(&this_rq->lock, SINGLE_DEPTH_NESTING);
-			ret = 1;
-		} else
-			spin_lock_nested(&busiest->lock, SINGLE_DEPTH_NESTING);
-	}
Quoted 8 lines

kernel/sched.c static int double_lock_balance(struct rq · line 2800

Quoted 4 lines
kernel/sched.c +3 -1
-	return ret;
+
+	spin_unlock(&this_rq->lock);
+	double_rq_lock(this_rq, busiest);

Rather than adding the extra atomic operation, can't you just put this into the unlikely spin_trylock failure path rather than the unfair logic there?

Quoted 4 lines

The trick is that we *must* first release this_rq before proceeding or the new proposal doesn't work as intended. This patch effectively breaks up the this_rq->lock critical section evenly across all CPUs as if it hit the case common for higher cpus.

Quoted 4 lines

I don't exactly see why my proposal would introduce any more latency, because we only trylock while holding the existing lock -- this is will only ever add a small ~constant time to the critical section, regardless of whether it is a high or low CPU runqueue.

Its because we are trying to create a break in the critical section of this_rq->lock, not improve the acquisition of busiest->lock. So whether you do spin_lock or spin_trylock on busiest does not matter. Busiest will not be contended in the case that I am concerned with. If you use my example below: rq[N] will not be contended because cpuN is blocked on rq[0] after already having released rq[N]. So its the contention against this_rq that is the problem.

Quoted 1 line

Or am I missing your point completely?

Well my point is just that after my change, there may be some windows of "unfair" behaviour where one CPU gets to go ahead early, but AFAIKS now there is no systemic bias against higher numbered CPUs (except the small issue of taking lowered numbered locks first which is also present in any solution).

As such, I would actually like to see my proposal implemented in the !lowlatency case as well... unless my reasoning has a hole in it?

But if you are _also_ wanting to eliminate the long lock hold time and strictly improve fairness for lowlatency kernels, then I agree that your patch goes much further than mine, so I don't object to putting that under CONFIG_PREEMPT.

Quoted 47 lines
Quoted 47 lines
Quoted 46 lines

This modification decreased
latency by over 800% (went from > 400us to < 50us) on cpus 6 and 7 in my 8-way box namely because they were not forced to wait for all the other lower cores to finish, but rather completions of double_lock_balance were handled in true FIFO w.r.t. to other calls to double_lock_balance(). It has to do with the positioning within your FIFO ticket locks (though even if ticket locks are not present on a given architecture we should still see an improvement.)

When a low cpu wants to double lock, it tends to hold this_rq and gets in line for busiest_rq with no bearing on how long it held this_rq. Therefore the following scenario can occur:

cpu 0 cpu N
----------------------------------
rq[0] locked
..
..
..
double_lock(N, 0)
rq[N] released
blocked on rq[0]
..
..
..
..
double_lock(0, N)
rq[N] locked
double_lock returns
..
..
..
..
rq[0] released rq[0] locked

                                  double_lock returns
                                  ...
                                  ...
                                  ...

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

So double lock acquisition favors the lower cpus unfairly. They will always win, even if they were not first. Now with the combination of my patch plus your ticket locks, entry into the double lock becomes FIFO because the "blocked on rq[0]" would have inserted it in the time-ordered head of rq[0].

Quoted 5 lines
Quoted 3 lines

Right, but I don't think it is particularly wrong to allow a given CPU to double_lock_balance ahead of another guy if we're already holding the lock.

Its not "wrong". Its just a latency source ;)

OK, sure.

Quoted 10 lines
Quoted 10 lines

_So long as_ the lock we are trying to acquire is uncontended,
and we don't introduce this skewed unfairness due to lower CPUs being allowed to hold their lower lock while higher CPUs have to release their lock and first queue on the lower.

The difference is that with my patch, there is a small window where the guy who asks for the double lock first will go through second. I don't think this really adds a fundamental amount of latency, and the performance benefit should not be ignored.

Quoted 6 lines
Quoted 3 lines

Linux's traditional and I suppose much largest user base does not require realtime or really strict fairness, so IMO it is always questionable to make changes like this.

Please take a look at the v2 series that I sent out yesterday. I have now predicated this on CONFIG_PREEMPT, per your comments.

Those patches look pretty OK with me now.

#7 lore raw

Re: [PATCH 2/5] sched: pull only one task during NEWIDLE balancing to limit critical section

In reply to Gregory Haskins
Quoted 11 lines · Gregory Haskins
Quoted 1 line · Nick Piggin

I'm surprised 2 is too much but 1 is OK. Seems pretty fragile to me.

Its not that 1 is magically "ok". Its simply that newidle balancing hurts latency, and 1 is the minimum to pull to reasonably reduce the critical section. I already check if we NEEDS_RESCHED before taking the rq->lock in newidle, so waiting for one task to pull is the first opportunity I have to end the section as quickly as possible. It would be nice if I could just keep going if I could detect whether there was not any real contention. Let me give this angle some more thought.

OK. Beware of introducing more cache coherency transitions, branches, icache, etc. If you are already resigned to put some special cases under CONFIG_PREEMPT, I think there is a lot to say for keeping the logic really simple and correct even if there is a small expense to performance.

But of course I never object to speedups ;)

Quoted 9 lines
Quoted 6 lines

FWIW, if you haven't already, then for -rt you might want to look at a more advanced data structure than simple run ordered list for moving tasks from one rq to the other. A simple one I was looking at is a time ordered list to pull the most cache cold tasks (and thus we can stop searching when we encounter the first cache hot task, in situations where it is appropriate, etc).

Im not sure I follow your point, but if I do note that the RT scheduler uses a completely different load balancer (that is priority ordered).

You still use the normal scheduler for other tasks, though? At any rate, no I haven't looked closely at the scheduler for a while, so I'm quite likely to be talking nonsense.

#30 lore raw

Re: [PATCH v2 3/6] sched: make double-lock-balance fair

In reply to Peter Zijlstra
Quoted 8 lines · Peter Zijlstra
Quoted 4 lines · Nick Piggin

BTW. I wonder about other architectures that are of interest to -rt? Like mips or arm perhaps... Any plans to implement ticket locks on those, or do they not tend to be used in SMP configurations on -rt yte?

Quoted 7 lines

I think both are starting to show more and more SMP machines, so yes, eventually we'll want ticket locks for them too.

That said, I'm not aware of anyone working on it - I suppose we could poke the regular arch maintainers.. Ralf, Russell ?

As an aside: I have an implementation of C-based ticket lock replacements for raw_spinlock_t that I could post. I never posted them because I mostly care about x86 and Nick's solution is superior there since its hand-tuned asm. But mine could be used in places that have not yet written arch support but need FIFO. I basically have it as a config option to enable "generic fifo spinlocks" or something like that.

-Greg

#33 lore raw

Re: [PATCH v2 3/6] sched: make double-lock-balance fair

In reply to Peter Zijlstra
Quoted 61 lines · Peter Zijlstra
Quoted 38 lines · Gregory Haskins

double_lock balance() currently favors logically lower cpus since they often do not have to release their own lock to acquire a second lock. The result is that logically higher cpus can get starved when there is a lot of pressure on the RQs. This can result in higher latencies on higher cpu-ids.

This patch makes the algorithm more fair by forcing all paths to have to release both locks before acquiring them again. Since callsites to double_lock_balance already consider it a potential preemption/reschedule point, they have the proper logic to recheck for atomicity violations.

---

 kernel/sched.c |   52 +++++++++++++++++++++++++++++++++++++++++++++-------
 1 files changed, 45 insertions(+), 7 deletions(-)
kernel/sched.c +9 -2
index df6b447..850b454 100644
@@ -2782,21 +2782,43 @@ static void double_rq_unlock(struct rq *rq1, struct rq *rq2)
 		__release(rq2->lock);
 }
 
+#ifdef CONFIG_PREEMPT
+
 /*
- * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
+ * fair double_lock_balance: Safely acquires both rq->locks in a fair
+ * way at the expense of forcing extra atomic operations in all
+ * invocations.  This assures that the double_lock is acquired using the
+ * same underlying policy as the spinlock_t on this architecture, which
+ * reduces latency compared to the unfair variant below.  However, it
+ * also adds more overhead and therefore may reduce throughput.
  */
-static int double_lock_balance(struct rq *this_rq, struct rq *busiest)
+static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)

kernel/sched.c static void double_rq_unlock(struct rq *rq1, struct rq *rq2) · line 2805

Quoted 10 lines
kernel/sched.c +9 -0
+	__releases(this_rq->lock)
+	__acquires(busiest->lock)
+	__acquires(this_rq->lock)
+{
+	spin_unlock(&this_rq->lock);
+	double_rq_lock(this_rq, busiest);
+
+	return 1;
+}
 

Right - so to belabour Nick's point:

  if (!spin_trylock(&busiest->lock)) {
    spin_unlock(&this_rq->lock);
    double_rq_lock(this_rq, busiest);
  }

might unfairly treat someone who is waiting on this_rq if I understand it right?

Quoted 7 lines

I suppose one could then write it like:

  if (spin_is_contended(&this_rq->lock) || !spin_trylock(&busiest->lock)) {
    spin_unlock(&this_rq->lock);
    double_rq_lock(this_rq, busiest);
  }

Indeed. This does get to the heart of the problem: contention against this_rq->lock.

Quoted 5 lines

But, I'm not sure that's worth the effort at that point..

Anyway - I think all this is utterly defeated on CONFIG_PREEMPT by the spin with IRQs enabled logic in kernel/spinlock.c.

I submitted some patches related to this a while back. The gist of it is that the presence of ticketlocks for a given config *should* defeat the preemptible version of the generic spinlocks or there is no point. Let me see if I can dig it up.

-Greg

#27 lore raw

Re: [PATCH v2 3/6] sched: make double-lock-balance fair

In reply to Nick Piggin
Quoted 9 lines · Nick Piggin
Quoted 7 lines · Nick Piggin
Quoted 3 lines · Peter Zijlstra

Does it make sense to make this _double_lock_balance() thing depend on that too?

Hmm, you might have a good point there. Greg?

Quoted 8 lines
Quoted 4 lines

BTW. I wonder about other architectures that are of interest to -rt? Like mips or arm perhaps... Any plans to implement ticket locks on those, or do they not tend to be used in SMP configurations on -rt yte?

Oh, or maybe I guess again: -rt might be using Greg's generic ticket lock implementation?

I never submitted them since yours were better for x86. But I can dust them off and post

-Greg

#14 lore raw

Re: [PATCH 3/5] sched: make double-lock-balance fair

In reply to Nick Piggin
Quoted 88 lines · Nick Piggin
Quoted 77 lines · Gregory Haskins
Quoted 62 lines · Nick Piggin
Quoted 55 lines · Gregory Haskins
Quoted 44 lines · Nick Piggin
Quoted 42 lines · Gregory Haskins

double_lock balance() currently favors logically lower cpus since they often do not have to release their own lock to acquire a second lock. The result is that logically higher cpus can get starved when there is a lot of pressure on the RQs. This can result in higher latencies on higher cpu-ids.

This patch makes the algorithm more fair by forcing all paths to have to release both locks before acquiring them again. Since callsites to double_lock_balance already consider it a potential preemption/reschedule point, they have the proper logic to recheck for atomicity violations.

---

 kernel/sched.c |   17 +++++------------
 1 files changed, 5 insertions(+), 12 deletions(-)
kernel/sched.c +0 -11
index 6e0bde6..b7326cd 100644
@@ -2790,23 +2790,16 @@ static int double_lock_balance(struct rq
 *this_rq, struct rq *busiest) __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);
 		BUG_ON(1);
 	}
-	if (unlikely(!spin_trylock(&busiest->lock))) {
-		if (busiest < this_rq) {
-			spin_unlock(&this_rq->lock);
-			spin_lock(&busiest->lock);
-			spin_lock_nested(&this_rq->lock, SINGLE_DEPTH_NESTING);
-			ret = 1;
-		} else
-			spin_lock_nested(&busiest->lock, SINGLE_DEPTH_NESTING);
-	}
Quoted 9 lines

kernel/sched.c static int double_lock_balance(struct rq · line 2801

Quoted 5 lines
kernel/sched.c +3 -1
-	return ret;
+
+	spin_unlock(&this_rq->lock);
+	double_rq_lock(this_rq, busiest);
 

Rather than adding the extra atomic operation, can't you just put this into the unlikely spin_trylock failure path rather than the unfair logic there?

Quoted 5 lines

The trick is that we *must* first release this_rq before proceeding or the new proposal doesn't work as intended. This patch effectively breaks up the this_rq->lock critical section evenly across all CPUs as if it hit the case common for higher cpus.

Quoted 5 lines

I don't exactly see why my proposal would introduce any more latency, because we only trylock while holding the existing lock -- this is will only ever add a small ~constant time to the critical section, regardless of whether it is a high or low CPU runqueue.

Its because we are trying to create a break in the critical section of this_rq->lock, not improve the acquisition of busiest->lock. So whether you do spin_lock or spin_trylock on busiest does not matter. Busiest will not be contended in the case that I am concerned with. If you use my example below: rq[N] will not be contended because cpuN is blocked on rq[0] after already having released rq[N]. So its the contention against this_rq that is the problem.

Quoted 2 lines

Or am I missing your point completely?

Well my point is just that after my change, there may be some windows of "unfair" behaviour where one CPU gets to go ahead early, but AFAIKS now there is no systemic bias against higher numbered CPUs (except the small issue of taking lowered numbered locks first which is also present in any solution).

Quoted 8 lines

As such, I would actually like to see my proposal implemented in the !lowlatency case as well... unless my reasoning has a hole in it?

But if you are _also_ wanting to eliminate the long lock hold time and strictly improve fairness for lowlatency kernels, then I agree that your patch goes much further than mine, so I don't object to putting that under CONFIG_PREEMPT.

Ok, I understand what you are saying now, and that makes sense.

-Greg

#32 lore raw

Re: [PATCH v2 3/6] sched: make double-lock-balance fair

In reply to Nick Piggin
Quoted 9 lines · Nick Piggin
Quoted 3 lines · Peter Zijlstra

Does it make sense to make this _double_lock_balance() thing depend on that too?

Hmm, you might have a good point there. Greg?

This makes sense to me.

#31 lore raw

Re: [PATCH v2 3/6] sched: make double-lock-balance fair

In reply to Peter Zijlstra
Quoted 9 lines · Peter Zijlstra
Quoted 3 lines

BTW. I wonder about other architectures that are of interest to -rt? Like mips or arm perhaps... Any plans to implement ticket locks on those, or do they not tend to be used in SMP configurations on -rt yte?

I think both are starting to show more and more SMP machines, so yes, eventually we'll want ticket locks for them too.

That said, I'm not aware of anyone working on it - I suppose we could poke the regular arch maintainers.. Ralf, Russell ?

I looked into this a bit and we definately need it. One large MIPS user already had converted his kernel to ticket locks due to an excessive number of cacheline bounces having been observed.

Ralf

#37 lore raw

Re: [PATCH v2 6/6] sched: create "pushable_tasks" list to limit pushing to one attempt

In reply to Gregory Haskins

Hi Ingo,

Quoted 45 lines · Gregory Haskins

The RT scheduler employs a "push/pull" design to actively balance tasks within the system (on a per disjoint cpuset basis). When a task is awoken, it is immediately determined if there are any lower priority cpus which should be preempted. This is opposed to the way normal SCHED_OTHER tasks behave, which will wait for a periodic rebalancing operation to occur before spreading out load.

When a particular RQ has more than 1 active RT task, it is said to be in an "overloaded" state. Once this occurs, the system enters the active balancing mode, where it will try to push the task away, or persuade a different cpu to pull it over. The system will stay in this state until the system falls back below the <= 1 queued RT task per RQ.

However, the current implementation suffers from a limitation in the push logic. Once overloaded, all tasks (other than current) on the RQ are analyzed on every push operation, even if it was previously unpushable (due to affinity, etc). Whats more, the operation stops at the first task that is unpushable and will not look at items lower in the queue. This causes two problems:

1) We can have the same tasks analyzed over and over again during each push, which extends out the fast path in the scheduler for no gain. Consider a RQ that has dozens of tasks that are bound to a core. Each one of those tasks will be encountered and skipped for each push operation while they are queued.

2) There may be lower-priority tasks under the unpushable task that could have been successfully pushed, but will never be considered until either the unpushable task is cleared, or a pull operation succeeds. The net result is a potential latency source for mid priority tasks.

This patch aims to rectify these two conditions by introducing a new priority sorted list: "pushable_tasks". A task is added to the list each time a task is activated or preempted. It is removed from the list any time it is deactivated, made current, or fails to push.

This works because a task only needs to be attempted to push once. After an initial failure to push, the other cpus will eventually try to pull the task when the conditions are proper. This also solves the problem that we don't completely analyze all tasks due to encountering an unpushable tasks. Now every task will have a push attempted (when appropriate).

Quoted 7 lines

This reduces latency both by shorting the critical section of the rq->lock for certain workloads, and by making sure the algorithm considers all eligible tasks in the system.

We have found a crash bug in this patch in our lab caused by this patch. So if you had any plans to pull this series in, please skip this last patch for now (6/6). I will send out a refresh after I fix the issue.

Thanks,
-Greg

#40 lore raw

v3 cover sched: misc rt fixes

In reply to Gregory Haskins

Hi Ingo,

The following repositories

git://git.kernel.org/pub/scm/linux/kernel/git/ghaskins/linux-2.6-hacks.git tip/sched/devel/rtbalance

ftp://ftp.novell.com/dev/ghaskins/tip-rt-fixes.tar.bz2

[

     *- Steve: I have also backported this to 2.6.26.3-rt5: *-

     ftp://ftp.novell.com/dev/ghaskins/PREEMPT_RT-rt-fixes.tar.bz2

]

apply to tip/sched/devel to pick up the following fixes for the RT scheduler.

[
Changelog:

v3:
*) fixed a bug in patch 6/6 in enqueue_pushable_task *) backported from tip to 26.3-rt5

v2:
*) predicated newidle and double_lock changes on
CONFIG_PREEMPT to address a concern by Nick Piggin

*) fixed a build issue when DEBUG_PI_LIST is defined

v1:
*) initial release
]

These patches were developed in the interest of shorting latencies in PREEMPT_RT, but they apply to the mainline scheduler as well, so I am offering them here as well.

This has been tested under both 26.3-rt5 and tip/sched/devel on x86_64 for both CONFIG_SMP and !CONFIG_SMP.

Comments/bug-fixes welcome!

Regards,
-Greg

---

Gregory Haskins (6):
sched: create "pushable_tasks" list to limit pushing to one attempt
plist: fix PLIST_NODE_INIT to work with debug enabled
sched: add sched_class->needs_post_schedule() member
sched: make double-lock-balance fair
sched: pull only one task during NEWIDLE balancing to limit critical section
sched: only try to push a task on wakeup if it is migratable

 include/linux/init_task.h |    1 
 include/linux/plist.h     |    9 ++-
 include/linux/sched.h     |    2 +
 kernel/sched.c            |   84 ++++++++++++++++++++++++---
 kernel/sched_rt.c         |  138 ++++++++++++++++++++++++++++++++++++++-------
 5 files changed, 201 insertions(+), 33 deletions(-)
#41 lore raw

PATCH v3 1/6 sched: only try to push a task on wakeup if it is migratable

There is no sense in wasting time trying to push a task away that cannot move anywhere else. We gain no benefit from trying to push other tasks at this point, so if the task being woken up is non migratable, just skip the whole operation. This reduces overhead in the wakeup path for certain tasks.

---

 kernel/sched_rt.c |    8 +++++---
 1 files changed, 5 insertions(+), 3 deletions(-)
kernel/sched_rt.c +5 -3
index 998ba54..768be35 100644
@@ -1229,14 +1229,16 @@ static void post_schedule_rt(struct rq *rq)
 }
 
 /*
- * If we are not running and we are not going to reschedule soon, we should
- * try to push tasks away now
+ * If we are not running, we are not going to reschedule soon,
+ * and we have tasks that could be pushed, we should try to push tasks
+ * away now
  */
 static void task_wake_up_rt(struct rq *rq, struct task_struct *p)
 {
 	if (!task_running(rq, p) &&
 	    !test_tsk_need_resched(rq->curr) &&
-	    rq->rt.overloaded)
+	    rq->rt.overloaded &&
+	    p->rt.nr_cpus_allowed > 1)
 		push_rt_tasks(rq);
 }
 
#42 lore raw

PATCH v3 2/6 sched: pull only one task during NEWIDLE balancing to limit critical section

In reply to Gregory Haskins

git-id c4acb2c0669c5c5c9b28e9d02a34b5c67edf7092 attempted to limit newidle critical section length by stopping after at least one task was moved. Further investigation has shown that there are other paths nested further inside the algorithm which still remain that allow long latencies to occur with newidle balancing. This patch applies the same technique inside balance_tasks() to limit the duration of this optional balancing operation.

---

 kernel/sched.c |   18 +++++++++++++++++-
 1 files changed, 17 insertions(+), 1 deletions(-)
kernel/sched.c +16 -0
index b112caa..35e1f21 100644
@@ -2962,6 +2962,16 @@ next:
 	pulled++;
 	rem_load_move -= p->se.load.weight;
 
+#ifdef CONFIG_PREEMPT
+	/*
+	 * NEWIDLE balancing is a source of latency, so preemptible kernels
+	 * will stop after the first task is pulled to minimize the critical
+	 * section.
+	 */
+	if (idle == CPU_NEWLY_IDLE)
+		goto out;
+#endif
+
 	/*
 	 * We only want to steal up to the prescribed amount of weighted load.
 	 */
@@ -3008,9 +3018,15 @@ static int move_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
 				sd, idle, all_pinned, &this_best_prio);
 		class = class->next;
 
+#ifdef CONFIG_PREEMPT
+		/*
+		 * NEWIDLE balancing is a source of latency, so preemptible
+		 * kernels will stop after the first task is pulled to minimize
+		 * the critical section.
+		 */
 		if (idle == CPU_NEWLY_IDLE && this_rq->nr_running)
 			break;
#43 lore raw

PATCH v3 3/6 sched: make double-lock-balance fair

In reply to Gregory Haskins

double_lock balance() currently favors logically lower cpus since they often do not have to release their own lock to acquire a second lock. The result is that logically higher cpus can get starved when there is a lot of pressure on the RQs. This can result in higher latencies on higher cpu-ids.

This patch makes the algorithm more fair by forcing all paths to have to release both locks before acquiring them again. Since callsites to double_lock_balance already consider it a potential preemption/reschedule point, they have the proper logic to recheck for atomicity violations.

---

 kernel/sched.c |   52 +++++++++++++++++++++++++++++++++++++++++++++-------
 1 files changed, 45 insertions(+), 7 deletions(-)
kernel/sched.c +45 -7
index 35e1f21..af4c6fa 100644
@@ -2782,21 +2782,43 @@ static void double_rq_unlock(struct rq *rq1, struct rq *rq2)
 		__release(rq2->lock);
 }
 
+#ifdef CONFIG_PREEMPT
+
 /*
- * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
+ * fair double_lock_balance: Safely acquires both rq->locks in a fair
+ * way at the expense of forcing extra atomic operations in all
+ * invocations.  This assures that the double_lock is acquired using the
+ * same underlying policy as the spinlock_t on this architecture, which
+ * reduces latency compared to the unfair variant below.  However, it
+ * also adds more overhead and therefore may reduce throughput.
  */
-static int double_lock_balance(struct rq *this_rq, struct rq *busiest)
+static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
+	__releases(this_rq->lock)
+	__acquires(busiest->lock)
+	__acquires(this_rq->lock)
+{
+	spin_unlock(&this_rq->lock);
+	double_rq_lock(this_rq, busiest);
+
+	return 1;
+}
+
+#else
+
+/*
+ * Unfair double_lock_balance: Optimizes throughput at the expense of
+ * latency by eliminating extra atomic operations when the locks are
+ * already in proper order on entry.  This favors lower cpu-ids and will
+ * grant the double lock to lower cpus over higher ids under contention,
+ * regardless of entry order into the function.
+ */
+static inline 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);
-		BUG_ON(1);
-	}
 	if (unlikely(!spin_trylock(&busiest->lock))) {
 		if (busiest < this_rq) {
 			spin_unlock(&this_rq->lock);
@@ -2809,6 +2831,22 @@ static int double_lock_balance(struct rq *this_rq, struct rq *busiest)
 	return ret;
 }
 
+#endif /* CONFIG_PREEMPT */
+
+/*
+ * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
+ */
+static int double_lock_balance(struct rq *this_rq, struct rq *busiest)
+{
+	if (unlikely(!irqs_disabled())) {
+		/* printk() doesn't work good under rq->lock */
+		spin_unlock(&this_rq->lock);
+		BUG_ON(1);
+	}
+
+	return _double_lock_balance(this_rq, busiest);
+}
+
 static void double_unlock_balance(struct rq *this_rq, struct rq *busiest)
 	__releases(busiest->lock)
 {
#44 lore raw

PATCH v3 4/6 sched: add sched_class->needs_post_schedule() member

In reply to Gregory Haskins

We currently run class->post_schedule() outside of the rq->lock, which means that we need to test for the need to post_schedule outside of the lock to avoid a forced reacquistion. This is currently not a problem as we only look at rq->rt.overloaded. However, we want to enhance this going forward to look at more state to reduce the need to post_schedule to a bare minimum set. Therefore, we introduce a new member-func called needs_post_schedule() which tests for the post_schedule condtion without actually performing the work. Therefore it is safe to call this function before the rq->lock is released, because we are guaranteed not to drop the lock at an intermediate point (such as what post_schedule() may do).

We will use this later in the series

---

 include/linux/sched.h |    1 +
 kernel/sched.c        |   10 +++++++++-
 kernel/sched_rt.c     |   24 ++++++++++++++----------
 3 files changed, 24 insertions(+), 11 deletions(-)
include/linux/sched.h +1 -0
index 08a87b5..cf8cd8c 100644
@@ -912,6 +912,7 @@ struct sched_class {
 			      struct rq *busiest, struct sched_domain *sd,
 			      enum cpu_idle_type idle);
 	void (*pre_schedule) (struct rq *this_rq, struct task_struct *task);
+	int (*needs_post_schedule) (struct rq *this_rq);
 	void (*post_schedule) (struct rq *this_rq);
 	void (*task_wake_up) (struct rq *this_rq, struct task_struct *task);
 #endif
kernel/sched.c +9 -1
index af4c6fa..ddc3877 100644
@@ -2525,6 +2525,14 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
 {
 	struct mm_struct *mm = rq->prev_mm;
 	long prev_state;
+#ifdef CONFIG_SMP
+	int post_schedule = 0;
+
+	if (current->sched_class->needs_post_schedule) {
+		BUG_ON(!current->sched_class->post_schedule);
+		post_schedule = current->sched_class->needs_post_schedule(rq);
+	}
+#endif
 
 	rq->prev_mm = NULL;
 
@@ -2543,7 +2551,7 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
 	finish_arch_switch(prev);
 	finish_lock_switch(rq, prev);
 #ifdef CONFIG_SMP
-	if (current->sched_class->post_schedule)
+	if (post_schedule)
 		current->sched_class->post_schedule(rq);
 #endif
 
kernel/sched_rt.c +14 -10
index 768be35..277ccd2 100644
@@ -1212,20 +1212,23 @@ static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
 		pull_rt_task(rq);
 }
 
+/*
+ * assumes rq->lock is held
+ */
+static int needs_post_schedule_rt(struct rq *rq)
+{
+	return rq->rt.overloaded ? 1 : 0;
+}
+
 static void post_schedule_rt(struct rq *rq)
 {
 	/*
-	 * If we have more than one rt_task queued, then
-	 * see if we can push the other rt_tasks off to other CPUS.
-	 * Note we may release the rq lock, and since
-	 * the lock was owned by prev, we need to release it
-	 * first via finish_lock_switch and then reaquire it here.
+	 * This is only called if needs_post_schedule_rt() indicates that
+	 * we need to push tasks away
 	 */
-	if (unlikely(rq->rt.overloaded)) {
-		spin_lock_irq(&rq->lock);
-		push_rt_tasks(rq);
-		spin_unlock_irq(&rq->lock);
-	}
+	spin_lock_irq(&rq->lock);
+	push_rt_tasks(rq);
+	spin_unlock_irq(&rq->lock);
 }
 
 /*
@@ -1473,6 +1476,7 @@ static const struct sched_class rt_sched_class = {
 	.rq_online              = rq_online_rt,
 	.rq_offline             = rq_offline_rt,
 	.pre_schedule		= pre_schedule_rt,
+	.needs_post_schedule	= needs_post_schedule_rt,
 	.post_schedule		= post_schedule_rt,
 	.task_wake_up		= task_wake_up_rt,
 	.switched_from		= switched_from_rt,
#47 lore raw

PATCH v3 5/6 plist: fix PLIST_NODE_INIT to work with debug enabled

In reply to Gregory Haskins

It seems that PLIST_NODE_INIT breaks if used and DEBUG_PI_LIST is defined. Since there are no current users of PLIST_NODE_INIT, this has gone undetected. This patch fixes the build issue that enables the DEBUG_PI_LIST later in the series when we use it in init_task.h

---

 include/linux/plist.h |    9 ++++++---
 1 files changed, 6 insertions(+), 3 deletions(-)
include/linux/plist.h +6 -3
index 85de2f0..2b65483 100644
@@ -96,6 +96,10 @@ struct plist_node {
 # define PLIST_HEAD_LOCK_INIT(_lock)
 #endif
 
+#define _PLIST_HEAD_INIT(head)				\
+	.prio_list = LIST_HEAD_INIT((head).prio_list),	\
+	.node_list = LIST_HEAD_INIT((head).node_list)
+
 /**
  * PLIST_HEAD_INIT - static struct plist_head initializer
  * @head:	struct plist_head variable name
@@ -103,8 +107,7 @@ struct plist_node {
  */
 #define PLIST_HEAD_INIT(head, _lock)			\
 {							\
-	.prio_list = LIST_HEAD_INIT((head).prio_list),	\
-	.node_list = LIST_HEAD_INIT((head).node_list),	\
+	_PLIST_HEAD_INIT(head),                         \
 	PLIST_HEAD_LOCK_INIT(&(_lock))			\
 }
 
@@ -116,7 +119,7 @@ struct plist_node {
 #define PLIST_NODE_INIT(node, __prio)			\
 {							\
 	.prio  = (__prio),				\
-	.plist = PLIST_HEAD_INIT((node).plist, NULL),	\
+	.plist = { _PLIST_HEAD_INIT((node).plist) }, 	\
 }
 
 /**
#48 lore raw

PATCH v3 6/6 sched: create "pushable_tasks" list to limit pushing to one attempt

In reply to Gregory Haskins

The RT scheduler employs a "push/pull" design to actively balance tasks within the system (on a per disjoint cpuset basis). When a task is awoken, it is immediately determined if there are any lower priority cpus which should be preempted. This is opposed to the way normal SCHED_OTHER tasks behave, which will wait for a periodic rebalancing operation to occur before spreading out load.

When a particular RQ has more than 1 active RT task, it is said to be in an "overloaded" state. Once this occurs, the system enters the active balancing mode, where it will try to push the task away, or persuade a different cpu to pull it over. The system will stay in this state until the system falls back below the <= 1 queued RT task per RQ.

However, the current implementation suffers from a limitation in the push logic. Once overloaded, all tasks (other than current) on the RQ are analyzed on every push operation, even if it was previously unpushable (due to affinity, etc). Whats more, the operation stops at the first task that is unpushable and will not look at items lower in the queue. This causes two problems:

1) We can have the same tasks analyzed over and over again during each push, which extends out the fast path in the scheduler for no gain. Consider a RQ that has dozens of tasks that are bound to a core. Each one of those tasks will be encountered and skipped for each push operation while they are queued.

2) There may be lower-priority tasks under the unpushable task that could have been successfully pushed, but will never be considered until either the unpushable task is cleared, or a pull operation succeeds. The net result is a potential latency source for mid priority tasks.

This patch aims to rectify these two conditions by introducing a new priority sorted list: "pushable_tasks". A task is added to the list each time a task is activated or preempted. It is removed from the list any time it is deactivated, made current, or fails to push.

This works because a task only needs to be attempted to push once. After an initial failure to push, the other cpus will eventually try to pull the task when the conditions are proper. This also solves the problem that we don't completely analyze all tasks due to encountering an unpushable tasks. Now every task will have a push attempted (when appropriate).

This reduces latency both by shorting the critical section of the rq->lock for certain workloads, and by making sure the algorithm considers all eligible tasks in the system.

---

 include/linux/init_task.h |    1 
 include/linux/sched.h     |    1 
 kernel/sched.c            |    4 ++
 kernel/sched_rt.c         |  110 +++++++++++++++++++++++++++++++++++++++++----
 4 files changed, 106 insertions(+), 10 deletions(-)
include/linux/init_task.h +1 -0
index 021d8e7..7f910f4 100644
@@ -140,6 +140,7 @@ extern struct group_info init_groups;
 		.nr_cpus_allowed = NR_CPUS,				\
 	},								\
 	.tasks		= LIST_HEAD_INIT(tsk.tasks),			\
+	.pushable_tasks = PLIST_NODE_INIT(tsk.pushable_tasks, MAX_PRIO), \
 	.ptraced	= LIST_HEAD_INIT(tsk.ptraced),			\
 	.ptrace_entry	= LIST_HEAD_INIT(tsk.ptrace_entry),		\
 	.real_parent	= &tsk,						\
include/linux/sched.h +1 -0
index cf8cd8c..3480c8a 100644
@@ -1078,6 +1078,7 @@ struct task_struct {
 #endif
 
 	struct list_head tasks;
+	struct plist_node pushable_tasks;
 
 	struct mm_struct *mm, *active_mm;
 
kernel/sched.c +4 -0
index ddc3877..dbb9e8c 100644
@@ -447,6 +447,7 @@ struct rt_rq {
 #ifdef CONFIG_SMP
 	unsigned long rt_nr_migratory;
 	int overloaded;
+	struct plist_head pushable_tasks;
 #endif
 	int rt_throttled;
 	u64 rt_time;
@@ -2383,6 +2384,8 @@ void sched_fork(struct task_struct *p, int clone_flags)
 	/* Want to start with kernel preemption disabled. */
 	task_thread_info(p)->preempt_count = 1;
 #endif
+	plist_node_init(&p->pushable_tasks, MAX_PRIO);
+
 	put_cpu();
 }
 
@@ -8009,6 +8012,7 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
 #ifdef CONFIG_SMP
 	rt_rq->rt_nr_migratory = 0;
 	rt_rq->overloaded = 0;
+	plist_head_init(&rq->rt.pushable_tasks, &rq->lock);
 #endif
 
 	rt_rq->rt_time = 0;
kernel/sched_rt.c +100 -10

219 lines not on this page · raw message

#45 lore raw

Re: [TIP/SCHED/DEVEL PATCH v3 4/6] sched: add sched_class->needs_post_schedule() member

In reply to Gregory Haskins

kernel/sched.c static void finish_task_switch(struct rq *rq, struct task_struct *prev) · line 2532

Quoted 13 lines · Gregory Haskins
kernel/sched.c +5 -0
index af4c6fa..ddc3877 100644
@@ -2525,6 +2525,14 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
 {
 	struct mm_struct *mm = rq->prev_mm;
 	long prev_state;
+#ifdef CONFIG_SMP
+	int post_schedule = 0;
+
+	if (current->sched_class->needs_post_schedule) {
+		BUG_ON(!current->sched_class->post_schedule);

The only one to ever hit this BUG_ON is a kernel developer creating a new sched class. Since they should be smart enough to figure out why they get a segv later on, we really don't need it. Because this BUG_ON is also in a hot path, I strongly suggest nuking it.

-- Steve

Quoted 3 lines
kernel/sched.c +3 -0
+		post_schedule = current->sched_class->needs_post_schedule(rq);
+	}
+#endif
#46 lore raw

Re: [TIP/SCHED/DEVEL PATCH v3 4/6] sched: add sched_class->needs_post_schedule() member

Quoted 13 lines · Steven Rostedt
Quoted 11 lines · Gregory Haskins
kernel/sched.c +3 -0
index af4c6fa..ddc3877 100644
@@ -2525,6 +2525,14 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev)
 {
 	struct mm_struct *mm = rq->prev_mm;
 	long prev_state;
+#ifdef CONFIG_SMP
+	int post_schedule = 0;
+
Quoted 9 lines

kernel/sched.c static void finish_task_switch(struct rq *rq, struct task_struct *prev) · line 2536

Quoted 3 lines
kernel/sched.c +2 -0
+	if (current->sched_class->needs_post_schedule) {
+		BUG_ON(!current->sched_class->post_schedule);
 

The only one to ever hit this BUG_ON is a kernel developer creating a new sched class. Since they should be smart enough to figure out why they get a segv later on, we really don't need it. Because this BUG_ON is also in a hot path, I strongly suggest nuking it.

Ack. Will do a respin after you review the last few patches.

-Greg

reviewer Acked-by on v3 6/6
#49 lore raw

Re: [TIP/SCHED/DEVEL PATCH v3 6/6] sched: create "pushable_tasks" list to limit pushing to one attempt

In reply to Gregory Haskins
Quoted 14 lines · Gregory Haskins

However, the current implementation suffers from a limitation in the push logic. Once overloaded, all tasks (other than current) on the RQ are analyzed on every push operation, even if it was previously unpushable (due to affinity, etc). Whats more, the operation stops at the first task that is unpushable and will not look at items lower in the queue. This causes two problems:

1) We can have the same tasks analyzed over and over again during each push, which extends out the fast path in the scheduler for no gain. Consider a RQ that has dozens of tasks that are bound to a core. Each one of those tasks will be encountered and skipped for each push operation while they are queued.

Quoted 5 lines

2) There may be lower-priority tasks under the unpushable task that could have been successfully pushed, but will never be considered until either the unpushable task is cleared, or a pull operation succeeds. The net result is a potential latency source for mid priority tasks.

Yep, we knew of these limitations when we created it. It was a big TODO. Thanks for actually doing it. It is what? One year already?

;-)

Quoted 182 lines

This patch aims to rectify these two conditions by introducing a new priority sorted list: "pushable_tasks". A task is added to the list each time a task is activated or preempted. It is removed from the list any time it is deactivated, made current, or fails to push.

This works because a task only needs to be attempted to push once. After an initial failure to push, the other cpus will eventually try to pull the task when the conditions are proper. This also solves the problem that we don't completely analyze all tasks due to encountering an unpushable tasks. Now every task will have a push attempted (when appropriate).

This reduces latency both by shorting the critical section of the rq->lock for certain workloads, and by making sure the algorithm considers all eligible tasks in the system.

---

 include/linux/init_task.h |    1 
 include/linux/sched.h     |    1 
 kernel/sched.c            |    4 ++
 kernel/sched_rt.c         |  110 +++++++++++++++++++++++++++++++++++++++++----
 4 files changed, 106 insertions(+), 10 deletions(-)
include/linux/init_task.h +1 -0
index 021d8e7..7f910f4 100644
@@ -140,6 +140,7 @@ extern struct group_info init_groups;
 		.nr_cpus_allowed = NR_CPUS,				\
 	},								\
 	.tasks		= LIST_HEAD_INIT(tsk.tasks),			\
+	.pushable_tasks = PLIST_NODE_INIT(tsk.pushable_tasks, MAX_PRIO), \
 	.ptraced	= LIST_HEAD_INIT(tsk.ptraced),			\
 	.ptrace_entry	= LIST_HEAD_INIT(tsk.ptrace_entry),		\
 	.real_parent	= &tsk,						\
include/linux/sched.h +1 -0
index cf8cd8c..3480c8a 100644
@@ -1078,6 +1078,7 @@ struct task_struct {
 #endif
 
 	struct list_head tasks;
+	struct plist_node pushable_tasks;
 
 	struct mm_struct *mm, *active_mm;
 
kernel/sched.c +4 -0
index ddc3877..dbb9e8c 100644
@@ -447,6 +447,7 @@ struct rt_rq {
 #ifdef CONFIG_SMP
 	unsigned long rt_nr_migratory;
 	int overloaded;
+	struct plist_head pushable_tasks;
 #endif
 	int rt_throttled;
 	u64 rt_time;
@@ -2383,6 +2384,8 @@ void sched_fork(struct task_struct *p, int clone_flags)
 	/* Want to start with kernel preemption disabled. */
 	task_thread_info(p)->preempt_count = 1;
 #endif
+	plist_node_init(&p->pushable_tasks, MAX_PRIO);
+
 	put_cpu();
 }
 
@@ -8009,6 +8012,7 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
 #ifdef CONFIG_SMP
 	rt_rq->rt_nr_migratory = 0;
 	rt_rq->overloaded = 0;
+	plist_head_init(&rq->rt.pushable_tasks, &rq->lock);
 #endif
 
 	rt_rq->rt_time = 0;
kernel/sched_rt.c +51 -1
index 277ccd2..b22d18a 100644
@@ -49,6 +49,24 @@ static void update_rt_migration(struct rq *rq)
 		rq->rt.overloaded = 0;
 	}
 }
+
+static void enqueue_pushable_task(struct rq *rq, struct task_struct *p)
+{
+	plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
+	plist_node_init(&p->pushable_tasks, p->prio);
+	plist_add(&p->pushable_tasks, &rq->rt.pushable_tasks);
+}
+
+static void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
+{
+	plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
+}
+
+#else
+
+#define enqueue_pushable_task(rq, p) do { } while (0)
+#define dequeue_pushable_task(rq, p) do { } while (0)
+
 #endif /* CONFIG_SMP */
 
 static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
@@ -669,6 +687,9 @@ static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup)
 
 	enqueue_rt_entity(rt_se);
 
+	if (!task_current(rq, p) && p->rt.nr_cpus_allowed > 1)
+		enqueue_pushable_task(rq, p);
+
 	inc_cpu_load(rq, p->se.load.weight);
 }
 
@@ -679,6 +700,8 @@ static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int sleep)
 	update_curr_rt(rq);
 	dequeue_rt_entity(rt_se);
 
+	dequeue_pushable_task(rq, p);
+
 	dec_cpu_load(rq, p->se.load.weight);
 }
 
@@ -824,7 +847,7 @@ static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
 	return next;
 }
 
-static struct task_struct *pick_next_task_rt(struct rq *rq)
+static struct task_struct *_pick_next_task_rt(struct rq *rq)
 {
 	struct sched_rt_entity *rt_se;
 	struct task_struct *p;
@@ -846,6 +869,18 @@ static struct task_struct *pick_next_task_rt(struct rq *rq)
 
 	p = rt_task_of(rt_se);
 	p->se.exec_start = rq->clock;
+
+	return p;
+}
+
+static struct task_struct *pick_next_task_rt(struct rq *rq)
+{
+	struct task_struct *p = _pick_next_task_rt(rq);
+
+	/* The running task is never eligible for pushing */
+	if (p)
+		dequeue_pushable_task(rq, p);
+
 	return p;
 }
 
@@ -853,6 +888,13 @@ static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
 {
 	update_curr_rt(rq);
 	p->se.exec_start = 0;
+
+	/*
+	 * The previous task needs to be made eligible for pushing
+	 * if it is still active
+	 */
+	if (p->se.on_rq && p->rt.nr_cpus_allowed > 1)
+		enqueue_pushable_task(rq, p);
 }
 
 #ifdef CONFIG_SMP
@@ -1031,6 +1073,28 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
 	return lowest_rq;
 }
 
+static inline int has_pushable_tasks(struct rq *rq)
+{
+	return !plist_head_empty(&rq->rt.pushable_tasks);
+}
+
+static struct task_struct *pick_next_pushable_task(struct rq *rq)
+{
+	struct task_struct *p;

kernel/sched_rt.c static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq) · line 1093

Quoted 10 lines
kernel/sched_rt.c +10 -0
+
+	if (!has_pushable_tasks(rq))
+		return NULL;
+
+	p = plist_first_entry(&rq->rt.pushable_tasks,
+			      struct task_struct, pushable_tasks);
+
+	BUG_ON(rq->cpu != task_cpu(p));
+	BUG_ON(task_current(rq, p));
+	BUG_ON(p->rt.nr_cpus_allowed <= 1);

I have two new BUG_ONs for you. (This isn't a fast path)

	BUG_ON(!p->se.on_rq);
	BUG_ON(!rt_task(p));
Quoted 119 lines
kernel/sched_rt.c +36 -9
+
+	return p;
+}
+
 /*
  * 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
@@ -1040,13 +1104,12 @@ 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;
 
 	if (!rq->rt.overloaded)
 		return 0;
 
-	next_task = pick_next_highest_task_rt(rq, -1);
+	next_task = pick_next_pushable_task(rq);
 	if (!next_task)
 		return 0;
 
@@ -1078,12 +1141,19 @@ static int push_rt_task(struct rq *rq)
 		 * so it is possible that next_task has changed.
 		 * If it has, then try again.
 		 */
-		task = pick_next_highest_task_rt(rq, -1);
+		task = pick_next_pushable_task(rq);
 		if (unlikely(task != next_task) && task && paranoid--) {
 			put_task_struct(next_task);
 			next_task = task;
 			goto retry;
 		}
+
+		/*
+		 * Once we have failed to push this task, we will not
+		 * try again, since the other cpus will pull from us
+		 * when they are ready
+		 */
+		dequeue_pushable_task(rq, next_task);
 		goto out;
 	}
 
@@ -1095,11 +1165,10 @@ static int push_rt_task(struct rq *rq)
 
 	double_unlock_balance(rq, lowest_rq);
 
-	ret = 1;
 out:
 	put_task_struct(next_task);
 
-	return ret;
+	return 1;
 }
 
 /*
@@ -1128,7 +1197,7 @@ static int pull_rt_task(struct rq *this_rq)
 	if (likely(!rt_overloaded(this_rq)))
 		return 0;
 
-	next = pick_next_task_rt(this_rq);
+	next = _pick_next_task_rt(this_rq);
 
 	for_each_cpu_mask_nr(cpu, this_rq->rd->rto_mask) {
 		if (this_cpu == cpu)
@@ -1145,7 +1214,7 @@ static int pull_rt_task(struct rq *this_rq)
 		if (double_lock_balance(this_rq, src_rq)) {
 			struct task_struct *old_next = next;
 
-			next = pick_next_task_rt(this_rq);
+			next = _pick_next_task_rt(this_rq);
 			if (next != old_next)
 				ret = 1;
 		}
@@ -1217,7 +1286,7 @@ static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
  */
 static int needs_post_schedule_rt(struct rq *rq)
 {
-	return rq->rt.overloaded ? 1 : 0;
+	return has_pushable_tasks(rq);
 }
 
 static void post_schedule_rt(struct rq *rq)
@@ -1240,7 +1309,7 @@ static void task_wake_up_rt(struct rq *rq, struct task_struct *p)
 {
 	if (!task_running(rq, p) &&
 	    !test_tsk_need_resched(rq->curr) &&
-	    rq->rt.overloaded &&
+	    has_pushable_tasks(rq) &&
 	    p->rt.nr_cpus_allowed > 1)
 		push_rt_tasks(rq);
 }
@@ -1277,6 +1346,24 @@ static void set_cpus_allowed_rt(struct task_struct *p,
 	if (p->se.on_rq && (weight != p->rt.nr_cpus_allowed)) {
 		struct rq *rq = task_rq(p);
 
+		if (!task_current(rq, p)) {
+			/*
+			 * Make sure we dequeue this task from the pushable list
+			 * before going further.  It will either remain off of
+			 * the list because we are no longer pushable, or it
+			 * will be requeued.
+			 */
+			if (p->rt.nr_cpus_allowed > 1)
+				dequeue_pushable_task(rq, p);
+
+			/*
+			 * Requeue if our weight is changing and still > 1
+			 */
+			if (weight > 1)
+				enqueue_pushable_task(rq, p);
+
+		}
+
 		if ((p->rt.nr_cpus_allowed <= 1) && (weight > 1)) {
 			rq->rt.rt_nr_migratory++;
 		} else if ((p->rt.nr_cpus_allowed > 1) && (weight <= 1)) {

kernel/sched_rt.c static void set_curr_task_rt(struct rq *rq) · line 1548

Quoted 9 lines
kernel/sched_rt.c +3 -0
@@ -1453,6 +1540,9 @@ static void set_curr_task_rt(struct rq *rq)
 	struct task_struct *p = rq->curr;
 
 	p->se.exec_start = rq->clock;
+
+	/* The running task is never eligible for pushing */
+	dequeue_pushable_task(rq, p);
 }
 
 static const struct sched_class rt_sched_class = {

OK, I like the patch, but I'm not 100% that it doesn't have bugs. I'll ACK it, but this definitely needs to be heavily tested, before going mainline. But for linux-tip, -mm, or linux-next, I think it is, on the surface, good to go (with the added BUG_ONs).

I'll pull it into -rt as well.

Thanks,

-- Steve

#50 lore raw

Re: [TIP/SCHED/DEVEL PATCH v3 6/6] sched: create "pushable_tasks" list to limit pushing to one attempt

Quoted 22 lines · Steven Rostedt
Quoted 13 lines · Gregory Haskins

However, the current implementation suffers from a limitation in the push logic. Once overloaded, all tasks (other than current) on the RQ are analyzed on every push operation, even if it was previously unpushable (due to affinity, etc). Whats more, the operation stops at the first task that is unpushable and will not look at items lower in the queue. This causes two problems:

1) We can have the same tasks analyzed over and over again during each push, which extends out the fast path in the scheduler for no gain. Consider a RQ that has dozens of tasks that are bound to a core. Each one of those tasks will be encountered and skipped for each push operation while they are queued.

Quoted 6 lines

2) There may be lower-priority tasks under the unpushable task that could have been successfully pushed, but will never be considered until either the unpushable task is cleared, or a pull operation succeeds. The net result is a potential latency source for mid priority tasks.

Quoted 5 lines

Yep, we knew of these limitations when we created it. It was a big TODO. Thanks for actually doing it. It is what? One year already?

;-)

Yeah, agreed. Sorry if it sounded like I was representing it as a new find.

Quoted 196 lines
Quoted 183 lines

This patch aims to rectify these two conditions by introducing a new priority sorted list: "pushable_tasks". A task is added to the list each time a task is activated or preempted. It is removed from the list any time it is deactivated, made current, or fails to push.

This works because a task only needs to be attempted to push once. After an initial failure to push, the other cpus will eventually try to pull the task when the conditions are proper. This also solves the problem that we don't completely analyze all tasks due to encountering an unpushable tasks. Now every task will have a push attempted (when appropriate).

This reduces latency both by shorting the critical section of the rq->lock for certain workloads, and by making sure the algorithm considers all eligible tasks in the system.

---

 include/linux/init_task.h |    1 
 include/linux/sched.h     |    1 
 kernel/sched.c            |    4 ++
 kernel/sched_rt.c         |  110 +++++++++++++++++++++++++++++++++++++++++----
 4 files changed, 106 insertions(+), 10 deletions(-)
include/linux/init_task.h +1 -0
index 021d8e7..7f910f4 100644
@@ -140,6 +140,7 @@ extern struct group_info init_groups;
 		.nr_cpus_allowed = NR_CPUS,				\
 	},								\
 	.tasks		= LIST_HEAD_INIT(tsk.tasks),			\
+	.pushable_tasks = PLIST_NODE_INIT(tsk.pushable_tasks, MAX_PRIO), \
 	.ptraced	= LIST_HEAD_INIT(tsk.ptraced),			\
 	.ptrace_entry	= LIST_HEAD_INIT(tsk.ptrace_entry),		\
 	.real_parent	= &tsk,						\
include/linux/sched.h +1 -0
index cf8cd8c..3480c8a 100644
@@ -1078,6 +1078,7 @@ struct task_struct {
 #endif
 
 	struct list_head tasks;
+	struct plist_node pushable_tasks;
 
 	struct mm_struct *mm, *active_mm;
 
kernel/sched.c +4 -0
index ddc3877..dbb9e8c 100644
@@ -447,6 +447,7 @@ struct rt_rq {
 #ifdef CONFIG_SMP
 	unsigned long rt_nr_migratory;
 	int overloaded;
+	struct plist_head pushable_tasks;
 #endif
 	int rt_throttled;
 	u64 rt_time;
@@ -2383,6 +2384,8 @@ void sched_fork(struct task_struct *p, int clone_flags)
 	/* Want to start with kernel preemption disabled. */
 	task_thread_info(p)->preempt_count = 1;
 #endif
+	plist_node_init(&p->pushable_tasks, MAX_PRIO);
+
 	put_cpu();
 }
 
@@ -8009,6 +8012,7 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
 #ifdef CONFIG_SMP
 	rt_rq->rt_nr_migratory = 0;
 	rt_rq->overloaded = 0;
+	plist_head_init(&rq->rt.pushable_tasks, &rq->lock);
 #endif
 
 	rt_rq->rt_time = 0;
kernel/sched_rt.c +52 -1
index 277ccd2..b22d18a 100644
@@ -49,6 +49,24 @@ static void update_rt_migration(struct rq *rq)
 		rq->rt.overloaded = 0;
 	}
 }
+
+static void enqueue_pushable_task(struct rq *rq, struct task_struct *p)
+{
+	plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
+	plist_node_init(&p->pushable_tasks, p->prio);
+	plist_add(&p->pushable_tasks, &rq->rt.pushable_tasks);
+}
+
+static void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
+{
+	plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
+}
+
+#else
+
+#define enqueue_pushable_task(rq, p) do { } while (0)
+#define dequeue_pushable_task(rq, p) do { } while (0)
+
 #endif /* CONFIG_SMP */
 
 static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
@@ -669,6 +687,9 @@ static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup)
 
 	enqueue_rt_entity(rt_se);
 
+	if (!task_current(rq, p) && p->rt.nr_cpus_allowed > 1)
+		enqueue_pushable_task(rq, p);
+
 	inc_cpu_load(rq, p->se.load.weight);
 }
 
@@ -679,6 +700,8 @@ static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int sleep)
 	update_curr_rt(rq);
 	dequeue_rt_entity(rt_se);
 
+	dequeue_pushable_task(rq, p);
+
 	dec_cpu_load(rq, p->se.load.weight);
 }
 
@@ -824,7 +847,7 @@ static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
 	return next;
 }
 
-static struct task_struct *pick_next_task_rt(struct rq *rq)
+static struct task_struct *_pick_next_task_rt(struct rq *rq)
 {
 	struct sched_rt_entity *rt_se;
 	struct task_struct *p;
@@ -846,6 +869,18 @@ static struct task_struct *pick_next_task_rt(struct rq *rq)
 
 	p = rt_task_of(rt_se);
 	p->se.exec_start = rq->clock;
+
+	return p;
+}
+
+static struct task_struct *pick_next_task_rt(struct rq *rq)
+{
+	struct task_struct *p = _pick_next_task_rt(rq);
+
+	/* The running task is never eligible for pushing */
+	if (p)
+		dequeue_pushable_task(rq, p);
+
 	return p;
 }
 
@@ -853,6 +888,13 @@ static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
 {
 	update_curr_rt(rq);
 	p->se.exec_start = 0;
+
+	/*
+	 * The previous task needs to be made eligible for pushing
+	 * if it is still active
+	 */
+	if (p->se.on_rq && p->rt.nr_cpus_allowed > 1)
+		enqueue_pushable_task(rq, p);
 }
 
 #ifdef CONFIG_SMP
@@ -1031,6 +1073,28 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
 	return lowest_rq;
 }
 
+static inline int has_pushable_tasks(struct rq *rq)
+{
+	return !plist_head_empty(&rq->rt.pushable_tasks);
+}
+
+static struct task_struct *pick_next_pushable_task(struct rq *rq)
+{
+	struct task_struct *p;
+

kernel/sched_rt.c static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq) · line 1094

Quoted 10 lines
kernel/sched_rt.c +9 -0
+	if (!has_pushable_tasks(rq))
+		return NULL;
+
+	p = plist_first_entry(&rq->rt.pushable_tasks,
+			      struct task_struct, pushable_tasks);
+
+	BUG_ON(rq->cpu != task_cpu(p));
+	BUG_ON(task_current(rq, p));
+	BUG_ON(p->rt.nr_cpus_allowed <= 1);
 

I have two new BUG_ONs for you. (This isn't a fast path)

Quoted 3 lines
	BUG_ON(!p->se.on_rq);
	BUG_ON(!rt_task(p));

ack

Quoted 137 lines
Quoted 122 lines
kernel/sched_rt.c +4 -0
+
+	return p;
+}
+
 /*
  * 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

kernel/sched_rt.c +32 -9
@@ -1040,13 +1104,12 @@ 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;
 
 	if (!rq->rt.overloaded)
 		return 0;
 
-	next_task = pick_next_highest_task_rt(rq, -1);
+	next_task = pick_next_pushable_task(rq);
 	if (!next_task)
 		return 0;
 
@@ -1078,12 +1141,19 @@ static int push_rt_task(struct rq *rq)
 		 * so it is possible that next_task has changed.
 		 * If it has, then try again.
 		 */
-		task = pick_next_highest_task_rt(rq, -1);
+		task = pick_next_pushable_task(rq);
 		if (unlikely(task != next_task) && task && paranoid--) {
 			put_task_struct(next_task);
 			next_task = task;
 			goto retry;
 		}
+
+		/*
+		 * Once we have failed to push this task, we will not
+		 * try again, since the other cpus will pull from us
+		 * when they are ready
+		 */
+		dequeue_pushable_task(rq, next_task);
 		goto out;
 	}
 
@@ -1095,11 +1165,10 @@ static int push_rt_task(struct rq *rq)
 
 	double_unlock_balance(rq, lowest_rq);
 
-	ret = 1;
 out:
 	put_task_struct(next_task);
 
-	return ret;
+	return 1;
 }
 
 /*
@@ -1128,7 +1197,7 @@ static int pull_rt_task(struct rq *this_rq)
 	if (likely(!rt_overloaded(this_rq)))
 		return 0;
 
-	next = pick_next_task_rt(this_rq);
+	next = _pick_next_task_rt(this_rq);
 
 	for_each_cpu_mask_nr(cpu, this_rq->rd->rto_mask) {
 		if (this_cpu == cpu)
@@ -1145,7 +1214,7 @@ static int pull_rt_task(struct rq *this_rq)
 		if (double_lock_balance(this_rq, src_rq)) {
 			struct task_struct *old_next = next;
 
-			next = pick_next_task_rt(this_rq);
+			next = _pick_next_task_rt(this_rq);
 			if (next != old_next)
 				ret = 1;
 		}
@@ -1217,7 +1286,7 @@ static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
  */
 static int needs_post_schedule_rt(struct rq *rq)
 {
-	return rq->rt.overloaded ? 1 : 0;
+	return has_pushable_tasks(rq);
 }
 
 static void post_schedule_rt(struct rq *rq)
@@ -1240,7 +1309,7 @@ static void task_wake_up_rt(struct rq *rq, struct task_struct *p)
 {
 	if (!task_running(rq, p) &&
 	    !test_tsk_need_resched(rq->curr) &&
-	    rq->rt.overloaded &&
+	    has_pushable_tasks(rq) &&
 	    p->rt.nr_cpus_allowed > 1)
 		push_rt_tasks(rq);
 }
@@ -1277,6 +1346,24 @@ static void set_cpus_allowed_rt(struct task_struct *p,
 	if (p->se.on_rq && (weight != p->rt.nr_cpus_allowed)) {
 		struct rq *rq = task_rq(p);
 
+		if (!task_current(rq, p)) {
+			/*
+			 * Make sure we dequeue this task from the pushable list
+			 * before going further.  It will either remain off of
+			 * the list because we are no longer pushable, or it
+			 * will be requeued.
+			 */
+			if (p->rt.nr_cpus_allowed > 1)
+				dequeue_pushable_task(rq, p);
+
+			/*
+			 * Requeue if our weight is changing and still > 1
+			 */
+			if (weight > 1)
+				enqueue_pushable_task(rq, p);
+
+		}
+
 		if ((p->rt.nr_cpus_allowed <= 1) && (weight > 1)) {
 			rq->rt.rt_nr_migratory++;
 		} else if ((p->rt.nr_cpus_allowed > 1) && (weight <= 1)) {

kernel/sched_rt.c static void set_curr_task_rt(struct rq *rq) · line 1548

Quoted 9 lines
kernel/sched_rt.c +3 -0
@@ -1453,6 +1540,9 @@ static void set_curr_task_rt(struct rq *rq)
 	struct task_struct *p = rq->curr;
 
 	p->se.exec_start = rq->clock;
+
+	/* The running task is never eligible for pushing */
+	dequeue_pushable_task(rq, p);
 }
 
 static const struct sched_class rt_sched_class = {

OK, I like the patch, but I'm not 100% that it doesn't have bugs. I'll ACK it, but this definitely needs to be heavily tested, before going mainline. But for linux-tip, -mm, or linux-next, I think it is, on the surface, good to go (with the added BUG_ONs).

Quoted 4 lines

I'll pull it into -rt as well.

Thanks Steve, Ill spin a v4 with the fixes you requested and get it out to you.

-Greg