linux-kernel - Re: [PATCH v5 3/4] futex: Document ordering guarantees

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: Windows password security audit tool. GUI, reports in PDF.

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

Date:	Fri, 10 Jan 2014 23:40:46 -0800
From:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To:	Davidlohr Bueso <davidlohr@...com>
Cc:	linux-kernel@...r.kernel.org, mingo@...nel.org,
	dvhart@...ux.intel.com, peterz@...radead.org, tglx@...utronix.de,
	efault@....de, jeffm@...e.com, torvalds@...ux-foundation.org,
	jason.low2@...com, Waiman.Long@...com, tom.vaden@...com,
	scott.norton@...com, aswin@...com,
	Randy Dunlap <rdunlap@...radead.org>
Subject: Re: [PATCH v5 3/4] futex: Document ordering guarantees

On Thu, Jan 02, 2014 at 07:05:19AM -0800, Davidlohr Bueso wrote:
> From: Thomas Gleixner <tglx@...utronix.de>
> 
> That's essential, if you want to hack on futexes.
> 
> Cc: Ingo Molnar <mingo@...nel.org>
> Cc: Darren Hart <dvhart@...ux.intel.com>
> Acked-by: Peter Zijlstra <peterz@...radead.org>
> Cc: Thomas Gleixner <tglx@...utronix.de>
> Cc: Paul E. McKenney <paulmck@...ux.vnet.ibm.com>
> Cc: Mike Galbraith <efault@....de>
> Cc: Jeff Mahoney <jeffm@...e.com>
> Cc: Linus Torvalds <torvalds@...ux-foundation.org>
> Cc: Randy Dunlap <rdunlap@...radead.org>
> Cc: Scott Norton <scott.norton@...com>
> Cc: Tom Vaden <tom.vaden@...com>
> Cc: Aswin Chandramouleeswaran <aswin@...com>
> Cc: Waiman Long <Waiman.Long@...com>
> Cc: Jason Low <jason.low2@...com>
> Signed-off-by: Thomas Gleixner <tglx@...utronix.de>
> Signed-off-by: Davidlohr Bueso <davidlohr@...com>

Reviewed-by: Paul E. McKenney <paulmck@...ux.vnet.ibm.com>

> ---
>  kernel/futex.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 57 insertions(+)
> 
> diff --git a/kernel/futex.c b/kernel/futex.c
> index 577481d..fcc6850 100644
> --- a/kernel/futex.c
> +++ b/kernel/futex.c
> @@ -69,6 +69,63 @@
> 
>  #include "locking/rtmutex_common.h"
> 
> +/*
> + * Basic futex operation and ordering guarantees:
> + *
> + * The waiter reads the futex value in user space and calls
> + * futex_wait(). This function computes the hash bucket and acquires
> + * the hash bucket lock. After that it reads the futex user space value
> + * again and verifies that the data has not changed. If it has not
> + * changed it enqueues itself into the hash bucket, releases the hash
> + * bucket lock and schedules.
> + *
> + * The waker side modifies the user space value of the futex and calls
> + * futex_wake(). This functions computes the hash bucket and acquires
> + * the hash bucket lock. Then it looks for waiters on that futex in the
> + * hash bucket and wakes them.
> + *
> + * Note that the spin_lock serializes waiters and wakers, so that the
> + * following scenario is avoided:
> + *
> + * CPU 0                               CPU 1
> + * val = *futex;
> + * sys_futex(WAIT, futex, val);
> + *   futex_wait(futex, val);
> + *   uval = *futex;
> + *                                     *futex = newval;
> + *                                     sys_futex(WAKE, futex);
> + *                                       futex_wake(futex);
> + *                                       if (queue_empty())
> + *                                         return;
> + *   if (uval == val)
> + *      lock(hash_bucket(futex));
> + *      queue();
> + *     unlock(hash_bucket(futex));
> + *     schedule();
> + *
> + * This would cause the waiter on CPU 0 to wait forever because it
> + * missed the transition of the user space value from val to newval
> + * and the waker did not find the waiter in the hash bucket queue.
> + * The spinlock serializes that:
> + *
> + * CPU 0                               CPU 1
> + * val = *futex;
> + * sys_futex(WAIT, futex, val);
> + *   futex_wait(futex, val);
> + *   lock(hash_bucket(futex));
> + *   uval = *futex;
> + *                                     *futex = newval;
> + *                                     sys_futex(WAKE, futex);
> + *                                       futex_wake(futex);
> + *                                       lock(hash_bucket(futex));
> + *   if (uval == val)
> + *      queue();
> + *     unlock(hash_bucket(futex));
> + *     schedule();                       if (!queue_empty())
> + *                                         wake_waiters(futex);
> + *                                       unlock(hash_bucket(futex));
> + */
> +
>  int __read_mostly futex_cmpxchg_enabled;
> 
>  /*
> -- 
> 1.8.1.4
> 

--
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/