1/*
2 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org>
3 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 * SUCH DAMAGE.
26 *
27 */
28
29
30/*
31 * Radix tree implementation.
32 */
33
34#include <sys/cdefs.h>
35
36#include <sys/param.h>
37#include <sys/conf.h>
38#include <sys/systm.h>
39#include <sys/kernel.h>
40#include <sys/malloc.h>
41#include <sys/queue.h>
42#include <sys/param.h>
43#include <sys/lock.h>
44#include <sys/mutex.h>
45#include <sys/ktr.h>
46#include <vm/uma.h>
47#include <vm/vm.h>
48#include <vm/vm_param.h>
49#include <vm/vm_extern.h>
50#include <vm/vm_kern.h>
51#include <vm/vm_page.h>
52#include <vm/vm_radix.h>
53#include <vm/vm_object.h>
54
55#include <sys/kdb.h>
56
57CTASSERT(sizeof(struct vm_radix_node) < PAGE_SIZE);
58
59static uma_zone_t vm_radix_node_zone;
60
61#ifndef UMA_MD_SMALL_ALLOC
62static void *
63vm_radix_node_zone_allocf(uma_zone_t zone, int size, uint8_t *flags, int wait)
64{
65 vm_offset_t addr;
66 vm_page_t m;
67 int pflags;
68
69 /* Inform UMA that this allocator uses kernel_map. */
70 *flags = UMA_SLAB_KERNEL;
71
72 pflags = VM_ALLOC_WIRED | VM_ALLOC_NOOBJ;
73
74 /*
75 * As kmem_alloc_nofault() can however fail, let just assume that
76 * M_NOWAIT is on and act accordingly.
77 */
78 pflags |= ((wait & M_USE_RESERVE) != 0) ? VM_ALLOC_INTERRUPT :
79 VM_ALLOC_SYSTEM;
80 if ((wait & M_ZERO) != 0)
81 pflags |= VM_ALLOC_ZERO;
82 addr = kmem_alloc_nofault(kernel_map, size);
83 if (addr == 0)
84 return (NULL);
85
86 /* Just one page allocation is assumed here. */
87 m = vm_page_alloc(NULL, OFF_TO_IDX(addr - VM_MIN_KERNEL_ADDRESS),
88 pflags);
89 if (m == NULL) {
90 kmem_free(kernel_map, addr, size);
91 return (NULL);
92 }
93 if ((wait & M_ZERO) != 0 && (m->flags & PG_ZERO) == 0)
94 pmap_zero_page(m);
95 pmap_qenter(addr, &m, 1);
96 return ((void *)addr);
97}
98
99static void
100vm_radix_node_zone_freef(void *item, int size, uint8_t flags)
101{
102 vm_page_t m;
103 vm_offset_t voitem;
104
105 MPASS((flags & UMA_SLAB_KERNEL) != 0);
106
107 /* Just one page allocation is assumed here. */
108 voitem = (vm_offset_t)item;
109 m = PHYS_TO_VM_PAGE(pmap_kextract(voitem));
110 pmap_qremove(voitem, 1);
111 vm_page_free(m);
112 kmem_free(kernel_map, voitem, size);
113}
114
115static void
116init_vm_radix_alloc(void *dummy __unused)
117{
118
119 uma_zone_set_allocf(vm_radix_node_zone, vm_radix_node_zone_allocf);
120 uma_zone_set_freef(vm_radix_node_zone, vm_radix_node_zone_freef);
121}
122SYSINIT(vm_radix, SI_SUB_KMEM, SI_ORDER_SECOND, init_vm_radix_alloc, NULL);
123#endif
124
125/*
126 * Radix node zone destructor.
127 */
128#ifdef INVARIANTS
129static void
130vm_radix_node_zone_dtor(void *mem, int size, void *arg)
131{
132 struct vm_radix_node *rnode;
133
134 rnode = mem;
135 KASSERT(rnode->rn_count == 0,
136 ("vm_radix_node_put: Freeing a node with %d children\n",
137 rnode->rn_count));
138}
139#endif
140
141/*
142 * Allocate a radix node. Initializes all elements to 0.
143 */
144static __inline struct vm_radix_node *
145vm_radix_node_get(void)
146{
147
148 return (uma_zalloc(vm_radix_node_zone, M_NOWAIT | M_ZERO));
149}
150
151/*
152 * Free radix node.
153 */
154static __inline void
155vm_radix_node_put(struct vm_radix_node *rnode)
156{
157
158 uma_zfree(vm_radix_node_zone, rnode);
159}
160
161/*
162 * Return the position in the array for a given level.
163 */
164static __inline int
165vm_radix_slot(vm_pindex_t index, int level)
166{
167
168 return ((index >> (level * VM_RADIX_WIDTH)) & VM_RADIX_MASK);
169}
170
171void
172vm_radix_init(void)
173{
174
175 vm_radix_node_zone = uma_zcreate("RADIX NODE",
176 sizeof(struct vm_radix_node), NULL,
177#ifdef INVARIANTS
178 vm_radix_node_zone_dtor,
179#else
180 NULL,
181#endif
182 NULL, NULL, VM_RADIX_HEIGHT, UMA_ZONE_VM);
183}
184
185/*
186 * Extract the root node and height from a radix tree with a single load.
187 */
188static __inline int
189vm_radix_height(struct vm_radix *rtree, struct vm_radix_node **rnode)
190{
191 uintptr_t root;
192 int height;
193
194 root = rtree->rt_root;
195 height = root & VM_RADIX_HEIGHT;
196 *rnode = (struct vm_radix_node *)(root - height);
197 return (height);
198}
199
200
201/*
202 * Set the root node and height for a radix tree.
203 */
204static inline void
205vm_radix_setroot(struct vm_radix *rtree, struct vm_radix_node *rnode,
206 int height)
207{
208 uintptr_t root;
209
210 root = (uintptr_t)rnode | height;
211 rtree->rt_root = root;
212}
213
214static inline void *
215vm_radix_match(void *child, int color)
216{
217 uintptr_t c;
218
219 c = (uintptr_t)child;
220
221 if ((c & color) == 0)
222 return (NULL);
223 return ((void *)(c & ~VM_RADIX_FLAGS));
224}
225
226static void
227vm_radix_reclaim_allnodes_internal(struct vm_radix_node *rnode, int level)
228{
229 int slot;
230
231 MPASS(rnode != NULL && level >= 0);
232
233 /*
234 * Level 0 just contains pages as children, thus make it a special
235 * case, free the node and return.
236 */
237 if (level == 0) {
238 CTR2(KTR_VM, "reclaiming: node %p, level %d", rnode, level);
239 rnode->rn_count = 0;
240 vm_radix_node_put(rnode);
241 return;
242 }
243 for (slot = 0; slot < VM_RADIX_COUNT && rnode->rn_count != 0; slot++) {
244 if (rnode->rn_child[slot] == NULL)
245 continue;
246 CTR3(KTR_VM,
247 "reclaiming: node %p, level %d recursing in slot %d",
248 rnode, level, slot);
249 vm_radix_reclaim_allnodes_internal(rnode->rn_child[slot],
250 level - 1);
251 rnode->rn_count--;
252 }
253 MPASS(rnode->rn_count == 0);
254 CTR2(KTR_VM, "reclaiming: node %p, level %d", rnode, level);
255 vm_radix_node_put(rnode);
256}
257
258/*
259 * Inserts the key-value pair in to the radix tree. Returns errno.
260 * Panics if the key already exists.
261 */
262int
263vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val)
264{
265 struct vm_radix_node *rnode;
266 struct vm_radix_node *root;
267 int level;
268 int slot;
269
270 CTR3(KTR_VM,
271 "insert: tree %p, index %ju, val %p", rtree, (uintmax_t)index, val);
272 if (index == -1)
273 panic("vm_radix_insert: -1 is not a valid index.\n");
274 level = vm_radix_height(rtree, &root);
275 /*
276 * Increase the height by adding nodes at the root until
277 * there is sufficient space.
278 */
279 while (level == 0 || index > VM_RADIX_MAX(level)) {
280 CTR3(KTR_VM, "insert: expanding %ju > %ju height %d",
281 (uintmax_t)index, (uintmax_t)VM_RADIX_MAX(level), level);
282 level++;
283 KASSERT(level <= VM_RADIX_LIMIT,
284 ("vm_radix_insert: Tree %p height %d too tall",
285 rtree, level));
286 /*
287 * Only allocate tree nodes if they are needed.
288 */
289 if (root == NULL || root->rn_count != 0) {
290 rnode = vm_radix_node_get();
291 if (rnode == NULL) {
292 CTR4(KTR_VM,
293 "insert: tree %p, root %p, index: %ju, level: %d ENOMEM",
294 rtree, root, (uintmax_t)index, level);
295 return (ENOMEM);
296 }
297 /*
298 * Store the new pointer with a memory barrier so
299 * that it is visible before the new root.
300 */
301 if (root) {
302 atomic_store_rel_ptr((volatile uintptr_t *)
303 &rnode->rn_child[0], (uintptr_t)root);
304 rnode->rn_count = 1;
305 }
306 root = rnode;
307 }
308 vm_radix_setroot(rtree, root, level);
309 }
310
311 /* Now that the tree is tall enough, fill in the path to the index. */
312 rnode = root;
313 for (level = level - 1; level > 0; level--) {
314 slot = vm_radix_slot(index, level);
315 /* Add the required intermidiate nodes. */
316 if (rnode->rn_child[slot] == NULL) {
317 rnode->rn_child[slot] = vm_radix_node_get();
318 if (rnode->rn_child[slot] == NULL) {
319 CTR5(KTR_VM,
320 "insert: tree %p, index %ju, level %d, slot %d, rnode %p ENOMEM",
321 rtree, (uintmax_t)index, level, slot,
322 rnode);
323 CTR4(KTR_VM,
324 "insert: tree %p, rnode %p, child %p, count %u ENOMEM",
325 rtree, rnode, rnode->rn_child[slot],
326 rnode->rn_count);
327 return (ENOMEM);
328 }
329 rnode->rn_count++;
330 }
331 CTR5(KTR_VM,
332 "insert: tree %p, index %ju, level %d, slot %d, rnode %p",
333 rtree, (uintmax_t)index, level, slot, rnode);
334 CTR4(KTR_VM,
335 "insert: tree %p, rnode %p, child %p, count %u",
336 rtree, rnode, rnode->rn_child[slot], rnode->rn_count);
337 rnode = rnode->rn_child[slot];
338 }
339
340 slot = vm_radix_slot(index, 0);
341 MPASS(rnode != NULL);
342 KASSERT(rnode->rn_child[slot] == NULL,
343 ("vm_radix_insert: Duplicate value %p at index: %lu\n",
344 rnode->rn_child[slot], (u_long)index));
345 val = (void *)((uintptr_t)val | VM_RADIX_BLACK);
346 rnode->rn_child[slot] = val;
347 atomic_add_32(&rnode->rn_count, 1);
348 CTR6(KTR_VM,
349 "insert: tree %p, index %ju, level %d, slot %d, rnode %p, count %u",
350 rtree, (uintmax_t)index, level, slot, rnode, rnode->rn_count);
351
352 return 0;
353}
354
355/*
356 * Returns the value stored at the index. If the index is not present
357 * NULL is returned.
358 */
359void *
360vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index, int color)
361{
362 struct vm_radix_node *rnode;
363 int slot;
364 int level;
365
366 level = vm_radix_height(rtree, &rnode);
367 if (index > VM_RADIX_MAX(level))
368 return NULL;
369 level--;
370 while (rnode) {
371 slot = vm_radix_slot(index, level);
372 CTR6(KTR_VM,
373 "lookup: tree %p, index %ju, level %d, slot %d, rnode %p, child %p",
374 rtree, (uintmax_t)index, level, slot, rnode,
375 rnode->rn_child[slot]);
376 if (level == 0)
377 return vm_radix_match(rnode->rn_child[slot], color);
378 rnode = rnode->rn_child[slot];
379 level--;
380 }
381 CTR2(KTR_VM, "lookup: tree %p, index %ju failed", rtree,
382 (uintmax_t)index);
383
384 return NULL;
385}
386
387void *
388vm_radix_color(struct vm_radix *rtree, vm_pindex_t index, int color)
389{
390 struct vm_radix_node *rnode;
391 uintptr_t child;
392 int slot;
393 int level;
394
395 level = vm_radix_height(rtree, &rnode);
396 if (index > VM_RADIX_MAX(level))
397 return NULL;
398 level--;
399 while (rnode) {
400 slot = vm_radix_slot(index, level);
401 CTR6(KTR_VM,
402 "color: tree %p, index %ju, level %d, slot %d, rnode %p, child %p",
403 rtree, (uintmax_t)index, level, slot, rnode,
404 rnode->rn_child[slot]);
405 if (level == 0)
406 break;
407 rnode = rnode->rn_child[slot];
408 level--;
409 }
410 if (rnode == NULL || rnode->rn_child[slot] == NULL)
411 return (NULL);
412 child = (uintptr_t)rnode->rn_child[slot];
413 child &= ~VM_RADIX_FLAGS;
414 rnode->rn_child[slot] = (void *)(child | color);
415
416 return (void *)child;
417}
418
419/*
420 * Find the first leaf with a valid node between *startp and end. Return
421 * the index of the first valid item in the leaf in *startp.
422 */
423static struct vm_radix_node *
424vm_radix_leaf(struct vm_radix *rtree, vm_pindex_t *startp, vm_pindex_t end)
425{
426 struct vm_radix_node *rnode;
427 vm_pindex_t start;
428 vm_pindex_t inc;
429 int slot;
430 int level;
431
432 start = *startp;
433restart:
434 level = vm_radix_height(rtree, &rnode);
435 if (start > VM_RADIX_MAX(level) || (end && start >= end)) {
436 rnode = NULL;
437 goto out;
438 }
439 /*
440 * Search the tree from the top for any leaf node holding an index
441 * between start and end.
442 */
443 for (level--; level; level--) {
444 slot = vm_radix_slot(start, level);
445 CTR6(KTR_VM,
446 "leaf: tree %p, index %ju, level %d, slot %d, rnode %p, child %p",
447 rtree, (uintmax_t)start, level, slot, rnode,
448 (rnode != NULL) ? rnode->rn_child[slot] : NULL);
449 if (rnode->rn_child[slot] != NULL) {
450 rnode = rnode->rn_child[slot];
451 continue;
452 }
453 /*
454 * Calculate how much to increment our index by
455 * based on the tree level. We must truncate the
456 * lower bits to start from the begnning of the
457 * next leaf.
458 */
459 inc = 1LL << (level * VM_RADIX_WIDTH);
460 start &= ~VM_RADIX_MAX(level);
| 1/*
2 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org>
3 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 * SUCH DAMAGE.
26 *
27 */
28
29
30/*
31 * Radix tree implementation.
32 */
33
34#include <sys/cdefs.h>
35
36#include <sys/param.h>
37#include <sys/conf.h>
38#include <sys/systm.h>
39#include <sys/kernel.h>
40#include <sys/malloc.h>
41#include <sys/queue.h>
42#include <sys/param.h>
43#include <sys/lock.h>
44#include <sys/mutex.h>
45#include <sys/ktr.h>
46#include <vm/uma.h>
47#include <vm/vm.h>
48#include <vm/vm_param.h>
49#include <vm/vm_extern.h>
50#include <vm/vm_kern.h>
51#include <vm/vm_page.h>
52#include <vm/vm_radix.h>
53#include <vm/vm_object.h>
54
55#include <sys/kdb.h>
56
57CTASSERT(sizeof(struct vm_radix_node) < PAGE_SIZE);
58
59static uma_zone_t vm_radix_node_zone;
60
61#ifndef UMA_MD_SMALL_ALLOC
62static void *
63vm_radix_node_zone_allocf(uma_zone_t zone, int size, uint8_t *flags, int wait)
64{
65 vm_offset_t addr;
66 vm_page_t m;
67 int pflags;
68
69 /* Inform UMA that this allocator uses kernel_map. */
70 *flags = UMA_SLAB_KERNEL;
71
72 pflags = VM_ALLOC_WIRED | VM_ALLOC_NOOBJ;
73
74 /*
75 * As kmem_alloc_nofault() can however fail, let just assume that
76 * M_NOWAIT is on and act accordingly.
77 */
78 pflags |= ((wait & M_USE_RESERVE) != 0) ? VM_ALLOC_INTERRUPT :
79 VM_ALLOC_SYSTEM;
80 if ((wait & M_ZERO) != 0)
81 pflags |= VM_ALLOC_ZERO;
82 addr = kmem_alloc_nofault(kernel_map, size);
83 if (addr == 0)
84 return (NULL);
85
86 /* Just one page allocation is assumed here. */
87 m = vm_page_alloc(NULL, OFF_TO_IDX(addr - VM_MIN_KERNEL_ADDRESS),
88 pflags);
89 if (m == NULL) {
90 kmem_free(kernel_map, addr, size);
91 return (NULL);
92 }
93 if ((wait & M_ZERO) != 0 && (m->flags & PG_ZERO) == 0)
94 pmap_zero_page(m);
95 pmap_qenter(addr, &m, 1);
96 return ((void *)addr);
97}
98
99static void
100vm_radix_node_zone_freef(void *item, int size, uint8_t flags)
101{
102 vm_page_t m;
103 vm_offset_t voitem;
104
105 MPASS((flags & UMA_SLAB_KERNEL) != 0);
106
107 /* Just one page allocation is assumed here. */
108 voitem = (vm_offset_t)item;
109 m = PHYS_TO_VM_PAGE(pmap_kextract(voitem));
110 pmap_qremove(voitem, 1);
111 vm_page_free(m);
112 kmem_free(kernel_map, voitem, size);
113}
114
115static void
116init_vm_radix_alloc(void *dummy __unused)
117{
118
119 uma_zone_set_allocf(vm_radix_node_zone, vm_radix_node_zone_allocf);
120 uma_zone_set_freef(vm_radix_node_zone, vm_radix_node_zone_freef);
121}
122SYSINIT(vm_radix, SI_SUB_KMEM, SI_ORDER_SECOND, init_vm_radix_alloc, NULL);
123#endif
124
125/*
126 * Radix node zone destructor.
127 */
128#ifdef INVARIANTS
129static void
130vm_radix_node_zone_dtor(void *mem, int size, void *arg)
131{
132 struct vm_radix_node *rnode;
133
134 rnode = mem;
135 KASSERT(rnode->rn_count == 0,
136 ("vm_radix_node_put: Freeing a node with %d children\n",
137 rnode->rn_count));
138}
139#endif
140
141/*
142 * Allocate a radix node. Initializes all elements to 0.
143 */
144static __inline struct vm_radix_node *
145vm_radix_node_get(void)
146{
147
148 return (uma_zalloc(vm_radix_node_zone, M_NOWAIT | M_ZERO));
149}
150
151/*
152 * Free radix node.
153 */
154static __inline void
155vm_radix_node_put(struct vm_radix_node *rnode)
156{
157
158 uma_zfree(vm_radix_node_zone, rnode);
159}
160
161/*
162 * Return the position in the array for a given level.
163 */
164static __inline int
165vm_radix_slot(vm_pindex_t index, int level)
166{
167
168 return ((index >> (level * VM_RADIX_WIDTH)) & VM_RADIX_MASK);
169}
170
171void
172vm_radix_init(void)
173{
174
175 vm_radix_node_zone = uma_zcreate("RADIX NODE",
176 sizeof(struct vm_radix_node), NULL,
177#ifdef INVARIANTS
178 vm_radix_node_zone_dtor,
179#else
180 NULL,
181#endif
182 NULL, NULL, VM_RADIX_HEIGHT, UMA_ZONE_VM);
183}
184
185/*
186 * Extract the root node and height from a radix tree with a single load.
187 */
188static __inline int
189vm_radix_height(struct vm_radix *rtree, struct vm_radix_node **rnode)
190{
191 uintptr_t root;
192 int height;
193
194 root = rtree->rt_root;
195 height = root & VM_RADIX_HEIGHT;
196 *rnode = (struct vm_radix_node *)(root - height);
197 return (height);
198}
199
200
201/*
202 * Set the root node and height for a radix tree.
203 */
204static inline void
205vm_radix_setroot(struct vm_radix *rtree, struct vm_radix_node *rnode,
206 int height)
207{
208 uintptr_t root;
209
210 root = (uintptr_t)rnode | height;
211 rtree->rt_root = root;
212}
213
214static inline void *
215vm_radix_match(void *child, int color)
216{
217 uintptr_t c;
218
219 c = (uintptr_t)child;
220
221 if ((c & color) == 0)
222 return (NULL);
223 return ((void *)(c & ~VM_RADIX_FLAGS));
224}
225
226static void
227vm_radix_reclaim_allnodes_internal(struct vm_radix_node *rnode, int level)
228{
229 int slot;
230
231 MPASS(rnode != NULL && level >= 0);
232
233 /*
234 * Level 0 just contains pages as children, thus make it a special
235 * case, free the node and return.
236 */
237 if (level == 0) {
238 CTR2(KTR_VM, "reclaiming: node %p, level %d", rnode, level);
239 rnode->rn_count = 0;
240 vm_radix_node_put(rnode);
241 return;
242 }
243 for (slot = 0; slot < VM_RADIX_COUNT && rnode->rn_count != 0; slot++) {
244 if (rnode->rn_child[slot] == NULL)
245 continue;
246 CTR3(KTR_VM,
247 "reclaiming: node %p, level %d recursing in slot %d",
248 rnode, level, slot);
249 vm_radix_reclaim_allnodes_internal(rnode->rn_child[slot],
250 level - 1);
251 rnode->rn_count--;
252 }
253 MPASS(rnode->rn_count == 0);
254 CTR2(KTR_VM, "reclaiming: node %p, level %d", rnode, level);
255 vm_radix_node_put(rnode);
256}
257
258/*
259 * Inserts the key-value pair in to the radix tree. Returns errno.
260 * Panics if the key already exists.
261 */
262int
263vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val)
264{
265 struct vm_radix_node *rnode;
266 struct vm_radix_node *root;
267 int level;
268 int slot;
269
270 CTR3(KTR_VM,
271 "insert: tree %p, index %ju, val %p", rtree, (uintmax_t)index, val);
272 if (index == -1)
273 panic("vm_radix_insert: -1 is not a valid index.\n");
274 level = vm_radix_height(rtree, &root);
275 /*
276 * Increase the height by adding nodes at the root until
277 * there is sufficient space.
278 */
279 while (level == 0 || index > VM_RADIX_MAX(level)) {
280 CTR3(KTR_VM, "insert: expanding %ju > %ju height %d",
281 (uintmax_t)index, (uintmax_t)VM_RADIX_MAX(level), level);
282 level++;
283 KASSERT(level <= VM_RADIX_LIMIT,
284 ("vm_radix_insert: Tree %p height %d too tall",
285 rtree, level));
286 /*
287 * Only allocate tree nodes if they are needed.
288 */
289 if (root == NULL || root->rn_count != 0) {
290 rnode = vm_radix_node_get();
291 if (rnode == NULL) {
292 CTR4(KTR_VM,
293 "insert: tree %p, root %p, index: %ju, level: %d ENOMEM",
294 rtree, root, (uintmax_t)index, level);
295 return (ENOMEM);
296 }
297 /*
298 * Store the new pointer with a memory barrier so
299 * that it is visible before the new root.
300 */
301 if (root) {
302 atomic_store_rel_ptr((volatile uintptr_t *)
303 &rnode->rn_child[0], (uintptr_t)root);
304 rnode->rn_count = 1;
305 }
306 root = rnode;
307 }
308 vm_radix_setroot(rtree, root, level);
309 }
310
311 /* Now that the tree is tall enough, fill in the path to the index. */
312 rnode = root;
313 for (level = level - 1; level > 0; level--) {
314 slot = vm_radix_slot(index, level);
315 /* Add the required intermidiate nodes. */
316 if (rnode->rn_child[slot] == NULL) {
317 rnode->rn_child[slot] = vm_radix_node_get();
318 if (rnode->rn_child[slot] == NULL) {
319 CTR5(KTR_VM,
320 "insert: tree %p, index %ju, level %d, slot %d, rnode %p ENOMEM",
321 rtree, (uintmax_t)index, level, slot,
322 rnode);
323 CTR4(KTR_VM,
324 "insert: tree %p, rnode %p, child %p, count %u ENOMEM",
325 rtree, rnode, rnode->rn_child[slot],
326 rnode->rn_count);
327 return (ENOMEM);
328 }
329 rnode->rn_count++;
330 }
331 CTR5(KTR_VM,
332 "insert: tree %p, index %ju, level %d, slot %d, rnode %p",
333 rtree, (uintmax_t)index, level, slot, rnode);
334 CTR4(KTR_VM,
335 "insert: tree %p, rnode %p, child %p, count %u",
336 rtree, rnode, rnode->rn_child[slot], rnode->rn_count);
337 rnode = rnode->rn_child[slot];
338 }
339
340 slot = vm_radix_slot(index, 0);
341 MPASS(rnode != NULL);
342 KASSERT(rnode->rn_child[slot] == NULL,
343 ("vm_radix_insert: Duplicate value %p at index: %lu\n",
344 rnode->rn_child[slot], (u_long)index));
345 val = (void *)((uintptr_t)val | VM_RADIX_BLACK);
346 rnode->rn_child[slot] = val;
347 atomic_add_32(&rnode->rn_count, 1);
348 CTR6(KTR_VM,
349 "insert: tree %p, index %ju, level %d, slot %d, rnode %p, count %u",
350 rtree, (uintmax_t)index, level, slot, rnode, rnode->rn_count);
351
352 return 0;
353}
354
355/*
356 * Returns the value stored at the index. If the index is not present
357 * NULL is returned.
358 */
359void *
360vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index, int color)
361{
362 struct vm_radix_node *rnode;
363 int slot;
364 int level;
365
366 level = vm_radix_height(rtree, &rnode);
367 if (index > VM_RADIX_MAX(level))
368 return NULL;
369 level--;
370 while (rnode) {
371 slot = vm_radix_slot(index, level);
372 CTR6(KTR_VM,
373 "lookup: tree %p, index %ju, level %d, slot %d, rnode %p, child %p",
374 rtree, (uintmax_t)index, level, slot, rnode,
375 rnode->rn_child[slot]);
376 if (level == 0)
377 return vm_radix_match(rnode->rn_child[slot], color);
378 rnode = rnode->rn_child[slot];
379 level--;
380 }
381 CTR2(KTR_VM, "lookup: tree %p, index %ju failed", rtree,
382 (uintmax_t)index);
383
384 return NULL;
385}
386
387void *
388vm_radix_color(struct vm_radix *rtree, vm_pindex_t index, int color)
389{
390 struct vm_radix_node *rnode;
391 uintptr_t child;
392 int slot;
393 int level;
394
395 level = vm_radix_height(rtree, &rnode);
396 if (index > VM_RADIX_MAX(level))
397 return NULL;
398 level--;
399 while (rnode) {
400 slot = vm_radix_slot(index, level);
401 CTR6(KTR_VM,
402 "color: tree %p, index %ju, level %d, slot %d, rnode %p, child %p",
403 rtree, (uintmax_t)index, level, slot, rnode,
404 rnode->rn_child[slot]);
405 if (level == 0)
406 break;
407 rnode = rnode->rn_child[slot];
408 level--;
409 }
410 if (rnode == NULL || rnode->rn_child[slot] == NULL)
411 return (NULL);
412 child = (uintptr_t)rnode->rn_child[slot];
413 child &= ~VM_RADIX_FLAGS;
414 rnode->rn_child[slot] = (void *)(child | color);
415
416 return (void *)child;
417}
418
419/*
420 * Find the first leaf with a valid node between *startp and end. Return
421 * the index of the first valid item in the leaf in *startp.
422 */
423static struct vm_radix_node *
424vm_radix_leaf(struct vm_radix *rtree, vm_pindex_t *startp, vm_pindex_t end)
425{
426 struct vm_radix_node *rnode;
427 vm_pindex_t start;
428 vm_pindex_t inc;
429 int slot;
430 int level;
431
432 start = *startp;
433restart:
434 level = vm_radix_height(rtree, &rnode);
435 if (start > VM_RADIX_MAX(level) || (end && start >= end)) {
436 rnode = NULL;
437 goto out;
438 }
439 /*
440 * Search the tree from the top for any leaf node holding an index
441 * between start and end.
442 */
443 for (level--; level; level--) {
444 slot = vm_radix_slot(start, level);
445 CTR6(KTR_VM,
446 "leaf: tree %p, index %ju, level %d, slot %d, rnode %p, child %p",
447 rtree, (uintmax_t)start, level, slot, rnode,
448 (rnode != NULL) ? rnode->rn_child[slot] : NULL);
449 if (rnode->rn_child[slot] != NULL) {
450 rnode = rnode->rn_child[slot];
451 continue;
452 }
453 /*
454 * Calculate how much to increment our index by
455 * based on the tree level. We must truncate the
456 * lower bits to start from the begnning of the
457 * next leaf.
458 */
459 inc = 1LL << (level * VM_RADIX_WIDTH);
460 start &= ~VM_RADIX_MAX(level);
|
476 }
477 if (slot == VM_RADIX_COUNT)
478 goto restart;
479 }
480
481out:
482 *startp = start;
483 return (rnode);
484}
485
486
487
488/*
489 * Looks up as many as cnt values between start and end, and stores
490 * them in the caller allocated array out. The next index can be used
491 * to restart the scan. This optimizes forward scans in the tree.
492 */
493int
494vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start,
495 vm_pindex_t end, int color, void **out, int cnt, vm_pindex_t *next)
496{
497 struct vm_radix_node *rnode;
498 void *val;
499 int slot;
500 int outidx;
501
502 CTR3(KTR_VM, "lookupn: tree %p, start %ju, end %ju",
503 rtree, (uintmax_t)start, (uintmax_t)end);
504 if (rtree->rt_root == 0)
505 return (0);
506 outidx = 0;
507 while ((rnode = vm_radix_leaf(rtree, &start, end)) != NULL) {
508 slot = vm_radix_slot(start, 0);
509 for (; slot < VM_RADIX_COUNT; slot++, start++) {
510 if (end != 0 && start >= end)
511 goto out;
512 val = vm_radix_match(rnode->rn_child[slot], color);
513 if (val == NULL)
514 continue;
515 CTR4(KTR_VM,
516 "lookupn: tree %p index %ju slot %d found child %p",
517 rtree, (uintmax_t)start, slot, val);
518 out[outidx] = val;
519 if (++outidx == cnt)
520 goto out;
521 }
522 if (end != 0 && start >= end)
523 break;
524 }
525out:
526 *next = start;
527 return (outidx);
528}
529
530void
531vm_radix_foreach(struct vm_radix *rtree, vm_pindex_t start, vm_pindex_t end,
532 int color, void (*iter)(void *))
533{
534 struct vm_radix_node *rnode;
535 void *val;
536 int slot;
537
538 if (rtree->rt_root == 0)
539 return;
540 while ((rnode = vm_radix_leaf(rtree, &start, end)) != NULL) {
541 slot = vm_radix_slot(start, 0);
542 for (; slot < VM_RADIX_COUNT; slot++, start++) {
543 if (end != 0 && start >= end)
544 return;
545 val = vm_radix_match(rnode->rn_child[slot], color);
546 if (val)
547 iter(val);
548 }
549 if (end != 0 && start >= end)
550 return;
551 }
552}
553
554
555/*
556 * Look up any entry at a position less than or equal to index.
557 */
558void *
559vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index, int color)
560{
561 struct vm_radix_node *rnode;
562 struct vm_radix_node *child;
563 vm_pindex_t max;
564 vm_pindex_t inc;
565 void *val;
566 int slot;
567 int level;
568
569 CTR2(KTR_VM,
570 "lookup_le: tree %p, index %ju", rtree, (uintmax_t)index);
571restart:
572 level = vm_radix_height(rtree, &rnode);
573 if (rnode == NULL)
574 return (NULL);
575 max = VM_RADIX_MAX(level);
576 if (index > max || index == 0)
577 index = max;
578 /*
579 * Search the tree from the top for any leaf node holding an index
580 * lower than 'index'.
581 */
582 level--;
583 while (rnode) {
584 slot = vm_radix_slot(index, level);
585 CTR6(KTR_VM,
586 "lookup_le: tree %p, index %ju, level %d, slot %d, rnode %p, child %p",
587 rtree, (uintmax_t)index, level, slot, rnode,
588 rnode->rn_child[slot]);
589 if (level == 0)
590 break;
591 /*
592 * If we don't have an exact match we must start our search
593 * from the next leaf and adjust our index appropriately.
594 */
595 if ((child = rnode->rn_child[slot]) == NULL) {
596 /*
597 * Calculate how much to decrement our index by
598 * based on the tree level. We must set the
599 * lower bits to start from the end of the next
600 * leaf.
601 */
602 inc = 1LL << (level * VM_RADIX_WIDTH);
603 index |= VM_RADIX_MAX(level);
604 index -= inc;
605 slot--;
606 CTR4(KTR_VM,
607 "lookup_le: start %ju inc %ju mask 0x%jX slot %d",
608 (uintmax_t)index, (uintmax_t)inc,
609 (uintmax_t)VM_RADIX_MAX(level), slot);
610 for (; slot >= 0; slot--, index -= inc) {
611 child = rnode->rn_child[slot];
612 if (child)
613 break;
614 }
615 }
616 rnode = child;
617 level--;
618 }
619 if (rnode) {
620 for (; slot >= 0; slot--, index--) {
621 val = vm_radix_match(rnode->rn_child[slot], color);
622 if (val)
623 return (val);
624 }
625 }
626 if (index != -1)
627 goto restart;
628 return (NULL);
629}
630
631/*
632 * Remove the specified index from the tree. If possible the height of the
633 * tree is adjusted after deletion. The value stored at index is returned
634 * panics if the key is not present.
635 */
636void *
637vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index, int color)
638{
639 struct vm_radix_node *stack[VM_RADIX_LIMIT];
640 struct vm_radix_node *rnode, *root;
641 void *val;
642 int level;
643 int slot;
644
645 level = vm_radix_height(rtree, &root);
646 KASSERT(index <= VM_RADIX_MAX(level),
647 ("vm_radix_remove: %p index %ju out of range %jd.",
648 rtree, (uintmax_t)index, VM_RADIX_MAX(level)));
649 rnode = root;
650 val = NULL;
651 level--;
652 /*
653 * Find the node and record the path in stack.
654 */
655 while (level && rnode) {
656 stack[level] = rnode;
657 slot = vm_radix_slot(index, level);
658 CTR5(KTR_VM,
659 "remove: tree %p, index %ju, level %d, slot %d, rnode %p",
660 rtree, (uintmax_t)index, level, slot, rnode);
661 CTR4(KTR_VM, "remove: tree %p, rnode %p, child %p, count %u",
662 rtree, rnode, rnode->rn_child[slot], rnode->rn_count);
663 rnode = rnode->rn_child[slot];
664 level--;
665 }
666 KASSERT(rnode != NULL,
667 ("vm_radix_remove: index %ju not present in the tree.\n",
668 (uintmax_t)index));
669 slot = vm_radix_slot(index, 0);
670 val = vm_radix_match(rnode->rn_child[slot], color);
671 KASSERT(val != NULL,
672 ("vm_radix_remove: index %ju not present in the tree.\n",
673 (uintmax_t)index));
674
675 for (;;) {
676 CTR5(KTR_VM,
677 "remove: resetting tree %p, index %ju, level %d, slot %d, rnode %p",
678 rtree, (uintmax_t)index, level, slot, rnode);
679 CTR4(KTR_VM,
680 "remove: resetting tree %p, rnode %p, child %p, count %u",
681 rtree, rnode,
682 (rnode != NULL) ? rnode->rn_child[slot] : NULL,
683 (rnode != NULL) ? rnode->rn_count : 0);
684 rnode->rn_child[slot] = NULL;
685 /*
686 * Use atomics for the last level since red and black
687 * will both adjust it.
688 * Use a write memory barrier here in order to avoid
689 * rn_count reaching 0 before to fetch the actual pointer.
690 * Concurrent black removal, infact, may want to reclaim
691 * the radix node itself before to read it.
692 */
693 if (level == 0)
694 atomic_add_rel_32(&rnode->rn_count, -1);
695 else
696 rnode->rn_count--;
697 /*
698 * Only allow black removes to prune the tree.
699 */
700 if ((color & VM_RADIX_BLACK) == 0 || rnode->rn_count > 0)
701 break;
702 vm_radix_node_put(rnode);
703 if (rnode == root) {
704 vm_radix_setroot(rtree, NULL, 0);
705 break;
706 }
707 rnode = stack[++level];
708 slot = vm_radix_slot(index, level);
709
710 }
711 return (val);
712}
713
714/*
715 * Remove and free all the nodes from the radix tree.
716 * This function is recrusive but there is a tight control on it as the
717 * maximum depth of the tree is fixed.
718 */
719void
720vm_radix_reclaim_allnodes(struct vm_radix *rtree)
721{
722 struct vm_radix_node *root;
723 int level;
724
725 if (rtree->rt_root == 0)
726 return;
727 level = vm_radix_height(rtree, &root);
728 vm_radix_reclaim_allnodes_internal(root, level - 1);
729 rtree->rt_root = 0;
730}
731
732/*
733 * Attempts to reduce the height of the tree.
734 */
735void
736vm_radix_shrink(struct vm_radix *rtree)
737{
738 struct vm_radix_node *tmp, *root;
739 int level;
740
741 if (rtree->rt_root == 0)
742 return;
743 level = vm_radix_height(rtree, &root);
744
745 /* Adjust the height of the tree. */
746 while (root->rn_count == 1 && root->rn_child[0] != NULL) {
747 tmp = root;
748 root->rn_count--;
749 root = root->rn_child[0];
750 level--;
751 vm_radix_node_put(tmp);
752 }
753 /* Finally see if we have an empty tree. */
754 if (root->rn_count == 0) {
755 vm_radix_node_put(root);
756 root = NULL;
757 level--;
758 }
759 vm_radix_setroot(rtree, root, level);
760}
| 486 }
487 if (slot == VM_RADIX_COUNT)
488 goto restart;
489 }
490
491out:
492 *startp = start;
493 return (rnode);
494}
495
496
497
498/*
499 * Looks up as many as cnt values between start and end, and stores
500 * them in the caller allocated array out. The next index can be used
501 * to restart the scan. This optimizes forward scans in the tree.
502 */
503int
504vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start,
505 vm_pindex_t end, int color, void **out, int cnt, vm_pindex_t *next)
506{
507 struct vm_radix_node *rnode;
508 void *val;
509 int slot;
510 int outidx;
511
512 CTR3(KTR_VM, "lookupn: tree %p, start %ju, end %ju",
513 rtree, (uintmax_t)start, (uintmax_t)end);
514 if (rtree->rt_root == 0)
515 return (0);
516 outidx = 0;
517 while ((rnode = vm_radix_leaf(rtree, &start, end)) != NULL) {
518 slot = vm_radix_slot(start, 0);
519 for (; slot < VM_RADIX_COUNT; slot++, start++) {
520 if (end != 0 && start >= end)
521 goto out;
522 val = vm_radix_match(rnode->rn_child[slot], color);
523 if (val == NULL)
524 continue;
525 CTR4(KTR_VM,
526 "lookupn: tree %p index %ju slot %d found child %p",
527 rtree, (uintmax_t)start, slot, val);
528 out[outidx] = val;
529 if (++outidx == cnt)
530 goto out;
531 }
532 if (end != 0 && start >= end)
533 break;
534 }
535out:
536 *next = start;
537 return (outidx);
538}
539
540void
541vm_radix_foreach(struct vm_radix *rtree, vm_pindex_t start, vm_pindex_t end,
542 int color, void (*iter)(void *))
543{
544 struct vm_radix_node *rnode;
545 void *val;
546 int slot;
547
548 if (rtree->rt_root == 0)
549 return;
550 while ((rnode = vm_radix_leaf(rtree, &start, end)) != NULL) {
551 slot = vm_radix_slot(start, 0);
552 for (; slot < VM_RADIX_COUNT; slot++, start++) {
553 if (end != 0 && start >= end)
554 return;
555 val = vm_radix_match(rnode->rn_child[slot], color);
556 if (val)
557 iter(val);
558 }
559 if (end != 0 && start >= end)
560 return;
561 }
562}
563
564
565/*
566 * Look up any entry at a position less than or equal to index.
567 */
568void *
569vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index, int color)
570{
571 struct vm_radix_node *rnode;
572 struct vm_radix_node *child;
573 vm_pindex_t max;
574 vm_pindex_t inc;
575 void *val;
576 int slot;
577 int level;
578
579 CTR2(KTR_VM,
580 "lookup_le: tree %p, index %ju", rtree, (uintmax_t)index);
581restart:
582 level = vm_radix_height(rtree, &rnode);
583 if (rnode == NULL)
584 return (NULL);
585 max = VM_RADIX_MAX(level);
586 if (index > max || index == 0)
587 index = max;
588 /*
589 * Search the tree from the top for any leaf node holding an index
590 * lower than 'index'.
591 */
592 level--;
593 while (rnode) {
594 slot = vm_radix_slot(index, level);
595 CTR6(KTR_VM,
596 "lookup_le: tree %p, index %ju, level %d, slot %d, rnode %p, child %p",
597 rtree, (uintmax_t)index, level, slot, rnode,
598 rnode->rn_child[slot]);
599 if (level == 0)
600 break;
601 /*
602 * If we don't have an exact match we must start our search
603 * from the next leaf and adjust our index appropriately.
604 */
605 if ((child = rnode->rn_child[slot]) == NULL) {
606 /*
607 * Calculate how much to decrement our index by
608 * based on the tree level. We must set the
609 * lower bits to start from the end of the next
610 * leaf.
611 */
612 inc = 1LL << (level * VM_RADIX_WIDTH);
613 index |= VM_RADIX_MAX(level);
614 index -= inc;
615 slot--;
616 CTR4(KTR_VM,
617 "lookup_le: start %ju inc %ju mask 0x%jX slot %d",
618 (uintmax_t)index, (uintmax_t)inc,
619 (uintmax_t)VM_RADIX_MAX(level), slot);
620 for (; slot >= 0; slot--, index -= inc) {
621 child = rnode->rn_child[slot];
622 if (child)
623 break;
624 }
625 }
626 rnode = child;
627 level--;
628 }
629 if (rnode) {
630 for (; slot >= 0; slot--, index--) {
631 val = vm_radix_match(rnode->rn_child[slot], color);
632 if (val)
633 return (val);
634 }
635 }
636 if (index != -1)
637 goto restart;
638 return (NULL);
639}
640
641/*
642 * Remove the specified index from the tree. If possible the height of the
643 * tree is adjusted after deletion. The value stored at index is returned
644 * panics if the key is not present.
645 */
646void *
647vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index, int color)
648{
649 struct vm_radix_node *stack[VM_RADIX_LIMIT];
650 struct vm_radix_node *rnode, *root;
651 void *val;
652 int level;
653 int slot;
654
655 level = vm_radix_height(rtree, &root);
656 KASSERT(index <= VM_RADIX_MAX(level),
657 ("vm_radix_remove: %p index %ju out of range %jd.",
658 rtree, (uintmax_t)index, VM_RADIX_MAX(level)));
659 rnode = root;
660 val = NULL;
661 level--;
662 /*
663 * Find the node and record the path in stack.
664 */
665 while (level && rnode) {
666 stack[level] = rnode;
667 slot = vm_radix_slot(index, level);
668 CTR5(KTR_VM,
669 "remove: tree %p, index %ju, level %d, slot %d, rnode %p",
670 rtree, (uintmax_t)index, level, slot, rnode);
671 CTR4(KTR_VM, "remove: tree %p, rnode %p, child %p, count %u",
672 rtree, rnode, rnode->rn_child[slot], rnode->rn_count);
673 rnode = rnode->rn_child[slot];
674 level--;
675 }
676 KASSERT(rnode != NULL,
677 ("vm_radix_remove: index %ju not present in the tree.\n",
678 (uintmax_t)index));
679 slot = vm_radix_slot(index, 0);
680 val = vm_radix_match(rnode->rn_child[slot], color);
681 KASSERT(val != NULL,
682 ("vm_radix_remove: index %ju not present in the tree.\n",
683 (uintmax_t)index));
684
685 for (;;) {
686 CTR5(KTR_VM,
687 "remove: resetting tree %p, index %ju, level %d, slot %d, rnode %p",
688 rtree, (uintmax_t)index, level, slot, rnode);
689 CTR4(KTR_VM,
690 "remove: resetting tree %p, rnode %p, child %p, count %u",
691 rtree, rnode,
692 (rnode != NULL) ? rnode->rn_child[slot] : NULL,
693 (rnode != NULL) ? rnode->rn_count : 0);
694 rnode->rn_child[slot] = NULL;
695 /*
696 * Use atomics for the last level since red and black
697 * will both adjust it.
698 * Use a write memory barrier here in order to avoid
699 * rn_count reaching 0 before to fetch the actual pointer.
700 * Concurrent black removal, infact, may want to reclaim
701 * the radix node itself before to read it.
702 */
703 if (level == 0)
704 atomic_add_rel_32(&rnode->rn_count, -1);
705 else
706 rnode->rn_count--;
707 /*
708 * Only allow black removes to prune the tree.
709 */
710 if ((color & VM_RADIX_BLACK) == 0 || rnode->rn_count > 0)
711 break;
712 vm_radix_node_put(rnode);
713 if (rnode == root) {
714 vm_radix_setroot(rtree, NULL, 0);
715 break;
716 }
717 rnode = stack[++level];
718 slot = vm_radix_slot(index, level);
719
720 }
721 return (val);
722}
723
724/*
725 * Remove and free all the nodes from the radix tree.
726 * This function is recrusive but there is a tight control on it as the
727 * maximum depth of the tree is fixed.
728 */
729void
730vm_radix_reclaim_allnodes(struct vm_radix *rtree)
731{
732 struct vm_radix_node *root;
733 int level;
734
735 if (rtree->rt_root == 0)
736 return;
737 level = vm_radix_height(rtree, &root);
738 vm_radix_reclaim_allnodes_internal(root, level - 1);
739 rtree->rt_root = 0;
740}
741
742/*
743 * Attempts to reduce the height of the tree.
744 */
745void
746vm_radix_shrink(struct vm_radix *rtree)
747{
748 struct vm_radix_node *tmp, *root;
749 int level;
750
751 if (rtree->rt_root == 0)
752 return;
753 level = vm_radix_height(rtree, &root);
754
755 /* Adjust the height of the tree. */
756 while (root->rn_count == 1 && root->rn_child[0] != NULL) {
757 tmp = root;
758 root->rn_count--;
759 root = root->rn_child[0];
760 level--;
761 vm_radix_node_put(tmp);
762 }
763 /* Finally see if we have an empty tree. */
764 if (root->rn_count == 0) {
765 vm_radix_node_put(root);
766 root = NULL;
767 level--;
768 }
769 vm_radix_setroot(rtree, root, level);
770}
|