Add ACCESS_ONCE to _STORE_SHARED
[urcu.git] / urcu.c
CommitLineData
b257a10b
MD
1/*
2 * urcu.c
3 *
4 * Userspace RCU library
5 *
6 * Copyright February 2009 - Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
7 *
8 * Distributed under GPLv2
54843abc
PM
9 *
10 * IBM's contributions to this file may be relicensed under LGPLv2 or later.
b257a10b
MD
11 */
12
27b012e2
MD
13#include <stdio.h>
14#include <pthread.h>
15#include <signal.h>
16#include <assert.h>
f69f195a
MD
17#include <stdlib.h>
18#include <string.h>
09a9f986 19#include <errno.h>
e8043c1b 20#include <poll.h>
27b012e2
MD
21
22#include "urcu.h"
23
24pthread_mutex_t urcu_mutex = PTHREAD_MUTEX_INITIALIZER;
25
128166c9
MD
26/*
27 * Global grace period counter.
28 * Contains the current RCU_GP_CTR_BIT.
29 * Also has a RCU_GP_CTR_BIT of 1, to accelerate the reader fast path.
b0d5e790 30 * Written to only by writer with mutex taken. Read by both writer and readers.
128166c9
MD
31 */
32long urcu_gp_ctr = RCU_GP_COUNT;
27b012e2 33
b0d5e790
MD
34/*
35 * Written to only by each individual reader. Read by both the reader and the
36 * writers.
37 */
6e8b8429 38long __thread urcu_active_readers;
27b012e2
MD
39
40/* Thread IDs of registered readers */
41#define INIT_NUM_THREADS 4
42
0a52082b 43struct reader_registry {
27b012e2 44 pthread_t tid;
128166c9 45 long *urcu_active_readers;
09a9f986 46 char *need_mb;
27b012e2
MD
47};
48
cf380c2f 49#ifdef DEBUG_YIELD
9d335088
MD
50unsigned int yield_active;
51unsigned int __thread rand_yield;
cf380c2f
MD
52#endif
53
0a52082b 54static struct reader_registry *registry;
09a9f986 55static char __thread need_mb;
27b012e2 56static int num_readers, alloc_readers;
27b012e2 57
c265818b 58void internal_urcu_lock(void)
41718ff9
MD
59{
60 int ret;
09a9f986
PM
61
62#ifndef DISTRUST_SIGNALS_EXTREME
41718ff9
MD
63 ret = pthread_mutex_lock(&urcu_mutex);
64 if (ret) {
65 perror("Error in pthread mutex lock");
66 exit(-1);
67 }
09a9f986
PM
68#else /* #ifndef DISTRUST_SIGNALS_EXTREME */
69 while ((ret = pthread_mutex_trylock(&urcu_mutex)) != 0) {
70 if (ret != EBUSY && ret != EINTR) {
71 printf("ret = %d, errno = %d\n", ret, errno);
72 perror("Error in pthread mutex lock");
73 exit(-1);
74 }
75 if (need_mb) {
76 smp_mb();
77 need_mb = 0;
78 smp_mb();
79 }
80 poll(NULL,0,10);
81 }
82#endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
41718ff9
MD
83}
84
c265818b 85void internal_urcu_unlock(void)
41718ff9
MD
86{
87 int ret;
88
89 ret = pthread_mutex_unlock(&urcu_mutex);
90 if (ret) {
91 perror("Error in pthread mutex unlock");
92 exit(-1);
93 }
94}
95
27b012e2
MD
96/*
97 * called with urcu_mutex held.
98 */
1430ee0b 99static void switch_next_urcu_qparity(void)
27b012e2 100{
b0d5e790 101 STORE_SHARED(urcu_gp_ctr, urcu_gp_ctr ^ RCU_GP_CTR_BIT);
27b012e2
MD
102}
103
bb488185 104#ifdef DEBUG_FULL_MB
e8043c1b 105#ifdef HAS_INCOHERENT_CACHES
09a9f986 106static void force_mb_single_thread(struct reader_registry *index)
40e140c9
MD
107{
108 smp_mb();
109}
e8043c1b 110#endif /* #ifdef HAS_INCOHERENT_CACHES */
40e140c9 111
bb488185
MD
112static void force_mb_all_threads(void)
113{
b715b99e 114 smp_mb();
bb488185 115}
e8043c1b
MD
116#else /* #ifdef DEBUG_FULL_MB */
117#ifdef HAS_INCOHERENT_CACHES
09a9f986 118static void force_mb_single_thread(struct reader_registry *index)
40e140c9 119{
0a52082b 120 assert(registry);
157dca95
MD
121 /*
122 * pthread_kill has a smp_mb(). But beware, we assume it performs
123 * a cache flush on architectures with non-coherent cache. Let's play
124 * safe and don't assume anything : we use smp_mc() to make sure the
125 * cache flush is enforced.
157dca95 126 */
09a9f986
PM
127 *index->need_mb = 1;
128 smp_mc(); /* write ->need_mb before sending the signals */
129 pthread_kill(index->tid, SIGURCU);
130 smp_mb();
40e140c9
MD
131 /*
132 * Wait for sighandler (and thus mb()) to execute on every thread.
133 * BUSY-LOOP.
134 */
09a9f986
PM
135 while (*index->need_mb) {
136 poll(NULL, 0, 1);
137 }
138 smp_mb(); /* read ->need_mb before ending the barrier */
40e140c9 139}
e8043c1b 140#endif /* #ifdef HAS_INCOHERENT_CACHES */
40e140c9 141
27b012e2
MD
142static void force_mb_all_threads(void)
143{
0a52082b 144 struct reader_registry *index;
27b012e2 145 /*
b715b99e 146 * Ask for each threads to execute a smp_mb() so we can consider the
27b012e2
MD
147 * compiler barriers around rcu read lock as real memory barriers.
148 */
0a52082b 149 if (!registry)
27b012e2 150 return;
3a86deba
MD
151 /*
152 * pthread_kill has a smp_mb(). But beware, we assume it performs
157dca95
MD
153 * a cache flush on architectures with non-coherent cache. Let's play
154 * safe and don't assume anything : we use smp_mc() to make sure the
155 * cache flush is enforced.
3a86deba 156 */
09a9f986
PM
157 for (index = registry; index < registry + num_readers; index++) {
158 *index->need_mb = 1;
159 smp_mc(); /* write need_mb before sending the signal */
f69f195a 160 pthread_kill(index->tid, SIGURCU);
09a9f986 161 }
27b012e2
MD
162 /*
163 * Wait for sighandler (and thus mb()) to execute on every thread.
09a9f986
PM
164 *
165 * Note that the pthread_kill() will never be executed on systems
166 * that correctly deliver signals in a timely manner. However, it
167 * is not uncommon for kernels to have bugs that can result in
168 * lost or unduly delayed signals.
169 *
170 * If you are seeing the below pthread_kill() executing much at
171 * all, we suggest testing the underlying kernel and filing the
172 * relevant bug report. For Linux kernels, we recommend getting
173 * the Linux Test Project (LTP).
27b012e2 174 */
09a9f986
PM
175 for (index = registry; index < registry + num_readers; index++) {
176 while (*index->need_mb) {
177 pthread_kill(index->tid, SIGURCU);
178 poll(NULL, 0, 1);
179 }
180 }
181 smp_mb(); /* read ->need_mb before ending the barrier */
27b012e2 182}
e8043c1b 183#endif /* #else #ifdef DEBUG_FULL_MB */
27b012e2 184
1430ee0b 185void wait_for_quiescent_state(void)
27b012e2 186{
0a52082b 187 struct reader_registry *index;
27b012e2 188
0a52082b 189 if (!registry)
27b012e2 190 return;
40e140c9
MD
191 /*
192 * Wait for each thread urcu_active_readers count to become 0.
27b012e2 193 */
0a52082b 194 for (index = registry; index < registry + num_readers; index++) {
e8043c1b
MD
195#ifndef HAS_INCOHERENT_CACHES
196 while (rcu_old_gp_ongoing(index->urcu_active_readers))
197 cpu_relax();
198#else /* #ifndef HAS_INCOHERENT_CACHES */
40e140c9 199 int wait_loops = 0;
27b012e2 200 /*
40e140c9
MD
201 * BUSY-LOOP. Force the reader thread to commit its
202 * urcu_active_readers update to memory if we wait for too long.
27b012e2 203 */
40e140c9
MD
204 while (rcu_old_gp_ongoing(index->urcu_active_readers)) {
205 if (wait_loops++ == KICK_READER_LOOPS) {
09a9f986 206 force_mb_single_thread(index);
40e140c9 207 wait_loops = 0;
3b55dbf4
MD
208 } else {
209 cpu_relax();
40e140c9
MD
210 }
211 }
e8043c1b 212#endif /* #else #ifndef HAS_INCOHERENT_CACHES */
27b012e2 213 }
27b012e2
MD
214}
215
9598a481 216void synchronize_rcu(void)
2bc59bd7 217{
135530fd
MD
218 internal_urcu_lock();
219
9598a481 220 /* All threads should read qparity before accessing data structure
135530fd
MD
221 * where new ptr points to. Must be done within internal_urcu_lock
222 * because it iterates on reader threads.*/
9598a481 223 /* Write new ptr before changing the qparity */
2bc59bd7 224 force_mb_all_threads();
9598a481 225
9598a481 226 switch_next_urcu_qparity(); /* 0 -> 1 */
2bc59bd7
PM
227
228 /*
9598a481
MD
229 * Must commit qparity update to memory before waiting for parity
230 * 0 quiescent state. Failure to do so could result in the writer
231 * waiting forever while new readers are always accessing data (no
232 * progress).
b0d5e790 233 * Ensured by STORE_SHARED and LOAD_SHARED.
2bc59bd7 234 */
2bc59bd7 235
9598a481
MD
236 /*
237 * Wait for previous parity to be empty of readers.
238 */
239 wait_for_quiescent_state(); /* Wait readers in parity 0 */
9598a481
MD
240
241 /*
242 * Must finish waiting for quiescent state for parity 0 before
243 * committing qparity update to memory. Failure to do so could result in
244 * the writer waiting forever while new readers are always accessing
245 * data (no progress).
b0d5e790 246 * Ensured by STORE_SHARED and LOAD_SHARED.
9598a481 247 */
9598a481
MD
248
249 switch_next_urcu_qparity(); /* 1 -> 0 */
9598a481
MD
250
251 /*
252 * Must commit qparity update to memory before waiting for parity
253 * 1 quiescent state. Failure to do so could result in the writer
254 * waiting forever while new readers are always accessing data (no
255 * progress).
b0d5e790 256 * Ensured by STORE_SHARED and LOAD_SHARED.
9598a481 257 */
9598a481
MD
258
259 /*
260 * Wait for previous parity to be empty of readers.
261 */
262 wait_for_quiescent_state(); /* Wait readers in parity 1 */
9598a481 263
9598a481 264 /* Finish waiting for reader threads before letting the old ptr being
135530fd
MD
265 * freed. Must be done within internal_urcu_lock because it iterates on
266 * reader threads. */
9598a481 267 force_mb_all_threads();
135530fd
MD
268
269 internal_urcu_unlock();
2bc59bd7
PM
270}
271
27b012e2
MD
272void urcu_add_reader(pthread_t id)
273{
0a52082b 274 struct reader_registry *oldarray;
f69f195a 275
0a52082b 276 if (!registry) {
27b012e2 277 alloc_readers = INIT_NUM_THREADS;
f69f195a 278 num_readers = 0;
0a52082b
MD
279 registry =
280 malloc(sizeof(struct reader_registry) * alloc_readers);
27b012e2
MD
281 }
282 if (alloc_readers < num_readers + 1) {
0a52082b
MD
283 oldarray = registry;
284 registry = malloc(sizeof(struct reader_registry)
27b012e2 285 * (alloc_readers << 1));
0a52082b
MD
286 memcpy(registry, oldarray,
287 sizeof(struct reader_registry) * alloc_readers);
27b012e2
MD
288 alloc_readers <<= 1;
289 free(oldarray);
290 }
0a52082b 291 registry[num_readers].tid = id;
27b012e2 292 /* reference to the TLS of _this_ reader thread. */
0a52082b 293 registry[num_readers].urcu_active_readers = &urcu_active_readers;
09a9f986 294 registry[num_readers].need_mb = &need_mb;
27b012e2
MD
295 num_readers++;
296}
297
298/*
299 * Never shrink (implementation limitation).
300 * This is O(nb threads). Eventually use a hash table.
301 */
302void urcu_remove_reader(pthread_t id)
303{
0a52082b 304 struct reader_registry *index;
27b012e2 305
0a52082b
MD
306 assert(registry != NULL);
307 for (index = registry; index < registry + num_readers; index++) {
e6d6e2dc 308 if (pthread_equal(index->tid, id)) {
0a52082b
MD
309 memcpy(index, &registry[num_readers - 1],
310 sizeof(struct reader_registry));
311 registry[num_readers - 1].tid = 0;
312 registry[num_readers - 1].urcu_active_readers = NULL;
27b012e2
MD
313 num_readers--;
314 return;
315 }
316 }
317 /* Hrm not found, forgot to register ? */
318 assert(0);
319}
320
321void urcu_register_thread(void)
322{
c265818b 323 internal_urcu_lock();
41718ff9 324 urcu_add_reader(pthread_self());
c265818b 325 internal_urcu_unlock();
27b012e2
MD
326}
327
f69f195a 328void urcu_unregister_thread(void)
27b012e2 329{
c265818b 330 internal_urcu_lock();
41718ff9 331 urcu_remove_reader(pthread_self());
c265818b 332 internal_urcu_unlock();
27b012e2
MD
333}
334
bb488185 335#ifndef DEBUG_FULL_MB
f69f195a 336void sigurcu_handler(int signo, siginfo_t *siginfo, void *context)
27b012e2 337{
40e140c9
MD
338 /*
339 * Executing this smp_mb() is the only purpose of this signal handler.
340 * It punctually promotes barrier() into smp_mb() on every thread it is
341 * executed on.
342 */
b715b99e 343 smp_mb();
09a9f986
PM
344 need_mb = 0;
345 smp_mb();
27b012e2
MD
346}
347
348void __attribute__((constructor)) urcu_init(void)
349{
350 struct sigaction act;
351 int ret;
352
353 act.sa_sigaction = sigurcu_handler;
354 ret = sigaction(SIGURCU, &act, NULL);
f69f195a
MD
355 if (ret) {
356 perror("Error in sigaction");
27b012e2
MD
357 exit(-1);
358 }
359}
360
361void __attribute__((destructor)) urcu_exit(void)
362{
363 struct sigaction act;
364 int ret;
365
366 ret = sigaction(SIGURCU, NULL, &act);
f69f195a
MD
367 if (ret) {
368 perror("Error in sigaction");
27b012e2
MD
369 exit(-1);
370 }
371 assert(act.sa_sigaction == sigurcu_handler);
0a52082b 372 free(registry);
27b012e2 373}
e8043c1b 374#endif /* #ifndef DEBUG_FULL_MB */
This page took 0.060827 seconds and 4 git commands to generate.