src/common/hashtable/hashtable.cpp

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