From 56d9fa4b8d4fa5166e3ec5dcdd37b5789b2cb01d Mon Sep 17 00:00:00 2001 From: Jens Axboe Date: Wed, 8 Apr 2015 11:02:13 -0600 Subject: [PATCH] Add support for normal/gaussian random distributions Signed-off-by: Jens Axboe --- Makefile | 2 +- cconv.c | 2 ++ file.h | 6 +++++- filesetup.c | 4 +++- fio.h | 1 + io_u.c | 11 ++++++++++ lib/gauss.c | 53 ++++++++++++++++++++++++++++++++++++++++++++++++ lib/gauss.h | 17 ++++++++++++++++ options.c | 11 ++++++++-- thread_options.h | 3 ++- 10 files changed, 104 insertions(+), 6 deletions(-) create mode 100644 lib/gauss.c create mode 100644 lib/gauss.h diff --git a/Makefile b/Makefile index 52e515b0..1227eb9f 100644 --- a/Makefile +++ b/Makefile @@ -36,7 +36,7 @@ SOURCE := gettime.c ioengines.c init.c stat.c log.c time.c filesetup.c \ lib/lfsr.c gettime-thread.c helpers.c lib/flist_sort.c \ lib/hweight.c lib/getrusage.c idletime.c td_error.c \ profiles/tiobench.c profiles/act.c io_u_queue.c filelock.c \ - lib/tp.c lib/bloom.c + lib/tp.c lib/bloom.c lib/gauss.c ifdef CONFIG_LIBHDFS HDFSFLAGS= -I $(JAVA_HOME)/include -I $(JAVA_HOME)/include/linux -I $(FIO_LIBHDFS_INCLUDE) diff --git a/cconv.c b/cconv.c index 0fca764e..fbe784e7 100644 --- a/cconv.c +++ b/cconv.c @@ -163,6 +163,7 @@ void convert_thread_options_to_cpu(struct thread_options *o, o->fsync_on_close = le32_to_cpu(top->fsync_on_close); o->bs_is_seq_rand = le32_to_cpu(top->bs_is_seq_rand); o->random_distribution = le32_to_cpu(top->random_distribution); + o->gauss_dev = le32_to_cpu(top->gauss_dev); o->zipf_theta.u.f = fio_uint64_to_double(le64_to_cpu(top->zipf_theta.u.i)); o->pareto_h.u.f = fio_uint64_to_double(le64_to_cpu(top->pareto_h.u.i)); o->random_generator = le32_to_cpu(top->random_generator); @@ -337,6 +338,7 @@ void convert_thread_options_to_net(struct thread_options_pack *top, top->fsync_on_close = cpu_to_le32(o->fsync_on_close); top->bs_is_seq_rand = cpu_to_le32(o->bs_is_seq_rand); top->random_distribution = cpu_to_le32(o->random_distribution); + top->gauss_dev = cpu_to_le32(o->gauss_dev); top->zipf_theta.u.i = __cpu_to_le64(fio_double_to_uint64(o->zipf_theta.u.f)); top->pareto_h.u.i = __cpu_to_le64(fio_double_to_uint64(o->pareto_h.u.f)); top->random_generator = cpu_to_le32(o->random_generator); diff --git a/file.h b/file.h index fc473102..22ec742f 100644 --- a/file.h +++ b/file.h @@ -8,6 +8,7 @@ #include "lib/zipf.h" #include "lib/axmap.h" #include "lib/lfsr.h" +#include "lib/gauss.h" /* * The type of object we are working on @@ -119,7 +120,10 @@ struct fio_file { /* * Used for zipf random distribution */ - struct zipf_state zipf; + union { + struct zipf_state zipf; + struct gauss_state gauss; + }; int references; enum fio_file_flags flags; diff --git a/filesetup.c b/filesetup.c index 0fb5589b..7dceddbb 100644 --- a/filesetup.c +++ b/filesetup.c @@ -998,8 +998,10 @@ static int __init_rand_distribution(struct thread_data *td, struct fio_file *f) if (td->o.random_distribution == FIO_RAND_DIST_ZIPF) zipf_init(&f->zipf, nranges, td->o.zipf_theta.u.f, seed); - else + else if (td->o.random_distribution == FIO_RAND_DIST_PARETO) pareto_init(&f->zipf, nranges, td->o.pareto_h.u.f, seed); + else if (td->o.random_distribution == FIO_RAND_DIST_GAUSS) + gauss_init(&f->gauss, nranges, td->o.gauss_dev, seed); return 1; } diff --git a/fio.h b/fio.h index f6880841..0fb86eae 100644 --- a/fio.h +++ b/fio.h @@ -649,6 +649,7 @@ enum { FIO_RAND_DIST_RANDOM = 0, FIO_RAND_DIST_ZIPF, FIO_RAND_DIST_PARETO, + FIO_RAND_DIST_GAUSS, }; #define FIO_DEF_ZIPF 1.1 diff --git a/io_u.c b/io_u.c index 975d2424..16065128 100644 --- a/io_u.c +++ b/io_u.c @@ -149,6 +149,15 @@ static int __get_next_rand_offset_pareto(struct thread_data *td, return 0; } +static int __get_next_rand_offset_gauss(struct thread_data *td, + struct fio_file *f, enum fio_ddir ddir, + uint64_t *b) +{ + *b = gauss_next(&f->gauss); + return 0; +} + + static int flist_cmp(void *data, struct flist_head *a, struct flist_head *b) { struct rand_off *r1 = flist_entry(a, struct rand_off, list); @@ -166,6 +175,8 @@ static int get_off_from_method(struct thread_data *td, struct fio_file *f, return __get_next_rand_offset_zipf(td, f, ddir, b); else if (td->o.random_distribution == FIO_RAND_DIST_PARETO) return __get_next_rand_offset_pareto(td, f, ddir, b); + else if (td->o.random_distribution == FIO_RAND_DIST_GAUSS) + return __get_next_rand_offset_gauss(td, f, ddir, b); log_err("fio: unknown random distribution: %d\n", td->o.random_distribution); return 1; diff --git a/lib/gauss.c b/lib/gauss.c new file mode 100644 index 00000000..cd8b6e3e --- /dev/null +++ b/lib/gauss.c @@ -0,0 +1,53 @@ +#include +#include +#include +#include "../hash.h" +#include "gauss.h" + +#define GAUSS_ITERS 12 + +static int gauss_dev(struct gauss_state *gs) +{ + unsigned int r; + int vr; + + if (!gs->stddev) + return 0; + + r = __rand(&gs->r); + vr = gs->stddev * (r / (FRAND_MAX + 1.0)); + + return vr - gs->stddev / 2; +} + +unsigned long long gauss_next(struct gauss_state *gs) +{ + unsigned long long sum = 0; + int i; + + for (i = 0; i < GAUSS_ITERS; i++) + sum += __rand(&gs->r) % (gs->nranges + 1); + + sum = (sum + GAUSS_ITERS - 1) / GAUSS_ITERS; + + if (gs->stddev) { + int dev = gauss_dev(gs); + + while (dev + sum >= gs->nranges) + dev /= 2; + sum += dev; + } + + return __hash_u64(sum) % gs->nranges; +} + +void gauss_init(struct gauss_state *gs, unsigned long nranges, unsigned int d, + unsigned int seed) +{ + memset(gs, 0, sizeof(*gs)); + init_rand_seed(&gs->r, seed); + gs->nranges = nranges; + gs->stddev = d; + if (gs->stddev > nranges / 2) + gs->stddev = nranges / 2; +} diff --git a/lib/gauss.h b/lib/gauss.h new file mode 100644 index 00000000..be45249c --- /dev/null +++ b/lib/gauss.h @@ -0,0 +1,17 @@ +#ifndef FIO_GAUSS_H +#define FIO_GAUSS_H + +#include +#include "rand.h" + +struct gauss_state { + struct frand_state r; + uint64_t nranges; + unsigned int stddev; +}; + +void gauss_init(struct gauss_state *gs, unsigned long nranges, unsigned int d, + unsigned int seed); +unsigned long long gauss_next(struct gauss_state *gs); + +#endif diff --git a/options.c b/options.c index 337fecdb..1857d411 100644 --- a/options.c +++ b/options.c @@ -718,6 +718,8 @@ static int str_random_distribution_cb(void *data, const char *str) val = FIO_DEF_ZIPF; else if (td->o.random_distribution == FIO_RAND_DIST_PARETO) val = FIO_DEF_PARETO; + else if (td->o.random_distribution == FIO_RAND_DIST_GAUSS) + val = 0.0; else return 0; @@ -736,13 +738,14 @@ static int str_random_distribution_cb(void *data, const char *str) return 1; } td->o.zipf_theta.u.f = val; - } else { + } else if (td->o.random_distribution == FIO_RAND_DIST_PARETO) { if (val <= 0.00 || val >= 1.00) { log_err("fio: pareto input out of range (0 < input < 1.0)\n"); return 1; } td->o.pareto_h.u.f = val; - } + } else + td->o.gauss_dev = val; return 0; } @@ -1875,6 +1878,10 @@ struct fio_option fio_options[FIO_MAX_OPTS] = { .oval = FIO_RAND_DIST_PARETO, .help = "Pareto distribution", }, + { .ival = "normal", + .oval = FIO_RAND_DIST_GAUSS, + .help = "Normal (gaussian) distribution", + }, }, .category = FIO_OPT_C_IO, .group = FIO_OPT_G_RANDOM, diff --git a/thread_options.h b/thread_options.h index 5a2428a4..69318066 100644 --- a/thread_options.h +++ b/thread_options.h @@ -126,6 +126,7 @@ struct thread_options { unsigned int verify_only; unsigned int random_distribution; + unsigned int gauss_dev; fio_fp64_t zipf_theta; fio_fp64_t pareto_h; @@ -354,7 +355,7 @@ struct thread_options_pack { uint32_t bs_is_seq_rand; uint32_t random_distribution; - uint32_t pad; + uint32_t gauss_dev; fio_fp64_t zipf_theta; fio_fp64_t pareto_h; -- 2.25.1