rcuja/rcuja-shadow-nodes.c

   1 /*
   2  * rcuja/rcuja-hashtable.c
   3  *
   4  * Userspace RCU library - RCU Judy Array Shadow Node Hash Table
   5  *
   6  * Copyright 2012 - 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 <stdint.h>
  25 #include <errno.h>
  26 #include <limits.h>
  27 #include <urcu/rcuja.h>
  28 #include <urcu/compiler.h>
  29 #include <urcu/arch.h>
  30 #include <assert.h>
  31 #include <urcu-pointer.h>
  32 #include <stdlib.h>
  33 #include <time.h>
  34
  35 #include "rcuja-internal.h"
  36 #include "bitfield.h"
  37
  38 static unsigned long hash_seed;
  39
  40 /*
  41  * Hash function
  42  * Source: http://burtleburtle.net/bob/c/lookup3.c
  43  * Originally Public Domain
  44  */
  45
  46 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
  47
  48 #define mix(a, b, c) \
  49 do { \
  50         a -= c; a ^= rot(c,  4); c += b; \
  51         b -= a; b ^= rot(a,  6); a += c; \
  52         c -= b; c ^= rot(b,  8); b += a; \
  53         a -= c; a ^= rot(c, 16); c += b; \
  54         b -= a; b ^= rot(a, 19); a += c; \
  55         c -= b; c ^= rot(b,  4); b += a; \
  56 } while (0)
  57
  58 #define final(a, b, c) \
  59 { \
  60         c ^= b; c -= rot(b, 14); \
  61         a ^= c; a -= rot(c, 11); \
  62         b ^= a; b -= rot(a, 25); \
  63         c ^= b; c -= rot(b, 16); \
  64         a ^= c; a -= rot(c,  4);\
  65         b ^= a; b -= rot(a, 14); \
  66         c ^= b; c -= rot(b, 24); \
  67 }
  68
  69 static inline __attribute__((unused))
  70 uint32_t hash_u32(
  71         const uint32_t *k,      /* the key, an array of uint32_t values */
  72         size_t length,          /* the length of the key, in uint32_ts */
  73         uint32_t initval)       /* the previous hash, or an arbitrary value */
  74 {
  75         uint32_t a, b, c;
  76
  77         /* Set up the internal state */
  78         a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval;
  79
  80         /*----------------------------------------- handle most of the key */
  81         while (length > 3) {
  82                 a += k[0];
  83                 b += k[1];
  84                 c += k[2];
  85                 mix(a, b, c);
  86                 length -= 3;
  87                 k += 3;
  88         }
  89
  90         /*----------------------------------- handle the last 3 uint32_t's */
  91         switch (length) {       /* all the case statements fall through */
  92         case 3: c += k[2];
  93         case 2: b += k[1];
  94         case 1: a += k[0];
  95                 final(a, b, c);
  96         case 0:                 /* case 0: nothing left to add */
  97                 break;
  98         }
  99         /*---------------------------------------------- report the result */
 100         return c;
 101 }
 102
 103 static inline
 104 void hashword2(
 105         const uint32_t *k,      /* the key, an array of uint32_t values */
 106         size_t length,          /* the length of the key, in uint32_ts */
 107         uint32_t *pc,           /* IN: seed OUT: primary hash value */
 108         uint32_t *pb)           /* IN: more seed OUT: secondary hash value */
 109 {
 110         uint32_t a, b, c;
 111
 112         /* Set up the internal state */
 113         a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc;
 114         c += *pb;
 115
 116         /*----------------------------------------- handle most of the key */
 117         while (length > 3) {
 118                 a += k[0];
 119                 b += k[1];
 120                 c += k[2];
 121                 mix(a, b, c);
 122                 length -= 3;
 123                 k += 3;
 124         }
 125
 126         /*----------------------------------- handle the last 3 uint32_t's */
 127         switch (length) {       /* all the case statements fall through */
 128         case 3: c += k[2];
 129         case 2: b += k[1];
 130         case 1: a += k[0];
 131                 final(a, b, c);
 132         case 0:                 /* case 0: nothing left to add */
 133                 break;
 134         }
 135         /*---------------------------------------------- report the result */
 136         *pc = c;
 137         *pb = b;
 138 }
 139
 140 #if (CAA_BITS_PER_LONG == 32)
 141 static
 142 unsigned long hash_pointer(const void *_key, unsigned long seed)
 143 {
 144         unsigned int key = (unsigned int) _key;
 145
 146         return hash_u32(&key, 1, seed);
 147 }
 148 #else
 149 static
 150 unsigned long hash_pointer(const void *_key, unsigned long seed)
 151 {
 152         union {
 153                 uint64_t v64;
 154                 uint32_t v32[2];
 155         } v;
 156         union {
 157                 uint64_t v64;
 158                 uint32_t v32[2];
 159         } key;
 160
 161         v.v64 = (uint64_t) seed;
 162         key.v64 = (uint64_t) _key;
 163         hashword2(key.v32, 2, &v.v32[0], &v.v32[1]);
 164         return v.v64;
 165 }
 166 #endif
 167
 168 static
 169 int match_pointer(struct cds_lfht_node *node, const void *key)
 170 {
 171         struct cds_ja_shadow_node *shadow =
 172                 caa_container_of(node, struct cds_ja_shadow_node, ht_node);
 173
 174         return (key == shadow->node_flag);
 175 }
 176
 177 __attribute__((visibility("protected")))
 178 struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht,
 179                 struct cds_ja_inode_flag *node_flag)
 180 {
 181         struct cds_lfht_iter iter;
 182         struct cds_lfht_node *lookup_node;
 183         struct cds_ja_shadow_node *shadow_node;
 184         const struct rcu_flavor_struct *flavor;
 185         int ret;
 186
 187         flavor = cds_lfht_rcu_flavor(ht);
 188         flavor->read_lock();
 189         cds_lfht_lookup(ht, hash_pointer(node_flag, hash_seed),
 190                         match_pointer, node_flag, &iter);
 191
 192         lookup_node = cds_lfht_iter_get_node(&iter);
 193         if (!lookup_node) {
 194                 shadow_node = NULL;
 195                 goto rcu_unlock;
 196         }
 197         shadow_node = caa_container_of(lookup_node,
 198                         struct cds_ja_shadow_node, ht_node);
 199         dbg_printf("Lock %p\n", shadow_node->lock);
 200         ret = pthread_mutex_lock(shadow_node->lock);
 201         assert(!ret);
 202         if (cds_lfht_is_node_deleted(lookup_node)) {
 203                 ret = pthread_mutex_unlock(shadow_node->lock);
 204                 assert(!ret);
 205                 shadow_node = NULL;
 206         }
 207 rcu_unlock:
 208         flavor->read_unlock();
 209         return shadow_node;
 210 }
 211
 212 __attribute__((visibility("protected")))
 213 void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node)
 214 {
 215         int ret;
 216
 217         dbg_printf("Unlock %p\n", shadow_node->lock);
 218         ret = pthread_mutex_unlock(shadow_node->lock);
 219         assert(!ret);
 220 }
 221
 222 __attribute__((visibility("protected")))
 223 struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht,
 224                 struct cds_ja_inode_flag *new_node_flag,
 225                 struct cds_ja_shadow_node *inherit_from,
 226                 struct cds_ja *ja, int level)
 227 {
 228         struct cds_ja_shadow_node *shadow_node;
 229         struct cds_lfht_node *ret_node;
 230         const struct rcu_flavor_struct *flavor;
 231
 232         shadow_node = calloc(sizeof(*shadow_node), 1);
 233         if (!shadow_node)
 234                 return NULL;
 235
 236         shadow_node->node_flag = new_node_flag;
 237         shadow_node->ja = ja;
 238         /*
 239          * Lock can be inherited from previous node at this position.
 240          */
 241         if (inherit_from) {
 242                 shadow_node->lock = inherit_from->lock;
 243                 shadow_node->level = inherit_from->level;
 244         } else {
 245                 shadow_node->lock = calloc(sizeof(*shadow_node->lock), 1);
 246                 if (!shadow_node->lock) {
 247                         free(shadow_node);
 248                         return NULL;
 249                 }
 250                 pthread_mutex_init(shadow_node->lock, NULL);
 251                 shadow_node->level = level;
 252         }
 253
 254         flavor = cds_lfht_rcu_flavor(ht);
 255         flavor->read_lock();
 256         ret_node = cds_lfht_add_unique(ht,
 257                         hash_pointer(new_node_flag, hash_seed),
 258                         match_pointer,
 259                         new_node_flag,
 260                         &shadow_node->ht_node);
 261         flavor->read_unlock();
 262
 263         if (ret_node != &shadow_node->ht_node) {
 264                 free(shadow_node);
 265                 return NULL;
 266         }
 267         return shadow_node;
 268 }
 269
 270 static
 271 void free_shadow_node(struct rcu_head *head)
 272 {
 273         struct cds_ja_shadow_node *shadow_node =
 274                 caa_container_of(head, struct cds_ja_shadow_node, head);
 275         free(shadow_node);
 276 }
 277
 278 static
 279 void free_shadow_node_and_node(struct rcu_head *head)
 280 {
 281         struct cds_ja_shadow_node *shadow_node =
 282                 caa_container_of(head, struct cds_ja_shadow_node, head);
 283         free_cds_ja_node(ja_node_ptr(shadow_node->node_flag));
 284         free(shadow_node);
 285 }
 286
 287 static
 288 void free_shadow_node_and_lock(struct rcu_head *head)
 289 {
 290         struct cds_ja_shadow_node *shadow_node =
 291                 caa_container_of(head, struct cds_ja_shadow_node, head);
 292         free(shadow_node->lock);
 293         free(shadow_node);
 294 }
 295
 296 static
 297 void free_shadow_node_and_node_and_lock(struct rcu_head *head)
 298 {
 299         struct cds_ja_shadow_node *shadow_node =
 300                 caa_container_of(head, struct cds_ja_shadow_node, head);
 301         assert(shadow_node->level);
 302         free_cds_ja_node(ja_node_ptr(shadow_node->node_flag));
 303         free(shadow_node->lock);
 304         free(shadow_node);
 305 }
 306
 307 __attribute__((visibility("protected")))
 308 int rcuja_shadow_clear(struct cds_lfht *ht,
 309                 struct cds_ja_inode_flag *node_flag,
 310                 struct cds_ja_shadow_node *shadow_node,
 311                 unsigned int flags)
 312 {
 313         struct cds_lfht_iter iter;
 314         struct cds_lfht_node *lookup_node;
 315         const struct rcu_flavor_struct *flavor;
 316         int ret, lockret;
 317         int lookup_shadow = 0;
 318
 319         flavor = cds_lfht_rcu_flavor(ht);
 320         flavor->read_lock();
 321
 322         cds_lfht_lookup(ht, hash_pointer(node_flag, hash_seed),
 323                         match_pointer, node_flag, &iter);
 324         lookup_node = cds_lfht_iter_get_node(&iter);
 325         if (!lookup_node) {
 326                 ret = -ENOENT;
 327                 goto rcu_unlock;
 328         }
 329
 330         if (!shadow_node) {
 331                 shadow_node = caa_container_of(lookup_node,
 332                                 struct cds_ja_shadow_node, ht_node);
 333                 lockret = pthread_mutex_lock(shadow_node->lock);
 334                 assert(!lockret);
 335                 lookup_shadow = 1;
 336         }
 337
 338         /*
 339          * Holding the mutex across deletion, and by also re-checking if
 340          * the node is deleted with mutex held at lookup ensure that we
 341          * don't let RCU JA use a node being removed.
 342          */
 343         ret = cds_lfht_del(ht, lookup_node);
 344         if (!ret) {
 345                 if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE)
 346                                 && shadow_node->level) {
 347                         if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
 348                                 flavor->update_call_rcu(&shadow_node->head,
 349                                         free_shadow_node_and_node_and_lock);
 350                         } else {
 351                                 flavor->update_call_rcu(&shadow_node->head,
 352                                         free_shadow_node_and_node);
 353                         }
 354                 } else {
 355                         if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
 356                                 flavor->update_call_rcu(&shadow_node->head,
 357                                         free_shadow_node_and_lock);
 358                         } else {
 359                                 flavor->update_call_rcu(&shadow_node->head,
 360                                         free_shadow_node);
 361                         }
 362                 }
 363         }
 364         if (lookup_shadow) {
 365                 lockret = pthread_mutex_unlock(shadow_node->lock);
 366                 assert(!lockret);
 367         }
 368 rcu_unlock:
 369         flavor->read_unlock();
 370
 371         return ret;
 372 }
 373
 374 /*
 375  * Delete all shadow nodes and nodes from hash table, along with their
 376  * associated lock.
 377  */
 378 __attribute__((visibility("protected")))
 379 void rcuja_shadow_prune(struct cds_lfht *ht,
 380                 unsigned int flags,
 381                 void (*free_node_cb)(struct rcu_head *head))
 382 {
 383         const struct rcu_flavor_struct *flavor;
 384         struct cds_ja_shadow_node *shadow_node;
 385         struct cds_lfht_iter iter;
 386         int ret, lockret;
 387
 388         flavor = cds_lfht_rcu_flavor(ht);
 389         flavor->read_lock();
 390         cds_lfht_for_each_entry(ht, &iter, shadow_node, ht_node) {
 391                 lockret = pthread_mutex_lock(shadow_node->lock);
 392                 assert(!lockret);
 393
 394                 ret = cds_lfht_del(ht, &shadow_node->ht_node);
 395                 if (!ret) {
 396                         if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE)
 397                                         && shadow_node->level) {
 398                                 if (shadow_node->level == shadow_node->ja->tree_depth - 1) {
 399                                         rcuja_free_all_children(shadow_node,
 400                                                         shadow_node->node_flag,
 401                                                         free_node_cb);
 402                                 }
 403                                 if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
 404                                         flavor->update_call_rcu(&shadow_node->head,
 405                                                 free_shadow_node_and_node_and_lock);
 406                                 } else {
 407                                         flavor->update_call_rcu(&shadow_node->head,
 408                                                 free_shadow_node_and_node);
 409                                 }
 410                         } else {
 411                                 if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
 412                                         flavor->update_call_rcu(&shadow_node->head,
 413                                                 free_shadow_node_and_lock);
 414                                 } else {
 415                                         flavor->update_call_rcu(&shadow_node->head,
 416                                                 free_shadow_node);
 417                                 }
 418                         }
 419                 }
 420                 lockret = pthread_mutex_unlock(shadow_node->lock);
 421                 assert(!lockret);
 422         }
 423         flavor->read_unlock();
 424 }
 425
 426 __attribute__((visibility("protected")))
 427 struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor)
 428 {
 429         return _cds_lfht_new(1, 1, 0,
 430                 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING,
 431                 NULL, flavor, NULL);
 432 }
 433
 434 __attribute__((visibility("protected")))
 435 int rcuja_delete_ht(struct cds_lfht *ht)
 436 {
 437         return cds_lfht_destroy(ht, NULL);
 438 }
 439
 440 __attribute__((constructor))
 441 void rcuja_ht_init(void)
 442 {
 443         hash_seed = (unsigned long) time(NULL);
 444 }