api: reimplement BUILD_BUG_ON in compiler.h
[urcu.git] / urcu-qsbr.c
CommitLineData
9f1621ca 1/*
7ac06cef 2 * urcu-qsbr.c
9f1621ca 3 *
7ac06cef 4 * Userspace RCU QSBR library
9f1621ca 5 *
6982d6d7 6 * Copyright (c) 2009 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
9f1621ca
MD
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
c1d2c60b 26#define _GNU_SOURCE
9f1621ca
MD
27#include <stdio.h>
28#include <pthread.h>
29#include <signal.h>
30#include <assert.h>
31#include <stdlib.h>
6d841bc2 32#include <stdint.h>
9f1621ca
MD
33#include <string.h>
34#include <errno.h>
35#include <poll.h>
36
57760d44 37#include "urcu/map/urcu-qsbr.h"
5e77fc1f 38
727f819d 39#define BUILD_QSBR_LIB
af7c2dbe 40#include "urcu/static/urcu-qsbr.h"
9f1621ca 41/* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
7ac06cef 42#include "urcu-qsbr.h"
9f1621ca 43
f6d18c64
MD
44void __attribute__((destructor)) rcu_exit(void);
45
6abb4bd5 46static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
9f1621ca 47
6d841bc2 48int32_t gp_futex;
bc6c15bb 49
9f1621ca
MD
50/*
51 * Global grace period counter.
52 */
02be5561 53unsigned long rcu_gp_ctr = RCU_GP_ONLINE;
9f1621ca 54
408f6d92
PB
55/*
56 * Active attempts to check for reader Q.S. before calling futex().
57 */
58#define RCU_QS_ACTIVE_ATTEMPTS 100
59
9f1621ca
MD
60/*
61 * Written to only by each individual reader. Read by both the reader and the
62 * writers.
63 */
02be5561 64struct rcu_reader __thread rcu_reader;
9f1621ca
MD
65
66#ifdef DEBUG_YIELD
67unsigned int yield_active;
68unsigned int __thread rand_yield;
69#endif
70
16aa9ee8 71static CDS_LIST_HEAD(registry);
9f1621ca 72
6abb4bd5 73static void mutex_lock(pthread_mutex_t *mutex)
9f1621ca
MD
74{
75 int ret;
76
77#ifndef DISTRUST_SIGNALS_EXTREME
6abb4bd5 78 ret = pthread_mutex_lock(mutex);
9f1621ca
MD
79 if (ret) {
80 perror("Error in pthread mutex lock");
81 exit(-1);
82 }
83#else /* #ifndef DISTRUST_SIGNALS_EXTREME */
6abb4bd5 84 while ((ret = pthread_mutex_trylock(mutex)) != 0) {
9f1621ca
MD
85 if (ret != EBUSY && ret != EINTR) {
86 printf("ret = %d, errno = %d\n", ret, errno);
87 perror("Error in pthread mutex lock");
88 exit(-1);
89 }
9f1621ca
MD
90 poll(NULL,0,10);
91 }
92#endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
93}
94
6abb4bd5 95static void mutex_unlock(pthread_mutex_t *mutex)
9f1621ca
MD
96{
97 int ret;
98
6abb4bd5 99 ret = pthread_mutex_unlock(mutex);
9f1621ca
MD
100 if (ret) {
101 perror("Error in pthread mutex unlock");
102 exit(-1);
103 }
104}
105
bc6c15bb
MD
106/*
107 * synchronize_rcu() waiting. Single thread.
108 */
4d703340 109static void wait_gp(void)
bc6c15bb 110{
4d703340 111 /* Read reader_gp before read futex */
5481ddb3 112 cmm_smp_rmb();
4d703340 113 if (uatomic_read(&gp_futex) == -1)
0854ccff 114 futex_noasync(&gp_futex, FUTEX_WAIT, -1,
4d703340 115 NULL, NULL, 0);
bc6c15bb
MD
116}
117
2dfb8b5e 118static void update_counter_and_wait(void)
9f1621ca 119{
16aa9ee8 120 CDS_LIST_HEAD(qsreaders);
4d703340 121 int wait_loops = 0;
02be5561 122 struct rcu_reader *index, *tmp;
9f1621ca 123
b39e1761 124#if (CAA_BITS_PER_LONG < 64)
32c15e4e 125 /* Switch parity: 0 -> 1, 1 -> 0 */
6cf3827c 126 CMM_STORE_SHARED(rcu_gp_ctr, rcu_gp_ctr ^ RCU_GP_CTR);
b39e1761 127#else /* !(CAA_BITS_PER_LONG < 64) */
2dfb8b5e 128 /* Increment current G.P. */
6cf3827c 129 CMM_STORE_SHARED(rcu_gp_ctr, rcu_gp_ctr + RCU_GP_CTR);
b39e1761 130#endif /* !(CAA_BITS_PER_LONG < 64) */
2dfb8b5e 131
7a5a38f5 132 /*
5e77fc1f
PM
133 * Must commit rcu_gp_ctr update to memory before waiting for
134 * quiescent state. Failure to do so could result in the writer
135 * waiting forever while new readers are always accessing data
136 * (no progress). Enforce compiler-order of store to rcu_gp_ctr
137 * before load rcu_reader ctr.
d40fde2c 138 */
5481ddb3 139 cmm_barrier();
d40fde2c
MD
140
141 /*
5481ddb3 142 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
935b11ff
MD
143 * model easier to understand. It does not have a big performance impact
144 * anyway, given this is the write-side.
7a5a38f5 145 */
5481ddb3 146 cmm_smp_mb();
7a5a38f5 147
9f1621ca 148 /*
3395d46c 149 * Wait for each thread rcu_reader_qs_gp count to become 0.
9f1621ca 150 */
4d703340
MD
151 for (;;) {
152 wait_loops++;
153 if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS) {
154 uatomic_dec(&gp_futex);
155 /* Write futex before read reader_gp */
5481ddb3 156 cmm_smp_mb();
4d703340
MD
157 }
158
16aa9ee8 159 cds_list_for_each_entry_safe(index, tmp, &registry, node) {
4d703340 160 if (!rcu_gp_ongoing(&index->ctr))
16aa9ee8 161 cds_list_move(&index->node, &qsreaders);
4d703340 162 }
bc6c15bb 163
16aa9ee8 164 if (cds_list_empty(&registry)) {
4d703340
MD
165 if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS) {
166 /* Read reader_gp before write futex */
5481ddb3 167 cmm_smp_mb();
4d703340
MD
168 uatomic_set(&gp_futex, 0);
169 }
170 break;
171 } else {
172 if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS) {
173 wait_gp();
bc6c15bb 174 } else {
9f1621ca 175#ifndef HAS_INCOHERENT_CACHES
06f22bdb 176 caa_cpu_relax();
9f1621ca 177#else /* #ifndef HAS_INCOHERENT_CACHES */
5481ddb3 178 cmm_smp_mb();
9f1621ca 179#endif /* #else #ifndef HAS_INCOHERENT_CACHES */
bc6c15bb
MD
180 }
181 }
9f1621ca 182 }
4d703340 183 /* put back the reader list in the registry */
16aa9ee8 184 cds_list_splice(&qsreaders, &registry);
9f1621ca
MD
185}
186
47d2f29e
MD
187/*
188 * Using a two-subphases algorithm for architectures with smaller than 64-bit
189 * long-size to ensure we do not encounter an overflow bug.
190 */
191
b39e1761 192#if (CAA_BITS_PER_LONG < 64)
47d2f29e
MD
193void synchronize_rcu(void)
194{
bc49c323
MD
195 unsigned long was_online;
196
02be5561 197 was_online = rcu_reader.ctr;
bc49c323 198
47d2f29e
MD
199 /* All threads should read qparity before accessing data structure
200 * where new ptr points to.
201 */
202 /* Write new ptr before changing the qparity */
5481ddb3 203 cmm_smp_mb();
47d2f29e 204
bc49c323
MD
205 /*
206 * Mark the writer thread offline to make sure we don't wait for
5e77fc1f
PM
207 * our own quiescent state. This allows using synchronize_rcu()
208 * in threads registered as readers.
bc49c323
MD
209 */
210 if (was_online)
6cf3827c 211 CMM_STORE_SHARED(rcu_reader.ctr, 0);
bc49c323 212
6abb4bd5 213 mutex_lock(&rcu_gp_lock);
47d2f29e 214
16aa9ee8 215 if (cds_list_empty(&registry))
2dfb8b5e 216 goto out;
47d2f29e
MD
217
218 /*
219 * Wait for previous parity to be empty of readers.
220 */
2dfb8b5e 221 update_counter_and_wait(); /* 0 -> 1, wait readers in parity 0 */
47d2f29e
MD
222
223 /*
224 * Must finish waiting for quiescent state for parity 0 before
5e77fc1f
PM
225 * committing next rcu_gp_ctr update to memory. Failure to
226 * do so could result in the writer waiting forever while new
227 * readers are always accessing data (no progress). Enforce
228 * compiler-order of load rcu_reader ctr before store to
229 * rcu_gp_ctr.
47d2f29e 230 */
5481ddb3 231 cmm_barrier();
47d2f29e 232
47d2f29e 233 /*
5481ddb3 234 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
2dfb8b5e
MD
235 * model easier to understand. It does not have a big performance impact
236 * anyway, given this is the write-side.
47d2f29e 237 */
5481ddb3 238 cmm_smp_mb();
47d2f29e
MD
239
240 /*
241 * Wait for previous parity to be empty of readers.
242 */
2dfb8b5e
MD
243 update_counter_and_wait(); /* 1 -> 0, wait readers in parity 1 */
244out:
6abb4bd5 245 mutex_unlock(&rcu_gp_lock);
47d2f29e 246
bc49c323
MD
247 /*
248 * Finish waiting for reader threads before letting the old ptr being
47d2f29e
MD
249 * freed.
250 */
bc49c323 251 if (was_online)
5e77fc1f
PM
252 _CMM_STORE_SHARED(rcu_reader.ctr,
253 CMM_LOAD_SHARED(rcu_gp_ctr));
5481ddb3 254 cmm_smp_mb();
47d2f29e 255}
b39e1761 256#else /* !(CAA_BITS_PER_LONG < 64) */
9f1621ca
MD
257void synchronize_rcu(void)
258{
f0f7dbdd 259 unsigned long was_online;
ff2f67a0 260
02be5561 261 was_online = rcu_reader.ctr;
ff2f67a0
MD
262
263 /*
264 * Mark the writer thread offline to make sure we don't wait for
5e77fc1f
PM
265 * our own quiescent state. This allows using synchronize_rcu()
266 * in threads registered as readers.
ff2f67a0 267 */
5481ddb3 268 cmm_smp_mb();
ff2f67a0 269 if (was_online)
6cf3827c 270 CMM_STORE_SHARED(rcu_reader.ctr, 0);
ff2f67a0 271
6abb4bd5 272 mutex_lock(&rcu_gp_lock);
16aa9ee8 273 if (cds_list_empty(&registry))
2dfb8b5e
MD
274 goto out;
275 update_counter_and_wait();
276out:
6abb4bd5 277 mutex_unlock(&rcu_gp_lock);
ff2f67a0
MD
278
279 if (was_online)
5e77fc1f
PM
280 _CMM_STORE_SHARED(rcu_reader.ctr,
281 CMM_LOAD_SHARED(rcu_gp_ctr));
5481ddb3 282 cmm_smp_mb();
9f1621ca 283}
b39e1761 284#endif /* !(CAA_BITS_PER_LONG < 64) */
9f1621ca
MD
285
286/*
287 * library wrappers to be used by non-LGPL compatible source code.
288 */
289
290void rcu_read_lock(void)
291{
292 _rcu_read_lock();
293}
294
295void rcu_read_unlock(void)
296{
297 _rcu_read_unlock();
298}
299
7ac06cef
MD
300void rcu_quiescent_state(void)
301{
302 _rcu_quiescent_state();
303}
304
305void rcu_thread_offline(void)
306{
307 _rcu_thread_offline();
308}
309
310void rcu_thread_online(void)
311{
312 _rcu_thread_online();
313}
314
9f1621ca
MD
315void rcu_register_thread(void)
316{
02be5561
MD
317 rcu_reader.tid = pthread_self();
318 assert(rcu_reader.ctr == 0);
4f8e3380 319
6abb4bd5 320 mutex_lock(&rcu_gp_lock);
16aa9ee8 321 cds_list_add(&rcu_reader.node, &registry);
6abb4bd5 322 mutex_unlock(&rcu_gp_lock);
5f373c84 323 _rcu_thread_online();
9f1621ca
MD
324}
325
326void rcu_unregister_thread(void)
327{
76f3022f
MD
328 /*
329 * We have to make the thread offline otherwise we end up dealocking
330 * with a waiting writer.
331 */
332 _rcu_thread_offline();
6abb4bd5 333 mutex_lock(&rcu_gp_lock);
16aa9ee8 334 cds_list_del(&rcu_reader.node);
6abb4bd5 335 mutex_unlock(&rcu_gp_lock);
9f1621ca 336}
f6d18c64
MD
337
338void rcu_exit(void)
339{
16aa9ee8 340 assert(cds_list_empty(&registry));
f6d18c64 341}
5e77fc1f
PM
342
343#include "urcu-call-rcu-impl.h"
0376e7b2 344#include "urcu-defer-impl.h"
This page took 0.068113 seconds and 4 git commands to generate.