rculfstack: document "push"
[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++;
83a2c421
PB
153 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
154 uatomic_set(&gp_futex, -1);
155 /*
156 * Write futex before write waiting (the other side
157 * reads them in the opposite order).
158 */
159 cmm_smp_wmb();
160 cds_list_for_each_entry(index, &registry, node) {
161 _CMM_STORE_SHARED(index->waiting, 1);
162 }
4d703340 163 /* Write futex before read reader_gp */
5481ddb3 164 cmm_smp_mb();
4d703340 165 }
16aa9ee8 166 cds_list_for_each_entry_safe(index, tmp, &registry, node) {
4d703340 167 if (!rcu_gp_ongoing(&index->ctr))
16aa9ee8 168 cds_list_move(&index->node, &qsreaders);
4d703340 169 }
bc6c15bb 170
16aa9ee8 171 if (cds_list_empty(&registry)) {
83a2c421 172 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
4d703340 173 /* Read reader_gp before write futex */
5481ddb3 174 cmm_smp_mb();
4d703340
MD
175 uatomic_set(&gp_futex, 0);
176 }
177 break;
178 } else {
83a2c421 179 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
4d703340 180 wait_gp();
bc6c15bb 181 } else {
9f1621ca 182#ifndef HAS_INCOHERENT_CACHES
06f22bdb 183 caa_cpu_relax();
9f1621ca 184#else /* #ifndef HAS_INCOHERENT_CACHES */
5481ddb3 185 cmm_smp_mb();
9f1621ca 186#endif /* #else #ifndef HAS_INCOHERENT_CACHES */
bc6c15bb
MD
187 }
188 }
9f1621ca 189 }
4d703340 190 /* put back the reader list in the registry */
16aa9ee8 191 cds_list_splice(&qsreaders, &registry);
9f1621ca
MD
192}
193
47d2f29e
MD
194/*
195 * Using a two-subphases algorithm for architectures with smaller than 64-bit
196 * long-size to ensure we do not encounter an overflow bug.
197 */
198
b39e1761 199#if (CAA_BITS_PER_LONG < 64)
47d2f29e
MD
200void synchronize_rcu(void)
201{
bc49c323
MD
202 unsigned long was_online;
203
02be5561 204 was_online = rcu_reader.ctr;
bc49c323 205
47d2f29e
MD
206 /* All threads should read qparity before accessing data structure
207 * where new ptr points to.
208 */
209 /* Write new ptr before changing the qparity */
5481ddb3 210 cmm_smp_mb();
47d2f29e 211
bc49c323
MD
212 /*
213 * Mark the writer thread offline to make sure we don't wait for
5e77fc1f
PM
214 * our own quiescent state. This allows using synchronize_rcu()
215 * in threads registered as readers.
bc49c323
MD
216 */
217 if (was_online)
6cf3827c 218 CMM_STORE_SHARED(rcu_reader.ctr, 0);
bc49c323 219
6abb4bd5 220 mutex_lock(&rcu_gp_lock);
47d2f29e 221
16aa9ee8 222 if (cds_list_empty(&registry))
2dfb8b5e 223 goto out;
47d2f29e
MD
224
225 /*
226 * Wait for previous parity to be empty of readers.
227 */
2dfb8b5e 228 update_counter_and_wait(); /* 0 -> 1, wait readers in parity 0 */
47d2f29e
MD
229
230 /*
231 * Must finish waiting for quiescent state for parity 0 before
5e77fc1f
PM
232 * committing next rcu_gp_ctr update to memory. Failure to
233 * do so could result in the writer waiting forever while new
234 * readers are always accessing data (no progress). Enforce
235 * compiler-order of load rcu_reader ctr before store to
236 * rcu_gp_ctr.
47d2f29e 237 */
5481ddb3 238 cmm_barrier();
47d2f29e 239
47d2f29e 240 /*
5481ddb3 241 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
2dfb8b5e
MD
242 * model easier to understand. It does not have a big performance impact
243 * anyway, given this is the write-side.
47d2f29e 244 */
5481ddb3 245 cmm_smp_mb();
47d2f29e
MD
246
247 /*
248 * Wait for previous parity to be empty of readers.
249 */
2dfb8b5e
MD
250 update_counter_and_wait(); /* 1 -> 0, wait readers in parity 1 */
251out:
6abb4bd5 252 mutex_unlock(&rcu_gp_lock);
47d2f29e 253
bc49c323
MD
254 /*
255 * Finish waiting for reader threads before letting the old ptr being
47d2f29e
MD
256 * freed.
257 */
bc49c323 258 if (was_online)
5e77fc1f
PM
259 _CMM_STORE_SHARED(rcu_reader.ctr,
260 CMM_LOAD_SHARED(rcu_gp_ctr));
5481ddb3 261 cmm_smp_mb();
47d2f29e 262}
b39e1761 263#else /* !(CAA_BITS_PER_LONG < 64) */
9f1621ca
MD
264void synchronize_rcu(void)
265{
f0f7dbdd 266 unsigned long was_online;
ff2f67a0 267
02be5561 268 was_online = rcu_reader.ctr;
ff2f67a0
MD
269
270 /*
271 * Mark the writer thread offline to make sure we don't wait for
5e77fc1f
PM
272 * our own quiescent state. This allows using synchronize_rcu()
273 * in threads registered as readers.
ff2f67a0 274 */
5481ddb3 275 cmm_smp_mb();
ff2f67a0 276 if (was_online)
6cf3827c 277 CMM_STORE_SHARED(rcu_reader.ctr, 0);
ff2f67a0 278
6abb4bd5 279 mutex_lock(&rcu_gp_lock);
16aa9ee8 280 if (cds_list_empty(&registry))
2dfb8b5e
MD
281 goto out;
282 update_counter_and_wait();
283out:
6abb4bd5 284 mutex_unlock(&rcu_gp_lock);
ff2f67a0
MD
285
286 if (was_online)
5e77fc1f
PM
287 _CMM_STORE_SHARED(rcu_reader.ctr,
288 CMM_LOAD_SHARED(rcu_gp_ctr));
5481ddb3 289 cmm_smp_mb();
9f1621ca 290}
b39e1761 291#endif /* !(CAA_BITS_PER_LONG < 64) */
9f1621ca
MD
292
293/*
294 * library wrappers to be used by non-LGPL compatible source code.
295 */
296
297void rcu_read_lock(void)
298{
299 _rcu_read_lock();
300}
301
302void rcu_read_unlock(void)
303{
304 _rcu_read_unlock();
305}
306
7ac06cef
MD
307void rcu_quiescent_state(void)
308{
309 _rcu_quiescent_state();
310}
311
312void rcu_thread_offline(void)
313{
314 _rcu_thread_offline();
315}
316
317void rcu_thread_online(void)
318{
319 _rcu_thread_online();
320}
321
9f1621ca
MD
322void rcu_register_thread(void)
323{
02be5561
MD
324 rcu_reader.tid = pthread_self();
325 assert(rcu_reader.ctr == 0);
4f8e3380 326
6abb4bd5 327 mutex_lock(&rcu_gp_lock);
16aa9ee8 328 cds_list_add(&rcu_reader.node, &registry);
6abb4bd5 329 mutex_unlock(&rcu_gp_lock);
5f373c84 330 _rcu_thread_online();
9f1621ca
MD
331}
332
333void rcu_unregister_thread(void)
334{
76f3022f
MD
335 /*
336 * We have to make the thread offline otherwise we end up dealocking
337 * with a waiting writer.
338 */
339 _rcu_thread_offline();
6abb4bd5 340 mutex_lock(&rcu_gp_lock);
16aa9ee8 341 cds_list_del(&rcu_reader.node);
6abb4bd5 342 mutex_unlock(&rcu_gp_lock);
9f1621ca 343}
f6d18c64
MD
344
345void rcu_exit(void)
346{
16aa9ee8 347 assert(cds_list_empty(&registry));
f6d18c64 348}
5e77fc1f
PM
349
350#include "urcu-call-rcu-impl.h"
0376e7b2 351#include "urcu-defer-impl.h"
This page took 0.068616 seconds and 4 git commands to generate.