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