rcuja/rcuja-range.c

   1 /*
   2  * rcuja/rcuja-range.c
   3  *
   4  * Userspace RCU library - RCU Judy Array Range Support
   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 <string.h>
  28 #include <assert.h>
  29 #include <pthread.h>
  30 #include <urcu/rcuja.h>
  31 #include <urcu/compiler.h>
  32 #include <urcu/arch.h>
  33 #include <urcu-pointer.h>
  34 #include <urcu/uatomic.h>
  35 #include <urcu/rcuja-range.h>
  36 #include <urcu-flavor.h>
  37
  38 #include "rcuja-internal.h"
  39
  40 /*
  41  * Discussion about order of lookup/lock vs allocated node deletion.
  42  *
  43  * - If node deletion returns before call to
  44  *   cds_ja_range_lookup(), the node will not be found by lookup.
  45  * - If node deletion is called after cds_ja_range_lock() returns a
  46  *   non-NULL range, the deletion will wait until the lock is released
  47  *   before it takes place.
  48  * - If node deletion call/return overlaps with the call to
  49  *   cds_ja_range_lookup() and return from cds_ja_range_lock(), the node
  50  *   may or may not be found by each of cds_ja_range_lookup() and
  51  *   cds_ja_range_lock().
  52  */
  53
  54 /*
  55  * Discussion about order of lookup/lock vs allocated node add. Assuming
  56  * no concurrent delete.
  57  *
  58  * - If node add returns before call to
  59  *   cds_ja_range_lookup(), the node will be found by lookup.
  60  * - If node add is called after cds_ja_range_lookup returns, the node
  61  *   will not be found by lookup.
  62  * - If node add call/return overlaps with the call to and return from
  63  *   cds_ja_range_lookup(), the node may or may not be found.
  64  * - If node add call/return overlaps with call to cds_ja_range_lookup()
  65  *   and return from cds_ja_range_lock(), in the specific case where
  66  *   cds_ja_range_lookup() _does_ succeed, then cds_ja_range_lock() will
  67  *   succeed (still assuming no concurrent deletion).
  68  */
  69
  70 /*
  71  * Discussion: concurrent deletion of contiguous allocated ranges.
  72  *
  73  * Ensuring that merge of contiguous free ranges is always performed, we
  74  * need to ensure locking of concurrent removal of contiguous allocated
  75  * ranges one with respect to another. This is done by locking the
  76  * ranges prior to and after the range to remove, even if that range is
  77  * allocated. This serializes removal of contiguous ranges. The only
  78  * cases for which there is no range to lock is when removing an
  79  * allocated range starting at 0, and/or ending at the end of the key
  80  * space.
  81  */
  82
  83 /*
  84  * Discussion of the type state transitions.
  85  *
  86  * State transitions of "type" always go from either:
  87  *
  88  * CDS_JA_RANGE_FREE -> CDS_JA_RANGE_REMOVED
  89  * or
  90  * CDS_JA_RANGE_ALLOCATED -> CDS_JA_RANGE_REMOVED
  91  *
  92  * A range type never changes otherwise.
  93  */
  94
  95 #define CDS_JA_RANGE_KEY_BITS   64
  96
  97 enum cds_ja_range_type {
  98         CDS_JA_RANGE_ALLOCATED,
  99         CDS_JA_RANGE_FREE,
 100         CDS_JA_RANGE_REMOVED,
 101 };
 102
 103 /*
 104  * Range goes from start (inclusive) to end (inclusive).
 105  * Range start is used as node key in the Judy array.
 106  */
 107 struct cds_ja_range {
 108         uint64_t end;
 109         struct cds_ja_node ja_node;
 110         pthread_mutex_t lock;
 111         void *priv;
 112         enum cds_ja_range_type type;
 113
 114         /* not required on lookup fast-path */
 115         uint64_t start;
 116         struct rcu_head head;
 117 };
 118
 119 struct cds_ja_range *cds_ja_range_lookup(struct cds_ja *ja, uint64_t key)
 120 {
 121         struct cds_ja_node *node, *last_node;
 122         struct cds_ja_range *range;
 123
 124         node = cds_ja_lookup_below_equal(ja, key, NULL);
 125         assert(node);
 126         /*
 127          * Get the last of duplicate chain. Adding a node to Judy array
 128          * duplicates inserts them at the end of the chain.
 129          */
 130         cds_ja_for_each_duplicate_rcu(node)
 131                 last_node = node;
 132         range = caa_container_of(last_node, struct cds_ja_range, ja_node);
 133         /*
 134          * If last node in the duplicates is removed or free, we can
 135          * consider that either a removal or add operation is in
 136          * progress, or removal is the last completed operation to
 137          * update this range. We can therefore consider that this area
 138          * is not allocated.
 139          */
 140         if (range->type != CDS_JA_RANGE_ALLOCATED)
 141                 return NULL;
 142         /*
 143          * We found an allocated range. We can return it for use with
 144          * RCU read-side protection for existence. However, we have no
 145          * mutual exclusion against removal at this point.
 146          */
 147         return range;
 148 }
 149
 150 /*
 151  * Provide mutual exclusion against removal.
 152  */
 153 struct cds_ja_range *cds_ja_range_lock(struct cds_ja_range *range)
 154 {
 155         pthread_mutex_lock(&range->lock);
 156
 157         if (range->type == CDS_JA_RANGE_REMOVED)
 158                 goto removed;
 159         return range;
 160
 161 removed:
 162         pthread_mutex_unlock(&range->lock);
 163         return NULL;
 164 }
 165
 166 void cds_ja_range_unlock(struct cds_ja_range *range)
 167 {
 168         pthread_mutex_unlock(&range->lock);
 169 }
 170
 171 static
 172 struct cds_ja_range *range_create(
 173                 uint64_t start,         /* inclusive */
 174                 uint64_t end,           /* inclusive */
 175                 void *priv,
 176                 enum cds_ja_range_type type)
 177 {
 178         struct cds_ja_range *range;
 179
 180         range = calloc(sizeof(*range), 1);
 181         if (!range)
 182                 return NULL;
 183         range->start = start;
 184         range->end = end;
 185         range->priv = priv;
 186         range->type = type;
 187         pthread_mutex_init(&range->lock, NULL);
 188         return range;
 189 }
 190
 191 static
 192 void free_range_cb(struct rcu_head *head)
 193 {
 194         struct cds_ja_range *range =
 195                 caa_container_of(head, struct cds_ja_range, head);
 196         free(range);
 197 }
 198
 199 static
 200 void free_range(struct cds_ja_range *range)
 201 {
 202         free(range);
 203 }
 204
 205 static
 206 void rcu_free_range(struct cds_ja *ja, struct cds_ja_range *range)
 207 {
 208         cds_lfht_rcu_flavor(ja->ht)->update_call_rcu(&range->head,
 209                         free_range_cb);
 210 }
 211
 212 int cds_ja_range_add(struct cds_ja *ja,
 213                 uint64_t start,         /* inclusive */
 214                 uint64_t end,           /* inclusive */
 215                 void *priv)
 216 {
 217         struct cds_ja_node *old_node, *old_node_end;
 218         struct cds_ja_range *old_range, *old_range_end, *new_range, *ranges[3];
 219         unsigned int nr_ranges, i;
 220         int ret;
 221
 222 retry:
 223         /*
 224          * Find if requested range is entirely contained within a single
 225          * free range.
 226          */
 227         old_node = cds_ja_lookup_below_equal(ja, start, NULL);
 228         assert(old_node);
 229
 230         old_range = caa_container_of(old_node, struct cds_ja_range, ja_node);
 231         switch (CMM_LOAD_SHARED(old_range->type)) {
 232         case CDS_JA_RANGE_ALLOCATED:
 233                 return -EEXIST;
 234         case CDS_JA_RANGE_FREE:
 235                 break;
 236         case CDS_JA_RANGE_REMOVED:
 237                 goto retry;
 238         }
 239
 240         old_node_end = cds_ja_lookup_below_equal(ja, end, NULL);
 241         assert(old_node_end);
 242         old_range_end = caa_container_of(old_node_end,
 243                         struct cds_ja_range, ja_node);
 244         if (old_range_end != old_range) {
 245                 switch (CMM_LOAD_SHARED(old_range->type)) {
 246                 case CDS_JA_RANGE_ALLOCATED:
 247                 case CDS_JA_RANGE_FREE:         /* fall-through */
 248                         return -EEXIST;
 249                 case CDS_JA_RANGE_REMOVED:
 250                         goto retry;
 251                 }
 252         }
 253
 254         pthread_mutex_lock(&old_range->lock);
 255
 256         if (old_range->type == CDS_JA_RANGE_REMOVED) {
 257                 pthread_mutex_unlock(&old_range->lock);
 258                 goto retry;
 259         }
 260
 261         /* Create replacement ranges: at most 2 free and 1 allocated */
 262         if (start == old_range->start) {
 263                 if (end == old_range->end) {
 264                         /* 1 range */
 265                         ranges[0] = new_range = range_create(start, end,
 266                                 priv, CDS_JA_RANGE_ALLOCATED);
 267                         nr_ranges = 1;
 268                 } else {
 269                         /* 2 ranges */
 270                         ranges[0] = new_range = range_create(start, end,
 271                                 priv, CDS_JA_RANGE_ALLOCATED);
 272                         ranges[1] = range_create(end + 1, old_range->end,
 273                                 NULL, CDS_JA_RANGE_FREE);
 274                         nr_ranges = 2;
 275                 }
 276         } else {
 277                 if (end == old_range->end) {
 278                         /* 2 ranges */
 279                         ranges[0] = range_create(old_range->start, start - 1,
 280                                 NULL, CDS_JA_RANGE_FREE);
 281                         ranges[1] = new_range = range_create(start, end,
 282                                 priv, CDS_JA_RANGE_ALLOCATED);
 283                         nr_ranges = 2;
 284                 } else {
 285                         /* 3 ranges */
 286                         ranges[0] = range_create(old_range->start, start - 1,
 287                                 NULL, CDS_JA_RANGE_FREE);
 288                         ranges[1] = new_range = range_create(start, end,
 289                                 priv, CDS_JA_RANGE_ALLOCATED);
 290                         ranges[2] = range_create(end + 1, old_range->end,
 291                                 NULL, CDS_JA_RANGE_FREE);
 292                         nr_ranges = 3;
 293                 }
 294         }
 295
 296         /* Add replacement ranges to Judy array */
 297         for (i = 0; i < nr_ranges; i++) {
 298                 ret = cds_ja_add(ja, ranges[i]->start, &ranges[i]->ja_node);
 299                 assert(!ret);
 300         }
 301
 302         /*
 303          * We add replacement ranges _before_ removing old ranges, so
 304          * concurrent traversals will always see one or the other. This
 305          * is OK because we temporarily have a duplicate key, and Judy
 306          * arrays provide key existence guarantee for lookups performed
 307          * concurrently with add followed by del of duplicate keys.
 308          */
 309
 310         /* Remove old free range */
 311         ret = cds_ja_del(ja, old_range->start, &old_range->ja_node);
 312         assert(!ret);
 313         old_range->type = CDS_JA_RANGE_REMOVED;
 314         pthread_mutex_unlock(&old_range->lock);
 315
 316         rcu_free_range(ja, old_range);
 317
 318         return 0;
 319 }
 320
 321 int cds_ja_range_del(struct cds_ja *ja, struct cds_ja_range *range)
 322 {
 323         struct cds_ja_node *prev_node, *next_node;
 324         struct cds_ja_range *new_range;
 325         struct cds_ja_range *merge_ranges[3], *lock_ranges[3];
 326         unsigned int nr_merge, nr_lock, i;
 327         uint64_t start, end;
 328         int ret;
 329
 330 retry:
 331         nr_merge = 0;
 332         nr_lock = 0;
 333         prev_node = cds_ja_lookup_below_equal(ja, range->start - 1, NULL);
 334         if (prev_node) {
 335                 struct cds_ja_range *prev_range;
 336
 337                 prev_range = caa_container_of(prev_node,
 338                         struct cds_ja_range, ja_node);
 339                 lock_ranges[nr_lock++] = prev_range;
 340                 if (prev_range->type != CDS_JA_RANGE_ALLOCATED)
 341                         merge_ranges[nr_merge++] = prev_range;
 342         }
 343
 344         lock_ranges[nr_lock++] = range;
 345         merge_ranges[nr_merge++] = range;
 346
 347         next_node = cds_ja_lookup_above_equal(ja, range->end + 1, NULL);
 348         if (next_node) {
 349                 struct cds_ja_range *next_range;
 350
 351                 next_range = caa_container_of(next_node,
 352                         struct cds_ja_range, ja_node);
 353                 lock_ranges[nr_lock++] = next_range;
 354                 if (next_range->type != CDS_JA_RANGE_ALLOCATED)
 355                         merge_ranges[nr_merge++] = next_range;
 356         }
 357
 358         /* Acquire locks in increasing key order for range merge */
 359         for (i = 0; i < nr_lock; i++)
 360                 pthread_mutex_lock(&lock_ranges[i]->lock);
 361         /* Ensure they are valid */
 362         for (i = 0; i < nr_lock; i++) {
 363                 if (lock_ranges[i]->type == CDS_JA_RANGE_REMOVED)
 364                         goto unlock_retry;
 365         }
 366
 367         /* Create new free range */
 368         start = merge_ranges[0]->start;
 369         end = merge_ranges[nr_merge - 1]->end;
 370         new_range = range_create(start, end, NULL, CDS_JA_RANGE_FREE);
 371         ret = cds_ja_add(ja, start, &new_range->ja_node);
 372         assert(!ret);
 373
 374         /* Remove old ranges */
 375         for (i = 0; i < nr_merge; i++) {
 376                 ret = cds_ja_del(ja, merge_ranges[i]->start,
 377                                 &merge_ranges[i]->ja_node);
 378                 assert(!ret);
 379                 merge_ranges[i]->type = CDS_JA_RANGE_REMOVED;
 380         }
 381         for (i = 0; i < nr_lock; i++)
 382                 pthread_mutex_unlock(&lock_ranges[i]->lock);
 383         /* Free old merged ranges */
 384         for (i = 0; i < nr_merge; i++)
 385                 rcu_free_range(ja, merge_ranges[i]);
 386
 387         return 0;
 388
 389         /* retry paths */
 390 unlock_retry:
 391         for (i = 0; i < nr_lock; i++)
 392                 pthread_mutex_unlock(&lock_ranges[i]->lock);
 393         goto retry;
 394 }
 395
 396 struct cds_ja *_cds_ja_range_new(const struct rcu_flavor_struct *flavor)
 397 {
 398         struct cds_ja_range *range;
 399         struct cds_ja *ja;
 400         int ret;
 401
 402         ja = _cds_ja_new(CDS_JA_RANGE_KEY_BITS, flavor);
 403         if (!ja)
 404                 return NULL;
 405         range = range_create(0, UINT64_MAX, NULL, CDS_JA_RANGE_FREE);
 406         if (!range)
 407                 goto free_ja;
 408         cds_lfht_rcu_flavor(ja->ht)->read_lock();
 409         ret = cds_ja_add(ja, 0, &range->ja_node);
 410         cds_lfht_rcu_flavor(ja->ht)->read_unlock();
 411         if (ret)
 412                 goto free_range;
 413         return ja;
 414
 415 free_range:
 416         free_range(range);
 417 free_ja:
 418         ret = cds_ja_destroy(ja);
 419         assert(!ret);
 420         return NULL;
 421 }
 422
 423 int cds_ja_range_destroy(struct cds_ja *ja,
 424                 void (*free_priv)(void *ptr))
 425 {
 426         uint64_t key;
 427         struct cds_ja_node *ja_node;
 428         int ret = 0;
 429
 430         cds_lfht_rcu_flavor(ja->ht)->read_lock();
 431         cds_ja_for_each_key_rcu(ja, key, ja_node) {
 432                 struct cds_ja_node *tmp_node;
 433
 434                 cds_ja_for_each_duplicate_safe_rcu(ja_node, tmp_node) {
 435                         struct cds_ja_range *range;
 436
 437                         range = caa_container_of(ja_node,
 438                                         struct cds_ja_range, ja_node);
 439                         ret = cds_ja_del(ja, key, &range->ja_node);
 440                         if (ret)
 441                                 goto error;
 442                         if (free_priv)
 443                                 free_priv(range->priv);
 444                         /* Alone using Judy array, OK to free now */
 445                         free_range(range);
 446                 }
 447         }
 448         cds_lfht_rcu_flavor(ja->ht)->read_unlock();
 449         return cds_ja_destroy(ja);
 450
 451 error:
 452         cds_lfht_rcu_flavor(ja->ht)->read_unlock();
 453         return ret;
 454 }