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