LFSR:Fix verification and spin bugs
PATCH 1/1 LFSR:Fix verification and spin bugs
Hi all,
As Jiri had previously noticed, verification did not work, which led to some ugly bugs slipping through the code (sorry about that). This patch not only fixes that but has some performance tweaks that should make the code perform almost twice as fast for most cases.
These have come at the expense of code readability, so I added some more comments where necessary.
Regards,
Alex
Alex Pyrgiotis (1):
Fix verification and spin bugs
lib/lfsr.c | 35 +++++++++++++++++++++++------------ lib/lfsr.h | 1 + t/lfsr-test.c | 6 ++++-- 3 files changed, 28 insertions(+), 14 deletions(-)
Signature · 1 line
1.8.1.4
PATCH 1/1 Fix verification and spin bugs
Changes:
1. Verification now works properly and reports for which value it fails
2. Fix a mishandling of spin incrementation which led to multiple calculation of the same values
lib/lfsr.c +23 -12
@@ -112,26 +112,36 @@ static inline void __lfsr_next(struct fio_lfsr *fl, unsigned int spin)* lfsr_next does the following: * * a. Return if the number of max values has been exceeded. -* b. Check if the next iteration(s) produce a cycle (due to spin) and add "1" -* where necessary. -* c. Calculate the next value and return. +* b. Check if we have a spin value that produces a repeating subsequence. +* This is previously calculated in `prepare_spin` and cycle_length should +* be > 0. If we do have such a spin: +* +* i. Decrement the calculated cycle. +* ii. If it reaches zero, add "+1" to the spin and reset the cycle_length +* (we have it cached in the struct fio_lfsr) +* +* In either case, continue with the calculation of the next value. +* c. Check if the calculated value exceeds the desirable range. In this case, +* go back to b, else return. */ int lfsr_next (struct fio_lfsr *fl,uint64_t *off,uint64_t last) { -int repeat; -unsigned int spin; +unsigned int spin = fl->spin;if (fl->num_vals++ > fl->max_val)return 1 ; - repeat = fl->num_vals % fl->cycle_length; -if (repeat ==0 ) - spin = fl->spin +1 ; -else - spin = fl->spin; -do { +if (fl->cycle_length) { + fl->cycle_length--; +if (!fl->cycle_length) { +__lfsr_next (fl, fl->spin +1 ); + fl->cycle_length = fl->cached_cycle_length; + goto check; + } + }__lfsr_next (fl, spin); +check: ; }while (fl->last_val > fl->max_val); *off = fl->last_val;
@@ -189,7 +199,7 @@ int prepare_spin(struct fio_lfsr *fl, unsigned int spin) x = max / (spin +1 ); y = max % (spin +1 ); - fl->cycle_length = max;/* This is the expected cycle */ + fl->cycle_length =0 ;/* No cycle occurs, other than the expected */ fl->spin = spin;for (i =1 ; i <= spin; i++) {
@@ -198,6 +208,7 @@ int prepare_spin(struct fio_lfsr *fl, unsigned int spin)break ; } } + fl->cached_cycle_length = fl->cycle_length;return 0 ; }
lib/lfsr.h +1 -0
@@ -18,6 +18,7 @@ struct fio_lfsr {uint64_t max_val;uint64_t num_vals;uint64_t cycle_length; +uint64_t cached_cycle_length;unsigned int spin; };
t/lfsr-test.c +4 -2
@@ -94,13 +94,15 @@ int main(int argc, char *argv[])clock_gettime (CLOCK_PROCESS_CPUTIME_ID , &end);fprintf (stderr,"finished.\n" ); +/* Check if all expected numbers within range have been calculated */ r =0 ;if (verify) {fprintf (stderr,"Verifying results... " );for (i =0 ; i < numbers; i++) { -if (*(uint8_t *)(v +1 ) !=1 ) { -fprintf (stderr,"failed.\n" ); +if (*(uint8_t *)(v + i) !=1 ) { +fprintf (stderr,"failed (%lu = %d).\n" , + i, *(uint8_t *)(v + i)); r =1 ;break ; }
Signature · 1 line
1.8.1.4
Jens Axboe
AppliedRe: [PATCH] Fix verification and spin bugs
Quoted 5 lines · Alex Pyrgiotis
Changes:
1. Verification now works properly and reports for which value it fails
2. Fix a mishandling of spin incrementation which led to multiple calculation of the same values
Thanks, applied.
Signature · 1 line
Jens Axboe