Possible lock-less list race in scheduler_ipi()
A message that is not in the archive (sent off-list or not yet received): [email protected]
Hi,
I recently reviewed the scheduler_ipi() code by coincidence, and noticed that the use of llist.h in there seemed a bit odd. So I'd like to have more eyes to help me look into this.
I've been told that there has been issues with IPIs lately, so here is one possible scenario I think might be possible:
- scheduler_ipi()
- sched_ttwu_pending()
- llist_del_all()
(grabs the wake_list with xchg())
- raw_spin_lock_irqsave(&rq->lock, flags);
- iteration on the llist (owned locally by interrupt handler) (for each item)
p = llist_entry(llist, struct task_struct, wake_entry); llist = llist_next(llist);
ttwu_do_activate(rq, p, 0);
- raw_spin_unlock_irqrestore(&rq->lock, flags);
ttwu_do_activate() ends up callingttwu_activate() and ttwu_do_wakeup(),
I'm worried that ttwu_do_wakeup() might end up indirectly handing off the task to the following functions (within another execution context):
- try_to_wake_up()
- ttwu_queue()
- ttwu_queue_remote adds the process to another wake_list with a cmpxchg()
llist_next() is pretty simple:
static inline struct llist_node *llist_next(struct llist_node *node)
{
return node->next;
}It is so simple that I wonder if the compiler would be within its rights to reorder the load of node->next after some operations within ttwu_do_activate(), thus causing corruption of this linked-list due to a concurrent try_to_wake_up() performed by another core.
Am I too paranoid about the possible compiler mishaps there, or are my concerns justified ?
Thanks,
Mathieu
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoted 8 lines · Mathieu Desnoyers
llist_next()is pretty simple:static inline struct
llist_node*llist_next(structllist_node*node){ return node->next; }
Quoted 8 lines
It is so simple that I wonder if the compiler would be within its rights to reorder the load of
node->nextafter some operations withinttwu_do_activate(), thus causing corruption of this linked-list due to a concurrenttry_to_wake_up()performed by another core.Am I too paranoid about the possible compiler mishaps there, or are my concerns justified ?
I *think* you are too paranoid, because that would be a major compiler bug anyway - gcc cannot reorder the load against anything that might be changing the value. Which obviously includes calling non-inlined functions.
At least the code generation I see doesn't seem to say that gcc gets this wrong:
...
leaq -32(%rbx), %rsi #, p
movq (%rbx), %rbx # MEM[(struct llist_node
*)__mptr_19].next, __mptr
movq %r12, %rdi # tcp_ptr__,
call ttwu_do_activate.constprop.85 #
...that "movq (%rbx), %rbx" is the "llist = llist_next(llist);" thing.
Linus
----- Original Message -----
Quoted 43 lines
From: "Linus Torvalds" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: "Paul E. McKenney" <[email protected]>, "Huang Ying" <[email protected]>, "Lai Jiangshan" <[email protected]>, "Lai Jiangshan" <[email protected]>, "Peter Zijlstra" <[email protected]>, "LKML" <[email protected]>, "Ingo Molnar" <[email protected]>, "Steven Rostedt" <[email protected]>
Sent: Thursday, March 5, 2015 8:02:06 PM
Subject: Re: Possible lock-less list race inscheduler_ipi()Quoted 8 lines · Mathieu Desnoyers
llist_next()is pretty simple:static inline struct
llist_node*llist_next(structllist_node*node){ return node->next; }Quoted 8 lines
It is so simple that I wonder if the compiler would be within its rights to reorder the load of
node->nextafter some operations withinttwu_do_activate(), thus causing corruption of this linked-list due to a concurrenttry_to_wake_up()performed by another core.Am I too paranoid about the possible compiler mishaps there, or are my concerns justified ?
I *think* you are too paranoid, because that would be a major compiler bug anyway - gcc cannot reorder the load against anything that might be changing the value. Which obviously includes calling non-inlined functions.
At least the code generation I see doesn't seem to say that gcc gets this wrong:
... leaq -32(%rbx), %rsi #, p movq (%rbx), %rbx # MEM[(struct llist_node *)__mptr_19].next, __mptr movq %r12, %rdi # tcp_ptr__, call ttwu_do_activate.constprop.85 # ...
Quoted 1 line
that "movq (%rbx), %rbx" is the "llist =
llist_next(llist);" thing.
Indeed, the compiler should never reorder loads/stores from/to same memory location from a program order POV. What I had in mind is a bit more far-fetched though: it would involve having the compiler reorder this load after a store to another memory location, which would in turn allow another execution context (interrupt or thread) to corrupt the list.
The assembly snippet you show above appears to be OK. However, another compiler may choose to inline ttwu_do_activate, leaving room for more aggressive optimizations.
But I agree that it is rather far-fetched.
Thanks,
Mathieu
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoted 6 lines · On Fri, 6 Mar 2015 14:35:23 +0000 (UTC) Mathieu Desnoyers…
Indeed, the compiler should never reorder loads/stores from/to same memory location from a program order POV. What I had in mind is a bit more far-fetched though: it would involve having the compiler reorder this load after a store to another memory location, which would in turn allow another execution context (interrupt or thread) to corrupt the list.
You mean on another CPU? Because the code you are worried about has interrupts disabled.
-- Steve
----- Original Message -----
Quoted 19 lines
From: "Steven Rostedt" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: "Linus Torvalds" <[email protected]>, "Paul E. McKenney" <[email protected]>, "Huang Ying" <[email protected]>, "Lai Jiangshan" <[email protected]>, "Lai Jiangshan" <[email protected]>, "Peter Zijlstra" <[email protected]>, "LKML" <[email protected]>, "Ingo Molnar" <[email protected]>
Sent: Friday, March 6, 2015 2:03:47 PM
Subject: Re: Possible lock-less list race inscheduler_ipi()Quoted 6 lines · On Fri, 6 Mar 2015 14:35:23 +0000 (UTC) Mathieu Desnoyers…
Indeed, the compiler should never reorder loads/stores from/to same memory location from a program order POV. What I had in mind is a bit more far-fetched though: it would involve having the compiler reorder this load after a store to another memory location, which would in turn allow another execution context (interrupt or thread) to corrupt the list.
Quoted 2 lines
You mean on another CPU? Because the code you are worried about has interrupts disabled.
I'm worried that another CPU could issue try_to_wake_up() on a task concurrently with the llist iteration within sched_ttwu_pending().
AFAIU, ttwu_queue_remote() is called from ttwu_queue() without holding the rq lock. So I'm wondering what prevents corruption of the wake_list in this situation.
Thanks,
Mathieu
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
On Fri, 6 Mar 2015 19:39:44 +0000 (UTC)
Mathieu Desnoyers <[email protected]> wrote:
ask concurrently with the llist iteration within sched_ttwu_pending().
Quoted 4 lines
AFAIU,
ttwu_queue_remote()is called fromttwu_queue()without holding the rq lock. So I'm wondering what prevents corruption of thewake_listin this situation.
I guess if it is on the wake_list, then the task's state is already RUNNING. Any other task can switch a task's state to RUNNING but only the task itself can switch it back to something else. If the task is on the wake_list, it's state is already RUNNING, but it has not run yet. That means any other wakeup will jump to the "goto out" and skip over the ttwu_queue() call.
-- Steve
Quoted 9 lines · On Fri, 6 Mar 2015 15:38:21 -0500 Steven Rostedt <[email protected]> wrote:
On Fri, 6 Mar 2015 19:39:44 +0000 (UTC)
Mathieu Desnoyers <[email protected]> wrote:ask concurrently with the llist iteration within
sched_ttwu_pending().Quoted 4 lines
AFAIU,
ttwu_queue_remote()is called fromttwu_queue()without holding the rq lock. So I'm wondering what prevents corruption of thewake_listin this situation.
Quoted 6 lines
I guess if it is on the
wake_list, then the task's state is already RUNNING. Any other task can switch a task's state to RUNNING but only the task itself can switch it back to something else. If the task is on thewake_list, it's state is already RUNNING, but it has not run yet. That means any other wakeup will jump to the "goto out" and skip over thettwu_queue()call.
If my assumption is indeed the case, then these types of subtleties really need comments in the code.
-- Steve
----- Original Message -----
Quoted 27 lines
From: "Steven Rostedt" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: "Linus Torvalds" <[email protected]>, "Paul E. McKenney" <[email protected]>, "Huang Ying" <[email protected]>, "Lai Jiangshan" <[email protected]>, "Lai Jiangshan" <[email protected]>, "Peter Zijlstra" <[email protected]>, "LKML" <[email protected]>, "Ingo Molnar" <[email protected]>
Sent: Friday, March 6, 2015 3:39:25 PM
Subject: Re: Possible lock-less list race inscheduler_ipi()Quoted 9 lines · On Fri, 6 Mar 2015 15:38:21 -0500 Steven Rostedt <[email protected]> wrote:
On Fri, 6 Mar 2015 19:39:44 +0000 (UTC)
Mathieu Desnoyers <[email protected]> wrote:ask concurrently with the llist iteration within
sched_ttwu_pending().Quoted 4 lines
AFAIU,
ttwu_queue_remote()is called fromttwu_queue()without holding the rq lock. So I'm wondering what prevents corruption of thewake_listin this situation.Quoted 6 lines
I guess if it is on the
wake_list, then the task's state is already RUNNING. Any other task can switch a task's state to RUNNING but only the task itself can switch it back to something else. If the task is on thewake_list, it's state is already RUNNING, but it has not run yet. That means any other wakeup will jump to the "goto out" and skip over thettwu_queue()call.
Quoted 2 lines
If my assumption is indeed the case, then these types of subtleties really need comments in the code.
My understanding is that try_to_wake_up, by calling ttwu_queue(), is responsible for enqueuing the task into the wake_list. Inspection of try_to_wake_up() seems to show that the state of the task is set to TASK_WAKING by try_to_wake_up.
Then when dequeuing the task from the llist, ttwu_do_wakeup sets the task state to TASK_RUNNING.
Both TASK_WAKING and TASK_RUNNING mean that the try_to_wake_up check for if (!(p->state & state)), which is typically done against TASK_NORMAL, will skip the following ttwu_queue() for that task until it is set to TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE again.
So there should not be any double-enqueue AFAIU.
Thanks,
Mathieu
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoted 42 lines · Mathieu Desnoyers
Hi,
I recently reviewed the
scheduler_ipi()code by coincidence, and noticed that the use ofllist.hin there seemed a bit odd. So I'd like to have more eyes to help me look into this.I've been told that there has been issues with IPIs lately, so here is one possible scenario I think might be possible:
-
scheduler_ipi()
-sched_ttwu_pending()
-llist_del_all()
(grabs thewake_listwithxchg())
-raw_spin_lock_irqsave(&rq->lock, flags);
- iteration on the llist (owned locally by interrupt handler) (for each item)
p =llist_entry(llist, struct task_struct, wake_entry); llist =llist_next(llist);
ttwu_do_activate(rq, p, 0);
-raw_spin_unlock_irqrestore(&rq->lock, flags);
ttwu_do_activate()ends up callingttwu_activate()andttwu_do_wakeup(),I'm worried that
ttwu_do_wakeup()might end up indirectly handing off the task to the following functions (within another execution context):-
try_to_wake_up()
-ttwu_queue()
-ttwu_queue_remoteadds the process to anotherwake_listwith acmpxchg()
llist_next()is pretty simple:static inline struct
llist_node*llist_next(structllist_node*node){ return node->next; }
Quoted 5 lines
It is so simple that I wonder if the compiler would be within its rights to reorder the load of
node->nextafter some operations withinttwu_do_activate(), thus causing corruption of this linked-list due to a concurrenttry_to_wake_up()performed by another core.
Well, it clearly cannot leak this load out of the critical section. That said, there is nothing in llist_next() that tells the compiler that it need to be careful with this load.
And all three functions, sched_ttwu_pending(), ttwu_do_activate(), and llist_next(), are in the same compilation unit. The compiler therefore has full knowledge, and full ability to rearrange. It can slide this load down past the CONFIG_SMP #ifdef in ttwu_do_activate() and into ttwu_activate(). However, it cannot push it past the call to sched_clock_cpu(), which is defined in the separate compilation unit kernel/sched/clock.c. And sched_clock_cpu() is invoked from update_rq_clock(), which is invoked from enqueue_task(), which is invoked from activate_task(), which is invoked from ttwu_activate(). And even if sched_clock_cpu() was in the same compilation unit, its preempt_disable_notrace() keeps the compiler from reordering. At least it does if the compiler cannot prove that sched_clock_cpu() takes one of two early exits. ;-)
So I am not seeing anything important that the compiler could reorder this past. The CPU might do additional reordering, of course.
Quoted 2 lines
Am I too paranoid about the possible compiler mishaps there, or are my concerns justified ?
Now try_to_wake_up() does acquire p->pi_lock, but that of course does not exclude sched_ttwu_pending(), which instead acquires rq->lock.
And in a virtualized environment, sched_ttwu_pending() can be preempted and delayed pretty much arbitrarily pretty much anywhere, even when its interrupts are disabled.
So let's look at the llist code. One question is of course "How does llist_add_batch() avoid the ABA problem?" In this case, the answer appears to be that llist_del_all() is used, and never llist_del_first(). (Mixing use of llist_del_all() and llist_del_first() by multiple threads could cause this ABA problem, even if only one thread at a time used llist_del_first().)
The code does appear to assume that if a given task is on the local llist, that it cannot be awakened any other way without acquiring the same runqueue lock that sched_ttwu_pending() holds. If this rule was violated, then of course the list could be corrupted. However, the only accesses to the list appear to be sched_ttwu_pending()'s llist_del_all(), ttwu_queue_remote()'s llist_add(), and a couple of llist_empty() calls. This combination appears to me to be safe.
The scheduler_ipi() code assumes that an IPI cannot outrun data. If this is violated, the scheduler_ipi() might still see an empty ->wake_list() even though the sender of the IPI just filled it. The last time I worked with a machine that violated this assumption was about twenty years ago, and I very much hope that such hardware designs have not come back from the dead. But this would cause a hang, not a corrupt list.
So, does this trigger any helpful thoughts?
Thanx, Paul