[LTP] [PATCH 0/5] New fuzzy sync library API

[LTP] [PATCH 0/5] New fuzzy sync library API

[Richard Palethorpe]

This is a major change to how the tst_fuzzy_sync.h library works and how it is
used. Previously I was working on a slightly modified version which just
introduces a timeout, but while I was waiting for that to be reviewed I
started this and had a 'breakthrough'. So I have decided to skip the slightly
modified version and jump straight to this (as Li Wang suggested).

Below are some notes on the timing calculation (addressing Cyril's concerns)
which may make sense after reading the code and docs:

I have tested this on X86 and some ARM systems, including Rasp Pi. It appears
they all have high resolution clocks capable of taking the time measurments
required. To simulate a system with a low resolution clock I used
CLOCK_REALTIME_COARSE. The result was that the time measurement averages which
the algorithm relies on were all close to zero with a large deviation. In this
case the randomised delay is simply never activated, which seems like an
acceptable outcome as the library still functions without it. If the clock has
a low resolution, but the timings are consistently above zero, then a delay
will be calculated which is maybe too large or too small. This may degrade the
performance of the algorithm, but I doubt it will break it.

If the time between end_race_a and end_race_b is less than the clock
resolution or too variable then the algorithm won't be able to calculate the
number of spins required to create a suitable time delay. There are possible
solutions for this, but I haven't thought of any which reduce complexity
instead of increasing it. I have no idea if this will be a problem in
practice. In the common case it won't be, but it needs testing on a very
diverse set of systems.

Richard Palethorpe (5):
  lib: Allow user to easily get LTP_TIMEOUT_MUL value
  tst_timer: Create interface for using multiple timers
  tst_timer: Add nano second conversions
  fzsync: Simplify API with start/end race calls and limit exec time
  Convert tests to use fzsync_{start,end}_race API

 include/tst_fuzzy_sync.h                      | 634 +++++++++++++-----
 include/tst_test.h                            |   1 +
 include/tst_timer.h                           |  62 ++
 lib/newlib_tests/test16.c                     |  24 +-
 lib/tst_test.c                                |  23 +-
 lib/tst_timer.c                               |  21 +
 testcases/cve/cve-2014-0196.c                 |  25 +-
 testcases/cve/cve-2016-7117.c                 |  35 +-
 testcases/cve/cve-2017-2671.c                 |  23 +-
 testcases/kernel/syscalls/inotify/inotify09.c |  23 +-
 .../kernel/syscalls/ipc/shmctl/shmctl05.c     |  28 +-
 11 files changed, 615 insertions(+), 284 deletions(-)

-- 
2.18.0

[LTP] [PATCH 1/5] lib: Allow user to easily get LTP_TIMEOUT_MUL value

[Richard Palethorpe]

Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
---
 include/tst_test.h |  1 +
 lib/tst_test.c     | 23 ++++++++++++++---------
 2 files changed, 15 insertions(+), 9 deletions(-)

diff --git a/include/tst_test.h b/include/tst_test.h
index 98dacf387..0ad9025f2 100644
--- a/include/tst_test.h
+++ b/include/tst_test.h
@@ -217,6 +217,7 @@ const char *tst_strsig(int sig);
  */
 const char *tst_strstatus(int status);
 
+float tst_timeout_mul(void);
 void tst_set_timeout(int timeout);
 
 #ifndef TST_NO_DEFAULT_MAIN
diff --git a/lib/tst_test.c b/lib/tst_test.c
index 2f3d357d2..f760e05b3 100644
--- a/lib/tst_test.c
+++ b/lib/tst_test.c
@@ -992,26 +992,31 @@ static void sigint_handler(int sig LTP_ATTRIBUTE_UNUSED)
 	}
 }
 
-void tst_set_timeout(int timeout)
+float tst_timeout_mul(void)
 {
 	char *mul = getenv("LTP_TIMEOUT_MUL");
 
-	if (timeout == -1) {
-		tst_res(TINFO, "Timeout per run is disabled");
-		return;
-	}
-
-	results->timeout = timeout;
-
 	if (mul) {
 		float m = atof(mul);
 
 		if (m < 1)
 			tst_brk(TBROK, "Invalid timeout multiplier '%s'", mul);
 
-		results->timeout = results->timeout * m + 0.5;
+		return m;
+	}
+
+	return 1;
+}
+
+void tst_set_timeout(int timeout)
+{
+	if (timeout == -1) {
+		tst_res(TINFO, "Timeout per run is disabled");
+		return;
 	}
 
+	results->timeout = timeout * tst_timeout_mul() + 0.5;
+
 	tst_res(TINFO, "Timeout per run is %uh %02um %02us",
 		results->timeout/3600, (results->timeout%3600)/60,
 		results->timeout % 60);
-- 
2.18.0

[LTP] [PATCH 2/5] tst_timer: Create interface for using multiple timers

[Richard Palethorpe]

Encapsulate information about a stopwatch timer in a struct and provide
methods for operating on that timer. This allows test authors to create
multiple timers in parallel.

Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
---
 include/tst_timer.h | 51 +++++++++++++++++++++++++++++++++++++++++++++
 lib/tst_timer.c     | 21 +++++++++++++++++++
 2 files changed, 72 insertions(+)

diff --git a/include/tst_timer.h b/include/tst_timer.h
index 0fd7ed6cf..3e4f611b0 100644
--- a/include/tst_timer.h
+++ b/include/tst_timer.h
@@ -34,6 +34,26 @@
 #include <sys/time.h>
 #include <time.h>
 
+#ifdef CLOCK_MONOTONIC_RAW
+# define TST_CLOCK_DEFAULT CLOCK_MONOTONIC_RAW
+#else
+# define TST_CLOCK_DEFAULT CLOCK_MONOTONIC
+#endif
+
+/**
+ * Encapsulates a stopwatch timer.
+ *
+ * Useful when you need to use multiple timers in a single test.
+ */
+struct tst_timer {
+	/** The POSIX clock type  */
+	clockid_t clock_id;
+	/** How much time can pass before tst_timer_expired_st() returns true */
+	struct timespec limit;
+	/** Where to start measuring time from */
+	struct timespec start_time;
+};
+
 /*
  * Converts timespec to microseconds.
  */
@@ -92,6 +112,19 @@ static inline struct timeval tst_us_to_timeval(long long us)
 	return ret;
 }
 
+/*
+ * Converts seconds to struct timespec
+ */
+static inline struct timespec tst_sec_to_timespec(time_t seconds)
+{
+	struct timespec ret;
+
+	ret.tv_sec = seconds;
+	ret.tv_nsec = 0;
+
+	return ret;
+}
+
 /*
  * Converts ms to struct timespec
  */
@@ -244,6 +277,8 @@ static inline long long tst_timespec_abs_diff_ms(struct timespec t1,
  */
 void tst_timer_check(clockid_t clk_id);
 
+void tst_timer_init_st(struct tst_timer *tim);
+
 /*
  * Marks a start time for given clock type.
  *
@@ -251,6 +286,14 @@ void tst_timer_check(clockid_t clk_id);
  */
 void tst_timer_start(clockid_t clk_id);
 
+/**
+ * Sets the start time for timer tim.
+ *
+ * @relates tst_timer
+ * @param tim The timer to start
+ */
+void tst_timer_start_st(struct tst_timer *tim);
+
 /*
  * Returns true if timer started by tst_timer_start() has been running for
  * longer than ms seconds.
@@ -259,6 +302,14 @@ void tst_timer_start(clockid_t clk_id);
  */
 int tst_timer_expired_ms(long long ms);
 
+/**
+ * Returns true if timer tim has been running for longer than tst_timer::limit
+ *
+ * @relates tst_timer
+ * @param tim The timer to check
+ */
+int tst_timer_expired_st(struct tst_timer *tim);
+
 /*
  * Marks timer end time.
  */
diff --git a/lib/tst_timer.c b/lib/tst_timer.c
index dffaba0cb..bb73018c6 100644
--- a/lib/tst_timer.c
+++ b/lib/tst_timer.c
@@ -61,6 +61,16 @@ void tst_timer_start(clockid_t clk_id)
 		tst_res(TWARN | TERRNO, "tst_clock_gettime() failed");
 }
 
+void tst_timer_start_st(struct tst_timer *tim)
+{
+	if (!tim->clock_id)
+		tim->clock_id = TST_CLOCK_DEFAULT;
+	tst_timer_check(tim->clock_id);
+
+	if (tst_clock_gettime(tim->clock_id, &tim->start_time))
+		tst_res(TWARN | TERRNO, "tst_clock_gettime() failed");
+}
+
 int tst_timer_expired_ms(long long ms)
 {
 	struct timespec cur_time;
@@ -71,6 +81,17 @@ int tst_timer_expired_ms(long long ms)
 	return tst_timespec_diff_ms(cur_time, start_time) >= ms;
 }
 
+int tst_timer_expired_st(struct tst_timer *tim)
+{
+	struct timespec cur_time;
+
+	if (tst_clock_gettime(tim->clock_id, &cur_time))
+		tst_res(TWARN | TERRNO, "tst_clock_gettime() failed");
+
+	return tst_timespec_lt(tim->limit,
+			       tst_timespec_diff(cur_time, tim->start_time));
+}
+
 void tst_timer_stop(void)
 {
 	if (tst_clock_gettime(clock_id, &stop_time))
-- 
2.18.0

[LTP] [PATCH 2/5] tst_timer: Create interface for using multiple timers

[Cyril Hrubis]

Hi!
> +#ifdef CLOCK_MONOTONIC_RAW
> +# define TST_CLOCK_DEFAULT CLOCK_MONOTONIC_RAW
> +#else
> +# define TST_CLOCK_DEFAULT CLOCK_MONOTONIC
> +#endif

This should probably go in a separate patch.

> +/**
> + * Encapsulates a stopwatch timer.
> + *
> + * Useful when you need to use multiple timers in a single test.
> + */
> +struct tst_timer {
> +	/** The POSIX clock type  */
> +	clockid_t clock_id;
> +	/** How much time can pass before tst_timer_expired_st() returns true */
> +	struct timespec limit;
> +	/** Where to start measuring time from */
> +	struct timespec start_time;
> +};
> +
>  /*
>   * Converts timespec to microseconds.
>   */
> @@ -92,6 +112,19 @@ static inline struct timeval tst_us_to_timeval(long long us)
>  	return ret;
>  }
>  
> +/*
> + * Converts seconds to struct timespec
> + */
> +static inline struct timespec tst_sec_to_timespec(time_t seconds)
> +{
> +	struct timespec ret;
> +
> +	ret.tv_sec = seconds;
> +	ret.tv_nsec = 0;
> +
> +	return ret;
> +}

This should be probably part of the next patch.

>  /*
>   * Converts ms to struct timespec
>   */
> @@ -244,6 +277,8 @@ static inline long long tst_timespec_abs_diff_ms(struct timespec t1,
>   */
>  void tst_timer_check(clockid_t clk_id);
>  
> +void tst_timer_init_st(struct tst_timer *tim);

Can we pass the timeout to this function instead of expecting user to
fill in the structure?

>  *
>   * Marks a start time for given clock type.
>   *
> @@ -251,6 +286,14 @@ void tst_timer_check(clockid_t clk_id);
>   */
>  void tst_timer_start(clockid_t clk_id);
>  
> +/**
> + * Sets the start time for timer tim.
> + *
> + * @relates tst_timer
> + * @param tim The timer to start
> + */
> +void tst_timer_start_st(struct tst_timer *tim);
> +
>  /*
>   * Returns true if timer started by tst_timer_start() has been running for
>   * longer than ms seconds.
> @@ -259,6 +302,14 @@ void tst_timer_start(clockid_t clk_id);
>   */
>  int tst_timer_expired_ms(long long ms);
>  
> +/**
> + * Returns true if timer tim has been running for longer than tst_timer::limit
> + *
> + * @relates tst_timer
> + * @param tim The timer to check
> + */
> +int tst_timer_expired_st(struct tst_timer *tim);
> +
>  /*
>   * Marks timer end time.
>   */
> diff --git a/lib/tst_timer.c b/lib/tst_timer.c
> index dffaba0cb..bb73018c6 100644
> --- a/lib/tst_timer.c
> +++ b/lib/tst_timer.c
> @@ -61,6 +61,16 @@ void tst_timer_start(clockid_t clk_id)
>  		tst_res(TWARN | TERRNO, "tst_clock_gettime() failed");
>  }
>  
> +void tst_timer_start_st(struct tst_timer *tim)
> +{
> +	if (!tim->clock_id)
> +		tim->clock_id = TST_CLOCK_DEFAULT;
> +	tst_timer_check(tim->clock_id);
> +
> +	if (tst_clock_gettime(tim->clock_id, &tim->start_time))
> +		tst_res(TWARN | TERRNO, "tst_clock_gettime() failed");
> +}
> +
>  int tst_timer_expired_ms(long long ms)
>  {
>  	struct timespec cur_time;
> @@ -71,6 +81,17 @@ int tst_timer_expired_ms(long long ms)
>  	return tst_timespec_diff_ms(cur_time, start_time) >= ms;
>  }
>  
> +int tst_timer_expired_st(struct tst_timer *tim)
> +{
> +	struct timespec cur_time;
> +
> +	if (tst_clock_gettime(tim->clock_id, &cur_time))
> +		tst_res(TWARN | TERRNO, "tst_clock_gettime() failed");
> +
> +	return tst_timespec_lt(tim->limit,
> +			       tst_timespec_diff(cur_time, tim->start_time));
> +}

I guess that adding more tst_timer_expired_* variants will end up quite
confusing. Maybe we should just make one timer implementation where user
has to define the tst_timer structure in order to make things simpler.

And given that the timer is used only in a single test it should be easy
to change the API.

-- 
Cyril Hrubis
chrubis@suse.cz

[LTP] [PATCH 3/5] tst_timer: Add nano second conversions

[Richard Palethorpe]

Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
---
 include/tst_timer.h | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/include/tst_timer.h b/include/tst_timer.h
index 3e4f611b0..29d5dad40 100644
--- a/include/tst_timer.h
+++ b/include/tst_timer.h
@@ -54,6 +54,11 @@ struct tst_timer {
 	struct timespec start_time;
 };
 
+static inline long long tst_timespec_to_ns(struct timespec t)
+{
+	return t.tv_sec * 1000000000 + t.tv_nsec;
+}
+
 /*
  * Converts timespec to microseconds.
  */
@@ -199,6 +204,12 @@ static inline struct timespec tst_timespec_diff(struct timespec t1,
 	return res;
 }
 
+static inline long long tst_timespec_diff_ns(struct timespec t1,
+					     struct timespec t2)
+{
+	return t1.tv_nsec - t2.tv_nsec + 1000000000LL * (t1.tv_sec - t2.tv_sec);
+}
+
 static inline long long tst_timespec_diff_us(struct timespec t1,
                                              struct timespec t2)
 {
-- 
2.18.0

[LTP] [PATCH 4/5] fzsync: Simplify API with start/end race calls and limit exec time

[Richard Palethorpe]

Make it so the test writer simply has to mark the beginning and end of a race
in each thread. Previously they must choose where to call a delay and where to
call a timestamp function which is used to calculate the delay as well as the
update function.

Along with the new API a randomised delay has been introduced which helps hit
some race conditions (see doc comments).

Also use the tst_timer library to check how long the main test loop has been
running for and break the loop if it exceeds (60 * LTP_TIMEOUT_MUL)
seconds. This prevents an overall test timeout which is reported as a failure.

Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
---
 include/tst_fuzzy_sync.h | 634 +++++++++++++++++++++++++++++----------
 1 file changed, 468 insertions(+), 166 deletions(-)

diff --git a/include/tst_fuzzy_sync.h b/include/tst_fuzzy_sync.h
index bcc625e24..6ed509154 100644
--- a/include/tst_fuzzy_sync.h
+++ b/include/tst_fuzzy_sync.h
@@ -14,159 +14,302 @@
  * You should have received a copy of the GNU General Public License
  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  */
-/*
+/**
+ * @file tst_fuzzy_sync.h
  * Fuzzy Synchronisation - abreviated to fzsync
  *
- * This library is intended to help reproduce race conditions by providing two
- * thread synchronisation mechanisms. The first is a 'checkpoint' system where
- * each thread will wait indefinitely for the other to enter a checkpoint
- * before continuing. This is acheived by calling tst_fzsync_wait() and/or
- * tst_fzsync_wait_update() at the points you want to synchronise in each
- * thread. This is functionally very similar to using pthread_barrier_wait()
- * with two threads. However tst_fzsync_wait() can be inlined and is
- * guaranteed not to call sleep or futex.
- *
- * The second takes the form a of a delay which is calculated by measuring the
- * time difference between two points in each thread and comparing it to the
- * desired difference (default is zero). Using a delay allows you to
- * synchronise the threads at a point outside of your direct control
- * (e.g. inside the kernel) or just increase the accuracy for the first
- * mechanism. It is acheived using tst_fzsync_delay_{a,b}(),
- * tst_fzsync_time_{a,b}() and tst_fzsync[_wait_]update().
+ * This library is intended to help reproduce race conditions by synchronising
+ * two threads at a given place by marking the range a race may occur
+ * in. Because the exact place where any race occurs is whithin the kernel,
+ * and therefor impossible to mark accurately, the library may add randomised
+ * delays to either thread in order to help find the exact race timing.
+ *
+ * Currently only two way races are explicitly supported, that is races
+ * involving two threads or processes. We refer to the main test thread as
+ * thread A and the child thread as thread B.
+ *
+ * In each thread you need a simple while or for loop which you call the
+ * tst_fzsync_* functions in. In the simplest case thread A will look
+ * something like:
+ *
+ * tst_fzsync_pair_reset(&pair, run_thread_b);
+ * for (;;) {
+ * 	// Perform some setup which must happen before the race
+ * 	if (!tst_fzsync_start_race_a(&pair))
+ * 		break;
+ * 	// Do some dodgy syscall
+ * 	tst_fzsync_end_race_a(&pair);
+ * }
+ *
+ * Then in thread B (run_thread_b):
+ *
+ * while (tst_fzsync_start_race_b(&pair)) {
+ * 	// Do something which can race with the dodgy syscall in A
+ * 	if (!tst_fzsync_end_race_b(&pair))
+ * 		break;
+ * }
+ *
+ * The calls to tst_fzsync_start/end_race act as barriers which niether thread
+ * will cross until the other has reached it. You can add more barriers by
+ * using tst_fzsync_wait_a() and tst_fzsync_wait_b() in each thread.
+ *
+ * You may limit the loop in thread A to a certain number of loops or just
+ * allow fzsync to timeout. This is 60 seconds by default, but you can change
+ * it by setting tst_fzsync_pair::execution_time before calling
+ * tst_fzsync_pair_reset().
+ *
+ * Generally speaking whatever loop or time limit you choose it will be wrong
+ * on some subset of systems supported by Linux, but a best guess, based on
+ * whatever systems you have access to, should suffice.
+ *
+ * It is possible to use the library just for tst_fzsync_pair_wait() to get a
+ * basic spin wait. However if you are actually testing a race condition then
+ * it is recommended to use tst_fzsync_start_race_a/b even if the
+ * randomisation is not needed. It provides some semantic information which
+ * may be useful in the future.
  *
  * For a usage example see testcases/cve/cve-2016-7117.c or just run
  * 'git grep tst_fuzzy_sync.h'
+ *
+ * @sa tst_fzsync_pair
  */
 
 #include <sys/time.h>
 #include <time.h>
 #include <math.h>
+#include <stdlib.h>
 #include "tst_atomic.h"
+#include "tst_timer.h"
+#include "tst_safe_pthread.h"
 
-#ifndef CLOCK_MONOTONIC_RAW
-# define CLOCK_MONOTONIC_RAW CLOCK_MONOTONIC
-#endif
+/** Some statistics for a variable */
+struct tst_fzsync_stat {
+	float avg;
+	float avg_dev;
+	float dev_ratio;
+};
 
 /**
- * struct tst_fzsync_pair - the state of a two way synchronisation
- * @avg_diff: Internal; the average time difference over multiple iterations.
- * @avg_diff_trgt: The desired average time difference, defaults to 0.
- * @avg_alpha: The rate at which old diff samples are forgotten,
- *             defaults to 0.25.
- * @avg_dev: Internal; Absolute average deviation.
- * @a: Internal; The time at which call site A was last passed.
- * @b: Internal; The time at which call site B was last passed.
- * @delay: Internal; The size of the delay, positive to delay A,
- *         negative to delay B.
- * @delay_inc: The step size of a delay increment, defaults to 1.
- * @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 statistics.
- *            Defaults to 0x7FFFF and must also be one less than a power of 2.
- * @a_cntr: Internal; Atomic counter used by fzsync_pair_wait()
- * @b_cntr: Internal; Atomic counter used by fzsync_pair_wait()
- * @exit: Internal; Used by tst_fzsync_pair_exit() and 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
- * event in another process.
+ * The state of a two way synchronisation or race.
+ *
+ * This contains all the necessary state for approximately synchronising two
+ * sections of code in different threads.
  *
  * Internal fields should only be accessed by library functions.
  */
 struct tst_fzsync_pair {
-	float avg_diff;
-	float avg_diff_trgt;
+	/**
+	 * The rate at which old diff samples are forgotten
+	 *
+	 * Defaults to 0.25.
+	 */
 	float avg_alpha;
-	float avg_dev;
-	struct timespec a;
-	struct timespec b;
-	long delay;
-	long delay_inc;
-	int update_gap;
-	int info_gap;
+	/** Internal; Thread A start time */
+	struct timespec a_start;
+	/** Internal; Thread B start time */
+	struct timespec b_start;
+	/** Internal; Thread A end time */
+	struct timespec a_end;
+	/** Internal; Thread B end time */
+	struct timespec b_end;
+	/** Internal; Avg. difference between a_start and b_start */
+	struct tst_fzsync_stat diff_ss;
+	/** Internal; Avg. difference between a_start and a_end */
+	struct tst_fzsync_stat diff_sa;
+	/** Internal; Avg. difference between b_start and b_end */
+	struct tst_fzsync_stat diff_sb;
+	/** Internal; Avg. difference between a_end and b_end */
+	struct tst_fzsync_stat diff_ab;
+	/** Internal; Number of spins while waiting for the slower thread */
+	int spins;
+	struct tst_fzsync_stat spins_avg;
+	/**
+	 * Internal; Number of spins to use in the delay.
+	 *
+	 * A negative value delays thread A and a positive delays thread B.
+	 */
+	int delay;
+	/**
+	 *  Internal; The number of samples left or the sampling state.
+	 *
+	 *  A positive value is the number of remaining mandatory
+	 *  samples. Zero or a negative indicate ssome other state.
+	 */
+	int sampling;
+	/**
+	 * The Minimum number of statistical samples which must be collected.
+	 *
+	 * The minimum number of iterations which must be performed before a
+	 * random delay can be calculated. Defaults to 1024.
+	 */
+	int min_samples;
+	/**
+	 * The maximum allowed proportional average deviation.
+	 *
+	 * A value in the range (0, 1) which gives the maximum average
+	 * deviation which must be attained before random delays can be
+	 * calculated.
+	 *
+	 * It is a ratio of (average_deviation / total_time). The default is
+	 * 0.1, so this allows an average deviation of at most 10%.
+	 */
+	float max_dev_ratio;
+        /** Internal; Atomic counter used by fzsync_pair_wait() */
 	int a_cntr;
+        /** Internal; Atomic counter used by fzsync_pair_wait() */
 	int b_cntr;
+	/** Internal; Used by tst_fzsync_pair_exit() and fzsync_pair_wait() */
 	int exit;
+	/** Internal; Used to limit the execution time. */
+	struct tst_timer timer;
+	/**
+	 * The maximum time, in seconds, the test loop should be run.
+	 *
+	 * If the test runs for this amount of time without crashing or
+	 * reaching some iteration limit, the wait and race functions will
+	 * return zero signalling that the test loop should end.
+	 *
+	 * Note that this value is multiplied by LTP_TIMEOUT_MUL.
+	 *
+	 * Defaults to 60 seconds.
+	 */
+	int execution_time;
+	/** Internal; The second thread or NULL */
+	pthread_t thread_b;
 };
 
 /**
- * TST_FZSYNC_PAIR_INIT - Default values for struct tst_fzysnc_pair
+ * Default static values for struct tst_fzysnc_pair
  */
 #define TST_FZSYNC_PAIR_INIT {	\
 	.avg_alpha = 0.25,	\
-	.delay_inc = 1,	        \
-	.update_gap = 0xF,	\
-	.info_gap = 0x7FFFF     \
+	.min_samples = 1024,	\
+	.max_dev_ratio = 0.1,	\
+	.execution_time = 60	\
 }
 
 /**
- * tst_fzsync_pair_info - Print some synchronisation statistics
+ * Indicate that all threads should exit
+ *
+ * @relates tst_fzsync_pair
+ *
+ * Causes tst_fzsync_pair_wait(), and any functions which use it, to return 0.
  */
-static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair)
+static inline void tst_fzsync_pair_exit(struct tst_fzsync_pair *pair)
 {
-	tst_res(TINFO,
-		"avg_diff = %.0fns, avg_dev = %.0fns, delay = %05ld loops",
-		pair->avg_diff, pair->avg_dev, pair->delay);
+	tst_atomic_store(1, &pair->exit);
 }
 
 /**
- * tst_fzsync_delay_a - Perform spin delay for A, if needed
+ * Exit and join thread B if necessary.
+ *
+ * @relates tst_fzsync_pair
  *
- * Usually called just before the point you want to synchronise.
+ * Call this from your cleanup function.
  */
-static inline void tst_fzsync_delay_a(struct tst_fzsync_pair *pair)
+static void tst_fzsync_pair_cleanup(struct tst_fzsync_pair *pair)
 {
-	volatile long spin_delay = pair->delay;
-
-	while (spin_delay > 0)
-		spin_delay--;
+	if (pair->thread_b) {
+		tst_fzsync_pair_exit(pair);
+		SAFE_PTHREAD_JOIN(pair->thread_b, 0);
+		pair->thread_b = 0;
+	}
 }
 
 /**
- * tst_fzsync_delay_b - Perform spin delay for B, if needed
+ * Zero some stat fields
  *
- * Usually called just before the point you want to synchronise.
+ * @relates tst_fzsync_stat
  */
-static inline void tst_fzsync_delay_b(struct tst_fzsync_pair *pair)
+static void tst_init_stat(struct tst_fzsync_stat *s)
 {
-	volatile long spin_delay = pair->delay;
-
-	while (spin_delay < 0)
-		spin_delay++;
+	s->avg = 0;
+	s->avg_dev = 0;
 }
 
-static inline void tst_fzsync_time(struct timespec *t)
+/**
+ * Reset or initialise fzsync.
+ *
+ * @relates tst_fzsync_pair
+ * @param pair The state structure initialised with TST_FZSYNC_PAIR_INIT.
+ * @param run_b The function defining thread B or NULL.
+ *
+ * Call this from your main test function (thread A), just before entering the
+ * main loop. It will setup any values needed by fzsync and (re)start thread B
+ * using the function provided.
+ *
+ * If you need to use fork or clone to start the second thread/process then
+ * you can pass NULL to run_b and handle starting and stopping thread B
+ * yourself. You may need to place tst_fzsync_pair in some shared memory as
+ * well.
+ */
+static void tst_fzsync_pair_reset(struct tst_fzsync_pair *pair,
+				  void *(*run_b)(void *))
 {
-	clock_gettime(CLOCK_MONOTONIC_RAW, t);
+	tst_fzsync_pair_cleanup(pair);
+
+	tst_init_stat(&pair->diff_ss);
+	tst_init_stat(&pair->diff_sa);
+	tst_init_stat(&pair->diff_sb);
+	tst_init_stat(&pair->diff_ab);
+	tst_init_stat(&pair->spins_avg);
+	pair->delay = 0;
+	pair->sampling = pair->min_samples;
+
+	pair->timer.limit =
+		tst_sec_to_timespec(pair->execution_time * tst_timeout_mul());
+
+	pair->a_cntr = 0;
+	pair->b_cntr = 0;
+	tst_atomic_store(0, &pair->exit);
+	if (run_b)
+		SAFE_PTHREAD_CREATE(&pair->thread_b, 0, run_b, 0);
+
+	tst_timer_start_st(&pair->timer);
 }
 
 /**
- * tst_fzsync_time_a - Set A's time to now.
+ * Print stat
  *
- * Called at the point you want to synchronise.
+ * @relates tst_fzsync_stat
  */
-static inline void tst_fzsync_time_a(struct tst_fzsync_pair *pair)
+static inline void tst_fzsync_stat_info(struct tst_fzsync_stat stat,
+					char *unit, char *name)
 {
-	tst_fzsync_time(&pair->a);
+	tst_res(TINFO,
+		"%1$-17s: { avg = %3$5.0f%2$s, avg_dev = %4$5.0f%2$s, dev_ratio = %5$.2f }",
+		name, unit, stat.avg, stat.avg_dev, stat.dev_ratio);
 }
 
 /**
- * tst_fzsync_time_b - Set B's call time to now.
+ * Print some synchronisation statistics
  *
- * Called at the point you want to synchronise.
+ * @relates tst_fzsync_pair
  */
-static inline void tst_fzsync_time_b(struct tst_fzsync_pair *pair)
+static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair, int loop_index)
 {
-	tst_fzsync_time(&pair->b);
+	tst_res(TINFO, "loop = %d", loop_index);
+	tst_fzsync_stat_info(pair->diff_ss, "ns", "start_a - start_b");
+	tst_fzsync_stat_info(pair->diff_sa, "ns", "end_a - start_a");
+	tst_fzsync_stat_info(pair->diff_sb, "ns", "end_b - start_b");
+	tst_fzsync_stat_info(pair->diff_ab, "ns", "end_a - end_b");
+	tst_fzsync_stat_info(pair->spins_avg, "  ", "spins");
+}
+
+/** Wraps clock_gettime */
+static inline void tst_fzsync_time(struct timespec *t)
+{
+	clock_gettime(CLOCK_MONOTONIC_RAW, t);
 }
 
 /**
- * tst_exp_moving_avg - Exponential moving average
- * @alpha: The preference for recent samples over old ones.
- * @sample: The current sample
- * @prev_avg: The average of the all the previous samples
+ * Exponential moving average
+ *
+ * @param alpha The preference for recent samples over old ones.
+ * @param sample The current sample
+ * @param prev_avg The average of the all the previous samples
  *
- * Returns average including the current sample.
+ * @return The average including the current sample.
  */
 static inline float tst_exp_moving_avg(float alpha,
 					float sample,
@@ -176,63 +319,160 @@ static inline float tst_exp_moving_avg(float alpha,
 }
 
 /**
- * tst_fzsync_pair_update - Recalculate the delay
- * @loop_index: The i in "for(i = 0;..." or zero to ignore update_gap
- * @pair: The state necessary for calculating the delay
- *
- * This should be called at the end of each loop to update the average
- * measured time difference (between A and B) and update the delay. It is
- * assumed that A and B are less than a second apart.
- *
- * The values of update_gap, avg_alpha and delay_inc decide the speed at which
- * the algorithm approaches the optimum delay value and whether it is
- * stable. If your test is behaving strangely, it could be because this
- * algorithm is behaving chaotically and flip-flopping between large positve
- * and negative delay values. You can call tst_fzysync_pair_info every few
- * loops to check whether the average difference and delay values are stable.
+ * Update a stat with a new sample
+ *
+ * @relates tst_fzsync_stat
+ */
+static inline void tst_upd_stat(struct tst_fzsync_stat *s,
+				 float alpha,
+				 float sample)
+{
+	s->avg = tst_exp_moving_avg(alpha, sample, s->avg);
+	s->avg_dev = tst_exp_moving_avg(alpha, fabs(s->avg - sample), s->avg_dev);
+	s->dev_ratio = fabs(s->avg ? s->avg_dev / s->avg : 0);
+}
+
+/**
+ * Update a stat with a new diff sample
+ *
+ * @relates tst_fzsync_stat
+ */
+static inline void tst_upd_diff_stat(struct tst_fzsync_stat *s,
+				     float alpha,
+				     struct timespec t1,
+				     struct timespec t2)
+{
+	tst_upd_stat(s, alpha, tst_timespec_diff_ns(t1, t2));
+}
+
+/**
+ * Calculate various statistics and the delay
+ *
+ * This function helps create the fuzz in fuzzy sync. Imagine we have the
+ * following timelines in threads A and B:
+ *
+ *  start_race_a
+ *      ^                    end_race_a (a)
+ *      |                        ^
+ *      |                        |
+ *  - --+------------------------+-- - -
+ *      |        Syscall A       |                 Thread A
+ *  - --+------------------------+-- - -
+ *  - --+----------------+-------+-- - -
+ *      |   Syscall B    | spin  |                 Thread B
+ *  - --+----------------+-------+-- - -
+ *      |                |
+ *      ^                ^
+ *  start_race_b     end_race_b
+ *
+ * Here we have synchronised the calls to syscall A and B with start_race_{a,
+ * b} so that they happen at approximately the same time in threads A and
+ * B. If the race condition occurs during the entry code for these two
+ * functions then we will quickly hit it. If it occurs during the exit code of
+ * B and mid way through A, then we will quickly hit it.
+ *
+ * However if the exit paths of A and B need to be aligned and (end_race_a -
+ * end_race_b) is large relative to the variation in call times, the
+ * probability of hitting the race condition is close to zero. To solve this
+ * scenario (and others) a randomised delay is introduced before the syscalls
+ * in A and B. Given enough time the following should happen where the exit
+ * paths are now synchronised:
+ *
+ *  start_race_a
+ *      ^                    end_race_a (a)
+ *      |                        ^
+ *      |                        |
+ *  - --+------------------------+-- - -
+ *      |        Syscall A       |                 Thread A
+ *  - --+------------------------+-- - -
+ *  - --+-------+----------------+-- - -
+ *      | delay |   Syscall B    |                 Thread B
+ *  - --+-------+----------------+-- - -
+ *      |                        |
+ *      ^                        ^
+ *  start_race_b             end_race_b
+ *
+ * The delay is not introduced immediately and the delay range is only
+ * calculated once the average relative deviation has dropped below some
+ * percentage of the total time.
+ *
+ * The delay range is choosen so that any point in Syscall A could be
+ * synchronised with any point in Syscall B using a value from the
+ * range. Because the delay range may be too large for a linear search, we use
+ * an evenly distributed random function to pick a value from it.
+ *
+ * @relates tst_fzsync_pair
  */
 static void tst_fzsync_pair_update(int loop_index, struct tst_fzsync_pair *pair)
 {
-	long diff;
-	long inc = pair->delay_inc;
-	float target = pair->avg_diff_trgt;
-	float avg = pair->avg_diff;
-
-	diff = pair->a.tv_nsec - pair->b.tv_nsec
-		+ 1000000000 * (pair->a.tv_sec - pair->b.tv_sec);
-	avg = tst_exp_moving_avg(pair->avg_alpha, diff, avg);
-	pair->avg_dev = tst_exp_moving_avg(pair->avg_alpha,
-					   fabs(diff - avg),
-					   pair->avg_dev);
-
-	if (!(loop_index & pair->update_gap)) {
-		if (avg > target)
-			pair->delay -= inc;
-		else if (avg < target)
-			pair->delay += inc;
-	}
+	float alpha = pair->avg_alpha;
+	float per_spin_time, time_delay, dev_ratio;
+
+	dev_ratio = (pair->diff_sa.dev_ratio
+		     + pair->diff_sb.dev_ratio
+		     + pair->diff_ab.dev_ratio
+		     + pair->spins_avg.dev_ratio) / 4;
+
+	if (pair->sampling > 0 || dev_ratio > pair->max_dev_ratio) {
+		tst_upd_diff_stat(&pair->diff_ss, alpha,
+				  pair->a_start, pair->b_start);
+		tst_upd_diff_stat(&pair->diff_sa, alpha,
+				  pair->a_end, pair->a_start);
+		tst_upd_diff_stat(&pair->diff_sb, alpha,
+				  pair->b_end, pair->b_start);
+		tst_upd_diff_stat(&pair->diff_ab, alpha,
+				  pair->a_end, pair->b_end);
+		tst_upd_stat(&pair->spins_avg, alpha, pair->spins);
+		if (pair->sampling > 0 && --pair->sampling == 0) {
+			tst_res(TINFO,
+				"Minimum sampling period ended, deviation ratio = %.2f",
+				dev_ratio);
+			tst_fzsync_pair_info(pair, loop_index);
+		}
+	} else if (pair->diff_ab.avg >= 1 && pair->spins_avg.avg >= 1) {
+		per_spin_time = fabs(pair->diff_ab.avg) / pair->spins_avg.avg;
+		time_delay = drand48() * (pair->diff_sa.avg + pair->diff_sb.avg)
+			- pair->diff_sb.avg;
+		pair->delay = (int)(time_delay / per_spin_time);
 
-	if (!(loop_index & pair->info_gap))
-		tst_fzsync_pair_info(pair);
+		if (!pair->sampling) {
+			tst_res(TINFO,
+				"Reached deviation ratio %.2f (max %.2f), introducing randomness",
+				dev_ratio, pair->max_dev_ratio);
+			tst_res(TINFO, "Delay range is [-%d, %d]",
+				(int)(pair->diff_sb.avg / per_spin_time),
+				(int)(pair->diff_sa.avg / per_spin_time));
+			tst_fzsync_pair_info(pair, loop_index);
+			pair->sampling = -1;
+		}
+	} else if (!pair->sampling) {
+		tst_res(TWARN, "Can't calculate random delay");
+		pair->sampling = -1;
+	}
 
-	pair->avg_diff = avg;
+	pair->spins = 0;
 }
 
 /**
- * tst_fzsync_pair_wait - Wait for the other thread
- * @our_cntr: The counter for the thread we are on
- * @other_cntr: The counter for the thread we are synchronising with
+ * Wait for the other thread
+ *
+ * @relates tst_fzsync_pair
+ * @param our_cntr The counter for the thread we are on
+ * @param other_cntr The counter for the thread we are synchronising with
+ * @param spins A pointer to the spin counter or NULL
  *
- * Use this (through tst_fzsync_pair_wait_a() and tst_fzsync_pair_wait_b()) if
- * you need an additional synchronisation point in a thread or you do not want
- * to use the delay facility (not recommended). See
- * tst_fzsync_pair_wait_update().
+ * Used by tst_fzsync_pair_wait_a(), tst_fzsync_pair_wait_b(),
+ * tst_fzsync_start_race_a(), etc. If the calling thread is ahead of the other
+ * thread, then it will spin wait. Unlike pthread_barrier_wait it will never
+ * use futex and can count the number of spins spent waiting.
  *
- * Returns a non-zero value if the thread should continue otherwise the
+ * @return 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,
-				       int *our_cntr, int *other_cntr)
+				       int *our_cntr,
+				       int *other_cntr,
+				       int *spins)
 {
 	if (tst_atomic_inc(other_cntr) == INT_MAX) {
 		/*
@@ -244,8 +484,10 @@ static inline int tst_fzsync_pair_wait(struct tst_fzsync_pair *pair,
 		 */
 		while (tst_atomic_load(our_cntr) > 0
 		       && tst_atomic_load(our_cntr) < INT_MAX
-		       && !tst_atomic_load(&pair->exit))
-			;
+		       && !tst_atomic_load(&pair->exit)) {
+			if (spins)
+				(*spins)++;
+		}
 
 		tst_atomic_store(0, other_cntr);
 		/*
@@ -261,66 +503,126 @@ static inline int tst_fzsync_pair_wait(struct tst_fzsync_pair *pair,
 		 * of it and need to wait.
 		 */
 		while (tst_atomic_load(our_cntr) < tst_atomic_load(other_cntr)
-		       && !tst_atomic_load(&pair->exit))
-			;
+		       && !tst_atomic_load(&pair->exit)) {
+			if (spins)
+				(*spins)++;
+		}
 	}
 
-	/* Only exit if we have done the same amount of work as the other thread */
-	return !tst_atomic_load(&pair->exit) ||
-	  tst_atomic_load(other_cntr) <= tst_atomic_load(our_cntr);
+	return !tst_atomic_load(&pair->exit);
 }
 
+/**
+ * Wait in thread A
+ *
+ * @relates tst_fzsync_pair
+ * @sa tst_fzsync_pair_wait
+ */
 static inline int tst_fzsync_wait_a(struct tst_fzsync_pair *pair)
 {
-	return tst_fzsync_pair_wait(pair, &pair->a_cntr, &pair->b_cntr);
+	return tst_fzsync_pair_wait(pair, &pair->a_cntr, &pair->b_cntr, NULL);
 }
 
+/**
+ * Wait in thread B
+ *
+ * @relates tst_fzsync_pair
+ * @sa tst_fzsync_pair_wait
+ */
 static inline int tst_fzsync_wait_b(struct tst_fzsync_pair *pair)
 {
-	return tst_fzsync_pair_wait(pair, &pair->b_cntr, &pair->a_cntr);
+	return tst_fzsync_pair_wait(pair, &pair->b_cntr, &pair->a_cntr, NULL);
 }
 
 /**
- * tst_fzsync_pair_wait_update_{a,b} - Wait and then recalculate
+ * Marks the start of a race region in thread A
+ *
+ * @relates tst_fzsync_pair
  *
- * This allows you to have two long running threads which wait for each other
- * every iteration. So each thread will exit this function at approximately
- * the same time. It also updates the delay values in a thread safe manner.
+ * This should be placed just before performing whatever action can cause a
+ * race condition. Usually it is placed just before a syscall and
+ * tst_fzsync_end_race_a() is placed just afterward.
  *
- * 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. That
- * is, make sure that a call to tst_fzsync_pair_wait_update_a() in one thread
- * corresponds to a call to tst_fzsync_pair_wait_update_b() in the other.
+ * A corrosponding call to tst_fzsync_start_race_b() should be made in thread
+ * B.
  *
- * Returns a non-zero value if the calling thread should continue to loop. If
+ * @return 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.
+ *
+ * @sa tst_fzsync_pair_update
  */
-static inline int tst_fzsync_wait_update_a(struct tst_fzsync_pair *pair)
+static inline int tst_fzsync_start_race_a(struct tst_fzsync_pair *pair)
 {
 	static int loop_index;
+	volatile int delay;
+	int ret;
+
+	tst_fzsync_wait_a(pair);
 
-	tst_fzsync_pair_wait(pair, &pair->a_cntr, &pair->b_cntr);
-	loop_index++;
-	tst_fzsync_pair_update(loop_index, pair);
-	return tst_fzsync_pair_wait(pair, &pair->a_cntr, &pair->b_cntr);
+	if (tst_timer_expired_st(&pair->timer)) {
+		tst_res(TINFO,
+			"Exceeded fuzzy sync time limit, requesting exit");
+		tst_fzsync_pair_exit(pair);
+	} else {
+		loop_index++;
+		tst_fzsync_pair_update(loop_index, pair);
+	}
+
+	ret = tst_fzsync_wait_a(pair);
+	tst_fzsync_time(&pair->a_start);
+
+	delay = pair->delay;
+	while (delay < 0)
+		delay++;
+
+	return ret;
 }
 
-static inline int tst_fzsync_wait_update_b(struct tst_fzsync_pair *pair)
+/**
+ * Marks the end of a race region in thread A
+ *
+ * @relates tst_fzsync_pair
+ * @sa tst_fzsync_start_race_a
+ */
+static inline int tst_fzsync_end_race_a(struct tst_fzsync_pair *pair)
 {
-	tst_fzsync_pair_wait(pair, &pair->b_cntr, &pair->a_cntr);
-	return tst_fzsync_pair_wait(pair, &pair->b_cntr, &pair->a_cntr);
+	tst_fzsync_time(&pair->a_end);
+	return tst_fzsync_pair_wait(pair, &pair->a_cntr, &pair->b_cntr,
+				    &pair->spins);
 }
 
 /**
- * tst_fzsync_pair_exit - Signal that the other thread should exit
+ * Marks the start of a race region in thread B
  *
- * Causes tst_fzsync_pair_wait() and tst_fzsync_pair_wait_update() to return
- * 0.
+ * @relates tst_fzsync_pair
+ * @sa tst_fzsync_start_race_a
  */
-static inline void tst_fzsync_pair_exit(struct tst_fzsync_pair *pair)
+static inline int tst_fzsync_start_race_b(struct tst_fzsync_pair *pair)
 {
-	tst_atomic_store(1, &pair->exit);
+	int ret;
+	volatile int delay;
+
+	tst_fzsync_wait_b(pair);
+	ret = tst_fzsync_wait_b(pair);
+	tst_fzsync_time(&pair->b_start);
+
+	delay = pair->delay;
+	while (delay > 0)
+		delay--;
+
+	return ret;
+}
+
+/**
+ * Marks the end of a race region in thread B
+ *
+ * @relates tst_fzsync_pair
+ * @sa tst_fzsync_start_race_a
+ */
+static inline int tst_fzsync_end_race_b(struct tst_fzsync_pair *pair)
+{
+	tst_fzsync_time(&pair->b_end);
+	return tst_fzsync_pair_wait(pair, &pair->b_cntr, &pair->a_cntr,
+				    &pair->spins);
 }
-- 
2.18.0

[LTP] [PATCH 4/5] fzsync: Simplify API with start/end race calls and limit exec time

[Cyril Hrubis]

Hi!
> + * tst_fzsync_pair_reset(&pair, run_thread_b);
> + * for (;;) {
> + * 	// Perform some setup which must happen before the race
> + * 	if (!tst_fzsync_start_race_a(&pair))
> + * 		break;
> + * 	// Do some dodgy syscall
> + * 	tst_fzsync_end_race_a(&pair);
> + * }
> + *
> + * Then in thread B (run_thread_b):
> + *
> + * while (tst_fzsync_start_race_b(&pair)) {
> + * 	// Do something which can race with the dodgy syscall in A
> + * 	if (!tst_fzsync_end_race_b(&pair))
> + * 		break;
> + * }


Speaking of API maybe it would be cleaner to split the exit condition
from the markers so that we can do something as:


while (tst_fzsync_run(&pair)) {
	...
	tst_fzsync_begin_race_X(&pair);
	...
	tst_fzsync_end_race_X(&pair);
	...
}

Or is there a good reason why the loops are different between thread A
and thread B?

> + * The calls to tst_fzsync_start/end_race act as barriers which niether thread
> + * will cross until the other has reached it. You can add more barriers by
> + * using tst_fzsync_wait_a() and tst_fzsync_wait_b() in each thread.
> + *
> + * You may limit the loop in thread A to a certain number of loops or just
> + * allow fzsync to timeout. This is 60 seconds by default, but you can change
> + * it by setting tst_fzsync_pair::execution_time before calling
> + * tst_fzsync_pair_reset().
> + *
> + * Generally speaking whatever loop or time limit you choose it will be wrong
> + * on some subset of systems supported by Linux, but a best guess, based on
> + * whatever systems you have access to, should suffice.
> + *
> + * It is possible to use the library just for tst_fzsync_pair_wait() to get a
> + * basic spin wait. However if you are actually testing a race condition then
> + * it is recommended to use tst_fzsync_start_race_a/b even if the
> + * randomisation is not needed. It provides some semantic information which
> + * may be useful in the future.
>   *
>   * For a usage example see testcases/cve/cve-2016-7117.c or just run
>   * 'git grep tst_fuzzy_sync.h'
> + *
> + * @sa tst_fzsync_pair
>   */
>  
>  #include <sys/time.h>
>  #include <time.h>
>  #include <math.h>
> +#include <stdlib.h>
>  #include "tst_atomic.h"
> +#include "tst_timer.h"
> +#include "tst_safe_pthread.h"
>  
> -#ifndef CLOCK_MONOTONIC_RAW
> -# define CLOCK_MONOTONIC_RAW CLOCK_MONOTONIC
> -#endif
> +/** Some statistics for a variable */
> +struct tst_fzsync_stat {
> +	float avg;
> +	float avg_dev;
> +	float dev_ratio;
> +};
>  
>  /**
> - * struct tst_fzsync_pair - the state of a two way synchronisation
> - * @avg_diff: Internal; the average time difference over multiple iterations.
> - * @avg_diff_trgt: The desired average time difference, defaults to 0.
> - * @avg_alpha: The rate at which old diff samples are forgotten,
> - *             defaults to 0.25.
> - * @avg_dev: Internal; Absolute average deviation.
> - * @a: Internal; The time at which call site A was last passed.
> - * @b: Internal; The time at which call site B was last passed.
> - * @delay: Internal; The size of the delay, positive to delay A,
> - *         negative to delay B.
> - * @delay_inc: The step size of a delay increment, defaults to 1.
> - * @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 statistics.
> - *            Defaults to 0x7FFFF and must also be one less than a power of 2.
> - * @a_cntr: Internal; Atomic counter used by fzsync_pair_wait()
> - * @b_cntr: Internal; Atomic counter used by fzsync_pair_wait()
> - * @exit: Internal; Used by tst_fzsync_pair_exit() and 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
> - * event in another process.
> + * The state of a two way synchronisation or race.
> + *
> + * This contains all the necessary state for approximately synchronising two
> + * sections of code in different threads.
>   *
>   * Internal fields should only be accessed by library functions.
>   */
>  struct tst_fzsync_pair {
> -	float avg_diff;
> -	float avg_diff_trgt;
> +	/**
> +	 * The rate at which old diff samples are forgotten
> +	 *
> +	 * Defaults to 0.25.
> +	 */
>  	float avg_alpha;
> -	float avg_dev;
> -	struct timespec a;
> -	struct timespec b;
> -	long delay;
> -	long delay_inc;
> -	int update_gap;
> -	int info_gap;
> +	/** Internal; Thread A start time */
> +	struct timespec a_start;
> +	/** Internal; Thread B start time */
> +	struct timespec b_start;
> +	/** Internal; Thread A end time */
> +	struct timespec a_end;
> +	/** Internal; Thread B end time */
> +	struct timespec b_end;
> +	/** Internal; Avg. difference between a_start and b_start */
> +	struct tst_fzsync_stat diff_ss;
> +	/** Internal; Avg. difference between a_start and a_end */
> +	struct tst_fzsync_stat diff_sa;
> +	/** Internal; Avg. difference between b_start and b_end */
> +	struct tst_fzsync_stat diff_sb;
> +	/** Internal; Avg. difference between a_end and b_end */
> +	struct tst_fzsync_stat diff_ab;
> +	/** Internal; Number of spins while waiting for the slower thread */
> +	int spins;
> +	struct tst_fzsync_stat spins_avg;
> +	/**
> +	 * Internal; Number of spins to use in the delay.
> +	 *
> +	 * A negative value delays thread A and a positive delays thread B.
> +	 */
> +	int delay;
> +	/**
> +	 *  Internal; The number of samples left or the sampling state.
> +	 *
> +	 *  A positive value is the number of remaining mandatory
> +	 *  samples. Zero or a negative indicate ssome other state.
> +	 */
> +	int sampling;
> +	/**
> +	 * The Minimum number of statistical samples which must be collected.
> +	 *
> +	 * The minimum number of iterations which must be performed before a
> +	 * random delay can be calculated. Defaults to 1024.
> +	 */
> +	int min_samples;
> +	/**
> +	 * The maximum allowed proportional average deviation.
> +	 *
> +	 * A value in the range (0, 1) which gives the maximum average
> +	 * deviation which must be attained before random delays can be
> +	 * calculated.
> +	 *
> +	 * It is a ratio of (average_deviation / total_time). The default is
> +	 * 0.1, so this allows an average deviation of at most 10%.
> +	 */
> +	float max_dev_ratio;
> +        /** Internal; Atomic counter used by fzsync_pair_wait() */
>  	int a_cntr;
> +        /** Internal; Atomic counter used by fzsync_pair_wait() */
>  	int b_cntr;
> +	/** Internal; Used by tst_fzsync_pair_exit() and fzsync_pair_wait() */
>  	int exit;
> +	/** Internal; Used to limit the execution time. */
> +	struct tst_timer timer;
> +	/**
> +	 * The maximum time, in seconds, the test loop should be run.
> +	 *
> +	 * If the test runs for this amount of time without crashing or
> +	 * reaching some iteration limit, the wait and race functions will
> +	 * return zero signalling that the test loop should end.
> +	 *
> +	 * Note that this value is multiplied by LTP_TIMEOUT_MUL.
> +	 *
> +	 * Defaults to 60 seconds.
> +	 */
> +	int execution_time;
> +	/** Internal; The second thread or NULL */
> +	pthread_t thread_b;
>  };
>  
>  /**
> - * TST_FZSYNC_PAIR_INIT - Default values for struct tst_fzysnc_pair
> + * Default static values for struct tst_fzysnc_pair
>   */
>  #define TST_FZSYNC_PAIR_INIT {	\
>  	.avg_alpha = 0.25,	\
> -	.delay_inc = 1,	        \
> -	.update_gap = 0xF,	\
> -	.info_gap = 0x7FFFF     \
> +	.min_samples = 1024,	\
> +	.max_dev_ratio = 0.1,	\
> +	.execution_time = 60	\
>  }
>  
>  /**
> - * tst_fzsync_pair_info - Print some synchronisation statistics
> + * Indicate that all threads should exit
> + *
> + * @relates tst_fzsync_pair
> + *
> + * Causes tst_fzsync_pair_wait(), and any functions which use it, to return 0.
>   */
> -static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair)
> +static inline void tst_fzsync_pair_exit(struct tst_fzsync_pair *pair)
>  {
> -	tst_res(TINFO,
> -		"avg_diff = %.0fns, avg_dev = %.0fns, delay = %05ld loops",
> -		pair->avg_diff, pair->avg_dev, pair->delay);
> +	tst_atomic_store(1, &pair->exit);
>  }
>  
>  /**
> - * tst_fzsync_delay_a - Perform spin delay for A, if needed
> + * Exit and join thread B if necessary.
> + *
> + * @relates tst_fzsync_pair
>   *
> - * Usually called just before the point you want to synchronise.
> + * Call this from your cleanup function.
>   */
> -static inline void tst_fzsync_delay_a(struct tst_fzsync_pair *pair)
> +static void tst_fzsync_pair_cleanup(struct tst_fzsync_pair *pair)
>  {
> -	volatile long spin_delay = pair->delay;
> -
> -	while (spin_delay > 0)
> -		spin_delay--;
> +	if (pair->thread_b) {
> +		tst_fzsync_pair_exit(pair);
> +		SAFE_PTHREAD_JOIN(pair->thread_b, 0);
> +		pair->thread_b = 0;
> +	}
>  }
>  
>  /**
> - * tst_fzsync_delay_b - Perform spin delay for B, if needed
> + * Zero some stat fields
>   *
> - * Usually called just before the point you want to synchronise.
> + * @relates tst_fzsync_stat
>   */
> -static inline void tst_fzsync_delay_b(struct tst_fzsync_pair *pair)
> +static void tst_init_stat(struct tst_fzsync_stat *s)
>  {
> -	volatile long spin_delay = pair->delay;
> -
> -	while (spin_delay < 0)
> -		spin_delay++;
> +	s->avg = 0;
> +	s->avg_dev = 0;
>  }
>  
> -static inline void tst_fzsync_time(struct timespec *t)
> +/**
> + * Reset or initialise fzsync.
> + *
> + * @relates tst_fzsync_pair
> + * @param pair The state structure initialised with TST_FZSYNC_PAIR_INIT.
> + * @param run_b The function defining thread B or NULL.
> + *
> + * Call this from your main test function (thread A), just before entering the
> + * main loop. It will setup any values needed by fzsync and (re)start thread B
> + * using the function provided.
> + *
> + * If you need to use fork or clone to start the second thread/process then
> + * you can pass NULL to run_b and handle starting and stopping thread B
> + * yourself. You may need to place tst_fzsync_pair in some shared memory as
> + * well.
> + */
> +static void tst_fzsync_pair_reset(struct tst_fzsync_pair *pair,
> +				  void *(*run_b)(void *))
>  {
> -	clock_gettime(CLOCK_MONOTONIC_RAW, t);
> +	tst_fzsync_pair_cleanup(pair);
> +
> +	tst_init_stat(&pair->diff_ss);
> +	tst_init_stat(&pair->diff_sa);
> +	tst_init_stat(&pair->diff_sb);
> +	tst_init_stat(&pair->diff_ab);
> +	tst_init_stat(&pair->spins_avg);
> +	pair->delay = 0;

If yuo init the pair with TST_FZSYNC_PAIR_INIT these fields are already
zeroed...

> +	pair->sampling = pair->min_samples;
> +
> +	pair->timer.limit =
> +		tst_sec_to_timespec(pair->execution_time * tst_timeout_mul());

Hmm, why can't we have the limit in seconds? We do convert it to
timespec here, then convert it again in the timer library.

Also maybe it would be cleaner to have tst_timeout_scale() function that
would return the timeout multiplied, that way we would keep the timeout
logic in the tst_test library.

> +	pair->a_cntr = 0;
> +	pair->b_cntr = 0;
> +	tst_atomic_store(0, &pair->exit);

This as well has been initialized by 0 already.

> +	if (run_b)
> +		SAFE_PTHREAD_CREATE(&pair->thread_b, 0, run_b, 0);
> +
> +	tst_timer_start_st(&pair->timer);
>  }
>  
>  /**
> - * tst_fzsync_time_a - Set A's time to now.
> + * Print stat
>   *
> - * Called at the point you want to synchronise.
> + * @relates tst_fzsync_stat
>   */
> -static inline void tst_fzsync_time_a(struct tst_fzsync_pair *pair)
> +static inline void tst_fzsync_stat_info(struct tst_fzsync_stat stat,
> +					char *unit, char *name)
>  {
> -	tst_fzsync_time(&pair->a);
> +	tst_res(TINFO,
> +		"%1$-17s: { avg = %3$5.0f%2$s, avg_dev = %4$5.0f%2$s, dev_ratio = %5$.2f }",
> +		name, unit, stat.avg, stat.avg_dev, stat.dev_ratio);
>  }
>  
>  /**
> - * tst_fzsync_time_b - Set B's call time to now.
> + * Print some synchronisation statistics
>   *
> - * Called at the point you want to synchronise.
> + * @relates tst_fzsync_pair
>   */
> -static inline void tst_fzsync_time_b(struct tst_fzsync_pair *pair)
> +static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair, int loop_index)
>  {
> -	tst_fzsync_time(&pair->b);
> +	tst_res(TINFO, "loop = %d", loop_index);
> +	tst_fzsync_stat_info(pair->diff_ss, "ns", "start_a - start_b");
> +	tst_fzsync_stat_info(pair->diff_sa, "ns", "end_a - start_a");
> +	tst_fzsync_stat_info(pair->diff_sb, "ns", "end_b - start_b");
> +	tst_fzsync_stat_info(pair->diff_ab, "ns", "end_a - end_b");
> +	tst_fzsync_stat_info(pair->spins_avg, "  ", "spins");
> +}
> +
> +/** Wraps clock_gettime */
> +static inline void tst_fzsync_time(struct timespec *t)
> +{
> +	clock_gettime(CLOCK_MONOTONIC_RAW, t);
>  }
>  
>  /**
> - * tst_exp_moving_avg - Exponential moving average
> - * @alpha: The preference for recent samples over old ones.
> - * @sample: The current sample
> - * @prev_avg: The average of the all the previous samples
> + * Exponential moving average
> + *
> + * @param alpha The preference for recent samples over old ones.
> + * @param sample The current sample
> + * @param prev_avg The average of the all the previous samples
>   *
> - * Returns average including the current sample.
> + * @return The average including the current sample.
>   */
>  static inline float tst_exp_moving_avg(float alpha,
>  					float sample,
> @@ -176,63 +319,160 @@ static inline float tst_exp_moving_avg(float alpha,
>  }
>  
>  /**
> - * tst_fzsync_pair_update - Recalculate the delay
> - * @loop_index: The i in "for(i = 0;..." or zero to ignore update_gap
> - * @pair: The state necessary for calculating the delay
> - *
> - * This should be called at the end of each loop to update the average
> - * measured time difference (between A and B) and update the delay. It is
> - * assumed that A and B are less than a second apart.
> - *
> - * The values of update_gap, avg_alpha and delay_inc decide the speed at which
> - * the algorithm approaches the optimum delay value and whether it is
> - * stable. If your test is behaving strangely, it could be because this
> - * algorithm is behaving chaotically and flip-flopping between large positve
> - * and negative delay values. You can call tst_fzysync_pair_info every few
> - * loops to check whether the average difference and delay values are stable.
> + * Update a stat with a new sample
> + *
> + * @relates tst_fzsync_stat
> + */
> +static inline void tst_upd_stat(struct tst_fzsync_stat *s,
> +				 float alpha,
> +				 float sample)
> +{
> +	s->avg = tst_exp_moving_avg(alpha, sample, s->avg);
> +	s->avg_dev = tst_exp_moving_avg(alpha, fabs(s->avg - sample), s->avg_dev);
> +	s->dev_ratio = fabs(s->avg ? s->avg_dev / s->avg : 0);
> +}
> +
> +/**
> + * Update a stat with a new diff sample
> + *
> + * @relates tst_fzsync_stat
> + */
> +static inline void tst_upd_diff_stat(struct tst_fzsync_stat *s,
> +				     float alpha,
> +				     struct timespec t1,
> +				     struct timespec t2)
> +{
> +	tst_upd_stat(s, alpha, tst_timespec_diff_ns(t1, t2));
> +}
> +
> +/**
> + * Calculate various statistics and the delay
> + *
> + * This function helps create the fuzz in fuzzy sync. Imagine we have the
> + * following timelines in threads A and B:
> + *
> + *  start_race_a
> + *      ^                    end_race_a (a)
> + *      |                        ^
> + *      |                        |
> + *  - --+------------------------+-- - -
> + *      |        Syscall A       |                 Thread A
> + *  - --+------------------------+-- - -
> + *  - --+----------------+-------+-- - -
> + *      |   Syscall B    | spin  |                 Thread B
> + *  - --+----------------+-------+-- - -
> + *      |                |
> + *      ^                ^
> + *  start_race_b     end_race_b
> + *
> + * Here we have synchronised the calls to syscall A and B with start_race_{a,
> + * b} so that they happen at approximately the same time in threads A and
> + * B. If the race condition occurs during the entry code for these two
> + * functions then we will quickly hit it. If it occurs during the exit code of
> + * B and mid way through A, then we will quickly hit it.
> + *
> + * However if the exit paths of A and B need to be aligned and (end_race_a -
> + * end_race_b) is large relative to the variation in call times, the
> + * probability of hitting the race condition is close to zero. To solve this
> + * scenario (and others) a randomised delay is introduced before the syscalls
> + * in A and B. Given enough time the following should happen where the exit
> + * paths are now synchronised:
> + *
> + *  start_race_a
> + *      ^                    end_race_a (a)
> + *      |                        ^
> + *      |                        |
> + *  - --+------------------------+-- - -
> + *      |        Syscall A       |                 Thread A
> + *  - --+------------------------+-- - -
> + *  - --+-------+----------------+-- - -
> + *      | delay |   Syscall B    |                 Thread B
> + *  - --+-------+----------------+-- - -
> + *      |                        |
> + *      ^                        ^
> + *  start_race_b             end_race_b
> + *
> + * The delay is not introduced immediately and the delay range is only
> + * calculated once the average relative deviation has dropped below some
> + * percentage of the total time.
> + *
> + * The delay range is choosen so that any point in Syscall A could be
> + * synchronised with any point in Syscall B using a value from the
> + * range. Because the delay range may be too large for a linear search, we use
> + * an evenly distributed random function to pick a value from it.
> + *
> + * @relates tst_fzsync_pair
>   */
>  static void tst_fzsync_pair_update(int loop_index, struct tst_fzsync_pair *pair)
>  {
> -	long diff;
> -	long inc = pair->delay_inc;
> -	float target = pair->avg_diff_trgt;
> -	float avg = pair->avg_diff;
> -
> -	diff = pair->a.tv_nsec - pair->b.tv_nsec
> -		+ 1000000000 * (pair->a.tv_sec - pair->b.tv_sec);
> -	avg = tst_exp_moving_avg(pair->avg_alpha, diff, avg);
> -	pair->avg_dev = tst_exp_moving_avg(pair->avg_alpha,
> -					   fabs(diff - avg),
> -					   pair->avg_dev);
> -
> -	if (!(loop_index & pair->update_gap)) {
> -		if (avg > target)
> -			pair->delay -= inc;
> -		else if (avg < target)
> -			pair->delay += inc;
> -	}
> +	float alpha = pair->avg_alpha;
> +	float per_spin_time, time_delay, dev_ratio;
> +
> +	dev_ratio = (pair->diff_sa.dev_ratio
> +		     + pair->diff_sb.dev_ratio
> +		     + pair->diff_ab.dev_ratio
> +		     + pair->spins_avg.dev_ratio) / 4;
> +
> +	if (pair->sampling > 0 || dev_ratio > pair->max_dev_ratio) {
> +		tst_upd_diff_stat(&pair->diff_ss, alpha,
> +				  pair->a_start, pair->b_start);
> +		tst_upd_diff_stat(&pair->diff_sa, alpha,
> +				  pair->a_end, pair->a_start);
> +		tst_upd_diff_stat(&pair->diff_sb, alpha,
> +				  pair->b_end, pair->b_start);
> +		tst_upd_diff_stat(&pair->diff_ab, alpha,
> +				  pair->a_end, pair->b_end);
> +		tst_upd_stat(&pair->spins_avg, alpha, pair->spins);
> +		if (pair->sampling > 0 && --pair->sampling == 0) {
> +			tst_res(TINFO,
> +				"Minimum sampling period ended, deviation ratio = %.2f",
> +				dev_ratio);
> +			tst_fzsync_pair_info(pair, loop_index);
> +		}

So we do collect the statistic here to be used later, and we end either
when deviation is small enough or we reached minimal number of spins?

The max_dev_ratio is supposed to be set by the testcase then? I would
like to avoid having magic constants if possible...

> +	} else if (pair->diff_ab.avg >= 1 && pair->spins_avg.avg >= 1) {
> +		per_spin_time = fabs(pair->diff_ab.avg) / pair->spins_avg.avg;
> +		time_delay = drand48() * (pair->diff_sa.avg + pair->diff_sb.avg)
> +			- pair->diff_sb.avg;

Uff, it took me a while to figure this out but it seems correct to me,
given that we do

race_start_a:

	while (delay < 0)
		delay++;

race_start_b:

	while (delay > 0)
		delay--;

This means that the range for random delay we need is [-B, A]

So maybe you should explain the implementation a little bit in the
comment above. It's nice that it explains the general idea but maybe we
need hints to understand the implementation as well.

> +		pair->delay = (int)(time_delay / per_spin_time);

Also we can probably use return here to avoid the excessive else if branches.


Generally this looks great, maybe needs a little more explanations, but
it surely looks like a step into the right direction to me.

-- 
Cyril Hrubis
chrubis@suse.cz

[LTP] [PATCH 4/5] fzsync: Simplify API with start/end race calls and limit exec time

[Richard Palethorpe]

Hello,

Cyril Hrubis <chrubis@suse.cz> writes:

> Hi!
>> + * tst_fzsync_pair_reset(&pair, run_thread_b);
>> + * for (;;) {
>> + * 	// Perform some setup which must happen before the race
>> + * 	if (!tst_fzsync_start_race_a(&pair))
>> + * 		break;
>> + * 	// Do some dodgy syscall
>> + * 	tst_fzsync_end_race_a(&pair);
>> + * }
>> + *
>> + * Then in thread B (run_thread_b):
>> + *
>> + * while (tst_fzsync_start_race_b(&pair)) {
>> + * 	// Do something which can race with the dodgy syscall in A
>> + * 	if (!tst_fzsync_end_race_b(&pair))
>> + * 		break;
>> + * }
>
>
> Speaking of API maybe it would be cleaner to split the exit condition
> from the markers so that we can do something as:
>
>
> while (tst_fzsync_run(&pair)) {
> 	...
> 	tst_fzsync_begin_race_X(&pair);
> 	...
> 	tst_fzsync_end_race_X(&pair);
> 	...
> }
>
> Or is there a good reason why the loops are different between thread A
> and thread B?

I don't think so. Not anymore anyway. I will try using this idea, it
looks good.

We can hide the time and iteration limits in tst_fzsync_run.

>
>> + * The calls to tst_fzsync_start/end_race act as barriers which niether thread
>> + * will cross until the other has reached it. You can add more barriers by
>> + * using tst_fzsync_wait_a() and tst_fzsync_wait_b() in each thread.
>> + *
>> + * You may limit the loop in thread A to a certain number of loops or just
>> + * allow fzsync to timeout. This is 60 seconds by default, but you can change
>> + * it by setting tst_fzsync_pair::execution_time before calling
>> + * tst_fzsync_pair_reset().
>> + *
>> + * Generally speaking whatever loop or time limit you choose it will be wrong
>> + * on some subset of systems supported by Linux, but a best guess, based on
>> + * whatever systems you have access to, should suffice.
>> + *
>> + * It is possible to use the library just for tst_fzsync_pair_wait() to get a
>> + * basic spin wait. However if you are actually testing a race condition then
>> + * it is recommended to use tst_fzsync_start_race_a/b even if the
>> + * randomisation is not needed. It provides some semantic information which
>> + * may be useful in the future.
>>   *
>>   * For a usage example see testcases/cve/cve-2016-7117.c or just run
>>   * 'git grep tst_fuzzy_sync.h'
>> + *
>> + * @sa tst_fzsync_pair
>>   */
>>
>>  #include <sys/time.h>
>>  #include <time.h>
>>  #include <math.h>
>> +#include <stdlib.h>
>>  #include "tst_atomic.h"
>> +#include "tst_timer.h"
>> +#include "tst_safe_pthread.h"
>>
>> -#ifndef CLOCK_MONOTONIC_RAW
>> -# define CLOCK_MONOTONIC_RAW CLOCK_MONOTONIC
>> -#endif
>> +/** Some statistics for a variable */
>> +struct tst_fzsync_stat {
>> +	float avg;
>> +	float avg_dev;
>> +	float dev_ratio;
>> +};
>>
>>  /**
>> - * struct tst_fzsync_pair - the state of a two way synchronisation
>> - * @avg_diff: Internal; the average time difference over multiple iterations.
>> - * @avg_diff_trgt: The desired average time difference, defaults to 0.
>> - * @avg_alpha: The rate at which old diff samples are forgotten,
>> - *             defaults to 0.25.
>> - * @avg_dev: Internal; Absolute average deviation.
>> - * @a: Internal; The time at which call site A was last passed.
>> - * @b: Internal; The time at which call site B was last passed.
>> - * @delay: Internal; The size of the delay, positive to delay A,
>> - *         negative to delay B.
>> - * @delay_inc: The step size of a delay increment, defaults to 1.
>> - * @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 statistics.
>> - *            Defaults to 0x7FFFF and must also be one less than a power of 2.
>> - * @a_cntr: Internal; Atomic counter used by fzsync_pair_wait()
>> - * @b_cntr: Internal; Atomic counter used by fzsync_pair_wait()
>> - * @exit: Internal; Used by tst_fzsync_pair_exit() and 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
>> - * event in another process.
>> + * The state of a two way synchronisation or race.
>> + *
>> + * This contains all the necessary state for approximately synchronising two
>> + * sections of code in different threads.
>>   *
>>   * Internal fields should only be accessed by library functions.
>>   */
>>  struct tst_fzsync_pair {
>> -	float avg_diff;
>> -	float avg_diff_trgt;
>> +	/**
>> +	 * The rate at which old diff samples are forgotten
>> +	 *
>> +	 * Defaults to 0.25.
>> +	 */
>>  	float avg_alpha;
>> -	float avg_dev;
>> -	struct timespec a;
>> -	struct timespec b;
>> -	long delay;
>> -	long delay_inc;
>> -	int update_gap;
>> -	int info_gap;
>> +	/** Internal; Thread A start time */
>> +	struct timespec a_start;
>> +	/** Internal; Thread B start time */
>> +	struct timespec b_start;
>> +	/** Internal; Thread A end time */
>> +	struct timespec a_end;
>> +	/** Internal; Thread B end time */
>> +	struct timespec b_end;
>> +	/** Internal; Avg. difference between a_start and b_start */
>> +	struct tst_fzsync_stat diff_ss;
>> +	/** Internal; Avg. difference between a_start and a_end */
>> +	struct tst_fzsync_stat diff_sa;
>> +	/** Internal; Avg. difference between b_start and b_end */
>> +	struct tst_fzsync_stat diff_sb;
>> +	/** Internal; Avg. difference between a_end and b_end */
>> +	struct tst_fzsync_stat diff_ab;
>> +	/** Internal; Number of spins while waiting for the slower thread */
>> +	int spins;
>> +	struct tst_fzsync_stat spins_avg;
>> +	/**
>> +	 * Internal; Number of spins to use in the delay.
>> +	 *
>> +	 * A negative value delays thread A and a positive delays thread B.
>> +	 */
>> +	int delay;
>> +	/**
>> +	 *  Internal; The number of samples left or the sampling state.
>> +	 *
>> +	 *  A positive value is the number of remaining mandatory
>> +	 *  samples. Zero or a negative indicate ssome other state.
>> +	 */
>> +	int sampling;
>> +	/**
>> +	 * The Minimum number of statistical samples which must be collected.
>> +	 *
>> +	 * The minimum number of iterations which must be performed before a
>> +	 * random delay can be calculated. Defaults to 1024.
>> +	 */
>> +	int min_samples;
>> +	/**
>> +	 * The maximum allowed proportional average deviation.
>> +	 *
>> +	 * A value in the range (0, 1) which gives the maximum average
>> +	 * deviation which must be attained before random delays can be
>> +	 * calculated.
>> +	 *
>> +	 * It is a ratio of (average_deviation / total_time). The default is
>> +	 * 0.1, so this allows an average deviation of at most 10%.
>> +	 */
>> +	float max_dev_ratio;
>> +        /** Internal; Atomic counter used by fzsync_pair_wait() */
>>  	int a_cntr;
>> +        /** Internal; Atomic counter used by fzsync_pair_wait() */
>>  	int b_cntr;
>> +	/** Internal; Used by tst_fzsync_pair_exit() and fzsync_pair_wait() */
>>  	int exit;
>> +	/** Internal; Used to limit the execution time. */
>> +	struct tst_timer timer;
>> +	/**
>> +	 * The maximum time, in seconds, the test loop should be run.
>> +	 *
>> +	 * If the test runs for this amount of time without crashing or
>> +	 * reaching some iteration limit, the wait and race functions will
>> +	 * return zero signalling that the test loop should end.
>> +	 *
>> +	 * Note that this value is multiplied by LTP_TIMEOUT_MUL.
>> +	 *
>> +	 * Defaults to 60 seconds.
>> +	 */
>> +	int execution_time;
>> +	/** Internal; The second thread or NULL */
>> +	pthread_t thread_b;
>>  };
>>
>>  /**
>> - * TST_FZSYNC_PAIR_INIT - Default values for struct tst_fzysnc_pair
>> + * Default static values for struct tst_fzysnc_pair
>>   */
>>  #define TST_FZSYNC_PAIR_INIT {	\
>>  	.avg_alpha = 0.25,	\
>> -	.delay_inc = 1,	        \
>> -	.update_gap = 0xF,	\
>> -	.info_gap = 0x7FFFF     \
>> +	.min_samples = 1024,	\
>> +	.max_dev_ratio = 0.1,	\
>> +	.execution_time = 60	\
>>  }
>>
>>  /**
>> - * tst_fzsync_pair_info - Print some synchronisation statistics
>> + * Indicate that all threads should exit
>> + *
>> + * @relates tst_fzsync_pair
>> + *
>> + * Causes tst_fzsync_pair_wait(), and any functions which use it, to return 0.
>>   */
>> -static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair)
>> +static inline void tst_fzsync_pair_exit(struct tst_fzsync_pair *pair)
>>  {
>> -	tst_res(TINFO,
>> -		"avg_diff = %.0fns, avg_dev = %.0fns, delay = %05ld loops",
>> -		pair->avg_diff, pair->avg_dev, pair->delay);
>> +	tst_atomic_store(1, &pair->exit);
>>  }
>>
>>  /**
>> - * tst_fzsync_delay_a - Perform spin delay for A, if needed
>> + * Exit and join thread B if necessary.
>> + *
>> + * @relates tst_fzsync_pair
>>   *
>> - * Usually called just before the point you want to synchronise.
>> + * Call this from your cleanup function.
>>   */
>> -static inline void tst_fzsync_delay_a(struct tst_fzsync_pair *pair)
>> +static void tst_fzsync_pair_cleanup(struct tst_fzsync_pair *pair)
>>  {
>> -	volatile long spin_delay = pair->delay;
>> -
>> -	while (spin_delay > 0)
>> -		spin_delay--;
>> +	if (pair->thread_b) {
>> +		tst_fzsync_pair_exit(pair);
>> +		SAFE_PTHREAD_JOIN(pair->thread_b, 0);
>> +		pair->thread_b = 0;
>> +	}
>>  }
>>
>>  /**
>> - * tst_fzsync_delay_b - Perform spin delay for B, if needed
>> + * Zero some stat fields
>>   *
>> - * Usually called just before the point you want to synchronise.
>> + * @relates tst_fzsync_stat
>>   */
>> -static inline void tst_fzsync_delay_b(struct tst_fzsync_pair *pair)
>> +static void tst_init_stat(struct tst_fzsync_stat *s)
>>  {
>> -	volatile long spin_delay = pair->delay;
>> -
>> -	while (spin_delay < 0)
>> -		spin_delay++;
>> +	s->avg = 0;
>> +	s->avg_dev = 0;
>>  }
>>
>> -static inline void tst_fzsync_time(struct timespec *t)
>> +/**
>> + * Reset or initialise fzsync.
>> + *
>> + * @relates tst_fzsync_pair
>> + * @param pair The state structure initialised with TST_FZSYNC_PAIR_INIT.
>> + * @param run_b The function defining thread B or NULL.
>> + *
>> + * Call this from your main test function (thread A), just before entering the
>> + * main loop. It will setup any values needed by fzsync and (re)start thread B
>> + * using the function provided.
>> + *
>> + * If you need to use fork or clone to start the second thread/process then
>> + * you can pass NULL to run_b and handle starting and stopping thread B
>> + * yourself. You may need to place tst_fzsync_pair in some shared memory as
>> + * well.
>> + */
>> +static void tst_fzsync_pair_reset(struct tst_fzsync_pair *pair,
>> +				  void *(*run_b)(void *))
>>  {
>> -	clock_gettime(CLOCK_MONOTONIC_RAW, t);
>> +	tst_fzsync_pair_cleanup(pair);
>> +
>> +	tst_init_stat(&pair->diff_ss);
>> +	tst_init_stat(&pair->diff_sa);
>> +	tst_init_stat(&pair->diff_sb);
>> +	tst_init_stat(&pair->diff_ab);
>> +	tst_init_stat(&pair->spins_avg);
>> +	pair->delay = 0;
>
> If yuo init the pair with TST_FZSYNC_PAIR_INIT these fields are already
> zeroed...

Not if the user uses the -i argument.

>
>> +	pair->sampling = pair->min_samples;
>> +
>> +	pair->timer.limit =
>> +		tst_sec_to_timespec(pair->execution_time * tst_timeout_mul());
>
> Hmm, why can't we have the limit in seconds? We do convert it to
> timespec here, then convert it again in the timer library.

I'm using the new timer API I invented which just uses timespec
structs.

>
> Also maybe it would be cleaner to have tst_timeout_scale() function that
> would return the timeout multiplied, that way we would keep the timeout
> logic in the tst_test library.

Yeah.

>
>> +	pair->a_cntr = 0;
>> +	pair->b_cntr = 0;
>> +	tst_atomic_store(0, &pair->exit);
>
> This as well has been initialized by 0 already.
>
>> +	if (run_b)
>> +		SAFE_PTHREAD_CREATE(&pair->thread_b, 0, run_b, 0);
>> +
>> +	tst_timer_start_st(&pair->timer);
>>  }
>>
>>  /**
>> - * tst_fzsync_time_a - Set A's time to now.
>> + * Print stat
>>   *
>> - * Called at the point you want to synchronise.
>> + * @relates tst_fzsync_stat
>>   */
>> -static inline void tst_fzsync_time_a(struct tst_fzsync_pair *pair)
>> +static inline void tst_fzsync_stat_info(struct tst_fzsync_stat stat,
>> +					char *unit, char *name)
>>  {
>> -	tst_fzsync_time(&pair->a);
>> +	tst_res(TINFO,
>> +		"%1$-17s: { avg = %3$5.0f%2$s, avg_dev = %4$5.0f%2$s, dev_ratio = %5$.2f }",
>> +		name, unit, stat.avg, stat.avg_dev, stat.dev_ratio);
>>  }
>>
>>  /**
>> - * tst_fzsync_time_b - Set B's call time to now.
>> + * Print some synchronisation statistics
>>   *
>> - * Called at the point you want to synchronise.
>> + * @relates tst_fzsync_pair
>>   */
>> -static inline void tst_fzsync_time_b(struct tst_fzsync_pair *pair)
>> +static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair, int loop_index)
>>  {
>> -	tst_fzsync_time(&pair->b);
>> +	tst_res(TINFO, "loop = %d", loop_index);
>> +	tst_fzsync_stat_info(pair->diff_ss, "ns", "start_a - start_b");
>> +	tst_fzsync_stat_info(pair->diff_sa, "ns", "end_a - start_a");
>> +	tst_fzsync_stat_info(pair->diff_sb, "ns", "end_b - start_b");
>> +	tst_fzsync_stat_info(pair->diff_ab, "ns", "end_a - end_b");
>> +	tst_fzsync_stat_info(pair->spins_avg, "  ", "spins");
>> +}
>> +
>> +/** Wraps clock_gettime */
>> +static inline void tst_fzsync_time(struct timespec *t)
>> +{
>> +	clock_gettime(CLOCK_MONOTONIC_RAW, t);
>>  }
>>
>>  /**
>> - * tst_exp_moving_avg - Exponential moving average
>> - * @alpha: The preference for recent samples over old ones.
>> - * @sample: The current sample
>> - * @prev_avg: The average of the all the previous samples
>> + * Exponential moving average
>> + *
>> + * @param alpha The preference for recent samples over old ones.
>> + * @param sample The current sample
>> + * @param prev_avg The average of the all the previous samples
>>   *
>> - * Returns average including the current sample.
>> + * @return The average including the current sample.
>>   */
>>  static inline float tst_exp_moving_avg(float alpha,
>>  					float sample,
>> @@ -176,63 +319,160 @@ static inline float tst_exp_moving_avg(float alpha,
>>  }
>>
>>  /**
>> - * tst_fzsync_pair_update - Recalculate the delay
>> - * @loop_index: The i in "for(i = 0;..." or zero to ignore update_gap
>> - * @pair: The state necessary for calculating the delay
>> - *
>> - * This should be called at the end of each loop to update the average
>> - * measured time difference (between A and B) and update the delay. It is
>> - * assumed that A and B are less than a second apart.
>> - *
>> - * The values of update_gap, avg_alpha and delay_inc decide the speed at which
>> - * the algorithm approaches the optimum delay value and whether it is
>> - * stable. If your test is behaving strangely, it could be because this
>> - * algorithm is behaving chaotically and flip-flopping between large positve
>> - * and negative delay values. You can call tst_fzysync_pair_info every few
>> - * loops to check whether the average difference and delay values are stable.
>> + * Update a stat with a new sample
>> + *
>> + * @relates tst_fzsync_stat
>> + */
>> +static inline void tst_upd_stat(struct tst_fzsync_stat *s,
>> +				 float alpha,
>> +				 float sample)
>> +{
>> +	s->avg = tst_exp_moving_avg(alpha, sample, s->avg);
>> +	s->avg_dev = tst_exp_moving_avg(alpha, fabs(s->avg - sample), s->avg_dev);
>> +	s->dev_ratio = fabs(s->avg ? s->avg_dev / s->avg : 0);
>> +}
>> +
>> +/**
>> + * Update a stat with a new diff sample
>> + *
>> + * @relates tst_fzsync_stat
>> + */
>> +static inline void tst_upd_diff_stat(struct tst_fzsync_stat *s,
>> +				     float alpha,
>> +				     struct timespec t1,
>> +				     struct timespec t2)
>> +{
>> +	tst_upd_stat(s, alpha, tst_timespec_diff_ns(t1, t2));
>> +}
>> +
>> +/**
>> + * Calculate various statistics and the delay
>> + *
>> + * This function helps create the fuzz in fuzzy sync. Imagine we have the
>> + * following timelines in threads A and B:
>> + *
>> + *  start_race_a
>> + *      ^                    end_race_a (a)
>> + *      |                        ^
>> + *      |                        |
>> + *  - --+------------------------+-- - -
>> + *      |        Syscall A       |                 Thread A
>> + *  - --+------------------------+-- - -
>> + *  - --+----------------+-------+-- - -
>> + *      |   Syscall B    | spin  |                 Thread B
>> + *  - --+----------------+-------+-- - -
>> + *      |                |
>> + *      ^                ^
>> + *  start_race_b     end_race_b
>> + *
>> + * Here we have synchronised the calls to syscall A and B with start_race_{a,
>> + * b} so that they happen at approximately the same time in threads A and
>> + * B. If the race condition occurs during the entry code for these two
>> + * functions then we will quickly hit it. If it occurs during the exit code of
>> + * B and mid way through A, then we will quickly hit it.
>> + *
>> + * However if the exit paths of A and B need to be aligned and (end_race_a -
>> + * end_race_b) is large relative to the variation in call times, the
>> + * probability of hitting the race condition is close to zero. To solve this
>> + * scenario (and others) a randomised delay is introduced before the syscalls
>> + * in A and B. Given enough time the following should happen where the exit
>> + * paths are now synchronised:
>> + *
>> + *  start_race_a
>> + *      ^                    end_race_a (a)
>> + *      |                        ^
>> + *      |                        |
>> + *  - --+------------------------+-- - -
>> + *      |        Syscall A       |                 Thread A
>> + *  - --+------------------------+-- - -
>> + *  - --+-------+----------------+-- - -
>> + *      | delay |   Syscall B    |                 Thread B
>> + *  - --+-------+----------------+-- - -
>> + *      |                        |
>> + *      ^                        ^
>> + *  start_race_b             end_race_b
>> + *
>> + * The delay is not introduced immediately and the delay range is only
>> + * calculated once the average relative deviation has dropped below some
>> + * percentage of the total time.
>> + *
>> + * The delay range is choosen so that any point in Syscall A could be
>> + * synchronised with any point in Syscall B using a value from the
>> + * range. Because the delay range may be too large for a linear search, we use
>> + * an evenly distributed random function to pick a value from it.
>> + *
>> + * @relates tst_fzsync_pair
>>   */
>>  static void tst_fzsync_pair_update(int loop_index, struct tst_fzsync_pair *pair)
>>  {
>> -	long diff;
>> -	long inc = pair->delay_inc;
>> -	float target = pair->avg_diff_trgt;
>> -	float avg = pair->avg_diff;
>> -
>> -	diff = pair->a.tv_nsec - pair->b.tv_nsec
>> -		+ 1000000000 * (pair->a.tv_sec - pair->b.tv_sec);
>> -	avg = tst_exp_moving_avg(pair->avg_alpha, diff, avg);
>> -	pair->avg_dev = tst_exp_moving_avg(pair->avg_alpha,
>> -					   fabs(diff - avg),
>> -					   pair->avg_dev);
>> -
>> -	if (!(loop_index & pair->update_gap)) {
>> -		if (avg > target)
>> -			pair->delay -= inc;
>> -		else if (avg < target)
>> -			pair->delay += inc;
>> -	}
>> +	float alpha = pair->avg_alpha;
>> +	float per_spin_time, time_delay, dev_ratio;
>> +
>> +	dev_ratio = (pair->diff_sa.dev_ratio
>> +		     + pair->diff_sb.dev_ratio
>> +		     + pair->diff_ab.dev_ratio
>> +		     + pair->spins_avg.dev_ratio) / 4;
>> +
>> +	if (pair->sampling > 0 || dev_ratio > pair->max_dev_ratio) {
>> +		tst_upd_diff_stat(&pair->diff_ss, alpha,
>> +				  pair->a_start, pair->b_start);
>> +		tst_upd_diff_stat(&pair->diff_sa, alpha,
>> +				  pair->a_end, pair->a_start);
>> +		tst_upd_diff_stat(&pair->diff_sb, alpha,
>> +				  pair->b_end, pair->b_start);
>> +		tst_upd_diff_stat(&pair->diff_ab, alpha,
>> +				  pair->a_end, pair->b_end);
>> +		tst_upd_stat(&pair->spins_avg, alpha, pair->spins);
>> +		if (pair->sampling > 0 && --pair->sampling == 0) {
>> +			tst_res(TINFO,
>> +				"Minimum sampling period ended, deviation ratio = %.2f",
>> +				dev_ratio);
>> +			tst_fzsync_pair_info(pair, loop_index);
>> +		}
>
> So we do collect the statistic here to be used later, and we end either
> when deviation is small enough or we reached minimal number of spins?

The sampling period ends when both the minimum number of spins have been
reached and the average deviation is small.

>
> The max_dev_ratio is supposed to be set by the testcase then? I would
> like to avoid having magic constants if possible...

Well, it can be, but I think most, if not all, tests can (and should)
use the default deviation ratio. We may need to change the default,
maybe on a per platform basis, but we need more data.

>
>> +	} else if (pair->diff_ab.avg >= 1 && pair->spins_avg.avg >= 1) {
>> +		per_spin_time = fabs(pair->diff_ab.avg) / pair->spins_avg.avg;
>> +		time_delay = drand48() * (pair->diff_sa.avg + pair->diff_sb.avg)
>> +			- pair->diff_sb.avg;
>
> Uff, it took me a while to figure this out but it seems correct to me,
> given that we do
>
> race_start_a:
>
> 	while (delay < 0)
> 		delay++;
>
> race_start_b:
>
> 	while (delay > 0)
> 		delay--;
>
> This means that the range for random delay we need is [-B, A]
>
> So maybe you should explain the implementation a little bit in the
> comment above. It's nice that it explains the general idea but maybe we
> need hints to understand the implementation as well.

Yeah sorry, I actually figured it out in mathematical notation on paper
and should have tried to clean it up and rewrite it in the doc
comment. Or possibly I should write it inline like I did for the wait
function.

>
>> +		pair->delay = (int)(time_delay / per_spin_time);
>
> Also we can probably use return here to avoid the excessive else if branches.
>
>
> Generally this looks great, maybe needs a little more explanations, but
> it surely looks like a step into the right direction to me.

Thanks!

--
Thank you,
Richard.

[LTP] [PATCH 4/5] fzsync: Simplify API with start/end race calls and limit exec time

[Cyril Hrubis]

Hi!
> > If yuo init the pair with TST_FZSYNC_PAIR_INIT these fields are already
> > zeroed...
> 
> Not if the user uses the -i argument.

Hmm, then we should probably drop the static initialization. We would
have to have way to set some parameters to non-default values, but I
guess that we can do that after we called the init function. Something
as:

	tst_fzsync_init(&pair);
	tst_fzsync_set_foo(&par, val);

Where tst_fzsync_set_foo() is an static inline function.

> >> +	pair->sampling = pair->min_samples;
> >> +
> >> +	pair->timer.limit =
> >> +		tst_sec_to_timespec(pair->execution_time * tst_timeout_mul());
> >
> > Hmm, why can't we have the limit in seconds? We do convert it to
> > timespec here, then convert it again in the timer library.
> 
> I'm using the new timer API I invented which just uses timespec
> structs.

Maybe we should keep the timer API as it is and reuse the API Jan is
recently working on, i.e. the tst_timeout_remaining() function.

> > So we do collect the statistic here to be used later, and we end either
> > when deviation is small enough or we reached minimal number of spins?
> 
> The sampling period ends when both the minimum number of spins have been
> reached and the average deviation is small.

Right, my bad.

> > The max_dev_ratio is supposed to be set by the testcase then? I would
> > like to avoid having magic constants if possible...
> 
> Well, it can be, but I think most, if not all, tests can (and should)
> use the default deviation ratio. We may need to change the default,
> maybe on a per platform basis, but we need more data.

That is the reason why I would like to have things auto-tuneable, it's
not like we can test the library on every hardware/distro combinations
out there. But let's see.

> >> +	} else if (pair->diff_ab.avg >= 1 && pair->spins_avg.avg >= 1) {
> >> +		per_spin_time = fabs(pair->diff_ab.avg) / pair->spins_avg.avg;
> >> +		time_delay = drand48() * (pair->diff_sa.avg + pair->diff_sb.avg)
> >> +			- pair->diff_sb.avg;
> >
> > Uff, it took me a while to figure this out but it seems correct to me,
> > given that we do
> >
> > race_start_a:
> >
> > 	while (delay < 0)
> > 		delay++;
> >
> > race_start_b:
> >
> > 	while (delay > 0)
> > 		delay--;
> >
> > This means that the range for random delay we need is [-B, A]
> >
> > So maybe you should explain the implementation a little bit in the
> > comment above. It's nice that it explains the general idea but maybe we
> > need hints to understand the implementation as well.
> 
> Yeah sorry, I actually figured it out in mathematical notation on paper
> and should have tried to clean it up and rewrite it in the doc
> comment. Or possibly I should write it inline like I did for the wait
> function.

I would have liked a top level comment about the implementation better.

Maybe we need two paragraphs in the top level comment, one about the
general idea and one with hints about the implementation.

> >> +		pair->delay = (int)(time_delay / per_spin_time);
> >
> > Also we can probably use return here to avoid the excessive else if branches.
> >
> >
> > Generally this looks great, maybe needs a little more explanations, but
> > it surely looks like a step into the right direction to me.
> 
> Thanks!
> 
> --
> Thank you,
> Richard.

-- 
Cyril Hrubis
chrubis@suse.cz

[LTP] [PATCH 4/5] fzsync: Simplify API with start/end race calls and limit exec time

[Richard Palethorpe]

Hello,

Cyril Hrubis <chrubis@suse.cz> writes:

> Hi!
>> > If yuo init the pair with TST_FZSYNC_PAIR_INIT these fields are already
>> > zeroed...
>>
>> Not if the user uses the -i argument.
>
> Hmm, then we should probably drop the static initialization. We would
> have to have way to set some parameters to non-default values, but I
> guess that we can do that after we called the init function. Something
> as:
>
> 	tst_fzsync_init(&pair);
> 	tst_fzsync_set_foo(&par, val);
>
> Where tst_fzsync_set_foo() is an static inline function.
>

Yeah, thinking about it we should not do the static initialisation
statically anyway incase the test writer needs to dynamically allocate
the memory where the struct is stored. Although they could use memcpy,
but it seems a little bit messy.

--
Thank you,
Richard.

[LTP] [PATCH 4/5] fzsync: Simplify API with start/end race calls and limit exec time

[Li Wang]

Hi Richard,

I have gone though this new fzsync API, the whole picture looks good but
with a tiny issue maybe be needs adjustment.

1. Moving the expired time detection to tst_fzsync_end_race_a() function,
because it maybe better if exit the loop after finishing a complete race
testing, and it also makes the _start_race_a() more aligned to
_start_race_b() I guess.

2. Do fzsync_pair_cleanup when the expired time occuring. This is for JOIN
the threads which might have collision(I know it has very small probability
but in case of that)with new threads if with -i parameter. And re-org the
tst_fzsync_clenaup() to make sure to be widely used.

So, for suggestion 1&2, the related function will be changed as:

static void tst_fzsync_pair_cleanup(struct tst_fzsync_pair *pair)
{
tst_fzsync_pair_exit(pair);

if (pair->thread_b) {
SAFE_PTHREAD_JOIN(pair->thread_b, 0);
pair->thread_b = 0;
}
}

static inline int tst_fzsync_end_race_a(struct tst_fzsync_pair *pair)
{
if (tst_timer_expired_st(&pair->timer)) {
tst_res(TINFO,
"Exceeded fuzzy sync time limit, requesting exit");
tst_fzsync_pair_cleanup(pair);
}

tst_fzsync_time(&pair->a_end);
return tst_fzsync_pair_wait(pair, &pair->a_cntr, &pair->b_cntr,
    &pair->spins);
}

3. I tend to agree with Cyril's opinion, to take use of
the tst_timeout_remaining() function which will be introduced by Jan's
patch for move_pages12, then fzsync can drop the expired time detection by
with new timer function involved.

4. The usage of fzsync is not very neat. For example in some places you
put tst_fzsync_start_race_b(&pair) into curves but others not, I know that
because of different situation needs variant race condition area,
but if we can have a uniform format to satisfy that, it would be more happy
to users.

5. I do not fully understand about the 'tst_fzsync_stat' part, if you can
give more explanation in code comments, that will be much appreciated.

Btw, I have tried this new API with my rhel7.5 x86_64 system, it woks fine
with or without -i parameter, and it also does correctly when the
execution_time expired. These comments are just FYI. Thanks!

-- 
Regards,
Li Wang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linux.it/pipermail/ltp/attachments/20180830/b55a3371/attachment.html>

[LTP] [PATCH 4/5] fzsync: Simplify API with start/end race calls and limit exec time

[Richard Palethorpe]

Hello,

Li Wang <liwang@redhat.com> writes:

> Hi Richard,
>
> I have gone though this new fzsync API, the whole picture looks good but
> with a tiny issue maybe be needs adjustment.
>
> 1. Moving the expired time detection to tst_fzsync_end_race_a() function,
> because it maybe better if exit the loop after finishing a complete race
> testing, and it also makes the _start_race_a() more aligned to
> _start_race_b() I guess.
>
> 2. Do fzsync_pair_cleanup when the expired time occuring. This is for JOIN
> the threads which might have collision(I know it has very small probability
> but in case of that)with new threads if with -i parameter. And re-org the
> tst_fzsync_clenaup() to make sure to be widely used.
>
> So, for suggestion 1&2, the related function will be changed as:
>
> static void tst_fzsync_pair_cleanup(struct tst_fzsync_pair *pair)
> {
> tst_fzsync_pair_exit(pair);
>
> if (pair->thread_b) {
> SAFE_PTHREAD_JOIN(pair->thread_b, 0);
> pair->thread_b = 0;
> }
> }
>
> static inline int tst_fzsync_end_race_a(struct tst_fzsync_pair *pair)
> {
> if (tst_timer_expired_st(&pair->timer)) {
> tst_res(TINFO,
> "Exceeded fuzzy sync time limit, requesting exit");
> tst_fzsync_pair_cleanup(pair);
> }
>
> tst_fzsync_time(&pair->a_end);
> return tst_fzsync_pair_wait(pair, &pair->a_cntr, &pair->b_cntr,
>     &pair->spins);
> }

This should also be solved with Cyril's tst_fzsync_run() idea if I move
tst_fzsync_pair_cleanup there.

>
> 3. I tend to agree with Cyril's opinion, to take use of
> the tst_timeout_remaining() function which will be introduced by Jan's
> patch for move_pages12, then fzsync can drop the expired time detection by
> with new timer function involved.
>
> 4. The usage of fzsync is not very neat. For example in some places you
> put tst_fzsync_start_race_b(&pair) into curves but others not, I know that
> because of different situation needs variant race condition area,
> but if we can have a uniform format to satisfy that, it would be more happy
> to users.

I think tst_fzsync_run() should help with this a bit as well. Also in
most cases we just need to synchronise two system calls (one in each
thread), so I could also create two macros like:

#define TST_FZSYNC_RACE_A(f) \
tst_fzsync_start_race_a(..); \
TEST(f);                     \
tst_fzsync_end_race_a(..)

I am not sure it is really worth hiding two lines from the user
though. We could add this in a later update after implementing more
tests cases using the API.

>
> 5. I do not fully understand about the 'tst_fzsync_stat' part, if you can
> give more explanation in code comments, that will be much appreciated.
>
> Btw, I have tried this new API with my rhel7.5 x86_64 system, it woks fine
> with or without -i parameter, and it also does correctly when the
> execution_time expired. These comments are just FYI. Thanks!
>
> --
> Regards,
> Li Wang


--
Thank you,
Richard.

[LTP] [PATCH 5/5] Convert tests to use fzsync_{start, end}_race API

[Richard Palethorpe]

---
 lib/newlib_tests/test16.c                     | 24 ++++---------
 testcases/cve/cve-2014-0196.c                 | 25 ++++---------
 testcases/cve/cve-2016-7117.c                 | 35 ++++++-------------
 testcases/cve/cve-2017-2671.c                 | 23 ++++--------
 testcases/kernel/syscalls/inotify/inotify09.c | 23 +++++-------
 .../kernel/syscalls/ipc/shmctl/shmctl05.c     | 28 +++++----------
 6 files changed, 49 insertions(+), 109 deletions(-)

diff --git a/lib/newlib_tests/test16.c b/lib/newlib_tests/test16.c
index d80bd5369..a209a7b5d 100644
--- a/lib/newlib_tests/test16.c
+++ b/lib/newlib_tests/test16.c
@@ -29,7 +29,6 @@
 /* LOOPS * 2 + 1 must be less than INT_MAX */
 #define LOOPS 0xFFFFFFULL
 
-static pthread_t thrd;
 static volatile char seq[LOOPS * 2 + 1];
 static struct tst_fzsync_pair pair = TST_FZSYNC_PAIR_INIT;
 static volatile int seq_n;
@@ -39,10 +38,8 @@ static void *worker(void *v LTP_ATTRIBUTE_UNUSED)
 {
 	unsigned long long i;
 
-	for (i = 0; tst_fzsync_wait_update_b(&pair); i++) {
-		tst_fzsync_delay_b(&pair);
-		tst_fzsync_time_b(&pair);
-		if (!tst_fzsync_wait_b(&pair))
+	for (i = 0; tst_fzsync_start_race_b(&pair); i++) {
+		if (!tst_fzsync_end_race_b(&pair))
 			break;
 		seq[seq_n] = 'B';
 		seq_n = (i + 1) * 2 % (int)LOOPS * 2;
@@ -55,22 +52,17 @@ static void *worker(void *v LTP_ATTRIBUTE_UNUSED)
 	return NULL;
 }
 
-static void setup(void)
-{
-	SAFE_PTHREAD_CREATE(&thrd, NULL, worker, NULL);
-}
-
 static void run(void)
 {
 	unsigned int i, j, fail = 0;
 
+	tst_fzsync_pair_reset(&pair, worker);
 	for (i = 0; i < LOOPS; i++) {
-		tst_fzsync_wait_update_a(&pair);
-		tst_fzsync_delay_a(&pair);
+		if (!tst_fzsync_start_race_a(&pair))
+			break;
 		seq[seq_n] = 'A';
 		seq_n = i * 2 + 1;
-		tst_fzsync_time_a(&pair);
-		if (!tst_fzsync_wait_a(&pair))
+		if (!tst_fzsync_end_race_a(&pair))
 			break;
 	}
 
@@ -101,12 +93,10 @@ static void run(void)
 
 static void cleanup(void)
 {
-	tst_fzsync_pair_exit(&pair);
-	SAFE_PTHREAD_JOIN(thrd, NULL);
+	tst_fzsync_pair_cleanup(&pair);
 }
 
 static struct tst_test test = {
-	.setup = setup,
 	.cleanup = cleanup,
 	.test_all = run,
 };
diff --git a/testcases/cve/cve-2014-0196.c b/testcases/cve/cve-2014-0196.c
index d18108897..0a971be41 100644
--- a/testcases/cve/cve-2014-0196.c
+++ b/testcases/cve/cve-2014-0196.c
@@ -56,7 +56,6 @@ static int filler_ptys[ONEOFF_ALLOCS * 2];
 static int target_ptys[RUN_ALLOCS * 2];
 static char buf[BUFLEN];
 
-static pthread_t overwrite_thread;
 static void *overwrite_thread_fn(void *);
 static struct tst_fzsync_pair fzsync_pair = TST_FZSYNC_PAIR_INIT;
 
@@ -74,22 +73,15 @@ static void setup(void)
 		create_pty(&filler_ptys[i],
 			   &filler_ptys[i + ONEOFF_ALLOCS]);
 	}
-
-	fzsync_pair.info_gap = 0xFFF;
-	SAFE_PTHREAD_CREATE(&overwrite_thread, NULL,
-			    overwrite_thread_fn, NULL);
 }
 
 static void *overwrite_thread_fn(void *p LTP_ATTRIBUTE_UNUSED)
 {
-	while(tst_fzsync_wait_update_b(&fzsync_pair)) {
-		tst_fzsync_delay_b(&fzsync_pair);
-		tst_fzsync_time_b(&fzsync_pair);
-
+	while(tst_fzsync_start_race_b(&fzsync_pair)) {
 		SAFE_WRITE(0, slave_fd, buf, BUFLEN - 1);
 		SAFE_WRITE(0, slave_fd, buf, BUFLEN - 1);
 		SAFE_WRITE(0, slave_fd, buf, BUFLEN);
-		if (!tst_fzsync_wait_b(&fzsync_pair))
+		if (!tst_fzsync_end_race_b(&fzsync_pair))
 			break;
 	}
 	return 0;
@@ -102,6 +94,7 @@ static void run(void)
 
 	tst_res(TINFO, "Attempting to overflow into a tty_struct...");
 
+	tst_fzsync_pair_reset(&fzsync_pair, overwrite_thread_fn);
 	for (i = 0; i < ATTEMPTS; i++) {
 		create_pty((int *)&master_fd, (int *)&slave_fd);
 
@@ -118,13 +111,12 @@ static void run(void)
 		t.c_lflag |= ECHO;
 		tcsetattr(master_fd, TCSANOW, &t);
 
-		tst_fzsync_wait_update_a(&fzsync_pair);
+		if (!tst_fzsync_start_race_a(&fzsync_pair))
+			break;
 
-		tst_fzsync_delay_a(&fzsync_pair);
-		tst_fzsync_time_a(&fzsync_pair);
 		SAFE_WRITE(0, master_fd, "A", 1);
 
-		tst_fzsync_wait_a(&fzsync_pair);
+		tst_fzsync_end_race_a(&fzsync_pair);
 
 		for (j = 0; j < RUN_ALLOCS; j++) {
 			if (j == RUN_ALLOCS / 2)
@@ -149,10 +141,7 @@ static void cleanup(void)
 {
 	int i;
 
-	if (overwrite_thread) {
-		tst_fzsync_pair_exit(&fzsync_pair);
-		SAFE_PTHREAD_JOIN(overwrite_thread, NULL);
-	}
+	tst_fzsync_pair_cleanup(&fzsync_pair);
 
 	for (i = 0; i < ONEOFF_ALLOCS * 2; i++)
 		close(filler_ptys[i]);
diff --git a/testcases/cve/cve-2016-7117.c b/testcases/cve/cve-2016-7117.c
index 3cb7efcdf..206e8f25e 100644
--- a/testcases/cve/cve-2016-7117.c
+++ b/testcases/cve/cve-2016-7117.c
@@ -51,7 +51,6 @@
 
 #include "tst_test.h"
 #include "tst_safe_net.h"
-#include "tst_safe_pthread.h"
 #include "tst_timer.h"
 #include "tst_fuzzy_sync.h"
 
@@ -94,38 +93,27 @@ static struct mmsghdr msghdrs[2] = {
 static char rbuf[sizeof(MSG)];
 static struct timespec timeout = { .tv_sec = RECV_TIMEOUT };
 static struct tst_fzsync_pair fzsync_pair = TST_FZSYNC_PAIR_INIT;
-static pthread_t pt_send;
 static void *send_and_close(void *);
 
-static void setup(void)
-{
-	SAFE_PTHREAD_CREATE(&pt_send, 0, send_and_close, 0);
-}
-
 static void cleanup(void)
 {
 	close(socket_fds[0]);
 	close(socket_fds[1]);
 
-	if (pt_send) {
-		tst_fzsync_pair_exit(&fzsync_pair);
-		SAFE_PTHREAD_JOIN(pt_send, 0);
-	}
+	tst_fzsync_pair_cleanup(&fzsync_pair);
 }
 
 static void *send_and_close(void *arg)
 {
-	while (tst_fzsync_wait_update_b(&fzsync_pair)) {
+	while (tst_fzsync_wait_b(&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]);
+
+		tst_fzsync_start_race_b(&fzsync_pair);
 		close(socket_fds[1]);
-		tst_fzsync_time_b(&fzsync_pair);
-		if (!tst_fzsync_wait_b(&fzsync_pair))
-			break;
+		tst_fzsync_end_race_b(&fzsync_pair);
 	}
 	return arg;
 }
@@ -136,31 +124,30 @@ static void run(void)
 
 	msghdrs[0].msg_hdr.msg_iov->iov_base = (void *)&rbuf;
 
+	tst_fzsync_pair_reset(&fzsync_pair, send_and_close);
 	for (i = 1; i < ATTEMPTS; i++) {
 		if (socketpair(AF_LOCAL, SOCK_DGRAM, 0, (int *)socket_fds))
 			tst_brk(TBROK | TERRNO, "Socket creation failed");
 
-		tst_fzsync_wait_update_a(&fzsync_pair);
-		tst_fzsync_delay_a(&fzsync_pair);
+		if (!tst_fzsync_wait_a(&fzsync_pair))
+			break;
 
+		tst_fzsync_start_race_a(&fzsync_pair);
 		stat = tst_syscall(__NR_recvmmsg,
 				   socket_fds[1], msghdrs, 2, 0, &timeout);
-		tst_fzsync_time_a(&fzsync_pair);
+		tst_fzsync_end_race_a(&fzsync_pair);
 		if (stat < 0 && errno == EBADF)
 			too_early_count++;
 		else if (stat == 0)
 			tst_res(TWARN, "No messages received, should be one");
 		else if (stat < 0)
 			tst_res(TWARN | TERRNO, "recvmmsg failed unexpectedly");
-
-		tst_fzsync_wait_a(&fzsync_pair);
 	}
 
-	tst_res(TPASS, "Nothing happened after %d attempts", ATTEMPTS);
+	tst_res(TPASS, "Nothing happened after %d attempts", i);
 }
 
 static struct tst_test test = {
-	.setup = setup,
 	.test_all = run,
 	.cleanup = cleanup,
 	.min_kver = "2.6.33",
diff --git a/testcases/cve/cve-2017-2671.c b/testcases/cve/cve-2017-2671.c
index b0471bfff..1f32f1c17 100644
--- a/testcases/cve/cve-2017-2671.c
+++ b/testcases/cve/cve-2017-2671.c
@@ -56,7 +56,6 @@ static int sockfd;
 static unsigned int ping_min_grp, ping_max_grp;
 static struct tst_fzsync_pair fzsync_pair = TST_FZSYNC_PAIR_INIT;
 static struct sockaddr_in iaddr, uaddr;
-static pthread_t thrd;
 static void *connect_b(void *);
 
 static void setup(void)
@@ -65,7 +64,6 @@ static void setup(void)
 	uaddr = iaddr;
 	iaddr.sin_family = AF_INET;
 	uaddr.sin_family = AF_UNSPEC;
-	fzsync_pair.delay_inc = 1;
 
 	if (access(PING_SYSCTL_PATH, F_OK))
 		tst_brk(TCONF, "socket() does not support IPPROTO_ICMP");
@@ -75,16 +73,12 @@ static void setup(void)
 	SAFE_FILE_PRINTF(PING_SYSCTL_PATH, "0 0");
 
 	sockfd = SAFE_SOCKET(AF_INET, SOCK_DGRAM, IPPROTO_ICMP);
-	SAFE_PTHREAD_CREATE(&thrd, 0, connect_b, 0);
 	tst_res(TINFO, "Created ping socket, attempting to race...");
 }
 
 static void cleanup(void)
 {
-	if (thrd) {
-		tst_fzsync_pair_exit(&fzsync_pair);
-		SAFE_PTHREAD_JOIN(thrd, NULL);
-	}
+	tst_fzsync_pair_cleanup(&fzsync_pair);
 
 	if (sockfd > 0)
 		SAFE_CLOSE(sockfd);
@@ -96,11 +90,9 @@ static void cleanup(void)
 
 static void *connect_b(void * param LTP_ATTRIBUTE_UNUSED)
 {
-	while(tst_fzsync_wait_update_b(&fzsync_pair)) {
-		tst_fzsync_delay_b(&fzsync_pair);
+	while(tst_fzsync_start_race_b(&fzsync_pair)) {
 		connect(sockfd, (struct sockaddr *)&uaddr, sizeof(uaddr));
-		tst_fzsync_time_b(&fzsync_pair);
-		if (!tst_fzsync_wait_b(&fzsync_pair))
+		if (!tst_fzsync_end_race_b(&fzsync_pair))
 			break;
 	}
 
@@ -111,16 +103,15 @@ static void run(void)
 {
 	int i;
 
+	tst_fzsync_pair_reset(&fzsync_pair, connect_b);
 	for (i = 0; i < ATTEMPTS; i++) {
 		SAFE_CONNECT(sockfd,
 			     (struct sockaddr *)&iaddr, sizeof(iaddr));
 
-		tst_fzsync_wait_update_a(&fzsync_pair);
-		tst_fzsync_delay_a(&fzsync_pair);
+		if (!tst_fzsync_start_race_a(&fzsync_pair))
+			break;
 		connect(sockfd, (struct sockaddr *)&uaddr, sizeof(uaddr));
-		tst_fzsync_time_a(&fzsync_pair);
-
-		tst_fzsync_wait_a(&fzsync_pair);
+		tst_fzsync_end_race_a(&fzsync_pair);
 	}
 
 	tst_res(TPASS, "We didn't crash");
diff --git a/testcases/kernel/syscalls/inotify/inotify09.c b/testcases/kernel/syscalls/inotify/inotify09.c
index 475411311..b15136fcf 100644
--- a/testcases/kernel/syscalls/inotify/inotify09.c
+++ b/testcases/kernel/syscalls/inotify/inotify09.c
@@ -52,19 +52,16 @@
 #include <sys/inotify.h>
 
 static struct tst_fzsync_pair fzsync_pair = TST_FZSYNC_PAIR_INIT;
-static pthread_t pt_write_seek;
 static int fd;
 
 static void *write_seek(void *unused)
 {
 	char buf[64];
 
-	while (tst_fzsync_wait_update_b(&fzsync_pair)) {
-		tst_fzsync_delay_b(&fzsync_pair);
+	while (tst_fzsync_start_race_b(&fzsync_pair)) {
 		SAFE_WRITE(0, fd, buf, sizeof(buf));
-		tst_fzsync_time_b(&fzsync_pair);
 		SAFE_LSEEK(fd, 0, SEEK_SET);
-		if (!tst_fzsync_wait_b(&fzsync_pair))
+		if (!tst_fzsync_end_race_b(&fzsync_pair))
 			break;
 	}
 	return unused;
@@ -73,8 +70,6 @@ static void *write_seek(void *unused)
 static void setup(void)
 {
 	fd = SAFE_OPEN(FNAME, O_CREAT | O_RDWR, 0600);
-	fzsync_pair.info_gap = 0x7fff;
-	SAFE_PTHREAD_CREATE(&pt_write_seek, 0, write_seek, NULL);
 }
 
 static void cleanup(void)
@@ -82,10 +77,7 @@ static void cleanup(void)
 	if (fd > 0)
 		SAFE_CLOSE(fd);
 
-	if (pt_write_seek) {
-		tst_fzsync_pair_exit(&fzsync_pair);
-		SAFE_PTHREAD_JOIN(pt_write_seek, NULL);
-	}
+	tst_fzsync_pair_cleanup(&fzsync_pair);
 }
 
 static void verify_inotify(void)
@@ -97,20 +89,21 @@ static void verify_inotify(void)
 	inotify_fd = myinotify_init1(0);
 	if (inotify_fd < 0)
 		tst_brk(TBROK | TERRNO, "inotify_init failed");
+
+	tst_fzsync_pair_reset(&fzsync_pair, write_seek);
 	for (tests = 0; tests < TEARDOWNS; tests++) {
 		wd = myinotify_add_watch(inotify_fd, FNAME, IN_MODIFY);
 		if (wd < 0)
 			tst_brk(TBROK | TERRNO, "inotify_add_watch() failed.");
 
-		tst_fzsync_wait_update_a(&fzsync_pair);
-		tst_fzsync_delay_a(&fzsync_pair);
+		if (!tst_fzsync_start_race_a(&fzsync_pair))
+			break;
 
 		wd = myinotify_rm_watch(inotify_fd, wd);
 		if (wd < 0)
 			tst_brk(TBROK | TERRNO, "inotify_rm_watch() failed.");
 
-		tst_fzsync_time_a(&fzsync_pair);
-		tst_fzsync_wait_a(&fzsync_pair);
+		tst_fzsync_end_race_a(&fzsync_pair);
 	}
 	SAFE_CLOSE(inotify_fd);
 	/* We survived for given time - test succeeded */
diff --git a/testcases/kernel/syscalls/ipc/shmctl/shmctl05.c b/testcases/kernel/syscalls/ipc/shmctl/shmctl05.c
index a960cc906..b984b9760 100644
--- a/testcases/kernel/syscalls/ipc/shmctl/shmctl05.c
+++ b/testcases/kernel/syscalls/ipc/shmctl/shmctl05.c
@@ -34,8 +34,6 @@
 
 static struct tst_fzsync_pair fzsync_pair = TST_FZSYNC_PAIR_INIT;
 
-static pthread_t thrd;
-
 /*
  * Thread 2: repeatedly remove the shm ID and reallocate it again for a
  * new shm segment.
@@ -44,12 +42,10 @@ static void *thrproc(void *unused)
 {
 	int id = SAFE_SHMGET(0xF00F, 4096, IPC_CREAT|0700);
 
-	for (;;) {
-		if (!tst_fzsync_wait_b(&fzsync_pair))
-			break;
+	while (tst_fzsync_start_race_b(&fzsync_pair)) {
 		SAFE_SHMCTL(id, IPC_RMID, NULL);
 		id = SAFE_SHMGET(0xF00F, 4096, IPC_CREAT|0700);
-		if (!tst_fzsync_wait_b(&fzsync_pair))
+		if (!tst_fzsync_end_race_b(&fzsync_pair))
 			break;
 	}
 	return unused;
@@ -57,30 +53,27 @@ static void *thrproc(void *unused)
 
 static void setup(void)
 {
-	tst_timer_check(CLOCK_MONOTONIC);
-
+	fzsync_pair.execution_time = 5;
 	/* Skip test if either remap_file_pages() or SysV IPC is unavailable */
 	tst_syscall(__NR_remap_file_pages, NULL, 0, 0, 0, 0);
 	tst_syscall(__NR_shmctl, 0xF00F, IPC_RMID, NULL);
-
-	SAFE_PTHREAD_CREATE(&thrd, NULL, thrproc, NULL);
 }
 
 static void do_test(void)
 {
-	tst_timer_start(CLOCK_MONOTONIC);
-
 	/*
 	 * Thread 1: repeatedly attach a shm segment, then remap it until the ID
 	 * seems to have been removed by the other process.
 	 */
-	while (!tst_timer_expired_ms(5000)) {
+	tst_fzsync_pair_reset(&fzsync_pair, thrproc);
+	for (;;) {
 		int id;
 		void *addr;
 
 		id = SAFE_SHMGET(0xF00F, 4096, IPC_CREAT|0700);
 		addr = SAFE_SHMAT(id, NULL, 0);
-		tst_fzsync_wait_a(&fzsync_pair);
+		if (!tst_fzsync_start_race_a(&fzsync_pair))
+			break;
 		do {
 			/* This is the system call that crashed */
 			TEST(syscall(__NR_remap_file_pages, addr, 4096,
@@ -91,7 +84,7 @@ static void do_test(void)
 			tst_brk(TBROK | TTERRNO,
 				"Unexpected remap_file_pages() error");
 		}
-		tst_fzsync_wait_a(&fzsync_pair);
+		tst_fzsync_end_race_a(&fzsync_pair);
 	}
 
 	tst_res(TPASS, "didn't crash");
@@ -99,10 +92,7 @@ static void do_test(void)
 
 static void cleanup(void)
 {
-	if (thrd) {
-		tst_fzsync_pair_exit(&fzsync_pair);
-		SAFE_PTHREAD_JOIN(thrd, NULL);
-	}
+	tst_fzsync_pair_cleanup(&fzsync_pair);
 	shmctl(0xF00F, IPC_RMID, NULL);
 }
 
-- 
2.18.0