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