linux/lib/radix-tree.c
<<
>>
Prefs
   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
  48struct 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
  56struct 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 */
  69static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;
  70
  71/*
  72 * Radix tree node cache.
  73 */
  74static struct kmem_cache *radix_tree_node_cachep;
  75
  76/*
  77 * Per-cpu pool of preloaded nodes
  78 */
  79struct radix_tree_preload {
  80        int nr;
  81        struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH];
  82};
  83static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
  84
  85static inline void *ptr_to_indirect(void *ptr)
  86{
  87        return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
  88}
  89
  90static inline void *indirect_to_ptr(void *ptr)
  91{
  92        return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
  93}
  94
  95static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
  96{
  97        return root->gfp_mask & __GFP_BITS_MASK;
  98}
  99
 100static 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
 106static 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
 112static 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
 118static 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
 123static 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
 128static inline void root_tag_clear_all(struct radix_tree_root *root)
 129{
 130        root->gfp_mask &= __GFP_BITS_MASK;
 131}
 132
 133static 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 */
 142static 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 */
 155static struct radix_tree_node *
 156radix_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
 183static 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
 203static inline void
 204radix_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 */
 218int 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;
 239out:
 240        return ret;
 241}
 242EXPORT_SYMBOL(radix_tree_preload);
 243
 244/*
 245 *      Return the maximum key which can be store into a
 246 *      radix tree with height HEIGHT.
 247 */
 248static 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 */
 256static 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);
 293out:
 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 */
 305int 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}
 365EXPORT_SYMBOL(radix_tree_insert);
 366
 367/*
 368 * is_slot == 1 : search for the slot.
 369 * is_slot == 0 : search for the node.
 370 */
 371static 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 */
 421void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
 422{
 423        return (void **)radix_tree_lookup_element(root, index, 1);
 424}
 425EXPORT_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 */
 439void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
 440{
 441        return radix_tree_lookup_element(root, index, 0);
 442}
 443EXPORT_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 */
 458void *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}
 488EXPORT_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 */
 504void *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
 554out:
 555        return slot;
 556}
 557EXPORT_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 */
 574int 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        int saw_unset_tag = 0;
 580
 581        /* check the root's tag bit */
 582        if (!root_tag_get(root, tag))
 583                return 0;
 584
 585        node = rcu_dereference_raw(root->rnode);
 586        if (node == NULL)
 587                return 0;
 588
 589        if (!radix_tree_is_indirect_ptr(node))
 590                return (index == 0);
 591        node = indirect_to_ptr(node);
 592
 593        height = node->height;
 594        if (index > radix_tree_maxindex(height))
 595                return 0;
 596
 597        shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 598
 599        for ( ; ; ) {
 600                int offset;
 601
 602                if (node == NULL)
 603                        return 0;
 604
 605                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
 606
 607                /*
 608                 * This is just a debug check.  Later, we can bale as soon as
 609                 * we see an unset tag.
 610                 */
 611                if (!tag_get(node, tag, offset))
 612                        saw_unset_tag = 1;
 613                if (height == 1)
 614                        return !!tag_get(node, tag, offset);
 615                node = rcu_dereference_raw(node->slots[offset]);
 616                shift -= RADIX_TREE_MAP_SHIFT;
 617                height--;
 618        }
 619}
 620EXPORT_SYMBOL(radix_tree_tag_get);
 621
 622/**
 623 * radix_tree_range_tag_if_tagged - for each item in given range set given
 624 *                                 tag if item has another tag set
 625 * @root:               radix tree root
 626 * @first_indexp:       pointer to a starting index of a range to scan
 627 * @last_index:         last index of a range to scan
 628 * @nr_to_tag:          maximum number items to tag
 629 * @iftag:              tag index to test
 630 * @settag:             tag index to set if tested tag is set
 631 *
 632 * This function scans range of radix tree from first_index to last_index
 633 * (inclusive).  For each item in the range if iftag is set, the function sets
 634 * also settag. The function stops either after tagging nr_to_tag items or
 635 * after reaching last_index.
 636 *
 637 * The tags must be set from the leaf level only and propagated back up the
 638 * path to the root. We must do this so that we resolve the full path before
 639 * setting any tags on intermediate nodes. If we set tags as we descend, then
 640 * we can get to the leaf node and find that the index that has the iftag
 641 * set is outside the range we are scanning. This reults in dangling tags and
 642 * can lead to problems with later tag operations (e.g. livelocks on lookups).
 643 *
 644 * The function returns number of leaves where the tag was set and sets
 645 * *first_indexp to the first unscanned index.
 646 * WARNING! *first_indexp can wrap if last_index is ULONG_MAX. Caller must
 647 * be prepared to handle that.
 648 */
 649unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
 650                unsigned long *first_indexp, unsigned long last_index,
 651                unsigned long nr_to_tag,
 652                unsigned int iftag, unsigned int settag)
 653{
 654        unsigned int height = root->height;
 655        struct radix_tree_path path[height];
 656        struct radix_tree_path *pathp = path;
 657        struct radix_tree_node *slot;
 658        unsigned int shift;
 659        unsigned long tagged = 0;
 660        unsigned long index = *first_indexp;
 661
 662        last_index = min(last_index, radix_tree_maxindex(height));
 663        if (index > last_index)
 664                return 0;
 665        if (!nr_to_tag)
 666                return 0;
 667        if (!root_tag_get(root, iftag)) {
 668                *first_indexp = last_index + 1;
 669                return 0;
 670        }
 671        if (height == 0) {
 672                *first_indexp = last_index + 1;
 673                root_tag_set(root, settag);
 674                return 1;
 675        }
 676
 677        shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 678        slot = indirect_to_ptr(root->rnode);
 679
 680        /*
 681         * we fill the path from (root->height - 2) to 0, leaving the index at
 682         * (root->height - 1) as a terminator. Zero the node in the terminator
 683         * so that we can use this to end walk loops back up the path.
 684         */
 685        path[height - 1].node = NULL;
 686
 687        for (;;) {
 688                int offset;
 689
 690                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
 691                if (!slot->slots[offset])
 692                        goto next;
 693                if (!tag_get(slot, iftag, offset))
 694                        goto next;
 695                if (height > 1) {
 696                        /* Go down one level */
 697                        height--;
 698                        shift -= RADIX_TREE_MAP_SHIFT;
 699                        path[height - 1].node = slot;
 700                        path[height - 1].offset = offset;
 701                        slot = slot->slots[offset];
 702                        continue;
 703                }
 704
 705                /* tag the leaf */
 706                tagged++;
 707                tag_set(slot, settag, offset);
 708
 709                /* walk back up the path tagging interior nodes */
 710                pathp = &path[0];
 711                while (pathp->node) {
 712                        /* stop if we find a node with the tag already set */
 713                        if (tag_get(pathp->node, settag, pathp->offset))
 714                                break;
 715                        tag_set(pathp->node, settag, pathp->offset);
 716                        pathp++;
 717                }
 718
 719next:
 720                /* Go to next item at level determined by 'shift' */
 721                index = ((index >> shift) + 1) << shift;
 722                /* Overflow can happen when last_index is ~0UL... */
 723                if (index > last_index || !index)
 724                        break;
 725                if (tagged >= nr_to_tag)
 726                        break;
 727                while (((index >> shift) & RADIX_TREE_MAP_MASK) == 0) {
 728                        /*
 729                         * We've fully scanned this node. Go up. Because
 730                         * last_index is guaranteed to be in the tree, what
 731                         * we do below cannot wander astray.
 732                         */
 733                        slot = path[height - 1].node;
 734                        height++;
 735                        shift += RADIX_TREE_MAP_SHIFT;
 736                }
 737        }
 738        /*
 739         * We need not to tag the root tag if there is no tag which is set with
 740         * settag within the range from *first_indexp to last_index.
 741         */
 742        if (tagged > 0)
 743                root_tag_set(root, settag);
 744        *first_indexp = index;
 745
 746        return tagged;
 747}
 748EXPORT_SYMBOL(radix_tree_range_tag_if_tagged);
 749
 750
 751/**
 752 *      radix_tree_next_hole    -    find the next hole (not-present entry)
 753 *      @root:          tree root
 754 *      @index:         index key
 755 *      @max_scan:      maximum range to search
 756 *
 757 *      Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest
 758 *      indexed hole.
 759 *
 760 *      Returns: the index of the hole if found, otherwise returns an index
 761 *      outside of the set specified (in which case 'return - index >= max_scan'
 762 *      will be true). In rare cases of index wrap-around, 0 will be returned.
 763 *
 764 *      radix_tree_next_hole may be called under rcu_read_lock. However, like
 765 *      radix_tree_gang_lookup, this will not atomically search a snapshot of
 766 *      the tree at a single point in time. For example, if a hole is created
 767 *      at index 5, then subsequently a hole is created at index 10,
 768 *      radix_tree_next_hole covering both indexes may return 10 if called
 769 *      under rcu_read_lock.
 770 */
 771unsigned long radix_tree_next_hole(struct radix_tree_root *root,
 772                                unsigned long index, unsigned long max_scan)
 773{
 774        unsigned long i;
 775
 776        for (i = 0; i < max_scan; i++) {
 777                if (!radix_tree_lookup(root, index))
 778                        break;
 779                index++;
 780                if (index == 0)
 781                        break;
 782        }
 783
 784        return index;
 785}
 786EXPORT_SYMBOL(radix_tree_next_hole);
 787
 788/**
 789 *      radix_tree_prev_hole    -    find the prev hole (not-present entry)
 790 *      @root:          tree root
 791 *      @index:         index key
 792 *      @max_scan:      maximum range to search
 793 *
 794 *      Search backwards in the range [max(index-max_scan+1, 0), index]
 795 *      for the first hole.
 796 *
 797 *      Returns: the index of the hole if found, otherwise returns an index
 798 *      outside of the set specified (in which case 'index - return >= max_scan'
 799 *      will be true). In rare cases of wrap-around, ULONG_MAX will be returned.
 800 *
 801 *      radix_tree_next_hole may be called under rcu_read_lock. However, like
 802 *      radix_tree_gang_lookup, this will not atomically search a snapshot of
 803 *      the tree at a single point in time. For example, if a hole is created
 804 *      at index 10, then subsequently a hole is created at index 5,
 805 *      radix_tree_prev_hole covering both indexes may return 5 if called under
 806 *      rcu_read_lock.
 807 */
 808unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
 809                                   unsigned long index, unsigned long max_scan)
 810{
 811        unsigned long i;
 812
 813        for (i = 0; i < max_scan; i++) {
 814                if (!radix_tree_lookup(root, index))
 815                        break;
 816                index--;
 817                if (index == ULONG_MAX)
 818                        break;
 819        }
 820
 821        return index;
 822}
 823EXPORT_SYMBOL(radix_tree_prev_hole);
 824
 825static unsigned int
 826__lookup(struct radix_tree_node *slot, void ***results, unsigned long *indices,
 827        unsigned long index, unsigned int max_items, unsigned long *next_index)
 828{
 829        unsigned int nr_found = 0;
 830        unsigned int shift, height;
 831        unsigned long i;
 832
 833        height = slot->height;
 834        if (height == 0)
 835                goto out;
 836        shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 837
 838        for ( ; height > 1; height--) {
 839                i = (index >> shift) & RADIX_TREE_MAP_MASK;
 840                for (;;) {
 841                        if (slot->slots[i] != NULL)
 842                                break;
 843                        index &= ~((1UL << shift) - 1);
 844                        index += 1UL << shift;
 845                        if (index == 0)
 846                                goto out;       /* 32-bit wraparound */
 847                        i++;
 848                        if (i == RADIX_TREE_MAP_SIZE)
 849                                goto out;
 850                }
 851
 852                shift -= RADIX_TREE_MAP_SHIFT;
 853                slot = rcu_dereference_raw(slot->slots[i]);
 854                if (slot == NULL)
 855                        goto out;
 856        }
 857
 858        /* Bottom level: grab some items */
 859        for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
 860                if (slot->slots[i]) {
 861                        results[nr_found] = &(slot->slots[i]);
 862                        if (indices)
 863                                indices[nr_found] = index;
 864                        if (++nr_found == max_items) {
 865                                index++;
 866                                goto out;
 867                        }
 868                }
 869                index++;
 870        }
 871out:
 872        *next_index = index;
 873        return nr_found;
 874}
 875
 876/**
 877 *      radix_tree_gang_lookup - perform multiple lookup on a radix tree
 878 *      @root:          radix tree root
 879 *      @results:       where the results of the lookup are placed
 880 *      @first_index:   start the lookup from this key
 881 *      @max_items:     place up to this many items at *results
 882 *
 883 *      Performs an index-ascending scan of the tree for present items.  Places
 884 *      them at *@results and returns the number of items which were placed at
 885 *      *@results.
 886 *
 887 *      The implementation is naive.
 888 *
 889 *      Like radix_tree_lookup, radix_tree_gang_lookup may be called under
 890 *      rcu_read_lock. In this case, rather than the returned results being
 891 *      an atomic snapshot of the tree at a single point in time, the semantics
 892 *      of an RCU protected gang lookup are as though multiple radix_tree_lookups
 893 *      have been issued in individual locks, and results stored in 'results'.
 894 */
 895unsigned int
 896radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
 897                        unsigned long first_index, unsigned int max_items)
 898{
 899        unsigned long max_index;
 900        struct radix_tree_node *node;
 901        unsigned long cur_index = first_index;
 902        unsigned int ret;
 903
 904        node = rcu_dereference_raw(root->rnode);
 905        if (!node)
 906                return 0;
 907
 908        if (!radix_tree_is_indirect_ptr(node)) {
 909                if (first_index > 0)
 910                        return 0;
 911                results[0] = node;
 912                return 1;
 913        }
 914        node = indirect_to_ptr(node);
 915
 916        max_index = radix_tree_maxindex(node->height);
 917
 918        ret = 0;
 919        while (ret < max_items) {
 920                unsigned int nr_found, slots_found, i;
 921                unsigned long next_index;       /* Index of next search */
 922
 923                if (cur_index > max_index)
 924                        break;
 925                slots_found = __lookup(node, (void ***)results + ret, NULL,
 926                                cur_index, max_items - ret, &next_index);
 927                nr_found = 0;
 928                for (i = 0; i < slots_found; i++) {
 929                        struct radix_tree_node *slot;
 930                        slot = *(((void ***)results)[ret + i]);
 931                        if (!slot)
 932                                continue;
 933                        results[ret + nr_found] =
 934                                indirect_to_ptr(rcu_dereference_raw(slot));
 935                        nr_found++;
 936                }
 937                ret += nr_found;
 938                if (next_index == 0)
 939                        break;
 940                cur_index = next_index;
 941        }
 942
 943        return ret;
 944}
 945EXPORT_SYMBOL(radix_tree_gang_lookup);
 946
 947/**
 948 *      radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
 949 *      @root:          radix tree root
 950 *      @results:       where the results of the lookup are placed
 951 *      @indices:       where their indices should be placed (but usually NULL)
 952 *      @first_index:   start the lookup from this key
 953 *      @max_items:     place up to this many items at *results
 954 *
 955 *      Performs an index-ascending scan of the tree for present items.  Places
 956 *      their slots at *@results and returns the number of items which were
 957 *      placed at *@results.
 958 *
 959 *      The implementation is naive.
 960 *
 961 *      Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must
 962 *      be dereferenced with radix_tree_deref_slot, and if using only RCU
 963 *      protection, radix_tree_deref_slot may fail requiring a retry.
 964 */
 965unsigned int
 966radix_tree_gang_lookup_slot(struct radix_tree_root *root,
 967                        void ***results, unsigned long *indices,
 968                        unsigned long first_index, unsigned int max_items)
 969{
 970        unsigned long max_index;
 971        struct radix_tree_node *node;
 972        unsigned long cur_index = first_index;
 973        unsigned int ret;
 974
 975        node = rcu_dereference_raw(root->rnode);
 976        if (!node)
 977                return 0;
 978
 979        if (!radix_tree_is_indirect_ptr(node)) {
 980                if (first_index > 0)
 981                        return 0;
 982                results[0] = (void **)&root->rnode;
 983                if (indices)
 984                        indices[0] = 0;
 985                return 1;
 986        }
 987        node = indirect_to_ptr(node);
 988
 989        max_index = radix_tree_maxindex(node->height);
 990
 991        ret = 0;
 992        while (ret < max_items) {
 993                unsigned int slots_found;
 994                unsigned long next_index;       /* Index of next search */
 995
 996                if (cur_index > max_index)
 997                        break;
 998                slots_found = __lookup(node, results + ret,
 999                                indices ? indices + ret : NULL,
1000                                cur_index, max_items - ret, &next_index);
1001                ret += slots_found;
1002                if (next_index == 0)
1003                        break;
1004                cur_index = next_index;
1005        }
1006
1007        return ret;
1008}
1009EXPORT_SYMBOL(radix_tree_gang_lookup_slot);
1010
1011/*
1012 * FIXME: the two tag_get()s here should use find_next_bit() instead of
1013 * open-coding the search.
1014 */
1015static unsigned int
1016__lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index,
1017        unsigned int max_items, unsigned long *next_index, unsigned int tag)
1018{
1019        unsigned int nr_found = 0;
1020        unsigned int shift, height;
1021
1022        height = slot->height;
1023        if (height == 0)
1024                goto out;
1025        shift = (height-1) * RADIX_TREE_MAP_SHIFT;
1026
1027        while (height > 0) {
1028                unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ;
1029
1030                for (;;) {
1031                        if (tag_get(slot, tag, i))
1032                                break;
1033                        index &= ~((1UL << shift) - 1);
1034                        index += 1UL << shift;
1035                        if (index == 0)
1036                                goto out;       /* 32-bit wraparound */
1037                        i++;
1038                        if (i == RADIX_TREE_MAP_SIZE)
1039                                goto out;
1040                }
1041                height--;
1042                if (height == 0) {      /* Bottom level: grab some items */
1043                        unsigned long j = index & RADIX_TREE_MAP_MASK;
1044
1045                        for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
1046                                index++;
1047                                if (!tag_get(slot, tag, j))
1048                                        continue;
1049                                /*
1050                                 * Even though the tag was found set, we need to
1051                                 * recheck that we have a non-NULL node, because
1052                                 * if this lookup is lockless, it may have been
1053                                 * subsequently deleted.
1054                                 *
1055                                 * Similar care must be taken in any place that
1056                                 * lookup ->slots[x] without a lock (ie. can't
1057                                 * rely on its value remaining the same).
1058                                 */
1059                                if (slot->slots[j]) {
1060                                        results[nr_found++] = &(slot->slots[j]);
1061                                        if (nr_found == max_items)
1062                                                goto out;
1063                                }
1064                        }
1065                }
1066                shift -= RADIX_TREE_MAP_SHIFT;
1067                slot = rcu_dereference_raw(slot->slots[i]);
1068                if (slot == NULL)
1069                        break;
1070        }
1071out:
1072        *next_index = index;
1073        return nr_found;
1074}
1075
1076/**
1077 *      radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
1078 *                                   based on a tag
1079 *      @root:          radix tree root
1080 *      @results:       where the results of the lookup are placed
1081 *      @first_index:   start the lookup from this key
1082 *      @max_items:     place up to this many items at *results
1083 *      @tag:           the tag index (< RADIX_TREE_MAX_TAGS)
1084 *
1085 *      Performs an index-ascending scan of the tree for present items which
1086 *      have the tag indexed by @tag set.  Places the items at *@results and
1087 *      returns the number of items which were placed at *@results.
1088 */
1089unsigned int
1090radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
1091                unsigned long first_index, unsigned int max_items,
1092                unsigned int tag)
1093{
1094        struct radix_tree_node *node;
1095        unsigned long max_index;
1096        unsigned long cur_index = first_index;
1097        unsigned int ret;
1098
1099        /* check the root's tag bit */
1100        if (!root_tag_get(root, tag))
1101                return 0;
1102
1103        node = rcu_dereference_raw(root->rnode);
1104        if (!node)
1105                return 0;
1106
1107        if (!radix_tree_is_indirect_ptr(node)) {
1108                if (first_index > 0)
1109                        return 0;
1110                results[0] = node;
1111                return 1;
1112        }
1113        node = indirect_to_ptr(node);
1114
1115        max_index = radix_tree_maxindex(node->height);
1116
1117        ret = 0;
1118        while (ret < max_items) {
1119                unsigned int nr_found, slots_found, i;
1120                unsigned long next_index;       /* Index of next search */
1121
1122                if (cur_index > max_index)
1123                        break;
1124                slots_found = __lookup_tag(node, (void ***)results + ret,
1125                                cur_index, max_items - ret, &next_index, tag);
1126                nr_found = 0;
1127                for (i = 0; i < slots_found; i++) {
1128                        struct radix_tree_node *slot;
1129                        slot = *(((void ***)results)[ret + i]);
1130                        if (!slot)
1131                                continue;
1132                        results[ret + nr_found] =
1133                                indirect_to_ptr(rcu_dereference_raw(slot));
1134                        nr_found++;
1135                }
1136                ret += nr_found;
1137                if (next_index == 0)
1138                        break;
1139                cur_index = next_index;
1140        }
1141
1142        return ret;
1143}
1144EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
1145
1146/**
1147 *      radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a
1148 *                                        radix tree based on a tag
1149 *      @root:          radix tree root
1150 *      @results:       where the results of the lookup are placed
1151 *      @first_index:   start the lookup from this key
1152 *      @max_items:     place up to this many items at *results
1153 *      @tag:           the tag index (< RADIX_TREE_MAX_TAGS)
1154 *
1155 *      Performs an index-ascending scan of the tree for present items which
1156 *      have the tag indexed by @tag set.  Places the slots at *@results and
1157 *      returns the number of slots which were placed at *@results.
1158 */
1159unsigned int
1160radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
1161                unsigned long first_index, unsigned int max_items,
1162                unsigned int tag)
1163{
1164        struct radix_tree_node *node;
1165        unsigned long max_index;
1166        unsigned long cur_index = first_index;
1167        unsigned int ret;
1168
1169        /* check the root's tag bit */
1170        if (!root_tag_get(root, tag))
1171                return 0;
1172
1173        node = rcu_dereference_raw(root->rnode);
1174        if (!node)
1175                return 0;
1176
1177        if (!radix_tree_is_indirect_ptr(node)) {
1178                if (first_index > 0)
1179                        return 0;
1180                results[0] = (void **)&root->rnode;
1181                return 1;
1182        }
1183        node = indirect_to_ptr(node);
1184
1185        max_index = radix_tree_maxindex(node->height);
1186
1187        ret = 0;
1188        while (ret < max_items) {
1189                unsigned int slots_found;
1190                unsigned long next_index;       /* Index of next search */
1191
1192                if (cur_index > max_index)
1193                        break;
1194                slots_found = __lookup_tag(node, results + ret,
1195                                cur_index, max_items - ret, &next_index, tag);
1196                ret += slots_found;
1197                if (next_index == 0)
1198                        break;
1199                cur_index = next_index;
1200        }
1201
1202        return ret;
1203}
1204EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);
1205
1206#if defined(CONFIG_SHMEM) && defined(CONFIG_SWAP)
1207#include <linux/sched.h> /* for cond_resched() */
1208
1209/*
1210 * This linear search is at present only useful to shmem_unuse_inode().
1211 */
1212static unsigned long __locate(struct radix_tree_node *slot, void *item,
1213                              unsigned long index, unsigned long *found_index)
1214{
1215        unsigned int shift, height;
1216        unsigned long i;
1217
1218        height = slot->height;
1219        shift = (height-1) * RADIX_TREE_MAP_SHIFT;
1220
1221        for ( ; height > 1; height--) {
1222                i = (index >> shift) & RADIX_TREE_MAP_MASK;
1223                for (;;) {
1224                        if (slot->slots[i] != NULL)
1225                                break;
1226                        index &= ~((1UL << shift) - 1);
1227                        index += 1UL << shift;
1228                        if (index == 0)
1229                                goto out;       /* 32-bit wraparound */
1230                        i++;
1231                        if (i == RADIX_TREE_MAP_SIZE)
1232                                goto out;
1233                }
1234
1235                shift -= RADIX_TREE_MAP_SHIFT;
1236                slot = rcu_dereference_raw(slot->slots[i]);
1237                if (slot == NULL)
1238                        goto out;
1239        }
1240
1241        /* Bottom level: check items */
1242        for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
1243                if (slot->slots[i] == item) {
1244                        *found_index = index + i;
1245                        index = 0;
1246                        goto out;
1247                }
1248        }
1249        index += RADIX_TREE_MAP_SIZE;
1250out:
1251        return index;
1252}
1253
1254/**
1255 *      radix_tree_locate_item - search through radix tree for item
1256 *      @root:          radix tree root
1257 *      @item:          item to be found
1258 *
1259 *      Returns index where item was found, or -1 if not found.
1260 *      Caller must hold no lock (since this time-consuming function needs
1261 *      to be preemptible), and must check afterwards if item is still there.
1262 */
1263unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
1264{
1265        struct radix_tree_node *node;
1266        unsigned long max_index;
1267        unsigned long cur_index = 0;
1268        unsigned long found_index = -1;
1269
1270        do {
1271                rcu_read_lock();
1272                node = rcu_dereference_raw(root->rnode);
1273                if (!radix_tree_is_indirect_ptr(node)) {
1274                        rcu_read_unlock();
1275                        if (node == item)
1276                                found_index = 0;
1277                        break;
1278                }
1279
1280                node = indirect_to_ptr(node);
1281                max_index = radix_tree_maxindex(node->height);
1282                if (cur_index > max_index)
1283                        break;
1284
1285                cur_index = __locate(node, item, cur_index, &found_index);
1286                rcu_read_unlock();
1287                cond_resched();
1288        } while (cur_index != 0 && cur_index <= max_index);
1289
1290        return found_index;
1291}
1292#else
1293unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
1294{
1295        return -1;
1296}
1297#endif /* CONFIG_SHMEM && CONFIG_SWAP */
1298
1299/**
1300 *      radix_tree_shrink    -    shrink height of a radix tree to minimal
1301 *      @root           radix tree root
1302 */
1303static inline void radix_tree_shrink(struct radix_tree_root *root)
1304{
1305        /* try to shrink tree height */
1306        while (root->height > 0) {
1307                struct radix_tree_node *to_free = root->rnode;
1308                void *newptr;
1309
1310                BUG_ON(!radix_tree_is_indirect_ptr(to_free));
1311                to_free = indirect_to_ptr(to_free);
1312
1313                /*
1314                 * The candidate node has more than one child, or its child
1315                 * is not at the leftmost slot, we cannot shrink.
1316                 */
1317                if (to_free->count != 1)
1318                        break;
1319                if (!to_free->slots[0])
1320                        break;
1321
1322                /*
1323                 * We don't need rcu_assign_pointer(), since we are simply
1324                 * moving the node from one part of the tree to another: if it
1325                 * was safe to dereference the old pointer to it
1326                 * (to_free->slots[0]), it will be safe to dereference the new
1327                 * one (root->rnode) as far as dependent read barriers go.
1328                 */
1329                newptr = to_free->slots[0];
1330                if (root->height > 1)
1331                        newptr = ptr_to_indirect(newptr);
1332                root->rnode = newptr;
1333                root->height--;
1334
1335                /*
1336                 * We have a dilemma here. The node's slot[0] must not be
1337                 * NULLed in case there are concurrent lookups expecting to
1338                 * find the item. However if this was a bottom-level node,
1339                 * then it may be subject to the slot pointer being visible
1340                 * to callers dereferencing it. If item corresponding to
1341                 * slot[0] is subsequently deleted, these callers would expect
1342                 * their slot to become empty sooner or later.
1343                 *
1344                 * For example, lockless pagecache will look up a slot, deref
1345                 * the page pointer, and if the page is 0 refcount it means it
1346                 * was concurrently deleted from pagecache so try the deref
1347                 * again. Fortunately there is already a requirement for logic
1348                 * to retry the entire slot lookup -- the indirect pointer
1349                 * problem (replacing direct root node with an indirect pointer
1350                 * also results in a stale slot). So tag the slot as indirect
1351                 * to force callers to retry.
1352                 */
1353                if (root->height == 0)
1354                        *((unsigned long *)&to_free->slots[0]) |=
1355                                                RADIX_TREE_INDIRECT_PTR;
1356
1357                radix_tree_node_free(to_free);
1358        }
1359}
1360
1361/**
1362 *      radix_tree_delete    -    delete an item from a radix tree
1363 *      @root:          radix tree root
1364 *      @index:         index key
1365 *
1366 *      Remove the item at @index from the radix tree rooted at @root.
1367 *
1368 *      Returns the address of the deleted item, or NULL if it was not present.
1369 */
1370void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
1371{
1372        /*
1373         * The radix tree path needs to be one longer than the maximum path
1374         * since the "list" is null terminated.
1375         */
1376        struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
1377        struct radix_tree_node *slot = NULL;
1378        struct radix_tree_node *to_free;
1379        unsigned int height, shift;
1380        int tag;
1381        int offset;
1382
1383        height = root->height;
1384        if (index > radix_tree_maxindex(height))
1385                goto out;
1386
1387        slot = root->rnode;
1388        if (height == 0) {
1389                root_tag_clear_all(root);
1390                root->rnode = NULL;
1391                goto out;
1392        }
1393        slot = indirect_to_ptr(slot);
1394
1395        shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
1396        pathp->node = NULL;
1397
1398        do {
1399                if (slot == NULL)
1400                        goto out;
1401
1402                pathp++;
1403                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
1404                pathp->offset = offset;
1405                pathp->node = slot;
1406                slot = slot->slots[offset];
1407                shift -= RADIX_TREE_MAP_SHIFT;
1408                height--;
1409        } while (height > 0);
1410
1411        if (slot == NULL)
1412                goto out;
1413
1414        /*
1415         * Clear all tags associated with the just-deleted item
1416         */
1417        for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
1418                if (tag_get(pathp->node, tag, pathp->offset))
1419                        radix_tree_tag_clear(root, index, tag);
1420        }
1421
1422        to_free = NULL;
1423        /* Now free the nodes we do not need anymore */
1424        while (pathp->node) {
1425                pathp->node->slots[pathp->offset] = NULL;
1426                pathp->node->count--;
1427                /*
1428                 * Queue the node for deferred freeing after the
1429                 * last reference to it disappears (set NULL, above).
1430                 */
1431                if (to_free)
1432                        radix_tree_node_free(to_free);
1433
1434                if (pathp->node->count) {
1435                        if (pathp->node == indirect_to_ptr(root->rnode))
1436                                radix_tree_shrink(root);
1437                        goto out;
1438                }
1439
1440                /* Node with zero slots in use so free it */
1441                to_free = pathp->node;
1442                pathp--;
1443
1444        }
1445        root_tag_clear_all(root);
1446        root->height = 0;
1447        root->rnode = NULL;
1448        if (to_free)
1449                radix_tree_node_free(to_free);
1450
1451out:
1452        return slot;
1453}
1454EXPORT_SYMBOL(radix_tree_delete);
1455
1456/**
1457 *      radix_tree_tagged - test whether any items in the tree are tagged
1458 *      @root:          radix tree root
1459 *      @tag:           tag to test
1460 */
1461int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
1462{
1463        return root_tag_get(root, tag);
1464}
1465EXPORT_SYMBOL(radix_tree_tagged);
1466
1467static void
1468radix_tree_node_ctor(void *node)
1469{
1470        memset(node, 0, sizeof(struct radix_tree_node));
1471}
1472
1473static __init unsigned long __maxindex(unsigned int height)
1474{
1475        unsigned int width = height * RADIX_TREE_MAP_SHIFT;
1476        int shift = RADIX_TREE_INDEX_BITS - width;
1477
1478        if (shift < 0)
1479                return ~0UL;
1480        if (shift >= BITS_PER_LONG)
1481                return 0UL;
1482        return ~0UL >> shift;
1483}
1484
1485static __init void radix_tree_init_maxindex(void)
1486{
1487        unsigned int i;
1488
1489        for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
1490                height_to_maxindex[i] = __maxindex(i);
1491}
1492
1493static int radix_tree_callback(struct notifier_block *nfb,
1494                            unsigned long action,
1495                            void *hcpu)
1496{
1497       int cpu = (long)hcpu;
1498       struct radix_tree_preload *rtp;
1499
1500       /* Free per-cpu pool of perloaded nodes */
1501       if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
1502               rtp = &per_cpu(radix_tree_preloads, cpu);
1503               while (rtp->nr) {
1504                       kmem_cache_free(radix_tree_node_cachep,
1505                                       rtp->nodes[rtp->nr-1]);
1506                       rtp->nodes[rtp->nr-1] = NULL;
1507                       rtp->nr--;
1508               }
1509       }
1510       return NOTIFY_OK;
1511}
1512
1513void __init radix_tree_init(void)
1514{
1515        radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
1516                        sizeof(struct radix_tree_node), 0,
1517                        SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
1518                        radix_tree_node_ctor);
1519        radix_tree_init_maxindex();
1520        hotcpu_notifier(radix_tree_callback, 0);
1521}
1522
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.