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
  32 /*
  33  * Radix tree node definition.
  34  */
  35 #define RADIX_TREE_MAP_SHIFT  6
  36 #define RADIX_TREE_MAP_SIZE  (1UL << RADIX_TREE_MAP_SHIFT)
  37 #define RADIX_TREE_MAP_MASK  (RADIX_TREE_MAP_SIZE-1)
  38
  39 struct radix_tree_node {
  40         unsigned int    count;
  41         void            *slots[RADIX_TREE_MAP_SIZE];
  42 };
  43
  44 struct radix_tree_path {
  45         struct radix_tree_node *node, **slot;
  46 };
  47
  48 #define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
  49 #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
  50
  51 static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH];
  52
  53 /*
  54  * Radix tree node cache.
  55  */
  56 static kmem_cache_t *radix_tree_node_cachep;
  57
  58 /*
  59  * Per-cpu pool of preloaded nodes
  60  */
  61 struct radix_tree_preload {
  62         int nr;
  63         struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH];
  64 };
  65 DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
  66
  67 /*
  68  * This assumes that the caller has performed appropriate preallocation, and
  69  * that the caller has pinned this thread of control to the current CPU.
  70  */
  71 static struct radix_tree_node *
  72 radix_tree_node_alloc(struct radix_tree_root *root)
  73 {
  74         struct radix_tree_node *ret;
  75
  76         ret = kmem_cache_alloc(radix_tree_node_cachep, root->gfp_mask);
  77         if (ret == NULL && !(root->gfp_mask & __GFP_WAIT)) {
  78                 struct radix_tree_preload *rtp;
  79
  80                 rtp = &__get_cpu_var(radix_tree_preloads);
  81                 if (rtp->nr) {
  82                         ret = rtp->nodes[rtp->nr - 1];
  83                         rtp->nodes[rtp->nr - 1] = NULL;
  84                         rtp->nr--;
  85                 }
  86         }
  87         return ret;
  88 }
  89
  90 static inline void
  91 radix_tree_node_free(struct radix_tree_node *node)
  92 {
  93         kmem_cache_free(radix_tree_node_cachep, node);
  94 }
  95
  96 /*
  97  * Load up this CPU's radix_tree_node buffer with sufficient objects to
  98  * ensure that the addition of a single element in the tree cannot fail.  On
  99  * success, return zero, with preemption disabled.  On error, return -ENOMEM
 100  * with preemption not disabled.
 101  */
 102 int radix_tree_preload(int gfp_mask)
 103 {
 104         struct radix_tree_preload *rtp;
 105         struct radix_tree_node *node;
 106         int ret = -ENOMEM;
 107
 108         preempt_disable();
 109         rtp = &__get_cpu_var(radix_tree_preloads);
 110         while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
 111                 preempt_enable();
 112                 node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
 113                 if (node == NULL)
 114                         goto out;
 115                 preempt_disable();
 116                 rtp = &__get_cpu_var(radix_tree_preloads);
 117                 if (rtp->nr < ARRAY_SIZE(rtp->nodes))
 118                         rtp->nodes[rtp->nr++] = node;
 119                 else
 120                         kmem_cache_free(radix_tree_node_cachep, node);
 121         }
 122         ret = 0;
 123 out:
 124         return ret;
 125 }
 126
 127 /*
 128  *      Return the maximum key which can be store into a
 129  *      radix tree with height HEIGHT.
 130  */
 131 static inline unsigned long radix_tree_maxindex(unsigned int height)
 132 {
 133         return height_to_maxindex[height];
 134 }
 135
 136 /*
 137  *      Extend a radix tree so it can store key @index.
 138  */
 139 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
 140 {
 141         struct radix_tree_node *node;
 142         unsigned int height;
 143
 144         /* Figure out what the height should be.  */
 145         height = root->height + 1;
 146         while (index > radix_tree_maxindex(height))
 147                 height++;
 148
 149         if (root->rnode) {
 150                 do {
 151                         if (!(node = radix_tree_node_alloc(root)))
 152                                 return -ENOMEM;
 153
 154                         /* Increase the height.  */
 155                         node->slots[0] = root->rnode;
 156                         node->count = 1;
 157                         root->rnode = node;
 158                         root->height++;
 159                 } while (height > root->height);
 160         } else
 161                 root->height = height;
 162
 163         return 0;
 164 }
 165
 166 /**
 167  *      radix_tree_insert    -    insert into a radix tree
 168  *      @root:          radix tree root
 169  *      @index:         index key
 170  *      @item:          item to insert
 171  *
 172  *      Insert an item into the radix tree at position @index.
 173  */
 174 int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
 175 {
 176         struct radix_tree_node *node = NULL, *tmp, **slot;
 177         unsigned int height, shift;
 178         int error;
 179
 180         /* Make sure the tree is high enough.  */
 181         if (index > radix_tree_maxindex(root->height)) {
 182                 error = radix_tree_extend(root, index);
 183                 if (error)
 184                         return error;
 185         }
 186
 187         slot = &root->rnode;
 188         height = root->height;
 189         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 190
 191         while (height > 0) {
 192                 if (*slot == NULL) {
 193                         /* Have to add a child node.  */
 194                         if (!(tmp = radix_tree_node_alloc(root)))
 195                                 return -ENOMEM;
 196                         *slot = tmp;
 197                         if (node)
 198                                 node->count++;
 199                 }
 200
 201                 /* Go a level down.  */
 202                 node = *slot;
 203                 slot = (struct radix_tree_node **)
 204                         (node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
 205                 shift -= RADIX_TREE_MAP_SHIFT;
 206                 height--;
 207         }
 208
 209         if (*slot != NULL)
 210                 return -EEXIST;
 211         if (node)
 212                 node->count++;
 213
 214         *slot = item;
 215         return 0;
 216 }
 217 EXPORT_SYMBOL(radix_tree_insert);
 218
 219 /**
 220  *      radix_tree_lookup    -    perform lookup operation on a radix tree
 221  *      @root:          radix tree root
 222  *      @index:         index key
 223  *
 224  *      Lookup them item at the position @index in the radix tree @root.
 225  */
 226 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
 227 {
 228         unsigned int height, shift;
 229         struct radix_tree_node **slot;
 230
 231         height = root->height;
 232         if (index > radix_tree_maxindex(height))
 233                 return NULL;
 234
 235         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 236         slot = &root->rnode;
 237
 238         while (height > 0) {
 239                 if (*slot == NULL)
 240                         return NULL;
 241
 242                 slot = (struct radix_tree_node **)
 243                         ((*slot)->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
 244                 shift -= RADIX_TREE_MAP_SHIFT;
 245                 height--;
 246         }
 247
 248         return (void *) *slot;
 249 }
 250 EXPORT_SYMBOL(radix_tree_lookup);
 251
 252 static /* inline */ unsigned int
 253 __lookup(struct radix_tree_root *root, void **results, unsigned long index,
 254         unsigned int max_items, unsigned long *next_index)
 255 {
 256         unsigned int nr_found = 0;
 257         unsigned int shift;
 258         unsigned int height = root->height;
 259         struct radix_tree_node *slot;
 260
 261         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 262         slot = root->rnode;
 263
 264         while (height > 0) {
 265                 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;
 266
 267                 for ( ; i < RADIX_TREE_MAP_SIZE; i++) {
 268                         if (slot->slots[i] != NULL)
 269                                 break;
 270                         index &= ~((1 << shift) - 1);
 271                         index += 1 << shift;
 272                         if (index == 0)
 273                                 goto out;       /* 32-bit wraparound */
 274                 }
 275                 if (i == RADIX_TREE_MAP_SIZE)
 276                         goto out;
 277                 height--;
 278                 if (height == 0) {      /* Bottom level: grab some items */
 279                         unsigned long j = index & RADIX_TREE_MAP_MASK;
 280
 281                         for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
 282                                 index++;
 283                                 if (slot->slots[j]) {
 284                                         results[nr_found++] = slot->slots[j];
 285                                         if (nr_found == max_items)
 286                                                 goto out;
 287                                 }
 288                         }
 289                 }
 290                 shift -= RADIX_TREE_MAP_SHIFT;
 291                 slot = slot->slots[i];
 292         }
 293 out:
 294         *next_index = index;
 295         return nr_found;
 296 }
 297
 298 /**
 299  *      radix_tree_gang_lookup - perform multiple lookup on a radix tree
 300  *      @root:          radix tree root
 301  *      @results:       where the results of the lookup are placed
 302  *      @first_index:   start the lookup from this key
 303  *      @max_items:     place up to this many items at *results
 304  *
 305  *      Performs an index-ascending scan of the tree for present items.  Places
 306  *      them at *@results and returns the number of items which were placed at
 307  *      *@results.
 308  *
 309  *      The implementation is naive.
 310  */
 311 unsigned int
 312 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
 313                         unsigned long first_index, unsigned int max_items)
 314 {
 315         const unsigned long max_index = radix_tree_maxindex(root->height);
 316         unsigned long cur_index = first_index;
 317         unsigned int ret = 0;
 318
 319         if (root->rnode == NULL)
 320                 goto out;
 321         if (max_index == 0) {                   /* Bah.  Special case */
 322                 if (first_index == 0) {
 323                         if (max_items > 0) {
 324                                 *results = root->rnode;
 325                                 ret = 1;
 326                         }
 327                 }
 328                 goto out;
 329         }
 330         while (ret < max_items) {
 331                 unsigned int nr_found;
 332                 unsigned long next_index;       /* Index of next search */
 333
 334                 if (cur_index > max_index)
 335                         break;
 336                 nr_found = __lookup(root, results + ret, cur_index,
 337                                         max_items - ret, &next_index);
 338                 ret += nr_found;
 339                 if (next_index == 0)
 340                         break;
 341                 cur_index = next_index;
 342         }
 343 out:
 344         return ret;
 345 }
 346 EXPORT_SYMBOL(radix_tree_gang_lookup);
 347
 348 /**
 349  *      radix_tree_delete    -    delete an item from a radix tree
 350  *      @root:          radix tree root
 351  *      @index:         index key
 352  *
 353  *      Remove the item at @index from the radix tree rooted at @root.
 354  *
 355  *      Returns the address of the deleted item, or NULL if it was not present.
 356  */
 357 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
 358 {
 359         struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
 360         unsigned int height, shift;
 361         void *ret = NULL;
 362
 363         height = root->height;
 364         if (index > radix_tree_maxindex(height))
 365                 goto out;
 366
 367         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 368         pathp->node = NULL;
 369         pathp->slot = &root->rnode;
 370
 371         while (height > 0) {
 372                 if (*pathp->slot == NULL)
 373                         goto out;
 374
 375                 pathp[1].node = *pathp[0].slot;
 376                 pathp[1].slot = (struct radix_tree_node **)
 377                     (pathp[1].node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
 378                 pathp++;
 379                 shift -= RADIX_TREE_MAP_SHIFT;
 380                 height--;
 381         }
 382
 383         ret = *pathp[0].slot;
 384         if (ret == NULL)
 385                 goto out;
 386
 387         *pathp[0].slot = NULL;
 388         while (pathp[0].node && --pathp[0].node->count == 0) {
 389                 pathp--;
 390                 *pathp[0].slot = NULL;
 391                 radix_tree_node_free(pathp[1].node);
 392         }
 393
 394         if (root->rnode == NULL)
 395                 root->height = 0;  /* Empty tree, we can reset the height */
 396 out:
 397         return ret;
 398 }
 399 EXPORT_SYMBOL(radix_tree_delete);
 400
 401 static void
 402 radix_tree_node_ctor(void *node, kmem_cache_t *cachep, unsigned long flags)
 403 {
 404         memset(node, 0, sizeof(struct radix_tree_node));
 405 }
 406
 407 static __init unsigned long __maxindex(unsigned int height)
 408 {
 409         unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
 410         unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
 411
 412         if (tmp >= RADIX_TREE_INDEX_BITS)
 413                 index = ~0UL;
 414         return index;
 415 }
 416
 417 static __init void radix_tree_init_maxindex(void)
 418 {
 419         unsigned int i;
 420
 421         for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
 422                 height_to_maxindex[i] = __maxindex(i);
 423 }
 424
 425 #ifdef CONFIG_HOTPLUG_CPU
 426 static int radix_tree_callback(struct notifier_block *nfb,
 427                             unsigned long action,
 428                             void *hcpu)
 429 {
 430        int cpu = (long)hcpu;
 431        struct radix_tree_preload *rtp;
 432
 433        /* Free per-cpu pool of perloaded nodes */
 434        if (action == CPU_DEAD) {
 435                rtp = &per_cpu(radix_tree_preloads, cpu);
 436                while (rtp->nr) {
 437                        kmem_cache_free(radix_tree_node_cachep,
 438                                        rtp->nodes[rtp->nr-1]);
 439                        rtp->nodes[rtp->nr-1] = NULL;
 440                        rtp->nr--;
 441                }
 442        }
 443        return NOTIFY_OK;
 444 }
 445 #endif /* CONFIG_HOTPLUG_CPU */
 446
 447 void __init radix_tree_init(void)
 448 {
 449         radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
 450                         sizeof(struct radix_tree_node), 0,
 451                         0, radix_tree_node_ctor, NULL);
 452         if (!radix_tree_node_cachep)
 453                 panic ("Failed to create radix_tree_node cache\n");
 454         radix_tree_init_maxindex();
 455         hotcpu_notifier(radix_tree_callback, 0);
 456 }