t/genzipf.c

   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
   6  * with theta 1.2, using 262144 (1 GiB / 4096) values and split the
   7  * reporting into 20 buckets:
   8  *
   9  *      ./t/fio-genzipf -t zipf -i 1.2 -g 1 -b 4096 -o 20
  10  *
  11  * Only the distribution type (zipf or pareto) and spread input need
  12  * to be given, if not given defaults are used.
  13  *
  14  */
  15 #include <stdio.h>
  16 #include <stdlib.h>
  17 #include <fcntl.h>
  18 #include <string.h>
  19 #include <unistd.h>
  20
  21 #include "../lib/zipf.h"
  22 #include "../lib/gauss.h"
  23 #include "../flist.h"
  24 #include "../hash.h"
  25
  26 #define DEF_NR_OUTPUT   20
  27
  28 struct node {
  29         struct flist_head list;
  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;
  37
  38 enum {
  39         TYPE_NONE = 0,
  40         TYPE_ZIPF,
  41         TYPE_PARETO,
  42         TYPE_NORMAL,
  43 };
  44 static const char *dist_types[] = { "None", "Zipf", "Pareto", "Normal" };
  45
  46 enum {
  47         OUTPUT_NORMAL,
  48         OUTPUT_CSV,
  49 };
  50
  51 static int dist_type = TYPE_ZIPF;
  52 static unsigned long gib_size = 500;
  53 static unsigned long block_size = 4096;
  54 static unsigned long output_nranges = DEF_NR_OUTPUT;
  55 static double percentage;
  56 static double dist_val;
  57 static int output_type = OUTPUT_NORMAL;
  58
  59 #define DEF_ZIPF_VAL    1.2
  60 #define DEF_PARETO_VAL  0.3
  61
  62 static unsigned int hashv(unsigned long long val)
  63 {
  64         return jhash(&val, sizeof(val), 0) & (hash_size - 1);
  65 }
  66
  67 static struct node *hash_lookup(unsigned long long val)
  68 {
  69         struct flist_head *l = &hash[hashv(val)];
  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
  82 static void hash_insert(struct node *n, unsigned long long val)
  83 {
  84         struct flist_head *l = &hash[hashv(val)];
  85
  86         n->val = val;
  87         n->hits = 1;
  88         flist_add_tail(&n->list, l);
  89 }
  90
  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");
  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");
  99         printf("\t-b\tBlock size of a given range (in bytes)\n");
 100         printf("\t-g\tSize of data set (in gigabytes)\n");
 101         printf("\t-o\tNumber of output rows\n");
 102         printf("\t-c\tOutput ranges in CSV format\n");
 103 }
 104
 105 static int parse_options(int argc, char *argv[])
 106 {
 107         const char *optstring = "t:g:i:o:b:p:ch";
 108         int c, dist_val_set = 0;
 109
 110         while ((c = getopt(argc, argv, optstring)) != -1) {
 111                 switch (c) {
 112                 case 'h':
 113                         usage();
 114                         return 1;
 115                 case 'p':
 116                         percentage = atof(optarg);
 117                         break;
 118                 case 'b':
 119                         block_size = strtoul(optarg, NULL, 10);
 120                         break;
 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;
 126                         else if (!strncmp(optarg, "normal", 6))
 127                                 dist_type = TYPE_NORMAL;
 128                         else {
 129                                 printf("wrong dist type: %s\n", optarg);
 130                                 return 1;
 131                         }
 132                         break;
 133                 case 'g':
 134                         gib_size = strtoul(optarg, NULL, 10);
 135                         break;
 136                 case 'i':
 137                         dist_val = atof(optarg);
 138                         dist_val_set = 1;
 139                         break;
 140                 case 'o':
 141                         output_nranges = strtoul(optarg, NULL, 10);
 142                         break;
 143                 case 'c':
 144                         output_type = OUTPUT_CSV;
 145                         break;
 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
 171 struct output_sum {
 172         double output;
 173         unsigned int nranges;
 174 };
 175
 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
 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) {
 230                                 double cs = (double) i * block_size / (1024.0 * 1024.0);
 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
 280 int main(int argc, char *argv[])
 281 {
 282         unsigned long offset;
 283         unsigned long long nranges;
 284         unsigned long nnodes;
 285         struct node *nodes;
 286         struct zipf_state zs;
 287         struct gauss_state gs;
 288         int i, j;
 289
 290         if (parse_options(argc, argv))
 291                 return 1;
 292
 293         if (output_type != OUTPUT_CSV)
 294                 printf("Generating %s distribution with %f input and %lu GiB size and %lu block_size.\n",
 295                        dist_types[dist_type], dist_val, gib_size, block_size);
 296
 297         nranges = gib_size * 1024 * 1024 * 1024ULL;
 298         nranges /= block_size;
 299
 300         if (dist_type == TYPE_ZIPF)
 301                 zipf_init(&zs, nranges, dist_val, 1);
 302         else if (dist_type == TYPE_PARETO)
 303                 pareto_init(&zs, nranges, dist_val, 1);
 304         else
 305                 gauss_init(&gs, nranges, dist_val, 1);
 306
 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
 314         hash = calloc(hash_size, sizeof(struct flist_head));
 315         for (i = 0; i < hash_size; i++)
 316                 INIT_FLIST_HEAD(&hash[i]);
 317
 318         nodes = malloc(nranges * sizeof(struct node));
 319
 320         for (i = j = 0; i < nranges; i++) {
 321                 struct node *n;
 322
 323                 if (dist_type == TYPE_ZIPF)
 324                         offset = zipf_next(&zs);
 325                 else if (dist_type == TYPE_PARETO)
 326                         offset = pareto_next(&zs);
 327                 else
 328                         offset = gauss_next(&gs);
 329
 330                 n = hash_lookup(offset);
 331                 if (n)
 332                         n->hits++;
 333                 else {
 334                         hash_insert(&nodes[j], offset);
 335                         j++;
 336                 }
 337         }
 338
 339         qsort(nodes, j, sizeof(struct node), node_cmp);
 340         nnodes = j;
 341
 342         if (output_type == OUTPUT_CSV)
 343                 output_csv(nodes, nnodes);
 344         else
 345                 output_normal(nodes, nnodes, nranges);
 346
 347         free(hash);
 348         free(nodes);
 349         return 0;
 350 }