[PATCH] LFSR: Do not ignore returning the seed

[PATCH] LFSR: Do not ignore returning the seed

[Alex Pyrgiotis]

Hi all,

Since Juan Casse stirred the LFSR subject, I took a look at the code and found
out that for certain spin values, the seed would not be used. The
following patch fixes that issue.

Most of the people will not be affected by this bug, except for those that
strictly needed a non-repeating LFSR.

Alex Pyrgiotis (1):
  LFSR: Do not ignore returning the seed

 lib/lfsr.c | 29 +++++++++++++++++------------
 1 file changed, 17 insertions(+), 12 deletions(-)

-- 
1.8.3.4

[PATCH] LFSR: Do not ignore returning the seed

[Alex Pyrgiotis]

Fix a situation where we would spin prematurely and would hop over the
seed value.

Also, add some more comments to the code.

Signed-off-by: Alex Pyrgiotis <apyrgio@grnet.gr>

diff --git a/lib/lfsr.c b/lib/lfsr.c
index b10ba7a..927b2a1 100644
--- a/lib/lfsr.c
+++ b/lib/lfsr.c
@@ -87,7 +87,6 @@ static inline void __lfsr_next(struct fio_lfsr *fl, unsigned int spin)
 	 * this switch.
 	 */
 	switch (spin) {
-		case 16: __LFSR_NEXT(fl, fl->last_val);
 		case 15: __LFSR_NEXT(fl, fl->last_val);
 		case 14: __LFSR_NEXT(fl, fl->last_val);
 		case 13: __LFSR_NEXT(fl, fl->last_val);
@@ -126,21 +125,16 @@ static inline void __lfsr_next(struct fio_lfsr *fl, unsigned int spin)
  */
 int lfsr_next(struct fio_lfsr *fl, uint64_t *off, uint64_t last)
 {
-	unsigned int spin = fl->spin;
-
 	if (fl->num_vals++ > fl->max_val)
 		return 1;
 
 	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;
-			}
+		if (fl->cycle_length && !--fl->cycle_length) {
+			__lfsr_next(fl, fl->spin + 1);
+			fl->cycle_length = fl->cached_cycle_length;
+			goto check;
 		}
-		__lfsr_next(fl, spin);
+		__lfsr_next(fl, fl->spin);
 check: ;
 	} while (fl->last_val > fl->max_val);
 
@@ -163,8 +157,13 @@ static uint8_t *find_lfsr(uint64_t size)
 {
 	int i;
 
+	/*
+	 * For an LFSR, there is always a prohibited state (all ones).
+	 * Thus, if we need to find the proper LFSR for our size, we must take that
+	 * into account.
+	 */
 	for (i = 3; i < 64; i++)
-		if ((1UL << i) > size) /* TODO: Explain why. */
+		if ((1UL << i) > size)
 			return taps[i];
 
 	return NULL;
@@ -210,6 +209,12 @@ int prepare_spin(struct fio_lfsr *fl, unsigned int spin)
 	}
 	fl->cached_cycle_length = fl->cycle_length;
 
+	/*
+	 * Increment cycle length for the first time only since the stored value
+	 * will not be printed otherwise.
+	 */
+	fl->cycle_length++;
+
 	return 0;
 }
 
-- 
1.8.3.4

Re: [PATCH] LFSR: Do not ignore returning the seed

[Jens Axboe]

On 08/26/2013 03:52 PM, Alex Pyrgiotis wrote:
> Fix a situation where we would spin prematurely and would hop over the
> seed value.
> 
> Also, add some more comments to the code.
> 
> Signed-off-by: Alex Pyrgiotis <apyrgio@grnet.gr>

Applied, thanks.

-- 
Jens Axboe