From dce89628fd85a875a8dc511d861057f218f3c1c8 Mon Sep 17 00:00:00 2001
From: =?utf8?q?J=C3=A9r=C3=A9mie=20Galarneau?=
 <jeremie.galarneau@efficios.com>
Date: Wed, 10 May 2017 15:36:23 -0400
Subject: [PATCH] Fix: futex can be free'd while used by waker thread
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

The futex_nto1 utils assume that the futex it operates on
has a program-long lifetime (or that is is protected by a
third-party).

The notification command system uses a futex allocated on the
waiter's stack. However, the waiter could never enter the
futex() syscall (due to of the opportunist check before the futex
call). In this case, the waiter's stack-allocated futex becomes
invalid, but will be used by the waker to perform the FUTEX_WAKE
operation.

Signed-off-by: Jérémie Galarneau <jeremie.galarneau@efficios.com>
---
 src/common/futex.c | 79 +++++++++++++++++++++++++++++++---------------
 1 file changed, 54 insertions(+), 25 deletions(-)

diff --git a/src/common/futex.c b/src/common/futex.c
index 384e957a2..f1b33ea34 100644
--- a/src/common/futex.c
+++ b/src/common/futex.c
@@ -30,18 +30,22 @@
  * This futex wait/wake scheme only works for N wakers / 1 waiters. Hence the
  * "nto1" added to all function signature.
  *
- * Please see wait_gp()/update_counter_and_wait() calls in urcu.c in the urcu
- * git tree for a detail example of this scheme being used. futex_async() is
- * the urcu wrapper over the futex() sycall.
- *
- * There is also a formal verification available in the git tree.
- *
- *   branch: formal-model
- *   commit id: 2a8044f3493046fcc8c67016902dc7beec6f026a
- *
- * Ref: git://git.lttng.org/userspace-rcu.git
+ * The code is adapted from the adaptative busy wait/wake_up scheme used in
+ * liburcu.
  */
 
+/* Number of busy-loop attempts before waiting on futex. */
+#define FUTEX_WAIT_ATTEMPTS 1000
+
+enum futex_wait_state {
+	/* FUTEX_WAIT_WAITING is compared directly (futex() compares it). */
+	FUTEX_WAIT_WAITING =	0,
+	/* non-zero are used as masks. */
+	FUTEX_WAIT_WAKEUP =	(1 << 0),
+	FUTEX_WAIT_RUNNING =	(1 << 1),
+	FUTEX_WAIT_TEARDOWN =	(1 << 2),
+};
+
 /*
  * Update futex according to active or not. This scheme is used to wake every
  * libust waiting on the shared memory map futex hence the INT_MAX used in the
@@ -71,7 +75,7 @@ void futex_wait_update(int32_t *futex, int active)
 LTTNG_HIDDEN
 void futex_nto1_prepare(int32_t *futex)
 {
-	uatomic_set(futex, -1);
+	uatomic_set(futex, FUTEX_WAIT_WAITING);
 	cmm_smp_mb();
 
 	DBG("Futex n to 1 prepare done");
@@ -83,25 +87,47 @@ void futex_nto1_prepare(int32_t *futex)
 LTTNG_HIDDEN
 void futex_nto1_wait(int32_t *futex)
 {
-	cmm_smp_mb();
+	unsigned int i;
 
-	if (uatomic_read(futex) != -1)
-		goto end;
-	while (futex_async(futex, FUTEX_WAIT, -1, NULL, NULL, 0)) {
+	/* Load and test condition before read state */
+	cmm_smp_rmb();
+	for (i = 0; i < FUTEX_WAIT_ATTEMPTS; i++) {
+		if (uatomic_read(futex) != FUTEX_WAIT_WAITING)
+			goto skip_futex_wait;
+		caa_cpu_relax();
+	}
+	while (futex_noasync(futex, FUTEX_WAIT, FUTEX_WAIT_WAITING,
+			NULL, NULL, 0)) {
 		switch (errno) {
 		case EWOULDBLOCK:
 			/* Value already changed. */
-			goto end;
+			goto skip_futex_wait;
 		case EINTR:
 			/* Retry if interrupted by signal. */
 			break;	/* Get out of switch. */
 		default:
 			/* Unexpected error. */
-			PERROR("futex_async");
+			PERROR("futex");
 			abort();
 		}
 	}
-end:
+skip_futex_wait:
+
+	/* Tell waker thread than we are running. */
+	uatomic_or(futex, FUTEX_WAIT_RUNNING);
+
+	/*
+	 * Wait until waker thread lets us know it's ok to tear down
+	 * memory allocated for the futex.
+	 */
+	for (i = 0; i < FUTEX_WAIT_ATTEMPTS; i++) {
+		if (uatomic_read(futex) & FUTEX_WAIT_TEARDOWN)
+			break;
+		caa_cpu_relax();
+	}
+	while (!(uatomic_read(futex) & FUTEX_WAIT_TEARDOWN))
+		poll(NULL, 0, 10);
+	assert(uatomic_read(futex) & FUTEX_WAIT_TEARDOWN);
 	DBG("Futex n to 1 wait done");
 }
 
@@ -111,13 +137,16 @@ end:
 LTTNG_HIDDEN
 void futex_nto1_wake(int32_t *futex)
 {
-	if (caa_unlikely(uatomic_read(futex) != -1))
-		goto end;
-	uatomic_set(futex, 0);
-	if (futex_async(futex, FUTEX_WAKE, 1, NULL, NULL, 0) < 0) {
-		PERROR("futex_async");
-		abort();
+	cmm_smp_mb();
+	uatomic_set(futex, FUTEX_WAIT_WAKEUP);
+	if (!(uatomic_read(futex) & FUTEX_WAIT_RUNNING)) {
+		if (futex_noasync(futex, FUTEX_WAKE, 1,
+				NULL, NULL, 0) < 0) {
+			PERROR("futex_noasync");
+			abort();
+		}
 	}
-end:
+	/* Allow teardown of futex. */
+	uatomic_or(futex, FUTEX_WAIT_TEARDOWN);
 	DBG("Futex n to 1 wake done");
 }
-- 
2.34.1