Commit | Line | Data |
---|---|---|
bec39940 DG |
1 | /* |
2 | * Copyright (C) 2011 - David Goulet <david.goulet@polymtl.ca> | |
3 | * | |
d14d33bf AM |
4 | * This program is free software; you can redistribute it and/or modify |
5 | * it under the terms of the GNU General Public License, version 2 only, | |
6 | * as published by the Free Software Foundation. | |
bec39940 DG |
7 | * |
8 | * This program is distributed in the hope that it will be useful, but WITHOUT | |
9 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
d14d33bf | 10 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for |
bec39940 DG |
11 | * more details. |
12 | * | |
d14d33bf AM |
13 | * You should have received a copy of the GNU General Public License along |
14 | * with this program; if not, write to the Free Software Foundation, Inc., | |
15 | * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. | |
bec39940 DG |
16 | */ |
17 | ||
18 | #define _GNU_SOURCE | |
6c1c0768 | 19 | #define _LGPL_SOURCE |
bec39940 DG |
20 | #include <assert.h> |
21 | #include <string.h> | |
22 | #include <urcu.h> | |
23 | #include <urcu/compiler.h> | |
24 | ||
990570ed DG |
25 | #include <common/common.h> |
26 | #include <common/defaults.h> | |
bec39940 | 27 | |
10a8a223 | 28 | #include "hashtable.h" |
bec39940 DG |
29 | #include "utils.h" |
30 | ||
b6314938 | 31 | unsigned long lttng_ht_seed; |
bec39940 DG |
32 | |
33 | static unsigned long min_hash_alloc_size = 1; | |
13fe1164 | 34 | static unsigned long max_hash_buckets_size = 0; |
bec39940 | 35 | |
63ee5555 MD |
36 | /* |
37 | * Getter/lookup functions need to be called with RCU read-side lock | |
38 | * held. However, modification functions (add, add_unique, replace, del) | |
39 | * take the RCU lock internally, so it does not matter whether the | |
40 | * caller hold the RCU lock or not. | |
41 | */ | |
42 | ||
bec39940 DG |
43 | /* |
44 | * Match function for string node. | |
45 | */ | |
46 | static int match_str(struct cds_lfht_node *node, const void *key) | |
47 | { | |
48 | struct lttng_ht_node_str *match_node = | |
49 | caa_container_of(node, struct lttng_ht_node_str, node); | |
50 | ||
51 | return hash_match_key_str(match_node->key, (void *) key); | |
52 | } | |
53 | ||
54 | /* | |
55 | * Match function for ulong node. | |
56 | */ | |
57 | static int match_ulong(struct cds_lfht_node *node, const void *key) | |
58 | { | |
59 | struct lttng_ht_node_ulong *match_node = | |
60 | caa_container_of(node, struct lttng_ht_node_ulong, node); | |
61 | ||
62 | return hash_match_key_ulong((void *) match_node->key, (void *) key); | |
63 | } | |
64 | ||
d88aee68 DG |
65 | /* |
66 | * Match function for u64 node. | |
67 | */ | |
68 | static int match_u64(struct cds_lfht_node *node, const void *key) | |
69 | { | |
70 | struct lttng_ht_node_u64 *match_node = | |
71 | caa_container_of(node, struct lttng_ht_node_u64, node); | |
72 | ||
73 | return hash_match_key_u64(&match_node->key, (void *) key); | |
74 | } | |
75 | ||
3c4599b9 JD |
76 | /* |
77 | * Match function for two uint64_t node. | |
78 | */ | |
79 | static int match_two_u64(struct cds_lfht_node *node, const void *key) | |
80 | { | |
81 | struct lttng_ht_node_two_u64 *match_node = | |
82 | caa_container_of(node, struct lttng_ht_node_two_u64, node); | |
83 | ||
84 | return hash_match_key_two_u64((void *) &match_node->key, (void *) key); | |
85 | } | |
86 | ||
bec39940 DG |
87 | /* |
88 | * Return an allocated lttng hashtable. | |
89 | */ | |
90 | struct lttng_ht *lttng_ht_new(unsigned long size, int type) | |
91 | { | |
92 | struct lttng_ht *ht; | |
93 | ||
94 | /* Test size */ | |
dc78d159 MD |
95 | if (!size) |
96 | size = DEFAULT_HT_SIZE; | |
bec39940 DG |
97 | |
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 | ||
139 | error: | |
140 | return NULL; | |
141 | } | |
142 | ||
143 | /* | |
144 | * Free a lttng hashtable. | |
145 | */ | |
146 | void lttng_ht_destroy(struct lttng_ht *ht) | |
147 | { | |
148 | int ret; | |
149 | ||
150 | ret = cds_lfht_destroy(ht->ht, NULL); | |
151 | assert(!ret); | |
cf5280ea | 152 | free(ht); |
bec39940 DG |
153 | } |
154 | ||
155 | /* | |
156 | * Init lttng ht node string. | |
157 | */ | |
158 | void lttng_ht_node_init_str(struct lttng_ht_node_str *node, char *key) | |
159 | { | |
160 | assert(node); | |
161 | ||
162 | node->key = key; | |
163 | cds_lfht_node_init(&node->node); | |
164 | } | |
165 | ||
166 | /* | |
167 | * Init lttng ht node unsigned long. | |
168 | */ | |
169 | void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node, | |
170 | unsigned long key) | |
171 | { | |
172 | assert(node); | |
173 | ||
174 | node->key = key; | |
175 | cds_lfht_node_init(&node->node); | |
176 | } | |
177 | ||
d88aee68 DG |
178 | /* |
179 | * Init lttng ht node uint64_t. | |
180 | */ | |
181 | void lttng_ht_node_init_u64(struct lttng_ht_node_u64 *node, | |
182 | uint64_t key) | |
183 | { | |
184 | assert(node); | |
185 | ||
186 | node->key = key; | |
187 | cds_lfht_node_init(&node->node); | |
188 | } | |
189 | ||
3c4599b9 JD |
190 | /* |
191 | * Init lttng ht node with two uint64_t. | |
192 | */ | |
193 | void lttng_ht_node_init_two_u64(struct lttng_ht_node_two_u64 *node, | |
194 | uint64_t key1, uint64_t key2) | |
195 | { | |
196 | assert(node); | |
197 | ||
198 | node->key.key1 = key1; | |
199 | node->key.key2 = key2; | |
200 | cds_lfht_node_init(&node->node); | |
201 | } | |
202 | ||
bec39940 DG |
203 | /* |
204 | * Free lttng ht node string. | |
205 | */ | |
206 | void lttng_ht_node_free_str(struct lttng_ht_node_str *node) | |
207 | { | |
208 | assert(node); | |
209 | free(node); | |
210 | } | |
211 | ||
212 | /* | |
213 | * Free lttng ht node unsigned long. | |
214 | */ | |
215 | void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node) | |
216 | { | |
217 | assert(node); | |
218 | free(node); | |
219 | } | |
220 | ||
d88aee68 DG |
221 | /* |
222 | * Free lttng ht node uint64_t. | |
223 | */ | |
7972aab2 | 224 | void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node) |
d88aee68 DG |
225 | { |
226 | assert(node); | |
227 | free(node); | |
228 | } | |
229 | ||
3c4599b9 JD |
230 | /* |
231 | * Free lttng ht node two uint64_t. | |
232 | */ | |
233 | void lttng_ht_node_free_two_u64(struct lttng_ht_node_two_u64 *node) | |
234 | { | |
235 | assert(node); | |
236 | free(node); | |
237 | } | |
238 | ||
bec39940 DG |
239 | /* |
240 | * Lookup function in hashtable. | |
241 | */ | |
242 | void lttng_ht_lookup(struct lttng_ht *ht, void *key, | |
243 | struct lttng_ht_iter *iter) | |
244 | { | |
245 | assert(ht); | |
246 | assert(ht->ht); | |
bec39940 | 247 | |
b6314938 | 248 | cds_lfht_lookup(ht->ht, ht->hash_fct(key, lttng_ht_seed), |
bec39940 DG |
249 | ht->match_fct, key, &iter->iter); |
250 | } | |
251 | ||
252 | /* | |
253 | * Add unique string node to hashtable. | |
254 | */ | |
255 | void lttng_ht_add_unique_str(struct lttng_ht *ht, | |
256 | struct lttng_ht_node_str *node) | |
257 | { | |
258 | struct cds_lfht_node *node_ptr; | |
259 | assert(ht); | |
260 | assert(ht->ht); | |
261 | assert(node); | |
262 | ||
63ee5555 MD |
263 | /* RCU read lock protects from ABA. */ |
264 | rcu_read_lock(); | |
b6314938 | 265 | node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(node->key, lttng_ht_seed), |
bec39940 | 266 | ht->match_fct, node->key, &node->node); |
63ee5555 | 267 | rcu_read_unlock(); |
bec39940 DG |
268 | assert(node_ptr == &node->node); |
269 | } | |
270 | ||
efa116c6 JD |
271 | /* |
272 | * Add string node to hashtable. | |
273 | */ | |
274 | void lttng_ht_add_str(struct lttng_ht *ht, | |
275 | struct lttng_ht_node_str *node) | |
276 | { | |
277 | assert(ht); | |
278 | assert(ht->ht); | |
279 | assert(node); | |
280 | ||
63ee5555 MD |
281 | /* RCU read lock protects from ABA. */ |
282 | rcu_read_lock(); | |
efa116c6 JD |
283 | cds_lfht_add(ht->ht, ht->hash_fct(node->key, lttng_ht_seed), |
284 | &node->node); | |
63ee5555 | 285 | rcu_read_unlock(); |
efa116c6 JD |
286 | } |
287 | ||
aefea3b7 DG |
288 | /* |
289 | * Add unsigned long node to hashtable. | |
290 | */ | |
291 | void lttng_ht_add_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node) | |
292 | { | |
293 | assert(ht); | |
294 | assert(ht->ht); | |
295 | assert(node); | |
296 | ||
63ee5555 MD |
297 | /* RCU read lock protects from ABA. */ |
298 | rcu_read_lock(); | |
b6314938 | 299 | cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed), |
aefea3b7 | 300 | &node->node); |
63ee5555 | 301 | rcu_read_unlock(); |
aefea3b7 DG |
302 | } |
303 | ||
d88aee68 DG |
304 | /* |
305 | * Add uint64_t node to hashtable. | |
306 | ||
307 | */ | |
308 | void lttng_ht_add_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node) | |
309 | { | |
310 | assert(ht); | |
311 | assert(ht->ht); | |
312 | assert(node); | |
313 | ||
63ee5555 MD |
314 | /* RCU read lock protects from ABA. */ |
315 | rcu_read_lock(); | |
d88aee68 DG |
316 | cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed), |
317 | &node->node); | |
63ee5555 | 318 | rcu_read_unlock(); |
d88aee68 DG |
319 | } |
320 | ||
bec39940 DG |
321 | /* |
322 | * Add unique unsigned long node to hashtable. | |
323 | */ | |
324 | void lttng_ht_add_unique_ulong(struct lttng_ht *ht, | |
325 | struct lttng_ht_node_ulong *node) | |
326 | { | |
327 | struct cds_lfht_node *node_ptr; | |
328 | assert(ht); | |
329 | assert(ht->ht); | |
330 | assert(node); | |
331 | ||
63ee5555 MD |
332 | /* RCU read lock protects from ABA. */ |
333 | rcu_read_lock(); | |
bec39940 | 334 | node_ptr = cds_lfht_add_unique(ht->ht, |
b6314938 | 335 | ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct, |
bec39940 | 336 | (void *) node->key, &node->node); |
63ee5555 | 337 | rcu_read_unlock(); |
bec39940 DG |
338 | assert(node_ptr == &node->node); |
339 | } | |
340 | ||
d88aee68 DG |
341 | /* |
342 | * Add unique uint64_t node to hashtable. | |
343 | */ | |
344 | void lttng_ht_add_unique_u64(struct lttng_ht *ht, | |
345 | struct lttng_ht_node_u64 *node) | |
346 | { | |
347 | struct cds_lfht_node *node_ptr; | |
348 | assert(ht); | |
349 | assert(ht->ht); | |
350 | assert(node); | |
351 | ||
63ee5555 MD |
352 | /* RCU read lock protects from ABA. */ |
353 | rcu_read_lock(); | |
d88aee68 DG |
354 | node_ptr = cds_lfht_add_unique(ht->ht, |
355 | ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct, | |
356 | &node->key, &node->node); | |
63ee5555 | 357 | rcu_read_unlock(); |
d88aee68 DG |
358 | assert(node_ptr == &node->node); |
359 | } | |
360 | ||
3c4599b9 JD |
361 | /* |
362 | * Add unique two uint64_t node to hashtable. | |
363 | */ | |
364 | void lttng_ht_add_unique_two_u64(struct lttng_ht *ht, | |
365 | struct lttng_ht_node_two_u64 *node) | |
366 | { | |
367 | struct cds_lfht_node *node_ptr; | |
368 | assert(ht); | |
369 | assert(ht->ht); | |
370 | assert(node); | |
371 | ||
63ee5555 MD |
372 | /* RCU read lock protects from ABA. */ |
373 | rcu_read_lock(); | |
3c4599b9 JD |
374 | node_ptr = cds_lfht_add_unique(ht->ht, |
375 | ht->hash_fct((void *) &node->key, lttng_ht_seed), ht->match_fct, | |
376 | (void *) &node->key, &node->node); | |
63ee5555 | 377 | rcu_read_unlock(); |
3c4599b9 JD |
378 | assert(node_ptr == &node->node); |
379 | } | |
380 | ||
702b1ea4 MD |
381 | /* |
382 | * Add replace unsigned long node to hashtable. | |
383 | */ | |
384 | struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(struct lttng_ht *ht, | |
385 | struct lttng_ht_node_ulong *node) | |
386 | { | |
387 | struct cds_lfht_node *node_ptr; | |
388 | assert(ht); | |
389 | assert(ht->ht); | |
390 | assert(node); | |
391 | ||
63ee5555 MD |
392 | /* RCU read lock protects from ABA. */ |
393 | rcu_read_lock(); | |
702b1ea4 | 394 | node_ptr = cds_lfht_add_replace(ht->ht, |
b6314938 | 395 | ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct, |
702b1ea4 | 396 | (void *) node->key, &node->node); |
63ee5555 | 397 | rcu_read_unlock(); |
702b1ea4 MD |
398 | if (!node_ptr) { |
399 | return NULL; | |
400 | } else { | |
401 | return caa_container_of(node_ptr, struct lttng_ht_node_ulong, node); | |
402 | } | |
403 | assert(node_ptr == &node->node); | |
404 | } | |
405 | ||
d88aee68 DG |
406 | /* |
407 | * Add replace unsigned long node to hashtable. | |
408 | */ | |
409 | struct lttng_ht_node_u64 *lttng_ht_add_replace_u64(struct lttng_ht *ht, | |
410 | struct lttng_ht_node_u64 *node) | |
411 | { | |
412 | struct cds_lfht_node *node_ptr; | |
413 | assert(ht); | |
414 | assert(ht->ht); | |
415 | assert(node); | |
416 | ||
63ee5555 MD |
417 | /* RCU read lock protects from ABA. */ |
418 | rcu_read_lock(); | |
d88aee68 DG |
419 | node_ptr = cds_lfht_add_replace(ht->ht, |
420 | ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct, | |
421 | &node->key, &node->node); | |
63ee5555 | 422 | rcu_read_unlock(); |
d88aee68 DG |
423 | if (!node_ptr) { |
424 | return NULL; | |
425 | } else { | |
426 | return caa_container_of(node_ptr, struct lttng_ht_node_u64, node); | |
427 | } | |
428 | assert(node_ptr == &node->node); | |
429 | } | |
430 | ||
bec39940 DG |
431 | /* |
432 | * Delete node from hashtable. | |
433 | */ | |
434 | int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter) | |
435 | { | |
63ee5555 MD |
436 | int ret; |
437 | ||
bec39940 DG |
438 | assert(ht); |
439 | assert(ht->ht); | |
440 | assert(iter); | |
441 | ||
63ee5555 MD |
442 | /* RCU read lock protects from ABA. */ |
443 | rcu_read_lock(); | |
444 | ret = cds_lfht_del(ht->ht, iter->iter.node); | |
445 | rcu_read_unlock(); | |
446 | return ret; | |
bec39940 DG |
447 | } |
448 | ||
449 | /* | |
450 | * Get first node in the hashtable. | |
451 | */ | |
452 | void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter) | |
453 | { | |
454 | assert(ht); | |
455 | assert(ht->ht); | |
456 | assert(iter); | |
457 | ||
458 | cds_lfht_first(ht->ht, &iter->iter); | |
459 | } | |
460 | ||
461 | /* | |
462 | * Get next node in the hashtable. | |
463 | */ | |
464 | void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter) | |
465 | { | |
466 | assert(ht); | |
467 | assert(ht->ht); | |
468 | assert(iter); | |
469 | ||
470 | cds_lfht_next(ht->ht, &iter->iter); | |
471 | } | |
472 | ||
473 | /* | |
474 | * Return the number of nodes in the hashtable. | |
475 | */ | |
476 | unsigned long lttng_ht_get_count(struct lttng_ht *ht) | |
477 | { | |
478 | long scb, sca; | |
479 | unsigned long count; | |
480 | ||
481 | assert(ht); | |
482 | assert(ht->ht); | |
483 | ||
63ee5555 MD |
484 | /* RCU read lock protects from ABA and allows RCU traversal. */ |
485 | rcu_read_lock(); | |
bec39940 | 486 | cds_lfht_count_nodes(ht->ht, &scb, &count, &sca); |
63ee5555 | 487 | rcu_read_unlock(); |
bec39940 DG |
488 | |
489 | return count; | |
490 | } | |
491 | ||
492 | /* | |
493 | * Return lttng ht string node from iterator. | |
494 | */ | |
495 | struct lttng_ht_node_str *lttng_ht_iter_get_node_str( | |
496 | struct lttng_ht_iter *iter) | |
497 | { | |
498 | struct cds_lfht_node *node; | |
499 | ||
500 | assert(iter); | |
501 | node = cds_lfht_iter_get_node(&iter->iter); | |
502 | if (!node) { | |
503 | return NULL; | |
504 | } | |
505 | return caa_container_of(node, struct lttng_ht_node_str, node); | |
506 | } | |
507 | ||
508 | /* | |
509 | * Return lttng ht unsigned long node from iterator. | |
510 | */ | |
511 | struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong( | |
512 | struct lttng_ht_iter *iter) | |
513 | { | |
514 | struct cds_lfht_node *node; | |
515 | ||
516 | assert(iter); | |
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_ulong, node); | |
522 | } | |
b6314938 | 523 | |
d88aee68 DG |
524 | /* |
525 | * Return lttng ht unsigned long node from iterator. | |
526 | */ | |
527 | struct lttng_ht_node_u64 *lttng_ht_iter_get_node_u64( | |
528 | struct lttng_ht_iter *iter) | |
529 | { | |
530 | struct cds_lfht_node *node; | |
531 | ||
532 | assert(iter); | |
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_u64, node); | |
538 | } | |
539 | ||
3c4599b9 JD |
540 | /* |
541 | * Return lttng ht stream and index id node from iterator. | |
542 | */ | |
543 | struct lttng_ht_node_two_u64 *lttng_ht_iter_get_node_two_u64( | |
544 | struct lttng_ht_iter *iter) | |
545 | { | |
546 | struct cds_lfht_node *node; | |
547 | ||
548 | assert(iter); | |
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_two_u64, node); | |
554 | } | |
555 | ||
b6314938 DG |
556 | /* |
557 | * lib constructor | |
558 | */ | |
d88aee68 | 559 | static void __attribute__((constructor)) _init(void) |
b6314938 DG |
560 | { |
561 | /* Init hash table seed */ | |
562 | lttng_ht_seed = (unsigned long) time(NULL); | |
563 | } |