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