1 /*
2 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
3 *
4 * SPDX-License-Identifier: MPL-2.0
5 *
6 * This Source Code Form is subject to the terms of the Mozilla Public
7 * License, v. 2.0. If a copy of the MPL was not distributed with this
8 * file, you can obtain one at https://mozilla.org/MPL/2.0/.
9 *
10 * See the COPYRIGHT file distributed with this work for additional
11 * information regarding copyright ownership.
12 */
13
14 /*
15 * Hazard Pointer implementation.
16 *
17 * This work is based on C++ code available from:
18 * https://github.com/pramalhe/ConcurrencyFreaks/
19 *
20 * Copyright (c) 2014-2016, Pedro Ramalhete, Andreia Correia
21 * All rights reserved.
22 *
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions are met:
25 *
26 * * Redistributions of source code must retain the above copyright
27 * notice, this list of conditions and the following disclaimer.
28 * * Redistributions in binary form must reproduce the above copyright
29 * notice, this list of conditions and the following disclaimer in the
30 * documentation and/or other materials provided with the distribution.
31 * * Neither the name of Concurrency Freaks nor the
32 * names of its contributors may be used to endorse or promote products
33 * derived from this software without specific prior written permission.
34 *
35 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
36 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
37 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
38 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER>
39 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
40 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
41 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
42 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
43 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
44 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
45 * THE POSSIBILITY OF SUCH DAMAGE.
46 */
47
48 #include <inttypes.h>
49
50 #include <isc/atomic.h>
51 #include <isc/hp.h>
52 #include <isc/mem.h>
53 #include <isc/once.h>
54 #include <isc/string.h>
55 #include <isc/thread.h>
56 #include <isc/util.h>
57
58 #define HP_MAX_THREADS 128
59 static int isc__hp_max_threads = HP_MAX_THREADS;
60 #define HP_MAX_HPS 4 /* This is named 'K' in the HP paper */
61 #define CLPAD (128 / sizeof(uintptr_t))
62 #define HP_THRESHOLD_R 0 /* This is named 'R' in the HP paper */
63
64 /* Maximum number of retired objects per thread */
65 static int isc__hp_max_retired = HP_MAX_THREADS * HP_MAX_HPS;
66
67 typedef struct retirelist {
68 int size;
69 uintptr_t *list;
70 } retirelist_t;
71
72 struct isc_hp {
73 int max_hps;
74 isc_mem_t *mctx;
75 atomic_uintptr_t **hp;
76 retirelist_t **rl;
77 isc_hp_deletefunc_t *deletefunc;
78 };
79
80 static inline int
tid(void)81 tid(void) {
82 return (isc_tid_v);
83 }
84
85 void
isc_hp_init(int max_threads)86 isc_hp_init(int max_threads) {
87 isc__hp_max_threads = max_threads;
88 isc__hp_max_retired = max_threads * HP_MAX_HPS;
89 }
90
91 isc_hp_t *
isc_hp_new(isc_mem_t * mctx,size_t max_hps,isc_hp_deletefunc_t * deletefunc)92 isc_hp_new(isc_mem_t *mctx, size_t max_hps, isc_hp_deletefunc_t *deletefunc) {
93 isc_hp_t *hp = isc_mem_get(mctx, sizeof(*hp));
94
95 if (max_hps == 0) {
96 max_hps = HP_MAX_HPS;
97 }
98
99 *hp = (isc_hp_t){ .max_hps = max_hps, .deletefunc = deletefunc };
100
101 isc_mem_attach(mctx, &hp->mctx);
102
103 hp->hp = isc_mem_get(mctx, isc__hp_max_threads * sizeof(hp->hp[0]));
104 hp->rl = isc_mem_get(mctx, isc__hp_max_threads * sizeof(hp->rl[0]));
105
106 for (int i = 0; i < isc__hp_max_threads; i++) {
107 hp->hp[i] = isc_mem_get(mctx, CLPAD * 2 * sizeof(hp->hp[i][0]));
108 hp->rl[i] = isc_mem_get(mctx, sizeof(*hp->rl[0]));
109 *hp->rl[i] = (retirelist_t){ .size = 0 };
110
111 for (int j = 0; j < hp->max_hps; j++) {
112 atomic_init(&hp->hp[i][j], 0);
113 }
114 hp->rl[i]->list = isc_mem_get(
115 hp->mctx, isc__hp_max_retired * sizeof(uintptr_t));
116 }
117
118 return (hp);
119 }
120
121 void
isc_hp_destroy(isc_hp_t * hp)122 isc_hp_destroy(isc_hp_t *hp) {
123 for (int i = 0; i < isc__hp_max_threads; i++) {
124 isc_mem_put(hp->mctx, hp->hp[i],
125 CLPAD * 2 * sizeof(hp->hp[i][0]));
126
127 for (int j = 0; j < hp->rl[i]->size; j++) {
128 void *data = (void *)hp->rl[i]->list[j];
129 hp->deletefunc(data);
130 }
131 isc_mem_put(hp->mctx, hp->rl[i]->list,
132 isc__hp_max_retired * sizeof(uintptr_t));
133 isc_mem_put(hp->mctx, hp->rl[i], sizeof(*hp->rl[0]));
134 }
135 isc_mem_put(hp->mctx, hp->hp, isc__hp_max_threads * sizeof(hp->hp[0]));
136 isc_mem_put(hp->mctx, hp->rl, isc__hp_max_threads * sizeof(hp->rl[0]));
137
138 isc_mem_putanddetach(&hp->mctx, hp, sizeof(*hp));
139 }
140
141 void
isc_hp_clear(isc_hp_t * hp)142 isc_hp_clear(isc_hp_t *hp) {
143 for (int i = 0; i < hp->max_hps; i++) {
144 atomic_store_release(&hp->hp[tid()][i], 0);
145 }
146 }
147
148 void
isc_hp_clear_one(isc_hp_t * hp,int ihp)149 isc_hp_clear_one(isc_hp_t *hp, int ihp) {
150 atomic_store_release(&hp->hp[tid()][ihp], 0);
151 }
152
153 uintptr_t
isc_hp_protect(isc_hp_t * hp,int ihp,atomic_uintptr_t * atom)154 isc_hp_protect(isc_hp_t *hp, int ihp, atomic_uintptr_t *atom) {
155 uintptr_t n = 0;
156 uintptr_t ret;
157 while ((ret = atomic_load(atom)) != n) {
158 atomic_store(&hp->hp[tid()][ihp], ret);
159 n = ret;
160 }
161 return (ret);
162 }
163
164 uintptr_t
isc_hp_protect_ptr(isc_hp_t * hp,int ihp,atomic_uintptr_t ptr)165 isc_hp_protect_ptr(isc_hp_t *hp, int ihp, atomic_uintptr_t ptr) {
166 atomic_store(&hp->hp[tid()][ihp], atomic_load(&ptr));
167 return (atomic_load(&ptr));
168 }
169
170 uintptr_t
isc_hp_protect_release(isc_hp_t * hp,int ihp,atomic_uintptr_t ptr)171 isc_hp_protect_release(isc_hp_t *hp, int ihp, atomic_uintptr_t ptr) {
172 atomic_store_release(&hp->hp[tid()][ihp], atomic_load(&ptr));
173 return (atomic_load(&ptr));
174 }
175
176 void
isc_hp_retire(isc_hp_t * hp,uintptr_t ptr)177 isc_hp_retire(isc_hp_t *hp, uintptr_t ptr) {
178 hp->rl[tid()]->list[hp->rl[tid()]->size++] = ptr;
179 INSIST(hp->rl[tid()]->size < isc__hp_max_retired);
180
181 if (hp->rl[tid()]->size < HP_THRESHOLD_R) {
182 return;
183 }
184
185 for (int iret = 0; iret < hp->rl[tid()]->size; iret++) {
186 uintptr_t obj = hp->rl[tid()]->list[iret];
187 bool can_delete = true;
188 for (int itid = 0; itid < isc__hp_max_threads && can_delete;
189 itid++) {
190 for (int ihp = hp->max_hps - 1; ihp >= 0; ihp--) {
191 if (atomic_load(&hp->hp[itid][ihp]) == obj) {
192 can_delete = false;
193 break;
194 }
195 }
196 }
197
198 if (can_delete) {
199 size_t bytes = (hp->rl[tid()]->size - iret) *
200 sizeof(hp->rl[tid()]->list[0]);
201 memmove(&hp->rl[tid()]->list[iret],
202 &hp->rl[tid()]->list[iret + 1], bytes);
203 hp->rl[tid()]->size--;
204 hp->deletefunc((void *)obj);
205 }
206 }
207 }
208