1309260Scognet/* 2309260Scognet * Copyright 2010-2015 Samy Al Bahra. 3309260Scognet * All rights reserved. 4309260Scognet * 5309260Scognet * Redistribution and use in source and binary forms, with or without 6309260Scognet * modification, are permitted provided that the following conditions 7309260Scognet * are met: 8309260Scognet * 1. Redistributions of source code must retain the above copyright 9309260Scognet * notice, this list of conditions and the following disclaimer. 10309260Scognet * 2. Redistributions in binary form must reproduce the above copyright 11309260Scognet * notice, this list of conditions and the following disclaimer in the 12309260Scognet * documentation and/or other materials provided with the distribution. 13309260Scognet * 14309260Scognet * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15309260Scognet * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16309260Scognet * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17309260Scognet * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18309260Scognet * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19309260Scognet * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20309260Scognet * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21309260Scognet * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22309260Scognet * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23309260Scognet * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24309260Scognet * SUCH DAMAGE. 25309260Scognet */ 26309260Scognet 27309260Scognet/* 28309260Scognet * (c) Copyright 2008, IBM Corporation. 29309260Scognet * Licensed under the Apache License, Version 2.0 (the "License"); 30309260Scognet * you may not use this file except in compliance with the License. 31309260Scognet * You may obtain a copy of the License at 32309260Scognet * 33309260Scognet * http://www.apache.org/licenses/LICENSE-2.0 34309260Scognet * 35309260Scognet * Unless required by applicable law or agreed to in writing, software 36309260Scognet * distributed under the License is distributed on an "AS IS" BASIS, 37309260Scognet * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 38309260Scognet * See the License for the specific language governing permissions and 39309260Scognet * limitations under the License. 40309260Scognet */ 41309260Scognet 42309260Scognet/* 43309260Scognet * This is an implementation of hazard pointers as detailed in: 44309260Scognet * http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf 45309260Scognet * 46309260Scognet * This API provides a publishing mechanism that defers destruction of 47309260Scognet * hazard pointers until it is safe to do so. Preventing arbitrary re-use 48309260Scognet * protects against the ABA problem and provides safe memory reclamation. 49309260Scognet * The implementation was derived from the Hazard Pointers implementation 50309260Scognet * from the Amino CBBS project. It has been heavily modified for Concurrency 51309260Scognet * Kit. 52309260Scognet */ 53309260Scognet 54309260Scognet#include <ck_backoff.h> 55309260Scognet#include <ck_cc.h> 56309260Scognet#include <ck_hp.h> 57309260Scognet#include <ck_pr.h> 58309260Scognet#include <ck_stack.h> 59309260Scognet#include <ck_stdbool.h> 60309260Scognet#include <ck_stddef.h> 61309260Scognet#include <ck_stdlib.h> 62309260Scognet#include <ck_string.h> 63309260Scognet 64309260ScognetCK_STACK_CONTAINER(struct ck_hp_record, global_entry, ck_hp_record_container) 65309260ScognetCK_STACK_CONTAINER(struct ck_hp_hazard, pending_entry, ck_hp_hazard_container) 66309260Scognet 67309260Scognetvoid 68309260Scognetck_hp_init(struct ck_hp *state, 69309260Scognet unsigned int degree, 70309260Scognet unsigned int threshold, 71309260Scognet ck_hp_destructor_t destroy) 72309260Scognet{ 73309260Scognet 74309260Scognet state->threshold = threshold; 75309260Scognet state->degree = degree; 76309260Scognet state->destroy = destroy; 77309260Scognet state->n_subscribers = 0; 78309260Scognet state->n_free = 0; 79309260Scognet ck_stack_init(&state->subscribers); 80309260Scognet ck_pr_fence_store(); 81309260Scognet 82309260Scognet return; 83309260Scognet} 84309260Scognet 85309260Scognetvoid 86309260Scognetck_hp_set_threshold(struct ck_hp *state, unsigned int threshold) 87309260Scognet{ 88309260Scognet 89309260Scognet ck_pr_store_uint(&state->threshold, threshold); 90309260Scognet return; 91309260Scognet} 92309260Scognet 93309260Scognetstruct ck_hp_record * 94309260Scognetck_hp_recycle(struct ck_hp *global) 95309260Scognet{ 96309260Scognet struct ck_hp_record *record; 97309260Scognet ck_stack_entry_t *entry; 98309260Scognet int state; 99309260Scognet 100309260Scognet if (ck_pr_load_uint(&global->n_free) == 0) 101309260Scognet return NULL; 102309260Scognet 103309260Scognet CK_STACK_FOREACH(&global->subscribers, entry) { 104309260Scognet record = ck_hp_record_container(entry); 105309260Scognet 106309260Scognet if (ck_pr_load_int(&record->state) == CK_HP_FREE) { 107309260Scognet ck_pr_fence_load(); 108309260Scognet state = ck_pr_fas_int(&record->state, CK_HP_USED); 109309260Scognet if (state == CK_HP_FREE) { 110309260Scognet ck_pr_dec_uint(&global->n_free); 111309260Scognet return record; 112309260Scognet } 113309260Scognet } 114309260Scognet } 115309260Scognet 116309260Scognet return NULL; 117309260Scognet} 118309260Scognet 119309260Scognetvoid 120309260Scognetck_hp_unregister(struct ck_hp_record *entry) 121309260Scognet{ 122309260Scognet 123309260Scognet entry->n_pending = 0; 124309260Scognet entry->n_peak = 0; 125309260Scognet entry->n_reclamations = 0; 126309260Scognet ck_stack_init(&entry->pending); 127309260Scognet ck_pr_fence_store(); 128309260Scognet ck_pr_store_int(&entry->state, CK_HP_FREE); 129309260Scognet ck_pr_inc_uint(&entry->global->n_free); 130309260Scognet return; 131309260Scognet} 132309260Scognet 133309260Scognetvoid 134309260Scognetck_hp_register(struct ck_hp *state, 135309260Scognet struct ck_hp_record *entry, 136309260Scognet void **pointers) 137309260Scognet{ 138309260Scognet 139309260Scognet entry->state = CK_HP_USED; 140309260Scognet entry->global = state; 141309260Scognet entry->pointers = pointers; 142309260Scognet entry->n_pending = 0; 143309260Scognet entry->n_peak = 0; 144309260Scognet entry->n_reclamations = 0; 145309260Scognet memset(pointers, 0, state->degree * sizeof(void *)); 146309260Scognet ck_stack_init(&entry->pending); 147309260Scognet ck_pr_fence_store(); 148309260Scognet ck_stack_push_upmc(&state->subscribers, &entry->global_entry); 149309260Scognet ck_pr_inc_uint(&state->n_subscribers); 150309260Scognet return; 151309260Scognet} 152309260Scognet 153309260Scognetstatic int 154309260Scognethazard_compare(const void *a, const void *b) 155309260Scognet{ 156309260Scognet void * const *x; 157309260Scognet void * const *y; 158309260Scognet 159309260Scognet x = a; 160309260Scognet y = b; 161309260Scognet return ((*x > *y) - (*x < *y)); 162309260Scognet} 163309260Scognet 164309260ScognetCK_CC_INLINE static bool 165309260Scognetck_hp_member_scan(ck_stack_entry_t *entry, unsigned int degree, void *pointer) 166309260Scognet{ 167309260Scognet struct ck_hp_record *record; 168309260Scognet unsigned int i; 169309260Scognet void *hazard; 170309260Scognet 171309260Scognet do { 172309260Scognet record = ck_hp_record_container(entry); 173309260Scognet if (ck_pr_load_int(&record->state) == CK_HP_FREE) 174309260Scognet continue; 175309260Scognet 176309260Scognet if (ck_pr_load_ptr(&record->pointers) == NULL) 177309260Scognet continue; 178309260Scognet 179309260Scognet for (i = 0; i < degree; i++) { 180309260Scognet hazard = ck_pr_load_ptr(&record->pointers[i]); 181309260Scognet if (hazard == pointer) 182309260Scognet return (true); 183309260Scognet } 184309260Scognet } while ((entry = CK_STACK_NEXT(entry)) != NULL); 185309260Scognet 186309260Scognet return (false); 187309260Scognet} 188309260Scognet 189309260ScognetCK_CC_INLINE static void * 190309260Scognetck_hp_member_cache(struct ck_hp *global, void **cache, unsigned int *n_hazards) 191309260Scognet{ 192309260Scognet struct ck_hp_record *record; 193309260Scognet ck_stack_entry_t *entry; 194309260Scognet unsigned int hazards = 0; 195309260Scognet unsigned int i; 196309260Scognet void *pointer; 197309260Scognet 198309260Scognet CK_STACK_FOREACH(&global->subscribers, entry) { 199309260Scognet record = ck_hp_record_container(entry); 200309260Scognet if (ck_pr_load_int(&record->state) == CK_HP_FREE) 201309260Scognet continue; 202309260Scognet 203309260Scognet if (ck_pr_load_ptr(&record->pointers) == NULL) 204309260Scognet continue; 205309260Scognet 206309260Scognet for (i = 0; i < global->degree; i++) { 207309260Scognet if (hazards > CK_HP_CACHE) 208309260Scognet break; 209309260Scognet 210309260Scognet pointer = ck_pr_load_ptr(&record->pointers[i]); 211309260Scognet if (pointer != NULL) 212309260Scognet cache[hazards++] = pointer; 213309260Scognet } 214309260Scognet } 215309260Scognet 216309260Scognet *n_hazards = hazards; 217309260Scognet return (entry); 218309260Scognet} 219309260Scognet 220309260Scognetvoid 221309260Scognetck_hp_reclaim(struct ck_hp_record *thread) 222309260Scognet{ 223309260Scognet struct ck_hp_hazard *hazard; 224309260Scognet struct ck_hp *global = thread->global; 225309260Scognet unsigned int n_hazards; 226309260Scognet void **cache, *marker, *match; 227309260Scognet ck_stack_entry_t *previous, *entry, *next; 228309260Scognet 229309260Scognet /* Store as many entries as possible in local array. */ 230309260Scognet cache = thread->cache; 231309260Scognet marker = ck_hp_member_cache(global, cache, &n_hazards); 232309260Scognet 233309260Scognet /* 234309260Scognet * In theory, there is an n such that (n * (log n) ** 2) < np. 235309260Scognet */ 236309260Scognet qsort(cache, n_hazards, sizeof(void *), hazard_compare); 237309260Scognet 238309260Scognet previous = NULL; 239309260Scognet CK_STACK_FOREACH_SAFE(&thread->pending, entry, next) { 240309260Scognet hazard = ck_hp_hazard_container(entry); 241309260Scognet match = bsearch(&hazard->pointer, cache, n_hazards, 242309260Scognet sizeof(void *), hazard_compare); 243309260Scognet if (match != NULL) { 244309260Scognet previous = entry; 245309260Scognet continue; 246309260Scognet } 247309260Scognet 248309260Scognet if (marker != NULL && 249309260Scognet ck_hp_member_scan(marker, global->degree, hazard->pointer)) { 250309260Scognet previous = entry; 251309260Scognet continue; 252309260Scognet } 253309260Scognet 254309260Scognet thread->n_pending -= 1; 255309260Scognet 256309260Scognet /* Remove from the pending stack. */ 257309260Scognet if (previous) 258309260Scognet CK_STACK_NEXT(previous) = CK_STACK_NEXT(entry); 259309260Scognet else 260309260Scognet CK_STACK_FIRST(&thread->pending) = CK_STACK_NEXT(entry); 261309260Scognet 262309260Scognet /* The entry is now safe to destroy. */ 263309260Scognet global->destroy(hazard->data); 264309260Scognet thread->n_reclamations++; 265309260Scognet } 266309260Scognet 267309260Scognet return; 268309260Scognet} 269309260Scognet 270309260Scognetvoid 271309260Scognetck_hp_retire(struct ck_hp_record *thread, 272309260Scognet struct ck_hp_hazard *hazard, 273309260Scognet void *data, 274309260Scognet void *pointer) 275309260Scognet{ 276309260Scognet 277309260Scognet ck_pr_store_ptr(&hazard->pointer, pointer); 278309260Scognet ck_pr_store_ptr(&hazard->data, data); 279309260Scognet ck_stack_push_spnc(&thread->pending, &hazard->pending_entry); 280309260Scognet 281309260Scognet thread->n_pending += 1; 282309260Scognet if (thread->n_pending > thread->n_peak) 283309260Scognet thread->n_peak = thread->n_pending; 284309260Scognet 285309260Scognet return; 286309260Scognet} 287309260Scognet 288309260Scognetvoid 289309260Scognetck_hp_free(struct ck_hp_record *thread, 290309260Scognet struct ck_hp_hazard *hazard, 291309260Scognet void *data, 292309260Scognet void *pointer) 293309260Scognet{ 294309260Scognet struct ck_hp *global; 295309260Scognet 296309260Scognet global = ck_pr_load_ptr(&thread->global); 297309260Scognet ck_pr_store_ptr(&hazard->data, data); 298309260Scognet ck_pr_store_ptr(&hazard->pointer, pointer); 299309260Scognet ck_stack_push_spnc(&thread->pending, &hazard->pending_entry); 300309260Scognet 301309260Scognet thread->n_pending += 1; 302309260Scognet if (thread->n_pending > thread->n_peak) 303309260Scognet thread->n_peak = thread->n_pending; 304309260Scognet 305309260Scognet if (thread->n_pending >= global->threshold) 306309260Scognet ck_hp_reclaim(thread); 307309260Scognet 308309260Scognet return; 309309260Scognet} 310309260Scognet 311309260Scognetvoid 312309260Scognetck_hp_purge(struct ck_hp_record *thread) 313309260Scognet{ 314309260Scognet ck_backoff_t backoff = CK_BACKOFF_INITIALIZER; 315309260Scognet 316309260Scognet while (thread->n_pending > 0) { 317309260Scognet ck_hp_reclaim(thread); 318309260Scognet if (thread->n_pending > 0) 319309260Scognet ck_backoff_eb(&backoff); 320309260Scognet } 321309260Scognet 322309260Scognet return; 323309260Scognet} 324