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, 2014 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 int
radix_max(struct radix_tree_root * root)44 radix_max(struct radix_tree_root *root)
45 {
46 return (1 << (root->height * RADIX_TREE_MAP_SHIFT)) - 1;
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 void *
radix_tree_lookup(struct radix_tree_root * root,unsigned long index)56 radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
57 {
58 struct radix_tree_node *node;
59 void *item;
60 int height;
61
62 item = NULL;
63 node = root->rnode;
64 height = root->height - 1;
65 if (index > radix_max(root))
66 goto out;
67 while (height && node)
68 node = node->slots[radix_pos(index, height--)];
69 if (node)
70 item = node->slots[radix_pos(index, 0)];
71
72 out:
73 return (item);
74 }
75
76 void *
radix_tree_delete(struct radix_tree_root * root,unsigned long index)77 radix_tree_delete(struct radix_tree_root *root, unsigned long index)
78 {
79 struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
80 struct radix_tree_node *node;
81 void *item;
82 int height;
83 int idx;
84
85 item = NULL;
86 node = root->rnode;
87 height = root->height - 1;
88 if (index > radix_max(root))
89 goto out;
90 /*
91 * Find the node and record the path in stack.
92 */
93 while (height && node) {
94 stack[height] = node;
95 node = node->slots[radix_pos(index, height--)];
96 }
97 idx = radix_pos(index, 0);
98 if (node)
99 item = node->slots[idx];
100 /*
101 * If we removed something reduce the height of the tree.
102 */
103 if (item)
104 for (;;) {
105 node->slots[idx] = NULL;
106 node->count--;
107 if (node->count > 0)
108 break;
109 free(node, M_RADIX);
110 if (node == root->rnode) {
111 root->rnode = NULL;
112 root->height = 0;
113 break;
114 }
115 height++;
116 node = stack[height];
117 idx = radix_pos(index, height);
118 }
119 out:
120 return (item);
121 }
122
123 int
radix_tree_insert(struct radix_tree_root * root,unsigned long index,void * item)124 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
125 {
126 struct radix_tree_node *node;
127 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1];
128 int height;
129 int idx;
130
131 /* bail out upon insertion of a NULL item */
132 if (item == NULL)
133 return (-EINVAL);
134
135 /* get root node, if any */
136 node = root->rnode;
137
138 /* allocate root node, if any */
139 if (node == NULL) {
140 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
141 if (node == NULL)
142 return (-ENOMEM);
143 root->rnode = node;
144 root->height++;
145 }
146
147 /* expand radix tree as needed */
148 while (radix_max(root) < index) {
149
150 /* check if the radix tree is getting too big */
151 if (root->height == RADIX_TREE_MAX_HEIGHT)
152 return (-E2BIG);
153
154 /*
155 * If the root radix level is not empty, we need to
156 * allocate a new radix level:
157 */
158 if (node->count != 0) {
159 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
160 if (node == NULL)
161 return (-ENOMEM);
162 node->slots[0] = root->rnode;
163 node->count++;
164 root->rnode = node;
165 }
166 root->height++;
167 }
168
169 /* get radix tree height index */
170 height = root->height - 1;
171
172 /* walk down the tree until the first missing node, if any */
173 for ( ; height != 0; height--) {
174 idx = radix_pos(index, height);
175 if (node->slots[idx] == NULL)
176 break;
177 node = node->slots[idx];
178 }
179
180 /* allocate the missing radix levels, if any */
181 for (idx = 0; idx != height; idx++) {
182 temp[idx] = malloc(sizeof(*node), M_RADIX,
183 root->gfp_mask | M_ZERO);
184 if (temp[idx] == NULL) {
185 while(idx--)
186 free(temp[idx], M_RADIX);
187 /* check if we should free the root node aswell */
188 if (root->rnode->count == 0) {
189 free(root->rnode, M_RADIX);
190 root->rnode = NULL;
191 root->height = 0;
192 }
193 return (-ENOMEM);
194 }
195 }
196
197 /* setup new radix levels, if any */
198 for ( ; height != 0; height--) {
199 idx = radix_pos(index, height);
200 node->slots[idx] = temp[height - 1];
201 node->count++;
202 node = node->slots[idx];
203 }
204
205 /*
206 * Insert and adjust count if the item does not already exist.
207 */
208 idx = radix_pos(index, 0);
209 if (node->slots[idx])
210 return (-EEXIST);
211 node->slots[idx] = item;
212 node->count++;
213
214 return (0);
215 }
216