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