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 /* check if the radix tree is getting too big */ 210 if (root->height == RADIX_TREE_MAX_HEIGHT) { 211 radix_tree_clean_root_node(root); 212 return (-E2BIG); 213 } 214 215 /* 216 * If the root radix level is not empty, we need to 217 * allocate a new radix level: 218 */ 219 if (node->count != 0) { 220 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 221 if (node == NULL) { 222 /* 223 * Freeing the already allocated radix 224 * levels, if any, will be handled by 225 * the radix_tree_delete() function. 226 * This code path can only happen when 227 * the tree is not empty. 228 */ 229 return (-ENOMEM); 230 } 231 node->slots[0] = root->rnode; 232 node->count++; 233 root->rnode = node; 234 } 235 root->height++; 236 } 237 238 /* get radix tree height index */ 239 height = root->height - 1; 240 241 /* walk down the tree until the first missing node, if any */ 242 for ( ; height != 0; height--) { 243 idx = radix_pos(index, height); 244 if (node->slots[idx] == NULL) 245 break; 246 node = node->slots[idx]; 247 } 248 249 /* allocate the missing radix levels, if any */ 250 for (idx = 0; idx != height; idx++) { 251 temp[idx] = malloc(sizeof(*node), M_RADIX, 252 root->gfp_mask | M_ZERO); 253 if (temp[idx] == NULL) { 254 while (idx--) 255 free(temp[idx], M_RADIX); 256 radix_tree_clean_root_node(root); 257 return (-ENOMEM); 258 } 259 } 260 261 /* setup new radix levels, if any */ 262 for ( ; height != 0; height--) { 263 idx = radix_pos(index, height); 264 node->slots[idx] = temp[height - 1]; 265 node->count++; 266 node = node->slots[idx]; 267 } 268 269 /* 270 * Insert and adjust count if the item does not already exist. 271 */ 272 idx = radix_pos(index, 0); 273 if (node->slots[idx]) 274 return (-EEXIST); 275 node->slots[idx] = item; 276 node->count++; 277 278 return (0); 279 } 280 281 int 282 radix_tree_store(struct radix_tree_root *root, unsigned long index, void **ppitem) 283 { 284 struct radix_tree_node *node; 285 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1]; 286 void *pitem; 287 int height; 288 int idx; 289 290 /* 291 * Inserting a NULL item means delete it. The old pointer is 292 * stored at the location pointed to by "ppitem". 293 */ 294 if (*ppitem == NULL) { 295 *ppitem = radix_tree_delete(root, index); 296 return (0); 297 } 298 299 /* get root node, if any */ 300 node = root->rnode; 301 302 /* allocate root node, if any */ 303 if (node == NULL) { 304 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 305 if (node == NULL) 306 return (-ENOMEM); 307 root->rnode = node; 308 root->height++; 309 } 310 311 /* expand radix tree as needed */ 312 while (radix_max(root) < index) { 313 /* check if the radix tree is getting too big */ 314 if (root->height == RADIX_TREE_MAX_HEIGHT) { 315 radix_tree_clean_root_node(root); 316 return (-E2BIG); 317 } 318 319 /* 320 * If the root radix level is not empty, we need to 321 * allocate a new radix level: 322 */ 323 if (node->count != 0) { 324 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 325 if (node == NULL) { 326 /* 327 * Freeing the already allocated radix 328 * levels, if any, will be handled by 329 * the radix_tree_delete() function. 330 * This code path can only happen when 331 * the tree is not empty. 332 */ 333 return (-ENOMEM); 334 } 335 node->slots[0] = root->rnode; 336 node->count++; 337 root->rnode = node; 338 } 339 root->height++; 340 } 341 342 /* get radix tree height index */ 343 height = root->height - 1; 344 345 /* walk down the tree until the first missing node, if any */ 346 for ( ; height != 0; height--) { 347 idx = radix_pos(index, height); 348 if (node->slots[idx] == NULL) 349 break; 350 node = node->slots[idx]; 351 } 352 353 /* allocate the missing radix levels, if any */ 354 for (idx = 0; idx != height; idx++) { 355 temp[idx] = malloc(sizeof(*node), M_RADIX, 356 root->gfp_mask | M_ZERO); 357 if (temp[idx] == NULL) { 358 while (idx--) 359 free(temp[idx], M_RADIX); 360 radix_tree_clean_root_node(root); 361 return (-ENOMEM); 362 } 363 } 364 365 /* setup new radix levels, if any */ 366 for ( ; height != 0; height--) { 367 idx = radix_pos(index, height); 368 node->slots[idx] = temp[height - 1]; 369 node->count++; 370 node = node->slots[idx]; 371 } 372 373 /* 374 * Insert and adjust count if the item does not already exist. 375 */ 376 idx = radix_pos(index, 0); 377 /* swap */ 378 pitem = node->slots[idx]; 379 node->slots[idx] = *ppitem; 380 *ppitem = pitem; 381 382 if (pitem == NULL) 383 node->count++; 384 return (0); 385 } 386