[fio.git] / t / genzipf.c

/*
 * Generate/analyze pareto/zipf distributions to better understand
 * what an access pattern would look like.
 *
 * For instance, the following would generate a zipf distribution
 * with theta 1.2, using 262144 (1 GiB / 4096) values and split the
 * reporting into 20 buckets:
 *
 *	./t/fio-genzipf -t zipf -i 1.2 -g 1 -b 4096 -o 20
 *
 * Only the distribution type (zipf or pareto) and spread input need
 * to be given, if not given defaults are used.
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <string.h>
#include <unistd.h>

#include "../lib/zipf.h"
#include "../lib/gauss.h"
#include "../flist.h"
#include "../hash.h"

#define DEF_NR_OUTPUT	20

struct node {
	struct flist_head list;
	unsigned long long val;
	unsigned long hits;
};

static struct flist_head *hash;
static unsigned long hash_bits = 24;
static unsigned long hash_size = 1 << 24;

enum {
	TYPE_NONE = 0,
	TYPE_ZIPF,
	TYPE_PARETO,
	TYPE_NORMAL,
};
static const char *dist_types[] = { "None", "Zipf", "Pareto", "Normal" };

enum {
	OUTPUT_NORMAL,
	OUTPUT_CSV,
};

static int dist_type = TYPE_ZIPF;
static unsigned long gib_size = 500;
static unsigned long block_size = 4096;
static unsigned long output_nranges = DEF_NR_OUTPUT;
static double percentage;
static double dist_val;
static int output_type = OUTPUT_NORMAL;

#define DEF_ZIPF_VAL	1.2
#define DEF_PARETO_VAL	0.3

static unsigned int hashv(unsigned long long val)
{
	return jhash(&val, sizeof(val), 0) & (hash_size - 1);
}

static struct node *hash_lookup(unsigned long long val)
{
	struct flist_head *l = &hash[hashv(val)];
	struct flist_head *entry;
	struct node *n;

	flist_for_each(entry, l) {
		n = flist_entry(entry, struct node, list);
		if (n->val == val)
			return n;
	}

	return NULL;
}

static void hash_insert(struct node *n, unsigned long long val)
{
	struct flist_head *l = &hash[hashv(val)];

	n->val = val;
	n->hits = 1;
	flist_add_tail(&n->list, l);
}

static void usage(void)
{
	printf("genzipf: test zipf/pareto values for fio input\n");
	printf("\t-h\tThis help screen\n");
	printf("\t-p\tGenerate size of data set that are hit by this percentage\n");
	printf("\t-t\tDistribution type (zipf, pareto, or normal)\n");
	printf("\t-i\tDistribution algorithm input (zipf theta, pareto power,\n"
		"\t\tor normal %% deviation)\n");
	printf("\t-b\tBlock size of a given range (in bytes)\n");
	printf("\t-g\tSize of data set (in gigabytes)\n");
	printf("\t-o\tNumber of output rows\n");
	printf("\t-c\tOutput ranges in CSV format\n");
}

static int parse_options(int argc, char *argv[])
{
	const char *optstring = "t:g:i:o:b:p:ch";
	int c, dist_val_set = 0;

	while ((c = getopt(argc, argv, optstring)) != -1) {
		switch (c) {
		case 'h':
			usage();
			return 1;
		case 'p':
			percentage = atof(optarg);
			break;
		case 'b':
			block_size = strtoul(optarg, NULL, 10);
			break;
		case 't':
			if (!strncmp(optarg, "zipf", 4))
				dist_type = TYPE_ZIPF;
			else if (!strncmp(optarg, "pareto", 6))
				dist_type = TYPE_PARETO;
			else if (!strncmp(optarg, "normal", 6))
				dist_type = TYPE_NORMAL;
			else {
				printf("wrong dist type: %s\n", optarg);
				return 1;
			}
			break;
		case 'g':
			gib_size = strtoul(optarg, NULL, 10);
			break;
		case 'i':
			dist_val = atof(optarg);
			dist_val_set = 1;
			break;
		case 'o':
			output_nranges = strtoul(optarg, NULL, 10);
			break;
		case 'c':
			output_type = OUTPUT_CSV;
			break;
		default:
			printf("bad option %c\n", c);
			return 1;
		}
	}

	if (dist_type == TYPE_PARETO) {
		if ((dist_val >= 1.00 || dist_val < 0.00)) {
			printf("pareto input must be > 0.00 and < 1.00\n");
			return 1;
		}
		if (!dist_val_set)
			dist_val = DEF_PARETO_VAL;
	} else if (dist_type == TYPE_ZIPF) {
		if (dist_val == 1.0) {
			printf("zipf input must be different than 1.0\n");
			return 1;
		}
		if (!dist_val_set)
			dist_val = DEF_ZIPF_VAL;
	}

	return 0;
}

struct output_sum {
	double output;
	unsigned int nranges;
};

static int node_cmp(const void *p1, const void *p2)
{
	const struct node *n1 = p1;
	const struct node *n2 = p2;

	return n2->hits - n1->hits;
}

static void output_csv(struct node *nodes, unsigned long nnodes)
{
	unsigned long i;

	printf("rank, count\n");
	for (i = 0; i < nnodes; i++)
		printf("%lu, %lu\n", i, nodes[i].hits);
}

static void output_normal(struct node *nodes, unsigned long nnodes,
			  unsigned long nranges)
{
	unsigned long i, j, cur_vals, interval_step, next_interval, total_vals;
	unsigned long blocks = percentage * nnodes / 100;
	double hit_percent_sum = 0;
	unsigned long long hit_sum = 0;
	double perc, perc_i;
	struct output_sum *output_sums;

	interval_step = (nnodes - 1) / output_nranges + 1;
	next_interval = interval_step;
	output_sums = malloc(output_nranges * sizeof(struct output_sum));

	for (i = 0; i < output_nranges; i++) {
		output_sums[i].output = 0.0;
		output_sums[i].nranges = 0;
	}

	j = total_vals = cur_vals = 0;

	for (i = 0; i < nnodes; i++) {
		struct output_sum *os = &output_sums[j];
		struct node *node = &nodes[i];
		cur_vals += node->hits;
		total_vals += node->hits;
		os->nranges += node->hits;
		if (i == (next_interval) -1 || i == nnodes - 1) {
			os->output = (double) cur_vals / (double) nranges;
			os->output *= 100.0;
			cur_vals = 0;
			next_interval += interval_step;
			j++;
		}

		if (percentage) {
			if (total_vals >= blocks) {
				double cs = (double) i * block_size / (1024.0 * 1024.0);
				char p = 'M';

				if (cs > 1024.0) {
					cs /= 1024.0;
					p = 'G';
				}
				if (cs > 1024.0) {
					cs /= 1024.0;
					p = 'T';
				}

				printf("%.2f%% of hits satisfied in %.3f%cB of cache\n", percentage, cs, p);
				percentage = 0.0;
			}
		}
	}

	perc_i = 100.0 / (double)output_nranges;
	perc = 0.0;

	printf("\n   Rows           Hits %%         Sum %%           # Hits          Size\n");
	printf("-----------------------------------------------------------------------\n");
	for (i = 0; i < output_nranges; i++) {
		struct output_sum *os = &output_sums[i];
		double gb = (double)os->nranges * block_size / 1024.0;
		char p = 'K';

		if (gb > 1024.0) {
			p = 'M';
			gb /= 1024.0;
		}
		if (gb > 1024.0) {
			p = 'G';
			gb /= 1024.0;
		}

		perc += perc_i;
		hit_percent_sum += os->output;
		hit_sum += os->nranges;
		printf("%s %6.2f%%\t%6.2f%%\t\t%6.2f%%\t\t%8u\t%6.2f%c\n",
			i ? "|->" : "Top", perc, os->output, hit_percent_sum,
			os->nranges, gb, p);
	}

	printf("-----------------------------------------------------------------------\n");
	printf("Total\t\t\t\t\t\t%8llu\n", hit_sum);
	free(output_sums);
}

int main(int argc, char *argv[])
{
	unsigned long offset;
	unsigned long long nranges;
	unsigned long nnodes;
	struct node *nodes;
	struct zipf_state zs;
	struct gauss_state gs;
	int i, j;

	if (parse_options(argc, argv))
		return 1;

	if (output_type != OUTPUT_CSV)
		printf("Generating %s distribution with %f input and %lu GiB size and %lu block_size.\n",
		       dist_types[dist_type], dist_val, gib_size, block_size);

	nranges = gib_size * 1024 * 1024 * 1024ULL;
	nranges /= block_size;

	if (dist_type == TYPE_ZIPF)
		zipf_init(&zs, nranges, dist_val, 1);
	else if (dist_type == TYPE_PARETO)
		pareto_init(&zs, nranges, dist_val, 1);
	else
		gauss_init(&gs, nranges, dist_val, 1);

	hash_bits = 0;
	hash_size = nranges;
	while ((hash_size >>= 1) != 0)
		hash_bits++;

	hash_size = 1 << hash_bits;

	hash = calloc(hash_size, sizeof(struct flist_head));
	for (i = 0; i < hash_size; i++)
		INIT_FLIST_HEAD(&hash[i]);

	nodes = malloc(nranges * sizeof(struct node));

	for (i = j = 0; i < nranges; i++) {
		struct node *n;

		if (dist_type == TYPE_ZIPF)
			offset = zipf_next(&zs);
		else if (dist_type == TYPE_PARETO)
			offset = pareto_next(&zs);
		else
			offset = gauss_next(&gs);

		n = hash_lookup(offset);
		if (n)
			n->hits++;
		else {
			hash_insert(&nodes[j], offset);
			j++;
		}
	}

	qsort(nodes, j, sizeof(struct node), node_cmp);
	nnodes = j;

	if (output_type == OUTPUT_CSV)
		output_csv(nodes, nnodes);
	else
		output_normal(nodes, nnodes, nranges);

	free(hash);
	free(nodes);
	return 0;
}
Commit	Line	Data
6ff38856 JA	1	/*
	2	* Generate/analyze pareto/zipf distributions to better understand
	3	* what an access pattern would look like.
	4	*
	5	* For instance, the following would generate a zipf distribution
4870138d RE	6	* with theta 1.2, using 262144 (1 GiB / 4096) values and split the
4870138d RE	7	* reporting into 20 buckets:
6ff38856	8	*
2c9b3ccd	9	* ./t/fio-genzipf -t zipf -i 1.2 -g 1 -b 4096 -o 20
6ff38856	10	*
f880b1f6 JA	11	* Only the distribution type (zipf or pareto) and spread input need
	12	* to be given, if not given defaults are used.
	13	*
6ff38856 JA	14	*/
	15	#include <stdio.h>
	16	#include <stdlib.h>
	17	#include <fcntl.h>
	18	#include <string.h>
921d17ba	19	#include <unistd.h>
6ff38856 JA	20
6ff38856 JA	21	#include "../lib/zipf.h"
c4ba4d4f	22	#include "../lib/gauss.h"
fd6f237d JA	23	#include "../flist.h"
fd6f237d JA	24	#include "../hash.h"
6ff38856	25
2c9b3ccd	26	#define DEF_NR_OUTPUT 20
f880b1f6	27
fd6f237d JA	28	struct node {
fd6f237d JA	29	struct flist_head list;
fd6f237d JA	30	unsigned long long val;
	31	unsigned long hits;
	32	};
	33
	34	static struct flist_head *hash;
	35	static unsigned long hash_bits = 24;
	36	static unsigned long hash_size = 1 << 24;
fd6f237d	37
921d17ba JA	38	enum {
	39	TYPE_NONE = 0,
	40	TYPE_ZIPF,
	41	TYPE_PARETO,
c4ba4d4f	42	TYPE_NORMAL,
921d17ba	43	};
c4ba4d4f	44	static const char *dist_types[] = { "None", "Zipf", "Pareto", "Normal" };
921d17ba	45
85629b7f JA	46	enum {
	47	OUTPUT_NORMAL,
	48	OUTPUT_CSV,
	49	};
	50
921d17ba	51	static int dist_type = TYPE_ZIPF;
4870138d	52	static unsigned long gib_size = 500;
444256ea	53	static unsigned long block_size = 4096;
921d17ba	54	static unsigned long output_nranges = DEF_NR_OUTPUT;
444256ea	55	static double percentage;
921d17ba	56	static double dist_val;
85629b7f	57	static int output_type = OUTPUT_NORMAL;
921d17ba JA	58
	59	#define DEF_ZIPF_VAL 1.2
	60	#define DEF_PARETO_VAL 0.3
	61
87f5fce3 JA	62	static unsigned int hashv(unsigned long long val)
	63	{
	64	return jhash(&val, sizeof(val), 0) & (hash_size - 1);
	65	}
	66
fd6f237d JA	67	static struct node *hash_lookup(unsigned long long val)
fd6f237d JA	68	{
87f5fce3	69	struct flist_head *l = &hash[hashv(val)];
fd6f237d JA	70	struct flist_head *entry;
	71	struct node *n;
	72
	73	flist_for_each(entry, l) {
	74	n = flist_entry(entry, struct node, list);
	75	if (n->val == val)
	76	return n;
	77	}
	78
	79	return NULL;
	80	}
	81
87f5fce3	82	static void hash_insert(struct node *n, unsigned long long val)
fd6f237d	83	{
87f5fce3	84	struct flist_head *l = &hash[hashv(val)];
fd6f237d JA	85
	86	n->val = val;
	87	n->hits = 1;
	88	flist_add_tail(&n->list, l);
6ff38856 JA	89	}
6ff38856 JA	90
4e98a450 JA	91	static void usage(void)
	92	{
	93	printf("genzipf: test zipf/pareto values for fio input\n");
	94	printf("\t-h\tThis help screen\n");
	95	printf("\t-p\tGenerate size of data set that are hit by this percentage\n");
c4ba4d4f JA	96	printf("\t-t\tDistribution type (zipf, pareto, or normal)\n");
	97	printf("\t-i\tDistribution algorithm input (zipf theta, pareto power,\n"
	98	"\t\tor normal %% deviation)\n");
4e98a450 JA	99	printf("\t-b\tBlock size of a given range (in bytes)\n");
4e98a450 JA	100	printf("\t-g\tSize of data set (in gigabytes)\n");
2c9b3ccd	101	printf("\t-o\tNumber of output rows\n");
4e98a450 JA	102	printf("\t-c\tOutput ranges in CSV format\n");
	103	}
	104
921d17ba JA	105	static int parse_options(int argc, char *argv[])
921d17ba JA	106	{
4e98a450	107	const char *optstring = "t:g:i:o:b:p:ch";
921d17ba JA	108	int c, dist_val_set = 0;
	109
	110	while ((c = getopt(argc, argv, optstring)) != -1) {
	111	switch (c) {
4e98a450 JA	112	case 'h':
	113	usage();
	114	return 1;
444256ea JA	115	case 'p':
	116	percentage = atof(optarg);
	117	break;
	118	case 'b':
	119	block_size = strtoul(optarg, NULL, 10);
	120	break;
921d17ba JA	121	case 't':
	122	if (!strncmp(optarg, "zipf", 4))
	123	dist_type = TYPE_ZIPF;
	124	else if (!strncmp(optarg, "pareto", 6))
	125	dist_type = TYPE_PARETO;
c4ba4d4f JA	126	else if (!strncmp(optarg, "normal", 6))
c4ba4d4f JA	127	dist_type = TYPE_NORMAL;
921d17ba JA	128	else {
	129	printf("wrong dist type: %s\n", optarg);
	130	return 1;
	131	}
	132	break;
	133	case 'g':
4870138d	134	gib_size = strtoul(optarg, NULL, 10);
921d17ba JA	135	break;
	136	case 'i':
	137	dist_val = atof(optarg);
	138	dist_val_set = 1;
	139	break;
921d17ba JA	140	case 'o':
	141	output_nranges = strtoul(optarg, NULL, 10);
	142	break;
355934b7	143	case 'c':
85629b7f	144	output_type = OUTPUT_CSV;
355934b7	145	break;
921d17ba JA	146	default:
	147	printf("bad option %c\n", c);
	148	return 1;
	149	}
	150	}
	151
	152	if (dist_type == TYPE_PARETO) {
	153	if ((dist_val >= 1.00 \|\| dist_val < 0.00)) {
	154	printf("pareto input must be > 0.00 and < 1.00\n");
	155	return 1;
	156	}
	157	if (!dist_val_set)
	158	dist_val = DEF_PARETO_VAL;
	159	} else if (dist_type == TYPE_ZIPF) {
	160	if (dist_val == 1.0) {
	161	printf("zipf input must be different than 1.0\n");
	162	return 1;
	163	}
	164	if (!dist_val_set)
	165	dist_val = DEF_ZIPF_VAL;
	166	}
	167
	168	return 0;
	169	}
	170
444256ea JA	171	struct output_sum {
	172	double output;
	173	unsigned int nranges;
	174	};
	175
24baa4c7 JA	176	static int node_cmp(const void p1, const void p2)
	177	{
	178	const struct node *n1 = p1;
	179	const struct node *n2 = p2;
	180
	181	return n2->hits - n1->hits;
	182	}
	183
85629b7f JA	184	static void output_csv(struct node *nodes, unsigned long nnodes)
	185	{
	186	unsigned long i;
	187
	188	printf("rank, count\n");
	189	for (i = 0; i < nnodes; i++)
	190	printf("%lu, %lu\n", i, nodes[i].hits);
	191	}
	192
	193	static void output_normal(struct node *nodes, unsigned long nnodes,
	194	unsigned long nranges)
	195	{
	196	unsigned long i, j, cur_vals, interval_step, next_interval, total_vals;
	197	unsigned long blocks = percentage * nnodes / 100;
	198	double hit_percent_sum = 0;
	199	unsigned long long hit_sum = 0;
	200	double perc, perc_i;
	201	struct output_sum *output_sums;
	202
	203	interval_step = (nnodes - 1) / output_nranges + 1;
	204	next_interval = interval_step;
	205	output_sums = malloc(output_nranges * sizeof(struct output_sum));
	206
	207	for (i = 0; i < output_nranges; i++) {
	208	output_sums[i].output = 0.0;
	209	output_sums[i].nranges = 0;
	210	}
	211
	212	j = total_vals = cur_vals = 0;
	213
	214	for (i = 0; i < nnodes; i++) {
	215	struct output_sum *os = &output_sums[j];
	216	struct node *node = &nodes[i];
	217	cur_vals += node->hits;
	218	total_vals += node->hits;
	219	os->nranges += node->hits;
	220	if (i == (next_interval) -1 \|\| i == nnodes - 1) {
	221	os->output = (double) cur_vals / (double) nranges;
	222	os->output *= 100.0;
	223	cur_vals = 0;
	224	next_interval += interval_step;
	225	j++;
	226	}
	227
	228	if (percentage) {
	229	if (total_vals >= blocks) {
18ae9b09	230	double cs = (double) i * block_size / (1024.0 * 1024.0);
85629b7f JA	231	char p = 'M';
	232
	233	if (cs > 1024.0) {
	234	cs /= 1024.0;
	235	p = 'G';
	236	}
	237	if (cs > 1024.0) {
	238	cs /= 1024.0;
	239	p = 'T';
	240	}
	241
	242	printf("%.2f%% of hits satisfied in %.3f%cB of cache\n", percentage, cs, p);
	243	percentage = 0.0;
	244	}
	245	}
	246	}
	247
	248	perc_i = 100.0 / (double)output_nranges;
	249	perc = 0.0;
	250
	251	printf("\n Rows Hits %% Sum %% # Hits Size\n");
	252	printf("-----------------------------------------------------------------------\n");
	253	for (i = 0; i < output_nranges; i++) {
	254	struct output_sum *os = &output_sums[i];
	255	double gb = (double)os->nranges * block_size / 1024.0;
	256	char p = 'K';
	257
	258	if (gb > 1024.0) {
	259	p = 'M';
	260	gb /= 1024.0;
	261	}
	262	if (gb > 1024.0) {
	263	p = 'G';
	264	gb /= 1024.0;
	265	}
	266
	267	perc += perc_i;
	268	hit_percent_sum += os->output;
	269	hit_sum += os->nranges;
	270	printf("%s %6.2f%%\t%6.2f%%\t\t%6.2f%%\t\t%8u\t%6.2f%c\n",
	271	i ? "\|->" : "Top", perc, os->output, hit_percent_sum,
	272	os->nranges, gb, p);
	273	}
	274
	275	printf("-----------------------------------------------------------------------\n");
	276	printf("Total\t\t\t\t\t\t%8llu\n", hit_sum);
	277	free(output_sums);
	278	}
	279
6ff38856 JA	280	int main(int argc, char *argv[])
6ff38856 JA	281	{
fd6f237d	282	unsigned long offset;
444256ea	283	unsigned long long nranges;
85629b7f	284	unsigned long nnodes;
24baa4c7	285	struct node *nodes;
6ff38856	286	struct zipf_state zs;
c4ba4d4f	287	struct gauss_state gs;
85629b7f	288	int i, j;
6ff38856	289
921d17ba	290	if (parse_options(argc, argv))
6ff38856	291	return 1;
6ff38856	292
85629b7f	293	if (output_type != OUTPUT_CSV)
4870138d RE	294	printf("Generating %s distribution with %f input and %lu GiB size and %lu block_size.\n",
4870138d RE	295	dist_types[dist_type], dist_val, gib_size, block_size);
444256ea	296
4870138d	297	nranges = gib_size * 1024 * 1024 * 1024ULL;
444256ea	298	nranges /= block_size;
f880b1f6	299
921d17ba JA	300	if (dist_type == TYPE_ZIPF)
921d17ba JA	301	zipf_init(&zs, nranges, dist_val, 1);
c4ba4d4f	302	else if (dist_type == TYPE_PARETO)
921d17ba	303	pareto_init(&zs, nranges, dist_val, 1);
c4ba4d4f JA	304	else
c4ba4d4f JA	305	gauss_init(&gs, nranges, dist_val, 1);
6ff38856	306
c71224e7 JA	307	hash_bits = 0;
	308	hash_size = nranges;
	309	while ((hash_size >>= 1) != 0)
	310	hash_bits++;
	311
	312	hash_size = 1 << hash_bits;
	313
87f5fce3	314	hash = calloc(hash_size, sizeof(struct flist_head));
fd6f237d JA	315	for (i = 0; i < hash_size; i++)
	316	INIT_FLIST_HEAD(&hash[i]);
	317
24baa4c7 JA	318	nodes = malloc(nranges * sizeof(struct node));
24baa4c7 JA	319
2c9b3ccd	320	for (i = j = 0; i < nranges; i++) {
fd6f237d	321	struct node *n;
6ff38856	322
921d17ba	323	if (dist_type == TYPE_ZIPF)
fd6f237d	324	offset = zipf_next(&zs);
c4ba4d4f	325	else if (dist_type == TYPE_PARETO)
fd6f237d	326	offset = pareto_next(&zs);
c4ba4d4f JA	327	else
c4ba4d4f JA	328	offset = gauss_next(&gs);
fd6f237d JA	329
	330	n = hash_lookup(offset);
	331	if (n)
	332	n->hits++;
24baa4c7 JA	333	else {
	334	hash_insert(&nodes[j], offset);
	335	j++;
	336	}
6ff38856 JA	337	}
6ff38856 JA	338
24baa4c7 JA	339	qsort(nodes, j, sizeof(struct node), node_cmp);
24baa4c7 JA	340	nnodes = j;
921d17ba	341
85629b7f JA	342	if (output_type == OUTPUT_CSV)
	343	output_csv(nodes, nnodes);
	344	else
	345	output_normal(nodes, nnodes, nranges);
6ff38856	346
fd6f237d	347	free(hash);
355934b7	348	free(nodes);
6ff38856 JA	349	return 0;
6ff38856 JA	350	}