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 <string.h>
  10 #include <urcu.h>
  11 #include <urcu/compiler.h>
  12
  13 #include <common/common.h>
  14 #include <common/defaults.h>
  15
  16 #include "hashtable.h"
  17 #include "utils.h"
  18
  19 /* seed_lock protects both seed_init and lttng_ht_seed. */
  20 static pthread_mutex_t seed_lock = PTHREAD_MUTEX_INITIALIZER;
  21 static bool seed_init;
  22 unsigned long lttng_ht_seed;
  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                 caa_container_of(node, struct 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                 caa_container_of(node, struct 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                 caa_container_of(node, struct 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                 caa_container_of(node, struct 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
  79 const char *lttng_ht_type_str(enum lttng_ht_type type)
  80 {
  81         switch (type) {
  82         case LTTNG_HT_TYPE_STRING:
  83                 return "STRING";
  84         case LTTNG_HT_TYPE_ULONG:
  85                 return "ULONG";
  86         case LTTNG_HT_TYPE_U64:
  87                 return "U64";
  88         case LTTNG_HT_TYPE_TWO_U64:
  89                 return "TWO_U64";
  90         default:
  91                 ERR("Unknown lttng hashtable type %d", type);
  92                 abort();
  93         }
  94 }
  95
  96 /*
  97  * Return an allocated lttng hashtable.
  98  */
  99 LTTNG_HIDDEN
 100 struct lttng_ht *lttng_ht_new(unsigned long size, int type)
 101 {
 102         struct lttng_ht *ht;
 103
 104         /* Test size */
 105         if (!size)
 106                 size = DEFAULT_HT_SIZE;
 107
 108         pthread_mutex_lock(&seed_lock);
 109         if (!seed_init) {
 110                 lttng_ht_seed = (unsigned long) time(NULL);
 111                 seed_init = true;
 112         }
 113         pthread_mutex_unlock(&seed_lock);
 114
 115         ht = zmalloc(sizeof(*ht));
 116         if (ht == NULL) {
 117                 PERROR("zmalloc lttng_ht");
 118                 goto error;
 119         }
 120
 121         ht->ht = cds_lfht_new(size, min_hash_alloc_size, max_hash_buckets_size,
 122                         CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, NULL);
 123         /*
 124          * There is already an assert in the RCU hashtable code so if the ht is
 125          * NULL here there is a *huge* problem.
 126          */
 127         LTTNG_ASSERT(ht->ht);
 128
 129         switch (type) {
 130         case LTTNG_HT_TYPE_STRING:
 131                 ht->match_fct = match_str;
 132                 ht->hash_fct = hash_key_str;
 133                 break;
 134         case LTTNG_HT_TYPE_ULONG:
 135                 ht->match_fct = match_ulong;
 136                 ht->hash_fct = hash_key_ulong;
 137                 break;
 138         case LTTNG_HT_TYPE_U64:
 139                 ht->match_fct = match_u64;
 140                 ht->hash_fct = hash_key_u64;
 141                 break;
 142         case LTTNG_HT_TYPE_TWO_U64:
 143                 ht->match_fct = match_two_u64;
 144                 ht->hash_fct = hash_key_two_u64;
 145                 break;
 146         default:
 147                 ERR("Unknown lttng hashtable type %d", type);
 148                 lttng_ht_destroy(ht);
 149                 goto error;
 150         }
 151
 152         DBG3("Created hashtable size %lu at %p of type %s", size, ht->ht,
 153                         lttng_ht_type_str(type));
 154
 155         return ht;
 156
 157 error:
 158         return NULL;
 159 }
 160
 161 /*
 162  * Free a lttng hashtable.
 163  */
 164 LTTNG_HIDDEN
 165 void lttng_ht_destroy(struct lttng_ht *ht)
 166 {
 167         int ret;
 168
 169         ret = cds_lfht_destroy(ht->ht, NULL);
 170         LTTNG_ASSERT(!ret);
 171         free(ht);
 172 }
 173
 174 /*
 175  * Init lttng ht node string.
 176  */
 177 LTTNG_HIDDEN
 178 void lttng_ht_node_init_str(struct lttng_ht_node_str *node, char *key)
 179 {
 180         LTTNG_ASSERT(node);
 181
 182         node->key = key;
 183         cds_lfht_node_init(&node->node);
 184 }
 185
 186 /*
 187  * Init lttng ht node unsigned long.
 188  */
 189 LTTNG_HIDDEN
 190 void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node,
 191                 unsigned long key)
 192 {
 193         LTTNG_ASSERT(node);
 194
 195         node->key = key;
 196         cds_lfht_node_init(&node->node);
 197 }
 198
 199 /*
 200  * Init lttng ht node uint64_t.
 201  */
 202 LTTNG_HIDDEN
 203 void lttng_ht_node_init_u64(struct lttng_ht_node_u64 *node,
 204                 uint64_t key)
 205 {
 206         LTTNG_ASSERT(node);
 207
 208         node->key = key;
 209         cds_lfht_node_init(&node->node);
 210 }
 211
 212 /*
 213  * Init lttng ht node with two uint64_t.
 214  */
 215 LTTNG_HIDDEN
 216 void lttng_ht_node_init_two_u64(struct lttng_ht_node_two_u64 *node,
 217                 uint64_t key1, uint64_t key2)
 218 {
 219         LTTNG_ASSERT(node);
 220
 221         node->key.key1 = key1;
 222         node->key.key2 = key2;
 223         cds_lfht_node_init(&node->node);
 224 }
 225
 226 /*
 227  * Free lttng ht node string.
 228  */
 229 LTTNG_HIDDEN
 230 void lttng_ht_node_free_str(struct lttng_ht_node_str *node)
 231 {
 232         LTTNG_ASSERT(node);
 233         free(node);
 234 }
 235
 236 /*
 237  * Free lttng ht node unsigned long.
 238  */
 239 LTTNG_HIDDEN
 240 void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node)
 241 {
 242         LTTNG_ASSERT(node);
 243         free(node);
 244 }
 245
 246 /*
 247  * Free lttng ht node uint64_t.
 248  */
 249 LTTNG_HIDDEN
 250 void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node)
 251 {
 252         LTTNG_ASSERT(node);
 253         free(node);
 254 }
 255
 256 /*
 257  * Free lttng ht node two uint64_t.
 258  */
 259 LTTNG_HIDDEN
 260 void lttng_ht_node_free_two_u64(struct lttng_ht_node_two_u64 *node)
 261 {
 262         LTTNG_ASSERT(node);
 263         free(node);
 264 }
 265
 266 /*
 267  * Lookup function in hashtable.
 268  */
 269 LTTNG_HIDDEN
 270 void lttng_ht_lookup(struct lttng_ht *ht, const void *key,
 271                 struct lttng_ht_iter *iter)
 272 {
 273         LTTNG_ASSERT(ht);
 274         LTTNG_ASSERT(ht->ht);
 275
 276         cds_lfht_lookup(ht->ht, ht->hash_fct(key, lttng_ht_seed),
 277                         ht->match_fct, key, &iter->iter);
 278 }
 279
 280 /*
 281  * Add unique string node to hashtable.
 282  */
 283 LTTNG_HIDDEN
 284 void lttng_ht_add_unique_str(struct lttng_ht *ht,
 285                 struct lttng_ht_node_str *node)
 286 {
 287         struct cds_lfht_node *node_ptr;
 288         LTTNG_ASSERT(ht);
 289         LTTNG_ASSERT(ht->ht);
 290         LTTNG_ASSERT(node);
 291
 292         /* RCU read lock protects from ABA. */
 293         rcu_read_lock();
 294         node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
 295                         ht->match_fct, node->key, &node->node);
 296         rcu_read_unlock();
 297         LTTNG_ASSERT(node_ptr == &node->node);
 298 }
 299
 300 /*
 301  * Add string node to hashtable.
 302  */
 303 LTTNG_HIDDEN
 304 void lttng_ht_add_str(struct lttng_ht *ht,
 305                 struct lttng_ht_node_str *node)
 306 {
 307         LTTNG_ASSERT(ht);
 308         LTTNG_ASSERT(ht->ht);
 309         LTTNG_ASSERT(node);
 310
 311         /* RCU read lock protects from ABA. */
 312         rcu_read_lock();
 313         cds_lfht_add(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
 314                         &node->node);
 315         rcu_read_unlock();
 316 }
 317
 318 /*
 319  * Add unsigned long node to hashtable.
 320  */
 321 LTTNG_HIDDEN
 322 void lttng_ht_add_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node)
 323 {
 324         LTTNG_ASSERT(ht);
 325         LTTNG_ASSERT(ht->ht);
 326         LTTNG_ASSERT(node);
 327
 328         /* RCU read lock protects from ABA. */
 329         rcu_read_lock();
 330         cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed),
 331                         &node->node);
 332         rcu_read_unlock();
 333 }
 334
 335 /*
 336  * Add uint64_t node to hashtable.
 337  */
 338 LTTNG_HIDDEN
 339 void lttng_ht_add_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node)
 340 {
 341         LTTNG_ASSERT(ht);
 342         LTTNG_ASSERT(ht->ht);
 343         LTTNG_ASSERT(node);
 344
 345         /* RCU read lock protects from ABA. */
 346         rcu_read_lock();
 347         cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed),
 348                         &node->node);
 349         rcu_read_unlock();
 350 }
 351
 352 /*
 353  * Add unique unsigned long node to hashtable.
 354  */
 355 LTTNG_HIDDEN
 356 void lttng_ht_add_unique_ulong(struct lttng_ht *ht,
 357                 struct lttng_ht_node_ulong *node)
 358 {
 359         struct cds_lfht_node *node_ptr;
 360         LTTNG_ASSERT(ht);
 361         LTTNG_ASSERT(ht->ht);
 362         LTTNG_ASSERT(node);
 363
 364         /* RCU read lock protects from ABA. */
 365         rcu_read_lock();
 366         node_ptr = cds_lfht_add_unique(ht->ht,
 367                         ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
 368                         (void *) node->key, &node->node);
 369         rcu_read_unlock();
 370         LTTNG_ASSERT(node_ptr == &node->node);
 371 }
 372
 373 /*
 374  * Add unique uint64_t node to hashtable.
 375  */
 376 LTTNG_HIDDEN
 377 void lttng_ht_add_unique_u64(struct lttng_ht *ht,
 378                 struct lttng_ht_node_u64 *node)
 379 {
 380         struct cds_lfht_node *node_ptr;
 381         LTTNG_ASSERT(ht);
 382         LTTNG_ASSERT(ht->ht);
 383         LTTNG_ASSERT(node);
 384
 385         /* RCU read lock protects from ABA. */
 386         rcu_read_lock();
 387         node_ptr = cds_lfht_add_unique(ht->ht,
 388                         ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct,
 389                         &node->key, &node->node);
 390         rcu_read_unlock();
 391         LTTNG_ASSERT(node_ptr == &node->node);
 392 }
 393
 394 /*
 395  * Add unique two uint64_t node to hashtable.
 396  */
 397 LTTNG_HIDDEN
 398 void lttng_ht_add_unique_two_u64(struct lttng_ht *ht,
 399                 struct lttng_ht_node_two_u64 *node)
 400 {
 401         struct cds_lfht_node *node_ptr;
 402         LTTNG_ASSERT(ht);
 403         LTTNG_ASSERT(ht->ht);
 404         LTTNG_ASSERT(node);
 405
 406         /* RCU read lock protects from ABA. */
 407         rcu_read_lock();
 408         node_ptr = cds_lfht_add_unique(ht->ht,
 409                         ht->hash_fct((void *) &node->key, lttng_ht_seed), ht->match_fct,
 410                         (void *) &node->key, &node->node);
 411         rcu_read_unlock();
 412         LTTNG_ASSERT(node_ptr == &node->node);
 413 }
 414
 415 /*
 416  * Add replace unsigned long node to hashtable.
 417  */
 418 LTTNG_HIDDEN
 419 struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(struct lttng_ht *ht,
 420                 struct lttng_ht_node_ulong *node)
 421 {
 422         struct cds_lfht_node *node_ptr;
 423         LTTNG_ASSERT(ht);
 424         LTTNG_ASSERT(ht->ht);
 425         LTTNG_ASSERT(node);
 426
 427         /* RCU read lock protects from ABA. */
 428         rcu_read_lock();
 429         node_ptr = cds_lfht_add_replace(ht->ht,
 430                         ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
 431                         (void *) node->key, &node->node);
 432         rcu_read_unlock();
 433         if (!node_ptr) {
 434                 return NULL;
 435         } else {
 436                 return caa_container_of(node_ptr, struct lttng_ht_node_ulong, node);
 437         }
 438         LTTNG_ASSERT(node_ptr == &node->node);
 439 }
 440
 441 /*
 442  * Add replace unsigned long node to hashtable.
 443  */
 444 LTTNG_HIDDEN
 445 struct lttng_ht_node_u64 *lttng_ht_add_replace_u64(struct lttng_ht *ht,
 446                 struct lttng_ht_node_u64 *node)
 447 {
 448         struct cds_lfht_node *node_ptr;
 449         LTTNG_ASSERT(ht);
 450         LTTNG_ASSERT(ht->ht);
 451         LTTNG_ASSERT(node);
 452
 453         /* RCU read lock protects from ABA. */
 454         rcu_read_lock();
 455         node_ptr = cds_lfht_add_replace(ht->ht,
 456                         ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct,
 457                         &node->key, &node->node);
 458         rcu_read_unlock();
 459         if (!node_ptr) {
 460                 return NULL;
 461         } else {
 462                 return caa_container_of(node_ptr, struct lttng_ht_node_u64, node);
 463         }
 464         LTTNG_ASSERT(node_ptr == &node->node);
 465 }
 466
 467 /*
 468  * Delete node from hashtable.
 469  */
 470 LTTNG_HIDDEN
 471 int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 472 {
 473         int ret;
 474
 475         LTTNG_ASSERT(ht);
 476         LTTNG_ASSERT(ht->ht);
 477         LTTNG_ASSERT(iter);
 478
 479         /* RCU read lock protects from ABA. */
 480         rcu_read_lock();
 481         ret = cds_lfht_del(ht->ht, iter->iter.node);
 482         rcu_read_unlock();
 483         return ret;
 484 }
 485
 486 /*
 487  * Get first node in the hashtable.
 488  */
 489 LTTNG_HIDDEN
 490 void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 491 {
 492         LTTNG_ASSERT(ht);
 493         LTTNG_ASSERT(ht->ht);
 494         LTTNG_ASSERT(iter);
 495
 496         cds_lfht_first(ht->ht, &iter->iter);
 497 }
 498
 499 /*
 500  * Get next node in the hashtable.
 501  */
 502 LTTNG_HIDDEN
 503 void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 504 {
 505         LTTNG_ASSERT(ht);
 506         LTTNG_ASSERT(ht->ht);
 507         LTTNG_ASSERT(iter);
 508
 509         cds_lfht_next(ht->ht, &iter->iter);
 510 }
 511
 512 /*
 513  * Return the number of nodes in the hashtable.
 514  */
 515 LTTNG_HIDDEN
 516 unsigned long lttng_ht_get_count(struct lttng_ht *ht)
 517 {
 518         long scb, sca;
 519         unsigned long count;
 520
 521         LTTNG_ASSERT(ht);
 522         LTTNG_ASSERT(ht->ht);
 523
 524         /* RCU read lock protects from ABA and allows RCU traversal. */
 525         rcu_read_lock();
 526         cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
 527         rcu_read_unlock();
 528
 529         return count;
 530 }
 531
 532 /*
 533  * Return lttng ht string node from iterator.
 534  */
 535 LTTNG_HIDDEN
 536 struct lttng_ht_node_str *lttng_ht_iter_get_node_str(
 537                 struct lttng_ht_iter *iter)
 538 {
 539         struct cds_lfht_node *node;
 540
 541         LTTNG_ASSERT(iter);
 542         node = cds_lfht_iter_get_node(&iter->iter);
 543         if (!node) {
 544                 return NULL;
 545         }
 546         return caa_container_of(node, struct lttng_ht_node_str, node);
 547 }
 548
 549 /*
 550  * Return lttng ht unsigned long node from iterator.
 551  */
 552 LTTNG_HIDDEN
 553 struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong(
 554                 struct lttng_ht_iter *iter)
 555 {
 556         struct cds_lfht_node *node;
 557
 558         LTTNG_ASSERT(iter);
 559         node = cds_lfht_iter_get_node(&iter->iter);
 560         if (!node) {
 561                 return NULL;
 562         }
 563         return caa_container_of(node, struct lttng_ht_node_ulong, node);
 564 }
 565
 566 /*
 567  * Return lttng ht unsigned long node from iterator.
 568  */
 569 LTTNG_HIDDEN
 570 struct lttng_ht_node_u64 *lttng_ht_iter_get_node_u64(
 571                 struct lttng_ht_iter *iter)
 572 {
 573         struct cds_lfht_node *node;
 574
 575         LTTNG_ASSERT(iter);
 576         node = cds_lfht_iter_get_node(&iter->iter);
 577         if (!node) {
 578                 return NULL;
 579         }
 580         return caa_container_of(node, struct lttng_ht_node_u64, node);
 581 }
 582
 583 /*
 584  * Return lttng ht stream and index id node from iterator.
 585  */
 586 LTTNG_HIDDEN
 587 struct lttng_ht_node_two_u64 *lttng_ht_iter_get_node_two_u64(
 588                 struct lttng_ht_iter *iter)
 589 {
 590         struct cds_lfht_node *node;
 591
 592         LTTNG_ASSERT(iter);
 593         node = cds_lfht_iter_get_node(&iter->iter);
 594         if (!node) {
 595                 return NULL;
 596         }
 597         return caa_container_of(node, struct lttng_ht_node_two_u64, node);
 598 }