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