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