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