56bd41f977dd868ca9b4f6270f05b0c10a673095
[urcu.git] / tests / test_urcu_hash.c
1 /*
2 * test_ht.c
3 *
4 * Userspace RCU library - test program
5 *
6 * Copyright February 2009 - Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program; if not, write to the Free Software Foundation, Inc.,
20 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 */
22
23 #define _GNU_SOURCE
24 #include <stdio.h>
25 #include <pthread.h>
26 #include <stdlib.h>
27 #include <string.h>
28 #include <sys/types.h>
29 #include <sys/wait.h>
30 #include <unistd.h>
31 #include <stdio.h>
32 #include <assert.h>
33 #include <sched.h>
34 #include <errno.h>
35
36 #ifdef __linux__
37 #include <syscall.h>
38 #endif
39
40 #define HASH_SIZE 32
41 #define RAND_POOL 1000000
42
43 /* Make this big enough to include the POWER5+ L3 cacheline size of 256B */
44 #define CACHE_LINE_SIZE 4096
45
46 /* hardcoded number of CPUs */
47 #define NR_CPUS 16384
48
49 #if defined(_syscall0)
50 _syscall0(pid_t, gettid)
51 #elif defined(__NR_gettid)
52 static inline pid_t gettid(void)
53 {
54 return syscall(__NR_gettid);
55 }
56 #else
57 #warning "use pid as tid"
58 static inline pid_t gettid(void)
59 {
60 return getpid();
61 }
62 #endif
63
64 #ifndef DYNAMIC_LINK_TEST
65 #define _LGPL_SOURCE
66 #else
67 #define debug_yield_read()
68 #endif
69 #include <urcu.h>
70 #include <urcu/rculfhash.h>
71 #include <urcu-call-rcu.h>
72
73 struct wr_count {
74 unsigned long update_ops;
75 unsigned long add;
76 unsigned long remove;
77 };
78
79 static unsigned int __thread rand_lookup;
80 static unsigned long __thread nr_add;
81 static unsigned long __thread nr_addexist;
82 static unsigned long __thread nr_del;
83 static unsigned long __thread nr_delnoent;
84 static unsigned long __thread lookup_fail;
85 static unsigned long __thread lookup_ok;
86
87 static struct rcu_ht *test_ht;
88
89 struct test_data {
90 int a;
91 int b;
92 };
93
94 static volatile int test_go, test_stop;
95
96 static unsigned long wdelay;
97
98 static unsigned long duration;
99
100 /* read-side C.S. duration, in loops */
101 static unsigned long rduration;
102
103 static inline void loop_sleep(unsigned long l)
104 {
105 while(l-- != 0)
106 caa_cpu_relax();
107 }
108
109 static int verbose_mode;
110
111 #define printf_verbose(fmt, args...) \
112 do { \
113 if (verbose_mode) \
114 printf(fmt, args); \
115 } while (0)
116
117 static unsigned int cpu_affinities[NR_CPUS];
118 static unsigned int next_aff = 0;
119 static int use_affinity = 0;
120
121 pthread_mutex_t affinity_mutex = PTHREAD_MUTEX_INITIALIZER;
122
123 static void set_affinity(void)
124 {
125 cpu_set_t mask;
126 int cpu;
127 int ret;
128
129 if (!use_affinity)
130 return;
131
132 ret = pthread_mutex_lock(&affinity_mutex);
133 if (ret) {
134 perror("Error in pthread mutex lock");
135 exit(-1);
136 }
137 cpu = cpu_affinities[next_aff++];
138 ret = pthread_mutex_unlock(&affinity_mutex);
139 if (ret) {
140 perror("Error in pthread mutex unlock");
141 exit(-1);
142 }
143 CPU_ZERO(&mask);
144 CPU_SET(cpu, &mask);
145 sched_setaffinity(0, sizeof(mask), &mask);
146 }
147
148 /*
149 * returns 0 if test should end.
150 */
151 static int test_duration_write(void)
152 {
153 return !test_stop;
154 }
155
156 static int test_duration_read(void)
157 {
158 return !test_stop;
159 }
160
161 static unsigned long long __thread nr_writes;
162 static unsigned long long __thread nr_reads;
163
164 static unsigned int nr_readers;
165 static unsigned int nr_writers;
166
167 pthread_mutex_t rcu_copy_mutex = PTHREAD_MUTEX_INITIALIZER;
168
169 void rcu_copy_mutex_lock(void)
170 {
171 int ret;
172 ret = pthread_mutex_lock(&rcu_copy_mutex);
173 if (ret) {
174 perror("Error in pthread mutex lock");
175 exit(-1);
176 }
177 }
178
179 void rcu_copy_mutex_unlock(void)
180 {
181 int ret;
182
183 ret = pthread_mutex_unlock(&rcu_copy_mutex);
184 if (ret) {
185 perror("Error in pthread mutex unlock");
186 exit(-1);
187 }
188 }
189
190 /*
191 * Hash function
192 * Source: http://burtleburtle.net/bob/c/lookup3.c
193 * Originally Public Domain
194 */
195
196 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
197
198 #define mix(a, b, c) \
199 do { \
200 a -= c; a ^= rot(c, 4); c += b; \
201 b -= a; b ^= rot(a, 6); a += c; \
202 c -= b; c ^= rot(b, 8); b += a; \
203 a -= c; a ^= rot(c, 16); c += b; \
204 b -= a; b ^= rot(a, 19); a += c; \
205 c -= b; c ^= rot(b, 4); b += a; \
206 } while (0)
207
208 #define final(a, b, c) \
209 { \
210 c ^= b; c -= rot(b, 14); \
211 a ^= c; a -= rot(c, 11); \
212 b ^= a; b -= rot(a, 25); \
213 c ^= b; c -= rot(b, 16); \
214 a ^= c; a -= rot(c, 4);\
215 b ^= a; b -= rot(a, 14); \
216 c ^= b; c -= rot(b, 24); \
217 }
218
219 static __attribute__((unused))
220 uint32_t hash_u32(
221 const uint32_t *k, /* the key, an array of uint32_t values */
222 size_t length, /* the length of the key, in uint32_ts */
223 uint32_t initval) /* the previous hash, or an arbitrary value */
224 {
225 uint32_t a, b, c;
226
227 /* Set up the internal state */
228 a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval;
229
230 /*----------------------------------------- handle most of the key */
231 while (length > 3) {
232 a += k[0];
233 b += k[1];
234 c += k[2];
235 mix(a, b, c);
236 length -= 3;
237 k += 3;
238 }
239
240 /*----------------------------------- handle the last 3 uint32_t's */
241 switch (length) { /* all the case statements fall through */
242 case 3: c += k[2];
243 case 2: b += k[1];
244 case 1: a += k[0];
245 final(a, b, c);
246 case 0: /* case 0: nothing left to add */
247 break;
248 }
249 /*---------------------------------------------- report the result */
250 return c;
251 }
252
253 static
254 void hashword2(
255 const uint32_t *k, /* the key, an array of uint32_t values */
256 size_t length, /* the length of the key, in uint32_ts */
257 uint32_t *pc, /* IN: seed OUT: primary hash value */
258 uint32_t *pb) /* IN: more seed OUT: secondary hash value */
259 {
260 uint32_t a, b, c;
261
262 /* Set up the internal state */
263 a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc;
264 c += *pb;
265
266 /*----------------------------------------- handle most of the key */
267 while (length > 3) {
268 a += k[0];
269 b += k[1];
270 c += k[2];
271 mix(a, b, c);
272 length -= 3;
273 k += 3;
274 }
275
276 /*----------------------------------- handle the last 3 uint32_t's */
277 switch (length) { /* all the case statements fall through */
278 case 3: c += k[2];
279 case 2: b += k[1];
280 case 1: a += k[0];
281 final(a, b, c);
282 case 0: /* case 0: nothing left to add */
283 break;
284 }
285 /*---------------------------------------------- report the result */
286 *pc = c;
287 *pb = b;
288 }
289
290 #if (CAA_BITS_PER_LONG == 32)
291 static
292 unsigned long test_hash(void *_key, size_t length, unsigned long seed)
293 {
294 unsigned long key = (unsigned long) _key;
295 unsigned long v;
296
297 assert(length == sizeof(unsigned long));
298 return hash_u32(&v, 1, seed);
299 }
300 #else
301 static
302 unsigned long test_hash(void *_key, size_t length, unsigned long seed)
303 {
304 union {
305 uint64_t v64;
306 uint32_t v32[2];
307 } v;
308 union {
309 uint64_t v64;
310 uint32_t v32[2];
311 } key;
312
313 assert(length == sizeof(unsigned long));
314 v.v64 = (uint64_t) seed;
315 key.v64 = (uint64_t) _key;
316 hashword2(key.v32, 2, &v.v32[0], &v.v32[1]);
317 return v.v64;
318 }
319 #endif
320
321 static
322 unsigned long test_compare(void *key1, size_t key1_len,
323 void *key2, size_t key2_len)
324 {
325 if (unlikely(key1_len != key2_len))
326 return -1;
327 assert(key1_len == sizeof(unsigned long));
328 if (key1 == key2)
329 return 0;
330 else
331 return 1;
332 }
333
334 void *thr_reader(void *_count)
335 {
336 unsigned long long *count = _count;
337 struct rcu_ht_node *node;
338
339 printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
340 "reader", pthread_self(), (unsigned long)gettid());
341
342 set_affinity();
343
344 rcu_register_thread();
345
346 while (!test_go)
347 {
348 }
349 cmm_smp_mb();
350
351 for (;;) {
352 rcu_read_lock();
353 node = ht_lookup(test_ht,
354 (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL),
355 sizeof(void *));
356 if (node == NULL)
357 lookup_fail++;
358 else
359 lookup_ok++;
360 debug_yield_read();
361 if (unlikely(rduration))
362 loop_sleep(rduration);
363 rcu_read_unlock();
364 nr_reads++;
365 if (unlikely(!test_duration_read()))
366 break;
367 }
368
369 rcu_unregister_thread();
370
371 *count = nr_reads;
372 printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
373 "reader", pthread_self(), (unsigned long)gettid());
374 printf_verbose("readid : %lx, lookupfail %lu, lookupok %lu\n",
375 pthread_self(), lookup_fail, lookup_ok);
376 return ((void*)1);
377
378 }
379
380 static
381 void free_node_cb(struct rcu_head *head)
382 {
383 struct rcu_ht_node *node =
384 caa_container_of(head, struct rcu_ht_node, head);
385 free(node);
386 }
387
388 void *thr_writer(void *_count)
389 {
390 struct rcu_ht_node *node, *ret_node;
391 struct wr_count *count = _count;
392 int ret;
393
394 printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
395 "writer", pthread_self(), (unsigned long)gettid());
396
397 set_affinity();
398
399 rcu_register_thread();
400
401 while (!test_go)
402 {
403 }
404 cmm_smp_mb();
405
406 for (;;) {
407 if (rand_r(&rand_lookup) & 1) {
408 node = malloc(sizeof(struct rcu_ht_node));
409 rcu_read_lock();
410 ht_node_init(node,
411 (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL),
412 sizeof(void *));
413 ret_node = ht_add_unique(test_ht, node);
414 rcu_read_unlock();
415 if (ret_node != node) {
416 free(node);
417 nr_addexist++;
418 } else
419 nr_add++;
420 } else {
421 /* May delete */
422 rcu_read_lock();
423 node = ht_lookup(test_ht,
424 (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL),
425 sizeof(void *));
426 if (node)
427 ret = ht_remove(test_ht, node);
428 else
429 ret = -ENOENT;
430 rcu_read_unlock();
431 if (ret == 0) {
432 call_rcu(&node->head, free_node_cb);
433 nr_del++;
434 } else
435 nr_delnoent++;
436 }
437 #if 0
438 //if (nr_writes % 100000 == 0) {
439 if (nr_writes % 1000 == 0) {
440 rcu_read_lock();
441 if (rand_r(&rand_lookup) & 1) {
442 ht_resize(test_ht, 1);
443 } else {
444 ht_resize(test_ht, -1);
445 }
446 rcu_read_unlock();
447 }
448 #endif //0
449 nr_writes++;
450 if (unlikely(!test_duration_write()))
451 break;
452 if (unlikely(wdelay))
453 loop_sleep(wdelay);
454 }
455
456 rcu_unregister_thread();
457
458 printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
459 "writer", pthread_self(), (unsigned long)gettid());
460 printf_verbose("info id %lx: nr_add %lu, nr_addexist %lu, nr_del %lu, "
461 "nr_delnoent %lu\n", pthread_self(), nr_add,
462 nr_addexist, nr_del, nr_delnoent);
463 count->update_ops = nr_writes;
464 count->add = nr_add;
465 count->remove = nr_del;
466 return ((void*)2);
467 }
468
469 void show_usage(int argc, char **argv)
470 {
471 printf("Usage : %s nr_readers nr_writers duration (s)", argv[0]);
472 #ifdef DEBUG_YIELD
473 printf(" [-r] [-w] (yield reader and/or writer)");
474 #endif
475 printf(" [-d delay] (writer period (us))");
476 printf(" [-c duration] (reader C.S. duration (in loops))");
477 printf(" [-v] (verbose output)");
478 printf(" [-a cpu#] [-a cpu#]... (affinity)");
479 printf("\n");
480 }
481
482 int main(int argc, char **argv)
483 {
484 int err;
485 pthread_t *tid_reader, *tid_writer;
486 void *tret;
487 unsigned long long *count_reader;
488 struct wr_count *count_writer;
489 unsigned long long tot_reads = 0, tot_writes = 0,
490 tot_add = 0, tot_remove = 0;
491 unsigned long count, removed;
492 int i, a, ret;
493
494 if (argc < 4) {
495 show_usage(argc, argv);
496 return -1;
497 }
498
499 err = sscanf(argv[1], "%u", &nr_readers);
500 if (err != 1) {
501 show_usage(argc, argv);
502 return -1;
503 }
504
505 err = sscanf(argv[2], "%u", &nr_writers);
506 if (err != 1) {
507 show_usage(argc, argv);
508 return -1;
509 }
510
511 err = sscanf(argv[3], "%lu", &duration);
512 if (err != 1) {
513 show_usage(argc, argv);
514 return -1;
515 }
516
517 for (i = 4; i < argc; i++) {
518 if (argv[i][0] != '-')
519 continue;
520 switch (argv[i][1]) {
521 #ifdef DEBUG_YIELD
522 case 'r':
523 yield_active |= YIELD_READ;
524 break;
525 case 'w':
526 yield_active |= YIELD_WRITE;
527 break;
528 #endif
529 case 'a':
530 if (argc < i + 2) {
531 show_usage(argc, argv);
532 return -1;
533 }
534 a = atoi(argv[++i]);
535 cpu_affinities[next_aff++] = a;
536 use_affinity = 1;
537 printf_verbose("Adding CPU %d affinity\n", a);
538 break;
539 case 'c':
540 if (argc < i + 2) {
541 show_usage(argc, argv);
542 return -1;
543 }
544 rduration = atol(argv[++i]);
545 break;
546 case 'd':
547 if (argc < i + 2) {
548 show_usage(argc, argv);
549 return -1;
550 }
551 wdelay = atol(argv[++i]);
552 break;
553 case 'v':
554 verbose_mode = 1;
555 break;
556 }
557 }
558
559 printf_verbose("running test for %lu seconds, %u readers, %u writers.\n",
560 duration, nr_readers, nr_writers);
561 printf_verbose("Writer delay : %lu loops.\n", wdelay);
562 printf_verbose("Reader duration : %lu loops.\n", rduration);
563 printf_verbose("thread %-6s, thread id : %lx, tid %lu\n",
564 "main", pthread_self(), (unsigned long)gettid());
565
566 tid_reader = malloc(sizeof(*tid_reader) * nr_readers);
567 tid_writer = malloc(sizeof(*tid_writer) * nr_writers);
568 count_reader = malloc(sizeof(*count_reader) * nr_readers);
569 count_writer = malloc(sizeof(*count_writer) * nr_writers);
570 test_ht = ht_new(test_hash, test_compare, 0x42UL,
571 HASH_SIZE, call_rcu);
572
573 err = create_all_cpu_call_rcu_data(0);
574 assert(!err);
575
576 next_aff = 0;
577
578 for (i = 0; i < nr_readers; i++) {
579 err = pthread_create(&tid_reader[i], NULL, thr_reader,
580 &count_reader[i]);
581 if (err != 0)
582 exit(1);
583 }
584 for (i = 0; i < nr_writers; i++) {
585 err = pthread_create(&tid_writer[i], NULL, thr_writer,
586 &count_writer[i]);
587 if (err != 0)
588 exit(1);
589 }
590
591 cmm_smp_mb();
592
593 test_go = 1;
594
595 sleep(duration);
596
597 test_stop = 1;
598
599 for (i = 0; i < nr_readers; i++) {
600 err = pthread_join(tid_reader[i], &tret);
601 if (err != 0)
602 exit(1);
603 tot_reads += count_reader[i];
604 }
605 for (i = 0; i < nr_writers; i++) {
606 err = pthread_join(tid_writer[i], &tret);
607 if (err != 0)
608 exit(1);
609 tot_writes += count_writer[i].update_ops;
610 tot_add += count_writer[i].add;
611 tot_remove += count_writer[i].remove;
612 }
613 ht_count_nodes(test_ht, &count, &removed);
614 if (count || removed)
615 printf("WARNING: nodes left in the hash table upon destroy: "
616 "%lu nodes + %lu logically removed.\n", count, removed);
617 (void) ht_destroy(test_ht);
618
619 printf_verbose("final delete: %d items\n", ret);
620 printf_verbose("total number of reads : %llu, writes %llu\n", tot_reads,
621 tot_writes);
622 printf("SUMMARY %-25s testdur %4lu nr_readers %3u rdur %6lu "
623 "nr_writers %3u "
624 "wdelay %6lu nr_reads %12llu nr_writes %12llu nr_ops %12llu "
625 "nr_add %12llu nr_remove %12llu nr_leaked %12llu\n",
626 argv[0], duration, nr_readers, rduration,
627 nr_writers, wdelay, tot_reads, tot_writes,
628 tot_reads + tot_writes, tot_add, tot_remove,
629 tot_add - tot_remove - count);
630 free(tid_reader);
631 free(tid_writer);
632 free(count_reader);
633 free(count_writer);
634 return 0;
635 }
This page took 0.06207 seconds and 3 git commands to generate.