src/common/hashtable/hashtable.cpp

   1 /*
   2  * Copyright (C) 2011 EfficiOS Inc.
   3  *
   4  * SPDX-License-Identifier: GPL-2.0-only
   5  *
   6  */
   7
   8 #define _LGPL_SOURCE
   9 #include "hashtable.hpp"
  10 #include "utils.hpp"
  11
  12 #include <common/common.hpp>
  13 #include <common/defaults.hpp>
  14 #include <common/urcu.hpp>
  15
  16 #include <string.h>
  17 #include <urcu.h>
  18 #include <urcu/compiler.h>
  19
  20 /* seed_lock protects both seed_init and lttng_ht_seed. */
  21 static pthread_mutex_t seed_lock = PTHREAD_MUTEX_INITIALIZER;
  22 static bool seed_init;
  23
  24 static unsigned long min_hash_alloc_size = 1;
  25 static unsigned long max_hash_buckets_size = 0;
  26
  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
  34 /*
  35  * Match function for string node.
  36  */
  37 static int match_str(struct cds_lfht_node *node, const void *key)
  38 {
  39         struct lttng_ht_node_str *match_node =
  40                 lttng::utils::container_of(node, &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  */
  48 static int match_ulong(struct cds_lfht_node *node, const void *key)
  49 {
  50         struct lttng_ht_node_ulong *match_node =
  51                 lttng::utils::container_of(node, &lttng_ht_node_ulong::node);
  52
  53         return hash_match_key_ulong((void *) match_node->key, (void *) key);
  54 }
  55
  56 /*
  57  * Match function for u64 node.
  58  */
  59 static int match_u64(struct cds_lfht_node *node, const void *key)
  60 {
  61         struct lttng_ht_node_u64 *match_node =
  62                 lttng::utils::container_of(node, &lttng_ht_node_u64::node);
  63
  64         return hash_match_key_u64(&match_node->key, (void *) key);
  65 }
  66
  67 /*
  68  * Match function for two uint64_t node.
  69  */
  70 static int match_two_u64(struct cds_lfht_node *node, const void *key)
  71 {
  72         struct lttng_ht_node_two_u64 *match_node =
  73                 lttng::utils::container_of(node, &lttng_ht_node_two_u64::node);
  74
  75         return hash_match_key_two_u64((void *) &match_node->key, (void *) key);
  76 }
  77
  78 static inline const char *lttng_ht_type_str(enum lttng_ht_type type)
  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
  95 /*
  96  * Return an allocated lttng hashtable.
  97  */
  98 struct lttng_ht *lttng_ht_new(unsigned long size, lttng_ht_type type)
  99 {
 100         struct lttng_ht *ht;
 101
 102         /* Test size */
 103         if (!size)
 104                 size = DEFAULT_HT_SIZE;
 105
 106         pthread_mutex_lock(&seed_lock);
 107         if (!seed_init) {
 108                 lttng_ht_seed = (unsigned long) time(nullptr);
 109                 seed_init = true;
 110         }
 111         pthread_mutex_unlock(&seed_lock);
 112
 113         ht = zmalloc<lttng_ht>();
 114         if (ht == nullptr) {
 115                 PERROR("zmalloc lttng_ht");
 116                 goto error;
 117         }
 118
 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,
 123                               nullptr);
 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         LTTNG_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;
 139         case LTTNG_HT_TYPE_U64:
 140                 ht->match_fct = match_u64;
 141                 ht->hash_fct = hash_key_u64;
 142                 break;
 143         case LTTNG_HT_TYPE_TWO_U64:
 144                 ht->match_fct = match_two_u64;
 145                 ht->hash_fct = hash_key_two_u64;
 146                 break;
 147         default:
 148                 ERR("Unknown lttng hashtable type %d", type);
 149                 lttng_ht_destroy(ht);
 150                 goto error;
 151         }
 152
 153         DBG3("Created hashtable size %lu at %p of type %s", size, ht->ht, lttng_ht_type_str(type));
 154
 155         return ht;
 156
 157 error:
 158         return nullptr;
 159 }
 160
 161 /*
 162  * Free a lttng hashtable.
 163  */
 164 void lttng_ht_destroy(struct lttng_ht *ht)
 165 {
 166         int ret;
 167
 168         ret = cds_lfht_destroy(ht->ht, nullptr);
 169         LTTNG_ASSERT(!ret);
 170         free(ht);
 171 }
 172
 173 /*
 174  * Init lttng ht node string.
 175  */
 176 void lttng_ht_node_init_str(struct lttng_ht_node_str *node, char *key)
 177 {
 178         LTTNG_ASSERT(node);
 179
 180         node->key = key;
 181         cds_lfht_node_init(&node->node);
 182 }
 183
 184 /*
 185  * Init lttng ht node unsigned long.
 186  */
 187 void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node, unsigned long key)
 188 {
 189         LTTNG_ASSERT(node);
 190
 191         node->key = key;
 192         cds_lfht_node_init(&node->node);
 193 }
 194
 195 /*
 196  * Init lttng ht node uint64_t.
 197  */
 198 void lttng_ht_node_init_u64(struct lttng_ht_node_u64 *node, uint64_t key)
 199 {
 200         LTTNG_ASSERT(node);
 201
 202         node->key = key;
 203         cds_lfht_node_init(&node->node);
 204 }
 205
 206 /*
 207  * Init lttng ht node with two uint64_t.
 208  */
 209 void lttng_ht_node_init_two_u64(struct lttng_ht_node_two_u64 *node, uint64_t key1, uint64_t key2)
 210 {
 211         LTTNG_ASSERT(node);
 212
 213         node->key.key1 = key1;
 214         node->key.key2 = key2;
 215         cds_lfht_node_init(&node->node);
 216 }
 217
 218 /*
 219  * Free lttng ht node string.
 220  */
 221 void lttng_ht_node_free_str(struct lttng_ht_node_str *node)
 222 {
 223         LTTNG_ASSERT(node);
 224         free(node);
 225 }
 226
 227 /*
 228  * Free lttng ht node unsigned long.
 229  */
 230 void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node)
 231 {
 232         LTTNG_ASSERT(node);
 233         free(node);
 234 }
 235
 236 /*
 237  * Free lttng ht node uint64_t.
 238  */
 239 void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node)
 240 {
 241         LTTNG_ASSERT(node);
 242         free(node);
 243 }
 244
 245 /*
 246  * Free lttng ht node two uint64_t.
 247  */
 248 void lttng_ht_node_free_two_u64(struct lttng_ht_node_two_u64 *node)
 249 {
 250         LTTNG_ASSERT(node);
 251         free(node);
 252 }
 253
 254 /*
 255  * Lookup function in hashtable.
 256  */
 257 void lttng_ht_lookup(struct lttng_ht *ht, const void *key, struct lttng_ht_iter *iter)
 258 {
 259         LTTNG_ASSERT(ht);
 260         LTTNG_ASSERT(ht->ht);
 261
 262         cds_lfht_lookup(ht->ht, ht->hash_fct(key, lttng_ht_seed), ht->match_fct, key, &iter->iter);
 263 }
 264
 265 /*
 266  * Add unique string node to hashtable.
 267  */
 268 void lttng_ht_add_unique_str(struct lttng_ht *ht, struct lttng_ht_node_str *node)
 269 {
 270         struct cds_lfht_node *node_ptr;
 271         LTTNG_ASSERT(ht);
 272         LTTNG_ASSERT(ht->ht);
 273         LTTNG_ASSERT(node);
 274
 275         /* RCU read lock protects from ABA. */
 276         lttng::urcu::read_lock_guard read_lock;
 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);
 282         LTTNG_ASSERT(node_ptr == &node->node);
 283 }
 284
 285 /*
 286  * Add string node to hashtable.
 287  */
 288 void lttng_ht_add_str(struct lttng_ht *ht, struct lttng_ht_node_str *node)
 289 {
 290         LTTNG_ASSERT(ht);
 291         LTTNG_ASSERT(ht->ht);
 292         LTTNG_ASSERT(node);
 293
 294         /* RCU read lock protects from ABA. */
 295         lttng::urcu::read_lock_guard read_lock;
 296         cds_lfht_add(ht->ht, ht->hash_fct(node->key, lttng_ht_seed), &node->node);
 297 }
 298
 299 /*
 300  * Add unsigned long node to hashtable.
 301  */
 302 void lttng_ht_add_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node)
 303 {
 304         LTTNG_ASSERT(ht);
 305         LTTNG_ASSERT(ht->ht);
 306         LTTNG_ASSERT(node);
 307
 308         /* RCU read lock protects from ABA. */
 309         lttng::urcu::read_lock_guard read_lock;
 310         cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed), &node->node);
 311 }
 312
 313 /*
 314  * Add uint64_t node to hashtable.
 315  */
 316 void lttng_ht_add_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node)
 317 {
 318         LTTNG_ASSERT(ht);
 319         LTTNG_ASSERT(ht->ht);
 320         LTTNG_ASSERT(node);
 321
 322         /* RCU read lock protects from ABA. */
 323         lttng::urcu::read_lock_guard read_lock;
 324         cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed), &node->node);
 325 }
 326
 327 /*
 328  * Add unique unsigned long node to hashtable.
 329  */
 330 void lttng_ht_add_unique_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node)
 331 {
 332         struct cds_lfht_node *node_ptr;
 333         LTTNG_ASSERT(ht);
 334         LTTNG_ASSERT(ht->ht);
 335         LTTNG_ASSERT(node);
 336
 337         /* RCU read lock protects from ABA. */
 338         lttng::urcu::read_lock_guard read_lock;
 339         node_ptr = cds_lfht_add_unique(ht->ht,
 340                                        ht->hash_fct((void *) node->key, lttng_ht_seed),
 341                                        ht->match_fct,
 342                                        (void *) node->key,
 343                                        &node->node);
 344         LTTNG_ASSERT(node_ptr == &node->node);
 345 }
 346
 347 /*
 348  * Add unique uint64_t node to hashtable.
 349  */
 350 void lttng_ht_add_unique_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node)
 351 {
 352         struct cds_lfht_node *node_ptr;
 353         LTTNG_ASSERT(ht);
 354         LTTNG_ASSERT(ht->ht);
 355         LTTNG_ASSERT(node);
 356
 357         /* RCU read lock protects from ABA. */
 358         lttng::urcu::read_lock_guard read_lock;
 359         node_ptr = cds_lfht_add_unique(ht->ht,
 360                                        ht->hash_fct(&node->key, lttng_ht_seed),
 361                                        ht->match_fct,
 362                                        &node->key,
 363                                        &node->node);
 364         LTTNG_ASSERT(node_ptr == &node->node);
 365 }
 366
 367 /*
 368  * Add unique two uint64_t node to hashtable.
 369  */
 370 void lttng_ht_add_unique_two_u64(struct lttng_ht *ht, struct lttng_ht_node_two_u64 *node)
 371 {
 372         struct cds_lfht_node *node_ptr;
 373         LTTNG_ASSERT(ht);
 374         LTTNG_ASSERT(ht->ht);
 375         LTTNG_ASSERT(node);
 376
 377         /* RCU read lock protects from ABA. */
 378         lttng::urcu::read_lock_guard read_lock;
 379         node_ptr = cds_lfht_add_unique(ht->ht,
 380                                        ht->hash_fct((void *) &node->key, lttng_ht_seed),
 381                                        ht->match_fct,
 382                                        (void *) &node->key,
 383                                        &node->node);
 384         LTTNG_ASSERT(node_ptr == &node->node);
 385 }
 386
 387 /*
 388  * Add replace unsigned long node to hashtable.
 389  */
 390 struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(struct lttng_ht *ht,
 391                                                        struct lttng_ht_node_ulong *node)
 392 {
 393         struct cds_lfht_node *node_ptr;
 394         LTTNG_ASSERT(ht);
 395         LTTNG_ASSERT(ht->ht);
 396         LTTNG_ASSERT(node);
 397
 398         /* RCU read lock protects from ABA. */
 399         lttng::urcu::read_lock_guard read_lock;
 400         node_ptr = cds_lfht_add_replace(ht->ht,
 401                                         ht->hash_fct((void *) node->key, lttng_ht_seed),
 402                                         ht->match_fct,
 403                                         (void *) node->key,
 404                                         &node->node);
 405         if (!node_ptr) {
 406                 return nullptr;
 407         } else {
 408                 return lttng::utils::container_of(node_ptr, &lttng_ht_node_ulong::node);
 409         }
 410 }
 411
 412 /*
 413  * Add replace unsigned long node to hashtable.
 414  */
 415 struct lttng_ht_node_u64 *lttng_ht_add_replace_u64(struct lttng_ht *ht,
 416                                                    struct lttng_ht_node_u64 *node)
 417 {
 418         struct cds_lfht_node *node_ptr;
 419         LTTNG_ASSERT(ht);
 420         LTTNG_ASSERT(ht->ht);
 421         LTTNG_ASSERT(node);
 422
 423         /* RCU read lock protects from ABA. */
 424         lttng::urcu::read_lock_guard read_lock;
 425         node_ptr = cds_lfht_add_replace(ht->ht,
 426                                         ht->hash_fct(&node->key, lttng_ht_seed),
 427                                         ht->match_fct,
 428                                         &node->key,
 429                                         &node->node);
 430         if (!node_ptr) {
 431                 return nullptr;
 432         } else {
 433                 LTTNG_ASSERT(node_ptr == &node->node);
 434                 return lttng::utils::container_of(node_ptr, &lttng_ht_node_u64::node);
 435         }
 436 }
 437
 438 /*
 439  * Delete node from hashtable.
 440  */
 441 int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 442 {
 443         int ret;
 444
 445         LTTNG_ASSERT(ht);
 446         LTTNG_ASSERT(ht->ht);
 447         LTTNG_ASSERT(iter);
 448
 449         /* RCU read lock protects from ABA. */
 450         lttng::urcu::read_lock_guard read_lock;
 451         ret = cds_lfht_del(ht->ht, iter->iter.node);
 452         return ret;
 453 }
 454
 455 /*
 456  * Get first node in the hashtable.
 457  */
 458 void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 459 {
 460         LTTNG_ASSERT(ht);
 461         LTTNG_ASSERT(ht->ht);
 462         LTTNG_ASSERT(iter);
 463
 464         cds_lfht_first(ht->ht, &iter->iter);
 465 }
 466
 467 /*
 468  * Get next node in the hashtable.
 469  */
 470 void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 471 {
 472         LTTNG_ASSERT(ht);
 473         LTTNG_ASSERT(ht->ht);
 474         LTTNG_ASSERT(iter);
 475
 476         cds_lfht_next(ht->ht, &iter->iter);
 477 }
 478
 479 /*
 480  * Return the number of nodes in the hashtable.
 481  */
 482 unsigned long lttng_ht_get_count(struct lttng_ht *ht)
 483 {
 484         long scb, sca;
 485         unsigned long count;
 486
 487         LTTNG_ASSERT(ht);
 488         LTTNG_ASSERT(ht->ht);
 489
 490         /* RCU read lock protects from ABA and allows RCU traversal. */
 491         lttng::urcu::read_lock_guard read_lock;
 492         cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
 493
 494         return count;
 495 }
 496
 497 /*
 498  * Return lttng ht string node from iterator.
 499  */
 500 struct lttng_ht_node_str *lttng_ht_iter_get_node_str(struct lttng_ht_iter *iter)
 501 {
 502         struct cds_lfht_node *node;
 503
 504         LTTNG_ASSERT(iter);
 505         node = cds_lfht_iter_get_node(&iter->iter);
 506         if (!node) {
 507                 return nullptr;
 508         }
 509         return lttng::utils::container_of(node, &lttng_ht_node_str::node);
 510 }
 511
 512 /*
 513  * Return lttng ht unsigned long node from iterator.
 514  */
 515 struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong(struct lttng_ht_iter *iter)
 516 {
 517         struct cds_lfht_node *node;
 518
 519         LTTNG_ASSERT(iter);
 520         node = cds_lfht_iter_get_node(&iter->iter);
 521         if (!node) {
 522                 return nullptr;
 523         }
 524         return lttng::utils::container_of(node, &lttng_ht_node_ulong::node);
 525 }
 526
 527 /*
 528  * Return lttng ht unsigned long node from iterator.
 529  */
 530 struct lttng_ht_node_u64 *lttng_ht_iter_get_node_u64(struct lttng_ht_iter *iter)
 531 {
 532         struct cds_lfht_node *node;
 533
 534         LTTNG_ASSERT(iter);
 535         node = cds_lfht_iter_get_node(&iter->iter);
 536         if (!node) {
 537                 return nullptr;
 538         }
 539         return lttng::utils::container_of(node, &lttng_ht_node_u64::node);
 540 }
 541
 542 /*
 543  * Return lttng ht stream and index id node from iterator.
 544  */
 545 struct lttng_ht_node_two_u64 *lttng_ht_iter_get_node_two_u64(struct lttng_ht_iter *iter)
 546 {
 547         struct cds_lfht_node *node;
 548
 549         LTTNG_ASSERT(iter);
 550         node = cds_lfht_iter_get_node(&iter->iter);
 551         if (!node) {
 552                 return nullptr;
 553         }
 554         return lttng::utils::container_of(node, &lttng_ht_node_two_u64::node);
 555 }