Fix: relayd: erroneous rundir permission logging message
[lttng-tools.git] / src / common / hashtable / hashtable.cpp
CommitLineData
bec39940 1/*
ab5be9fa 2 * Copyright (C) 2011 David Goulet <david.goulet@polymtl.ca>
bec39940 3 *
ab5be9fa 4 * SPDX-License-Identifier: GPL-2.0-only
bec39940 5 *
bec39940
DG
6 */
7
6c1c0768 8#define _LGPL_SOURCE
bec39940
DG
9#include <string.h>
10#include <urcu.h>
11#include <urcu/compiler.h>
12
990570ed
DG
13#include <common/common.h>
14#include <common/defaults.h>
bec39940 15
10a8a223 16#include "hashtable.h"
bec39940
DG
17#include "utils.h"
18
6dcd74cf
JG
19/* seed_lock protects both seed_init and lttng_ht_seed. */
20static pthread_mutex_t seed_lock = PTHREAD_MUTEX_INITIALIZER;
21static bool seed_init;
b6314938 22unsigned long lttng_ht_seed;
bec39940
DG
23
24static unsigned long min_hash_alloc_size = 1;
13fe1164 25static unsigned long max_hash_buckets_size = 0;
bec39940 26
42ce408e
MD
27/*
28 * Getter/lookup functions need to be called with RCU read-side lock
29 * held. However, modification functions (add, add_unique, replace, del)
30 * take the RCU lock internally, so it does not matter whether the
31 * caller hold the RCU lock or not.
32 */
33
bec39940
DG
34/*
35 * Match function for string node.
36 */
37static int match_str(struct cds_lfht_node *node, const void *key)
38{
39 struct lttng_ht_node_str *match_node =
40 caa_container_of(node, struct lttng_ht_node_str, node);
41
42 return hash_match_key_str(match_node->key, (void *) key);
43}
44
45/*
46 * Match function for ulong node.
47 */
48static int match_ulong(struct cds_lfht_node *node, const void *key)
49{
50 struct lttng_ht_node_ulong *match_node =
51 caa_container_of(node, struct lttng_ht_node_ulong, node);
52
53 return hash_match_key_ulong((void *) match_node->key, (void *) key);
54}
55
d88aee68
DG
56/*
57 * Match function for u64 node.
58 */
59static int match_u64(struct cds_lfht_node *node, const void *key)
60{
61 struct lttng_ht_node_u64 *match_node =
62 caa_container_of(node, struct lttng_ht_node_u64, node);
63
64 return hash_match_key_u64(&match_node->key, (void *) key);
65}
66
3c4599b9
JD
67/*
68 * Match function for two uint64_t node.
69 */
70static int match_two_u64(struct cds_lfht_node *node, const void *key)
71{
72 struct lttng_ht_node_two_u64 *match_node =
73 caa_container_of(node, struct lttng_ht_node_two_u64, node);
74
75 return hash_match_key_two_u64((void *) &match_node->key, (void *) key);
76}
77
e2530e2b
FD
78static inline
79const char *lttng_ht_type_str(enum lttng_ht_type type)
80{
81 switch (type) {
82 case LTTNG_HT_TYPE_STRING:
83 return "STRING";
84 case LTTNG_HT_TYPE_ULONG:
85 return "ULONG";
86 case LTTNG_HT_TYPE_U64:
87 return "U64";
88 case LTTNG_HT_TYPE_TWO_U64:
89 return "TWO_U64";
90 default:
91 ERR("Unknown lttng hashtable type %d", type);
92 abort();
93 }
94}
95
bec39940
DG
96/*
97 * Return an allocated lttng hashtable.
98 */
6dca8ba7 99struct lttng_ht *lttng_ht_new(unsigned long size, lttng_ht_type type)
bec39940
DG
100{
101 struct lttng_ht *ht;
102
103 /* Test size */
dc78d159
MD
104 if (!size)
105 size = DEFAULT_HT_SIZE;
bec39940 106
6dcd74cf
JG
107 pthread_mutex_lock(&seed_lock);
108 if (!seed_init) {
109 lttng_ht_seed = (unsigned long) time(NULL);
110 seed_init = true;
111 }
112 pthread_mutex_unlock(&seed_lock);
113
6dca8ba7 114 ht = (lttng_ht *) zmalloc(sizeof(*ht));
bec39940
DG
115 if (ht == NULL) {
116 PERROR("zmalloc lttng_ht");
117 goto error;
118 }
119
120 ht->ht = cds_lfht_new(size, min_hash_alloc_size, max_hash_buckets_size,
13fe1164 121 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, NULL);
bec39940
DG
122 /*
123 * There is already an assert in the RCU hashtable code so if the ht is
124 * NULL here there is a *huge* problem.
125 */
a0377dfe 126 LTTNG_ASSERT(ht->ht);
bec39940
DG
127
128 switch (type) {
129 case LTTNG_HT_TYPE_STRING:
130 ht->match_fct = match_str;
131 ht->hash_fct = hash_key_str;
132 break;
133 case LTTNG_HT_TYPE_ULONG:
134 ht->match_fct = match_ulong;
135 ht->hash_fct = hash_key_ulong;
136 break;
d88aee68
DG
137 case LTTNG_HT_TYPE_U64:
138 ht->match_fct = match_u64;
139 ht->hash_fct = hash_key_u64;
140 break;
3c4599b9
JD
141 case LTTNG_HT_TYPE_TWO_U64:
142 ht->match_fct = match_two_u64;
143 ht->hash_fct = hash_key_two_u64;
144 break;
bec39940
DG
145 default:
146 ERR("Unknown lttng hashtable type %d", type);
42305b36 147 lttng_ht_destroy(ht);
bec39940
DG
148 goto error;
149 }
150
e2530e2b
FD
151 DBG3("Created hashtable size %lu at %p of type %s", size, ht->ht,
152 lttng_ht_type_str(type));
bec39940
DG
153
154 return ht;
155
156error:
157 return NULL;
158}
159
160/*
161 * Free a lttng hashtable.
162 */
163void lttng_ht_destroy(struct lttng_ht *ht)
164{
165 int ret;
166
167 ret = cds_lfht_destroy(ht->ht, NULL);
a0377dfe 168 LTTNG_ASSERT(!ret);
cf5280ea 169 free(ht);
bec39940
DG
170}
171
172/*
173 * Init lttng ht node string.
174 */
175void lttng_ht_node_init_str(struct lttng_ht_node_str *node, char *key)
176{
a0377dfe 177 LTTNG_ASSERT(node);
bec39940
DG
178
179 node->key = key;
180 cds_lfht_node_init(&node->node);
181}
182
183/*
184 * Init lttng ht node unsigned long.
185 */
186void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node,
187 unsigned long key)
188{
a0377dfe 189 LTTNG_ASSERT(node);
bec39940
DG
190
191 node->key = key;
192 cds_lfht_node_init(&node->node);
193}
194
d88aee68
DG
195/*
196 * Init lttng ht node uint64_t.
197 */
198void lttng_ht_node_init_u64(struct lttng_ht_node_u64 *node,
199 uint64_t key)
200{
a0377dfe 201 LTTNG_ASSERT(node);
d88aee68
DG
202
203 node->key = key;
204 cds_lfht_node_init(&node->node);
205}
206
3c4599b9
JD
207/*
208 * Init lttng ht node with two uint64_t.
209 */
210void lttng_ht_node_init_two_u64(struct lttng_ht_node_two_u64 *node,
211 uint64_t key1, uint64_t key2)
212{
a0377dfe 213 LTTNG_ASSERT(node);
3c4599b9
JD
214
215 node->key.key1 = key1;
216 node->key.key2 = key2;
217 cds_lfht_node_init(&node->node);
218}
219
bec39940
DG
220/*
221 * Free lttng ht node string.
222 */
223void lttng_ht_node_free_str(struct lttng_ht_node_str *node)
224{
a0377dfe 225 LTTNG_ASSERT(node);
bec39940
DG
226 free(node);
227}
228
229/*
230 * Free lttng ht node unsigned long.
231 */
232void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node)
233{
a0377dfe 234 LTTNG_ASSERT(node);
bec39940
DG
235 free(node);
236}
237
d88aee68
DG
238/*
239 * Free lttng ht node uint64_t.
240 */
7972aab2 241void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node)
d88aee68 242{
a0377dfe 243 LTTNG_ASSERT(node);
d88aee68
DG
244 free(node);
245}
246
3c4599b9
JD
247/*
248 * Free lttng ht node two uint64_t.
249 */
250void lttng_ht_node_free_two_u64(struct lttng_ht_node_two_u64 *node)
251{
a0377dfe 252 LTTNG_ASSERT(node);
3c4599b9
JD
253 free(node);
254}
255
bec39940
DG
256/*
257 * Lookup function in hashtable.
258 */
fb9a95c4 259void lttng_ht_lookup(struct lttng_ht *ht, const void *key,
bec39940
DG
260 struct lttng_ht_iter *iter)
261{
a0377dfe
FD
262 LTTNG_ASSERT(ht);
263 LTTNG_ASSERT(ht->ht);
bec39940 264
b6314938 265 cds_lfht_lookup(ht->ht, ht->hash_fct(key, lttng_ht_seed),
bec39940
DG
266 ht->match_fct, key, &iter->iter);
267}
268
269/*
270 * Add unique string node to hashtable.
271 */
272void lttng_ht_add_unique_str(struct lttng_ht *ht,
273 struct lttng_ht_node_str *node)
274{
275 struct cds_lfht_node *node_ptr;
a0377dfe
FD
276 LTTNG_ASSERT(ht);
277 LTTNG_ASSERT(ht->ht);
278 LTTNG_ASSERT(node);
bec39940 279
42ce408e
MD
280 /* RCU read lock protects from ABA. */
281 rcu_read_lock();
b6314938 282 node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
bec39940 283 ht->match_fct, node->key, &node->node);
42ce408e 284 rcu_read_unlock();
a0377dfe 285 LTTNG_ASSERT(node_ptr == &node->node);
bec39940
DG
286}
287
efa116c6
JD
288/*
289 * Add string node to hashtable.
290 */
291void lttng_ht_add_str(struct lttng_ht *ht,
292 struct lttng_ht_node_str *node)
293{
a0377dfe
FD
294 LTTNG_ASSERT(ht);
295 LTTNG_ASSERT(ht->ht);
296 LTTNG_ASSERT(node);
efa116c6 297
42ce408e
MD
298 /* RCU read lock protects from ABA. */
299 rcu_read_lock();
efa116c6
JD
300 cds_lfht_add(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
301 &node->node);
42ce408e 302 rcu_read_unlock();
efa116c6
JD
303}
304
aefea3b7
DG
305/*
306 * Add unsigned long node to hashtable.
307 */
308void lttng_ht_add_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node)
309{
a0377dfe
FD
310 LTTNG_ASSERT(ht);
311 LTTNG_ASSERT(ht->ht);
312 LTTNG_ASSERT(node);
aefea3b7 313
42ce408e
MD
314 /* RCU read lock protects from ABA. */
315 rcu_read_lock();
b6314938 316 cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed),
aefea3b7 317 &node->node);
42ce408e 318 rcu_read_unlock();
aefea3b7
DG
319}
320
d88aee68
DG
321/*
322 * Add uint64_t node to hashtable.
d88aee68
DG
323 */
324void lttng_ht_add_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node)
325{
a0377dfe
FD
326 LTTNG_ASSERT(ht);
327 LTTNG_ASSERT(ht->ht);
328 LTTNG_ASSERT(node);
d88aee68 329
42ce408e
MD
330 /* RCU read lock protects from ABA. */
331 rcu_read_lock();
d88aee68
DG
332 cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed),
333 &node->node);
42ce408e 334 rcu_read_unlock();
d88aee68
DG
335}
336
bec39940
DG
337/*
338 * Add unique unsigned long node to hashtable.
339 */
340void lttng_ht_add_unique_ulong(struct lttng_ht *ht,
341 struct lttng_ht_node_ulong *node)
342{
343 struct cds_lfht_node *node_ptr;
a0377dfe
FD
344 LTTNG_ASSERT(ht);
345 LTTNG_ASSERT(ht->ht);
346 LTTNG_ASSERT(node);
bec39940 347
42ce408e
MD
348 /* RCU read lock protects from ABA. */
349 rcu_read_lock();
bec39940 350 node_ptr = cds_lfht_add_unique(ht->ht,
b6314938 351 ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
bec39940 352 (void *) node->key, &node->node);
42ce408e 353 rcu_read_unlock();
a0377dfe 354 LTTNG_ASSERT(node_ptr == &node->node);
bec39940
DG
355}
356
d88aee68
DG
357/*
358 * Add unique uint64_t node to hashtable.
359 */
360void lttng_ht_add_unique_u64(struct lttng_ht *ht,
361 struct lttng_ht_node_u64 *node)
362{
363 struct cds_lfht_node *node_ptr;
a0377dfe
FD
364 LTTNG_ASSERT(ht);
365 LTTNG_ASSERT(ht->ht);
366 LTTNG_ASSERT(node);
d88aee68 367
42ce408e
MD
368 /* RCU read lock protects from ABA. */
369 rcu_read_lock();
d88aee68
DG
370 node_ptr = cds_lfht_add_unique(ht->ht,
371 ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct,
372 &node->key, &node->node);
42ce408e 373 rcu_read_unlock();
a0377dfe 374 LTTNG_ASSERT(node_ptr == &node->node);
d88aee68
DG
375}
376
3c4599b9
JD
377/*
378 * Add unique two uint64_t node to hashtable.
379 */
380void lttng_ht_add_unique_two_u64(struct lttng_ht *ht,
381 struct lttng_ht_node_two_u64 *node)
382{
383 struct cds_lfht_node *node_ptr;
a0377dfe
FD
384 LTTNG_ASSERT(ht);
385 LTTNG_ASSERT(ht->ht);
386 LTTNG_ASSERT(node);
3c4599b9 387
42ce408e
MD
388 /* RCU read lock protects from ABA. */
389 rcu_read_lock();
3c4599b9
JD
390 node_ptr = cds_lfht_add_unique(ht->ht,
391 ht->hash_fct((void *) &node->key, lttng_ht_seed), ht->match_fct,
392 (void *) &node->key, &node->node);
42ce408e 393 rcu_read_unlock();
a0377dfe 394 LTTNG_ASSERT(node_ptr == &node->node);
3c4599b9
JD
395}
396
702b1ea4
MD
397/*
398 * Add replace unsigned long node to hashtable.
399 */
400struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(struct lttng_ht *ht,
401 struct lttng_ht_node_ulong *node)
402{
403 struct cds_lfht_node *node_ptr;
a0377dfe
FD
404 LTTNG_ASSERT(ht);
405 LTTNG_ASSERT(ht->ht);
406 LTTNG_ASSERT(node);
702b1ea4 407
42ce408e
MD
408 /* RCU read lock protects from ABA. */
409 rcu_read_lock();
702b1ea4 410 node_ptr = cds_lfht_add_replace(ht->ht,
b6314938 411 ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
702b1ea4 412 (void *) node->key, &node->node);
42ce408e 413 rcu_read_unlock();
702b1ea4
MD
414 if (!node_ptr) {
415 return NULL;
416 } else {
417 return caa_container_of(node_ptr, struct lttng_ht_node_ulong, node);
418 }
a0377dfe 419 LTTNG_ASSERT(node_ptr == &node->node);
702b1ea4
MD
420}
421
d88aee68
DG
422/*
423 * Add replace unsigned long node to hashtable.
424 */
425struct lttng_ht_node_u64 *lttng_ht_add_replace_u64(struct lttng_ht *ht,
426 struct lttng_ht_node_u64 *node)
427{
428 struct cds_lfht_node *node_ptr;
a0377dfe
FD
429 LTTNG_ASSERT(ht);
430 LTTNG_ASSERT(ht->ht);
431 LTTNG_ASSERT(node);
d88aee68 432
42ce408e
MD
433 /* RCU read lock protects from ABA. */
434 rcu_read_lock();
d88aee68
DG
435 node_ptr = cds_lfht_add_replace(ht->ht,
436 ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct,
437 &node->key, &node->node);
42ce408e 438 rcu_read_unlock();
d88aee68
DG
439 if (!node_ptr) {
440 return NULL;
441 } else {
442 return caa_container_of(node_ptr, struct lttng_ht_node_u64, node);
443 }
a0377dfe 444 LTTNG_ASSERT(node_ptr == &node->node);
d88aee68
DG
445}
446
bec39940
DG
447/*
448 * Delete node from hashtable.
449 */
450int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
451{
42ce408e
MD
452 int ret;
453
a0377dfe
FD
454 LTTNG_ASSERT(ht);
455 LTTNG_ASSERT(ht->ht);
456 LTTNG_ASSERT(iter);
bec39940 457
42ce408e
MD
458 /* RCU read lock protects from ABA. */
459 rcu_read_lock();
460 ret = cds_lfht_del(ht->ht, iter->iter.node);
461 rcu_read_unlock();
462 return ret;
bec39940
DG
463}
464
465/*
466 * Get first node in the hashtable.
467 */
468void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter)
469{
a0377dfe
FD
470 LTTNG_ASSERT(ht);
471 LTTNG_ASSERT(ht->ht);
472 LTTNG_ASSERT(iter);
bec39940
DG
473
474 cds_lfht_first(ht->ht, &iter->iter);
475}
476
477/*
478 * Get next node in the hashtable.
479 */
480void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter)
481{
a0377dfe
FD
482 LTTNG_ASSERT(ht);
483 LTTNG_ASSERT(ht->ht);
484 LTTNG_ASSERT(iter);
bec39940
DG
485
486 cds_lfht_next(ht->ht, &iter->iter);
487}
488
489/*
490 * Return the number of nodes in the hashtable.
491 */
492unsigned long lttng_ht_get_count(struct lttng_ht *ht)
493{
494 long scb, sca;
495 unsigned long count;
496
a0377dfe
FD
497 LTTNG_ASSERT(ht);
498 LTTNG_ASSERT(ht->ht);
bec39940 499
42ce408e
MD
500 /* RCU read lock protects from ABA and allows RCU traversal. */
501 rcu_read_lock();
bec39940 502 cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
42ce408e 503 rcu_read_unlock();
bec39940
DG
504
505 return count;
506}
507
508/*
509 * Return lttng ht string node from iterator.
510 */
511struct lttng_ht_node_str *lttng_ht_iter_get_node_str(
512 struct lttng_ht_iter *iter)
513{
514 struct cds_lfht_node *node;
515
a0377dfe 516 LTTNG_ASSERT(iter);
bec39940
DG
517 node = cds_lfht_iter_get_node(&iter->iter);
518 if (!node) {
519 return NULL;
520 }
521 return caa_container_of(node, struct lttng_ht_node_str, node);
522}
523
524/*
525 * Return lttng ht unsigned long node from iterator.
526 */
527struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong(
528 struct lttng_ht_iter *iter)
529{
530 struct cds_lfht_node *node;
531
a0377dfe 532 LTTNG_ASSERT(iter);
bec39940
DG
533 node = cds_lfht_iter_get_node(&iter->iter);
534 if (!node) {
535 return NULL;
536 }
537 return caa_container_of(node, struct lttng_ht_node_ulong, node);
538}
b6314938 539
d88aee68
DG
540/*
541 * Return lttng ht unsigned long node from iterator.
542 */
543struct lttng_ht_node_u64 *lttng_ht_iter_get_node_u64(
544 struct lttng_ht_iter *iter)
545{
546 struct cds_lfht_node *node;
547
a0377dfe 548 LTTNG_ASSERT(iter);
d88aee68
DG
549 node = cds_lfht_iter_get_node(&iter->iter);
550 if (!node) {
551 return NULL;
552 }
553 return caa_container_of(node, struct lttng_ht_node_u64, node);
554}
555
3c4599b9
JD
556/*
557 * Return lttng ht stream and index id node from iterator.
558 */
559struct lttng_ht_node_two_u64 *lttng_ht_iter_get_node_two_u64(
560 struct lttng_ht_iter *iter)
561{
562 struct cds_lfht_node *node;
563
a0377dfe 564 LTTNG_ASSERT(iter);
3c4599b9
JD
565 node = cds_lfht_iter_get_node(&iter->iter);
566 if (!node) {
567 return NULL;
568 }
569 return caa_container_of(node, struct lttng_ht_node_two_u64, node);
570}
This page took 0.103261 seconds and 4 git commands to generate.