[LTP] [PATCH v2 0/7] Fuzzy Sync single core support and tests

[LTP] [PATCH v2 0/7] Fuzzy Sync single core support and tests

[Richard Palethorpe]

Hello,

V2:
* Add tst_ncpus_available() to API
* Don't use CHK macro for yield_in_wait to prevent compiler warnings
* Simplify and split the test in two

I'm reasonably confident of the first tests correctness. The second is
maybe not complete and more formal analyses is needed IMO. I suspect
also that we can remove add_delay_bias and implement randomised
probing instead. The more I think about it the more clear it becomes,
but it may require some bigger changes to how we calculate and
introduce the delays.

Occasionally some tests may not reach the lower threshold and fail. It
may be caused by changes in the environment between the measuring and
delay implementation phases. This is also something which could be
investigated.

Anyway this is all still very time consuming and making it perform
well on single core is most important right now.

Leo Yu-Chi Liang (1):
  fzsync: Add sched_yield for single core machine

Richard Palethorpe (6):
  fzsync: Add self tests
  fzsync: Reset delay bias
  fzsync: Correctly print positive lower delay range bound
  fzsync: Move yield check out of loop and add yield to delay
  API: Add tst_ncpus_available
  fzsync: Check processor affinity

 include/tst_cpu.h                   |   1 +
 include/tst_fuzzy_sync.h            | 106 ++++++++++---
 lib/newlib_tests/.gitignore         |   2 +
 lib/newlib_tests/test16.c           |   2 +
 lib/newlib_tests/tst_fuzzy_sync01.c | 232 ++++++++++++++++++++++++++++
 lib/newlib_tests/tst_fuzzy_sync02.c | 179 +++++++++++++++++++++
 lib/tst_cpu.c                       |  23 +++
 7 files changed, 521 insertions(+), 24 deletions(-)
 create mode 100644 lib/newlib_tests/tst_fuzzy_sync01.c
 create mode 100644 lib/newlib_tests/tst_fuzzy_sync02.c

-- 
2.30.1

[LTP] [PATCH v2 1/7] fzsync: Add self tests

[Richard Palethorpe]

Add validation tests for the Fuzzy Sync library. They have a range of
data races which Fuzzy Sync must reproduce. This is much easier to
setup and run than reproducing real kernel bugs.

We don't explicitly cover races where there is a large amount of
volatility in the timings. This can be simulated by running the tests
in parallel. However it is not really a concern as a high level of
volatility should make the delay phase redundant.

We also don't cover every possible combination of parameters. We test
every unique category of race as identified by the order of critical
sections. Additionally we test variations to the timings, but not much
more.

Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
Suggested-by: Cyril Hrubis <chrubis@suse.cz>
---
 lib/newlib_tests/.gitignore         |   2 +
 lib/newlib_tests/test16.c           |   2 +
 lib/newlib_tests/tst_fuzzy_sync01.c | 232 ++++++++++++++++++++++++++++
 lib/newlib_tests/tst_fuzzy_sync02.c | 179 +++++++++++++++++++++
 4 files changed, 415 insertions(+)
 create mode 100644 lib/newlib_tests/tst_fuzzy_sync01.c
 create mode 100644 lib/newlib_tests/tst_fuzzy_sync02.c

diff --git a/lib/newlib_tests/.gitignore b/lib/newlib_tests/.gitignore
index 6c2612259..bebecad8b 100644
--- a/lib/newlib_tests/.gitignore
+++ b/lib/newlib_tests/.gitignore
@@ -40,3 +40,5 @@ tst_bool_expr
 test_macros01
 test_macros02
 test_macros03
+tst_fuzzy_sync01
+tst_fuzzy_sync02
diff --git a/lib/newlib_tests/test16.c b/lib/newlib_tests/test16.c
index 0d74e1eae..7a9b5f20e 100644
--- a/lib/newlib_tests/test16.c
+++ b/lib/newlib_tests/test16.c
@@ -9,6 +9,8 @@
  * which they should take it in turns to update.
  */
 
+#define _GNU_SOURCE
+
 #include <stdlib.h>
 #include "tst_test.h"
 #include "tst_safe_pthread.h"
diff --git a/lib/newlib_tests/tst_fuzzy_sync01.c b/lib/newlib_tests/tst_fuzzy_sync01.c
new file mode 100644
index 000000000..8db102bdc
--- /dev/null
+++ b/lib/newlib_tests/tst_fuzzy_sync01.c
@@ -0,0 +1,232 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Copyright (c) 2021 Richard Palethorpe <rpalethorpe@suse.com>
+ */
+/*\
+ * [DESCRIPTION]
+ *
+ * This verifies Fuzzy Sync's basic ability to reproduce a particular
+ * outcome to a data race when the critical sections are not aligned.
+ *
+ * We make the simplifying assumptions that:
+ * - Each thread contains a single contiguous critical section.
+ * - The threads only interact through a single variable.
+ * - The various timings are constant except for variations introduced
+ *   by the environment.
+ *
+ * If a single data race has N critical sections then we may remove
+ * N-1 sections to produce a more difficult race. We may then test
+ * only the more difficult race and induce from this the outcome of
+ * testing the easier races.
+ *
+ * In real code, the threads may interact through many side
+ * effects. While some of these side effects may not result in a bug,
+ * they may effect the total time it takes to execute either
+ * thread. This will be handled in tst_fuzzy_sync02.
+ *
+ * The number of variables which two threads interact through is
+ * irrelevant as the combined state of two variables can be
+ * represented with a single variable. We may also reduce the number
+ * of states to simply those required to show the thread is inside or
+ * outside of the critical section.
+ *
+ * There are two fundamental races which require alignment under these
+ * assumptions:
+ *      1        2
+ * A +-----+  +----+	The outer box is total execution time.
+ *   | #   |  | #  |	The '#' is the critical section.
+ *
+ *   |  # |   |   # |
+ * B +----+   +-----+
+ *
+ * So we can either have the critical section of the shorter race
+ * before that of the longer one. Or the critical section of the
+ * longer one before the shorter.
+ *
+ * In reality both threads will never be the same length, but we can
+ * test that anyway. We also test with both A as the shorter and B as
+ * the shorter. We also vary the distance of the critical section from
+ * the start or end. The delay times are cubed to ensure that a delay
+ * range is required.
+ *
+ * When entering their critical sections, both threads increment the
+ * 'c' counter variable atomically. They both also increment it when
+ * leaving their critical sections. We record the value of 'c' when A
+ * increments it. From the recorded values of 'c' we can deduce if the
+ * critical sections overlap and their ordering.
+ *
+ * 	Start (cs)	| End (ct)	| Ordering
+ * 	--------------------------------------------
+ * 	1		| 2		| A before B
+ * 	3		| 4		| B before A
+ *
+ * Any other combination of 'cs' and 'ct' means the critical sections
+ * overlapped.
+\*/
+
+#define _GNU_SOURCE
+
+#include "tst_test.h"
+#include "tst_fuzzy_sync.h"
+
+#define TIME_SCALE(x) ((x) * (x) * (x))
+
+/* The time signature of a code path containing a critical section. */
+struct window {
+	/* The delay until the start of the critical section */
+	const int critical_s;
+	/* The length of the critical section */
+	const int critical_t;
+	/* The remaining delay until the method returns */
+	const int return_t;
+};
+
+/* The time signatures of threads A and B */
+struct race {
+	const struct window a;
+	const struct window b;
+};
+
+static int c;
+static struct tst_fzsync_pair pair;
+
+static const struct race races[] = {
+	/* Degnerate cases where the critical sections are already
+	 * aligned. The first case will fail when ncpu < 2 as a yield
+	 * inside the critical section is required for the other
+	 * thread to run.
+	 */
+	{ .a = { 0, 0, 0 }, .b = { 0, 0, 0 } },
+	{ .a = { 0, 1, 0 }, .b = { 0, 1, 0 } },
+	{ .a = { 1, 1, 1 }, .b = { 1, 1, 1 } },
+	{ .a = { 3, 1, 1 }, .b = { 3, 1, 1 } },
+
+	/* Both windows are the same length */
+	{ .a = { 3, 1, 1 }, .b = { 1, 1, 3 } },
+	{ .a = { 1, 1, 3 }, .b = { 3, 1, 1 } },
+
+	/* Different sized windows */
+	{ .a = { 3, 1, 1 }, .b = { 1, 1, 2 } },
+	{ .a = { 1, 1, 3 }, .b = { 2, 1, 1 } },
+	{ .a = { 2, 1, 1 }, .b = { 1, 1, 3 } },
+	{ .a = { 1, 1, 2 }, .b = { 3, 1, 1 } },
+
+	/* Same as above, but with critical section@entry or exit */
+	{ .a = { 3, 1, 0 }, .b = { 0, 1, 3 } },
+	{ .a = { 0, 1, 3 }, .b = { 3, 1, 0 } },
+
+	{ .a = { 3, 1, 0 }, .b = { 0, 1, 2 } },
+	{ .a = { 0, 1, 3 }, .b = { 2, 1, 0 } },
+	{ .a = { 2, 1, 0 }, .b = { 0, 1, 3 } },
+	{ .a = { 0, 1, 2 }, .b = { 3, 1, 0 } },
+
+	/* One side is very short */
+	{ .a = { 3, 1, 1 }, .b = { 0, 1, 0 } },
+	{ .a = { 1, 1, 3 }, .b = { 0, 1, 0 } },
+	{ .a = { 0, 1, 0 }, .b = { 1, 1, 3 } },
+	{ .a = { 0, 1, 0 }, .b = { 3, 1, 1 } },
+
+	{ .a = { 3, 1, 1 }, .b = { 0, 0, 0 } },
+	{ .a = { 1, 1, 3 }, .b = { 0, 0, 0 } },
+	{ .a = { 0, 0, 0 }, .b = { 1, 1, 3 } },
+	{ .a = { 0, 0, 0 }, .b = { 3, 1, 1 } },
+
+};
+
+static void cleanup(void)
+{
+	tst_fzsync_pair_cleanup(&pair);
+}
+
+static void setup(void)
+{
+	pair.min_samples = 10000;
+
+	tst_fzsync_pair_init(&pair);
+}
+
+static void delay(const int t)
+{
+	int k = TIME_SCALE(t);
+
+	while (k--)
+		sched_yield();
+}
+
+static void *worker(void *v)
+{
+	unsigned int i = *(unsigned int *)v;
+	const struct window b = races[i].b;
+
+	while (tst_fzsync_run_b(&pair)) {
+		if (tst_atomic_load(&c))
+			tst_brk(TBROK, "Counter should now be zero");
+
+		tst_fzsync_start_race_b(&pair);
+		delay(b.critical_s);
+
+		tst_atomic_add_return(1, &c);
+		delay(b.critical_t);
+		tst_atomic_add_return(1, &c);
+
+		delay(b.return_t);
+		tst_fzsync_end_race_b(&pair);
+	}
+
+	return NULL;
+}
+
+static void run(unsigned int i)
+{
+	const struct window a = races[i].a;
+	struct tst_fzsync_run_thread wrap_run_b = {
+		.func = worker,
+		.arg = &i,
+	};
+	int cs, ct, r, too_early = 0, critical = 0, too_late = 0;
+
+	tst_fzsync_pair_reset(&pair, NULL);
+	SAFE_PTHREAD_CREATE(&pair.thread_b, 0, tst_fzsync_thread_wrapper,
+			    &wrap_run_b);
+
+	while (tst_fzsync_run_a(&pair)) {
+
+		tst_fzsync_start_race_a(&pair);
+		delay(a.critical_s);
+
+		cs = tst_atomic_add_return(1, &c);
+		delay(a.critical_t);
+		ct = tst_atomic_add_return(1, &c);
+
+		delay(a.return_t);
+		tst_fzsync_end_race_a(&pair);
+
+		if (cs == 1 && ct == 2)
+			too_early++;
+		else if (cs == 3 && ct == 4)
+			too_late++;
+		else
+			critical++;
+
+		r = tst_atomic_add_return(-4, &c);
+		if (r)
+			tst_brk(TBROK, "cs = %d, ct = %d, r = %d", cs, ct, r);
+
+		if (critical > 100) {
+			tst_fzsync_pair_cleanup(&pair);
+			break;
+		}
+	}
+
+	tst_res(critical > 50 ? TPASS : TFAIL,
+		"cs:%-2d ct:%-2d rt:%-2d | =:%-4d -:%-4d +:%-4d",
+		a.critical_s, a.critical_t, a.return_t,
+		critical, too_early, too_late);
+}
+
+static struct tst_test test = {
+	.tcnt = ARRAY_SIZE(races),
+	.test = run,
+	.setup = setup,
+	.cleanup = cleanup,
+};
diff --git a/lib/newlib_tests/tst_fuzzy_sync02.c b/lib/newlib_tests/tst_fuzzy_sync02.c
new file mode 100644
index 000000000..22ac539b5
--- /dev/null
+++ b/lib/newlib_tests/tst_fuzzy_sync02.c
@@ -0,0 +1,179 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Copyright (c) 2021 Richard Palethorpe <rpalethorpe@suse.com>
+ */
+/*\
+ * [DESCRIPTION]
+ *
+ * This verifies Fuzzy Sync's ability to reproduce a particular
+ * outcome to a data race when multiple races are present.
+ *
+ * We make the simplifying assumptions that:
+ * - There is one data race we want to hit and one to avoid.
+ * - Each thread contains two contiguous critical sections. One for each race.
+ * - The threads only interact through two variables, one for each race.
+ * - If we hit the race we want to avoid then it causes thread A to exit early.
+ *
+ * We don't consider more complicated dynamic interactions between the
+ * two threads. Fuzzy Sync will eventually trigger a race so long as
+ * the delay range is large enough. Assuming the race is possible to
+ * reproduce without further tampering to increase the race window (a
+ * technique specific to each race). So I conject that beyond a lower
+ * threshold of complexity, increasing the complexity of the race is
+ * no different from adding random noise.
+ *
+ * Emperically this appears to be true. So far we have seen in
+ * reproducers that there are no more than two significant data
+ * races. One we wish to reproduce and one we wish to avoid. It is
+ * possible that the code contains multiple data races, but that they
+ * appear only as two to us.
+ *
+ * Indeed it is also only possible to add a delay to A or B. So
+ * regardless of the underlying complexity we really only have two
+ * options.
+ *
+ * Here we only test a bias to delay B. A delay of A would be
+ * identical except that the necessary delay bias would be negative.
+ *
+\*/
+
+#define _GNU_SOURCE
+
+#include "tst_test.h"
+#include "tst_fuzzy_sync.h"
+
+/* The time signature of a code path containing a critical section. */
+struct window {
+	/* The delay until the start of the critical section */
+	const int critical_s;
+	/* The length of the critical section */
+	const int critical_t;
+	/* The remaining delay until the method returns */
+	const int return_t;
+};
+
+/* The time signatures of threads A and B. We interlace the two
+ * windows for each thread. bd.return_t is ignored, but ad.return_t is
+ * used instead of a.return_t if the ad and bd critical sections
+ * overlap. This may result in the critical section of a never being
+ * reached.
+ */
+struct race {
+	const struct window ad;
+	const struct window a;
+	const struct window bd;
+	const struct window b;
+};
+
+static int c, d;
+static struct tst_fzsync_pair pair;
+
+static const struct race races[] = {
+	{ .a =  { 1, 1, 1 }, .b =  { 1, 1, 1 },
+	  .ad = { 0, 1, 0 }, .bd = { 0, 1, 0 } },
+	{ .a =  { 30, 1, 1 }, .b =  { 1, 1,  1 },
+	  .ad = { 0,  1, 0 }, .bd = { 0, 20, 0 } },
+	{ .a =  { 40, 1,  0 }, .b =  { 1, 1,  20 },
+	  .ad = { 1,  10, 0 }, .bd = { 1, 10, 0 } },
+};
+
+static void cleanup(void)
+{
+	tst_fzsync_pair_cleanup(&pair);
+}
+
+static void setup(void)
+{
+	pair.min_samples = 10000;
+
+	tst_fzsync_pair_init(&pair);
+}
+
+static struct window to_abs(const struct window w)
+{
+	const struct window wc = {
+		w.critical_s,
+		w.critical_s + w.critical_t,
+		w.critical_s + w.critical_t + w.return_t,
+	};
+
+	return wc;
+}
+
+static void *worker(void *v)
+{
+	unsigned int i = *(unsigned int *)v;
+	const struct window b = to_abs(races[i].b);
+	const struct window bd = to_abs(races[i].bd);
+	int now, fin = MAX(b.return_t, bd.return_t);
+
+	while (tst_fzsync_run_b(&pair)) {
+		tst_fzsync_start_race_b(&pair);
+		for (now = 0; now <= fin; now++) {
+			if (now == b.critical_s || now == b.critical_t)
+				tst_atomic_add_return(1, &c);
+			if (now == bd.critical_s || now == bd.critical_t)
+				tst_atomic_add_return(1, &d);
+
+			sched_yield();
+		}
+		tst_fzsync_end_race_b(&pair);
+	}
+
+	return NULL;
+}
+
+static void run(unsigned int i)
+{
+	const struct window a = to_abs(races[i].a);
+	const struct window ad = to_abs(races[i].ad);
+	struct tst_fzsync_run_thread wrap_run_b = {
+		.func = worker,
+		.arg = &i,
+	};
+	int critical = 0;
+	int now, fin;
+
+	tst_fzsync_pair_reset(&pair, NULL);
+	SAFE_PTHREAD_CREATE(&pair.thread_b, 0, tst_fzsync_thread_wrapper,
+			    &wrap_run_b);
+
+	while (tst_fzsync_run_a(&pair)) {
+		c = 0;
+		d = 0;
+		fin = a.return_t;
+
+		tst_fzsync_start_race_a(&pair);
+		for (now = 0; now <= fin; now++) {
+			if (now >= ad.critical_s &&
+			    now <= ad.critical_t && tst_atomic_load(&d) > 0)
+				fin = ad.return_t;
+
+			if (now >= a.critical_s &&
+			    now <= a.critical_t && tst_atomic_load(&c) == 1) {
+				tst_atomic_add_return(1, &c);
+				critical++;
+			}
+
+			sched_yield();
+		}
+		tst_fzsync_end_race_a(&pair);
+
+		if (fin == ad.return_t)
+			tst_fzsync_pair_add_bias(&pair, 1);
+
+		if (critical > 100) {
+			tst_fzsync_pair_cleanup(&pair);
+			break;
+		}
+	}
+
+	tst_res(critical > 50 ? TPASS : TFAIL, "%d| =:%-4d", i, critical);
+}
+
+static struct tst_test test = {
+	.tcnt = ARRAY_SIZE(races),
+	.test = run,
+	.setup = setup,
+	.cleanup = cleanup,
+};
-- 
2.30.1

[LTP] [PATCH v2 1/7] fzsync: Add self tests

[Petr Vorel]

Hi Richie,

FYI this commit fails due
/usr/bin/ld: /tmp/ccBD0Mxi.o: in function `tst_fzsync_pair_cleanup':
/home/pevik/install/src/ltp.git/lib/newlib_tests/../../include/tst_fuzzy_sync.h:226: undefined reference to `pthread_cancel'
/usr/bin/ld: /home/pevik/install/src/ltp.git/lib/newlib_tests/../../include/tst_fuzzy_sync.h:226: undefined reference to `pthread_cancel'
/usr/bin/ld: ../../lib/libltp.a(safe_pthread.o): in function `safe_pthread_create':
/home/pevik/install/src/ltp.git/lib/safe_pthread.c:18: undefined reference to `pthread_create'
/usr/bin/ld: ../../lib/libltp.a(safe_pthread.o): in function `safe_pthread_join':
/home/pevik/install/src/ltp.git/lib/safe_pthread.c:34: undefined reference to `pthread_join'
collect2: error: ld returned 1 exit status
make[1]: *** [../../include/mk/rules.mk:37: tst_fuzzy_sync01] Error 1
make: *** [../include/mk/generic_trunk_target.inc:105: all] Error 2

lib/newlib_tests/Makefile needs to add:
tst_fuzzy_sync01: CFLAGS+=-pthread
tst_fuzzy_sync02: CFLAGS+=-pthread

Kind regards,
Petr

[LTP] [PATCH v2 1/7] fzsync: Add self tests

[Richard Palethorpe]

Hello,

Petr Vorel <pvorel@suse.cz> writes:

> Hi Richie,
>
> FYI this commit fails due
> /usr/bin/ld: /tmp/ccBD0Mxi.o: in function `tst_fzsync_pair_cleanup':
> /home/pevik/install/src/ltp.git/lib/newlib_tests/../../include/tst_fuzzy_sync.h:226: undefined reference to `pthread_cancel'
> /usr/bin/ld: /home/pevik/install/src/ltp.git/lib/newlib_tests/../../include/tst_fuzzy_sync.h:226: undefined reference to `pthread_cancel'
> /usr/bin/ld: ../../lib/libltp.a(safe_pthread.o): in function `safe_pthread_create':
> /home/pevik/install/src/ltp.git/lib/safe_pthread.c:18: undefined reference to `pthread_create'
> /usr/bin/ld: ../../lib/libltp.a(safe_pthread.o): in function `safe_pthread_join':
> /home/pevik/install/src/ltp.git/lib/safe_pthread.c:34: undefined reference to `pthread_join'
> collect2: error: ld returned 1 exit status
> make[1]: *** [../../include/mk/rules.mk:37: tst_fuzzy_sync01] Error 1
> make: *** [../include/mk/generic_trunk_target.inc:105: all] Error 2
>
> lib/newlib_tests/Makefile needs to add:
> tst_fuzzy_sync01: CFLAGS+=-pthread
> tst_fuzzy_sync02: CFLAGS+=-pthread
>
> Kind regards,
> Petr

Ah, I really should compile with GCC as well as Clang!


-- 
Thank you,
Richard.

[LTP] [PATCH v2 2/7] fzsync: Reset delay bias

[Richard Palethorpe]

If the delay bias a preserved then it breaks tests which have multiple
scenarios and/or use -i. The test author could reset it manually in
this case, but it's likely to be error prone.

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

diff --git a/include/tst_fuzzy_sync.h b/include/tst_fuzzy_sync.h
index 4141f5c64..b8841d96d 100644
--- a/include/tst_fuzzy_sync.h
+++ b/include/tst_fuzzy_sync.h
@@ -289,6 +289,7 @@ static void tst_fzsync_pair_reset(struct tst_fzsync_pair *pair,
 	tst_init_stat(&pair->diff_ab);
 	tst_init_stat(&pair->spins_avg);
 	pair->delay = 0;
+	pair->delay_bias = 0;
 	pair->sampling = pair->min_samples;
 
 	pair->exec_loop = 0;
-- 
2.30.1

[LTP] [PATCH v2 2/7] fzsync: Reset delay bias

[Cyril Hrubis]

Hi!
Reviewed-by: Cyril Hrubis <chrubis@suse.cz>

-- 
Cyril Hrubis
chrubis@suse.cz

[LTP] [PATCH v2 3/7] fzsync: Correctly print positive lower delay range bound

[Richard Palethorpe]

If the magnitude of delay_bias is large enough then it can turn the
lower bound positive.

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

diff --git a/include/tst_fuzzy_sync.h b/include/tst_fuzzy_sync.h
index b8841d96d..4063e95cb 100644
--- a/include/tst_fuzzy_sync.h
+++ b/include/tst_fuzzy_sync.h
@@ -518,9 +518,9 @@ static void tst_fzsync_pair_update(struct tst_fzsync_pair *pair)
 			tst_res(TINFO,
 				"Reached deviation ratios < %.2f, introducing randomness",
 				pair->max_dev_ratio);
-			tst_res(TINFO, "Delay range is [-%d, %d]",
-				(int)(pair->diff_sb.avg / per_spin_time) + pair->delay_bias,
-				(int)(pair->diff_sa.avg / per_spin_time) - pair->delay_bias);
+			tst_res(TINFO, "Delay range is [%d, %d]",
+				-(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;
 		}
-- 
2.30.1

[LTP] [PATCH v2 4/7] fzsync: Add sched_yield for single core machine

[Richard Palethorpe]

From: Leo Yu-Chi Liang <ycliang@andestech.com>

Fuzzy sync library uses spin waiting mechanism to implement thread
barrier behavior, which would cause this test to be time-consuming
on single core machine.

Fix this by adding sched_yield in the spin waiting loop, so that the
thread yields cpu as soon as it enters the waiting loop.

Signed-off-by: Leo Yu-Chi Liang <ycliang@andestech.com>
---
 include/tst_fuzzy_sync.h | 34 ++++++++++++++++++++++++++--------
 1 file changed, 26 insertions(+), 8 deletions(-)

diff --git a/include/tst_fuzzy_sync.h b/include/tst_fuzzy_sync.h
index 4063e95cb..5474f81e3 100644
--- a/include/tst_fuzzy_sync.h
+++ b/include/tst_fuzzy_sync.h
@@ -59,12 +59,15 @@
  * @sa tst_fzsync_pair
  */
 
-#include <sys/time.h>
-#include <time.h>
 #include <math.h>
-#include <stdlib.h>
 #include <pthread.h>
+#include <sched.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <sys/time.h>
+#include <time.h>
 #include "tst_atomic.h"
+#include "tst_cpu.h"
 #include "tst_timer.h"
 #include "tst_safe_pthread.h"
 
@@ -180,6 +183,15 @@ struct tst_fzsync_pair {
 	int exec_loop;
 	/** Internal; The second thread or 0 */
 	pthread_t thread_b;
+	/** 
+	 * Internal; The flag indicates single core machines or not
+	 * 
+	 * If running on single core machines, it would take considerable
+	 * amount of time to run fuzzy sync library.
+	 * Thus call sched_yield to give up cpu to decrease the test time.
+	 */
+	bool yield_in_wait;
+
 };
 
 #define CHK(param, low, hi, def) do {					      \
@@ -206,6 +218,7 @@ static void tst_fzsync_pair_init(struct tst_fzsync_pair *pair)
 	CHK(max_dev_ratio, 0, 1, 0.1);
 	CHK(exec_time_p, 0, 1, 0.5);
 	CHK(exec_loops, 20, INT_MAX, 3000000);
+	CHK(yield_in_wait, 0, 1, (tst_ncpus() <= 1));
 }
 #undef CHK
 
@@ -551,7 +564,8 @@ static void tst_fzsync_pair_update(struct tst_fzsync_pair *pair)
  */
 static inline void tst_fzsync_pair_wait(int *our_cntr,
 					int *other_cntr,
-					int *spins)
+					int *spins,
+					bool yield_in_wait)
 {
 	if (tst_atomic_inc(other_cntr) == INT_MAX) {
 		/*
@@ -565,6 +579,8 @@ static inline void tst_fzsync_pair_wait(int *our_cntr,
 		       && tst_atomic_load(our_cntr) < INT_MAX) {
 			if (spins)
 				(*spins)++;
+			if(yield_in_wait)
+				sched_yield();
 		}
 
 		tst_atomic_store(0, other_cntr);
@@ -582,6 +598,8 @@ static inline void tst_fzsync_pair_wait(int *our_cntr,
 		while (tst_atomic_load(our_cntr) < tst_atomic_load(other_cntr)) {
 			if (spins)
 				(*spins)++;
+			if(yield_in_wait)
+				sched_yield();
 		}
 	}
 }
@@ -594,7 +612,7 @@ static inline void tst_fzsync_pair_wait(int *our_cntr,
  */
 static inline void tst_fzsync_wait_a(struct tst_fzsync_pair *pair)
 {
-	tst_fzsync_pair_wait(&pair->a_cntr, &pair->b_cntr, NULL);
+	tst_fzsync_pair_wait(&pair->a_cntr, &pair->b_cntr, NULL, pair->yield_in_wait);
 }
 
 /**
@@ -605,7 +623,7 @@ static inline void tst_fzsync_wait_a(struct tst_fzsync_pair *pair)
  */
 static inline void tst_fzsync_wait_b(struct tst_fzsync_pair *pair)
 {
-	tst_fzsync_pair_wait(&pair->b_cntr, &pair->a_cntr, NULL);
+	tst_fzsync_pair_wait(&pair->b_cntr, &pair->a_cntr, NULL, pair->yield_in_wait);
 }
 
 /**
@@ -710,7 +728,7 @@ static inline void tst_fzsync_start_race_a(struct tst_fzsync_pair *pair)
 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);
+	tst_fzsync_pair_wait(&pair->a_cntr, &pair->b_cntr, &pair->spins, pair->yield_in_wait);
 }
 
 /**
@@ -741,7 +759,7 @@ static inline void tst_fzsync_start_race_b(struct tst_fzsync_pair *pair)
 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);
+	tst_fzsync_pair_wait(&pair->b_cntr, &pair->a_cntr, &pair->spins, pair->yield_in_wait);
 }
 
 /**
-- 
2.30.1

[LTP] [PATCH v2 5/7] fzsync: Move yield check out of loop and add yield to delay

[Richard Palethorpe]

During my testing I found no difference between having the branch
inside the loop and outside. However looking at the generated
assembly, it definitely does perform the branch inside the loop. This
could have an effect on some platform with worse branch prediction. So
I have moved the branch outside of the loop.

Also I have added sched_yield to the delay loop. If we only have one
CPU then it is not delaying anything unless the other process can
progress.

Reviewed-by: Leo Yu-Chi Liang <ycliang@andestech.com>
Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
---
 include/tst_fuzzy_sync.h | 72 ++++++++++++++++++++++++++++++----------
 1 file changed, 54 insertions(+), 18 deletions(-)

diff --git a/include/tst_fuzzy_sync.h b/include/tst_fuzzy_sync.h
index 5474f81e3..36a604e13 100644
--- a/include/tst_fuzzy_sync.h
+++ b/include/tst_fuzzy_sync.h
@@ -183,9 +183,9 @@ struct tst_fzsync_pair {
 	int exec_loop;
 	/** Internal; The second thread or 0 */
 	pthread_t thread_b;
-	/** 
-	 * Internal; The flag indicates single core machines or not
-	 * 
+	/**
+	 * The flag indicates single core machines or not
+	 *
 	 * If running on single core machines, it would take considerable
 	 * amount of time to run fuzzy sync library.
 	 * Thus call sched_yield to give up cpu to decrease the test time.
@@ -575,31 +575,53 @@ static inline void tst_fzsync_pair_wait(int *our_cntr,
 		 * line above before doing that. If we are in rear position
 		 * then our counter may already have been set to zero.
 		 */
-		while (tst_atomic_load(our_cntr) > 0
-		       && tst_atomic_load(our_cntr) < INT_MAX) {
-			if (spins)
-				(*spins)++;
-			if(yield_in_wait)
+		if (yield_in_wait) {
+			while (tst_atomic_load(our_cntr) > 0
+			       && tst_atomic_load(our_cntr) < INT_MAX) {
+				if (spins)
+					(*spins)++;
+
 				sched_yield();
+			}
+		} else {
+			while (tst_atomic_load(our_cntr) > 0
+			       && 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)
-			;
+		if (yield_in_wait) {
+			while (tst_atomic_load(our_cntr) > 1)
+				sched_yield();
+		} else {
+			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)) {
-			if (spins)
-				(*spins)++;
-			if(yield_in_wait)
+		if (yield_in_wait) {
+			while (tst_atomic_load(our_cntr) <
+			       tst_atomic_load(other_cntr)) {
+				if (spins)
+					(*spins)++;
 				sched_yield();
+			}
+		} else {
+			while (tst_atomic_load(our_cntr) <
+			       tst_atomic_load(other_cntr)) {
+				if (spins)
+					(*spins)++;
+			}
 		}
 	}
 }
@@ -713,8 +735,15 @@ static inline void tst_fzsync_start_race_a(struct tst_fzsync_pair *pair)
 	tst_fzsync_wait_a(pair);
 
 	delay = pair->delay;
-	while (delay < 0)
-		delay++;
+	if (pair->yield_in_wait) {
+		while (delay < 0) {
+			sched_yield();
+			delay++;
+		}
+	} else {
+		while (delay < 0)
+			delay++;
+	}
 
 	tst_fzsync_time(&pair->a_start);
 }
@@ -744,8 +773,15 @@ static inline void tst_fzsync_start_race_b(struct tst_fzsync_pair *pair)
 	tst_fzsync_wait_b(pair);
 
 	delay = pair->delay;
-	while (delay > 0)
-		delay--;
+	if (pair->yield_in_wait) {
+		while (delay > 0) {
+			sched_yield();
+			delay--;
+		}
+	} else {
+		while (delay > 0)
+			delay--;
+	}
 
 	tst_fzsync_time(&pair->b_start);
 }
-- 
2.30.1

[LTP] [PATCH v2 6/7] API: Add tst_ncpus_available

[Richard Palethorpe]

Same as tst_ncpus, but takes CPU affinity into account.

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

diff --git a/include/tst_cpu.h b/include/tst_cpu.h
index 117e27087..b3a449bea 100644
--- a/include/tst_cpu.h
+++ b/include/tst_cpu.h
@@ -8,6 +8,7 @@
 long tst_ncpus(void);
 long tst_ncpus_conf(void);
 long tst_ncpus_max(void);
+long tst_ncpus_available(void);
 
 #define VIRT_ANY	0	/* catch-all argument for tst_is_virt() */
 #define VIRT_XEN	1	/* xen dom0/domU */
diff --git a/lib/tst_cpu.c b/lib/tst_cpu.c
index 033155e47..581215199 100644
--- a/lib/tst_cpu.c
+++ b/lib/tst_cpu.c
@@ -17,6 +17,8 @@
  *   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  */
 
+#include "lapi/cpuset.h"
+
 #include <stdlib.h>
 #include <unistd.h>
 #include "test.h"
@@ -71,3 +73,24 @@ long tst_ncpus_max(void)
 	}
 	return ncpus_max;
 }
+
+long tst_ncpus_available(void)
+{
+#ifdef CPU_COUNT
+	long ncpus = tst_ncpus_max();
+	size_t cpusz = CPU_ALLOC_SIZE(ncpus);
+	cpu_set_t *cpus = CPU_ALLOC(ncpus);
+
+	if (sched_getaffinity(0, cpusz, cpus)) {
+		tst_resm(TWARN | TERRNO, "sched_getaffinity(0, %zu, %zx)",
+			cpusz, (size_t)cpus);
+	} else {
+		ncpus = CPU_COUNT(cpus);
+	}
+	free(cpus);
+
+	return ncpus;
+#else
+	return tst_ncpus();
+#endif
+}
-- 
2.30.1

[LTP] [PATCH v2 6/7] API: Add tst_ncpus_available

[Cyril Hrubis]

Hi!
> Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
> ---
>  include/tst_cpu.h |  1 +
>  lib/tst_cpu.c     | 23 +++++++++++++++++++++++
>  2 files changed, 24 insertions(+)
> 
> diff --git a/include/tst_cpu.h b/include/tst_cpu.h
> index 117e27087..b3a449bea 100644
> --- a/include/tst_cpu.h
> +++ b/include/tst_cpu.h
> @@ -8,6 +8,7 @@
>  long tst_ncpus(void);
>  long tst_ncpus_conf(void);
>  long tst_ncpus_max(void);
> +long tst_ncpus_available(void);
>  
>  #define VIRT_ANY	0	/* catch-all argument for tst_is_virt() */
>  #define VIRT_XEN	1	/* xen dom0/domU */
> diff --git a/lib/tst_cpu.c b/lib/tst_cpu.c
> index 033155e47..581215199 100644
> --- a/lib/tst_cpu.c
> +++ b/lib/tst_cpu.c
> @@ -17,6 +17,8 @@
>   *   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
>   */
>  
> +#include "lapi/cpuset.h"
> +
>  #include <stdlib.h>
>  #include <unistd.h>
>  #include "test.h"
> @@ -71,3 +73,24 @@ long tst_ncpus_max(void)
>  	}
>  	return ncpus_max;
>  }
> +
> +long tst_ncpus_available(void)
> +{
> +#ifdef CPU_COUNT
> +	long ncpus = tst_ncpus_max();
> +	size_t cpusz = CPU_ALLOC_SIZE(ncpus);
> +	cpu_set_t *cpus = CPU_ALLOC(ncpus);


The CPU_ALLOC() is allowed to fail an return NULL, I guess that the
worst that would happen here is EFAULT from sched_getaffinity() but it
would be nicer to do something as:

	if (!cpus) {
		tst_resm(TWARN | TERRNO, "CPU_ALLOC() failed");
		return ncpus;
	}

> +	if (sched_getaffinity(0, cpusz, cpus)) {
> +		tst_resm(TWARN | TERRNO, "sched_getaffinity(0, %zu, %zx)",
> +			cpusz, (size_t)cpus);
> +	} else {
> +		ncpus = CPU_COUNT(cpus);
> +	}
> +	free(cpus);

This should be CPU_FREE() if we are pedantic.

I guess that nothing stops glibc from using alloca() if we have less
than a few bytes to allocate and switch to malloc() only if the ncpus is
bigger than certain threshold internally in the CPU_ALLOC() macro.

> +	return ncpus;
> +#else
> +	return tst_ncpus();
> +#endif
> +}
> -- 
> 2.30.1
> 
> 
> -- 
> Mailing list info: https://lists.linux.it/listinfo/ltp

-- 
Cyril Hrubis
chrubis@suse.cz

[LTP] [PATCH v2 6/7] API: Add tst_ncpus_available

[Cyril Hrubis]

Hi!
Forget this, there is a v3 that is fine.

-- 
Cyril Hrubis
chrubis@suse.cz

[LTP] [PATCH v2 7/7] fzsync: Check processor affinity

[Richard Palethorpe]

It is useful for testing Fuzzy Sync itself to set the CPU affinity to
a single core. The current processes affinity does not effect
tst_ncpus(), but we can get the affinity separately.

Note that checking this still does not guarantee we will use yield
when restricted to only one core. We would have to periodically probe
which CPUs threads are running on until we detect more than one CPU.

Reviewed-by: Leo Yu-Chi Liang <ycliang@andestech.com>
Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
---
 include/tst_fuzzy_sync.h | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)

diff --git a/include/tst_fuzzy_sync.h b/include/tst_fuzzy_sync.h
index 36a604e13..e38b56e5e 100644
--- a/include/tst_fuzzy_sync.h
+++ b/include/tst_fuzzy_sync.h
@@ -61,7 +61,6 @@
 
 #include <math.h>
 #include <pthread.h>
-#include <sched.h>
 #include <stdbool.h>
 #include <stdlib.h>
 #include <sys/time.h>
@@ -213,12 +212,16 @@ struct tst_fzsync_pair {
  */
 static void tst_fzsync_pair_init(struct tst_fzsync_pair *pair)
 {
+	long ncpus = tst_ncpus_available();
+
 	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.5);
 	CHK(exec_loops, 20, INT_MAX, 3000000);
-	CHK(yield_in_wait, 0, 1, (tst_ncpus() <= 1));
+
+	if (ncpus <= 1)
+		pair->yield_in_wait = 1;
 }
 #undef CHK
 
-- 
2.30.1