urcu-bp.c

   1 /*
   2  * urcu-bp.c
   3  *
   4  * Userspace RCU library, "bulletproof" version.
   5  *
   6  * Copyright (c) 2009 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   7  * Copyright (c) 2009 Paul E. McKenney, IBM Corporation.
   8  *
   9  * This library is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU Lesser General Public
  11  * License as published by the Free Software Foundation; either
  12  * version 2.1 of the License, or (at your option) any later version.
  13  *
  14  * This library is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * Lesser General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public
  20  * License along with this library; if not, write to the Free Software
  21  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  22  *
  23  * IBM's contributions to this file may be relicensed under LGPLv2 or later.
  24  */
  25
  26 #define _GNU_SOURCE
  27 #define _LGPL_SOURCE
  28 #include <stdio.h>
  29 #include <pthread.h>
  30 #include <signal.h>
  31 #include <assert.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34 #include <errno.h>
  35 #include <poll.h>
  36 #include <unistd.h>
  37 #include <sys/mman.h>
  38
  39 #include "urcu/wfqueue.h"
  40 #include "urcu/map/urcu-bp.h"
  41 #include "urcu/static/urcu-bp.h"
  42 #include "urcu-pointer.h"
  43 #include "urcu/tls-compat.h"
  44
  45 #include "urcu-die.h"
  46
  47 /* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
  48 #undef _LGPL_SOURCE
  49 #include "urcu-bp.h"
  50 #define _LGPL_SOURCE
  51
  52 #ifndef MAP_ANONYMOUS
  53 #define MAP_ANONYMOUS MAP_ANON
  54 #endif
  55
  56 #ifdef __linux__
  57 static
  58 void *mremap_wrapper(void *old_address, size_t old_size,
  59                 size_t new_size, int flags)
  60 {
  61         return mremap(old_address, old_size, new_size, flags);
  62 }
  63 #else
  64
  65 #define MREMAP_MAYMOVE  1
  66 #define MREMAP_FIXED    2
  67
  68 /*
  69  * mremap wrapper for non-Linux systems not allowing MAYMOVE.
  70  * This is not generic.
  71 */
  72 static
  73 void *mremap_wrapper(void *old_address, size_t old_size,
  74                 size_t new_size, int flags)
  75 {
  76         assert(!(flags & MREMAP_MAYMOVE));
  77
  78         return MAP_FAILED;
  79 }
  80 #endif
  81
  82 /* Sleep delay in ms */
  83 #define RCU_SLEEP_DELAY_MS      10
  84 #define INIT_NR_THREADS         8
  85 #define ARENA_INIT_ALLOC                \
  86         sizeof(struct registry_chunk)   \
  87         + INIT_NR_THREADS * sizeof(struct rcu_reader)
  88
  89 /*
  90  * Active attempts to check for reader Q.S. before calling sleep().
  91  */
  92 #define RCU_QS_ACTIVE_ATTEMPTS 100
  93
  94 static
  95 int rcu_bp_refcount;
  96
  97 static
  98 void __attribute__((constructor)) rcu_bp_init(void);
  99 static
 100 void __attribute__((destructor)) rcu_bp_exit(void);
 101
 102 static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
 103
 104 static pthread_mutex_t init_lock = PTHREAD_MUTEX_INITIALIZER;
 105 static int initialized;
 106
 107 static pthread_key_t urcu_bp_key;
 108
 109 #ifdef DEBUG_YIELD
 110 unsigned int yield_active;
 111 __DEFINE_URCU_TLS_GLOBAL(unsigned int, rand_yield);
 112 #endif
 113
 114 /*
 115  * Global grace period counter.
 116  * Contains the current RCU_GP_CTR_PHASE.
 117  * Also has a RCU_GP_COUNT of 1, to accelerate the reader fast path.
 118  * Written to only by writer with mutex taken. Read by both writer and readers.
 119  */
 120 long rcu_gp_ctr = RCU_GP_COUNT;
 121
 122 /*
 123  * Pointer to registry elements. Written to only by each individual reader. Read
 124  * by both the reader and the writers.
 125  */
 126 __DEFINE_URCU_TLS_GLOBAL(struct rcu_reader *, rcu_reader);
 127
 128 static CDS_LIST_HEAD(registry);
 129
 130 struct registry_chunk {
 131         size_t data_len;                /* data length */
 132         size_t used;                    /* amount of data used */
 133         struct cds_list_head node;      /* chunk_list node */
 134         char data[];
 135 };
 136
 137 struct registry_arena {
 138         struct cds_list_head chunk_list;
 139 };
 140
 141 static struct registry_arena registry_arena = {
 142         .chunk_list = CDS_LIST_HEAD_INIT(registry_arena.chunk_list),
 143 };
 144
 145 /* Saved fork signal mask, protected by rcu_gp_lock */
 146 static sigset_t saved_fork_signal_mask;
 147
 148 static void mutex_lock(pthread_mutex_t *mutex)
 149 {
 150         int ret;
 151
 152 #ifndef DISTRUST_SIGNALS_EXTREME
 153         ret = pthread_mutex_lock(mutex);
 154         if (ret)
 155                 urcu_die(ret);
 156 #else /* #ifndef DISTRUST_SIGNALS_EXTREME */
 157         while ((ret = pthread_mutex_trylock(mutex)) != 0) {
 158                 if (ret != EBUSY && ret != EINTR)
 159                         urcu_die(ret);
 160                 poll(NULL,0,10);
 161         }
 162 #endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
 163 }
 164
 165 static void mutex_unlock(pthread_mutex_t *mutex)
 166 {
 167         int ret;
 168
 169         ret = pthread_mutex_unlock(mutex);
 170         if (ret)
 171                 urcu_die(ret);
 172 }
 173
 174 void update_counter_and_wait(void)
 175 {
 176         CDS_LIST_HEAD(qsreaders);
 177         unsigned int wait_loops = 0;
 178         struct rcu_reader *index, *tmp;
 179
 180         /* Switch parity: 0 -> 1, 1 -> 0 */
 181         CMM_STORE_SHARED(rcu_gp_ctr, rcu_gp_ctr ^ RCU_GP_CTR_PHASE);
 182
 183         /*
 184          * Must commit qparity update to memory before waiting for other parity
 185          * quiescent state. Failure to do so could result in the writer waiting
 186          * forever while new readers are always accessing data (no progress).
 187          * Ensured by CMM_STORE_SHARED and CMM_LOAD_SHARED.
 188          */
 189
 190         /*
 191          * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
 192          * model easier to understand. It does not have a big performance impact
 193          * anyway, given this is the write-side.
 194          */
 195         cmm_smp_mb();
 196
 197         /*
 198          * Wait for each thread rcu_reader.ctr count to become 0.
 199          */
 200         for (;;) {
 201                 if (wait_loops < RCU_QS_ACTIVE_ATTEMPTS)
 202                         wait_loops++;
 203
 204                 cds_list_for_each_entry_safe(index, tmp, &registry, node) {
 205                         if (!rcu_old_gp_ongoing(&index->ctr))
 206                                 cds_list_move(&index->node, &qsreaders);
 207                 }
 208
 209                 if (cds_list_empty(&registry)) {
 210                         break;
 211                 } else {
 212                         if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS)
 213                                 (void) poll(NULL, 0, RCU_SLEEP_DELAY_MS);
 214                         else
 215                                 caa_cpu_relax();
 216                 }
 217         }
 218         /* put back the reader list in the registry */
 219         cds_list_splice(&qsreaders, &registry);
 220 }
 221
 222 void synchronize_rcu(void)
 223 {
 224         sigset_t newmask, oldmask;
 225         int ret;
 226
 227         ret = sigfillset(&newmask);
 228         assert(!ret);
 229         ret = pthread_sigmask(SIG_BLOCK, &newmask, &oldmask);
 230         assert(!ret);
 231
 232         mutex_lock(&rcu_gp_lock);
 233
 234         if (cds_list_empty(&registry))
 235                 goto out;
 236
 237         /* All threads should read qparity before accessing data structure
 238          * where new ptr points to. */
 239         /* Write new ptr before changing the qparity */
 240         cmm_smp_mb();
 241
 242         /*
 243          * Wait for previous parity to be empty of readers.
 244          */
 245         update_counter_and_wait();      /* 0 -> 1, wait readers in parity 0 */
 246
 247         /*
 248          * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
 249          * model easier to understand. It does not have a big performance impact
 250          * anyway, given this is the write-side.
 251          */
 252         cmm_smp_mb();
 253
 254         /*
 255          * Wait for previous parity to be empty of readers.
 256          */
 257         update_counter_and_wait();      /* 1 -> 0, wait readers in parity 1 */
 258
 259         /*
 260          * Finish waiting for reader threads before letting the old ptr being
 261          * freed.
 262          */
 263         cmm_smp_mb();
 264 out:
 265         mutex_unlock(&rcu_gp_lock);
 266         ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
 267         assert(!ret);
 268 }
 269
 270 /*
 271  * library wrappers to be used by non-LGPL compatible source code.
 272  */
 273
 274 void rcu_read_lock(void)
 275 {
 276         _rcu_read_lock();
 277 }
 278
 279 void rcu_read_unlock(void)
 280 {
 281         _rcu_read_unlock();
 282 }
 283
 284 /*
 285  * Only grow for now. If empty, allocate a ARENA_INIT_ALLOC sized chunk.
 286  * Else, try expanding the last chunk. If this fails, allocate a new
 287  * chunk twice as big as the last chunk.
 288  * Memory used by chunks _never_ moves. A chunk could theoretically be
 289  * freed when all "used" slots are released, but we don't do it at this
 290  * point.
 291  */
 292 static
 293 void expand_arena(struct registry_arena *arena)
 294 {
 295         struct registry_chunk *new_chunk, *last_chunk;
 296         size_t old_chunk_len, new_chunk_len;
 297
 298         /* No chunk. */
 299         if (cds_list_empty(&arena->chunk_list)) {
 300                 assert(ARENA_INIT_ALLOC >=
 301                         sizeof(struct registry_chunk)
 302                         + sizeof(struct rcu_reader));
 303                 new_chunk_len = ARENA_INIT_ALLOC;
 304                 new_chunk = mmap(NULL, new_chunk_len,
 305                         PROT_READ | PROT_WRITE,
 306                         MAP_ANONYMOUS | MAP_PRIVATE,
 307                         -1, 0);
 308                 if (new_chunk == MAP_FAILED)
 309                         abort();
 310                 bzero(new_chunk, new_chunk_len);
 311                 new_chunk->data_len =
 312                         new_chunk_len - sizeof(struct registry_chunk);
 313                 cds_list_add_tail(&new_chunk->node, &arena->chunk_list);
 314                 return;         /* We're done. */
 315         }
 316
 317         /* Try expanding last chunk. */
 318         last_chunk = cds_list_entry(arena->chunk_list.prev,
 319                 struct registry_chunk, node);
 320         old_chunk_len =
 321                 last_chunk->data_len + sizeof(struct registry_chunk);
 322         new_chunk_len = old_chunk_len << 1;
 323
 324         /* Don't allow memory mapping to move, just expand. */
 325         new_chunk = mremap_wrapper(last_chunk, old_chunk_len,
 326                 new_chunk_len, 0);
 327         if (new_chunk != MAP_FAILED) {
 328                 /* Should not have moved. */
 329                 assert(new_chunk == last_chunk);
 330                 bzero((char *) last_chunk + old_chunk_len,
 331                         new_chunk_len - old_chunk_len);
 332                 last_chunk->data_len =
 333                         new_chunk_len - sizeof(struct registry_chunk);
 334                 return;         /* We're done. */
 335         }
 336
 337         /* Remap did not succeed, we need to add a new chunk. */
 338         new_chunk = mmap(NULL, new_chunk_len,
 339                 PROT_READ | PROT_WRITE,
 340                 MAP_ANONYMOUS | MAP_PRIVATE,
 341                 -1, 0);
 342         if (new_chunk == MAP_FAILED)
 343                 abort();
 344         bzero(new_chunk, new_chunk_len);
 345         new_chunk->data_len =
 346                 new_chunk_len - sizeof(struct registry_chunk);
 347         cds_list_add_tail(&new_chunk->node, &arena->chunk_list);
 348 }
 349
 350 static
 351 struct rcu_reader *arena_alloc(struct registry_arena *arena)
 352 {
 353         struct registry_chunk *chunk;
 354         struct rcu_reader *rcu_reader_reg;
 355         int expand_done = 0;    /* Only allow to expand once per alloc */
 356         size_t len = sizeof(struct rcu_reader);
 357
 358 retry:
 359         cds_list_for_each_entry(chunk, &arena->chunk_list, node) {
 360                 if (chunk->data_len - chunk->used < len)
 361                         continue;
 362                 /* Find spot */
 363                 for (rcu_reader_reg = (struct rcu_reader *) &chunk->data[0];
 364                                 rcu_reader_reg < (struct rcu_reader *) &chunk->data[chunk->data_len];
 365                                 rcu_reader_reg++) {
 366                         if (!rcu_reader_reg->alloc) {
 367                                 rcu_reader_reg->alloc = 1;
 368                                 chunk->used += len;
 369                                 return rcu_reader_reg;
 370                         }
 371                 }
 372         }
 373
 374         if (!expand_done) {
 375                 expand_arena(arena);
 376                 expand_done = 1;
 377                 goto retry;
 378         }
 379
 380         return NULL;
 381 }
 382
 383 /* Called with signals off and mutex locked */
 384 static
 385 void add_thread(void)
 386 {
 387         struct rcu_reader *rcu_reader_reg;
 388         int ret;
 389
 390         rcu_reader_reg = arena_alloc(&registry_arena);
 391         if (!rcu_reader_reg)
 392                 abort();
 393         ret = pthread_setspecific(urcu_bp_key, rcu_reader_reg);
 394         if (ret)
 395                 abort();
 396
 397         /* Add to registry */
 398         rcu_reader_reg->tid = pthread_self();
 399         assert(rcu_reader_reg->ctr == 0);
 400         cds_list_add(&rcu_reader_reg->node, &registry);
 401         /*
 402          * Reader threads are pointing to the reader registry. This is
 403          * why its memory should never be relocated.
 404          */
 405         URCU_TLS(rcu_reader) = rcu_reader_reg;
 406 }
 407
 408 /* Called with mutex locked */
 409 static
 410 void cleanup_thread(struct registry_chunk *chunk,
 411                 struct rcu_reader *rcu_reader_reg)
 412 {
 413         rcu_reader_reg->ctr = 0;
 414         cds_list_del(&rcu_reader_reg->node);
 415         rcu_reader_reg->tid = 0;
 416         rcu_reader_reg->alloc = 0;
 417         chunk->used -= sizeof(struct rcu_reader);
 418 }
 419
 420 static
 421 struct registry_chunk *find_chunk(struct rcu_reader *rcu_reader_reg)
 422 {
 423         struct registry_chunk *chunk;
 424
 425         cds_list_for_each_entry(chunk, &registry_arena.chunk_list, node) {
 426                 if (rcu_reader_reg < (struct rcu_reader *) &chunk->data[0])
 427                         continue;
 428                 if (rcu_reader_reg >= (struct rcu_reader *) &chunk->data[chunk->data_len])
 429                         continue;
 430                 return chunk;
 431         }
 432         return NULL;
 433 }
 434
 435 /* Called with signals off and mutex locked */
 436 static
 437 void remove_thread(struct rcu_reader *rcu_reader_reg)
 438 {
 439         cleanup_thread(find_chunk(rcu_reader_reg), rcu_reader_reg);
 440         URCU_TLS(rcu_reader) = NULL;
 441 }
 442
 443 /* Disable signals, take mutex, add to registry */
 444 void rcu_bp_register(void)
 445 {
 446         sigset_t newmask, oldmask;
 447         int ret;
 448
 449         ret = sigfillset(&newmask);
 450         if (ret)
 451                 abort();
 452         ret = pthread_sigmask(SIG_BLOCK, &newmask, &oldmask);
 453         if (ret)
 454                 abort();
 455
 456         /*
 457          * Check if a signal concurrently registered our thread since
 458          * the check in rcu_read_lock().
 459          */
 460         if (URCU_TLS(rcu_reader))
 461                 goto end;
 462
 463         /*
 464          * Take care of early registration before urcu_bp constructor.
 465          */
 466         rcu_bp_init();
 467
 468         mutex_lock(&rcu_gp_lock);
 469         add_thread();
 470         mutex_unlock(&rcu_gp_lock);
 471 end:
 472         ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
 473         if (ret)
 474                 abort();
 475 }
 476
 477 /* Disable signals, take mutex, remove from registry */
 478 static
 479 void rcu_bp_unregister(struct rcu_reader *rcu_reader_reg)
 480 {
 481         sigset_t newmask, oldmask;
 482         int ret;
 483
 484         ret = sigfillset(&newmask);
 485         if (ret)
 486                 abort();
 487         ret = pthread_sigmask(SIG_BLOCK, &newmask, &oldmask);
 488         if (ret)
 489                 abort();
 490
 491         mutex_lock(&rcu_gp_lock);
 492         remove_thread(rcu_reader_reg);
 493         mutex_unlock(&rcu_gp_lock);
 494         ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
 495         if (ret)
 496                 abort();
 497         rcu_bp_exit();
 498 }
 499
 500 /*
 501  * Remove thread from the registry when it exits, and flag it as
 502  * destroyed so garbage collection can take care of it.
 503  */
 504 static
 505 void urcu_bp_thread_exit_notifier(void *rcu_key)
 506 {
 507         rcu_bp_unregister(rcu_key);
 508 }
 509
 510 static
 511 void rcu_bp_init(void)
 512 {
 513         mutex_lock(&init_lock);
 514         if (!rcu_bp_refcount++) {
 515                 int ret;
 516
 517                 ret = pthread_key_create(&urcu_bp_key,
 518                                 urcu_bp_thread_exit_notifier);
 519                 if (ret)
 520                         abort();
 521                 initialized = 1;
 522         }
 523         mutex_unlock(&init_lock);
 524 }
 525
 526 static
 527 void rcu_bp_exit(void)
 528 {
 529         mutex_lock(&init_lock);
 530         if (!--rcu_bp_refcount) {
 531                 struct registry_chunk *chunk, *tmp;
 532                 int ret;
 533
 534                 cds_list_for_each_entry_safe(chunk, tmp,
 535                                 &registry_arena.chunk_list, node) {
 536                         munmap(chunk, chunk->data_len
 537                                         + sizeof(struct registry_chunk));
 538                 }
 539                 ret = pthread_key_delete(urcu_bp_key);
 540                 if (ret)
 541                         abort();
 542         }
 543         mutex_unlock(&init_lock);
 544 }
 545
 546 /*
 547  * Holding the rcu_gp_lock across fork will make sure we fork() don't race with
 548  * a concurrent thread executing with this same lock held. This ensures that the
 549  * registry is in a coherent state in the child.
 550  */
 551 void rcu_bp_before_fork(void)
 552 {
 553         sigset_t newmask, oldmask;
 554         int ret;
 555
 556         ret = sigfillset(&newmask);
 557         assert(!ret);
 558         ret = pthread_sigmask(SIG_BLOCK, &newmask, &oldmask);
 559         assert(!ret);
 560         mutex_lock(&rcu_gp_lock);
 561         saved_fork_signal_mask = oldmask;
 562 }
 563
 564 void rcu_bp_after_fork_parent(void)
 565 {
 566         sigset_t oldmask;
 567         int ret;
 568
 569         oldmask = saved_fork_signal_mask;
 570         mutex_unlock(&rcu_gp_lock);
 571         ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
 572         assert(!ret);
 573 }
 574
 575 /*
 576  * Prune all entries from registry except our own thread. Fits the Linux
 577  * fork behavior. Called with rcu_gp_lock held.
 578  */
 579 static
 580 void urcu_bp_prune_registry(void)
 581 {
 582         struct registry_chunk *chunk;
 583         struct rcu_reader *rcu_reader_reg;
 584
 585         cds_list_for_each_entry(chunk, &registry_arena.chunk_list, node) {
 586                 for (rcu_reader_reg = (struct rcu_reader *) &chunk->data[0];
 587                                 rcu_reader_reg < (struct rcu_reader *) &chunk->data[chunk->data_len];
 588                                 rcu_reader_reg++) {
 589                         if (!rcu_reader_reg->alloc)
 590                                 continue;
 591                         if (rcu_reader_reg->tid == pthread_self())
 592                                 continue;
 593                         cleanup_thread(chunk, rcu_reader_reg);
 594                 }
 595         }
 596 }
 597
 598 void rcu_bp_after_fork_child(void)
 599 {
 600         sigset_t oldmask;
 601         int ret;
 602
 603         urcu_bp_prune_registry();
 604         oldmask = saved_fork_signal_mask;
 605         mutex_unlock(&rcu_gp_lock);
 606         ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
 607         assert(!ret);
 608 }
 609
 610 void *rcu_dereference_sym_bp(void *p)
 611 {
 612         return _rcu_dereference(p);
 613 }
 614
 615 void *rcu_set_pointer_sym_bp(void **p, void *v)
 616 {
 617         cmm_wmb();
 618         uatomic_set(p, v);
 619         return v;
 620 }
 621
 622 void *rcu_xchg_pointer_sym_bp(void **p, void *v)
 623 {
 624         cmm_wmb();
 625         return uatomic_xchg(p, v);
 626 }
 627
 628 void *rcu_cmpxchg_pointer_sym_bp(void **p, void *old, void *_new)
 629 {
 630         cmm_wmb();
 631         return uatomic_cmpxchg(p, old, _new);
 632 }
 633
 634 DEFINE_RCU_FLAVOR(rcu_flavor);
 635
 636 #include "urcu-call-rcu-impl.h"
 637 #include "urcu-defer-impl.h"