ia64/linux-2.6.18-xen.hg

view lib/radix-tree.c @ 897:329ea0ccb344

balloon: try harder to balloon up under memory pressure.

Currently if the balloon driver is unable to increase the guest's
reservation it assumes the failure was due to reaching its full
allocation, gives up on the ballooning operation and records the limit
it reached as the "hard limit". The driver will not try again until
the target is set again (even to the same value).

However it is possible that ballooning has in fact failed due to
memory pressure in the host and therefore it is desirable to keep
attempting to reach the target in case memory becomes available. The
most likely scenario is that some guests are ballooning down while
others are ballooning up and therefore there is temporary memory
pressure while things stabilise. You would not expect a well behaved
toolstack to ask a domain to balloon to more than its allocation nor
would you expect it to deliberately over-commit memory by setting
balloon targets which exceed the total host memory.

This patch drops the concept of a hard limit and causes the balloon
driver to retry increasing the reservation on a timer in the same
manner as when decreasing the reservation.

Also if we partially succeed in increasing the reservation
(i.e. receive less pages than we asked for) then we may as well keep
those pages rather than returning them to Xen.

Signed-off-by: Ian Campbell <ian.campbell@citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Fri Jun 05 14:01:20 2009 +0100 (2009-06-05)
parents 831230e53067
children
line source
1 /*
2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
4 * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com>
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License as
8 * published by the Free Software Foundation; either version 2, or (at
9 * your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 */
21 #include <linux/errno.h>
22 #include <linux/init.h>
23 #include <linux/kernel.h>
24 #include <linux/module.h>
25 #include <linux/radix-tree.h>
26 #include <linux/percpu.h>
27 #include <linux/slab.h>
28 #include <linux/notifier.h>
29 #include <linux/cpu.h>
30 #include <linux/gfp.h>
31 #include <linux/string.h>
32 #include <linux/bitops.h>
35 #ifdef __KERNEL__
36 #define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
37 #else
38 #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */
39 #endif
41 #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
42 #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
44 #define RADIX_TREE_TAG_LONGS \
45 ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
47 struct radix_tree_node {
48 unsigned int count;
49 void *slots[RADIX_TREE_MAP_SIZE];
50 unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
51 };
53 struct radix_tree_path {
54 struct radix_tree_node *node;
55 int offset;
56 };
58 #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
59 #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
61 static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly;
63 /*
64 * Radix tree node cache.
65 */
66 static kmem_cache_t *radix_tree_node_cachep;
68 /*
69 * Per-cpu pool of preloaded nodes
70 */
71 struct radix_tree_preload {
72 int nr;
73 struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH];
74 };
75 DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
77 static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
78 {
79 return root->gfp_mask & __GFP_BITS_MASK;
80 }
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 gfp_t gfp_mask = root_gfp_mask(root);
92 ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
93 if (ret == NULL && !(gfp_mask & __GFP_WAIT)) {
94 struct radix_tree_preload *rtp;
96 rtp = &__get_cpu_var(radix_tree_preloads);
97 if (rtp->nr) {
98 ret = rtp->nodes[rtp->nr - 1];
99 rtp->nodes[rtp->nr - 1] = NULL;
100 rtp->nr--;
101 }
102 }
103 return ret;
104 }
106 static inline void
107 radix_tree_node_free(struct radix_tree_node *node)
108 {
109 kmem_cache_free(radix_tree_node_cachep, node);
110 }
112 /*
113 * Load up this CPU's radix_tree_node buffer with sufficient objects to
114 * ensure that the addition of a single element in the tree cannot fail. On
115 * success, return zero, with preemption disabled. On error, return -ENOMEM
116 * with preemption not disabled.
117 */
118 int radix_tree_preload(gfp_t gfp_mask)
119 {
120 struct radix_tree_preload *rtp;
121 struct radix_tree_node *node;
122 int ret = -ENOMEM;
124 preempt_disable();
125 rtp = &__get_cpu_var(radix_tree_preloads);
126 while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
127 preempt_enable();
128 node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
129 if (node == NULL)
130 goto out;
131 preempt_disable();
132 rtp = &__get_cpu_var(radix_tree_preloads);
133 if (rtp->nr < ARRAY_SIZE(rtp->nodes))
134 rtp->nodes[rtp->nr++] = node;
135 else
136 kmem_cache_free(radix_tree_node_cachep, node);
137 }
138 ret = 0;
139 out:
140 return ret;
141 }
143 static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
144 int offset)
145 {
146 __set_bit(offset, node->tags[tag]);
147 }
149 static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
150 int offset)
151 {
152 __clear_bit(offset, node->tags[tag]);
153 }
155 static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
156 int offset)
157 {
158 return test_bit(offset, node->tags[tag]);
159 }
161 static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
162 {
163 root->gfp_mask |= (1 << (tag + __GFP_BITS_SHIFT));
164 }
167 static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
168 {
169 root->gfp_mask &= ~(1 << (tag + __GFP_BITS_SHIFT));
170 }
172 static inline void root_tag_clear_all(struct radix_tree_root *root)
173 {
174 root->gfp_mask &= __GFP_BITS_MASK;
175 }
177 static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
178 {
179 return root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
180 }
182 /*
183 * Returns 1 if any slot in the node has this tag set.
184 * Otherwise returns 0.
185 */
186 static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
187 {
188 int idx;
189 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
190 if (node->tags[tag][idx])
191 return 1;
192 }
193 return 0;
194 }
196 /*
197 * Return the maximum key which can be store into a
198 * radix tree with height HEIGHT.
199 */
200 static inline unsigned long radix_tree_maxindex(unsigned int height)
201 {
202 return height_to_maxindex[height];
203 }
205 /*
206 * Extend a radix tree so it can store key @index.
207 */
208 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
209 {
210 struct radix_tree_node *node;
211 unsigned int height;
212 int tag;
214 /* Figure out what the height should be. */
215 height = root->height + 1;
216 while (index > radix_tree_maxindex(height))
217 height++;
219 if (root->rnode == NULL) {
220 root->height = height;
221 goto out;
222 }
224 do {
225 if (!(node = radix_tree_node_alloc(root)))
226 return -ENOMEM;
228 /* Increase the height. */
229 node->slots[0] = root->rnode;
231 /* Propagate the aggregated tag info into the new root */
232 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
233 if (root_tag_get(root, tag))
234 tag_set(node, tag, 0);
235 }
237 node->count = 1;
238 root->rnode = node;
239 root->height++;
240 } while (height > root->height);
241 out:
242 return 0;
243 }
245 /**
246 * radix_tree_insert - insert into a radix tree
247 * @root: radix tree root
248 * @index: index key
249 * @item: item to insert
250 *
251 * Insert an item into the radix tree at position @index.
252 */
253 int radix_tree_insert(struct radix_tree_root *root,
254 unsigned long index, void *item)
255 {
256 struct radix_tree_node *node = NULL, *slot;
257 unsigned int height, shift;
258 int offset;
259 int error;
261 /* Make sure the tree is high enough. */
262 if (index > radix_tree_maxindex(root->height)) {
263 error = radix_tree_extend(root, index);
264 if (error)
265 return error;
266 }
268 slot = root->rnode;
269 height = root->height;
270 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
272 offset = 0; /* uninitialised var warning */
273 while (height > 0) {
274 if (slot == NULL) {
275 /* Have to add a child node. */
276 if (!(slot = radix_tree_node_alloc(root)))
277 return -ENOMEM;
278 if (node) {
279 node->slots[offset] = slot;
280 node->count++;
281 } else
282 root->rnode = slot;
283 }
285 /* Go a level down */
286 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
287 node = slot;
288 slot = node->slots[offset];
289 shift -= RADIX_TREE_MAP_SHIFT;
290 height--;
291 }
293 if (slot != NULL)
294 return -EEXIST;
296 if (node) {
297 node->count++;
298 node->slots[offset] = item;
299 BUG_ON(tag_get(node, 0, offset));
300 BUG_ON(tag_get(node, 1, offset));
301 } else {
302 root->rnode = item;
303 BUG_ON(root_tag_get(root, 0));
304 BUG_ON(root_tag_get(root, 1));
305 }
307 return 0;
308 }
309 EXPORT_SYMBOL(radix_tree_insert);
311 static inline void **__lookup_slot(struct radix_tree_root *root,
312 unsigned long index)
313 {
314 unsigned int height, shift;
315 struct radix_tree_node **slot;
317 height = root->height;
319 if (index > radix_tree_maxindex(height))
320 return NULL;
322 if (height == 0 && root->rnode)
323 return (void **)&root->rnode;
325 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
326 slot = &root->rnode;
328 while (height > 0) {
329 if (*slot == NULL)
330 return NULL;
332 slot = (struct radix_tree_node **)
333 ((*slot)->slots +
334 ((index >> shift) & RADIX_TREE_MAP_MASK));
335 shift -= RADIX_TREE_MAP_SHIFT;
336 height--;
337 }
339 return (void **)slot;
340 }
342 /**
343 * radix_tree_lookup_slot - lookup a slot in a radix tree
344 * @root: radix tree root
345 * @index: index key
346 *
347 * Lookup the slot corresponding to the position @index in the radix tree
348 * @root. This is useful for update-if-exists operations.
349 */
350 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
351 {
352 return __lookup_slot(root, index);
353 }
354 EXPORT_SYMBOL(radix_tree_lookup_slot);
356 /**
357 * radix_tree_lookup - perform lookup operation on a radix tree
358 * @root: radix tree root
359 * @index: index key
360 *
361 * Lookup the item at the position @index in the radix tree @root.
362 */
363 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
364 {
365 void **slot;
367 slot = __lookup_slot(root, index);
368 return slot != NULL ? *slot : NULL;
369 }
370 EXPORT_SYMBOL(radix_tree_lookup);
372 /**
373 * radix_tree_tag_set - set a tag on a radix tree node
374 * @root: radix tree root
375 * @index: index key
376 * @tag: tag index
377 *
378 * Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
379 * corresponding to @index in the radix tree. From
380 * the root all the way down to the leaf node.
381 *
382 * Returns the address of the tagged item. Setting a tag on a not-present
383 * item is a bug.
384 */
385 void *radix_tree_tag_set(struct radix_tree_root *root,
386 unsigned long index, unsigned int tag)
387 {
388 unsigned int height, shift;
389 struct radix_tree_node *slot;
391 height = root->height;
392 BUG_ON(index > radix_tree_maxindex(height));
394 slot = root->rnode;
395 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
397 while (height > 0) {
398 int offset;
400 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
401 if (!tag_get(slot, tag, offset))
402 tag_set(slot, tag, offset);
403 slot = slot->slots[offset];
404 BUG_ON(slot == NULL);
405 shift -= RADIX_TREE_MAP_SHIFT;
406 height--;
407 }
409 /* set the root's tag bit */
410 if (slot && !root_tag_get(root, tag))
411 root_tag_set(root, tag);
413 return slot;
414 }
415 EXPORT_SYMBOL(radix_tree_tag_set);
417 /**
418 * radix_tree_tag_clear - clear a tag on a radix tree node
419 * @root: radix tree root
420 * @index: index key
421 * @tag: tag index
422 *
423 * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
424 * corresponding to @index in the radix tree. If
425 * this causes the leaf node to have no tags set then clear the tag in the
426 * next-to-leaf node, etc.
427 *
428 * Returns the address of the tagged item on success, else NULL. ie:
429 * has the same return value and semantics as radix_tree_lookup().
430 */
431 void *radix_tree_tag_clear(struct radix_tree_root *root,
432 unsigned long index, unsigned int tag)
433 {
434 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
435 struct radix_tree_node *slot = NULL;
436 unsigned int height, shift;
438 height = root->height;
439 if (index > radix_tree_maxindex(height))
440 goto out;
442 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
443 pathp->node = NULL;
444 slot = root->rnode;
446 while (height > 0) {
447 int offset;
449 if (slot == NULL)
450 goto out;
452 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
453 pathp[1].offset = offset;
454 pathp[1].node = slot;
455 slot = slot->slots[offset];
456 pathp++;
457 shift -= RADIX_TREE_MAP_SHIFT;
458 height--;
459 }
461 if (slot == NULL)
462 goto out;
464 while (pathp->node) {
465 if (!tag_get(pathp->node, tag, pathp->offset))
466 goto out;
467 tag_clear(pathp->node, tag, pathp->offset);
468 if (any_tag_set(pathp->node, tag))
469 goto out;
470 pathp--;
471 }
473 /* clear the root's tag bit */
474 if (root_tag_get(root, tag))
475 root_tag_clear(root, tag);
477 out:
478 return slot;
479 }
480 EXPORT_SYMBOL(radix_tree_tag_clear);
482 #ifndef __KERNEL__ /* Only the test harness uses this at present */
483 /**
484 * radix_tree_tag_get - get a tag on a radix tree node
485 * @root: radix tree root
486 * @index: index key
487 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
488 *
489 * Return values:
490 *
491 * 0: tag not present or not set
492 * 1: tag set
493 */
494 int radix_tree_tag_get(struct radix_tree_root *root,
495 unsigned long index, unsigned int tag)
496 {
497 unsigned int height, shift;
498 struct radix_tree_node *slot;
499 int saw_unset_tag = 0;
501 height = root->height;
502 if (index > radix_tree_maxindex(height))
503 return 0;
505 /* check the root's tag bit */
506 if (!root_tag_get(root, tag))
507 return 0;
509 if (height == 0)
510 return 1;
512 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
513 slot = root->rnode;
515 for ( ; ; ) {
516 int offset;
518 if (slot == NULL)
519 return 0;
521 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
523 /*
524 * This is just a debug check. Later, we can bale as soon as
525 * we see an unset tag.
526 */
527 if (!tag_get(slot, tag, offset))
528 saw_unset_tag = 1;
529 if (height == 1) {
530 int ret = tag_get(slot, tag, offset);
532 BUG_ON(ret && saw_unset_tag);
533 return !!ret;
534 }
535 slot = slot->slots[offset];
536 shift -= RADIX_TREE_MAP_SHIFT;
537 height--;
538 }
539 }
540 EXPORT_SYMBOL(radix_tree_tag_get);
541 #endif
543 static unsigned int
544 __lookup(struct radix_tree_root *root, void **results, unsigned long index,
545 unsigned int max_items, unsigned long *next_index)
546 {
547 unsigned int nr_found = 0;
548 unsigned int shift, height;
549 struct radix_tree_node *slot;
550 unsigned long i;
552 height = root->height;
553 if (height == 0) {
554 if (root->rnode && index == 0)
555 results[nr_found++] = root->rnode;
556 goto out;
557 }
559 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
560 slot = root->rnode;
562 for ( ; height > 1; height--) {
564 for (i = (index >> shift) & RADIX_TREE_MAP_MASK ;
565 i < RADIX_TREE_MAP_SIZE; i++) {
566 if (slot->slots[i] != NULL)
567 break;
568 index &= ~((1UL << shift) - 1);
569 index += 1UL << shift;
570 if (index == 0)
571 goto out; /* 32-bit wraparound */
572 }
573 if (i == RADIX_TREE_MAP_SIZE)
574 goto out;
576 shift -= RADIX_TREE_MAP_SHIFT;
577 slot = slot->slots[i];
578 }
580 /* Bottom level: grab some items */
581 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
582 index++;
583 if (slot->slots[i]) {
584 results[nr_found++] = slot->slots[i];
585 if (nr_found == max_items)
586 goto out;
587 }
588 }
589 out:
590 *next_index = index;
591 return nr_found;
592 }
594 /**
595 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
596 * @root: radix tree root
597 * @results: where the results of the lookup are placed
598 * @first_index: start the lookup from this key
599 * @max_items: place up to this many items at *results
600 *
601 * Performs an index-ascending scan of the tree for present items. Places
602 * them at *@results and returns the number of items which were placed at
603 * *@results.
604 *
605 * The implementation is naive.
606 */
607 unsigned int
608 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
609 unsigned long first_index, unsigned int max_items)
610 {
611 const unsigned long max_index = radix_tree_maxindex(root->height);
612 unsigned long cur_index = first_index;
613 unsigned int ret = 0;
615 while (ret < max_items) {
616 unsigned int nr_found;
617 unsigned long next_index; /* Index of next search */
619 if (cur_index > max_index)
620 break;
621 nr_found = __lookup(root, results + ret, cur_index,
622 max_items - ret, &next_index);
623 ret += nr_found;
624 if (next_index == 0)
625 break;
626 cur_index = next_index;
627 }
628 return ret;
629 }
630 EXPORT_SYMBOL(radix_tree_gang_lookup);
632 /*
633 * FIXME: the two tag_get()s here should use find_next_bit() instead of
634 * open-coding the search.
635 */
636 static unsigned int
637 __lookup_tag(struct radix_tree_root *root, void **results, unsigned long index,
638 unsigned int max_items, unsigned long *next_index, unsigned int tag)
639 {
640 unsigned int nr_found = 0;
641 unsigned int shift;
642 unsigned int height = root->height;
643 struct radix_tree_node *slot;
645 if (height == 0) {
646 if (root->rnode && index == 0)
647 results[nr_found++] = root->rnode;
648 goto out;
649 }
651 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
652 slot = root->rnode;
654 do {
655 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;
657 for ( ; i < RADIX_TREE_MAP_SIZE; i++) {
658 if (tag_get(slot, tag, i)) {
659 BUG_ON(slot->slots[i] == NULL);
660 break;
661 }
662 index &= ~((1UL << shift) - 1);
663 index += 1UL << shift;
664 if (index == 0)
665 goto out; /* 32-bit wraparound */
666 }
667 if (i == RADIX_TREE_MAP_SIZE)
668 goto out;
669 height--;
670 if (height == 0) { /* Bottom level: grab some items */
671 unsigned long j = index & RADIX_TREE_MAP_MASK;
673 for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
674 index++;
675 if (tag_get(slot, tag, j)) {
676 BUG_ON(slot->slots[j] == NULL);
677 results[nr_found++] = slot->slots[j];
678 if (nr_found == max_items)
679 goto out;
680 }
681 }
682 }
683 shift -= RADIX_TREE_MAP_SHIFT;
684 slot = slot->slots[i];
685 } while (height > 0);
686 out:
687 *next_index = index;
688 return nr_found;
689 }
691 /**
692 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
693 * based on a tag
694 * @root: radix tree root
695 * @results: where the results of the lookup are placed
696 * @first_index: start the lookup from this key
697 * @max_items: place up to this many items at *results
698 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
699 *
700 * Performs an index-ascending scan of the tree for present items which
701 * have the tag indexed by @tag set. Places the items at *@results and
702 * returns the number of items which were placed at *@results.
703 */
704 unsigned int
705 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
706 unsigned long first_index, unsigned int max_items,
707 unsigned int tag)
708 {
709 const unsigned long max_index = radix_tree_maxindex(root->height);
710 unsigned long cur_index = first_index;
711 unsigned int ret = 0;
713 /* check the root's tag bit */
714 if (!root_tag_get(root, tag))
715 return 0;
717 while (ret < max_items) {
718 unsigned int nr_found;
719 unsigned long next_index; /* Index of next search */
721 if (cur_index > max_index)
722 break;
723 nr_found = __lookup_tag(root, results + ret, cur_index,
724 max_items - ret, &next_index, tag);
725 ret += nr_found;
726 if (next_index == 0)
727 break;
728 cur_index = next_index;
729 }
730 return ret;
731 }
732 EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
734 /**
735 * radix_tree_shrink - shrink height of a radix tree to minimal
736 * @root radix tree root
737 */
738 static inline void radix_tree_shrink(struct radix_tree_root *root)
739 {
740 /* try to shrink tree height */
741 while (root->height > 0 &&
742 root->rnode->count == 1 &&
743 root->rnode->slots[0]) {
744 struct radix_tree_node *to_free = root->rnode;
746 root->rnode = to_free->slots[0];
747 root->height--;
748 /* must only free zeroed nodes into the slab */
749 tag_clear(to_free, 0, 0);
750 tag_clear(to_free, 1, 0);
751 to_free->slots[0] = NULL;
752 to_free->count = 0;
753 radix_tree_node_free(to_free);
754 }
755 }
757 /**
758 * radix_tree_delete - delete an item from a radix tree
759 * @root: radix tree root
760 * @index: index key
761 *
762 * Remove the item at @index from the radix tree rooted at @root.
763 *
764 * Returns the address of the deleted item, or NULL if it was not present.
765 */
766 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
767 {
768 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
769 struct radix_tree_node *slot = NULL;
770 unsigned int height, shift;
771 int tag;
772 int offset;
774 height = root->height;
775 if (index > radix_tree_maxindex(height))
776 goto out;
778 slot = root->rnode;
779 if (height == 0 && root->rnode) {
780 root_tag_clear_all(root);
781 root->rnode = NULL;
782 goto out;
783 }
785 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
786 pathp->node = NULL;
788 do {
789 if (slot == NULL)
790 goto out;
792 pathp++;
793 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
794 pathp->offset = offset;
795 pathp->node = slot;
796 slot = slot->slots[offset];
797 shift -= RADIX_TREE_MAP_SHIFT;
798 height--;
799 } while (height > 0);
801 if (slot == NULL)
802 goto out;
804 /*
805 * Clear all tags associated with the just-deleted item
806 */
807 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
808 if (tag_get(pathp->node, tag, pathp->offset))
809 radix_tree_tag_clear(root, index, tag);
810 }
812 /* Now free the nodes we do not need anymore */
813 while (pathp->node) {
814 pathp->node->slots[pathp->offset] = NULL;
815 pathp->node->count--;
817 if (pathp->node->count) {
818 if (pathp->node == root->rnode)
819 radix_tree_shrink(root);
820 goto out;
821 }
823 /* Node with zero slots in use so free it */
824 radix_tree_node_free(pathp->node);
826 pathp--;
827 }
828 root_tag_clear_all(root);
829 root->height = 0;
830 root->rnode = NULL;
832 out:
833 return slot;
834 }
835 EXPORT_SYMBOL(radix_tree_delete);
837 /**
838 * radix_tree_tagged - test whether any items in the tree are tagged
839 * @root: radix tree root
840 * @tag: tag to test
841 */
842 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
843 {
844 return root_tag_get(root, tag);
845 }
846 EXPORT_SYMBOL(radix_tree_tagged);
848 static void
849 radix_tree_node_ctor(void *node, kmem_cache_t *cachep, unsigned long flags)
850 {
851 memset(node, 0, sizeof(struct radix_tree_node));
852 }
854 static __init unsigned long __maxindex(unsigned int height)
855 {
856 unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
857 unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
859 if (tmp >= RADIX_TREE_INDEX_BITS)
860 index = ~0UL;
861 return index;
862 }
864 static __init void radix_tree_init_maxindex(void)
865 {
866 unsigned int i;
868 for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
869 height_to_maxindex[i] = __maxindex(i);
870 }
872 #ifdef CONFIG_HOTPLUG_CPU
873 static int radix_tree_callback(struct notifier_block *nfb,
874 unsigned long action,
875 void *hcpu)
876 {
877 int cpu = (long)hcpu;
878 struct radix_tree_preload *rtp;
880 /* Free per-cpu pool of perloaded nodes */
881 if (action == CPU_DEAD) {
882 rtp = &per_cpu(radix_tree_preloads, cpu);
883 while (rtp->nr) {
884 kmem_cache_free(radix_tree_node_cachep,
885 rtp->nodes[rtp->nr-1]);
886 rtp->nodes[rtp->nr-1] = NULL;
887 rtp->nr--;
888 }
889 }
890 return NOTIFY_OK;
891 }
892 #endif /* CONFIG_HOTPLUG_CPU */
894 void __init radix_tree_init(void)
895 {
896 radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
897 sizeof(struct radix_tree_node), 0,
898 SLAB_PANIC, radix_tree_node_ctor, NULL);
899 radix_tree_init_maxindex();
900 hotcpu_notifier(radix_tree_callback, 0);
901 }