Hi,
Partially based on the findings from Waiman Long:
a) The memory barriers in ipc are not properly documented, and at least
for some architectures insufficient:
Reading the xyz->status is only a control barrier, thus
smp_acquire__after_ctrl_dep() was missing in mqueue.c and msg.c
sem.c contained a full smp_mb(), which is not required.
Patch 1: Document that wake_q_add() contains a barrier.
b) wake_q_add() provides a memory barrier, ipc/mqueue.c relies on this.
Move the documentation to wake_q_add(), instead writing it in ipc/mqueue.c
Patch 2-4: Update the ipc code, especially add missing
smp_mb__after_ctrl_dep().
c) [optional]
Clarify that smp_mb__{before,after}_atomic() are compatible with all
RMW atomic operations, not just the operations that do not return a value.
Patch 5: Documentation for smp_mb__{before,after}_atomic().
From my point of view, patch 1 is a prerequisite for patches 2-4:
If the barrier is not part of the documented API, then ipc should not rely
on it, i.e. then I would propose to replace the WRITE_ONCE with
smp_store_release().
Open issues:
- More testing. I did some tests, but doubt that the tests would be
sufficient to show issues with regards to incorrect memory barriers.
- Should I add a "Fixes:" or "Cc:stable"? The only issues that I see are
the missing smp_mb__after_ctrl_dep(), and WRITE_ONCE() vs.
"ptr = NULL".
What do you think?
--
Manfred
Update and document memory barriers for mqueue.c:
- ewp->state is read without any locks, thus READ_ONCE is required.
- add smp_aquire__after_ctrl_dep() after the RAED_ONCE, we need
acquire semantics if the value is STATE_READY.
- document that the code relies on the barrier inside wake_q_add()
- document why __set_current_state() may be used:
Reading task->state cannot happen before the wake_q_add() call,
which happens while holding info->lock.
Signed-off-by: Manfred Spraul <[email protected]>
Cc: Waiman Long <[email protected]>
Cc: Davidlohr Bueso <[email protected]>
---
ipc/mqueue.c | 32 +++++++++++++++++++++-----------
1 file changed, 21 insertions(+), 11 deletions(-)
diff --git a/ipc/mqueue.c b/ipc/mqueue.c
index 3d920ff15c80..902167407737 100644
--- a/ipc/mqueue.c
+++ b/ipc/mqueue.c
@@ -646,17 +646,25 @@ static int wq_sleep(struct mqueue_inode_info *info, int sr,
wq_add(info, sr, ewp);
for (;;) {
+ /* memory barrier not required, we hold info->lock */
__set_current_state(TASK_INTERRUPTIBLE);
spin_unlock(&info->lock);
time = schedule_hrtimeout_range_clock(timeout, 0,
HRTIMER_MODE_ABS, CLOCK_REALTIME);
- if (ewp->state == STATE_READY) {
+ if (READ_ONCE(ewp->state) == STATE_READY) {
+ /*
+ * Pairs, together with READ_ONCE(), with
+ * the barrier in wake_q_add().
+ */
+ smp_acquire__after_ctrl_dep();
retval = 0;
goto out;
}
spin_lock(&info->lock);
+
+ /* we hold info->lock, so no memory barrier required */
if (ewp->state == STATE_READY) {
retval = 0;
goto out_unlock;
@@ -928,16 +936,11 @@ static inline void pipelined_send(struct wake_q_head *wake_q,
{
receiver->msg = message;
list_del(&receiver->list);
+
wake_q_add(wake_q, receiver->task);
- /*
- * Rely on the implicit cmpxchg barrier from wake_q_add such
- * that we can ensure that updating receiver->state is the last
- * write operation: As once set, the receiver can continue,
- * and if we don't have the reference count from the wake_q,
- * yet, at that point we can later have a use-after-free
- * condition and bogus wakeup.
- */
- receiver->state = STATE_READY;
+
+ /* The memory barrier is provided by wake_q_add(). */
+ WRITE_ONCE(receiver->state, STATE_READY);
}
/* pipelined_receive() - if there is task waiting in sys_mq_timedsend()
@@ -956,8 +959,11 @@ static inline void pipelined_receive(struct wake_q_head *wake_q,
return;
list_del(&sender->list);
+
wake_q_add(wake_q, sender->task);
- sender->state = STATE_READY;
+
+ /* The memory barrier is provided by wake_q_add(). */
+ WRITE_ONCE(sender->state, STATE_READY);
}
static int do_mq_timedsend(mqd_t mqdes, const char __user *u_msg_ptr,
@@ -1044,6 +1050,8 @@ static int do_mq_timedsend(mqd_t mqdes, const char __user *u_msg_ptr,
} else {
wait.task = current;
wait.msg = (void *) msg_ptr;
+
+ /* memory barrier not required, we hold info->lock */
wait.state = STATE_NONE;
ret = wq_sleep(info, SEND, timeout, &wait);
/*
@@ -1147,6 +1155,8 @@ static int do_mq_timedreceive(mqd_t mqdes, char __user *u_msg_ptr,
ret = -EAGAIN;
} else {
wait.task = current;
+
+ /* memory barrier not required, we hold info->lock */
wait.state = STATE_NONE;
ret = wq_sleep(info, RECV, timeout, &wait);
msg_ptr = wait.msg;
--
2.21.0
1) wake_q_add() contains a memory barrier, and callers such as
ipc/mqueue.c rely on this barrier.
Unfortunately, this is documented in ipc/mqueue.c, and not in the
description of wake_q_add().
Therefore: Update the documentation.
Removing/updating ipc/mqueue.c will happen with the next patch in the
series.
2) wake_up_q() relies on the memory barrier in try_to_wake_up().
Add a comment, to simplify searching.
3) wake_q.next is accessed without synchroniyation by wake_q_add(),
using cmpxchg_relaxed(), and by wake_up_q().
Therefore: Use WRITE_ONCE in wake_up_q(), to ensure that the
compiler doesn't perform any tricks.
Signed-off-by: Manfred Spraul <[email protected]>
Cc: Davidlohr Bueso <[email protected]>
---
kernel/sched/core.c | 12 +++++++++---
1 file changed, 9 insertions(+), 3 deletions(-)
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index dd05a378631a..2cf3f7321303 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -440,8 +440,11 @@ static bool __wake_q_add(struct wake_q_head *head, struct task_struct *task)
* @task: the task to queue for 'later' wakeup
*
* Queue a task for later wakeup, most likely by the wake_up_q() call in the
- * same context, _HOWEVER_ this is not guaranteed, the wakeup can come
- * instantly.
+ * same context, _HOWEVER_ this is not guaranteed. Especially, the wakeup
+ * may happen before the function returns.
+ *
+ * What is guaranteed is that there is a memory barrier before the wakeup,
+ * callers may rely on this barrier.
*
* This function must be used as-if it were wake_up_process(); IOW the task
* must be ready to be woken at this location.
@@ -486,11 +489,14 @@ void wake_up_q(struct wake_q_head *head)
BUG_ON(!task);
/* Task can safely be re-inserted now: */
node = node->next;
- task->wake_q.next = NULL;
+
+ WRITE_ONCE(task->wake_q.next, NULL);
/*
* wake_up_process() executes a full barrier, which pairs with
* the queueing in wake_q_add() so as not to miss wakeups.
+ * The barrier is the smp_mb__after_spinlock() in
+ * try_to_wake_up().
*/
wake_up_process(task);
put_task_struct(task);
--
2.21.0
On Fri, 11 Oct 2019, Manfred Spraul wrote:
>Update and document memory barriers for mqueue.c:
>- ewp->state is read without any locks, thus READ_ONCE is required.
In general we relied on the barrier for not needing READ/WRITE_ONCE,
but I agree this scenario should be better documented with them.
Similarly imo, the 'state' should also need them for write, even if
under the lock -- consistency and documentation, for example.
In addition, I think it makes sense to encapsulate some of the
pipelined send/recv operations, that also can allow us to keep
the barrier comments in pipelined_send(), which I wonder why
you chose to remove. Something like so, before your changes:
diff --git a/ipc/mqueue.c b/ipc/mqueue.c
index 3d920ff15c80..be48c0ba92f7 100644
--- a/ipc/mqueue.c
+++ b/ipc/mqueue.c
@@ -918,17 +918,12 @@ SYSCALL_DEFINE1(mq_unlink, const char __user *, u_name)
* The same algorithm is used for senders.
*/
-/* pipelined_send() - send a message directly to the task waiting in
- * sys_mq_timedreceive() (without inserting message into a queue).
- */
-static inline void pipelined_send(struct wake_q_head *wake_q,
+static inline void __pipelined_op(struct wake_q_head *wake_q,
struct mqueue_inode_info *info,
- struct msg_msg *message,
- struct ext_wait_queue *receiver)
+ struct ext_wait_queue *this)
{
- receiver->msg = message;
- list_del(&receiver->list);
- wake_q_add(wake_q, receiver->task);
+ list_del(&this->list);
+ wake_q_add(wake_q, this->task);
/*
* Rely on the implicit cmpxchg barrier from wake_q_add such
* that we can ensure that updating receiver->state is the last
@@ -937,7 +932,19 @@ static inline void pipelined_send(struct wake_q_head *wake_q,
* yet, at that point we can later have a use-after-free
* condition and bogus wakeup.
*/
- receiver->state = STATE_READY;
+ this->state = STATE_READY;
+}
+
+/* pipelined_send() - send a message directly to the task waiting in
+ * sys_mq_timedreceive() (without inserting message into a queue).
+ */
+static inline void pipelined_send(struct wake_q_head *wake_q,
+ struct mqueue_inode_info *info,
+ struct msg_msg *message,
+ struct ext_wait_queue *receiver)
+{
+ receiver->msg = message;
+ __pipelined_op(wake_q, info, receiver);
}
/* pipelined_receive() - if there is task waiting in sys_mq_timedsend()
@@ -955,9 +962,7 @@ static inline void pipelined_receive(struct wake_q_head *wake_q,
if (msg_insert(sender->msg, info))
return;
- list_del(&sender->list);
- wake_q_add(wake_q, sender->task);
- sender->state = STATE_READY;
+ __pipelined_op(wake_q, info, sender);
}
static int do_mq_timedsend(mqd_t mqdes, const char __user *u_msg_ptr,
On 10/11/19 6:55 PM, Davidlohr Bueso wrote:
> On Fri, 11 Oct 2019, Manfred Spraul wrote:
>
>> Update and document memory barriers for mqueue.c:
>> - ewp->state is read without any locks, thus READ_ONCE is required.
>
> In general we relied on the barrier for not needing READ/WRITE_ONCE,
> but I agree this scenario should be better documented with them.
After reading core-api/atomic_ops.rst:
> _ONCE() should be used. [...] Alternatively, you can place a barrier.
So both approaches are ok.
Let's follow the "should", i.e.: all operations on the ->state variables
to READ_ONCE()/WRITE_ONCE().
Then we have a standard, and since we can follow the "should", we should
do that.
> Similarly imo, the 'state' should also need them for write, even if
> under the lock -- consistency and documentation, for example.
>
Ok, so let's convert everything to _ONCE. (assuming that my analysis
below is incorrect)
> In addition, I think it makes sense to encapsulate some of the
> pipelined send/recv operations, that also can allow us to keep
> the barrier comments in pipelined_send(), which I wonder why
> you chose to remove. Something like so, before your changes:
>
I thought that the simple "memory barrier is provided" is enough, so I
had removed the comment.
But you are right, there are two different scenarios:
1) thread already in another wake_q, wakeup happens immediately after
the cmpxchg_relaxed().
This scenario is safe, due to the smp_mb__before_atomic() in wake_q_add()
2) thread woken up but e.g. a timeout, see ->state=STATE_READY, returns
to user space, calls sys_exit.
This must not happen before get_task_struct acquired a reference.
And this appears to be unsafe: get_task_struct() is refcount_inc(),
which is refcount_inc_checked(), which is according to lib/refcount.c
fully unordered.
Thus: ->state=STATE_READY can execute before the refcount increase.
Thus: ->state=STATE_READY needs a smp_store_release(), correct?
> diff --git a/ipc/mqueue.c b/ipc/mqueue.c
> index 3d920ff15c80..be48c0ba92f7 100644
> --- a/ipc/mqueue.c
> +++ b/ipc/mqueue.c
> @@ -918,17 +918,12 @@ SYSCALL_DEFINE1(mq_unlink, const char __user *,
> u_name)
> * The same algorithm is used for senders.
> */
>
> -/* pipelined_send() - send a message directly to the task waiting in
> - * sys_mq_timedreceive() (without inserting message into a queue).
> - */
> -static inline void pipelined_send(struct wake_q_head *wake_q,
> +static inline void __pipelined_op(struct wake_q_head *wake_q,
> struct mqueue_inode_info *info,
> - struct msg_msg *message,
> - struct ext_wait_queue *receiver)
> + struct ext_wait_queue *this)
> {
> - receiver->msg = message;
> - list_del(&receiver->list);
> - wake_q_add(wake_q, receiver->task);
> + list_del(&this->list);
> + wake_q_add(wake_q, this->task);
> /*
> * Rely on the implicit cmpxchg barrier from wake_q_add such
> * that we can ensure that updating receiver->state is the last
> @@ -937,7 +932,19 @@ static inline void pipelined_send(struct
> wake_q_head *wake_q,
> * yet, at that point we can later have a use-after-free
> * condition and bogus wakeup.
> */
> - receiver->state = STATE_READY;
> + this->state = STATE_READY;
> +}
> +
> +/* pipelined_send() - send a message directly to the task waiting in
> + * sys_mq_timedreceive() (without inserting message into a queue).
> + */
> +static inline void pipelined_send(struct wake_q_head *wake_q,
> + struct mqueue_inode_info *info,
> + struct msg_msg *message,
> + struct ext_wait_queue *receiver)
> +{
> + receiver->msg = message;
> + __pipelined_op(wake_q, info, receiver);
> }
>
> /* pipelined_receive() - if there is task waiting in sys_mq_timedsend()
> @@ -955,9 +962,7 @@ static inline void pipelined_receive(struct
> wake_q_head *wake_q,
> if (msg_insert(sender->msg, info))
> return;
>
> - list_del(&sender->list);
> - wake_q_add(wake_q, sender->task);
> - sender->state = STATE_READY;
> + __pipelined_op(wake_q, info, sender);
> }
>
> static int do_mq_timedsend(mqd_t mqdes, const char __user *u_msg_ptr,
I would merge that into the series, ok?
--
Manfred
On Fri, 11 Oct 2019, Manfred Spraul wrote:
>But you are right, there are two different scenarios:
>
>1) thread already in another wake_q, wakeup happens immediately after
>the cmpxchg_relaxed().
>
>This scenario is safe, due to the smp_mb__before_atomic() in wake_q_add()
>
>2) thread woken up but e.g. a timeout, see ->state=STATE_READY,
>returns to user space, calls sys_exit.
>
>This must not happen before get_task_struct acquired a reference.
>
>And this appears to be unsafe: get_task_struct() is refcount_inc(),
>which is refcount_inc_checked(), which is according to lib/refcount.c
>fully unordered.
>
>Thus: ->state=STATE_READY can execute before the refcount increase.
>
>Thus: ->state=STATE_READY needs a smp_store_release(), correct?
What if we did the reference count explicitly, and then just use
wake_q_add_safe()? That would avoid the extra barrier, __pipelined_op()
would become:
list_del();
get_task_struct();
wake_q_add_safe();
WRITE_ONCE(->state, STATE_READY);
Thanks,
Davidlohr