Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1253564 > unrolled thread
| Started by | Kosuke Tatsukawa <tatsu@ab.jp.nec.com> |
|---|---|
| First post | 2015-10-22 10:10 +0200 |
| Last post | 2015-10-23 14:50 +0200 |
| Articles | 4 — 2 participants |
Back to article view | Back to linux.kernel
[PATCH v2] wait: add comment before waitqueue_active noting memory barrier is required Kosuke Tatsukawa <tatsu@ab.jp.nec.com> - 2015-10-22 10:10 +0200
Re: [PATCH v2] wait: add comment before waitqueue_active noting memory barrier is required Peter Zijlstra <peterz@infradead.org> - 2015-10-22 15:00 +0200
Re: [PATCH v2] wait: add comment before waitqueue_active noting memory barrier is required Kosuke Tatsukawa <tatsu@ab.jp.nec.com> - 2015-10-23 01:30 +0200
Re: [PATCH v2] wait: add comment before waitqueue_active noting memory barrier is required Peter Zijlstra <peterz@infradead.org> - 2015-10-23 14:50 +0200
| From | Kosuke Tatsukawa <tatsu@ab.jp.nec.com> |
|---|---|
| Date | 2015-10-22 10:10 +0200 |
| Subject | [PATCH v2] wait: add comment before waitqueue_active noting memory barrier is required |
| Message-ID | <qmj6F-4MD-11@gated-at.bofh.it> |
This patch adds a comment before waitqueue_active noting that memory
barriers are required.
In the following code, the wake_up thread might fail to wake up the
waiting thread and leave it sleeping due to lack of memory barriers.
wake_up thread waiting thread
------------------------------------------------------------------------
CONDITION = 1; add_wait_queue(wq, &wait);
if (waitqueue_active(wq)) for (;;) {
wake_up(wq); if (CONDITION)
break;
wait_woken(&wait, ...);
}
------------------------------------------------------------------------
There are two problems that can occur.
First, on the wake_up thread side, the CPU can reorder waitqueue_active
to happen before the store.
wake_up thread waiting thread
(reordered)
------------------------------------------------------------------------
if (waitqueue_active(wq))
add_wait_queue(wq, &wait);
for (;;) {
if (CONDITION)
break;
CONDITION = 1;
wait_woken(&wait, ...);
}
------------------------------------------------------------------------
Second, on the waiting thread side, the CPU can reorder the load of
CONDITION to occur during add_wait_queue active, before the entry is
added to the wait queue.
wake_up thread waiting thread
(reordered)
------------------------------------------------------------------------
spin_lock_irqsave(...) <add_wait_queue>
if (CONDITION)
CONDITION = 1;
if (waitqueue_active(wq))
__add_wait_queue(...) <add_wait_queue>
spin_unlock_irqrestore(...) <add_wait_queue>
wait_woken(&wait, ...);
------------------------------------------------------------------------
Both problems can be fixed by removing the waitqueue_active() call at
the cost of calling spin_lock and spin_unlock even when the queue is
empty.
However, if that is too expensive, the reordering could be prevented by
adding memory barriers in the following places.
wake_up thread waiting thread
------------------------------------------------------------------------
CONDITION = 1; add_wait_queue(wq, &wait);
smp_mb(); smp_mb();
if (waitqueue_active(wq)) for (;;) {
wake_up(wq); if (CONDITION)
break;
wait_woken(&wait, ...);
}
------------------------------------------------------------------------
If the waiting thread uses prepare_to_wait() or wait_event*() instead of
directly calling add_wait_queue(), set_current_state() called within
those functions contains the necessary memory barrier. The memory
barrier in the wake_up thread is still needed.
There were several places in the linux kernel source code which lacked
the memory barrier. Hopefully, the comment will make people using
waitqueue_active a little more cautious.
Signed-off-by: Kosuke Tatsukawa <tatsu@ab.jp.nec.com>
---
include/linux/wait.h | 13 +++++++++++++
1 files changed, 13 insertions(+), 0 deletions(-)
diff --git a/include/linux/wait.h b/include/linux/wait.h
index 1e1bf9f..4a4c6fc 100644
--- a/include/linux/wait.h
+++ b/include/linux/wait.h
@@ -102,6 +102,19 @@ init_waitqueue_func_entry(wait_queue_t *q, wait_queue_func_t func)
q->func = func;
}
+/*
+ * Note: When adding waitqueue_active before calling wake_up for
+ * optimization, some sort of memory barrier is required on SMP so
+ * that the waiting thread does not miss the wake up.
+ *
+ * A memory barrier is required before waitqueue_active to prevent
+ * waitqueue_active from being reordered by the CPU before any writes
+ * done prior to it.
+ *
+ * The waiting side also needs a memory barrier which pairs with the
+ * wake_up side. If prepare_to_wait() or wait_event*() is used, they
+ * contain the memory barrier in set_current_state().
+ */
static inline int waitqueue_active(wait_queue_head_t *q)
{
return !list_empty(&q->task_list);
--
1.7.1
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[toc] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2015-10-22 15:00 +0200 |
| Subject | Re: [PATCH v2] wait: add comment before waitqueue_active noting memory barrier is required |
| Message-ID | <qmnDj-2Sv-7@gated-at.bofh.it> |
| In reply to | #1253564 |
On Thu, Oct 22, 2015 at 08:01:37AM +0000, Kosuke Tatsukawa wrote:
Its somewhat unfortunate you chose the whole wait_woken() thing, its
'rare'.
> Second, on the waiting thread side, the CPU can reorder the load of
> CONDITION to occur during add_wait_queue active, before the entry is
> added to the wait queue.
> wake_up thread waiting thread
> (reordered)
> ------------------------------------------------------------------------
> spin_lock_irqsave(...) <add_wait_queue>
> if (CONDITION)
> CONDITION = 1;
> if (waitqueue_active(wq))
wake_up();
> __add_wait_queue(...) <add_wait_queue>
> spin_unlock_irqrestore(...) <add_wait_queue>
> wait_woken(&wait, ...);
> ------------------------------------------------------------------------
This isn't actually a problem IIRC, because wait_woken() will test
WQ_FLAG_WOKEN and not actually sleep.
> However, if that is too expensive, the reordering could be prevented by
> adding memory barriers in the following places.
> wake_up thread waiting thread
> ------------------------------------------------------------------------
> CONDITION = 1; add_wait_queue(wq, &wait);
> smp_mb(); smp_mb();
> if (waitqueue_active(wq)) for (;;) {
> wake_up(wq); if (CONDITION)
> break;
> wait_woken(&wait, ...);
> }
So for wait_woken, WQ_FLAG_WOKEN should 'fix' that, and for pretty much
anything else you must have a set_current_state() before testing
CONDITION and you're good (as you state elsewhere).
> +++ b/include/linux/wait.h
> @@ -102,6 +102,19 @@ init_waitqueue_func_entry(wait_queue_t *q, wait_queue_func_t func)
> q->func = func;
> }
>
> +/*
> + * Note: When adding waitqueue_active before calling wake_up for
> + * optimization, some sort of memory barrier is required on SMP so
> + * that the waiting thread does not miss the wake up.
> + *
> + * A memory barrier is required before waitqueue_active to prevent
> + * waitqueue_active from being reordered by the CPU before any writes
> + * done prior to it.
> + *
> + * The waiting side also needs a memory barrier which pairs with the
> + * wake_up side. If prepare_to_wait() or wait_event*() is used, they
> + * contain the memory barrier in set_current_state().
> + */
> static inline int waitqueue_active(wait_queue_head_t *q)
> {
> return !list_empty(&q->task_list);
How about something like:
/**
* waitqueue_active -- locklessly test for waiters on the queue
* @q: the waitqueue to test for waiters
*
* returns true if the wait list is not empty
*
* NOTE: this function is lockless and requires care, incorrect usage
* _will_ lead to sporadic and non-obvious failure.
*
* Use either while holding wait_queue_head_t::lock or when used for
* wakeups with an extra smp_mb() like:
*
* CPU0 - waker CPU1 - waiter
*
* for (;;) {
* @cond = true; prepare_to_wait(&wq, &wait, state);
* smp_mb(); /* smp_mb() from set_current_state() */
* if (waitqueue_active(wq)) if (@cond)
* wake_up(wq); break;
* schedule();
* }
*
* Because without the explicit smp_mb() its possible for the
* waitqueue_active() load to get hoisted over the @cond store such that
* we'll observe an empty wait list while the waiter might not observe
* @cond.
*
* Also note that this 'optimization' trades a spin_lock() for an
* smp_mb(), which (when the lock is uncontended) are of roughly equal
* cost.
*/
Does that work for you?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | Kosuke Tatsukawa <tatsu@ab.jp.nec.com> |
|---|---|
| Date | 2015-10-23 01:30 +0200 |
| Subject | Re: [PATCH v2] wait: add comment before waitqueue_active noting memory barrier is required |
| Message-ID | <qmxt0-x2-15@gated-at.bofh.it> |
| In reply to | #1253779 |
Peter Zijlstra wrote:
> On Thu, Oct 22, 2015 at 08:01:37AM +0000, Kosuke Tatsukawa wrote:
>
> Its somewhat unfortunate you chose the whole wait_woken() thing, its
> 'rare'.
Yes. I first noticed this lack of memory barrier before
waitqueue_active() issue in drivers/tty/n_tty.c which was using
wait_woken(). However, other places were mostly using prepare_to_wait()
or wait_event*(), so wait_woken() is 'rare'.
>> Second, on the waiting thread side, the CPU can reorder the load of
>> CONDITION to occur during add_wait_queue active, before the entry is
>> added to the wait queue.
>> wake_up thread waiting thread
>> (reordered)
>> ------------------------------------------------------------------------
>> spin_lock_irqsave(...) <add_wait_queue>
>> if (CONDITION)
>> CONDITION = 1;
>> if (waitqueue_active(wq))
> wake_up();
>> __add_wait_queue(...) <add_wait_queue>
>> spin_unlock_irqrestore(...) <add_wait_queue>
>> wait_woken(&wait, ...);
>> ------------------------------------------------------------------------
>
> This isn't actually a problem IIRC, because wait_woken() will test
> WQ_FLAG_WOKEN and not actually sleep.
In the above figure, waitqueue_active(wq) will return 0 (queue is
inactive) and skip the whole wake_up() call, because __add_wait_queue()
hasn't been called yet. This actually does occur using a reproducer.
>> However, if that is too expensive, the reordering could be prevented by
>> adding memory barriers in the following places.
>> wake_up thread waiting thread
>> ------------------------------------------------------------------------
>> CONDITION = 1; add_wait_queue(wq, &wait);
>> smp_mb(); smp_mb();
>> if (waitqueue_active(wq)) for (;;) {
>> wake_up(wq); if (CONDITION)
>> break;
>> wait_woken(&wait, ...);
>> }
>
> So for wait_woken, WQ_FLAG_WOKEN should 'fix' that, and for pretty much
> anything else you must have a set_current_state() before testing
> CONDITION and you're good (as you state elsewhere).
wait_woken() calls set_current_state(), but that is after the CONDITION
test.
>> +++ b/include/linux/wait.h
>> @@ -102,6 +102,19 @@ init_waitqueue_func_entry(wait_queue_t *q, wait_queue_func_t func)
>> q->func = func;
>> }
>>
>> +/*
>> + * Note: When adding waitqueue_active before calling wake_up for
>> + * optimization, some sort of memory barrier is required on SMP so
>> + * that the waiting thread does not miss the wake up.
>> + *
>> + * A memory barrier is required before waitqueue_active to prevent
>> + * waitqueue_active from being reordered by the CPU before any writes
>> + * done prior to it.
>> + *
>> + * The waiting side also needs a memory barrier which pairs with the
>> + * wake_up side. If prepare_to_wait() or wait_event*() is used, they
>> + * contain the memory barrier in set_current_state().
>> + */
>> static inline int waitqueue_active(wait_queue_head_t *q)
>> {
>> return !list_empty(&q->task_list);
>
> How about something like:
>
> /**
> * waitqueue_active -- locklessly test for waiters on the queue
> * @q: the waitqueue to test for waiters
> *
> * returns true if the wait list is not empty
> *
> * NOTE: this function is lockless and requires care, incorrect usage
> * _will_ lead to sporadic and non-obvious failure.
> *
> * Use either while holding wait_queue_head_t::lock or when used for
> * wakeups with an extra smp_mb() like:
> *
> * CPU0 - waker CPU1 - waiter
> *
> * for (;;) {
> * @cond = true; prepare_to_wait(&wq, &wait, state);
> * smp_mb(); /* smp_mb() from set_current_state() */
> * if (waitqueue_active(wq)) if (@cond)
> * wake_up(wq); break;
> * schedule();
> * }
> *
> * Because without the explicit smp_mb() its possible for the
> * waitqueue_active() load to get hoisted over the @cond store such that
> * we'll observe an empty wait list while the waiter might not observe
> * @cond.
> *
> * Also note that this 'optimization' trades a spin_lock() for an
> * smp_mb(), which (when the lock is uncontended) are of roughly equal
> * cost.
> */
>
> Does that work for you?
Yes. Considering that the use of wait_woken is pretty rare, I think the
explanation is more focused and easier to understand this way.
Best regards.
---
Kosuke TATSUKAWA | 3rd IT Platform Department
| IT Platform Division, NEC Corporation
| tatsu@ab.jp.nec.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2015-10-23 14:50 +0200 |
| Subject | Re: [PATCH v2] wait: add comment before waitqueue_active noting memory barrier is required |
| Message-ID | <qmJXd-1GX-31@gated-at.bofh.it> |
| In reply to | #1254229 |
On Thu, Oct 22, 2015 at 11:18:33PM +0000, Kosuke Tatsukawa wrote:
> Peter Zijlstra wrote:
> > On Thu, Oct 22, 2015 at 08:01:37AM +0000, Kosuke Tatsukawa wrote:
> >
> > Its somewhat unfortunate you chose the whole wait_woken() thing, its
> > 'rare'.
>
> Yes. I first noticed this lack of memory barrier before
> waitqueue_active() issue in drivers/tty/n_tty.c which was using
> wait_woken(). However, other places were mostly using prepare_to_wait()
> or wait_event*(), so wait_woken() is 'rare'.
Which I no doubt introduced there (the wait_woken thing), and it would
have been nice if I'd been Cc to that discussion.
In any case, I found the patch in next and dropping the
waitqueue_active() think is in deed the sane solution. It will serialize
everything on the queue lock.
> >> Second, on the waiting thread side, the CPU can reorder the load of
> >> CONDITION to occur during add_wait_queue active, before the entry is
> >> added to the wait queue.
> >> wake_up thread waiting thread
> >> (reordered)
> >> ------------------------------------------------------------------------
> >> spin_lock_irqsave(...) <add_wait_queue>
> >> if (CONDITION)
> >> CONDITION = 1;
> >> if (waitqueue_active(wq))
> > wake_up();
> >> __add_wait_queue(...) <add_wait_queue>
> >> spin_unlock_irqrestore(...) <add_wait_queue>
> >> wait_woken(&wait, ...);
> >> ------------------------------------------------------------------------
> >
> > This isn't actually a problem IIRC, because wait_woken() will test
> > WQ_FLAG_WOKEN and not actually sleep.
>
> In the above figure, waitqueue_active(wq) will return 0 (queue is
> inactive) and skip the whole wake_up() call, because __add_wait_queue()
> hasn't been called yet. This actually does occur using a reproducer.
Duh, indeed.
> > Does that work for you?
>
> Yes. Considering that the use of wait_woken is pretty rare, I think the
> explanation is more focused and easier to understand this way.
OK, thanks, I'll queue the below.
---
Subject: sched, wait: Document waitqueue_active
From: Peter Zijlstra <peterz@infradead.org>
Date: Fri Oct 23 14:32:34 CEST 2015
Kosuku reports that there were a fair number of buggy
waitqueue_active() users and this function deserves a big comment in
order to avoid growing more.
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Reported-by: Kosuke Tatsukawa <tatsu@ab.jp.nec.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
include/linux/wait.h | 30 ++++++++++++++++++++++++++++++
1 file changed, 30 insertions(+)
--- a/include/linux/wait.h
+++ b/include/linux/wait.h
@@ -102,6 +102,36 @@ init_waitqueue_func_entry(wait_queue_t *
q->func = func;
}
+/**
+ * waitqueue_active -- locklessly test for waiters on the queue
+ * @q: the waitqueue to test for waiters
+ *
+ * returns true if the wait list is not empty
+ *
+ * NOTE: this function is lockless and requires care, incorrect usage _will_
+ * lead to sporadic and non-obvious failure.
+ *
+ * Use either while holding wait_queue_head_t::lock or when used for wakeups
+ * with an extra smp_mb() like:
+ *
+ * CPU0 - waker CPU1 - waiter
+ *
+ * for (;;) {
+ * @cond = true; prepare_to_wait(&wq, &wait, state);
+ * smp_mb(); // smp_mb() from set_current_state()
+ * if (waitqueue_active(wq)) if (@cond)
+ * wake_up(wq); break;
+ * schedule();
+ * }
+ * finish_wait(&wq, &wait);
+ *
+ * Because without the explicit smp_mb() it's possible for the
+ * waitqueue_active() load to get hoisted over the @cond store such that we'll
+ * observe an empty wait list while the waiter might not observe @cond.
+ *
+ * Also note that this 'optimization' trades a spin_lock() for an smp_mb(),
+ * which (when the lock is uncontended) are of roughly equal cost.
+ */
static inline int waitqueue_active(wait_queue_head_t *q)
{
return !list_empty(&q->task_list);
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[toc] | [prev] | [standalone]
Back to top | Article view | linux.kernel
csiph-web