1 /* 2 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 3 * 4 * This Source Code Form is subject to the terms of the Mozilla Public 5 * License, v. 2.0. If a copy of the MPL was not distributed with this 6 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 7 * 8 * See the COPYRIGHT file distributed with this work for additional 9 * information regarding copyright ownership. 10 */ 11 12 /* 13 * Hazard Pointer implementation. 14 * 15 * This work is based on C++ code available from: 16 * https://github.com/pramalhe/ConcurrencyFreaks/ 17 * 18 * Copyright (c) 2014-2016, Pedro Ramalhete, Andreia Correia 19 * All rights reserved. 20 * 21 * Redistribution and use in source and binary forms, with or without 22 * modification, are permitted provided that the following conditions are met: 23 * 24 * * Redistributions of source code must retain the above copyright 25 * notice, this list of conditions and the following disclaimer. 26 * * Redistributions in binary form must reproduce the above copyright 27 * notice, this list of conditions and the following disclaimer in the 28 * documentation and/or other materials provided with the distribution. 29 * * Neither the name of Concurrency Freaks nor the 30 * names of its contributors may be used to endorse or promote products 31 * derived from this software without specific prior written permission. 32 * 33 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 34 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 35 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 36 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> 37 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 38 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 39 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 40 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 41 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 42 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 43 * THE POSSIBILITY OF SUCH DAMAGE. 44 */ 45 46 #pragma once 47 48 #include <isc/atomic.h> 49 #include <isc/mem.h> 50 #include <isc/string.h> 51 #include <isc/types.h> 52 #include <isc/util.h> 53 54 /*% 55 * Hazard pointers are a mechanism for protecting objects in memory 56 * from being deleted by other threads while in use. This allows 57 * safe lock-free data structures. 58 * 59 * This is an adaptation of the ConcurrencyFreaks implementation in C. 60 * More details available at https://github.com/pramalhe/ConcurrencyFreaks, 61 * in the file HazardPointers.hpp. 62 */ 63 64 typedef void(isc_hp_deletefunc_t)(void *); 65 66 void 67 isc_hp_init(int max_threads); 68 /*%< 69 * Initialize hazard pointer constants, isc__hp_max_threads and 70 * isc__hp_max_retired. If more threads try to access hp, it 71 * will assert. Calling this function repeatedly can be used 72 * to increase the limits, but cannot reduce them. 73 */ 74 75 isc_hp_t * 76 isc_hp_new(isc_mem_t *mctx, size_t max_hps, isc_hp_deletefunc_t *deletefunc); 77 /*%< 78 * Create a new hazard pointer array of size 'max_hps' (or a reasonable 79 * default value if 'max_hps' is 0). The function 'deletefunc' will be 80 * used to delete objects protected by hazard pointers when it becomes 81 * safe to retire them. 82 */ 83 84 void 85 isc_hp_destroy(isc_hp_t *hp); 86 /*%< 87 * Destroy a hazard pointer array and clean up all objects protected 88 * by hazard pointers. 89 */ 90 91 void 92 isc_hp_clear(isc_hp_t *hp); 93 /*%< 94 * Clear all hazard pointers in the array for the current thread. 95 * 96 * Progress condition: wait-free bounded (by max_hps) 97 */ 98 99 void 100 isc_hp_clear_one(isc_hp_t *hp, int ihp); 101 /*%< 102 * Clear a specified hazard pointer in the array for the current thread. 103 * 104 * Progress condition: wait-free population oblivious. 105 */ 106 107 uintptr_t 108 isc_hp_protect(isc_hp_t *hp, int ihp, atomic_uintptr_t *atom); 109 /*%< 110 * Protect an object referenced by 'atom' with a hazard pointer for the 111 * current thread. 112 * 113 * Progress condition: lock-free. 114 */ 115 116 uintptr_t 117 isc_hp_protect_ptr(isc_hp_t *hp, int ihp, atomic_uintptr_t ptr); 118 /*%< 119 * This returns the same value that is passed as ptr, which is sometimes 120 * useful. 121 * 122 * Progress condition: wait-free population oblivious. 123 */ 124 125 uintptr_t 126 isc_hp_protect_release(isc_hp_t *hp, int ihp, atomic_uintptr_t ptr); 127 /*%< 128 * Same as isc_hp_protect_ptr(), but explicitly uses memory_order_release. 129 * 130 * Progress condition: wait-free population oblivious. 131 */ 132 133 void 134 isc_hp_retire(isc_hp_t *hp, uintptr_t ptr); 135 /*%< 136 * Retire an object that is no longer in use by any thread, calling 137 * the delete function that was specified in isc_hp_new(). 138 * 139 * Progress condition: wait-free bounded (by the number of threads squared) 140 */ 141