xref: /freebsd/sys/compat/linuxkpi/common/src/linux_idr.c (revision c7312643b7e5f01adc2a3094c5139f5dcab5f0a4)
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