4 * Userspace RCU library - batch memory reclamation
6 * Copyright (c) 2009 Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
32 #include "urcu-reclaim-static.h"
33 /* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
34 #include "urcu-reclaim.h"
36 void __attribute__((destructor
)) urcu_reclaim_exit(void);
38 extern void synchronize_rcu(void);
41 * urcu_reclaim_mutex nests inside reclaim_thread_mutex.
43 static pthread_mutex_t urcu_reclaim_mutex
= PTHREAD_MUTEX_INITIALIZER
;
44 static pthread_mutex_t reclaim_thread_mutex
= PTHREAD_MUTEX_INITIALIZER
;
47 * Written to only by each individual reclaimer. Read by both the reclaimer and
48 * the reclamation tread.
50 struct reclaim_queue __thread reclaim_queue
;
52 /* Thread IDs of registered reclaimers */
53 #define INIT_NUM_THREADS 4
55 struct reclaimer_registry
{
57 struct reclaim_queue
*reclaim_queue
;
58 unsigned long last_head
;
61 static struct reclaimer_registry
*registry
;
62 static int num_reclaimers
, alloc_reclaimers
;
64 static pthread_t tid_reclaim
;
65 static int exit_reclaim
;
67 static void internal_urcu_lock(pthread_mutex_t
*mutex
)
71 #ifndef DISTRUST_SIGNALS_EXTREME
72 ret
= pthread_mutex_lock(mutex
);
74 perror("Error in pthread mutex lock");
77 #else /* #ifndef DISTRUST_SIGNALS_EXTREME */
78 while ((ret
= pthread_mutex_trylock(mutex
)) != 0) {
79 if (ret
!= EBUSY
&& ret
!= EINTR
) {
80 printf("ret = %d, errno = %d\n", ret
, errno
);
81 perror("Error in pthread mutex lock");
86 #endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
89 static void internal_urcu_unlock(pthread_mutex_t
*mutex
)
93 ret
= pthread_mutex_unlock(mutex
);
95 perror("Error in pthread mutex unlock");
101 * Must be called after Q.S. is reached.
103 static void rcu_reclaim_barrier_queue(struct reclaim_queue
*queue
,
109 * Tail is only modified when lock is held.
110 * Head is only modified by owner thread.
113 for (i
= queue
->tail
; i
!= head
; i
++) {
114 smp_rmb(); /* read head before q[]. */
115 free(LOAD_SHARED(queue
->q
[i
& RECLAIM_QUEUE_MASK
]));
117 smp_mb(); /* push tail after having used q[] */
118 STORE_SHARED(queue
->tail
, i
);
121 static void _rcu_reclaim_barrier_thread(void)
125 head
= reclaim_queue
.head
;
127 rcu_reclaim_barrier_queue(&reclaim_queue
, head
);
131 void rcu_reclaim_barrier_thread(void)
133 internal_urcu_lock(&urcu_reclaim_mutex
);
134 _rcu_reclaim_barrier_thread();
135 internal_urcu_unlock(&urcu_reclaim_mutex
);
138 void rcu_reclaim_barrier(void)
140 struct reclaimer_registry
*index
;
145 internal_urcu_lock(&urcu_reclaim_mutex
);
146 for (index
= registry
; index
< registry
+ num_reclaimers
; index
++)
147 index
->last_head
= LOAD_SHARED(index
->reclaim_queue
->head
);
149 for (index
= registry
; index
< registry
+ num_reclaimers
; index
++)
150 rcu_reclaim_barrier_queue(index
->reclaim_queue
,
152 internal_urcu_unlock(&urcu_reclaim_mutex
);
155 void *thr_reclaim(void *args
)
158 if (LOAD_SHARED(exit_reclaim
))
160 poll(NULL
,0,100); /* wait for 100ms */
161 rcu_reclaim_barrier();
168 * library wrappers to be used by non-LGPL compatible source code.
171 void rcu_reclaim_queue(void *p
)
173 _rcu_reclaim_queue(p
);
176 static void rcu_add_reclaimer(pthread_t id
)
178 struct reclaimer_registry
*oldarray
;
181 alloc_reclaimers
= INIT_NUM_THREADS
;
184 malloc(sizeof(struct reclaimer_registry
) * alloc_reclaimers
);
186 if (alloc_reclaimers
< num_reclaimers
+ 1) {
188 registry
= malloc(sizeof(struct reclaimer_registry
)
189 * (alloc_reclaimers
<< 1));
190 memcpy(registry
, oldarray
,
191 sizeof(struct reclaimer_registry
) * alloc_reclaimers
);
192 alloc_reclaimers
<<= 1;
195 registry
[num_reclaimers
].tid
= id
;
196 /* reference to the TLS of _this_ reclaimer thread. */
197 registry
[num_reclaimers
].reclaim_queue
= &reclaim_queue
;
202 * Never shrink (implementation limitation).
203 * This is O(nb threads). Eventually use a hash table.
205 static void rcu_remove_reclaimer(pthread_t id
)
207 struct reclaimer_registry
*index
;
209 assert(registry
!= NULL
);
210 for (index
= registry
; index
< registry
+ num_reclaimers
; index
++) {
211 if (pthread_equal(index
->tid
, id
)) {
212 memcpy(index
, ®istry
[num_reclaimers
- 1],
213 sizeof(struct reclaimer_registry
));
214 registry
[num_reclaimers
- 1].tid
= 0;
215 registry
[num_reclaimers
- 1].reclaim_queue
= NULL
;
220 /* Hrm not found, forgot to register ? */
224 static void start_reclaim_thread(void)
228 ret
= pthread_create(&tid_reclaim
, NULL
, thr_reclaim
,
233 static void stop_reclaim_thread(void)
238 STORE_SHARED(exit_reclaim
, 1);
239 ret
= pthread_join(tid_reclaim
, &tret
);
243 void rcu_reclaim_register_thread(void)
247 internal_urcu_lock(&reclaim_thread_mutex
);
248 internal_urcu_lock(&urcu_reclaim_mutex
);
249 reclaim_queue
.q
= malloc(sizeof(void *) * RECLAIM_QUEUE_SIZE
);
250 rcu_add_reclaimer(pthread_self());
251 reclaimers
= num_reclaimers
;
252 internal_urcu_unlock(&urcu_reclaim_mutex
);
255 start_reclaim_thread();
256 internal_urcu_unlock(&reclaim_thread_mutex
);
259 void rcu_reclaim_unregister_thread(void)
263 internal_urcu_lock(&reclaim_thread_mutex
);
264 internal_urcu_lock(&urcu_reclaim_mutex
);
265 rcu_remove_reclaimer(pthread_self());
266 _rcu_reclaim_barrier_thread();
267 free(reclaim_queue
.q
);
268 reclaim_queue
.q
= NULL
;
269 reclaimers
= num_reclaimers
;
270 internal_urcu_unlock(&urcu_reclaim_mutex
);
273 stop_reclaim_thread();
274 internal_urcu_unlock(&reclaim_thread_mutex
);
277 void urcu_reclaim_exit(void)