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