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