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