rculfhash.c

   1 /*
   2  * rculfhash.c
   3  *
   4  * Userspace RCU library - Lock-Free Expandable RCU Hash Table
   5  *
   6  * Copyright 2010-2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  21  */
  22
  23 #define _LGPL_SOURCE
  24 #include <stdlib.h>
  25 #include <errno.h>
  26 #include <assert.h>
  27 #include <stdio.h>
  28 #include <stdint.h>
  29 #include <string.h>
  30
  31 #include <urcu.h>
  32 #include <urcu-call-rcu.h>
  33 #include <urcu/arch.h>
  34 #include <urcu/uatomic.h>
  35 #include <urcu/jhash.h>
  36 #include <urcu/compiler.h>
  37 #include <urcu/rculfhash.h>
  38 #include <stdio.h>
  39 #include <pthread.h>
  40
  41 #define DEBUG           /* Test */
  42
  43 #ifdef DEBUG
  44 #define dbg_printf(args...)     printf(args)
  45 #else
  46 #define dbg_printf(args...)
  47 #endif
  48
  49 #define CHAIN_LEN_TARGET                1
  50 #define CHAIN_LEN_RESIZE_THRESHOLD      2
  51
  52 #ifndef max
  53 #define max(a, b)       ((a) > (b) ? (a) : (b))
  54 #endif
  55
  56 struct rcu_table {
  57         unsigned long size;     /* always a power of 2 */
  58         unsigned long resize_target;
  59         int resize_initiated;
  60         struct rcu_head head;
  61         struct rcu_ht_node *tbl[0];
  62 };
  63
  64 struct rcu_ht {
  65         struct rcu_table *t;            /* shared */
  66         ht_hash_fct hash_fct;
  67         ht_compare_fct compare_fct;
  68         unsigned long hash_seed;
  69         pthread_mutex_t resize_mutex;   /* resize mutex: add/del mutex */
  70         void (*ht_call_rcu)(struct rcu_head *head,
  71                       void (*func)(struct rcu_head *head));
  72 };
  73
  74 struct rcu_resize_work {
  75         struct rcu_head head;
  76         struct rcu_ht *ht;
  77 };
  78
  79 /*
  80  * Algorithm to reverse bits in a word by lookup table, extended to
  81  * 64-bit words.
  82  * Source:
  83  * http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
  84  * Originally from Public Domain.
  85  */
  86
  87 static const uint8_t BitReverseTable256[256] =
  88 {
  89 #define R2(n) (n),   (n) + 2*64,     (n) + 1*64,     (n) + 3*64
  90 #define R4(n) R2(n), R2((n) + 2*16), R2((n) + 1*16), R2((n) + 3*16)
  91 #define R6(n) R4(n), R4((n) + 2*4 ), R4((n) + 1*4 ), R4((n) + 3*4 )
  92         R6(0), R6(2), R6(1), R6(3)
  93 };
  94 #undef R2
  95 #undef R4
  96 #undef R6
  97
  98 static
  99 uint8_t bit_reverse_u8(uint8_t v)
 100 {
 101         return BitReverseTable256[v];
 102 }
 103
 104 static __attribute__((unused))
 105 uint32_t bit_reverse_u32(uint32_t v)
 106 {
 107         return ((uint32_t) bit_reverse_u8(v) << 24) |
 108                 ((uint32_t) bit_reverse_u8(v >> 8) << 16) |
 109                 ((uint32_t) bit_reverse_u8(v >> 16) << 8) |
 110                 ((uint32_t) bit_reverse_u8(v >> 24));
 111 }
 112
 113 static __attribute__((unused))
 114 uint64_t bit_reverse_u64(uint64_t v)
 115 {
 116         return ((uint64_t) bit_reverse_u8(v) << 56) |
 117                 ((uint64_t) bit_reverse_u8(v >> 8)  << 48) |
 118                 ((uint64_t) bit_reverse_u8(v >> 16) << 40) |
 119                 ((uint64_t) bit_reverse_u8(v >> 24) << 32) |
 120                 ((uint64_t) bit_reverse_u8(v >> 32) << 24) |
 121                 ((uint64_t) bit_reverse_u8(v >> 40) << 16) |
 122                 ((uint64_t) bit_reverse_u8(v >> 48) << 8) |
 123                 ((uint64_t) bit_reverse_u8(v >> 56));
 124 }
 125
 126 static
 127 unsigned long bit_reverse_ulong(unsigned long v)
 128 {
 129 #if (CAA_BITS_PER_LONG == 32)
 130         return bit_reverse_u32(v);
 131 #else
 132         return bit_reverse_u64(v);
 133 #endif
 134 }
 135
 136 /*
 137  * Algorithm to find the log2 of a 32-bit unsigned integer.
 138  * source: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup
 139  * Originally from Public Domain.
 140  */
 141 static const char LogTable256[256] =
 142 {
 143 #define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
 144         -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
 145         LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
 146         LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
 147 };
 148
 149 uint32_t log2_u32(uint32_t v)
 150 {
 151         uint32_t t, tt;
 152
 153         if ((tt = (v >> 16)))
 154                 return (t = (tt >> 8))
 155                                 ? 24 + LogTable256[t]
 156                                 : 16 + LogTable256[tt];
 157         else
 158                 return (t = (v >> 8))
 159                                 ? 8 + LogTable256[t]
 160                                 : LogTable256[v];
 161 }
 162
 163 static
 164 void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth);
 165
 166 static
 167 void check_resize(struct rcu_ht *ht, struct rcu_table *t,
 168                   uint32_t chain_len)
 169 {
 170         if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD)
 171                 ht_resize_lazy(ht, t,
 172                         log2_u32(chain_len - CHAIN_LEN_TARGET - 1));
 173 }
 174
 175 static
 176 struct rcu_ht_node *clear_flag(struct rcu_ht_node *node)
 177 {
 178         return (struct rcu_ht_node *) (((unsigned long) node) & ~0x1);
 179 }
 180
 181 static
 182 int is_removed(struct rcu_ht_node *node)
 183 {
 184         return ((unsigned long) node) & 0x1;
 185 }
 186
 187 static
 188 struct rcu_ht_node *flag_removed(struct rcu_ht_node *node)
 189 {
 190         return (struct rcu_ht_node *) (((unsigned long) node) | 0x1);
 191 }
 192
 193 static
 194 unsigned long _uatomic_max(unsigned long *ptr, unsigned long v)
 195 {
 196         unsigned long old1, old2;
 197
 198         old1 = uatomic_read(ptr);
 199         do {
 200                 old2 = old1;
 201                 if (old2 >= v)
 202                         return old2;
 203         } while ((old1 = uatomic_cmpxchg(ptr, old2, v)) != old2);
 204         return v;
 205 }
 206
 207 /*
 208  * Remove all logically deleted nodes from a bucket up to a certain node key.
 209  */
 210 static
 211 void _ht_gc_bucket(struct rcu_ht_node *dummy, struct rcu_ht_node *node)
 212 {
 213         struct rcu_ht_node *iter_prev, *iter, *next;
 214
 215         for (;;) {
 216                 iter_prev = dummy;
 217                 /* We can always skip the dummy node initially */
 218                 iter = rcu_dereference(iter_prev->next);
 219                 assert(iter_prev->reverse_hash <= node->reverse_hash);
 220                 for (;;) {
 221                         if (unlikely(!iter))
 222                                 return;
 223                         if (clear_flag(iter)->reverse_hash > node->reverse_hash)
 224                                 return;
 225                         next = rcu_dereference(clear_flag(iter)->next);
 226                         if (is_removed(next))
 227                                 break;
 228                         iter_prev = iter;
 229                         iter = next;
 230                 }
 231                 assert(!is_removed(iter));
 232                 (void) uatomic_cmpxchg(&iter_prev->next, iter, clear_flag(next));
 233         }
 234 }
 235
 236 static
 237 int _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node,
 238              int unique)
 239 {
 240         struct rcu_ht_node *iter_prev, *dummy, *iter, *next;
 241         unsigned long hash;
 242
 243         if (!t->size)
 244                 return 0;
 245         hash = bit_reverse_ulong(node->reverse_hash);
 246         for (;;) {
 247                 uint32_t chain_len = 0;
 248
 249                 /*
 250                  * iter_prev points to the non-removed node prior to the
 251                  * insert location.
 252                  */
 253                 iter_prev = rcu_dereference(t->tbl[hash & (t->size - 1)]);
 254                 /* We can always skip the dummy node initially */
 255                 iter = rcu_dereference(iter_prev->next);
 256                 assert(iter_prev->reverse_hash <= node->reverse_hash);
 257                 for (;;) {
 258                         if (unlikely(!iter))
 259                                 goto insert;
 260                         if (clear_flag(iter)->reverse_hash > node->reverse_hash)
 261                                 goto insert;
 262                         next = rcu_dereference(clear_flag(iter)->next);
 263                         if (is_removed(next))
 264                                 goto gc_node;
 265                         if (unique
 266                             && !clear_flag(iter)->dummy
 267                             && !ht->compare_fct(node->key, node->key_len,
 268                                                 clear_flag(iter)->key,
 269                                                 clear_flag(iter)->key_len))
 270                                 return -EEXIST;
 271                         /* Only account for identical reverse hash once */
 272                         if (iter_prev->reverse_hash != clear_flag(iter)->reverse_hash)
 273                                 check_resize(ht, t, ++chain_len);
 274                         iter_prev = clear_flag(iter);
 275                         iter = next;
 276                 }
 277         insert:
 278                 assert(node != clear_flag(iter));
 279                 assert(!is_removed(iter_prev));
 280                 assert(iter_prev != node);
 281                 node->next = iter;
 282                 if (uatomic_cmpxchg(&iter_prev->next, iter,
 283                                     node) != iter)
 284                         continue;       /* retry */
 285                 else
 286                         goto gc_end;
 287         gc_node:
 288                 assert(!is_removed(iter));
 289                 (void) uatomic_cmpxchg(&iter_prev->next, iter, clear_flag(next));
 290                 /* retry */
 291         }
 292 gc_end:
 293         /* Garbage collect logically removed nodes in the bucket */
 294         dummy = rcu_dereference(t->tbl[hash & (t->size - 1)]);
 295         _ht_gc_bucket(dummy, node);
 296         return 0;
 297 }
 298
 299 static
 300 int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
 301 {
 302         struct rcu_ht_node *dummy, *next, *old;
 303         int flagged = 0;
 304         unsigned long hash;
 305
 306         /* logically delete the node */
 307         old = rcu_dereference(node->next);
 308         do {
 309                 next = old;
 310                 if (is_removed(next))
 311                         goto end;
 312                 assert(!node->dummy);
 313                 old = uatomic_cmpxchg(&node->next, next,
 314                                       flag_removed(next));
 315         } while (old != next);
 316
 317         /* We performed the (logical) deletion. */
 318         flagged = 1;
 319
 320         /*
 321          * Ensure that the node is not visible to readers anymore: lookup for
 322          * the node, and remove it (along with any other logically removed node)
 323          * if found.
 324          */
 325         hash = bit_reverse_ulong(node->reverse_hash);
 326         dummy = rcu_dereference(t->tbl[hash & (t->size - 1)]);
 327         _ht_gc_bucket(dummy, node);
 328 end:
 329         /*
 330          * Only the flagging action indicated that we (and no other)
 331          * removed the node from the hash.
 332          */
 333         if (flagged) {
 334                 assert(is_removed(rcu_dereference(node->next)));
 335                 return 0;
 336         } else
 337                 return -ENOENT;
 338 }
 339
 340 static
 341 void init_table(struct rcu_ht *ht, struct rcu_table *t,
 342                 unsigned long first, unsigned long len)
 343 {
 344         unsigned long i, end;
 345
 346         end = first + len;
 347         for (i = first; i < end; i++) {
 348                 /* Update table size when power of two */
 349                 if (i != 0 && !(i & (i - 1)))
 350                         t->size = i;
 351                 t->tbl[i] = calloc(1, sizeof(struct rcu_ht_node));
 352                 t->tbl[i]->dummy = 1;
 353                 t->tbl[i]->reverse_hash = bit_reverse_ulong(i);
 354                 (void) _ht_add(ht, t, t->tbl[i], 0);
 355         }
 356         t->resize_target = t->size = end;
 357         t->resize_initiated = 0;
 358 }
 359
 360 struct rcu_ht *ht_new(ht_hash_fct hash_fct,
 361                       ht_compare_fct compare_fct,
 362                       unsigned long hash_seed,
 363                       unsigned long init_size,
 364                       void (*ht_call_rcu)(struct rcu_head *head,
 365                                 void (*func)(struct rcu_head *head)))
 366 {
 367         struct rcu_ht *ht;
 368
 369         ht = calloc(1, sizeof(struct rcu_ht));
 370         ht->hash_fct = hash_fct;
 371         ht->compare_fct = compare_fct;
 372         ht->hash_seed = hash_seed;
 373         ht->ht_call_rcu = ht_call_rcu;
 374         /* this mutex should not nest in read-side C.S. */
 375         pthread_mutex_init(&ht->resize_mutex, NULL);
 376         ht->t = calloc(1, sizeof(struct rcu_table)
 377                        + (max(init_size, 1) * sizeof(struct rcu_ht_node *)));
 378         ht->t->size = 0;
 379         pthread_mutex_lock(&ht->resize_mutex);
 380         init_table(ht, ht->t, 0, max(init_size, 1));
 381         pthread_mutex_unlock(&ht->resize_mutex);
 382         return ht;
 383 }
 384
 385 struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len)
 386 {
 387         struct rcu_table *t;
 388         struct rcu_ht_node *node;
 389         unsigned long hash, reverse_hash;
 390
 391         hash = ht->hash_fct(key, key_len, ht->hash_seed);
 392         reverse_hash = bit_reverse_ulong(hash);
 393
 394         t = rcu_dereference(ht->t);
 395         node = rcu_dereference(t->tbl[hash & (t->size - 1)]);
 396         for (;;) {
 397                 if (unlikely(!node))
 398                         break;
 399                 if (unlikely(node->reverse_hash > reverse_hash)) {
 400                         node = NULL;
 401                         break;
 402                 }
 403                 if (likely(!is_removed(rcu_dereference(node->next)))
 404                     && !node->dummy
 405                     && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
 406                                 break;
 407                 }
 408                 node = clear_flag(rcu_dereference(node->next));
 409         }
 410         assert(!node || !node->dummy);
 411         return node;
 412 }
 413
 414 void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node)
 415 {
 416         struct rcu_table *t;
 417         unsigned long hash;
 418
 419         hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
 420         node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
 421
 422         t = rcu_dereference(ht->t);
 423         (void) _ht_add(ht, t, node, 0);
 424 }
 425
 426 int ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node)
 427 {
 428         struct rcu_table *t;
 429         unsigned long hash;
 430
 431         hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed);
 432         node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
 433
 434         t = rcu_dereference(ht->t);
 435         return _ht_add(ht, t, node, 1);
 436 }
 437
 438 int ht_remove(struct rcu_ht *ht, struct rcu_ht_node *node)
 439 {
 440         struct rcu_table *t;
 441
 442         t = rcu_dereference(ht->t);
 443         return _ht_remove(ht, t, node);
 444 }
 445
 446 static
 447 int ht_delete_dummy(struct rcu_ht *ht)
 448 {
 449         struct rcu_table *t;
 450         struct rcu_ht_node *node;
 451         unsigned long i;
 452
 453         t = ht->t;
 454         /* Check that the table is empty */
 455         node = t->tbl[0];
 456         do {
 457                 if (!node->dummy)
 458                         return -EPERM;
 459                 node = node->next;
 460                 assert(!is_removed(node));
 461         } while (node);
 462         /* Internal sanity check: all nodes left should be dummy */
 463         for (i = 0; i < t->size; i++) {
 464                 assert(t->tbl[i]->dummy);
 465                 free(t->tbl[i]);
 466         }
 467         return 0;
 468 }
 469
 470 /*
 471  * Should only be called when no more concurrent readers nor writers can
 472  * possibly access the table.
 473  */
 474 int ht_destroy(struct rcu_ht *ht)
 475 {
 476         int ret;
 477
 478         ret = ht_delete_dummy(ht);
 479         if (ret)
 480                 return ret;
 481         free(ht->t);
 482         free(ht);
 483         return ret;
 484 }
 485
 486 void ht_count_nodes(struct rcu_ht *ht,
 487                 unsigned long *count,
 488                 unsigned long *removed)
 489 {
 490         struct rcu_table *t;
 491         struct rcu_ht_node *node, *next;
 492
 493         *count = 0;
 494         *removed = 0;
 495
 496         t = rcu_dereference(ht->t);
 497         /* Check that the table is empty */
 498         node = rcu_dereference(t->tbl[0]);
 499         do {
 500                 next = rcu_dereference(node->next);
 501                 if (is_removed(next)) {
 502                         assert(!node->dummy);
 503                         (*removed)++;
 504                 } else if (!node->dummy)
 505                         (*count)++;
 506                 node = clear_flag(next);
 507         } while (node);
 508 }
 509
 510 static
 511 void ht_free_table_cb(struct rcu_head *head)
 512 {
 513         struct rcu_table *t =
 514                 caa_container_of(head, struct rcu_table, head);
 515         free(t);
 516 }
 517
 518 /* called with resize mutex held */
 519 static
 520 void _do_ht_resize(struct rcu_ht *ht)
 521 {
 522         unsigned long new_size, old_size;
 523         struct rcu_table *new_t, *old_t;
 524
 525         old_t = ht->t;
 526         old_size = old_t->size;
 527
 528         new_size = CMM_LOAD_SHARED(old_t->resize_target);
 529         dbg_printf("rculfhash: resize from %lu to %lu buckets\n",
 530                    old_size, new_size);
 531         if (old_size == new_size)
 532                 return;
 533         new_t = malloc(sizeof(struct rcu_table)
 534                         + (new_size * sizeof(struct rcu_ht_node *)));
 535         assert(new_size > old_size);
 536         memcpy(&new_t->tbl, &old_t->tbl,
 537                old_size * sizeof(struct rcu_ht_node *));
 538         init_table(ht, new_t, old_size, new_size - old_size);
 539         /* Changing table and size atomically wrt lookups */
 540         rcu_assign_pointer(ht->t, new_t);
 541         ht->ht_call_rcu(&old_t->head, ht_free_table_cb);
 542 }
 543
 544 static
 545 unsigned long resize_target_update(struct rcu_table *t,
 546                                    int growth_order)
 547 {
 548         return _uatomic_max(&t->resize_target,
 549                             t->size << growth_order);
 550 }
 551
 552 void ht_resize(struct rcu_ht *ht, int growth)
 553 {
 554         struct rcu_table *t = rcu_dereference(ht->t);
 555         unsigned long target_size;
 556
 557         target_size = resize_target_update(t, growth);
 558         if (t->size < target_size) {
 559                 CMM_STORE_SHARED(t->resize_initiated, 1);
 560                 pthread_mutex_lock(&ht->resize_mutex);
 561                 _do_ht_resize(ht);
 562                 pthread_mutex_unlock(&ht->resize_mutex);
 563         }
 564 }
 565
 566 static
 567 void do_resize_cb(struct rcu_head *head)
 568 {
 569         struct rcu_resize_work *work =
 570                 caa_container_of(head, struct rcu_resize_work, head);
 571         struct rcu_ht *ht = work->ht;
 572
 573         pthread_mutex_lock(&ht->resize_mutex);
 574         _do_ht_resize(ht);
 575         pthread_mutex_unlock(&ht->resize_mutex);
 576         free(work);
 577 }
 578
 579 static
 580 void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth)
 581 {
 582         struct rcu_resize_work *work;
 583         unsigned long target_size;
 584
 585         target_size = resize_target_update(t, growth);
 586         if (!CMM_LOAD_SHARED(t->resize_initiated) && t->size < target_size) {
 587                 work = malloc(sizeof(*work));
 588                 work->ht = ht;
 589                 ht->ht_call_rcu(&work->head, do_resize_cb);
 590                 CMM_STORE_SHARED(t->resize_initiated, 1);
 591         }
 592 }