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 #include <sys/param.h> 32 #include <sys/systm.h> 33 #include <sys/malloc.h> 34 #include <sys/kernel.h> 35 #include <sys/sysctl.h> 36 37 #include <linux/slab.h> 38 #include <linux/kernel.h> 39 #include <linux/radix-tree.h> 40 #include <linux/err.h> 41 42 static MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat"); 43 44 static inline unsigned long 45 radix_max(struct radix_tree_root *root) 46 { 47 return ((1UL << (root->height * RADIX_TREE_MAP_SHIFT)) - 1UL); 48 } 49 50 static inline int 51 radix_pos(long id, int height) 52 { 53 return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK; 54 } 55 56 static void 57 radix_tree_clean_root_node(struct radix_tree_root *root) 58 { 59 /* Check if the root node should be freed */ 60 if (root->rnode->count == 0) { 61 free(root->rnode, M_RADIX); 62 root->rnode = NULL; 63 root->height = 0; 64 } 65 } 66 67 void * 68 radix_tree_lookup(struct radix_tree_root *root, unsigned long index) 69 { 70 struct radix_tree_node *node; 71 void *item; 72 int height; 73 74 item = NULL; 75 node = root->rnode; 76 height = root->height - 1; 77 if (index > radix_max(root)) 78 goto out; 79 while (height && node) 80 node = node->slots[radix_pos(index, height--)]; 81 if (node) 82 item = node->slots[radix_pos(index, 0)]; 83 84 out: 85 return (item); 86 } 87 88 bool 89 radix_tree_iter_find(struct radix_tree_root *root, struct radix_tree_iter *iter, 90 void ***pppslot) 91 { 92 struct radix_tree_node *node; 93 unsigned long index = iter->index; 94 int height; 95 96 restart: 97 node = root->rnode; 98 if (node == NULL) 99 return (false); 100 height = root->height - 1; 101 if (height == -1 || index > radix_max(root)) 102 return (false); 103 do { 104 unsigned long mask = RADIX_TREE_MAP_MASK << (RADIX_TREE_MAP_SHIFT * height); 105 unsigned long step = 1UL << (RADIX_TREE_MAP_SHIFT * height); 106 int pos = radix_pos(index, height); 107 struct radix_tree_node *next; 108 109 /* track last slot */ 110 *pppslot = node->slots + pos; 111 112 next = node->slots[pos]; 113 if (next == NULL) { 114 index += step; 115 index &= -step; 116 if ((index & mask) == 0) 117 goto restart; 118 } else { 119 node = next; 120 height--; 121 } 122 } while (height != -1); 123 iter->index = index; 124 return (true); 125 } 126 127 void * 128 radix_tree_delete(struct radix_tree_root *root, unsigned long index) 129 { 130 struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT]; 131 struct radix_tree_node *node; 132 void *item; 133 int height; 134 int idx; 135 136 item = NULL; 137 node = root->rnode; 138 height = root->height - 1; 139 if (index > radix_max(root)) 140 goto out; 141 /* 142 * Find the node and record the path in stack. 143 */ 144 while (height && node) { 145 stack[height] = node; 146 node = node->slots[radix_pos(index, height--)]; 147 } 148 idx = radix_pos(index, 0); 149 if (node) 150 item = node->slots[idx]; 151 /* 152 * If we removed something reduce the height of the tree. 153 */ 154 if (item) 155 for (;;) { 156 node->slots[idx] = NULL; 157 node->count--; 158 if (node->count > 0) 159 break; 160 free(node, M_RADIX); 161 if (node == root->rnode) { 162 root->rnode = NULL; 163 root->height = 0; 164 break; 165 } 166 height++; 167 node = stack[height]; 168 idx = radix_pos(index, height); 169 } 170 out: 171 return (item); 172 } 173 174 void 175 radix_tree_iter_delete(struct radix_tree_root *root, 176 struct radix_tree_iter *iter, void **slot) 177 { 178 radix_tree_delete(root, iter->index); 179 } 180 181 int 182 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item) 183 { 184 struct radix_tree_node *node; 185 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1]; 186 int height; 187 int idx; 188 189 /* bail out upon insertion of a NULL item */ 190 if (item == NULL) 191 return (-EINVAL); 192 193 /* get root node, if any */ 194 node = root->rnode; 195 196 /* allocate root node, if any */ 197 if (node == NULL) { 198 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 199 if (node == NULL) 200 return (-ENOMEM); 201 root->rnode = node; 202 root->height++; 203 } 204 205 /* expand radix tree as needed */ 206 while (radix_max(root) < index) { 207 /* check if the radix tree is getting too big */ 208 if (root->height == RADIX_TREE_MAX_HEIGHT) { 209 radix_tree_clean_root_node(root); 210 return (-E2BIG); 211 } 212 213 /* 214 * If the root radix level is not empty, we need to 215 * allocate a new radix level: 216 */ 217 if (node->count != 0) { 218 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 219 if (node == NULL) { 220 /* 221 * Freeing the already allocated radix 222 * levels, if any, will be handled by 223 * the radix_tree_delete() function. 224 * This code path can only happen when 225 * the tree is not empty. 226 */ 227 return (-ENOMEM); 228 } 229 node->slots[0] = root->rnode; 230 node->count++; 231 root->rnode = node; 232 } 233 root->height++; 234 } 235 236 /* get radix tree height index */ 237 height = root->height - 1; 238 239 /* walk down the tree until the first missing node, if any */ 240 for ( ; height != 0; height--) { 241 idx = radix_pos(index, height); 242 if (node->slots[idx] == NULL) 243 break; 244 node = node->slots[idx]; 245 } 246 247 /* allocate the missing radix levels, if any */ 248 for (idx = 0; idx != height; idx++) { 249 temp[idx] = malloc(sizeof(*node), M_RADIX, 250 root->gfp_mask | M_ZERO); 251 if (temp[idx] == NULL) { 252 while (idx--) 253 free(temp[idx], M_RADIX); 254 radix_tree_clean_root_node(root); 255 return (-ENOMEM); 256 } 257 } 258 259 /* setup new radix levels, if any */ 260 for ( ; height != 0; height--) { 261 idx = radix_pos(index, height); 262 node->slots[idx] = temp[height - 1]; 263 node->count++; 264 node = node->slots[idx]; 265 } 266 267 /* 268 * Insert and adjust count if the item does not already exist. 269 */ 270 idx = radix_pos(index, 0); 271 if (node->slots[idx]) 272 return (-EEXIST); 273 node->slots[idx] = item; 274 node->count++; 275 276 return (0); 277 } 278 279 int 280 radix_tree_store(struct radix_tree_root *root, unsigned long index, void **ppitem) 281 { 282 struct radix_tree_node *node; 283 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1]; 284 void *pitem; 285 int height; 286 int idx; 287 288 /* 289 * Inserting a NULL item means delete it. The old pointer is 290 * stored at the location pointed to by "ppitem". 291 */ 292 if (*ppitem == NULL) { 293 *ppitem = radix_tree_delete(root, index); 294 return (0); 295 } 296 297 /* get root node, if any */ 298 node = root->rnode; 299 300 /* allocate root node, if any */ 301 if (node == NULL) { 302 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 303 if (node == NULL) 304 return (-ENOMEM); 305 root->rnode = node; 306 root->height++; 307 } 308 309 /* expand radix tree as needed */ 310 while (radix_max(root) < index) { 311 /* check if the radix tree is getting too big */ 312 if (root->height == RADIX_TREE_MAX_HEIGHT) { 313 radix_tree_clean_root_node(root); 314 return (-E2BIG); 315 } 316 317 /* 318 * If the root radix level is not empty, we need to 319 * allocate a new radix level: 320 */ 321 if (node->count != 0) { 322 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 323 if (node == NULL) { 324 /* 325 * Freeing the already allocated radix 326 * levels, if any, will be handled by 327 * the radix_tree_delete() function. 328 * This code path can only happen when 329 * the tree is not empty. 330 */ 331 return (-ENOMEM); 332 } 333 node->slots[0] = root->rnode; 334 node->count++; 335 root->rnode = node; 336 } 337 root->height++; 338 } 339 340 /* get radix tree height index */ 341 height = root->height - 1; 342 343 /* walk down the tree until the first missing node, if any */ 344 for ( ; height != 0; height--) { 345 idx = radix_pos(index, height); 346 if (node->slots[idx] == NULL) 347 break; 348 node = node->slots[idx]; 349 } 350 351 /* allocate the missing radix levels, if any */ 352 for (idx = 0; idx != height; idx++) { 353 temp[idx] = malloc(sizeof(*node), M_RADIX, 354 root->gfp_mask | M_ZERO); 355 if (temp[idx] == NULL) { 356 while (idx--) 357 free(temp[idx], M_RADIX); 358 radix_tree_clean_root_node(root); 359 return (-ENOMEM); 360 } 361 } 362 363 /* setup new radix levels, if any */ 364 for ( ; height != 0; height--) { 365 idx = radix_pos(index, height); 366 node->slots[idx] = temp[height - 1]; 367 node->count++; 368 node = node->slots[idx]; 369 } 370 371 /* 372 * Insert and adjust count if the item does not already exist. 373 */ 374 idx = radix_pos(index, 0); 375 /* swap */ 376 pitem = node->slots[idx]; 377 node->slots[idx] = *ppitem; 378 *ppitem = pitem; 379 380 if (pitem == NULL) 381 node->count++; 382 return (0); 383 } 384