linux-kernel - Re: [PATCH v2] wait: add comment before waitqueue

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Thu, 22 Oct 2015 14:56:15 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Kosuke Tatsukawa <tatsu@...jp.nec.com>
Cc:	Ingo Molnar <mingo@...hat.com>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH v2] wait: add comment before waitqueue_active noting
 memory barrier is required

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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/