linux_xarray.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) 2020 Mellanox Technologies, Ltd.
    3  * All rights reserved.
    4  *
    5  * Redistribution and use in source and binary forms, with or without
    6  * modification, are permitted provided that the following conditions
    7  * are met:
    8  * 1. Redistributions of source code must retain the above copyright
    9  *    notice unmodified, this list of conditions, and the following
   10  *    disclaimer.
   11  * 2. Redistributions in binary form must reproduce the above copyright
   12  *    notice, this list of conditions and the following disclaimer in the
   13  *    documentation and/or other materials provided with the distribution.
   14  *
   15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
   16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
   18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
   19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
   20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
   21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
   22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
   24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   25  */
   26 
   27 #include <sys/cdefs.h>
   28 __FBSDID("$FreeBSD$");
   29 
   30 #include <linux/xarray.h>
   31 
   32 #include <vm/vm_pageout.h>
   33 
   34 /*
   35  * This function removes the element at the given index and returns
   36  * the pointer to the removed element, if any.
   37  */
   38 void *
   39 __xa_erase(struct xarray *xa, uint32_t index)
   40 {
   41         XA_ASSERT_LOCKED(xa);
   42 
   43         return (radix_tree_delete(&xa->root, index));
   44 }
   45 
   46 void *
   47 xa_erase(struct xarray *xa, uint32_t index)
   48 {
   49         void *retval;
   50 
   51         xa_lock(xa);
   52         retval = __xa_erase(xa, index);
   53         xa_unlock(xa);
   54 
   55         return (retval);
   56 }
   57 
   58 /*
   59  * This function returns the element pointer at the given index. A
   60  * value of NULL is returned if the element does not exist.
   61  */
   62 void *
   63 xa_load(struct xarray *xa, uint32_t index)
   64 {
   65         void *retval;
   66 
   67         xa_lock(xa);
   68         retval = radix_tree_lookup(&xa->root, index);
   69         xa_unlock(xa);
   70 
   71         return (retval);
   72 }
   73 
   74 /*
   75  * This is an internal function used to sleep until more memory
   76  * becomes available.
   77  */
   78 static void
   79 xa_vm_wait_locked(struct xarray *xa)
   80 {
   81         xa_unlock(xa);
   82         vm_wait(NULL);
   83         xa_lock(xa);
   84 }
   85 
   86 /*
   87  * This function iterates the xarray until it finds a free slot where
   88  * it can insert the element pointer to by "ptr". It starts at the
   89  * index pointed to by "pindex" and updates this value at return. The
   90  * "mask" argument defines the maximum index allowed, inclusivly, and
   91  * must be a power of two minus one value. The "gfp" argument
   92  * basically tells if we can wait for more memory to become available
   93  * or not. This function returns zero upon success or a negative error
   94  * code on failure. A typical error code is -ENOMEM which means either
   95  * the xarray is full, or there was not enough internal memory
   96  * available to complete the radix tree insertion.
   97  */
   98 int
   99 __xa_alloc(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask, gfp_t gfp)
  100 {
  101         int retval;
  102 
  103         XA_ASSERT_LOCKED(xa);
  104 
  105         /* mask should allow to allocate at least one item */
  106         MPASS(mask > ((xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 0));
  107 
  108         /* mask can be any power of two value minus one */
  109         MPASS((mask & (mask + 1)) == 0);
  110 
  111         *pindex = (xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 0;
  112 retry:
  113         retval = radix_tree_insert(&xa->root, *pindex, ptr);
  114 
  115         switch (retval) {
  116         case -EEXIST:
  117                 if (likely(*pindex != mask)) {
  118                         (*pindex)++;
  119                         goto retry;
  120                 }
  121                 retval = -ENOMEM;
  122                 break;
  123         case -ENOMEM:
  124                 if (likely(gfp & M_WAITOK)) {
  125                         xa_vm_wait_locked(xa);
  126                         goto retry;
  127                 }
  128                 break;
  129         default:
  130                 break;
  131         }
  132         return (retval);
  133 }
  134 
  135 int
  136 xa_alloc(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask, gfp_t gfp)
  137 {
  138         int retval;
  139 
  140         xa_lock(xa);
  141         retval = __xa_alloc(xa, pindex, ptr, mask, gfp);
  142         xa_unlock(xa);
  143 
  144         return (retval);
  145 }
  146 
  147 /*
  148  * This function works the same like the "xa_alloc" function, except
  149  * it wraps the next index value to zero when there are no entries
  150  * left at the end of the xarray searching for a free slot from the
  151  * beginning of the array. If the xarray is full -ENOMEM is returned.
  152  */
  153 int
  154 __xa_alloc_cyclic(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask,
  155     uint32_t *pnext_index, gfp_t gfp)
  156 {
  157         int retval;
  158         int timeout = 1;
  159 
  160         XA_ASSERT_LOCKED(xa);
  161 
  162         /* mask should allow to allocate at least one item */
  163         MPASS(mask > ((xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 0));
  164 
  165         /* mask can be any power of two value minus one */
  166         MPASS((mask & (mask + 1)) == 0);
  167 
  168         *pnext_index = (xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 0;
  169 retry:
  170         retval = radix_tree_insert(&xa->root, *pnext_index, ptr);
  171 
  172         switch (retval) {
  173         case -EEXIST:
  174                 if (unlikely(*pnext_index == mask) && !timeout--) {
  175                         retval = -ENOMEM;
  176                         break;
  177                 }
  178                 (*pnext_index)++;
  179                 (*pnext_index) &= mask;
  180                 if (*pnext_index == 0 && (xa->flags & XA_FLAGS_ALLOC1) != 0)
  181                         (*pnext_index)++;
  182                 goto retry;
  183         case -ENOMEM:
  184                 if (likely(gfp & M_WAITOK)) {
  185                         xa_vm_wait_locked(xa);
  186                         goto retry;
  187                 }
  188                 break;
  189         default:
  190                 break;
  191         }
  192         *pindex = *pnext_index;
  193 
  194         return (retval);
  195 }
  196 
  197 int
  198 xa_alloc_cyclic(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask,
  199     uint32_t *pnext_index, gfp_t gfp)
  200 {
  201         int retval;
  202 
  203         xa_lock(xa);
  204         retval = __xa_alloc_cyclic(xa, pindex, ptr, mask, pnext_index, gfp);
  205         xa_unlock(xa);
  206 
  207         return (retval);
  208 }
  209 
  210 /*
  211  * This function tries to insert an element at the given index. The
  212  * "gfp" argument basically decides of this function can sleep or not
  213  * trying to allocate internal memory for its radix tree.  The
  214  * function returns an error code upon failure. Typical error codes
  215  * are element exists (-EEXIST) or out of memory (-ENOMEM).
  216  */
  217 int
  218 __xa_insert(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp)
  219 {
  220         int retval;
  221 
  222         XA_ASSERT_LOCKED(xa);
  223 retry:
  224         retval = radix_tree_insert(&xa->root, index, ptr);
  225 
  226         switch (retval) {
  227         case -ENOMEM:
  228                 if (likely(gfp & M_WAITOK)) {
  229                         xa_vm_wait_locked(xa);
  230                         goto retry;
  231                 }
  232                 break;
  233         default:
  234                 break;
  235         }
  236         return (retval);
  237 }
  238 
  239 int
  240 xa_insert(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp)
  241 {
  242         int retval;
  243 
  244         xa_lock(xa);
  245         retval = __xa_insert(xa, index, ptr, gfp);
  246         xa_unlock(xa);
  247 
  248         return (retval);
  249 }
  250 
  251 /*
  252  * This function updates the element at the given index and returns a
  253  * pointer to the old element. The "gfp" argument basically decides of
  254  * this function can sleep or not trying to allocate internal memory
  255  * for its radix tree. The function returns an XA_ERROR() pointer code
  256  * upon failure. Code using this function must always check if the
  257  * return value is an XA_ERROR() code before using the returned value.
  258  */
  259 void *
  260 __xa_store(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp)
  261 {
  262         int retval;
  263 
  264         XA_ASSERT_LOCKED(xa);
  265 retry:
  266         retval = radix_tree_store(&xa->root, index, &ptr);
  267 
  268         switch (retval) {
  269         case 0:
  270                 break;
  271         case -ENOMEM:
  272                 if (likely(gfp & M_WAITOK)) {
  273                         xa_vm_wait_locked(xa);
  274                         goto retry;
  275                 }
  276                 ptr = XA_ERROR(retval);
  277                 break;
  278         default:
  279                 ptr = XA_ERROR(retval);
  280                 break;
  281         }
  282         return (ptr);
  283 }
  284 
  285 void *
  286 xa_store(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp)
  287 {
  288         void *retval;
  289 
  290         xa_lock(xa);
  291         retval = __xa_store(xa, index, ptr, gfp);
  292         xa_unlock(xa);
  293 
  294         return (retval);
  295 }
  296 
  297 /*
  298  * This function initialize an xarray structure.
  299  */
  300 void
  301 xa_init_flags(struct xarray *xa, uint32_t flags)
  302 {
  303         memset(xa, 0, sizeof(*xa));
  304 
  305         mtx_init(&xa->mtx, "lkpi-xarray", NULL, MTX_DEF | MTX_RECURSE);
  306         xa->root.gfp_mask = GFP_NOWAIT;
  307         xa->flags = flags;
  308 }
  309 
  310 /*
  311  * This function destroys an xarray structure and all its internal
  312  * memory and locks.
  313  */
  314 void
  315 xa_destroy(struct xarray *xa)
  316 {
  317         struct radix_tree_iter iter;
  318         void **ppslot;
  319 
  320         radix_tree_for_each_slot(ppslot, &xa->root, &iter, 0)
  321                 radix_tree_iter_delete(&xa->root, &iter, ppslot);
  322         mtx_destroy(&xa->mtx);
  323 }
  324 
  325 /*
  326  * This function checks if an xarray is empty or not.
  327  * It returns true if empty, else false.
  328  */
  329 bool
  330 __xa_empty(struct xarray *xa)
  331 {
  332         struct radix_tree_iter iter = {};
  333         void **temp;
  334 
  335         XA_ASSERT_LOCKED(xa);
  336 
  337         return (!radix_tree_iter_find(&xa->root, &iter, &temp));
  338 }
  339 
  340 bool
  341 xa_empty(struct xarray *xa)
  342 {
  343         bool retval;
  344 
  345         xa_lock(xa);
  346         retval = __xa_empty(xa);
  347         xa_unlock(xa);
  348 
  349         return (retval);
  350 }
  351 
  352 /*
  353  * This function returns the next valid xarray entry based on the
  354  * index given by "pindex". The valued pointed to by "pindex" is
  355  * updated before return.
  356  */
  357 void *
  358 __xa_next(struct xarray *xa, unsigned long *pindex, bool not_first)
  359 {
  360         struct radix_tree_iter iter = { .index = *pindex };
  361         void **ppslot;
  362         void *retval;
  363         bool found;
  364 
  365         XA_ASSERT_LOCKED(xa);
  366 
  367         if (not_first) {
  368                 /* advance to next index, if any */
  369                 iter.index++;
  370                 if (iter.index == 0)
  371                         return (NULL);
  372         }
  373 
  374         found = radix_tree_iter_find(&xa->root, &iter, &ppslot);
  375         if (likely(found)) {
  376                 retval = *ppslot;
  377                 *pindex = iter.index;
  378         } else {
  379                 retval = NULL;
  380         }
  381         return (retval);
  382 }
  383 
  384 void *
  385 xa_next(struct xarray *xa, unsigned long *pindex, bool not_first)
  386 {
  387         void *retval;
  388 
  389         xa_lock(xa);
  390         retval = __xa_next(xa, pindex, not_first);
  391         xa_unlock(xa);
  392 
  393         return (retval);
  394 }
Cache object: 1ce010d76c25258000fef63859e0d0fc
[ 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_xarray.c

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