vm_radix.h revision 227544
1124208Sdes/* 2124208Sdes * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org> 3124208Sdes * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com> 4124208Sdes * All rights reserved. 5124208Sdes * 6124208Sdes * Redistribution and use in source and binary forms, with or without 7124208Sdes * modification, are permitted provided that the following conditions 8124208Sdes * are met: 9124208Sdes * 1. Redistributions of source code must retain the above copyright 10124208Sdes * notice, this list of conditions and the following disclaimer. 11124208Sdes * 2. Redistributions in binary form must reproduce the above copyright 12124208Sdes * notice, this list of conditions and the following disclaimer in the 13124208Sdes * documentation and/or other materials provided with the distribution. 14124208Sdes * 15124208Sdes * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16124208Sdes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17124208Sdes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18124208Sdes * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19124208Sdes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20124208Sdes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21124208Sdes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22124208Sdes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23124208Sdes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24124208Sdes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2598937Sdes * SUCH DAMAGE. 2698937Sdes * 2798937Sdes */ 28295367Sdes 2998937Sdes#ifndef _VM_RADIX_H_ 3098937Sdes#define _VM_RADIX_H_ 3198937Sdes 3298937Sdes#include <sys/queue.h> 33162852Sdes 3498937Sdes/* Default values of the tree parameters */ 3598937Sdes#define VM_RADIX_WIDTH 5 3698937Sdes#define VM_RADIX_COUNT (1 << VM_RADIX_WIDTH) 3798937Sdes#define VM_RADIX_MASK (VM_RADIX_COUNT - 1) 3898937Sdes#define VM_RADIX_LIMIT howmany((sizeof(vm_pindex_t) * NBBY), VM_RADIX_WIDTH) 3998937Sdes#define VM_RADIX_FLAGS 0x3 /* Flag bits stored in node pointers. */ 4098937Sdes#define VM_RADIX_BLACK 0x1 /* Black node. (leaf only) */ 4198937Sdes#define VM_RADIX_RED 0x2 /* Red node. (leaf only) */ 4298937Sdes#define VM_RADIX_ANY (VM_RADIX_RED | VM_RADIX_BLACK) 4398937Sdes#define VM_RADIX_EMPTY 0x1 /* Empty hint. (internal only) */ 4498937Sdes#define VM_RADIX_HEIGHT 0xf /* Bits of height in root */ 45221420Sdes#define VM_RADIX_STACK 8 /* Nodes to store on stack. */ 46323124Sdes 47323124Sdes/* Calculates maximum value for a tree of height h. */ 48323124Sdes#define VM_RADIX_MAX(h) \ 49323124Sdes ((h) == VM_RADIX_LIMIT ? ((vm_pindex_t)-1) : \ 50323124Sdes (((vm_pindex_t)1 << ((h) * VM_RADIX_WIDTH)) - 1)) 51323124Sdes 52323124Sdes/* 53323124Sdes * Radix tree root. The height and pointer are set together to permit 54323124Sdes * coherent lookups while the root is modified. 55323124Sdes */ 56323124Sdesstruct vm_radix { 57323124Sdes uintptr_t rt_root; /* root + height */ 58323124Sdes}; 59221420Sdes 60221420Sdes#ifdef _KERNEL 61221487SdesCTASSERT(VM_RADIX_HEIGHT >= VM_RADIX_LIMIT); 62221420Sdes 6398937Sdesstruct vm_radix_node { 6498937Sdes void *rn_child[VM_RADIX_COUNT]; /* child nodes. */ 6598937Sdes uint16_t rn_count; /* Valid children. */ 6698937Sdes}; 6798937Sdes 6898937Sdesvoid vm_radix_init(void); 6998937Sdes 7098937Sdes/* 71221420Sdes * Functions which only work with black nodes. (object lock) 72221420Sdes */ 73221420Sdesint vm_radix_insert(struct vm_radix *, vm_pindex_t, void *); 74221420Sdesvoid vm_radix_shrink(struct vm_radix *); 75221420Sdes 76221420Sdes/* 77221420Sdes * Functions which work on specified colors. (object, vm_page_queue_free locks) 78221420Sdes */ 79221420Sdesvoid *vm_radix_color(struct vm_radix *, vm_pindex_t, int); 80221420Sdesvoid *vm_radix_lookup(struct vm_radix *, vm_pindex_t, int); 81221420Sdesint vm_radix_lookupn(struct vm_radix *, vm_pindex_t, vm_pindex_t, int, 82221420Sdes void **, int, vm_pindex_t *); 83221420Sdesvoid *vm_radix_lookup_le(struct vm_radix *, vm_pindex_t, int); 84221420Sdesvoid vm_radix_reclaim_allnodes(struct vm_radix *); 85221420Sdesvoid *vm_radix_remove(struct vm_radix *, vm_pindex_t, int); 86221420Sdesvoid vm_radix_foreach(struct vm_radix *, vm_pindex_t, vm_pindex_t, int, 87221420Sdes void (*)(void *)); 88221420Sdes 89221420Sdes/* 90221420Sdes * Look up any entry at a position greater or equal to index. 91221420Sdes */ 92221420Sdesstatic inline void * 93221420Sdesvm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index, int color) 94221420Sdes{ 95221420Sdes void *val; 96221420Sdes 97221420Sdes if (vm_radix_lookupn(rtree, index, 0, color, &val, 1, &index)) 98221420Sdes return (val); 99221420Sdes return (NULL); 100221420Sdes} 101221420Sdes 102221420Sdesstatic inline void * 103240075Sdesvm_radix_last(struct vm_radix *rtree, int color) 104240075Sdes{ 105240075Sdes 106240075Sdes return vm_radix_lookup_le(rtree, 0, color); 107240075Sdes} 108240075Sdes 10998937Sdesstatic inline void * 11098937Sdesvm_radix_first(struct vm_radix *rtree, int color) 11198937Sdes{ 11298937Sdes 113149749Sdes return vm_radix_lookup_ge(rtree, 0, color); 114149749Sdes} 115149749Sdes 116149749Sdesstatic inline void * 117149749Sdesvm_radix_next(struct vm_radix *rtree, vm_pindex_t index, int color) 11898937Sdes{ 11998937Sdes 12098937Sdes if (index == -1) 121295367Sdes return (NULL); 122295367Sdes return vm_radix_lookup_ge(rtree, index + 1, color); 123295367Sdes} 124295367Sdes 125295367Sdesstatic inline void * 126295367Sdesvm_radix_prev(struct vm_radix *rtree, vm_pindex_t index, int color) 127295367Sdes{ 128295367Sdes 129295367Sdes if (index == 0) 130295367Sdes return (NULL); 131295367Sdes return vm_radix_lookup_le(rtree, index - 1, color); 132181111Sdes} 133149749Sdes 134149749Sdes#endif /* _KERNEL */ 135149749Sdes#endif /* !_VM_RADIX_H_ */ 13698937Sdes