1 /*-
2  * Copyright (c) 2010 Isilon Systems, Inc.
3  * Copyright (c) 2010 iX Systems, Inc.
4  * Copyright (c) 2010 Panasas, Inc.
5  * Copyright (c) 2013-2018 Mellanox Technologies, Ltd.
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice unmodified, this list of conditions, and the following
13  *    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 ``AS IS'' AND ANY EXPRESS OR
19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29 
30 #include <sys/cdefs.h>
31 __FBSDID("$FreeBSD$");
32 
33 #include <sys/param.h>
34 #include <sys/systm.h>
35 #include <sys/malloc.h>
36 #include <sys/kernel.h>
37 #include <sys/sysctl.h>
38 
39 #include <linux/slab.h>
40 #include <linux/kernel.h>
41 #include <linux/radix-tree.h>
42 #include <linux/err.h>
43 
44 static MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat");
45 
46 static inline unsigned long
radix_max(struct radix_tree_root * root)47 radix_max(struct radix_tree_root *root)
48 {
49 	return ((1UL << (root->height * RADIX_TREE_MAP_SHIFT)) - 1UL);
50 }
51 
52 static inline int
radix_pos(long id,int height)53 radix_pos(long id, int height)
54 {
55 	return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK;
56 }
57 
58 void *
radix_tree_lookup(struct radix_tree_root * root,unsigned long index)59 radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
60 {
61 	struct radix_tree_node *node;
62 	void *item;
63 	int height;
64 
65 	item = NULL;
66 	node = root->rnode;
67 	height = root->height - 1;
68 	if (index > radix_max(root))
69 		goto out;
70 	while (height && node)
71 		node = node->slots[radix_pos(index, height--)];
72 	if (node)
73 		item = node->slots[radix_pos(index, 0)];
74 
75 out:
76 	return (item);
77 }
78 
79 bool
radix_tree_iter_find(struct radix_tree_root * root,struct radix_tree_iter * iter,void *** pppslot)80 radix_tree_iter_find(struct radix_tree_root *root, struct radix_tree_iter *iter,
81     void ***pppslot)
82 {
83 	struct radix_tree_node *node;
84 	unsigned long index = iter->index;
85 	int height;
86 
87 restart:
88 	node = root->rnode;
89 	if (node == NULL)
90 		return (false);
91 	height = root->height - 1;
92 	if (height == -1 || index > radix_max(root))
93 		return (false);
94 	do {
95 		unsigned long mask = RADIX_TREE_MAP_MASK << (RADIX_TREE_MAP_SHIFT * height);
96 		unsigned long step = 1UL << (RADIX_TREE_MAP_SHIFT * height);
97 		int pos = radix_pos(index, height);
98 		struct radix_tree_node *next;
99 
100 		/* track last slot */
101 		*pppslot = node->slots + pos;
102 
103 		next = node->slots[pos];
104 		if (next == NULL) {
105 			index += step;
106 			index &= -step;
107 			if ((index & mask) == 0)
108 				goto restart;
109 		} else {
110 			node = next;
111 			height--;
112 		}
113 	} while (height != -1);
114 	iter->index = index;
115 	return (true);
116 }
117 
118 void *
radix_tree_delete(struct radix_tree_root * root,unsigned long index)119 radix_tree_delete(struct radix_tree_root *root, unsigned long index)
120 {
121 	struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
122 	struct radix_tree_node *node;
123 	void *item;
124 	int height;
125 	int idx;
126 
127 	item = NULL;
128 	node = root->rnode;
129 	height = root->height - 1;
130 	if (index > radix_max(root))
131 		goto out;
132 	/*
133 	 * Find the node and record the path in stack.
134 	 */
135 	while (height && node) {
136 		stack[height] = node;
137 		node = node->slots[radix_pos(index, height--)];
138 	}
139 	idx = radix_pos(index, 0);
140 	if (node)
141 		item = node->slots[idx];
142 	/*
143 	 * If we removed something reduce the height of the tree.
144 	 */
145 	if (item)
146 		for (;;) {
147 			node->slots[idx] = NULL;
148 			node->count--;
149 			if (node->count > 0)
150 				break;
151 			free(node, M_RADIX);
152 			if (node == root->rnode) {
153 				root->rnode = NULL;
154 				root->height = 0;
155 				break;
156 			}
157 			height++;
158 			node = stack[height];
159 			idx = radix_pos(index, height);
160 		}
161 out:
162 	return (item);
163 }
164 
165 void
radix_tree_iter_delete(struct radix_tree_root * root,struct radix_tree_iter * iter,void ** slot)166 radix_tree_iter_delete(struct radix_tree_root *root,
167     struct radix_tree_iter *iter, void **slot)
168 {
169 	radix_tree_delete(root, iter->index);
170 }
171 
172 int
radix_tree_insert(struct radix_tree_root * root,unsigned long index,void * item)173 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
174 {
175 	struct radix_tree_node *node;
176 	struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1];
177 	int height;
178 	int idx;
179 
180 	/* bail out upon insertion of a NULL item */
181 	if (item == NULL)
182 		return (-EINVAL);
183 
184 	/* get root node, if any */
185 	node = root->rnode;
186 
187 	/* allocate root node, if any */
188 	if (node == NULL) {
189 		node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
190 		if (node == NULL)
191 			return (-ENOMEM);
192 		root->rnode = node;
193 		root->height++;
194 	}
195 
196 	/* expand radix tree as needed */
197 	while (radix_max(root) < index) {
198 
199 		/* check if the radix tree is getting too big */
200 		if (root->height == RADIX_TREE_MAX_HEIGHT)
201 			return (-E2BIG);
202 
203 		/*
204 		 * If the root radix level is not empty, we need to
205 		 * allocate a new radix level:
206 		 */
207 		if (node->count != 0) {
208 			node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
209 			if (node == NULL)
210 				return (-ENOMEM);
211 			node->slots[0] = root->rnode;
212 			node->count++;
213 			root->rnode = node;
214 		}
215 		root->height++;
216 	}
217 
218 	/* get radix tree height index */
219 	height = root->height - 1;
220 
221 	/* walk down the tree until the first missing node, if any */
222 	for ( ; height != 0; height--) {
223 		idx = radix_pos(index, height);
224 		if (node->slots[idx] == NULL)
225 			break;
226 		node = node->slots[idx];
227 	}
228 
229 	/* allocate the missing radix levels, if any */
230 	for (idx = 0; idx != height; idx++) {
231 		temp[idx] = malloc(sizeof(*node), M_RADIX,
232 		    root->gfp_mask | M_ZERO);
233 		if (temp[idx] == NULL) {
234 			while(idx--)
235 				free(temp[idx], M_RADIX);
236 			/* Check if we should free the root node as well. */
237 			if (root->rnode->count == 0) {
238 				free(root->rnode, M_RADIX);
239 				root->rnode = NULL;
240 				root->height = 0;
241 			}
242 			return (-ENOMEM);
243 		}
244 	}
245 
246 	/* setup new radix levels, if any */
247 	for ( ; height != 0; height--) {
248 		idx = radix_pos(index, height);
249 		node->slots[idx] = temp[height - 1];
250 		node->count++;
251 		node = node->slots[idx];
252 	}
253 
254 	/*
255 	 * Insert and adjust count if the item does not already exist.
256 	 */
257 	idx = radix_pos(index, 0);
258 	if (node->slots[idx])
259 		return (-EEXIST);
260 	node->slots[idx] = item;
261 	node->count++;
262 
263 	return (0);
264 }
265