Tests: Fix: Use '.logfile' instead of '.log' for test app output
[lttng-tools.git] / src / common / hashtable / hashtable.cpp
CommitLineData
bec39940 1/*
21cf9b6b 2 * Copyright (C) 2011 EfficiOS Inc.
bec39940 3 *
ab5be9fa 4 * SPDX-License-Identifier: GPL-2.0-only
bec39940 5 *
bec39940
DG
6 */
7
6c1c0768 8#define _LGPL_SOURCE
28ab034a
JG
9#include "hashtable.hpp"
10#include "utils.hpp"
bec39940 11
c9e313bc
SM
12#include <common/common.hpp>
13#include <common/defaults.hpp>
56047f5a 14#include <common/urcu.hpp>
bec39940 15
28ab034a
JG
16#include <string.h>
17#include <urcu.h>
18#include <urcu/compiler.h>
bec39940 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;
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{
ef2f8a02
JG
39 auto *match_node = reinterpret_cast<lttng_ht_node_str *>(
40 lttng::utils::container_of(node, &lttng_ht_node_str::node));
bec39940
DG
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{
ef2f8a02
JG
50 auto *match_node = reinterpret_cast<lttng_ht_node_ulong *>(
51 lttng::utils::container_of(node, &lttng_ht_node_ulong::node));
bec39940
DG
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{
ef2f8a02
JG
61 auto *match_node = reinterpret_cast<lttng_ht_node_u64 *>(
62 lttng::utils::container_of(node, &lttng_ht_node_u64::node));
d88aee68
DG
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{
ef2f8a02
JG
72 auto *match_node = reinterpret_cast<lttng_ht_node_two_u64 *>(
73 lttng::utils::container_of(node, &lttng_ht_node_two_u64::node));
3c4599b9
JD
74
75 return hash_match_key_two_u64((void *) &match_node->key, (void *) key);
76}
77
28ab034a 78static inline const char *lttng_ht_type_str(enum lttng_ht_type type)
e2530e2b
FD
79{
80 switch (type) {
81 case LTTNG_HT_TYPE_STRING:
82 return "STRING";
83 case LTTNG_HT_TYPE_ULONG:
84 return "ULONG";
85 case LTTNG_HT_TYPE_U64:
86 return "U64";
87 case LTTNG_HT_TYPE_TWO_U64:
88 return "TWO_U64";
89 default:
90 ERR("Unknown lttng hashtable type %d", type);
91 abort();
92 }
93}
94
bec39940
DG
95/*
96 * Return an allocated lttng hashtable.
97 */
6dca8ba7 98struct lttng_ht *lttng_ht_new(unsigned long size, lttng_ht_type type)
bec39940
DG
99{
100 struct lttng_ht *ht;
101
102 /* Test size */
dc78d159
MD
103 if (!size)
104 size = DEFAULT_HT_SIZE;
bec39940 105
6dcd74cf
JG
106 pthread_mutex_lock(&seed_lock);
107 if (!seed_init) {
cd9adb8b 108 lttng_ht_seed = (unsigned long) time(nullptr);
6dcd74cf
JG
109 seed_init = true;
110 }
111 pthread_mutex_unlock(&seed_lock);
112
64803277 113 ht = zmalloc<lttng_ht>();
cd9adb8b 114 if (ht == nullptr) {
bec39940
DG
115 PERROR("zmalloc lttng_ht");
116 goto error;
117 }
118
28ab034a
JG
119 ht->ht = cds_lfht_new(size,
120 min_hash_alloc_size,
121 max_hash_buckets_size,
122 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING,
cd9adb8b 123 nullptr);
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 */
a0377dfe 128 LTTNG_ASSERT(ht->ht);
bec39940
DG
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
28ab034a 153 DBG3("Created hashtable size %lu at %p of type %s", size, ht->ht, lttng_ht_type_str(type));
bec39940
DG
154
155 return ht;
156
157error:
cd9adb8b 158 return nullptr;
bec39940
DG
159}
160
161/*
162 * Free a lttng hashtable.
163 */
164void lttng_ht_destroy(struct lttng_ht *ht)
165{
166 int ret;
167
cd9adb8b 168 ret = cds_lfht_destroy(ht->ht, nullptr);
a0377dfe 169 LTTNG_ASSERT(!ret);
cf5280ea 170 free(ht);
bec39940
DG
171}
172
173/*
174 * Init lttng ht node string.
175 */
176void lttng_ht_node_init_str(struct lttng_ht_node_str *node, char *key)
177{
a0377dfe 178 LTTNG_ASSERT(node);
bec39940
DG
179
180 node->key = key;
181 cds_lfht_node_init(&node->node);
182}
183
184/*
185 * Init lttng ht node unsigned long.
186 */
28ab034a 187void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node, unsigned long key)
bec39940 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 */
28ab034a 198void lttng_ht_node_init_u64(struct lttng_ht_node_u64 *node, uint64_t key)
d88aee68 199{
a0377dfe 200 LTTNG_ASSERT(node);
d88aee68
DG
201
202 node->key = key;
203 cds_lfht_node_init(&node->node);
204}
205
3c4599b9
JD
206/*
207 * Init lttng ht node with two uint64_t.
208 */
28ab034a 209void lttng_ht_node_init_two_u64(struct lttng_ht_node_two_u64 *node, uint64_t key1, uint64_t key2)
3c4599b9 210{
a0377dfe 211 LTTNG_ASSERT(node);
3c4599b9
JD
212
213 node->key.key1 = key1;
214 node->key.key2 = key2;
215 cds_lfht_node_init(&node->node);
216}
217
bec39940
DG
218/*
219 * Free lttng ht node string.
220 */
221void lttng_ht_node_free_str(struct lttng_ht_node_str *node)
222{
a0377dfe 223 LTTNG_ASSERT(node);
bec39940
DG
224 free(node);
225}
226
227/*
228 * Free lttng ht node unsigned long.
229 */
230void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node)
231{
a0377dfe 232 LTTNG_ASSERT(node);
bec39940
DG
233 free(node);
234}
235
d88aee68
DG
236/*
237 * Free lttng ht node uint64_t.
238 */
7972aab2 239void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node)
d88aee68 240{
a0377dfe 241 LTTNG_ASSERT(node);
d88aee68
DG
242 free(node);
243}
244
3c4599b9
JD
245/*
246 * Free lttng ht node two uint64_t.
247 */
248void lttng_ht_node_free_two_u64(struct lttng_ht_node_two_u64 *node)
249{
a0377dfe 250 LTTNG_ASSERT(node);
3c4599b9
JD
251 free(node);
252}
253
bec39940
DG
254/*
255 * Lookup function in hashtable.
256 */
28ab034a 257void lttng_ht_lookup(struct lttng_ht *ht, const void *key, struct lttng_ht_iter *iter)
bec39940 258{
a0377dfe
FD
259 LTTNG_ASSERT(ht);
260 LTTNG_ASSERT(ht->ht);
bec39940 261
28ab034a 262 cds_lfht_lookup(ht->ht, ht->hash_fct(key, lttng_ht_seed), ht->match_fct, key, &iter->iter);
bec39940
DG
263}
264
265/*
266 * Add unique string node to hashtable.
267 */
28ab034a 268void lttng_ht_add_unique_str(struct lttng_ht *ht, struct lttng_ht_node_str *node)
bec39940
DG
269{
270 struct cds_lfht_node *node_ptr;
a0377dfe
FD
271 LTTNG_ASSERT(ht);
272 LTTNG_ASSERT(ht->ht);
273 LTTNG_ASSERT(node);
bec39940 274
42ce408e 275 /* RCU read lock protects from ABA. */
07c4863f 276 const lttng::urcu::read_lock_guard read_lock;
28ab034a
JG
277 node_ptr = cds_lfht_add_unique(ht->ht,
278 ht->hash_fct(node->key, lttng_ht_seed),
279 ht->match_fct,
280 node->key,
281 &node->node);
a0377dfe 282 LTTNG_ASSERT(node_ptr == &node->node);
bec39940
DG
283}
284
efa116c6
JD
285/*
286 * Add string node to hashtable.
287 */
28ab034a 288void lttng_ht_add_str(struct lttng_ht *ht, struct lttng_ht_node_str *node)
efa116c6 289{
a0377dfe
FD
290 LTTNG_ASSERT(ht);
291 LTTNG_ASSERT(ht->ht);
292 LTTNG_ASSERT(node);
efa116c6 293
42ce408e 294 /* RCU read lock protects from ABA. */
07c4863f 295 const lttng::urcu::read_lock_guard read_lock;
28ab034a 296 cds_lfht_add(ht->ht, ht->hash_fct(node->key, lttng_ht_seed), &node->node);
efa116c6
JD
297}
298
aefea3b7
DG
299/*
300 * Add unsigned long node to hashtable.
301 */
302void lttng_ht_add_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node)
303{
a0377dfe
FD
304 LTTNG_ASSERT(ht);
305 LTTNG_ASSERT(ht->ht);
306 LTTNG_ASSERT(node);
aefea3b7 307
42ce408e 308 /* RCU read lock protects from ABA. */
07c4863f 309 const lttng::urcu::read_lock_guard read_lock;
28ab034a 310 cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed), &node->node);
aefea3b7
DG
311}
312
d88aee68
DG
313/*
314 * Add uint64_t node to hashtable.
d88aee68
DG
315 */
316void lttng_ht_add_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node)
317{
a0377dfe
FD
318 LTTNG_ASSERT(ht);
319 LTTNG_ASSERT(ht->ht);
320 LTTNG_ASSERT(node);
d88aee68 321
42ce408e 322 /* RCU read lock protects from ABA. */
07c4863f 323 const lttng::urcu::read_lock_guard read_lock;
28ab034a 324 cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed), &node->node);
d88aee68
DG
325}
326
bec39940
DG
327/*
328 * Add unique unsigned long node to hashtable.
329 */
28ab034a 330void lttng_ht_add_unique_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node)
bec39940
DG
331{
332 struct cds_lfht_node *node_ptr;
a0377dfe
FD
333 LTTNG_ASSERT(ht);
334 LTTNG_ASSERT(ht->ht);
335 LTTNG_ASSERT(node);
bec39940 336
42ce408e 337 /* RCU read lock protects from ABA. */
07c4863f 338 const lttng::urcu::read_lock_guard read_lock;
bec39940 339 node_ptr = cds_lfht_add_unique(ht->ht,
28ab034a
JG
340 ht->hash_fct((void *) node->key, lttng_ht_seed),
341 ht->match_fct,
342 (void *) node->key,
343 &node->node);
a0377dfe 344 LTTNG_ASSERT(node_ptr == &node->node);
bec39940
DG
345}
346
d88aee68
DG
347/*
348 * Add unique uint64_t node to hashtable.
349 */
28ab034a 350void lttng_ht_add_unique_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node)
d88aee68
DG
351{
352 struct cds_lfht_node *node_ptr;
a0377dfe
FD
353 LTTNG_ASSERT(ht);
354 LTTNG_ASSERT(ht->ht);
355 LTTNG_ASSERT(node);
d88aee68 356
42ce408e 357 /* RCU read lock protects from ABA. */
07c4863f 358 const lttng::urcu::read_lock_guard read_lock;
d88aee68 359 node_ptr = cds_lfht_add_unique(ht->ht,
28ab034a
JG
360 ht->hash_fct(&node->key, lttng_ht_seed),
361 ht->match_fct,
362 &node->key,
363 &node->node);
a0377dfe 364 LTTNG_ASSERT(node_ptr == &node->node);
d88aee68
DG
365}
366
3c4599b9
JD
367/*
368 * Add unique two uint64_t node to hashtable.
369 */
28ab034a 370void lttng_ht_add_unique_two_u64(struct lttng_ht *ht, struct lttng_ht_node_two_u64 *node)
3c4599b9
JD
371{
372 struct cds_lfht_node *node_ptr;
a0377dfe
FD
373 LTTNG_ASSERT(ht);
374 LTTNG_ASSERT(ht->ht);
375 LTTNG_ASSERT(node);
3c4599b9 376
42ce408e 377 /* RCU read lock protects from ABA. */
07c4863f 378 const lttng::urcu::read_lock_guard read_lock;
3c4599b9 379 node_ptr = cds_lfht_add_unique(ht->ht,
28ab034a
JG
380 ht->hash_fct((void *) &node->key, lttng_ht_seed),
381 ht->match_fct,
382 (void *) &node->key,
383 &node->node);
a0377dfe 384 LTTNG_ASSERT(node_ptr == &node->node);
3c4599b9
JD
385}
386
702b1ea4
MD
387/*
388 * Add replace unsigned long node to hashtable.
389 */
390struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(struct lttng_ht *ht,
28ab034a 391 struct lttng_ht_node_ulong *node)
702b1ea4
MD
392{
393 struct cds_lfht_node *node_ptr;
a0377dfe
FD
394 LTTNG_ASSERT(ht);
395 LTTNG_ASSERT(ht->ht);
396 LTTNG_ASSERT(node);
702b1ea4 397
42ce408e 398 /* RCU read lock protects from ABA. */
07c4863f 399 const lttng::urcu::read_lock_guard read_lock;
702b1ea4 400 node_ptr = cds_lfht_add_replace(ht->ht,
28ab034a
JG
401 ht->hash_fct((void *) node->key, lttng_ht_seed),
402 ht->match_fct,
403 (void *) node->key,
404 &node->node);
702b1ea4 405 if (!node_ptr) {
cd9adb8b 406 return nullptr;
702b1ea4 407 } else {
ef2f8a02
JG
408 return reinterpret_cast<lttng_ht_node_ulong *>(
409 lttng::utils::container_of(node_ptr, &lttng_ht_node_ulong::node));
702b1ea4 410 }
702b1ea4
MD
411}
412
d88aee68
DG
413/*
414 * Add replace unsigned long node to hashtable.
415 */
416struct lttng_ht_node_u64 *lttng_ht_add_replace_u64(struct lttng_ht *ht,
28ab034a 417 struct lttng_ht_node_u64 *node)
d88aee68
DG
418{
419 struct cds_lfht_node *node_ptr;
a0377dfe
FD
420 LTTNG_ASSERT(ht);
421 LTTNG_ASSERT(ht->ht);
422 LTTNG_ASSERT(node);
d88aee68 423
42ce408e 424 /* RCU read lock protects from ABA. */
07c4863f 425 const lttng::urcu::read_lock_guard read_lock;
d88aee68 426 node_ptr = cds_lfht_add_replace(ht->ht,
28ab034a
JG
427 ht->hash_fct(&node->key, lttng_ht_seed),
428 ht->match_fct,
429 &node->key,
430 &node->node);
d88aee68 431 if (!node_ptr) {
cd9adb8b 432 return nullptr;
d88aee68 433 } else {
56047f5a 434 LTTNG_ASSERT(node_ptr == &node->node);
ef2f8a02
JG
435 return reinterpret_cast<lttng_ht_node_u64 *>(
436 lttng::utils::container_of(node_ptr, &lttng_ht_node_u64::node));
d88aee68 437 }
d88aee68
DG
438}
439
bec39940
DG
440/*
441 * Delete node from hashtable.
442 */
443int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
444{
42ce408e
MD
445 int ret;
446
a0377dfe
FD
447 LTTNG_ASSERT(ht);
448 LTTNG_ASSERT(ht->ht);
449 LTTNG_ASSERT(iter);
bec39940 450
42ce408e 451 /* RCU read lock protects from ABA. */
07c4863f 452 const lttng::urcu::read_lock_guard read_lock;
42ce408e 453 ret = cds_lfht_del(ht->ht, iter->iter.node);
42ce408e 454 return ret;
bec39940
DG
455}
456
457/*
458 * Get first node in the hashtable.
459 */
460void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter)
461{
a0377dfe
FD
462 LTTNG_ASSERT(ht);
463 LTTNG_ASSERT(ht->ht);
464 LTTNG_ASSERT(iter);
bec39940
DG
465
466 cds_lfht_first(ht->ht, &iter->iter);
467}
468
469/*
470 * Get next node in the hashtable.
471 */
472void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter)
473{
a0377dfe
FD
474 LTTNG_ASSERT(ht);
475 LTTNG_ASSERT(ht->ht);
476 LTTNG_ASSERT(iter);
bec39940
DG
477
478 cds_lfht_next(ht->ht, &iter->iter);
479}
480
481/*
482 * Return the number of nodes in the hashtable.
483 */
484unsigned long lttng_ht_get_count(struct lttng_ht *ht)
485{
486 long scb, sca;
487 unsigned long count;
488
a0377dfe
FD
489 LTTNG_ASSERT(ht);
490 LTTNG_ASSERT(ht->ht);
bec39940 491
42ce408e 492 /* RCU read lock protects from ABA and allows RCU traversal. */
07c4863f 493 const lttng::urcu::read_lock_guard read_lock;
bec39940
DG
494 cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
495
496 return count;
00d7d903 497}
This page took 0.12387 seconds and 5 git commands to generate.