debuggers.hg

annotate xen/common/radix-tree.c @ 22848:6341fe0f4e5a

Added tag 4.1.0-rc2 for changeset 9dca60d88c63
author Keir Fraser <keir@xen.org>
date Tue Jan 25 14:06:55 2011 +0000 (2011-01-25)
parents 6348b2ab5c39
children
rev   line source
keir@19684 1 /*
keir@19684 2 * Copyright (C) 2001 Momchil Velikov
keir@19684 3 * Portions Copyright (C) 2001 Christoph Hellwig
keir@19684 4 * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com>
keir@19684 5 *
keir@19684 6 * This program is free software; you can redistribute it and/or
keir@19684 7 * modify it under the terms of the GNU General Public License as
keir@19684 8 * published by the Free Software Foundation; either version 2, or (at
keir@19684 9 * your option) any later version.
keir@19684 10 *
keir@19684 11 * This program is distributed in the hope that it will be useful, but
keir@19684 12 * WITHOUT ANY WARRANTY; without even the implied warranty of
keir@19684 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
keir@19684 14 * General Public License for more details.
keir@19684 15 *
keir@19684 16 * You should have received a copy of the GNU General Public License
keir@19684 17 * along with this program; if not, write to the Free Software
keir@19684 18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
keir@19684 19 */
keir@19684 20
keir@19684 21 /*
keir@19684 22 * Copyright (C) 2009 adaption for Xen tmem by Dan Magenheimer, Oracle Corp.
keir@19684 23 * Changed:
keir@19684 24 * o Linux 2.6.18 source used (prior to read-copy-update addition)
keir@19684 25 * o constants and data structures moved out to radix-tree.h header
keir@19684 26 * o tagging code removed
keir@19684 27 * o radix_tree_insert has func parameter for dynamic data struct allocation
keir@19684 28 * o radix_tree_destroy added (including recursive helper function)
keir@19684 29 * o __init functions must be called explicitly
keir@19684 30 * o other include files adapted to Xen
keir@19684 31 */
keir@19684 32
keir@19684 33 #include <xen/config.h>
keir@21436 34 #include <xen/init.h>
keir@19684 35 #include <xen/lib.h>
keir@19684 36 #include <xen/types.h>
keir@19684 37 #include <xen/errno.h>
keir@19684 38 #include <xen/radix-tree.h>
keir@19684 39 #include <asm/cache.h>
keir@19684 40
keir@19684 41 static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;
keir@19684 42
keir@19684 43 /*
keir@19684 44 * Return the maximum key which can be store into a
keir@19684 45 * radix tree with height HEIGHT.
keir@19684 46 */
keir@19684 47 static inline unsigned long radix_tree_maxindex(unsigned int height)
keir@19684 48 {
keir@19684 49 return height_to_maxindex[height];
keir@19684 50 }
keir@19684 51
keir@19684 52 /*
keir@19684 53 * Extend a radix tree so it can store key @index.
keir@19684 54 */
keir@19684 55 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index,
keir@19684 56 struct radix_tree_node *(*node_alloc)(void *), void *arg)
keir@19684 57 {
keir@19684 58 struct radix_tree_node *node;
keir@19684 59 unsigned int height;
keir@19684 60
keir@19684 61 /* Figure out what the height should be. */
keir@19684 62 height = root->height + 1;
keir@19684 63 if (index > radix_tree_maxindex(height))
keir@19684 64 while (index > radix_tree_maxindex(height))
keir@19684 65 height++;
keir@19684 66
keir@19684 67 if (root->rnode == NULL) {
keir@19684 68 root->height = height;
keir@19684 69 goto out;
keir@19684 70 }
keir@19684 71
keir@19684 72 do {
keir@19684 73 if (!(node = node_alloc(arg)))
keir@19684 74 return -ENOMEM;
keir@19684 75
keir@19684 76 /* Increase the height. */
keir@19684 77 node->slots[0] = root->rnode;
keir@19684 78
keir@19684 79 node->count = 1;
keir@19684 80 root->rnode = node;
keir@19684 81 root->height++;
keir@19684 82 } while (height > root->height);
keir@19684 83 out:
keir@19684 84 return 0;
keir@19684 85 }
keir@19684 86
keir@19684 87 /**
keir@19684 88 * radix_tree_insert - insert into a radix tree
keir@19684 89 * @root: radix tree root
keir@19684 90 * @index: index key
keir@19684 91 * @item: item to insert
keir@19684 92 *
keir@19684 93 * Insert an item into the radix tree at position @index.
keir@19684 94 */
keir@19684 95 int radix_tree_insert(struct radix_tree_root *root, unsigned long index,
keir@19684 96 void *item, struct radix_tree_node *(*node_alloc)(void *), void *arg)
keir@19684 97 {
keir@19684 98 struct radix_tree_node *node = NULL, *slot;
keir@19684 99 unsigned int height, shift;
keir@19684 100 int offset;
keir@19684 101 int error;
keir@19684 102
keir@19684 103 /* Make sure the tree is high enough. */
keir@19684 104 if (index > radix_tree_maxindex(root->height)) {
keir@19684 105 error = radix_tree_extend(root, index, node_alloc, arg);
keir@19684 106 if (error)
keir@19684 107 return error;
keir@19684 108 }
keir@19684 109
keir@19684 110 slot = root->rnode;
keir@19684 111 height = root->height;
keir@19684 112 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
keir@19684 113
keir@19684 114 offset = 0; /* uninitialised var warning */
keir@19684 115 while (height > 0) {
keir@19684 116 if (slot == NULL) {
keir@19684 117 /* Have to add a child node. */
keir@19684 118 if (!(slot = node_alloc(arg)))
keir@19684 119 return -ENOMEM;
keir@19684 120 if (node) {
keir@19684 121
keir@19684 122 node->slots[offset] = slot;
keir@19684 123 node->count++;
keir@19684 124 } else
keir@19684 125 root->rnode = slot;
keir@19684 126 }
keir@19684 127
keir@19684 128 /* Go a level down */
keir@19684 129 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
keir@19684 130 node = slot;
keir@19684 131 slot = node->slots[offset];
keir@19684 132 shift -= RADIX_TREE_MAP_SHIFT;
keir@19684 133 height--;
keir@19684 134 }
keir@19684 135
keir@19684 136 if (slot != NULL)
keir@19684 137 return -EEXIST;
keir@19684 138
keir@19684 139 if (node) {
keir@19684 140 node->count++;
keir@19684 141 node->slots[offset] = item;
keir@19684 142 } else {
keir@19684 143 root->rnode = item;
keir@19684 144 }
keir@19684 145
keir@19684 146 return 0;
keir@19684 147 }
keir@19684 148 EXPORT_SYMBOL(radix_tree_insert);
keir@19684 149
keir@19684 150 static inline void **__lookup_slot(struct radix_tree_root *root,
keir@19684 151 unsigned long index)
keir@19684 152 {
keir@19684 153 unsigned int height, shift;
keir@19684 154 struct radix_tree_node **slot;
keir@19684 155
keir@19684 156 height = root->height;
keir@19684 157
keir@19684 158 if (index > radix_tree_maxindex(height))
keir@19684 159 return NULL;
keir@19684 160
keir@19684 161 if (height == 0 && root->rnode)
keir@19684 162 return (void **)&root->rnode;
keir@19684 163
keir@19684 164 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
keir@19684 165 slot = &root->rnode;
keir@19684 166
keir@19684 167 while (height > 0) {
keir@19684 168 if (*slot == NULL)
keir@19684 169 return NULL;
keir@19684 170
keir@19684 171 slot = (struct radix_tree_node **)
keir@19684 172 ((*slot)->slots +
keir@19684 173 ((index >> shift) & RADIX_TREE_MAP_MASK));
keir@19684 174 shift -= RADIX_TREE_MAP_SHIFT;
keir@19684 175 height--;
keir@19684 176 }
keir@19684 177
keir@19684 178 return (void **)slot;
keir@19684 179 }
keir@19684 180
keir@19684 181 /**
keir@19684 182 * radix_tree_lookup_slot - lookup a slot in a radix tree
keir@19684 183 * @root: radix tree root
keir@19684 184 * @index: index key
keir@19684 185 *
keir@19684 186 * Lookup the slot corresponding to the position @index in the radix tree
keir@19684 187 * @root. This is useful for update-if-exists operations.
keir@19684 188 */
keir@19684 189 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
keir@19684 190 {
keir@19684 191 return __lookup_slot(root, index);
keir@19684 192 }
keir@19684 193 EXPORT_SYMBOL(radix_tree_lookup_slot);
keir@19684 194
keir@19684 195 /**
keir@19684 196 * radix_tree_lookup - perform lookup operation on a radix tree
keir@19684 197 * @root: radix tree root
keir@19684 198 * @index: index key
keir@19684 199 *
keir@19684 200 * Lookup the item at the position @index in the radix tree @root.
keir@19684 201 */
keir@19684 202 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
keir@19684 203 {
keir@19684 204 void **slot;
keir@19684 205
keir@19684 206 slot = __lookup_slot(root, index);
keir@19684 207 return slot != NULL ? *slot : NULL;
keir@19684 208 }
keir@19684 209 EXPORT_SYMBOL(radix_tree_lookup);
keir@19684 210
keir@19684 211 static unsigned int
keir@19684 212 __lookup(struct radix_tree_root *root, void **results, unsigned long index,
keir@19684 213 unsigned int max_items, unsigned long *next_index)
keir@19684 214 {
keir@19684 215 unsigned int nr_found = 0;
keir@19684 216 unsigned int shift, height;
keir@19684 217 struct radix_tree_node *slot;
keir@19684 218 unsigned long i;
keir@19684 219
keir@19684 220 height = root->height;
keir@19684 221 if (index > radix_tree_maxindex(height))
keir@19684 222 if (height == 0) {
keir@19684 223 if (root->rnode && index == 0)
keir@19684 224 results[nr_found++] = root->rnode;
keir@19684 225 goto out;
keir@19684 226 }
keir@19684 227
keir@19684 228 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
keir@19684 229 slot = root->rnode;
keir@19684 230
keir@19684 231 for ( ; height > 1; height--) {
keir@19684 232
keir@19684 233 for (i = (index >> shift) & RADIX_TREE_MAP_MASK ;
keir@19684 234 i < RADIX_TREE_MAP_SIZE; i++) {
keir@19684 235 if (slot->slots[i] != NULL)
keir@19684 236 break;
keir@19684 237 index &= ~((1UL << shift) - 1);
keir@19684 238 index += 1UL << shift;
keir@19684 239 if (index == 0)
keir@19684 240 goto out; /* 32-bit wraparound */
keir@19684 241 }
keir@19684 242 if (i == RADIX_TREE_MAP_SIZE)
keir@19684 243 goto out;
keir@19684 244
keir@19684 245 shift -= RADIX_TREE_MAP_SHIFT;
keir@19684 246 slot = slot->slots[i];
keir@19684 247 }
keir@19684 248
keir@19684 249 /* Bottom level: grab some items */
keir@19684 250 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
keir@19684 251 index++;
keir@19684 252 if (slot->slots[i]) {
keir@19684 253 results[nr_found++] = slot->slots[i];
keir@19684 254 if (nr_found == max_items)
keir@19684 255 goto out;
keir@19684 256 }
keir@19684 257 }
keir@19684 258 out:
keir@19684 259 *next_index = index;
keir@19684 260 return nr_found;
keir@19684 261 }
keir@19684 262
keir@19684 263 /**
keir@19684 264 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
keir@19684 265 * @root: radix tree root
keir@19684 266 * @results: where the results of the lookup are placed
keir@19684 267 * @first_index: start the lookup from this key
keir@19684 268 * @max_items: place up to this many items at *results
keir@19684 269 *
keir@19684 270 * Performs an index-ascending scan of the tree for present items. Places
keir@19684 271 * them at *@results and returns the number of items which were placed at
keir@19684 272 * *@results.
keir@19684 273 *
keir@19684 274 * The implementation is naive.
keir@19684 275 */
keir@19684 276 unsigned int
keir@19684 277 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
keir@19684 278 unsigned long first_index, unsigned int max_items)
keir@19684 279 {
keir@19684 280 const unsigned long max_index = radix_tree_maxindex(root->height);
keir@19684 281 unsigned long cur_index = first_index;
keir@19684 282 unsigned int ret = 0;
keir@19684 283
keir@19684 284 while (ret < max_items) {
keir@19684 285 unsigned int nr_found;
keir@19684 286 unsigned long next_index; /* Index of next search */
keir@19684 287
keir@19684 288 if (cur_index > max_index)
keir@19684 289 break;
keir@19684 290 nr_found = __lookup(root, results + ret, cur_index,
keir@19684 291 max_items - ret, &next_index);
keir@19684 292 ret += nr_found;
keir@19684 293 if (next_index == 0)
keir@19684 294 break;
keir@19684 295 cur_index = next_index;
keir@19684 296 }
keir@19684 297 return ret;
keir@19684 298 }
keir@19684 299 EXPORT_SYMBOL(radix_tree_gang_lookup);
keir@19684 300
keir@19684 301 /**
keir@19684 302 * radix_tree_shrink - shrink height of a radix tree to minimal
keir@19684 303 * @root radix tree root
keir@19684 304 */
keir@19684 305 static inline void radix_tree_shrink(struct radix_tree_root *root,
keir@19684 306 void (*node_free)(struct radix_tree_node *))
keir@19684 307 {
keir@19684 308 /* try to shrink tree height */
keir@19684 309 while (root->height > 0 &&
keir@19684 310 root->rnode->count == 1 &&
keir@19684 311 root->rnode->slots[0]) {
keir@19684 312 struct radix_tree_node *to_free = root->rnode;
keir@19684 313
keir@19684 314 root->rnode = to_free->slots[0];
keir@19684 315 root->height--;
keir@19684 316 to_free->slots[0] = NULL;
keir@19684 317 to_free->count = 0;
keir@19684 318 node_free(to_free);
keir@19684 319 }
keir@19684 320 }
keir@19684 321
keir@19684 322 /**
keir@19684 323 * radix_tree_delete - delete an item from a radix tree
keir@19684 324 * @root: radix tree root
keir@19684 325 * @index: index key
keir@19684 326 *
keir@19684 327 * Remove the item at @index from the radix tree rooted at @root.
keir@19684 328 *
keir@19684 329 * Returns the address of the deleted item, or NULL if it was not present.
keir@19684 330 */
keir@19684 331 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index,
keir@19684 332 void(*node_free)(struct radix_tree_node *))
keir@19684 333 {
keir@19684 334 struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
keir@19684 335 struct radix_tree_node *slot = NULL;
keir@19684 336 unsigned int height, shift;
keir@19684 337 int offset;
keir@19684 338
keir@19684 339 height = root->height;
keir@19684 340 if (index > radix_tree_maxindex(height))
keir@19684 341 goto out;
keir@19684 342
keir@19684 343 slot = root->rnode;
keir@19684 344 if (height == 0 && root->rnode) {
keir@19684 345 root->rnode = NULL;
keir@19684 346 goto out;
keir@19684 347 }
keir@19684 348
keir@19684 349 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
keir@19684 350 pathp->node = NULL;
keir@19684 351
keir@19684 352 do {
keir@19684 353 if (slot == NULL)
keir@19684 354 goto out;
keir@19684 355
keir@19684 356 pathp++;
keir@19684 357 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
keir@19684 358 pathp->offset = offset;
keir@19684 359 pathp->node = slot;
keir@19684 360 slot = slot->slots[offset];
keir@19684 361 shift -= RADIX_TREE_MAP_SHIFT;
keir@19684 362 height--;
keir@19684 363 } while (height > 0);
keir@19684 364
keir@19684 365 if (slot == NULL)
keir@19684 366 goto out;
keir@19684 367
keir@19684 368 /* Now free the nodes we do not need anymore */
keir@19684 369 while (pathp->node) {
keir@19684 370 pathp->node->slots[pathp->offset] = NULL;
keir@19684 371 pathp->node->count--;
keir@19684 372
keir@19684 373 if (pathp->node->count) {
keir@19684 374 if (pathp->node == root->rnode)
keir@19684 375 radix_tree_shrink(root, node_free);
keir@19684 376 goto out;
keir@19684 377 }
keir@19684 378
keir@19684 379 /* Node with zero slots in use so free it */
keir@19684 380 node_free(pathp->node);
keir@19684 381
keir@19684 382 pathp--;
keir@19684 383 }
keir@19684 384 root->height = 0;
keir@19684 385 root->rnode = NULL;
keir@19684 386
keir@19684 387 out:
keir@19684 388 return slot;
keir@19684 389 }
keir@19684 390 EXPORT_SYMBOL(radix_tree_delete);
keir@19684 391
keir@19684 392 static void
keir@19684 393 radix_tree_node_destroy(struct radix_tree_node *node, unsigned int height,
keir@19684 394 void (*slot_free)(void *), void (*node_free)(struct radix_tree_node *))
keir@19684 395 {
keir@19684 396 int i;
keir@19684 397
keir@19684 398 if (height == 0)
keir@19684 399 return;
keir@19684 400 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
keir@19684 401 if (node->slots[i]) {
keir@19684 402 if (height == 1) {
keir@19684 403 slot_free(node->slots[i]);
keir@19684 404 node->slots[i] = NULL;
keir@19684 405 continue;
keir@19684 406 }
keir@19684 407 radix_tree_node_destroy(node->slots[i], height-1,
keir@19684 408 slot_free, node_free);
keir@19684 409 node_free(node->slots[i]);
keir@19684 410 node->slots[i] = NULL;
keir@19684 411 }
keir@19684 412 }
keir@19684 413 }
keir@19684 414
keir@19684 415 void radix_tree_destroy(struct radix_tree_root *root,
keir@19684 416 void (*slot_free)(void *), void (*node_free)(struct radix_tree_node *))
keir@19684 417 {
keir@19684 418 if (root->rnode == NULL)
keir@19684 419 return;
keir@19684 420 if (root->height == 0)
keir@19684 421 slot_free(root->rnode);
keir@19684 422 else {
keir@19684 423 radix_tree_node_destroy(root->rnode, root->height,
keir@19684 424 slot_free, node_free);
keir@19684 425 node_free(root->rnode);
keir@19684 426 root->height = 0;
keir@19684 427 }
keir@19684 428 root->rnode = NULL;
keir@19684 429 /* caller must delete root if desired */
keir@19684 430 }
keir@19684 431 EXPORT_SYMBOL(radix_tree_destroy);
keir@19684 432
keir@21436 433 static unsigned long __init __maxindex(unsigned int height)
keir@19684 434 {
keir@19684 435 unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
keir@19684 436 unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
keir@19684 437
keir@19684 438 if (tmp >= RADIX_TREE_INDEX_BITS)
keir@19684 439 index = ~0UL;
keir@19684 440 return index;
keir@19684 441 }
keir@19684 442
keir@21436 443 void __init radix_tree_init(void)
keir@19684 444 {
keir@19684 445 unsigned int i;
keir@19684 446
keir@19684 447 for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
keir@19684 448 height_to_maxindex[i] = __maxindex(i);
keir@19684 449 }