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_BASE(struct pctrie *ptree, void *parentp, \
90 uint64_t *val, uint64_t *found, struct type **found_out) \
91 { \
92 struct pctrie_node *parent; \
93 \
94 if (__predict_false(found != NULL)) { \
95 *found_out = name##_PCTRIE_VAL2PTR(found); \
96 return (EEXIST); \
97 } \
98 if (parentp != NULL) { \
99 parent = allocfn(ptree); \
100 if (__predict_false(parent == NULL)) { \
101 if (found_out != NULL) \
102 *found_out = NULL; \
103 return (ENOMEM); \
104 } \
105 pctrie_insert_node(parentp, parent, val); \
106 } \
107 return (0); \
108 } \
109 \
110 static __inline __unused int \
111 name##_PCTRIE_INSERT(struct pctrie *ptree, struct type *ptr) \
112 { \
113 void *parentp; \
114 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
115 \
116 parentp = pctrie_insert_lookup_strict(ptree, val); \
117 return (name##_PCTRIE_INSERT_BASE(ptree, parentp, val, \
118 NULL, NULL)); \
119 } \
120 \
121 static __inline __unused int \
122 name##_PCTRIE_FIND_OR_INSERT(struct pctrie *ptree, struct type *ptr, \
123 struct type **found_out_opt) \
124 { \
125 void *parentp; \
126 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
127 uint64_t *found; \
128 \
129 parentp = pctrie_insert_lookup(ptree, val, &found); \
130 return (name##_PCTRIE_INSERT_BASE(ptree, parentp, val, \
131 found, found_out_opt)); \
132 } \
133 \
134 static __inline __unused int \
135 name##_PCTRIE_INSERT_LOOKUP_GE(struct pctrie *ptree, struct type *ptr, \
136 struct type **found_out) \
137 { \
138 struct pctrie_node *neighbor; \
139 void *parentp; \
140 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
141 uint64_t *found; \
142 int retval; \
143 \
144 parentp = pctrie_insert_lookup_gt(ptree, val, &found, \
145 &neighbor); \
146 retval = name##_PCTRIE_INSERT_BASE(ptree, parentp, val, \
147 found, found_out); \
148 if (retval != 0) \
149 return (retval); \
150 found = pctrie_subtree_lookup_gt(neighbor, *val); \
151 *found_out = name##_PCTRIE_VAL2PTR(found); \
152 pctrie_subtree_lookup_gt_assert(neighbor, *val, ptree, found); \
153 return (0); \
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 *neighbor; \
161 void *parentp; \
162 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
163 uint64_t *found; \
164 int retval; \
165 \
166 parentp = pctrie_insert_lookup_lt(ptree, val, &found, \
167 &neighbor); \
168 retval = name##_PCTRIE_INSERT_BASE(ptree, parentp, val, \
169 found, found_out); \
170 if (retval != 0) \
171 return (retval); \
172 found = pctrie_subtree_lookup_lt(neighbor, *val); \
173 *found_out = name##_PCTRIE_VAL2PTR(found); \
174 pctrie_subtree_lookup_lt_assert(neighbor, *val, ptree, found); \
175 return (0); \
176 } \
177 \
178 static __inline __unused struct type * \
179 name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key) \
180 { \
181 \
182 return name##_PCTRIE_VAL2PTR(pctrie_lookup(ptree, key)); \
183 } \
184 \
185 static __inline __unused struct type * \
186 name##_PCTRIE_LOOKUP_LE(struct pctrie *ptree, uint64_t key) \
187 { \
188 \
189 return name##_PCTRIE_VAL2PTR(pctrie_lookup_le(ptree, key)); \
190 } \
191 \
192 static __inline __unused struct type * \
193 name##_PCTRIE_LOOKUP_GE(struct pctrie *ptree, uint64_t key) \
194 { \
195 \
196 return name##_PCTRIE_VAL2PTR(pctrie_lookup_ge(ptree, key)); \
197 } \
198 \
199 static __inline __unused void \
200 name##_PCTRIE_RECLAIM(struct pctrie *ptree) \
201 { \
202 struct pctrie_node *freenode, *node; \
203 \
204 for (freenode = pctrie_reclaim_begin(&node, ptree); \
205 freenode != NULL; \
206 freenode = pctrie_reclaim_resume(&node)) \
207 freefn(ptree, freenode); \
208 } \
209 \
210 /* \
211 * While reclaiming all internal trie nodes, invoke callback(leaf, arg) \
212 * on every leaf in the trie, in order. \
213 */ \
214 static __inline __unused void \
215 name##_PCTRIE_RECLAIM_CALLBACK(struct pctrie *ptree, \
216 void (*typed_cb)(struct type *, void *), void *arg) \
217 { \
218 struct pctrie_node *freenode, *node; \
219 pctrie_cb_t callback = (pctrie_cb_t)typed_cb; \
220 \
221 for (freenode = pctrie_reclaim_begin_cb(&node, ptree, \
222 callback, __offsetof(struct type, field), arg); \
223 freenode != NULL; \
224 freenode = pctrie_reclaim_resume_cb(&node, \
225 callback, __offsetof(struct type, field), arg)) \
226 freefn(ptree, freenode); \
227 } \
228 \
229 static __inline __unused int \
230 name##_PCTRIE_ITER_INSERT(struct pctrie_iter *it, struct type *ptr) \
231 { \
232 struct pctrie_node *parent; \
233 void *parentp; \
234 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
235 \
236 parentp = pctrie_iter_insert_lookup(it, val); \
237 if (parentp == NULL) \
238 return (0); \
239 parent = allocfn(it->ptree); \
240 if (__predict_false(parent == NULL)) \
241 return (ENOMEM); \
242 pctrie_insert_node(parentp, parent, val); \
243 it->path[it->top++] = parent; \
244 return (0); \
245 } \
246 \
247 static __inline __unused struct type * \
248 name##_PCTRIE_ITER_LOOKUP(struct pctrie_iter *it, uint64_t index) \
249 { \
250 return name##_PCTRIE_VAL2PTR(pctrie_iter_lookup(it, index)); \
251 } \
252 \
253 static __inline __unused struct type * \
254 name##_PCTRIE_ITER_STRIDE(struct pctrie_iter *it, int stride) \
255 { \
256 return name##_PCTRIE_VAL2PTR(pctrie_iter_stride(it, stride)); \
257 } \
258 \
259 static __inline __unused struct type * \
260 name##_PCTRIE_ITER_NEXT(struct pctrie_iter *it) \
261 { \
262 return name##_PCTRIE_VAL2PTR(pctrie_iter_next(it)); \
263 } \
264 \
265 static __inline __unused struct type * \
266 name##_PCTRIE_ITER_PREV(struct pctrie_iter *it) \
267 { \
268 return name##_PCTRIE_VAL2PTR(pctrie_iter_prev(it)); \
269 } \
270 \
271 static __inline __unused struct type * \
272 name##_PCTRIE_ITER_VALUE(struct pctrie_iter *it) \
273 { \
274 return name##_PCTRIE_VAL2PTR(pctrie_iter_value(it)); \
275 } \
276 \
277 static __inline __unused struct type * \
278 name##_PCTRIE_ITER_LOOKUP_GE(struct pctrie_iter *it, uint64_t index) \
279 { \
280 return name##_PCTRIE_VAL2PTR(pctrie_iter_lookup_ge(it, index)); \
281 } \
282 \
283 static __inline __unused struct type * \
284 name##_PCTRIE_ITER_JUMP_GE(struct pctrie_iter *it, int64_t jump) \
285 { \
286 return name##_PCTRIE_VAL2PTR(pctrie_iter_jump_ge(it, jump)); \
287 } \
288 \
289 static __inline __unused struct type * \
290 name##_PCTRIE_ITER_STEP_GE(struct pctrie_iter *it) \
291 { \
292 return name##_PCTRIE_VAL2PTR(pctrie_iter_jump_ge(it, 1)); \
293 } \
294 \
295 static __inline __unused struct type * \
296 name##_PCTRIE_ITER_LOOKUP_LE(struct pctrie_iter *it, uint64_t index) \
297 { \
298 return name##_PCTRIE_VAL2PTR(pctrie_iter_lookup_le(it, index)); \
299 } \
300 \
301 static __inline __unused struct type * \
302 name##_PCTRIE_ITER_JUMP_LE(struct pctrie_iter *it, int64_t jump) \
303 { \
304 return name##_PCTRIE_VAL2PTR(pctrie_iter_jump_le(it, jump)); \
305 } \
306 \
307 static __inline __unused struct type * \
308 name##_PCTRIE_ITER_STEP_LE(struct pctrie_iter *it) \
309 { \
310 return name##_PCTRIE_VAL2PTR(pctrie_iter_jump_le(it, 1)); \
311 } \
312 \
313 static __inline __unused void \
314 name##_PCTRIE_REMOVE_BASE(struct pctrie *ptree, \
315 struct pctrie_node *freenode) \
316 { \
317 if (freenode != NULL) \
318 freefn(ptree, freenode); \
319 } \
320 \
321 static __inline __unused void \
322 name##_PCTRIE_ITER_REMOVE(struct pctrie_iter *it) \
323 { \
324 uint64_t *val; \
325 struct pctrie_node *freenode; \
326 \
327 val = pctrie_iter_remove(it, &freenode); \
328 if (val == NULL) \
329 panic("%s: key not found", __func__); \
330 name##_PCTRIE_REMOVE_BASE(it->ptree, freenode); \
331 } \
332 \
333 static __inline __unused struct type * \
334 name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr) \
335 { \
336 \
337 return name##_PCTRIE_VAL2PTR( \
338 pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr))); \
339 } \
340 \
341 static __inline __unused void \
342 name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key) \
343 { \
344 uint64_t *val; \
345 struct pctrie_node *freenode; \
346 \
347 val = pctrie_remove_lookup(ptree, key, &freenode); \
348 if (val == NULL) \
349 panic("%s: key not found", __func__); \
350 name##_PCTRIE_REMOVE_BASE(ptree, freenode); \
351 } \
352 \
353 static __inline __unused struct type * \
354 name##_PCTRIE_REMOVE_LOOKUP(struct pctrie *ptree, uint64_t key) \
355 { \
356 uint64_t *val; \
357 struct pctrie_node *freenode; \
358 \
359 val = pctrie_remove_lookup(ptree, key, &freenode); \
360 name##_PCTRIE_REMOVE_BASE(ptree, freenode); \
361 return name##_PCTRIE_VAL2PTR(val); \
362 }
363
364 struct pctrie_iter;
365 void *pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val,
366 uint64_t **found_out);
367 void *pctrie_insert_lookup_gt(struct pctrie *ptree, uint64_t *val,
368 uint64_t **found_out, struct pctrie_node **neighbor_out);
369 void *pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t *val,
370 uint64_t **found_out, struct pctrie_node **neighbor_out);
371 void *pctrie_insert_lookup_strict(struct pctrie *ptree,
372 uint64_t *val);
373 void pctrie_insert_node(void *parentp,
374 struct pctrie_node *parent, uint64_t *val);
375 uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key);
376 uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key,
377 smr_t smr);
378 uint64_t *pctrie_iter_lookup(struct pctrie_iter *it, uint64_t index);
379 uint64_t *pctrie_iter_stride(struct pctrie_iter *it, int stride);
380 uint64_t *pctrie_iter_next(struct pctrie_iter *it);
381 uint64_t *pctrie_iter_prev(struct pctrie_iter *it);
382 void *pctrie_iter_insert_lookup(struct pctrie_iter *it,
383 uint64_t *val);
384 uint64_t *pctrie_lookup_ge(struct pctrie *ptree, uint64_t key);
385 uint64_t *pctrie_subtree_lookup_gt(struct pctrie_node *node,
386 uint64_t key);
387 uint64_t *pctrie_iter_lookup_ge(struct pctrie_iter *it, uint64_t index);
388 uint64_t *pctrie_iter_jump_ge(struct pctrie_iter *it, int64_t jump);
389 uint64_t *pctrie_lookup_le(struct pctrie *ptree, uint64_t key);
390 uint64_t *pctrie_subtree_lookup_lt(struct pctrie_node *node,
391 uint64_t key);
392 uint64_t *pctrie_iter_lookup_le(struct pctrie_iter *it, uint64_t index);
393 uint64_t *pctrie_iter_jump_le(struct pctrie_iter *it, int64_t jump);
394 struct pctrie_node *pctrie_reclaim_begin(struct pctrie_node **pnode,
395 struct pctrie *ptree);
396 struct pctrie_node *pctrie_reclaim_resume(struct pctrie_node **pnode);
397 struct pctrie_node *pctrie_reclaim_begin_cb(struct pctrie_node **pnode,
398 struct pctrie *ptree,
399 pctrie_cb_t callback, int keyoff, void *arg);
400 struct pctrie_node *pctrie_reclaim_resume_cb(struct pctrie_node **pnode,
401 pctrie_cb_t callback, int keyoff, void *arg);
402 uint64_t *pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
403 struct pctrie_node **killnode);
404 uint64_t *pctrie_iter_remove(struct pctrie_iter *it,
405 struct pctrie_node **freenode);
406 uint64_t *pctrie_iter_value(struct pctrie_iter *it);
407 uint64_t *pctrie_replace(struct pctrie *ptree, uint64_t *newval);
408 size_t pctrie_node_size(void);
409 int pctrie_zone_init(void *mem, int size, int flags);
410
411 /*
412 * Each search path in the trie terminates at a leaf, which is a pointer to a
413 * value marked with a set 1-bit. A leaf may be associated with a null pointer
414 * to indicate no value there.
415 */
416 #define PCTRIE_ISLEAF 0x1
417 #define PCTRIE_NULL (struct pctrie_node *)PCTRIE_ISLEAF
418
419 static __inline void
pctrie_init(struct pctrie * ptree)420 pctrie_init(struct pctrie *ptree)
421 {
422 ptree->pt_root = PCTRIE_NULL;
423 }
424
425 static __inline bool
pctrie_is_empty(struct pctrie * ptree)426 pctrie_is_empty(struct pctrie *ptree)
427 {
428 return (ptree->pt_root == PCTRIE_NULL);
429 }
430
431 /* Set of all flag bits stored in node pointers. */
432 #define PCTRIE_FLAGS (PCTRIE_ISLEAF)
433 /* Minimum align parameter for uma_zcreate. */
434 #define PCTRIE_PAD PCTRIE_FLAGS
435
436 /*
437 * These widths should allow the pointers to a node's children to fit within
438 * a single cache line. The extra levels from a narrow width should not be
439 * a problem thanks to path compression.
440 */
441 #ifdef __LP64__
442 #define PCTRIE_WIDTH 4
443 #else
444 #define PCTRIE_WIDTH 3
445 #endif
446
447 #define PCTRIE_COUNT (1 << PCTRIE_WIDTH)
448 #define PCTRIE_LIMIT howmany(sizeof(uint64_t) * NBBY, PCTRIE_WIDTH)
449
450 struct pctrie_iter {
451 struct pctrie *ptree;
452 struct pctrie_node *path[PCTRIE_LIMIT];
453 uint64_t index;
454 uint64_t limit;
455 int top;
456 };
457
458 static __inline void
pctrie_iter_reset(struct pctrie_iter * it)459 pctrie_iter_reset(struct pctrie_iter *it)
460 {
461 it->top = 0;
462 }
463
464 static __inline void
pctrie_iter_init(struct pctrie_iter * it,struct pctrie * ptree)465 pctrie_iter_init(struct pctrie_iter *it, struct pctrie *ptree)
466 {
467 it->ptree = ptree;
468 it->top = 0;
469 it->limit = 0;
470 }
471
472 static __inline void
pctrie_iter_limit_init(struct pctrie_iter * it,struct pctrie * ptree,uint64_t limit)473 pctrie_iter_limit_init(struct pctrie_iter *it, struct pctrie *ptree,
474 uint64_t limit)
475 {
476 pctrie_iter_init(it, ptree);
477 it->limit = limit;
478 }
479
480 #endif /* _KERNEL */
481 #endif /* !_SYS_PCTRIE_H_ */
482