Deleted Added
sdiff udiff text old ( 226873 ) new ( 226876 )
full compact
vm_radix.c (226873) vm_radix.c (226876)
1/*
2 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
3 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org>
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:

--- 31 unchanged lines hidden (view full) ---

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>
1/*
2 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
3 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org>
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:

--- 31 unchanged lines hidden (view full) ---

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>
48#include <vm/vm_extern.h>
49#include <vm/vm_kern.h>
50#include <vm/vm_page.h>
51#include <vm/vm_radix.h>
52#include <vm/vm_object.h>
53
54#include <sys/kdb.h>
55
56CTASSERT(sizeof(struct vm_radix_node) < PAGE_SIZE);
57
58static uma_zone_t vm_radix_node_zone;
59
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
60#if 0
61#ifndef UMA_MD_SMALL_ALLOC
61static void *
62vm_radix_node_zone_allocf(uma_zone_t zone, int size, uint8_t *flags, int wait)
63{
64 vm_offset_t addr;
65 vm_page_t m;
66 int pflags;
67
68 /* Inform UMA that this allocator uses kernel_map. */

--- 66 unchanged lines hidden (view full) ---

135 ("vm_radix_node_put: Freeing a node with %d children\n",
136 rnode->rn_count));
137}
138#endif
139
140/*
141 * Allocate a radix node. Initializes all elements to 0.
142 */
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. */

--- 66 unchanged lines hidden (view full) ---

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 */
143static struct vm_radix_node *
144static __inline struct vm_radix_node *
144vm_radix_node_get(void)
145{
146
147 return (uma_zalloc(vm_radix_node_zone, M_NOWAIT | M_ZERO));
148}
149
150/*
151 * Free radix node.
152 */
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 */
153static void
154static __inline void
154vm_radix_node_put(struct vm_radix_node *rnode)
155{
156
157 uma_zfree(vm_radix_node_zone, rnode);
158}
159
160/*
161 * Return the position in the array for a given level.
162 */
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 */
163static inline int
164static __inline int
164vm_radix_slot(vm_pindex_t index, int level)
165{
166
167 return ((index >> (level * VM_RADIX_WIDTH)) & VM_RADIX_MASK);
168}
169
170void
171vm_radix_init(void)
172{
173
174 vm_radix_node_zone = uma_zcreate("RADIX NODE",
175 sizeof(struct vm_radix_node), NULL,
176#ifdef INVARIANTS
177 vm_radix_node_zone_dtor,
178#else
179 NULL,
180#endif
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
181 NULL, NULL, UMA_ALIGN_PTR, UMA_ZONE_VM);
182 NULL, NULL, VM_RADIX_HEIGHT, UMA_ZONE_VM);
182}
183
184/*
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
214/*
185 * Inserts the key-value pair in to the radix tree. Returns errno.
186 * Panics if the key already exists.
187 */
188int
189vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val)
190{
191 struct vm_radix_node *rnode;
215 * Inserts the key-value pair in to the radix tree. Returns errno.
216 * Panics if the key already exists.
217 */
218int
219vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val)
220{
221 struct vm_radix_node *rnode;
192 int slot;
222 struct vm_radix_node *root;
193 int level;
223 int level;
224 int slot;
194
195 CTR3(KTR_VM,
196 "insert: tree %p, index %p, val %p", rtree, (void *)index, val);
197 if (index == -1)
198 panic("vm_radix_insert: -1 is not a valid index.\n");
225
226 CTR3(KTR_VM,
227 "insert: tree %p, index %p, val %p", rtree, (void *)index, val);
228 if (index == -1)
229 panic("vm_radix_insert: -1 is not a valid index.\n");
230 level = vm_radix_height(rtree, &root);
199 /*
200 * Increase the height by adding nodes at the root until
201 * there is sufficient space.
202 */
231 /*
232 * Increase the height by adding nodes at the root until
233 * there is sufficient space.
234 */
203 while (rtree->rt_height == 0 ||
204 index > VM_RADIX_MAX(rtree->rt_height)) {
235 while (level == 0 || index > VM_RADIX_MAX(level)) {
205 CTR3(KTR_VM, "insert: expanding %jd > %jd height %d",
236 CTR3(KTR_VM, "insert: expanding %jd > %jd height %d",
206 index, VM_RADIX_MAX(rtree->rt_height), rtree->rt_height);
237 index, VM_RADIX_MAX(level), level);
238 level++;
239 KASSERT(level <= VM_RADIX_LIMIT,
240 ("vm_radix_insert: Tree %p height %d too tall",
241 rtree, level));
207 /*
208 * Only allocate tree nodes if they are needed.
209 */
242 /*
243 * Only allocate tree nodes if they are needed.
244 */
210 if (rtree->rt_root == NULL || rtree->rt_root->rn_count != 0) {
245 if (root == NULL || root->rn_count != 0) {
211 rnode = vm_radix_node_get();
212 if (rnode == NULL)
213 return (ENOMEM);
246 rnode = vm_radix_node_get();
247 if (rnode == NULL)
248 return (ENOMEM);
214 if (rtree->rt_root) {
215 rnode->rn_child[0] = rtree->rt_root;
249 /*
250 * Store the new pointer with a memory barrier so
251 * that it is visible before the new root.
252 */
253 if (root) {
254 atomic_store_rel_ptr((volatile uintptr_t *)
255 &rnode->rn_child[0], (uintptr_t)root);
216 rnode->rn_count = 1;
217 }
256 rnode->rn_count = 1;
257 }
218 rtree->rt_root = rnode;
258 root = rnode;
219 }
259 }
220 rtree->rt_height++;
221 KASSERT(rtree->rt_height <= VM_RADIX_LIMIT,
222 ("vm_radix_insert: Tree %p height %d too tall", rtree,
223 rtree->rt_height));
260 vm_radix_setroot(rtree, root, level);
224 }
225
226 /* Now that the tree is tall enough, fill in the path to the index. */
261 }
262
263 /* Now that the tree is tall enough, fill in the path to the index. */
227 rnode = rtree->rt_root;
228 for (level = rtree->rt_height - 1; level > 0; level--) {
264 rnode = root;
265 for (level = level - 1; level > 0; level--) {
229 slot = vm_radix_slot(index, level);
230 /* Add the required intermidiate nodes. */
231 if (rnode->rn_child[slot] == NULL) {
232 rnode->rn_child[slot] = vm_radix_node_get();
233 if (rnode->rn_child[slot] == NULL)
234 return (ENOMEM);
235 rnode->rn_count++;
236 }

--- 21 unchanged lines hidden (view full) ---

258 */
259void *
260vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index)
261{
262 struct vm_radix_node *rnode;
263 int slot;
264 int level;
265
266 slot = vm_radix_slot(index, level);
267 /* Add the required intermidiate nodes. */
268 if (rnode->rn_child[slot] == NULL) {
269 rnode->rn_child[slot] = vm_radix_node_get();
270 if (rnode->rn_child[slot] == NULL)
271 return (ENOMEM);
272 rnode->rn_count++;
273 }

--- 21 unchanged lines hidden (view full) ---

295 */
296void *
297vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index)
298{
299 struct vm_radix_node *rnode;
300 int slot;
301 int level;
302
266 if (index > VM_RADIX_MAX(rtree->rt_height))
303 level = vm_radix_height(rtree, &rnode);
304 if (index > VM_RADIX_MAX(level))
267 return NULL;
305 return NULL;
268 level = rtree->rt_height - 1;
269 rnode = rtree->rt_root;
306 level--;
270 while (rnode) {
271 slot = vm_radix_slot(index, level);
272 CTR5(KTR_VM,
273 "lookup: tree %p, index %p, level %d, slot %d, child %p",
274 rtree, (void *)index, level, slot, rnode->rn_child[slot]);
275 if (level == 0)
276 return rnode->rn_child[slot];
277 rnode = rnode->rn_child[slot];

--- 21 unchanged lines hidden (view full) ---

299 int level;
300 void *val;
301 int outidx;
302 int loops = 0;
303
304 CTR3(KTR_VM, "lookupn: tree %p, start %p, end %p",
305 rtree, (void *)start, (void *)end);
306 outidx = 0;
307 while (rnode) {
308 slot = vm_radix_slot(index, level);
309 CTR5(KTR_VM,
310 "lookup: tree %p, index %p, level %d, slot %d, child %p",
311 rtree, (void *)index, level, slot, rnode->rn_child[slot]);
312 if (level == 0)
313 return rnode->rn_child[slot];
314 rnode = rnode->rn_child[slot];

--- 21 unchanged lines hidden (view full) ---

336 int level;
337 void *val;
338 int outidx;
339 int loops = 0;
340
341 CTR3(KTR_VM, "lookupn: tree %p, start %p, end %p",
342 rtree, (void *)start, (void *)end);
343 outidx = 0;
307 max = VM_RADIX_MAX(rtree->rt_height);
344restart:
345 level = vm_radix_height(rtree, &rnode);
346 max = VM_RADIX_MAX(level);
308 if (start > max)
347 if (start > max)
309 return 0;
348 goto out;
310 if (end > max || end == 0)
311 end = max;
349 if (end > max || end == 0)
350 end = max;
312restart:
313 loops++;
314 if (loops > 1000)
315 panic("vm_radix_lookupn: looping %d\n", loops);
316 /*
317 * Search the tree from the top for any leaf node holding an index
318 * between start and end.
319 */
351 loops++;
352 if (loops > 1000)
353 panic("vm_radix_lookupn: looping %d\n", loops);
354 /*
355 * Search the tree from the top for any leaf node holding an index
356 * between start and end.
357 */
320 level = rtree->rt_height - 1;
321 rnode = rtree->rt_root;
358 level--;
322 while (rnode) {
323 slot = vm_radix_slot(start, level);
324 CTR5(KTR_VM,
325 "lookupn: tree %p, index %p, level %d, slot %d, child %p",
326 rtree, (void *)start, level, slot, rnode->rn_child[slot]);
327 if (level == 0)
328 break;
329 /*

--- 69 unchanged lines hidden (view full) ---

399 vm_pindex_t max;
400 vm_pindex_t inc;
401 int slot;
402 int level;
403 int loops = 0;
404
405 CTR2(KTR_VM,
406 "lookup_le: tree %p, index %p", rtree, (void *)index);
359 while (rnode) {
360 slot = vm_radix_slot(start, level);
361 CTR5(KTR_VM,
362 "lookupn: tree %p, index %p, level %d, slot %d, child %p",
363 rtree, (void *)start, level, slot, rnode->rn_child[slot]);
364 if (level == 0)
365 break;
366 /*

--- 69 unchanged lines hidden (view full) ---

436 vm_pindex_t max;
437 vm_pindex_t inc;
438 int slot;
439 int level;
440 int loops = 0;
441
442 CTR2(KTR_VM,
443 "lookup_le: tree %p, index %p", rtree, (void *)index);
407 if (rtree->rt_root == NULL)
444restart:
445 level = vm_radix_height(rtree, &rnode);
446 if (rnode == NULL)
408 return (NULL);
447 return (NULL);
409 max = VM_RADIX_MAX(rtree->rt_height);
448 max = VM_RADIX_MAX(level);
410 if (index > max || index == 0)
411 index = max;
449 if (index > max || index == 0)
450 index = max;
412restart:
413 loops++;
414 if (loops > 1000)
415 panic("vm_radix_looku_le: looping %d\n", loops);
416 /*
417 * Search the tree from the top for any leaf node holding an index
418 * lower than 'index'.
419 */
451 loops++;
452 if (loops > 1000)
453 panic("vm_radix_looku_le: looping %d\n", loops);
454 /*
455 * Search the tree from the top for any leaf node holding an index
456 * lower than 'index'.
457 */
420 level = rtree->rt_height - 1;
421 rnode = rtree->rt_root;
458 level--;
422 while (rnode) {
423 slot = vm_radix_slot(index, level);
424 CTR5(KTR_VM,
425 "lookup_le: tree %p, index %p, level %d, slot %d, child %p",
426 rtree, (void *)index, level, slot, rnode->rn_child[slot]);
427 if (level == 0)
428 break;
429 /*

--- 38 unchanged lines hidden (view full) ---

468 * Remove the specified index from the tree. If possible the height of the
469 * tree is adjusted after deletion. The value stored at index is returned
470 * panics if the key is not present.
471 */
472void *
473vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index)
474{
475 struct vm_radix_node *stack[VM_RADIX_LIMIT];
459 while (rnode) {
460 slot = vm_radix_slot(index, level);
461 CTR5(KTR_VM,
462 "lookup_le: tree %p, index %p, level %d, slot %d, child %p",
463 rtree, (void *)index, level, slot, rnode->rn_child[slot]);
464 if (level == 0)
465 break;
466 /*

--- 38 unchanged lines hidden (view full) ---

505 * Remove the specified index from the tree. If possible the height of the
506 * tree is adjusted after deletion. The value stored at index is returned
507 * panics if the key is not present.
508 */
509void *
510vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index)
511{
512 struct vm_radix_node *stack[VM_RADIX_LIMIT];
476 struct vm_radix_node *rnode;
513 struct vm_radix_node *rnode, *root;
477 void *val;
478 int level;
479 int slot;
480
514 void *val;
515 int level;
516 int slot;
517
481 KASSERT(index <= VM_RADIX_MAX(rtree->rt_height),
518 level = vm_radix_height(rtree, &root);
519 KASSERT(index <= VM_RADIX_MAX(level),
482 ("vm_radix_remove: %p index %jd out of range %jd.",
520 ("vm_radix_remove: %p index %jd out of range %jd.",
483 rtree, index, VM_RADIX_MAX(rtree->rt_height)));
521 rtree, index, VM_RADIX_MAX(level)));
522 rnode = root;
484 val = NULL;
523 val = NULL;
485 rnode = rtree->rt_root;
486 level = rtree->rt_height - 1;
524 level--;
487 /*
488 * Find the node and record the path in stack.
489 */
490 while (level && rnode) {
491 stack[level] = rnode;
492 slot = vm_radix_slot(index, level);
493 rnode = rnode->rn_child[slot];
494 CTR5(KTR_VM,

--- 7 unchanged lines hidden (view full) ---

502
503 val = rnode->rn_child[slot];
504 for (;;) {
505 rnode->rn_child[slot] = NULL;
506 rnode->rn_count--;
507 if (rnode->rn_count > 0)
508 break;
509 vm_radix_node_put(rnode);
525 /*
526 * Find the node and record the path in stack.
527 */
528 while (level && rnode) {
529 stack[level] = rnode;
530 slot = vm_radix_slot(index, level);
531 rnode = rnode->rn_child[slot];
532 CTR5(KTR_VM,

--- 7 unchanged lines hidden (view full) ---

540
541 val = rnode->rn_child[slot];
542 for (;;) {
543 rnode->rn_child[slot] = NULL;
544 rnode->rn_count--;
545 if (rnode->rn_count > 0)
546 break;
547 vm_radix_node_put(rnode);
510 if (rnode == rtree->rt_root) {
511 rtree->rt_root = NULL;
512 rtree->rt_height = 0;
548 if (rnode == root) {
549 vm_radix_setroot(rtree, NULL, 0);
513 break;
514 }
515 rnode = stack[++level];
516 slot = vm_radix_slot(index, level);
517
518 }
519 return (val);
520}
521
522/*
523 * Attempts to reduce the height of the tree.
524 */
525void
526vm_radix_shrink(struct vm_radix *rtree)
527{
550 break;
551 }
552 rnode = stack[++level];
553 slot = vm_radix_slot(index, level);
554
555 }
556 return (val);
557}
558
559/*
560 * Attempts to reduce the height of the tree.
561 */
562void
563vm_radix_shrink(struct vm_radix *rtree)
564{
528 struct vm_radix_node *tmp;
565 struct vm_radix_node *tmp, *root;
566 int level;
529
567
530 if (rtree->rt_root == NULL)
568 if (rtree->rt_root == 0)
531 return;
569 return;
570 level = vm_radix_height(rtree, &root);
532
533 /* Adjust the height of the tree. */
571
572 /* Adjust the height of the tree. */
534 while (rtree->rt_root->rn_count == 1 &&
535 rtree->rt_root->rn_child[0] != NULL) {
536 tmp = rtree->rt_root;
537 rtree->rt_root = tmp->rn_child[0];
538 rtree->rt_height--;
539 tmp->rn_count--;
573 while (root->rn_count == 1 && root->rn_child[0] != NULL) {
574 tmp = root;
575 root->rn_count--;
576 root = root->rn_child[0];
577 level--;
540 vm_radix_node_put(tmp);
541 }
542 /* Finally see if we have an empty tree. */
578 vm_radix_node_put(tmp);
579 }
580 /* Finally see if we have an empty tree. */
543 if (rtree->rt_root->rn_count == 0) {
544 vm_radix_node_put(rtree->rt_root);
545 rtree->rt_root = NULL;
546 rtree->rt_height = 0;
581 if (root->rn_count == 0) {
582 vm_radix_node_put(root);
583 root = NULL;
584 level--;
547 }
585 }
586 vm_radix_setroot(rtree, root, level);
548}
587}