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