lib/plist: Provide plist_add_head() for nodes with the same prio
Subsystems (2)
PATCH v6 1/3 lib/plist: Provide plist_add_head() for nodes with the same prio
From: Xunlei Pang <[email protected]>
If there're multiple nodes with the same prio as @node, currently plist_add() will add @node behind all of them. Now we need to add @node before all of these nodes for SMP RT scheduler.
This patch adds a common __plist_add() for adding @node before or after existing nodes with the same prio, then adds plist_add_head() and plist_add_tail() inline wrapper functions for convenient uses.
Finally, define plist_add() as plist_add_tail() which has the same behaviour as before.
---v5->v6:
Add more detailed annotations.
include/linux/plist.h | 30 +++++++++++++++++++++++++++++- lib/plist.c | 28 +++++++++++++++++++++++----- 2 files changed, 52 insertions(+), 6 deletions(-)
include/linux/plist.h +29 -1
@@ -138,7 +138,35 @@ static inline void plist_node_init(struct plist_node *node, int prio)INIT_LIST_HEAD (&node->node_list); } -extern void plist_add (struct plist_node *node,struct plist_head *head); +extern void __plist_add (struct plist_node *node, +struct plist_head *head,bool is_head); + +/** +* plist_add_head - add @node to @head, before all existing same-prio nodes +* +* @node: The plist_node to be added to @head +* @head: The plist_head that @node is being added to +*/ +static inline +void plist_add_head (struct plist_node *node,struct plist_head *head) +{ +__plist_add (node, head, true); +} + +/** +* plist_add_tail - add @node to @head, after all existing same-prio nodes +* +* @node: The plist_node to be added to @head +* @head: The plist_head that @node is being added to +*/ +static inline +void plist_add_tail (struct plist_node *node,struct plist_head *head) +{ +__plist_add (node, head, false); +} + +#define plist_add plist_add_tail +extern void plist_del (struct plist_node *node,struct plist_head *head);extern void plist_requeue (struct plist_node *node,struct plist_head *head);
lib/plist.c +23 -5
@@ -66,12 +66,18 @@ static void plist_check_head(struct plist_head *head)#endif /** -* plist_add - add @node to @head +* __plist_add - add @node to @head * -* @node: &struct plist_node pointer -* @head: &struct plist_head pointer +* @node: The plist_node to be added to @head +* @head: The plist_head that @node is being added to +* @is_head: True if adding to head of prio list, false otherwise +* +* For nodes of the same prio, @node will be added at the +* head of previously added nodes if @is_head is true, or +* it will be added at the tail of previously added nodes +* if @is_head is false. */ -void plist_add (struct plist_node *node,struct plist_head *head) +void __plist_add (struct plist_node *node,struct plist_head *head,bool is_head) {struct plist_node *first, *iter, *prev =NULL ;struct list_head *node_next = &head->node_list;
@@ -96,8 +102,20 @@ void plist_add(struct plist_node *node, struct plist_head *head) struct plist_node, prio_list); }while (iter != first); -if (!prev || prev->prio != node->prio) +if (!prev || prev->prio != node->prio) {list_add_tail (&node->prio_list, &iter->prio_list); + }else if (is_head) { +/* +* prev has the same priority as the node that is being +* added. It is also the first node for this priority, +* but the new node needs to be added ahead of it. +* To accomplish this, replace prev in the prio_list +* with node. Then set node_next to prev->node_list so +* that the new node gets added before prev and not iter. +*/ +list_replace_init (&prev->prio_list, &node->prio_list); + node_next = &prev->node_list; + } ins_node:list_add_tail (&node->node_list, node_next);
Signature · 1 line
1.9.1
PATCH v6 2/3 sched/rt: Fix wrong SMP scheduler behavior for equal prio cases
From: Xunlei Pang <[email protected]>
Currently, SMP RT scheduler has some trouble in dealing with equal prio cases.
For example, in check_preempt_equal_prio():
When RT1(current task) gets preempted by RT2, if there is a migratable RT3 with same prio, RT3 will be pushed away instead of RT1 afterwards, because RT1 will be enqueued to the tail of the pushable list when going through succeeding put_prev_task_rt() triggered by resched. This broke FIFO.
Furthermore, this is also problematic for normal preempted cases if there're some rt tasks queued with the same prio as current. Because current will be put behind these tasks in the pushable queue.
So, if a task is running and gets preempted by a higher priority task (or even with same priority for migrating), this patch ensures that it is put ahead of any existing task with the same priority in the pushable queue.
---v5->v6:
Add wrapped enqueue_pushable_task_preempted() and enqueue_pushable_task() for __enqueue_pushable_task() to avoid the "bool head" parameter everywhere.
kernel/sched/rt.c | 41 +++++++++++++++++++++++++++++++++++++---- 1 file changed, 37 insertions(+), 4 deletions(-)
kernel/sched/rt.c +37 -4
@@ -359,17 +359,32 @@ static inline void set_post_schedule(struct rq *rq) rq->post_schedule =has_pushable_tasks (rq); } -static void enqueue_pushable_task (struct rq *rq,struct task_struct *p) +static void +__enqueue_pushable_task (struct rq *rq,struct task_struct *p,bool head) {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); +if (head) +plist_add_head (&p->pushable_tasks, &rq->rt.pushable_tasks); +else +plist_add_tail (&p->pushable_tasks, &rq->rt.pushable_tasks);/* Update the highest prio pushable task */ if (p->prio < rq->rt.highest_prio.next) rq->rt.highest_prio.next = p->prio; } +static inline +void enqueue_pushable_task_preempted (struct rq *rq,struct task_struct *p) +{ +__enqueue_pushable_task (rq, p, true); +} + +static inline void enqueue_pushable_task (struct rq *rq,struct task_struct *p) +{ +__enqueue_pushable_task (rq, p, false); +} +static void dequeue_pushable_task (struct rq *rq,struct task_struct *p) {plist_del (&p->pushable_tasks, &rq->rt.pushable_tasks);
@@ -385,6 +400,11 @@ static void dequeue_pushable_task(struct rq *rq, struct task_struct *p)#else +static inline +void enqueue_pushable_task_preempted (struct rq *rq,struct task_struct *p) +{ +} +static inline void enqueue_pushable_task (struct rq *rq,struct task_struct *p) { }
@@ -1506,8 +1526,21 @@ static void put_prev_task_rt(struct rq *rq, struct task_struct *p)* The previous task needs to be made eligible for pushing * if it is still active */ -if (on_rt_rq (&p->rt) && p->nr_cpus_allowed >1 ) -enqueue_pushable_task (rq, p); +if (on_rt_rq (&p->rt) && p->nr_cpus_allowed >1 ) { +/* +* put_prev_task_rt() is called by many functions, +* pick_next_task_rt() is the only one may have +* PREEMPT_ACTIVE set. So if detecting p(current +* task) is preempted in such case, we should +* enqueue it to the front of the pushable plist, +* as there may be multiple tasks with the same +* priority as p. +*/ +if (preempt_count () &PREEMPT_ACTIVE ) +enqueue_pushable_task_preempted (rq, p); +else +enqueue_pushable_task (rq, p); + } }#ifdef CONFIG_SMP
Signature · 1 line
1.9.1
Steven Rostedt
reviewerRe: [PATCH v6 2/3] sched/rt: Fix wrong SMP scheduler behavior for equal prio cases
Quoted 8 lines · On Mon, 20 Apr 2015 16:22:47 +0800 Xunlei Pang <[email protected]> wrote:
static inline void
enqueue_pushable_task(struct rq *rq, struct task_struct *p){
}kernel/sched/rt.c +0
-1@@ -1506,8 +1526,21 @@ static void put_prev_task_rt(struct rq *rq, struct task_struct *p)* The previous task needs to be made eligible for pushing * if it is still active */ -if (on_rt_rq (&p->rt) && p->nr_cpus_allowed >1 )
kernel/sched/rt.c static void put_prev_task_rt(struct rq *rq, struct task_struct *p) · line 1537
Quoted 10 lines
kernel/sched/rt.c +9
-1-enqueue_pushable_task (rq, p); +if (on_rt_rq (&p->rt) && p->nr_cpus_allowed >1 ) { +/* +* put_prev_task_rt() is called by many functions, +* pick_next_task_rt() is the only one may have +* PREEMPT_ACTIVE set. So if detecting p(current +* task) is preempted in such case, we should +* enqueue it to the front of the pushable plist, +* as there may be multiple tasks with the same +* priority as p.
The above comment is very difficult to understand. Maybe something like:
/*
* When put_prev_task_rt() is called by
* pick_next_task_rt(), if PREEMPT_ACTIVE is set, it
* means that the current rt task is being preempted by
* a higher priority task. To maintain FIFO, it must
* stay ahead of any other task that is queued at the
* same priority.
*/
-- Steve
Quoted 9 lines
kernel/sched/rt.c +6
-0+*/ +if (preempt_count () &PREEMPT_ACTIVE ) +enqueue_pushable_task_preempted (rq, p); +else +enqueue_pushable_task (rq, p); + } }#ifdef CONFIG_SMP
Peter Zijlstra
maintainerRe: [PATCH v6 2/3] sched/rt: Fix wrong SMP scheduler behavior for equal prio cases
Quoted 35 lines · Steven Rostedt
Quoted 8 lines · On Mon, 20 Apr 2015 16:22:47 +0800 Xunlei Pang <[email protected]> wrote:
static inline void
enqueue_pushable_task(struct rq *rq, struct task_struct *p){
}kernel/sched/rt.c +0
-1@@ -1506,8 +1526,21 @@ static void put_prev_task_rt(struct rq *rq, struct task_struct *p)* The previous task needs to be made eligible for pushing * if it is still active */ -if (on_rt_rq (&p->rt) && p->nr_cpus_allowed >1 )kernel/sched/rt.c static void put_prev_task_rt(struct rq *rq, struct task_struct *p) · line 1537
Quoted 10 lines
kernel/sched/rt.c +9
-1-enqueue_pushable_task (rq, p); +if (on_rt_rq (&p->rt) && p->nr_cpus_allowed >1 ) { +/* +* put_prev_task_rt() is called by many functions, +* pick_next_task_rt() is the only one may have +* PREEMPT_ACTIVE set. So if detecting p(current +* task) is preempted in such case, we should +* enqueue it to the front of the pushable plist, +* as there may be multiple tasks with the same +* priority as p. The above comment is very difficult to understand. Maybe something like:
/*
* Whenput_prev_task_rt()is called by
*pick_next_task_rt(), ifPREEMPT_ACTIVEis set, it
* means that the current rt task is being preempted by
* a higher priority task. To maintain FIFO, it must
* stay ahead of any other task that is queued at the
* same priority.
*/-- Steve
Quoted 7 lines
kernel/sched/rt.c static void put_prev_task_rt(struct rq *rq, struct task_struct *p) · line 1544
Quoted 7 lines
kernel/sched/rt.c +6
-0+*/ +if (preempt_count () &PREEMPT_ACTIVE ) +enqueue_pushable_task_preempted (rq, p); +else +enqueue_pushable_task (rq, p); + } }
This looks wrong, what do you want to find? _any_ preemption? In that case PREEMPT_ACTIVE is wrong. What you need to check is if the task is still on the RQ or not.
If the task was put to sleep it got dequeued, if it was not dequeued, it got preempted.
PREEMPT_ACTIVE is only ever set for forced kernel preemption, which is a special sub case only ever triggered with CONFIG_PREEMPT=y.
Steven Rostedt
reviewerRe: [PATCH v6 2/3] sched/rt: Fix wrong SMP scheduler behavior for equal prio cases
Quoted 12 lines · On Mon, 20 Apr 2015 19:20:48 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 7 lines
kernel/sched/rt.c static void put_prev_task_rt(struct rq *rq, struct task_struct *p) · line 1544
Quoted 7 lines
kernel/sched/rt.c +6
-0+*/ +if (preempt_count () &PREEMPT_ACTIVE ) +enqueue_pushable_task_preempted (rq, p); +else +enqueue_pushable_task (rq, p); + } }This looks wrong, what do you want to find? _any_ preemption? In that case
PREEMPT_ACTIVEis wrong. What you need to check is if the task is still on the RQ or not.
Quoted 5 lines
If the task was put to sleep it got dequeued, if it was not dequeued, it got preempted.
PREEMPT_ACTIVEis only ever set for forced kernel preemption, which is a special sub case only ever triggered withCONFIG_PREEMPT=y.
Ah, you're right. I was thinking of just forced preemption, but, I wasn't thinking about voluntary preemption (preemption points). We want this behavior for that too (for kernel).
And yes, if we preempt in user space, this isn't enough either.
Actually, I think we only care if the state of the task is TASK_RUNNING, if it is anything else, the task is probably going to sleep anyway and we don't care about FIFO order then.
-- Steve
Peter Zijlstra
maintainerRe: [PATCH v6 2/3] sched/rt: Fix wrong SMP scheduler behavior for equal prio cases
Quoted 25 lines · Steven Rostedt
Quoted 12 lines · On Mon, 20 Apr 2015 19:20:48 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 7 lines
kernel/sched/rt.c static void put_prev_task_rt(struct rq *rq, struct task_struct *p) · line 1544
Quoted 7 lines
kernel/sched/rt.c +6
-0+*/ +if (preempt_count () &PREEMPT_ACTIVE ) +enqueue_pushable_task_preempted (rq, p); +else +enqueue_pushable_task (rq, p); + } }This looks wrong, what do you want to find? _any_ preemption? In that case
PREEMPT_ACTIVEis wrong. What you need to check is if the task is still on the RQ or not.Quoted 5 lines
If the task was put to sleep it got dequeued, if it was not dequeued, it got preempted.
PREEMPT_ACTIVEis only ever set for forced kernel preemption, which is a special sub case only ever triggered withCONFIG_PREEMPT=y.Ah, you're right. I was thinking of just forced preemption, but, I wasn't thinking about voluntary preemption (preemption points). We want this behavior for that too (for kernel).
Quoted 5 lines
And yes, if we preempt in user space, this isn't enough either.
Actually, I think we only care if the state of the task is
TASK_RUNNING, if it is anything else, the task is probably going to sleep anyway and we don't care about FIFO order then.
Please don't try and be clever there :-) Task state can be misleading, you might get a wakeup before you're running again, in which case you never went to sleep.
Please use task_on_rq_queued(p) like all other sites.
Steven Rostedt
reviewerRe: [PATCH v6 2/3] sched/rt: Fix wrong SMP scheduler behavior for equal prio cases
Quoted 3 lines · On Tue, 21 Apr 2015 01:45:50 +0200 Peter Zijlstra <[email protected]> wrote:
Please don't try and be clever there :-) Task state can be misleading, you might get a wakeup before you're running again, in which case you never went to sleep.
OK, point taken.
Quoted 2 lines
Please use
task_on_rq_queued(p)like all other sites.
Agreed.
-- Steve
A message that is not in the archive (sent off-list or not yet received): OFB1503F16.1E65406F-ON48257E2E.002B562D-48257E30.0008BFEB@zte.com.cn
Steven Rostedt
reviewerRe: [PATCH v6 2/3] sched/rt: Fix wrong SMP scheduler behavior for equal prio cases
Quoted 39 lines · On Thu, 23 Apr 2015 09:35:12 +0800 [email protected] wrote:
Hi Steve, Peter,
Steven Rostedt <[email protected]> wrote 2015-04-21 AM 01:48:03:
Quoted 11 lines
Quoted 8 lines · On Mon, 20 Apr 2015 19:20:48 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 7 lines
Quoted 7 lines
kernel/sched/rt.c +6
-0+*/ +if (preempt_count () &PREEMPT_ACTIVE ) +enqueue_pushable_task_preempted (rq, p); +else +enqueue_pushable_task (rq, p); + } }Quoted 5 lines
Quoted 5 lines
This looks wrong, what do you want to find? _any_ preemption? In that case
PREEMPT_ACTIVEis wrong. What you need to check is if the task is still on the RQ or not.If the task was put to sleep it got dequeued, if it was not dequeued,
it
Quoted 3 lines
Quoted 3 lines
got preempted.
PREEMPT_ACTIVEis only ever set for forced kernel preemption, which isa
Quoted 7 lines
Quoted 1 line
special sub case only ever triggered with
CONFIG_PREEMPT=y.Ah, you're right. I was thinking of just forced preemption, but, I wasn't thinking about voluntary preemption (preemption points). We want this behavior for that too (for kernel).
And yes, if we preempt in user space, this isn't enough either.
Thanks, I understood this.
So, we can't rely on
PREEMPT_ACTIVEto do the job. Even for forced kernel preemption, it will be problematic for RR policy when running out of time slice intask_tick_rt(), as it callsresched_curr()to do the reschedule.
Quoted 5 lines
So, I think we need to add a flag in
task_structand set it properly when doing real preemption.How about my unfinished patch below for this idea?
Why not use Peter's idea of instead of checking PREEMPT_ACTIVE, just check if the task is on the runqueue or not. If it scheduled out, it would take itself off the runqueue, if it was preempted by anything, it would still be on the run queue, and according to FIFO, it should still maintain CPU ownership over other tasks of the same prio.
-- Steve
A message that is not in the archive (sent off-list or not yet received): OFE3B71874.C9D81693-ON48257E30.0024F69F-48257E30.0025E2D3@zte.com.cn
Steven Rostedt
reviewerRe: [PATCH v6 2/3] sched/rt: Fix wrong SMP scheduler behavior for equal prio cases
Quoted 9 lines · On Thu, 23 Apr 2015 14:53:27 +0800 [email protected] wrote:
Quoted 6 lines
Why not use Peter's idea of instead of checking
PREEMPT_ACTIVE, just check if the task is on the runqueue or not. If it scheduled out, it would take itself off the runqueue, if it was preempted by anything, it would still be on the run queue, and according to FIFO, it should still maintain CPU ownership over other tasks of the same prio.But for
yield()or RR scheduling when running out of time slice, I think this would be still inappropriate, am I missing something?
Good point, I'll have to look into this a bit more.
-- Steve
Peter Zijlstra
maintainerRe: Re: [PATCH v6 2/3] sched/rt: Fix wrong SMP scheduler behavior for equal prio cases
In reply to a message not in the archiveQuoted 2 lines · On Thu, Apr 23, 2015 at 02:53:27PM +0800, [email protected] wrote:
But for
yield()or RR scheduling when running out of time slice, I think this would be still inappropriate, am I missing something?
Those two have explicit hooks you can use to do the right queueing with.
Look at yield_task_rt() and task_tick_rt() both end up doing requeue_task_rt(), which is exactly what you want, no?
A message that is not in the archive (sent off-list or not yet received): OF0B05B4FE.F40C0BE3-ON48257E32.004EF485-48257E32.00513DB3@zte.com.cn
Peter Zijlstra
maintainerRe: Re: Re: [PATCH v6 2/3] sched/rt: Fix wrong SMP scheduler behavior for equal prio cases
Quoted 3 lines · On Sat, Apr 25, 2015 at 10:47:00PM +0800, [email protected] wrote:
We want to do the operation in
put_prev_task_rt(), andput_prev_task_rt()has many call sites.
So I've still no clue wtf you're trying to do, there's words in your changelog but none of them seem to describe the actual problem nor the proposed solution.
A message that is not in the archive (sent off-list or not yet received): OFD410EB1E.5A02675A-ON48257E33.00309252-48257E33.003641FF@zte.com.cn
Steven Rostedt
reviewerRe: [PATCH v6 2/3] sched/rt: Fix wrong SMP scheduler behavior for equal prio cases
Quoted 23 lines · On Sun, 26 Apr 2015 17:52:16 +0800 [email protected] wrote:
The problem I tried to describe here is:
We know, there are two main queues each cpu for RT scheduler:
"run queue" and "pushable queue".For RT tasks, the scheduler uses "plist" to manage the pushable queue, so when there are multiple tasks queued at the same priority, they get queued in the FIFO order.
Currently, when an rt task gets queued, it is put to the head or the tail of its "run queue" according to different scenarios. Then if it is migratable, it will also and always be put to the tail of its "pushable queue".
For one cpu, assuming initially it has multiple migratable tasks queued at the same priority as current(RT) in "run queue" and "pushable queue" both in the same order. At some time, when current gets preempted, it will be put behind these tasks in the "pushable queue", while it still stays ahead of these tasks in the "run queue". Afterwards, if there comes a pull from other cpu or a push from local cpu, the task behind current in the "run queue" will be pulled from the "pushable queue" and gets running.
Quoted 8 lines
Obviously, to maintain the same order between the two queues, when current
is
preempted(not involving re-queue in the "run queue"), we want to put itahead of all those tasks queued at the same priority in the "pushable queue".
-Xunlei
I think what Xunlei is trying to say, is that we don't currently keep FIFO when preemption or migration is involved. If a task is currently running, strict FIFO denotes that it should run ahead of all other tasks queued at its priority or less until it decides to schedule out. But the issue is, if it gets preempted or migrates, it gets placed behind other tasks of the same priority as itself, but it never voluntarily relinquished the CPU.
Thus, if it gets preempted by a higher priority task, it should at a minimum be placed ahead of all other tasks of its priority or less to run on the CPU again. If it gets migrated to another CPU, it should at least be placed ahead of other tasks on that new CPU of the same priority. Although, for the migration case, I'm not sure why it would be migrated to a CPU where it couldn't run right away in the first place, as the push/pull logic only migrates RT tasks that can run on the new CPU. Unless, he's talking about a race where a new task just got scheduled before it made it to the CPU? But that's a separate issue.
But at least for being preempted by a higher priority task, it should be placed back ahead of the currently running tasks, unless it did a yield or is RR and its time ran out.
I'm not sure why your solution with yield_task_rt() and task_tick_rt() doesn't work. Maybe Xunlei is looking too deep into the solution. Monday, I'll try to spend some time looking at the scheduler logic there.
-- Steve
Peter Zijlstra
maintainerRe: [PATCH v6 2/3] sched/rt: Fix wrong SMP scheduler behavior for equal prio cases
Quoted 7 lines · Steven Rostedt
I think what Xunlei is trying to say, is that we don't currently keep FIFO when preemption or migration is involved. If a task is currently running, strict FIFO denotes that it should run ahead of all other tasks queued at its priority or less until it decides to schedule out. But the issue is, if it gets preempted or migrates, it gets placed behind other tasks of the same priority as itself, but it never voluntarily relinquished the CPU.
So 1) FIFO is only defined for UP, anything SMP is well outside of the FIFO spec and therefore we cannot break it.
2) The 'head' of the queue only has meaning on UP, with SMP there's 'n' heads, which of those heads is is the foremost head? That is, we're already lost order, you cannot reconstruct. This cannot be done without first defining order and then implementing that.
The Changelog is completely devoid of useful information.
Quoted 3 lines
Thus, if it gets preempted by a higher priority task, it should at a minimum be placed ahead of all other tasks of its priority or less to run on the CPU again.
Which, with the current status is an impossibility with the exception of SMP=n.
Quoted 3 lines
If it gets migrated to another CPU, it should at
least be placed ahead of other tasks on that new CPU of the same priority.
Who says this task is further 'ahead' than the head on the new CPU?
Quoted 5 lines
Although, for the migration case, I'm not sure why it would be migrated to a CPU where it couldn't run right away in the first place, as the push/pull logic only migrates RT tasks that can run on the new CPU. Unless, he's talking about a race where a new task just got scheduled before it made it to the CPU? But that's a separate issue.
See, even you don't really know wtf he's wanting to do.
Quoted 3 lines
But at least for being preempted by a higher priority task, it should be placed back ahead of the currently running tasks, unless it did a yield or is RR and its time ran out.
AFAICT this is already so. For RT we do not dequeue running tasks (CFS does), so pick_next_task/put_prev_task does not change the location of a task on the queues.
Quoted 4 lines
I'm not sure why your solution with
yield_task_rt()andtask_tick_rt()doesn't work. Maybe Xunlei is looking too deep into the solution. Monday, I'll try to spend some time looking at the scheduler logic there.
No, have Xunlei go write a coherent problem statement, and for as long as you don't understand it send him back to it.
Re: [PATCH v6 2/3] sched/rt: Fix wrong SMP scheduler behavior for equal prio cases
Quoted 9 lines · Peter Zijlstra
Quoted 7 lines · Steven Rostedt
I think what Xunlei is trying to say, is that we don't currently keep FIFO when preemption or migration is involved. If a task is currently running, strict FIFO denotes that it should run ahead of all other tasks queued at its priority or less until it decides to schedule out. But the issue is, if it gets preempted or migrates, it gets placed behind other tasks of the same priority as itself, but it never voluntarily relinquished the CPU.
Quoted 7 lines
So 1) FIFO is only defined for UP, anything SMP is well outside of the FIFO spec and therefore we cannot break it.
2) The 'head' of the queue only has meaning on UP, with SMP there's 'n' heads, which of those heads is is the foremost head? That is, we're already lost order, you cannot reconstruct. This cannot be done without first defining order and then implementing that.
Good luck with that :) Trying to preserve run order across the box led me to a seemingly _endless_ supply of deadlocks while piddling with preemptible spinning locks in rt. Maybe you can pull that off, me it gave serious headaches.
-Mike
PATCH v6 3/3 sched/rt: Check to push the task when changing its affinity
In reply to Xunlei PangFrom: Xunlei Pang <[email protected]>
We may suffer from extra rt overload rq due to the affinity, so when the affinity of any runnable rt task is changed, we should check to trigger balancing, otherwise it will cause some unnecessary delayed real-time response. Unfortunately, current RT global scheduler does nothing about this.
For example: a 2-cpu system with two runnable FIFO tasks(same rt_priority) bound on CPU0, let's name them rt1(running) and rt2(runnable) respectively; CPU1 has no RTs. Then, someone sets the affinity of rt2 to 0x3(i.e. CPU0 and CPU1), but after this, rt2 still can't be scheduled until rt1 enters schedule(), this definitely causes some/big response latency for rt2.
So, when doing set_cpus_allowed_rt(), if detecting such cases, check to trigger a push behaviour.
--- kernel/sched/rt.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 71 insertions(+), 10 deletions(-)
kernel/sched/rt.c +71 -10
@@ -1460,10 +1460,9 @@ 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 *peek_next_task_rt (struct rq *rq) {struct sched_rt_entity *rt_se; -struct task_struct *p;struct rt_rq *rt_rq = &rq->rt; do {
@@ -1472,7 +1471,14 @@ static struct task_struct *_pick_next_task_rt(struct rq *rq) rt_rq =group_rt_rq (rt_se); }while (rt_rq); - p =rt_task_of (rt_se); +return rt_task_of (rt_se); +} + +static inline struct task_struct *_pick_next_task_rt (struct rq *rq) +{ +struct task_struct *p; + + p =peek_next_task_rt (rq); p->se.exec_start =rq_clock_task (rq);return p;
@@ -2096,28 +2102,77 @@ static void set_cpus_allowed_rt(struct task_struct *p, const struct cpumask *new_mask) {struct rq *rq; -int weight; +int old_weight, new_weight; +int preempt_push =0 , direct_push =0 ;BUG_ON (!rt_task (p));if (!task_on_rq_queued (p))return ; - weight =cpumask_weight (new_mask); + old_weight = p->nr_cpus_allowed; + new_weight =cpumask_weight (new_mask); + rq =task_rq (p); + +if (new_weight >1 && +rt_task (rq->curr) && + rq->rt.rt_nr_total >1 && + !test_tsk_need_resched (rq->curr)) { +/* +* We own p->pi_lock and rq->lock. rq->lock might +* get released when doing direct pushing, however +* p->pi_lock is always held, so it's safe to assign +* new_mask and new_weight to p below. +*/ +if (!task_running (rq, p)) { +cpumask_copy (&p->cpus_allowed, new_mask); + p->nr_cpus_allowed = new_weight; + direct_push =1 ; + }else if (cpumask_test_cpu (task_cpu (p), new_mask)) { +struct task_struct *next; + +cpumask_copy (&p->cpus_allowed, new_mask); + p->nr_cpus_allowed = new_weight; +if (!cpupri_find (&rq->rd->cpupri, p,NULL )) + goto update; + +/* +* At this point, current task gets migratable most +* likely due to the change of its affinity, let's +* figure out if we can migrate it. +* +* Can we find any task with the same priority as +* current? To accomplish this, firstly we requeue +* current to the tail and peek next, then restore +* current to the head. +*/ +requeue_task_rt (rq, p,0 ); + next =peek_next_task_rt (rq); +requeue_task_rt (rq, p,1 ); +if (next != p && next->prio == p->prio) { +/* +* Target found, so let's reschedule to try +* and push current away. +*/ +requeue_task_rt (rq, next,1 ); + preempt_push =1 ; + } + } + } + +update:/* * Only update if the process changes its state from whether it * can migrate or not. */ -if ((p->nr_cpus_allowed >1 ) == (weight >1 )) -return ; - - rq =task_rq (p); +if ((old_weight >1 ) == (new_weight >1 )) + goto out;/* * The process used to be able to migrate OR it can now migrate */ -if (weight <=1 ) { +if (new_weight <=1 ) {if (!task_current (rq, p))dequeue_pushable_task (rq, p);BUG_ON (!rq->rt.rt_nr_migratory);
@@ -2129,6 +2184,12 @@ static void set_cpus_allowed_rt(struct task_struct *p, }update_rt_migration (&rq->rt); + +out: +if (direct_push) +push_rt_tasks (rq); +else if (preempt_push) +resched_curr (rq); }/* Assumes rq->lock is held */
Signature · 1 line
1.9.1
Steven Rostedt
reviewerRe: [PATCH v6 3/3] sched/rt: Check to push the task when changing its affinity
Quoted 23 lines · On Mon, 20 Apr 2015 16:22:48 +0800 Xunlei Pang <[email protected]> wrote:
kernel/sched/rt.c +23
-0+ rq =task_rq (p); + +if (new_weight >1 && +rt_task (rq->curr) && + rq->rt.rt_nr_total >1 && + !test_tsk_need_resched (rq->curr)) { +/* +* We own p->pi_lock and rq->lock. rq->lock might +* get released when doing direct pushing, however +* p->pi_lock is always held, so it's safe to assign +* new_mask and new_weight to p below. +*/ +if (!task_running (rq, p)) { +cpumask_copy (&p->cpus_allowed, new_mask); + p->nr_cpus_allowed = new_weight; + direct_push =1 ; + }else if (cpumask_test_cpu (task_cpu (p), new_mask)) { +struct task_struct *next; + +cpumask_copy (&p->cpus_allowed, new_mask); + p->nr_cpus_allowed = new_weight; +if (!cpupri_find (&rq->rd->cpupri, p,NULL )) + goto update;
kernel/sched/rt.c static void set_cpus_allowed_rt(struct task_struct *p, · line 2148
Quoted 10 lines
kernel/sched/rt.c +10
-0+ +/* +* At this point, current task gets migratable most +* likely due to the change of its affinity, let's +* figure out if we can migrate it. +* +* Can we find any task with the same priority as +* current? To accomplish this, firstly we requeue +* current to the tail and peek next, then restore +* current to the head.
"current"? Don't you mean 'p'?
kernel/sched/rt.c static void set_cpus_allowed_rt(struct task_struct *p, · line 2152
Quoted 4 lines
kernel/sched/rt.c +4
-0+*/ +requeue_task_rt (rq, p,0 ); + next =peek_next_task_rt (rq); +requeue_task_rt (rq, p,1 );
Actually, I'm totally confused by all this. Why are you looking at next? The running task (current) should not be in the next_task_rt() list to begin with. If p can not preempt current, and cpupri_find() finds something for p to run on, then move it there, and be done with it.
I also looked at set_cpus_allowed_ptr() and think we should probably add a p->sched_class->pick_cpu() and do:
if (p->sched_class->pick_cpu) dest_cpu = p->sched_class->pick_cpu(p, cpu_active_mask, new_mask); else dest_cpu = cpumask_any_and(cpu_active_mask, new_mask);
Hmm, maybe all this work should be done there, or have do_set_cpus_allowed() return a value that states that the sched_class->set_cpus_allowed() did all the work for us.
-- Steve
Quoted 44 lines
kernel/sched/rt.c +21
-5+if (next != p && next->prio == p->prio) { +/* +* Target found, so let's reschedule to try +* and push current away. +*/ +requeue_task_rt (rq, next,1 ); + preempt_push =1 ; + } + } + } + +update:/* * Only update if the process changes its state from whether it * can migrate or not. */ -if ((p->nr_cpus_allowed >1 ) == (weight >1 )) -return ; - - rq =task_rq (p); +if ((old_weight >1 ) == (new_weight >1 )) + goto out;/* * The process used to be able to migrate OR it can now migrate */ -if (weight <=1 ) { +if (new_weight <=1 ) {if (!task_current (rq, p))dequeue_pushable_task (rq, p);BUG_ON (!rq->rt.rt_nr_migratory);@@ -2129,6 +2184,12 @@ static void set_cpus_allowed_rt(struct task_struct *p, }update_rt_migration (&rq->rt); + +out: +if (direct_push) +push_rt_tasks (rq); +else if (preempt_push) +resched_curr (rq); }/* Assumes rq->lock is held */
Quoted 6 lines · On Mon, 20 Apr 2015 16:22:46 +0800 Xunlei Pang <[email protected]> wrote:
From: Xunlei Pang <[email protected]>
If there're multiple nodes with the same prio as @node, currently
plist_add()will add @node behind all of them. Now we need to add @node before all of these nodes for SMP RT scheduler.
Quoted 8 lines
This patch adds a common
__plist_add()for adding @node before or after existing nodes with the same prio, then addsplist_add_head()andplist_add_tail()inline wrapper functions for convenient uses.Finally, define
plist_add()asplist_add_tail()which has the same behaviour as before.Reviewed-by Dan Streetman <[email protected]>
-- Steve
Quoted 5 lines
Signed-off-by Xunlei Pang <[email protected]>---
v5->v6:
Add more detailed annotations.
Steven Rostedt
reviewerinclude/linux/plist.h static inline void plist_node_init(struct plist_node *node, int prio) · line 168
Quoted 13 lines · On Mon, 20 Apr 2015 16:22:46 +0800 Xunlei Pang <[email protected]> wrote:
include/linux/plist.h +13
-0+/** +* plist_add_tail - add @node to @head, after all existing same-prio nodes +* +* @node: The plist_node to be added to @head +* @head: The plist_head that @node is being added to +*/ +static inline +void plist_add_tail (struct plist_node *node,struct plist_head *head) +{ +__plist_add (node, head, false); +} + +#define plist_add plist_add_tail
I already placed my review by, but this is more of a matter of taste.
I don't think this should be a #define, but instead a static inline. The assembly will end up as the same, but the compiler warnings will be more helpful if it is a static inline, as we don't want "plist_add_tail()" being shown in warnings when the developer never typed in "_tail()".
Thus it should be:
static inline voidplist_add(struct plist_node *node, struct plist_head *head)
{
plist_add_tail(node, head);
}You can keep my Reviewed-by, but please make this update.
-- Steve
Quoted 8 lines
include/linux/plist.h +1
-0+extern void plist_del (struct plist_node *node,struct plist_head *head);extern void plist_requeue (struct plist_node *node,struct plist_head *head);lib/plist.c +0
-0