linux_radix.c revision 364383 
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/11/sys/compat/linuxkpi/common/src/linux_radix.c 364383 2020-08-19 12:26:23Z 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
44static MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat");
45
46static inline unsigned long
47radix_max(struct radix_tree_root *root)
48{
49	return ((1UL << (root->height * RADIX_TREE_MAP_SHIFT)) - 1UL);
50}
51
52static inline int
53radix_pos(long id, int height)
54{
55	return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK;
56}
57
58static void
59radix_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
69void *
70radix_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
86out:
87	return (item);
88}
89
90bool
91radix_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
98restart:
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
129void *
130radix_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		}
172out:
173	return (item);
174}
175
176void
177radix_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
183int
184radix_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
282int
283radix_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