lib/ovs-rcu.h

   1 /*
   2  * Copyright (c) 2014, 2015, 2016 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef OVS_RCU_H
  18 #define OVS_RCU_H 1
  19
  20 /* Read-Copy-Update (RCU)
  21  * ======================
  22  *
  23  * Introduction
  24  * ------------
  25  *
  26  * Atomic pointer access makes it pretty easy to implement lock-free
  27  * algorithms.  There is one big problem, though: when a writer updates a
  28  * pointer to point to a new data structure, some thread might be reading the
  29  * old version, and there's no convenient way to free the old version when all
  30  * threads are done with the old version.
  31  *
  32  * The function ovsrcu_postpone() solves that problem.  The function pointer
  33  * passed in as its argument is called only after all threads are done with old
  34  * versions of data structures.  The function callback frees an old version of
  35  * data no longer in use.  This technique is called "read-copy-update", or RCU
  36  * for short.
  37  *
  38  *
  39  * Details
  40  * -------
  41  *
  42  * A "quiescent state" is a time at which a thread holds no pointers to memory
  43  * that is managed by RCU; that is, when the thread is known not to reference
  44  * memory that might be an old version of some object freed via RCU.  For
  45  * example, poll_block() includes a quiescent state, as does
  46  * ovs_mutex_cond_wait().
  47  *
  48  * The following functions manage the recognition of quiescent states:
  49  *
  50  *     void ovsrcu_quiesce(void)
  51  *
  52  *         Recognizes a momentary quiescent state in the current thread.
  53  *
  54  *     void ovsrcu_quiesce_start(void)
  55  *     void ovsrcu_quiesce_end(void)
  56  *
  57  *         Brackets a time period during which the current thread is quiescent.
  58  *
  59  * A newly created thread is initially active, not quiescent. When a process
  60  * becomes multithreaded, the main thread becomes active, not quiescent.
  61  *
  62  * When a quiescient state has occurred in every thread, we say that a "grace
  63  * period" has occurred.  Following a grace period, all of the callbacks
  64  * postponed before the start of the grace period MAY be invoked.  OVS takes
  65  * care of this automatically through the RCU mechanism: while a process still
  66  * has only a single thread, it invokes the postponed callbacks directly from
  67  * ovsrcu_quiesce() and ovsrcu_quiesce_start(); after additional threads have
  68  * been created, it creates an extra helper thread to invoke callbacks.
  69  *
  70  * Please note that while a postponed function call is guaranteed to happen
  71  * after the next time all participating threads have quiesced at least once,
  72  * there is no quarantee that all postponed functions are called as early as
  73  * possible, or that the functions postponed by different threads would be
  74  * called in the order the registrations took place.  In particular, even if
  75  * two threads provably postpone a function each in a specific order, the
  76  * postponed functions may still be called in the opposite order, depending on
  77  * the timing of when the threads call ovsrcu_quiesce(), how many functions
  78  * they postpone, and when the ovs-rcu thread happens to grab the functions to
  79  * be called.
  80  *
  81  * All functions postponed by a single thread are guaranteed to execute in the
  82  * order they were postponed, however.
  83  *
  84  * Usage
  85  * -----
  86  *
  87  * Use OVSRCU_TYPE(TYPE) to declare a pointer to RCU-protected data, e.g. the
  88  * following declares an RCU-protected "struct flow *" named flowp:
  89  *
  90  *     OVSRCU_TYPE(struct flow *) flowp;
  91  *
  92  * Use ovsrcu_get(TYPE, VAR) to read an RCU-protected pointer, e.g. to read the
  93  * pointer variable declared above:
  94  *
  95  *     struct flow *flow = ovsrcu_get(struct flow *, &flowp);
  96  *
  97  * If the pointer variable is currently protected against change (because
  98  * the current thread holds a mutex that protects it), ovsrcu_get_protected()
  99  * may be used instead.  Only on the Alpha architecture is this likely to
 100  * generate different code, but it may be useful documentation.
 101  *
 102  * (With GNU C or Clang, you get a compiler error if TYPE is wrong; other
 103  * compilers will merrily carry along accepting the wrong type.)
 104  *
 105  * Use ovsrcu_set() to write an RCU-protected pointer and ovsrcu_postpone() to
 106  * free the previous data.  ovsrcu_set_hidden() can be used on RCU protected
 107  * data not visible to any readers yet, but will be made visible by a later
 108  * ovsrcu_set().   ovsrcu_init() can be used to initialize RCU pointers when
 109  * no readers are yet executing.  If more than one thread can write the
 110  * pointer, then some form of external synchronization, e.g. a mutex, is
 111  * needed to prevent writers from interfering with one another.  For example,
 112  * to write the pointer variable declared above while safely freeing the old
 113  * value:
 114  *
 115  *     static struct ovs_mutex mutex = OVS_MUTEX_INITIALIZER;
 116  *
 117  *     OVSRCU_TYPE(struct flow *) flowp;
 118  *
 119  *     void
 120  *     change_flow(struct flow *new_flow)
 121  *     {
 122  *         ovs_mutex_lock(&mutex);
 123  *         ovsrcu_postpone(free,
 124  *                         ovsrcu_get_protected(struct flow *, &flowp));
 125  *         ovsrcu_set(&flowp, new_flow);
 126  *         ovs_mutex_unlock(&mutex);
 127  *     }
 128  *
 129  */
 130
 131 #include "compiler.h"
 132 #include "ovs-atomic.h"
 133
 134 #if __GNUC__
 135 #define OVSRCU_TYPE(TYPE) struct { ATOMIC(TYPE) p; }
 136 #define OVSRCU_INITIALIZER(VALUE) { ATOMIC_VAR_INIT(VALUE) }
 137 #define ovsrcu_get__(TYPE, VAR, ORDER)                                  \
 138     ({                                                                  \
 139         TYPE value__;                                                   \
 140         typeof(VAR) ovsrcu_var = (VAR);                                 \
 141                                                                         \
 142         atomic_read_explicit(CONST_CAST(ATOMIC(TYPE) *, &ovsrcu_var->p), \
 143                              &value__, ORDER);                          \
 144                                                                         \
 145         value__;                                                        \
 146     })
 147 #define ovsrcu_get(TYPE, VAR) \
 148     ovsrcu_get__(TYPE, VAR, memory_order_consume)
 149 #define ovsrcu_get_protected(TYPE, VAR) \
 150     ovsrcu_get__(TYPE, VAR, memory_order_relaxed)
 151
 152 /* 'VALUE' may be an atomic operation, which must be evaluated before
 153  * any of the body of the atomic_store_explicit.  Since the type of
 154  * 'VAR' is not fixed, we cannot use an inline function to get
 155  * function semantics for this. */
 156 #define ovsrcu_set__(VAR, VALUE, ORDER)                                 \
 157     ({                                                                  \
 158         typeof(VAR) ovsrcu_var = (VAR);                                 \
 159         typeof(VALUE) ovsrcu_value = (VALUE);                           \
 160         memory_order ovsrcu_order = (ORDER);                            \
 161                                                                         \
 162         atomic_store_explicit(&ovsrcu_var->p, ovsrcu_value, ovsrcu_order); \
 163         (void *) 0;                                                     \
 164     })
 165 #else  /* not GNU C */
 166 struct ovsrcu_pointer { ATOMIC(void *) p; };
 167 #define OVSRCU_TYPE(TYPE) struct ovsrcu_pointer
 168 #define OVSRCU_INITIALIZER(VALUE) { ATOMIC_VAR_INIT(VALUE) }
 169 static inline void *
 170 ovsrcu_get__(const struct ovsrcu_pointer *pointer, memory_order order)
 171 {
 172     void *value;
 173     atomic_read_explicit(&CONST_CAST(struct ovsrcu_pointer *, pointer)->p,
 174                          &value, order);
 175     return value;
 176 }
 177 #define ovsrcu_get(TYPE, VAR) \
 178     CONST_CAST(TYPE, ovsrcu_get__(VAR, memory_order_consume))
 179 #define ovsrcu_get_protected(TYPE, VAR) \
 180     CONST_CAST(TYPE, ovsrcu_get__(VAR, memory_order_relaxed))
 181
 182 static inline void ovsrcu_set__(struct ovsrcu_pointer *pointer,
 183                                 const void *value,
 184                                 memory_order order)
 185 {
 186     atomic_store_explicit(&pointer->p, CONST_CAST(void *, value), order);
 187 }
 188 #endif
 189
 190 /* Writes VALUE to the RCU-protected pointer whose address is VAR.
 191  *
 192  * Users require external synchronization (e.g. a mutex).  See "Usage" above
 193  * for an example. */
 194 #define ovsrcu_set(VAR, VALUE) \
 195     ovsrcu_set__(VAR, VALUE, memory_order_release)
 196
 197 /* This can be used for initializing RCU pointers before any readers can
 198  * see them.  A later ovsrcu_set() needs to make the bigger structure this
 199  * is part of visible to the readers. */
 200 #define ovsrcu_set_hidden(VAR, VALUE) \
 201     ovsrcu_set__(VAR, VALUE, memory_order_relaxed)
 202
 203 /* This can be used for initializing RCU pointers before any readers are
 204  * executing. */
 205 #define ovsrcu_init(VAR, VALUE) atomic_init(&(VAR)->p, VALUE)
 206
 207 /* Calls FUNCTION passing ARG as its pointer-type argument following the next
 208  * grace period.  See "Usage" above for an example. */
 209 void ovsrcu_postpone__(void (*function)(void *aux), void *aux);
 210 #define ovsrcu_postpone(FUNCTION, ARG)                          \
 211     (/* Verify that ARG is appropriate for FUNCTION. */         \
 212      (void) sizeof((FUNCTION)(ARG), 1),                         \
 213      /* Verify that ARG is a pointer type. */                   \
 214      (void) sizeof(*(ARG)),                                     \
 215      ovsrcu_postpone__((void (*)(void *))(FUNCTION), ARG))
 216
 217 /* Quiescent states. */
 218 void ovsrcu_quiesce_start(void);
 219 void ovsrcu_quiesce_end(void);
 220 void ovsrcu_quiesce(void);
 221 bool ovsrcu_is_quiescent(void);
 222
 223 /* Synchronization.  Waits for all non-quiescent threads to quiesce at least
 224  * once.  This can block for a relatively long time. */
 225 void ovsrcu_synchronize(void);
 226
 227 #endif /* ovs-rcu.h */