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