1 /*
2 * Copyright (C) 2016, Emilio G. Cota <cota@braap.org>
3 *
4 * License: GNU GPL, version 2 or later.
5 * See the COPYING file in the top-level directory.
6 */
7 #include "qemu/osdep.h"
8 #include "qemu/processor.h"
9 #include "qemu/atomic.h"
10 #include "qemu/qht.h"
11 #include "qemu/rcu.h"
12 #include "qemu/xxhash.h"
13 #include "qemu/memalign.h"
14
15 struct thread_stats {
16 size_t rd;
17 size_t not_rd;
18 size_t in;
19 size_t not_in;
20 size_t rm;
21 size_t not_rm;
22 size_t rz;
23 size_t not_rz;
24 };
25
26 struct thread_info {
27 void (*func)(struct thread_info *);
28 struct thread_stats stats;
29 /*
30 * Seed is in the range [1..UINT64_MAX], because the RNG requires
31 * a non-zero seed. To use, subtract 1 and compare against the
32 * threshold with </>=. This lets threshold = 0 never match (0% hit),
33 * and threshold = UINT64_MAX always match (100% hit).
34 */
35 uint64_t seed;
36 bool write_op; /* writes alternate between insertions and removals */
37 bool resize_down;
38 } QEMU_ALIGNED(64); /* avoid false sharing among threads */
39
40 static struct qht ht;
41 static QemuThread *rw_threads;
42
43 #define DEFAULT_RANGE (4096)
44 #define DEFAULT_QHT_N_ELEMS DEFAULT_RANGE
45
46 static unsigned int duration = 1;
47 static unsigned int n_rw_threads = 1;
48 static unsigned long lookup_range = DEFAULT_RANGE;
49 static unsigned long update_range = DEFAULT_RANGE;
50 static size_t init_range = DEFAULT_RANGE;
51 static size_t init_size = DEFAULT_RANGE;
52 static size_t n_ready_threads;
53 static long populate_offset;
54 static long *keys;
55
56 static size_t resize_min;
57 static size_t resize_max;
58 static struct thread_info *rz_info;
59 static unsigned long resize_delay = 1000;
60 static double resize_rate; /* 0.0 to 1.0 */
61 static unsigned int n_rz_threads = 1;
62 static QemuThread *rz_threads;
63 static bool precompute_hash;
64
65 static double update_rate; /* 0.0 to 1.0 */
66 static uint64_t update_threshold;
67 static uint64_t resize_threshold;
68
69 static size_t qht_n_elems = DEFAULT_QHT_N_ELEMS;
70 static int qht_mode;
71
72 static bool test_start;
73 static bool test_stop;
74
75 static struct thread_info *rw_info;
76
77 static const char commands_string[] =
78 " -d = duration, in seconds\n"
79 " -n = number of threads\n"
80 "\n"
81 " -o = offset at which keys start\n"
82 " -p = precompute hashes\n"
83 "\n"
84 " -g = set -s,-k,-K,-l,-r to the same value\n"
85 " -s = initial size hint\n"
86 " -k = initial number of keys\n"
87 " -K = initial range of keys (will be rounded up to pow2)\n"
88 " -l = lookup range of keys (will be rounded up to pow2)\n"
89 " -r = update range of keys (will be rounded up to pow2)\n"
90 "\n"
91 " -u = update rate (0.0 to 100.0), 50/50 split of insertions/removals\n"
92 "\n"
93 " -R = enable auto-resize\n"
94 " -S = resize rate (0.0 to 100.0)\n"
95 " -D = delay (in us) between potential resizes\n"
96 " -N = number of resize threads";
97
usage_complete(int argc,char * argv[])98 static void usage_complete(int argc, char *argv[])
99 {
100 fprintf(stderr, "Usage: %s [options]\n", argv[0]);
101 fprintf(stderr, "options:\n%s\n", commands_string);
102 exit(-1);
103 }
104
is_equal(const void * ap,const void * bp)105 static bool is_equal(const void *ap, const void *bp)
106 {
107 const long *a = ap;
108 const long *b = bp;
109
110 return *a == *b;
111 }
112
h(unsigned long v)113 static uint32_t h(unsigned long v)
114 {
115 return qemu_xxhash2(v);
116 }
117
hval(unsigned long v)118 static uint32_t hval(unsigned long v)
119 {
120 return v;
121 }
122
123 static uint32_t (*hfunc)(unsigned long v) = h;
124
125 /*
126 * From: https://en.wikipedia.org/wiki/Xorshift
127 * This is faster than rand_r(), and gives us a wider range (RAND_MAX is only
128 * guaranteed to be >= INT_MAX).
129 */
xorshift64star(uint64_t x)130 static uint64_t xorshift64star(uint64_t x)
131 {
132 x ^= x >> 12; /* a */
133 x ^= x << 25; /* b */
134 x ^= x >> 27; /* c */
135 return x * UINT64_C(2685821657736338717);
136 }
137
do_rz(struct thread_info * info)138 static void do_rz(struct thread_info *info)
139 {
140 struct thread_stats *stats = &info->stats;
141 uint64_t r = info->seed - 1;
142
143 if (r < resize_threshold) {
144 size_t size = info->resize_down ? resize_min : resize_max;
145 bool resized;
146
147 resized = qht_resize(&ht, size);
148 info->resize_down = !info->resize_down;
149
150 if (resized) {
151 stats->rz++;
152 } else {
153 stats->not_rz++;
154 }
155 }
156 g_usleep(resize_delay);
157 }
158
do_rw(struct thread_info * info)159 static void do_rw(struct thread_info *info)
160 {
161 struct thread_stats *stats = &info->stats;
162 uint64_t r = info->seed - 1;
163 uint32_t hash;
164 long *p;
165
166 if (r >= update_threshold) {
167 bool read;
168
169 p = &keys[r & (lookup_range - 1)];
170 hash = hfunc(*p);
171 read = qht_lookup(&ht, p, hash);
172 if (read) {
173 stats->rd++;
174 } else {
175 stats->not_rd++;
176 }
177 } else {
178 p = &keys[r & (update_range - 1)];
179 hash = hfunc(*p);
180 if (info->write_op) {
181 bool written = false;
182
183 if (qht_lookup(&ht, p, hash) == NULL) {
184 written = qht_insert(&ht, p, hash, NULL);
185 }
186 if (written) {
187 stats->in++;
188 } else {
189 stats->not_in++;
190 }
191 } else {
192 bool removed = false;
193
194 if (qht_lookup(&ht, p, hash)) {
195 removed = qht_remove(&ht, p, hash);
196 }
197 if (removed) {
198 stats->rm++;
199 } else {
200 stats->not_rm++;
201 }
202 }
203 info->write_op = !info->write_op;
204 }
205 }
206
thread_func(void * p)207 static void *thread_func(void *p)
208 {
209 struct thread_info *info = p;
210
211 rcu_register_thread();
212
213 qatomic_inc(&n_ready_threads);
214 while (!qatomic_read(&test_start)) {
215 cpu_relax();
216 }
217
218 rcu_read_lock();
219 while (!qatomic_read(&test_stop)) {
220 info->seed = xorshift64star(info->seed);
221 info->func(info);
222 }
223 rcu_read_unlock();
224
225 rcu_unregister_thread();
226 return NULL;
227 }
228
229 /* sets everything except info->func */
prepare_thread_info(struct thread_info * info,int i)230 static void prepare_thread_info(struct thread_info *info, int i)
231 {
232 /* seed for the RNG; each thread should have a different one */
233 info->seed = (i + 1) ^ time(NULL);
234 /* the first update will be a write */
235 info->write_op = true;
236 /* the first resize will be down */
237 info->resize_down = true;
238
239 memset(&info->stats, 0, sizeof(info->stats));
240 }
241
242 static void
th_create_n(QemuThread ** threads,struct thread_info ** infos,const char * name,void (* func)(struct thread_info *),int offset,int n)243 th_create_n(QemuThread **threads, struct thread_info **infos, const char *name,
244 void (*func)(struct thread_info *), int offset, int n)
245 {
246 struct thread_info *info;
247 QemuThread *th;
248 int i;
249
250 th = g_malloc(sizeof(*th) * n);
251 *threads = th;
252
253 info = qemu_memalign(64, sizeof(*info) * n);
254 *infos = info;
255
256 for (i = 0; i < n; i++) {
257 prepare_thread_info(&info[i], offset + i);
258 info[i].func = func;
259 qemu_thread_create(&th[i], name, thread_func, &info[i],
260 QEMU_THREAD_JOINABLE);
261 }
262 }
263
create_threads(void)264 static void create_threads(void)
265 {
266 th_create_n(&rw_threads, &rw_info, "rw", do_rw, 0, n_rw_threads);
267 th_create_n(&rz_threads, &rz_info, "rz", do_rz, n_rw_threads, n_rz_threads);
268 }
269
pr_params(void)270 static void pr_params(void)
271 {
272 printf("Parameters:\n");
273 printf(" duration: %d s\n", duration);
274 printf(" # of threads: %u\n", n_rw_threads);
275 printf(" initial # of keys: %zu\n", init_size);
276 printf(" initial size hint: %zu\n", qht_n_elems);
277 printf(" auto-resize: %s\n",
278 qht_mode & QHT_MODE_AUTO_RESIZE ? "on" : "off");
279 if (resize_rate) {
280 printf(" resize_rate: %f%%\n", resize_rate * 100.0);
281 printf(" resize range: %zu-%zu\n", resize_min, resize_max);
282 printf(" # resize threads %u\n", n_rz_threads);
283 }
284 printf(" update rate: %f%%\n", update_rate * 100.0);
285 printf(" offset: %ld\n", populate_offset);
286 printf(" initial key range: %zu\n", init_range);
287 printf(" lookup range: %lu\n", lookup_range);
288 printf(" update range: %lu\n", update_range);
289 }
290
do_threshold(double rate,uint64_t * threshold)291 static void do_threshold(double rate, uint64_t *threshold)
292 {
293 /*
294 * For 0 <= rate <= 1, scale to fit in a uint64_t.
295 *
296 * Scale by 2**64, with a special case for 1.0.
297 * The remainder of the possible values are scattered between 0
298 * and 0xfffffffffffff800 (nextafter(0x1p64, 0)).
299 *
300 * Note that we cannot simply scale by UINT64_MAX, because that
301 * value is not representable as an IEEE double value.
302 *
303 * If we scale by the next largest value, nextafter(0x1p64, 0),
304 * then the remainder of the possible values are scattered between
305 * 0 and 0xfffffffffffff000. Which leaves us with a gap between
306 * the final two inputs that is twice as large as any other.
307 */
308 if (rate == 1.0) {
309 *threshold = UINT64_MAX;
310 } else {
311 *threshold = rate * 0x1p64;
312 }
313 }
314
htable_init(void)315 static void htable_init(void)
316 {
317 unsigned long n = MAX(init_range, update_range);
318 uint64_t r = time(NULL);
319 size_t retries = 0;
320 size_t i;
321
322 /* avoid allocating memory later by allocating all the keys now */
323 keys = g_malloc(sizeof(*keys) * n);
324 for (i = 0; i < n; i++) {
325 long val = populate_offset + i;
326
327 keys[i] = precompute_hash ? h(val) : hval(val);
328 }
329
330 /* some sanity checks */
331 g_assert_cmpuint(lookup_range, <=, n);
332
333 /* compute thresholds */
334 do_threshold(update_rate, &update_threshold);
335 do_threshold(resize_rate, &resize_threshold);
336
337 if (resize_rate) {
338 resize_min = n / 2;
339 resize_max = n;
340 assert(resize_min < resize_max);
341 } else {
342 n_rz_threads = 0;
343 }
344
345 /* initialize the hash table */
346 qht_init(&ht, is_equal, qht_n_elems, qht_mode);
347 assert(init_size <= init_range);
348
349 pr_params();
350
351 fprintf(stderr, "Initialization: populating %zu items...", init_size);
352 for (i = 0; i < init_size; i++) {
353 for (;;) {
354 uint32_t hash;
355 long *p;
356
357 r = xorshift64star(r);
358 p = &keys[r & (init_range - 1)];
359 hash = hfunc(*p);
360 if (qht_insert(&ht, p, hash, NULL)) {
361 break;
362 }
363 retries++;
364 }
365 }
366 fprintf(stderr, " populated after %zu retries\n", retries);
367 }
368
add_stats(struct thread_stats * s,struct thread_info * info,int n)369 static void add_stats(struct thread_stats *s, struct thread_info *info, int n)
370 {
371 int i;
372
373 for (i = 0; i < n; i++) {
374 struct thread_stats *stats = &info[i].stats;
375
376 s->rd += stats->rd;
377 s->not_rd += stats->not_rd;
378
379 s->in += stats->in;
380 s->not_in += stats->not_in;
381
382 s->rm += stats->rm;
383 s->not_rm += stats->not_rm;
384
385 s->rz += stats->rz;
386 s->not_rz += stats->not_rz;
387 }
388 }
389
pr_stats(void)390 static void pr_stats(void)
391 {
392 struct thread_stats s = {};
393 double tx;
394
395 add_stats(&s, rw_info, n_rw_threads);
396 add_stats(&s, rz_info, n_rz_threads);
397
398 printf("Results:\n");
399
400 if (resize_rate) {
401 printf(" Resizes: %zu (%.2f%% of %zu)\n",
402 s.rz, (double)s.rz / (s.rz + s.not_rz) * 100, s.rz + s.not_rz);
403 }
404
405 printf(" Read: %.2f M (%.2f%% of %.2fM)\n",
406 (double)s.rd / 1e6,
407 (double)s.rd / (s.rd + s.not_rd) * 100,
408 (double)(s.rd + s.not_rd) / 1e6);
409 printf(" Inserted: %.2f M (%.2f%% of %.2fM)\n",
410 (double)s.in / 1e6,
411 (double)s.in / (s.in + s.not_in) * 100,
412 (double)(s.in + s.not_in) / 1e6);
413 printf(" Removed: %.2f M (%.2f%% of %.2fM)\n",
414 (double)s.rm / 1e6,
415 (double)s.rm / (s.rm + s.not_rm) * 100,
416 (double)(s.rm + s.not_rm) / 1e6);
417
418 tx = (s.rd + s.not_rd + s.in + s.not_in + s.rm + s.not_rm) / 1e6 / duration;
419 printf(" Throughput: %.2f MT/s\n", tx);
420 printf(" Throughput/thread: %.2f MT/s/thread\n", tx / n_rw_threads);
421 }
422
run_test(void)423 static void run_test(void)
424 {
425 int i;
426
427 while (qatomic_read(&n_ready_threads) != n_rw_threads + n_rz_threads) {
428 cpu_relax();
429 }
430
431 qatomic_set(&test_start, true);
432 g_usleep(duration * G_USEC_PER_SEC);
433 qatomic_set(&test_stop, true);
434
435 for (i = 0; i < n_rw_threads; i++) {
436 qemu_thread_join(&rw_threads[i]);
437 }
438 for (i = 0; i < n_rz_threads; i++) {
439 qemu_thread_join(&rz_threads[i]);
440 }
441 }
442
parse_args(int argc,char * argv[])443 static void parse_args(int argc, char *argv[])
444 {
445 int c;
446
447 for (;;) {
448 c = getopt(argc, argv, "d:D:g:k:K:l:hn:N:o:pr:Rs:S:u:");
449 if (c < 0) {
450 break;
451 }
452 switch (c) {
453 case 'd':
454 duration = atoi(optarg);
455 break;
456 case 'D':
457 resize_delay = atol(optarg);
458 break;
459 case 'g':
460 init_range = pow2ceil(atol(optarg));
461 lookup_range = pow2ceil(atol(optarg));
462 update_range = pow2ceil(atol(optarg));
463 qht_n_elems = atol(optarg);
464 init_size = atol(optarg);
465 break;
466 case 'h':
467 usage_complete(argc, argv);
468 exit(0);
469 case 'k':
470 init_size = atol(optarg);
471 break;
472 case 'K':
473 init_range = pow2ceil(atol(optarg));
474 break;
475 case 'l':
476 lookup_range = pow2ceil(atol(optarg));
477 break;
478 case 'n':
479 n_rw_threads = atoi(optarg);
480 break;
481 case 'N':
482 n_rz_threads = atoi(optarg);
483 break;
484 case 'o':
485 populate_offset = atol(optarg);
486 break;
487 case 'p':
488 precompute_hash = true;
489 hfunc = hval;
490 break;
491 case 'r':
492 update_range = pow2ceil(atol(optarg));
493 break;
494 case 'R':
495 qht_mode |= QHT_MODE_AUTO_RESIZE;
496 break;
497 case 's':
498 qht_n_elems = atol(optarg);
499 break;
500 case 'S':
501 resize_rate = atof(optarg) / 100.0;
502 if (resize_rate > 1.0) {
503 resize_rate = 1.0;
504 }
505 break;
506 case 'u':
507 update_rate = atof(optarg) / 100.0;
508 if (update_rate > 1.0) {
509 update_rate = 1.0;
510 }
511 break;
512 }
513 }
514 }
515
main(int argc,char * argv[])516 int main(int argc, char *argv[])
517 {
518 parse_args(argc, argv);
519 htable_init();
520 create_threads();
521 run_test();
522 pr_stats();
523 return 0;
524 }
525