src/common/hashtable/hashtable.c

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