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