1 /* 2 * Copyright (C) 2001 Momchil Velikov 3 * Portions Copyright (C) 2001 Christoph Hellwig 4 * Copyright (C) 2005 SGI, Christoph Lameter 5 * Copyright (C) 2006 Nick Piggin 6 * 7 * This program is free software; you can redistribute it and/or 8 * modify it under the terms of the GNU General Public License as 9 * published by the Free Software Foundation; either version 2, or (at 10 * your option) any later version. 11 * 12 * This program is distributed in the hope that it will be useful, but 13 * WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 * General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with this program; if not, write to the Free Software 19 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 20 */ 21 22 #include <linux/errno.h> 23 #include <linux/init.h> 24 #include <linux/kernel.h> 25 #include <linux/module.h> 26 #include <linux/radix-tree.h> 27 #include <linux/percpu.h> 28 #include <linux/slab.h> 29 #include <linux/notifier.h> 30 #include <linux/cpu.h> 31 #include <linux/string.h> 32 #include <linux/bitops.h> 33 #include <linux/rcupdate.h> 34 35 36 #ifdef __KERNEL__ 37 #define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) 38 #else 39 #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ 40 #endif 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 height; /* Height from the bottom */ 50 unsigned int count; 51 struct rcu_head rcu_head; 52 void __rcu *slots[RADIX_TREE_MAP_SIZE]; 53 unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]; 54 }; 55 56 struct radix_tree_path { 57 struct radix_tree_node *node; 58 int offset; 59 }; 60 61 #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) 62 #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \ 63 RADIX_TREE_MAP_SHIFT)) 64 65 /* 66 * The height_to_maxindex array needs to be one deeper than the maximum 67 * path as height 0 holds only 1 entry. 68 */ 69 static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly; 70 71 /* 72 * Radix tree node cache. 73 */ 74 static struct kmem_cache *radix_tree_node_cachep; 75 76 /* 77 * Per-cpu pool of preloaded nodes 78 */ 79 struct radix_tree_preload { 80 int nr; 81 struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH]; 82 }; 83 static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, }; 84 85 static inline void *ptr_to_indirect(void *ptr) 86 { 87 return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR); 88 } 89 90 static inline void *indirect_to_ptr(void *ptr) 91 { 92 return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR); 93 } 94 95 static inline gfp_t root_gfp_mask(struct radix_tree_root *root) 96 { 97 return root->gfp_mask & __GFP_BITS_MASK; 98 } 99 100 static inline void tag_set(struct radix_tree_node *node, unsigned int tag, 101 int offset) 102 { 103 __set_bit(offset, node->tags[tag]); 104 } 105 106 static inline void tag_clear(struct radix_tree_node *node, unsigned int tag, 107 int offset) 108 { 109 __clear_bit(offset, node->tags[tag]); 110 } 111 112 static inline int tag_get(struct radix_tree_node *node, unsigned int tag, 113 int offset) 114 { 115 return test_bit(offset, node->tags[tag]); 116 } 117 118 static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag) 119 { 120 root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT)); 121 } 122 123 static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag) 124 { 125 root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT)); 126 } 127 128 static inline void root_tag_clear_all(struct radix_tree_root *root) 129 { 130 root->gfp_mask &= __GFP_BITS_MASK; 131 } 132 133 static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag) 134 { 135 return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT)); 136 } 137 138 /* 139 * Returns 1 if any slot in the node has this tag set. 140 * Otherwise returns 0. 141 */ 142 static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag) 143 { 144 int idx; 145 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { 146 if (node->tags[tag][idx]) 147 return 1; 148 } 149 return 0; 150 } 151 /* 152 * This assumes that the caller has performed appropriate preallocation, and 153 * that the caller has pinned this thread of control to the current CPU. 154 */ 155 static struct radix_tree_node * 156 radix_tree_node_alloc(struct radix_tree_root *root) 157 { 158 struct radix_tree_node *ret = NULL; 159 gfp_t gfp_mask = root_gfp_mask(root); 160 161 if (!(gfp_mask & __GFP_WAIT)) { 162 struct radix_tree_preload *rtp; 163 164 /* 165 * Provided the caller has preloaded here, we will always 166 * succeed in getting a node here (and never reach 167 * kmem_cache_alloc) 168 */ 169 rtp = &__get_cpu_var(radix_tree_preloads); 170 if (rtp->nr) { 171 ret = rtp->nodes[rtp->nr - 1]; 172 rtp->nodes[rtp->nr - 1] = NULL; 173 rtp->nr--; 174 } 175 } 176 if (ret == NULL) 177 ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); 178 179 BUG_ON(radix_tree_is_indirect_ptr(ret)); 180 return ret; 181 } 182 183 static void radix_tree_node_rcu_free(struct rcu_head *head) 184 { 185 struct radix_tree_node *node = 186 container_of(head, struct radix_tree_node, rcu_head); 187 int i; 188 189 /* 190 * must only free zeroed nodes into the slab. radix_tree_shrink 191 * can leave us with a non-NULL entry in the first slot, so clear 192 * that here to make sure. 193 */ 194 for (i = 0; i < RADIX_TREE_MAX_TAGS; i++) 195 tag_clear(node, i, 0); 196 197 node->slots[0] = NULL; 198 node->count = 0; 199 200 kmem_cache_free(radix_tree_node_cachep, node); 201 } 202 203 static inline void 204 radix_tree_node_free(struct radix_tree_node *node) 205 { 206 call_rcu(&node->rcu_head, radix_tree_node_rcu_free); 207 } 208 209 /* 210 * Load up this CPU's radix_tree_node buffer with sufficient objects to 211 * ensure that the addition of a single element in the tree cannot fail. On 212 * success, return zero, with preemption disabled. On error, return -ENOMEM 213 * with preemption not disabled. 214 * 215 * To make use of this facility, the radix tree must be initialised without 216 * __GFP_WAIT being passed to INIT_RADIX_TREE(). 217 */ 218 int radix_tree_preload(gfp_t gfp_mask) 219 { 220 struct radix_tree_preload *rtp; 221 struct radix_tree_node *node; 222 int ret = -ENOMEM; 223 224 preempt_disable(); 225 rtp = &__get_cpu_var(radix_tree_preloads); 226 while (rtp->nr < ARRAY_SIZE(rtp->nodes)) { 227 preempt_enable(); 228 node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); 229 if (node == NULL) 230 goto out; 231 preempt_disable(); 232 rtp = &__get_cpu_var(radix_tree_preloads); 233 if (rtp->nr < ARRAY_SIZE(rtp->nodes)) 234 rtp->nodes[rtp->nr++] = node; 235 else 236 kmem_cache_free(radix_tree_node_cachep, node); 237 } 238 ret = 0; 239 out: 240 return ret; 241 } 242 EXPORT_SYMBOL(radix_tree_preload); 243 244 /* 245 * Return the maximum key which can be store into a 246 * radix tree with height HEIGHT. 247 */ 248 static inline unsigned long radix_tree_maxindex(unsigned int height) 249 { 250 return height_to_maxindex[height]; 251 } 252 253 /* 254 * Extend a radix tree so it can store key @index. 255 */ 256 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) 257 { 258 struct radix_tree_node *node; 259 unsigned int height; 260 int tag; 261 262 /* Figure out what the height should be. */ 263 height = root->height + 1; 264 while (index > radix_tree_maxindex(height)) 265 height++; 266 267 if (root->rnode == NULL) { 268 root->height = height; 269 goto out; 270 } 271 272 do { 273 unsigned int newheight; 274 if (!(node = radix_tree_node_alloc(root))) 275 return -ENOMEM; 276 277 /* Increase the height. */ 278 node->slots[0] = indirect_to_ptr(root->rnode); 279 280 /* Propagate the aggregated tag info into the new root */ 281 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) { 282 if (root_tag_get(root, tag)) 283 tag_set(node, tag, 0); 284 } 285 286 newheight = root->height+1; 287 node->height = newheight; 288 node->count = 1; 289 node = ptr_to_indirect(node); 290 rcu_assign_pointer(root->rnode, node); 291 root->height = newheight; 292 } while (height > root->height); 293 out: 294 return 0; 295 } 296 297 /** 298 * radix_tree_insert - insert into a radix tree 299 * @root: radix tree root 300 * @index: index key 301 * @item: item to insert 302 * 303 * Insert an item into the radix tree at position @index. 304 */ 305 int radix_tree_insert(struct radix_tree_root *root, 306 unsigned long index, void *item) 307 { 308 struct radix_tree_node *node = NULL, *slot; 309 unsigned int height, shift; 310 int offset; 311 int error; 312 313 BUG_ON(radix_tree_is_indirect_ptr(item)); 314 315 /* Make sure the tree is high enough. */ 316 if (index > radix_tree_maxindex(root->height)) { 317 error = radix_tree_extend(root, index); 318 if (error) 319 return error; 320 } 321 322 slot = indirect_to_ptr(root->rnode); 323 324 height = root->height; 325 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 326 327 offset = 0; /* uninitialised var warning */ 328 while (height > 0) { 329 if (slot == NULL) { 330 /* Have to add a child node. */ 331 if (!(slot = radix_tree_node_alloc(root))) 332 return -ENOMEM; 333 slot->height = height; 334 if (node) { 335 rcu_assign_pointer(node->slots[offset], slot); 336 node->count++; 337 } else 338 rcu_assign_pointer(root->rnode, ptr_to_indirect(slot)); 339 } 340 341 /* Go a level down */ 342 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 343 node = slot; 344 slot = node->slots[offset]; 345 shift -= RADIX_TREE_MAP_SHIFT; 346 height--; 347 } 348 349 if (slot != NULL) 350 return -EEXIST; 351 352 if (node) { 353 node->count++; 354 rcu_assign_pointer(node->slots[offset], item); 355 BUG_ON(tag_get(node, 0, offset)); 356 BUG_ON(tag_get(node, 1, offset)); 357 } else { 358 rcu_assign_pointer(root->rnode, item); 359 BUG_ON(root_tag_get(root, 0)); 360 BUG_ON(root_tag_get(root, 1)); 361 } 362 363 return 0; 364 } 365 EXPORT_SYMBOL(radix_tree_insert); 366 367 /* 368 * is_slot == 1 : search for the slot. 369 * is_slot == 0 : search for the node. 370 */ 371 static void *radix_tree_lookup_element(struct radix_tree_root *root, 372 unsigned long index, int is_slot) 373 { 374 unsigned int height, shift; 375 struct radix_tree_node *node, **slot; 376 377 node = rcu_dereference_raw(root->rnode); 378 if (node == NULL) 379 return NULL; 380 381 if (!radix_tree_is_indirect_ptr(node)) { 382 if (index > 0) 383 return NULL; 384 return is_slot ? (void *)&root->rnode : node; 385 } 386 node = indirect_to_ptr(node); 387 388 height = node->height; 389 if (index > radix_tree_maxindex(height)) 390 return NULL; 391 392 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 393 394 do { 395 slot = (struct radix_tree_node **) 396 (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)); 397 node = rcu_dereference_raw(*slot); 398 if (node == NULL) 399 return NULL; 400 401 shift -= RADIX_TREE_MAP_SHIFT; 402 height--; 403 } while (height > 0); 404 405 return is_slot ? (void *)slot : indirect_to_ptr(node); 406 } 407 408 /** 409 * radix_tree_lookup_slot - lookup a slot in a radix tree 410 * @root: radix tree root 411 * @index: index key 412 * 413 * Returns: the slot corresponding to the position @index in the 414 * radix tree @root. This is useful for update-if-exists operations. 415 * 416 * This function can be called under rcu_read_lock iff the slot is not 417 * modified by radix_tree_replace_slot, otherwise it must be called 418 * exclusive from other writers. Any dereference of the slot must be done 419 * using radix_tree_deref_slot. 420 */ 421 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) 422 { 423 return (void **)radix_tree_lookup_element(root, index, 1); 424 } 425 EXPORT_SYMBOL(radix_tree_lookup_slot); 426 427 /** 428 * radix_tree_lookup - perform lookup operation on a radix tree 429 * @root: radix tree root 430 * @index: index key 431 * 432 * Lookup the item at the position @index in the radix tree @root. 433 * 434 * This function can be called under rcu_read_lock, however the caller 435 * must manage lifetimes of leaf nodes (eg. RCU may also be used to free 436 * them safely). No RCU barriers are required to access or modify the 437 * returned item, however. 438 */ 439 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) 440 { 441 return radix_tree_lookup_element(root, index, 0); 442 } 443 EXPORT_SYMBOL(radix_tree_lookup); 444 445 /** 446 * radix_tree_tag_set - set a tag on a radix tree node 447 * @root: radix tree root 448 * @index: index key 449 * @tag: tag index 450 * 451 * Set the search tag (which must be < RADIX_TREE_MAX_TAGS) 452 * corresponding to @index in the radix tree. From 453 * the root all the way down to the leaf node. 454 * 455 * Returns the address of the tagged item. Setting a tag on a not-present 456 * item is a bug. 457 */ 458 void *radix_tree_tag_set(struct radix_tree_root *root, 459 unsigned long index, unsigned int tag) 460 { 461 unsigned int height, shift; 462 struct radix_tree_node *slot; 463 464 height = root->height; 465 BUG_ON(index > radix_tree_maxindex(height)); 466 467 slot = indirect_to_ptr(root->rnode); 468 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 469 470 while (height > 0) { 471 int offset; 472 473 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 474 if (!tag_get(slot, tag, offset)) 475 tag_set(slot, tag, offset); 476 slot = slot->slots[offset]; 477 BUG_ON(slot == NULL); 478 shift -= RADIX_TREE_MAP_SHIFT; 479 height--; 480 } 481 482 /* set the root's tag bit */ 483 if (slot && !root_tag_get(root, tag)) 484 root_tag_set(root, tag); 485 486 return slot; 487 } 488 EXPORT_SYMBOL(radix_tree_tag_set); 489 490 /** 491 * radix_tree_tag_clear - clear a tag on a radix tree node 492 * @root: radix tree root 493 * @index: index key 494 * @tag: tag index 495 * 496 * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS) 497 * corresponding to @index in the radix tree. If 498 * this causes the leaf node to have no tags set then clear the tag in the 499 * next-to-leaf node, etc. 500 * 501 * Returns the address of the tagged item on success, else NULL. ie: 502 * has the same return value and semantics as radix_tree_lookup(). 503 */ 504 void *radix_tree_tag_clear(struct radix_tree_root *root, 505 unsigned long index, unsigned int tag) 506 { 507 /* 508 * The radix tree path needs to be one longer than the maximum path 509 * since the "list" is null terminated. 510 */ 511 struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path; 512 struct radix_tree_node *slot = NULL; 513 unsigned int height, shift; 514 515 height = root->height; 516 if (index > radix_tree_maxindex(height)) 517 goto out; 518 519 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 520 pathp->node = NULL; 521 slot = indirect_to_ptr(root->rnode); 522 523 while (height > 0) { 524 int offset; 525 526 if (slot == NULL) 527 goto out; 528 529 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 530 pathp[1].offset = offset; 531 pathp[1].node = slot; 532 slot = slot->slots[offset]; 533 pathp++; 534 shift -= RADIX_TREE_MAP_SHIFT; 535 height--; 536 } 537 538 if (slot == NULL) 539 goto out; 540 541 while (pathp->node) { 542 if (!tag_get(pathp->node, tag, pathp->offset)) 543 goto out; 544 tag_clear(pathp->node, tag, pathp->offset); 545 if (any_tag_set(pathp->node, tag)) 546 goto out; 547 pathp--; 548 } 549 550 /* clear the root's tag bit */ 551 if (root_tag_get(root, tag)) 552 root_tag_clear(root, tag); 553 554 out: 555 return slot; 556 } 557 EXPORT_SYMBOL(radix_tree_tag_clear); 558 559 /** 560 * radix_tree_tag_get - get a tag on a radix tree node 561 * @root: radix tree root 562 * @index: index key 563 * @tag: tag index (< RADIX_TREE_MAX_TAGS) 564 * 565 * Return values: 566 * 567 * 0: tag not present or not set 568 * 1: tag set 569 * 570 * Note that the return value of this function may not be relied on, even if 571 * the RCU lock is held, unless tag modification and node deletion are excluded 572 * from concurrency. 573 */ 574 int radix_tree_tag_get(struct radix_tree_root *root, 575 unsigned long index, unsigned int tag) 576 { 577 unsigned int height, shift; 578 struct radix_tree_node *node; 579 580 /* check the root's tag bit */ 581 if (!root_tag_get(root, tag)) 582 return 0; 583 584 node = rcu_dereference_raw(root->rnode); 585 if (node == NULL) 586 return 0; 587 588 if (!radix_tree_is_indirect_ptr(node)) 589 return (index == 0); 590 node = indirect_to_ptr(node); 591 592 height = node->height; 593 if (index > radix_tree_maxindex(height)) 594 return 0; 595 596 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 597 598 for ( ; ; ) { 599 int offset; 600 601 if (node == NULL) 602 return 0; 603 604 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 605 if (!tag_get(node, tag, offset)) 606 return 0; 607 if (height == 1) 608 return 1; 609 node = rcu_dereference_raw(node->slots[offset]); 610 shift -= RADIX_TREE_MAP_SHIFT; 611 height--; 612 } 613 } 614 EXPORT_SYMBOL(radix_tree_tag_get); 615 616 /** 617 * radix_tree_range_tag_if_tagged - for each item in given range set given 618 * tag if item has another tag set 619 * @root: radix tree root 620 * @first_indexp: pointer to a starting index of a range to scan 621 * @last_index: last index of a range to scan 622 * @nr_to_tag: maximum number items to tag 623 * @iftag: tag index to test 624 * @settag: tag index to set if tested tag is set 625 * 626 * This function scans range of radix tree from first_index to last_index 627 * (inclusive). For each item in the range if iftag is set, the function sets 628 * also settag. The function stops either after tagging nr_to_tag items or 629 * after reaching last_index. 630 * 631 * The tags must be set from the leaf level only and propagated back up the 632 * path to the root. We must do this so that we resolve the full path before 633 * setting any tags on intermediate nodes. If we set tags as we descend, then 634 * we can get to the leaf node and find that the index that has the iftag 635 * set is outside the range we are scanning. This reults in dangling tags and 636 * can lead to problems with later tag operations (e.g. livelocks on lookups). 637 * 638 * The function returns number of leaves where the tag was set and sets 639 * *first_indexp to the first unscanned index. 640 * WARNING! *first_indexp can wrap if last_index is ULONG_MAX. Caller must 641 * be prepared to handle that. 642 */ 643 unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, 644 unsigned long *first_indexp, unsigned long last_index, 645 unsigned long nr_to_tag, 646 unsigned int iftag, unsigned int settag) 647 { 648 unsigned int height = root->height; 649 struct radix_tree_path path[height]; 650 struct radix_tree_path *pathp = path; 651 struct radix_tree_node *slot; 652 unsigned int shift; 653 unsigned long tagged = 0; 654 unsigned long index = *first_indexp; 655 656 last_index = min(last_index, radix_tree_maxindex(height)); 657 if (index > last_index) 658 return 0; 659 if (!nr_to_tag) 660 return 0; 661 if (!root_tag_get(root, iftag)) { 662 *first_indexp = last_index + 1; 663 return 0; 664 } 665 if (height == 0) { 666 *first_indexp = last_index + 1; 667 root_tag_set(root, settag); 668 return 1; 669 } 670 671 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 672 slot = indirect_to_ptr(root->rnode); 673 674 /* 675 * we fill the path from (root->height - 2) to 0, leaving the index at 676 * (root->height - 1) as a terminator. Zero the node in the terminator 677 * so that we can use this to end walk loops back up the path. 678 */ 679 path[height - 1].node = NULL; 680 681 for (;;) { 682 int offset; 683 684 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 685 if (!slot->slots[offset]) 686 goto next; 687 if (!tag_get(slot, iftag, offset)) 688 goto next; 689 if (height > 1) { 690 /* Go down one level */ 691 height--; 692 shift -= RADIX_TREE_MAP_SHIFT; 693 path[height - 1].node = slot; 694 path[height - 1].offset = offset; 695 slot = slot->slots[offset]; 696 continue; 697 } 698 699 /* tag the leaf */ 700 tagged++; 701 tag_set(slot, settag, offset); 702 703 /* walk back up the path tagging interior nodes */ 704 pathp = &path[0]; 705 while (pathp->node) { 706 /* stop if we find a node with the tag already set */ 707 if (tag_get(pathp->node, settag, pathp->offset)) 708 break; 709 tag_set(pathp->node, settag, pathp->offset); 710 pathp++; 711 } 712 713 next: 714 /* Go to next item at level determined by 'shift' */ 715 index = ((index >> shift) + 1) << shift; 716 /* Overflow can happen when last_index is ~0UL... */ 717 if (index > last_index || !index) 718 break; 719 if (tagged >= nr_to_tag) 720 break; 721 while (((index >> shift) & RADIX_TREE_MAP_MASK) == 0) { 722 /* 723 * We've fully scanned this node. Go up. Because 724 * last_index is guaranteed to be in the tree, what 725 * we do below cannot wander astray. 726 */ 727 slot = path[height - 1].node; 728 height++; 729 shift += RADIX_TREE_MAP_SHIFT; 730 } 731 } 732 /* 733 * We need not to tag the root tag if there is no tag which is set with 734 * settag within the range from *first_indexp to last_index. 735 */ 736 if (tagged > 0) 737 root_tag_set(root, settag); 738 *first_indexp = index; 739 740 return tagged; 741 } 742 EXPORT_SYMBOL(radix_tree_range_tag_if_tagged); 743 744 745 /** 746 * radix_tree_next_hole - find the next hole (not-present entry) 747 * @root: tree root 748 * @index: index key 749 * @max_scan: maximum range to search 750 * 751 * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest 752 * indexed hole. 753 * 754 * Returns: the index of the hole if found, otherwise returns an index 755 * outside of the set specified (in which case 'return - index >= max_scan' 756 * will be true). In rare cases of index wrap-around, 0 will be returned. 757 * 758 * radix_tree_next_hole may be called under rcu_read_lock. However, like 759 * radix_tree_gang_lookup, this will not atomically search a snapshot of 760 * the tree at a single point in time. For example, if a hole is created 761 * at index 5, then subsequently a hole is created at index 10, 762 * radix_tree_next_hole covering both indexes may return 10 if called 763 * under rcu_read_lock. 764 */ 765 unsigned long radix_tree_next_hole(struct radix_tree_root *root, 766 unsigned long index, unsigned long max_scan) 767 { 768 unsigned long i; 769 770 for (i = 0; i < max_scan; i++) { 771 if (!radix_tree_lookup(root, index)) 772 break; 773 index++; 774 if (index == 0) 775 break; 776 } 777 778 return index; 779 } 780 EXPORT_SYMBOL(radix_tree_next_hole); 781 782 /** 783 * radix_tree_prev_hole - find the prev hole (not-present entry) 784 * @root: tree root 785 * @index: index key 786 * @max_scan: maximum range to search 787 * 788 * Search backwards in the range [max(index-max_scan+1, 0), index] 789 * for the first hole. 790 * 791 * Returns: the index of the hole if found, otherwise returns an index 792 * outside of the set specified (in which case 'index - return >= max_scan' 793 * will be true). In rare cases of wrap-around, ULONG_MAX will be returned. 794 * 795 * radix_tree_next_hole may be called under rcu_read_lock. However, like 796 * radix_tree_gang_lookup, this will not atomically search a snapshot of 797 * the tree at a single point in time. For example, if a hole is created 798 * at index 10, then subsequently a hole is created at index 5, 799 * radix_tree_prev_hole covering both indexes may return 5 if called under 800 * rcu_read_lock. 801 */ 802 unsigned long radix_tree_prev_hole(struct radix_tree_root *root, 803 unsigned long index, unsigned long max_scan) 804 { 805 unsigned long i; 806 807 for (i = 0; i < max_scan; i++) { 808 if (!radix_tree_lookup(root, index)) 809 break; 810 index--; 811 if (index == ULONG_MAX) 812 break; 813 } 814 815 return index; 816 } 817 EXPORT_SYMBOL(radix_tree_prev_hole); 818 819 static unsigned int 820 __lookup(struct radix_tree_node *slot, void ***results, unsigned long *indices, 821 unsigned long index, unsigned int max_items, unsigned long *next_index) 822 { 823 unsigned int nr_found = 0; 824 unsigned int shift, height; 825 unsigned long i; 826 827 height = slot->height; 828 if (height == 0) 829 goto out; 830 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 831 832 for ( ; height > 1; height--) { 833 i = (index >> shift) & RADIX_TREE_MAP_MASK; 834 for (;;) { 835 if (slot->slots[i] != NULL) 836 break; 837 index &= ~((1UL << shift) - 1); 838 index += 1UL << shift; 839 if (index == 0) 840 goto out; /* 32-bit wraparound */ 841 i++; 842 if (i == RADIX_TREE_MAP_SIZE) 843 goto out; 844 } 845 846 shift -= RADIX_TREE_MAP_SHIFT; 847 slot = rcu_dereference_raw(slot->slots[i]); 848 if (slot == NULL) 849 goto out; 850 } 851 852 /* Bottom level: grab some items */ 853 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) { 854 if (slot->slots[i]) { 855 results[nr_found] = &(slot->slots[i]); 856 if (indices) 857 indices[nr_found] = index; 858 if (++nr_found == max_items) { 859 index++; 860 goto out; 861 } 862 } 863 index++; 864 } 865 out: 866 *next_index = index; 867 return nr_found; 868 } 869 870 /** 871 * radix_tree_gang_lookup - perform multiple lookup on a radix tree 872 * @root: radix tree root 873 * @results: where the results of the lookup are placed 874 * @first_index: start the lookup from this key 875 * @max_items: place up to this many items at *results 876 * 877 * Performs an index-ascending scan of the tree for present items. Places 878 * them at *@results and returns the number of items which were placed at 879 * *@results. 880 * 881 * The implementation is naive. 882 * 883 * Like radix_tree_lookup, radix_tree_gang_lookup may be called under 884 * rcu_read_lock. In this case, rather than the returned results being 885 * an atomic snapshot of the tree at a single point in time, the semantics 886 * of an RCU protected gang lookup are as though multiple radix_tree_lookups 887 * have been issued in individual locks, and results stored in 'results'. 888 */ 889 unsigned int 890 radix_tree_gang_lookup(struct radix_tree_root *root, void **results, 891 unsigned long first_index, unsigned int max_items) 892 { 893 unsigned long max_index; 894 struct radix_tree_node *node; 895 unsigned long cur_index = first_index; 896 unsigned int ret; 897 898 node = rcu_dereference_raw(root->rnode); 899 if (!node) 900 return 0; 901 902 if (!radix_tree_is_indirect_ptr(node)) { 903 if (first_index > 0) 904 return 0; 905 results[0] = node; 906 return 1; 907 } 908 node = indirect_to_ptr(node); 909 910 max_index = radix_tree_maxindex(node->height); 911 912 ret = 0; 913 while (ret < max_items) { 914 unsigned int nr_found, slots_found, i; 915 unsigned long next_index; /* Index of next search */ 916 917 if (cur_index > max_index) 918 break; 919 slots_found = __lookup(node, (void ***)results + ret, NULL, 920 cur_index, max_items - ret, &next_index); 921 nr_found = 0; 922 for (i = 0; i < slots_found; i++) { 923 struct radix_tree_node *slot; 924 slot = *(((void ***)results)[ret + i]); 925 if (!slot) 926 continue; 927 results[ret + nr_found] = 928 indirect_to_ptr(rcu_dereference_raw(slot)); 929 nr_found++; 930 } 931 ret += nr_found; 932 if (next_index == 0) 933 break; 934 cur_index = next_index; 935 } 936 937 return ret; 938 } 939 EXPORT_SYMBOL(radix_tree_gang_lookup); 940 941 /** 942 * radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree 943 * @root: radix tree root 944 * @results: where the results of the lookup are placed 945 * @indices: where their indices should be placed (but usually NULL) 946 * @first_index: start the lookup from this key 947 * @max_items: place up to this many items at *results 948 * 949 * Performs an index-ascending scan of the tree for present items. Places 950 * their slots at *@results and returns the number of items which were 951 * placed at *@results. 952 * 953 * The implementation is naive. 954 * 955 * Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must 956 * be dereferenced with radix_tree_deref_slot, and if using only RCU 957 * protection, radix_tree_deref_slot may fail requiring a retry. 958 */ 959 unsigned int 960 radix_tree_gang_lookup_slot(struct radix_tree_root *root, 961 void ***results, unsigned long *indices, 962 unsigned long first_index, unsigned int max_items) 963 { 964 unsigned long max_index; 965 struct radix_tree_node *node; 966 unsigned long cur_index = first_index; 967 unsigned int ret; 968 969 node = rcu_dereference_raw(root->rnode); 970 if (!node) 971 return 0; 972 973 if (!radix_tree_is_indirect_ptr(node)) { 974 if (first_index > 0) 975 return 0; 976 results[0] = (void **)&root->rnode; 977 if (indices) 978 indices[0] = 0; 979 return 1; 980 } 981 node = indirect_to_ptr(node); 982 983 max_index = radix_tree_maxindex(node->height); 984 985 ret = 0; 986 while (ret < max_items) { 987 unsigned int slots_found; 988 unsigned long next_index; /* Index of next search */ 989 990 if (cur_index > max_index) 991 break; 992 slots_found = __lookup(node, results + ret, 993 indices ? indices + ret : NULL, 994 cur_index, max_items - ret, &next_index); 995 ret += slots_found; 996 if (next_index == 0) 997 break; 998 cur_index = next_index; 999 } 1000 1001 return ret; 1002 } 1003 EXPORT_SYMBOL(radix_tree_gang_lookup_slot); 1004 1005 /* 1006 * FIXME: the two tag_get()s here should use find_next_bit() instead of 1007 * open-coding the search. 1008 */ 1009 static unsigned int 1010 __lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index, 1011 unsigned int max_items, unsigned long *next_index, unsigned int tag) 1012 { 1013 unsigned int nr_found = 0; 1014 unsigned int shift, height; 1015 1016 height = slot->height; 1017 if (height == 0) 1018 goto out; 1019 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 1020 1021 while (height > 0) { 1022 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ; 1023 1024 for (;;) { 1025 if (tag_get(slot, tag, i)) 1026 break; 1027 index &= ~((1UL << shift) - 1); 1028 index += 1UL << shift; 1029 if (index == 0) 1030 goto out; /* 32-bit wraparound */ 1031 i++; 1032 if (i == RADIX_TREE_MAP_SIZE) 1033 goto out; 1034 } 1035 height--; 1036 if (height == 0) { /* Bottom level: grab some items */ 1037 unsigned long j = index & RADIX_TREE_MAP_MASK; 1038 1039 for ( ; j < RADIX_TREE_MAP_SIZE; j++) { 1040 index++; 1041 if (!tag_get(slot, tag, j)) 1042 continue; 1043 /* 1044 * Even though the tag was found set, we need to 1045 * recheck that we have a non-NULL node, because 1046 * if this lookup is lockless, it may have been 1047 * subsequently deleted. 1048 * 1049 * Similar care must be taken in any place that 1050 * lookup ->slots[x] without a lock (ie. can't 1051 * rely on its value remaining the same). 1052 */ 1053 if (slot->slots[j]) { 1054 results[nr_found++] = &(slot->slots[j]); 1055 if (nr_found == max_items) 1056 goto out; 1057 } 1058 } 1059 } 1060 shift -= RADIX_TREE_MAP_SHIFT; 1061 slot = rcu_dereference_raw(slot->slots[i]); 1062 if (slot == NULL) 1063 break; 1064 } 1065 out: 1066 *next_index = index; 1067 return nr_found; 1068 } 1069 1070 /** 1071 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree 1072 * based on a tag 1073 * @root: radix tree root 1074 * @results: where the results of the lookup are placed 1075 * @first_index: start the lookup from this key 1076 * @max_items: place up to this many items at *results 1077 * @tag: the tag index (< RADIX_TREE_MAX_TAGS) 1078 * 1079 * Performs an index-ascending scan of the tree for present items which 1080 * have the tag indexed by @tag set. Places the items at *@results and 1081 * returns the number of items which were placed at *@results. 1082 */ 1083 unsigned int 1084 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, 1085 unsigned long first_index, unsigned int max_items, 1086 unsigned int tag) 1087 { 1088 struct radix_tree_node *node; 1089 unsigned long max_index; 1090 unsigned long cur_index = first_index; 1091 unsigned int ret; 1092 1093 /* check the root's tag bit */ 1094 if (!root_tag_get(root, tag)) 1095 return 0; 1096 1097 node = rcu_dereference_raw(root->rnode); 1098 if (!node) 1099 return 0; 1100 1101 if (!radix_tree_is_indirect_ptr(node)) { 1102 if (first_index > 0) 1103 return 0; 1104 results[0] = node; 1105 return 1; 1106 } 1107 node = indirect_to_ptr(node); 1108 1109 max_index = radix_tree_maxindex(node->height); 1110 1111 ret = 0; 1112 while (ret < max_items) { 1113 unsigned int nr_found, slots_found, i; 1114 unsigned long next_index; /* Index of next search */ 1115 1116 if (cur_index > max_index) 1117 break; 1118 slots_found = __lookup_tag(node, (void ***)results + ret, 1119 cur_index, max_items - ret, &next_index, tag); 1120 nr_found = 0; 1121 for (i = 0; i < slots_found; i++) { 1122 struct radix_tree_node *slot; 1123 slot = *(((void ***)results)[ret + i]); 1124 if (!slot) 1125 continue; 1126 results[ret + nr_found] = 1127 indirect_to_ptr(rcu_dereference_raw(slot)); 1128 nr_found++; 1129 } 1130 ret += nr_found; 1131 if (next_index == 0) 1132 break; 1133 cur_index = next_index; 1134 } 1135 1136 return ret; 1137 } 1138 EXPORT_SYMBOL(radix_tree_gang_lookup_tag); 1139 1140 /** 1141 * radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a 1142 * radix tree based on a tag 1143 * @root: radix tree root 1144 * @results: where the results of the lookup are placed 1145 * @first_index: start the lookup from this key 1146 * @max_items: place up to this many items at *results 1147 * @tag: the tag index (< RADIX_TREE_MAX_TAGS) 1148 * 1149 * Performs an index-ascending scan of the tree for present items which 1150 * have the tag indexed by @tag set. Places the slots at *@results and 1151 * returns the number of slots which were placed at *@results. 1152 */ 1153 unsigned int 1154 radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results, 1155 unsigned long first_index, unsigned int max_items, 1156 unsigned int tag) 1157 { 1158 struct radix_tree_node *node; 1159 unsigned long max_index; 1160 unsigned long cur_index = first_index; 1161 unsigned int ret; 1162 1163 /* check the root's tag bit */ 1164 if (!root_tag_get(root, tag)) 1165 return 0; 1166 1167 node = rcu_dereference_raw(root->rnode); 1168 if (!node) 1169 return 0; 1170 1171 if (!radix_tree_is_indirect_ptr(node)) { 1172 if (first_index > 0) 1173 return 0; 1174 results[0] = (void **)&root->rnode; 1175 return 1; 1176 } 1177 node = indirect_to_ptr(node); 1178 1179 max_index = radix_tree_maxindex(node->height); 1180 1181 ret = 0; 1182 while (ret < max_items) { 1183 unsigned int slots_found; 1184 unsigned long next_index; /* Index of next search */ 1185 1186 if (cur_index > max_index) 1187 break; 1188 slots_found = __lookup_tag(node, results + ret, 1189 cur_index, max_items - ret, &next_index, tag); 1190 ret += slots_found; 1191 if (next_index == 0) 1192 break; 1193 cur_index = next_index; 1194 } 1195 1196 return ret; 1197 } 1198 EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot); 1199 1200 #if defined(CONFIG_SHMEM) && defined(CONFIG_SWAP) 1201 #include <linux/sched.h> /* for cond_resched() */ 1202 1203 /* 1204 * This linear search is at present only useful to shmem_unuse_inode(). 1205 */ 1206 static unsigned long __locate(struct radix_tree_node *slot, void *item, 1207 unsigned long index, unsigned long *found_index) 1208 { 1209 unsigned int shift, height; 1210 unsigned long i; 1211 1212 height = slot->height; 1213 shift = (height-1) * RADIX_TREE_MAP_SHIFT; 1214 1215 for ( ; height > 1; height--) { 1216 i = (index >> shift) & RADIX_TREE_MAP_MASK; 1217 for (;;) { 1218 if (slot->slots[i] != NULL) 1219 break; 1220 index &= ~((1UL << shift) - 1); 1221 index += 1UL << shift; 1222 if (index == 0) 1223 goto out; /* 32-bit wraparound */ 1224 i++; 1225 if (i == RADIX_TREE_MAP_SIZE) 1226 goto out; 1227 } 1228 1229 shift -= RADIX_TREE_MAP_SHIFT; 1230 slot = rcu_dereference_raw(slot->slots[i]); 1231 if (slot == NULL) 1232 goto out; 1233 } 1234 1235 /* Bottom level: check items */ 1236 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) { 1237 if (slot->slots[i] == item) { 1238 *found_index = index + i; 1239 index = 0; 1240 goto out; 1241 } 1242 } 1243 index += RADIX_TREE_MAP_SIZE; 1244 out: 1245 return index; 1246 } 1247 1248 /** 1249 * radix_tree_locate_item - search through radix tree for item 1250 * @root: radix tree root 1251 * @item: item to be found 1252 * 1253 * Returns index where item was found, or -1 if not found. 1254 * Caller must hold no lock (since this time-consuming function needs 1255 * to be preemptible), and must check afterwards if item is still there. 1256 */ 1257 unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) 1258 { 1259 struct radix_tree_node *node; 1260 unsigned long max_index; 1261 unsigned long cur_index = 0; 1262 unsigned long found_index = -1; 1263 1264 do { 1265 rcu_read_lock(); 1266 node = rcu_dereference_raw(root->rnode); 1267 if (!radix_tree_is_indirect_ptr(node)) { 1268 rcu_read_unlock(); 1269 if (node == item) 1270 found_index = 0; 1271 break; 1272 } 1273 1274 node = indirect_to_ptr(node); 1275 max_index = radix_tree_maxindex(node->height); 1276 if (cur_index > max_index) 1277 break; 1278 1279 cur_index = __locate(node, item, cur_index, &found_index); 1280 rcu_read_unlock(); 1281 cond_resched(); 1282 } while (cur_index != 0 && cur_index <= max_index); 1283 1284 return found_index; 1285 } 1286 #else 1287 unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) 1288 { 1289 return -1; 1290 } 1291 #endif /* CONFIG_SHMEM && CONFIG_SWAP */ 1292 1293 /** 1294 * radix_tree_shrink - shrink height of a radix tree to minimal 1295 * @root radix tree root 1296 */ 1297 static inline void radix_tree_shrink(struct radix_tree_root *root) 1298 { 1299 /* try to shrink tree height */ 1300 while (root->height > 0) { 1301 struct radix_tree_node *to_free = root->rnode; 1302 void *newptr; 1303 1304 BUG_ON(!radix_tree_is_indirect_ptr(to_free)); 1305 to_free = indirect_to_ptr(to_free); 1306 1307 /* 1308 * The candidate node has more than one child, or its child 1309 * is not at the leftmost slot, we cannot shrink. 1310 */ 1311 if (to_free->count != 1) 1312 break; 1313 if (!to_free->slots[0]) 1314 break; 1315 1316 /* 1317 * We don't need rcu_assign_pointer(), since we are simply 1318 * moving the node from one part of the tree to another: if it 1319 * was safe to dereference the old pointer to it 1320 * (to_free->slots[0]), it will be safe to dereference the new 1321 * one (root->rnode) as far as dependent read barriers go. 1322 */ 1323 newptr = to_free->slots[0]; 1324 if (root->height > 1) 1325 newptr = ptr_to_indirect(newptr); 1326 root->rnode = newptr; 1327 root->height--; 1328 1329 /* 1330 * We have a dilemma here. The node's slot[0] must not be 1331 * NULLed in case there are concurrent lookups expecting to 1332 * find the item. However if this was a bottom-level node, 1333 * then it may be subject to the slot pointer being visible 1334 * to callers dereferencing it. If item corresponding to 1335 * slot[0] is subsequently deleted, these callers would expect 1336 * their slot to become empty sooner or later. 1337 * 1338 * For example, lockless pagecache will look up a slot, deref 1339 * the page pointer, and if the page is 0 refcount it means it 1340 * was concurrently deleted from pagecache so try the deref 1341 * again. Fortunately there is already a requirement for logic 1342 * to retry the entire slot lookup -- the indirect pointer 1343 * problem (replacing direct root node with an indirect pointer 1344 * also results in a stale slot). So tag the slot as indirect 1345 * to force callers to retry. 1346 */ 1347 if (root->height == 0) 1348 *((unsigned long *)&to_free->slots[0]) |= 1349 RADIX_TREE_INDIRECT_PTR; 1350 1351 radix_tree_node_free(to_free); 1352 } 1353 } 1354 1355 /** 1356 * radix_tree_delete - delete an item from a radix tree 1357 * @root: radix tree root 1358 * @index: index key 1359 * 1360 * Remove the item at @index from the radix tree rooted at @root. 1361 * 1362 * Returns the address of the deleted item, or NULL if it was not present. 1363 */ 1364 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) 1365 { 1366 /* 1367 * The radix tree path needs to be one longer than the maximum path 1368 * since the "list" is null terminated. 1369 */ 1370 struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path; 1371 struct radix_tree_node *slot = NULL; 1372 struct radix_tree_node *to_free; 1373 unsigned int height, shift; 1374 int tag; 1375 int offset; 1376 1377 height = root->height; 1378 if (index > radix_tree_maxindex(height)) 1379 goto out; 1380 1381 slot = root->rnode; 1382 if (height == 0) { 1383 root_tag_clear_all(root); 1384 root->rnode = NULL; 1385 goto out; 1386 } 1387 slot = indirect_to_ptr(slot); 1388 1389 shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 1390 pathp->node = NULL; 1391 1392 do { 1393 if (slot == NULL) 1394 goto out; 1395 1396 pathp++; 1397 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 1398 pathp->offset = offset; 1399 pathp->node = slot; 1400 slot = slot->slots[offset]; 1401 shift -= RADIX_TREE_MAP_SHIFT; 1402 height--; 1403 } while (height > 0); 1404 1405 if (slot == NULL) 1406 goto out; 1407 1408 /* 1409 * Clear all tags associated with the just-deleted item 1410 */ 1411 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) { 1412 if (tag_get(pathp->node, tag, pathp->offset)) 1413 radix_tree_tag_clear(root, index, tag); 1414 } 1415 1416 to_free = NULL; 1417 /* Now free the nodes we do not need anymore */ 1418 while (pathp->node) { 1419 pathp->node->slots[pathp->offset] = NULL; 1420 pathp->node->count--; 1421 /* 1422 * Queue the node for deferred freeing after the 1423 * last reference to it disappears (set NULL, above). 1424 */ 1425 if (to_free) 1426 radix_tree_node_free(to_free); 1427 1428 if (pathp->node->count) { 1429 if (pathp->node == indirect_to_ptr(root->rnode)) 1430 radix_tree_shrink(root); 1431 goto out; 1432 } 1433 1434 /* Node with zero slots in use so free it */ 1435 to_free = pathp->node; 1436 pathp--; 1437 1438 } 1439 root_tag_clear_all(root); 1440 root->height = 0; 1441 root->rnode = NULL; 1442 if (to_free) 1443 radix_tree_node_free(to_free); 1444 1445 out: 1446 return slot; 1447 } 1448 EXPORT_SYMBOL(radix_tree_delete); 1449 1450 /** 1451 * radix_tree_tagged - test whether any items in the tree are tagged 1452 * @root: radix tree root 1453 * @tag: tag to test 1454 */ 1455 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag) 1456 { 1457 return root_tag_get(root, tag); 1458 } 1459 EXPORT_SYMBOL(radix_tree_tagged); 1460 1461 static void 1462 radix_tree_node_ctor(void *node) 1463 { 1464 memset(node, 0, sizeof(struct radix_tree_node)); 1465 } 1466 1467 static __init unsigned long __maxindex(unsigned int height) 1468 { 1469 unsigned int width = height * RADIX_TREE_MAP_SHIFT; 1470 int shift = RADIX_TREE_INDEX_BITS - width; 1471 1472 if (shift < 0) 1473 return ~0UL; 1474 if (shift >= BITS_PER_LONG) 1475 return 0UL; 1476 return ~0UL >> shift; 1477 } 1478 1479 static __init void radix_tree_init_maxindex(void) 1480 { 1481 unsigned int i; 1482 1483 for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++) 1484 height_to_maxindex[i] = __maxindex(i); 1485 } 1486 1487 static int radix_tree_callback(struct notifier_block *nfb, 1488 unsigned long action, 1489 void *hcpu) 1490 { 1491 int cpu = (long)hcpu; 1492 struct radix_tree_preload *rtp; 1493 1494 /* Free per-cpu pool of perloaded nodes */ 1495 if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) { 1496 rtp = &per_cpu(radix_tree_preloads, cpu); 1497 while (rtp->nr) { 1498 kmem_cache_free(radix_tree_node_cachep, 1499 rtp->nodes[rtp->nr-1]); 1500 rtp->nodes[rtp->nr-1] = NULL; 1501 rtp->nr--; 1502 } 1503 } 1504 return NOTIFY_OK; 1505 } 1506 1507 void __init radix_tree_init(void) 1508 { 1509 radix_tree_node_cachep = kmem_cache_create("radix_tree_node", 1510 sizeof(struct radix_tree_node), 0, 1511 SLAB_PANIC | SLAB_RECLAIM_ACCOUNT, 1512 radix_tree_node_ctor); 1513 radix_tree_init_maxindex(); 1514 hotcpu_notifier(radix_tree_callback, 0); 1515 } 1516