aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorThomas Gleixner <[email protected]>2014-01-12 15:31:24 -0800
committerIngo Molnar <[email protected]>2014-01-13 11:45:19 +0100
commit99b60ce69734dfeda58c6184a326b9475ce1dba3 (patch)
treef9e4c7f179859f3e20bdd5e7c501196f0a07eddf
parenta52b89ebb6d4499be38780db8d176c5d3a6fbc17 (diff)
futexes: Document multiprocessor ordering guarantees
That's essential, if you want to hack on futexes. Reviewed-by: Darren Hart <[email protected]> Reviewed-by: Peter Zijlstra <[email protected]> Reviewed-by: Paul E. McKenney <[email protected]> Signed-off-by: Thomas Gleixner <[email protected]> Signed-off-by: Davidlohr Bueso <[email protected]> Cc: Mike Galbraith <[email protected]> Cc: Jeff Mahoney <[email protected]> Cc: Linus Torvalds <[email protected]> Cc: Randy Dunlap <[email protected]> Cc: Scott Norton <[email protected]> Cc: Tom Vaden <[email protected]> Cc: Aswin Chandramouleeswaran <[email protected]> Cc: Waiman Long <[email protected]> Cc: Jason Low <[email protected]> Cc: Andrew Morton <[email protected]> Link: http://lkml.kernel.org/r/[email protected] Signed-off-by: Ingo Molnar <[email protected]>
-rw-r--r--kernel/futex.c57
1 files changed, 57 insertions, 0 deletions
diff --git a/kernel/futex.c b/kernel/futex.c
index 577481d5c59d..fcc6850483fb 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;
/*