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 BUCKET_SIZE_RESIZE_THRESHOLD    32
  42 #define MAX_NR_BUCKETS                  1048576         /* 1M buckets */
  43
  44 #ifndef max
  45 #define max(a, b)       ((a) > (b) ? (a) : (b))
  46 #endif
  47
  48 struct rcu_table {
  49         unsigned long size;     /* always a power of 2 */
  50         struct rcu_head head;
  51         struct rcu_ht_node *tbl[0];
  52 };
  53
  54 struct rcu_ht {
  55         struct rcu_table *t;            /* shared */
  56         ht_hash_fct hash_fct;
  57         void *hashseed;
  58         pthread_mutex_t resize_mutex;   /* resize mutex: add/del mutex */
  59         unsigned long target_size;
  60         void (*ht_call_rcu)(struct rcu_head *head,
  61                       void (*func)(struct rcu_head *head));
  62 };
  63
  64 struct rcu_resize_work {
  65         struct rcu_head head;
  66         struct rcu_ht *ht;
  67 };
  68
  69 static
  70 void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth);
  71
  72 static
  73 void check_resize(struct rcu_ht *ht, struct rcu_table *t,
  74                   unsigned long chain_len)
  75 {
  76         //printf("check resize chain len %lu\n", chain_len);
  77         if (chain_len >= BUCKET_SIZE_RESIZE_THRESHOLD)
  78                 ht_resize_lazy(ht, t, chain_len / BUCKET_SIZE_RESIZE_THRESHOLD);
  79 }
  80
  81 /*
  82  * Algorithm to reverse bits in a word by lookup table, extended to
  83  * 64-bit words.
  84  * ref.
  85  * http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
  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 static
 138 struct rcu_ht_node *clear_flag(struct rcu_ht_node *node)
 139 {
 140         return (struct rcu_ht_node *) (((unsigned long) node) & ~0x1);
 141 }
 142
 143 static
 144 int is_removed(struct rcu_ht_node *node)
 145 {
 146         return ((unsigned long) node) & 0x1;
 147 }
 148
 149 static
 150 struct rcu_ht_node *flag_removed(struct rcu_ht_node *node)
 151 {
 152         return (struct rcu_ht_node *) (((unsigned long) node) | 0x1);
 153 }
 154
 155 static
 156 void _uatomic_max(unsigned long *ptr, unsigned long v)
 157 {
 158         unsigned long old1, old2;
 159
 160         old1 = uatomic_read(ptr);
 161         do {
 162                 old2 = old1;
 163                 if (old2 >= v)
 164                         break;
 165         } while ((old1 = uatomic_cmpxchg(ptr, old2, v)) != old2);
 166 }
 167
 168 static
 169 void _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
 170 {
 171         struct rcu_ht_node *iter_prev = NULL, *iter = NULL;
 172
 173         if (!t->size)
 174                 return;
 175         for (;;) {
 176                 unsigned long chain_len = 0;
 177
 178                 iter_prev = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
 179                 //printf("iter prev %p hash %lu bucket %lu\n", iter_prev,
 180                 //      node->hash, node->hash & (t->size - 1));
 181                 assert(iter_prev);
 182                 assert(iter_prev->reverse_hash <= node->reverse_hash);
 183                 for (;;) {
 184                         iter = clear_flag(rcu_dereference(iter_prev->next));
 185                         if (unlikely(!iter))
 186                                 break;
 187                         if (iter->reverse_hash < node->reverse_hash)
 188                                 break;
 189                         iter_prev = iter;
 190                         check_resize(ht, t, ++chain_len);
 191                 }
 192                 /* add in iter_prev->next */
 193                 if (is_removed(iter))
 194                         continue;
 195                 assert(node != iter);
 196                 node->next = iter;
 197                 assert(iter_prev != node);
 198                 if (uatomic_cmpxchg(&iter_prev->next, iter, node) != iter)
 199                         continue;
 200                 break;
 201         }
 202 }
 203
 204 static
 205 int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node)
 206 {
 207         struct rcu_ht_node *iter_prev, *iter, *next, *old;
 208         unsigned long chain_len;
 209         int found, ret = 0;
 210         int flagged = 0;
 211
 212 retry:
 213         chain_len = 0;
 214         found = 0;
 215         iter_prev = rcu_dereference(t->tbl[node->hash & (t->size - 1)]);
 216         assert(iter_prev);
 217         assert(iter_prev->reverse_hash <= node->reverse_hash);
 218         for (;;) {
 219                 iter = clear_flag(rcu_dereference(iter_prev->next));
 220                 if (unlikely(!iter))
 221                         break;
 222                 if (iter->reverse_hash < node->reverse_hash)
 223                         break;
 224                 if (iter == node) {
 225                         found = 1;
 226                         break;
 227                 }
 228                 iter_prev = iter;
 229         }
 230         if (!found) {
 231                 ret = -ENOENT;
 232                 goto end;
 233         }
 234         next = rcu_dereference(iter->next);
 235         if (!flagged) {
 236                 if (is_removed(next)) {
 237                         ret = -ENOENT;
 238                         goto end;
 239                 }
 240                 /* set deletion flag */
 241                 if ((old = uatomic_cmpxchg(&iter->next, next,
 242                                            flag_removed(next))) != next) {
 243                         if (old == flag_removed(next)) {
 244                                 ret = -ENOENT;
 245                                 goto end;
 246                         } else {
 247                                 goto retry;
 248                         }
 249                 }
 250                 flagged = 1;
 251         }
 252         /*
 253          * Remove the element from the list. Retry if there has been a
 254          * concurrent add (there cannot be a concurrent delete, because
 255          * we won the deletion flag cmpxchg).
 256          */
 257         if (uatomic_cmpxchg(&iter_prev->next, iter, clear_flag(next)) != iter)
 258                 goto retry;
 259 end:
 260         return ret;
 261 }
 262
 263 static
 264 void init_table(struct rcu_ht *ht, struct rcu_table *t,
 265                 unsigned long first, unsigned long len)
 266 {
 267         unsigned long i, end;
 268
 269         end = first + len;
 270         for (i = first; i < end; i++) {
 271                 /* Update table size when power of two */
 272                 if (i != 0 && !(i & (i - 1)))
 273                         t->size = i;
 274                 t->tbl[i] = calloc(1, sizeof(struct rcu_ht_node));
 275                 t->tbl[i]->dummy = 1;
 276                 t->tbl[i]->hash = i;
 277                 t->tbl[i]->reverse_hash = bit_reverse_ulong(i);
 278                 _ht_add(ht, t, t->tbl[i]);
 279         }
 280         t->size = end;
 281 }
 282
 283 struct rcu_ht *ht_new(ht_hash_fct hash_fct,
 284                       void *hashseed,
 285                       unsigned long init_size,
 286                       void (*ht_call_rcu)(struct rcu_head *head,
 287                                 void (*func)(struct rcu_head *head)))
 288 {
 289         struct rcu_ht *ht;
 290
 291         ht = calloc(1, sizeof(struct rcu_ht));
 292         ht->hash_fct = hash_fct;
 293         ht->hashseed = hashseed;
 294         ht->ht_call_rcu = ht_call_rcu;
 295         /* this mutex should not nest in read-side C.S. */
 296         pthread_mutex_init(&ht->resize_mutex, NULL);
 297         ht->t = calloc(1, sizeof(struct rcu_table)
 298                        + (max(init_size, 1) * sizeof(struct rcu_ht_node *)));
 299         ht->t->size = 0;
 300         pthread_mutex_lock(&ht->resize_mutex);
 301         init_table(ht, ht->t, 0, max(init_size, 1));
 302         pthread_mutex_unlock(&ht->resize_mutex);
 303         ht->target_size = ht->t->size;
 304         return ht;
 305 }
 306
 307 struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key)
 308 {
 309         struct rcu_table *t;
 310         struct rcu_ht_node *node;
 311         unsigned long hash, reverse_hash;
 312
 313         hash = ht->hash_fct(ht->hashseed, key);
 314         reverse_hash = bit_reverse_ulong(hash);
 315
 316         t = rcu_dereference(ht->t);
 317         node = rcu_dereference(t->tbl[hash & (t->size - 1)]);
 318         for (;;) {
 319                 if (unlikely(!node))
 320                         break;
 321                 if (node->reverse_hash > reverse_hash) {
 322                         node = NULL;
 323                         break;
 324                 }
 325                 if (node->key == key) {
 326                         if (is_removed(rcu_dereference(node->next)))
 327                                 node = NULL;
 328                         break;
 329                 }
 330                 node = clear_flag(rcu_dereference(node->next));
 331         }
 332         return node;
 333 }
 334
 335 void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node)
 336 {
 337         struct rcu_table *t;
 338
 339         node->hash = ht->hash_fct(ht->hashseed, node->key);
 340         node->reverse_hash = bit_reverse_ulong((unsigned long) node->hash);
 341
 342         t = rcu_dereference(ht->t);
 343         _ht_add(ht, t, node);
 344 }
 345
 346 int ht_remove(struct rcu_ht *ht, struct rcu_ht_node *node)
 347 {
 348         struct rcu_table *t;
 349
 350         t = rcu_dereference(ht->t);
 351         return _ht_remove(ht, t, node);
 352 }
 353
 354 static
 355 int ht_delete_dummy(struct rcu_ht *ht)
 356 {
 357         struct rcu_table *t;
 358         struct rcu_ht_node *node;
 359         unsigned long i;
 360
 361         t = ht->t;
 362         /* Check that the table is empty */
 363         node = t->tbl[0];
 364         do {
 365                 if (!node->dummy)
 366                         return -EPERM;
 367                 node = node->next;
 368         } while (node);
 369         /* Internal sanity check: all nodes left should be dummy */
 370         for (i = 0; i < t->size; i++) {
 371                 assert(t->tbl[i]->dummy);
 372                 free(t->tbl[i]);
 373         }
 374         return 0;
 375 }
 376
 377 /*
 378  * Should only be called when no more concurrent readers nor writers can
 379  * possibly access the table.
 380  */
 381 int ht_destroy(struct rcu_ht *ht)
 382 {
 383         int ret;
 384
 385         ret = ht_delete_dummy(ht);
 386         if (ret)
 387                 return ret;
 388         free(ht->t);
 389         free(ht);
 390         return ret;
 391 }
 392
 393 static
 394 void ht_free_table_cb(struct rcu_head *head)
 395 {
 396         struct rcu_table *t =
 397                 caa_container_of(head, struct rcu_table, head);
 398         free(t);
 399 }
 400
 401 /* called with resize mutex held */
 402 static
 403 void _do_ht_resize(struct rcu_ht *ht)
 404 {
 405         unsigned long new_size, old_size;
 406         struct rcu_table *new_t, *old_t;
 407
 408         //return; //TEST
 409
 410         old_t = ht->t;
 411         old_size = old_t->size;
 412
 413         new_size = CMM_LOAD_SHARED(ht->target_size);
 414         if (old_size == new_size)
 415                 return;
 416         new_t = malloc(sizeof(struct rcu_table)
 417                         + (new_size * sizeof(struct rcu_ht_node *)));
 418         assert(new_size > old_size);
 419         memcpy(&new_t->tbl, &old_t->tbl,
 420                old_size * sizeof(struct rcu_ht_node *));
 421         init_table(ht, new_t, old_size, new_size - old_size);
 422         new_t->size = new_size;
 423         /* Changing table and size atomically wrt lookups */
 424         rcu_assign_pointer(ht->t, new_t);
 425         ht->ht_call_rcu(&old_t->head, ht_free_table_cb);
 426 }
 427
 428 static
 429 void resize_target_update(struct rcu_ht *ht, struct rcu_table *t,
 430                           int growth_order)
 431 {
 432         unsigned long new_size = t->size << growth_order;
 433
 434         if (new_size > MAX_NR_BUCKETS)
 435                 new_size = MAX_NR_BUCKETS;
 436         //printf("resize update prevtarget %lu current %lu order %d\n",
 437         //      ht->target_size, t->size, growth_order);
 438         _uatomic_max(&ht->target_size, new_size);
 439 }
 440
 441 void ht_resize(struct rcu_ht *ht, int growth)
 442 {
 443         resize_target_update(ht, rcu_dereference(ht->t), growth);
 444         pthread_mutex_lock(&ht->resize_mutex);
 445         _do_ht_resize(ht);
 446         pthread_mutex_unlock(&ht->resize_mutex);
 447 }
 448
 449 static
 450 void do_resize_cb(struct rcu_head *head)
 451 {
 452         struct rcu_resize_work *work =
 453                 caa_container_of(head, struct rcu_resize_work, head);
 454         struct rcu_ht *ht = work->ht;
 455
 456         pthread_mutex_lock(&ht->resize_mutex);
 457         _do_ht_resize(ht);
 458         pthread_mutex_unlock(&ht->resize_mutex);
 459         free(work);
 460 }
 461
 462 static
 463 void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth)
 464 {
 465         struct rcu_resize_work *work;
 466
 467         work = malloc(sizeof(*work));
 468         work->ht = ht;
 469         resize_target_update(ht, t, growth);
 470         ht->ht_call_rcu(&work->head, do_resize_cb);
 471 }