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 rcu_ja_shadow_node *shadow =
 172                 caa_container_of(node, struct rcu_ja_shadow_node, ht_node);
 173
 174         return (key == shadow->node);
 175 }
 176
 177 __attribute__((visibility("protected")))
 178 struct rcu_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht,
 179                 struct rcu_ja_node *node)
 180 {
 181         struct cds_lfht_iter iter;
 182         struct cds_lfht_node *lookup_node;
 183         struct rcu_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 rcu_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 rcu_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 rcu_ja_node *node)
 223 {
 224         struct rcu_ja_shadow_node *shadow_node;
 225         struct cds_lfht_node *ret_node;
 226         const struct rcu_flavor_struct *flavor;
 227
 228         shadow_node = calloc(sizeof(*shadow_node), 1);
 229         if (!shadow_node)
 230                 return -ENOMEM;
 231
 232         shadow_node->node = node;
 233         pthread_mutex_init(&shadow_node->lock, NULL);
 234
 235         flavor = cds_lfht_rcu_flavor(ht);
 236         flavor->read_lock();
 237         ret_node = cds_lfht_add_unique(ht,
 238                         hash_pointer(node, hash_seed),
 239                         match_pointer,
 240                         node,
 241                         &shadow_node->ht_node);
 242         flavor->read_unlock();
 243
 244         if (ret_node != &shadow_node->ht_node) {
 245                 free(shadow_node);
 246                 return -EEXIST;
 247         }
 248         return 0;
 249 }
 250
 251 static
 252 void free_shadow_node_and_node(struct rcu_head *head)
 253 {
 254         struct rcu_ja_shadow_node *shadow_node =
 255                 caa_container_of(head, struct rcu_ja_shadow_node, head);
 256         free(shadow_node->node);
 257         free(shadow_node);
 258 }
 259
 260 __attribute__((visibility("protected")))
 261 int rcuja_shadow_clear_and_free_node(struct cds_lfht *ht,
 262                 struct rcu_ja_node *node)
 263 {
 264         struct cds_lfht_iter iter;
 265         struct cds_lfht_node *lookup_node;
 266         struct rcu_ja_shadow_node *shadow_node;
 267         const struct rcu_flavor_struct *flavor;
 268         int ret, lockret;
 269
 270         flavor = cds_lfht_rcu_flavor(ht);
 271         flavor->read_lock();
 272         cds_lfht_lookup(ht, hash_pointer(node, hash_seed),
 273                         match_pointer, node, &iter);
 274         lookup_node = cds_lfht_iter_get_node(&iter);
 275         if (!lookup_node) {
 276                 ret = -ENOENT;
 277                 goto rcu_unlock;
 278         }
 279         shadow_node = caa_container_of(lookup_node,
 280                         struct rcu_ja_shadow_node, ht_node);
 281         lockret = pthread_mutex_lock(&shadow_node->lock);
 282         assert(!lockret);
 283
 284         /*
 285          * Holding the mutex across deletion, and by also re-checking if
 286          * the node is deleted with mutex held at lookup ensure that we
 287          * don't let RCU JA use a node being removed.
 288          */
 289         ret = cds_lfht_del(ht, lookup_node);
 290         if (!ret) {
 291                 flavor->update_call_rcu(&shadow_node->head, free_shadow_node_and_node);
 292         }
 293         lockret = pthread_mutex_unlock(&shadow_node->lock);
 294         assert(!lockret);
 295 rcu_unlock:
 296         flavor->read_unlock();
 297
 298         return ret;
 299 }
 300
 301 __attribute__((visibility("protected")))
 302 struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor)
 303 {
 304         return _cds_lfht_new(1, 1, 0,
 305                 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING,
 306                 NULL, flavor, NULL);
 307 }
 308
 309 __attribute__((visibility("protected")))
 310 void rcuja_delete_ht(struct cds_lfht *ht)
 311 {
 312         int ret;
 313
 314         ret = cds_lfht_destroy(ht, NULL);
 315         assert(!ret);
 316 }
 317
 318 __attribute__((constructor))
 319 void rcuja_ht_init(void)
 320 {
 321         hash_seed = (unsigned long) time(NULL);
 322 }