Add LFSR generator

Signed-off-by: Jens Axboe <axboe@kernel.dk>

diff --git a/Makefile b/Makefile
index 70309147e0d89a220fa4ce4ad1812c193eda19cf..d197853e8fdcae707930b04b3bc2adbe4cad6252 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -17,7 +17,7 @@ SOURCE := gettime.c fio.c ioengines.c init.c stat.c log.c time.c filesetup.c \
                lib/num2str.c lib/ieee754.c $(wildcard crc/*.c) engines/cpu.c \
                engines/mmap.c engines/sync.c engines/null.c engines/net.c \
                memalign.c server.c client.c iolog.c backend.c libfio.c flow.c \
-               json.c lib/zipf.c lib/bitmap.c gettime-thread.c
+               json.c lib/zipf.c lib/bitmap.c lib/lfsr.c gettime-thread.c
 
 ifeq ($(UNAME), Linux)
   SOURCE += diskutil.c fifo.c blktrace.c helpers.c cgroup.c trim.c \

diff --git a/file.h b/file.h
index ce92ff75305dda0438ec041dcfa7f37c6fb5ce83..9dd08731e63f7e47ed049fbbca469198da36da39 100644 (file)
--- a/file.h
+++ b/file.h
@@ -7,6 +7,7 @@
 #include "flist.h"
 #include "lib/zipf.h"
 #include "lib/bitmap.h"
+#include "lib/lfsr.h"
 
 /*
  * The type of object we are working on
@@ -111,6 +112,8 @@ struct fio_file {
         */
        struct bitmap *io_bitmap;
 
+       struct fio_lfsr lfsr;
+
        /*
         * Used for zipf random distribution
         */

diff --git a/filesetup.c b/filesetup.c
index c96c2502a46bdec4494d2141cd5a2078a75d2014..e7f5f1f39847f3865caa3599dea6c98b02a74ffd 100644 (file)
--- a/filesetup.c
+++ b/filesetup.c
@@ -917,9 +917,14 @@ int init_random_map(struct thread_data *td)
        for_each_file(td, f, i) {
                blocks = (f->real_file_size + td->o.rw_min_bs - 1) /
                                (unsigned long long) td->o.rw_min_bs;
-               f->io_bitmap = bitmap_new(blocks);
-               if (f->io_bitmap)
-                       continue;
+               if (td->o.random_generator == FIO_RAND_GEN_LFSR) {
+                       if (!lfsr_init(&f->lfsr, blocks))
+                               continue;
+               } else {
+                       f->io_bitmap = bitmap_new(blocks);
+                       if (f->io_bitmap)
+                               continue;
+               }
 
                if (!td->o.softrandommap) {
                        log_err("fio: failed allocating random map. If running"

diff --git a/fio.h b/fio.h
index 654db5f528b4d9ca4eb9dec9f70c6e3cfb7bf49d..0100e3d8680a07af00894495c73e99322bcd6b60 100644 (file)
--- a/fio.h
+++ b/fio.h
@@ -181,6 +181,8 @@ struct thread_options {
        double zipf_theta;
        double pareto_h;
 
+       unsigned int random_generator;
+
        unsigned int hugepage_size;
        unsigned int rw_min_bs;
        unsigned int thinktime;
@@ -822,4 +824,9 @@ enum {
        FIO_RAND_DIST_PARETO,
 };
 
+enum {
+       FIO_RAND_GEN_TAUSWORTHE = 0,
+       FIO_RAND_GEN_LFSR,
+};
+
 #endif

diff --git a/io_u.c b/io_u.c
index aff24eb884c2fc1db5aa6eccc81c1001746cc372..2904ad40bd7183d1a4e9bab64fc434d3ebe4ff2b 100644 (file)
--- a/io_u.c
+++ b/io_u.c
@@ -77,25 +77,36 @@ static unsigned long long last_block(struct thread_data *td, struct fio_file *f,
 static int __get_next_rand_offset(struct thread_data *td, struct fio_file *f,
                                  enum fio_ddir ddir, unsigned long long *b)
 {
-       unsigned long long rmax, r, lastb;
+       unsigned long long r;
 
-       lastb = last_block(td, f, ddir);
-       if (!lastb)
-               return 1;
+       if (td->o.random_generator == FIO_RAND_GEN_TAUSWORTHE) {
+               unsigned long long rmax, lastb;
 
-       rmax = td->o.use_os_rand ? OS_RAND_MAX : FRAND_MAX;
+               lastb = last_block(td, f, ddir);
+               if (!lastb)
+                       return 1;
 
-       if (td->o.use_os_rand) {
-               rmax = OS_RAND_MAX;
-               r = os_random_long(&td->random_state);
+               rmax = td->o.use_os_rand ? OS_RAND_MAX : FRAND_MAX;
+
+               if (td->o.use_os_rand) {
+                       rmax = OS_RAND_MAX;
+                       r = os_random_long(&td->random_state);
+               } else {
+                       rmax = FRAND_MAX;
+                       r = __rand(&td->__random_state);
+               }
+
+               dprint(FD_RANDOM, "off rand %llu\n", r);
+
+               *b = (lastb - 1) * (r / ((unsigned long long) rmax + 1.0));
        } else {
-               rmax = FRAND_MAX;
-               r = __rand(&td->__random_state);
-       }
+               uint64_t off = 0;
 
-       *b = (lastb - 1) * (r / ((unsigned long long) rmax + 1.0));
+               if (lfsr_next(&f->lfsr, &off))
+                       return 1;
 
-       dprint(FD_RANDOM, "off rand %llu\n", r);
+               *b = off;
+       }
 
        /*
         * if we are not maintaining a random map, we are done.

diff --git a/lib/lfsr.c b/lib/lfsr.c
new file mode 100644 (file)
index 0000000..64442ab
--- /dev/null
+++ b/lib/lfsr.c
@@ -0,0 +1,264 @@
+#include <stdio.h>
+
+#include "lfsr.h"
+
+/*
+ * Trom table 3 of
+ *
+ * http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
+ */
+static struct lfsr_taps lfsr_taps[] = {
+       {
+               .length = 16,
+               .taps   = { 16, 15, 13, 4, },
+       },
+       {
+               .length = 17,
+               .taps   = { 17, 14, },
+       },
+       {
+               .length = 18,
+               .taps   = { 18, 11, },
+       },
+       {
+               .length = 19,
+               .taps   = { 19, 6, 2, 1, },
+       },
+       {
+               .length = 20,
+               .taps   = { 20, 17, },
+       },
+       {
+               .length = 21,
+               .taps   = { 21, 19, },
+       },
+       {
+               .length = 22,
+               .taps   = { 22, 21, },
+       },
+       {
+               .length = 23,
+               .taps   = { 23, 18, },
+       },
+       {
+               .length = 24,
+               .taps   = { 24, 23, 22, 17, },
+       },
+       {
+               .length = 25,
+               .taps   = { 25, 22, },
+       },
+       {
+               .length = 26,
+               .taps   = {26, 6, 2, 1, },
+       },
+       {
+               .length = 27,
+               .taps   = { 27, 5, 2, 1, },
+       },
+       {
+               .length = 28,
+               .taps   = { 28, 25, },
+       },
+       {
+               .length = 29,
+               .taps   = {29, 27, },
+       },
+       {
+               .length = 30,
+               .taps   = { 30, 6, 4, 1, },
+       },
+       {
+               .length = 31,
+               .taps   = { 31, 28, },
+       },
+       {
+               .length = 32,
+               .taps   = { 32, 22, 2, 1, },
+       },
+       {
+               .length = 33,
+               .taps   = { 33, 20, },
+       },
+       {
+               .length = 34,
+               .taps   = { 34, 27, 2, 1, },
+       },
+       {
+               .length = 35,
+               .taps   = { 35, 33, },
+       },
+       {
+               .length = 36,
+               .taps   = { 36, 25, },
+       },
+       {
+               .length = 37,
+               .taps   = { 37, 5, 4, 3, 2, 1, },
+       },
+       {
+               .length = 38,
+               .taps   = { 38, 6, 5, 1, },
+       },
+       {
+               .length = 39,
+               .taps   = { 39, 35, },
+       },
+       {
+               .length = 40,
+               .taps   = { 40, 38, 21, 19, },
+       },
+       {
+               .length = 41,
+               .taps   = { 41, 38, },
+       },
+       {
+               .length = 42,
+               .taps   = { 42, 41, 20, 19, },
+       },
+       {
+               .length = 43,
+               .taps   = { 43, 42, 38, 37, },
+       },
+       {
+               .length = 44,
+               .taps   = { 44, 43, 38, 37, },
+       },
+       {
+               .length = 45,
+               .taps   = { 45, 44, 42, 41, },
+       },
+       {
+               .length = 46,
+               .taps   = { 46, 45, 26, 25, },
+       },
+       {
+               .length = 47,
+               .taps   = { 47, 42, },
+       },
+       {
+               .length = 48,
+               .taps   = { 48, 47, 21, 20, },
+       },
+       {
+               .length = 49,
+               .taps   = { 49, 40, },
+       },
+       {
+               .length = 50,
+               .taps   = { 50, 49, 36, 35, },
+       },
+       {
+               .length = 51,
+               .taps   = { 51, 50, 36, 35, },
+       },
+       {
+               .length = 52,
+               .taps   = { 52, 49, },
+       },
+       {
+               .length = 53,
+               .taps   = { 53, 52, 38, 37 },
+       },
+       {
+               .length = 54,
+               .taps   = { 54, 53, 18, 17 },
+       },
+       {
+               .length = 55,
+               .taps   = { 55, 31, },
+       },
+       {
+               .length = 56,
+               .taps   = { 56, 55, 35, 34, },
+       },
+       {
+               .length = 57,
+               .taps   = { 57, 50, },
+       },
+       {
+               .length = 58,
+               .taps   = { 58, 39, },
+       },
+       {
+               .length = 59,
+               .taps   = { 59, 58, 38, 37, },
+       },
+       {
+               .length = 60,
+               .taps   = { 60, 59, },
+       },
+       {
+               .length = 61,
+               .taps   = { 61, 60, 46, 45, },
+       },
+       {
+               .length = 62,
+               .taps   = { 62, 61, 6, 5, },
+       },
+       {
+               .length = 63,
+               .taps   = { 63, 62, },
+       },
+};
+
+static uint64_t __lfsr_next(uint64_t v, struct lfsr_taps *lt)
+{
+       uint64_t xor_mask = 0;
+       int i;
+
+       for (i = 0; lt->taps[i]; i++)
+               xor_mask ^= (v << (lt->taps[i] - 1));
+
+       xor_mask &= ~(~0UL << 1) << (lt->length - 1);
+       return xor_mask | (v >> 1);
+}
+
+int lfsr_next(struct fio_lfsr *fl, uint64_t *off)
+{
+       if (fl->num_vals > fl->max_val)
+               return 1;
+
+       do {
+               fl->last_val = __lfsr_next(fl->last_val, &fl->taps);
+               if (fl->last_val - 1 <= fl->max_val)
+                       break;
+       } while (1);
+
+       *off = fl->last_val - 1;
+       fl->num_vals++;
+       return 0;
+}
+
+static struct lfsr_taps *find_lfsr(uint64_t size)
+{
+       int i;
+
+       for (i = 0; lfsr_taps[i].length; i++)
+               if ((1UL << lfsr_taps[i].length) >= size)
+                       return &lfsr_taps[i];
+
+       return NULL;
+}
+
+int lfsr_init(struct fio_lfsr *fl, uint64_t size)
+{
+       struct lfsr_taps *tap;
+       int i;
+
+       tap = find_lfsr(size);
+       if (!tap)
+               return 1;
+
+       fl->last_val = 1;
+       fl->max_val = size - 1;
+       fl->num_vals = 0;
+       fl->taps.length = tap->length;
+       for (i = 0; i < FIO_MAX_TAPS; i++) {
+               fl->taps.taps[i] = tap->taps[i];
+               if (!fl->taps.taps[i])
+                       break;
+       }
+
+       return 0;
+}

diff --git a/lib/lfsr.h b/lib/lfsr.h
new file mode 100644 (file)
index 0000000..0de9ea8
--- /dev/null
+++ b/lib/lfsr.h
@@ -0,0 +1,24 @@
+#ifndef FIO_LFSR_H
+#define FIO_LFSR_H
+
+#include <inttypes.h>
+
+#define FIO_MAX_TAPS   8
+
+struct lfsr_taps {
+       unsigned int length;
+       unsigned int taps[FIO_MAX_TAPS];
+};
+
+
+struct fio_lfsr {
+       uint64_t last_val;
+       uint64_t max_val;
+       uint64_t num_vals;
+       struct lfsr_taps taps;
+};
+
+int lfsr_next(struct fio_lfsr *fl, uint64_t *off);
+int lfsr_init(struct fio_lfsr *fl, uint64_t size);
+
+#endif

diff --git a/options.c b/options.c
index ae8598825e048a783da985bf9c6d89b8fb2530a2..d46bcbbcf6c9cab8fc1c41e8800bc5071429ccd9 100644 (file)
--- a/options.c
+++ b/options.c
@@ -1511,6 +1511,23 @@ static struct fio_option options[FIO_MAX_OPTS] = {
                .parent = "norandommap",
                .def    = "0",
        },
+       {
+               .name   = "random_generator",
+               .type   = FIO_OPT_STR,
+               .off1   = td_var_offset(random_generator),
+               .help   = "Type of random number generator to use",
+               .def    = "tausworthe",
+               .posval = {
+                         { .ival = "tausworthe",
+                           .oval = FIO_RAND_GEN_TAUSWORTHE,
+                           .help = "Strong Tausworthe generator",
+                         },
+                         { .ival = "lfsr",
+                           .oval = FIO_RAND_GEN_LFSR,
+                           .help = "Variable length LFSR",
+                         },
+               },
+       },
        {
                .name   = "random_distribution",
                .type   = FIO_OPT_STR,