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 struct pctrie_iter {
38 struct pctrie *ptree;
39 struct pctrie_node *node;
40 uint64_t index;
41 uint64_t limit;
42 };
43
44 static __inline void
pctrie_iter_reset(struct pctrie_iter * it)45 pctrie_iter_reset(struct pctrie_iter *it)
46 {
47 it->node = NULL;
48 }
49
50 static __inline void
pctrie_iter_init(struct pctrie_iter * it,struct pctrie * ptree)51 pctrie_iter_init(struct pctrie_iter *it, struct pctrie *ptree)
52 {
53 it->ptree = ptree;
54 it->node = NULL;
55 it->limit = 0;
56 }
57
58 static __inline void
pctrie_iter_limit_init(struct pctrie_iter * it,struct pctrie * ptree,uint64_t limit)59 pctrie_iter_limit_init(struct pctrie_iter *it, struct pctrie *ptree,
60 uint64_t limit)
61 {
62 pctrie_iter_init(it, ptree);
63 it->limit = limit;
64 }
65
66 #ifdef _KERNEL
67
68 typedef void (*pctrie_cb_t)(void *ptr, void *arg);
69
70 #define PCTRIE_DEFINE_SMR(name, type, field, allocfn, freefn, smr) \
71 PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
72 \
73 static __inline struct type * \
74 name##_PCTRIE_LOOKUP_UNLOCKED(struct pctrie *ptree, uint64_t key) \
75 { \
76 \
77 return name##_PCTRIE_VAL2PTR(pctrie_lookup_unlocked(ptree, \
78 key, (smr))); \
79 } \
80
81 #define PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
82 \
83 CTASSERT(sizeof(((struct type *)0)->field) == sizeof(uint64_t)); \
84 /* \
85 * XXX This assert protects flag bits, it does not enforce natural \
86 * alignment. 32bit architectures do not naturally align 64bit fields. \
87 */ \
88 CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t) - 1)) == 0); \
89 \
90 static __inline struct type * \
91 name##_PCTRIE_VAL2PTR(uint64_t *val) \
92 { \
93 \
94 if (val == NULL) \
95 return (NULL); \
96 return (struct type *) \
97 ((uintptr_t)val - __offsetof(struct type, field)); \
98 } \
99 \
100 static __inline uint64_t * \
101 name##_PCTRIE_PTR2VAL(struct type *ptr) \
102 { \
103 \
104 return &ptr->field; \
105 } \
106 \
107 static __inline __unused int \
108 name##_PCTRIE_INSERT_BASE(struct pctrie *ptree, uint64_t *val, \
109 struct pctrie_node *parent, void *parentp, \
110 uint64_t *found, struct type **found_out) \
111 { \
112 struct pctrie_node *child; \
113 \
114 if (__predict_false(found != NULL)) { \
115 *found_out = name##_PCTRIE_VAL2PTR(found); \
116 return (EEXIST); \
117 } \
118 if (parentp != NULL) { \
119 child = allocfn(ptree); \
120 if (__predict_false(child == NULL)) { \
121 if (found_out != NULL) \
122 *found_out = NULL; \
123 return (ENOMEM); \
124 } \
125 pctrie_insert_node(val, parent, parentp, child); \
126 } \
127 return (0); \
128 } \
129 \
130 static __inline __unused int \
131 name##_PCTRIE_INSERT(struct pctrie *ptree, struct type *ptr) \
132 { \
133 void *parentp; \
134 struct pctrie_node *parent; \
135 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
136 \
137 parentp = pctrie_insert_lookup_strict(ptree, val, &parent); \
138 return (name##_PCTRIE_INSERT_BASE(ptree, val, parent, parentp, \
139 NULL, NULL)); \
140 } \
141 \
142 static __inline __unused int \
143 name##_PCTRIE_FIND_OR_INSERT(struct pctrie *ptree, struct type *ptr, \
144 struct type **found_out_opt) \
145 { \
146 void *parentp; \
147 struct pctrie_node *parent; \
148 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
149 uint64_t *found; \
150 \
151 parentp = pctrie_insert_lookup(ptree, val, &parent, &found); \
152 return (name##_PCTRIE_INSERT_BASE(ptree, val, parent, parentp, \
153 found, found_out_opt)); \
154 } \
155 \
156 static __inline __unused int \
157 name##_PCTRIE_INSERT_LOOKUP_LE(struct pctrie *ptree, struct type *ptr, \
158 struct type **found_out) \
159 { \
160 struct pctrie_node *parent; \
161 void *parentp; \
162 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
163 uint64_t *found; \
164 int retval; \
165 \
166 parentp = pctrie_insert_lookup(ptree, val, &parent, &found); \
167 retval = name##_PCTRIE_INSERT_BASE(ptree, val, parent, parentp, \
168 found, found_out); \
169 if (retval != 0) \
170 return (retval); \
171 found = pctrie_subtree_lookup_lt(ptree, parent, *val); \
172 *found_out = name##_PCTRIE_VAL2PTR(found); \
173 return (0); \
174 } \
175 \
176 static __inline __unused int \
177 name##_PCTRIE_ITER_INSERT(struct pctrie_iter *it, struct type *ptr) \
178 { \
179 void *parentp; \
180 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
181 \
182 parentp = pctrie_iter_insert_lookup(it, val); \
183 return (name##_PCTRIE_INSERT_BASE(it->ptree, val, it->node, \
184 parentp, NULL, NULL)); \
185 } \
186 \
187 static __inline __unused struct type * \
188 name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key) \
189 { \
190 \
191 return name##_PCTRIE_VAL2PTR(pctrie_lookup(ptree, key)); \
192 } \
193 \
194 static __inline __unused struct type * \
195 name##_PCTRIE_LOOKUP_LE(struct pctrie *ptree, uint64_t key) \
196 { \
197 \
198 return name##_PCTRIE_VAL2PTR(pctrie_lookup_le(ptree, key)); \
199 } \
200 \
201 static __inline __unused struct type * \
202 name##_PCTRIE_LOOKUP_GE(struct pctrie *ptree, uint64_t key) \
203 { \
204 \
205 return name##_PCTRIE_VAL2PTR(pctrie_lookup_ge(ptree, key)); \
206 } \
207 \
208 static __inline __unused void \
209 name##_PCTRIE_RECLAIM(struct pctrie *ptree) \
210 { \
211 struct pctrie_node *freenode, *node; \
212 \
213 for (freenode = pctrie_reclaim_begin(&node, ptree); \
214 freenode != NULL; \
215 freenode = pctrie_reclaim_resume(&node)) \
216 freefn(ptree, freenode); \
217 } \
218 \
219 /* \
220 * While reclaiming all internal trie nodes, invoke callback(leaf, arg) \
221 * on every leaf in the trie, in order. \
222 */ \
223 static __inline __unused void \
224 name##_PCTRIE_RECLAIM_CALLBACK(struct pctrie *ptree, \
225 void (*typed_cb)(struct type *, void *), void *arg) \
226 { \
227 struct pctrie_node *freenode, *node; \
228 pctrie_cb_t callback = (pctrie_cb_t)typed_cb; \
229 \
230 for (freenode = pctrie_reclaim_begin_cb(&node, ptree, \
231 callback, __offsetof(struct type, field), arg); \
232 freenode != NULL; \
233 freenode = pctrie_reclaim_resume_cb(&node, \
234 callback, __offsetof(struct type, field), arg)) \
235 freefn(ptree, freenode); \
236 } \
237 \
238 static __inline __unused struct type * \
239 name##_PCTRIE_ITER_LOOKUP(struct pctrie_iter *it, uint64_t index) \
240 { \
241 return name##_PCTRIE_VAL2PTR(pctrie_iter_lookup(it, index)); \
242 } \
243 \
244 static __inline __unused struct type * \
245 name##_PCTRIE_ITER_STRIDE(struct pctrie_iter *it, int stride) \
246 { \
247 return name##_PCTRIE_VAL2PTR(pctrie_iter_stride(it, stride)); \
248 } \
249 \
250 static __inline __unused struct type * \
251 name##_PCTRIE_ITER_NEXT(struct pctrie_iter *it) \
252 { \
253 return name##_PCTRIE_VAL2PTR(pctrie_iter_next(it)); \
254 } \
255 \
256 static __inline __unused struct type * \
257 name##_PCTRIE_ITER_PREV(struct pctrie_iter *it) \
258 { \
259 return name##_PCTRIE_VAL2PTR(pctrie_iter_prev(it)); \
260 } \
261 \
262 static __inline __unused struct type * \
263 name##_PCTRIE_ITER_VALUE(struct pctrie_iter *it) \
264 { \
265 return name##_PCTRIE_VAL2PTR(pctrie_iter_value(it)); \
266 } \
267 \
268 static __inline __unused struct type * \
269 name##_PCTRIE_ITER_LOOKUP_GE(struct pctrie_iter *it, uint64_t index) \
270 { \
271 return name##_PCTRIE_VAL2PTR(pctrie_iter_lookup_ge(it, index)); \
272 } \
273 \
274 static __inline __unused struct type * \
275 name##_PCTRIE_ITER_JUMP_GE(struct pctrie_iter *it, int64_t jump) \
276 { \
277 return name##_PCTRIE_VAL2PTR(pctrie_iter_jump_ge(it, jump)); \
278 } \
279 \
280 static __inline __unused struct type * \
281 name##_PCTRIE_ITER_STEP_GE(struct pctrie_iter *it) \
282 { \
283 return name##_PCTRIE_VAL2PTR(pctrie_iter_jump_ge(it, 1)); \
284 } \
285 \
286 static __inline __unused struct type * \
287 name##_PCTRIE_ITER_LOOKUP_LE(struct pctrie_iter *it, uint64_t index) \
288 { \
289 return name##_PCTRIE_VAL2PTR(pctrie_iter_lookup_le(it, index)); \
290 } \
291 \
292 static __inline __unused struct type * \
293 name##_PCTRIE_ITER_JUMP_LE(struct pctrie_iter *it, int64_t jump) \
294 { \
295 return name##_PCTRIE_VAL2PTR(pctrie_iter_jump_le(it, jump)); \
296 } \
297 \
298 static __inline __unused struct type * \
299 name##_PCTRIE_ITER_STEP_LE(struct pctrie_iter *it) \
300 { \
301 return name##_PCTRIE_VAL2PTR(pctrie_iter_jump_le(it, 1)); \
302 } \
303 \
304 static __inline __unused void \
305 name##_PCTRIE_REMOVE_BASE(struct pctrie *ptree, \
306 struct pctrie_node *freenode) \
307 { \
308 if (freenode != NULL) \
309 freefn(ptree, freenode); \
310 } \
311 \
312 static __inline __unused void \
313 name##_PCTRIE_ITER_REMOVE(struct pctrie_iter *it) \
314 { \
315 uint64_t *val; \
316 struct pctrie_node *freenode; \
317 \
318 val = pctrie_iter_remove(it, &freenode); \
319 if (val == NULL) \
320 panic("%s: key not found", __func__); \
321 name##_PCTRIE_REMOVE_BASE(it->ptree, freenode); \
322 } \
323 \
324 static __inline __unused struct type * \
325 name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr) \
326 { \
327 \
328 return name##_PCTRIE_VAL2PTR( \
329 pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr))); \
330 } \
331 \
332 static __inline __unused void \
333 name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key) \
334 { \
335 uint64_t *val; \
336 struct pctrie_node *freenode; \
337 \
338 val = pctrie_remove_lookup(ptree, key, &freenode); \
339 if (val == NULL) \
340 panic("%s: key not found", __func__); \
341 name##_PCTRIE_REMOVE_BASE(ptree, freenode); \
342 } \
343 \
344 static __inline __unused struct type * \
345 name##_PCTRIE_REMOVE_LOOKUP(struct pctrie *ptree, uint64_t key) \
346 { \
347 uint64_t *val; \
348 struct pctrie_node *freenode; \
349 \
350 val = pctrie_remove_lookup(ptree, key, &freenode); \
351 name##_PCTRIE_REMOVE_BASE(ptree, freenode); \
352 return name##_PCTRIE_VAL2PTR(val); \
353 }
354
355 struct pctrie_iter;
356 void *pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val,
357 struct pctrie_node **parent_out, uint64_t **found_out);
358 void *pctrie_insert_lookup_strict(struct pctrie *ptree, uint64_t *val,
359 struct pctrie_node **parent_out);
360 void pctrie_insert_node(uint64_t *val, struct pctrie_node *parent,
361 void *parentp, struct pctrie_node *child);
362 uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key);
363 uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key,
364 smr_t smr);
365 uint64_t *pctrie_iter_lookup(struct pctrie_iter *it, uint64_t index);
366 uint64_t *pctrie_iter_stride(struct pctrie_iter *it, int stride);
367 uint64_t *pctrie_iter_next(struct pctrie_iter *it);
368 uint64_t *pctrie_iter_prev(struct pctrie_iter *it);
369 void *pctrie_iter_insert_lookup(struct pctrie_iter *it,
370 uint64_t *val);
371 uint64_t *pctrie_lookup_ge(struct pctrie *ptree, uint64_t key);
372 uint64_t *pctrie_iter_lookup_ge(struct pctrie_iter *it, uint64_t index);
373 uint64_t *pctrie_iter_jump_ge(struct pctrie_iter *it, int64_t jump);
374 uint64_t *pctrie_lookup_le(struct pctrie *ptree, uint64_t key);
375 uint64_t *pctrie_subtree_lookup_lt(struct pctrie *ptree,
376 struct pctrie_node *node, uint64_t key);
377 uint64_t *pctrie_iter_lookup_le(struct pctrie_iter *it, uint64_t index);
378 uint64_t *pctrie_iter_jump_le(struct pctrie_iter *it, int64_t jump);
379 struct pctrie_node *pctrie_reclaim_begin(struct pctrie_node **pnode,
380 struct pctrie *ptree);
381 struct pctrie_node *pctrie_reclaim_resume(struct pctrie_node **pnode);
382 struct pctrie_node *pctrie_reclaim_begin_cb(struct pctrie_node **pnode,
383 struct pctrie *ptree,
384 pctrie_cb_t callback, int keyoff, void *arg);
385 struct pctrie_node *pctrie_reclaim_resume_cb(struct pctrie_node **pnode,
386 pctrie_cb_t callback, int keyoff, void *arg);
387 uint64_t *pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
388 struct pctrie_node **killnode);
389 uint64_t *pctrie_iter_remove(struct pctrie_iter *it,
390 struct pctrie_node **freenode);
391 uint64_t *pctrie_iter_value(struct pctrie_iter *it);
392 uint64_t *pctrie_replace(struct pctrie *ptree, uint64_t *newval);
393 size_t pctrie_node_size(void);
394 int pctrie_zone_init(void *mem, int size, int flags);
395
396 /*
397 * Each search path in the trie terminates at a leaf, which is a pointer to a
398 * value marked with a set 1-bit. A leaf may be associated with a null pointer
399 * to indicate no value there.
400 */
401 #define PCTRIE_ISLEAF 0x1
402 #define PCTRIE_NULL (struct pctrie_node *)PCTRIE_ISLEAF
403
404 static __inline void
pctrie_init(struct pctrie * ptree)405 pctrie_init(struct pctrie *ptree)
406 {
407 ptree->pt_root = PCTRIE_NULL;
408 }
409
410 static __inline bool
pctrie_is_empty(struct pctrie * ptree)411 pctrie_is_empty(struct pctrie *ptree)
412 {
413 return (ptree->pt_root == PCTRIE_NULL);
414 }
415
416 /* Set of all flag bits stored in node pointers. */
417 #define PCTRIE_FLAGS (PCTRIE_ISLEAF)
418 /* Minimum align parameter for uma_zcreate. */
419 #define PCTRIE_PAD PCTRIE_FLAGS
420
421 /*
422 * These widths should allow the pointers to a node's children to fit within
423 * a single cache line. The extra levels from a narrow width should not be
424 * a problem thanks to path compression.
425 */
426 #ifdef __LP64__
427 #define PCTRIE_WIDTH 4
428 #else
429 #define PCTRIE_WIDTH 3
430 #endif
431
432 #define PCTRIE_COUNT (1 << PCTRIE_WIDTH)
433
434 #endif /* _KERNEL */
435 #endif /* !_SYS_PCTRIE_H_ */
436