2 * Copyright (c) 2014 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
20 /* Read-Copy-Update (RCU)
21 * ======================
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.
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
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().
48 * The following functions manage the recognition of quiescent states:
50 * void ovsrcu_quiesce(void)
52 * Recognizes a momentary quiescent state in the current thread.
54 * void ovsrcu_quiesce_start(void)
55 * void ovsrcu_quiesce_end(void)
57 * Brackets a time period during which the current thread is quiescent.
59 * A newly created thread is initially active, not quiescent.
61 * When a quiescient state has occurred in every thread, we say that a "grace
62 * period" has occurred. Following a grace period, all of the callbacks
63 * postponed before the start of the grace period may be invoked. OVS takes
64 * care of this automatically through the RCU mechanism: while a process still
65 * has only a single thread, it invokes the postponed callbacks directly from
66 * ovsrcu_quiesce() and ovsrcu_quiesce_start(); after additional threads have
67 * been created, it creates an extra helper thread to invoke callbacks.
73 * Use OVSRCU_TYPE(TYPE) to declare a pointer to RCU-protected data, e.g. the
74 * following declares an RCU-protected "struct flow *" named flowp:
76 * OVSRCU_TYPE(struct flow *) flowp;
78 * Use ovsrcu_get(TYPE, VAR) to read an RCU-protected pointer, e.g. to read the
79 * pointer variable declared above:
81 * struct flow *flow = ovsrcu_get(struct flow *, &flowp);
83 * If the pointer variable is currently protected against change (because
84 * the current thread holds a mutex that protects it), ovsrcu_get_protected()
85 * may be used instead. Only on the Alpha architecture is this likely to
86 * generate different code, but it may be useful documentation.
88 * (With GNU C or Clang, you get a compiler error if TYPE is wrong; other
89 * compilers will merrily carry along accepting the wrong type.)
91 * Use ovsrcu_set() to write an RCU-protected pointer and ovsrcu_postpone() to
92 * free the previous data. ovsrcu_init() can be used on (newly created) RCU-
93 * protected pointer that is not yet visible to the readers. If more than one
94 * thread can write the pointer, then some form of external synchronization,
95 * e.g. a mutex, is needed to prevent writers from interfering with one
96 * another. For example, to write the pointer variable declared above while
97 * safely freeing the old value:
99 * static struct ovs_mutex mutex = OVS_MUTEX_INITIALIZER;
101 * OVSRCU_TYPE(struct flow *) flowp;
104 * change_flow(struct flow *new_flow)
106 * ovs_mutex_lock(&mutex);
107 * ovsrcu_postpone(free,
108 * ovsrcu_get_protected(struct flow *, &flowp));
109 * ovsrcu_set(&flowp, new_flow);
110 * ovs_mutex_unlock(&mutex);
115 #include "compiler.h"
116 #include "ovs-atomic.h"
119 #define OVSRCU_TYPE(TYPE) struct { ATOMIC(TYPE) p; }
120 #define OVSRCU_TYPE_INITIALIZER { NULL }
121 #define ovsrcu_get__(TYPE, VAR, ORDER) \
125 atomic_read_explicit(CONST_CAST(ATOMIC(TYPE) *, &(VAR)->p), \
130 #define ovsrcu_get(TYPE, VAR) \
131 CONST_CAST(TYPE, ovsrcu_get__(TYPE, VAR, memory_order_consume))
132 #define ovsrcu_get_protected(TYPE, VAR) \
133 CONST_CAST(TYPE, ovsrcu_get__(TYPE, VAR, memory_order_relaxed))
134 #else /* not GNU C */
135 typedef struct ovsrcu_pointer { ATOMIC(void *) p; };
136 #define OVSRCU_TYPE(TYPE) struct ovsrcu_pointer
137 #define OVSRCU_TYPE_INITIALIZER { NULL }
139 ovsrcu_get__(const struct ovsrcu_pointer *pointer, memory_order order)
142 atomic_read_explicit(&CONST_CAST(struct ovsrcu_pointer *, pointer)->p,
146 #define ovsrcu_get(TYPE, VAR) \
147 CONST_CAST(TYPE, ovsrcu_get__(VAR, memory_order_consume))
148 #define ovsrcu_get_protected(TYPE, VAR) \
149 CONST_CAST(TYPE, ovsrcu_get__(VAR, memory_order_relaxed))
152 /* Writes VALUE to the RCU-protected pointer whose address is VAR.
154 * Users require external synchronization (e.g. a mutex). See "Usage" above
156 #define ovsrcu_set(VAR, VALUE) \
157 atomic_store_explicit(&(VAR)->p, VALUE, memory_order_release)
159 /* This can be used for initializing RCU pointers before any readers can
160 * see them. A later ovsrcu_set() needs to make the bigger structure this
161 * is part of visible to the readers. */
162 #define ovsrcu_init(VAR, VALUE) \
163 atomic_store_explicit(&(VAR)->p, VALUE, memory_order_relaxed)
165 /* Calls FUNCTION passing ARG as its pointer-type argument following the next
166 * grace period. See "Usage" above for example. */
167 void ovsrcu_postpone__(void (*function)(void *aux), void *aux);
168 #define ovsrcu_postpone(FUNCTION, ARG) \
169 ((void) sizeof((FUNCTION)(ARG), 1), \
170 (void) sizeof(*(ARG)), \
171 ovsrcu_postpone__((void (*)(void *))(FUNCTION), ARG))
173 /* Quiescent states. */
174 void ovsrcu_quiesce_start(void);
175 void ovsrcu_quiesce_end(void);
176 void ovsrcu_quiesce(void);
177 bool ovsrcu_is_quiescent(void);
179 #endif /* ovs-rcu.h */