1*a3a2f5cbSFrançois Tigeot /*-
2*a3a2f5cbSFrançois Tigeot * Copyright (c) 2010 Isilon Systems, Inc.
3*a3a2f5cbSFrançois Tigeot * Copyright (c) 2010 iX Systems, Inc.
4*a3a2f5cbSFrançois Tigeot * Copyright (c) 2010 Panasas, Inc.
5*a3a2f5cbSFrançois Tigeot * Copyright (c) 2013-2018 Mellanox Technologies, Ltd.
6*a3a2f5cbSFrançois Tigeot * All rights reserved.
7*a3a2f5cbSFrançois Tigeot *
8*a3a2f5cbSFrançois Tigeot * Redistribution and use in source and binary forms, with or without
9*a3a2f5cbSFrançois Tigeot * modification, are permitted provided that the following conditions
10*a3a2f5cbSFrançois Tigeot * are met:
11*a3a2f5cbSFrançois Tigeot * 1. Redistributions of source code must retain the above copyright
12*a3a2f5cbSFrançois Tigeot * notice unmodified, this list of conditions, and the following
13*a3a2f5cbSFrançois Tigeot * disclaimer.
14*a3a2f5cbSFrançois Tigeot * 2. Redistributions in binary form must reproduce the above copyright
15*a3a2f5cbSFrançois Tigeot * notice, this list of conditions and the following disclaimer in the
16*a3a2f5cbSFrançois Tigeot * documentation and/or other materials provided with the distribution.
17*a3a2f5cbSFrançois Tigeot *
18*a3a2f5cbSFrançois Tigeot * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19*a3a2f5cbSFrançois Tigeot * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20*a3a2f5cbSFrançois Tigeot * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21*a3a2f5cbSFrançois Tigeot * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22*a3a2f5cbSFrançois Tigeot * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23*a3a2f5cbSFrançois Tigeot * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24*a3a2f5cbSFrançois Tigeot * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25*a3a2f5cbSFrançois Tigeot * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26*a3a2f5cbSFrançois Tigeot * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27*a3a2f5cbSFrançois Tigeot * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28*a3a2f5cbSFrançois Tigeot */
29*a3a2f5cbSFrançois Tigeot
30*a3a2f5cbSFrançois Tigeot #include <sys/cdefs.h>
31*a3a2f5cbSFrançois Tigeot
32*a3a2f5cbSFrançois Tigeot #include <sys/param.h>
33*a3a2f5cbSFrançois Tigeot #include <sys/systm.h>
34*a3a2f5cbSFrançois Tigeot #include <sys/kernel.h>
35*a3a2f5cbSFrançois Tigeot #include <sys/sysctl.h>
36*a3a2f5cbSFrançois Tigeot
37*a3a2f5cbSFrançois Tigeot #include <linux/slab.h>
38*a3a2f5cbSFrançois Tigeot #include <linux/kernel.h>
39*a3a2f5cbSFrançois Tigeot #include <linux/radix-tree.h>
40*a3a2f5cbSFrançois Tigeot #include <linux/err.h>
41*a3a2f5cbSFrançois Tigeot
42*a3a2f5cbSFrançois Tigeot static inline unsigned long
radix_max(struct radix_tree_root * root)43*a3a2f5cbSFrançois Tigeot radix_max(struct radix_tree_root *root)
44*a3a2f5cbSFrançois Tigeot {
45*a3a2f5cbSFrançois Tigeot return ((1UL << (root->height * RADIX_TREE_MAP_SHIFT)) - 1UL);
46*a3a2f5cbSFrançois Tigeot }
47*a3a2f5cbSFrançois Tigeot
48*a3a2f5cbSFrançois Tigeot static inline int
radix_pos(long id,int height)49*a3a2f5cbSFrançois Tigeot radix_pos(long id, int height)
50*a3a2f5cbSFrançois Tigeot {
51*a3a2f5cbSFrançois Tigeot return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK;
52*a3a2f5cbSFrançois Tigeot }
53*a3a2f5cbSFrançois Tigeot
54*a3a2f5cbSFrançois Tigeot void *
radix_tree_lookup(struct radix_tree_root * root,unsigned long index)55*a3a2f5cbSFrançois Tigeot radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
56*a3a2f5cbSFrançois Tigeot {
57*a3a2f5cbSFrançois Tigeot struct radix_tree_node *node;
58*a3a2f5cbSFrançois Tigeot void *item;
59*a3a2f5cbSFrançois Tigeot int height;
60*a3a2f5cbSFrançois Tigeot
61*a3a2f5cbSFrançois Tigeot item = NULL;
62*a3a2f5cbSFrançois Tigeot node = root->rnode;
63*a3a2f5cbSFrançois Tigeot height = root->height - 1;
64*a3a2f5cbSFrançois Tigeot if (index > radix_max(root))
65*a3a2f5cbSFrançois Tigeot goto out;
66*a3a2f5cbSFrançois Tigeot while (height && node)
67*a3a2f5cbSFrançois Tigeot node = node->slots[radix_pos(index, height--)];
68*a3a2f5cbSFrançois Tigeot if (node)
69*a3a2f5cbSFrançois Tigeot item = node->slots[radix_pos(index, 0)];
70*a3a2f5cbSFrançois Tigeot
71*a3a2f5cbSFrançois Tigeot out:
72*a3a2f5cbSFrançois Tigeot return (item);
73*a3a2f5cbSFrançois Tigeot }
74*a3a2f5cbSFrançois Tigeot
75*a3a2f5cbSFrançois Tigeot bool
radix_tree_iter_find(struct radix_tree_root * root,struct radix_tree_iter * iter,void *** pppslot)76*a3a2f5cbSFrançois Tigeot radix_tree_iter_find(struct radix_tree_root *root, struct radix_tree_iter *iter,
77*a3a2f5cbSFrançois Tigeot void ***pppslot)
78*a3a2f5cbSFrançois Tigeot {
79*a3a2f5cbSFrançois Tigeot struct radix_tree_node *node;
80*a3a2f5cbSFrançois Tigeot unsigned long index = iter->index;
81*a3a2f5cbSFrançois Tigeot int height;
82*a3a2f5cbSFrançois Tigeot
83*a3a2f5cbSFrançois Tigeot restart:
84*a3a2f5cbSFrançois Tigeot node = root->rnode;
85*a3a2f5cbSFrançois Tigeot if (node == NULL)
86*a3a2f5cbSFrançois Tigeot return (false);
87*a3a2f5cbSFrançois Tigeot height = root->height - 1;
88*a3a2f5cbSFrançois Tigeot if (height == -1 || index > radix_max(root))
89*a3a2f5cbSFrançois Tigeot return (false);
90*a3a2f5cbSFrançois Tigeot do {
91*a3a2f5cbSFrançois Tigeot unsigned long mask = RADIX_TREE_MAP_MASK << (RADIX_TREE_MAP_SHIFT * height);
92*a3a2f5cbSFrançois Tigeot unsigned long step = 1UL << (RADIX_TREE_MAP_SHIFT * height);
93*a3a2f5cbSFrançois Tigeot int pos = radix_pos(index, height);
94*a3a2f5cbSFrançois Tigeot struct radix_tree_node *next;
95*a3a2f5cbSFrançois Tigeot
96*a3a2f5cbSFrançois Tigeot /* track last slot */
97*a3a2f5cbSFrançois Tigeot *pppslot = node->slots + pos;
98*a3a2f5cbSFrançois Tigeot
99*a3a2f5cbSFrançois Tigeot next = node->slots[pos];
100*a3a2f5cbSFrançois Tigeot if (next == NULL) {
101*a3a2f5cbSFrançois Tigeot index += step;
102*a3a2f5cbSFrançois Tigeot index &= -step;
103*a3a2f5cbSFrançois Tigeot if ((index & mask) == 0)
104*a3a2f5cbSFrançois Tigeot goto restart;
105*a3a2f5cbSFrançois Tigeot } else {
106*a3a2f5cbSFrançois Tigeot node = next;
107*a3a2f5cbSFrançois Tigeot height--;
108*a3a2f5cbSFrançois Tigeot }
109*a3a2f5cbSFrançois Tigeot } while (height != -1);
110*a3a2f5cbSFrançois Tigeot iter->index = index;
111*a3a2f5cbSFrançois Tigeot return (true);
112*a3a2f5cbSFrançois Tigeot }
113*a3a2f5cbSFrançois Tigeot
114*a3a2f5cbSFrançois Tigeot void *
radix_tree_delete(struct radix_tree_root * root,unsigned long index)115*a3a2f5cbSFrançois Tigeot radix_tree_delete(struct radix_tree_root *root, unsigned long index)
116*a3a2f5cbSFrançois Tigeot {
117*a3a2f5cbSFrançois Tigeot struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
118*a3a2f5cbSFrançois Tigeot struct radix_tree_node *node;
119*a3a2f5cbSFrançois Tigeot void *item;
120*a3a2f5cbSFrançois Tigeot int height;
121*a3a2f5cbSFrançois Tigeot int idx;
122*a3a2f5cbSFrançois Tigeot
123*a3a2f5cbSFrançois Tigeot item = NULL;
124*a3a2f5cbSFrançois Tigeot node = root->rnode;
125*a3a2f5cbSFrançois Tigeot height = root->height - 1;
126*a3a2f5cbSFrançois Tigeot if (index > radix_max(root))
127*a3a2f5cbSFrançois Tigeot goto out;
128*a3a2f5cbSFrançois Tigeot /*
129*a3a2f5cbSFrançois Tigeot * Find the node and record the path in stack.
130*a3a2f5cbSFrançois Tigeot */
131*a3a2f5cbSFrançois Tigeot while (height && node) {
132*a3a2f5cbSFrançois Tigeot stack[height] = node;
133*a3a2f5cbSFrançois Tigeot node = node->slots[radix_pos(index, height--)];
134*a3a2f5cbSFrançois Tigeot }
135*a3a2f5cbSFrançois Tigeot idx = radix_pos(index, 0);
136*a3a2f5cbSFrançois Tigeot if (node)
137*a3a2f5cbSFrançois Tigeot item = node->slots[idx];
138*a3a2f5cbSFrançois Tigeot /*
139*a3a2f5cbSFrançois Tigeot * If we removed something reduce the height of the tree.
140*a3a2f5cbSFrançois Tigeot */
141*a3a2f5cbSFrançois Tigeot if (item)
142*a3a2f5cbSFrançois Tigeot for (;;) {
143*a3a2f5cbSFrançois Tigeot node->slots[idx] = NULL;
144*a3a2f5cbSFrançois Tigeot node->count--;
145*a3a2f5cbSFrançois Tigeot if (node->count > 0)
146*a3a2f5cbSFrançois Tigeot break;
147*a3a2f5cbSFrançois Tigeot kfree(node);
148*a3a2f5cbSFrançois Tigeot if (node == root->rnode) {
149*a3a2f5cbSFrançois Tigeot root->rnode = NULL;
150*a3a2f5cbSFrançois Tigeot root->height = 0;
151*a3a2f5cbSFrançois Tigeot break;
152*a3a2f5cbSFrançois Tigeot }
153*a3a2f5cbSFrançois Tigeot height++;
154*a3a2f5cbSFrançois Tigeot node = stack[height];
155*a3a2f5cbSFrançois Tigeot idx = radix_pos(index, height);
156*a3a2f5cbSFrançois Tigeot }
157*a3a2f5cbSFrançois Tigeot out:
158*a3a2f5cbSFrançois Tigeot return (item);
159*a3a2f5cbSFrançois Tigeot }
160*a3a2f5cbSFrançois Tigeot
161*a3a2f5cbSFrançois Tigeot void
radix_tree_iter_delete(struct radix_tree_root * root,struct radix_tree_iter * iter,void ** slot)162*a3a2f5cbSFrançois Tigeot radix_tree_iter_delete(struct radix_tree_root *root,
163*a3a2f5cbSFrançois Tigeot struct radix_tree_iter *iter, void **slot)
164*a3a2f5cbSFrançois Tigeot {
165*a3a2f5cbSFrançois Tigeot radix_tree_delete(root, iter->index);
166*a3a2f5cbSFrançois Tigeot }
167*a3a2f5cbSFrançois Tigeot
168*a3a2f5cbSFrançois Tigeot int
radix_tree_insert(struct radix_tree_root * root,unsigned long index,void * item)169*a3a2f5cbSFrançois Tigeot radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
170*a3a2f5cbSFrançois Tigeot {
171*a3a2f5cbSFrançois Tigeot struct radix_tree_node *node;
172*a3a2f5cbSFrançois Tigeot struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1];
173*a3a2f5cbSFrançois Tigeot int height;
174*a3a2f5cbSFrançois Tigeot int idx;
175*a3a2f5cbSFrançois Tigeot
176*a3a2f5cbSFrançois Tigeot /* bail out upon insertion of a NULL item */
177*a3a2f5cbSFrançois Tigeot if (item == NULL)
178*a3a2f5cbSFrançois Tigeot return (-EINVAL);
179*a3a2f5cbSFrançois Tigeot
180*a3a2f5cbSFrançois Tigeot /* get root node, if any */
181*a3a2f5cbSFrançois Tigeot node = root->rnode;
182*a3a2f5cbSFrançois Tigeot
183*a3a2f5cbSFrançois Tigeot /* allocate root node, if any */
184*a3a2f5cbSFrançois Tigeot if (node == NULL) {
185*a3a2f5cbSFrançois Tigeot node = kmalloc(sizeof(*node), M_DRM, root->gfp_mask | M_ZERO);
186*a3a2f5cbSFrançois Tigeot if (node == NULL)
187*a3a2f5cbSFrançois Tigeot return (-ENOMEM);
188*a3a2f5cbSFrançois Tigeot root->rnode = node;
189*a3a2f5cbSFrançois Tigeot root->height++;
190*a3a2f5cbSFrançois Tigeot }
191*a3a2f5cbSFrançois Tigeot
192*a3a2f5cbSFrançois Tigeot /* expand radix tree as needed */
193*a3a2f5cbSFrançois Tigeot while (radix_max(root) < index) {
194*a3a2f5cbSFrançois Tigeot
195*a3a2f5cbSFrançois Tigeot /* check if the radix tree is getting too big */
196*a3a2f5cbSFrançois Tigeot if (root->height == RADIX_TREE_MAX_HEIGHT)
197*a3a2f5cbSFrançois Tigeot return (-E2BIG);
198*a3a2f5cbSFrançois Tigeot
199*a3a2f5cbSFrançois Tigeot /*
200*a3a2f5cbSFrançois Tigeot * If the root radix level is not empty, we need to
201*a3a2f5cbSFrançois Tigeot * allocate a new radix level:
202*a3a2f5cbSFrançois Tigeot */
203*a3a2f5cbSFrançois Tigeot if (node->count != 0) {
204*a3a2f5cbSFrançois Tigeot node = kmalloc(sizeof(*node), M_DRM, root->gfp_mask | M_ZERO);
205*a3a2f5cbSFrançois Tigeot if (node == NULL)
206*a3a2f5cbSFrançois Tigeot return (-ENOMEM);
207*a3a2f5cbSFrançois Tigeot node->slots[0] = root->rnode;
208*a3a2f5cbSFrançois Tigeot node->count++;
209*a3a2f5cbSFrançois Tigeot root->rnode = node;
210*a3a2f5cbSFrançois Tigeot }
211*a3a2f5cbSFrançois Tigeot root->height++;
212*a3a2f5cbSFrançois Tigeot }
213*a3a2f5cbSFrançois Tigeot
214*a3a2f5cbSFrançois Tigeot /* get radix tree height index */
215*a3a2f5cbSFrançois Tigeot height = root->height - 1;
216*a3a2f5cbSFrançois Tigeot
217*a3a2f5cbSFrançois Tigeot /* walk down the tree until the first missing node, if any */
218*a3a2f5cbSFrançois Tigeot for ( ; height != 0; height--) {
219*a3a2f5cbSFrançois Tigeot idx = radix_pos(index, height);
220*a3a2f5cbSFrançois Tigeot if (node->slots[idx] == NULL)
221*a3a2f5cbSFrançois Tigeot break;
222*a3a2f5cbSFrançois Tigeot node = node->slots[idx];
223*a3a2f5cbSFrançois Tigeot }
224*a3a2f5cbSFrançois Tigeot
225*a3a2f5cbSFrançois Tigeot /* allocate the missing radix levels, if any */
226*a3a2f5cbSFrançois Tigeot for (idx = 0; idx != height; idx++) {
227*a3a2f5cbSFrançois Tigeot temp[idx] = kmalloc(sizeof(*node), M_DRM,
228*a3a2f5cbSFrançois Tigeot root->gfp_mask | M_ZERO);
229*a3a2f5cbSFrançois Tigeot if (temp[idx] == NULL) {
230*a3a2f5cbSFrançois Tigeot while(idx--)
231*a3a2f5cbSFrançois Tigeot kfree(temp[idx]);
232*a3a2f5cbSFrançois Tigeot /* Check if we should free the root node as well. */
233*a3a2f5cbSFrançois Tigeot if (root->rnode->count == 0) {
234*a3a2f5cbSFrançois Tigeot kfree(root->rnode);
235*a3a2f5cbSFrançois Tigeot root->rnode = NULL;
236*a3a2f5cbSFrançois Tigeot root->height = 0;
237*a3a2f5cbSFrançois Tigeot }
238*a3a2f5cbSFrançois Tigeot return (-ENOMEM);
239*a3a2f5cbSFrançois Tigeot }
240*a3a2f5cbSFrançois Tigeot }
241*a3a2f5cbSFrançois Tigeot
242*a3a2f5cbSFrançois Tigeot /* setup new radix levels, if any */
243*a3a2f5cbSFrançois Tigeot for ( ; height != 0; height--) {
244*a3a2f5cbSFrançois Tigeot idx = radix_pos(index, height);
245*a3a2f5cbSFrançois Tigeot node->slots[idx] = temp[height - 1];
246*a3a2f5cbSFrançois Tigeot node->count++;
247*a3a2f5cbSFrançois Tigeot node = node->slots[idx];
248*a3a2f5cbSFrançois Tigeot }
249*a3a2f5cbSFrançois Tigeot
250*a3a2f5cbSFrançois Tigeot /*
251*a3a2f5cbSFrançois Tigeot * Insert and adjust count if the item does not already exist.
252*a3a2f5cbSFrançois Tigeot */
253*a3a2f5cbSFrançois Tigeot idx = radix_pos(index, 0);
254*a3a2f5cbSFrançois Tigeot if (node->slots[idx])
255*a3a2f5cbSFrançois Tigeot return (-EEXIST);
256*a3a2f5cbSFrançois Tigeot node->slots[idx] = item;
257*a3a2f5cbSFrançois Tigeot node->count++;
258*a3a2f5cbSFrançois Tigeot
259*a3a2f5cbSFrançois Tigeot return (0);
260*a3a2f5cbSFrançois Tigeot }
261