Skip to content

Commit 99b60ce

Browse files
KAGA-KOKOIngo Molnar
authored andcommitted
futexes: Document multiprocessor ordering guarantees
That's essential, if you want to hack on futexes. Reviewed-by: Darren Hart <dvhart@linux.intel.com> Reviewed-by: Peter Zijlstra <peterz@infradead.org> Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Davidlohr Bueso <davidlohr@hp.com> Cc: Mike Galbraith <efault@gmx.de> Cc: Jeff Mahoney <jeffm@suse.com> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Randy Dunlap <rdunlap@infradead.org> Cc: Scott Norton <scott.norton@hp.com> Cc: Tom Vaden <tom.vaden@hp.com> Cc: Aswin Chandramouleeswaran <aswin@hp.com> Cc: Waiman Long <Waiman.Long@hp.com> Cc: Jason Low <jason.low2@hp.com> Cc: Andrew Morton <akpm@linux-foundation.org> Link: http://lkml.kernel.org/r/1389569486-25487-4-git-send-email-davidlohr@hp.com Signed-off-by: Ingo Molnar <mingo@kernel.org>
1 parent a52b89e commit 99b60ce

File tree

1 file changed

+57
-0
lines changed

1 file changed

+57
-0
lines changed

kernel/futex.c

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -69,6 +69,63 @@
6969

7070
#include "locking/rtmutex_common.h"
7171

72+
/*
73+
* Basic futex operation and ordering guarantees:
74+
*
75+
* The waiter reads the futex value in user space and calls
76+
* futex_wait(). This function computes the hash bucket and acquires
77+
* the hash bucket lock. After that it reads the futex user space value
78+
* again and verifies that the data has not changed. If it has not
79+
* changed it enqueues itself into the hash bucket, releases the hash
80+
* bucket lock and schedules.
81+
*
82+
* The waker side modifies the user space value of the futex and calls
83+
* futex_wake(). This functions computes the hash bucket and acquires
84+
* the hash bucket lock. Then it looks for waiters on that futex in the
85+
* hash bucket and wakes them.
86+
*
87+
* Note that the spin_lock serializes waiters and wakers, so that the
88+
* following scenario is avoided:
89+
*
90+
* CPU 0 CPU 1
91+
* val = *futex;
92+
* sys_futex(WAIT, futex, val);
93+
* futex_wait(futex, val);
94+
* uval = *futex;
95+
* *futex = newval;
96+
* sys_futex(WAKE, futex);
97+
* futex_wake(futex);
98+
* if (queue_empty())
99+
* return;
100+
* if (uval == val)
101+
* lock(hash_bucket(futex));
102+
* queue();
103+
* unlock(hash_bucket(futex));
104+
* schedule();
105+
*
106+
* This would cause the waiter on CPU 0 to wait forever because it
107+
* missed the transition of the user space value from val to newval
108+
* and the waker did not find the waiter in the hash bucket queue.
109+
* The spinlock serializes that:
110+
*
111+
* CPU 0 CPU 1
112+
* val = *futex;
113+
* sys_futex(WAIT, futex, val);
114+
* futex_wait(futex, val);
115+
* lock(hash_bucket(futex));
116+
* uval = *futex;
117+
* *futex = newval;
118+
* sys_futex(WAKE, futex);
119+
* futex_wake(futex);
120+
* lock(hash_bucket(futex));
121+
* if (uval == val)
122+
* queue();
123+
* unlock(hash_bucket(futex));
124+
* schedule(); if (!queue_empty())
125+
* wake_waiters(futex);
126+
* unlock(hash_bucket(futex));
127+
*/
128+
72129
int __read_mostly futex_cmpxchg_enabled;
73130

74131
/*

0 commit comments

Comments
 (0)