[RFC patch 2/5] futex: Document ordering guarantees

[Thomas Gleixner <tglx@linutronix.de>]

[-- Attachment #1: futex-document-serialization.patch --]
[-- Type: text/plain, Size: 2414 bytes --]

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

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 kernel/futex.c |   57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 57 insertions(+)

Index: linux-2.6/kernel/futex.c
===================================================================
--- linux-2.6.orig/kernel/futex.c
+++ linux-2.6/kernel/futex.c
@@ -68,6 +68,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(). It 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(). It 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;
 
 #define FUTEX_HASHBITS (CONFIG_BASE_SMALL ? 4 : 8)