Add support for normal/gaussian random distributions

Signed-off-by: Jens Axboe <axboe@fb.com>

diff --git a/Makefile b/Makefile
index 52e515b04f01f87189e41223a02e2d702f959882..1227eb9f2faf0382d26685221842ceb9e74b6138 100644 (file)
--- 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 0fca764e97865b8e4bd9fbaf869a6d9c489c71ec..fbe784e7e2ff281001dc30ba416f65845a6bebf5 100644 (file)
--- 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 fc473102ae3565276db1f6c3d8906f19a089915a..22ec742fc1bc47deb22d5552202100b3ea042717 100644 (file)
--- 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 0fb5589b7c33ce1aa154c21ecf42cf52a682c4d8..7dceddbbf4dc21077d312dace3fa2321ba04f037 100644 (file)
--- 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 f6880841b048353ed027698ba67003b3f0998454..0fb86eaed442324832700d61b70d7123bbecc482 100644 (file)
--- 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 975d2424b2c377c39b331865df7bf8e1c5060a4b..16065128c324e76e3cf9326ff1824fec42baad5b 100644 (file)
--- 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 (file)
index 0000000..cd8b6e3
--- /dev/null
+++ b/lib/gauss.c
@@ -0,0 +1,53 @@
+#include <math.h>
+#include <string.h>
+#include <stdio.h>
+#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 (file)
index 0000000..be45249
--- /dev/null
+++ b/lib/gauss.h
@@ -0,0 +1,17 @@
+#ifndef FIO_GAUSS_H
+#define FIO_GAUSS_H
+
+#include <inttypes.h>
+#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 337fecdb54231fca391b837cf363f0552d03d84b..1857d4115f9a80234ec8aec2bb4a591405448a70 100644 (file)
--- 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 5a2428a41bb4c6b48971130d678e911de02c1e95..693180664b1fa6f6307e2a07e51be296a779644d 100644 (file)
--- 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;