sys/compat/linuxkpi/common/src/linux_radix.c

   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 }