Skip to contentSkip to conversation

futex_cmp_requeue01: fix test expectations

PATCH New Jan Stancek 2 participants 10 messages Nov 11, 2019 – Dec 6, 2019

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 futex_cmp_requeue01: fix test expectations

There are couple problems:

1. Keeping same uaddr1 value across requeue leads to a side-effect. If there is a signal or spurious wakeup, futex_wait() operation can be restarted (by kernel) with same input parameters. Which means that process requeued for uaddr2, goes back to queueing for uaddr1. Such use case is currently not valid as it is expected that uaddr1 value changes, so that any late waiter can notice it and goes back with -EWOULDBLOCK (-EAGAIN).

2. Test doesn't expect possibility of spurious wakeups.

3. Test is expecting to get exact values of woken/requeued processes. Man page wording like "at most" or "maximum of" does not guarantee exact numbers.

Change futex value before requeue, so child processes can observe spurious wakeups.

Change child process, such that it always sleeps, to guarantee that TST_PROCESS_STATE_WAIT() will always succeed finding sleeping process.

Change default timeout to 5 seconds. Spawning 1000 process on slower systems was getting close to 1 second. This doesn't affect runtime in PASS-ing case.

Change checks such that they reflect wording in man page, and don't test for absolute values (see comments in code). One exception is that we assume futex_wake(tc->num_waiters) will always wake up all remaining processes.

---
 .../kernel/syscalls/futex/futex_cmp_requeue01.c    | 82 +++++++++++++++++-----
 1 file changed, 64 insertions(+), 18 deletions(-)

@Cyril: I'm still testing this, but sending early to see if you'd be
OK with this approach.

testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +64 -18
index f5264c2ba26f..2bd228a11437 100644
@@ -20,6 +20,7 @@
 #include "futextest.h"
 
 static futex_t *futexes;
+static int *spurious, *test_done;
 
 static struct tcase {
 	int num_waiters;
@@ -37,14 +38,28 @@ static struct tcase {
 
 static void do_child(void)
 {
-	struct timespec usec = tst_ms_to_timespec(2000);
+	int max_sleep_ms = 5000, slept_for_ms = 0;
+	struct timespec usec = tst_ms_to_timespec(max_sleep_ms);
 	int pid = getpid();
+	int ret = 0;
+
+	if (futex_wait(&futexes[0], futexes[0], &usec, 0) == -1) {
+		if (errno == EAGAIN) {
+			/* spurious wakeup or signal */
+			tst_atomic_inc(spurious);
+		} else {
+			tst_res(TFAIL | TERRNO, "process %d wasn't woken up", pid);
+			ret = 1;
+		}
+	}
 
-	if (!futex_wait(&futexes[0], futexes[0], &usec, 0))
-		exit(0);
+	/* make sure TST_PROCESS_STATE_WAIT() can always succeed */
+	while (!tst_atomic_load(test_done) && (slept_for_ms < max_sleep_ms)) {
+		usleep(50000);
+		slept_for_ms += 50;
+	}
 
-	tst_res(TINFO | TERRNO, "process %d wasn't woken up", pid);
-	exit(1);
+	exit(ret);
 }
 
 static void verify_futex_cmp_requeue(unsigned int n)
@@ -55,6 +70,8 @@ static void verify_futex_cmp_requeue(unsigned int n)
 	int pid[tc->num_waiters];
 	int exp_ret = tc->set_wakes + tc->set_requeues;
 
+	tst_atomic_store(0, spurious);
+	tst_atomic_store(0, test_done);
 	for (i = 0; i < tc->num_waiters; i++) {
 		pid[i] = SAFE_FORK();
 		if (!pid[i])
@@ -64,46 +81,69 @@ static void verify_futex_cmp_requeue(unsigned int n)
 	for (i = 0; i < tc->num_waiters; i++)
 		TST_PROCESS_STATE_WAIT(pid[i], 'S');
 
+	tst_res(TINFO, "Test %d: waiters: %d, wakes: %d, requeues: %d",
+		n, tc->num_waiters, tc->set_wakes, tc->set_requeues);
+
+	/*
+	 * change futex value, so any spurious wakeups or signals after
+	 * this point get bounced back to userspace.
+	 */
+	futexes[0]++;
+	futexes[1]++;
+
+	/*
+	 * Wakes up a maximum of tc->set_wakes waiters. tc->set_requeues
+	 * specifies an upper limit on the number of waiters that are requeued.
+	 * Returns the total number of waiters that were woken up or requeued.
+	 */
 	TEST(futex_cmp_requeue(&futexes[0], futexes[0], &futexes[1],
 	     tc->set_wakes, tc->set_requeues, 0));
-	if (TST_RET != exp_ret) {
-		tst_res(TFAIL, "futex_cmp_requeue() returned %ld, expected %d",
+
+	/* Fail if more than requested wakes + requeues were returned */
+	if (TST_RET > exp_ret) {
+		tst_res(TFAIL, "futex_cmp_requeue() returned %ld, expected <= %d",
 			TST_RET, exp_ret);
+	} else {
+		tst_res(TINFO, "futex_cmp_requeue() returned %ld", TST_RET);
 	}
 
 	num_requeues = futex_wake(&futexes[1], tc->num_waiters, 0);
 	num_waits = futex_wake(&futexes[0], tc->num_waiters, 0);
 
 	for (i = 0; i < tc->num_waiters; i++) {
+		tst_atomic_store(1, test_done);
 		SAFE_WAITPID(pid[i], &status, 0);
 		if (WIFEXITED(status) && !WEXITSTATUS(status))
 			num_total++;
 	}
 
+	tst_res(TINFO, "children woken, futex0: %d, futex1: %d, "
+		"spurious wakeups: %d",
+		num_waits, num_requeues, tst_atomic_load(spurious));
+
+	/* Fail if any waiter timed out */
 	if (num_total != tc->num_waiters) {
 		tst_res(TFAIL, "%d waiters were not woken up normally",
 			tc->num_waiters - num_total);
 		return;
 	}
 
-	if (num_requeues != tc->set_requeues) {
+	/* Fail if more than upper limit of tc->set_requeues were found at futex1 */
+	if (num_requeues > tc->set_requeues) {
 		tst_res(TFAIL,
-			"futex_cmp_requeue() requeues %d waiters, expected %d",
+			"requeued %d waiters, expected <= %d",
 			num_requeues, tc->set_requeues);
 		return;
 	}
 
-	if (tc->num_waiters - num_requeues - num_waits != tc->set_wakes) {
-		tst_res(TFAIL,
-			"futex_cmp_requeue() woke up %d waiters, expected %d",
-			tc->num_waiters - num_requeues - num_waits,
-			tc->set_wakes);
+	/* Fail if more than tc->set_wakes were woken up by requeue */
+	exp_ret = tc->num_waiters - TST_RET - tst_atomic_load(spurious);
+	if (num_waits < exp_ret) {
+		tst_res(TFAIL, "woken up %d on futex0, expected >= %d", num_waits, exp_ret);
 		return;
 	}
 
-	tst_res(TPASS,
-		"futex_cmp_requeue() woke up %d waiters and requeued %d waiters",
-		tc->set_wakes, tc->set_requeues);
+	tst_res(TPASS, "futex_cmp_requeue()");
 }
 
 static void setup(void)
@@ -112,13 +152,19 @@ static void setup(void)
 			    MAP_ANONYMOUS | MAP_SHARED, -1, 0);
 
 	futexes[0] = FUTEX_INITIALIZER;
-	futexes[1] = FUTEX_INITIALIZER + 1;
+	futexes[1] = FUTEX_INITIALIZER + 1000;
+
+	spurious = SAFE_MMAP(NULL, sizeof(int) * 2, PROT_READ | PROT_WRITE,
+			    MAP_ANONYMOUS | MAP_SHARED, -1, 0);
+	test_done = spurious + 1;
 }
 
 static void cleanup(void)
 {
 	if (futexes)
 		SAFE_MUNMAP((void *)futexes, sizeof(futex_t) * 2);
+	if (spurious)
+		SAFE_MUNMAP((void *)spurious, sizeof(int) * 2);
 }
 
 static struct tst_test test = {
Signature · 1 line
1.8.3.1
#1 lore raw

PATCH 1/1 futex_cmp_requeue01: fix test expectations

Hi!

Quoted 20 lines

1. Keeping same uaddr1 value across requeue leads to a side-effect. If there is a signal or spurious wakeup, futex_wait() operation can be restarted (by kernel) with same input parameters. Which means that process requeued for uaddr2, goes back to queueing for uaddr1. Such use case is currently not valid as it is expected that uaddr1 value changes, so that any late waiter can notice it and goes back with -EWOULDBLOCK (-EAGAIN).

2. Test doesn't expect possibility of spurious wakeups.

3. Test is expecting to get exact values of woken/requeued processes. Man page wording like "at most" or "maximum of" does not guarantee exact numbers.

Change futex value before requeue, so child processes can observe spurious wakeups.

Change child process, such that it always sleeps, to guarantee that TST_PROCESS_STATE_WAIT() will always succeed finding sleeping process.

Quoted 8 lines

Change default timeout to 5 seconds. Spawning 1000 process on slower systems was getting close to 1 second. This doesn't affect runtime in PASS-ing case.

Change checks such that they reflect wording in man page, and don't test for absolute values (see comments in code). One exception is that we assume futex_wake(tc->num_waiters) will always wake up all remaining processes.

Sounds good, a few comments below.

Quoted 13 lines
---
 .../kernel/syscalls/futex/futex_cmp_requeue01.c    | 82 +++++++++++++++++-----
 1 file changed, 64 insertions(+), 18 deletions(-)

@Cyril: I'm still testing this, but sending early to see if you'd be
OK with this approach.

testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +0 -0
index f5264c2ba26f..2bd228a11437 100644

testcases/kernel/syscalls/futex/futex_cmp_requeue01.c line 23

Quoted 4 lines
testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +1 -0
@@ -20,6 +20,7 @@
 #include "futextest.h"
 
 static futex_t *futexes;
+static int *spurious, *test_done;

Shouldn't these be volatile? Or does the tst_atomic_load() guarantee that compiler knows that it could be changed from a different process?

testcases/kernel/syscalls/futex/futex_cmp_requeue01.c static struct tcase { · line 41

Quoted 8 lines
testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +1 -1
 static struct tcase {
 	int num_waiters;
@@ -37,14 +38,28 @@ static struct tcase {
 
 static void do_child(void)
 {
-	struct timespec usec = tst_ms_to_timespec(2000);
+	int max_sleep_ms = 5000, slept_for_ms = 0;

We do have a tst_multiply_timeout() in the test library now, shouldn't we use it for the max_sleep_ms here as well?

Also if we do that it would make sense to keep the timeout in global and initialize it in the parent, that would save us some runtime.

Quoted 64 lines
testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +39 -6
+	struct timespec usec = tst_ms_to_timespec(max_sleep_ms);
 	int pid = getpid();
+	int ret = 0;
+
+	if (futex_wait(&futexes[0], futexes[0], &usec, 0) == -1) {
+		if (errno == EAGAIN) {
+			/* spurious wakeup or signal */
+			tst_atomic_inc(spurious);
+		} else {
+			tst_res(TFAIL | TERRNO, "process %d wasn't woken up", pid);
+			ret = 1;
+		}
+	}
 
-	if (!futex_wait(&futexes[0], futexes[0], &usec, 0))
-		exit(0);
+	/* make sure TST_PROCESS_STATE_WAIT() can always succeed */
+	while (!tst_atomic_load(test_done) && (slept_for_ms < max_sleep_ms)) {
+		usleep(50000);
+		slept_for_ms += 50;
+	}
 
-	tst_res(TINFO | TERRNO, "process %d wasn't woken up", pid);
-	exit(1);
+	exit(ret);
 }
 
 static void verify_futex_cmp_requeue(unsigned int n)
@@ -55,6 +70,8 @@ static void verify_futex_cmp_requeue(unsigned int n)
 	int pid[tc->num_waiters];
 	int exp_ret = tc->set_wakes + tc->set_requeues;
 
+	tst_atomic_store(0, spurious);
+	tst_atomic_store(0, test_done);
 	for (i = 0; i < tc->num_waiters; i++) {
 		pid[i] = SAFE_FORK();
 		if (!pid[i])
@@ -64,46 +81,69 @@ static void verify_futex_cmp_requeue(unsigned int n)
 	for (i = 0; i < tc->num_waiters; i++)
 		TST_PROCESS_STATE_WAIT(pid[i], 'S');
 
+	tst_res(TINFO, "Test %d: waiters: %d, wakes: %d, requeues: %d",
+		n, tc->num_waiters, tc->set_wakes, tc->set_requeues);
+
+	/*
+	 * change futex value, so any spurious wakeups or signals after
+	 * this point get bounced back to userspace.
+	 */
+	futexes[0]++;
+	futexes[1]++;
+
+	/*
+	 * Wakes up a maximum of tc->set_wakes waiters. tc->set_requeues
+	 * specifies an upper limit on the number of waiters that are requeued.
+	 * Returns the total number of waiters that were woken up or requeued.
+	 */
 	TEST(futex_cmp_requeue(&futexes[0], futexes[0], &futexes[1],
 	     tc->set_wakes, tc->set_requeues, 0));
-	if (TST_RET != exp_ret) {
-		tst_res(TFAIL, "futex_cmp_requeue() returned %ld, expected %d",
+
+	/* Fail if more than requested wakes + requeues were returned */
+	if (TST_RET > exp_ret) {
+		tst_res(TFAIL, "futex_cmp_requeue() returned %ld, expected <= %d",

testcases/kernel/syscalls/futex/futex_cmp_requeue01.c static void verify_futex_cmp_requeue(unsigned int n) · line 114

Quoted 10 lines
testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +3 -0
 			TST_RET, exp_ret);
+	} else {
+		tst_res(TINFO, "futex_cmp_requeue() returned %ld", TST_RET);
 	}
 
 	num_requeues = futex_wake(&futexes[1], tc->num_waiters, 0);
 	num_waits = futex_wake(&futexes[0], tc->num_waiters, 0);
 
 	for (i = 0; i < tc->num_waiters; i++) {
+		tst_atomic_store(1, test_done);

What's the point of storing the value in the loop, shouldn't it suffice to do it once before the loop?

testcases/kernel/syscalls/futex/futex_cmp_requeue01.c static void verify_futex_cmp_requeue(unsigned int n) · line 122

Quoted 8 lines
testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +3 -0
 		SAFE_WAITPID(pid[i], &status, 0);
 		if (WIFEXITED(status) && !WEXITSTATUS(status))
 			num_total++;
 	}
 
+	tst_res(TINFO, "children woken, futex0: %d, futex1: %d, "
+		"spurious wakeups: %d",
+		num_waits, num_requeues, tst_atomic_load(spurious));

I guess that we do not need atomic access once all the children are waited for.

Quoted 14 lines
testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +4 -2
+	/* Fail if any waiter timed out */
 	if (num_total != tc->num_waiters) {
 		tst_res(TFAIL, "%d waiters were not woken up normally",
 			tc->num_waiters - num_total);
 		return;
 	}
 
-	if (num_requeues != tc->set_requeues) {
+	/* Fail if more than upper limit of tc->set_requeues were found at futex1 */
+	if (num_requeues > tc->set_requeues) {
 		tst_res(TFAIL,
-			"futex_cmp_requeue() requeues %d waiters, expected %d",
+			"requeued %d waiters, expected <= %d",
 			num_requeues, tc->set_requeues);

testcases/kernel/syscalls/futex/futex_cmp_requeue01.c static void verify_futex_cmp_requeue(unsigned int n) · line 140

Quoted 10 lines
testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +2 -5
 		return;
 	}
 
-	if (tc->num_waiters - num_requeues - num_waits != tc->set_wakes) {
-		tst_res(TFAIL,
-			"futex_cmp_requeue() woke up %d waiters, expected %d",
-			tc->num_waiters - num_requeues - num_waits,
-			tc->set_wakes);
+	/* Fail if more than tc->set_wakes were woken up by requeue */
+	exp_ret = tc->num_waiters - TST_RET - tst_atomic_load(spurious);

Here as well, do we really need the atomic load?

Quoted 20 lines
testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +6 -4
+	if (num_waits < exp_ret) {
+		tst_res(TFAIL, "woken up %d on futex0, expected >= %d", num_waits, exp_ret);
 		return;
 	}
 
-	tst_res(TPASS,
-		"futex_cmp_requeue() woke up %d waiters and requeued %d waiters",
-		tc->set_wakes, tc->set_requeues);
+	tst_res(TPASS, "futex_cmp_requeue()");
 }
 
 static void setup(void)
@@ -112,13 +152,19 @@ static void setup(void)
 			    MAP_ANONYMOUS | MAP_SHARED, -1, 0);
 
 	futexes[0] = FUTEX_INITIALIZER;
-	futexes[1] = FUTEX_INITIALIZER + 1;
+	futexes[1] = FUTEX_INITIALIZER + 1000;
+
+	spurious = SAFE_MMAP(NULL, sizeof(int) * 2, PROT_READ | PROT_WRITE,

testcases/kernel/syscalls/futex/futex_cmp_requeue01.c static void setup(void) · line 167

Quoted 10 lines
testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +4 -0
+			    MAP_ANONYMOUS | MAP_SHARED, -1, 0);
+	test_done = spurious + 1;
 }
 
 static void cleanup(void)
 {
 	if (futexes)
 		SAFE_MUNMAP((void *)futexes, sizeof(futex_t) * 2);
+	if (spurious)
+		SAFE_MUNMAP((void *)spurious, sizeof(int) * 2);

Can't we just use a single page? It should be large enough for both futexes and counters...

I guess that we can as well define a structure with all the parameters so that we do only a single mmap() later on.

Quoted 6 lines
testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +0 -0
 }
 
 static struct tst_test test = {
Signature · 1 line
1.8.3.1
Signature · 2 lines
Cyril Hrubis
[email protected]
#2 lore raw

PATCH 1/1 futex_cmp_requeue01: fix test expectations

----- Original Message -----

Quoted 2 lines

Shouldn't these be volatile? Or does the tst_atomic_load() guarantee that compiler knows that it could be changed from a different process?

That should be implied. Our fallback functions issue compiler barriers too.

Quoted 13 lines

testcases/kernel/syscalls/futex/futex_cmp_requeue01.c static struct tcase { · line 41

Quoted 9 lines

static struct tcase {

testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +1 -1
 	int num_waiters;
@@ -37,14 +38,28 @@ static struct tcase {
 
 static void do_child(void)
 {
-	struct timespec usec = tst_ms_to_timespec(2000);
+	int max_sleep_ms = 5000, slept_for_ms = 0;

We do have a tst_multiply_timeout() in the test library now, shouldn't we use it for the max_sleep_ms here as well?

Quoted 2 lines

Also if we do that it would make sense to keep the timeout in global and initialize it in the parent, that would save us some runtime.

OK, I can add that.

Quoted 8 lines

testcases/kernel/syscalls/futex/futex_cmp_requeue01.c static void verify_futex_cmp_requeue(unsigned int n) · line 114

Quoted 5 lines
testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +1 -0
 	num_requeues = futex_wake(&futexes[1], tc->num_waiters, 0);
 	num_waits = futex_wake(&futexes[0], tc->num_waiters, 0);
 
 	for (i = 0; i < tc->num_waiters; i++) {
+		tst_atomic_store(1, test_done);

What's the point of storing the value in the loop, shouldn't it suffice to do it once before the loop?

Yes. I previously used kill() here for each child. When I changed that I forgot to move it out of loop.

Quoted 6 lines
Quoted 6 lines
testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +0 -0
 		SAFE_WAITPID(pid[i], &status, 0);
 		if (WIFEXITED(status) && !WEXITSTATUS(status))
 			num_total++;
 	}
 
Quoted 6 lines

testcases/kernel/syscalls/futex/futex_cmp_requeue01.c static void verify_futex_cmp_requeue(unsigned int n) · line 122

Quoted 3 lines
testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +3 -0
+	tst_res(TINFO, "children woken, futex0: %d, futex1: %d, "
+		"spurious wakeups: %d",
+		num_waits, num_requeues, tst_atomic_load(spurious));

I guess that we do not need atomic access once all the children are waited for.

Strictly no, but it seems more consistent. I don't think we care about performance impact of it.

Quoted 11 lines

testcases/kernel/syscalls/futex/futex_cmp_requeue01.c static void setup(void) · line 167

Quoted 7 lines
testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +2 -0
 static void cleanup(void)
 {
 	if (futexes)
 		SAFE_MUNMAP((void *)futexes, sizeof(futex_t) * 2);
+	if (spurious)
+		SAFE_MUNMAP((void *)spurious, sizeof(int) * 2);

Can't we just use a single page? It should be large enough for both futexes and counters...

Quoted 2 lines

I guess that we can as well define a structure with all the parameters so that we do only a single mmap() later on.

I'll put it into single struct and single mmap.

Thanks,
Jan

#3 lore raw

PATCH v2 1/1 futex_cmp_requeue01: fix test expectations

There are couple problems:

1. Keeping same uaddr1 value across requeue leads to a side-effect. If there is a signal or spurious wakeup, futex_wait() operation can be restarted (by kernel) with same input parameters. Which means that process requeued for uaddr2, goes back to queueing for uaddr1. Such use case is currently not valid as it is expected that uaddr1 value changes, so that any late waiter can notice it and goes back with -EWOULDBLOCK (-EAGAIN).

2. Test doesn't expect possibility of spurious wakeups.

3. Test is expecting to get exact values of woken/requeued processes. Man page wording like "at most" or "maximum of" does not guarantee exact numbers.

Change futex value before requeue, so child processes can observe spurious wakeups.

Change child process, such that it always sleeps, to guarantee that TST_PROCESS_STATE_WAIT() will always succeed finding sleeping process.

Change default timeout to 5 seconds. Spawning 1000 process on slower systems was getting close to 1 second. This doesn't affect runtime in PASS-ing case.

Change checks such that they reflect wording in man page, and don't test for absolute values (see comments in code). One exception is that we assume futex_wake(tc->num_waiters) will always wake up all remaining processes.

---
 .../kernel/syscalls/futex/futex_cmp_requeue01.c    | 105 +++++++++++++++------
 1 file changed, 78 insertions(+), 27 deletions(-)

v2 changes:
- use tst_multiply_timeout()
- remove tst_atomic_store from loop
- shared variables moved to single struct

testcases/kernel/syscalls/futex/futex_cmp_requeue01.c +78 -27
index f5264c2ba26f..1711861ef298 100644
@@ -19,7 +19,14 @@
 #include "tst_test.h"
 #include "futextest.h"
 
-static futex_t *futexes;
+struct shared_data {
+	futex_t futexes[2];
+	int spurious;
+	int test_done;
+};
+
+static struct shared_data *sd;
+static int max_sleep_ms;
 
 static struct tcase {
 	int num_waiters;
@@ -37,14 +44,30 @@ static struct tcase {
 
 static void do_child(void)
 {
-	struct timespec usec = tst_ms_to_timespec(2000);
+	int slept_for_ms = 0;
+	struct timespec usec = tst_ms_to_timespec(max_sleep_ms);
 	int pid = getpid();
+	int ret = 0;
+
+	if (futex_wait(&sd->futexes[0], sd->futexes[0], &usec, 0) == -1) {
+		if (errno == EAGAIN) {
+			/* spurious wakeup or signal */
+			tst_atomic_inc(&sd->spurious);
+		} else {
+			tst_res(TFAIL | TERRNO, "process %d wasn't woken up",
+				pid);
+			ret = 1;
+		}
+	}
 
-	if (!futex_wait(&futexes[0], futexes[0], &usec, 0))
-		exit(0);
+	/* make sure TST_PROCESS_STATE_WAIT() can always succeed */
+	while (!tst_atomic_load(&sd->test_done)
+		&& (slept_for_ms < max_sleep_ms)) {
+		usleep(50000);
+		slept_for_ms += 50;
+	}
 
-	tst_res(TINFO | TERRNO, "process %d wasn't woken up", pid);
-	exit(1);
+	exit(ret);
 }
 
 static void verify_futex_cmp_requeue(unsigned int n)
@@ -55,6 +78,8 @@ static void verify_futex_cmp_requeue(unsigned int n)
 	int pid[tc->num_waiters];
 	int exp_ret = tc->set_wakes + tc->set_requeues;
 
+	tst_atomic_store(0, &sd->spurious);
+	tst_atomic_store(0, &sd->test_done);
 	for (i = 0; i < tc->num_waiters; i++) {
 		pid[i] = SAFE_FORK();
 		if (!pid[i])
@@ -64,61 +89,87 @@ static void verify_futex_cmp_requeue(unsigned int n)
 	for (i = 0; i < tc->num_waiters; i++)
 		TST_PROCESS_STATE_WAIT(pid[i], 'S');
 
-	TEST(futex_cmp_requeue(&futexes[0], futexes[0], &futexes[1],
-	     tc->set_wakes, tc->set_requeues, 0));
-	if (TST_RET != exp_ret) {
-		tst_res(TFAIL, "futex_cmp_requeue() returned %ld, expected %d",
+	tst_res(TINFO, "Test %d: waiters: %d, wakes: %d, requeues: %d",
+		n, tc->num_waiters, tc->set_wakes, tc->set_requeues);
+
+	/*
+	 * change futex value, so any spurious wakeups or signals after
+	 * this point get bounced back to userspace.
+	 */
+	sd->futexes[0]++;
+	sd->futexes[1]++;
+
+	/*
+	 * Wakes up a maximum of tc->set_wakes waiters. tc->set_requeues
+	 * specifies an upper limit on the number of waiters that are requeued.
+	 * Returns the total number of waiters that were woken up or requeued.
+	 */
+	TEST(futex_cmp_requeue(&sd->futexes[0], sd->futexes[0], &sd->futexes[1],
+		tc->set_wakes, tc->set_requeues, 0));
+
+	/* Fail if more than requested wakes + requeues were returned */
+	if (TST_RET > exp_ret) {
+		tst_res(TFAIL, "futex_cmp_requeue() returned %ld, expected <= %d",
 			TST_RET, exp_ret);
+	} else {
+		tst_res(TINFO, "futex_cmp_requeue() returned %ld", TST_RET);
 	}
 
-	num_requeues = futex_wake(&futexes[1], tc->num_waiters, 0);
-	num_waits = futex_wake(&futexes[0], tc->num_waiters, 0);
+	num_requeues = futex_wake(&sd->futexes[1], tc->num_waiters, 0);
+	num_waits = futex_wake(&sd->futexes[0], tc->num_waiters, 0);
 
+	tst_atomic_store(1, &sd->test_done);
 	for (i = 0; i < tc->num_waiters; i++) {
 		SAFE_WAITPID(pid[i], &status, 0);
 		if (WIFEXITED(status) && !WEXITSTATUS(status))
 			num_total++;
 	}
 
+	tst_res(TINFO, "children woken, futex0: %d, futex1: %d, "
+		"spurious wakeups: %d",
+		num_waits, num_requeues, tst_atomic_load(&sd->spurious));
+
+	/* Fail if any waiter timed out */
 	if (num_total != tc->num_waiters) {
 		tst_res(TFAIL, "%d waiters were not woken up normally",
 			tc->num_waiters - num_total);
 		return;
 	}
 
-	if (num_requeues != tc->set_requeues) {
+	/* Fail if more than upper limit of tc->set_requeues is at futex1 */
+	if (num_requeues > tc->set_requeues) {
 		tst_res(TFAIL,
-			"futex_cmp_requeue() requeues %d waiters, expected %d",
+			"requeued %d waiters, expected <= %d",
 			num_requeues, tc->set_requeues);
 		return;
 	}
 
-	if (tc->num_waiters - num_requeues - num_waits != tc->set_wakes) {
-		tst_res(TFAIL,
-			"futex_cmp_requeue() woke up %d waiters, expected %d",
-			tc->num_waiters - num_requeues - num_waits,
-			tc->set_wakes);
+	/* Fail if more than tc->set_wakes were woken up by requeue */
+	exp_ret = tc->num_waiters - TST_RET - tst_atomic_load(&sd->spurious);
+	if (num_waits < exp_ret) {
+		tst_res(TFAIL, "woken up %d on futex0, expected >= %d",
+			num_waits, exp_ret);
 		return;
 	}
 
-	tst_res(TPASS,
-		"futex_cmp_requeue() woke up %d waiters and requeued %d waiters",
-		tc->set_wakes, tc->set_requeues);
+	tst_res(TPASS, "futex_cmp_requeue()");
 }
 
 static void setup(void)
 {
-	futexes = SAFE_MMAP(NULL, sizeof(futex_t) * 2, PROT_READ | PROT_WRITE,
+	max_sleep_ms = tst_multiply_timeout(5000);
+
+	sd = SAFE_MMAP(NULL, sizeof(*sd), PROT_READ | PROT_WRITE,
 			    MAP_ANONYMOUS | MAP_SHARED, -1, 0);
 
-	futexes[0] = FUTEX_INITIALIZER;
-	futexes[1] = FUTEX_INITIALIZER + 1;
+	sd->futexes[0] = FUTEX_INITIALIZER;
+	sd->futexes[1] = FUTEX_INITIALIZER + 1000;
 }
 
 static void cleanup(void)
 {
-	if (futexes)
-		SAFE_MUNMAP((void *)futexes, sizeof(futex_t) * 2);
+	if (sd)
+		SAFE_MUNMAP((void *)sd, sizeof(*sd));
 }
 
 static struct tst_test test = {
Signature · 1 line
1.8.3.1
#4 lore raw

PATCH v2 1/1 futex_cmp_requeue01: fix test expectations

Hi!

Quoted 20 lines

1. Keeping same uaddr1 value across requeue leads to a side-effect. If there is a signal or spurious wakeup, futex_wait() operation can be restarted (by kernel) with same input parameters. Which means that process requeued for uaddr2, goes back to queueing for uaddr1. Such use case is currently not valid as it is expected that uaddr1 value changes, so that any late waiter can notice it and goes back with -EWOULDBLOCK (-EAGAIN).

2. Test doesn't expect possibility of spurious wakeups.

3. Test is expecting to get exact values of woken/requeued processes. Man page wording like "at most" or "maximum of" does not guarantee exact numbers.

Change futex value before requeue, so child processes can observe spurious wakeups.

Change child process, such that it always sleeps, to guarantee that TST_PROCESS_STATE_WAIT() will always succeed finding sleeping process.

Quoted 8 lines

Change default timeout to 5 seconds. Spawning 1000 process on slower systems was getting close to 1 second. This doesn't affect runtime in PASS-ing case.

Change checks such that they reflect wording in man page, and don't test for absolute values (see comments in code). One exception is that we assume futex_wake(tc->num_waiters) will always wake up all remaining processes.

I was thinking about this and the only unpreciseness we can get here is the number of spuriously woken up processes at the end of the test and that is because we cannot tell where exactly the spurious wakeup happened, right?

That means that all the assertion we could have made without the spurious wakeups will still hold, but we will have to take the number of spurious wakeups as our measurement error, just like in physics.

Also the futex_cmp_requeue() should prefer waking processes up against requeue operation so basically:

TST_RET - num_requeues = set_wakes

Unless spurious wakeup has happened between the requeue and wake operation which means that the num_requeues can be smaller because we will wake up less than requeued processes. So if we sampled spurious wakeups before the requeue operation and after the futex_wake() for requeued processes and call it delta_spurious we would get a range:

TST_RET - num_requeues >= set_wakes

&&

TST_RET - num_requeues - delta_spurious <= set_wakes

Similarily the number of processes left waiting on the futex should be in a range of expected and MIN(0, expected - spurious) where expected = num_waiter - set_wakes - set_requeues.

And lastly the num_requeues should be between set_requeues and MIN(0, set_requeues - spurious).

Or did is miss something that invalidates my line of thought?

Also btw, we are missing a tcase where we attempt to wake more processes that are sleeping on the futex and check that we haven't requeued any because all were woken up.

Signature · 2 lines
Cyril Hrubis
[email protected]
#5 lore raw

PATCH v2 1/1 futex_cmp_requeue01: fix test expectations

----- Original Message -----

Quoted 10 lines

I was thinking about this and the only unpreciseness we can get here is the number of spuriously woken up processes at the end of the test and that is because we cannot tell where exactly the spurious wakeup happened, right?

That means that all the assertion we could have made without the spurious wakeups will still hold
, but we will have to take the number of
spurious wakeups as our measurement error, just like in physics.

Quoted 4 lines

Also the futex_cmp_requeue() should prefer waking processes up against requeue operation so basically:

TST_RET - num_requeues = set_wakes

It comes down to how we interpret man page (more below).

Quoted 8 lines

Unless spurious wakeup has happened between the requeue and wake operation which means that the num_requeues can be smaller because we will wake up less than requeued processes. So if we sampled spurious wakeups before the requeue operation and after the futex_wake() for requeued processes and call it delta_spurious we would get a range:

TST_RET - num_requeues >= set_wakes

This doesn't look correct if we consider spurious wakeups:

5 processes, set_wakes = 5, set_requeue = 0, 1 spuriously wakes up, remaining 4 are woken up by futex(), 0 are requeued:

4 - 0 >= 5

Quoted 4 lines

&&

TST_RET - num_requeues - delta_spurious <= set_wakes

This seems ok - number of processes woken up by futex_cmp_requeue must be less than set_wakes.

If number of processes we find on uaddr1/uaddr2 have expected values and nothing timed out, that should imply above as well.

Quoted 3 lines

Similarily the number of processes left waiting on the futex should be in a range of expected and MIN(0, expected - spurious) where

I don't get the "MIN()". It's 0 or less than zero?

Quoted 1 line

expected = num_waiter - set_wakes - set_requeues.

This might be where I took man page too pessimistically. Specifically this part: "wakes up a maximum of val waiters". I took that as "can wake up fewer waiters at any time". While your formulas seem to imply that "if there are _enough_ waiters, it will _always_ wake up val waiters".

Looking at futex_requeue():

                if (++task_count <= nr_wake && !requeue_pi) {
                        mark_wake_futex(&wake_q, this);
                        continue;
                }

the latter looks plausible. We don't use FUTEX_CMP_REQUEUE_PI, which appears to be only way to avoid wakeup (when there are enough waiters).

If we go with latter case, then I agree v2 is unnecessarily cautious in its assertions.

Quoted 3 lines

And lastly the num_requeues should be between set_requeues and MIN(0, set_requeues - spurious).

Was MIN supposed to be MAX?

Quoted 7 lines

Or did is miss something that invalidates my line of thought?

Also btw, we are missing a tcase where we attempt to wake more processes that are sleeping on the futex and check that we haven't requeued any because all were woken up.

That looks like it would complicate things because we no longer assume there are "enough waiters".

expected = num_waiter - set_wakes - set_requeues

could go negative. It might be enough to have tcase where num_waiter == set_wakes and set_requeues = 0.

#6 lore raw

PATCH v2 1/1 futex_cmp_requeue01: fix test expectations

Hi!

Quoted 6 lines
Quoted 6 lines

Unless spurious wakeup has happened between the requeue and wake operation which means that the num_requeues can be smaller because we will wake up less than requeued processes. So if we sampled spurious wakeups before the requeue operation and after the futex_wake() for requeued processes and call it delta_spurious we would get a range:

Quoted 8 lines
Quoted 1 line

TST_RET - num_requeues >= set_wakes

This doesn't look correct if we consider spurious wakeups:

5 processes, set_wakes = 5, set_requeue = 0, 1 spuriously wakes up, remaining 4 are woken up by futex(), 0 are requeued:

4 - 0 >= 5

Well I was betting on the fact that we wake up much less processes than we attempt to lock on the futex and that waking up processes takes precedence. I we can add delta_spurious to the right side that wouldn't change much and we end up being correct all the time, i.e.

TST_RET + delta_spurious - num_requeues >= set_wakes

That together with the next one gives us range:

TST_RET - num_requeues = set_wakes +-delta_spurious

Quoted 8 lines
Quoted 4 lines

&&

TST_RET - num_requeues - delta_spurious <= set_wakes

This seems ok - number of processes woken up by futex_cmp_requeue must be less than set_wakes.

Quoted 8 lines

If number of processes we find on uaddr1/uaddr2 have expected values and nothing timed out, that should imply above as well.

Quoted 3 lines

Similarily the number of processes left waiting on the futex should be in a range of expected and MIN(0, expected - spurious) where

I don't get the "MIN()". It's 0 or less than zero?

Sigh, should have been MAX() to avoid negative numbers in case that spurious > expected.

Quoted 13 lines
Quoted 1 line

expected = num_waiter - set_wakes - set_requeues.

This might be where I took man page too pessimistically. Specifically this part: "wakes up a maximum of val waiters". I took that as "can wake up fewer waiters at any time". While your formulas seem to imply that "if there are _enough_ waiters, it will _always_ wake up val waiters".

Looking at futex_requeue():

                if (++task_count <= nr_wake && !requeue_pi) {
                        mark_wake_futex(&wake_q, this);
                        continue;
                }
Quoted 6 lines

the latter looks plausible. We don't use FUTEX_CMP_REQUEUE_PI, which appears to be only way to avoid wakeup (when there are enough waiters).

If we go with latter case, then I agree v2 is unnecessarily cautious in its assertions.

As far as I can tell the wording in man page is there to suggest that it cannot wake more processes than it's sleeping on the futex. I do not think that it's explicitelly written anywhere that it will never fail to wake up waiters it was requested to but all of the code from the original futex tests was depending on that and the rewritten tests does as well, have a look at futex_wake02.c for instance. Also there is no point in waking less than available, it would only complicate the API since we would have to loop over each futex_wake() in userspace. Having a look at "Futexes are tricky" by Drepper none of the example code does that either.

Quoted 4 lines
Quoted 2 lines

And lastly the num_requeues should be between set_requeues and MIN(0, set_requeues - spurious).

Was MIN supposed to be MAX?

Yes, indeed, sorry.

Quoted 7 lines
Quoted 6 lines

Or did is miss something that invalidates my line of thought?

Also btw, we are missing a tcase where we attempt to wake more processes that are sleeping on the futex and check that we haven't requeued any because all were woken up.

Quoted 7 lines

That looks like it would complicate things because we no longer assume there are "enough waiters".

expected = num_waiter - set_wakes - set_requeues

could go negative. It might be enough to have tcase where num_waiter == set_wakes and set_requeues = 0.

I was thinking of putting that case into a separate testcase, all that we would have to check there as a PASS would be that there are none sleepers requeued if number of processes to wake was >= than the number of sleeping processes.

Signature · 2 lines
Cyril Hrubis
[email protected]
#7 lore raw

PATCH v2 1/1 futex_cmp_requeue01: fix test expectations

----- Original Message -----

Quoted 14 lines

Hi!

Quoted 13 lines
Quoted 7 lines

Unless spurious wakeup has happened between the requeue and wake operation which means that the num_requeues can be smaller because we will wake up less than requeued processes. So if we sampled spurious wakeups before the requeue operation and after the futex_wake() for requeued processes and call it delta_spurious we would get a range:

TST_RET - num_requeues >= set_wakes

This doesn't look correct if we consider spurious wakeups:

5 processes, set_wakes = 5, set_requeue = 0, 1 spuriously wakes up, remaining 4 are woken up by futex(), 0 are requeued:

Quoted 8 lines
Quoted 1 line

4 - 0 >= 5

Well I was betting on the fact that we wake up much less processes than we attempt to lock on the futex and that waking up processes takes precedence. I we can add delta_spurious to the right side that wouldn't change much and we end up being correct all the time, i.e.

TST_RET + delta_spurious - num_requeues >= set_wakes

I'd go with just spurious instead of delta_spurious. If there is spurious wake up before requeue (and first sample), wouldn't that fail in same way as example above?

TST_RET + delta_spurious - num_requeues >= set_wakes 4 + 0 - 0 >= 5

Also delta_spurious looks racy, because it's based on counter that is increased only after user-space gets chance to run. But process may have been already removed from futex queue on kernel side. So 'first sample before requeue' can see inaccurate state.

So I'd tweak your check to:
set_wakes-spurious <= TST_RET-num_requeues <= set_wakes+spurious

#8 lore raw

PATCH v2 1/1 futex_cmp_requeue01: fix test expectations

Any thoughts about my last reply?

----- Original Message -----

Quoted 46 lines

----- Original Message -----

Quoted 14 lines

Hi!

Quoted 13 lines
Quoted 7 lines

Unless spurious wakeup has happened between the requeue and wake operation which means that the num_requeues can be smaller because we will wake up less than requeued processes. So if we sampled spurious wakeups before the requeue operation and after the futex_wake() for requeued processes and call it delta_spurious we would get a range:

TST_RET - num_requeues >= set_wakes

This doesn't look correct if we consider spurious wakeups:

5 processes, set_wakes = 5, set_requeue = 0, 1 spuriously wakes up, remaining 4 are woken up by futex(), 0 are requeued:

Quoted 8 lines
Quoted 1 line

4 - 0 >= 5

Well I was betting on the fact that we wake up much less processes than we attempt to lock on the futex and that waking up processes takes precedence. I we can add delta_spurious to the right side that wouldn't change much and we end up being correct all the time, i.e.

TST_RET + delta_spurious - num_requeues >= set_wakes

I'd go with just spurious instead of delta_spurious. If there is spurious wake up before requeue (and first sample), wouldn't that fail in same way as example above?

TST_RET + delta_spurious - num_requeues >= set_wakes 4 + 0 - 0 >= 5

Also delta_spurious looks racy, because it's based on counter that is increased only after user-space gets chance to run. But process may have been already removed from futex queue on kernel side. So 'first sample before requeue' can see inaccurate state.

So I'd tweak your check to:
set_wakes-spurious <= TST_RET-num_requeues <= set_wakes+spurious

--
Mailing list info: https://lists.linux.it/listinfo/ltp

#9 lore raw

PATCH v2 1/1 futex_cmp_requeue01: fix test expectations

Hi!

Quoted 1 line

Any thoughts about my last reply?

Sorry this fallen out of my radar since I've been off previous week.

Quoted 29 lines
Quoted 29 lines
Quoted 13 lines
Quoted 13 lines
Quoted 7 lines

Unless spurious wakeup has happened between the requeue and wake operation which means that the num_requeues can be smaller because we will wake up less than requeued processes. So if we sampled spurious wakeups before the requeue operation and after the futex_wake() for requeued processes and call it delta_spurious we would get a range:

TST_RET - num_requeues >= set_wakes

This doesn't look correct if we consider spurious wakeups:

5 processes, set_wakes = 5, set_requeue = 0, 1 spuriously wakes up, remaining 4 are woken up by futex(), 0 are requeued:

Quoted 8 lines
Quoted 1 line

4 - 0 >= 5

Well I was betting on the fact that we wake up much less processes than we attempt to lock on the futex and that waking up processes takes precedence. I we can add delta_spurious to the right side that wouldn't change much and we end up being correct all the time, i.e.

TST_RET + delta_spurious - num_requeues >= set_wakes

I'd go with just spurious instead of delta_spurious. If there is spurious wake up before requeue (and first sample), wouldn't that fail in same way as example above?

TST_RET + delta_spurious - num_requeues >= set_wakes 4 + 0 - 0 >= 5

Quoted 7 lines
Quoted 7 lines

Also delta_spurious looks racy, because it's based on counter that is increased only after user-space gets chance to run. But process may have been already removed from futex queue on kernel side. So 'first sample before requeue' can see inaccurate state.

So I'd tweak your check to:
set_wakes-spurious <= TST_RET-num_requeues <= set_wakes+spurious

Sounds reasonable to me.

Signature · 2 lines
Cyril Hrubis
[email protected]