Fuzzy Sync single core support and tests
v2 cover Fuzzy Sync single core support and tests
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
Signature · 1 line
2.30.1
PATCH v2 1/7 fzsync: Add self tests
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.
--- 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
lib/newlib_tests/.gitignore +2 -0
@@ -40,3 +40,5 @@ tst_bool_expr test_macros01 test_macros02 test_macros03 +tst_fuzzy_sync01 +tst_fuzzy_sync02
lib/newlib_tests/test16.c +2 -0
@@ -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"
lib/newlib_tests/tst_fuzzy_sync01.c new file +232 -0
232 lines not on this page · raw message
lib/newlib_tests/tst_fuzzy_sync02.c new file +179 -0
179 lines not on this page · raw message
Signature · 1 line
2.30.1
PATCH v2 1/7 fzsync: Add self tests
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+=-pthreadtst_fuzzy_sync02: CFLAGS+=-pthread
Kind regards,
Petr
PATCH v2 1/7 fzsync: Add self tests
Hello,
Quoted 14 lines · 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 topthread_cancel' /usr/bin/ld: /home/pevik/install/src/ltp.git/lib/newlib_tests/../../include/tst_fuzzy_sync.h:226: undefined reference topthread_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
Quoted 6 lines
lib/newlib_tests/Makefileneeds to add:tst_fuzzy_sync01: CFLAGS+=-pthreadtst_fuzzy_sync02: CFLAGS+=-pthreadKind regards,
Petr
Ah, I really should compile with GCC as well as Clang!
Signature · 2 lines
Thank you, Richard.
PATCH v2 2/7 fzsync: Reset delay bias
In reply to Richard PalethorpeIf 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.
--- include/tst_fuzzy_sync.h | 1 + 1 file changed, 1 insertion(+)
include/tst_fuzzy_sync.h +1 -0
@@ -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 ;
Signature · 1 line
2.30.1
PATCH v2 2/7 fzsync: Reset delay bias
PATCH v2 3/7 fzsync: Correctly print positive lower delay range bound
In reply to Richard PalethorpeIf the magnitude of delay_bias is large enough then it can turn the lower bound positive.
--- include/tst_fuzzy_sync.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)
include/tst_fuzzy_sync.h +3 -3
@@ -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 ; }
Signature · 1 line
2.30.1
PATCH v2 4/7 fzsync: Add sched_yield for single core machine
In reply to Richard PalethorpeFrom: Leo Yu-Chi Liang <[email protected]>
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.
--- include/tst_fuzzy_sync.h | 34 ++++++++++++++++++++++++++-------- 1 file changed, 26 insertions(+), 8 deletions(-)
include/tst_fuzzy_sync.h +26 -8
@@ -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); }/**
Signature · 1 line
2.30.1
PATCH v2 5/7 fzsync: Move yield check out of loop and add yield to delay
In reply to Richard PalethorpeDuring 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.
--- include/tst_fuzzy_sync.h | 72 ++++++++++++++++++++++++++++++---------- 1 file changed, 54 insertions(+), 18 deletions(-)
include/tst_fuzzy_sync.h +54 -18
@@ -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); }
Signature · 1 line
2.30.1
PATCH v2 6/7 API: Add tst_ncpus_available
In reply to Richard PalethorpeSame as tst_ncpus, but takes CPU affinity into account.
--- include/tst_cpu.h | 1 + lib/tst_cpu.c | 23 +++++++++++++++++++++++ 2 files changed, 24 insertions(+)
include/tst_cpu.h +1 -0
@@ -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 */
lib/tst_cpu.c +23 -0
@@ -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 +}
Signature · 1 line
2.30.1
PATCH v2 6/7 API: Add tst_ncpus_available
Hi!
Quoted 32 lines
Signed-off-by Richard Palethorpe <[email protected]>--- include/tst_cpu.h | 1 + lib/tst_cpu.c | 23 +++++++++++++++++++++++ 2 files changed, 24 insertions(+)include/tst_cpu.h +1
-0@@ -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 */ lib/tst_cpu.c +2
-0@@ -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"
lib/tst_cpu.c long tst_ncpus_max(void) · line 82
Quoted 10 lines
lib/tst_cpu.c +7
-0@@ -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;
}lib/tst_cpu.c long tst_ncpus_max(void) · line 90
Quoted 7 lines
lib/tst_cpu.c +7
-0+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.
Quoted 11 lines
lib/tst_cpu.c +5
-0+return ncpus; +#else +return tst_ncpus (); +#endif +}Signature · 5 lines
2.30.1 -- Mailing list info: https://lists.linux.it/listinfo/ltp
Signature · 2 lines
Cyril Hrubis [email protected]
PATCH v2 6/7 API: Add tst_ncpus_available
Hi!
Forget this, there is a v3 that is fine.
Signature · 2 lines
Cyril Hrubis [email protected]
PATCH v2 7/7 fzsync: Check processor affinity
In reply to Richard PalethorpeIt 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.
--- include/tst_fuzzy_sync.h | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-)
include/tst_fuzzy_sync.h +5 -2
@@ -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
Signature · 1 line
2.30.1