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, 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/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 int
  47 radix_max(struct radix_tree_root *root)
  48 {
  49         return (1 << (root->height * RADIX_TREE_MAP_SHIFT)) - 1;
  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 void *
  80 radix_tree_delete(struct radix_tree_root *root, unsigned long index)
  81 {
  82         struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
  83         struct radix_tree_node *node;
  84         void *item;
  85         int height;
  86         int idx;
  87
  88         item = NULL;
  89         node = root->rnode;
  90         height = root->height - 1;
  91         if (index > radix_max(root))
  92                 goto out;
  93         /*
  94          * Find the node and record the path in stack.
  95          */
  96         while (height && node) {
  97                 stack[height] = node;
  98                 node = node->slots[radix_pos(index, height--)];
  99         }
 100         idx = radix_pos(index, 0);
 101         if (node)
 102                 item = node->slots[idx];
 103         /*
 104          * If we removed something reduce the height of the tree.
 105          */
 106         if (item)
 107                 for (;;) {
 108                         node->slots[idx] = NULL;
 109                         node->count--;
 110                         if (node->count > 0)
 111                                 break;
 112                         free(node, M_RADIX);
 113                         if (node == root->rnode) {
 114                                 root->rnode = NULL;
 115                                 root->height = 0;
 116                                 break;
 117                         }
 118                         height++;
 119                         node = stack[height];
 120                         idx = radix_pos(index, height);
 121                 }
 122 out:
 123         return (item);
 124 }
 125
 126 int
 127 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
 128 {
 129         struct radix_tree_node *node;
 130         struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1];
 131         int height;
 132         int idx;
 133
 134         /* bail out upon insertion of a NULL item */
 135         if (item == NULL)
 136                 return (-EINVAL);
 137
 138         /* get root node, if any */
 139         node = root->rnode;
 140
 141         /* allocate root node, if any */
 142         if (node == NULL) {
 143                 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
 144                 if (node == NULL)
 145                         return (-ENOMEM);
 146                 root->rnode = node;
 147                 root->height++;
 148         }
 149
 150         /* expand radix tree as needed */
 151         while (radix_max(root) < index) {
 152
 153                 /* check if the radix tree is getting too big */
 154                 if (root->height == RADIX_TREE_MAX_HEIGHT)
 155                         return (-E2BIG);
 156
 157                 /*
 158                  * If the root radix level is not empty, we need to
 159                  * allocate a new radix level:
 160                  */
 161                 if (node->count != 0) {
 162                         node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
 163                         if (node == NULL)
 164                                 return (-ENOMEM);
 165                         node->slots[0] = root->rnode;
 166                         node->count++;
 167                         root->rnode = node;
 168                 }
 169                 root->height++;
 170         }
 171
 172         /* get radix tree height index */
 173         height = root->height - 1;
 174
 175         /* walk down the tree until the first missing node, if any */
 176         for ( ; height != 0; height--) {
 177                 idx = radix_pos(index, height);
 178                 if (node->slots[idx] == NULL)
 179                         break;
 180                 node = node->slots[idx];
 181         }
 182
 183         /* allocate the missing radix levels, if any */
 184         for (idx = 0; idx != height; idx++) {
 185                 temp[idx] = malloc(sizeof(*node), M_RADIX,
 186                     root->gfp_mask | M_ZERO);
 187                 if (temp[idx] == NULL) {
 188                         while(idx--)
 189                                 free(temp[idx], M_RADIX);
 190                         /* check if we should free the root node aswell */
 191                         if (root->rnode->count == 0) {
 192                                 free(root->rnode, M_RADIX);
 193                                 root->rnode = NULL;
 194                                 root->height = 0;
 195                         }
 196                         return (-ENOMEM);
 197                 }
 198         }
 199
 200         /* setup new radix levels, if any */
 201         for ( ; height != 0; height--) {
 202                 idx = radix_pos(index, height);
 203                 node->slots[idx] = temp[height - 1];
 204                 node->count++;
 205                 node = node->slots[idx];
 206         }
 207
 208         /*
 209          * Insert and adjust count if the item does not already exist.
 210          */
 211         idx = radix_pos(index, 0);
 212         if (node->slots[idx])
 213                 return (-EEXIST);
 214         node->slots[idx] = item;
 215         node->count++;
 216
 217         return (0);
 218 }