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 #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 unsigned long lttng_ht_seed;
  31
  32 static unsigned long min_hash_alloc_size = 1;
  33 static unsigned long max_hash_buckets_size = 0;
  34
  35 /*
  36  * Getter/lookup functions need to be called with RCU read-side lock
  37  * held. However, modification functions (add, add_unique, replace, del)
  38  * take the RCU lock internally, so it does not matter whether the
  39  * caller hold the RCU lock or not.
  40  */
  41
  42 /*
  43  * Match function for string node.
  44  */
  45 static int match_str(struct cds_lfht_node *node, const void *key)
  46 {
  47         struct lttng_ht_node_str *match_node =
  48                 caa_container_of(node, struct lttng_ht_node_str, node);
  49
  50         return hash_match_key_str(match_node->key, (void *) key);
  51 }
  52
  53 /*
  54  * Match function for ulong node.
  55  */
  56 static int match_ulong(struct cds_lfht_node *node, const void *key)
  57 {
  58         struct lttng_ht_node_ulong *match_node =
  59                 caa_container_of(node, struct lttng_ht_node_ulong, node);
  60
  61         return hash_match_key_ulong((void *) match_node->key, (void *) key);
  62 }
  63
  64 /*
  65  * Match function for u64 node.
  66  */
  67 static int match_u64(struct cds_lfht_node *node, const void *key)
  68 {
  69         struct lttng_ht_node_u64 *match_node =
  70                 caa_container_of(node, struct lttng_ht_node_u64, node);
  71
  72         return hash_match_key_u64(&match_node->key, (void *) key);
  73 }
  74
  75 /*
  76  * Match function for two uint64_t node.
  77  */
  78 static int match_two_u64(struct cds_lfht_node *node, const void *key)
  79 {
  80         struct lttng_ht_node_two_u64 *match_node =
  81                 caa_container_of(node, struct lttng_ht_node_two_u64, node);
  82
  83         return hash_match_key_two_u64((void *) &match_node->key, (void *) key);
  84 }
  85
  86 /*
  87  * Return an allocated lttng hashtable.
  88  */
  89 struct lttng_ht *lttng_ht_new(unsigned long size, int type)
  90 {
  91         struct lttng_ht *ht;
  92
  93         /* Test size */
  94         if (!size)
  95                 size = DEFAULT_HT_SIZE;
  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 void lttng_ht_destroy(struct lttng_ht *ht)
 146 {
 147         int ret;
 148
 149         ret = cds_lfht_destroy(ht->ht, NULL);
 150         assert(!ret);
 151         free(ht);
 152 }
 153
 154 /*
 155  * Init lttng ht node string.
 156  */
 157 void lttng_ht_node_init_str(struct lttng_ht_node_str *node, char *key)
 158 {
 159         assert(node);
 160
 161         node->key = key;
 162         cds_lfht_node_init(&node->node);
 163 }
 164
 165 /*
 166  * Init lttng ht node unsigned long.
 167  */
 168 void lttng_ht_node_init_ulong(struct lttng_ht_node_ulong *node,
 169                 unsigned long key)
 170 {
 171         assert(node);
 172
 173         node->key = key;
 174         cds_lfht_node_init(&node->node);
 175 }
 176
 177 /*
 178  * Init lttng ht node uint64_t.
 179  */
 180 void lttng_ht_node_init_u64(struct lttng_ht_node_u64 *node,
 181                 uint64_t key)
 182 {
 183         assert(node);
 184
 185         node->key = key;
 186         cds_lfht_node_init(&node->node);
 187 }
 188
 189 /*
 190  * Init lttng ht node with two uint64_t.
 191  */
 192 void lttng_ht_node_init_two_u64(struct lttng_ht_node_two_u64 *node,
 193                 uint64_t key1, uint64_t key2)
 194 {
 195         assert(node);
 196
 197         node->key.key1 = key1;
 198         node->key.key2 = key2;
 199         cds_lfht_node_init(&node->node);
 200 }
 201
 202 /*
 203  * Free lttng ht node string.
 204  */
 205 void lttng_ht_node_free_str(struct lttng_ht_node_str *node)
 206 {
 207         assert(node);
 208         free(node);
 209 }
 210
 211 /*
 212  * Free lttng ht node unsigned long.
 213  */
 214 void lttng_ht_node_free_ulong(struct lttng_ht_node_ulong *node)
 215 {
 216         assert(node);
 217         free(node);
 218 }
 219
 220 /*
 221  * Free lttng ht node uint64_t.
 222  */
 223 void lttng_ht_node_free_u64(struct lttng_ht_node_u64 *node)
 224 {
 225         assert(node);
 226         free(node);
 227 }
 228
 229 /*
 230  * Free lttng ht node two uint64_t.
 231  */
 232 void lttng_ht_node_free_two_u64(struct lttng_ht_node_two_u64 *node)
 233 {
 234         assert(node);
 235         free(node);
 236 }
 237
 238 /*
 239  * Lookup function in hashtable.
 240  */
 241 void lttng_ht_lookup(struct lttng_ht *ht, void *key,
 242                 struct lttng_ht_iter *iter)
 243 {
 244         assert(ht);
 245         assert(ht->ht);
 246
 247         cds_lfht_lookup(ht->ht, ht->hash_fct(key, lttng_ht_seed),
 248                         ht->match_fct, key, &iter->iter);
 249 }
 250
 251 /*
 252  * Add unique string node to hashtable.
 253  */
 254 void lttng_ht_add_unique_str(struct lttng_ht *ht,
 255                 struct lttng_ht_node_str *node)
 256 {
 257         struct cds_lfht_node *node_ptr;
 258         assert(ht);
 259         assert(ht->ht);
 260         assert(node);
 261
 262         /* RCU read lock protects from ABA. */
 263         rcu_read_lock();
 264         node_ptr = cds_lfht_add_unique(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
 265                         ht->match_fct, node->key, &node->node);
 266         rcu_read_unlock();
 267         assert(node_ptr == &node->node);
 268 }
 269
 270 /*
 271  * Add string node to hashtable.
 272  */
 273 void lttng_ht_add_str(struct lttng_ht *ht,
 274                 struct lttng_ht_node_str *node)
 275 {
 276         assert(ht);
 277         assert(ht->ht);
 278         assert(node);
 279
 280         /* RCU read lock protects from ABA. */
 281         rcu_read_lock();
 282         cds_lfht_add(ht->ht, ht->hash_fct(node->key, lttng_ht_seed),
 283                         &node->node);
 284         rcu_read_unlock();
 285 }
 286
 287 /*
 288  * Add unsigned long node to hashtable.
 289  */
 290 void lttng_ht_add_ulong(struct lttng_ht *ht, struct lttng_ht_node_ulong *node)
 291 {
 292         assert(ht);
 293         assert(ht->ht);
 294         assert(node);
 295
 296         /* RCU read lock protects from ABA. */
 297         rcu_read_lock();
 298         cds_lfht_add(ht->ht, ht->hash_fct((void *) node->key, lttng_ht_seed),
 299                         &node->node);
 300         rcu_read_unlock();
 301 }
 302
 303 /*
 304  * Add uint64_t node to hashtable.
 305
 306  */
 307 void lttng_ht_add_u64(struct lttng_ht *ht, struct lttng_ht_node_u64 *node)
 308 {
 309         assert(ht);
 310         assert(ht->ht);
 311         assert(node);
 312
 313         /* RCU read lock protects from ABA. */
 314         rcu_read_lock();
 315         cds_lfht_add(ht->ht, ht->hash_fct(&node->key, lttng_ht_seed),
 316                         &node->node);
 317         rcu_read_unlock();
 318 }
 319
 320 /*
 321  * Add unique unsigned long node to hashtable.
 322  */
 323 void lttng_ht_add_unique_ulong(struct lttng_ht *ht,
 324                 struct lttng_ht_node_ulong *node)
 325 {
 326         struct cds_lfht_node *node_ptr;
 327         assert(ht);
 328         assert(ht->ht);
 329         assert(node);
 330
 331         /* RCU read lock protects from ABA. */
 332         rcu_read_lock();
 333         node_ptr = cds_lfht_add_unique(ht->ht,
 334                         ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
 335                         (void *) node->key, &node->node);
 336         rcu_read_unlock();
 337         assert(node_ptr == &node->node);
 338 }
 339
 340 /*
 341  * Add unique uint64_t node to hashtable.
 342  */
 343 void lttng_ht_add_unique_u64(struct lttng_ht *ht,
 344                 struct lttng_ht_node_u64 *node)
 345 {
 346         struct cds_lfht_node *node_ptr;
 347         assert(ht);
 348         assert(ht->ht);
 349         assert(node);
 350
 351         /* RCU read lock protects from ABA. */
 352         rcu_read_lock();
 353         node_ptr = cds_lfht_add_unique(ht->ht,
 354                         ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct,
 355                         &node->key, &node->node);
 356         rcu_read_unlock();
 357         assert(node_ptr == &node->node);
 358 }
 359
 360 /*
 361  * Add unique two uint64_t node to hashtable.
 362  */
 363 void lttng_ht_add_unique_two_u64(struct lttng_ht *ht,
 364                 struct lttng_ht_node_two_u64 *node)
 365 {
 366         struct cds_lfht_node *node_ptr;
 367         assert(ht);
 368         assert(ht->ht);
 369         assert(node);
 370
 371         /* RCU read lock protects from ABA. */
 372         rcu_read_lock();
 373         node_ptr = cds_lfht_add_unique(ht->ht,
 374                         ht->hash_fct((void *) &node->key, lttng_ht_seed), ht->match_fct,
 375                         (void *) &node->key, &node->node);
 376         rcu_read_unlock();
 377         assert(node_ptr == &node->node);
 378 }
 379
 380 /*
 381  * Add replace unsigned long node to hashtable.
 382  */
 383 struct lttng_ht_node_ulong *lttng_ht_add_replace_ulong(struct lttng_ht *ht,
 384                 struct lttng_ht_node_ulong *node)
 385 {
 386         struct cds_lfht_node *node_ptr;
 387         assert(ht);
 388         assert(ht->ht);
 389         assert(node);
 390
 391         /* RCU read lock protects from ABA. */
 392         rcu_read_lock();
 393         node_ptr = cds_lfht_add_replace(ht->ht,
 394                         ht->hash_fct((void *) node->key, lttng_ht_seed), ht->match_fct,
 395                         (void *) node->key, &node->node);
 396         rcu_read_unlock();
 397         if (!node_ptr) {
 398                 return NULL;
 399         } else {
 400                 return caa_container_of(node_ptr, struct lttng_ht_node_ulong, node);
 401         }
 402         assert(node_ptr == &node->node);
 403 }
 404
 405 /*
 406  * Add replace unsigned long node to hashtable.
 407  */
 408 struct lttng_ht_node_u64 *lttng_ht_add_replace_u64(struct lttng_ht *ht,
 409                 struct lttng_ht_node_u64 *node)
 410 {
 411         struct cds_lfht_node *node_ptr;
 412         assert(ht);
 413         assert(ht->ht);
 414         assert(node);
 415
 416         /* RCU read lock protects from ABA. */
 417         rcu_read_lock();
 418         node_ptr = cds_lfht_add_replace(ht->ht,
 419                         ht->hash_fct(&node->key, lttng_ht_seed), ht->match_fct,
 420                         &node->key, &node->node);
 421         rcu_read_unlock();
 422         if (!node_ptr) {
 423                 return NULL;
 424         } else {
 425                 return caa_container_of(node_ptr, struct lttng_ht_node_u64, node);
 426         }
 427         assert(node_ptr == &node->node);
 428 }
 429
 430 /*
 431  * Delete node from hashtable.
 432  */
 433 int lttng_ht_del(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 434 {
 435         int ret;
 436
 437         assert(ht);
 438         assert(ht->ht);
 439         assert(iter);
 440
 441         /* RCU read lock protects from ABA. */
 442         rcu_read_lock();
 443         ret = cds_lfht_del(ht->ht, iter->iter.node);
 444         rcu_read_unlock();
 445         return ret;
 446 }
 447
 448 /*
 449  * Get first node in the hashtable.
 450  */
 451 void lttng_ht_get_first(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 452 {
 453         assert(ht);
 454         assert(ht->ht);
 455         assert(iter);
 456
 457         cds_lfht_first(ht->ht, &iter->iter);
 458 }
 459
 460 /*
 461  * Get next node in the hashtable.
 462  */
 463 void lttng_ht_get_next(struct lttng_ht *ht, struct lttng_ht_iter *iter)
 464 {
 465         assert(ht);
 466         assert(ht->ht);
 467         assert(iter);
 468
 469         cds_lfht_next(ht->ht, &iter->iter);
 470 }
 471
 472 /*
 473  * Return the number of nodes in the hashtable.
 474  */
 475 unsigned long lttng_ht_get_count(struct lttng_ht *ht)
 476 {
 477         long scb, sca;
 478         unsigned long count;
 479
 480         assert(ht);
 481         assert(ht->ht);
 482
 483         /* RCU read lock protects from ABA and allows RCU traversal. */
 484         rcu_read_lock();
 485         cds_lfht_count_nodes(ht->ht, &scb, &count, &sca);
 486         rcu_read_unlock();
 487
 488         return count;
 489 }
 490
 491 /*
 492  * Return lttng ht string node from iterator.
 493  */
 494 struct lttng_ht_node_str *lttng_ht_iter_get_node_str(
 495                 struct lttng_ht_iter *iter)
 496 {
 497         struct cds_lfht_node *node;
 498
 499         assert(iter);
 500         node = cds_lfht_iter_get_node(&iter->iter);
 501         if (!node) {
 502                 return NULL;
 503         }
 504         return caa_container_of(node, struct lttng_ht_node_str, node);
 505 }
 506
 507 /*
 508  * Return lttng ht unsigned long node from iterator.
 509  */
 510 struct lttng_ht_node_ulong *lttng_ht_iter_get_node_ulong(
 511                 struct lttng_ht_iter *iter)
 512 {
 513         struct cds_lfht_node *node;
 514
 515         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_ulong, node);
 521 }
 522
 523 /*
 524  * Return lttng ht unsigned long node from iterator.
 525  */
 526 struct lttng_ht_node_u64 *lttng_ht_iter_get_node_u64(
 527                 struct lttng_ht_iter *iter)
 528 {
 529         struct cds_lfht_node *node;
 530
 531         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_u64, node);
 537 }
 538
 539 /*
 540  * Return lttng ht stream and index id node from iterator.
 541  */
 542 struct lttng_ht_node_two_u64 *lttng_ht_iter_get_node_two_u64(
 543                 struct lttng_ht_iter *iter)
 544 {
 545         struct cds_lfht_node *node;
 546
 547         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_two_u64, node);
 553 }
 554
 555 /*
 556  * lib constructor
 557  */
 558 static void __attribute__((constructor)) _init(void)
 559 {
 560         /* Init hash table seed */
 561         lttng_ht_seed = (unsigned long) time(NULL);
 562 }