Add missing rcu_cmpxchg_pointer define
[urcu.git] / urcu-qsbr.c
CommitLineData
9f1621ca 1/*
7ac06cef 2 * urcu-qsbr.c
9f1621ca 3 *
7ac06cef 4 * Userspace RCU QSBR library
9f1621ca
MD
5 *
6 * Copyright (c) 2009 Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
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
26#include <stdio.h>
27#include <pthread.h>
28#include <signal.h>
29#include <assert.h>
30#include <stdlib.h>
31#include <string.h>
32#include <errno.h>
33#include <poll.h>
34
727f819d 35#define BUILD_QSBR_LIB
7ac06cef 36#include "urcu-qsbr-static.h"
9f1621ca 37/* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
7ac06cef 38#include "urcu-qsbr.h"
9f1621ca 39
81d1f1f5 40static pthread_mutex_t urcu_mutex = PTHREAD_MUTEX_INITIALIZER;
9f1621ca 41
bc6c15bb
MD
42int gp_futex;
43
9f1621ca
MD
44/*
45 * Global grace period counter.
46 */
ac258107 47unsigned long urcu_gp_ctr = RCU_GP_ONLINE;
9f1621ca
MD
48
49/*
50 * Written to only by each individual reader. Read by both the reader and the
51 * writers.
52 */
f0f7dbdd 53unsigned long __thread rcu_reader_qs_gp;
9f1621ca
MD
54
55/* Thread IDs of registered readers */
56#define INIT_NUM_THREADS 4
57
58struct reader_registry {
59 pthread_t tid;
f0f7dbdd 60 unsigned long *rcu_reader_qs_gp;
9f1621ca
MD
61};
62
63#ifdef DEBUG_YIELD
64unsigned int yield_active;
65unsigned int __thread rand_yield;
66#endif
67
68static struct reader_registry *registry;
9f1621ca
MD
69static int num_readers, alloc_readers;
70
90c1618a 71static void internal_urcu_lock(void)
9f1621ca
MD
72{
73 int ret;
74
75#ifndef DISTRUST_SIGNALS_EXTREME
76 ret = pthread_mutex_lock(&urcu_mutex);
77 if (ret) {
78 perror("Error in pthread mutex lock");
79 exit(-1);
80 }
81#else /* #ifndef DISTRUST_SIGNALS_EXTREME */
82 while ((ret = pthread_mutex_trylock(&urcu_mutex)) != 0) {
83 if (ret != EBUSY && ret != EINTR) {
84 printf("ret = %d, errno = %d\n", ret, errno);
85 perror("Error in pthread mutex lock");
86 exit(-1);
87 }
9f1621ca
MD
88 poll(NULL,0,10);
89 }
90#endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
91}
92
90c1618a 93static void internal_urcu_unlock(void)
9f1621ca
MD
94{
95 int ret;
96
97 ret = pthread_mutex_unlock(&urcu_mutex);
98 if (ret) {
99 perror("Error in pthread mutex unlock");
100 exit(-1);
101 }
102}
103
bc6c15bb
MD
104/*
105 * synchronize_rcu() waiting. Single thread.
106 */
107static void wait_gp(struct reader_registry *index)
108{
109 atomic_dec(&gp_futex);
110 smp_mb(); /* Write futex before read reader_gp */
111 if (!rcu_gp_ongoing(index->rcu_reader_qs_gp)) {
112 /* Read reader_gp before write futex */
113 smp_mb();
114 /* Callbacks are queued, don't wait. */
115 atomic_set(&gp_futex, 0);
116 } else {
117 /* Read reader_gp before read futex */
118 smp_rmb();
119 if (atomic_read(&gp_futex) == -1)
120 futex(&gp_futex, FUTEX_WAIT, -1,
121 NULL, NULL, 0);
122 }
123}
124
90c1618a 125static void wait_for_quiescent_state(void)
9f1621ca
MD
126{
127 struct reader_registry *index;
128
129 if (!registry)
130 return;
131 /*
3395d46c 132 * Wait for each thread rcu_reader_qs_gp count to become 0.
9f1621ca
MD
133 */
134 for (index = registry; index < registry + num_readers; index++) {
bc6c15bb
MD
135 int wait_loops = 0;
136
137 while (rcu_gp_ongoing(index->rcu_reader_qs_gp)) {
138 if (wait_loops++ == RCU_QS_ACTIVE_ATTEMPTS) {
139 wait_gp(index);
140 } else {
9f1621ca 141#ifndef HAS_INCOHERENT_CACHES
bc6c15bb 142 cpu_relax();
9f1621ca 143#else /* #ifndef HAS_INCOHERENT_CACHES */
bc6c15bb 144 smp_mb();
9f1621ca 145#endif /* #else #ifndef HAS_INCOHERENT_CACHES */
bc6c15bb
MD
146 }
147 }
9f1621ca
MD
148 }
149}
150
47d2f29e
MD
151/*
152 * Using a two-subphases algorithm for architectures with smaller than 64-bit
153 * long-size to ensure we do not encounter an overflow bug.
154 */
155
156#if (BITS_PER_LONG < 64)
157/*
158 * called with urcu_mutex held.
159 */
160static void switch_next_urcu_qparity(void)
161{
162 STORE_SHARED(urcu_gp_ctr, urcu_gp_ctr ^ RCU_GP_CTR);
163}
164
165void synchronize_rcu(void)
166{
bc49c323
MD
167 unsigned long was_online;
168
169 was_online = rcu_reader_qs_gp;
170
47d2f29e
MD
171 /* All threads should read qparity before accessing data structure
172 * where new ptr points to.
173 */
174 /* Write new ptr before changing the qparity */
175 smp_mb();
176
bc49c323
MD
177 /*
178 * Mark the writer thread offline to make sure we don't wait for
179 * our own quiescent state. This allows using synchronize_rcu() in
180 * threads registered as readers.
181 */
182 if (was_online)
183 STORE_SHARED(rcu_reader_qs_gp, 0);
184
47d2f29e
MD
185 internal_urcu_lock();
186
187 switch_next_urcu_qparity(); /* 0 -> 1 */
188
189 /*
190 * Must commit qparity update to memory before waiting for parity
191 * 0 quiescent state. Failure to do so could result in the writer
192 * waiting forever while new readers are always accessing data (no
193 * progress).
194 * Ensured by STORE_SHARED and LOAD_SHARED.
195 */
196
197 /*
198 * Wait for previous parity to be empty of readers.
199 */
200 wait_for_quiescent_state(); /* Wait readers in parity 0 */
201
202 /*
203 * Must finish waiting for quiescent state for parity 0 before
204 * committing qparity update to memory. Failure to do so could result in
205 * the writer waiting forever while new readers are always accessing
206 * data (no progress).
207 * Ensured by STORE_SHARED and LOAD_SHARED.
208 */
209
210 switch_next_urcu_qparity(); /* 1 -> 0 */
211
212 /*
213 * Must commit qparity update to memory before waiting for parity
214 * 1 quiescent state. Failure to do so could result in the writer
215 * waiting forever while new readers are always accessing data (no
216 * progress).
217 * Ensured by STORE_SHARED and LOAD_SHARED.
218 */
219
220 /*
221 * Wait for previous parity to be empty of readers.
222 */
223 wait_for_quiescent_state(); /* Wait readers in parity 1 */
224
225 internal_urcu_unlock();
226
bc49c323
MD
227 /*
228 * Finish waiting for reader threads before letting the old ptr being
47d2f29e
MD
229 * freed.
230 */
bc49c323
MD
231 if (was_online)
232 _STORE_SHARED(rcu_reader_qs_gp, LOAD_SHARED(urcu_gp_ctr));
47d2f29e
MD
233 smp_mb();
234}
235#else /* !(BITS_PER_LONG < 64) */
9f1621ca
MD
236void synchronize_rcu(void)
237{
f0f7dbdd 238 unsigned long was_online;
ff2f67a0 239
ab179a17 240 was_online = rcu_reader_qs_gp;
ff2f67a0
MD
241
242 /*
243 * Mark the writer thread offline to make sure we don't wait for
244 * our own quiescent state. This allows using synchronize_rcu() in
245 * threads registered as readers.
246 */
8f50d1ce 247 smp_mb();
ff2f67a0 248 if (was_online)
8f50d1ce 249 STORE_SHARED(rcu_reader_qs_gp, 0);
ff2f67a0 250
4e27f058 251 internal_urcu_lock();
55570466 252 STORE_SHARED(urcu_gp_ctr, urcu_gp_ctr + RCU_GP_CTR);
9f1621ca 253 wait_for_quiescent_state();
9f1621ca 254 internal_urcu_unlock();
ff2f67a0
MD
255
256 if (was_online)
ab179a17 257 _STORE_SHARED(rcu_reader_qs_gp, LOAD_SHARED(urcu_gp_ctr));
8f50d1ce 258 smp_mb();
9f1621ca 259}
47d2f29e 260#endif /* !(BITS_PER_LONG < 64) */
9f1621ca
MD
261
262/*
263 * library wrappers to be used by non-LGPL compatible source code.
264 */
265
266void rcu_read_lock(void)
267{
268 _rcu_read_lock();
269}
270
271void rcu_read_unlock(void)
272{
273 _rcu_read_unlock();
274}
275
276void *rcu_dereference(void *p)
277{
278 return _rcu_dereference(p);
279}
280
281void *rcu_assign_pointer_sym(void **p, void *v)
282{
283 wmb();
284 return STORE_SHARED(p, v);
285}
286
4d1ce26f
MD
287void *rcu_cmpxchg_pointer_sym(void **p, void *old, void *_new)
288{
289 wmb();
290 return cmpxchg(p, old, _new);
291}
292
9f1621ca
MD
293void *rcu_xchg_pointer_sym(void **p, void *v)
294{
295 wmb();
296 return xchg(p, v);
297}
298
299void *rcu_publish_content_sym(void **p, void *v)
300{
301 void *oldptr;
302
303 oldptr = _rcu_xchg_pointer(p, v);
304 synchronize_rcu();
305 return oldptr;
306}
307
7ac06cef
MD
308void rcu_quiescent_state(void)
309{
310 _rcu_quiescent_state();
311}
312
313void rcu_thread_offline(void)
314{
315 _rcu_thread_offline();
316}
317
318void rcu_thread_online(void)
319{
320 _rcu_thread_online();
321}
322
9f1621ca
MD
323static void rcu_add_reader(pthread_t id)
324{
325 struct reader_registry *oldarray;
326
327 if (!registry) {
328 alloc_readers = INIT_NUM_THREADS;
329 num_readers = 0;
330 registry =
331 malloc(sizeof(struct reader_registry) * alloc_readers);
332 }
333 if (alloc_readers < num_readers + 1) {
334 oldarray = registry;
335 registry = malloc(sizeof(struct reader_registry)
336 * (alloc_readers << 1));
337 memcpy(registry, oldarray,
338 sizeof(struct reader_registry) * alloc_readers);
339 alloc_readers <<= 1;
340 free(oldarray);
341 }
342 registry[num_readers].tid = id;
343 /* reference to the TLS of _this_ reader thread. */
3395d46c 344 registry[num_readers].rcu_reader_qs_gp = &rcu_reader_qs_gp;
9f1621ca
MD
345 num_readers++;
346}
347
348/*
349 * Never shrink (implementation limitation).
350 * This is O(nb threads). Eventually use a hash table.
351 */
352static void rcu_remove_reader(pthread_t id)
353{
354 struct reader_registry *index;
355
356 assert(registry != NULL);
357 for (index = registry; index < registry + num_readers; index++) {
358 if (pthread_equal(index->tid, id)) {
359 memcpy(index, &registry[num_readers - 1],
360 sizeof(struct reader_registry));
361 registry[num_readers - 1].tid = 0;
3395d46c 362 registry[num_readers - 1].rcu_reader_qs_gp = NULL;
9f1621ca
MD
363 num_readers--;
364 return;
365 }
366 }
367 /* Hrm not found, forgot to register ? */
368 assert(0);
369}
370
371void rcu_register_thread(void)
372{
373 internal_urcu_lock();
9f1621ca
MD
374 rcu_add_reader(pthread_self());
375 internal_urcu_unlock();
5f373c84 376 _rcu_thread_online();
9f1621ca
MD
377}
378
379void rcu_unregister_thread(void)
380{
76f3022f
MD
381 /*
382 * We have to make the thread offline otherwise we end up dealocking
383 * with a waiting writer.
384 */
385 _rcu_thread_offline();
9f1621ca
MD
386 internal_urcu_lock();
387 rcu_remove_reader(pthread_self());
388 internal_urcu_unlock();
389}
This page took 0.056723 seconds and 4 git commands to generate.