src/common/hashtable/hashtable.c

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