From 925fee33e47f7eb755ee893e87f0de2bd405a8cc Mon Sep 17 00:00:00 2001
From: Jens Axboe <axboe@kernel.dk>
Date: Tue, 6 Nov 2012 13:50:32 +0100
Subject: [PATCH] Add pareto distribution randomizer

Signed-off-by: Jens Axboe <axboe@kernel.dk>
---
 fio.h      |  2 ++
 init.c     |  6 +++++-
 io_u.c     | 15 +++++++++++++--
 lib/zipf.c | 18 ++++++++++++++++++
 lib/zipf.h |  4 ++++
 options.c  | 20 +++++++++++++++-----
 6 files changed, 57 insertions(+), 8 deletions(-)

diff --git a/fio.h b/fio.h
index 15ab3084..7eb0abba 100644
--- a/fio.h
+++ b/fio.h
@@ -180,6 +180,7 @@ struct thread_options {
 
 	unsigned int random_distribution;
 	double zipf_theta;
+	double pareto_h;
 
 	unsigned int hugepage_size;
 	unsigned int rw_min_bs;
@@ -827,6 +828,7 @@ enum {
 enum {
 	FIO_RAND_DIST_RANDOM	= 0,
 	FIO_RAND_DIST_ZIPF,
+	FIO_RAND_DIST_PARETO,
 };
 
 #endif
diff --git a/init.c b/init.c
index 1cee0964..bf4aa030 100644
--- a/init.c
+++ b/init.c
@@ -393,7 +393,11 @@ static void init_rand_distribution(struct thread_data *td)
 	range_size = min(td->o.min_bs[DDIR_READ], td->o.min_bs[DDIR_WRITE]);
 
 	nranges = (td->o.size + range_size - 1) / range_size;
-	zipf_init(&td->zipf, nranges, td->o.zipf_theta);
+
+	if (td->o.random_distribution == FIO_RAND_DIST_ZIPF)
+		zipf_init(&td->zipf, nranges, td->o.zipf_theta);
+	else
+		pareto_init(&td->zipf, nranges, td->o.pareto_h);
 }
 
 /*
diff --git a/io_u.c b/io_u.c
index 8f2ce302..688249bd 100644
--- a/io_u.c
+++ b/io_u.c
@@ -234,13 +234,22 @@ ret:
 	return 0;
 }
 
-static int __get_next_rand_offset_zipf(struct thread_data *td, struct fio_file *f,
-				  enum fio_ddir ddir, unsigned long long *b)
+static int __get_next_rand_offset_zipf(struct thread_data *td,
+				       struct fio_file *f, enum fio_ddir ddir,
+				       unsigned long long *b)
 {
 	*b = zipf_next(&td->zipf);
 	return 0;
 }
 
+static int __get_next_rand_offset_pareto(struct thread_data *td,
+					 struct fio_file *f, enum fio_ddir ddir,
+					 unsigned long long *b)
+{
+	*b = pareto_next(&td->zipf);
+	return 0;
+}
+
 static int get_next_rand_offset(struct thread_data *td, struct fio_file *f,
 				enum fio_ddir ddir, unsigned long long *b)
 {
@@ -248,6 +257,8 @@ static int get_next_rand_offset(struct thread_data *td, struct fio_file *f,
 		return __get_next_rand_offset(td, f, ddir, b);
 	else if (td->o.random_distribution == FIO_RAND_DIST_ZIPF)
 		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);
 
 	log_err("fio: unknown random distribution: %d\n", td->o.random_distribution);
 	return 1;
diff --git a/lib/zipf.c b/lib/zipf.c
index 34f28772..28e8d77e 100644
--- a/lib/zipf.c
+++ b/lib/zipf.c
@@ -126,3 +126,21 @@ unsigned long long zipf_next(struct zipf_state *zs)
 
 	return val - 1;
 }
+
+void pareto_init(struct zipf_state *zs, unsigned long nranges, double h)
+{
+	memset(zs, 0, sizeof(*zs));
+
+	zs->nranges = nranges;
+	zs->pareto_pow = log(h) / log(1.0 - h);
+
+	init_rand(&zs->rand);
+}
+
+unsigned long long pareto_next(struct zipf_state *zs)
+{
+	double rand = (double) __rand(&zs->rand) / (double) FRAND_MAX;
+	unsigned long long n = zs->nranges - 1;
+
+	return n * pow(rand, zs->pareto_pow);
+}
diff --git a/lib/zipf.h b/lib/zipf.h
index 6578ef1c..97a9b32f 100644
--- a/lib/zipf.h
+++ b/lib/zipf.h
@@ -8,10 +8,14 @@ struct zipf_state {
 	double theta;
 	double zeta2;
 	double zetan;
+	double pareto_pow;
 	struct frand_state rand;
 };
 
 void zipf_init(struct zipf_state *zs, unsigned long nranges, double theta);
 unsigned long long zipf_next(struct zipf_state *zs);
 
+void pareto_init(struct zipf_state *zs, unsigned long nranges, double h);
+unsigned long long pareto_next(struct zipf_state *zs);
+
 #endif
diff --git a/options.c b/options.c
index 05a6a508..ea1ffb13 100644
--- a/options.c
+++ b/options.c
@@ -734,19 +734,25 @@ static int str_random_distribution_cb(void *data, const char *str)
 	double val;
 	char *nr;
 
-	if (td->o.random_distribution == FIO_RAND_DIST_RANDOM)
+	if (td->o.random_distribution == FIO_RAND_DIST_ZIPF)
+		val = 1.1;
+	else if (td->o.random_distribution == FIO_RAND_DIST_PARETO)
+		val = 0.2;
+	else
 		return 0;
 
 	nr = get_opt_postfix(str);
-	if (!nr)
-		val = 0.6;
-	else if (!str_to_float(nr, &val)) {
+	if (nr && !str_to_float(nr, &val)) {
 		log_err("fio: random postfix parsing failed\n");
 		free(nr);
 		return 1;
 	}
 
-	td->o.zipf_theta = val;
+	if (td->o.random_distribution == FIO_RAND_DIST_ZIPF)
+		td->o.zipf_theta = val;
+	else
+		td->o.pareto_h = val;
+
 	free(nr);
 	return 0;
 }
@@ -1511,6 +1517,10 @@ static struct fio_option options[FIO_MAX_OPTS] = {
 			    .oval = FIO_RAND_DIST_ZIPF,
 			    .help = "Zipf distribution",
 			  },
+			  { .ival = "pareto",
+			    .oval = FIO_RAND_DIST_PARETO,
+			    .help = "Pareto distribution",
+			  },
 		},
 	},
 	{
-- 
2.25.1