linux_radix.c revision 271127 
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
41static MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat");
42
43static inline int
44radix_max(struct radix_tree_root *root)
45{
46	return (1 << (root->height * RADIX_TREE_MAP_SHIFT)) - 1;
47}
48
49static inline int
50radix_pos(long id, int height)
51{
52	return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK;
53}
54
55void *
56radix_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
72out:
73	return (item);
74}
75
76void *
77radix_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		}
119out:
120	return (item);
121}
122
123int
124radix_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