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$"); 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 44 static MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat"); 45 46 static inline unsigned long 47 radix_max(struct radix_tree_root *root) 48 { 49 return ((1UL << (root->height * RADIX_TREE_MAP_SHIFT)) - 1UL); 50 } 51 52 static inline int 53 radix_pos(long id, int height) 54 { 55 return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK; 56 } 57 58 void * 59 radix_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 75 out: 76 return (item); 77 } 78 79 bool 80 radix_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 87 restart: 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 118 void * 119 radix_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 } 161 out: 162 return (item); 163 } 164 165 void 166 radix_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 172 int 173 radix_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