Fix: x86 and s390: uatomic __hp() macro clang support
[urcu.git] / src / 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
e37faee1 26#define URCU_NO_COMPAT_IDENTIFIERS
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
4477a870
MD
38#include <urcu/wfcqueue.h>
39#include <urcu/map/urcu-qsbr.h>
727f819d 40#define BUILD_QSBR_LIB
4477a870
MD
41#include <urcu/static/urcu-qsbr.h>
42#include <urcu/pointer.h>
43#include <urcu/tls-compat.h>
71c811bf 44
4a6d7378 45#include "urcu-die.h"
cba82d7b 46#include "urcu-wait.h"
ce28e67a 47#include "urcu-utils.h"
4a6d7378 48
4477a870 49#define URCU_API_MAP
9f1621ca 50/* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
71c811bf 51#undef _LGPL_SOURCE
4477a870 52#include <urcu/urcu-qsbr.h>
71c811bf 53#define _LGPL_SOURCE
9f1621ca 54
4477a870 55void __attribute__((destructor)) urcu_qsbr_exit(void);
f6d18c64 56
731ccb96
MD
57/*
58 * rcu_gp_lock ensures mutual exclusion between threads calling
59 * synchronize_rcu().
60 */
6abb4bd5 61static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
731ccb96
MD
62/*
63 * rcu_registry_lock ensures mutual exclusion between threads
64 * registering and unregistering themselves to/from the registry, and
65 * with threads reading that registry from synchronize_rcu(). However,
66 * this lock is not held all the way through the completion of awaiting
67 * for the grace period. It is sporadically released between iterations
68 * on the registry.
69 * rcu_registry_lock may nest inside rcu_gp_lock.
70 */
71static pthread_mutex_t rcu_registry_lock = PTHREAD_MUTEX_INITIALIZER;
4477a870 72struct urcu_gp urcu_qsbr_gp = { .ctr = URCU_QSBR_GP_ONLINE };
9f1621ca 73
408f6d92
PB
74/*
75 * Active attempts to check for reader Q.S. before calling futex().
76 */
77#define RCU_QS_ACTIVE_ATTEMPTS 100
78
9f1621ca
MD
79/*
80 * Written to only by each individual reader. Read by both the reader and the
81 * writers.
82 */
4477a870 83DEFINE_URCU_TLS(struct urcu_qsbr_reader, urcu_qsbr_reader);
9f1621ca 84
16aa9ee8 85static CDS_LIST_HEAD(registry);
9f1621ca 86
6362f68f 87/*
bf6822a6 88 * Queue keeping threads awaiting to wait for a grace period. Contains
6362f68f
MD
89 * struct gp_waiters_thread objects.
90 */
bf6822a6 91static DEFINE_URCU_WAIT_QUEUE(gp_waiters);
6362f68f 92
6abb4bd5 93static void mutex_lock(pthread_mutex_t *mutex)
9f1621ca
MD
94{
95 int ret;
96
97#ifndef DISTRUST_SIGNALS_EXTREME
6abb4bd5 98 ret = pthread_mutex_lock(mutex);
4a6d7378
MD
99 if (ret)
100 urcu_die(ret);
9f1621ca 101#else /* #ifndef DISTRUST_SIGNALS_EXTREME */
6abb4bd5 102 while ((ret = pthread_mutex_trylock(mutex)) != 0) {
4a6d7378
MD
103 if (ret != EBUSY && ret != EINTR)
104 urcu_die(ret);
9f1621ca
MD
105 poll(NULL,0,10);
106 }
107#endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
108}
109
6abb4bd5 110static void mutex_unlock(pthread_mutex_t *mutex)
9f1621ca
MD
111{
112 int ret;
113
6abb4bd5 114 ret = pthread_mutex_unlock(mutex);
4a6d7378
MD
115 if (ret)
116 urcu_die(ret);
9f1621ca
MD
117}
118
bc6c15bb
MD
119/*
120 * synchronize_rcu() waiting. Single thread.
121 */
4d703340 122static void wait_gp(void)
bc6c15bb 123{
4d703340 124 /* Read reader_gp before read futex */
5481ddb3 125 cmm_smp_rmb();
4477a870 126 if (uatomic_read(&urcu_qsbr_gp.futex) != -1)
b0a841b4 127 return;
4477a870 128 while (futex_noasync(&urcu_qsbr_gp.futex, FUTEX_WAIT, -1,
b0a841b4
MD
129 NULL, NULL, 0)) {
130 switch (errno) {
131 case EWOULDBLOCK:
132 /* Value already changed. */
133 return;
134 case EINTR:
135 /* Retry if interrupted by signal. */
136 break; /* Get out of switch. */
137 default:
138 /* Unexpected error. */
139 urcu_die(errno);
140 }
141 }
bc6c15bb
MD
142}
143
731ccb96
MD
144/*
145 * Always called with rcu_registry lock held. Releases this lock between
146 * iterations and grabs it again. Holds the lock when it returns.
147 */
708d89f0
MD
148static void wait_for_readers(struct cds_list_head *input_readers,
149 struct cds_list_head *cur_snap_readers,
150 struct cds_list_head *qsreaders)
9f1621ca 151{
9340c38d 152 unsigned int wait_loops = 0;
4477a870 153 struct urcu_qsbr_reader *index, *tmp;
9f1621ca 154
9f1621ca 155 /*
4477a870 156 * Wait for each thread URCU_TLS(urcu_qsbr_reader).ctr to either
f6b42f9c 157 * indicate quiescence (offline), or for them to observe the
4477a870 158 * current urcu_qsbr_gp.ctr value.
9f1621ca 159 */
4d703340 160 for (;;) {
5e81fed7
MD
161 if (wait_loops < RCU_QS_ACTIVE_ATTEMPTS)
162 wait_loops++;
83a2c421 163 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
4477a870 164 uatomic_set(&urcu_qsbr_gp.futex, -1);
83a2c421
PB
165 /*
166 * Write futex before write waiting (the other side
167 * reads them in the opposite order).
168 */
169 cmm_smp_wmb();
708d89f0 170 cds_list_for_each_entry(index, input_readers, node) {
83a2c421
PB
171 _CMM_STORE_SHARED(index->waiting, 1);
172 }
4d703340 173 /* Write futex before read reader_gp */
5481ddb3 174 cmm_smp_mb();
4d703340 175 }
708d89f0 176 cds_list_for_each_entry_safe(index, tmp, input_readers, node) {
4477a870
MD
177 switch (urcu_qsbr_reader_state(&index->ctr)) {
178 case URCU_READER_ACTIVE_CURRENT:
708d89f0
MD
179 if (cur_snap_readers) {
180 cds_list_move(&index->node,
181 cur_snap_readers);
182 break;
183 }
184 /* Fall-through */
4477a870 185 case URCU_READER_INACTIVE:
708d89f0
MD
186 cds_list_move(&index->node, qsreaders);
187 break;
4477a870 188 case URCU_READER_ACTIVE_OLD:
708d89f0
MD
189 /*
190 * Old snapshot. Leaving node in
191 * input_readers will make us busy-loop
192 * until the snapshot becomes current or
193 * the reader becomes inactive.
194 */
195 break;
196 }
4d703340 197 }
bc6c15bb 198
708d89f0 199 if (cds_list_empty(input_readers)) {
83a2c421 200 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
4d703340 201 /* Read reader_gp before write futex */
5481ddb3 202 cmm_smp_mb();
4477a870 203 uatomic_set(&urcu_qsbr_gp.futex, 0);
4d703340
MD
204 }
205 break;
206 } else {
731ccb96
MD
207 /* Temporarily unlock the registry lock. */
208 mutex_unlock(&rcu_registry_lock);
83a2c421 209 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
4d703340 210 wait_gp();
bc6c15bb 211 } else {
9f1621ca 212#ifndef HAS_INCOHERENT_CACHES
06f22bdb 213 caa_cpu_relax();
9f1621ca 214#else /* #ifndef HAS_INCOHERENT_CACHES */
5481ddb3 215 cmm_smp_mb();
9f1621ca 216#endif /* #else #ifndef HAS_INCOHERENT_CACHES */
bc6c15bb 217 }
731ccb96
MD
218 /* Re-lock the registry lock before the next loop. */
219 mutex_lock(&rcu_registry_lock);
bc6c15bb 220 }
9f1621ca
MD
221 }
222}
223
47d2f29e
MD
224/*
225 * Using a two-subphases algorithm for architectures with smaller than 64-bit
226 * long-size to ensure we do not encounter an overflow bug.
227 */
228
b39e1761 229#if (CAA_BITS_PER_LONG < 64)
4477a870 230void urcu_qsbr_synchronize_rcu(void)
47d2f29e 231{
708d89f0
MD
232 CDS_LIST_HEAD(cur_snap_readers);
233 CDS_LIST_HEAD(qsreaders);
bc49c323 234 unsigned long was_online;
bf6822a6
MD
235 DEFINE_URCU_WAIT_NODE(wait, URCU_WAIT_WAITING);
236 struct urcu_waiters waiters;
bc49c323 237
4477a870 238 was_online = urcu_qsbr_read_ongoing();
bc49c323 239
47d2f29e 240 /* All threads should read qparity before accessing data structure
27b940e7
PB
241 * where new ptr points to. In the "then" case, rcu_thread_offline
242 * includes a memory barrier.
243 *
bc49c323 244 * Mark the writer thread offline to make sure we don't wait for
5e77fc1f
PM
245 * our own quiescent state. This allows using synchronize_rcu()
246 * in threads registered as readers.
bc49c323 247 */
27b940e7 248 if (was_online)
4477a870 249 urcu_qsbr_thread_offline();
27b940e7
PB
250 else
251 cmm_smp_mb();
bc49c323 252
6362f68f 253 /*
bf6822a6 254 * Add ourself to gp_waiters queue of threads awaiting to wait
6362f68f 255 * for a grace period. Proceed to perform the grace period only
bf6822a6 256 * if we are the first thread added into the queue.
6362f68f 257 */
bf6822a6
MD
258 if (urcu_wait_add(&gp_waiters, &wait) != 0) {
259 /* Not first in queue: will be awakened by another thread. */
260 urcu_adaptative_busy_wait(&wait);
6362f68f
MD
261 goto gp_end;
262 }
bf6822a6
MD
263 /* We won't need to wake ourself up */
264 urcu_wait_set_state(&wait, URCU_WAIT_RUNNING);
6362f68f 265
6abb4bd5 266 mutex_lock(&rcu_gp_lock);
47d2f29e 267
6362f68f 268 /*
bf6822a6 269 * Move all waiters into our local queue.
6362f68f 270 */
bf6822a6 271 urcu_move_waiters(&waiters, &gp_waiters);
6362f68f 272
731ccb96
MD
273 mutex_lock(&rcu_registry_lock);
274
16aa9ee8 275 if (cds_list_empty(&registry))
2dfb8b5e 276 goto out;
47d2f29e
MD
277
278 /*
f6b42f9c 279 * Wait for readers to observe original parity or be quiescent.
731ccb96
MD
280 * wait_for_readers() can release and grab again rcu_registry_lock
281 * interally.
47d2f29e 282 */
708d89f0 283 wait_for_readers(&registry, &cur_snap_readers, &qsreaders);
47d2f29e
MD
284
285 /*
f6b42f9c 286 * Must finish waiting for quiescent state for original parity
4477a870 287 * before committing next urcu_qsbr_gp.ctr update to memory. Failure
f6b42f9c 288 * to do so could result in the writer waiting forever while new
5e77fc1f 289 * readers are always accessing data (no progress). Enforce
4477a870
MD
290 * compiler-order of load URCU_TLS(urcu_qsbr_reader).ctr before store
291 * to urcu_qsbr_gp.ctr.
47d2f29e 292 */
5481ddb3 293 cmm_barrier();
47d2f29e 294
47d2f29e 295 /*
5481ddb3 296 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
2dfb8b5e
MD
297 * model easier to understand. It does not have a big performance impact
298 * anyway, given this is the write-side.
47d2f29e 299 */
5481ddb3 300 cmm_smp_mb();
47d2f29e 301
f6b42f9c 302 /* Switch parity: 0 -> 1, 1 -> 0 */
4477a870 303 CMM_STORE_SHARED(urcu_qsbr_gp.ctr, urcu_qsbr_gp.ctr ^ URCU_QSBR_GP_CTR);
f6b42f9c 304
47d2f29e 305 /*
4477a870 306 * Must commit urcu_qsbr_gp.ctr update to memory before waiting for
f6b42f9c
MD
307 * quiescent state. Failure to do so could result in the writer
308 * waiting forever while new readers are always accessing data
4477a870
MD
309 * (no progress). Enforce compiler-order of store to urcu_qsbr_gp.ctr
310 * before load URCU_TLS(urcu_qsbr_reader).ctr.
47d2f29e 311 */
f6b42f9c
MD
312 cmm_barrier();
313
314 /*
315 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
316 * model easier to understand. It does not have a big performance impact
317 * anyway, given this is the write-side.
318 */
319 cmm_smp_mb();
320
321 /*
322 * Wait for readers to observe new parity or be quiescent.
731ccb96
MD
323 * wait_for_readers() can release and grab again rcu_registry_lock
324 * interally.
f6b42f9c 325 */
708d89f0
MD
326 wait_for_readers(&cur_snap_readers, NULL, &qsreaders);
327
328 /*
329 * Put quiescent reader list back into registry.
330 */
331 cds_list_splice(&qsreaders, &registry);
2dfb8b5e 332out:
731ccb96 333 mutex_unlock(&rcu_registry_lock);
6abb4bd5 334 mutex_unlock(&rcu_gp_lock);
bf6822a6 335 urcu_wake_all_waiters(&waiters);
6362f68f 336gp_end:
bc49c323
MD
337 /*
338 * Finish waiting for reader threads before letting the old ptr being
47d2f29e
MD
339 * freed.
340 */
bc49c323 341 if (was_online)
4477a870 342 urcu_qsbr_thread_online();
27b940e7
PB
343 else
344 cmm_smp_mb();
47d2f29e 345}
b39e1761 346#else /* !(CAA_BITS_PER_LONG < 64) */
4477a870 347void urcu_qsbr_synchronize_rcu(void)
9f1621ca 348{
708d89f0 349 CDS_LIST_HEAD(qsreaders);
f0f7dbdd 350 unsigned long was_online;
bf6822a6
MD
351 DEFINE_URCU_WAIT_NODE(wait, URCU_WAIT_WAITING);
352 struct urcu_waiters waiters;
ff2f67a0 353
4477a870 354 was_online = urcu_qsbr_read_ongoing();
ff2f67a0
MD
355
356 /*
357 * Mark the writer thread offline to make sure we don't wait for
5e77fc1f
PM
358 * our own quiescent state. This allows using synchronize_rcu()
359 * in threads registered as readers.
ff2f67a0 360 */
27b940e7 361 if (was_online)
4477a870 362 urcu_qsbr_thread_offline();
27b940e7
PB
363 else
364 cmm_smp_mb();
ff2f67a0 365
6362f68f 366 /*
bf6822a6 367 * Add ourself to gp_waiters queue of threads awaiting to wait
6362f68f 368 * for a grace period. Proceed to perform the grace period only
bf6822a6 369 * if we are the first thread added into the queue.
6362f68f 370 */
bf6822a6
MD
371 if (urcu_wait_add(&gp_waiters, &wait) != 0) {
372 /* Not first in queue: will be awakened by another thread. */
373 urcu_adaptative_busy_wait(&wait);
6362f68f
MD
374 goto gp_end;
375 }
bf6822a6
MD
376 /* We won't need to wake ourself up */
377 urcu_wait_set_state(&wait, URCU_WAIT_RUNNING);
6362f68f 378
6abb4bd5 379 mutex_lock(&rcu_gp_lock);
6362f68f
MD
380
381 /*
bf6822a6 382 * Move all waiters into our local queue.
6362f68f 383 */
bf6822a6 384 urcu_move_waiters(&waiters, &gp_waiters);
6362f68f 385
731ccb96
MD
386 mutex_lock(&rcu_registry_lock);
387
16aa9ee8 388 if (cds_list_empty(&registry))
2dfb8b5e 389 goto out;
f6b42f9c
MD
390
391 /* Increment current G.P. */
4477a870 392 CMM_STORE_SHARED(urcu_qsbr_gp.ctr, urcu_qsbr_gp.ctr + URCU_QSBR_GP_CTR);
f6b42f9c
MD
393
394 /*
4477a870 395 * Must commit urcu_qsbr_gp.ctr update to memory before waiting for
f6b42f9c
MD
396 * quiescent state. Failure to do so could result in the writer
397 * waiting forever while new readers are always accessing data
4477a870
MD
398 * (no progress). Enforce compiler-order of store to urcu_qsbr_gp.ctr
399 * before load URCU_TLS(urcu_qsbr_reader).ctr.
f6b42f9c
MD
400 */
401 cmm_barrier();
402
403 /*
404 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
405 * model easier to understand. It does not have a big performance impact
406 * anyway, given this is the write-side.
407 */
408 cmm_smp_mb();
409
410 /*
411 * Wait for readers to observe new count of be quiescent.
731ccb96
MD
412 * wait_for_readers() can release and grab again rcu_registry_lock
413 * interally.
f6b42f9c 414 */
708d89f0
MD
415 wait_for_readers(&registry, NULL, &qsreaders);
416
417 /*
418 * Put quiescent reader list back into registry.
419 */
420 cds_list_splice(&qsreaders, &registry);
2dfb8b5e 421out:
731ccb96 422 mutex_unlock(&rcu_registry_lock);
6abb4bd5 423 mutex_unlock(&rcu_gp_lock);
bf6822a6 424 urcu_wake_all_waiters(&waiters);
6362f68f 425gp_end:
ff2f67a0 426 if (was_online)
4477a870 427 urcu_qsbr_thread_online();
27b940e7
PB
428 else
429 cmm_smp_mb();
9f1621ca 430}
b39e1761 431#endif /* !(CAA_BITS_PER_LONG < 64) */
9f1621ca
MD
432
433/*
434 * library wrappers to be used by non-LGPL compatible source code.
435 */
436
4477a870 437void urcu_qsbr_read_lock(void)
9f1621ca 438{
4477a870 439 _urcu_qsbr_read_lock();
9f1621ca
MD
440}
441
4477a870 442void urcu_qsbr_read_unlock(void)
9f1621ca 443{
4477a870 444 _urcu_qsbr_read_unlock();
9f1621ca
MD
445}
446
4477a870 447int urcu_qsbr_read_ongoing(void)
882f3357 448{
4477a870 449 return _urcu_qsbr_read_ongoing();
882f3357 450}
4477a870 451void rcu_read_ongoing_qsbr();
882f3357 452
4477a870 453void urcu_qsbr_quiescent_state(void)
7ac06cef 454{
4477a870 455 _urcu_qsbr_quiescent_state();
7ac06cef 456}
4477a870 457void rcu_quiescent_state_qsbr();
7ac06cef 458
4477a870 459void urcu_qsbr_thread_offline(void)
7ac06cef 460{
4477a870 461 _urcu_qsbr_thread_offline();
7ac06cef 462}
4477a870 463void rcu_thread_offline_qsbr();
7ac06cef 464
4477a870 465void urcu_qsbr_thread_online(void)
7ac06cef 466{
4477a870 467 _urcu_qsbr_thread_online();
7ac06cef
MD
468}
469
4477a870 470void urcu_qsbr_register_thread(void)
9f1621ca 471{
4477a870
MD
472 URCU_TLS(urcu_qsbr_reader).tid = pthread_self();
473 assert(URCU_TLS(urcu_qsbr_reader).ctr == 0);
4f8e3380 474
731ccb96 475 mutex_lock(&rcu_registry_lock);
4477a870
MD
476 assert(!URCU_TLS(urcu_qsbr_reader).registered);
477 URCU_TLS(urcu_qsbr_reader).registered = 1;
478 cds_list_add(&URCU_TLS(urcu_qsbr_reader).node, &registry);
731ccb96 479 mutex_unlock(&rcu_registry_lock);
4477a870 480 _urcu_qsbr_thread_online();
9f1621ca
MD
481}
482
4477a870 483void urcu_qsbr_unregister_thread(void)
9f1621ca 484{
76f3022f
MD
485 /*
486 * We have to make the thread offline otherwise we end up dealocking
487 * with a waiting writer.
488 */
4477a870
MD
489 _urcu_qsbr_thread_offline();
490 assert(URCU_TLS(urcu_qsbr_reader).registered);
491 URCU_TLS(urcu_qsbr_reader).registered = 0;
731ccb96 492 mutex_lock(&rcu_registry_lock);
4477a870 493 cds_list_del(&URCU_TLS(urcu_qsbr_reader).node);
731ccb96 494 mutex_unlock(&rcu_registry_lock);
9f1621ca 495}
f6d18c64 496
4477a870 497void urcu_qsbr_exit(void)
f6d18c64 498{
01cadde4
MD
499 /*
500 * Assertion disabled because call_rcu threads are now rcu
501 * readers, and left running at exit.
502 * assert(cds_list_empty(&registry));
503 */
f6d18c64 504}
5e77fc1f 505
5e6b23a6 506DEFINE_RCU_FLAVOR(rcu_flavor);
541d828d 507
5e77fc1f 508#include "urcu-call-rcu-impl.h"
0376e7b2 509#include "urcu-defer-impl.h"
This page took 0.070914 seconds and 4 git commands to generate.