1 /* 2 * Copyright (C) 2001 Momchil Velikov 3 * Portions Copyright (C) 2001 Christoph Hellwig 4 * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com> 5 * 6 * This program is free software; you can redistribute it and/or 7 * modify it under the terms of the GNU General Public License as 8 * published by the Free Software Foundation; either version 2, or (at 9 * your option) any later version. 10 * 11 * This program is distributed in the hope that it will be useful, but 12 * WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 * General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program; if not, write to the Free Software 18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 19 */ 20 21 #include <linux/errno.h> 22 #include <linux/init.h> 23 #include <linux/kernel.h> 24 #include <linux/module.h> 25 #include <linux/radix-tree.h> 26 #include <linux/percpu.h> 27 #include <linux/slab.h> 28 #include <linux/notifier.h> 29 #include <linux/cpu.h> 30 #include <linux/gfp.h> 31 #include <linux/string.h> 32 #include <linux/bitops.h> 33 34 35 #ifdef __KERNEL__ 36 #define RADIX_TREE_MAP_SHIFT 6 37 #else 38 #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ 39 #endif 40 #define RADIX_TREE_TAGS 2 41 42 #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) 43 #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) 44 45 #define RADIX_TREE_TAG_LONGS \ 46 ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG) 47 48 struct radix_tree_node { 49 unsigned int count; 50 void *slots[RADIX_TREE_MAP_SIZE]; 51 unsigned long tags[RADIX_TREE_TAGS][RADIX_TREE_TAG_LONGS]; 52 }; 53 54 struct radix_tree_path { 55 struct radix_tree_node *node; 56 int offset; 57 }; 58 59 #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) 60 #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2) 61 62 static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly; 63 64 /* 65 * Radix tree node cache. 66 */ 67 static kmem_cache_t *radix_tree_node_cachep; 68 69 /* 70 * Per-cpu pool of preloaded nodes 71 */ 72 struct radix_tree_preload { 73 int nr; 74 struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH]; 75 }; 76 DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, }; 77 78 /* 79 * This assumes that the caller has performed appropriate preallocation, and 80 * that the caller has pinned this thread of control to the current CPU. 81 */ 82 static struct radix_tree_node * 83 radix_tree_node_alloc(struct radix_tree_root *root) 84 { 85 struct radix_tree_node *ret; 86 87 ret = kmem_cache_alloc(radix_tree_node_cachep, root->gfp_mask); 88 if (ret == NULL && !(root->gfp_mask & __GFP_WAIT)) { 89 struct radix_tree_preload *rtp; 90 91 rtp = &__get_cpu_var(radix_tree_preloads); 92 if (rtp->nr) { 93 ret = rtp->nodes[rtp->nr - 1]; 94 rtp->nodes[rtp->nr - 1] = NULL; 95 rtp->nr--; 96 } 97 } 98 return ret; 99 } 100 101 static inline void 102 radix_tree_node_free(struct radix_tree_node *node) 103 { 104 kmem_cache_free(radix_tree_node_cachep, node); 105 } 106 107 /* 108 * Load up this CPU's radix_tree_node buffer with sufficient objects to 109 * ensure that the addition of a single element in the tree cannot fail. On 110 * success, return zero, with preemption disabled. On error, return -ENOMEM 111 * with preemption not disabled. 112 */ 113 int radix_tree_preload(gfp_t gfp_mask) 114 { 115 struct radix_tree_preload *rtp; 116 struct radix_tree_node *node; 117 int ret = -ENOMEM; 118 119 preempt_disable(); 120 rtp = &__get_cpu_var(radix_tree_preloads); 121 while (rtp->nr < ARRAY_SIZE(rtp->nodes)) { 122 preempt_enable(); 123 node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); 124 if (node == NULL) 125 goto out; 126 preempt_disable(); 127 rtp = &__get_cpu_var(radix_tree_preloads); 128 if (rtp->nr < ARRAY_SIZE(rtp->nodes)) 129 rtp->nodes[rtp->nr++] = node; 130 else 131 kmem_cache_free(radix_tree_node_cachep, node); 132 } 133 ret = 0; 134 out: 135 return ret; 136 } 137 138 static inline void tag_set(struct radix_tree_node *node, int tag, int offset) 139 { 140 if (!test_bit(offset, &node->tags[tag][0])) 141 __set_bit(offset, &node->tags[tag][0]); 142 } 143 144 static inline void tag_clear(struct radix_tree_node *node, int tag, int offset) 145 { 146 __clear_bit(offset, &node->tags[tag][0]); 147 } 148 149 static inline int tag_get(struct radix_tree_node *node, int tag, int offset) 150 { 151 return test_bit(offset, &node->tags[tag][0]); 152 } 153 154 /* 155 * Return the maximum key which can be store into a 156 * radix tree with height HEIGHT. 157 */ 158 static inline unsigned long radix_tree_maxindex(unsigned int height) 159 { 160 return height_to_maxindex[height]; 161 } 162 163 /* 164 * Extend a radix tree so it can store key @index. 165 */ 166 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) 167 { 168 struct radix_tree_node *node; 169 unsigned int height; 170 char tags[RADIX_TREE_TAGS]; 171 int tag; 172 173 /* Figure out what the height should be. */ 174 height = root->height + 1; 175 while (index > radix_tree_maxindex(height)) 176 height++; 177 178 if (root->rnode == NULL) { 179 root->height = height; 180 goto out; 181 } 182 183 /* 184 * Prepare the tag status of the top-level node for propagation 185 * into the newly-pushed top-level node(s) 186 */ 187 for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { 188 int idx; 189 190 tags[tag] = 0; 191 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { 192 if (root->rnode->tags[tag][idx]) { 193 tags[tag] = 1; 194 break; 195 } 196 } 197 } 198 199 do { 200 if (!(node = radix_tree_node_alloc(root))) 201 return -ENOMEM; 202 203 /* Increase the height. */ 204 node->slots[0] = root->rnode; 205 206 /* Propagate the aggregated tag info into the new root */ 207 for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { 208 if (tags[tag]) 209 tag_set(node, tag, 0); 210 } 211 212 node->count = 1; 213 root->rnode = node; 214 root->height++; 215 } while (height > root->height); 216 out: 217 return 0; 218 } 219 220 /** 221 * radix_tree_insert - insert into a radix tree 222 * @root: radix tree root 223 * @index: index key 224 * @item: item to insert 225 * 226 * Insert an item into the radix tree at position @index. 227 */ 228 int radix_tree_insert(struct radix_tree_root *root, 229 unsigned long index, void *item) 230 { 231 struct radix_tree_node *node = NULL, *slot; 232 unsigned int height, shift; 233 int offset; 234 int error; 235 236 /* Make sure the tree is high enough. */ 237 if ((!index && !root->rnode) || 238 index > radix_tree_maxindex(root->height)) { 239 error = radix_tree_extend(root, index); 240 if (error) 241 return error; 242 } 243 244 slot = root->rnode; 245 height = root->height; 246 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 247 248 offset = 0; /* uninitialised var warning */ 249 while (height > 0) { 250 if (slot == NULL) { 251 /* Have to add a child node. */ 252 if (!(slot = radix_tree_node_alloc(root))) 253 return -ENOMEM; 254 if (node) { 255 node->slots[offset] = slot; 256 node->count++; 257 } else 258 root->rnode = slot; 259 } 260 261 /* Go a level down */ 262 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 263 node = slot; 264 slot = node->slots[offset]; 265 shift -= RADIX_TREE_MAP_SHIFT; 266 height--; 267 } 268 269 if (slot != NULL) 270 return -EEXIST; 271 272 if (node) { 273 node->count++; 274 node->slots[offset] = item; 275 BUG_ON(tag_get(node, 0, offset)); 276 BUG_ON(tag_get(node, 1, offset)); 277 } else 278 root->rnode = item; 279 280 return 0; 281 } 282 EXPORT_SYMBOL(radix_tree_insert); 283 284 /** 285 * radix_tree_lookup - perform lookup operation on a radix tree 286 * @root: radix tree root 287 * @index: index key 288 * 289 * Lookup the item at the position @index in the radix tree @root. 290 */ 291 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) 292 { 293 unsigned int height, shift; 294 struct radix_tree_node *slot; 295 296 height = root->height; 297 if (index > radix_tree_maxindex(height)) 298 return NULL; 299 300 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 301 slot = root->rnode; 302 303 while (height > 0) { 304 if (slot == NULL) 305 return NULL; 306 307 slot = slot->slots[(index >> shift) & RADIX_TREE_MAP_MASK]; 308 shift -= RADIX_TREE_MAP_SHIFT; 309 height--; 310 } 311 312 return slot; 313 } 314 EXPORT_SYMBOL(radix_tree_lookup); 315 316 /** 317 * radix_tree_tag_set - set a tag on a radix tree node 318 * @root: radix tree root 319 * @index: index key 320 * @tag: tag index 321 * 322 * Set the search tag corresponging to @index in the radix tree. From 323 * the root all the way down to the leaf node. 324 * 325 * Returns the address of the tagged item. Setting a tag on a not-present 326 * item is a bug. 327 */ 328 void *radix_tree_tag_set(struct radix_tree_root *root, 329 unsigned long index, int tag) 330 { 331 unsigned int height, shift; 332 struct radix_tree_node *slot; 333 334 height = root->height; 335 if (index > radix_tree_maxindex(height)) 336 return NULL; 337 338 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 339 slot = root->rnode; 340 341 while (height > 0) { 342 int offset; 343 344 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 345 tag_set(slot, tag, offset); 346 slot = slot->slots[offset]; 347 BUG_ON(slot == NULL); 348 shift -= RADIX_TREE_MAP_SHIFT; 349 height--; 350 } 351 352 return slot; 353 } 354 EXPORT_SYMBOL(radix_tree_tag_set); 355 356 /** 357 * radix_tree_tag_clear - clear a tag on a radix tree node 358 * @root: radix tree root 359 * @index: index key 360 * @tag: tag index 361 * 362 * Clear the search tag corresponging to @index in the radix tree. If 363 * this causes the leaf node to have no tags set then clear the tag in the 364 * next-to-leaf node, etc. 365 * 366 * Returns the address of the tagged item on success, else NULL. ie: 367 * has the same return value and semantics as radix_tree_lookup(). 368 */ 369 void *radix_tree_tag_clear(struct radix_tree_root *root, 370 unsigned long index, int tag) 371 { 372 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; 373 struct radix_tree_node *slot; 374 unsigned int height, shift; 375 void *ret = NULL; 376 377 height = root->height; 378 if (index > radix_tree_maxindex(height)) 379 goto out; 380 381 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 382 pathp->node = NULL; 383 slot = root->rnode; 384 385 while (height > 0) { 386 int offset; 387 388 if (slot == NULL) 389 goto out; 390 391 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 392 pathp[1].offset = offset; 393 pathp[1].node = slot; 394 slot = slot->slots[offset]; 395 pathp++; 396 shift -= RADIX_TREE_MAP_SHIFT; 397 height--; 398 } 399 400 ret = slot; 401 if (ret == NULL) 402 goto out; 403 404 do { 405 int idx; 406 407 tag_clear(pathp->node, tag, pathp->offset); 408 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { 409 if (pathp->node->tags[tag][idx]) 410 goto out; 411 } 412 pathp--; 413 } while (pathp->node); 414 out: 415 return ret; 416 } 417 EXPORT_SYMBOL(radix_tree_tag_clear); 418 419 #ifndef __KERNEL__ /* Only the test harness uses this at present */ 420 /** 421 * radix_tree_tag_get - get a tag on a radix tree node 422 * @root: radix tree root 423 * @index: index key 424 * @tag: tag index 425 * 426 * Return values: 427 * 428 * 0: tag not present 429 * 1: tag present, set 430 * -1: tag present, unset 431 */ 432 int radix_tree_tag_get(struct radix_tree_root *root, 433 unsigned long index, int tag) 434 { 435 unsigned int height, shift; 436 struct radix_tree_node *slot; 437 int saw_unset_tag = 0; 438 439 height = root->height; 440 if (index > radix_tree_maxindex(height)) 441 return 0; 442 443 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 444 slot = root->rnode; 445 446 for ( ; ; ) { 447 int offset; 448 449 if (slot == NULL) 450 return 0; 451 452 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 453 454 /* 455 * This is just a debug check. Later, we can bale as soon as 456 * we see an unset tag. 457 */ 458 if (!tag_get(slot, tag, offset)) 459 saw_unset_tag = 1; 460 if (height == 1) { 461 int ret = tag_get(slot, tag, offset); 462 463 BUG_ON(ret && saw_unset_tag); 464 return ret ? 1 : -1; 465 } 466 slot = slot->slots[offset]; 467 shift -= RADIX_TREE_MAP_SHIFT; 468 height--; 469 } 470 } 471 EXPORT_SYMBOL(radix_tree_tag_get); 472 #endif 473 474 static unsigned int 475 __lookup(struct radix_tree_root *root, void **results, unsigned long index, 476 unsigned int max_items, unsigned long *next_index) 477 { 478 unsigned int nr_found = 0; 479 unsigned int shift, height; 480 struct radix_tree_node *slot; 481 unsigned long i; 482 483 height = root->height; 484 if (height == 0) 485 goto out; 486 487 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 488 slot = root->rnode; 489 490 for ( ; height > 1; height--) { 491 492 for (i = (index >> shift) & RADIX_TREE_MAP_MASK ; 493 i < RADIX_TREE_MAP_SIZE; i++) { 494 if (slot->slots[i] != NULL) 495 break; 496 index &= ~((1UL << shift) - 1); 497 index += 1UL << shift; 498 if (index == 0) 499 goto out; /* 32-bit wraparound */ 500 } 501 if (i == RADIX_TREE_MAP_SIZE) 502 goto out; 503 504 shift -= RADIX_TREE_MAP_SHIFT; 505 slot = slot->slots[i]; 506 } 507 508 /* Bottom level: grab some items */ 509 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) { 510 index++; 511 if (slot->slots[i]) { 512 results[nr_found++] = slot->slots[i]; 513 if (nr_found == max_items) 514 goto out; 515 } 516 } 517 out: 518 *next_index = index; 519 return nr_found; 520 } 521 522 /** 523 * radix_tree_gang_lookup - perform multiple lookup on a radix tree 524 * @root: radix tree root 525 * @results: where the results of the lookup are placed 526 * @first_index: start the lookup from this key 527 * @max_items: place up to this many items at *results 528 * 529 * Performs an index-ascending scan of the tree for present items. Places 530 * them at *@results and returns the number of items which were placed at 531 * *@results. 532 * 533 * The implementation is naive. 534 */ 535 unsigned int 536 radix_tree_gang_lookup(struct radix_tree_root *root, void **results, 537 unsigned long first_index, unsigned int max_items) 538 { 539 const unsigned long max_index = radix_tree_maxindex(root->height); 540 unsigned long cur_index = first_index; 541 unsigned int ret = 0; 542 543 while (ret < max_items) { 544 unsigned int nr_found; 545 unsigned long next_index; /* Index of next search */ 546 547 if (cur_index > max_index) 548 break; 549 nr_found = __lookup(root, results + ret, cur_index, 550 max_items - ret, &next_index); 551 ret += nr_found; 552 if (next_index == 0) 553 break; 554 cur_index = next_index; 555 } 556 return ret; 557 } 558 EXPORT_SYMBOL(radix_tree_gang_lookup); 559 560 /* 561 * FIXME: the two tag_get()s here should use find_next_bit() instead of 562 * open-coding the search. 563 */ 564 static unsigned int 565 __lookup_tag(struct radix_tree_root *root, void **results, unsigned long index, 566 unsigned int max_items, unsigned long *next_index, int tag) 567 { 568 unsigned int nr_found = 0; 569 unsigned int shift; 570 unsigned int height = root->height; 571 struct radix_tree_node *slot; 572 573 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 574 slot = root->rnode; 575 576 while (height > 0) { 577 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK; 578 579 for ( ; i < RADIX_TREE_MAP_SIZE; i++) { 580 if (tag_get(slot, tag, i)) { 581 BUG_ON(slot->slots[i] == NULL); 582 break; 583 } 584 index &= ~((1UL << shift) - 1); 585 index += 1UL << shift; 586 if (index == 0) 587 goto out; /* 32-bit wraparound */ 588 } 589 if (i == RADIX_TREE_MAP_SIZE) 590 goto out; 591 height--; 592 if (height == 0) { /* Bottom level: grab some items */ 593 unsigned long j = index & RADIX_TREE_MAP_MASK; 594 595 for ( ; j < RADIX_TREE_MAP_SIZE; j++) { 596 index++; 597 if (tag_get(slot, tag, j)) { 598 BUG_ON(slot->slots[j] == NULL); 599 results[nr_found++] = slot->slots[j]; 600 if (nr_found == max_items) 601 goto out; 602 } 603 } 604 } 605 shift -= RADIX_TREE_MAP_SHIFT; 606 slot = slot->slots[i]; 607 } 608 out: 609 *next_index = index; 610 return nr_found; 611 } 612 613 /** 614 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree 615 * based on a tag 616 * @root: radix tree root 617 * @results: where the results of the lookup are placed 618 * @first_index: start the lookup from this key 619 * @max_items: place up to this many items at *results 620 * @tag: the tag index 621 * 622 * Performs an index-ascending scan of the tree for present items which 623 * have the tag indexed by @tag set. Places the items at *@results and 624 * returns the number of items which were placed at *@results. 625 */ 626 unsigned int 627 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, 628 unsigned long first_index, unsigned int max_items, int tag) 629 { 630 const unsigned long max_index = radix_tree_maxindex(root->height); 631 unsigned long cur_index = first_index; 632 unsigned int ret = 0; 633 634 while (ret < max_items) { 635 unsigned int nr_found; 636 unsigned long next_index; /* Index of next search */ 637 638 if (cur_index > max_index) 639 break; 640 nr_found = __lookup_tag(root, results + ret, cur_index, 641 max_items - ret, &next_index, tag); 642 ret += nr_found; 643 if (next_index == 0) 644 break; 645 cur_index = next_index; 646 } 647 return ret; 648 } 649 EXPORT_SYMBOL(radix_tree_gang_lookup_tag); 650 651 /** 652 * radix_tree_delete - delete an item from a radix tree 653 * @root: radix tree root 654 * @index: index key 655 * 656 * Remove the item at @index from the radix tree rooted at @root. 657 * 658 * Returns the address of the deleted item, or NULL if it was not present. 659 */ 660 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) 661 { 662 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; 663 struct radix_tree_path *orig_pathp; 664 struct radix_tree_node *slot; 665 unsigned int height, shift; 666 void *ret = NULL; 667 char tags[RADIX_TREE_TAGS]; 668 int nr_cleared_tags; 669 670 height = root->height; 671 if (index > radix_tree_maxindex(height)) 672 goto out; 673 674 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 675 pathp->node = NULL; 676 slot = root->rnode; 677 678 for ( ; height > 0; height--) { 679 int offset; 680 681 if (slot == NULL) 682 goto out; 683 684 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 685 pathp[1].offset = offset; 686 pathp[1].node = slot; 687 slot = slot->slots[offset]; 688 pathp++; 689 shift -= RADIX_TREE_MAP_SHIFT; 690 } 691 692 ret = slot; 693 if (ret == NULL) 694 goto out; 695 696 orig_pathp = pathp; 697 698 /* 699 * Clear all tags associated with the just-deleted item 700 */ 701 memset(tags, 0, sizeof(tags)); 702 do { 703 int tag; 704 705 nr_cleared_tags = RADIX_TREE_TAGS; 706 for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { 707 int idx; 708 709 if (tags[tag]) 710 continue; 711 712 tag_clear(pathp->node, tag, pathp->offset); 713 714 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { 715 if (pathp->node->tags[tag][idx]) { 716 tags[tag] = 1; 717 nr_cleared_tags--; 718 break; 719 } 720 } 721 } 722 pathp--; 723 } while (pathp->node && nr_cleared_tags); 724 725 /* Now free the nodes we do not need anymore */ 726 for (pathp = orig_pathp; pathp->node; pathp--) { 727 pathp->node->slots[pathp->offset] = NULL; 728 if (--pathp->node->count) 729 goto out; 730 731 /* Node with zero slots in use so free it */ 732 radix_tree_node_free(pathp->node); 733 } 734 root->rnode = NULL; 735 root->height = 0; 736 out: 737 return ret; 738 } 739 EXPORT_SYMBOL(radix_tree_delete); 740 741 /** 742 * radix_tree_tagged - test whether any items in the tree are tagged 743 * @root: radix tree root 744 * @tag: tag to test 745 */ 746 int radix_tree_tagged(struct radix_tree_root *root, int tag) 747 { 748 int idx; 749 750 if (!root->rnode) 751 return 0; 752 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { 753 if (root->rnode->tags[tag][idx]) 754 return 1; 755 } 756 return 0; 757 } 758 EXPORT_SYMBOL(radix_tree_tagged); 759 760 static void 761 radix_tree_node_ctor(void *node, kmem_cache_t *cachep, unsigned long flags) 762 { 763 memset(node, 0, sizeof(struct radix_tree_node)); 764 } 765 766 static __init unsigned long __maxindex(unsigned int height) 767 { 768 unsigned int tmp = height * RADIX_TREE_MAP_SHIFT; 769 unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1; 770 771 if (tmp >= RADIX_TREE_INDEX_BITS) 772 index = ~0UL; 773 return index; 774 } 775 776 static __init void radix_tree_init_maxindex(void) 777 { 778 unsigned int i; 779 780 for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++) 781 height_to_maxindex[i] = __maxindex(i); 782 } 783 784 #ifdef CONFIG_HOTPLUG_CPU 785 static int radix_tree_callback(struct notifier_block *nfb, 786 unsigned long action, 787 void *hcpu) 788 { 789 int cpu = (long)hcpu; 790 struct radix_tree_preload *rtp; 791 792 /* Free per-cpu pool of perloaded nodes */ 793 if (action == CPU_DEAD) { 794 rtp = &per_cpu(radix_tree_preloads, cpu); 795 while (rtp->nr) { 796 kmem_cache_free(radix_tree_node_cachep, 797 rtp->nodes[rtp->nr-1]); 798 rtp->nodes[rtp->nr-1] = NULL; 799 rtp->nr--; 800 } 801 } 802 return NOTIFY_OK; 803 } 804 #endif /* CONFIG_HOTPLUG_CPU */ 805 806 void __init radix_tree_init(void) 807 { 808 radix_tree_node_cachep = kmem_cache_create("radix_tree_node", 809 sizeof(struct radix_tree_node), 0, 810 SLAB_PANIC, radix_tree_node_ctor, NULL); 811 radix_tree_init_maxindex(); 812 hotcpu_notifier(radix_tree_callback, 0); 813 } 814