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 } 351
