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(const struct radix_tree_root * root)44 radix_max(const 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 inline int
root_tag_get(const struct radix_tree_root * root,unsigned tag)56 root_tag_get(const struct radix_tree_root *root, unsigned tag)
57 {
58 return (test_bit(tag, root->tags));
59 }
60
61 static inline void
root_tag_set(struct radix_tree_root * root,unsigned tag)62 root_tag_set(struct radix_tree_root *root, unsigned tag)
63 {
64 set_bit(tag, root->tags);
65 }
66
67 static inline void
root_tag_clear(struct radix_tree_root * root,unsigned tag)68 root_tag_clear(struct radix_tree_root *root, unsigned tag)
69 {
70 clear_bit(tag, root->tags);
71 }
72
73 static inline int
tag_get(const struct radix_tree_node * node,unsigned int tag,int pos)74 tag_get(const struct radix_tree_node *node, unsigned int tag, int pos)
75 {
76 return (test_bit(pos, node->tags[tag]));
77 }
78
79 static inline void
tag_set(struct radix_tree_node * node,unsigned int tag,int pos)80 tag_set(struct radix_tree_node *node, unsigned int tag, int pos)
81 {
82 set_bit(pos, node->tags[tag]);
83 }
84
85 static inline void
tag_clear(struct radix_tree_node * node,unsigned int tag,int pos)86 tag_clear(struct radix_tree_node *node, unsigned int tag, int pos)
87 {
88 clear_bit(pos, node->tags[tag]);
89 }
90
91 static inline bool
any_tag_set(const struct radix_tree_node * node,unsigned int tag)92 any_tag_set(const struct radix_tree_node *node, unsigned int tag)
93 {
94 unsigned int pos;
95
96 for (pos = 0; pos < RADIX_TREE_TAG_LONGS; pos++)
97 if (node->tags[tag][pos])
98 return (true);
99
100 return (false);
101 }
102
103 static void
node_tag_clear(struct radix_tree_root * root,struct radix_tree_node * stack[],unsigned long index,unsigned int tag)104 node_tag_clear(struct radix_tree_root *root, struct radix_tree_node *stack[],
105 unsigned long index, unsigned int tag)
106 {
107 struct radix_tree_node *node;
108 int height, pos;
109
110 height = 1;
111 node = stack[height];
112
113 while (node && height <= root->height - 1) {
114 pos = radix_pos(index, height);
115 if (!tag_get(node, tag, pos))
116 return;
117
118 tag_clear(node, tag, pos);
119 if (any_tag_set(node, tag))
120 return;
121
122 height++;
123 node = stack[height];
124 }
125
126 if (root_tag_get(root, tag))
127 root_tag_clear(root, tag);
128 }
129
130 static void
radix_tree_clean_root_node(struct radix_tree_root * root)131 radix_tree_clean_root_node(struct radix_tree_root *root)
132 {
133 /* Check if the root node should be freed */
134 if (root->rnode->count == 0) {
135 free(root->rnode, M_RADIX);
136 root->rnode = NULL;
137 root->height = 0;
138 }
139 }
140
141 void *
radix_tree_lookup(const struct radix_tree_root * root,unsigned long index)142 radix_tree_lookup(const struct radix_tree_root *root, unsigned long index)
143 {
144 struct radix_tree_node *node;
145 void *item;
146 int height;
147
148 item = NULL;
149 node = root->rnode;
150 height = root->height - 1;
151 if (index > radix_max(root))
152 goto out;
153 while (height && node)
154 node = node->slots[radix_pos(index, height--)];
155 if (node)
156 item = node->slots[radix_pos(index, 0)];
157
158 out:
159 return (item);
160 }
161
162 unsigned int
radix_tree_gang_lookup(const struct radix_tree_root * root,void ** results,unsigned long first_index,unsigned int max_items)163 radix_tree_gang_lookup(const struct radix_tree_root *root, void **results,
164 unsigned long first_index, unsigned int max_items)
165 {
166 struct radix_tree_iter iter;
167 void **slot;
168 int count;
169
170 count = 0;
171 if (max_items == 0)
172 return (count);
173
174 radix_tree_for_each_slot(slot, root, &iter, first_index) {
175 results[count] = *slot;
176 if (results[count] == NULL)
177 continue;
178
179 count++;
180 if (count == max_items)
181 break;
182 }
183
184 return (count);
185 }
186
187 unsigned int
radix_tree_gang_lookup_tag(const struct radix_tree_root * root,void ** results,unsigned long first_index,unsigned int max_items,unsigned int tag)188 radix_tree_gang_lookup_tag(const struct radix_tree_root *root,
189 void **results, unsigned long first_index, unsigned int max_items,
190 unsigned int tag)
191 {
192 struct radix_tree_iter iter;
193 void **slot;
194 int count;
195
196 count = 0;
197 if (max_items == 0)
198 return (count);
199
200 radix_tree_for_each_slot_tagged(slot, root, &iter, first_index, tag) {
201 results[count] = *slot;
202 if (results[count] == NULL)
203 continue;
204
205 count++;
206 if (count == max_items)
207 break;
208 }
209
210 return (count);
211 }
212
213 bool
radix_tree_iter_find(const struct radix_tree_root * root,struct radix_tree_iter * iter,void *** pppslot,int flags)214 radix_tree_iter_find(const struct radix_tree_root *root,
215 struct radix_tree_iter *iter, void ***pppslot, int flags)
216 {
217 struct radix_tree_node *node;
218 unsigned long index = iter->index;
219 unsigned int tag;
220 int height;
221
222 tag = flags & RADIX_TREE_ITER_TAG_MASK;
223 if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
224 return (false);
225
226 restart:
227 node = root->rnode;
228 if (node == NULL)
229 return (false);
230 height = root->height - 1;
231 if (height == -1 || index > radix_max(root))
232 return (false);
233 do {
234 unsigned long mask = RADIX_TREE_MAP_MASK << (RADIX_TREE_MAP_SHIFT * height);
235 unsigned long step = 1UL << (RADIX_TREE_MAP_SHIFT * height);
236 int pos = radix_pos(index, height);
237 struct radix_tree_node *next;
238
239 /* track last slot */
240 *pppslot = node->slots + pos;
241
242 next = node->slots[pos];
243 if (next == NULL ||
244 (flags & RADIX_TREE_ITER_TAGGED &&
245 !tag_get(next, tag, pos))) {
246 index += step;
247 index &= -step;
248 if ((index & mask) == 0)
249 goto restart;
250 } else {
251 node = next;
252 height--;
253 }
254 } while (height != -1);
255 iter->index = index;
256 return (true);
257 }
258
259 void *
radix_tree_delete(struct radix_tree_root * root,unsigned long index)260 radix_tree_delete(struct radix_tree_root *root, unsigned long index)
261 {
262 struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
263 struct radix_tree_node *node;
264 void *item;
265 int height;
266 int idx;
267 int tag;
268
269 item = NULL;
270 node = root->rnode;
271 height = root->height - 1;
272 if (index > radix_max(root))
273 goto out;
274 /*
275 * Find the node and record the path in stack.
276 */
277 while (height && node) {
278 stack[height] = node;
279 node = node->slots[radix_pos(index, height--)];
280 }
281
282 if (node) {
283 idx = radix_pos(index, 0);
284 item = node->slots[idx];
285
286 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
287 node_tag_clear(root, stack, index, tag);
288 }
289
290 /*
291 * If we removed something reduce the height of the tree.
292 */
293 if (item)
294 for (;;) {
295 node->slots[idx] = NULL;
296 node->count--;
297 if (node->count > 0)
298 break;
299 free(node, M_RADIX);
300 if (node == root->rnode) {
301 root->rnode = NULL;
302 root->height = 0;
303 break;
304 }
305 height++;
306 node = stack[height];
307 idx = radix_pos(index, height);
308 }
309 out:
310 return (item);
311 }
312
313 void
radix_tree_iter_delete(struct radix_tree_root * root,struct radix_tree_iter * iter,void ** slot)314 radix_tree_iter_delete(struct radix_tree_root *root,
315 struct radix_tree_iter *iter, void **slot)
316 {
317 radix_tree_delete(root, iter->index);
318 }
319
320 int
radix_tree_insert(struct radix_tree_root * root,unsigned long index,void * item)321 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
322 {
323 struct radix_tree_node *node;
324 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1];
325 int height;
326 int idx;
327
328 /* bail out upon insertion of a NULL item */
329 if (item == NULL)
330 return (-EINVAL);
331
332 /* get root node, if any */
333 node = root->rnode;
334
335 /* allocate root node, if any */
336 if (node == NULL) {
337 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
338 if (node == NULL)
339 return (-ENOMEM);
340 root->rnode = node;
341 root->height++;
342 }
343
344 /* expand radix tree as needed */
345 while (radix_max(root) < index) {
346 /* check if the radix tree is getting too big */
347 if (root->height == RADIX_TREE_MAX_HEIGHT) {
348 radix_tree_clean_root_node(root);
349 return (-E2BIG);
350 }
351
352 /*
353 * If the root radix level is not empty, we need to
354 * allocate a new radix level:
355 */
356 if (node->count != 0) {
357 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
358 if (node == NULL) {
359 /*
360 * Freeing the already allocated radix
361 * levels, if any, will be handled by
362 * the radix_tree_delete() function.
363 * This code path can only happen when
364 * the tree is not empty.
365 */
366 return (-ENOMEM);
367 }
368 node->slots[0] = root->rnode;
369 node->count++;
370 root->rnode = node;
371 }
372 root->height++;
373 }
374
375 /* get radix tree height index */
376 height = root->height - 1;
377
378 /* walk down the tree until the first missing node, if any */
379 for ( ; height != 0; height--) {
380 idx = radix_pos(index, height);
381 if (node->slots[idx] == NULL)
382 break;
383 node = node->slots[idx];
384 }
385
386 /* allocate the missing radix levels, if any */
387 for (idx = 0; idx != height; idx++) {
388 temp[idx] = malloc(sizeof(*node), M_RADIX,
389 root->gfp_mask | M_ZERO);
390 if (temp[idx] == NULL) {
391 while (idx--)
392 free(temp[idx], M_RADIX);
393 radix_tree_clean_root_node(root);
394 return (-ENOMEM);
395 }
396 }
397
398 /* setup new radix levels, if any */
399 for ( ; height != 0; height--) {
400 idx = radix_pos(index, height);
401 node->slots[idx] = temp[height - 1];
402 node->count++;
403 node = node->slots[idx];
404 }
405
406 /*
407 * Insert and adjust count if the item does not already exist.
408 */
409 idx = radix_pos(index, 0);
410 if (node->slots[idx])
411 return (-EEXIST);
412 node->slots[idx] = item;
413 node->count++;
414
415 return (0);
416 }
417
418 int
radix_tree_store(struct radix_tree_root * root,unsigned long index,void ** ppitem)419 radix_tree_store(struct radix_tree_root *root, unsigned long index, void **ppitem)
420 {
421 struct radix_tree_node *node;
422 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1];
423 void *pitem;
424 int height;
425 int idx;
426
427 /*
428 * Inserting a NULL item means delete it. The old pointer is
429 * stored at the location pointed to by "ppitem".
430 */
431 if (*ppitem == NULL) {
432 *ppitem = radix_tree_delete(root, index);
433 return (0);
434 }
435
436 /* get root node, if any */
437 node = root->rnode;
438
439 /* allocate root node, if any */
440 if (node == NULL) {
441 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
442 if (node == NULL)
443 return (-ENOMEM);
444 root->rnode = node;
445 root->height++;
446 }
447
448 /* expand radix tree as needed */
449 while (radix_max(root) < index) {
450 /* check if the radix tree is getting too big */
451 if (root->height == RADIX_TREE_MAX_HEIGHT) {
452 radix_tree_clean_root_node(root);
453 return (-E2BIG);
454 }
455
456 /*
457 * If the root radix level is not empty, we need to
458 * allocate a new radix level:
459 */
460 if (node->count != 0) {
461 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
462 if (node == NULL) {
463 /*
464 * Freeing the already allocated radix
465 * levels, if any, will be handled by
466 * the radix_tree_delete() function.
467 * This code path can only happen when
468 * the tree is not empty.
469 */
470 return (-ENOMEM);
471 }
472 node->slots[0] = root->rnode;
473 node->count++;
474 root->rnode = node;
475 }
476 root->height++;
477 }
478
479 /* get radix tree height index */
480 height = root->height - 1;
481
482 /* walk down the tree until the first missing node, if any */
483 for ( ; height != 0; height--) {
484 idx = radix_pos(index, height);
485 if (node->slots[idx] == NULL)
486 break;
487 node = node->slots[idx];
488 }
489
490 /* allocate the missing radix levels, if any */
491 for (idx = 0; idx != height; idx++) {
492 temp[idx] = malloc(sizeof(*node), M_RADIX,
493 root->gfp_mask | M_ZERO);
494 if (temp[idx] == NULL) {
495 while (idx--)
496 free(temp[idx], M_RADIX);
497 radix_tree_clean_root_node(root);
498 return (-ENOMEM);
499 }
500 }
501
502 /* setup new radix levels, if any */
503 for ( ; height != 0; height--) {
504 idx = radix_pos(index, height);
505 node->slots[idx] = temp[height - 1];
506 node->count++;
507 node = node->slots[idx];
508 }
509
510 /*
511 * Insert and adjust count if the item does not already exist.
512 */
513 idx = radix_pos(index, 0);
514 /* swap */
515 pitem = node->slots[idx];
516 node->slots[idx] = *ppitem;
517 *ppitem = pitem;
518
519 if (pitem == NULL)
520 node->count++;
521 return (0);
522 }
523
524 void *
radix_tree_tag_set(struct radix_tree_root * root,unsigned long index,unsigned int tag)525 radix_tree_tag_set(struct radix_tree_root *root, unsigned long index,
526 unsigned int tag)
527 {
528 struct radix_tree_node *node;
529 void *item;
530 int height, pos;
531
532 item = NULL;
533 node = root->rnode;
534 height = root->height - 1;
535 if (index > radix_max(root))
536 goto out;
537
538 while (height) {
539 KASSERT(
540 node != NULL,
541 ("Node at index %lu does not exist in radix tree %p",
542 index, root));
543
544 pos = radix_pos(index, height--);
545 node = node->slots[pos];
546
547 if (!tag_get(node, tag, pos))
548 tag_set(node, tag, pos);
549 }
550
551 item = node->slots[radix_pos(index, 0)];
552
553 root_tag_set(root, tag);
554
555 out:
556 return (item);
557 }
558
559 void *
radix_tree_tag_clear(struct radix_tree_root * root,unsigned long index,unsigned int tag)560 radix_tree_tag_clear(struct radix_tree_root *root,
561 unsigned long index, unsigned int tag)
562 {
563 struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
564 struct radix_tree_node *node;
565 void *item;
566 int height;
567
568 item = NULL;
569 node = root->rnode;
570 height = root->height - 1;
571 if (index > radix_max(root))
572 goto out;
573
574 while (height && node) {
575 stack[height] = node;
576 node = node->slots[radix_pos(index, height--)];
577 }
578
579 if (node) {
580 item = node->slots[radix_pos(index, 0)];
581
582 node_tag_clear(root, stack, index, tag);
583 }
584
585 out:
586 return (item);
587 }
588
589 int
radix_tree_tagged(const struct radix_tree_root * root,unsigned int tag)590 radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag)
591 {
592 return (root_tag_get(root, tag));
593 }
594