Add Promela model
[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
9 */
10
27b012e2
MD
11#include <stdio.h>
12#include <pthread.h>
13#include <signal.h>
14#include <assert.h>
f69f195a
MD
15#include <stdlib.h>
16#include <string.h>
27b012e2
MD
17
18#include "urcu.h"
19
20pthread_mutex_t urcu_mutex = PTHREAD_MUTEX_INITIALIZER;
21
128166c9
MD
22/*
23 * Global grace period counter.
24 * Contains the current RCU_GP_CTR_BIT.
25 * Also has a RCU_GP_CTR_BIT of 1, to accelerate the reader fast path.
26 */
27long urcu_gp_ctr = RCU_GP_COUNT;
27b012e2 28
6e8b8429 29long __thread urcu_active_readers;
27b012e2
MD
30
31/* Thread IDs of registered readers */
32#define INIT_NUM_THREADS 4
33
34struct reader_data {
35 pthread_t tid;
128166c9 36 long *urcu_active_readers;
27b012e2
MD
37};
38
cf380c2f 39#ifdef DEBUG_YIELD
9d335088
MD
40unsigned int yield_active;
41unsigned int __thread rand_yield;
cf380c2f
MD
42#endif
43
27b012e2
MD
44static struct reader_data *reader_data;
45static int num_readers, alloc_readers;
46static int sig_done;
47
c265818b 48void internal_urcu_lock(void)
41718ff9
MD
49{
50 int ret;
51 ret = pthread_mutex_lock(&urcu_mutex);
52 if (ret) {
53 perror("Error in pthread mutex lock");
54 exit(-1);
55 }
56}
57
c265818b 58void internal_urcu_unlock(void)
41718ff9
MD
59{
60 int ret;
61
62 ret = pthread_mutex_unlock(&urcu_mutex);
63 if (ret) {
64 perror("Error in pthread mutex unlock");
65 exit(-1);
66 }
67}
68
27b012e2
MD
69/*
70 * called with urcu_mutex held.
71 */
1430ee0b 72static void switch_next_urcu_qparity(void)
27b012e2 73{
1430ee0b 74 urcu_gp_ctr ^= RCU_GP_CTR_BIT;
27b012e2
MD
75}
76
bb488185
MD
77#ifdef DEBUG_FULL_MB
78static void force_mb_all_threads(void)
79{
80 mb();
81}
82#else
27b012e2
MD
83static void force_mb_all_threads(void)
84{
f69f195a 85 struct reader_data *index;
27b012e2
MD
86 /*
87 * Ask for each threads to execute a mb() so we can consider the
88 * compiler barriers around rcu read lock as real memory barriers.
89 */
90 if (!reader_data)
91 return;
cf380c2f 92 debug_yield_write();
27b012e2 93 sig_done = 0;
cf380c2f 94 debug_yield_write();
f69f195a 95 mb(); /* write sig_done before sending the signals */
cf380c2f
MD
96 debug_yield_write();
97 for (index = reader_data; index < reader_data + num_readers; index++) {
f69f195a 98 pthread_kill(index->tid, SIGURCU);
cf380c2f
MD
99 debug_yield_write();
100 }
27b012e2
MD
101 /*
102 * Wait for sighandler (and thus mb()) to execute on every thread.
103 * BUSY-LOOP.
104 */
105 while (sig_done < num_readers)
106 barrier();
cf380c2f 107 debug_yield_write();
f69f195a 108 mb(); /* read sig_done before ending the barrier */
cf380c2f 109 debug_yield_write();
27b012e2 110}
bb488185 111#endif
27b012e2 112
1430ee0b 113void wait_for_quiescent_state(void)
27b012e2 114{
f69f195a 115 struct reader_data *index;
27b012e2
MD
116
117 if (!reader_data)
118 return;
119 /* Wait for each thread urcu_active_readers count to become 0.
120 */
f69f195a 121 for (index = reader_data; index < reader_data + num_readers; index++) {
27b012e2
MD
122 /*
123 * BUSY-LOOP.
124 */
1430ee0b 125 while (rcu_old_gp_ongoing(index->urcu_active_readers))
27b012e2
MD
126 barrier();
127 }
27b012e2
MD
128}
129
9598a481 130void synchronize_rcu(void)
2bc59bd7 131{
9598a481
MD
132 /* All threads should read qparity before accessing data structure
133 * where new ptr points to. */
134 /* Write new ptr before changing the qparity */
2bc59bd7 135 force_mb_all_threads();
cf380c2f 136 debug_yield_write();
9598a481
MD
137
138 internal_urcu_lock();
139 debug_yield_write();
140
141 switch_next_urcu_qparity(); /* 0 -> 1 */
cf380c2f 142 debug_yield_write();
2bc59bd7
PM
143
144 /*
9598a481
MD
145 * Must commit qparity update to memory before waiting for parity
146 * 0 quiescent state. Failure to do so could result in the writer
147 * waiting forever while new readers are always accessing data (no
148 * progress).
2bc59bd7 149 */
9598a481 150 mb();
2bc59bd7 151
9598a481
MD
152 /*
153 * Wait for previous parity to be empty of readers.
154 */
155 wait_for_quiescent_state(); /* Wait readers in parity 0 */
cf380c2f 156 debug_yield_write();
9598a481
MD
157
158 /*
159 * Must finish waiting for quiescent state for parity 0 before
160 * committing qparity update to memory. Failure to do so could result in
161 * the writer waiting forever while new readers are always accessing
162 * data (no progress).
163 */
164 mb();
165
166 switch_next_urcu_qparity(); /* 1 -> 0 */
cf380c2f 167 debug_yield_write();
9598a481
MD
168
169 /*
170 * Must commit qparity update to memory before waiting for parity
171 * 1 quiescent state. Failure to do so could result in the writer
172 * waiting forever while new readers are always accessing data (no
173 * progress).
174 */
175 mb();
176
177 /*
178 * Wait for previous parity to be empty of readers.
179 */
180 wait_for_quiescent_state(); /* Wait readers in parity 1 */
cf380c2f 181 debug_yield_write();
9598a481 182
e7b43771 183 internal_urcu_unlock();
cf380c2f 184 debug_yield_write();
9598a481
MD
185
186 /* All threads should finish using the data referred to by old ptr
187 * before decrementing their urcu_active_readers count */
188 /* Finish waiting for reader threads before letting the old ptr being
189 * freed. */
190 force_mb_all_threads();
191 debug_yield_write();
2bc59bd7
PM
192}
193
27b012e2
MD
194void urcu_add_reader(pthread_t id)
195{
f69f195a
MD
196 struct reader_data *oldarray;
197
27b012e2
MD
198 if (!reader_data) {
199 alloc_readers = INIT_NUM_THREADS;
f69f195a 200 num_readers = 0;
27b012e2
MD
201 reader_data =
202 malloc(sizeof(struct reader_data) * alloc_readers);
27b012e2
MD
203 }
204 if (alloc_readers < num_readers + 1) {
27b012e2
MD
205 oldarray = reader_data;
206 reader_data = malloc(sizeof(struct reader_data)
207 * (alloc_readers << 1));
208 memcpy(reader_data, oldarray,
209 sizeof(struct reader_data) * alloc_readers);
210 alloc_readers <<= 1;
211 free(oldarray);
212 }
213 reader_data[num_readers].tid = id;
214 /* reference to the TLS of _this_ reader thread. */
1430ee0b 215 reader_data[num_readers].urcu_active_readers = &urcu_active_readers;
27b012e2
MD
216 num_readers++;
217}
218
219/*
220 * Never shrink (implementation limitation).
221 * This is O(nb threads). Eventually use a hash table.
222 */
223void urcu_remove_reader(pthread_t id)
224{
225 struct reader_data *index;
226
227 assert(reader_data != NULL);
228 for (index = reader_data; index < reader_data + num_readers; index++) {
e6d6e2dc 229 if (pthread_equal(index->tid, id)) {
27b012e2
MD
230 memcpy(index, &reader_data[num_readers - 1],
231 sizeof(struct reader_data));
232 reader_data[num_readers - 1].tid = 0;
233 reader_data[num_readers - 1].urcu_active_readers = NULL;
234 num_readers--;
235 return;
236 }
237 }
238 /* Hrm not found, forgot to register ? */
239 assert(0);
240}
241
242void urcu_register_thread(void)
243{
c265818b 244 internal_urcu_lock();
41718ff9 245 urcu_add_reader(pthread_self());
c265818b 246 internal_urcu_unlock();
27b012e2
MD
247}
248
f69f195a 249void urcu_unregister_thread(void)
27b012e2 250{
c265818b 251 internal_urcu_lock();
41718ff9 252 urcu_remove_reader(pthread_self());
c265818b 253 internal_urcu_unlock();
27b012e2
MD
254}
255
bb488185 256#ifndef DEBUG_FULL_MB
f69f195a 257void sigurcu_handler(int signo, siginfo_t *siginfo, void *context)
27b012e2
MD
258{
259 mb();
260 atomic_inc(&sig_done);
261}
262
263void __attribute__((constructor)) urcu_init(void)
264{
265 struct sigaction act;
266 int ret;
267
268 act.sa_sigaction = sigurcu_handler;
269 ret = sigaction(SIGURCU, &act, NULL);
f69f195a
MD
270 if (ret) {
271 perror("Error in sigaction");
27b012e2
MD
272 exit(-1);
273 }
274}
275
276void __attribute__((destructor)) urcu_exit(void)
277{
278 struct sigaction act;
279 int ret;
280
281 ret = sigaction(SIGURCU, NULL, &act);
f69f195a
MD
282 if (ret) {
283 perror("Error in sigaction");
27b012e2
MD
284 exit(-1);
285 }
286 assert(act.sa_sigaction == sigurcu_handler);
287 free(reader_data);
288}
bb488185 289#endif
This page took 0.055585 seconds and 4 git commands to generate.