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