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);
 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 *node)
 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, hash_seed),
 190                         match_pointer, node, &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 *new_node,
 225                 struct cds_ja_shadow_node *inherit_from)
 226 {
 227         struct cds_ja_shadow_node *shadow_node;
 228         struct cds_lfht_node *ret_node;
 229         const struct rcu_flavor_struct *flavor;
 230
 231         shadow_node = calloc(sizeof(*shadow_node), 1);
 232         if (!shadow_node)
 233                 return NULL;
 234
 235         shadow_node->node = new_node;
 236         /*
 237          * Lock can be inherited from previous node at this position.
 238          */
 239         if (inherit_from) {
 240                 shadow_node->lock = inherit_from->lock;
 241         } else {
 242                 shadow_node->lock = calloc(sizeof(*shadow_node->lock), 1);
 243                 if (!shadow_node->lock) {
 244                         free(shadow_node);
 245                         return NULL;
 246                 }
 247                 pthread_mutex_init(shadow_node->lock, NULL);
 248         }
 249
 250         flavor = cds_lfht_rcu_flavor(ht);
 251         flavor->read_lock();
 252         ret_node = cds_lfht_add_unique(ht,
 253                         hash_pointer(new_node, hash_seed),
 254                         match_pointer,
 255                         new_node,
 256                         &shadow_node->ht_node);
 257         flavor->read_unlock();
 258
 259         if (ret_node != &shadow_node->ht_node) {
 260                 free(shadow_node);
 261                 return NULL;
 262         }
 263         return shadow_node;
 264 }
 265
 266 static
 267 void free_shadow_node(struct rcu_head *head)
 268 {
 269         struct cds_ja_shadow_node *shadow_node =
 270                 caa_container_of(head, struct cds_ja_shadow_node, head);
 271         free(shadow_node);
 272 }
 273
 274 static
 275 void free_shadow_node_and_node(struct rcu_head *head)
 276 {
 277         struct cds_ja_shadow_node *shadow_node =
 278                 caa_container_of(head, struct cds_ja_shadow_node, head);
 279         free(shadow_node->node);
 280         free(shadow_node);
 281 }
 282
 283 static
 284 void free_shadow_node_and_lock(struct rcu_head *head)
 285 {
 286         struct cds_ja_shadow_node *shadow_node =
 287                 caa_container_of(head, struct cds_ja_shadow_node, head);
 288         free(shadow_node->lock);
 289         free(shadow_node);
 290 }
 291
 292 static
 293 void free_shadow_node_and_node_and_lock(struct rcu_head *head)
 294 {
 295         struct cds_ja_shadow_node *shadow_node =
 296                 caa_container_of(head, struct cds_ja_shadow_node, head);
 297         assert(!shadow_node->is_root);
 298         free(shadow_node->node);
 299         free(shadow_node->lock);
 300         free(shadow_node);
 301 }
 302
 303 __attribute__((visibility("protected")))
 304 int rcuja_shadow_clear(struct cds_lfht *ht,
 305                 struct cds_ja_inode *node,
 306                 struct cds_ja_shadow_node *shadow_node,
 307                 unsigned int flags)
 308 {
 309         struct cds_lfht_iter iter;
 310         struct cds_lfht_node *lookup_node;
 311         const struct rcu_flavor_struct *flavor;
 312         int ret, lockret;
 313         int lookup_shadow = 0;
 314
 315         flavor = cds_lfht_rcu_flavor(ht);
 316         flavor->read_lock();
 317
 318         cds_lfht_lookup(ht, hash_pointer(node, hash_seed),
 319                         match_pointer, node, &iter);
 320         lookup_node = cds_lfht_iter_get_node(&iter);
 321         if (!lookup_node) {
 322                 ret = -ENOENT;
 323                 goto rcu_unlock;
 324         }
 325
 326         if (!shadow_node) {
 327                 shadow_node = caa_container_of(lookup_node,
 328                                 struct cds_ja_shadow_node, ht_node);
 329                 lockret = pthread_mutex_lock(shadow_node->lock);
 330                 assert(!lockret);
 331                 lookup_shadow = 1;
 332         }
 333
 334         /*
 335          * Holding the mutex across deletion, and by also re-checking if
 336          * the node is deleted with mutex held at lookup ensure that we
 337          * don't let RCU JA use a node being removed.
 338          */
 339         ret = cds_lfht_del(ht, lookup_node);
 340         if (!ret) {
 341                 if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE)
 342                                 && !shadow_node->is_root) {
 343                         if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
 344                                 flavor->update_call_rcu(&shadow_node->head,
 345                                         free_shadow_node_and_node_and_lock);
 346                         } else {
 347                                 flavor->update_call_rcu(&shadow_node->head,
 348                                         free_shadow_node_and_node);
 349                         }
 350                 } else {
 351                         if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
 352                                 flavor->update_call_rcu(&shadow_node->head,
 353                                         free_shadow_node_and_lock);
 354                         } else {
 355                                 flavor->update_call_rcu(&shadow_node->head,
 356                                         free_shadow_node);
 357                         }
 358                 }
 359         }
 360         if (lookup_shadow) {
 361                 lockret = pthread_mutex_unlock(shadow_node->lock);
 362                 assert(!lockret);
 363         }
 364 rcu_unlock:
 365         flavor->read_unlock();
 366
 367         return ret;
 368 }
 369
 370 /*
 371  * Delete all shadow nodes and nodes from hash table, along with their
 372  * associated lock.
 373  */
 374 __attribute__((visibility("protected")))
 375 void rcuja_shadow_prune(struct cds_lfht *ht,
 376                 unsigned int flags)
 377 {
 378         const struct rcu_flavor_struct *flavor;
 379         struct cds_ja_shadow_node *shadow_node;
 380         struct cds_lfht_iter iter;
 381         int ret, lockret;
 382
 383         flavor = cds_lfht_rcu_flavor(ht);
 384         flavor->read_lock();
 385         cds_lfht_for_each_entry(ht, &iter, shadow_node, ht_node) {
 386                 lockret = pthread_mutex_lock(shadow_node->lock);
 387                 assert(!lockret);
 388
 389                 ret = cds_lfht_del(ht, &shadow_node->ht_node);
 390                 if (!ret) {
 391                         if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE)
 392                                         && !shadow_node->is_root) {
 393                                 if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
 394                                         flavor->update_call_rcu(&shadow_node->head,
 395                                                 free_shadow_node_and_node_and_lock);
 396                                 } else {
 397                                         flavor->update_call_rcu(&shadow_node->head,
 398                                                 free_shadow_node_and_node);
 399                                 }
 400                         } else {
 401                                 if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
 402                                         flavor->update_call_rcu(&shadow_node->head,
 403                                                 free_shadow_node_and_lock);
 404                                 } else {
 405                                         flavor->update_call_rcu(&shadow_node->head,
 406                                                 free_shadow_node);
 407                                 }
 408                         }
 409                 }
 410                 lockret = pthread_mutex_unlock(shadow_node->lock);
 411                 assert(!lockret);
 412         }
 413         flavor->read_unlock();
 414 }
 415
 416 __attribute__((visibility("protected")))
 417 struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor)
 418 {
 419         return _cds_lfht_new(1, 1, 0,
 420                 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING,
 421                 NULL, flavor, NULL);
 422 }
 423
 424 __attribute__((visibility("protected")))
 425 int rcuja_delete_ht(struct cds_lfht *ht)
 426 {
 427         return cds_lfht_destroy(ht, NULL);
 428 }
 429
 430 __attribute__((constructor))
 431 void rcuja_ht_init(void)
 432 {
 433         hash_seed = (unsigned long) time(NULL);
 434 }