2 * 2002-10-18 written by Jim Houston jim.houston@ccur.com
3 * Copyright (C) 2002 by Concurrent Computer Corporation
4 * Distributed under the GNU GPL license version 2.
6 * Modified by George Anzinger to reuse immediately and to use
7 * find bit instructions. Also removed _irq on spinlocks.
9 * Small id to pointer translation service.
11 * It uses a radix tree like structure as a sparse array indexed
12 * by the id to obtain the pointer. The bitmap makes allocating
15 * You call it to allocate an id (an int) an associate with that id a
16 * pointer or what ever, we treat it as a (void *). You can pass this
17 * id to a user for him to pass back at a later time. You then pass
18 * that id to this code and it returns your pointer.
20 * You can release ids at any time. When all ids are released, most of
21 * the memory is returned (we keep IDR_FREE_MAX) in a local pool so we
22 * don't need to go to the memory "store" during an id allocate, just
23 * so you don't need to be too concerned about locking and conflicts
24 * with the slab allocator.
27 #ifndef TEST // to test in user space...
28 #include <linux/slab.h>
29 #include <linux/init.h>
30 #include <linux/module.h>
32 #include <linux/err.h>
33 #include <linux/string.h>
34 #include <linux/idr.h>
36 static struct kmem_cache
*idr_layer_cache
;
38 static struct idr_layer
*alloc_layer(struct idr
*idp
)
43 spin_lock_irqsave(&idp
->lock
, flags
);
44 if ((p
= idp
->id_free
)) {
45 idp
->id_free
= p
->ary
[0];
49 spin_unlock_irqrestore(&idp
->lock
, flags
);
53 /* only called when idp->lock is held */
54 static void __free_layer(struct idr
*idp
, struct idr_layer
*p
)
56 p
->ary
[0] = idp
->id_free
;
61 static void free_layer(struct idr
*idp
, struct idr_layer
*p
)
66 * Depends on the return element being zeroed.
68 spin_lock_irqsave(&idp
->lock
, flags
);
70 spin_unlock_irqrestore(&idp
->lock
, flags
);
73 static void idr_mark_full(struct idr_layer
**pa
, int id
)
75 struct idr_layer
*p
= pa
[0];
78 __set_bit(id
& IDR_MASK
, &p
->bitmap
);
80 * If this layer is full mark the bit in the layer above to
81 * show that this part of the radix tree is full. This may
82 * complete the layer above and require walking up the radix
85 while (p
->bitmap
== IDR_FULL
) {
89 __set_bit((id
& IDR_MASK
), &p
->bitmap
);
94 * idr_pre_get - reserver resources for idr allocation
96 * @gfp_mask: memory allocation flags
98 * This function should be called prior to locking and calling the
99 * following function. It preallocates enough memory to satisfy
100 * the worst possible allocation.
102 * If the system is REALLY out of memory this function returns 0,
105 int idr_pre_get(struct idr
*idp
, gfp_t gfp_mask
)
107 while (idp
->id_free_cnt
< IDR_FREE_MAX
) {
108 struct idr_layer
*new;
109 new = kmem_cache_alloc(idr_layer_cache
, gfp_mask
);
112 free_layer(idp
, new);
116 EXPORT_SYMBOL(idr_pre_get
);
118 static int sub_alloc(struct idr
*idp
, int *starting_id
, struct idr_layer
**pa
)
121 struct idr_layer
*p
, *new;
132 * We run around this while until we reach the leaf node...
134 n
= (id
>> (IDR_BITS
*l
)) & IDR_MASK
;
136 m
= find_next_bit(&bm
, IDR_SIZE
, n
);
138 /* no space available go back to previous layer. */
141 id
= (id
| ((1 << (IDR_BITS
* l
)) - 1)) + 1;
143 /* if already at the top layer, we need to grow */
149 /* If we need to go up one layer, continue the
150 * loop; otherwise, restart from the top.
152 sh
= IDR_BITS
* (l
+ 1);
153 if (oid
>> sh
== id
>> sh
)
160 id
= ((id
>> sh
) ^ n
^ m
) << sh
;
162 if ((id
>= MAX_ID_BIT
) || (id
< 0))
167 * Create the layer below if it is missing.
170 if (!(new = alloc_layer(idp
)))
183 static int idr_get_empty_slot(struct idr
*idp
, int starting_id
,
184 struct idr_layer
**pa
)
186 struct idr_layer
*p
, *new;
193 layers
= idp
->layers
;
195 if (!(p
= alloc_layer(idp
)))
200 * Add a new layer to the top of the tree if the requested
201 * id is larger than the currently allocated space.
203 while ((layers
< (MAX_LEVEL
- 1)) && (id
>= (1 << (layers
*IDR_BITS
)))) {
207 if (!(new = alloc_layer(idp
))) {
209 * The allocation failed. If we built part of
210 * the structure tear it down.
212 spin_lock_irqsave(&idp
->lock
, flags
);
213 for (new = p
; p
&& p
!= idp
->top
; new = p
) {
216 new->bitmap
= new->count
= 0;
217 __free_layer(idp
, new);
219 spin_unlock_irqrestore(&idp
->lock
, flags
);
224 if (p
->bitmap
== IDR_FULL
)
225 __set_bit(0, &new->bitmap
);
229 idp
->layers
= layers
;
230 v
= sub_alloc(idp
, &id
, pa
);
236 static int idr_get_new_above_int(struct idr
*idp
, void *ptr
, int starting_id
)
238 struct idr_layer
*pa
[MAX_LEVEL
];
241 id
= idr_get_empty_slot(idp
, starting_id
, pa
);
244 * Successfully found an empty slot. Install the user
245 * pointer and mark the slot full.
247 pa
[0]->ary
[id
& IDR_MASK
] = (struct idr_layer
*)ptr
;
249 idr_mark_full(pa
, id
);
256 * idr_get_new_above - allocate new idr entry above or equal to a start id
258 * @ptr: pointer you want associated with the ide
259 * @start_id: id to start search at
260 * @id: pointer to the allocated handle
262 * This is the allocate id function. It should be called with any
265 * If memory is required, it will return -EAGAIN, you should unlock
266 * and go back to the idr_pre_get() call. If the idr is full, it will
269 * @id returns a value in the range 0 ... 0x7fffffff
271 int idr_get_new_above(struct idr
*idp
, void *ptr
, int starting_id
, int *id
)
275 rv
= idr_get_new_above_int(idp
, ptr
, starting_id
);
277 * This is a cheap hack until the IDR code can be fixed to
278 * return proper error values.
283 else /* Will be -3 */
289 EXPORT_SYMBOL(idr_get_new_above
);
292 * idr_get_new - allocate new idr entry
294 * @ptr: pointer you want associated with the ide
295 * @id: pointer to the allocated handle
297 * This is the allocate id function. It should be called with any
300 * If memory is required, it will return -EAGAIN, you should unlock
301 * and go back to the idr_pre_get() call. If the idr is full, it will
304 * @id returns a value in the range 0 ... 0x7fffffff
306 int idr_get_new(struct idr
*idp
, void *ptr
, int *id
)
310 rv
= idr_get_new_above_int(idp
, ptr
, 0);
312 * This is a cheap hack until the IDR code can be fixed to
313 * return proper error values.
318 else /* Will be -3 */
324 EXPORT_SYMBOL(idr_get_new
);
326 static void idr_remove_warning(int id
)
328 printk("idr_remove called for id=%d which is not allocated.\n", id
);
332 static void sub_remove(struct idr
*idp
, int shift
, int id
)
334 struct idr_layer
*p
= idp
->top
;
335 struct idr_layer
**pa
[MAX_LEVEL
];
336 struct idr_layer
***paa
= &pa
[0];
342 while ((shift
> 0) && p
) {
343 n
= (id
>> shift
) & IDR_MASK
;
344 __clear_bit(n
, &p
->bitmap
);
350 if (likely(p
!= NULL
&& test_bit(n
, &p
->bitmap
))){
351 __clear_bit(n
, &p
->bitmap
);
353 while(*paa
&& ! --((**paa
)->count
)){
354 free_layer(idp
, **paa
);
360 idr_remove_warning(id
);
364 * idr_remove - remove the given id and free it's slot
368 void idr_remove(struct idr
*idp
, int id
)
372 /* Mask off upper bits we don't use for the search. */
375 sub_remove(idp
, (idp
->layers
- 1) * IDR_BITS
, id
);
376 if (idp
->top
&& idp
->top
->count
== 1 && (idp
->layers
> 1) &&
377 idp
->top
->ary
[0]) { // We can drop a layer
379 p
= idp
->top
->ary
[0];
380 idp
->top
->bitmap
= idp
->top
->count
= 0;
381 free_layer(idp
, idp
->top
);
385 while (idp
->id_free_cnt
>= IDR_FREE_MAX
) {
386 p
= alloc_layer(idp
);
387 kmem_cache_free(idr_layer_cache
, p
);
391 EXPORT_SYMBOL(idr_remove
);
394 * idr_destroy - release all cached layers within an idr tree
397 void idr_destroy(struct idr
*idp
)
399 while (idp
->id_free_cnt
) {
400 struct idr_layer
*p
= alloc_layer(idp
);
401 kmem_cache_free(idr_layer_cache
, p
);
404 EXPORT_SYMBOL(idr_destroy
);
407 * idr_find - return pointer for given id
411 * Return the pointer given the id it has been registered with. A %NULL
412 * return indicates that @id is not valid or you passed %NULL in
415 * The caller must serialize idr_find() vs idr_get_new() and idr_remove().
417 void *idr_find(struct idr
*idp
, int id
)
422 n
= idp
->layers
* IDR_BITS
;
425 /* Mask off upper bits we don't use for the search. */
433 p
= p
->ary
[(id
>> n
) & IDR_MASK
];
437 EXPORT_SYMBOL(idr_find
);
440 * idr_replace - replace pointer for given id
442 * @ptr: pointer you want associated with the id
445 * Replace the pointer registered with an id and return the old value.
446 * A -ENOENT return indicates that @id was not found.
447 * A -EINVAL return indicates that @id was not within valid constraints.
449 * The caller must serialize vs idr_find(), idr_get_new(), and idr_remove().
451 void *idr_replace(struct idr
*idp
, void *ptr
, int id
)
454 struct idr_layer
*p
, *old_p
;
456 n
= idp
->layers
* IDR_BITS
;
462 return ERR_PTR(-EINVAL
);
465 while ((n
> 0) && p
) {
466 p
= p
->ary
[(id
>> n
) & IDR_MASK
];
471 if (unlikely(p
== NULL
|| !test_bit(n
, &p
->bitmap
)))
472 return ERR_PTR(-ENOENT
);
479 EXPORT_SYMBOL(idr_replace
);
481 static void idr_cache_ctor(void * idr_layer
, struct kmem_cache
*idr_layer_cache
,
484 memset(idr_layer
, 0, sizeof(struct idr_layer
));
487 static int init_id_cache(void)
489 if (!idr_layer_cache
)
490 idr_layer_cache
= kmem_cache_create("idr_layer_cache",
491 sizeof(struct idr_layer
), 0, 0, idr_cache_ctor
, NULL
);
496 * idr_init - initialize idr handle
499 * This function is use to set up the handle (@idp) that you will pass
500 * to the rest of the functions.
502 void idr_init(struct idr
*idp
)
505 memset(idp
, 0, sizeof(struct idr
));
506 spin_lock_init(&idp
->lock
);
508 EXPORT_SYMBOL(idr_init
);
512 * IDA - IDR based ID allocator
514 * this is id allocator without id -> pointer translation. Memory
515 * usage is much lower than full blown idr because each id only
516 * occupies a bit. ida uses a custom leaf node which contains
517 * IDA_BITMAP_BITS slots.
519 * 2007-04-25 written by Tejun Heo <htejun@gmail.com>
522 static void free_bitmap(struct ida
*ida
, struct ida_bitmap
*bitmap
)
526 if (!ida
->free_bitmap
) {
527 spin_lock_irqsave(&ida
->idr
.lock
, flags
);
528 if (!ida
->free_bitmap
) {
529 ida
->free_bitmap
= bitmap
;
532 spin_unlock_irqrestore(&ida
->idr
.lock
, flags
);
539 * ida_pre_get - reserve resources for ida allocation
541 * @gfp_mask: memory allocation flag
543 * This function should be called prior to locking and calling the
544 * following function. It preallocates enough memory to satisfy the
545 * worst possible allocation.
547 * If the system is REALLY out of memory this function returns 0,
550 int ida_pre_get(struct ida
*ida
, gfp_t gfp_mask
)
552 /* allocate idr_layers */
553 if (!idr_pre_get(&ida
->idr
, gfp_mask
))
556 /* allocate free_bitmap */
557 if (!ida
->free_bitmap
) {
558 struct ida_bitmap
*bitmap
;
560 bitmap
= kmalloc(sizeof(struct ida_bitmap
), gfp_mask
);
564 free_bitmap(ida
, bitmap
);
569 EXPORT_SYMBOL(ida_pre_get
);
572 * ida_get_new_above - allocate new ID above or equal to a start id
574 * @staring_id: id to start search at
575 * @p_id: pointer to the allocated handle
577 * Allocate new ID above or equal to @ida. It should be called with
578 * any required locks.
580 * If memory is required, it will return -EAGAIN, you should unlock
581 * and go back to the ida_pre_get() call. If the ida is full, it will
584 * @p_id returns a value in the range 0 ... 0x7fffffff.
586 int ida_get_new_above(struct ida
*ida
, int starting_id
, int *p_id
)
588 struct idr_layer
*pa
[MAX_LEVEL
];
589 struct ida_bitmap
*bitmap
;
591 int idr_id
= starting_id
/ IDA_BITMAP_BITS
;
592 int offset
= starting_id
% IDA_BITMAP_BITS
;
596 /* get vacant slot */
597 t
= idr_get_empty_slot(&ida
->idr
, idr_id
, pa
);
601 else /* will be -3 */
605 if (t
* IDA_BITMAP_BITS
>= MAX_ID_BIT
)
612 /* if bitmap isn't there, create a new one */
613 bitmap
= (void *)pa
[0]->ary
[idr_id
& IDR_MASK
];
615 spin_lock_irqsave(&ida
->idr
.lock
, flags
);
616 bitmap
= ida
->free_bitmap
;
617 ida
->free_bitmap
= NULL
;
618 spin_unlock_irqrestore(&ida
->idr
.lock
, flags
);
623 memset(bitmap
, 0, sizeof(struct ida_bitmap
));
624 pa
[0]->ary
[idr_id
& IDR_MASK
] = (void *)bitmap
;
628 /* lookup for empty slot */
629 t
= find_next_zero_bit(bitmap
->bitmap
, IDA_BITMAP_BITS
, offset
);
630 if (t
== IDA_BITMAP_BITS
) {
631 /* no empty slot after offset, continue to the next chunk */
637 id
= idr_id
* IDA_BITMAP_BITS
+ t
;
638 if (id
>= MAX_ID_BIT
)
641 __set_bit(t
, bitmap
->bitmap
);
642 if (++bitmap
->nr_busy
== IDA_BITMAP_BITS
)
643 idr_mark_full(pa
, idr_id
);
647 /* Each leaf node can handle nearly a thousand slots and the
648 * whole idea of ida is to have small memory foot print.
649 * Throw away extra resources one by one after each successful
652 if (ida
->idr
.id_free_cnt
|| ida
->free_bitmap
) {
653 struct idr_layer
*p
= alloc_layer(&ida
->idr
);
655 kmem_cache_free(idr_layer_cache
, p
);
660 EXPORT_SYMBOL(ida_get_new_above
);
663 * ida_get_new - allocate new ID
665 * @p_id: pointer to the allocated handle
667 * Allocate new ID. It should be called with any required locks.
669 * If memory is required, it will return -EAGAIN, you should unlock
670 * and go back to the idr_pre_get() call. If the idr is full, it will
673 * @id returns a value in the range 0 ... 0x7fffffff.
675 int ida_get_new(struct ida
*ida
, int *p_id
)
677 return ida_get_new_above(ida
, 0, p_id
);
679 EXPORT_SYMBOL(ida_get_new
);
682 * ida_remove - remove the given ID
686 void ida_remove(struct ida
*ida
, int id
)
688 struct idr_layer
*p
= ida
->idr
.top
;
689 int shift
= (ida
->idr
.layers
- 1) * IDR_BITS
;
690 int idr_id
= id
/ IDA_BITMAP_BITS
;
691 int offset
= id
% IDA_BITMAP_BITS
;
693 struct ida_bitmap
*bitmap
;
695 /* clear full bits while looking up the leaf idr_layer */
696 while ((shift
> 0) && p
) {
697 n
= (idr_id
>> shift
) & IDR_MASK
;
698 __clear_bit(n
, &p
->bitmap
);
706 n
= idr_id
& IDR_MASK
;
707 __clear_bit(n
, &p
->bitmap
);
709 bitmap
= (void *)p
->ary
[n
];
710 if (!test_bit(offset
, bitmap
->bitmap
))
713 /* update bitmap and remove it if empty */
714 __clear_bit(offset
, bitmap
->bitmap
);
715 if (--bitmap
->nr_busy
== 0) {
716 __set_bit(n
, &p
->bitmap
); /* to please idr_remove() */
717 idr_remove(&ida
->idr
, idr_id
);
718 free_bitmap(ida
, bitmap
);
725 "ida_remove called for id=%d which is not allocated.\n", id
);
727 EXPORT_SYMBOL(ida_remove
);
730 * ida_destroy - release all cached layers within an ida tree
733 void ida_destroy(struct ida
*ida
)
735 idr_destroy(&ida
->idr
);
736 kfree(ida
->free_bitmap
);
738 EXPORT_SYMBOL(ida_destroy
);
741 * ida_init - initialize ida handle
744 * This function is use to set up the handle (@ida) that you will pass
745 * to the rest of the functions.
747 void ida_init(struct ida
*ida
)
749 memset(ida
, 0, sizeof(struct ida
));
753 EXPORT_SYMBOL(ida_init
);
This page took 0.04498 seconds and 5 git commands to generate.