linux-kernel - [tip:core/locking] futexes: Document multiprocessor 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]

Message-ID: <tip-99b60ce69734dfeda58c6184a326b9475ce1dba3@git.kernel.org>
Date:	Mon, 13 Jan 2014 07:52:49 -0800
From:	tip-bot for Thomas Gleixner <tipbot@...or.com>
To:	linux-tip-commits@...r.kernel.org
Cc:	mingo@...nel.org, torvalds@...ux-foundation.org, efault@....de,
	peterz@...radead.org, rdunlap@...radead.org, jason.low2@...com,
	Waiman.Long@...com, akpm@...ux-foundation.org, tglx@...utronix.de,
	scott.norton@...com, davidlohr@...com,
	linux-kernel@...r.kernel.org, hpa@...or.com,
	dvhart@...ux.intel.com, paulmck@...ux.vnet.ibm.com,
	tom.vaden@...com, jeffm@...e.com, aswin@...com
Subject: [tip:core/locking] futexes:
  Document multiprocessor ordering guarantees

Commit-ID:  99b60ce69734dfeda58c6184a326b9475ce1dba3
Gitweb:     http://git.kernel.org/tip/99b60ce69734dfeda58c6184a326b9475ce1dba3
Author:     Thomas Gleixner <tglx@...utronix.de>
AuthorDate: Sun, 12 Jan 2014 15:31:24 -0800
Committer:  Ingo Molnar <mingo@...nel.org>
CommitDate: Mon, 13 Jan 2014 11:45:19 +0100

futexes: Document multiprocessor ordering guarantees

That's essential, if you want to hack on futexes.

Reviewed-by: Darren Hart <dvhart@...ux.intel.com>
Reviewed-by: Peter Zijlstra <peterz@...radead.org>
Reviewed-by: Paul E. McKenney <paulmck@...ux.vnet.ibm.com>
Signed-off-by: Thomas Gleixner <tglx@...utronix.de>
Signed-off-by: Davidlohr Bueso <davidlohr@...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>
Cc: Andrew Morton <akpm@...ux-foundation.org>
Link: http://lkml.kernel.org/r/1389569486-25487-4-git-send-email-davidlohr@hp.com
Signed-off-by: Ingo Molnar <mingo@...nel.org>
---
 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;
 
 /*
--
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/