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