src/common/hashtable/hashtable.c

   1 /*
   2  * Copyright (C) 2011 David Goulet <david.goulet@polymtl.ca>
   3  *
   4  * SPDX-License-Identifier: GPL-2.0-only
   5  *
   6  */
   7
   8 #define _LGPL_SOURCE
   9 #include <assert.h>
  10 #include <string.h>
  11 #include <urcu.h>
  12 #include <urcu/compiler.h>
  13
  14 #include <common/common.h>
  15 #include <common/defaults.h>
  16
  17 #include "hashtable.h"
  18 #include "utils.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 unsigned long lttng_ht_seed;
  24
  25 static unsigned long min_hash_alloc_size = 1;
  26 static unsigned long max_hash_buckets_size = 0;
  27
  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
  35 /*
  36  * Match function for string node.
  37  */
  38 static 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  */
  49 static 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
  57 /*
  58  * Match function for u64 node.
  59  */
  60 static 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
  68 /*
  69  * Match function for two uint64_t node.
  70  */
  71 static 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
  79 /*
  80  * Return an allocated lttng hashtable.
  81  */
  82 LTTNG_HIDDEN
  83 struct lttng_ht *lttng_ht_new(unsigned long size, int type)
  84 {
  85         struct lttng_ht *ht;
  86
  87         /* Test size */
  88         if (!size)
  89                 size = DEFAULT_HT_SIZE;
  90
  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
  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,
 105                         CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, NULL);
 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;
 121         case LTTNG_HT_TYPE_U64:
 122                 ht->match_fct = match_u64;
 123                 ht->hash_fct = hash_key_u64;
 124                 break;
 125         case LTTNG_HT_TYPE_TWO_U64:
 126                 ht->match_fct = match_two_u64;
 127                 ht->hash_fct = hash_key_two_u64;
 128                 break;
 129         default:
 130                 ERR("Unknown lttng hashtable type %d", type);
 131                 lttng_ht_destroy(ht);
 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 LTTNG_HIDDEN
 147 void lttng_ht_destroy(struct lttng_ht *ht)
 148 {
 149         int ret;
 150
 151         ret = cds_lfht_destroy(ht->ht, NULL);
 152         assert(!ret);
 153         free(ht);
 154 }
 155
 156 /*
 157  * Init lttng ht node string.
 158  */
 159 LTTNG_HIDDEN
 160 void 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  */
 171 LTTNG_HIDDEN
 172 void 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
 181 /*
 182  * Init lttng ht node uint64_t.
 183  */
 184 LTTNG_HIDDEN
 185 void 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
 194 /*
 195  * Init lttng ht node with two uint64_t.
 196  */
 197 LTTNG_HIDDEN
 198 void 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
 208 /*
 209  * Free lttng ht node string.
 210  */
 211 LTTNG_HIDDEN
 212 void 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  */
 221 LTTNG_HIDDEN
 222 void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node)
 223 {
 224         assert(node);
 225         free(node);
 226 }
 227
 228 /*
 229  * Free lttng ht node uint64_t.
 230  */
 231 LTTNG_HIDDEN
 232 void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node)
 233 {
 234         assert(node);
 235         free(node);
 236 }
 237
 238 /*
 239  * Free lttng ht node two uint64_t.
 240  */
 241 LTTNG_HIDDEN
 242 void lttng_ht_node_free_two_u64(struct lttng_ht_node_two_u64 *node)
 243 {
 244         assert(node);
 245         free(node);
 246 }
 247
 248 /*
 249  * Lookup function in hashtable.
 250  */
 251 LTTNG_HIDDEN
 252 void lttng_ht_lookup(struct lttng_ht *ht, const void *key,
 253                 struct lttng_ht_iter *iter)
 254 {
 255         assert(ht);
 256         assert(ht->ht);
 257
 258         cds_lfht_lookup(ht->ht, ht->hash_fct(key, lttng_ht_seed),
 259                         ht->match_fct, key, &iter->iter);
 260 }
 261
 262 /*
 263  * Add unique string node to hashtable.
 264  */
 265 LTTNG_HIDDEN
 266 void 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
 274         /* RCU read lock protects from ABA. */
 275         rcu_read_lock();
 276         node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
 277                         ht->match_fct, node->key, &node->node);
 278         rcu_read_unlock();
 279         assert(node_ptr == &node->node);
 280 }
 281
 282 /*
 283  * Add string node to hashtable.
 284  */
 285 LTTNG_HIDDEN
 286 void 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
 293         /* RCU read lock protects from ABA. */
 294         rcu_read_lock();
 295         cds_lfht_add(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
 296                         &node->node);
 297         rcu_read_unlock();
 298 }
 299
 300 /*
 301  * Add unsigned long node to hashtable.
 302  */
 303 LTTNG_HIDDEN
 304 void 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
 310         /* RCU read lock protects from ABA. */
 311         rcu_read_lock();
 312         cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed),
 313                         &node->node);
 314         rcu_read_unlock();
 315 }
 316
 317 /*
 318  * Add uint64_t node to hashtable.
 319  */
 320 LTTNG_HIDDEN
 321 void 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
 327         /* RCU read lock protects from ABA. */
 328         rcu_read_lock();
 329         cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed),
 330                         &node->node);
 331         rcu_read_unlock();
 332 }
 333
 334 /*
 335  * Add unique unsigned long node to hashtable.
 336  */
 337 LTTNG_HIDDEN
 338 void 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
 346         /* RCU read lock protects from ABA. */
 347         rcu_read_lock();
 348         node_ptr = cds_lfht_add_unique(ht->ht,
 349                         ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
 350                         (void *) node->key, &node->node);
 351         rcu_read_unlock();
 352         assert(node_ptr == &node->node);
 353 }
 354
 355 /*
 356  * Add unique uint64_t node to hashtable.
 357  */
 358 LTTNG_HIDDEN
 359 void 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
 367         /* RCU read lock protects from ABA. */
 368         rcu_read_lock();
 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);
 372         rcu_read_unlock();
 373         assert(node_ptr == &node->node);
 374 }
 375
 376 /*
 377  * Add unique two uint64_t node to hashtable.
 378  */
 379 LTTNG_HIDDEN
 380 void 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
 388         /* RCU read lock protects from ABA. */
 389         rcu_read_lock();
 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);
 393         rcu_read_unlock();
 394         assert(node_ptr == &node->node);
 395 }
 396
 397 /*
 398  * Add replace unsigned long node to hashtable.
 399  */
 400 LTTNG_HIDDEN
 401 struct 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
 409         /* RCU read lock protects from ABA. */
 410         rcu_read_lock();
 411         node_ptr = cds_lfht_add_replace(ht->ht,
 412                         ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
 413                         (void *) node->key, &node->node);
 414         rcu_read_unlock();
 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
 423 /*
 424  * Add replace unsigned long node to hashtable.
 425  */
 426 LTTNG_HIDDEN
 427 struct 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
 435         /* RCU read lock protects from ABA. */
 436         rcu_read_lock();
 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);
 440         rcu_read_unlock();
 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
 449 /*
 450  * Delete node from hashtable.
 451  */
 452 LTTNG_HIDDEN
 453 int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 454 {
 455         int ret;
 456
 457         assert(ht);
 458         assert(ht->ht);
 459         assert(iter);
 460
 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;
 466 }
 467
 468 /*
 469  * Get first node in the hashtable.
 470  */
 471 LTTNG_HIDDEN
 472 void 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  */
 484 LTTNG_HIDDEN
 485 void 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  */
 497 LTTNG_HIDDEN
 498 unsigned 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
 506         /* RCU read lock protects from ABA and allows RCU traversal. */
 507         rcu_read_lock();
 508         cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
 509         rcu_read_unlock();
 510
 511         return count;
 512 }
 513
 514 /*
 515  * Return lttng ht string node from iterator.
 516  */
 517 LTTNG_HIDDEN
 518 struct 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  */
 534 LTTNG_HIDDEN
 535 struct 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 }
 547
 548 /*
 549  * Return lttng ht unsigned long node from iterator.
 550  */
 551 LTTNG_HIDDEN
 552 struct 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
 565 /*
 566  * Return lttng ht stream and index id node from iterator.
 567  */
 568 LTTNG_HIDDEN
 569 struct 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 }