2 * Copyright (c) 2010 Isilon Systems, Inc.
3 * Copyright (c) 2010 iX Systems, Inc.
4 * Copyright (c) 2010 Panasas, Inc.
5 * Copyright (c) 2013-2016 Mellanox Technologies, Ltd.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice unmodified, this list of conditions, and the following
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.
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.
30 #include <sys/cdefs.h>
31 __FBSDID("$FreeBSD$");
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>
39 #include <sys/mutex.h>
41 #include <machine/stdarg.h>
43 #include <linux/bitops.h>
44 #include <linux/kobject.h>
45 #include <linux/slab.h>
46 #include <linux/idr.h>
47 #include <linux/err.h>
52 * This is quick and dirty and not as re-entrant as the linux version
53 * however it should be fairly fast. It is basically a radix tree with
54 * a builtin bitmap for allocation.
56 static MALLOC_DEFINE(M_IDR, "idr", "Linux IDR compat");
59 idr_max(struct idr *idr)
61 return (1 << (idr->layers * IDR_BITS)) - 1;
65 idr_pos(int id, int layer)
67 return (id >> (IDR_BITS * layer)) & IDR_MASK;
71 idr_init(struct idr *idr)
73 bzero(idr, sizeof(*idr));
74 mtx_init(&idr->lock, "idr", NULL, MTX_DEF);
77 /* Only frees cached pages. */
79 idr_destroy(struct idr *idr)
81 struct idr_layer *il, *iln;
85 for (il = idr->free; il != NULL; il = iln) {
89 mtx_unlock(&idr->lock);
90 mtx_destroy(&idr->lock);
94 idr_remove_layer(struct idr_layer *il, int layer)
104 for (i = 0; i < IDR_SIZE; i++)
106 idr_remove_layer(il->ary[i], layer - 1);
110 idr_remove_all(struct idr *idr)
113 mtx_lock(&idr->lock);
114 idr_remove_layer(idr->top, idr->layers - 1);
117 mtx_unlock(&idr->lock);
121 idr_remove_locked(struct idr *idr, int id)
123 struct idr_layer *il;
129 layer = idr->layers - 1;
130 if (il == NULL || id > idr_max(idr))
133 * Walk down the tree to this item setting bitmaps along the way
134 * as we know at least one item will be free along this path.
136 while (layer && il) {
137 idx = idr_pos(id, layer);
138 il->bitmap |= 1 << idx;
144 * At this point we've set free space bitmaps up the whole tree.
145 * We could make this non-fatal and unwind but linux dumps a stack
146 * and a warning so I don't think it's necessary.
148 if (il == NULL || (il->bitmap & (1 << idx)) != 0)
149 panic("idr_remove: Item %d not allocated (%p, %p)\n",
152 il->bitmap |= 1 << idx;
156 idr_remove(struct idr *idr, int id)
158 mtx_lock(&idr->lock);
159 idr_remove_locked(idr, id);
160 mtx_unlock(&idr->lock);
164 static inline struct idr_layer *
165 idr_find_layer_locked(struct idr *idr, int id)
167 struct idr_layer *il;
172 layer = idr->layers - 1;
173 if (il == NULL || id > idr_max(idr))
175 while (layer && il) {
176 il = il->ary[idr_pos(id, layer)];
183 idr_replace(struct idr *idr, void *ptr, int id)
185 struct idr_layer *il;
189 mtx_lock(&idr->lock);
190 il = idr_find_layer_locked(idr, id);
193 /* Replace still returns an error if the item was not allocated. */
194 if (il == NULL || (il->bitmap & (1 << idx))) {
195 res = ERR_PTR(-ENOENT);
200 mtx_unlock(&idr->lock);
205 idr_find_locked(struct idr *idr, int id)
207 struct idr_layer *il;
210 mtx_assert(&idr->lock, MA_OWNED);
211 il = idr_find_layer_locked(idr, id);
213 res = il->ary[id & IDR_MASK];
220 idr_find(struct idr *idr, int id)
224 mtx_lock(&idr->lock);
225 res = idr_find_locked(idr, id);
226 mtx_unlock(&idr->lock);
231 idr_get_next(struct idr *idr, int *nextidp)
236 mtx_lock(&idr->lock);
237 for (; id <= idr_max(idr); id++) {
238 res = idr_find_locked(idr, id);
244 mtx_unlock(&idr->lock);
249 idr_pre_get(struct idr *idr, gfp_t gfp_mask)
251 struct idr_layer *il, *iln;
252 struct idr_layer *head;
255 mtx_lock(&idr->lock);
257 need = idr->layers + 1;
258 for (il = idr->free; il != NULL; il = il->ary[0])
260 mtx_unlock(&idr->lock);
263 for (head = NULL; need; need--) {
264 iln = malloc(sizeof(*il), M_IDR, M_ZERO | gfp_mask);
267 bitmap_fill(&iln->bitmap, IDR_SIZE);
276 mtx_lock(&idr->lock);
277 il->ary[0] = idr->free;
283 static inline struct idr_layer *
284 idr_get(struct idr *idr)
286 struct idr_layer *il;
290 idr->free = il->ary[0];
294 il = malloc(sizeof(*il), M_IDR, M_ZERO | M_NOWAIT);
296 bitmap_fill(&il->bitmap, IDR_SIZE);
301 * Could be implemented as get_new_above(idr, ptr, 0, idp) but written
302 * first for simplicity sake.
305 idr_get_new_locked(struct idr *idr, void *ptr, int *idp)
307 struct idr_layer *stack[MAX_LEVEL];
308 struct idr_layer *il;
314 mtx_assert(&idr->lock, MA_OWNED);
318 * Expand the tree until there is free space.
320 if (idr->top == NULL || idr->top->bitmap == 0) {
321 if (idr->layers == MAX_LEVEL + 1) {
328 il->ary[0] = idr->top;
337 * Walk the tree following free bitmaps, record our path.
339 for (layer = idr->layers - 1;; layer--) {
341 idx = ffsl(il->bitmap);
343 panic("idr_get_new: Invalid leaf state (%p, %p)\n",
346 id |= idx << (layer * IDR_BITS);
349 if (il->ary[idx] == NULL) {
350 il->ary[idx] = idr_get(idr);
351 if (il->ary[idx] == NULL)
357 * Allocate the leaf to the consumer.
359 il->bitmap &= ~(1 << idx);
363 * Clear bitmaps potentially up to the root.
365 while (il->bitmap == 0 && ++layer < idr->layers) {
367 il->bitmap &= ~(1 << idr_pos(id, layer));
372 if (error == 0 && idr_find_locked(idr, id) != ptr) {
373 panic("idr_get_new: Failed for idr %p, id %d, ptr %p\n",
381 idr_get_new(struct idr *idr, void *ptr, int *idp)
385 mtx_lock(&idr->lock);
386 retval = idr_get_new_locked(idr, ptr, idp);
387 mtx_unlock(&idr->lock);
392 idr_get_new_above_locked(struct idr *idr, void *ptr, int starting_id, int *idp)
394 struct idr_layer *stack[MAX_LEVEL];
395 struct idr_layer *il;
401 mtx_assert(&idr->lock, MA_OWNED);
405 * Compute the layers required to support starting_id and the mask
411 while (idx & ~IDR_MASK) {
415 if (layer == MAX_LEVEL + 1) {
420 * Expand the tree until there is free space at or beyond starting_id.
422 while (idr->layers <= layer ||
423 idr->top->bitmap < (1 << idr_pos(starting_id, idr->layers - 1))) {
424 if (idr->layers == MAX_LEVEL + 1) {
431 il->ary[0] = idr->top;
432 if (idr->top && idr->top->bitmap == 0)
440 * Walk the tree following free bitmaps, record our path.
442 for (layer = idr->layers - 1;; layer--) {
444 sidx = idr_pos(starting_id, layer);
445 /* Returns index numbered from 0 or size if none exists. */
446 idx = find_next_bit(&il->bitmap, IDR_SIZE, sidx);
447 if (idx == IDR_SIZE && sidx == 0)
448 panic("idr_get_new: Invalid leaf state (%p, %p)\n",
451 * We may have walked a path where there was a free bit but
452 * it was lower than what we wanted. Restart the search with
453 * a larger starting id. id contains the progress we made so
454 * far. Search the leaf one above this level. This may
455 * restart as many as MAX_LEVEL times but that is expected
458 if (idx == IDR_SIZE) {
459 starting_id = id + (1 << ((layer + 1) * IDR_BITS));
463 starting_id = 0; /* Search the whole subtree. */
464 id |= idx << (layer * IDR_BITS);
467 if (il->ary[idx] == NULL) {
468 il->ary[idx] = idr_get(idr);
469 if (il->ary[idx] == NULL)
475 * Allocate the leaf to the consumer.
477 il->bitmap &= ~(1 << idx);
481 * Clear bitmaps potentially up to the root.
483 while (il->bitmap == 0 && ++layer < idr->layers) {
485 il->bitmap &= ~(1 << idr_pos(id, layer));
490 if (error == 0 && idr_find_locked(idr, id) != ptr) {
491 panic("idr_get_new_above: Failed for idr %p, id %d, ptr %p\n",
499 idr_get_new_above(struct idr *idr, void *ptr, int starting_id, int *idp)
503 mtx_lock(&idr->lock);
504 retval = idr_get_new_above_locked(idr, ptr, starting_id, idp);
505 mtx_unlock(&idr->lock);
510 ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
512 return (idr_get_new_above(&ida->idr, NULL, starting_id, p_id));
516 idr_alloc_locked(struct idr *idr, void *ptr, int start, int end)
518 int max = end > 0 ? end - 1 : INT_MAX;
522 mtx_assert(&idr->lock, MA_OWNED);
524 if (unlikely(start < 0))
526 if (unlikely(max < start))
530 error = idr_get_new_locked(idr, ptr, &id);
532 error = idr_get_new_above_locked(idr, ptr, start, &id);
534 if (unlikely(error < 0))
536 if (unlikely(id > max)) {
537 idr_remove_locked(idr, id);
544 idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
548 mtx_lock(&idr->lock);
549 retval = idr_alloc_locked(idr, ptr, start, end);
550 mtx_unlock(&idr->lock);
555 idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
559 mtx_lock(&idr->lock);
560 retval = idr_alloc_locked(idr, ptr, max(start, idr->next_cyclic_id), end);
561 if (unlikely(retval == -ENOSPC))
562 retval = idr_alloc_locked(idr, ptr, start, end);
563 if (likely(retval >= 0))
564 idr->next_cyclic_id = retval + 1;
565 mtx_unlock(&idr->lock);
570 idr_for_each_layer(struct idr_layer *il, int layer,
571 int (*f)(int id, void *p, void *data), void *data)
578 for (i = 0; i < IDR_SIZE; i++) {
579 if (il->ary[i] == NULL)
581 err = f(i, il->ary[i], data);
587 for (i = 0; i < IDR_SIZE; i++) {
588 if (il->ary[i] == NULL)
590 err = idr_for_each_layer(il->ary[i], layer - 1, f, data);
597 /* NOTE: It is not allowed to modify the IDR tree while it is being iterated */
599 idr_for_each(struct idr *idp, int (*f)(int id, void *p, void *data), void *data)
601 return (idr_for_each_layer(idp->top, idp->layers - 1, f, data));
605 ida_pre_get(struct ida *ida, gfp_t flags)
607 if (idr_pre_get(&ida->idr, flags) == 0)
610 if (ida->free_bitmap == NULL) {
612 malloc(sizeof(struct ida_bitmap), M_IDR, flags);
614 return (ida->free_bitmap != NULL);
618 ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
624 MPASS((int)start >= 0);
625 MPASS((int)end >= 0);
634 if (!ida_pre_get(ida, flags))
637 if ((ret = ida_get_new_above(ida, start, &id)) == 0) {
645 if (__predict_false(ret == -EAGAIN))
652 ida_simple_remove(struct ida *ida, unsigned int id)
654 idr_remove(&ida->idr, id);
658 ida_remove(struct ida *ida, int id)
660 idr_remove(&ida->idr, id);
664 ida_init(struct ida *ida)
670 ida_destroy(struct ida *ida)
672 idr_destroy(&ida->idr);
673 free(ida->free_bitmap, M_IDR);