[LTP] [PATCH v2 0/4] New Fuzzy Sync library API

[LTP] [PATCH v2 0/4] New Fuzzy Sync library API

[Richard Palethorpe]

This second version is significantly different from the first. Amongst other
things I have dropped the new timer API I created in favor of Jan's timeout
function. The exit variable is now only checked and set in a single place
which has simplified the spin wait and the API usage.

However I have also had to introduce some extra complexity for the sake of
cve-2016-7117. After making some seemingly unrelated code changes (I guess the
main one was removing the exit flag check from the spin wait) the dominant
chronological order and therefor timings of the racing syscalls changed. To
fix this I added a delay bias to coerce the syscalls into the correct
order. This appears to work, but requires the test author to figure out a way
of setting the delay bias (easy enough for cve-2016-7117). I also attempted
simply expanding the delay range, but this was not effective. The test
requires a high level accuracy when setting the delay range, otherwise we will
not hit the race condition in a reasonable amount of time.

Another approach, which would be transparent to the test author, but require
even more complexity within the library. Would be to continue collecting
timing statistics once the random delays have been introduced to look for
statistically significant changes in the syscall timings caused by the
delay. If we can identify groups (clusters) of similar timings then we could
automatically create new delay ranges based on these timings. However I think
there is lower hanging fruit to be had before attempting anything like this.

Richard Palethorpe (4):
  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
  Add delay bias for difficult races

 include/tst_fuzzy_sync.h                      | 787 ++++++++++++++----
 include/tst_timer.h                           |  11 +
 lib/newlib_tests/test16.c                     |  62 +-
 testcases/cve/cve-2014-0196.c                 |  37 +-
 testcases/cve/cve-2016-7117.c                 |  59 +-
 testcases/cve/cve-2017-2671.c                 |  32 +-
 testcases/kernel/syscalls/inotify/inotify09.c |  33 +-
 .../kernel/syscalls/ipc/shmctl/shmctl05.c     |  30 +-
 8 files changed, 727 insertions(+), 324 deletions(-)

-- 
2.18.0

[LTP] [PATCH v2 1/4] 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 0fd7ed6cf..577bc88ef 100644
--- a/include/tst_timer.h
+++ b/include/tst_timer.h
@@ -34,6 +34,11 @@
 #include <sys/time.h>
 #include <time.h>
 
+static inline long long tst_timespec_to_ns(struct timespec t)
+{
+	return t.tv_sec * 1000000000 + t.tv_nsec;
+}
+
 /*
  * Converts timespec to microseconds.
  */
@@ -166,6 +171,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 v2 1/4] tst_timer: Add nano second conversions

[Petr Vorel]

Hi Richard,

> Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
Reviewed-by: Petr Vorel <pvorel@suse.cz>

It'd be nice to add doc into doc/test-writing-guidelines.txt.
(I know the docs isn't complete, at least tst_timeval_diff_ms() is not
mentioned.

> ---
>  include/tst_timer.h | 11 +++++++++++
>  1 file changed, 11 insertions(+)

> diff --git a/include/tst_timer.h b/include/tst_timer.h
> index 0fd7ed6cf..577bc88ef 100644
> --- a/include/tst_timer.h
> +++ b/include/tst_timer.h
> @@ -34,6 +34,11 @@
>  #include <sys/time.h>
>  #include <time.h>

> +static inline long long tst_timespec_to_ns(struct timespec t)
> +{
> +	return t.tv_sec * 1000000000 + t.tv_nsec;
> +}
> +
>  /*
>   * Converts timespec to microseconds.
>   */
> @@ -166,6 +171,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);
I guess this can be just 1000000000 (nitpicking).

> +}
> +
>  static inline long long tst_timespec_diff_us(struct timespec t1,
>                                               struct timespec t2)
>  {


Kind regards,
Petr

[LTP] [PATCH v2 1/4] tst_timer: Add nano second conversions

[Richard Palethorpe]

Hello,

Petr Vorel <pvorel@suse.cz> writes:

> Hi Richard,
>
>> Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
> Reviewed-by: Petr Vorel <pvorel@suse.cz>
>
> It'd be nice to add doc into doc/test-writing-guidelines.txt.
> (I know the docs isn't complete, at least tst_timeval_diff_ms() is not
> mentioned.
>
>> ---
>>  include/tst_timer.h | 11 +++++++++++
>>  1 file changed, 11 insertions(+)
>
>> diff --git a/include/tst_timer.h b/include/tst_timer.h
>> index 0fd7ed6cf..577bc88ef 100644
>> --- a/include/tst_timer.h
>> +++ b/include/tst_timer.h
>> @@ -34,6 +34,11 @@
>>  #include <sys/time.h>
>>  #include <time.h>
>
>> +static inline long long tst_timespec_to_ns(struct timespec t)
>> +{
>> +	return t.tv_sec * 1000000000 + t.tv_nsec;
>> +}
>> +
>>  /*
>>   * Converts timespec to microseconds.
>>   */
>> @@ -166,6 +171,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);
> I guess this can be just 1000000000 (nitpicking).

Is tv_sec (time_t) guaranteed to be 64bits? That is how it is defined in the
headers, but in the POSIX specification it just says it should be an
integer. Either way it is only two extra characters :-p

>
>> +}
>> +
>>  static inline long long tst_timespec_diff_us(struct timespec t1,
>>                                               struct timespec t2)
>>  {
>
>
> Kind regards,
> Petr


-- 
Thank you,
Richard.

[LTP] [PATCH v2 2/4] 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 | 732 +++++++++++++++++++++++++++++----------
 1 file changed, 555 insertions(+), 177 deletions(-)

diff --git a/include/tst_fuzzy_sync.h b/include/tst_fuzzy_sync.h
index bcc625e24..e38a23fa1 100644
--- a/include/tst_fuzzy_sync.h
+++ b/include/tst_fuzzy_sync.h
@@ -1,3 +1,4 @@
+/* SPDX-License-Identifier: GPL-2.0 */
 /*
  * Copyright (c) 2017 Richard Palethorpe <rpalethorpe@suse.com>
  *
@@ -14,225 +15,513 @@
  * 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 the tst_fzsync_*
+ * functions are called in. In the simplest case thread A will look something
+ * like:
+ *
+ * tst_fzsync_pair_reset(&pair, run_thread_b);
+ * while (tst_fzsync_run_a(&pair)) {
+ *	// Perform some setup which must happen before the race
+ *	tst_fzsync_start_race_a(&pair);
+ *	// Do some dodgy syscall
+ *	tst_fzsync_end_race_a(&pair);
+ * }
+ *
+ * Then in thread B (run_thread_b):
+ *
+ * while (tst_fzsync_run_b(&pair)) {
+ *	tst_fzsync_start_race_b(&pair);
+ *	// Do something which can race with the dodgy syscall in A
+ *	tst_fzsync_end_race_b(&pair)
+ * }
+ *
+ * The calls to tst_fzsync_start/end_race and tst_fzsync_run_a/b block (at
+ * least) until both threads have enter them. These functions can only be
+ * called once for each iteration, but further sychronisation points can be
+ * added by calling tst_fzsync_wait_a() and tst_fzsync_wait_b() in each
+ * thread.
+ *
+ * The execution of the loops in threads A and B are bounded by both iteration
+ * count and time. A slow machine is likely to be limited by time and a fast
+ * one by iteration count. The user can use the -i parameter to run the test
+ * multiple times or LTP_TIMEOUT_MUL to give the test more time.
+ *
+ * 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.
+ *
+ * Some of the fields can be configured before calling
+ * tst_fzsync_pair_reset(), however this is mainly for debugging purposes. If
+ * a test requires one of the parameters to be modified, we should consider
+ * finding a way of automatically selecting an appropriate value at runtime.
  *
  * 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;
+	/**
+	 * The maximum desired execution time as a proportion of the timeout
+	 *
+	 * A value x so that 0 < x < 1 which decides how long the test should
+	 * be run for (assuming the loop limit is not exceeded first).
+	 *
+	 * Defaults to 0.1 (~30 seconds with default timeout).
+	 */
+	float exec_time_p;
+	/** Internal; The test time remaining on tst_fzsync_pair_reset() */
+	float exec_time_start;
+	/**
+	 * The maximum number of iterations to execute during the test
+	 *
+	 * Defaults to a large number, but not too large.
+	 */
+	int exec_loops;
+	/** Internal; The current loop index  */
+	int exec_loop;
+	/** Internal; The second thread or NULL */
+	pthread_t thread_b;
 };
 
+#define CHK(param, low, hi, def) do {					      \
+	pair->param = (pair->param ? pair->param : def);		      \
+	if (pair->param <= low)						      \
+		tst_brk(TBROK, #param " is less than the lower bound " #low); \
+	if (pair->param >= hi)						      \
+		tst_brk(TBROK, #param " is more than the upper bound " #hi);  \
+	} while (0)
 /**
- * TST_FZSYNC_PAIR_INIT - Default values for struct tst_fzysnc_pair
+ * Ensures that any Fuzzy Sync parameters are properly set
+ *
+ * @relates tst_fzsync_pair
+ *
+ * Usually called from the setup function, it sets default parameter values or
+ * validates any existing non-defaults.
+ *
+ * @sa tst_fzsync_pair_reset()
  */
-#define TST_FZSYNC_PAIR_INIT {	\
-	.avg_alpha = 0.25,	\
-	.delay_inc = 1,	        \
-	.update_gap = 0xF,	\
-	.info_gap = 0x7FFFF     \
+static void tst_fzsync_pair_init(struct tst_fzsync_pair *pair)
+{
+	CHK(avg_alpha, 0, 1, 0.25);
+	CHK(min_samples, 20, INT_MAX, 1024);
+	CHK(max_dev_ratio, 0, 1, 0.1);
+	CHK(exec_time_p, 0, 1, 0.2);
+	CHK(exec_loops, 20, INT_MAX, 1000000);
 }
+#undef CHK
 
 /**
- * tst_fzsync_pair_info - Print some synchronisation statistics
+ * Exit and join thread B if necessary.
+ *
+ * @relates tst_fzsync_pair
+ *
+ * Call this from your cleanup function.
  */
-static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair)
+static void tst_fzsync_pair_cleanup(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);
+	if (pair->thread_b) {
+		tst_atomic_store(1, &pair->exit);
+		SAFE_PTHREAD_JOIN(pair->thread_b, 0);
+		pair->thread_b = 0;
+	}
 }
 
 /**
- * tst_fzsync_delay_a - Perform spin delay for A, 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_a(struct tst_fzsync_pair *pair)
+static void tst_init_stat(struct tst_fzsync_stat *s)
 {
-	volatile long spin_delay = pair->delay;
+	s->avg = 0;
+	s->avg_dev = 0;
+}
 
-	while (spin_delay > 0)
-		spin_delay--;
+/**
+ * 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 (re)set any variables 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.
+ *
+ * @sa tst_fzsync_pair_init()
+ */
+static void tst_fzsync_pair_reset(struct tst_fzsync_pair *pair,
+				  void *(*run_b)(void *))
+{
+	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->exec_loop = 0;
+
+	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);
+
+	pair->exec_time_start = (float)tst_timeout_remaining();
 }
 
 /**
- * tst_fzsync_delay_b - Perform spin delay for B, if needed
+ * Print stat
  *
- * 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 inline void tst_fzsync_stat_info(struct tst_fzsync_stat stat,
+					char *unit, char *name)
 {
-	volatile long spin_delay = pair->delay;
+	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);
+}
 
-	while (spin_delay < 0)
-		spin_delay++;
+/**
+ * Print some synchronisation statistics
+ *
+ * @relates tst_fzsync_pair
+ */
+static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair)
+{
+	tst_res(TINFO, "loop = %d", pair->exec_loop);
+	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)
 {
+#ifdef CLOCK_MONOTONIC_RAW
 	clock_gettime(CLOCK_MONOTONIC_RAW, t);
+#else
+	clock_gettime(CLOCK_MONOTONIC, t);
+#endif
 }
 
 /**
- * tst_fzsync_time_a - Set A's time to now.
+ * Exponential moving average
  *
- * Called at the point you want to synchronise.
+ * @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
+ *
+ * @return The average including the current sample.
  */
-static inline void tst_fzsync_time_a(struct tst_fzsync_pair *pair)
+static inline float tst_exp_moving_avg(float alpha,
+					float sample,
+					float prev_avg)
 {
-	tst_fzsync_time(&pair->a);
+	return alpha * sample + (1.0 - alpha) * prev_avg;
 }
 
 /**
- * tst_fzsync_time_b - Set B's call time to now.
+ * Update a stat with a new sample
  *
- * Called at the point you want to synchronise.
+ * @relates tst_fzsync_stat
  */
-static inline void tst_fzsync_time_b(struct tst_fzsync_pair *pair)
+static inline void tst_upd_stat(struct tst_fzsync_stat *s,
+				 float alpha,
+				 float sample)
 {
-	tst_fzsync_time(&pair->b);
+	s->avg = tst_exp_moving_avg(alpha, sample, s->avg);
+	s->avg_dev = tst_exp_moving_avg(alpha,
+					5fabs(s->avg - sample), s->avg_dev);
+	s->dev_ratio = fabs(s->avg ? s->avg_dev / s->avg : 0);
 }
 
 /**
- * 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
+ * Update a stat with a new diff sample
  *
- * Returns average including the current sample.
+ * @relates tst_fzsync_stat
  */
-static inline float tst_exp_moving_avg(float alpha,
-					float sample,
-					float prev_avg)
+static inline void tst_upd_diff_stat(struct tst_fzsync_stat *s,
+				     float alpha,
+				     struct timespec t1,
+				     struct timespec t2)
 {
-	return alpha * sample + (1.0 - alpha) * prev_avg;
+	tst_upd_stat(s, alpha, tst_timespec_diff_ns(t1, t2));
 }
 
 /**
- * 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.
+ * 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.
+ *
+ * The delay range goes from positive to negative. A negative delay will delay
+ * thread A and and positive one will delay thread B. The range is bounded by
+ * the point where the entry code to Syscall A is synchronised with the exit
+ * to Syscall B and the entry code to Syscall B is synchronised with the exit
+ * of A.
+ *
+ * In order to calculate the lower bound (the max delay of A) we can simply
+ * negate the execution time of Syscall B and convert it to a spin count. For
+ * the upper bound (the max delay of B), we just take the execution time of A
+ * and convert it to a spin count.
+ *
+ * In order to calculate spin count we need to know approximately how long a
+ * spin takes and devide the delay time with it. We find this by first
+ * counting how many spins one thread spends waiting for the other during
+ * end_race[1]. We also know when each syscall exits so we can take the
+ * difference between the exit times and divde it with the number of spins
+ * spent waiting.
+ *
+ * All the times and counts we use in the calculation are averaged over a
+ * variable number of iterations. There is an initial sampling period where we
+ * simply collect time and count samples then caculate their averages. When a
+ * minimum number of samples have been collected, and if the average deviation
+ * is below some proportion of the average sample magnitude, then the sampling
+ * period is ended. On all further iterations a random delay is calculated and
+ * applied, but the averages are not updated.
+ *
+ * [1] This assumes there is always a significant difference. The algorithm
+ * may fail to introduce a delay (when one is needed) in situations where
+ * Syscall A and B finish at approximately the same time.
+ *
+ * @relates tst_fzsync_pair
  */
-static void tst_fzsync_pair_update(int loop_index, struct tst_fzsync_pair *pair)
+static void tst_fzsync_pair_update(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 (!(loop_index & pair->info_gap))
-		tst_fzsync_pair_info(pair);
+	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);
+		}
+	} else if (fabsf(pair->diff_ab.avg) >= 1 && pair->spins_avg.avg >= 1) {
+		per_spin_time = fabsf(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);
 
-	pair->avg_diff = avg;
+		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);
+			pair->sampling = -1;
+		}
+	} else if (!pair->sampling) {
+		tst_res(TWARN, "Can't calculate random delay");
+		pair->sampling = -1;
+	}
+
+	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)
+static inline void tst_fzsync_pair_wait(int *our_cntr,
+					int *other_cntr,
+					int *spins)
 {
 	if (tst_atomic_inc(other_cntr) == INT_MAX) {
 		/*
@@ -243,84 +532,173 @@ static inline int tst_fzsync_pair_wait(struct tst_fzsync_pair *pair,
 		 * then our counter may already have been set to zero.
 		 */
 		while (tst_atomic_load(our_cntr) > 0
-		       && tst_atomic_load(our_cntr) < INT_MAX
-		       && !tst_atomic_load(&pair->exit))
-			;
+		       && tst_atomic_load(our_cntr) < INT_MAX) {
+			if (spins)
+				(*spins)++;
+		}
 
 		tst_atomic_store(0, other_cntr);
 		/*
 		 * Once both counters have been set to zero the invariant
 		 * is restored and we can continue.
 		 */
-		while (tst_atomic_load(our_cntr) > 1
-		       && !tst_atomic_load(&pair->exit))
+		while (tst_atomic_load(our_cntr) > 1)
 			;
 	} else {
 		/*
 		 * If our counter is less than the other thread's we are ahead
 		 * of it and need to wait.
 		 */
-		while (tst_atomic_load(our_cntr) < tst_atomic_load(other_cntr)
-		       && !tst_atomic_load(&pair->exit))
-			;
+		while (tst_atomic_load(our_cntr) < tst_atomic_load(other_cntr)) {
+			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);
+/**
+ * Wait in thread A
+ *
+ * @relates tst_fzsync_pair
+ * @sa tst_fzsync_pair_wait
+ */
+static inline void tst_fzsync_wait_a(struct tst_fzsync_pair *pair)
+{
+	tst_fzsync_pair_wait(&pair->a_cntr, &pair->b_cntr, NULL);
 }
 
-static inline int tst_fzsync_wait_a(struct tst_fzsync_pair *pair)
+/**
+ * Wait in thread B
+ *
+ * @relates tst_fzsync_pair
+ * @sa tst_fzsync_pair_wait
+ */
+static inline void tst_fzsync_wait_b(struct tst_fzsync_pair *pair)
 {
-	return tst_fzsync_pair_wait(pair, &pair->a_cntr, &pair->b_cntr);
+	tst_fzsync_pair_wait(&pair->b_cntr, &pair->a_cntr, NULL);
 }
 
-static inline int tst_fzsync_wait_b(struct tst_fzsync_pair *pair)
+/**
+ * Decide whether to continue running thread A
+ *
+ * @relates tst_fzsync_pair
+ *
+ * Checks some values and decides whether it is time to break the loop of
+ * thread A.
+ *
+ * @return True to continue and false to break.
+ * @sa tst_fzsync_run_a
+ */
+static inline int tst_fzsync_run_a(struct tst_fzsync_pair *pair)
 {
-	return tst_fzsync_pair_wait(pair, &pair->b_cntr, &pair->a_cntr);
+	int exit = 0;
+
+	if (pair->exec_time_p
+	    < 1 - tst_timeout_remaining() / pair->exec_time_start) {
+		tst_res(TINFO,
+			"Exceeded execution time, requesting exit");
+		exit = 1;
+	}
+
+	if (++pair->exec_loop > pair->exec_loops) {
+		tst_res(TINFO,
+			"Exceeded execution loops, requesting exit");
+		exit = 1;
+	}
+
+	tst_atomic_store(exit, &pair->exit);
+	tst_fzsync_wait_a(pair);
+
+	if (exit) {
+		tst_fzsync_pair_cleanup(pair);
+		return 0;
+	}
+
+	return 1;
 }
 
 /**
- * tst_fzsync_pair_wait_update_{a,b} - Wait and then recalculate
+ * Decide whether to continue running thread B
+ *
+ * @relates tst_fzsync_pair
+ * @sa tst_fzsync_run_a
+ */
+static inline int tst_fzsync_run_b(struct tst_fzsync_pair *pair)
+{
+	tst_fzsync_wait_b(pair);
+	return !tst_atomic_load(&pair->exit);
+}
+
+/**
+ * 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 void tst_fzsync_start_race_a(struct tst_fzsync_pair *pair)
 {
-	static int loop_index;
+	volatile int delay;
+
+	tst_fzsync_pair_update(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);
+	tst_fzsync_wait_a(pair);
+	tst_fzsync_time(&pair->a_start);
+
+	delay = pair->delay;
+	while (delay < 0)
+		delay++;
+}
+
+/**
+ * Marks the end of a race region in thread A
+ *
+ * @relates tst_fzsync_pair
+ * @sa tst_fzsync_start_race_a
+ */
+static inline void tst_fzsync_end_race_a(struct tst_fzsync_pair *pair)
+{
+	tst_fzsync_time(&pair->a_end);
+	tst_fzsync_pair_wait(&pair->a_cntr, &pair->b_cntr, &pair->spins);
 }
 
-static inline int tst_fzsync_wait_update_b(struct tst_fzsync_pair *pair)
+/**
+ * Marks the start of a race region in thread B
+ *
+ * @relates tst_fzsync_pair
+ * @sa tst_fzsync_start_race_a
+ */
+static inline void tst_fzsync_start_race_b(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);
+	volatile int delay;
+
+	tst_fzsync_wait_b(pair);
+	tst_fzsync_time(&pair->b_start);
+
+	delay = pair->delay;
+	while (delay > 0)
+		delay--;
 }
 
 /**
- * tst_fzsync_pair_exit - Signal that the other thread should exit
+ * Marks the end 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 void tst_fzsync_end_race_b(struct tst_fzsync_pair *pair)
 {
-	tst_atomic_store(1, &pair->exit);
+	tst_fzsync_time(&pair->b_end);
+	tst_fzsync_pair_wait(&pair->b_cntr, &pair->a_cntr, &pair->spins);
 }
-- 
2.18.0

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

[Richard Palethorpe]

Richard Palethorpe <rpalethorpe@suse.com> writes:

> +static inline void tst_upd_stat(struct tst_fzsync_stat *s,
> +				 float alpha,
> +				 float sample)
>  {
> -	tst_fzsync_time(&pair->b);
> +	s->avg = tst_exp_moving_avg(alpha, sample, s->avg);
> +	s->avg_dev = tst_exp_moving_avg(alpha,
> +					5fabs(s->avg - sample), s->avg_dev);
                                        ^ whoops

-- 
Thank you,
Richard.

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

[Li Wang]

Hi Richard,

Sorry for late reply. This patch V2 is good, not sure if below comments are
useful to you, so just FYI.

Richard Palethorpe <rpalethorpe@suse.com> wrote:

> 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.
> ...
> +       /**
> +        * 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.
>

s/ssome/some/, a typo here?

+
> +       /** 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;
> +       /**
> +        * The maximum desired execution time as a proportion of the
> timeout
> +        *
> +        * A value x so that 0 < x < 1 which decides how long the test
> should
> +        * be run for (assuming the loop limit is not exceeded first).
> +        *
> +        * Defaults to 0.1 (~30 seconds with default timeout).
> +        */
> +       float exec_time_p;
> +       /** Internal; The test time remaining on tst_fzsync_pair_reset() */
> +       float exec_time_start;
>

I think maybe call it as 'exec_time_remain' or 'exec_time_total' is better?
because this value is the remain part of the whole timeout time before next
resetting.

+
> -#define TST_FZSYNC_PAIR_INIT { \
> -       .avg_alpha = 0.25,      \
> -       .delay_inc = 1,         \
> -       .update_gap = 0xF,      \
> -       .info_gap = 0x7FFFF     \
> +static void tst_fzsync_pair_init(struct tst_fzsync_pair *pair)
> +{
> +       CHK(avg_alpha, 0, 1, 0.25);
> +       CHK(min_samples, 20, INT_MAX, 1024);
> +       CHK(max_dev_ratio, 0, 1, 0.1);
> +       CHK(exec_time_p, 0, 1, 0.2);
>

The code comment says the default is 0.1, but why here gives 0.2?

+static void tst_fzsync_pair_reset(struct tst_fzsync_pair *pair,
> +                                 void *(*run_b)(void *))
> +{
> +       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->exec_loop = 0;
> +
> +       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);
> +
> +       pair->exec_time_start = (float)tst_timeout_remaining();


Here we start to get the whole remain time before reaching timeout
aborting, and base on that to comparing in tst_fzsync_run_a() to guarantee
test exit when execute time exceed. That's fine, but it is too early to get
the time here I guess, because samples collection will also cost some of
the limitation_time(~30 seconds), and we don't know what proportion the
sampling occupied in exec_time_p, if it's too much, then there only has
very little time on race execution.

To avoid this, maybe we should make the limitation time all spend on race
execution but any on samplings.
So, I suggest to get pair->exec_time_start value after samples data
collection in the end of tst_fzsync_pair_update() function.
-- 
Regards,
Li Wang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linux.it/pipermail/ltp/attachments/20180926/bcb7822b/attachment.html>

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

[Richard Palethorpe]

Hello,

Li Wang <liwang@redhat.com> writes:

> Hi Richard,
>
> Sorry for late reply. This patch V2 is good, not sure if below comments are
> useful to you, so just FYI.
>
> Richard Palethorpe <rpalethorpe@suse.com> wrote:
>
>> 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.
>> ...
>> +       /**
>> +        * 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.
>>
>
> s/ssome/some/, a typo here?
>
> +
>> +       /** 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;
>> +       /**
>> +        * The maximum desired execution time as a proportion of the
>> timeout
>> +        *
>> +        * A value x so that 0 < x < 1 which decides how long the test
>> should
>> +        * be run for (assuming the loop limit is not exceeded first).
>> +        *
>> +        * Defaults to 0.1 (~30 seconds with default timeout).
>> +        */
>> +       float exec_time_p;
>> +       /** Internal; The test time remaining on tst_fzsync_pair_reset() */
>> +       float exec_time_start;
>>
>
> I think maybe call it as 'exec_time_remain' or 'exec_time_total' is better?
> because this value is the remain part of the whole timeout time before next
> resetting.

I'm not sure, it is quite confusing either way. Probably
'exec_time_remaining_at_start' is less confusing, but it is too long. I
can't think of anything which is short and accurate.

>
> +
>> -#define TST_FZSYNC_PAIR_INIT { \
>> -       .avg_alpha = 0.25,      \
>> -       .delay_inc = 1,         \
>> -       .update_gap = 0xF,      \
>> -       .info_gap = 0x7FFFF     \
>> +static void tst_fzsync_pair_init(struct tst_fzsync_pair *pair)
>> +{
>> +       CHK(avg_alpha, 0, 1, 0.25);
>> +       CHK(min_samples, 20, INT_MAX, 1024);
>> +       CHK(max_dev_ratio, 0, 1, 0.1);
>> +       CHK(exec_time_p, 0, 1, 0.2);
>>
>
> The code comment says the default is 0.1, but why here gives 0.2?

It should be 0.1 here as well.

>
> +static void tst_fzsync_pair_reset(struct tst_fzsync_pair *pair,
>> +                                 void *(*run_b)(void *))
>> +{
>> +       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->exec_loop = 0;
>> +
>> +       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);
>> +
>> +       pair->exec_time_start = (float)tst_timeout_remaining();
>
>
> Here we start to get the whole remain time before reaching timeout
> aborting, and base on that to comparing in tst_fzsync_run_a() to guarantee
> test exit when execute time exceed. That's fine, but it is too early to get
> the time here I guess, because samples collection will also cost some of
> the limitation_time(~30 seconds), and we don't know what proportion the
> sampling occupied in exec_time_p, if it's too much, then there only has
> very little time on race execution.

The race can still happen during the sampling period (although for some
tests it is unlikely).

>
> To avoid this, maybe we should make the limitation time all spend on race
> execution but any on samplings.
> So, I suggest to get pair->exec_time_start value after samples data
> collection in the end of tst_fzsync_pair_update() function.

I don't like the sampling time being bounding only by the overall test
timeout. Users really hate test broken messages. Possibly if the test
timeouts before the sampling period has finished, then we could return
TWARN or TCONF saying that the test did not have enough time to execute?

--
Thank you,
Richard.

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

[Li Wang]

Richard Palethorpe <rpalethorpe@suse.de> wrote:

>
> > Here we start to get the whole remain time before reaching timeout
> > aborting, and base on that to comparing in tst_fzsync_run_a() to
> guarantee
> > test exit when execute time exceed. That's fine, but it is too early to
> get
> > the time here I guess, because samples collection will also cost some of
> > the limitation_time(~30 seconds), and we don't know what proportion the
> > sampling occupied in exec_time_p, if it's too much, then there only has
> > very little time on race execution.
>
> The race can still happen during the sampling period (although for some
> tests it is unlikely).
>

Sounds right.


>
> >
> > To avoid this, maybe we should make the limitation time all spend on race
> > execution but any on samplings.
> > So, I suggest to get pair->exec_time_start value after samples data
> > collection in the end of tst_fzsync_pair_update() function.
>
> I don't like the sampling time being bounding only by the overall test
> timeout. Users really hate test broken messages. Possibly if the test
> timeouts before the sampling period has finished, then we could return
> TWARN or TCONF saying that the test did not have enough time to execute?
>

Sure, that makes users know when timeout occurred, in sampling period or
after, at least good for debugging work sometimes.

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

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

[Cyril Hrubis]

Hi!
> +#define CHK(param, low, hi, def) do {					      \
> +	pair->param = (pair->param ? pair->param : def);		      \
> +	if (pair->param <= low)						      \
> +		tst_brk(TBROK, #param " is less than the lower bound " #low); \
> +	if (pair->param >= hi)						      \
> +		tst_brk(TBROK, #param " is more than the upper bound " #hi);  \
> +	} while (0)

I would kind of expect that given parameter can be set to both low and
hi as well. I guess that it may make sense to exclude the bounds for the
two ratios, from a mathematical point of view, but not so much for
floating point I would say.

>  /**
> - * TST_FZSYNC_PAIR_INIT - Default values for struct tst_fzysnc_pair
> + * Ensures that any Fuzzy Sync parameters are properly set
> + *
> + * @relates tst_fzsync_pair
> + *
> + * Usually called from the setup function, it sets default parameter values or
> + * validates any existing non-defaults.
> + *
> + * @sa tst_fzsync_pair_reset()
>   */
> -#define TST_FZSYNC_PAIR_INIT {	\
> -	.avg_alpha = 0.25,	\
> -	.delay_inc = 1,	        \
> -	.update_gap = 0xF,	\
> -	.info_gap = 0x7FFFF     \
> +static void tst_fzsync_pair_init(struct tst_fzsync_pair *pair)
> +{
> +	CHK(avg_alpha, 0, 1, 0.25);
> +	CHK(min_samples, 20, INT_MAX, 1024);
> +	CHK(max_dev_ratio, 0, 1, 0.1);
> +	CHK(exec_time_p, 0, 1, 0.2);
> +	CHK(exec_loops, 20, INT_MAX, 1000000);
>  }
> +#undef CHK
>  
>  /**
> - * tst_fzsync_pair_info - Print some synchronisation statistics
> + * Exit and join thread B if necessary.
> + *
> + * @relates tst_fzsync_pair
> + *
> + * Call this from your cleanup function.
>   */
> -static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair)
> +static void tst_fzsync_pair_cleanup(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);
> +	if (pair->thread_b) {
> +		tst_atomic_store(1, &pair->exit);
> +		SAFE_PTHREAD_JOIN(pair->thread_b, 0);
                                                  ^
						  This should be NULL
> +		pair->thread_b = 0;
> +	}
>  }
>  
>  /**
> - * tst_fzsync_delay_a - Perform spin delay for A, 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_a(struct tst_fzsync_pair *pair)
> +static void tst_init_stat(struct tst_fzsync_stat *s)
>  {
> -	volatile long spin_delay = pair->delay;
> +	s->avg = 0;
> +	s->avg_dev = 0;
> +}
>  
> -	while (spin_delay > 0)
> -		spin_delay--;
> +/**
> + * 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 (re)set any variables 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.
> + *
> + * @sa tst_fzsync_pair_init()
> + */
> +static void tst_fzsync_pair_reset(struct tst_fzsync_pair *pair,
> +				  void *(*run_b)(void *))
> +{
> +	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->exec_loop = 0;
> +
> +	pair->a_cntr = 0;
> +	pair->b_cntr = 0;
> +	tst_atomic_store(0, &pair->exit);

Do we have to use atomic store here? Aren't we running in a single
thread at this point?

> +	if (run_b)
> +		SAFE_PTHREAD_CREATE(&pair->thread_b, 0, run_b, 0);
> +
> +	pair->exec_time_start = (float)tst_timeout_remaining();
>  }
>  
>  /**
> - * tst_fzsync_delay_b - Perform spin delay for B, if needed
> + * Print stat
>   *
> - * 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 inline void tst_fzsync_stat_info(struct tst_fzsync_stat stat,
> +					char *unit, char *name)
>  {
> -	volatile long spin_delay = pair->delay;
> +	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);
> +}
>  
> -	while (spin_delay < 0)
> -		spin_delay++;
> +/**
> + * Print some synchronisation statistics
> + *
> + * @relates tst_fzsync_pair
> + */
> +static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair)
> +{
> +	tst_res(TINFO, "loop = %d", pair->exec_loop);
> +	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)
>  {
> +#ifdef CLOCK_MONOTONIC_RAW
>  	clock_gettime(CLOCK_MONOTONIC_RAW, t);
> +#else
> +	clock_gettime(CLOCK_MONOTONIC, t);
> +#endif
>  }
>  
>  /**
> - * tst_fzsync_time_a - Set A's time to now.
> + * Exponential moving average
>   *
> - * Called at the point you want to synchronise.
> + * @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
> + *
> + * @return The average including the current sample.
>   */
> -static inline void tst_fzsync_time_a(struct tst_fzsync_pair *pair)
> +static inline float tst_exp_moving_avg(float alpha,
> +					float sample,
> +					float prev_avg)
>  {
> -	tst_fzsync_time(&pair->a);
> +	return alpha * sample + (1.0 - alpha) * prev_avg;
>  }
>  
>  /**
> - * tst_fzsync_time_b - Set B's call time to now.
> + * Update a stat with a new sample
>   *
> - * Called at the point you want to synchronise.
> + * @relates tst_fzsync_stat
>   */
> -static inline void tst_fzsync_time_b(struct tst_fzsync_pair *pair)
> +static inline void tst_upd_stat(struct tst_fzsync_stat *s,
> +				 float alpha,
> +				 float sample)
>  {
> -	tst_fzsync_time(&pair->b);
> +	s->avg = tst_exp_moving_avg(alpha, sample, s->avg);
> +	s->avg_dev = tst_exp_moving_avg(alpha,
> +					5fabs(s->avg - sample), s->avg_dev);
> +	s->dev_ratio = fabs(s->avg ? s->avg_dev / s->avg : 0);
>  }
>  
>  /**
> - * 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
> + * Update a stat with a new diff sample
>   *
> - * Returns average including the current sample.
> + * @relates tst_fzsync_stat
>   */
> -static inline float tst_exp_moving_avg(float alpha,
> -					float sample,
> -					float prev_avg)
> +static inline void tst_upd_diff_stat(struct tst_fzsync_stat *s,
> +				     float alpha,
> +				     struct timespec t1,
> +				     struct timespec t2)
>  {
> -	return alpha * sample + (1.0 - alpha) * prev_avg;
> +	tst_upd_stat(s, alpha, tst_timespec_diff_ns(t1, t2));
>  }
>  
>  /**
> - * 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.
> + * 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.
> + *
> + * The delay range goes from positive to negative. A negative delay will delay
> + * thread A and and positive one will delay thread B. The range is bounded by
> + * the point where the entry code to Syscall A is synchronised with the exit
> + * to Syscall B and the entry code to Syscall B is synchronised with the exit
> + * of A.
> + *
> + * In order to calculate the lower bound (the max delay of A) we can simply
> + * negate the execution time of Syscall B and convert it to a spin count. For
> + * the upper bound (the max delay of B), we just take the execution time of A
> + * and convert it to a spin count.
> + *
> + * In order to calculate spin count we need to know approximately how long a
> + * spin takes and devide the delay time with it. We find this by first
                     ^
		     divide?
> + * counting how many spins one thread spends waiting for the other during
> + * end_race[1]. We also know when each syscall exits so we can take the
> + * difference between the exit times and divde it with the number of spins
                                            ^
					    divide?
> + * spent waiting.
> + *
> + * All the times and counts we use in the calculation are averaged over a
> + * variable number of iterations. There is an initial sampling period where we
> + * simply collect time and count samples then caculate their averages. When a
> + * minimum number of samples have been collected, and if the average deviation
> + * is below some proportion of the average sample magnitude, then the sampling
> + * period is ended. On all further iterations a random delay is calculated and
> + * applied, but the averages are not updated.
> + *
> + * [1] This assumes there is always a significant difference. The algorithm
> + * may fail to introduce a delay (when one is needed) in situations where
> + * Syscall A and B finish at approximately the same time.
> + *
> + * @relates tst_fzsync_pair
>   */

Other than the typos pointed out and minor things this version looks
good to me.

I will try it on an old arm board that has no hadrware timers, i.e. the
clock_gettime() is backed only by jiffies to see how that will behave
and let you know later on.

-- 
Cyril Hrubis
chrubis@suse.cz

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

[Richard Palethorpe]

---
 lib/newlib_tests/test16.c                     | 62 ++++++++++---------
 testcases/cve/cve-2014-0196.c                 | 37 ++++-------
 testcases/cve/cve-2016-7117.c                 | 58 ++++++++---------
 testcases/cve/cve-2017-2671.c                 | 32 ++++------
 testcases/kernel/syscalls/inotify/inotify09.c | 33 ++++------
 .../kernel/syscalls/ipc/shmctl/shmctl05.c     | 30 +++------
 6 files changed, 105 insertions(+), 147 deletions(-)

diff --git a/lib/newlib_tests/test16.c b/lib/newlib_tests/test16.c
index d80bd5369..f453968cd 100644
--- a/lib/newlib_tests/test16.c
+++ b/lib/newlib_tests/test16.c
@@ -27,51 +27,54 @@
 #include "tst_fuzzy_sync.h"
 
 /* LOOPS * 2 + 1 must be less than INT_MAX */
-#define LOOPS 0xFFFFFFULL
+#define LOOPS 0xFFFFULL
 
-static pthread_t thrd;
 static volatile char seq[LOOPS * 2 + 1];
-static struct tst_fzsync_pair pair = TST_FZSYNC_PAIR_INIT;
+static struct tst_fzsync_pair pair;
 static volatile int seq_n;
-static volatile int iterations;
+static volatile char last_wins;
+
+static void setup(void)
+{
+	pair.exec_loops = LOOPS;
+	tst_fzsync_pair_init(&pair);
+}
 
 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))
-			break;
+	for (i = 0; tst_fzsync_run_b(&pair); i++) {
+		tst_fzsync_start_race_b(&pair);
+		usleep(1);
+		last_wins = 'B';
+		tst_fzsync_end_race_b(&pair);
 		seq[seq_n] = 'B';
 		seq_n = (i + 1) * 2 % (int)LOOPS * 2;
 	}
 
-	if (i > LOOPS * iterations)
-		tst_res(TWARN, "Worker performed too many iterations: %lld > %lld",
-			i, LOOPS * iterations);
+	if (i != LOOPS) {
+		tst_res(TFAIL,
+			"Worker performed wrong number of iterations: %lld != %lld",
+			i, LOOPS);
+	}
 
 	return NULL;
 }
 
-static void setup(void)
-{
-	SAFE_PTHREAD_CREATE(&thrd, NULL, worker, NULL);
-}
-
 static void run(void)
 {
-	unsigned int i, j, fail = 0;
+	unsigned int i, j, fail = 0, lost_race = 0;
 
-	for (i = 0; i < LOOPS; i++) {
-		tst_fzsync_wait_update_a(&pair);
-		tst_fzsync_delay_a(&pair);
+	tst_fzsync_pair_reset(&pair, worker);
+	for (i = 0; tst_fzsync_run_a(&pair); i++) {
+		tst_fzsync_start_race_a(&pair);
 		seq[seq_n] = 'A';
 		seq_n = i * 2 + 1;
-		tst_fzsync_time_a(&pair);
-		if (!tst_fzsync_wait_a(&pair))
-			break;
+		last_wins = 'A';
+		tst_fzsync_end_race_a(&pair);
+		if (last_wins == 'B')
+			lost_race++;
 	}
 
 	tst_res(TINFO, "Checking sequence...");
@@ -93,16 +96,15 @@ static void run(void)
 	if (!fail)
 		tst_res(TPASS, "Sequence is correct");
 
-	if (labs(pair.delay) > 1000)
-		tst_res(TFAIL, "Delay is suspiciously large");
-
-	iterations++;
+	if (lost_race < 100)
+		tst_res(TFAIL, "A only lost the race %d times", lost_race);
+	else
+		tst_res(TPASS, "A lost the race %d times", lost_race);
 }
 
 static void cleanup(void)
 {
-	tst_fzsync_pair_exit(&pair);
-	SAFE_PTHREAD_JOIN(thrd, NULL);
+	tst_fzsync_pair_cleanup(&pair);
 }
 
 static struct tst_test test = {
diff --git a/testcases/cve/cve-2014-0196.c b/testcases/cve/cve-2014-0196.c
index d18108897..239ea81b5 100644
--- a/testcases/cve/cve-2014-0196.c
+++ b/testcases/cve/cve-2014-0196.c
@@ -48,7 +48,6 @@
 
 #define ONEOFF_ALLOCS 200
 #define RUN_ALLOCS    30
-#define ATTEMPTS      0x7000
 #define BUFLEN        512
 
 static volatile int master_fd, slave_fd;
@@ -56,9 +55,8 @@ 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;
+static struct tst_fzsync_pair fzsync_pair;
 
 static void create_pty(int *amaster, int *aslave)
 {
@@ -70,27 +68,22 @@ static void setup(void)
 {
 	int i;
 
+	tst_fzsync_pair_init(&fzsync_pair);
+
 	for (i = 0; i < ONEOFF_ALLOCS; i++) {
 		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_run_b(&fzsync_pair)) {
+		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))
-			break;
+		tst_fzsync_end_race_b(&fzsync_pair);
 	}
 	return 0;
 }
@@ -98,11 +91,12 @@ static void *overwrite_thread_fn(void *p LTP_ATTRIBUTE_UNUSED)
 static void run(void)
 {
 	struct termios t;
-	int i, j;
+	int j;
 
 	tst_res(TINFO, "Attempting to overflow into a tty_struct...");
 
-	for (i = 0; i < ATTEMPTS; i++) {
+	tst_fzsync_pair_reset(&fzsync_pair, overwrite_thread_fn);
+	while (tst_fzsync_run_a(&fzsync_pair)) {
 		create_pty((int *)&master_fd, (int *)&slave_fd);
 
 		for (j = 0; j < RUN_ALLOCS; j++)
@@ -118,13 +112,9 @@ static void run(void)
 		t.c_lflag |= ECHO;
 		tcsetattr(master_fd, TCSANOW, &t);
 
-		tst_fzsync_wait_update_a(&fzsync_pair);
-
-		tst_fzsync_delay_a(&fzsync_pair);
-		tst_fzsync_time_a(&fzsync_pair);
+		tst_fzsync_start_race_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 +139,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..f3d9970c3 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"
 
@@ -93,13 +92,12 @@ 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 struct tst_fzsync_pair fzsync_pair;
 static void *send_and_close(void *);
 
 static void setup(void)
 {
-	SAFE_PTHREAD_CREATE(&pt_send, 0, send_and_close, 0);
+	tst_fzsync_pair_init(&fzsync_pair);
 }
 
 static void cleanup(void)
@@ -107,61 +105,63 @@ 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_run_b(&fzsync_pair)) {
+
+		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;
 }
 
 static void run(void)
 {
-	int i, stat, too_early_count = 0;
+	int stat, too_early_count = 0;
 
 	msghdrs[0].msg_hdr.msg_iov->iov_base = (void *)&rbuf;
 
-	for (i = 1; i < ATTEMPTS; i++) {
+	tst_fzsync_pair_reset(&fzsync_pair, send_and_close);
+	while (tst_fzsync_run_a(&fzsync_pair)) {
+
 		if (socketpair(AF_LOCAL, SOCK_DGRAM, 0, (int *)socket_fds))
 			tst_brk(TBROK | TERRNO, "Socket creation failed");
+		tst_fzsync_wait_a(&fzsync_pair);
 
-		tst_fzsync_wait_update_a(&fzsync_pair);
-		tst_fzsync_delay_a(&fzsync_pair);
-
+		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);
-		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_end_race_a(&fzsync_pair);
 
-		tst_fzsync_wait_a(&fzsync_pair);
+		if (stat == 0)
+			tst_res(TWARN, "No messages received, should be one");
+		else if (stat < 0) {
+			if (errno != EBADF) {
+				tst_res(TWARN | TERRNO,
+					"recvmmsg failed unexpectedly");
+			} else {
+				too_early_count++;
+			}
+		}
 	}
 
-	tst_res(TPASS, "Nothing happened after %d attempts", ATTEMPTS);
+	tst_res(TPASS, "Nothing bad happened, probably.");
+	tst_res(TINFO, "Socket was closed too early %d times", too_early_count);
 }
 
 static struct tst_test test = {
-	.setup = setup,
 	.test_all = run,
+	.setup = setup,
 	.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..5bdb37b69 100644
--- a/testcases/cve/cve-2017-2671.c
+++ b/testcases/cve/cve-2017-2671.c
@@ -54,9 +54,8 @@
 
 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 tst_fzsync_pair fzsync_pair;
 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,14 @@ 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...");
+
+	tst_fzsync_pair_init(&fzsync_pair);
 }
 
 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,12 +92,10 @@ 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_run_b(&fzsync_pair)) {
+		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))
-			break;
+		tst_fzsync_end_race_b(&fzsync_pair);
 	}
 
 	return 0;
@@ -109,18 +103,14 @@ static void *connect_b(void * param LTP_ATTRIBUTE_UNUSED)
 
 static void run(void)
 {
-	int i;
-
-	for (i = 0; i < ATTEMPTS; i++) {
+	tst_fzsync_pair_reset(&fzsync_pair, connect_b);
+	while (tst_fzsync_run_a(&fzsync_pair)) {
 		SAFE_CONNECT(sockfd,
 			     (struct sockaddr *)&iaddr, sizeof(iaddr));
 
-		tst_fzsync_wait_update_a(&fzsync_pair);
-		tst_fzsync_delay_a(&fzsync_pair);
+		tst_fzsync_start_race_a(&fzsync_pair);
 		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..f587a3a3c 100644
--- a/testcases/kernel/syscalls/inotify/inotify09.c
+++ b/testcases/kernel/syscalls/inotify/inotify09.c
@@ -46,26 +46,22 @@
 #include "inotify.h"
 
 #define FNAME "stress_fname"
-#define TEARDOWNS 200000
 
 #if defined(HAVE_SYS_INOTIFY_H)
 #include <sys/inotify.h>
 
-static struct tst_fzsync_pair fzsync_pair = TST_FZSYNC_PAIR_INIT;
-static pthread_t pt_write_seek;
+static struct tst_fzsync_pair fzsync_pair;
 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_run_b(&fzsync_pair)) {
+		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))
-			break;
+		tst_fzsync_end_race_b(&fzsync_pair);
 	}
 	return unused;
 }
@@ -73,8 +69,7 @@ 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);
+	tst_fzsync_pair_init(&fzsync_pair);
 }
 
 static void cleanup(void)
@@ -82,35 +77,29 @@ 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)
 {
 	int inotify_fd;
 	int wd;
-	int tests;
 
 	inotify_fd = myinotify_init1(0);
 	if (inotify_fd < 0)
 		tst_brk(TBROK | TERRNO, "inotify_init failed");
-	for (tests = 0; tests < TEARDOWNS; tests++) {
+
+	tst_fzsync_pair_reset(&fzsync_pair, write_seek);
+	while (tst_fzsync_run_a(&fzsync_pair)) {
 		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);
-
+		tst_fzsync_start_race_a(&fzsync_pair);
 		wd = myinotify_rm_watch(inotify_fd, wd);
+		tst_fzsync_end_race_a(&fzsync_pair);
 		if (wd < 0)
 			tst_brk(TBROK | TERRNO, "inotify_rm_watch() failed.");
-
-		tst_fzsync_time_a(&fzsync_pair);
-		tst_fzsync_wait_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 51879c220..ecae202e8 100644
--- a/testcases/kernel/syscalls/ipc/shmctl/shmctl05.c
+++ b/testcases/kernel/syscalls/ipc/shmctl/shmctl05.c
@@ -32,9 +32,7 @@
 #include "tst_safe_sysv_ipc.h"
 #include "tst_timer.h"
 
-static struct tst_fzsync_pair fzsync_pair = TST_FZSYNC_PAIR_INIT;
-
-static pthread_t thrd;
+static struct tst_fzsync_pair fzsync_pair;
 
 /*
  * Thread 2: repeatedly remove the shm ID and reallocate it again for a
@@ -44,54 +42,49 @@ 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_run_b(&fzsync_pair)) {
+		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))
-			break;
+		tst_fzsync_end_race_b(&fzsync_pair);
 	}
 	return unused;
 }
 
 static void setup(void)
 {
-	tst_timer_check(CLOCK_MONOTONIC);
-
 	/* 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);
+	tst_fzsync_pair_init(&fzsync_pair);
 }
 
 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);
+	while (tst_fzsync_run_a(&fzsync_pair)) {
 		int id;
 		void *addr;
 
 		id = SAFE_SHMGET(0xF00F, 4096, IPC_CREAT|0700);
 		addr = SAFE_SHMAT(id, NULL, 0);
-		tst_fzsync_wait_a(&fzsync_pair);
+		tst_fzsync_start_race_a(&fzsync_pair);
 		do {
 			/* This is the system call that crashed */
 			TEST(syscall(__NR_remap_file_pages, addr, 4096,
 				     0, 0, 0));
 		} while (TST_RET == 0);
+		tst_fzsync_end_race_a(&fzsync_pair);
 
 		if (TST_ERR != EIDRM && TST_ERR != EINVAL) {
 			tst_brk(TBROK | TTERRNO,
 				"Unexpected remap_file_pages() error");
 		}
-		tst_fzsync_wait_a(&fzsync_pair);
 
 		/*
 		 * Ensure that a shm segment will actually be destroyed.
@@ -106,10 +99,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

[LTP] [PATCH v2 4/4] Add delay bias for difficult races

[Richard Palethorpe]

Races with short exploitation windows and nonlinear timings, given varying
chronological order, appear to require an offset to the synchronisation to
achieve the correct order so that the average timings are valid for the race
condition.

Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
---
 include/tst_fuzzy_sync.h      | 75 ++++++++++++++++++++++++++++++-----
 testcases/cve/cve-2016-7117.c |  1 +
 2 files changed, 66 insertions(+), 10 deletions(-)

diff --git a/include/tst_fuzzy_sync.h b/include/tst_fuzzy_sync.h
index e38a23fa1..c6dfc2894 100644
--- a/include/tst_fuzzy_sync.h
+++ b/include/tst_fuzzy_sync.h
@@ -132,6 +132,8 @@ struct tst_fzsync_pair {
 	 * A negative value delays thread A and a positive delays thread B.
 	 */
 	int delay;
+	int delay_bias;
+	int discard_flag;
 	/**
 	 *  Internal; The number of samples left or the sampling state.
 	 *
@@ -178,6 +180,10 @@ struct tst_fzsync_pair {
 	/**
 	 * The maximum number of iterations to execute during the test
 	 *
+	 * Note that under normal operation this limit remains constant once
+	 * set, however some special functions, such as
+	 * tst_fzsync_pair_add_bias() may increment this limit.
+	 *
 	 * Defaults to a large number, but not too large.
 	 */
 	int exec_loops;
@@ -241,6 +247,15 @@ static void tst_init_stat(struct tst_fzsync_stat *s)
 	s->avg_dev = 0;
 }
 
+static void tst_fzsync_pair_reset_stats(struct tst_fzsync_pair *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);
+}
+
 /**
  * Reset or initialise fzsync.
  *
@@ -264,13 +279,10 @@ static void tst_fzsync_pair_reset(struct tst_fzsync_pair *pair,
 {
 	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);
+	tst_fzsync_pair_reset_stats(pair);
 	pair->delay = 0;
 	pair->sampling = pair->min_samples;
+	pair->discard_flag = 0;
 
 	pair->exec_loop = 0;
 
@@ -303,7 +315,8 @@ static inline void tst_fzsync_stat_info(struct tst_fzsync_stat stat,
  */
 static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair)
 {
-	tst_res(TINFO, "loop = %d", pair->exec_loop);
+	tst_res(TINFO, "loop = %d, delay_bias = %d",
+		pair->exec_loop, pair->delay_bias);
 	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");
@@ -458,12 +471,20 @@ static void tst_fzsync_pair_update(struct tst_fzsync_pair *pair)
 	float alpha = pair->avg_alpha;
 	float per_spin_time, time_delay, dev_ratio;
 
+	pair->delay = pair->delay_bias;
+
 	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) {
+	if (pair->sampling > 0 && pair->discard_flag) {
+		tst_fzsync_pair_reset_stats(pair);
+		pair->discard_flag = 0;
+		pair->sampling += 20;
+		if (pair->exec_loops <= INT_MAX)
+			pair->exec_loops++;
+	} else 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,
@@ -483,15 +504,15 @@ static void tst_fzsync_pair_update(struct tst_fzsync_pair *pair)
 		per_spin_time = fabsf(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);
+		pair->delay += (int)(time_delay / per_spin_time);
 
 		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));
+				(int)(pair->diff_sb.avg / per_spin_time) + pair->delay_bias,
+				(int)(pair->diff_sa.avg / per_spin_time) - pair->delay_bias);
 			tst_fzsync_pair_info(pair);
 			pair->sampling = -1;
 		}
@@ -702,3 +723,37 @@ static inline void tst_fzsync_end_race_b(struct tst_fzsync_pair *pair)
 	tst_fzsync_time(&pair->b_end);
 	tst_fzsync_pair_wait(&pair->b_cntr, &pair->a_cntr, &pair->spins);
 }
+
+/**
+ * Add some amount to the delay bias
+ *
+ * @relates tst_fzsync_pair
+ * @param change The amount to add, can be negative
+ *
+ * A positive change delays thread B and a negative one delays thread
+ * A. Calling this will invalidate the statistics gathered so far and extend
+ * the minimum sampling period. Calling it once the sampling period has
+ * finished will have no effect.
+ *
+ * It is intended to be used in tests where the time taken by syscall A and/or
+ * B are significantly affected by their chronological order. To the extent
+ * that the delay range will not include the correct values if too many of the
+ * initial samples are taken when the syscalls (or operations within the
+ * syscalls) happen in the wrong order.
+ *
+ * An example of this is cve/cve-2016-7117.c where a call to close() is racing
+ * with a call to recvmmsg(). If close() happens before recvmmsg() has chance
+ * to check if the file descriptor is open then recvmmsg() completes very
+ * quickly. If the call to close() happens once recvmmsg() has already checked
+ * the descriptor it takes much longer. The sample where recvmmsg() completes
+ * quickly is essentially invalid for our purposes. The test uses the simple
+ * heuristic of whether recvmmsg() returns EBADF, to decide if it should call
+ * tst_fzsync_pair_add_bias() to further delay syscall B.
+ */
+static void tst_fzsync_pair_add_bias(struct tst_fzsync_pair *pair, int change)
+{
+	if (pair->sampling > 0) {
+		pair->delay_bias += change;
+		pair->discard_flag = 1;
+	}
+}
diff --git a/testcases/cve/cve-2016-7117.c b/testcases/cve/cve-2016-7117.c
index f3d9970c3..55cfdb05c 100644
--- a/testcases/cve/cve-2016-7117.c
+++ b/testcases/cve/cve-2016-7117.c
@@ -150,6 +150,7 @@ static void run(void)
 				tst_res(TWARN | TERRNO,
 					"recvmmsg failed unexpectedly");
 			} else {
+				tst_fzsync_pair_add_bias(&fzsync_pair, 1);
 				too_early_count++;
 			}
 		}
-- 
2.18.0

[LTP] [PATCH v2 4/4] Add delay bias for difficult races

[Petr Vorel]

Hi Richard,

> Races with short exploitation windows and nonlinear timings, given varying
> chronological order, appear to require an offset to the synchronisation to
> achieve the correct order so that the average timings are valid for the race
> condition.

> Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
> ---

> +static void tst_fzsync_pair_add_bias(struct tst_fzsync_pair *pair, int change)
> +{
> +	if (pair->sampling > 0) {
> +		pair->delay_bias += change;
> +		pair->discard_flag = 1;
> +	}
> +}

Minor warning due being in header and not in C file:
../../../include/tst_fuzzy_sync.h:753:13: warning: ‘tst_fzsync_pair_add_bias’ defined but not used [-Wunused-function]
 static void tst_fzsync_pair_add_bias(struct tst_fzsync_pair *pair, int change)


Kind regards,
Petr

[LTP] [PATCH v2 4/4] Add delay bias for difficult races

[Richard Palethorpe]

Hello,

Petr Vorel <pvorel@suse.cz> writes:

> Hi Richard,
>
>> Races with short exploitation windows and nonlinear timings, given varying
>> chronological order, appear to require an offset to the synchronisation to
>> achieve the correct order so that the average timings are valid for the race
>> condition.
>
>> Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
>> ---
>
>> +static void tst_fzsync_pair_add_bias(struct tst_fzsync_pair *pair, int change)
>> +{
>> +	if (pair->sampling > 0) {
>> +		pair->delay_bias += change;
>> +		pair->discard_flag = 1;
>> +	}
>> +}
>
> Minor warning due being in header and not in C file:
> ../../../include/tst_fuzzy_sync.h:753:13: warning: ‘tst_fzsync_pair_add_bias’ defined but not used [-Wunused-function]
>  static void tst_fzsync_pair_add_bias(struct tst_fzsync_pair *pair, int change)
>
>
> Kind regards,
> Petr

OK, I have added unused attribute to this function for the next version

-- 
Thank you,
Richard.

[LTP] [PATCH v2 4/4] Add delay bias for difficult races

[Cyril Hrubis]

Hi!
> > Minor warning due being in header and not in C file:
> > ../../../include/tst_fuzzy_sync.h:753:13: warning: ???tst_fzsync_pair_add_bias??? defined but not used [-Wunused-function]
> >  static void tst_fzsync_pair_add_bias(struct tst_fzsync_pair *pair, int change)
> >
> >
> > Kind regards,
> > Petr
> 
> OK, I have added unused attribute to this function for the next version

static inline is a canonical way for functions implemented in headers,
that shouldn't produce warnings.

-- 
Cyril Hrubis
chrubis@suse.cz

[LTP] [PATCH v2 4/4] Add delay bias for difficult races

[Cyril Hrubis]

Hi!
> Races with short exploitation windows and nonlinear timings, given varying
> chronological order, appear to require an offset to the synchronisation to
> achieve the correct order so that the average timings are valid for the race
> condition.

The general idea looks good to me, a few comments below.

> Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
> ---
>  include/tst_fuzzy_sync.h      | 75 ++++++++++++++++++++++++++++++-----
>  testcases/cve/cve-2016-7117.c |  1 +
>  2 files changed, 66 insertions(+), 10 deletions(-)
> 
> diff --git a/include/tst_fuzzy_sync.h b/include/tst_fuzzy_sync.h
> index e38a23fa1..c6dfc2894 100644
> --- a/include/tst_fuzzy_sync.h
> +++ b/include/tst_fuzzy_sync.h
> @@ -132,6 +132,8 @@ struct tst_fzsync_pair {
>  	 * A negative value delays thread A and a positive delays thread B.
>  	 */
>  	int delay;
> +	int delay_bias;
> +	int discard_flag;
>  	/**
>  	 *  Internal; The number of samples left or the sampling state.
>  	 *
> @@ -178,6 +180,10 @@ struct tst_fzsync_pair {
>  	/**
>  	 * The maximum number of iterations to execute during the test
>  	 *
> +	 * Note that under normal operation this limit remains constant once
> +	 * set, however some special functions, such as
> +	 * tst_fzsync_pair_add_bias() may increment this limit.
> +	 *
>  	 * Defaults to a large number, but not too large.
>  	 */
>  	int exec_loops;
> @@ -241,6 +247,15 @@ static void tst_init_stat(struct tst_fzsync_stat *s)
>  	s->avg_dev = 0;
>  }
>  
> +static void tst_fzsync_pair_reset_stats(struct tst_fzsync_pair *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);
> +}
> +
>  /**
>   * Reset or initialise fzsync.
>   *
> @@ -264,13 +279,10 @@ static void tst_fzsync_pair_reset(struct tst_fzsync_pair *pair,
>  {
>  	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);
> +	tst_fzsync_pair_reset_stats(pair);
>  	pair->delay = 0;
>  	pair->sampling = pair->min_samples;
> +	pair->discard_flag = 0;
>  
>  	pair->exec_loop = 0;
>  
> @@ -303,7 +315,8 @@ static inline void tst_fzsync_stat_info(struct tst_fzsync_stat stat,
>   */
>  static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair)
>  {
> -	tst_res(TINFO, "loop = %d", pair->exec_loop);
> +	tst_res(TINFO, "loop = %d, delay_bias = %d",
> +		pair->exec_loop, pair->delay_bias);
>  	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");
> @@ -458,12 +471,20 @@ static void tst_fzsync_pair_update(struct tst_fzsync_pair *pair)
>  	float alpha = pair->avg_alpha;
>  	float per_spin_time, time_delay, dev_ratio;
>  
> +	pair->delay = pair->delay_bias;
> +
>  	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) {
> +	if (pair->sampling > 0 && pair->discard_flag) {
> +		tst_fzsync_pair_reset_stats(pair);
> +		pair->discard_flag = 0;
> +		pair->sampling += 20;

Why += 20 here?

I'm afraid that this will grow too big, i.e. for each loop that attempts
to sample the rate we will add 20 to the minimal sampling count.

Shouldn't we simply reset the sampling counter here, i.e.
pair->sampling = pair->min_samples as we do in the reset? Or even better
shouldn't that be done in the tst_fszync_pair_reset_stats()?

> +		if (pair->exec_loops <= INT_MAX)
> +			pair->exec_loops++;
> +	} else 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,
> @@ -483,15 +504,15 @@ static void tst_fzsync_pair_update(struct tst_fzsync_pair *pair)
>  		per_spin_time = fabsf(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);
> +		pair->delay += (int)(time_delay / per_spin_time);


I've been puzzled by this for a while then I noticed that we do
pair->delay = pair->delay_bias at the start of this function. Shouldn't
it be cleaner if we did just:

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

here?

>  		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));
> +				(int)(pair->diff_sb.avg / per_spin_time) + pair->delay_bias,
> +				(int)(pair->diff_sa.avg / per_spin_time) - pair->delay_bias);
>  			tst_fzsync_pair_info(pair);
>  			pair->sampling = -1;
>  		}
> @@ -702,3 +723,37 @@ static inline void tst_fzsync_end_race_b(struct tst_fzsync_pair *pair)
>  	tst_fzsync_time(&pair->b_end);
>  	tst_fzsync_pair_wait(&pair->b_cntr, &pair->a_cntr, &pair->spins);
>  }
> +
> +/**
> + * Add some amount to the delay bias
> + *
> + * @relates tst_fzsync_pair
> + * @param change The amount to add, can be negative
> + *
> + * A positive change delays thread B and a negative one delays thread
> + * A. Calling this will invalidate the statistics gathered so far and extend
> + * the minimum sampling period. Calling it once the sampling period has
> + * finished will have no effect.
> + *
> + * It is intended to be used in tests where the time taken by syscall A and/or
> + * B are significantly affected by their chronological order. To the extent
> + * that the delay range will not include the correct values if too many of the
> + * initial samples are taken when the syscalls (or operations within the
> + * syscalls) happen in the wrong order.
> + *
> + * An example of this is cve/cve-2016-7117.c where a call to close() is racing
> + * with a call to recvmmsg(). If close() happens before recvmmsg() has chance
> + * to check if the file descriptor is open then recvmmsg() completes very
> + * quickly. If the call to close() happens once recvmmsg() has already checked
> + * the descriptor it takes much longer. The sample where recvmmsg() completes
> + * quickly is essentially invalid for our purposes. The test uses the simple
> + * heuristic of whether recvmmsg() returns EBADF, to decide if it should call
> + * tst_fzsync_pair_add_bias() to further delay syscall B.
> + */
> +static void tst_fzsync_pair_add_bias(struct tst_fzsync_pair *pair, int change)
> +{
> +	if (pair->sampling > 0) {
> +		pair->delay_bias += change;
> +		pair->discard_flag = 1;
> +	}
> +}
> diff --git a/testcases/cve/cve-2016-7117.c b/testcases/cve/cve-2016-7117.c
> index f3d9970c3..55cfdb05c 100644
> --- a/testcases/cve/cve-2016-7117.c
> +++ b/testcases/cve/cve-2016-7117.c
> @@ -150,6 +150,7 @@ static void run(void)
>  				tst_res(TWARN | TERRNO,
>  					"recvmmsg failed unexpectedly");
>  			} else {
> +				tst_fzsync_pair_add_bias(&fzsync_pair, 1);
>  				too_early_count++;
>  			}
>  		}
> -- 
> 2.18.0
> 
> 
> -- 
> Mailing list info: https://lists.linux.it/listinfo/ltp

-- 
Cyril Hrubis
chrubis@suse.cz

[LTP] [PATCH v2 4/4] Add delay bias for difficult races

[Richard Palethorpe]

Hello,

Cyril Hrubis <chrubis@suse.cz> writes:

> Hi!
>> Races with short exploitation windows and nonlinear timings, given varying
>> chronological order, appear to require an offset to the synchronisation to
>> achieve the correct order so that the average timings are valid for the race
>> condition.
>
> The general idea looks good to me, a few comments below.
>
>> Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
>> ---
>>  include/tst_fuzzy_sync.h      | 75 ++++++++++++++++++++++++++++++-----
>>  testcases/cve/cve-2016-7117.c |  1 +
>>  2 files changed, 66 insertions(+), 10 deletions(-)
>>
>> diff --git a/include/tst_fuzzy_sync.h b/include/tst_fuzzy_sync.h
>> index e38a23fa1..c6dfc2894 100644
>> --- a/include/tst_fuzzy_sync.h
>> +++ b/include/tst_fuzzy_sync.h
>> @@ -132,6 +132,8 @@ struct tst_fzsync_pair {
>>  	 * A negative value delays thread A and a positive delays thread B.
>>  	 */
>>  	int delay;
>> +	int delay_bias;
>> +	int discard_flag;
>>  	/**
>>  	 *  Internal; The number of samples left or the sampling state.
>>  	 *
>> @@ -178,6 +180,10 @@ struct tst_fzsync_pair {
>>  	/**
>>  	 * The maximum number of iterations to execute during the test
>>  	 *
>> +	 * Note that under normal operation this limit remains constant once
>> +	 * set, however some special functions, such as
>> +	 * tst_fzsync_pair_add_bias() may increment this limit.
>> +	 *
>>  	 * Defaults to a large number, but not too large.
>>  	 */
>>  	int exec_loops;
>> @@ -241,6 +247,15 @@ static void tst_init_stat(struct tst_fzsync_stat *s)
>>  	s->avg_dev = 0;
>>  }
>>
>> +static void tst_fzsync_pair_reset_stats(struct tst_fzsync_pair *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);
>> +}
>> +
>>  /**
>>   * Reset or initialise fzsync.
>>   *
>> @@ -264,13 +279,10 @@ static void tst_fzsync_pair_reset(struct tst_fzsync_pair *pair,
>>  {
>>  	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);
>> +	tst_fzsync_pair_reset_stats(pair);
>>  	pair->delay = 0;
>>  	pair->sampling = pair->min_samples;
>> +	pair->discard_flag = 0;
>>
>>  	pair->exec_loop = 0;
>>
>> @@ -303,7 +315,8 @@ static inline void tst_fzsync_stat_info(struct tst_fzsync_stat stat,
>>   */
>>  static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair)
>>  {
>> -	tst_res(TINFO, "loop = %d", pair->exec_loop);
>> +	tst_res(TINFO, "loop = %d, delay_bias = %d",
>> +		pair->exec_loop, pair->delay_bias);
>>  	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");
>> @@ -458,12 +471,20 @@ static void tst_fzsync_pair_update(struct tst_fzsync_pair *pair)
>>  	float alpha = pair->avg_alpha;
>>  	float per_spin_time, time_delay, dev_ratio;
>>
>> +	pair->delay = pair->delay_bias;
>> +
>>  	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) {
>> +	if (pair->sampling > 0 && pair->discard_flag) {
>> +		tst_fzsync_pair_reset_stats(pair);
>> +		pair->discard_flag = 0;
>> +		pair->sampling += 20;
>
> Why += 20 here?

I vaguely remember that 20 is a statistically 'large' sample size and it
seemed appropriate to ensure we had at least 20 samples after a reset.

>
> I'm afraid that this will grow too big, i.e. for each loop that attempts
> to sample the rate we will add 20 to the minimal sampling count.
>
> Shouldn't we simply reset the sampling counter here, i.e.
> pair->sampling = pair->min_samples as we do in the reset? Or even better
> shouldn't that be done in the tst_fszync_pair_reset_stats()?

Resetting the sampling altogether extended the sample period too much in
my testing. Although I can see why it would be safer.

However maybe I should just remove the reset altogether and rely on the
moving average to 'forget' the earlier samples before we reach the
minimum sampling period. I will try testing it and see what difference
it makes.

>
>> +		if (pair->exec_loops <= INT_MAX)
>> +			pair->exec_loops++;
>> +	} else 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,
>> @@ -483,15 +504,15 @@ static void tst_fzsync_pair_update(struct tst_fzsync_pair *pair)
>>  		per_spin_time = fabsf(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);
>> +		pair->delay += (int)(time_delay / per_spin_time);
>
>
> I've been puzzled by this for a while then I noticed that we do
> pair->delay = pair->delay_bias at the start of this function. Shouldn't
> it be cleaner if we did just:
>
> pair->delay = pair->delay_bias + (int)(time_delay / per_spin_time);
>
> here?

The delay bias needs to be applied during the sampling period as well or
if the algorithm abandons trying to calculate a delay (i.e. for all the
'if' statement's branches).

So we would need to add the bias in every branch. I guess this is maybe
a bit confusing because the delay is described as only taking effect
after the sampling period completes. However we must apply the delay
bias during sampling so that we get a feedback loop where the test can
judge whether to add more bias.

>
>>  		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));
>> +				(int)(pair->diff_sb.avg / per_spin_time) + pair->delay_bias,
>> +				(int)(pair->diff_sa.avg / per_spin_time) - pair->delay_bias);
>>  			tst_fzsync_pair_info(pair);
>>  			pair->sampling = -1;
>>  		}
>> @@ -702,3 +723,37 @@ static inline void tst_fzsync_end_race_b(struct tst_fzsync_pair *pair)
>>  	tst_fzsync_time(&pair->b_end);
>>  	tst_fzsync_pair_wait(&pair->b_cntr, &pair->a_cntr, &pair->spins);
>>  }
>> +
>> +/**
>> + * Add some amount to the delay bias
>> + *
>> + * @relates tst_fzsync_pair
>> + * @param change The amount to add, can be negative
>> + *
>> + * A positive change delays thread B and a negative one delays thread
>> + * A. Calling this will invalidate the statistics gathered so far and extend
>> + * the minimum sampling period. Calling it once the sampling period has
>> + * finished will have no effect.
>> + *
>> + * It is intended to be used in tests where the time taken by syscall A and/or
>> + * B are significantly affected by their chronological order. To the extent
>> + * that the delay range will not include the correct values if too many of the
>> + * initial samples are taken when the syscalls (or operations within the
>> + * syscalls) happen in the wrong order.
>> + *
>> + * An example of this is cve/cve-2016-7117.c where a call to close() is racing
>> + * with a call to recvmmsg(). If close() happens before recvmmsg() has chance
>> + * to check if the file descriptor is open then recvmmsg() completes very
>> + * quickly. If the call to close() happens once recvmmsg() has already checked
>> + * the descriptor it takes much longer. The sample where recvmmsg() completes
>> + * quickly is essentially invalid for our purposes. The test uses the simple
>> + * heuristic of whether recvmmsg() returns EBADF, to decide if it should call
>> + * tst_fzsync_pair_add_bias() to further delay syscall B.
>> + */
>> +static void tst_fzsync_pair_add_bias(struct tst_fzsync_pair *pair, int change)
>> +{
>> +	if (pair->sampling > 0) {
>> +		pair->delay_bias += change;
>> +		pair->discard_flag = 1;
>> +	}
>> +}
>> diff --git a/testcases/cve/cve-2016-7117.c b/testcases/cve/cve-2016-7117.c
>> index f3d9970c3..55cfdb05c 100644
>> --- a/testcases/cve/cve-2016-7117.c
>> +++ b/testcases/cve/cve-2016-7117.c
>> @@ -150,6 +150,7 @@ static void run(void)
>>  				tst_res(TWARN | TERRNO,
>>  					"recvmmsg failed unexpectedly");
>>  			} else {
>> +				tst_fzsync_pair_add_bias(&fzsync_pair, 1);
>>  				too_early_count++;
>>  			}
>>  		}
>> --
>> 2.18.0
>>
>>
>> --
>> Mailing list info: https://lists.linux.it/listinfo/ltp


--
Thank you,
Richard.