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 static inline
  80 const 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
  97 /*
  98  * Return an allocated lttng hashtable.
  99  */
 100 LTTNG_HIDDEN
 101 struct lttng_ht *lttng_ht_new(unsigned long size, int type)
 102 {
 103         struct lttng_ht *ht;
 104
 105         /* Test size */
 106         if (!size)
 107                 size = DEFAULT_HT_SIZE;
 108
 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
 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,
 123                         CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, NULL);
 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;
 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,
 154                         lttng_ht_type_str(type));
 155
 156         return ht;
 157
 158 error:
 159         return NULL;
 160 }
 161
 162 /*
 163  * Free a lttng hashtable.
 164  */
 165 LTTNG_HIDDEN
 166 void lttng_ht_destroy(struct lttng_ht *ht)
 167 {
 168         int ret;
 169
 170         ret = cds_lfht_destroy(ht->ht, NULL);
 171         assert(!ret);
 172         free(ht);
 173 }
 174
 175 /*
 176  * Init lttng ht node string.
 177  */
 178 LTTNG_HIDDEN
 179 void 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  */
 190 LTTNG_HIDDEN
 191 void 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
 200 /*
 201  * Init lttng ht node uint64_t.
 202  */
 203 LTTNG_HIDDEN
 204 void 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
 213 /*
 214  * Init lttng ht node with two uint64_t.
 215  */
 216 LTTNG_HIDDEN
 217 void 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
 227 /*
 228  * Free lttng ht node string.
 229  */
 230 LTTNG_HIDDEN
 231 void 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  */
 240 LTTNG_HIDDEN
 241 void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node)
 242 {
 243         assert(node);
 244         free(node);
 245 }
 246
 247 /*
 248  * Free lttng ht node uint64_t.
 249  */
 250 LTTNG_HIDDEN
 251 void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node)
 252 {
 253         assert(node);
 254         free(node);
 255 }
 256
 257 /*
 258  * Free lttng ht node two uint64_t.
 259  */
 260 LTTNG_HIDDEN
 261 void lttng_ht_node_free_two_u64(struct lttng_ht_node_two_u64 *node)
 262 {
 263         assert(node);
 264         free(node);
 265 }
 266
 267 /*
 268  * Lookup function in hashtable.
 269  */
 270 LTTNG_HIDDEN
 271 void lttng_ht_lookup(struct lttng_ht *ht, const void *key,
 272                 struct lttng_ht_iter *iter)
 273 {
 274         assert(ht);
 275         assert(ht->ht);
 276
 277         cds_lfht_lookup(ht->ht, ht->hash_fct(key, lttng_ht_seed),
 278                         ht->match_fct, key, &iter->iter);
 279 }
 280
 281 /*
 282  * Add unique string node to hashtable.
 283  */
 284 LTTNG_HIDDEN
 285 void 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
 293         /* RCU read lock protects from ABA. */
 294         rcu_read_lock();
 295         node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
 296                         ht->match_fct, node->key, &node->node);
 297         rcu_read_unlock();
 298         assert(node_ptr == &node->node);
 299 }
 300
 301 /*
 302  * Add string node to hashtable.
 303  */
 304 LTTNG_HIDDEN
 305 void 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
 312         /* RCU read lock protects from ABA. */
 313         rcu_read_lock();
 314         cds_lfht_add(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
 315                         &node->node);
 316         rcu_read_unlock();
 317 }
 318
 319 /*
 320  * Add unsigned long node to hashtable.
 321  */
 322 LTTNG_HIDDEN
 323 void 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
 329         /* RCU read lock protects from ABA. */
 330         rcu_read_lock();
 331         cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed),
 332                         &node->node);
 333         rcu_read_unlock();
 334 }
 335
 336 /*
 337  * Add uint64_t node to hashtable.
 338  */
 339 LTTNG_HIDDEN
 340 void 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
 346         /* RCU read lock protects from ABA. */
 347         rcu_read_lock();
 348         cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed),
 349                         &node->node);
 350         rcu_read_unlock();
 351 }
 352
 353 /*
 354  * Add unique unsigned long node to hashtable.
 355  */
 356 LTTNG_HIDDEN
 357 void 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
 365         /* RCU read lock protects from ABA. */
 366         rcu_read_lock();
 367         node_ptr = cds_lfht_add_unique(ht->ht,
 368                         ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
 369                         (void *) node->key, &node->node);
 370         rcu_read_unlock();
 371         assert(node_ptr == &node->node);
 372 }
 373
 374 /*
 375  * Add unique uint64_t node to hashtable.
 376  */
 377 LTTNG_HIDDEN
 378 void 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
 386         /* RCU read lock protects from ABA. */
 387         rcu_read_lock();
 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);
 391         rcu_read_unlock();
 392         assert(node_ptr == &node->node);
 393 }
 394
 395 /*
 396  * Add unique two uint64_t node to hashtable.
 397  */
 398 LTTNG_HIDDEN
 399 void 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
 407         /* RCU read lock protects from ABA. */
 408         rcu_read_lock();
 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);
 412         rcu_read_unlock();
 413         assert(node_ptr == &node->node);
 414 }
 415
 416 /*
 417  * Add replace unsigned long node to hashtable.
 418  */
 419 LTTNG_HIDDEN
 420 struct 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
 428         /* RCU read lock protects from ABA. */
 429         rcu_read_lock();
 430         node_ptr = cds_lfht_add_replace(ht->ht,
 431                         ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
 432                         (void *) node->key, &node->node);
 433         rcu_read_unlock();
 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
 442 /*
 443  * Add replace unsigned long node to hashtable.
 444  */
 445 LTTNG_HIDDEN
 446 struct 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
 454         /* RCU read lock protects from ABA. */
 455         rcu_read_lock();
 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);
 459         rcu_read_unlock();
 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
 468 /*
 469  * Delete node from hashtable.
 470  */
 471 LTTNG_HIDDEN
 472 int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 473 {
 474         int ret;
 475
 476         assert(ht);
 477         assert(ht->ht);
 478         assert(iter);
 479
 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;
 485 }
 486
 487 /*
 488  * Get first node in the hashtable.
 489  */
 490 LTTNG_HIDDEN
 491 void 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  */
 503 LTTNG_HIDDEN
 504 void 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  */
 516 LTTNG_HIDDEN
 517 unsigned 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
 525         /* RCU read lock protects from ABA and allows RCU traversal. */
 526         rcu_read_lock();
 527         cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
 528         rcu_read_unlock();
 529
 530         return count;
 531 }
 532
 533 /*
 534  * Return lttng ht string node from iterator.
 535  */
 536 LTTNG_HIDDEN
 537 struct 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  */
 553 LTTNG_HIDDEN
 554 struct 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 }
 566
 567 /*
 568  * Return lttng ht unsigned long node from iterator.
 569  */
 570 LTTNG_HIDDEN
 571 struct 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
 584 /*
 585  * Return lttng ht stream and index id node from iterator.
 586  */
 587 LTTNG_HIDDEN
 588 struct 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 }