2d1
< * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
3a3
> * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
213a214,225
> static inline void *
> vm_radix_match(void *child, int color)
> {
> uintptr_t c;
>
> c = (uintptr_t)child;
>
> if ((c & color) == 0)
> return (NULL);
> return ((void *)(c & ~VM_RADIX_FLAGS));
> }
>
280c292
< slot = vm_radix_slot(index, level);
---
> slot = vm_radix_slot(index, 0);
285a298
> val = (void *)((uintptr_t)val | VM_RADIX_BLACK);
287c300
< rnode->rn_count++;
---
> atomic_add_int((volatile int *)&rnode->rn_count, 1);
297c310
< vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index)
---
> vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index, int color)
313c326
< return rnode->rn_child[slot];
---
> return vm_radix_match(rnode->rn_child[slot], color);
321a335,365
> void *
> vm_radix_color(struct vm_radix *rtree, vm_pindex_t index, int color)
> {
> struct vm_radix_node *rnode;
> uintptr_t child;
> int slot;
> int level;
>
> level = vm_radix_height(rtree, &rnode);
> if (index > VM_RADIX_MAX(level))
> return NULL;
> level--;
> while (rnode) {
> slot = vm_radix_slot(index, level);
> CTR5(KTR_VM,
> "color: tree %p, index %p, level %d, slot %d, child %p",
> rtree, (void *)index, level, slot, rnode->rn_child[slot]);
> if (level == 0)
> break;
> rnode = rnode->rn_child[slot];
> level--;
> }
> if (rnode == NULL || rnode->rn_child[slot] == NULL)
> return (NULL);
> child = (uintptr_t)rnode->rn_child[slot];
> child &= ~VM_RADIX_FLAGS;
> rnode->rn_child[slot] = (void *)(child | color);
>
> return (void *)child;
> }
>
323,325c367,369
< * Looks up as many as cnt values between start and end inclusive, and stores
< * them in the caller allocated array out. The next index can be used to
< * restart the scan. This optimizes forward scans in the tree.
---
> * Looks up as many as cnt values between start and end, and stores
> * them in the caller allocated array out. The next index can be used
> * to restart the scan. This optimizes forward scans in the tree.
329c373
< vm_pindex_t end, void **out, int cnt, vm_pindex_t *next)
---
> vm_pindex_t end, int color, void **out, int cnt, vm_pindex_t *next)
332,333d375
< struct vm_radix_node *child;
< vm_pindex_t max;
339d380
< int loops = 0;
346,347c387
< max = VM_RADIX_MAX(level);
< if (start > max)
---
> if (rnode == NULL || start > VM_RADIX_MAX(level))
349,353c389,390
< if (end > max || end == 0)
< end = max;
< loops++;
< if (loops > 1000)
< panic("vm_radix_lookupn: looping %d\n", loops);
---
> if (end && start >= end)
> goto out;
358,359c395
< level--;
< while (rnode) {
---
> for (level--; level; level--) {
364,365c400,403
< if (level == 0)
< break;
---
> if (rnode->rn_child[slot] != NULL) {
> rnode = rnode->rn_child[slot];
> continue;
> }
367,388c405,423
< * If we don't have an exact match we must start our search
< * from the next leaf and adjust our index appropriately.
< */
< if ((child = rnode->rn_child[slot]) == NULL) {
< /*
< * Calculate how much to increment our index by
< * based on the tree level. We must truncate the
< * lower bits to start from the begnning of the next
< * leaf.
< */
< inc = 1LL << (level * VM_RADIX_WIDTH);
< start &= ~VM_RADIX_MAX(level);
< start += inc;
< slot++;
< CTR5(KTR_VM,
< "lookupn: start %p end %p inc %d mask 0x%lX slot %d",
< (void *)start, (void *)end, inc, ~VM_RADIX_MAX(level), slot);
< for (; slot < VM_RADIX_COUNT && start <= end;
< slot++, start += inc) {
< child = rnode->rn_child[slot];
< if (child)
< break;
---
> * Calculate how much to increment our index by
> * based on the tree level. We must truncate the
> * lower bits to start from the begnning of the
> * next leaf.
> */
> inc = 1LL << (level * VM_RADIX_WIDTH);
> start &= ~VM_RADIX_MAX(level);
> start += inc;
> slot++;
> CTR5(KTR_VM,
> "lookupn: start %p end %p inc %d mask 0x%lX slot %d",
> (void *)start, (void *)end, inc,
> ~VM_RADIX_MAX(level), slot);
> for (; slot < VM_RADIX_COUNT; slot++, start += inc) {
> if (end != 0 && start >= end)
> goto out;
> if (rnode->rn_child[slot]) {
> rnode = rnode->rn_child[slot];
> break;
391,403c426
< rnode = child;
< level--;
< }
< if (rnode == NULL) {
< /*
< * If we still have another range to search, start looking
< * from the next node. Otherwise, return what we've already
< * found. The loop above has already adjusted start to the
< * beginning of the next node.
< *
< * Detect start wrapping back to 0 and return in this case.
< */
< if (start <= end && start != 0)
---
> if (slot == VM_RADIX_COUNT)
405d427
< goto out;
407,409c429,433
< for (; outidx < cnt && slot < VM_RADIX_COUNT && start <= end;
< slot++, start++) {
< val = rnode->rn_child[slot];
---
> slot = vm_radix_slot(start, 0);
> for (; slot < VM_RADIX_COUNT; slot++, start++) {
> if (end != 0 && start >= end)
> goto out;
> val = vm_radix_match(rnode->rn_child[slot], color);
411a436,438
> CTR4(KTR_VM,
> "lookupn: tree %p index %p slot %d found child %p",
> rtree, (void *)start, slot, val);
412a440,441
> if (outidx == cnt)
> goto out;
419c448
< if (outidx < cnt && start <= end)
---
> if ((end == 0 || start < end))
421d449
<
432c460
< vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index)
---
> vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index, int color)
437a466
> void *val;
440d468
< int loops = 0;
451,453d478
< loops++;
< if (loops > 1000)
< panic("vm_radix_looku_le: looping %d\n", loops);
495,496c520,522
< if (rnode->rn_child[slot])
< return (rnode->rn_child[slot]);
---
> val = vm_radix_match(rnode->rn_child[slot], color);
> if (val)
> return (val);
510c536
< vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index)
---
> vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index, int color)
536a563,564
> KASSERT(rnode != NULL,
> ("vm_radix_remove: index %jd not present in the tree.\n", index));
538c566,567
< KASSERT(rnode != NULL && rnode->rn_child[slot] != NULL,
---
> val = vm_radix_match(rnode->rn_child[slot], color);
> KASSERT(val != NULL,
541d569
< val = rnode->rn_child[slot];
544,545c572,583
< rnode->rn_count--;
< if (rnode->rn_count > 0)
---
> /*
> * Use atomics for the last level since red and black
> * will both adjust it.
> */
> if (level == 0)
> atomic_add_int((volatile int *)&rnode->rn_count, -1);
> else
> rnode->rn_count--;
> /*
> * Only allow black removes to prune the tree.
> */
> if ((color & VM_RADIX_BLACK) == 0 || rnode->rn_count > 0)