1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause
3 *
4 * Copyright (c) 2013 EMC Corp.
5 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org>
6 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 */
30
31 #ifndef _SYS_PCTRIE_H_
32 #define _SYS_PCTRIE_H_
33
34 #include <sys/_pctrie.h>
35 #include <sys/_smr.h>
36
37 #ifdef _KERNEL
38
39 typedef void (*pctrie_cb_t)(void *ptr, void *arg);
40
41 #define PCTRIE_DEFINE_SMR(name, type, field, allocfn, freefn, smr) \
42 PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
43 \
44 static __inline struct type * \
45 name##_PCTRIE_LOOKUP_UNLOCKED(struct pctrie *ptree, uint64_t key) \
46 { \
47 \
48 return name##_PCTRIE_VAL2PTR(pctrie_lookup_unlocked(ptree, \
49 key, (smr))); \
50 } \
51
52 #ifdef INVARIANTS
53 void pctrie_subtree_lookup_gt_assert(struct pctrie_node *node,
54 uint64_t key, struct pctrie *ptree, uint64_t *res);
55 void pctrie_subtree_lookup_lt_assert(struct pctrie_node *node,
56 uint64_t key, struct pctrie *ptree, uint64_t *res);
57 #else
58 #define pctrie_subtree_lookup_gt_assert(node, key, ptree, res)
59 #define pctrie_subtree_lookup_lt_assert(node, key, ptree, res)
60 #endif
61
62 #define PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
63 \
64 CTASSERT(sizeof(((struct type *)0)->field) == sizeof(uint64_t)); \
65 /* \
66 * XXX This assert protects flag bits, it does not enforce natural \
67 * alignment. 32bit architectures do not naturally align 64bit fields. \
68 */ \
69 CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t) - 1)) == 0); \
70 \
71 static __inline struct type * \
72 name##_PCTRIE_VAL2PTR(uint64_t *val) \
73 { \
74 \
75 if (val == NULL) \
76 return (NULL); \
77 return (struct type *) \
78 ((uintptr_t)val - __offsetof(struct type, field)); \
79 } \
80 \
81 static __inline uint64_t * \
82 name##_PCTRIE_PTR2VAL(struct type *ptr) \
83 { \
84 \
85 return &ptr->field; \
86 } \
87 \
88 static __inline __unused int \
89 name##_PCTRIE_INSERT(struct pctrie *ptree, struct type *ptr) \
90 { \
91 struct pctrie_node *parent; \
92 void *parentp; \
93 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
94 \
95 parentp = pctrie_insert_lookup_strict(ptree, val); \
96 if (parentp == NULL) \
97 return (0); \
98 parent = allocfn(ptree); \
99 if (__predict_false(parent == NULL)) \
100 return (ENOMEM); \
101 pctrie_insert_node(parentp, parent, val); \
102 return (0); \
103 } \
104 \
105 static __inline __unused int \
106 name##_PCTRIE_FIND_OR_INSERT(struct pctrie *ptree, struct type *ptr, \
107 struct type **found_out_opt) \
108 { \
109 struct pctrie_node *parent; \
110 void *parentp; \
111 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
112 uint64_t *found; \
113 \
114 parentp = pctrie_insert_lookup(ptree, val, &found); \
115 if (found != NULL) { \
116 if (found_out_opt != NULL) \
117 *found_out_opt = name##_PCTRIE_VAL2PTR(found); \
118 return (EEXIST); \
119 } \
120 if (parentp == NULL) \
121 return (0); \
122 parent = allocfn(ptree); \
123 if (__predict_false(parent == NULL)) \
124 return (ENOMEM); \
125 pctrie_insert_node(parentp, parent, val); \
126 return (0); \
127 } \
128 \
129 static __inline __unused int \
130 name##_PCTRIE_INSERT_LOOKUP_GE(struct pctrie *ptree, struct type *ptr, \
131 struct type **found_out) \
132 { \
133 struct pctrie_node *parent, *neighbor; \
134 void *parentp; \
135 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
136 uint64_t *found; \
137 \
138 parentp = pctrie_insert_lookup_gt(ptree, val, &found, \
139 &neighbor); \
140 if (__predict_false(found != NULL)) { \
141 *found_out = name##_PCTRIE_VAL2PTR(found); \
142 return (EEXIST); \
143 } \
144 if (parentp != NULL) { \
145 parent = allocfn(ptree); \
146 if (__predict_false(parent == NULL)) { \
147 *found_out = NULL; \
148 return (ENOMEM); \
149 } \
150 if (neighbor == parentp) \
151 neighbor = parent; \
152 pctrie_insert_node(parentp, parent, val); \
153 } \
154 found = pctrie_subtree_lookup_gt(neighbor, *val); \
155 *found_out = name##_PCTRIE_VAL2PTR(found); \
156 pctrie_subtree_lookup_gt_assert(neighbor, *val, ptree, found); \
157 return (0); \
158 } \
159 \
160 static __inline __unused int \
161 name##_PCTRIE_INSERT_LOOKUP_LE(struct pctrie *ptree, struct type *ptr, \
162 struct type **found_out) \
163 { \
164 struct pctrie_node *parent, *neighbor; \
165 void *parentp; \
166 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
167 uint64_t *found; \
168 \
169 parentp = pctrie_insert_lookup_lt(ptree, val, &found, \
170 &neighbor); \
171 if (__predict_false(found != NULL)) { \
172 *found_out = name##_PCTRIE_VAL2PTR(found); \
173 return (EEXIST); \
174 } \
175 if (parentp != NULL) { \
176 parent = allocfn(ptree); \
177 if (__predict_false(parent == NULL)) { \
178 *found_out = NULL; \
179 return (ENOMEM); \
180 } \
181 if (neighbor == parentp) \
182 neighbor = parent; \
183 pctrie_insert_node(parentp, parent, val); \
184 } \
185 found = pctrie_subtree_lookup_lt(neighbor, *val); \
186 *found_out = name##_PCTRIE_VAL2PTR(found); \
187 pctrie_subtree_lookup_lt_assert(neighbor, *val, ptree, found); \
188 return (0); \
189 } \
190 \
191 static __inline __unused struct type * \
192 name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key) \
193 { \
194 \
195 return name##_PCTRIE_VAL2PTR(pctrie_lookup(ptree, key)); \
196 } \
197 \
198 static __inline __unused struct type * \
199 name##_PCTRIE_LOOKUP_LE(struct pctrie *ptree, uint64_t key) \
200 { \
201 \
202 return name##_PCTRIE_VAL2PTR(pctrie_lookup_le(ptree, key)); \
203 } \
204 \
205 static __inline __unused struct type * \
206 name##_PCTRIE_LOOKUP_GE(struct pctrie *ptree, uint64_t key) \
207 { \
208 \
209 return name##_PCTRIE_VAL2PTR(pctrie_lookup_ge(ptree, key)); \
210 } \
211 \
212 static __inline __unused void \
213 name##_PCTRIE_RECLAIM(struct pctrie *ptree) \
214 { \
215 struct pctrie_node *freenode, *node; \
216 \
217 for (freenode = pctrie_reclaim_begin(&node, ptree); \
218 freenode != NULL; \
219 freenode = pctrie_reclaim_resume(&node)) \
220 freefn(ptree, freenode); \
221 } \
222 \
223 /* \
224 * While reclaiming all internal trie nodes, invoke callback(leaf, arg) \
225 * on every leaf in the trie, in order. \
226 */ \
227 static __inline __unused void \
228 name##_PCTRIE_RECLAIM_CALLBACK(struct pctrie *ptree, \
229 void (*typed_cb)(struct type *, void *), void *arg) \
230 { \
231 struct pctrie_node *freenode, *node; \
232 pctrie_cb_t callback = (pctrie_cb_t)typed_cb; \
233 \
234 for (freenode = pctrie_reclaim_begin_cb(&node, ptree, \
235 callback, __offsetof(struct type, field), arg); \
236 freenode != NULL; \
237 freenode = pctrie_reclaim_resume_cb(&node, \
238 callback, __offsetof(struct type, field), arg)) \
239 freefn(ptree, freenode); \
240 } \
241 \
242 static __inline __unused struct type * \
243 name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr) \
244 { \
245 \
246 return name##_PCTRIE_VAL2PTR( \
247 pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr))); \
248 } \
249 \
250 static __inline __unused void \
251 name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key) \
252 { \
253 uint64_t *val; \
254 struct pctrie_node *freenode; \
255 \
256 val = pctrie_remove_lookup(ptree, key, &freenode); \
257 if (val == NULL) \
258 panic("%s: key not found", __func__); \
259 if (freenode != NULL) \
260 freefn(ptree, freenode); \
261 } \
262 \
263 static __inline __unused struct type * \
264 name##_PCTRIE_REMOVE_LOOKUP(struct pctrie *ptree, uint64_t key) \
265 { \
266 uint64_t *val; \
267 struct pctrie_node *freenode; \
268 \
269 val = pctrie_remove_lookup(ptree, key, &freenode); \
270 if (freenode != NULL) \
271 freefn(ptree, freenode); \
272 return name##_PCTRIE_VAL2PTR(val); \
273 }
274
275 void *pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val,
276 uint64_t **found_out);
277 void *pctrie_insert_lookup_gt(struct pctrie *ptree, uint64_t *val,
278 uint64_t **found_out, struct pctrie_node **neighbor_out);
279 void *pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t *val,
280 uint64_t **found_out, struct pctrie_node **neighbor_out);
281 void *pctrie_insert_lookup_strict(struct pctrie *ptree,
282 uint64_t *val);
283 void pctrie_insert_node(void *parentp,
284 struct pctrie_node *parent, uint64_t *val);
285 uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key);
286 uint64_t *pctrie_lookup_ge(struct pctrie *ptree, uint64_t key);
287 uint64_t *pctrie_lookup_le(struct pctrie *ptree, uint64_t key);
288 uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key,
289 smr_t smr);
290 struct pctrie_node *pctrie_reclaim_begin(struct pctrie_node **pnode,
291 struct pctrie *ptree);
292 struct pctrie_node *pctrie_reclaim_resume(struct pctrie_node **pnode);
293 struct pctrie_node *pctrie_reclaim_begin_cb(struct pctrie_node **pnode,
294 struct pctrie *ptree,
295 pctrie_cb_t callback, int keyoff, void *arg);
296 struct pctrie_node *pctrie_reclaim_resume_cb(struct pctrie_node **pnode,
297 pctrie_cb_t callback, int keyoff, void *arg);
298 uint64_t *pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
299 struct pctrie_node **killnode);
300 uint64_t *pctrie_replace(struct pctrie *ptree, uint64_t *newval);
301 uint64_t *pctrie_subtree_lookup_gt(struct pctrie_node *node,
302 uint64_t key);
303 uint64_t *pctrie_subtree_lookup_lt(struct pctrie_node *node,
304 uint64_t key);
305 size_t pctrie_node_size(void);
306 int pctrie_zone_init(void *mem, int size, int flags);
307
308 /*
309 * Each search path in the trie terminates at a leaf, which is a pointer to a
310 * value marked with a set 1-bit. A leaf may be associated with a null pointer
311 * to indicate no value there.
312 */
313 #define PCTRIE_ISLEAF 0x1
314 #define PCTRIE_NULL (struct pctrie_node *)PCTRIE_ISLEAF
315
316 static __inline void
pctrie_init(struct pctrie * ptree)317 pctrie_init(struct pctrie *ptree)
318 {
319 ptree->pt_root = PCTRIE_NULL;
320 }
321
322 static __inline bool
pctrie_is_empty(struct pctrie * ptree)323 pctrie_is_empty(struct pctrie *ptree)
324 {
325 return (ptree->pt_root == PCTRIE_NULL);
326 }
327
328 /* Set of all flag bits stored in node pointers. */
329 #define PCTRIE_FLAGS (PCTRIE_ISLEAF)
330 /* Minimum align parameter for uma_zcreate. */
331 #define PCTRIE_PAD PCTRIE_FLAGS
332
333 /*
334 * These widths should allow the pointers to a node's children to fit within
335 * a single cache line. The extra levels from a narrow width should not be
336 * a problem thanks to path compression.
337 */
338 #ifdef __LP64__
339 #define PCTRIE_WIDTH 4
340 #else
341 #define PCTRIE_WIDTH 3
342 #endif
343
344 #define PCTRIE_COUNT (1 << PCTRIE_WIDTH)
345
346 #endif /* _KERNEL */
347 #endif /* !_SYS_PCTRIE_H_ */
348