1 /*- 2 * Copyright (c) 2010 Isilon Systems, Inc. 3 * Copyright (c) 2010 iX Systems, Inc. 4 * Copyright (c) 2010 Panasas, Inc. 5 * Copyright (c) 2013-2020 Mellanox Technologies, Ltd. 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice unmodified, this list of conditions, and the following 13 * 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 ``AS IS'' AND ANY EXPRESS OR 19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30 #include <sys/cdefs.h> 31 __FBSDID("$FreeBSD$"); 32 33 #include <sys/param.h> 34 #include <sys/systm.h> 35 #include <sys/malloc.h> 36 #include <sys/kernel.h> 37 #include <sys/sysctl.h> 38 39 #include <linux/slab.h> 40 #include <linux/kernel.h> 41 #include <linux/radix-tree.h> 42 #include <linux/err.h> 43 44 static MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat"); 45 46 static inline unsigned long 47 radix_max(struct radix_tree_root *root) 48 { 49 return ((1UL << (root->height * RADIX_TREE_MAP_SHIFT)) - 1UL); 50 } 51 52 static inline int 53 radix_pos(long id, int height) 54 { 55 return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK; 56 } 57 58 static void 59 radix_tree_clean_root_node(struct radix_tree_root *root) 60 { 61 /* Check if the root node should be freed */ 62 if (root->rnode->count == 0) { 63 free(root->rnode, M_RADIX); 64 root->rnode = NULL; 65 root->height = 0; 66 } 67 } 68 69 void * 70 radix_tree_lookup(struct radix_tree_root *root, unsigned long index) 71 { 72 struct radix_tree_node *node; 73 void *item; 74 int height; 75 76 item = NULL; 77 node = root->rnode; 78 height = root->height - 1; 79 if (index > radix_max(root)) 80 goto out; 81 while (height && node) 82 node = node->slots[radix_pos(index, height--)]; 83 if (node) 84 item = node->slots[radix_pos(index, 0)]; 85 86 out: 87 return (item); 88 } 89 90 bool 91 radix_tree_iter_find(struct radix_tree_root *root, struct radix_tree_iter *iter, 92 void ***pppslot) 93 { 94 struct radix_tree_node *node; 95 unsigned long index = iter->index; 96 int height; 97 98 restart: 99 node = root->rnode; 100 if (node == NULL) 101 return (false); 102 height = root->height - 1; 103 if (height == -1 || index > radix_max(root)) 104 return (false); 105 do { 106 unsigned long mask = RADIX_TREE_MAP_MASK << (RADIX_TREE_MAP_SHIFT * height); 107 unsigned long step = 1UL << (RADIX_TREE_MAP_SHIFT * height); 108 int pos = radix_pos(index, height); 109 struct radix_tree_node *next; 110 111 /* track last slot */ 112 *pppslot = node->slots + pos; 113 114 next = node->slots[pos]; 115 if (next == NULL) { 116 index += step; 117 index &= -step; 118 if ((index & mask) == 0) 119 goto restart; 120 } else { 121 node = next; 122 height--; 123 } 124 } while (height != -1); 125 iter->index = index; 126 return (true); 127 } 128 129 void * 130 radix_tree_delete(struct radix_tree_root *root, unsigned long index) 131 { 132 struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT]; 133 struct radix_tree_node *node; 134 void *item; 135 int height; 136 int idx; 137 138 item = NULL; 139 node = root->rnode; 140 height = root->height - 1; 141 if (index > radix_max(root)) 142 goto out; 143 /* 144 * Find the node and record the path in stack. 145 */ 146 while (height && node) { 147 stack[height] = node; 148 node = node->slots[radix_pos(index, height--)]; 149 } 150 idx = radix_pos(index, 0); 151 if (node) 152 item = node->slots[idx]; 153 /* 154 * If we removed something reduce the height of the tree. 155 */ 156 if (item) 157 for (;;) { 158 node->slots[idx] = NULL; 159 node->count--; 160 if (node->count > 0) 161 break; 162 free(node, M_RADIX); 163 if (node == root->rnode) { 164 root->rnode = NULL; 165 root->height = 0; 166 break; 167 } 168 height++; 169 node = stack[height]; 170 idx = radix_pos(index, height); 171 } 172 out: 173 return (item); 174 } 175 176 void 177 radix_tree_iter_delete(struct radix_tree_root *root, 178 struct radix_tree_iter *iter, void **slot) 179 { 180 radix_tree_delete(root, iter->index); 181 } 182 183 int 184 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item) 185 { 186 struct radix_tree_node *node; 187 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1]; 188 int height; 189 int idx; 190 191 /* bail out upon insertion of a NULL item */ 192 if (item == NULL) 193 return (-EINVAL); 194 195 /* get root node, if any */ 196 node = root->rnode; 197 198 /* allocate root node, if any */ 199 if (node == NULL) { 200 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 201 if (node == NULL) 202 return (-ENOMEM); 203 root->rnode = node; 204 root->height++; 205 } 206 207 /* expand radix tree as needed */ 208 while (radix_max(root) < index) { 209 210 /* check if the radix tree is getting too big */ 211 if (root->height == RADIX_TREE_MAX_HEIGHT) { 212 radix_tree_clean_root_node(root); 213 return (-E2BIG); 214 } 215 216 /* 217 * If the root radix level is not empty, we need to 218 * allocate a new radix level: 219 */ 220 if (node->count != 0) { 221 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 222 if (node == NULL) { 223 /* 224 * Freeing the already allocated radix 225 * levels, if any, will be handled by 226 * the radix_tree_delete() function. 227 * This code path can only happen when 228 * the tree is not empty. 229 */ 230 return (-ENOMEM); 231 } 232 node->slots[0] = root->rnode; 233 node->count++; 234 root->rnode = node; 235 } 236 root->height++; 237 } 238 239 /* get radix tree height index */ 240 height = root->height - 1; 241 242 /* walk down the tree until the first missing node, if any */ 243 for ( ; height != 0; height--) { 244 idx = radix_pos(index, height); 245 if (node->slots[idx] == NULL) 246 break; 247 node = node->slots[idx]; 248 } 249 250 /* allocate the missing radix levels, if any */ 251 for (idx = 0; idx != height; idx++) { 252 temp[idx] = malloc(sizeof(*node), M_RADIX, 253 root->gfp_mask | M_ZERO); 254 if (temp[idx] == NULL) { 255 while (idx--) 256 free(temp[idx], M_RADIX); 257 radix_tree_clean_root_node(root); 258 return (-ENOMEM); 259 } 260 } 261 262 /* setup new radix levels, if any */ 263 for ( ; height != 0; height--) { 264 idx = radix_pos(index, height); 265 node->slots[idx] = temp[height - 1]; 266 node->count++; 267 node = node->slots[idx]; 268 } 269 270 /* 271 * Insert and adjust count if the item does not already exist. 272 */ 273 idx = radix_pos(index, 0); 274 if (node->slots[idx]) 275 return (-EEXIST); 276 node->slots[idx] = item; 277 node->count++; 278 279 return (0); 280 } 281 282 int 283 radix_tree_store(struct radix_tree_root *root, unsigned long index, void **ppitem) 284 { 285 struct radix_tree_node *node; 286 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1]; 287 void *pitem; 288 int height; 289 int idx; 290 291 /* 292 * Inserting a NULL item means delete it. The old pointer is 293 * stored at the location pointed to by "ppitem". 294 */ 295 if (*ppitem == NULL) { 296 *ppitem = radix_tree_delete(root, index); 297 return (0); 298 } 299 300 /* get root node, if any */ 301 node = root->rnode; 302 303 /* allocate root node, if any */ 304 if (node == NULL) { 305 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 306 if (node == NULL) 307 return (-ENOMEM); 308 root->rnode = node; 309 root->height++; 310 } 311 312 /* expand radix tree as needed */ 313 while (radix_max(root) < index) { 314 315 /* check if the radix tree is getting too big */ 316 if (root->height == RADIX_TREE_MAX_HEIGHT) { 317 radix_tree_clean_root_node(root); 318 return (-E2BIG); 319 } 320 321 /* 322 * If the root radix level is not empty, we need to 323 * allocate a new radix level: 324 */ 325 if (node->count != 0) { 326 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 327 if (node == NULL) { 328 /* 329 * Freeing the already allocated radix 330 * levels, if any, will be handled by 331 * the radix_tree_delete() function. 332 * This code path can only happen when 333 * the tree is not empty. 334 */ 335 return (-ENOMEM); 336 } 337 node->slots[0] = root->rnode; 338 node->count++; 339 root->rnode = node; 340 } 341 root->height++; 342 } 343 344 /* get radix tree height index */ 345 height = root->height - 1; 346 347 /* walk down the tree until the first missing node, if any */ 348 for ( ; height != 0; height--) { 349 idx = radix_pos(index, height); 350 if (node->slots[idx] == NULL) 351 break; 352 node = node->slots[idx]; 353 } 354 355 /* allocate the missing radix levels, if any */ 356 for (idx = 0; idx != height; idx++) { 357 temp[idx] = malloc(sizeof(*node), M_RADIX, 358 root->gfp_mask | M_ZERO); 359 if (temp[idx] == NULL) { 360 while (idx--) 361 free(temp[idx], M_RADIX); 362 radix_tree_clean_root_node(root); 363 return (-ENOMEM); 364 } 365 } 366 367 /* setup new radix levels, if any */ 368 for ( ; height != 0; height--) { 369 idx = radix_pos(index, height); 370 node->slots[idx] = temp[height - 1]; 371 node->count++; 372 node = node->slots[idx]; 373 } 374 375 /* 376 * Insert and adjust count if the item does not already exist. 377 */ 378 idx = radix_pos(index, 0); 379 /* swap */ 380 pitem = node->slots[idx]; 381 node->slots[idx] = *ppitem; 382 *ppitem = pitem; 383 384 if (pitem == NULL) 385 node->count++; 386 return (0); 387 } 388