linux_idr.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-2017 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 #include <sys/lock.h>
   39 #include <sys/mutex.h>
   40 
   41 #include <machine/stdarg.h>
   42 
   43 #include <linux/bitmap.h>
   44 #include <linux/kobject.h>
   45 #include <linux/slab.h>
   46 #include <linux/idr.h>
   47 #include <linux/err.h>
   48 
   49 #define MAX_IDR_LEVEL   ((MAX_IDR_SHIFT + IDR_BITS - 1) / IDR_BITS)
   50 #define MAX_IDR_FREE    (MAX_IDR_LEVEL * 2)
   51 
   52 struct linux_idr_cache {
   53         spinlock_t lock;
   54         struct idr_layer *head;
   55         unsigned count;
   56 };
   57 
   58 DPCPU_DEFINE_STATIC(struct linux_idr_cache, linux_idr_cache);
   59 
   60 /*
   61  * IDR Implementation.
   62  *
   63  * This is quick and dirty and not as re-entrant as the linux version
   64  * however it should be fairly fast.  It is basically a radix tree with
   65  * a builtin bitmap for allocation.
   66  */
   67 static MALLOC_DEFINE(M_IDR, "idr", "Linux IDR compat");
   68 
   69 static struct idr_layer *
   70 idr_preload_dequeue_locked(struct linux_idr_cache *lic)
   71 {
   72         struct idr_layer *retval;
   73 
   74         /* check if wrong thread is trying to dequeue */
   75         if (mtx_owned(&lic->lock.m) == 0)
   76                 return (NULL);
   77 
   78         retval = lic->head;
   79         if (likely(retval != NULL)) {
   80                 lic->head = retval->ary[0];
   81                 lic->count--;
   82                 retval->ary[0] = NULL;
   83         }
   84         return (retval);
   85 }
   86 
   87 static void
   88 idr_preload_init(void *arg)
   89 {
   90         int cpu;
   91 
   92         CPU_FOREACH(cpu) {
   93                 struct linux_idr_cache *lic =
   94                     DPCPU_ID_PTR(cpu, linux_idr_cache);
   95 
   96                 spin_lock_init(&lic->lock);
   97         }
   98 }
   99 SYSINIT(idr_preload_init, SI_SUB_CPU, SI_ORDER_ANY, idr_preload_init, NULL);
  100 
  101 static void
  102 idr_preload_uninit(void *arg)
  103 {
  104         int cpu;
  105 
  106         CPU_FOREACH(cpu) {
  107                 struct idr_layer *cacheval;
  108                 struct linux_idr_cache *lic =
  109                     DPCPU_ID_PTR(cpu, linux_idr_cache);
  110 
  111                 while (1) {
  112                         spin_lock(&lic->lock);
  113                         cacheval = idr_preload_dequeue_locked(lic);
  114                         spin_unlock(&lic->lock);
  115 
  116                         if (cacheval == NULL)
  117                                 break;
  118                         free(cacheval, M_IDR);
  119                 }
  120                 spin_lock_destroy(&lic->lock);
  121         }
  122 }
  123 SYSUNINIT(idr_preload_uninit, SI_SUB_LOCK, SI_ORDER_FIRST, idr_preload_uninit, NULL);
  124 
  125 void
  126 idr_preload(gfp_t gfp_mask)
  127 {
  128         struct linux_idr_cache *lic;
  129         struct idr_layer *cacheval;
  130 
  131         sched_pin();
  132 
  133         lic = &DPCPU_GET(linux_idr_cache);
  134 
  135         /* fill up cache */
  136         spin_lock(&lic->lock);
  137         while (lic->count < MAX_IDR_FREE) {
  138                 spin_unlock(&lic->lock);
  139                 cacheval = malloc(sizeof(*cacheval), M_IDR, M_ZERO | gfp_mask);
  140                 spin_lock(&lic->lock);
  141                 if (cacheval == NULL)
  142                         break;
  143                 cacheval->ary[0] = lic->head;
  144                 lic->head = cacheval;
  145                 lic->count++;
  146         }
  147 }
  148 
  149 void
  150 idr_preload_end(void)
  151 {
  152         struct linux_idr_cache *lic;
  153 
  154         lic = &DPCPU_GET(linux_idr_cache);
  155         spin_unlock(&lic->lock);
  156         sched_unpin();
  157 }
  158 
  159 static inline int
  160 idr_max(struct idr *idr)
  161 {
  162         return (1 << (idr->layers * IDR_BITS)) - 1;
  163 }
  164 
  165 static inline int
  166 idr_pos(int id, int layer)
  167 {
  168         return (id >> (IDR_BITS * layer)) & IDR_MASK;
  169 }
  170 
  171 void
  172 idr_init(struct idr *idr)
  173 {
  174         bzero(idr, sizeof(*idr));
  175         mtx_init(&idr->lock, "idr", NULL, MTX_DEF);
  176 }
  177 
  178 /* Only frees cached pages. */
  179 void
  180 idr_destroy(struct idr *idr)
  181 {
  182         struct idr_layer *il, *iln;
  183 
  184         idr_remove_all(idr);
  185         mtx_lock(&idr->lock);
  186         for (il = idr->free; il != NULL; il = iln) {
  187                 iln = il->ary[0];
  188                 free(il, M_IDR);
  189         }
  190         mtx_unlock(&idr->lock);
  191         mtx_destroy(&idr->lock);
  192 }
  193 
  194 static void
  195 idr_remove_layer(struct idr_layer *il, int layer)
  196 {
  197         int i;
  198 
  199         if (il == NULL)
  200                 return;
  201         if (layer == 0) {
  202                 free(il, M_IDR);
  203                 return;
  204         }
  205         for (i = 0; i < IDR_SIZE; i++)
  206                 if (il->ary[i])
  207                         idr_remove_layer(il->ary[i], layer - 1);
  208 }
  209 
  210 void
  211 idr_remove_all(struct idr *idr)
  212 {
  213 
  214         mtx_lock(&idr->lock);
  215         idr_remove_layer(idr->top, idr->layers - 1);
  216         idr->top = NULL;
  217         idr->layers = 0;
  218         mtx_unlock(&idr->lock);
  219 }
  220 
  221 static void *
  222 idr_remove_locked(struct idr *idr, int id)
  223 {
  224         struct idr_layer *il;
  225         void *res;
  226         int layer;
  227         int idx;
  228 
  229         id &= MAX_ID_MASK;
  230         il = idr->top;
  231         layer = idr->layers - 1;
  232         if (il == NULL || id > idr_max(idr))
  233                 return (NULL);
  234         /*
  235          * Walk down the tree to this item setting bitmaps along the way
  236          * as we know at least one item will be free along this path.
  237          */
  238         while (layer && il) {
  239                 idx = idr_pos(id, layer);
  240                 il->bitmap |= 1 << idx;
  241                 il = il->ary[idx];
  242                 layer--;
  243         }
  244         idx = id & IDR_MASK;
  245         /*
  246          * At this point we've set free space bitmaps up the whole tree.
  247          * We could make this non-fatal and unwind but linux dumps a stack
  248          * and a warning so I don't think it's necessary.
  249          */
  250         if (il == NULL || (il->bitmap & (1 << idx)) != 0)
  251                 panic("idr_remove: Item %d not allocated (%p, %p)\n",
  252                     id, idr, il);
  253         res = il->ary[idx];
  254         il->ary[idx] = NULL;
  255         il->bitmap |= 1 << idx;
  256 
  257         return (res);
  258 }
  259 
  260 void *
  261 idr_remove(struct idr *idr, int id)
  262 {
  263         void *res;
  264 
  265         mtx_lock(&idr->lock);
  266         res = idr_remove_locked(idr, id);
  267         mtx_unlock(&idr->lock);
  268 
  269         return (res);
  270 }
  271 
  272 static inline struct idr_layer *
  273 idr_find_layer_locked(struct idr *idr, int id)
  274 {
  275         struct idr_layer *il;
  276         int layer;
  277 
  278         id &= MAX_ID_MASK;
  279         il = idr->top;
  280         layer = idr->layers - 1;
  281         if (il == NULL || id > idr_max(idr))
  282                 return (NULL);
  283         while (layer && il) {
  284                 il = il->ary[idr_pos(id, layer)];
  285                 layer--;
  286         }
  287         return (il);
  288 }
  289 
  290 void *
  291 idr_replace(struct idr *idr, void *ptr, int id)
  292 {
  293         struct idr_layer *il;
  294         void *res;
  295         int idx;
  296 
  297         mtx_lock(&idr->lock);
  298         il = idr_find_layer_locked(idr, id);
  299         idx = id & IDR_MASK;
  300 
  301         /* Replace still returns an error if the item was not allocated. */
  302         if (il == NULL || (il->bitmap & (1 << idx))) {
  303                 res = ERR_PTR(-ENOENT);
  304         } else {
  305                 res = il->ary[idx];
  306                 il->ary[idx] = ptr;
  307         }
  308         mtx_unlock(&idr->lock);
  309         return (res);
  310 }
  311 
  312 static inline void *
  313 idr_find_locked(struct idr *idr, int id)
  314 {
  315         struct idr_layer *il;
  316         void *res;
  317 
  318         mtx_assert(&idr->lock, MA_OWNED);
  319         il = idr_find_layer_locked(idr, id);
  320         if (il != NULL)
  321                 res = il->ary[id & IDR_MASK];
  322         else
  323                 res = NULL;
  324         return (res);
  325 }
  326 
  327 void *
  328 idr_find(struct idr *idr, int id)
  329 {
  330         void *res;
  331 
  332         mtx_lock(&idr->lock);
  333         res = idr_find_locked(idr, id);
  334         mtx_unlock(&idr->lock);
  335         return (res);
  336 }
  337 
  338 void *
  339 idr_get_next(struct idr *idr, int *nextidp)
  340 {
  341         void *res = NULL;
  342         int id = *nextidp;
  343 
  344         mtx_lock(&idr->lock);
  345         for (; id <= idr_max(idr); id++) {
  346                 res = idr_find_locked(idr, id);
  347                 if (res == NULL)
  348                         continue;
  349                 *nextidp = id;
  350                 break;
  351         }
  352         mtx_unlock(&idr->lock);
  353         return (res);
  354 }
  355 
  356 int
  357 idr_pre_get(struct idr *idr, gfp_t gfp_mask)
  358 {
  359         struct idr_layer *il, *iln;
  360         struct idr_layer *head;
  361         int need;
  362 
  363         mtx_lock(&idr->lock);
  364         for (;;) {
  365                 need = idr->layers + 1;
  366                 for (il = idr->free; il != NULL; il = il->ary[0])
  367                         need--;
  368                 mtx_unlock(&idr->lock);
  369                 if (need <= 0)
  370                         break;
  371                 for (head = NULL; need; need--) {
  372                         iln = malloc(sizeof(*il), M_IDR, M_ZERO | gfp_mask);
  373                         if (iln == NULL)
  374                                 break;
  375                         bitmap_fill(&iln->bitmap, IDR_SIZE);
  376                         if (head != NULL) {
  377                                 il->ary[0] = iln;
  378                                 il = iln;
  379                         } else
  380                                 head = il = iln;
  381                 }
  382                 if (head == NULL)
  383                         return (0);
  384                 mtx_lock(&idr->lock);
  385                 il->ary[0] = idr->free;
  386                 idr->free = head;
  387         }
  388         return (1);
  389 }
  390 
  391 static struct idr_layer *
  392 idr_free_list_get(struct idr *idp)
  393 {
  394         struct idr_layer *il;
  395 
  396         if ((il = idp->free) != NULL) {
  397                 idp->free = il->ary[0];
  398                 il->ary[0] = NULL;
  399         }
  400         return (il);
  401 }
  402 
  403 static inline struct idr_layer *
  404 idr_get(struct idr *idp)
  405 {
  406         struct idr_layer *il;
  407 
  408         if ((il = idr_free_list_get(idp)) != NULL) {
  409                 MPASS(il->bitmap != 0);
  410         } else if ((il = malloc(sizeof(*il), M_IDR, M_ZERO | M_NOWAIT)) != NULL) {
  411                 bitmap_fill(&il->bitmap, IDR_SIZE);
  412         } else if ((il = idr_preload_dequeue_locked(&DPCPU_GET(linux_idr_cache))) != NULL) {
  413                 bitmap_fill(&il->bitmap, IDR_SIZE);
  414         } else {
  415                 return (NULL);
  416         }
  417         return (il);
  418 }
  419 
  420 /*
  421  * Could be implemented as get_new_above(idr, ptr, 0, idp) but written
  422  * first for simplicity sake.
  423  */
  424 static int
  425 idr_get_new_locked(struct idr *idr, void *ptr, int *idp)
  426 {
  427         struct idr_layer *stack[MAX_LEVEL];
  428         struct idr_layer *il;
  429         int error;
  430         int layer;
  431         int idx;
  432         int id;
  433 
  434         mtx_assert(&idr->lock, MA_OWNED);
  435 
  436         error = -EAGAIN;
  437         /*
  438          * Expand the tree until there is free space.
  439          */
  440         if (idr->top == NULL || idr->top->bitmap == 0) {
  441                 if (idr->layers == MAX_LEVEL + 1) {
  442                         error = -ENOSPC;
  443                         goto out;
  444                 }
  445                 il = idr_get(idr);
  446                 if (il == NULL)
  447                         goto out;
  448                 il->ary[0] = idr->top;
  449                 if (idr->top)
  450                         il->bitmap &= ~1;
  451                 idr->top = il;
  452                 idr->layers++;
  453         }
  454         il = idr->top;
  455         id = 0;
  456         /*
  457          * Walk the tree following free bitmaps, record our path.
  458          */
  459         for (layer = idr->layers - 1;; layer--) {
  460                 stack[layer] = il;
  461                 idx = ffsl(il->bitmap);
  462                 if (idx == 0)
  463                         panic("idr_get_new: Invalid leaf state (%p, %p)\n",
  464                             idr, il);
  465                 idx--;
  466                 id |= idx << (layer * IDR_BITS);
  467                 if (layer == 0)
  468                         break;
  469                 if (il->ary[idx] == NULL) {
  470                         il->ary[idx] = idr_get(idr);
  471                         if (il->ary[idx] == NULL)
  472                                 goto out;
  473                 }
  474                 il = il->ary[idx];
  475         }
  476         /*
  477          * Allocate the leaf to the consumer.
  478          */
  479         il->bitmap &= ~(1 << idx);
  480         il->ary[idx] = ptr;
  481         *idp = id;
  482         /*
  483          * Clear bitmaps potentially up to the root.
  484          */
  485         while (il->bitmap == 0 && ++layer < idr->layers) {
  486                 il = stack[layer];
  487                 il->bitmap &= ~(1 << idr_pos(id, layer));
  488         }
  489         error = 0;
  490 out:
  491 #ifdef INVARIANTS
  492         if (error == 0 && idr_find_locked(idr, id) != ptr) {
  493                 panic("idr_get_new: Failed for idr %p, id %d, ptr %p\n",
  494                     idr, id, ptr);
  495         }
  496 #endif
  497         return (error);
  498 }
  499 
  500 int
  501 idr_get_new(struct idr *idr, void *ptr, int *idp)
  502 {
  503         int retval;
  504 
  505         mtx_lock(&idr->lock);
  506         retval = idr_get_new_locked(idr, ptr, idp);
  507         mtx_unlock(&idr->lock);
  508         return (retval);
  509 }
  510 
  511 static int
  512 idr_get_new_above_locked(struct idr *idr, void *ptr, int starting_id, int *idp)
  513 {
  514         struct idr_layer *stack[MAX_LEVEL];
  515         struct idr_layer *il;
  516         int error;
  517         int layer;
  518         int idx, sidx;
  519         int id;
  520 
  521         mtx_assert(&idr->lock, MA_OWNED);
  522 
  523         error = -EAGAIN;
  524         /*
  525          * Compute the layers required to support starting_id and the mask
  526          * at the top layer.
  527          */
  528 restart:
  529         idx = starting_id;
  530         layer = 0;
  531         while (idx & ~IDR_MASK) {
  532                 layer++;
  533                 idx >>= IDR_BITS;
  534         }
  535         if (layer == MAX_LEVEL + 1) {
  536                 error = -ENOSPC;
  537                 goto out;
  538         }
  539         /*
  540          * Expand the tree until there is free space at or beyond starting_id.
  541          */
  542         while (idr->layers <= layer ||
  543             idr->top->bitmap < (1 << idr_pos(starting_id, idr->layers - 1))) {
  544                 if (idr->layers == MAX_LEVEL + 1) {
  545                         error = -ENOSPC;
  546                         goto out;
  547                 }
  548                 il = idr_get(idr);
  549                 if (il == NULL)
  550                         goto out;
  551                 il->ary[0] = idr->top;
  552                 if (idr->top && idr->top->bitmap == 0)
  553                         il->bitmap &= ~1;
  554                 idr->top = il;
  555                 idr->layers++;
  556         }
  557         il = idr->top;
  558         id = 0;
  559         /*
  560          * Walk the tree following free bitmaps, record our path.
  561          */
  562         for (layer = idr->layers - 1;; layer--) {
  563                 stack[layer] = il;
  564                 sidx = idr_pos(starting_id, layer);
  565                 /* Returns index numbered from 0 or size if none exists. */
  566                 idx = find_next_bit(&il->bitmap, IDR_SIZE, sidx);
  567                 if (idx == IDR_SIZE && sidx == 0)
  568                         panic("idr_get_new: Invalid leaf state (%p, %p)\n",
  569                             idr, il);
  570                 /*
  571                  * We may have walked a path where there was a free bit but
  572                  * it was lower than what we wanted.  Restart the search with
  573                  * a larger starting id.  id contains the progress we made so
  574                  * far.  Search the leaf one above this level.  This may
  575                  * restart as many as MAX_LEVEL times but that is expected
  576                  * to be rare.
  577                  */
  578                 if (idx == IDR_SIZE) {
  579                         starting_id = id + (1 << ((layer + 1) * IDR_BITS));
  580                         goto restart;
  581                 }
  582                 if (idx > sidx)
  583                         starting_id = 0;        /* Search the whole subtree. */
  584                 id |= idx << (layer * IDR_BITS);
  585                 if (layer == 0)
  586                         break;
  587                 if (il->ary[idx] == NULL) {
  588                         il->ary[idx] = idr_get(idr);
  589                         if (il->ary[idx] == NULL)
  590                                 goto out;
  591                 }
  592                 il = il->ary[idx];
  593         }
  594         /*
  595          * Allocate the leaf to the consumer.
  596          */
  597         il->bitmap &= ~(1 << idx);
  598         il->ary[idx] = ptr;
  599         *idp = id;
  600         /*
  601          * Clear bitmaps potentially up to the root.
  602          */
  603         while (il->bitmap == 0 && ++layer < idr->layers) {
  604                 il = stack[layer];
  605                 il->bitmap &= ~(1 << idr_pos(id, layer));
  606         }
  607         error = 0;
  608 out:
  609 #ifdef INVARIANTS
  610         if (error == 0 && idr_find_locked(idr, id) != ptr) {
  611                 panic("idr_get_new_above: Failed for idr %p, id %d, ptr %p\n",
  612                     idr, id, ptr);
  613         }
  614 #endif
  615         return (error);
  616 }
  617 
  618 int
  619 idr_get_new_above(struct idr *idr, void *ptr, int starting_id, int *idp)
  620 {
  621         int retval;
  622 
  623         mtx_lock(&idr->lock);
  624         retval = idr_get_new_above_locked(idr, ptr, starting_id, idp);
  625         mtx_unlock(&idr->lock);
  626         return (retval);
  627 }
  628 
  629 int
  630 ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
  631 {
  632         return (idr_get_new_above(&ida->idr, NULL, starting_id, p_id));
  633 }
  634 
  635 static int
  636 idr_alloc_locked(struct idr *idr, void *ptr, int start, int end)
  637 {
  638         int max = end > 0 ? end - 1 : INT_MAX;
  639         int error;
  640         int id;
  641 
  642         mtx_assert(&idr->lock, MA_OWNED);
  643 
  644         if (unlikely(start < 0))
  645                 return (-EINVAL);
  646         if (unlikely(max < start))
  647                 return (-ENOSPC);
  648 
  649         if (start == 0)
  650                 error = idr_get_new_locked(idr, ptr, &id);
  651         else
  652                 error = idr_get_new_above_locked(idr, ptr, start, &id);
  653 
  654         if (unlikely(error < 0))
  655                 return (error);
  656         if (unlikely(id > max)) {
  657                 idr_remove_locked(idr, id);
  658                 return (-ENOSPC);
  659         }
  660         return (id);
  661 }
  662 
  663 int
  664 idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
  665 {
  666         int retval;
  667 
  668         mtx_lock(&idr->lock);
  669         retval = idr_alloc_locked(idr, ptr, start, end);
  670         mtx_unlock(&idr->lock);
  671         return (retval);
  672 }
  673 
  674 int
  675 idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
  676 {
  677         int retval;
  678 
  679         mtx_lock(&idr->lock);
  680         retval = idr_alloc_locked(idr, ptr, max(start, idr->next_cyclic_id), end);
  681         if (unlikely(retval == -ENOSPC))
  682                 retval = idr_alloc_locked(idr, ptr, start, end);
  683         if (likely(retval >= 0))
  684                 idr->next_cyclic_id = retval + 1;
  685         mtx_unlock(&idr->lock);
  686         return (retval);
  687 }
  688 
  689 static int
  690 idr_for_each_layer(struct idr_layer *il, int offset, int layer,
  691     int (*f)(int id, void *p, void *data), void *data)
  692 {
  693         int i, err;
  694 
  695         if (il == NULL)
  696                 return (0);
  697         if (layer == 0) {
  698                 for (i = 0; i < IDR_SIZE; i++) {
  699                         if (il->ary[i] == NULL)
  700                                 continue;
  701                         err = f(i + offset, il->ary[i],  data);
  702                         if (err)
  703                                 return (err);
  704                 }
  705                 return (0);
  706         }
  707         for (i = 0; i < IDR_SIZE; i++) {
  708                 if (il->ary[i] == NULL)
  709                         continue;
  710                 err = idr_for_each_layer(il->ary[i],
  711                     (i + offset) * IDR_SIZE, layer - 1, f, data);
  712                 if (err)
  713                         return (err);
  714         }
  715         return (0);
  716 }
  717 
  718 /* NOTE: It is not allowed to modify the IDR tree while it is being iterated */
  719 int
  720 idr_for_each(struct idr *idp, int (*f)(int id, void *p, void *data), void *data)
  721 {
  722         return (idr_for_each_layer(idp->top, 0, idp->layers - 1, f, data));
  723 }
  724 
  725 static int
  726 idr_has_entry(int id, void *p, void *data)
  727 {
  728 
  729         return (1);
  730 }
  731 
  732 bool
  733 idr_is_empty(struct idr *idp)
  734 {
  735 
  736         return (idr_for_each(idp, idr_has_entry, NULL) == 0);
  737 }
  738 
  739 int
  740 ida_pre_get(struct ida *ida, gfp_t flags)
  741 {
  742         if (idr_pre_get(&ida->idr, flags) == 0)
  743                 return (0);
  744 
  745         if (ida->free_bitmap == NULL) {
  746                 ida->free_bitmap =
  747                     malloc(sizeof(struct ida_bitmap), M_IDR, flags);
  748         }
  749         return (ida->free_bitmap != NULL);
  750 }
  751 
  752 int
  753 ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
  754     gfp_t flags)
  755 {
  756         int ret, id;
  757         unsigned int max;
  758 
  759         MPASS((int)start >= 0);
  760         MPASS((int)end >= 0);
  761 
  762         if (end == 0)
  763                 max = 0x80000000;
  764         else {
  765                 MPASS(end > start);
  766                 max = end - 1;
  767         }
  768 again:
  769         if (!ida_pre_get(ida, flags))
  770                 return (-ENOMEM);
  771 
  772         if ((ret = ida_get_new_above(ida, start, &id)) == 0) {
  773                 if (id > max) {
  774                         ida_remove(ida, id);
  775                         ret = -ENOSPC;
  776                 } else {
  777                         ret = id;
  778                 }
  779         }
  780         if (__predict_false(ret == -EAGAIN))
  781                 goto again;
  782 
  783         return (ret);
  784 }
  785 
  786 void
  787 ida_simple_remove(struct ida *ida, unsigned int id)
  788 {
  789         idr_remove(&ida->idr, id);
  790 }
  791 
  792 void
  793 ida_remove(struct ida *ida, int id)
  794 {
  795         idr_remove(&ida->idr, id);
  796 }
  797 
  798 void
  799 ida_init(struct ida *ida)
  800 {
  801         idr_init(&ida->idr);
  802 }
  803 
  804 void
  805 ida_destroy(struct ida *ida)
  806 {
  807         idr_destroy(&ida->idr);
  808         free(ida->free_bitmap, M_IDR);
  809 }
Cache object: 58298cc57345be873db9170583aed890
[ 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_idr.c

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