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(const 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 inline int 56 root_tag_get(const struct radix_tree_root *root, unsigned tag) 57 { 58 return (test_bit(tag, root->tags)); 59 } 60 61 static inline void 62 root_tag_set(struct radix_tree_root *root, unsigned tag) 63 { 64 set_bit(tag, root->tags); 65 } 66 67 static inline void 68 root_tag_clear(struct radix_tree_root *root, unsigned tag) 69 { 70 clear_bit(tag, root->tags); 71 } 72 73 static inline int 74 tag_get(const struct radix_tree_node *node, unsigned int tag, int pos) 75 { 76 return (test_bit(pos, node->tags[tag])); 77 } 78 79 static inline void 80 tag_set(struct radix_tree_node *node, unsigned int tag, int pos) 81 { 82 set_bit(pos, node->tags[tag]); 83 } 84 85 static inline void 86 tag_clear(struct radix_tree_node *node, unsigned int tag, int pos) 87 { 88 clear_bit(pos, node->tags[tag]); 89 } 90 91 static inline bool 92 any_tag_set(const struct radix_tree_node *node, unsigned int tag) 93 { 94 unsigned int pos; 95 96 for (pos = 0; pos < RADIX_TREE_TAG_LONGS; pos++) 97 if (node->tags[tag][pos]) 98 return (true); 99 100 return (false); 101 } 102 103 static void 104 node_tag_clear(struct radix_tree_root *root, struct radix_tree_node *stack[], 105 unsigned long index, unsigned int tag) 106 { 107 struct radix_tree_node *node; 108 int height, pos; 109 110 height = 1; 111 node = stack[height]; 112 113 while (node && height <= root->height - 1) { 114 pos = radix_pos(index, height); 115 if (!tag_get(node, tag, pos)) 116 return; 117 118 tag_clear(node, tag, pos); 119 if (any_tag_set(node, tag)) 120 return; 121 122 height++; 123 node = stack[height]; 124 } 125 126 if (root_tag_get(root, tag)) 127 root_tag_clear(root, tag); 128 } 129 130 static void 131 radix_tree_clean_root_node(struct radix_tree_root *root) 132 { 133 /* Check if the root node should be freed */ 134 if (root->rnode->count == 0) { 135 free(root->rnode, M_RADIX); 136 root->rnode = NULL; 137 root->height = 0; 138 } 139 } 140 141 void * 142 radix_tree_lookup(const struct radix_tree_root *root, unsigned long index) 143 { 144 struct radix_tree_node *node; 145 void *item; 146 int height; 147 148 item = NULL; 149 node = root->rnode; 150 height = root->height - 1; 151 if (index > radix_max(root)) 152 goto out; 153 while (height && node) 154 node = node->slots[radix_pos(index, height--)]; 155 if (node) 156 item = node->slots[radix_pos(index, 0)]; 157 158 out: 159 return (item); 160 } 161 162 unsigned int 163 radix_tree_gang_lookup(const struct radix_tree_root *root, void **results, 164 unsigned long first_index, unsigned int max_items) 165 { 166 struct radix_tree_iter iter; 167 void **slot; 168 int count; 169 170 count = 0; 171 if (max_items == 0) 172 return (count); 173 174 radix_tree_for_each_slot(slot, root, &iter, first_index) { 175 results[count] = *slot; 176 if (results[count] == NULL) 177 continue; 178 179 count++; 180 if (count == max_items) 181 break; 182 } 183 184 return (count); 185 } 186 187 unsigned int 188 radix_tree_gang_lookup_tag(const struct radix_tree_root *root, 189 void **results, unsigned long first_index, unsigned int max_items, 190 unsigned int tag) 191 { 192 struct radix_tree_iter iter; 193 void **slot; 194 int count; 195 196 count = 0; 197 if (max_items == 0) 198 return (count); 199 200 radix_tree_for_each_slot_tagged(slot, root, &iter, first_index, tag) { 201 results[count] = *slot; 202 if (results[count] == NULL) 203 continue; 204 205 count++; 206 if (count == max_items) 207 break; 208 } 209 210 return (count); 211 } 212 213 bool 214 radix_tree_iter_find(const struct radix_tree_root *root, 215 struct radix_tree_iter *iter, void ***pppslot, int flags) 216 { 217 struct radix_tree_node *node; 218 unsigned long index = iter->index; 219 unsigned int tag; 220 int height; 221 222 tag = flags & RADIX_TREE_ITER_TAG_MASK; 223 if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag)) 224 return (false); 225 226 restart: 227 node = root->rnode; 228 if (node == NULL) 229 return (false); 230 height = root->height - 1; 231 if (height == -1 || index > radix_max(root)) 232 return (false); 233 do { 234 unsigned long mask = RADIX_TREE_MAP_MASK << (RADIX_TREE_MAP_SHIFT * height); 235 unsigned long step = 1UL << (RADIX_TREE_MAP_SHIFT * height); 236 int pos = radix_pos(index, height); 237 struct radix_tree_node *next; 238 239 /* track last slot */ 240 *pppslot = node->slots + pos; 241 242 next = node->slots[pos]; 243 if (next == NULL || 244 (flags & RADIX_TREE_ITER_TAGGED && 245 !tag_get(next, tag, pos))) { 246 index += step; 247 index &= -step; 248 if ((index & mask) == 0) 249 goto restart; 250 } else { 251 node = next; 252 height--; 253 } 254 } while (height != -1); 255 iter->index = index; 256 return (true); 257 } 258 259 void * 260 radix_tree_delete(struct radix_tree_root *root, unsigned long index) 261 { 262 struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT]; 263 struct radix_tree_node *node; 264 void *item; 265 int height; 266 int idx; 267 int tag; 268 269 item = NULL; 270 node = root->rnode; 271 height = root->height - 1; 272 if (index > radix_max(root)) 273 goto out; 274 /* 275 * Find the node and record the path in stack. 276 */ 277 while (height && node) { 278 stack[height] = node; 279 node = node->slots[radix_pos(index, height--)]; 280 } 281 282 if (node) { 283 idx = radix_pos(index, 0); 284 item = node->slots[idx]; 285 286 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) 287 node_tag_clear(root, stack, index, tag); 288 } 289 290 /* 291 * If we removed something reduce the height of the tree. 292 */ 293 if (item) 294 for (;;) { 295 node->slots[idx] = NULL; 296 node->count--; 297 if (node->count > 0) 298 break; 299 free(node, M_RADIX); 300 if (node == root->rnode) { 301 root->rnode = NULL; 302 root->height = 0; 303 break; 304 } 305 height++; 306 node = stack[height]; 307 idx = radix_pos(index, height); 308 } 309 out: 310 return (item); 311 } 312 313 void 314 radix_tree_iter_delete(struct radix_tree_root *root, 315 struct radix_tree_iter *iter, void **slot) 316 { 317 radix_tree_delete(root, iter->index); 318 } 319 320 int 321 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item) 322 { 323 struct radix_tree_node *node; 324 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1]; 325 int height; 326 int idx; 327 328 /* bail out upon insertion of a NULL item */ 329 if (item == NULL) 330 return (-EINVAL); 331 332 /* get root node, if any */ 333 node = root->rnode; 334 335 /* allocate root node, if any */ 336 if (node == NULL) { 337 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 338 if (node == NULL) 339 return (-ENOMEM); 340 root->rnode = node; 341 root->height++; 342 } 343 344 /* expand radix tree as needed */ 345 while (radix_max(root) < index) { 346 /* check if the radix tree is getting too big */ 347 if (root->height == RADIX_TREE_MAX_HEIGHT) { 348 radix_tree_clean_root_node(root); 349 return (-E2BIG); 350 } 351 352 /* 353 * If the root radix level is not empty, we need to 354 * allocate a new radix level: 355 */ 356 if (node->count != 0) { 357 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 358 if (node == NULL) { 359 /* 360 * Freeing the already allocated radix 361 * levels, if any, will be handled by 362 * the radix_tree_delete() function. 363 * This code path can only happen when 364 * the tree is not empty. 365 */ 366 return (-ENOMEM); 367 } 368 node->slots[0] = root->rnode; 369 node->count++; 370 root->rnode = node; 371 } 372 root->height++; 373 } 374 375 /* get radix tree height index */ 376 height = root->height - 1; 377 378 /* walk down the tree until the first missing node, if any */ 379 for ( ; height != 0; height--) { 380 idx = radix_pos(index, height); 381 if (node->slots[idx] == NULL) 382 break; 383 node = node->slots[idx]; 384 } 385 386 /* allocate the missing radix levels, if any */ 387 for (idx = 0; idx != height; idx++) { 388 temp[idx] = malloc(sizeof(*node), M_RADIX, 389 root->gfp_mask | M_ZERO); 390 if (temp[idx] == NULL) { 391 while (idx--) 392 free(temp[idx], M_RADIX); 393 radix_tree_clean_root_node(root); 394 return (-ENOMEM); 395 } 396 } 397 398 /* setup new radix levels, if any */ 399 for ( ; height != 0; height--) { 400 idx = radix_pos(index, height); 401 node->slots[idx] = temp[height - 1]; 402 node->count++; 403 node = node->slots[idx]; 404 } 405 406 /* 407 * Insert and adjust count if the item does not already exist. 408 */ 409 idx = radix_pos(index, 0); 410 if (node->slots[idx]) 411 return (-EEXIST); 412 node->slots[idx] = item; 413 node->count++; 414 415 return (0); 416 } 417 418 int 419 radix_tree_store(struct radix_tree_root *root, unsigned long index, void **ppitem) 420 { 421 struct radix_tree_node *node; 422 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1]; 423 void *pitem; 424 int height; 425 int idx; 426 427 /* 428 * Inserting a NULL item means delete it. The old pointer is 429 * stored at the location pointed to by "ppitem". 430 */ 431 if (*ppitem == NULL) { 432 *ppitem = radix_tree_delete(root, index); 433 return (0); 434 } 435 436 /* get root node, if any */ 437 node = root->rnode; 438 439 /* allocate root node, if any */ 440 if (node == NULL) { 441 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 442 if (node == NULL) 443 return (-ENOMEM); 444 root->rnode = node; 445 root->height++; 446 } 447 448 /* expand radix tree as needed */ 449 while (radix_max(root) < index) { 450 /* check if the radix tree is getting too big */ 451 if (root->height == RADIX_TREE_MAX_HEIGHT) { 452 radix_tree_clean_root_node(root); 453 return (-E2BIG); 454 } 455 456 /* 457 * If the root radix level is not empty, we need to 458 * allocate a new radix level: 459 */ 460 if (node->count != 0) { 461 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO); 462 if (node == NULL) { 463 /* 464 * Freeing the already allocated radix 465 * levels, if any, will be handled by 466 * the radix_tree_delete() function. 467 * This code path can only happen when 468 * the tree is not empty. 469 */ 470 return (-ENOMEM); 471 } 472 node->slots[0] = root->rnode; 473 node->count++; 474 root->rnode = node; 475 } 476 root->height++; 477 } 478 479 /* get radix tree height index */ 480 height = root->height - 1; 481 482 /* walk down the tree until the first missing node, if any */ 483 for ( ; height != 0; height--) { 484 idx = radix_pos(index, height); 485 if (node->slots[idx] == NULL) 486 break; 487 node = node->slots[idx]; 488 } 489 490 /* allocate the missing radix levels, if any */ 491 for (idx = 0; idx != height; idx++) { 492 temp[idx] = malloc(sizeof(*node), M_RADIX, 493 root->gfp_mask | M_ZERO); 494 if (temp[idx] == NULL) { 495 while (idx--) 496 free(temp[idx], M_RADIX); 497 radix_tree_clean_root_node(root); 498 return (-ENOMEM); 499 } 500 } 501 502 /* setup new radix levels, if any */ 503 for ( ; height != 0; height--) { 504 idx = radix_pos(index, height); 505 node->slots[idx] = temp[height - 1]; 506 node->count++; 507 node = node->slots[idx]; 508 } 509 510 /* 511 * Insert and adjust count if the item does not already exist. 512 */ 513 idx = radix_pos(index, 0); 514 /* swap */ 515 pitem = node->slots[idx]; 516 node->slots[idx] = *ppitem; 517 *ppitem = pitem; 518 519 if (pitem == NULL) 520 node->count++; 521 return (0); 522 } 523 524 void * 525 radix_tree_tag_set(struct radix_tree_root *root, unsigned long index, 526 unsigned int tag) 527 { 528 struct radix_tree_node *node; 529 void *item; 530 int height, pos; 531 532 item = NULL; 533 node = root->rnode; 534 height = root->height - 1; 535 if (index > radix_max(root)) 536 goto out; 537 538 while (height) { 539 KASSERT( 540 node != NULL, 541 ("Node at index %lu does not exist in radix tree %p", 542 index, root)); 543 544 pos = radix_pos(index, height--); 545 node = node->slots[pos]; 546 547 if (!tag_get(node, tag, pos)) 548 tag_set(node, tag, pos); 549 } 550 551 item = node->slots[radix_pos(index, 0)]; 552 553 root_tag_set(root, tag); 554 555 out: 556 return (item); 557 } 558 559 void * 560 radix_tree_tag_clear(struct radix_tree_root *root, 561 unsigned long index, unsigned int tag) 562 { 563 struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT]; 564 struct radix_tree_node *node; 565 void *item; 566 int height; 567 568 item = NULL; 569 node = root->rnode; 570 height = root->height - 1; 571 if (index > radix_max(root)) 572 goto out; 573 574 while (height && node) { 575 stack[height] = node; 576 node = node->slots[radix_pos(index, height--)]; 577 } 578 579 if (node) { 580 item = node->slots[radix_pos(index, 0)]; 581 582 node_tag_clear(root, stack, index, tag); 583 } 584 585 out: 586 return (item); 587 } 588 589 int 590 radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag) 591 { 592 return (root_tag_get(root, tag)); 593 } 594