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-2018 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
32 #include <sys/param.h>
33 #include <sys/systm.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 inline unsigned long
radix_max(struct radix_tree_root * root)43 radix_max(struct radix_tree_root *root)
44 {
45 return ((1UL << (root->height * RADIX_TREE_MAP_SHIFT)) - 1UL);
46 }
47
48 static inline int
radix_pos(long id,int height)49 radix_pos(long id, int height)
50 {
51 return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK;
52 }
53
54 void *
radix_tree_lookup(struct radix_tree_root * root,unsigned long index)55 radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
56 {
57 struct radix_tree_node *node;
58 void *item;
59 int height;
60
61 item = NULL;
62 node = root->rnode;
63 height = root->height - 1;
64 if (index > radix_max(root))
65 goto out;
66 while (height && node)
67 node = node->slots[radix_pos(index, height--)];
68 if (node)
69 item = node->slots[radix_pos(index, 0)];
70
71 out:
72 return (item);
73 }
74
75 bool
radix_tree_iter_find(struct radix_tree_root * root,struct radix_tree_iter * iter,void *** pppslot)76 radix_tree_iter_find(struct radix_tree_root *root, struct radix_tree_iter *iter,
77 void ***pppslot)
78 {
79 struct radix_tree_node *node;
80 unsigned long index = iter->index;
81 int height;
82
83 restart:
84 node = root->rnode;
85 if (node == NULL)
86 return (false);
87 height = root->height - 1;
88 if (height == -1 || index > radix_max(root))
89 return (false);
90 do {
91 unsigned long mask = RADIX_TREE_MAP_MASK << (RADIX_TREE_MAP_SHIFT * height);
92 unsigned long step = 1UL << (RADIX_TREE_MAP_SHIFT * height);
93 int pos = radix_pos(index, height);
94 struct radix_tree_node *next;
95
96 /* track last slot */
97 *pppslot = node->slots + pos;
98
99 next = node->slots[pos];
100 if (next == NULL) {
101 index += step;
102 index &= -step;
103 if ((index & mask) == 0)
104 goto restart;
105 } else {
106 node = next;
107 height--;
108 }
109 } while (height != -1);
110 iter->index = index;
111 return (true);
112 }
113
114 void *
radix_tree_delete(struct radix_tree_root * root,unsigned long index)115 radix_tree_delete(struct radix_tree_root *root, unsigned long index)
116 {
117 struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
118 struct radix_tree_node *node;
119 void *item;
120 int height;
121 int idx;
122
123 item = NULL;
124 node = root->rnode;
125 height = root->height - 1;
126 if (index > radix_max(root))
127 goto out;
128 /*
129 * Find the node and record the path in stack.
130 */
131 while (height && node) {
132 stack[height] = node;
133 node = node->slots[radix_pos(index, height--)];
134 }
135 idx = radix_pos(index, 0);
136 if (node)
137 item = node->slots[idx];
138 /*
139 * If we removed something reduce the height of the tree.
140 */
141 if (item)
142 for (;;) {
143 node->slots[idx] = NULL;
144 node->count--;
145 if (node->count > 0)
146 break;
147 kfree(node);
148 if (node == root->rnode) {
149 root->rnode = NULL;
150 root->height = 0;
151 break;
152 }
153 height++;
154 node = stack[height];
155 idx = radix_pos(index, height);
156 }
157 out:
158 return (item);
159 }
160
161 void
radix_tree_iter_delete(struct radix_tree_root * root,struct radix_tree_iter * iter,void ** slot)162 radix_tree_iter_delete(struct radix_tree_root *root,
163 struct radix_tree_iter *iter, void **slot)
164 {
165 radix_tree_delete(root, iter->index);
166 }
167
168 int
radix_tree_insert(struct radix_tree_root * root,unsigned long index,void * item)169 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
170 {
171 struct radix_tree_node *node;
172 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1];
173 int height;
174 int idx;
175
176 /* bail out upon insertion of a NULL item */
177 if (item == NULL)
178 return (-EINVAL);
179
180 /* get root node, if any */
181 node = root->rnode;
182
183 /* allocate root node, if any */
184 if (node == NULL) {
185 node = kmalloc(sizeof(*node), M_DRM, root->gfp_mask | M_ZERO);
186 if (node == NULL)
187 return (-ENOMEM);
188 root->rnode = node;
189 root->height++;
190 }
191
192 /* expand radix tree as needed */
193 while (radix_max(root) < index) {
194
195 /* check if the radix tree is getting too big */
196 if (root->height == RADIX_TREE_MAX_HEIGHT)
197 return (-E2BIG);
198
199 /*
200 * If the root radix level is not empty, we need to
201 * allocate a new radix level:
202 */
203 if (node->count != 0) {
204 node = kmalloc(sizeof(*node), M_DRM, root->gfp_mask | M_ZERO);
205 if (node == NULL)
206 return (-ENOMEM);
207 node->slots[0] = root->rnode;
208 node->count++;
209 root->rnode = node;
210 }
211 root->height++;
212 }
213
214 /* get radix tree height index */
215 height = root->height - 1;
216
217 /* walk down the tree until the first missing node, if any */
218 for ( ; height != 0; height--) {
219 idx = radix_pos(index, height);
220 if (node->slots[idx] == NULL)
221 break;
222 node = node->slots[idx];
223 }
224
225 /* allocate the missing radix levels, if any */
226 for (idx = 0; idx != height; idx++) {
227 temp[idx] = kmalloc(sizeof(*node), M_DRM,
228 root->gfp_mask | M_ZERO);
229 if (temp[idx] == NULL) {
230 while(idx--)
231 kfree(temp[idx]);
232 /* Check if we should free the root node as well. */
233 if (root->rnode->count == 0) {
234 kfree(root->rnode);
235 root->rnode = NULL;
236 root->height = 0;
237 }
238 return (-ENOMEM);
239 }
240 }
241
242 /* setup new radix levels, if any */
243 for ( ; height != 0; height--) {
244 idx = radix_pos(index, height);
245 node->slots[idx] = temp[height - 1];
246 node->count++;
247 node = node->slots[idx];
248 }
249
250 /*
251 * Insert and adjust count if the item does not already exist.
252 */
253 idx = radix_pos(index, 0);
254 if (node->slots[idx])
255 return (-EEXIST);
256 node->slots[idx] = item;
257 node->count++;
258
259 return (0);
260 }
261