lib/radix-tree.c

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