2  * Copyright 2010-2015 Samy Al Bahra.
33  * http://www.apache.org/licenses/LICENSE-2.0
44  *   http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf
47  * hazard pointers until it is safe to do so. Preventing arbitrary re-use
69 	   unsigned int degree,  in CK_STACK_CONTAINER()
70 	   unsigned int threshold,  in CK_STACK_CONTAINER()
74 	state->threshold = threshold;  in CK_STACK_CONTAINER()
75 	state->degree = degree;  in CK_STACK_CONTAINER()
76 	state->destroy = destroy;  in CK_STACK_CONTAINER()
77 	state->n_subscribers = 0;  in CK_STACK_CONTAINER()
78 	state->n_free = 0;  in CK_STACK_CONTAINER()
79 	ck_stack_init(&state->subscribers);  in CK_STACK_CONTAINER()
86 ck_hp_set_threshold(struct ck_hp *state, unsigned int threshold)  in ck_hp_set_threshold()  argument
89 	ck_pr_store_uint(&state->threshold, threshold);  in ck_hp_set_threshold()
98 	int state;  in ck_hp_recycle()
100 	if (ck_pr_load_uint(&global->n_free) == 0)  in ck_hp_recycle()
103 	CK_STACK_FOREACH(&global->subscribers, entry) {  in ck_hp_recycle()
106 		if (ck_pr_load_int(&record->state) == CK_HP_FREE) {  in ck_hp_recycle()
108 			state = ck_pr_fas_int(&record->state, CK_HP_USED);  in ck_hp_recycle()
110 				ck_pr_dec_uint(&global->n_free);  in ck_hp_recycle()
123 	entry->n_pending = 0;  in ck_hp_unregister()
124 	entry->n_peak = 0;  in ck_hp_unregister()
125 	entry->n_reclamations = 0;  in ck_hp_unregister()
126 	ck_stack_init(&entry->pending);  in ck_hp_unregister()
128 	ck_pr_store_int(&entry->state, CK_HP_FREE);  in ck_hp_unregister()
129 	ck_pr_inc_uint(&entry->global->n_free);  in ck_hp_unregister()
139 	entry->state = CK_HP_USED;  in ck_hp_register()
140 	entry->global = state;  in ck_hp_register()
141 	entry->pointers = pointers;  in ck_hp_register()
142 	entry->n_pending = 0;  in ck_hp_register()
143 	entry->n_peak = 0;  in ck_hp_register()
144 	entry->n_reclamations = 0;  in ck_hp_register()
145 	memset(pointers, 0, state->degree * sizeof(void *));  in ck_hp_register()
146 	ck_stack_init(&entry->pending);  in ck_hp_register()
148 	ck_stack_push_upmc(&state->subscribers, &entry->global_entry);  in ck_hp_register()
149 	ck_pr_inc_uint(&state->n_subscribers);  in ck_hp_register()
153 static int
161 	return ((*x > *y) - (*x < *y));  in hazard_compare()
165 ck_hp_member_scan(ck_stack_entry_t *entry, unsigned int degree, void *pointer)  in ck_hp_member_scan()
168 	unsigned int i;  in ck_hp_member_scan()
173 		if (ck_pr_load_int(&record->state) == CK_HP_FREE)  in ck_hp_member_scan()
176 		if (ck_pr_load_ptr(&record->pointers) == NULL)  in ck_hp_member_scan()
180 			hazard = ck_pr_load_ptr(&record->pointers[i]);  in ck_hp_member_scan()
190 ck_hp_member_cache(struct ck_hp *global, void **cache, unsigned int *n_hazards)  in ck_hp_member_cache()
194 	unsigned int hazards = 0;  in ck_hp_member_cache()
195 	unsigned int i;  in ck_hp_member_cache()
198 	CK_STACK_FOREACH(&global->subscribers, entry) {  in ck_hp_member_cache()
200 		if (ck_pr_load_int(&record->state) == CK_HP_FREE)  in ck_hp_member_cache()
203 		if (ck_pr_load_ptr(&record->pointers) == NULL)  in ck_hp_member_cache()
206 		for (i = 0; i < global->degree; i++) {  in ck_hp_member_cache()
210 			pointer = ck_pr_load_ptr(&record->pointers[i]);  in ck_hp_member_cache()
224 	struct ck_hp *global = thread->global;  in ck_hp_reclaim()
225 	unsigned int n_hazards;  in ck_hp_reclaim()
230 	cache = thread->cache;  in ck_hp_reclaim()
239 	CK_STACK_FOREACH_SAFE(&thread->pending, entry, next) {  in ck_hp_reclaim()
241 		match = bsearch(&hazard->pointer, cache, n_hazards,  in ck_hp_reclaim()
249 		    ck_hp_member_scan(marker, global->degree, hazard->pointer)) {  in ck_hp_reclaim()
254 		thread->n_pending -= 1;  in ck_hp_reclaim()
260 			CK_STACK_FIRST(&thread->pending) = CK_STACK_NEXT(entry);  in ck_hp_reclaim()
263 		global->destroy(hazard->data);  in ck_hp_reclaim()
264 		thread->n_reclamations++;  in ck_hp_reclaim()
277 	ck_pr_store_ptr(&hazard->pointer, pointer);  in ck_hp_retire()
278 	ck_pr_store_ptr(&hazard->data, data);  in ck_hp_retire()
279 	ck_stack_push_spnc(&thread->pending, &hazard->pending_entry);  in ck_hp_retire()
281 	thread->n_pending += 1;  in ck_hp_retire()
282 	if (thread->n_pending > thread->n_peak)  in ck_hp_retire()
283 		thread->n_peak = thread->n_pending;  in ck_hp_retire()
296 	global = ck_pr_load_ptr(&thread->global);  in ck_hp_free()
297 	ck_pr_store_ptr(&hazard->data, data);  in ck_hp_free()
298 	ck_pr_store_ptr(&hazard->pointer, pointer);  in ck_hp_free()
299 	ck_stack_push_spnc(&thread->pending, &hazard->pending_entry);  in ck_hp_free()
301 	thread->n_pending += 1;  in ck_hp_free()
302 	if (thread->n_pending > thread->n_peak)  in ck_hp_free()
303 		thread->n_peak = thread->n_pending;  in ck_hp_free()
305 	if (thread->n_pending >= global->threshold)  in ck_hp_free()
316 	while (thread->n_pending > 0) {  in ck_hp_purge()
318 		if (thread->n_pending > 0)  in ck_hp_purge()