sys/dev/drm/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
  32 #include <sys/param.h>
  33 #include <sys/systm.h>
  34 #include <sys/kernel.h>
  35 #include <sys/sysctl.h>
  36
  37 #include <linux/slab.h>
  38 #include <linux/kernel.h>
  39 #include <linux/radix-tree.h>
  40 #include <linux/err.h>
  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                         kfree(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 = kmalloc(sizeof(*node), M_DRM, 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 = kmalloc(sizeof(*node), M_DRM, 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] = kmalloc(sizeof(*node), M_DRM,
 228                     root->gfp_mask | M_ZERO);
 229                 if (temp[idx] == NULL) {
 230                         while(idx--)
 231                                 kfree(temp[idx]);
 232                         /* Check if we should free the root node as well. */
 233                         if (root->rnode->count == 0) {
 234                                 kfree(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 }