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         ret = pthread_mutex_lock(shadow_node->lock);
 200         assert(!ret);
 201         if (cds_lfht_is_node_deleted(lookup_node)) {
 202                 ret = pthread_mutex_unlock(shadow_node->lock);
 203                 assert(!ret);
 204                 shadow_node = NULL;
 205         }
 206 rcu_unlock:
 207         flavor->read_unlock();
 208         return shadow_node;
 209 }
 210
 211 __attribute__((visibility("protected")))
 212 void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node)
 213 {
 214         int ret;
 215
 216         ret = pthread_mutex_unlock(shadow_node->lock);
 217         assert(!ret);
 218 }
 219
 220 __attribute__((visibility("protected")))
 221 int rcuja_shadow_set(struct cds_lfht *ht,
 222                 struct cds_ja_inode *new_node,
 223                 struct cds_ja_shadow_node *inherit_from)
 224 {
 225         struct cds_ja_shadow_node *shadow_node;
 226         struct cds_lfht_node *ret_node;
 227         const struct rcu_flavor_struct *flavor;
 228
 229         shadow_node = calloc(sizeof(*shadow_node), 1);
 230         if (!shadow_node)
 231                 return -ENOMEM;
 232
 233         shadow_node->node = new_node;
 234         /*
 235          * Lock can be inherited from previous node at this position.
 236          */
 237         if (inherit_from) {
 238                 shadow_node->lock = inherit_from->lock;
 239         } else {
 240                 shadow_node->lock = calloc(sizeof(*shadow_node->lock), 1);
 241                 if (!shadow_node->lock) {
 242                         free(shadow_node);
 243                         return -ENOMEM;
 244                 }
 245                 pthread_mutex_init(shadow_node->lock, NULL);
 246         }
 247
 248         flavor = cds_lfht_rcu_flavor(ht);
 249         flavor->read_lock();
 250         ret_node = cds_lfht_add_unique(ht,
 251                         hash_pointer(new_node, hash_seed),
 252                         match_pointer,
 253                         new_node,
 254                         &shadow_node->ht_node);
 255         flavor->read_unlock();
 256
 257         if (ret_node != &shadow_node->ht_node) {
 258                 free(shadow_node);
 259                 return -EEXIST;
 260         }
 261         return 0;
 262 }
 263
 264 static
 265 void free_shadow_node_and_node(struct rcu_head *head)
 266 {
 267         struct cds_ja_shadow_node *shadow_node =
 268                 caa_container_of(head, struct cds_ja_shadow_node, head);
 269         free(shadow_node->node);
 270         free(shadow_node);
 271 }
 272
 273 static
 274 void free_shadow_node_and_node_and_lock(struct rcu_head *head)
 275 {
 276         struct cds_ja_shadow_node *shadow_node =
 277                 caa_container_of(head, struct cds_ja_shadow_node, head);
 278         free(shadow_node->node);
 279         free(shadow_node->lock);
 280         free(shadow_node);
 281 }
 282
 283 __attribute__((visibility("protected")))
 284 int rcuja_shadow_clear(struct cds_lfht *ht,
 285                 struct cds_ja_inode *node,
 286                 unsigned int flags)
 287 {
 288         struct cds_lfht_iter iter;
 289         struct cds_lfht_node *lookup_node;
 290         struct cds_ja_shadow_node *shadow_node;
 291         const struct rcu_flavor_struct *flavor;
 292         int ret, lockret;
 293
 294         flavor = cds_lfht_rcu_flavor(ht);
 295         flavor->read_lock();
 296         cds_lfht_lookup(ht, hash_pointer(node, hash_seed),
 297                         match_pointer, node, &iter);
 298         lookup_node = cds_lfht_iter_get_node(&iter);
 299         if (!lookup_node) {
 300                 ret = -ENOENT;
 301                 goto rcu_unlock;
 302         }
 303         shadow_node = caa_container_of(lookup_node,
 304                         struct cds_ja_shadow_node, ht_node);
 305         lockret = pthread_mutex_lock(shadow_node->lock);
 306         assert(!lockret);
 307
 308         /*
 309          * Holding the mutex across deletion, and by also re-checking if
 310          * the node is deleted with mutex held at lookup ensure that we
 311          * don't let RCU JA use a node being removed.
 312          */
 313         ret = cds_lfht_del(ht, lookup_node);
 314         if (!ret) {
 315                 assert(flags & RCUJA_SHADOW_CLEAR_FREE_NODE);
 316                 if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) {
 317                         flavor->update_call_rcu(&shadow_node->head,
 318                                 free_shadow_node_and_node_and_lock);
 319                 } else {
 320                         flavor->update_call_rcu(&shadow_node->head,
 321                                 free_shadow_node_and_node);
 322                 }
 323         }
 324         lockret = pthread_mutex_unlock(shadow_node->lock);
 325         assert(!lockret);
 326 rcu_unlock:
 327         flavor->read_unlock();
 328
 329         return ret;
 330 }
 331
 332 /*
 333  * Delete all shadow nodes and nodes from hash table, along with their
 334  * associated lock.
 335  */
 336 __attribute__((visibility("protected")))
 337 void rcuja_shadow_prune(struct cds_lfht *ht,
 338                 unsigned int flags)
 339 {
 340         const struct rcu_flavor_struct *flavor;
 341         struct cds_ja_shadow_node *shadow_node;
 342         struct cds_lfht_iter iter;
 343         int ret, lockret;
 344
 345         flavor = cds_lfht_rcu_flavor(ht);
 346         flavor->read_lock();
 347         cds_lfht_for_each_entry(ht, &iter, shadow_node, ht_node) {
 348                 lockret = pthread_mutex_lock(shadow_node->lock);
 349                 assert(!lockret);
 350
 351                 ret = cds_lfht_del(ht, &shadow_node->ht_node);
 352                 if (!ret) {
 353                         assert((flags & RCUJA_SHADOW_CLEAR_FREE_NODE)
 354                                 && (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK));
 355                         flavor->update_call_rcu(&shadow_node->head,
 356                                 free_shadow_node_and_node_and_lock);
 357                 }
 358                 lockret = pthread_mutex_unlock(shadow_node->lock);
 359                 assert(!lockret);
 360         }
 361         flavor->read_unlock();
 362 }
 363
 364 __attribute__((visibility("protected")))
 365 struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor)
 366 {
 367         return _cds_lfht_new(1, 1, 0,
 368                 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING,
 369                 NULL, flavor, NULL);
 370 }
 371
 372 __attribute__((visibility("protected")))
 373 int rcuja_delete_ht(struct cds_lfht *ht)
 374 {
 375         return cds_lfht_destroy(ht, NULL);
 376 }
 377
 378 __attribute__((constructor))
 379 void rcuja_ht_init(void)
 380 {
 381         hash_seed = (unsigned long) time(NULL);
 382 }