lib/hash.h: fix hash_2words
[sliver-openvswitch.git] / lib / ovs-rcu.h
1 /*
2  * Copyright (c) 2014 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.
60  *
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.
68  *
69  *
70  * Use
71  * ---
72  *
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:
75  *
76  *     OVSRCU_TYPE(struct flow *) flowp;
77  *
78  * Use ovsrcu_get(TYPE, VAR) to read an RCU-protected pointer, e.g. to read the
79  * pointer variable declared above:
80  *
81  *     struct flow *flow = ovsrcu_get(struct flow *, flowp);
82  *
83  * Use ovsrcu_set() to write an RCU-protected pointer and ovsrcu_postpone() to
84  * free the previous data.  If more than one thread can write the pointer, then
85  * some form of external synchronization, e.g. a mutex, is needed to prevent
86  * writers from interfering with one another.  For example, to write the
87  * pointer variable declared above while safely freeing the old value:
88  *
89  *     static struct ovs_mutex mutex = OVS_MUTEX_INITIALIZER;
90  *
91  *     static void
92  *     free_flow(struct flow *flow)
93  *     {
94  *         free(flow);
95  *     }
96  *
97  *     void
98  *     change_flow(struct flow *new_flow)
99  *     {
100  *         ovs_mutex_lock(&mutex);
101  *         ovsrcu_postpone(free_flow,
102  *                         ovsrcu_get_protected(struct flow *, &flowp));
103  *         ovsrcu_set(&flowp, new_flow);
104  *         ovs_mutex_unlock(&mutex);
105  *     }
106  *
107  */
108
109 #include "compiler.h"
110 #include "ovs-atomic.h"
111
112 /* Use OVSRCU_TYPE(TYPE) to declare a pointer to RCU-protected data, e.g. the
113  * following declares an RCU-protected "struct flow *" named flowp:
114  *
115  *     OVSRCU_TYPE(struct flow *) flowp;
116  *
117  * Use ovsrcu_get(TYPE, VAR) to read an RCU-protected pointer, e.g. to read the
118  * pointer variable declared above:
119  *
120  *     struct flow *flow = ovsrcu_get(struct flow *, flowp);
121  *
122  * If the pointer variable is currently protected against change (because
123  * the current thread holds a mutex that protects it), ovsrcu_get_protected()
124  * may be used instead.  Only on the Alpha architecture is this likely to
125  * generate different code, but it may be useful documentation.
126  *
127  * (With GNU C or Clang, you get a compiler error if TYPE is wrong; other
128  * compilers will merrily carry along accepting the wrong type.)
129  */
130 #if __GNUC__
131 #define OVSRCU_TYPE(TYPE) struct { ATOMIC(TYPE) p; }
132 #define ovsrcu_get__(TYPE, VAR, ORDER)                                  \
133     ({                                                                  \
134         TYPE value__;                                                   \
135                                                                         \
136         atomic_read_explicit(CONST_CAST(ATOMIC(TYPE) *, &(VAR)->p),     \
137                              &value__, ORDER);                          \
138                                                                         \
139         value__;                                                        \
140     })
141 #define ovsrcu_get(TYPE, VAR) \
142     CONST_CAST(TYPE, ovsrcu_get__(TYPE, VAR, memory_order_consume))
143 #define ovsrcu_get_protected(TYPE, VAR) \
144     CONST_CAST(TYPE, ovsrcu_get__(TYPE, VAR, memory_order_relaxed))
145 #else  /* not GNU C */
146 typedef struct ovsrcu_pointer { ATOMIC(void *) p; };
147 #define OVSRCU_TYPE(TYPE) struct ovsrcu_pointer
148 static inline void *
149 ovsrcu_get__(const struct ovsrcu_pointer *pointer, memory_order order)
150 {
151     void *value;
152     atomic_read_explicit(&CONST_CAST(struct ovsrcu_pointer *, pointer)->p,
153                          &value, order);
154     return value;
155 }
156 #define ovsrcu_get(TYPE, VAR) \
157     CONST_CAST(TYPE, ovsrcu_get__(VAR, memory_order_consume))
158 #define ovsrcu_get_protected(TYPE, VAR) \
159     CONST_CAST(TYPE, ovsrcu_get__(VAR, memory_order_relaxed))
160 #endif
161
162 /* Writes VALUE to the RCU-protected pointer whose address is VAR.
163  *
164  * Users require external synchronization (e.g. a mutex).  See "Usage" above
165  * for an example. */
166 #define ovsrcu_set(VAR, VALUE) \
167     atomic_store_explicit(&(VAR)->p, VALUE, memory_order_release)
168
169 /* Calls FUNCTION passing ARG as its pointer-type argument following the next
170  * grace period.  See "Usage" above for example.  */
171 void ovsrcu_postpone__(void (*function)(void *aux), void *aux);
172 #define ovsrcu_postpone(FUNCTION, ARG)                          \
173     ((void) sizeof((FUNCTION)(ARG), 1),                         \
174      (void) sizeof(*(ARG)),                                     \
175      ovsrcu_postpone__((void (*)(void *))(FUNCTION), ARG))
176
177 /* Quiescent states. */
178 void ovsrcu_quiesce_start(void);
179 void ovsrcu_quiesce_end(void);
180 void ovsrcu_quiesce(void);
181
182 #endif /* ovs-rcu.h */