linux_radix.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    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-2020 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 static void
   59 radix_tree_clean_root_node(struct radix_tree_root *root)
   60 {
   61         /* Check if the root node should be freed */
   62         if (root->rnode->count == 0) {
   63                 free(root->rnode, M_RADIX);
   64                 root->rnode = NULL;
   65                 root->height = 0;
   66         }
   67 }
   68 
   69 void *
   70 radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
   71 {
   72         struct radix_tree_node *node;
   73         void *item;
   74         int height;
   75 
   76         item = NULL;
   77         node = root->rnode;
   78         height = root->height - 1;
   79         if (index > radix_max(root))
   80                 goto out;
   81         while (height && node)
   82                 node = node->slots[radix_pos(index, height--)];
   83         if (node)
   84                 item = node->slots[radix_pos(index, 0)];
   85 
   86 out:
   87         return (item);
   88 }
   89 
   90 bool
   91 radix_tree_iter_find(struct radix_tree_root *root, struct radix_tree_iter *iter,
   92     void ***pppslot)
   93 {
   94         struct radix_tree_node *node;
   95         unsigned long index = iter->index;
   96         int height;
   97 
   98 restart:
   99         node = root->rnode;
  100         if (node == NULL)
  101                 return (false);
  102         height = root->height - 1;
  103         if (height == -1 || index > radix_max(root))
  104                 return (false);
  105         do {
  106                 unsigned long mask = RADIX_TREE_MAP_MASK << (RADIX_TREE_MAP_SHIFT * height);
  107                 unsigned long step = 1UL << (RADIX_TREE_MAP_SHIFT * height);
  108                 int pos = radix_pos(index, height);
  109                 struct radix_tree_node *next;
  110 
  111                 /* track last slot */
  112                 *pppslot = node->slots + pos;
  113 
  114                 next = node->slots[pos];
  115                 if (next == NULL) {
  116                         index += step;
  117                         index &= -step;
  118                         if ((index & mask) == 0)
  119                                 goto restart;
  120                 } else {
  121                         node = next;
  122                         height--;
  123                 }
  124         } while (height != -1);
  125         iter->index = index;
  126         return (true);
  127 }
  128 
  129 void *
  130 radix_tree_delete(struct radix_tree_root *root, unsigned long index)
  131 {
  132         struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
  133         struct radix_tree_node *node;
  134         void *item;
  135         int height;
  136         int idx;
  137 
  138         item = NULL;
  139         node = root->rnode;
  140         height = root->height - 1;
  141         if (index > radix_max(root))
  142                 goto out;
  143         /*
  144          * Find the node and record the path in stack.
  145          */
  146         while (height && node) {
  147                 stack[height] = node;
  148                 node = node->slots[radix_pos(index, height--)];
  149         }
  150         idx = radix_pos(index, 0);
  151         if (node)
  152                 item = node->slots[idx];
  153         /*
  154          * If we removed something reduce the height of the tree.
  155          */
  156         if (item)
  157                 for (;;) {
  158                         node->slots[idx] = NULL;
  159                         node->count--;
  160                         if (node->count > 0)
  161                                 break;
  162                         free(node, M_RADIX);
  163                         if (node == root->rnode) {
  164                                 root->rnode = NULL;
  165                                 root->height = 0;
  166                                 break;
  167                         }
  168                         height++;
  169                         node = stack[height];
  170                         idx = radix_pos(index, height);
  171                 }
  172 out:
  173         return (item);
  174 }
  175 
  176 void
  177 radix_tree_iter_delete(struct radix_tree_root *root,
  178     struct radix_tree_iter *iter, void **slot)
  179 {
  180         radix_tree_delete(root, iter->index);
  181 }
  182 
  183 int
  184 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
  185 {
  186         struct radix_tree_node *node;
  187         struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1];
  188         int height;
  189         int idx;
  190 
  191         /* bail out upon insertion of a NULL item */
  192         if (item == NULL)
  193                 return (-EINVAL);
  194 
  195         /* get root node, if any */
  196         node = root->rnode;
  197 
  198         /* allocate root node, if any */
  199         if (node == NULL) {
  200                 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
  201                 if (node == NULL)
  202                         return (-ENOMEM);
  203                 root->rnode = node;
  204                 root->height++;
  205         }
  206 
  207         /* expand radix tree as needed */
  208         while (radix_max(root) < index) {
  209                 /* check if the radix tree is getting too big */
  210                 if (root->height == RADIX_TREE_MAX_HEIGHT) {
  211                         radix_tree_clean_root_node(root);
  212                         return (-E2BIG);
  213                 }
  214 
  215                 /*
  216                  * If the root radix level is not empty, we need to
  217                  * allocate a new radix level:
  218                  */
  219                 if (node->count != 0) {
  220                         node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
  221                         if (node == NULL) {
  222                                 /*
  223                                  * Freeing the already allocated radix
  224                                  * levels, if any, will be handled by
  225                                  * the radix_tree_delete() function.
  226                                  * This code path can only happen when
  227                                  * the tree is not empty.
  228                                  */
  229                                 return (-ENOMEM);
  230                         }
  231                         node->slots[0] = root->rnode;
  232                         node->count++;
  233                         root->rnode = node;
  234                 }
  235                 root->height++;
  236         }
  237 
  238         /* get radix tree height index */
  239         height = root->height - 1;
  240 
  241         /* walk down the tree until the first missing node, if any */
  242         for ( ; height != 0; height--) {
  243                 idx = radix_pos(index, height);
  244                 if (node->slots[idx] == NULL)
  245                         break;
  246                 node = node->slots[idx];
  247         }
  248 
  249         /* allocate the missing radix levels, if any */
  250         for (idx = 0; idx != height; idx++) {
  251                 temp[idx] = malloc(sizeof(*node), M_RADIX,
  252                     root->gfp_mask | M_ZERO);
  253                 if (temp[idx] == NULL) {
  254                         while (idx--)
  255                                 free(temp[idx], M_RADIX);
  256                         radix_tree_clean_root_node(root);
  257                         return (-ENOMEM);
  258                 }
  259         }
  260 
  261         /* setup new radix levels, if any */
  262         for ( ; height != 0; height--) {
  263                 idx = radix_pos(index, height);
  264                 node->slots[idx] = temp[height - 1];
  265                 node->count++;
  266                 node = node->slots[idx];
  267         }
  268 
  269         /*
  270          * Insert and adjust count if the item does not already exist.
  271          */
  272         idx = radix_pos(index, 0);
  273         if (node->slots[idx])
  274                 return (-EEXIST);
  275         node->slots[idx] = item;
  276         node->count++;
  277 
  278         return (0);
  279 }
  280 
  281 int
  282 radix_tree_store(struct radix_tree_root *root, unsigned long index, void **ppitem)
  283 {
  284         struct radix_tree_node *node;
  285         struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1];
  286         void *pitem;
  287         int height;
  288         int idx;
  289 
  290         /*
  291          * Inserting a NULL item means delete it. The old pointer is
  292          * stored at the location pointed to by "ppitem".
  293          */
  294         if (*ppitem == NULL) {
  295                 *ppitem = radix_tree_delete(root, index);
  296                 return (0);
  297         }
  298 
  299         /* get root node, if any */
  300         node = root->rnode;
  301 
  302         /* allocate root node, if any */
  303         if (node == NULL) {
  304                 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
  305                 if (node == NULL)
  306                         return (-ENOMEM);
  307                 root->rnode = node;
  308                 root->height++;
  309         }
  310 
  311         /* expand radix tree as needed */
  312         while (radix_max(root) < index) {
  313                 /* check if the radix tree is getting too big */
  314                 if (root->height == RADIX_TREE_MAX_HEIGHT) {
  315                         radix_tree_clean_root_node(root);
  316                         return (-E2BIG);
  317                 }
  318 
  319                 /*
  320                  * If the root radix level is not empty, we need to
  321                  * allocate a new radix level:
  322                  */
  323                 if (node->count != 0) {
  324                         node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
  325                         if (node == NULL) {
  326                                 /*
  327                                  * Freeing the already allocated radix
  328                                  * levels, if any, will be handled by
  329                                  * the radix_tree_delete() function.
  330                                  * This code path can only happen when
  331                                  * the tree is not empty.
  332                                  */
  333                                 return (-ENOMEM);
  334                         }
  335                         node->slots[0] = root->rnode;
  336                         node->count++;
  337                         root->rnode = node;
  338                 }
  339                 root->height++;
  340         }
  341 
  342         /* get radix tree height index */
  343         height = root->height - 1;
  344 
  345         /* walk down the tree until the first missing node, if any */
  346         for ( ; height != 0; height--) {
  347                 idx = radix_pos(index, height);
  348                 if (node->slots[idx] == NULL)
  349                         break;
  350                 node = node->slots[idx];
  351         }
  352 
  353         /* allocate the missing radix levels, if any */
  354         for (idx = 0; idx != height; idx++) {
  355                 temp[idx] = malloc(sizeof(*node), M_RADIX,
  356                     root->gfp_mask | M_ZERO);
  357                 if (temp[idx] == NULL) {
  358                         while (idx--)
  359                                 free(temp[idx], M_RADIX);
  360                         radix_tree_clean_root_node(root);
  361                         return (-ENOMEM);
  362                 }
  363         }
  364 
  365         /* setup new radix levels, if any */
  366         for ( ; height != 0; height--) {
  367                 idx = radix_pos(index, height);
  368                 node->slots[idx] = temp[height - 1];
  369                 node->count++;
  370                 node = node->slots[idx];
  371         }
  372 
  373         /*
  374          * Insert and adjust count if the item does not already exist.
  375          */
  376         idx = radix_pos(index, 0);
  377         /* swap */
  378         pitem = node->slots[idx];
  379         node->slots[idx] = *ppitem;
  380         *ppitem = pitem;
  381 
  382         if (pitem == NULL)
  383                 node->count++;
  384         return (0);
  385 }
Cache object: 5e8101119cdcf58f7b430b306b9ee1b1
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/compat/linuxkpi/common/src/linux_radix.c

FreeBSD/Linux Kernel Cross Reference
sys/compat/linuxkpi/common/src/linux_radix.c
