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