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 http://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 #include <inttypes.h>
47
48 #include <isc/atomic.h>
49 #include <isc/hp.h>
50 #include <isc/mem.h>
51 #include <isc/once.h>
52 #include <isc/string.h>
53 #include <isc/thread.h>
54 #include <isc/util.h>
55
56 #define HP_MAX_THREADS 128
57 static int isc__hp_max_threads = HP_MAX_THREADS;
58 #define HP_MAX_HPS 4 /* This is named 'K' in the HP paper */
59 #define CLPAD (128 / sizeof(uintptr_t))
60 #define HP_THRESHOLD_R 0 /* This is named 'R' in the HP paper */
61
62 /* Maximum number of retired objects per thread */
63 static int isc__hp_max_retired = HP_MAX_THREADS * HP_MAX_HPS;
64
65 #define TID_UNKNOWN -1
66
67 static atomic_int_fast32_t tid_v_base = ATOMIC_VAR_INIT(0);
68
69 ISC_THREAD_LOCAL int tid_v = TID_UNKNOWN;
70
71 typedef struct retirelist {
72 int size;
73 uintptr_t *list;
74 } retirelist_t;
75
76 struct isc_hp {
77 int max_hps;
78 isc_mem_t *mctx;
79 atomic_uintptr_t **hp;
80 retirelist_t **rl;
81 isc_hp_deletefunc_t *deletefunc;
82 };
83
84 static inline int
tid()85 tid() {
86 if (tid_v == TID_UNKNOWN) {
87 tid_v = atomic_fetch_add(&tid_v_base, 1);
88 REQUIRE(tid_v < isc__hp_max_threads);
89 }
90
91 return (tid_v);
92 }
93
94 void
isc_hp_init(int max_threads)95 isc_hp_init(int max_threads) {
96 isc__hp_max_threads = max_threads;
97 isc__hp_max_retired = max_threads * HP_MAX_HPS;
98 }
99
100 isc_hp_t *
isc_hp_new(isc_mem_t * mctx,size_t max_hps,isc_hp_deletefunc_t * deletefunc)101 isc_hp_new(isc_mem_t *mctx, size_t max_hps, isc_hp_deletefunc_t *deletefunc) {
102 isc_hp_t *hp = isc_mem_get(mctx, sizeof(*hp));
103
104 if (max_hps == 0) {
105 max_hps = HP_MAX_HPS;
106 }
107
108 *hp = (isc_hp_t){ .max_hps = max_hps, .deletefunc = deletefunc };
109
110 isc_mem_attach(mctx, &hp->mctx);
111
112 hp->hp = isc_mem_get(mctx, isc__hp_max_threads * sizeof(hp->hp[0]));
113 hp->rl = isc_mem_get(mctx, isc__hp_max_threads * sizeof(hp->rl[0]));
114
115 for (int i = 0; i < isc__hp_max_threads; i++) {
116 hp->hp[i] = isc_mem_get(mctx, CLPAD * 2 * sizeof(hp->hp[i][0]));
117 hp->rl[i] = isc_mem_get(mctx, sizeof(*hp->rl[0]));
118 *hp->rl[i] = (retirelist_t){ .size = 0 };
119
120 for (int j = 0; j < hp->max_hps; j++) {
121 atomic_init(&hp->hp[i][j], 0);
122 }
123 hp->rl[i]->list = isc_mem_get(
124 hp->mctx, isc__hp_max_retired * sizeof(uintptr_t));
125 }
126
127 return (hp);
128 }
129
130 void
isc_hp_destroy(isc_hp_t * hp)131 isc_hp_destroy(isc_hp_t *hp) {
132 for (int i = 0; i < isc__hp_max_threads; i++) {
133 isc_mem_put(hp->mctx, hp->hp[i],
134 CLPAD * 2 * sizeof(hp->hp[i][0]));
135
136 for (int j = 0; j < hp->rl[i]->size; j++) {
137 void *data = (void *)hp->rl[i]->list[j];
138 hp->deletefunc(data);
139 }
140 isc_mem_put(hp->mctx, hp->rl[i]->list,
141 isc__hp_max_retired * sizeof(uintptr_t));
142 isc_mem_put(hp->mctx, hp->rl[i], sizeof(*hp->rl[0]));
143 }
144 isc_mem_put(hp->mctx, hp->hp, isc__hp_max_threads * sizeof(hp->hp[0]));
145 isc_mem_put(hp->mctx, hp->rl, isc__hp_max_threads * sizeof(hp->rl[0]));
146
147 isc_mem_putanddetach(&hp->mctx, hp, sizeof(*hp));
148 }
149
150 void
isc_hp_clear(isc_hp_t * hp)151 isc_hp_clear(isc_hp_t *hp) {
152 for (int i = 0; i < hp->max_hps; i++) {
153 atomic_store_release(&hp->hp[tid()][i], 0);
154 }
155 }
156
157 void
isc_hp_clear_one(isc_hp_t * hp,int ihp)158 isc_hp_clear_one(isc_hp_t *hp, int ihp) {
159 atomic_store_release(&hp->hp[tid()][ihp], 0);
160 }
161
162 uintptr_t
isc_hp_protect(isc_hp_t * hp,int ihp,atomic_uintptr_t * atom)163 isc_hp_protect(isc_hp_t *hp, int ihp, atomic_uintptr_t *atom) {
164 uintptr_t n = 0;
165 uintptr_t ret;
166 while ((ret = atomic_load(atom)) != n) {
167 atomic_store(&hp->hp[tid()][ihp], ret);
168 n = ret;
169 }
170 return (ret);
171 }
172
173 uintptr_t
isc_hp_protect_ptr(isc_hp_t * hp,int ihp,atomic_uintptr_t ptr)174 isc_hp_protect_ptr(isc_hp_t *hp, int ihp, atomic_uintptr_t ptr) {
175 atomic_store(&hp->hp[tid()][ihp], atomic_load(&ptr));
176 return (atomic_load(&ptr));
177 }
178
179 uintptr_t
isc_hp_protect_release(isc_hp_t * hp,int ihp,atomic_uintptr_t ptr)180 isc_hp_protect_release(isc_hp_t *hp, int ihp, atomic_uintptr_t ptr) {
181 atomic_store_release(&hp->hp[tid()][ihp], atomic_load(&ptr));
182 return (atomic_load(&ptr));
183 }
184
185 void
isc_hp_retire(isc_hp_t * hp,uintptr_t ptr)186 isc_hp_retire(isc_hp_t *hp, uintptr_t ptr) {
187 hp->rl[tid()]->list[hp->rl[tid()]->size++] = ptr;
188 INSIST(hp->rl[tid()]->size < isc__hp_max_retired);
189
190 if (hp->rl[tid()]->size < HP_THRESHOLD_R) {
191 return;
192 }
193
194 for (int iret = 0; iret < hp->rl[tid()]->size; iret++) {
195 uintptr_t obj = hp->rl[tid()]->list[iret];
196 bool can_delete = true;
197 for (int itid = 0; itid < isc__hp_max_threads && can_delete;
198 itid++) {
199 for (int ihp = hp->max_hps - 1; ihp >= 0; ihp--) {
200 if (atomic_load(&hp->hp[itid][ihp]) == obj) {
201 can_delete = false;
202 break;
203 }
204 }
205 }
206
207 if (can_delete) {
208 size_t bytes = (hp->rl[tid()]->size - iret) *
209 sizeof(hp->rl[tid()]->list[0]);
210 memmove(&hp->rl[tid()]->list[iret],
211 &hp->rl[tid()]->list[iret + 1], bytes);
212 hp->rl[tid()]->size--;
213 hp->deletefunc((void *)obj);
214 }
215 }
216 }
217