18d59ecb2SHans Petter Selasky /*- 28d59ecb2SHans Petter Selasky * Copyright (c) 2010 Isilon Systems, Inc. 38d59ecb2SHans Petter Selasky * Copyright (c) 2010 iX Systems, Inc. 48d59ecb2SHans Petter Selasky * Copyright (c) 2010 Panasas, Inc. 5427cefdeSHans Petter Selasky * Copyright (c) 2013-2017 Mellanox Technologies, Ltd. 68d59ecb2SHans Petter Selasky * All rights reserved. 78d59ecb2SHans Petter Selasky * 88d59ecb2SHans Petter Selasky * Redistribution and use in source and binary forms, with or without 98d59ecb2SHans Petter Selasky * modification, are permitted provided that the following conditions 108d59ecb2SHans Petter Selasky * are met: 118d59ecb2SHans Petter Selasky * 1. Redistributions of source code must retain the above copyright 128d59ecb2SHans Petter Selasky * notice unmodified, this list of conditions, and the following 138d59ecb2SHans Petter Selasky * disclaimer. 148d59ecb2SHans Petter Selasky * 2. Redistributions in binary form must reproduce the above copyright 158d59ecb2SHans Petter Selasky * notice, this list of conditions and the following disclaimer in the 168d59ecb2SHans Petter Selasky * documentation and/or other materials provided with the distribution. 178d59ecb2SHans Petter Selasky * 188d59ecb2SHans Petter Selasky * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 198d59ecb2SHans Petter Selasky * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 208d59ecb2SHans Petter Selasky * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 218d59ecb2SHans Petter Selasky * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 228d59ecb2SHans Petter Selasky * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 238d59ecb2SHans Petter Selasky * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 248d59ecb2SHans Petter Selasky * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 258d59ecb2SHans Petter Selasky * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 268d59ecb2SHans Petter Selasky * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 278d59ecb2SHans Petter Selasky * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 288d59ecb2SHans Petter Selasky */ 298d59ecb2SHans Petter Selasky 308d59ecb2SHans Petter Selasky #include <sys/param.h> 318d59ecb2SHans Petter Selasky #include <sys/systm.h> 328d59ecb2SHans Petter Selasky #include <sys/malloc.h> 338d59ecb2SHans Petter Selasky #include <sys/kernel.h> 348d59ecb2SHans Petter Selasky #include <sys/sysctl.h> 358d59ecb2SHans Petter Selasky #include <sys/lock.h> 368d59ecb2SHans Petter Selasky #include <sys/mutex.h> 378d59ecb2SHans Petter Selasky 388d59ecb2SHans Petter Selasky #include <machine/stdarg.h> 398d59ecb2SHans Petter Selasky 40c9dd0b48SHans Petter Selasky #include <linux/bitmap.h> 418d59ecb2SHans Petter Selasky #include <linux/kobject.h> 428d59ecb2SHans Petter Selasky #include <linux/slab.h> 438d59ecb2SHans Petter Selasky #include <linux/idr.h> 448d59ecb2SHans Petter Selasky #include <linux/err.h> 458d59ecb2SHans Petter Selasky 46427cefdeSHans Petter Selasky #define MAX_IDR_LEVEL ((MAX_IDR_SHIFT + IDR_BITS - 1) / IDR_BITS) 47427cefdeSHans Petter Selasky #define MAX_IDR_FREE (MAX_IDR_LEVEL * 2) 48427cefdeSHans Petter Selasky 49427cefdeSHans Petter Selasky struct linux_idr_cache { 50427cefdeSHans Petter Selasky spinlock_t lock; 51427cefdeSHans Petter Selasky struct idr_layer *head; 52427cefdeSHans Petter Selasky unsigned count; 53427cefdeSHans Petter Selasky }; 54427cefdeSHans Petter Selasky 552bf95012SAndrew Turner DPCPU_DEFINE_STATIC(struct linux_idr_cache, linux_idr_cache); 56427cefdeSHans Petter Selasky 578d59ecb2SHans Petter Selasky /* 588d59ecb2SHans Petter Selasky * IDR Implementation. 598d59ecb2SHans Petter Selasky * 608d59ecb2SHans Petter Selasky * This is quick and dirty and not as re-entrant as the linux version 618d59ecb2SHans Petter Selasky * however it should be fairly fast. It is basically a radix tree with 628d59ecb2SHans Petter Selasky * a builtin bitmap for allocation. 638d59ecb2SHans Petter Selasky */ 648d59ecb2SHans Petter Selasky static MALLOC_DEFINE(M_IDR, "idr", "Linux IDR compat"); 658d59ecb2SHans Petter Selasky 66427cefdeSHans Petter Selasky static struct idr_layer * 67427cefdeSHans Petter Selasky idr_preload_dequeue_locked(struct linux_idr_cache *lic) 68427cefdeSHans Petter Selasky { 69427cefdeSHans Petter Selasky struct idr_layer *retval; 70427cefdeSHans Petter Selasky 71427cefdeSHans Petter Selasky /* check if wrong thread is trying to dequeue */ 72427cefdeSHans Petter Selasky if (mtx_owned(&lic->lock.m) == 0) 73427cefdeSHans Petter Selasky return (NULL); 74427cefdeSHans Petter Selasky 75427cefdeSHans Petter Selasky retval = lic->head; 76427cefdeSHans Petter Selasky if (likely(retval != NULL)) { 77427cefdeSHans Petter Selasky lic->head = retval->ary[0]; 78427cefdeSHans Petter Selasky lic->count--; 79427cefdeSHans Petter Selasky retval->ary[0] = NULL; 80427cefdeSHans Petter Selasky } 81427cefdeSHans Petter Selasky return (retval); 82427cefdeSHans Petter Selasky } 83427cefdeSHans Petter Selasky 84427cefdeSHans Petter Selasky static void 85427cefdeSHans Petter Selasky idr_preload_init(void *arg) 86427cefdeSHans Petter Selasky { 87427cefdeSHans Petter Selasky int cpu; 88427cefdeSHans Petter Selasky 89427cefdeSHans Petter Selasky CPU_FOREACH(cpu) { 90427cefdeSHans Petter Selasky struct linux_idr_cache *lic = 91427cefdeSHans Petter Selasky DPCPU_ID_PTR(cpu, linux_idr_cache); 92427cefdeSHans Petter Selasky 93427cefdeSHans Petter Selasky spin_lock_init(&lic->lock); 94427cefdeSHans Petter Selasky } 95427cefdeSHans Petter Selasky } 9625b3ef2cSHans Petter Selasky SYSINIT(idr_preload_init, SI_SUB_CPU, SI_ORDER_ANY, idr_preload_init, NULL); 97427cefdeSHans Petter Selasky 98427cefdeSHans Petter Selasky static void 99427cefdeSHans Petter Selasky idr_preload_uninit(void *arg) 100427cefdeSHans Petter Selasky { 101427cefdeSHans Petter Selasky int cpu; 102427cefdeSHans Petter Selasky 103427cefdeSHans Petter Selasky CPU_FOREACH(cpu) { 104427cefdeSHans Petter Selasky struct idr_layer *cacheval; 105427cefdeSHans Petter Selasky struct linux_idr_cache *lic = 106427cefdeSHans Petter Selasky DPCPU_ID_PTR(cpu, linux_idr_cache); 107427cefdeSHans Petter Selasky 108427cefdeSHans Petter Selasky while (1) { 109427cefdeSHans Petter Selasky spin_lock(&lic->lock); 110427cefdeSHans Petter Selasky cacheval = idr_preload_dequeue_locked(lic); 111427cefdeSHans Petter Selasky spin_unlock(&lic->lock); 112427cefdeSHans Petter Selasky 113427cefdeSHans Petter Selasky if (cacheval == NULL) 114427cefdeSHans Petter Selasky break; 115427cefdeSHans Petter Selasky free(cacheval, M_IDR); 116427cefdeSHans Petter Selasky } 117427cefdeSHans Petter Selasky spin_lock_destroy(&lic->lock); 118427cefdeSHans Petter Selasky } 119427cefdeSHans Petter Selasky } 120427cefdeSHans Petter Selasky SYSUNINIT(idr_preload_uninit, SI_SUB_LOCK, SI_ORDER_FIRST, idr_preload_uninit, NULL); 121427cefdeSHans Petter Selasky 122427cefdeSHans Petter Selasky void 123427cefdeSHans Petter Selasky idr_preload(gfp_t gfp_mask) 124427cefdeSHans Petter Selasky { 125427cefdeSHans Petter Selasky struct linux_idr_cache *lic; 126427cefdeSHans Petter Selasky struct idr_layer *cacheval; 127427cefdeSHans Petter Selasky 128427cefdeSHans Petter Selasky sched_pin(); 129427cefdeSHans Petter Selasky 130427cefdeSHans Petter Selasky lic = &DPCPU_GET(linux_idr_cache); 131427cefdeSHans Petter Selasky 132427cefdeSHans Petter Selasky /* fill up cache */ 133427cefdeSHans Petter Selasky spin_lock(&lic->lock); 134427cefdeSHans Petter Selasky while (lic->count < MAX_IDR_FREE) { 135427cefdeSHans Petter Selasky spin_unlock(&lic->lock); 136427cefdeSHans Petter Selasky cacheval = malloc(sizeof(*cacheval), M_IDR, M_ZERO | gfp_mask); 137427cefdeSHans Petter Selasky spin_lock(&lic->lock); 138427cefdeSHans Petter Selasky if (cacheval == NULL) 139427cefdeSHans Petter Selasky break; 140427cefdeSHans Petter Selasky cacheval->ary[0] = lic->head; 141427cefdeSHans Petter Selasky lic->head = cacheval; 142427cefdeSHans Petter Selasky lic->count++; 143427cefdeSHans Petter Selasky } 144427cefdeSHans Petter Selasky } 145427cefdeSHans Petter Selasky 146427cefdeSHans Petter Selasky void 147427cefdeSHans Petter Selasky idr_preload_end(void) 148427cefdeSHans Petter Selasky { 149427cefdeSHans Petter Selasky struct linux_idr_cache *lic; 150427cefdeSHans Petter Selasky 151427cefdeSHans Petter Selasky lic = &DPCPU_GET(linux_idr_cache); 152427cefdeSHans Petter Selasky spin_unlock(&lic->lock); 153427cefdeSHans Petter Selasky sched_unpin(); 154427cefdeSHans Petter Selasky } 155427cefdeSHans Petter Selasky 1568d59ecb2SHans Petter Selasky static inline int 1578d59ecb2SHans Petter Selasky idr_max(struct idr *idr) 1588d59ecb2SHans Petter Selasky { 1598d59ecb2SHans Petter Selasky return (1 << (idr->layers * IDR_BITS)) - 1; 1608d59ecb2SHans Petter Selasky } 1618d59ecb2SHans Petter Selasky 1628d59ecb2SHans Petter Selasky static inline int 1638d59ecb2SHans Petter Selasky idr_pos(int id, int layer) 1648d59ecb2SHans Petter Selasky { 1658d59ecb2SHans Petter Selasky return (id >> (IDR_BITS * layer)) & IDR_MASK; 1668d59ecb2SHans Petter Selasky } 1678d59ecb2SHans Petter Selasky 1688d59ecb2SHans Petter Selasky void 1698d59ecb2SHans Petter Selasky idr_init(struct idr *idr) 1708d59ecb2SHans Petter Selasky { 1718d59ecb2SHans Petter Selasky bzero(idr, sizeof(*idr)); 1728d59ecb2SHans Petter Selasky mtx_init(&idr->lock, "idr", NULL, MTX_DEF); 1738d59ecb2SHans Petter Selasky } 1748d59ecb2SHans Petter Selasky 1758d59ecb2SHans Petter Selasky /* Only frees cached pages. */ 1768d59ecb2SHans Petter Selasky void 1778d59ecb2SHans Petter Selasky idr_destroy(struct idr *idr) 1788d59ecb2SHans Petter Selasky { 1798d59ecb2SHans Petter Selasky struct idr_layer *il, *iln; 1808d59ecb2SHans Petter Selasky 1818d59ecb2SHans Petter Selasky idr_remove_all(idr); 1828d59ecb2SHans Petter Selasky mtx_lock(&idr->lock); 1838d59ecb2SHans Petter Selasky for (il = idr->free; il != NULL; il = iln) { 1848d59ecb2SHans Petter Selasky iln = il->ary[0]; 1858d59ecb2SHans Petter Selasky free(il, M_IDR); 1868d59ecb2SHans Petter Selasky } 1878d59ecb2SHans Petter Selasky mtx_unlock(&idr->lock); 1885d35d777SHans Petter Selasky mtx_destroy(&idr->lock); 1898d59ecb2SHans Petter Selasky } 1908d59ecb2SHans Petter Selasky 1918d59ecb2SHans Petter Selasky static void 1928d59ecb2SHans Petter Selasky idr_remove_layer(struct idr_layer *il, int layer) 1938d59ecb2SHans Petter Selasky { 1948d59ecb2SHans Petter Selasky int i; 1958d59ecb2SHans Petter Selasky 1968d59ecb2SHans Petter Selasky if (il == NULL) 1978d59ecb2SHans Petter Selasky return; 1988d59ecb2SHans Petter Selasky if (layer == 0) { 1998d59ecb2SHans Petter Selasky free(il, M_IDR); 2008d59ecb2SHans Petter Selasky return; 2018d59ecb2SHans Petter Selasky } 2028d59ecb2SHans Petter Selasky for (i = 0; i < IDR_SIZE; i++) 2038d59ecb2SHans Petter Selasky if (il->ary[i]) 2048d59ecb2SHans Petter Selasky idr_remove_layer(il->ary[i], layer - 1); 2058d59ecb2SHans Petter Selasky } 2068d59ecb2SHans Petter Selasky 2078d59ecb2SHans Petter Selasky void 2088d59ecb2SHans Petter Selasky idr_remove_all(struct idr *idr) 2098d59ecb2SHans Petter Selasky { 2108d59ecb2SHans Petter Selasky 2118d59ecb2SHans Petter Selasky mtx_lock(&idr->lock); 2128d59ecb2SHans Petter Selasky idr_remove_layer(idr->top, idr->layers - 1); 2138d59ecb2SHans Petter Selasky idr->top = NULL; 2148d59ecb2SHans Petter Selasky idr->layers = 0; 2158d59ecb2SHans Petter Selasky mtx_unlock(&idr->lock); 2168d59ecb2SHans Petter Selasky } 2178d59ecb2SHans Petter Selasky 21869d6653bSHans Petter Selasky static void * 2192d1bee65SHans Petter Selasky idr_remove_locked(struct idr *idr, int id) 2208d59ecb2SHans Petter Selasky { 2218d59ecb2SHans Petter Selasky struct idr_layer *il; 22269d6653bSHans Petter Selasky void *res; 2238d59ecb2SHans Petter Selasky int layer; 2248d59ecb2SHans Petter Selasky int idx; 2258d59ecb2SHans Petter Selasky 2268d59ecb2SHans Petter Selasky id &= MAX_ID_MASK; 2278d59ecb2SHans Petter Selasky il = idr->top; 2288d59ecb2SHans Petter Selasky layer = idr->layers - 1; 2292d1bee65SHans Petter Selasky if (il == NULL || id > idr_max(idr)) 23069d6653bSHans Petter Selasky return (NULL); 2318d59ecb2SHans Petter Selasky /* 2328d59ecb2SHans Petter Selasky * Walk down the tree to this item setting bitmaps along the way 2338d59ecb2SHans Petter Selasky * as we know at least one item will be free along this path. 2348d59ecb2SHans Petter Selasky */ 2358d59ecb2SHans Petter Selasky while (layer && il) { 2368d59ecb2SHans Petter Selasky idx = idr_pos(id, layer); 2378d59ecb2SHans Petter Selasky il->bitmap |= 1 << idx; 2388d59ecb2SHans Petter Selasky il = il->ary[idx]; 2398d59ecb2SHans Petter Selasky layer--; 2408d59ecb2SHans Petter Selasky } 2418d59ecb2SHans Petter Selasky idx = id & IDR_MASK; 2428d59ecb2SHans Petter Selasky /* 2438d59ecb2SHans Petter Selasky * At this point we've set free space bitmaps up the whole tree. 2448d59ecb2SHans Petter Selasky * We could make this non-fatal and unwind but linux dumps a stack 2458d59ecb2SHans Petter Selasky * and a warning so I don't think it's necessary. 2468d59ecb2SHans Petter Selasky */ 2478d59ecb2SHans Petter Selasky if (il == NULL || (il->bitmap & (1 << idx)) != 0) 2488d59ecb2SHans Petter Selasky panic("idr_remove: Item %d not allocated (%p, %p)\n", 2498d59ecb2SHans Petter Selasky id, idr, il); 25069d6653bSHans Petter Selasky res = il->ary[idx]; 2518d59ecb2SHans Petter Selasky il->ary[idx] = NULL; 2528d59ecb2SHans Petter Selasky il->bitmap |= 1 << idx; 25369d6653bSHans Petter Selasky 25469d6653bSHans Petter Selasky return (res); 2552d1bee65SHans Petter Selasky } 2562d1bee65SHans Petter Selasky 25769d6653bSHans Petter Selasky void * 2582d1bee65SHans Petter Selasky idr_remove(struct idr *idr, int id) 2592d1bee65SHans Petter Selasky { 26069d6653bSHans Petter Selasky void *res; 26169d6653bSHans Petter Selasky 2622d1bee65SHans Petter Selasky mtx_lock(&idr->lock); 26369d6653bSHans Petter Selasky res = idr_remove_locked(idr, id); 2648d59ecb2SHans Petter Selasky mtx_unlock(&idr->lock); 26569d6653bSHans Petter Selasky 26669d6653bSHans Petter Selasky return (res); 2678d59ecb2SHans Petter Selasky } 2688d59ecb2SHans Petter Selasky 269f8221002SHans Petter Selasky static inline struct idr_layer * 270f8221002SHans Petter Selasky idr_find_layer_locked(struct idr *idr, int id) 271f8221002SHans Petter Selasky { 272f8221002SHans Petter Selasky struct idr_layer *il; 273f8221002SHans Petter Selasky int layer; 274f8221002SHans Petter Selasky 275f8221002SHans Petter Selasky id &= MAX_ID_MASK; 276f8221002SHans Petter Selasky il = idr->top; 277f8221002SHans Petter Selasky layer = idr->layers - 1; 278f8221002SHans Petter Selasky if (il == NULL || id > idr_max(idr)) 279f8221002SHans Petter Selasky return (NULL); 280f8221002SHans Petter Selasky while (layer && il) { 281f8221002SHans Petter Selasky il = il->ary[idr_pos(id, layer)]; 282f8221002SHans Petter Selasky layer--; 283f8221002SHans Petter Selasky } 284f8221002SHans Petter Selasky return (il); 285f8221002SHans Petter Selasky } 286f8221002SHans Petter Selasky 2878d59ecb2SHans Petter Selasky void * 2888d59ecb2SHans Petter Selasky idr_replace(struct idr *idr, void *ptr, int id) 2898d59ecb2SHans Petter Selasky { 2908d59ecb2SHans Petter Selasky struct idr_layer *il; 2918d59ecb2SHans Petter Selasky void *res; 2928d59ecb2SHans Petter Selasky int idx; 2938d59ecb2SHans Petter Selasky 2948d59ecb2SHans Petter Selasky mtx_lock(&idr->lock); 295f8221002SHans Petter Selasky il = idr_find_layer_locked(idr, id); 2968d59ecb2SHans Petter Selasky idx = id & IDR_MASK; 297f8221002SHans Petter Selasky 298f8221002SHans Petter Selasky /* Replace still returns an error if the item was not allocated. */ 299f8221002SHans Petter Selasky if (il == NULL || (il->bitmap & (1 << idx))) { 300f8221002SHans Petter Selasky res = ERR_PTR(-ENOENT); 301f8221002SHans Petter Selasky } else { 3028d59ecb2SHans Petter Selasky res = il->ary[idx]; 3038d59ecb2SHans Petter Selasky il->ary[idx] = ptr; 3048d59ecb2SHans Petter Selasky } 3058d59ecb2SHans Petter Selasky mtx_unlock(&idr->lock); 3068d59ecb2SHans Petter Selasky return (res); 3078d59ecb2SHans Petter Selasky } 3088d59ecb2SHans Petter Selasky 3098d59ecb2SHans Petter Selasky static inline void * 3108d59ecb2SHans Petter Selasky idr_find_locked(struct idr *idr, int id) 3118d59ecb2SHans Petter Selasky { 3128d59ecb2SHans Petter Selasky struct idr_layer *il; 3138d59ecb2SHans Petter Selasky void *res; 3148d59ecb2SHans Petter Selasky 3158d59ecb2SHans Petter Selasky mtx_assert(&idr->lock, MA_OWNED); 316f8221002SHans Petter Selasky il = idr_find_layer_locked(idr, id); 3178d59ecb2SHans Petter Selasky if (il != NULL) 3188d59ecb2SHans Petter Selasky res = il->ary[id & IDR_MASK]; 319f8221002SHans Petter Selasky else 320f8221002SHans Petter Selasky res = NULL; 3218d59ecb2SHans Petter Selasky return (res); 3228d59ecb2SHans Petter Selasky } 3238d59ecb2SHans Petter Selasky 3248d59ecb2SHans Petter Selasky void * 3258d59ecb2SHans Petter Selasky idr_find(struct idr *idr, int id) 3268d59ecb2SHans Petter Selasky { 3278d59ecb2SHans Petter Selasky void *res; 3288d59ecb2SHans Petter Selasky 3298d59ecb2SHans Petter Selasky mtx_lock(&idr->lock); 3308d59ecb2SHans Petter Selasky res = idr_find_locked(idr, id); 3318d59ecb2SHans Petter Selasky mtx_unlock(&idr->lock); 3328d59ecb2SHans Petter Selasky return (res); 3338d59ecb2SHans Petter Selasky } 3348d59ecb2SHans Petter Selasky 335fd42d623SHans Petter Selasky void * 336fd42d623SHans Petter Selasky idr_get_next(struct idr *idr, int *nextidp) 337fd42d623SHans Petter Selasky { 338fd42d623SHans Petter Selasky void *res = NULL; 339fd42d623SHans Petter Selasky int id = *nextidp; 340fd42d623SHans Petter Selasky 341fd42d623SHans Petter Selasky mtx_lock(&idr->lock); 342fd42d623SHans Petter Selasky for (; id <= idr_max(idr); id++) { 343fd42d623SHans Petter Selasky res = idr_find_locked(idr, id); 344fd42d623SHans Petter Selasky if (res == NULL) 345fd42d623SHans Petter Selasky continue; 346fd42d623SHans Petter Selasky *nextidp = id; 347fd42d623SHans Petter Selasky break; 348fd42d623SHans Petter Selasky } 349fd42d623SHans Petter Selasky mtx_unlock(&idr->lock); 350fd42d623SHans Petter Selasky return (res); 351fd42d623SHans Petter Selasky } 352fd42d623SHans Petter Selasky 3538d59ecb2SHans Petter Selasky int 3548d59ecb2SHans Petter Selasky idr_pre_get(struct idr *idr, gfp_t gfp_mask) 3558d59ecb2SHans Petter Selasky { 3568d59ecb2SHans Petter Selasky struct idr_layer *il, *iln; 3578d59ecb2SHans Petter Selasky struct idr_layer *head; 3588d59ecb2SHans Petter Selasky int need; 3598d59ecb2SHans Petter Selasky 3608d59ecb2SHans Petter Selasky mtx_lock(&idr->lock); 3618d59ecb2SHans Petter Selasky for (;;) { 3628d59ecb2SHans Petter Selasky need = idr->layers + 1; 3638d59ecb2SHans Petter Selasky for (il = idr->free; il != NULL; il = il->ary[0]) 3648d59ecb2SHans Petter Selasky need--; 3658d59ecb2SHans Petter Selasky mtx_unlock(&idr->lock); 3668d59ecb2SHans Petter Selasky if (need <= 0) 3678d59ecb2SHans Petter Selasky break; 3688d59ecb2SHans Petter Selasky for (head = NULL; need; need--) { 3698d59ecb2SHans Petter Selasky iln = malloc(sizeof(*il), M_IDR, M_ZERO | gfp_mask); 3708d59ecb2SHans Petter Selasky if (iln == NULL) 3718d59ecb2SHans Petter Selasky break; 3728d59ecb2SHans Petter Selasky bitmap_fill(&iln->bitmap, IDR_SIZE); 3738d59ecb2SHans Petter Selasky if (head != NULL) { 3748d59ecb2SHans Petter Selasky il->ary[0] = iln; 3758d59ecb2SHans Petter Selasky il = iln; 3768d59ecb2SHans Petter Selasky } else 3778d59ecb2SHans Petter Selasky head = il = iln; 3788d59ecb2SHans Petter Selasky } 3798d59ecb2SHans Petter Selasky if (head == NULL) 3808d59ecb2SHans Petter Selasky return (0); 3818d59ecb2SHans Petter Selasky mtx_lock(&idr->lock); 3828d59ecb2SHans Petter Selasky il->ary[0] = idr->free; 3838d59ecb2SHans Petter Selasky idr->free = head; 3848d59ecb2SHans Petter Selasky } 3858d59ecb2SHans Petter Selasky return (1); 3868d59ecb2SHans Petter Selasky } 3878d59ecb2SHans Petter Selasky 388427cefdeSHans Petter Selasky static struct idr_layer * 389427cefdeSHans Petter Selasky idr_free_list_get(struct idr *idp) 3908d59ecb2SHans Petter Selasky { 3918d59ecb2SHans Petter Selasky struct idr_layer *il; 3928d59ecb2SHans Petter Selasky 393427cefdeSHans Petter Selasky if ((il = idp->free) != NULL) { 394427cefdeSHans Petter Selasky idp->free = il->ary[0]; 3958d59ecb2SHans Petter Selasky il->ary[0] = NULL; 396427cefdeSHans Petter Selasky } 3978d59ecb2SHans Petter Selasky return (il); 3988d59ecb2SHans Petter Selasky } 399427cefdeSHans Petter Selasky 400427cefdeSHans Petter Selasky static inline struct idr_layer * 401427cefdeSHans Petter Selasky idr_get(struct idr *idp) 402427cefdeSHans Petter Selasky { 403427cefdeSHans Petter Selasky struct idr_layer *il; 404427cefdeSHans Petter Selasky 405427cefdeSHans Petter Selasky if ((il = idr_free_list_get(idp)) != NULL) { 406427cefdeSHans Petter Selasky MPASS(il->bitmap != 0); 407427cefdeSHans Petter Selasky } else if ((il = malloc(sizeof(*il), M_IDR, M_ZERO | M_NOWAIT)) != NULL) { 4088d59ecb2SHans Petter Selasky bitmap_fill(&il->bitmap, IDR_SIZE); 409427cefdeSHans Petter Selasky } else if ((il = idr_preload_dequeue_locked(&DPCPU_GET(linux_idr_cache))) != NULL) { 410427cefdeSHans Petter Selasky bitmap_fill(&il->bitmap, IDR_SIZE); 411427cefdeSHans Petter Selasky } else { 412427cefdeSHans Petter Selasky return (NULL); 413427cefdeSHans Petter Selasky } 4148d59ecb2SHans Petter Selasky return (il); 4158d59ecb2SHans Petter Selasky } 4168d59ecb2SHans Petter Selasky 4178d59ecb2SHans Petter Selasky /* 4188d59ecb2SHans Petter Selasky * Could be implemented as get_new_above(idr, ptr, 0, idp) but written 4198d59ecb2SHans Petter Selasky * first for simplicity sake. 4208d59ecb2SHans Petter Selasky */ 4212d1bee65SHans Petter Selasky static int 4222d1bee65SHans Petter Selasky idr_get_new_locked(struct idr *idr, void *ptr, int *idp) 4238d59ecb2SHans Petter Selasky { 4248d59ecb2SHans Petter Selasky struct idr_layer *stack[MAX_LEVEL]; 4258d59ecb2SHans Petter Selasky struct idr_layer *il; 4268d59ecb2SHans Petter Selasky int error; 4278d59ecb2SHans Petter Selasky int layer; 4288d59ecb2SHans Petter Selasky int idx; 4298d59ecb2SHans Petter Selasky int id; 4308d59ecb2SHans Petter Selasky 4312d1bee65SHans Petter Selasky mtx_assert(&idr->lock, MA_OWNED); 4322d1bee65SHans Petter Selasky 4338d59ecb2SHans Petter Selasky error = -EAGAIN; 4348d59ecb2SHans Petter Selasky /* 4358d59ecb2SHans Petter Selasky * Expand the tree until there is free space. 4368d59ecb2SHans Petter Selasky */ 4378d59ecb2SHans Petter Selasky if (idr->top == NULL || idr->top->bitmap == 0) { 4388d59ecb2SHans Petter Selasky if (idr->layers == MAX_LEVEL + 1) { 4398d59ecb2SHans Petter Selasky error = -ENOSPC; 4408d59ecb2SHans Petter Selasky goto out; 4418d59ecb2SHans Petter Selasky } 4428d59ecb2SHans Petter Selasky il = idr_get(idr); 4438d59ecb2SHans Petter Selasky if (il == NULL) 4448d59ecb2SHans Petter Selasky goto out; 4458d59ecb2SHans Petter Selasky il->ary[0] = idr->top; 4468d59ecb2SHans Petter Selasky if (idr->top) 4478d59ecb2SHans Petter Selasky il->bitmap &= ~1; 4488d59ecb2SHans Petter Selasky idr->top = il; 4498d59ecb2SHans Petter Selasky idr->layers++; 4508d59ecb2SHans Petter Selasky } 4518d59ecb2SHans Petter Selasky il = idr->top; 4528d59ecb2SHans Petter Selasky id = 0; 4538d59ecb2SHans Petter Selasky /* 4548d59ecb2SHans Petter Selasky * Walk the tree following free bitmaps, record our path. 4558d59ecb2SHans Petter Selasky */ 4568d59ecb2SHans Petter Selasky for (layer = idr->layers - 1;; layer--) { 4578d59ecb2SHans Petter Selasky stack[layer] = il; 4588d59ecb2SHans Petter Selasky idx = ffsl(il->bitmap); 4598d59ecb2SHans Petter Selasky if (idx == 0) 4608d59ecb2SHans Petter Selasky panic("idr_get_new: Invalid leaf state (%p, %p)\n", 4618d59ecb2SHans Petter Selasky idr, il); 4628d59ecb2SHans Petter Selasky idx--; 4638d59ecb2SHans Petter Selasky id |= idx << (layer * IDR_BITS); 4648d59ecb2SHans Petter Selasky if (layer == 0) 4658d59ecb2SHans Petter Selasky break; 4668d59ecb2SHans Petter Selasky if (il->ary[idx] == NULL) { 4678d59ecb2SHans Petter Selasky il->ary[idx] = idr_get(idr); 4688d59ecb2SHans Petter Selasky if (il->ary[idx] == NULL) 4698d59ecb2SHans Petter Selasky goto out; 4708d59ecb2SHans Petter Selasky } 4718d59ecb2SHans Petter Selasky il = il->ary[idx]; 4728d59ecb2SHans Petter Selasky } 4738d59ecb2SHans Petter Selasky /* 4748d59ecb2SHans Petter Selasky * Allocate the leaf to the consumer. 4758d59ecb2SHans Petter Selasky */ 4768d59ecb2SHans Petter Selasky il->bitmap &= ~(1 << idx); 4778d59ecb2SHans Petter Selasky il->ary[idx] = ptr; 4788d59ecb2SHans Petter Selasky *idp = id; 4798d59ecb2SHans Petter Selasky /* 4808d59ecb2SHans Petter Selasky * Clear bitmaps potentially up to the root. 4818d59ecb2SHans Petter Selasky */ 4828d59ecb2SHans Petter Selasky while (il->bitmap == 0 && ++layer < idr->layers) { 4838d59ecb2SHans Petter Selasky il = stack[layer]; 4848d59ecb2SHans Petter Selasky il->bitmap &= ~(1 << idr_pos(id, layer)); 4858d59ecb2SHans Petter Selasky } 4868d59ecb2SHans Petter Selasky error = 0; 4878d59ecb2SHans Petter Selasky out: 4888d59ecb2SHans Petter Selasky #ifdef INVARIANTS 4898d59ecb2SHans Petter Selasky if (error == 0 && idr_find_locked(idr, id) != ptr) { 4908d59ecb2SHans Petter Selasky panic("idr_get_new: Failed for idr %p, id %d, ptr %p\n", 4918d59ecb2SHans Petter Selasky idr, id, ptr); 4928d59ecb2SHans Petter Selasky } 4938d59ecb2SHans Petter Selasky #endif 4948d59ecb2SHans Petter Selasky return (error); 4958d59ecb2SHans Petter Selasky } 4968d59ecb2SHans Petter Selasky 4978d59ecb2SHans Petter Selasky int 4982d1bee65SHans Petter Selasky idr_get_new(struct idr *idr, void *ptr, int *idp) 4992d1bee65SHans Petter Selasky { 5002d1bee65SHans Petter Selasky int retval; 5012d1bee65SHans Petter Selasky 5022d1bee65SHans Petter Selasky mtx_lock(&idr->lock); 5032d1bee65SHans Petter Selasky retval = idr_get_new_locked(idr, ptr, idp); 5042d1bee65SHans Petter Selasky mtx_unlock(&idr->lock); 5052d1bee65SHans Petter Selasky return (retval); 5062d1bee65SHans Petter Selasky } 5072d1bee65SHans Petter Selasky 5082d1bee65SHans Petter Selasky static int 5092d1bee65SHans Petter Selasky idr_get_new_above_locked(struct idr *idr, void *ptr, int starting_id, int *idp) 5108d59ecb2SHans Petter Selasky { 5118d59ecb2SHans Petter Selasky struct idr_layer *stack[MAX_LEVEL]; 5128d59ecb2SHans Petter Selasky struct idr_layer *il; 5138d59ecb2SHans Petter Selasky int error; 5148d59ecb2SHans Petter Selasky int layer; 5158d59ecb2SHans Petter Selasky int idx, sidx; 5168d59ecb2SHans Petter Selasky int id; 5178d59ecb2SHans Petter Selasky 5182d1bee65SHans Petter Selasky mtx_assert(&idr->lock, MA_OWNED); 5192d1bee65SHans Petter Selasky 5208d59ecb2SHans Petter Selasky error = -EAGAIN; 5218d59ecb2SHans Petter Selasky /* 5228d59ecb2SHans Petter Selasky * Compute the layers required to support starting_id and the mask 5238d59ecb2SHans Petter Selasky * at the top layer. 5248d59ecb2SHans Petter Selasky */ 5258d59ecb2SHans Petter Selasky restart: 5268d59ecb2SHans Petter Selasky idx = starting_id; 5278d59ecb2SHans Petter Selasky layer = 0; 5288d59ecb2SHans Petter Selasky while (idx & ~IDR_MASK) { 5298d59ecb2SHans Petter Selasky layer++; 5308d59ecb2SHans Petter Selasky idx >>= IDR_BITS; 5318d59ecb2SHans Petter Selasky } 5328d59ecb2SHans Petter Selasky if (layer == MAX_LEVEL + 1) { 5338d59ecb2SHans Petter Selasky error = -ENOSPC; 5348d59ecb2SHans Petter Selasky goto out; 5358d59ecb2SHans Petter Selasky } 5368d59ecb2SHans Petter Selasky /* 5378d59ecb2SHans Petter Selasky * Expand the tree until there is free space at or beyond starting_id. 5388d59ecb2SHans Petter Selasky */ 5398d59ecb2SHans Petter Selasky while (idr->layers <= layer || 5408d59ecb2SHans Petter Selasky idr->top->bitmap < (1 << idr_pos(starting_id, idr->layers - 1))) { 5418d59ecb2SHans Petter Selasky if (idr->layers == MAX_LEVEL + 1) { 5428d59ecb2SHans Petter Selasky error = -ENOSPC; 5438d59ecb2SHans Petter Selasky goto out; 5448d59ecb2SHans Petter Selasky } 5458d59ecb2SHans Petter Selasky il = idr_get(idr); 5468d59ecb2SHans Petter Selasky if (il == NULL) 5478d59ecb2SHans Petter Selasky goto out; 5488d59ecb2SHans Petter Selasky il->ary[0] = idr->top; 5498d59ecb2SHans Petter Selasky if (idr->top && idr->top->bitmap == 0) 5508d59ecb2SHans Petter Selasky il->bitmap &= ~1; 5518d59ecb2SHans Petter Selasky idr->top = il; 5528d59ecb2SHans Petter Selasky idr->layers++; 5538d59ecb2SHans Petter Selasky } 5548d59ecb2SHans Petter Selasky il = idr->top; 5558d59ecb2SHans Petter Selasky id = 0; 5568d59ecb2SHans Petter Selasky /* 5578d59ecb2SHans Petter Selasky * Walk the tree following free bitmaps, record our path. 5588d59ecb2SHans Petter Selasky */ 5598d59ecb2SHans Petter Selasky for (layer = idr->layers - 1;; layer--) { 5608d59ecb2SHans Petter Selasky stack[layer] = il; 5618d59ecb2SHans Petter Selasky sidx = idr_pos(starting_id, layer); 5628d59ecb2SHans Petter Selasky /* Returns index numbered from 0 or size if none exists. */ 5638d59ecb2SHans Petter Selasky idx = find_next_bit(&il->bitmap, IDR_SIZE, sidx); 5648d59ecb2SHans Petter Selasky if (idx == IDR_SIZE && sidx == 0) 5658d59ecb2SHans Petter Selasky panic("idr_get_new: Invalid leaf state (%p, %p)\n", 5668d59ecb2SHans Petter Selasky idr, il); 5678d59ecb2SHans Petter Selasky /* 5688d59ecb2SHans Petter Selasky * We may have walked a path where there was a free bit but 5698d59ecb2SHans Petter Selasky * it was lower than what we wanted. Restart the search with 5708d59ecb2SHans Petter Selasky * a larger starting id. id contains the progress we made so 5718d59ecb2SHans Petter Selasky * far. Search the leaf one above this level. This may 5728d59ecb2SHans Petter Selasky * restart as many as MAX_LEVEL times but that is expected 5738d59ecb2SHans Petter Selasky * to be rare. 5748d59ecb2SHans Petter Selasky */ 5758d59ecb2SHans Petter Selasky if (idx == IDR_SIZE) { 5768d59ecb2SHans Petter Selasky starting_id = id + (1 << ((layer + 1) * IDR_BITS)); 5778d59ecb2SHans Petter Selasky goto restart; 5788d59ecb2SHans Petter Selasky } 5798d59ecb2SHans Petter Selasky if (idx > sidx) 5808d59ecb2SHans Petter Selasky starting_id = 0; /* Search the whole subtree. */ 5818d59ecb2SHans Petter Selasky id |= idx << (layer * IDR_BITS); 5828d59ecb2SHans Petter Selasky if (layer == 0) 5838d59ecb2SHans Petter Selasky break; 5848d59ecb2SHans Petter Selasky if (il->ary[idx] == NULL) { 5858d59ecb2SHans Petter Selasky il->ary[idx] = idr_get(idr); 5868d59ecb2SHans Petter Selasky if (il->ary[idx] == NULL) 5878d59ecb2SHans Petter Selasky goto out; 5888d59ecb2SHans Petter Selasky } 5898d59ecb2SHans Petter Selasky il = il->ary[idx]; 5908d59ecb2SHans Petter Selasky } 5918d59ecb2SHans Petter Selasky /* 5928d59ecb2SHans Petter Selasky * Allocate the leaf to the consumer. 5938d59ecb2SHans Petter Selasky */ 5948d59ecb2SHans Petter Selasky il->bitmap &= ~(1 << idx); 5958d59ecb2SHans Petter Selasky il->ary[idx] = ptr; 5968d59ecb2SHans Petter Selasky *idp = id; 5978d59ecb2SHans Petter Selasky /* 5988d59ecb2SHans Petter Selasky * Clear bitmaps potentially up to the root. 5998d59ecb2SHans Petter Selasky */ 6008d59ecb2SHans Petter Selasky while (il->bitmap == 0 && ++layer < idr->layers) { 6018d59ecb2SHans Petter Selasky il = stack[layer]; 6028d59ecb2SHans Petter Selasky il->bitmap &= ~(1 << idr_pos(id, layer)); 6038d59ecb2SHans Petter Selasky } 6048d59ecb2SHans Petter Selasky error = 0; 6058d59ecb2SHans Petter Selasky out: 6068d59ecb2SHans Petter Selasky #ifdef INVARIANTS 6078d59ecb2SHans Petter Selasky if (error == 0 && idr_find_locked(idr, id) != ptr) { 6088d59ecb2SHans Petter Selasky panic("idr_get_new_above: Failed for idr %p, id %d, ptr %p\n", 6098d59ecb2SHans Petter Selasky idr, id, ptr); 6108d59ecb2SHans Petter Selasky } 6118d59ecb2SHans Petter Selasky #endif 6128d59ecb2SHans Petter Selasky return (error); 6138d59ecb2SHans Petter Selasky } 6142d1bee65SHans Petter Selasky 6152d1bee65SHans Petter Selasky int 6162d1bee65SHans Petter Selasky idr_get_new_above(struct idr *idr, void *ptr, int starting_id, int *idp) 6172d1bee65SHans Petter Selasky { 6182d1bee65SHans Petter Selasky int retval; 6192d1bee65SHans Petter Selasky 6202d1bee65SHans Petter Selasky mtx_lock(&idr->lock); 6212d1bee65SHans Petter Selasky retval = idr_get_new_above_locked(idr, ptr, starting_id, idp); 6222d1bee65SHans Petter Selasky mtx_unlock(&idr->lock); 6232d1bee65SHans Petter Selasky return (retval); 6242d1bee65SHans Petter Selasky } 6252d1bee65SHans Petter Selasky 626fd42d623SHans Petter Selasky int 627fd42d623SHans Petter Selasky ida_get_new_above(struct ida *ida, int starting_id, int *p_id) 628fd42d623SHans Petter Selasky { 629fd42d623SHans Petter Selasky return (idr_get_new_above(&ida->idr, NULL, starting_id, p_id)); 630fd42d623SHans Petter Selasky } 631fd42d623SHans Petter Selasky 6322d1bee65SHans Petter Selasky static int 6332d1bee65SHans Petter Selasky idr_alloc_locked(struct idr *idr, void *ptr, int start, int end) 6342d1bee65SHans Petter Selasky { 6352d1bee65SHans Petter Selasky int max = end > 0 ? end - 1 : INT_MAX; 6362d1bee65SHans Petter Selasky int error; 6372d1bee65SHans Petter Selasky int id; 6382d1bee65SHans Petter Selasky 6392d1bee65SHans Petter Selasky mtx_assert(&idr->lock, MA_OWNED); 6402d1bee65SHans Petter Selasky 6412d1bee65SHans Petter Selasky if (unlikely(start < 0)) 6422d1bee65SHans Petter Selasky return (-EINVAL); 6432d1bee65SHans Petter Selasky if (unlikely(max < start)) 6442d1bee65SHans Petter Selasky return (-ENOSPC); 6452d1bee65SHans Petter Selasky 6462d1bee65SHans Petter Selasky if (start == 0) 6472d1bee65SHans Petter Selasky error = idr_get_new_locked(idr, ptr, &id); 6482d1bee65SHans Petter Selasky else 6492d1bee65SHans Petter Selasky error = idr_get_new_above_locked(idr, ptr, start, &id); 6502d1bee65SHans Petter Selasky 6512d1bee65SHans Petter Selasky if (unlikely(error < 0)) 6522d1bee65SHans Petter Selasky return (error); 6532d1bee65SHans Petter Selasky if (unlikely(id > max)) { 6542d1bee65SHans Petter Selasky idr_remove_locked(idr, id); 6552d1bee65SHans Petter Selasky return (-ENOSPC); 6562d1bee65SHans Petter Selasky } 6572d1bee65SHans Petter Selasky return (id); 6582d1bee65SHans Petter Selasky } 6592d1bee65SHans Petter Selasky 6602d1bee65SHans Petter Selasky int 6612d1bee65SHans Petter Selasky idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask) 6622d1bee65SHans Petter Selasky { 6632d1bee65SHans Petter Selasky int retval; 6642d1bee65SHans Petter Selasky 6652d1bee65SHans Petter Selasky mtx_lock(&idr->lock); 6662d1bee65SHans Petter Selasky retval = idr_alloc_locked(idr, ptr, start, end); 6672d1bee65SHans Petter Selasky mtx_unlock(&idr->lock); 6682d1bee65SHans Petter Selasky return (retval); 6692d1bee65SHans Petter Selasky } 6702d1bee65SHans Petter Selasky 6712d1bee65SHans Petter Selasky int 6722d1bee65SHans Petter Selasky idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask) 6732d1bee65SHans Petter Selasky { 6742d1bee65SHans Petter Selasky int retval; 6752d1bee65SHans Petter Selasky 6762d1bee65SHans Petter Selasky mtx_lock(&idr->lock); 6772d1bee65SHans Petter Selasky retval = idr_alloc_locked(idr, ptr, max(start, idr->next_cyclic_id), end); 6782d1bee65SHans Petter Selasky if (unlikely(retval == -ENOSPC)) 6792d1bee65SHans Petter Selasky retval = idr_alloc_locked(idr, ptr, start, end); 6802d1bee65SHans Petter Selasky if (likely(retval >= 0)) 6812d1bee65SHans Petter Selasky idr->next_cyclic_id = retval + 1; 6822d1bee65SHans Petter Selasky mtx_unlock(&idr->lock); 6832d1bee65SHans Petter Selasky return (retval); 6842d1bee65SHans Petter Selasky } 685fd42d623SHans Petter Selasky 686fd42d623SHans Petter Selasky static int 687f885420dSHans Petter Selasky idr_for_each_layer(struct idr_layer *il, int offset, int layer, 688fd42d623SHans Petter Selasky int (*f)(int id, void *p, void *data), void *data) 689fd42d623SHans Petter Selasky { 690fd42d623SHans Petter Selasky int i, err; 691fd42d623SHans Petter Selasky 692fd42d623SHans Petter Selasky if (il == NULL) 693fd42d623SHans Petter Selasky return (0); 694fd42d623SHans Petter Selasky if (layer == 0) { 695fd42d623SHans Petter Selasky for (i = 0; i < IDR_SIZE; i++) { 696fd42d623SHans Petter Selasky if (il->ary[i] == NULL) 697fd42d623SHans Petter Selasky continue; 698f885420dSHans Petter Selasky err = f(i + offset, il->ary[i], data); 699fd42d623SHans Petter Selasky if (err) 700fd42d623SHans Petter Selasky return (err); 701fd42d623SHans Petter Selasky } 702fd42d623SHans Petter Selasky return (0); 703fd42d623SHans Petter Selasky } 704fd42d623SHans Petter Selasky for (i = 0; i < IDR_SIZE; i++) { 705fd42d623SHans Petter Selasky if (il->ary[i] == NULL) 706fd42d623SHans Petter Selasky continue; 707f885420dSHans Petter Selasky err = idr_for_each_layer(il->ary[i], 708f885420dSHans Petter Selasky (i + offset) * IDR_SIZE, layer - 1, f, data); 709fd42d623SHans Petter Selasky if (err) 710fd42d623SHans Petter Selasky return (err); 711fd42d623SHans Petter Selasky } 712fd42d623SHans Petter Selasky return (0); 713fd42d623SHans Petter Selasky } 714fd42d623SHans Petter Selasky 715dacb734eSHans Petter Selasky /* NOTE: It is not allowed to modify the IDR tree while it is being iterated */ 716fd42d623SHans Petter Selasky int 717fd42d623SHans Petter Selasky idr_for_each(struct idr *idp, int (*f)(int id, void *p, void *data), void *data) 718fd42d623SHans Petter Selasky { 719f885420dSHans Petter Selasky return (idr_for_each_layer(idp->top, 0, idp->layers - 1, f, data)); 720fd42d623SHans Petter Selasky } 721fd42d623SHans Petter Selasky 72269d6653bSHans Petter Selasky static int 72369d6653bSHans Petter Selasky idr_has_entry(int id, void *p, void *data) 72469d6653bSHans Petter Selasky { 72569d6653bSHans Petter Selasky 72669d6653bSHans Petter Selasky return (1); 72769d6653bSHans Petter Selasky } 72869d6653bSHans Petter Selasky 72969d6653bSHans Petter Selasky bool 73069d6653bSHans Petter Selasky idr_is_empty(struct idr *idp) 73169d6653bSHans Petter Selasky { 73269d6653bSHans Petter Selasky 73369d6653bSHans Petter Selasky return (idr_for_each(idp, idr_has_entry, NULL) == 0); 73469d6653bSHans Petter Selasky } 73569d6653bSHans Petter Selasky 736fd42d623SHans Petter Selasky int 737fd42d623SHans Petter Selasky ida_pre_get(struct ida *ida, gfp_t flags) 738fd42d623SHans Petter Selasky { 739fd42d623SHans Petter Selasky if (idr_pre_get(&ida->idr, flags) == 0) 740fd42d623SHans Petter Selasky return (0); 741fd42d623SHans Petter Selasky 742fd42d623SHans Petter Selasky if (ida->free_bitmap == NULL) { 743fd42d623SHans Petter Selasky ida->free_bitmap = 744fd42d623SHans Petter Selasky malloc(sizeof(struct ida_bitmap), M_IDR, flags); 745fd42d623SHans Petter Selasky } 746fd42d623SHans Petter Selasky return (ida->free_bitmap != NULL); 747fd42d623SHans Petter Selasky } 748fd42d623SHans Petter Selasky 749fd42d623SHans Petter Selasky int 750fd42d623SHans Petter Selasky ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, 751fd42d623SHans Petter Selasky gfp_t flags) 752fd42d623SHans Petter Selasky { 753fd42d623SHans Petter Selasky int ret, id; 754fd42d623SHans Petter Selasky unsigned int max; 755fd42d623SHans Petter Selasky 756fd42d623SHans Petter Selasky MPASS((int)start >= 0); 757fd42d623SHans Petter Selasky 758*c7312643SVladimir Kondratyev if ((int)end <= 0) 759*c7312643SVladimir Kondratyev max = INT_MAX; 760fd42d623SHans Petter Selasky else { 761fd42d623SHans Petter Selasky MPASS(end > start); 762fd42d623SHans Petter Selasky max = end - 1; 763fd42d623SHans Petter Selasky } 764fd42d623SHans Petter Selasky again: 765fd42d623SHans Petter Selasky if (!ida_pre_get(ida, flags)) 766fd42d623SHans Petter Selasky return (-ENOMEM); 767fd42d623SHans Petter Selasky 768fd42d623SHans Petter Selasky if ((ret = ida_get_new_above(ida, start, &id)) == 0) { 769fd42d623SHans Petter Selasky if (id > max) { 770fd42d623SHans Petter Selasky ida_remove(ida, id); 771fd42d623SHans Petter Selasky ret = -ENOSPC; 772fd42d623SHans Petter Selasky } else { 773fd42d623SHans Petter Selasky ret = id; 774fd42d623SHans Petter Selasky } 775fd42d623SHans Petter Selasky } 776fd42d623SHans Petter Selasky if (__predict_false(ret == -EAGAIN)) 777fd42d623SHans Petter Selasky goto again; 778fd42d623SHans Petter Selasky 779fd42d623SHans Petter Selasky return (ret); 780fd42d623SHans Petter Selasky } 781fd42d623SHans Petter Selasky 782fd42d623SHans Petter Selasky void 783fd42d623SHans Petter Selasky ida_simple_remove(struct ida *ida, unsigned int id) 784fd42d623SHans Petter Selasky { 785fd42d623SHans Petter Selasky idr_remove(&ida->idr, id); 786fd42d623SHans Petter Selasky } 787fd42d623SHans Petter Selasky 788fd42d623SHans Petter Selasky void 789fd42d623SHans Petter Selasky ida_remove(struct ida *ida, int id) 790fd42d623SHans Petter Selasky { 791fd42d623SHans Petter Selasky idr_remove(&ida->idr, id); 792fd42d623SHans Petter Selasky } 793fd42d623SHans Petter Selasky 794fd42d623SHans Petter Selasky void 795fd42d623SHans Petter Selasky ida_init(struct ida *ida) 796fd42d623SHans Petter Selasky { 797fd42d623SHans Petter Selasky idr_init(&ida->idr); 798fd42d623SHans Petter Selasky } 799fd42d623SHans Petter Selasky 800fd42d623SHans Petter Selasky void 801fd42d623SHans Petter Selasky ida_destroy(struct ida *ida) 802fd42d623SHans Petter Selasky { 803fd42d623SHans Petter Selasky idr_destroy(&ida->idr); 804fd42d623SHans Petter Selasky free(ida->free_bitmap, M_IDR); 805fd42d623SHans Petter Selasky } 806