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 #define PCTRIE_DEFINE_SMR(name, type, field, allocfn, freefn, smr) \ 40 PCTRIE_DEFINE(name, type, field, allocfn, freefn) \ 41 \ 42 static __inline struct type * \ 43 name##_PCTRIE_LOOKUP_UNLOCKED(struct pctrie *ptree, uint64_t key) \ 44 { \ 45 \ 46 return name##_PCTRIE_VAL2PTR(pctrie_lookup_unlocked(ptree, \ 47 key, (smr))); \ 48 } \ 49 50 #define PCTRIE_DEFINE(name, type, field, allocfn, freefn) \ 51 \ 52 CTASSERT(sizeof(((struct type *)0)->field) == sizeof(uint64_t)); \ 53 /* \ 54 * XXX This assert protects flag bits, it does not enforce natural \ 55 * alignment. 32bit architectures do not naturally align 64bit fields. \ 56 */ \ 57 CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t) - 1)) == 0); \ 58 \ 59 static __inline struct type * \ 60 name##_PCTRIE_VAL2PTR(uint64_t *val) \ 61 { \ 62 \ 63 if (val == NULL) \ 64 return (NULL); \ 65 return (struct type *) \ 66 ((uintptr_t)val - __offsetof(struct type, field)); \ 67 } \ 68 \ 69 static __inline uint64_t * \ 70 name##_PCTRIE_PTR2VAL(struct type *ptr) \ 71 { \ 72 \ 73 return &ptr->field; \ 74 } \ 75 \ 76 static __inline int \ 77 name##_PCTRIE_INSERT(struct pctrie *ptree, struct type *ptr) \ 78 { \ 79 struct pctrie_node *parent; \ 80 void *parentp; \ 81 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \ 82 \ 83 parentp = pctrie_insert_lookup(ptree, val); \ 84 if (parentp == NULL) \ 85 return (0); \ 86 parent = allocfn(ptree); \ 87 if (parent == NULL) \ 88 return (ENOMEM); \ 89 pctrie_insert_node(parentp, parent, val); \ 90 return (0); \ 91 } \ 92 \ 93 static __inline __unused struct type * \ 94 name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key) \ 95 { \ 96 \ 97 return name##_PCTRIE_VAL2PTR(pctrie_lookup(ptree, key)); \ 98 } \ 99 \ 100 static __inline __unused struct type * \ 101 name##_PCTRIE_LOOKUP_LE(struct pctrie *ptree, uint64_t key) \ 102 { \ 103 \ 104 return name##_PCTRIE_VAL2PTR(pctrie_lookup_le(ptree, key)); \ 105 } \ 106 \ 107 static __inline __unused struct type * \ 108 name##_PCTRIE_LOOKUP_GE(struct pctrie *ptree, uint64_t key) \ 109 { \ 110 \ 111 return name##_PCTRIE_VAL2PTR(pctrie_lookup_ge(ptree, key)); \ 112 } \ 113 \ 114 static __inline __unused void \ 115 name##_PCTRIE_RECLAIM(struct pctrie *ptree) \ 116 { \ 117 struct pctrie_node *freenode, *node; \ 118 \ 119 for (freenode = pctrie_reclaim_begin(&node, ptree); \ 120 freenode != NULL; \ 121 freenode = pctrie_reclaim_resume(&node)) \ 122 freefn(ptree, freenode); \ 123 } \ 124 \ 125 static __inline __unused struct type * \ 126 name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr) \ 127 { \ 128 \ 129 return name##_PCTRIE_VAL2PTR( \ 130 pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr))); \ 131 } \ 132 \ 133 static __inline __unused void \ 134 name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key) \ 135 { \ 136 uint64_t *val; \ 137 struct pctrie_node *freenode; \ 138 \ 139 val = pctrie_remove_lookup(ptree, key, &freenode); \ 140 if (val == NULL) \ 141 panic("%s: key not found", __func__); \ 142 if (freenode != NULL) \ 143 freefn(ptree, freenode); \ 144 } \ 145 \ 146 static __inline __unused struct type * \ 147 name##_PCTRIE_REMOVE_LOOKUP(struct pctrie *ptree, uint64_t key) \ 148 { \ 149 uint64_t *val; \ 150 struct pctrie_node *freenode; \ 151 \ 152 val = pctrie_remove_lookup(ptree, key, &freenode); \ 153 if (freenode != NULL) \ 154 freefn(ptree, freenode); \ 155 return name##_PCTRIE_VAL2PTR(val); \ 156 } 157 158 void *pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val); 159 void pctrie_insert_node(void *parentp, 160 struct pctrie_node *parent, uint64_t *val); 161 uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key); 162 uint64_t *pctrie_lookup_ge(struct pctrie *ptree, uint64_t key); 163 uint64_t *pctrie_lookup_le(struct pctrie *ptree, uint64_t key); 164 uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key, 165 smr_t smr); 166 struct pctrie_node *pctrie_reclaim_begin(struct pctrie_node **pnode, 167 struct pctrie *ptree); 168 struct pctrie_node *pctrie_reclaim_resume(struct pctrie_node **pnode); 169 uint64_t *pctrie_remove_lookup(struct pctrie *ptree, uint64_t index, 170 struct pctrie_node **killnode); 171 uint64_t *pctrie_replace(struct pctrie *ptree, uint64_t *newval); 172 size_t pctrie_node_size(void); 173 int pctrie_zone_init(void *mem, int size, int flags); 174 175 /* 176 * Each search path in the trie terminates at a leaf, which is a pointer to a 177 * value marked with a set 1-bit. A leaf may be associated with a null pointer 178 * to indicate no value there. 179 */ 180 #define PCTRIE_ISLEAF 0x1 181 #define PCTRIE_NULL (struct pctrie_node *)PCTRIE_ISLEAF 182 183 static __inline void 184 pctrie_init(struct pctrie *ptree) 185 { 186 ptree->pt_root = PCTRIE_NULL; 187 } 188 189 static __inline bool 190 pctrie_is_empty(struct pctrie *ptree) 191 { 192 return (ptree->pt_root == PCTRIE_NULL); 193 } 194 195 /* Set of all flag bits stored in node pointers. */ 196 #define PCTRIE_FLAGS (PCTRIE_ISLEAF) 197 /* Minimum align parameter for uma_zcreate. */ 198 #define PCTRIE_PAD PCTRIE_FLAGS 199 200 /* 201 * These widths should allow the pointers to a node's children to fit within 202 * a single cache line. The extra levels from a narrow width should not be 203 * a problem thanks to path compression. 204 */ 205 #ifdef __LP64__ 206 #define PCTRIE_WIDTH 4 207 #else 208 #define PCTRIE_WIDTH 3 209 #endif 210 211 #define PCTRIE_COUNT (1 << PCTRIE_WIDTH) 212 213 #endif /* _KERNEL */ 214 #endif /* !_SYS_PCTRIE_H_ */ 215