debuggers.hg

view xen/common/radix-tree.c @ 21436:6348b2ab5c39

Remove many uses of cpu_possible_map and iterators over NR_CPUS.

The significant remaining culprits for x86 are credit2, hpet, and
percpu-area subsystems. To be dealt with in a separate patch.

Signed-off-by: Keir Fraser <keir.fraser@citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Fri May 14 20:37:02 2010 +0100 (2010-05-14)
parents f210a633571c
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 /*
22 * Copyright (C) 2009 adaption for Xen tmem by Dan Magenheimer, Oracle Corp.
23 * Changed:
24 * o Linux 2.6.18 source used (prior to read-copy-update addition)
25 * o constants and data structures moved out to radix-tree.h header
26 * o tagging code removed
27 * o radix_tree_insert has func parameter for dynamic data struct allocation
28 * o radix_tree_destroy added (including recursive helper function)
29 * o __init functions must be called explicitly
30 * o other include files adapted to Xen
31 */
33 #include <xen/config.h>
34 #include <xen/init.h>
35 #include <xen/lib.h>
36 #include <xen/types.h>
37 #include <xen/errno.h>
38 #include <xen/radix-tree.h>
39 #include <asm/cache.h>
41 static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;
43 /*
44 * Return the maximum key which can be store into a
45 * radix tree with height HEIGHT.
46 */
47 static inline unsigned long radix_tree_maxindex(unsigned int height)
48 {
49 return height_to_maxindex[height];
50 }
52 /*
53 * Extend a radix tree so it can store key @index.
54 */
55 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index,
56 struct radix_tree_node *(*node_alloc)(void *), void *arg)
57 {
58 struct radix_tree_node *node;
59 unsigned int height;
61 /* Figure out what the height should be. */
62 height = root->height + 1;
63 if (index > radix_tree_maxindex(height))
64 while (index > radix_tree_maxindex(height))
65 height++;
67 if (root->rnode == NULL) {
68 root->height = height;
69 goto out;
70 }
72 do {
73 if (!(node = node_alloc(arg)))
74 return -ENOMEM;
76 /* Increase the height. */
77 node->slots[0] = root->rnode;
79 node->count = 1;
80 root->rnode = node;
81 root->height++;
82 } while (height > root->height);
83 out:
84 return 0;
85 }
87 /**
88 * radix_tree_insert - insert into a radix tree
89 * @root: radix tree root
90 * @index: index key
91 * @item: item to insert
92 *
93 * Insert an item into the radix tree at position @index.
94 */
95 int radix_tree_insert(struct radix_tree_root *root, unsigned long index,
96 void *item, struct radix_tree_node *(*node_alloc)(void *), void *arg)
97 {
98 struct radix_tree_node *node = NULL, *slot;
99 unsigned int height, shift;
100 int offset;
101 int error;
103 /* Make sure the tree is high enough. */
104 if (index > radix_tree_maxindex(root->height)) {
105 error = radix_tree_extend(root, index, node_alloc, arg);
106 if (error)
107 return error;
108 }
110 slot = root->rnode;
111 height = root->height;
112 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
114 offset = 0; /* uninitialised var warning */
115 while (height > 0) {
116 if (slot == NULL) {
117 /* Have to add a child node. */
118 if (!(slot = node_alloc(arg)))
119 return -ENOMEM;
120 if (node) {
122 node->slots[offset] = slot;
123 node->count++;
124 } else
125 root->rnode = slot;
126 }
128 /* Go a level down */
129 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
130 node = slot;
131 slot = node->slots[offset];
132 shift -= RADIX_TREE_MAP_SHIFT;
133 height--;
134 }
136 if (slot != NULL)
137 return -EEXIST;
139 if (node) {
140 node->count++;
141 node->slots[offset] = item;
142 } else {
143 root->rnode = item;
144 }
146 return 0;
147 }
148 EXPORT_SYMBOL(radix_tree_insert);
150 static inline void **__lookup_slot(struct radix_tree_root *root,
151 unsigned long index)
152 {
153 unsigned int height, shift;
154 struct radix_tree_node **slot;
156 height = root->height;
158 if (index > radix_tree_maxindex(height))
159 return NULL;
161 if (height == 0 && root->rnode)
162 return (void **)&root->rnode;
164 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
165 slot = &root->rnode;
167 while (height > 0) {
168 if (*slot == NULL)
169 return NULL;
171 slot = (struct radix_tree_node **)
172 ((*slot)->slots +
173 ((index >> shift) & RADIX_TREE_MAP_MASK));
174 shift -= RADIX_TREE_MAP_SHIFT;
175 height--;
176 }
178 return (void **)slot;
179 }
181 /**
182 * radix_tree_lookup_slot - lookup a slot in a radix tree
183 * @root: radix tree root
184 * @index: index key
185 *
186 * Lookup the slot corresponding to the position @index in the radix tree
187 * @root. This is useful for update-if-exists operations.
188 */
189 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
190 {
191 return __lookup_slot(root, index);
192 }
193 EXPORT_SYMBOL(radix_tree_lookup_slot);
195 /**
196 * radix_tree_lookup - perform lookup operation on a radix tree
197 * @root: radix tree root
198 * @index: index key
199 *
200 * Lookup the item at the position @index in the radix tree @root.
201 */
202 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
203 {
204 void **slot;
206 slot = __lookup_slot(root, index);
207 return slot != NULL ? *slot : NULL;
208 }
209 EXPORT_SYMBOL(radix_tree_lookup);
211 static unsigned int
212 __lookup(struct radix_tree_root *root, void **results, unsigned long index,
213 unsigned int max_items, unsigned long *next_index)
214 {
215 unsigned int nr_found = 0;
216 unsigned int shift, height;
217 struct radix_tree_node *slot;
218 unsigned long i;
220 height = root->height;
221 if (index > radix_tree_maxindex(height))
222 if (height == 0) {
223 if (root->rnode && index == 0)
224 results[nr_found++] = root->rnode;
225 goto out;
226 }
228 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
229 slot = root->rnode;
231 for ( ; height > 1; height--) {
233 for (i = (index >> shift) & RADIX_TREE_MAP_MASK ;
234 i < RADIX_TREE_MAP_SIZE; i++) {
235 if (slot->slots[i] != NULL)
236 break;
237 index &= ~((1UL << shift) - 1);
238 index += 1UL << shift;
239 if (index == 0)
240 goto out; /* 32-bit wraparound */
241 }
242 if (i == RADIX_TREE_MAP_SIZE)
243 goto out;
245 shift -= RADIX_TREE_MAP_SHIFT;
246 slot = slot->slots[i];
247 }
249 /* Bottom level: grab some items */
250 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
251 index++;
252 if (slot->slots[i]) {
253 results[nr_found++] = slot->slots[i];
254 if (nr_found == max_items)
255 goto out;
256 }
257 }
258 out:
259 *next_index = index;
260 return nr_found;
261 }
263 /**
264 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
265 * @root: radix tree root
266 * @results: where the results of the lookup are placed
267 * @first_index: start the lookup from this key
268 * @max_items: place up to this many items at *results
269 *
270 * Performs an index-ascending scan of the tree for present items. Places
271 * them at *@results and returns the number of items which were placed at
272 * *@results.
273 *
274 * The implementation is naive.
275 */
276 unsigned int
277 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
278 unsigned long first_index, unsigned int max_items)
279 {
280 const unsigned long max_index = radix_tree_maxindex(root->height);
281 unsigned long cur_index = first_index;
282 unsigned int ret = 0;
284 while (ret < max_items) {
285 unsigned int nr_found;
286 unsigned long next_index; /* Index of next search */
288 if (cur_index > max_index)
289 break;
290 nr_found = __lookup(root, results + ret, cur_index,
291 max_items - ret, &next_index);
292 ret += nr_found;
293 if (next_index == 0)
294 break;
295 cur_index = next_index;
296 }
297 return ret;
298 }
299 EXPORT_SYMBOL(radix_tree_gang_lookup);
301 /**
302 * radix_tree_shrink - shrink height of a radix tree to minimal
303 * @root radix tree root
304 */
305 static inline void radix_tree_shrink(struct radix_tree_root *root,
306 void (*node_free)(struct radix_tree_node *))
307 {
308 /* try to shrink tree height */
309 while (root->height > 0 &&
310 root->rnode->count == 1 &&
311 root->rnode->slots[0]) {
312 struct radix_tree_node *to_free = root->rnode;
314 root->rnode = to_free->slots[0];
315 root->height--;
316 to_free->slots[0] = NULL;
317 to_free->count = 0;
318 node_free(to_free);
319 }
320 }
322 /**
323 * radix_tree_delete - delete an item from a radix tree
324 * @root: radix tree root
325 * @index: index key
326 *
327 * Remove the item at @index from the radix tree rooted at @root.
328 *
329 * Returns the address of the deleted item, or NULL if it was not present.
330 */
331 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index,
332 void(*node_free)(struct radix_tree_node *))
333 {
334 struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
335 struct radix_tree_node *slot = NULL;
336 unsigned int height, shift;
337 int offset;
339 height = root->height;
340 if (index > radix_tree_maxindex(height))
341 goto out;
343 slot = root->rnode;
344 if (height == 0 && root->rnode) {
345 root->rnode = NULL;
346 goto out;
347 }
349 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
350 pathp->node = NULL;
352 do {
353 if (slot == NULL)
354 goto out;
356 pathp++;
357 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
358 pathp->offset = offset;
359 pathp->node = slot;
360 slot = slot->slots[offset];
361 shift -= RADIX_TREE_MAP_SHIFT;
362 height--;
363 } while (height > 0);
365 if (slot == NULL)
366 goto out;
368 /* Now free the nodes we do not need anymore */
369 while (pathp->node) {
370 pathp->node->slots[pathp->offset] = NULL;
371 pathp->node->count--;
373 if (pathp->node->count) {
374 if (pathp->node == root->rnode)
375 radix_tree_shrink(root, node_free);
376 goto out;
377 }
379 /* Node with zero slots in use so free it */
380 node_free(pathp->node);
382 pathp--;
383 }
384 root->height = 0;
385 root->rnode = NULL;
387 out:
388 return slot;
389 }
390 EXPORT_SYMBOL(radix_tree_delete);
392 static void
393 radix_tree_node_destroy(struct radix_tree_node *node, unsigned int height,
394 void (*slot_free)(void *), void (*node_free)(struct radix_tree_node *))
395 {
396 int i;
398 if (height == 0)
399 return;
400 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
401 if (node->slots[i]) {
402 if (height == 1) {
403 slot_free(node->slots[i]);
404 node->slots[i] = NULL;
405 continue;
406 }
407 radix_tree_node_destroy(node->slots[i], height-1,
408 slot_free, node_free);
409 node_free(node->slots[i]);
410 node->slots[i] = NULL;
411 }
412 }
413 }
415 void radix_tree_destroy(struct radix_tree_root *root,
416 void (*slot_free)(void *), void (*node_free)(struct radix_tree_node *))
417 {
418 if (root->rnode == NULL)
419 return;
420 if (root->height == 0)
421 slot_free(root->rnode);
422 else {
423 radix_tree_node_destroy(root->rnode, root->height,
424 slot_free, node_free);
425 node_free(root->rnode);
426 root->height = 0;
427 }
428 root->rnode = NULL;
429 /* caller must delete root if desired */
430 }
431 EXPORT_SYMBOL(radix_tree_destroy);
433 static unsigned long __init __maxindex(unsigned int height)
434 {
435 unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
436 unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
438 if (tmp >= RADIX_TREE_INDEX_BITS)
439 index = ~0UL;
440 return index;
441 }
443 void __init radix_tree_init(void)
444 {
445 unsigned int i;
447 for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
448 height_to_maxindex[i] = __maxindex(i);
449 }