util/rcu.c

   1 /*
   2  * urcu-mb.c
   3  *
   4  * Userspace RCU library with explicit memory barriers
   5  *
   6  * Copyright (c) 2009 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   7  * Copyright (c) 2009 Paul E. McKenney, IBM Corporation.
   8  * Copyright 2015 Red Hat, Inc.
   9  *
  10  * Ported to QEMU by Paolo Bonzini  <pbonzini@redhat.com>
  11  *
  12  * This library is free software; you can redistribute it and/or
  13  * modify it under the terms of the GNU Lesser General Public
  14  * License as published by the Free Software Foundation; either
  15  * version 2.1 of the License, or (at your option) any later version.
  16  *
  17  * This library is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20  * Lesser General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Lesser General Public
  23  * License along with this library; if not, write to the Free Software
  24  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  25  *
  26  * IBM's contributions to this file may be relicensed under LGPLv2 or later.
  27  */
  28
  29 #include "qemu/osdep.h"
  30 #include "qemu-common.h"
  31 #include "qemu/rcu.h"
  32 #include "qemu/atomic.h"
  33 #include "qemu/thread.h"
  34 #include "qemu/main-loop.h"
  35
  36 /*
  37  * Global grace period counter.  Bit 0 is always one in rcu_gp_ctr.
  38  * Bits 1 and above are defined in synchronize_rcu.
  39  */
  40 #define RCU_GP_LOCKED           (1UL << 0)
  41 #define RCU_GP_CTR              (1UL << 1)
  42
  43 unsigned long rcu_gp_ctr = RCU_GP_LOCKED;
  44
  45 QemuEvent rcu_gp_event;
  46 static QemuMutex rcu_registry_lock;
  47 static QemuMutex rcu_sync_lock;
  48
  49 /*
  50  * Check whether a quiescent state was crossed between the beginning of
  51  * update_counter_and_wait and now.
  52  */
  53 static inline int rcu_gp_ongoing(unsigned long *ctr)
  54 {
  55     unsigned long v;
  56
  57     v = atomic_read(ctr);
  58     return v && (v != rcu_gp_ctr);
  59 }
  60
  61 /* Written to only by each individual reader. Read by both the reader and the
  62  * writers.
  63  */
  64 __thread struct rcu_reader_data rcu_reader;
  65
  66 /* Protected by rcu_registry_lock.  */
  67 typedef QLIST_HEAD(, rcu_reader_data) ThreadList;
  68 static ThreadList registry = QLIST_HEAD_INITIALIZER(registry);
  69
  70 /* Wait for previous parity/grace period to be empty of readers.  */
  71 static void wait_for_readers(void)
  72 {
  73     ThreadList qsreaders = QLIST_HEAD_INITIALIZER(qsreaders);
  74     struct rcu_reader_data *index, *tmp;
  75
  76     for (;;) {
  77         /* We want to be notified of changes made to rcu_gp_ongoing
  78          * while we walk the list.
  79          */
  80         qemu_event_reset(&rcu_gp_event);
  81
  82         /* Instead of using atomic_mb_set for index->waiting, and
  83          * atomic_mb_read for index->ctr, memory barriers are placed
  84          * manually since writes to different threads are independent.
  85          * atomic_mb_set has a smp_wmb before...
  86          */
  87         smp_wmb();
  88         QLIST_FOREACH(index, &registry, node) {
  89             atomic_set(&index->waiting, true);
  90         }
  91
  92         /* ... and a smp_mb after.  */
  93         smp_mb();
  94
  95         QLIST_FOREACH_SAFE(index, &registry, node, tmp) {
  96             if (!rcu_gp_ongoing(&index->ctr)) {
  97                 QLIST_REMOVE(index, node);
  98                 QLIST_INSERT_HEAD(&qsreaders, index, node);
  99
 100                 /* No need for mb_set here, worst of all we
 101                  * get some extra futex wakeups.
 102                  */
 103                 atomic_set(&index->waiting, false);
 104             }
 105         }
 106
 107         /* atomic_mb_read has smp_rmb after.  */
 108         smp_rmb();
 109
 110         if (QLIST_EMPTY(&registry)) {
 111             break;
 112         }
 113
 114         /* Wait for one thread to report a quiescent state and try again.
 115          * Release rcu_registry_lock, so rcu_(un)register_thread() doesn't
 116          * wait too much time.
 117          *
 118          * rcu_register_thread() may add nodes to &registry; it will not
 119          * wake up synchronize_rcu, but that is okay because at least another
 120          * thread must exit its RCU read-side critical section before
 121          * synchronize_rcu is done.  The next iteration of the loop will
 122          * move the new thread's rcu_reader from &registry to &qsreaders,
 123          * because rcu_gp_ongoing() will return false.
 124          *
 125          * rcu_unregister_thread() may remove nodes from &qsreaders instead
 126          * of &registry if it runs during qemu_event_wait.  That's okay;
 127          * the node then will not be added back to &registry by QLIST_SWAP
 128          * below.  The invariant is that the node is part of one list when
 129          * rcu_registry_lock is released.
 130          */
 131         qemu_mutex_unlock(&rcu_registry_lock);
 132         qemu_event_wait(&rcu_gp_event);
 133         qemu_mutex_lock(&rcu_registry_lock);
 134     }
 135
 136     /* put back the reader list in the registry */
 137     QLIST_SWAP(&registry, &qsreaders, node);
 138 }
 139
 140 void synchronize_rcu(void)
 141 {
 142     qemu_mutex_lock(&rcu_sync_lock);
 143     qemu_mutex_lock(&rcu_registry_lock);
 144
 145     if (!QLIST_EMPTY(&registry)) {
 146         /* In either case, the atomic_mb_set below blocks stores that free
 147          * old RCU-protected pointers.
 148          */
 149         if (sizeof(rcu_gp_ctr) < 8) {
 150             /* For architectures with 32-bit longs, a two-subphases algorithm
 151              * ensures we do not encounter overflow bugs.
 152              *
 153              * Switch parity: 0 -> 1, 1 -> 0.
 154              */
 155             atomic_mb_set(&rcu_gp_ctr, rcu_gp_ctr ^ RCU_GP_CTR);
 156             wait_for_readers();
 157             atomic_mb_set(&rcu_gp_ctr, rcu_gp_ctr ^ RCU_GP_CTR);
 158         } else {
 159             /* Increment current grace period.  */
 160             atomic_mb_set(&rcu_gp_ctr, rcu_gp_ctr + RCU_GP_CTR);
 161         }
 162
 163         wait_for_readers();
 164     }
 165
 166     qemu_mutex_unlock(&rcu_registry_lock);
 167     qemu_mutex_unlock(&rcu_sync_lock);
 168 }
 169
 170
 171 #define RCU_CALL_MIN_SIZE        30
 172
 173 /* Multi-producer, single-consumer queue based on urcu/static/wfqueue.h
 174  * from liburcu.  Note that head is only used by the consumer.
 175  */
 176 static struct rcu_head dummy;
 177 static struct rcu_head *head = &dummy, **tail = &dummy.next;
 178 static int rcu_call_count;
 179 static QemuEvent rcu_call_ready_event;
 180
 181 static void enqueue(struct rcu_head *node)
 182 {
 183     struct rcu_head **old_tail;
 184
 185     node->next = NULL;
 186     old_tail = atomic_xchg(&tail, &node->next);
 187     atomic_mb_set(old_tail, node);
 188 }
 189
 190 static struct rcu_head *try_dequeue(void)
 191 {
 192     struct rcu_head *node, *next;
 193
 194 retry:
 195     /* Test for an empty list, which we do not expect.  Note that for
 196      * the consumer head and tail are always consistent.  The head
 197      * is consistent because only the consumer reads/writes it.
 198      * The tail, because it is the first step in the enqueuing.
 199      * It is only the next pointers that might be inconsistent.
 200      */
 201     if (head == &dummy && atomic_mb_read(&tail) == &dummy.next) {
 202         abort();
 203     }
 204
 205     /* If the head node has NULL in its next pointer, the value is
 206      * wrong and we need to wait until its enqueuer finishes the update.
 207      */
 208     node = head;
 209     next = atomic_mb_read(&head->next);
 210     if (!next) {
 211         return NULL;
 212     }
 213
 214     /* Since we are the sole consumer, and we excluded the empty case
 215      * above, the queue will always have at least two nodes: the
 216      * dummy node, and the one being removed.  So we do not need to update
 217      * the tail pointer.
 218      */
 219     head = next;
 220
 221     /* If we dequeued the dummy node, add it back at the end and retry.  */
 222     if (node == &dummy) {
 223         enqueue(node);
 224         goto retry;
 225     }
 226
 227     return node;
 228 }
 229
 230 static void *call_rcu_thread(void *opaque)
 231 {
 232     struct rcu_head *node;
 233
 234     rcu_register_thread();
 235
 236     for (;;) {
 237         int tries = 0;
 238         int n = atomic_read(&rcu_call_count);
 239
 240         /* Heuristically wait for a decent number of callbacks to pile up.
 241          * Fetch rcu_call_count now, we only must process elements that were
 242          * added before synchronize_rcu() starts.
 243          */
 244         while (n == 0 || (n < RCU_CALL_MIN_SIZE && ++tries <= 5)) {
 245             g_usleep(10000);
 246             if (n == 0) {
 247                 qemu_event_reset(&rcu_call_ready_event);
 248                 n = atomic_read(&rcu_call_count);
 249                 if (n == 0) {
 250                     qemu_event_wait(&rcu_call_ready_event);
 251                 }
 252             }
 253             n = atomic_read(&rcu_call_count);
 254         }
 255
 256         atomic_sub(&rcu_call_count, n);
 257         synchronize_rcu();
 258         qemu_mutex_lock_iothread();
 259         while (n > 0) {
 260             node = try_dequeue();
 261             while (!node) {
 262                 qemu_mutex_unlock_iothread();
 263                 qemu_event_reset(&rcu_call_ready_event);
 264                 node = try_dequeue();
 265                 if (!node) {
 266                     qemu_event_wait(&rcu_call_ready_event);
 267                     node = try_dequeue();
 268                 }
 269                 qemu_mutex_lock_iothread();
 270             }
 271
 272             n--;
 273             node->func(node);
 274         }
 275         qemu_mutex_unlock_iothread();
 276     }
 277     abort();
 278 }
 279
 280 void call_rcu1(struct rcu_head *node, void (*func)(struct rcu_head *node))
 281 {
 282     node->func = func;
 283     enqueue(node);
 284     atomic_inc(&rcu_call_count);
 285     qemu_event_set(&rcu_call_ready_event);
 286 }
 287
 288 void rcu_register_thread(void)
 289 {
 290     assert(rcu_reader.ctr == 0);
 291     qemu_mutex_lock(&rcu_registry_lock);
 292     QLIST_INSERT_HEAD(&registry, &rcu_reader, node);
 293     qemu_mutex_unlock(&rcu_registry_lock);
 294 }
 295
 296 void rcu_unregister_thread(void)
 297 {
 298     qemu_mutex_lock(&rcu_registry_lock);
 299     QLIST_REMOVE(&rcu_reader, node);
 300     qemu_mutex_unlock(&rcu_registry_lock);
 301 }
 302
 303 static void rcu_init_complete(void)
 304 {
 305     QemuThread thread;
 306
 307     qemu_mutex_init(&rcu_registry_lock);
 308     qemu_mutex_init(&rcu_sync_lock);
 309     qemu_event_init(&rcu_gp_event, true);
 310
 311     qemu_event_init(&rcu_call_ready_event, false);
 312
 313     /* The caller is assumed to have iothread lock, so the call_rcu thread
 314      * must have been quiescent even after forking, just recreate it.
 315      */
 316     qemu_thread_create(&thread, "call_rcu", call_rcu_thread,
 317                        NULL, QEMU_THREAD_DETACHED);
 318
 319     rcu_register_thread();
 320 }
 321
 322 #ifdef CONFIG_POSIX
 323 static void rcu_init_lock(void)
 324 {
 325     qemu_mutex_lock(&rcu_sync_lock);
 326     qemu_mutex_lock(&rcu_registry_lock);
 327 }
 328
 329 static void rcu_init_unlock(void)
 330 {
 331     qemu_mutex_unlock(&rcu_registry_lock);
 332     qemu_mutex_unlock(&rcu_sync_lock);
 333 }
 334 #endif
 335
 336 void rcu_after_fork(void)
 337 {
 338     memset(&registry, 0, sizeof(registry));
 339     rcu_init_complete();
 340 }
 341
 342 static void __attribute__((__constructor__)) rcu_init(void)
 343 {
 344 #ifdef CONFIG_POSIX
 345     pthread_atfork(rcu_init_lock, rcu_init_unlock, rcu_init_unlock);
 346 #endif
 347     rcu_init_complete();
 348 }