1/*- 2 * SPDX-License-Identifier: BSD-2-Clause 3 * 4 * Copyright (c) 2013 EMC Corp. 5 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org> 6 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com> 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 28 * SUCH DAMAGE. 29 */ 30 31#ifndef _VM_RADIX_H_ 32#define _VM_RADIX_H_ 33 34#include <vm/_vm_radix.h> 35 36#ifdef _KERNEL 37#include <sys/pctrie.h> 38#include <vm/vm_page.h> 39#include <vm/vm.h> 40 41void vm_radix_wait(void); 42void vm_radix_zinit(void); 43void *vm_radix_node_alloc(struct pctrie *ptree); 44void vm_radix_node_free(struct pctrie *ptree, void *node); 45extern smr_t vm_radix_smr; 46 47static __inline void 48vm_radix_init(struct vm_radix *rtree) 49{ 50 pctrie_init(&rtree->rt_trie); 51} 52 53static __inline bool 54vm_radix_is_empty(struct vm_radix *rtree) 55{ 56 return (pctrie_is_empty(&rtree->rt_trie)); 57} 58 59PCTRIE_DEFINE_SMR(VM_RADIX, vm_page, pindex, vm_radix_node_alloc, vm_radix_node_free, 60 vm_radix_smr); 61 62/* 63 * Inserts the key-value pair into the trie. 64 * Panics if the key already exists. 65 */ 66static __inline int 67vm_radix_insert(struct vm_radix *rtree, vm_page_t page) 68{ 69 return (VM_RADIX_PCTRIE_INSERT(&rtree->rt_trie, page)); 70} 71 72/* 73 * Insert the page into the vm_radix tree with its pindex as the key. Panic if 74 * the pindex already exists. Return zero on success or a non-zero error on 75 * memory allocation failure. Set the out parameter mpred to the previous page 76 * in the tree as if found by a previous call to vm_radix_lookup_le with the 77 * new page pindex. 78 */ 79static __inline int 80vm_radix_insert_lookup_lt(struct vm_radix *rtree, vm_page_t page, 81 vm_page_t *mpred) 82{ 83 int error; 84 85 error = VM_RADIX_PCTRIE_INSERT_LOOKUP_LE(&rtree->rt_trie, page, mpred); 86 if (__predict_false(error == EEXIST)) 87 panic("vm_radix_insert_lookup_lt: page already present, %p", 88 *mpred); 89 return (error); 90} 91 92/* 93 * Returns the value stored at the index assuming there is an external lock. 94 * 95 * If the index is not present, NULL is returned. 96 */ 97static __inline vm_page_t 98vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index) 99{ 100 return (VM_RADIX_PCTRIE_LOOKUP(&rtree->rt_trie, index)); 101} 102 103/* 104 * Returns the value stored at the index without requiring an external lock. 105 * 106 * If the index is not present, NULL is returned. 107 */ 108static __inline vm_page_t 109vm_radix_lookup_unlocked(struct vm_radix *rtree, vm_pindex_t index) 110{ 111 return (VM_RADIX_PCTRIE_LOOKUP_UNLOCKED(&rtree->rt_trie, index)); 112} 113 114/* 115 * Returns the page with the least pindex that is greater than or equal to the 116 * specified pindex, or NULL if there are no such pages. 117 * 118 * Requires that access be externally synchronized by a lock. 119 */ 120static __inline vm_page_t 121vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) 122{ 123 return (VM_RADIX_PCTRIE_LOOKUP_GE(&rtree->rt_trie, index)); 124} 125 126/* 127 * Returns the page with the greatest pindex that is less than or equal to the 128 * specified pindex, or NULL if there are no such pages. 129 * 130 * Requires that access be externally synchronized by a lock. 131 */ 132static __inline vm_page_t 133vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) 134{ 135 return (VM_RADIX_PCTRIE_LOOKUP_LE(&rtree->rt_trie, index)); 136} 137 138/* 139 * Remove the specified index from the trie, and return the value stored at 140 * that index. If the index is not present, return NULL. 141 */ 142static __inline vm_page_t 143vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index) 144{ 145 return (VM_RADIX_PCTRIE_REMOVE_LOOKUP(&rtree->rt_trie, index)); 146} 147 148/* 149 * Remove and free all the nodes from the radix tree. 150 */ 151static __inline void 152vm_radix_reclaim_allnodes(struct vm_radix *rtree) 153{ 154 VM_RADIX_PCTRIE_RECLAIM(&rtree->rt_trie); 155} 156 157/* 158 * Replace an existing page in the trie with another one. 159 * Panics if there is not an old page in the trie at the new page's index. 160 */ 161static __inline vm_page_t 162vm_radix_replace(struct vm_radix *rtree, vm_page_t newpage) 163{ 164 return (VM_RADIX_PCTRIE_REPLACE(&rtree->rt_trie, newpage)); 165} 166 167#endif /* _KERNEL */ 168#endif /* !_VM_RADIX_H_ */ 169