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