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