From 8055e41d0ecc54770a2653427532b3e2c5fabdad Mon Sep 17 00:00:00 2001 From: Jens Axboe Date: Mon, 26 Nov 2012 08:43:47 +0100 Subject: [PATCH] Add LFSR generator Signed-off-by: Jens Axboe --- Makefile | 2 +- file.h | 3 + filesetup.c | 11 ++- fio.h | 7 ++ io_u.c | 37 +++++--- lib/lfsr.c | 264 ++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/lfsr.h | 24 +++++ options.c | 17 ++++ 8 files changed, 348 insertions(+), 17 deletions(-) create mode 100644 lib/lfsr.c create mode 100644 lib/lfsr.h diff --git a/Makefile b/Makefile index 70309147..d197853e 100644 --- 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 ce92ff75..9dd08731 100644 --- 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 c96c2502..e7f5f1f3 100644 --- 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 654db5f5..0100e3d8 100644 --- 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 aff24eb8..2904ad40 100644 --- 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 index 00000000..64442ab5 --- /dev/null +++ b/lib/lfsr.c @@ -0,0 +1,264 @@ +#include + +#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 index 00000000..0de9ea8e --- /dev/null +++ b/lib/lfsr.h @@ -0,0 +1,24 @@ +#ifndef FIO_LFSR_H +#define FIO_LFSR_H + +#include + +#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 ae859882..d46bcbbc 100644 --- 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, -- 2.25.1