From: Davidlohr Bueso <davidlohr@hp.com>
To: linux-kernel@vger.kernel.org
Cc: mingo@kernel.org, dvhart@linux.intel.com, peterz@infradead.org,
tglx@linutronix.de, paulmck@linux.vnet.ibm.com, efault@gmx.de,
jeffm@suse.com, torvalds@linux-foundation.org, jason.low2@hp.com,
Waiman.Long@hp.com, tom.vaden@hp.com, scott.norton@hp.com,
aswin@hp.com, davidlohr@hp.com,
Randy Dunlap <rdunlap@infradead.org>
Subject: [PATCH v5 3/4] futex: Document ordering guarantees
Date: Thu, 2 Jan 2014 07:05:19 -0800 [thread overview]
Message-ID: <1388675120-8017-4-git-send-email-davidlohr@hp.com> (raw)
In-Reply-To: <1388675120-8017-1-git-send-email-davidlohr@hp.com>
From: Thomas Gleixner <tglx@linutronix.de>
That's essential, if you want to hack on futexes.
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Darren Hart <dvhart@linux.intel.com>
Acked-by: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.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>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Davidlohr Bueso <davidlohr@hp.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
next prev parent reply other threads:[~2014-01-02 15:06 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-01-02 15:05 [PATCH v5 0/4] futex: Wakeup optimizations Davidlohr Bueso
2014-01-02 15:05 ` [PATCH v5 1/4] futex: Misc cleanups Davidlohr Bueso
2014-01-11 6:43 ` Paul E. McKenney
2014-01-02 15:05 ` [PATCH v5 2/4] futex: Larger hash table Davidlohr Bueso
2014-01-11 7:37 ` Paul E. McKenney
2014-01-02 15:05 ` Davidlohr Bueso [this message]
2014-01-06 18:58 ` [PATCH v5 3/4] futex: Document ordering guarantees Darren Hart
2014-01-11 7:40 ` Paul E. McKenney
2014-01-02 15:05 ` [PATCH v5 4/4] futex: Avoid taking hb lock if nothing to wakeup Davidlohr Bueso
2014-01-02 19:23 ` Linus Torvalds
2014-01-02 20:59 ` Davidlohr Bueso
2014-01-06 20:56 ` Darren Hart
2014-01-06 20:52 ` Darren Hart
2014-01-07 3:29 ` Davidlohr Bueso
2014-01-07 17:40 ` Darren Hart
2014-01-11 9:49 ` Paul E. McKenney
2014-01-11 9:52 ` Paul E. McKenney
2014-01-11 18:21 ` Davidlohr Bueso
2014-01-06 0:59 ` [PATCH v5 0/4] futex: Wakeup optimizations Davidlohr Bueso
2014-01-06 1:38 ` [PATCH 5/4] futex: silence uninitialized warnings Davidlohr Bueso
2014-01-06 18:48 ` Darren Hart
2014-01-07 2:55 ` Linus Torvalds
2014-01-07 3:02 ` Davidlohr Bueso
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1388675120-8017-4-git-send-email-davidlohr@hp.com \
--to=davidlohr@hp.com \
--cc=Waiman.Long@hp.com \
--cc=aswin@hp.com \
--cc=dvhart@linux.intel.com \
--cc=efault@gmx.de \
--cc=jason.low2@hp.com \
--cc=jeffm@suse.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=paulmck@linux.vnet.ibm.com \
--cc=peterz@infradead.org \
--cc=rdunlap@infradead.org \
--cc=scott.norton@hp.com \
--cc=tglx@linutronix.de \
--cc=tom.vaden@hp.com \
--cc=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).