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);
74 * idr_pre_get - reserver resources for idr allocation
76 * @gfp_mask: memory allocation flags
78 * This function should be called prior to locking and calling the
79 * following function. It preallocates enough memory to satisfy
80 * the worst possible allocation.
82 * If the system is REALLY out of memory this function returns 0,
85 int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
87 while (idp->id_free_cnt < IDR_FREE_MAX) {
88 struct idr_layer *new;
89 new = kmem_cache_alloc(idr_layer_cache, gfp_mask);
96 EXPORT_SYMBOL(idr_pre_get);
98 static int sub_alloc(struct idr *idp, void *ptr, int *starting_id)
101 struct idr_layer *p, *new;
102 struct idr_layer *pa[MAX_LEVEL];
113 * We run around this while until we reach the leaf node...
115 n = (id >> (IDR_BITS*l)) & IDR_MASK;
117 m = find_next_bit(&bm, IDR_SIZE, n);
119 /* no space available go back to previous layer. */
122 id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
124 /* if already at the top layer, we need to grow */
130 /* If we need to go up one layer, continue the
131 * loop; otherwise, restart from the top.
133 sh = IDR_BITS * (l + 1);
134 if (oid >> sh == id >> sh)
141 id = ((id >> sh) ^ n ^ m) << sh;
143 if ((id >= MAX_ID_BIT) || (id < 0))
148 * Create the layer below if it is missing.
151 if (!(new = alloc_layer(idp)))
160 * We have reached the leaf node, plant the
161 * users pointer and return the raw id.
163 p->ary[m] = (struct idr_layer *)ptr;
164 __set_bit(m, &p->bitmap);
167 * If this layer is full mark the bit in the layer above
168 * to show that this part of the radix tree is full.
169 * This may complete the layer above and require walking
173 while (p->bitmap == IDR_FULL) {
177 __set_bit((n & IDR_MASK), &p->bitmap);
182 static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
184 struct idr_layer *p, *new;
191 layers = idp->layers;
193 if (!(p = alloc_layer(idp)))
198 * Add a new layer to the top of the tree if the requested
199 * id is larger than the currently allocated space.
201 while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
205 if (!(new = alloc_layer(idp))) {
207 * The allocation failed. If we built part of
208 * the structure tear it down.
210 spin_lock_irqsave(&idp->lock, flags);
211 for (new = p; p && p != idp->top; new = p) {
214 new->bitmap = new->count = 0;
215 __free_layer(idp, new);
217 spin_unlock_irqrestore(&idp->lock, flags);
222 if (p->bitmap == IDR_FULL)
223 __set_bit(0, &new->bitmap);
227 idp->layers = layers;
228 v = sub_alloc(idp, ptr, &id);
235 * idr_get_new_above - allocate new idr entry above or equal to a start id
237 * @ptr: pointer you want associated with the ide
238 * @start_id: id to start search at
239 * @id: pointer to the allocated handle
241 * This is the allocate id function. It should be called with any
244 * If memory is required, it will return -EAGAIN, you should unlock
245 * and go back to the idr_pre_get() call. If the idr is full, it will
248 * @id returns a value in the range 0 ... 0x7fffffff
250 int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)
254 rv = idr_get_new_above_int(idp, ptr, starting_id);
256 * This is a cheap hack until the IDR code can be fixed to
257 * return proper error values.
262 else /* Will be -3 */
268 EXPORT_SYMBOL(idr_get_new_above);
271 * idr_get_new - allocate new idr entry
273 * @ptr: pointer you want associated with the ide
274 * @id: pointer to the allocated handle
276 * This is the allocate id function. It should be called with any
279 * If memory is required, it will return -EAGAIN, you should unlock
280 * and go back to the idr_pre_get() call. If the idr is full, it will
283 * @id returns a value in the range 0 ... 0x7fffffff
285 int idr_get_new(struct idr *idp, void *ptr, int *id)
289 rv = idr_get_new_above_int(idp, ptr, 0);
291 * This is a cheap hack until the IDR code can be fixed to
292 * return proper error values.
297 else /* Will be -3 */
303 EXPORT_SYMBOL(idr_get_new);
305 static void idr_remove_warning(int id)
307 printk("idr_remove called for id=%d which is not allocated.\n", id);
311 static void sub_remove(struct idr *idp, int shift, int id)
313 struct idr_layer *p = idp->top;
314 struct idr_layer **pa[MAX_LEVEL];
315 struct idr_layer ***paa = &pa[0];
321 while ((shift > 0) && p) {
322 n = (id >> shift) & IDR_MASK;
323 __clear_bit(n, &p->bitmap);
329 if (likely(p != NULL && test_bit(n, &p->bitmap))){
330 __clear_bit(n, &p->bitmap);
332 while(*paa && ! --((**paa)->count)){
333 free_layer(idp, **paa);
339 idr_remove_warning(id);
343 * idr_remove - remove the given id and free it's slot
347 void idr_remove(struct idr *idp, int id)
351 /* Mask off upper bits we don't use for the search. */
354 sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
355 if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
356 idp->top->ary[0]) { // We can drop a layer
358 p = idp->top->ary[0];
359 idp->top->bitmap = idp->top->count = 0;
360 free_layer(idp, idp->top);
364 while (idp->id_free_cnt >= IDR_FREE_MAX) {
365 p = alloc_layer(idp);
366 kmem_cache_free(idr_layer_cache, p);
370 EXPORT_SYMBOL(idr_remove);
373 * idr_destroy - release all cached layers within an idr tree
376 void idr_destroy(struct idr *idp)
378 while (idp->id_free_cnt) {
379 struct idr_layer *p = alloc_layer(idp);
380 kmem_cache_free(idr_layer_cache, p);
383 EXPORT_SYMBOL(idr_destroy);
386 * idr_find - return pointer for given id
390 * Return the pointer given the id it has been registered with. A %NULL
391 * return indicates that @id is not valid or you passed %NULL in
394 * The caller must serialize idr_find() vs idr_get_new() and idr_remove().
396 void *idr_find(struct idr *idp, int id)
401 n = idp->layers * IDR_BITS;
404 /* Mask off upper bits we don't use for the search. */
412 p = p->ary[(id >> n) & IDR_MASK];
416 EXPORT_SYMBOL(idr_find);
419 * idr_replace - replace pointer for given id
421 * @ptr: pointer you want associated with the id
424 * Replace the pointer registered with an id and return the old value.
425 * A -ENOENT return indicates that @id was not found.
426 * A -EINVAL return indicates that @id was not within valid constraints.
428 * The caller must serialize vs idr_find(), idr_get_new(), and idr_remove().
430 void *idr_replace(struct idr *idp, void *ptr, int id)
433 struct idr_layer *p, *old_p;
435 n = idp->layers * IDR_BITS;
441 return ERR_PTR(-EINVAL);
444 while ((n > 0) && p) {
445 p = p->ary[(id >> n) & IDR_MASK];
450 if (unlikely(p == NULL || !test_bit(n, &p->bitmap)))
451 return ERR_PTR(-ENOENT);
458 EXPORT_SYMBOL(idr_replace);
460 static void idr_cache_ctor(void * idr_layer, struct kmem_cache *idr_layer_cache,
463 memset(idr_layer, 0, sizeof(struct idr_layer));
466 static int init_id_cache(void)
468 if (!idr_layer_cache)
469 idr_layer_cache = kmem_cache_create("idr_layer_cache",
470 sizeof(struct idr_layer), 0, 0, idr_cache_ctor, NULL);
475 * idr_init - initialize idr handle
478 * This function is use to set up the handle (@idp) that you will pass
479 * to the rest of the functions.
481 void idr_init(struct idr *idp)
484 memset(idp, 0, sizeof(struct idr));
485 spin_lock_init(&idp->lock);
487 EXPORT_SYMBOL(idr_init);