[LTP] [RFC PATCH 0/4] Synchronising two threads

[LTP] [RFC PATCH 0/4] Synchronising two threads

[Richard Palethorpe]

As well as fixing a bug, this patch allows two long running threads to be
synchronised at given points using memory barriers. Previously we were
effectively synchronising the threads by restarting one of them each
iteration. However this had a significant overhead and may have caused
greater variation in timings between iterations.

I am using __atomic_* builtins which don't exist on older compilers. I will
probably update tst_atomic.h and introduce some more tst_atomic_* functions.

Richard Palethorpe (4):
  fzsync: Add long running thread support
  Convert cve-2016-7117 test to use long running threads
  fzsync: Correctly handle timestamps across second boundaries
  fzsync: Print info from pair_update

 include/tst_fuzzy_sync.h      | 108 +++++++++++++++++++++++++++++++++++++++++-
 testcases/cve/cve-2016-7117.c |  32 ++++++-------
 2 files changed, 121 insertions(+), 19 deletions(-)

-- 
2.13.3

[LTP] [RFC PATCH 1/4] fzsync: Add long running thread support

[Richard Palethorpe]

---
 include/tst_fuzzy_sync.h | 94 +++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 93 insertions(+), 1 deletion(-)

diff --git a/include/tst_fuzzy_sync.h b/include/tst_fuzzy_sync.h
index 229217495..5234c5aa5 100644
--- a/include/tst_fuzzy_sync.h
+++ b/include/tst_fuzzy_sync.h
@@ -49,6 +49,8 @@
  * @delay_inc: The step size of a delay increment, defaults to 10
  * @update_gap: The number of iterations between recalculating the delay.
  *              Defaults to 0xF and must be of the form $2^n - 1$
+ * @yin: Used by fzsync_pair_wait()
+ * @yang: Used by fzsync_pair_wait()
  *
  * This contains all the necessary state for synchronising two points A and
  * B. Where A is the time of an event in one process and B is the time of an
@@ -63,6 +65,8 @@ struct tst_fzsync_pair {
 	long delay;
 	long delay_inc;
 	int update_gap;
+	unsigned int yin;
+	unsigned int yang;
 };
 
 /**
@@ -70,7 +74,7 @@ struct tst_fzsync_pair {
  */
 #define TST_FZSYNC_PAIR_INIT {	\
 	.avg_alpha = 0.25,	\
-	.delay_inc = 10,	\
+	.delay_inc = 1,	        \
 	.update_gap = 0xF	\
 }
 
@@ -180,3 +184,91 @@ static void tst_fzsync_pair_update(int loop_index, struct tst_fzsync_pair *pair)
 
 	pair->avg_diff = avg;
 }
+
+#define FENCE_ERROR tst_brk(TBROK, "pair->fence is invalid: %d", f)
+
+/**
+ * tst_fzsync_pair_wait - Wait for the other thread
+ *
+ * Use this if you need an additional synchronisation point in a thread. See
+ * tst_fzsync_pair_wait_update().
+ *
+ * Returns a non-zero value if the thread should continue otherwise the
+ * calling thread should exit.
+ */
+static inline int tst_fzsync_pair_wait(struct tst_fzsync_pair *pair)
+{
+	unsigned int n;
+
+	__atomic_add_fetch(&pair->yin, 1, __ATOMIC_RELEASE);
+	do {
+		n = 2;
+		__atomic_compare_exchange_n(&pair->yin, &n, 0, 0,
+					    __ATOMIC_RELEASE, __ATOMIC_ACQUIRE);
+	} while (n == 1);
+
+	__atomic_add_fetch(&pair->yang, 1, __ATOMIC_RELEASE);
+	do {
+		n = 2;
+		__atomic_compare_exchange_n(&pair->yang, &n, 0, 0,
+					    __ATOMIC_RELEASE, __ATOMIC_ACQUIRE);
+	} while (n == 1);
+
+	return n < 3;
+}
+
+/**
+ * tst_fzsync_pair_wait_update - Wait for the other thread and then recalculate
+ *
+ * This allows you to have two long running threads which wait for each other
+ * every iteration. So each thread will exit this function@approximately
+ * the same time. It also updates the delay values in a thread safe manner.
+ *
+ * You must call this function in both threads the same number of times each
+ * iteration. So a call in one thread must match with a call in the
+ * other. Make sure that calls to tst_fzsync_pair_wait() and
+ * tst_fzsync_pair_wait_update() happen in the same order in each thread.
+ *
+ * Returns a non-zero value if the calling thread should continue to loop. If
+ * it returns zero then tst_fzsync_exit() has been called and you must exit
+ * the thread.
+ */
+static inline int tst_fzsync_pair_wait_update(struct tst_fzsync_pair *pair)
+{
+	static int loop_index = 0;
+	unsigned int n = __atomic_add_fetch(&pair->yin, 1, __ATOMIC_ACQ_REL);
+
+	if (n == 2) {
+		loop_index++;
+		tst_fzsync_pair_update(loop_index, pair);
+		__atomic_compare_exchange_n(&pair->yin, &n, 0, 0,
+					    __ATOMIC_RELEASE, __ATOMIC_ACQUIRE);
+ 	}
+
+	 do {
+		n = __atomic_load_n(&pair->yin, __ATOMIC_ACQUIRE);
+	 } while (n && n < 3);
+
+	__atomic_add_fetch(&pair->yang, 1, __ATOMIC_RELEASE);
+	do {
+		n = 2;
+		__atomic_compare_exchange_n(&pair->yang, &n, 0, 0,
+					    __ATOMIC_RELEASE, __ATOMIC_ACQUIRE);
+	} while (n == 1);
+
+	return n < 3;
+}
+
+#undef FENCE_ERROR
+
+/**
+ * tst_fzsync_pair_exit - Signal that the other thread should exit
+ *
+ * Causes tst_fzsync_pair_wait() and tst_fzsync_pair_wait_update() to return
+ * 0.
+ */
+static inline void tst_fzsync_pair_exit(struct tst_fzsync_pair *pair)
+{
+	__atomic_store_n(&pair->yang, 3, __ATOMIC_RELEASE);
+	__atomic_store_n(&pair->yin, 3, __ATOMIC_RELEASE);
+}
-- 
2.13.3

[LTP] [RFC PATCH 2/4] Convert cve-2016-7117 test to use long running threads

[Richard Palethorpe]

---
 testcases/cve/cve-2016-7117.c | 32 +++++++++++++++-----------------
 1 file changed, 15 insertions(+), 17 deletions(-)

diff --git a/testcases/cve/cve-2016-7117.c b/testcases/cve/cve-2016-7117.c
index deb667761..e047f5001 100644
--- a/testcases/cve/cve-2016-7117.c
+++ b/testcases/cve/cve-2016-7117.c
@@ -103,15 +103,18 @@ static void cleanup(void)
 
 static void *send_and_close(void *arg)
 {
-	send(socket_fds[0], MSG, sizeof(MSG), 0);
-	send(socket_fds[0], MSG, sizeof(MSG), 0);
+	while(tst_fzsync_pair_wait_update(&fzsync_pair)) {
+		send(socket_fds[0], MSG, sizeof(MSG), 0);
+		send(socket_fds[0], MSG, sizeof(MSG), 0);
 
-	tst_fzsync_delay_b(&fzsync_pair);
-
-	close(socket_fds[0]);
-	close(socket_fds[1]);
-	tst_fzsync_time_b(&fzsync_pair);
+		tst_fzsync_delay_b(&fzsync_pair);
 
+		close(socket_fds[0]);
+		close(socket_fds[1]);
+		tst_fzsync_time_b(&fzsync_pair);
+		if (!tst_fzsync_pair_wait(&fzsync_pair))
+			return arg;
+	}
 	return arg;
 }
 
@@ -121,13 +124,13 @@ static void run(void)
 	int i, stat, too_early_count = 0;
 
 	msghdrs[0].msg_hdr.msg_iov->iov_base = (void *)&rbuf;
+	SAFE_PTHREAD_CREATE(&pt_send, 0, send_and_close, 0);
 
 	for (i = 1; i < ATTEMPTS; i++) {
 		if (socketpair(AF_LOCAL, SOCK_DGRAM, 0, socket_fds))
 			tst_brk(TBROK | TERRNO, "Socket creation failed");
 
-		SAFE_PTHREAD_CREATE(&pt_send, 0, send_and_close, 0);
-
+		tst_fzsync_pair_wait_update(&fzsync_pair);
 		tst_fzsync_delay_a(&fzsync_pair);
 
 		stat = tst_syscall(__NR_recvmmsg,
@@ -140,16 +143,11 @@ static void run(void)
 		else if (stat < 0)
 			tst_res(TWARN | TERRNO, "recvmmsg failed unexpectedly");
 
-		SAFE_PTHREAD_JOIN(pt_send, 0);
-
-		tst_fzsync_pair_update(i, &fzsync_pair);
-		if (!(i & 0x7FFFF)) {
-			tst_res(TINFO, "Too early: %.1f%%",
-				100 * too_early_count / (float)i);
-			tst_fzsync_pair_info(&fzsync_pair);
-		}
+		tst_fzsync_pair_wait(&fzsync_pair);
 	}
 
+	tst_fzsync_pair_exit(&fzsync_pair);
+	SAFE_PTHREAD_JOIN(pt_send, 0);
 	tst_res(TPASS, "Nothing happened after %d attempts", ATTEMPTS);
 }
 
-- 
2.13.3

[LTP] [RFC PATCH 3/4] fzsync: Correctly handle timestamps across second boundaries

[Richard Palethorpe]

Previously we only calculated the difference between timestamps based on
tv_nsec so when a.tv_sec: 281122, a.tv_nsec: 999996364, b.tv_sec: 281123,
b.tv_nsec: 31. The difference between a and b is incorrectly calculated
as (a - b = 999996364 - 31) even though b happened after a.

Now, one second is added to b's tv_nsec so that the calculation in the above
example becomes (999996364 - 1000000031). It is assumed that a and b will
never be more than a second apart. However the average diff should not be too
badly effected if they occasionally are.
---
 include/tst_fuzzy_sync.h | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/include/tst_fuzzy_sync.h b/include/tst_fuzzy_sync.h
index 5234c5aa5..5305f88e8 100644
--- a/include/tst_fuzzy_sync.h
+++ b/include/tst_fuzzy_sync.h
@@ -172,6 +172,12 @@ static void tst_fzsync_pair_update(int loop_index, struct tst_fzsync_pair *pair)
 	double target = pair->avg_diff_trgt;
 	double avg = pair->avg_diff;
 
+	if (pair->a.tv_sec > pair->b.tv_sec) {
+		pair->a.tv_nsec += 1000000000;
+	} else if (pair->a.tv_sec < pair->b.tv_sec) {
+		pair->b.tv_nsec += 1000000000;
+	}
+
 	diff = pair->a.tv_nsec - pair->b.tv_nsec;
 	avg = tst_exp_moving_avg(pair->avg_alpha, diff, avg);
 
-- 
2.13.3

[LTP] [RFC PATCH 4/4] fzsync: Print info from pair_update

[Richard Palethorpe]

It is very useful to see some stats so we include it in the update function by
default.
---
 include/tst_fuzzy_sync.h | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/include/tst_fuzzy_sync.h b/include/tst_fuzzy_sync.h
index 5305f88e8..e361322d8 100644
--- a/include/tst_fuzzy_sync.h
+++ b/include/tst_fuzzy_sync.h
@@ -49,6 +49,7 @@
  * @delay_inc: The step size of a delay increment, defaults to 10
  * @update_gap: The number of iterations between recalculating the delay.
  *              Defaults to 0xF and must be of the form $2^n - 1$
+ * @info_gap: The number of iterations between printing some stats.
  * @yin: Used by fzsync_pair_wait()
  * @yang: Used by fzsync_pair_wait()
  *
@@ -65,6 +66,7 @@ struct tst_fzsync_pair {
 	long delay;
 	long delay_inc;
 	int update_gap;
+	int info_gap;
 	unsigned int yin;
 	unsigned int yang;
 };
@@ -75,7 +77,8 @@ struct tst_fzsync_pair {
 #define TST_FZSYNC_PAIR_INIT {	\
 	.avg_alpha = 0.25,	\
 	.delay_inc = 1,	        \
-	.update_gap = 0xF	\
+	.update_gap = 0xF,	\
+	.info_gap = 0x7FFFF     \
 }
 
 static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair)
@@ -188,6 +191,9 @@ static void tst_fzsync_pair_update(int loop_index, struct tst_fzsync_pair *pair)
 			pair->delay += inc;
 	}
 
+	if (!(loop_index & pair->info_gap))
+		tst_fzsync_pair_info(pair);
+
 	pair->avg_diff = avg;
 }
 
-- 
2.13.3