From 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sat, 16 Apr 2005 15:20:36 -0700 Subject: Linux-2.6.12-rc2 Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip! --- lib/idr.c | 408 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 408 insertions(+) create mode 100644 lib/idr.c (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c new file mode 100644 index 0000000..81fc430 --- /dev/null +++ b/lib/idr.c @@ -0,0 +1,408 @@ +/* + * 2002-10-18 written by Jim Houston jim.houston@ccur.com + * Copyright (C) 2002 by Concurrent Computer Corporation + * Distributed under the GNU GPL license version 2. + * + * Modified by George Anzinger to reuse immediately and to use + * find bit instructions. Also removed _irq on spinlocks. + * + * Small id to pointer translation service. + * + * It uses a radix tree like structure as a sparse array indexed + * by the id to obtain the pointer. The bitmap makes allocating + * a new id quick. + * + * You call it to allocate an id (an int) an associate with that id a + * pointer or what ever, we treat it as a (void *). You can pass this + * id to a user for him to pass back at a later time. You then pass + * that id to this code and it returns your pointer. + + * You can release ids at any time. When all ids are released, most of + * the memory is returned (we keep IDR_FREE_MAX) in a local pool so we + * don't need to go to the memory "store" during an id allocate, just + * so you don't need to be too concerned about locking and conflicts + * with the slab allocator. + */ + +#ifndef TEST // to test in user space... +#include +#include +#include +#endif +#include +#include + +static kmem_cache_t *idr_layer_cache; + +static struct idr_layer *alloc_layer(struct idr *idp) +{ + struct idr_layer *p; + + spin_lock(&idp->lock); + if ((p = idp->id_free)) { + idp->id_free = p->ary[0]; + idp->id_free_cnt--; + p->ary[0] = NULL; + } + spin_unlock(&idp->lock); + return(p); +} + +static void free_layer(struct idr *idp, struct idr_layer *p) +{ + /* + * Depends on the return element being zeroed. + */ + spin_lock(&idp->lock); + p->ary[0] = idp->id_free; + idp->id_free = p; + idp->id_free_cnt++; + spin_unlock(&idp->lock); +} + +/** + * idr_pre_get - reserver resources for idr allocation + * @idp: idr handle + * @gfp_mask: memory allocation flags + * + * This function should be called prior to locking and calling the + * following function. It preallocates enough memory to satisfy + * the worst possible allocation. + * + * If the system is REALLY out of memory this function returns 0, + * otherwise 1. + */ +int idr_pre_get(struct idr *idp, unsigned gfp_mask) +{ + while (idp->id_free_cnt < IDR_FREE_MAX) { + struct idr_layer *new; + new = kmem_cache_alloc(idr_layer_cache, gfp_mask); + if(new == NULL) + return (0); + free_layer(idp, new); + } + return 1; +} +EXPORT_SYMBOL(idr_pre_get); + +static int sub_alloc(struct idr *idp, void *ptr, int *starting_id) +{ + int n, m, sh; + struct idr_layer *p, *new; + struct idr_layer *pa[MAX_LEVEL]; + int l, id; + long bm; + + id = *starting_id; + p = idp->top; + l = idp->layers; + pa[l--] = NULL; + while (1) { + /* + * We run around this while until we reach the leaf node... + */ + n = (id >> (IDR_BITS*l)) & IDR_MASK; + bm = ~p->bitmap; + m = find_next_bit(&bm, IDR_SIZE, n); + if (m == IDR_SIZE) { + /* no space available go back to previous layer. */ + l++; + id = (id | ((1 << (IDR_BITS*l))-1)) + 1; + if (!(p = pa[l])) { + *starting_id = id; + return -2; + } + continue; + } + if (m != n) { + sh = IDR_BITS*l; + id = ((id >> sh) ^ n ^ m) << sh; + } + if ((id >= MAX_ID_BIT) || (id < 0)) + return -3; + if (l == 0) + break; + /* + * Create the layer below if it is missing. + */ + if (!p->ary[m]) { + if (!(new = alloc_layer(idp))) + return -1; + p->ary[m] = new; + p->count++; + } + pa[l--] = p; + p = p->ary[m]; + } + /* + * We have reached the leaf node, plant the + * users pointer and return the raw id. + */ + p->ary[m] = (struct idr_layer *)ptr; + __set_bit(m, &p->bitmap); + p->count++; + /* + * If this layer is full mark the bit in the layer above + * to show that this part of the radix tree is full. + * This may complete the layer above and require walking + * up the radix tree. + */ + n = id; + while (p->bitmap == IDR_FULL) { + if (!(p = pa[++l])) + break; + n = n >> IDR_BITS; + __set_bit((n & IDR_MASK), &p->bitmap); + } + return(id); +} + +static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id) +{ + struct idr_layer *p, *new; + int layers, v, id; + + id = starting_id; +build_up: + p = idp->top; + layers = idp->layers; + if (unlikely(!p)) { + if (!(p = alloc_layer(idp))) + return -1; + layers = 1; + } + /* + * Add a new layer to the top of the tree if the requested + * id is larger than the currently allocated space. + */ + while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) { + layers++; + if (!p->count) + continue; + if (!(new = alloc_layer(idp))) { + /* + * The allocation failed. If we built part of + * the structure tear it down. + */ + for (new = p; p && p != idp->top; new = p) { + p = p->ary[0]; + new->ary[0] = NULL; + new->bitmap = new->count = 0; + free_layer(idp, new); + } + return -1; + } + new->ary[0] = p; + new->count = 1; + if (p->bitmap == IDR_FULL) + __set_bit(0, &new->bitmap); + p = new; + } + idp->top = p; + idp->layers = layers; + v = sub_alloc(idp, ptr, &id); + if (v == -2) + goto build_up; + return(v); +} + +/** + * idr_get_new_above - allocate new idr entry above a start id + * @idp: idr handle + * @ptr: pointer you want associated with the ide + * @start_id: id to start search at + * @id: pointer to the allocated handle + * + * This is the allocate id function. It should be called with any + * required locks. + * + * If memory is required, it will return -EAGAIN, you should unlock + * and go back to the idr_pre_get() call. If the idr is full, it will + * return -ENOSPC. + * + * @id returns a value in the range 0 ... 0x7fffffff + */ +int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id) +{ + int rv; + rv = idr_get_new_above_int(idp, ptr, starting_id); + /* + * This is a cheap hack until the IDR code can be fixed to + * return proper error values. + */ + if (rv < 0) { + if (rv == -1) + return -EAGAIN; + else /* Will be -3 */ + return -ENOSPC; + } + *id = rv; + return 0; +} +EXPORT_SYMBOL(idr_get_new_above); + +/** + * idr_get_new - allocate new idr entry + * @idp: idr handle + * @ptr: pointer you want associated with the ide + * @id: pointer to the allocated handle + * + * This is the allocate id function. It should be called with any + * required locks. + * + * If memory is required, it will return -EAGAIN, you should unlock + * and go back to the idr_pre_get() call. If the idr is full, it will + * return -ENOSPC. + * + * @id returns a value in the range 0 ... 0x7fffffff + */ +int idr_get_new(struct idr *idp, void *ptr, int *id) +{ + int rv; + rv = idr_get_new_above_int(idp, ptr, 0); + /* + * This is a cheap hack until the IDR code can be fixed to + * return proper error values. + */ + if (rv < 0) { + if (rv == -1) + return -EAGAIN; + else /* Will be -3 */ + return -ENOSPC; + } + *id = rv; + return 0; +} +EXPORT_SYMBOL(idr_get_new); + +static void idr_remove_warning(int id) +{ + printk("idr_remove called for id=%d which is not allocated.\n", id); + dump_stack(); +} + +static void sub_remove(struct idr *idp, int shift, int id) +{ + struct idr_layer *p = idp->top; + struct idr_layer **pa[MAX_LEVEL]; + struct idr_layer ***paa = &pa[0]; + int n; + + *paa = NULL; + *++paa = &idp->top; + + while ((shift > 0) && p) { + n = (id >> shift) & IDR_MASK; + __clear_bit(n, &p->bitmap); + *++paa = &p->ary[n]; + p = p->ary[n]; + shift -= IDR_BITS; + } + n = id & IDR_MASK; + if (likely(p != NULL && test_bit(n, &p->bitmap))){ + __clear_bit(n, &p->bitmap); + p->ary[n] = NULL; + while(*paa && ! --((**paa)->count)){ + free_layer(idp, **paa); + **paa-- = NULL; + } + if ( ! *paa ) + idp->layers = 0; + } else { + idr_remove_warning(id); + } +} + +/** + * idr_remove - remove the given id and free it's slot + * idp: idr handle + * id: uniqueue key + */ +void idr_remove(struct idr *idp, int id) +{ + struct idr_layer *p; + + /* Mask off upper bits we don't use for the search. */ + id &= MAX_ID_MASK; + + sub_remove(idp, (idp->layers - 1) * IDR_BITS, id); + if ( idp->top && idp->top->count == 1 && + (idp->layers > 1) && + idp->top->ary[0]){ // We can drop a layer + + p = idp->top->ary[0]; + idp->top->bitmap = idp->top->count = 0; + free_layer(idp, idp->top); + idp->top = p; + --idp->layers; + } + while (idp->id_free_cnt >= IDR_FREE_MAX) { + + p = alloc_layer(idp); + kmem_cache_free(idr_layer_cache, p); + return; + } +} +EXPORT_SYMBOL(idr_remove); + +/** + * idr_find - return pointer for given id + * @idp: idr handle + * @id: lookup key + * + * Return the pointer given the id it has been registered with. A %NULL + * return indicates that @id is not valid or you passed %NULL in + * idr_get_new(). + * + * The caller must serialize idr_find() vs idr_get_new() and idr_remove(). + */ +void *idr_find(struct idr *idp, int id) +{ + int n; + struct idr_layer *p; + + n = idp->layers * IDR_BITS; + p = idp->top; + + /* Mask off upper bits we don't use for the search. */ + id &= MAX_ID_MASK; + + if (id >= (1 << n)) + return NULL; + + while (n > 0 && p) { + n -= IDR_BITS; + p = p->ary[(id >> n) & IDR_MASK]; + } + return((void *)p); +} +EXPORT_SYMBOL(idr_find); + +static void idr_cache_ctor(void * idr_layer, + kmem_cache_t *idr_layer_cache, unsigned long flags) +{ + memset(idr_layer, 0, sizeof(struct idr_layer)); +} + +static int init_id_cache(void) +{ + if (!idr_layer_cache) + idr_layer_cache = kmem_cache_create("idr_layer_cache", + sizeof(struct idr_layer), 0, 0, idr_cache_ctor, NULL); + return 0; +} + +/** + * idr_init - initialize idr handle + * @idp: idr handle + * + * This function is use to set up the handle (@idp) that you will pass + * to the rest of the functions. + */ +void idr_init(struct idr *idp) +{ + init_id_cache(); + memset(idp, 0, sizeof(struct idr)); + spin_lock_init(&idp->lock); +} +EXPORT_SYMBOL(idr_init); -- cgit v1.1