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-2020 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 #include <sys/param.h>
32 #include <sys/systm.h>
33 #include <sys/malloc.h>
34 #include <sys/kernel.h>
35 #include <sys/sysctl.h>
36
37 #include <linux/slab.h>
38 #include <linux/kernel.h>
39 #include <linux/radix-tree.h>
40 #include <linux/err.h>
41
42 static MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat");
43
44 static inline unsigned long
radix_max(struct radix_tree_root * root)45 radix_max(struct radix_tree_root *root)
46 {
47 return ((1UL << (root->height * RADIX_TREE_MAP_SHIFT)) - 1UL);
48 }
49
50 static inline int
radix_pos(long id,int height)51 radix_pos(long id, int height)
52 {
53 return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK;
54 }
55
56 static void
radix_tree_clean_root_node(struct radix_tree_root * root)57 radix_tree_clean_root_node(struct radix_tree_root *root)
58 {
59 /* Check if the root node should be freed */
60 if (root->rnode->count == 0) {
61 free(root->rnode, M_RADIX);
62 root->rnode = NULL;
63 root->height = 0;
64 }
65 }
66
67 void *
radix_tree_lookup(struct radix_tree_root * root,unsigned long index)68 radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
69 {
70 struct radix_tree_node *node;
71 void *item;
72 int height;
73
74 item = NULL;
75 node = root->rnode;
76 height = root->height - 1;
77 if (index > radix_max(root))
78 goto out;
79 while (height && node)
80 node = node->slots[radix_pos(index, height--)];
81 if (node)
82 item = node->slots[radix_pos(index, 0)];
83
84 out:
85 return (item);
86 }
87
88 bool
radix_tree_iter_find(struct radix_tree_root * root,struct radix_tree_iter * iter,void *** pppslot)89 radix_tree_iter_find(struct radix_tree_root *root, struct radix_tree_iter *iter,
90 void ***pppslot)
91 {
92 struct radix_tree_node *node;
93 unsigned long index = iter->index;
94 int height;
95
96 restart:
97 node = root->rnode;
98 if (node == NULL)
99 return (false);
100 height = root->height - 1;
101 if (height == -1 || index > radix_max(root))
102 return (false);
103 do {
104 unsigned long mask = RADIX_TREE_MAP_MASK << (RADIX_TREE_MAP_SHIFT * height);
105 unsigned long step = 1UL << (RADIX_TREE_MAP_SHIFT * height);
106 int pos = radix_pos(index, height);
107 struct radix_tree_node *next;
108
109 /* track last slot */
110 *pppslot = node->slots + pos;
111
112 next = node->slots[pos];
113 if (next == NULL) {
114 index += step;
115 index &= -step;
116 if ((index & mask) == 0)
117 goto restart;
118 } else {
119 node = next;
120 height--;
121 }
122 } while (height != -1);
123 iter->index = index;
124 return (true);
125 }
126
127 void *
radix_tree_delete(struct radix_tree_root * root,unsigned long index)128 radix_tree_delete(struct radix_tree_root *root, unsigned long index)
129 {
130 struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
131 struct radix_tree_node *node;
132 void *item;
133 int height;
134 int idx;
135
136 item = NULL;
137 node = root->rnode;
138 height = root->height - 1;
139 if (index > radix_max(root))
140 goto out;
141 /*
142 * Find the node and record the path in stack.
143 */
144 while (height && node) {
145 stack[height] = node;
146 node = node->slots[radix_pos(index, height--)];
147 }
148 idx = radix_pos(index, 0);
149 if (node)
150 item = node->slots[idx];
151 /*
152 * If we removed something reduce the height of the tree.
153 */
154 if (item)
155 for (;;) {
156 node->slots[idx] = NULL;
157 node->count--;
158 if (node->count > 0)
159 break;
160 free(node, M_RADIX);
161 if (node == root->rnode) {
162 root->rnode = NULL;
163 root->height = 0;
164 break;
165 }
166 height++;
167 node = stack[height];
168 idx = radix_pos(index, height);
169 }
170 out:
171 return (item);
172 }
173
174 void
radix_tree_iter_delete(struct radix_tree_root * root,struct radix_tree_iter * iter,void ** slot)175 radix_tree_iter_delete(struct radix_tree_root *root,
176 struct radix_tree_iter *iter, void **slot)
177 {
178 radix_tree_delete(root, iter->index);
179 }
180
181 int
radix_tree_insert(struct radix_tree_root * root,unsigned long index,void * item)182 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
183 {
184 struct radix_tree_node *node;
185 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1];
186 int height;
187 int idx;
188
189 /* bail out upon insertion of a NULL item */
190 if (item == NULL)
191 return (-EINVAL);
192
193 /* get root node, if any */
194 node = root->rnode;
195
196 /* allocate root node, if any */
197 if (node == NULL) {
198 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
199 if (node == NULL)
200 return (-ENOMEM);
201 root->rnode = node;
202 root->height++;
203 }
204
205 /* expand radix tree as needed */
206 while (radix_max(root) < index) {
207 /* check if the radix tree is getting too big */
208 if (root->height == RADIX_TREE_MAX_HEIGHT) {
209 radix_tree_clean_root_node(root);
210 return (-E2BIG);
211 }
212
213 /*
214 * If the root radix level is not empty, we need to
215 * allocate a new radix level:
216 */
217 if (node->count != 0) {
218 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
219 if (node == NULL) {
220 /*
221 * Freeing the already allocated radix
222 * levels, if any, will be handled by
223 * the radix_tree_delete() function.
224 * This code path can only happen when
225 * the tree is not empty.
226 */
227 return (-ENOMEM);
228 }
229 node->slots[0] = root->rnode;
230 node->count++;
231 root->rnode = node;
232 }
233 root->height++;
234 }
235
236 /* get radix tree height index */
237 height = root->height - 1;
238
239 /* walk down the tree until the first missing node, if any */
240 for ( ; height != 0; height--) {
241 idx = radix_pos(index, height);
242 if (node->slots[idx] == NULL)
243 break;
244 node = node->slots[idx];
245 }
246
247 /* allocate the missing radix levels, if any */
248 for (idx = 0; idx != height; idx++) {
249 temp[idx] = malloc(sizeof(*node), M_RADIX,
250 root->gfp_mask | M_ZERO);
251 if (temp[idx] == NULL) {
252 while (idx--)
253 free(temp[idx], M_RADIX);
254 radix_tree_clean_root_node(root);
255 return (-ENOMEM);
256 }
257 }
258
259 /* setup new radix levels, if any */
260 for ( ; height != 0; height--) {
261 idx = radix_pos(index, height);
262 node->slots[idx] = temp[height - 1];
263 node->count++;
264 node = node->slots[idx];
265 }
266
267 /*
268 * Insert and adjust count if the item does not already exist.
269 */
270 idx = radix_pos(index, 0);
271 if (node->slots[idx])
272 return (-EEXIST);
273 node->slots[idx] = item;
274 node->count++;
275
276 return (0);
277 }
278
279 int
radix_tree_store(struct radix_tree_root * root,unsigned long index,void ** ppitem)280 radix_tree_store(struct radix_tree_root *root, unsigned long index, void **ppitem)
281 {
282 struct radix_tree_node *node;
283 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1];
284 void *pitem;
285 int height;
286 int idx;
287
288 /*
289 * Inserting a NULL item means delete it. The old pointer is
290 * stored at the location pointed to by "ppitem".
291 */
292 if (*ppitem == NULL) {
293 *ppitem = radix_tree_delete(root, index);
294 return (0);
295 }
296
297 /* get root node, if any */
298 node = root->rnode;
299
300 /* allocate root node, if any */
301 if (node == NULL) {
302 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
303 if (node == NULL)
304 return (-ENOMEM);
305 root->rnode = node;
306 root->height++;
307 }
308
309 /* expand radix tree as needed */
310 while (radix_max(root) < index) {
311 /* check if the radix tree is getting too big */
312 if (root->height == RADIX_TREE_MAX_HEIGHT) {
313 radix_tree_clean_root_node(root);
314 return (-E2BIG);
315 }
316
317 /*
318 * If the root radix level is not empty, we need to
319 * allocate a new radix level:
320 */
321 if (node->count != 0) {
322 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
323 if (node == NULL) {
324 /*
325 * Freeing the already allocated radix
326 * levels, if any, will be handled by
327 * the radix_tree_delete() function.
328 * This code path can only happen when
329 * the tree is not empty.
330 */
331 return (-ENOMEM);
332 }
333 node->slots[0] = root->rnode;
334 node->count++;
335 root->rnode = node;
336 }
337 root->height++;
338 }
339
340 /* get radix tree height index */
341 height = root->height - 1;
342
343 /* walk down the tree until the first missing node, if any */
344 for ( ; height != 0; height--) {
345 idx = radix_pos(index, height);
346 if (node->slots[idx] == NULL)
347 break;
348 node = node->slots[idx];
349 }
350
351 /* allocate the missing radix levels, if any */
352 for (idx = 0; idx != height; idx++) {
353 temp[idx] = malloc(sizeof(*node), M_RADIX,
354 root->gfp_mask | M_ZERO);
355 if (temp[idx] == NULL) {
356 while (idx--)
357 free(temp[idx], M_RADIX);
358 radix_tree_clean_root_node(root);
359 return (-ENOMEM);
360 }
361 }
362
363 /* setup new radix levels, if any */
364 for ( ; height != 0; height--) {
365 idx = radix_pos(index, height);
366 node->slots[idx] = temp[height - 1];
367 node->count++;
368 node = node->slots[idx];
369 }
370
371 /*
372 * Insert and adjust count if the item does not already exist.
373 */
374 idx = radix_pos(index, 0);
375 /* swap */
376 pitem = node->slots[idx];
377 node->slots[idx] = *ppitem;
378 *ppitem = pitem;
379
380 if (pitem == NULL)
381 node->count++;
382 return (0);
383 }
384