1 /*
2 * Copyright 2010-2015 Samy Al Bahra.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 */
26
27 /*
28 * (c) Copyright 2008, IBM Corporation.
29 * Licensed under the Apache License, Version 2.0 (the "License");
30 * you may not use this file except in compliance with the License.
31 * You may obtain a copy of the License at
32 *
33 * http://www.apache.org/licenses/LICENSE-2.0
34 *
35 * Unless required by applicable law or agreed to in writing, software
36 * distributed under the License is distributed on an "AS IS" BASIS,
37 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
38 * See the License for the specific language governing permissions and
39 * limitations under the License.
40 */
41
42 /*
43 * This is an implementation of hazard pointers as detailed in:
44 * http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf
45 *
46 * This API provides a publishing mechanism that defers destruction of
47 * hazard pointers until it is safe to do so. Preventing arbitrary re-use
48 * protects against the ABA problem and provides safe memory reclamation.
49 * The implementation was derived from the Hazard Pointers implementation
50 * from the Amino CBBS project. It has been heavily modified for Concurrency
51 * Kit.
52 */
53
54 #include <ck_backoff.h>
55 #include <ck_cc.h>
56 #include <ck_hp.h>
57 #include <ck_pr.h>
58 #include <ck_stack.h>
59 #include <ck_stdbool.h>
60 #include <ck_stddef.h>
61 #include <ck_stdlib.h>
62 #include <ck_string.h>
63
CK_STACK_CONTAINER(struct ck_hp_record,global_entry,ck_hp_record_container)64 CK_STACK_CONTAINER(struct ck_hp_record, global_entry, ck_hp_record_container)
65 CK_STACK_CONTAINER(struct ck_hp_hazard, pending_entry, ck_hp_hazard_container)
66
67 void
68 ck_hp_init(struct ck_hp *state,
69 unsigned int degree,
70 unsigned int threshold,
71 ck_hp_destructor_t destroy)
72 {
73
74 state->threshold = threshold;
75 state->degree = degree;
76 state->destroy = destroy;
77 state->n_subscribers = 0;
78 state->n_free = 0;
79 ck_stack_init(&state->subscribers);
80 ck_pr_fence_store();
81
82 return;
83 }
84
85 void
ck_hp_set_threshold(struct ck_hp * state,unsigned int threshold)86 ck_hp_set_threshold(struct ck_hp *state, unsigned int threshold)
87 {
88
89 ck_pr_store_uint(&state->threshold, threshold);
90 return;
91 }
92
93 struct ck_hp_record *
ck_hp_recycle(struct ck_hp * global)94 ck_hp_recycle(struct ck_hp *global)
95 {
96 struct ck_hp_record *record;
97 ck_stack_entry_t *entry;
98 int state;
99
100 if (ck_pr_load_uint(&global->n_free) == 0)
101 return NULL;
102
103 CK_STACK_FOREACH(&global->subscribers, entry) {
104 record = ck_hp_record_container(entry);
105
106 if (ck_pr_load_int(&record->state) == CK_HP_FREE) {
107 ck_pr_fence_load();
108 state = ck_pr_fas_int(&record->state, CK_HP_USED);
109 if (state == CK_HP_FREE) {
110 ck_pr_dec_uint(&global->n_free);
111 return record;
112 }
113 }
114 }
115
116 return NULL;
117 }
118
119 void
ck_hp_unregister(struct ck_hp_record * entry)120 ck_hp_unregister(struct ck_hp_record *entry)
121 {
122
123 entry->n_pending = 0;
124 entry->n_peak = 0;
125 entry->n_reclamations = 0;
126 ck_stack_init(&entry->pending);
127 ck_pr_fence_store();
128 ck_pr_store_int(&entry->state, CK_HP_FREE);
129 ck_pr_inc_uint(&entry->global->n_free);
130 return;
131 }
132
133 void
ck_hp_register(struct ck_hp * state,struct ck_hp_record * entry,void ** pointers)134 ck_hp_register(struct ck_hp *state,
135 struct ck_hp_record *entry,
136 void **pointers)
137 {
138
139 entry->state = CK_HP_USED;
140 entry->global = state;
141 entry->pointers = pointers;
142 entry->n_pending = 0;
143 entry->n_peak = 0;
144 entry->n_reclamations = 0;
145 memset(pointers, 0, state->degree * sizeof(void *));
146 ck_stack_init(&entry->pending);
147 ck_pr_fence_store();
148 ck_stack_push_upmc(&state->subscribers, &entry->global_entry);
149 ck_pr_inc_uint(&state->n_subscribers);
150 return;
151 }
152
153 static int
hazard_compare(const void * a,const void * b)154 hazard_compare(const void *a, const void *b)
155 {
156 void * const *x;
157 void * const *y;
158
159 x = a;
160 y = b;
161 return ((*x > *y) - (*x < *y));
162 }
163
164 CK_CC_INLINE static bool
ck_hp_member_scan(ck_stack_entry_t * entry,unsigned int degree,void * pointer)165 ck_hp_member_scan(ck_stack_entry_t *entry, unsigned int degree, void *pointer)
166 {
167 struct ck_hp_record *record;
168 unsigned int i;
169 void *hazard;
170
171 do {
172 record = ck_hp_record_container(entry);
173 if (ck_pr_load_int(&record->state) == CK_HP_FREE)
174 continue;
175
176 if (ck_pr_load_ptr(&record->pointers) == NULL)
177 continue;
178
179 for (i = 0; i < degree; i++) {
180 hazard = ck_pr_load_ptr(&record->pointers[i]);
181 if (hazard == pointer)
182 return (true);
183 }
184 } while ((entry = CK_STACK_NEXT(entry)) != NULL);
185
186 return (false);
187 }
188
189 CK_CC_INLINE static void *
ck_hp_member_cache(struct ck_hp * global,void ** cache,unsigned int * n_hazards)190 ck_hp_member_cache(struct ck_hp *global, void **cache, unsigned int *n_hazards)
191 {
192 struct ck_hp_record *record;
193 ck_stack_entry_t *entry;
194 unsigned int hazards = 0;
195 unsigned int i;
196 void *pointer;
197
198 CK_STACK_FOREACH(&global->subscribers, entry) {
199 record = ck_hp_record_container(entry);
200 if (ck_pr_load_int(&record->state) == CK_HP_FREE)
201 continue;
202
203 if (ck_pr_load_ptr(&record->pointers) == NULL)
204 continue;
205
206 for (i = 0; i < global->degree; i++) {
207 if (hazards > CK_HP_CACHE)
208 break;
209
210 pointer = ck_pr_load_ptr(&record->pointers[i]);
211 if (pointer != NULL)
212 cache[hazards++] = pointer;
213 }
214 }
215
216 *n_hazards = hazards;
217 return (entry);
218 }
219
220 void
ck_hp_reclaim(struct ck_hp_record * thread)221 ck_hp_reclaim(struct ck_hp_record *thread)
222 {
223 struct ck_hp_hazard *hazard;
224 struct ck_hp *global = thread->global;
225 unsigned int n_hazards;
226 void **cache, *marker, *match;
227 ck_stack_entry_t *previous, *entry, *next;
228
229 /* Store as many entries as possible in local array. */
230 cache = thread->cache;
231 marker = ck_hp_member_cache(global, cache, &n_hazards);
232
233 /*
234 * In theory, there is an n such that (n * (log n) ** 2) < np.
235 */
236 qsort(cache, n_hazards, sizeof(void *), hazard_compare);
237
238 previous = NULL;
239 CK_STACK_FOREACH_SAFE(&thread->pending, entry, next) {
240 hazard = ck_hp_hazard_container(entry);
241 match = bsearch(&hazard->pointer, cache, n_hazards,
242 sizeof(void *), hazard_compare);
243 if (match != NULL) {
244 previous = entry;
245 continue;
246 }
247
248 if (marker != NULL &&
249 ck_hp_member_scan(marker, global->degree, hazard->pointer)) {
250 previous = entry;
251 continue;
252 }
253
254 thread->n_pending -= 1;
255
256 /* Remove from the pending stack. */
257 if (previous)
258 CK_STACK_NEXT(previous) = CK_STACK_NEXT(entry);
259 else
260 CK_STACK_FIRST(&thread->pending) = CK_STACK_NEXT(entry);
261
262 /* The entry is now safe to destroy. */
263 global->destroy(hazard->data);
264 thread->n_reclamations++;
265 }
266
267 return;
268 }
269
270 void
ck_hp_retire(struct ck_hp_record * thread,struct ck_hp_hazard * hazard,void * data,void * pointer)271 ck_hp_retire(struct ck_hp_record *thread,
272 struct ck_hp_hazard *hazard,
273 void *data,
274 void *pointer)
275 {
276
277 ck_pr_store_ptr(&hazard->pointer, pointer);
278 ck_pr_store_ptr(&hazard->data, data);
279 ck_stack_push_spnc(&thread->pending, &hazard->pending_entry);
280
281 thread->n_pending += 1;
282 if (thread->n_pending > thread->n_peak)
283 thread->n_peak = thread->n_pending;
284
285 return;
286 }
287
288 void
ck_hp_free(struct ck_hp_record * thread,struct ck_hp_hazard * hazard,void * data,void * pointer)289 ck_hp_free(struct ck_hp_record *thread,
290 struct ck_hp_hazard *hazard,
291 void *data,
292 void *pointer)
293 {
294 struct ck_hp *global;
295
296 global = ck_pr_load_ptr(&thread->global);
297 ck_pr_store_ptr(&hazard->data, data);
298 ck_pr_store_ptr(&hazard->pointer, pointer);
299 ck_stack_push_spnc(&thread->pending, &hazard->pending_entry);
300
301 thread->n_pending += 1;
302 if (thread->n_pending > thread->n_peak)
303 thread->n_peak = thread->n_pending;
304
305 if (thread->n_pending >= global->threshold)
306 ck_hp_reclaim(thread);
307
308 return;
309 }
310
311 void
ck_hp_purge(struct ck_hp_record * thread)312 ck_hp_purge(struct ck_hp_record *thread)
313 {
314 ck_backoff_t backoff = CK_BACKOFF_INITIALIZER;
315
316 while (thread->n_pending > 0) {
317 ck_hp_reclaim(thread);
318 if (thread->n_pending > 0)
319 ck_backoff_eb(&backoff);
320 }
321
322 return;
323 }
324