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 420 pctrie_init(struct pctrie *ptree) 421 { 422 ptree->pt_root = PCTRIE_NULL; 423 } 424 425 static __inline bool 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 459 pctrie_iter_reset(struct pctrie_iter *it) 460 { 461 it->top = 0; 462 } 463 464 static __inline void 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 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