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