WebSVN – Kolibri OS – Diff – /drivers/ddk/linux/idr.c


/*
 * 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.
 *
 * Modified by Nadia Derbey to make it RCU safe.
 *
 * 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.
 */
 
#include 
#include 
#include 
#include 
//#include 
 
unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
{
    const unsigned long *p = addr;
    unsigned long result = 0;
    unsigned long tmp;
 
    while (size & ~(BITS_PER_LONG-1)) {
        if ((tmp = *(p++)))
            goto found;
        result += BITS_PER_LONG;
        size -= BITS_PER_LONG;
    }
    if (!size)
        return result;
 
    tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
    if (tmp == 0UL)     /* Are any bits set? */
        return result + size;   /* Nope. */
found:
    return result + __ffs(tmp);
}
 
int find_next_bit(const unsigned long *addr, int size, int offset)
{
    const unsigned long *p = addr + (offset >> 5);
    int set = 0, bit = offset & 31, res;
 
    if (bit)
    {
        /*
         * Look for nonzero in the first 32 bits:
         */
        __asm__("bsfl %1,%0\n\t"
                "jne 1f\n\t"
                "movl $32, %0\n"
                "1:"
                : "=r" (set)
                : "r" (*p >> bit));
        if (set < (32 - bit))
                return set + offset;
        set = 32 - bit;
        p++;
    }
    /*
     * No set bit yet, search remaining full words for a bit
     */
    res = find_first_bit (p, size - 32 * (p - addr));
    return (offset + set + res);
}
 
#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
 
#define rcu_dereference(p)     ({ \
                                typeof(p) _________p1 = ACCESS_ONCE(p); \
                                (_________p1); \
                                })
 
#define rcu_assign_pointer(p, v) \
        ({ \
                if (!__builtin_constant_p(v) || \
                    ((v) != NULL)) \
                (p) = (v); \
        })
 
//static struct kmem_cache *idr_layer_cache;
 
 
 
 
 
static struct idr_layer *get_from_free_list(struct idr *idp)
{
	struct idr_layer *p;
	unsigned long flags;
 
//   spin_lock_irqsave(&idp->lock, flags);
	if ((p = idp->id_free)) {
		idp->id_free = p->ary[0];
		idp->id_free_cnt--;
		p->ary[0] = NULL;
	}
//   spin_unlock_irqrestore(&idp->lock, flags);
	return(p);
}
 
 
static void idr_layer_rcu_free(struct rcu_head *head)
{
	struct idr_layer *layer;
 
    layer = container_of(head, struct idr_layer, rcu_head);
    kfree(layer);
}
 
 
 
static inline void free_layer(struct idr_layer *p)
{
    kfree(p);
}
 
 
/* only called when idp->lock is held */
static void __move_to_free_list(struct idr *idp, struct idr_layer *p)
{
	p->ary[0] = idp->id_free;
	idp->id_free = p;
	idp->id_free_cnt++;
}
 
static void move_to_free_list(struct idr *idp, struct idr_layer *p)
{
	unsigned long flags;
 
	/*
	 * Depends on the return element being zeroed.
	 */
//   spin_lock_irqsave(&idp->lock, flags);
	__move_to_free_list(idp, p);
//   spin_unlock_irqrestore(&idp->lock, flags);
}
 
static void idr_mark_full(struct idr_layer **pa, int id)
{
	struct idr_layer *p = pa[0];
	int l = 0;
 
	__set_bit(id & IDR_MASK, &p->bitmap);
	/*
	 * 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.
	 */
	while (p->bitmap == IDR_FULL) {
		if (!(p = pa[++l]))
			break;
		id = id >> IDR_BITS;
		__set_bit((id & IDR_MASK), &p->bitmap);
	}
}
 
 
 
/**
 * idr_pre_get - reserve resources for idr allocation
 * @idp:	idr handle
 * @gfp_mask:	memory allocation flags
 *
 * This function should be called prior to calling the idr_get_new* functions.
 * It preallocates enough memory to satisfy the worst possible allocation. The
 * caller should pass in GFP_KERNEL if possible.  This of course requires that
 * no spinning locks be held.
 *
 * If the system is REALLY out of memory this function returns %0,
 * otherwise %1.
 */
int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
{
   while (idp->id_free_cnt < IDR_FREE_MAX) {
       struct idr_layer *new;
       new = kzalloc(sizeof(struct idr_layer), gfp_mask);
       if (new == NULL)
           return (0);
       move_to_free_list(idp, new);
   }
   return 1;
}
 
static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa)
{
	int n, m, sh;
	struct idr_layer *p, *new;
	int l, id, oid;
	unsigned long bm;
 
	id = *starting_id;
 restart:
	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++;
			oid = id;
			id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
 
			/* if already at the top layer, we need to grow */
			if (!(p = pa[l])) {
				*starting_id = id;
				return IDR_NEED_TO_GROW;
			}
 
			/* If we need to go up one layer, continue the
			 * loop; otherwise, restart from the top.
			 */
			sh = IDR_BITS * (l + 1);
			if (oid >> sh == id >> sh)
				continue;
			else
				goto restart;
		}
		if (m != n) {
			sh = IDR_BITS*l;
			id = ((id >> sh) ^ n ^ m) << sh;
		}
		if ((id >= MAX_ID_BIT) || (id < 0))
			return IDR_NOMORE_SPACE;
		if (l == 0)
			break;
		/*
		 * Create the layer below if it is missing.
		 */
		if (!p->ary[m]) {
			new = get_from_free_list(idp);
			if (!new)
				return -1;
			new->layer = l-1;
			rcu_assign_pointer(p->ary[m], new);
			p->count++;
		}
		pa[l--] = p;
		p = p->ary[m];
	}
 
	pa[l] = p;
	return id;
}
 
 
static int idr_get_empty_slot(struct idr *idp, int starting_id,
			      struct idr_layer **pa)
{
	struct idr_layer *p, *new;
	int layers, v, id;
	unsigned long flags;
 
	id = starting_id;
build_up:
	p = idp->top;
	layers = idp->layers;
	if (unlikely(!p)) {
		if (!(p = get_from_free_list(idp)))
			return -1;
		p->layer = 0;
		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 - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
		layers++;
		if (!p->count) {
			/* special case: if the tree is currently empty,
			 * then we grow the tree by moving the top node
			 * upwards.
			 */
			p->layer++;
			continue;
		}
		if (!(new = get_from_free_list(idp))) {
			/*
			 * The allocation failed.  If we built part of
			 * the structure tear it down.
			 */
//           spin_lock_irqsave(&idp->lock, flags);
			for (new = p; p && p != idp->top; new = p) {
				p = p->ary[0];
				new->ary[0] = NULL;
				new->bitmap = new->count = 0;
				__move_to_free_list(idp, new);
			}
//           spin_unlock_irqrestore(&idp->lock, flags);
			return -1;
		}
		new->ary[0] = p;
		new->count = 1;
		new->layer = layers-1;
		if (p->bitmap == IDR_FULL)
			__set_bit(0, &new->bitmap);
		p = new;
	}
	rcu_assign_pointer(idp->top, p);
	idp->layers = layers;
	v = sub_alloc(idp, &id, pa);
	if (v == IDR_NEED_TO_GROW)
		goto build_up;
	return(v);
}
 
static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
{
	struct idr_layer *pa[MAX_LEVEL];
	int id;
 
	id = idr_get_empty_slot(idp, starting_id, pa);
	if (id >= 0) {
		/*
		 * Successfully found an empty slot.  Install the user
		 * pointer and mark the slot full.
		 */
		rcu_assign_pointer(pa[0]->ary[id & IDR_MASK],
				(struct idr_layer *)ptr);
		pa[0]->count++;
		idr_mark_full(pa, id);
	}
 
	return id;
}
 
/**
 * idr_get_new_above - allocate new idr entry above or equal to a start id
 * @idp: idr handle
 * @ptr: pointer you want associated with the id
 * @starting_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 allocation from IDR's private freelist fails, idr_get_new_above() will
 * return %-EAGAIN.  The caller should retry the idr_pre_get() call to refill
 * IDR's preallocation and then retry the idr_get_new_above() call.
 *
 * If the idr is full idr_get_new_above() will return %-ENOSPC.
 *
 * @id returns a value in the range @starting_id ... %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)
    {
        dbgprintf("fail\n");
        return _idr_rc_to_errno(rv);
    };
	*id = rv;
    return 0;
}
 
/**
 * idr_get_new - allocate new idr entry
 * @idp: idr handle
 * @ptr: pointer you want associated with the id
 * @id: pointer to the allocated handle
 *
 * If allocation from IDR's private freelist fails, idr_get_new_above() will
 * return %-EAGAIN.  The caller should retry the idr_pre_get() call to refill
 * IDR's preallocation and then retry the idr_get_new_above() call.
 *
 * If the idr is full idr_get_new_above() 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)
		return _idr_rc_to_errno(rv);
	*id = rv;
	return 0;
}
 
static void idr_remove_warning(int id)
{
	printk(KERN_WARNING
		"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];
	struct idr_layer *to_free;
	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);
		rcu_assign_pointer(p->ary[n], NULL);
		to_free = NULL;
		while(*paa && ! --((**paa)->count)){
			if (to_free)
				free_layer(to_free);
			to_free = **paa;
			**paa-- = NULL;
		}
		if (!*paa)
			idp->layers = 0;
		if (to_free)
			free_layer(to_free);
	} else
		idr_remove_warning(id);
}
 
/**
 * idr_remove - remove the given id and free its slot
 * @idp: idr handle
 * @id: unique key
 */
void idr_remove(struct idr *idp, int id)
{
	struct idr_layer *p;
	struct idr_layer *to_free;
 
	/* 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]) {
		/*
		 * Single child at leftmost slot: we can shrink the tree.
		 * This level is not needed anymore since when layers are
		 * inserted, they are inserted at the top of the existing
		 * tree.
		 */
		to_free = idp->top;
		p = idp->top->ary[0];
		rcu_assign_pointer(idp->top, p);
		--idp->layers;
		to_free->bitmap = to_free->count = 0;
		free_layer(to_free);
	}
	while (idp->id_free_cnt >= IDR_FREE_MAX) {
		p = get_from_free_list(idp);
		/*
		 * Note: we don't call the rcu callback here, since the only
		 * layers that fall into the freelist are those that have been
		 * preallocated.
		 */
        kfree(p);
	}
	return;
}
 
 
/**
 * idr_remove_all - remove all ids from the given idr tree
 * @idp: idr handle
 *
 * idr_destroy() only frees up unused, cached idp_layers, but this
 * function will remove all id mappings and leave all idp_layers
 * unused.
 *
 * A typical clean-up sequence for objects stored in an idr tree will
 * use idr_for_each() to free all objects, if necessay, then
 * idr_remove_all() to remove all ids, and idr_destroy() to free
 * up the cached idr_layers.
 */
void idr_remove_all(struct idr *idp)
{
	int n, id, max;
	int bt_mask;
	struct idr_layer *p;
	struct idr_layer *pa[MAX_LEVEL];
	struct idr_layer **paa = &pa[0];
 
	n = idp->layers * IDR_BITS;
	p = idp->top;
	rcu_assign_pointer(idp->top, NULL);
	max = 1 << n;
 
	id = 0;
	while (id < max) {
		while (n > IDR_BITS && p) {
			n -= IDR_BITS;
			*paa++ = p;
			p = p->ary[(id >> n) & IDR_MASK];
		}
 
		bt_mask = id;
		id += 1 << n;
		/* Get the highest bit that the above add changed from 0->1. */
		while (n < fls(id ^ bt_mask)) {
			if (p)
				free_layer(p);
			n += IDR_BITS;
			p = *--paa;
		}
	}
	idp->layers = 0;
}
 
/**
 * idr_destroy - release all cached layers within an idr tree
 * @idp: idr handle
 */
void idr_destroy(struct idr *idp)
{
	while (idp->id_free_cnt) {
		struct idr_layer *p = get_from_free_list(idp);
        kfree(p);
	}
}
 
 
/**
 * 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().
 *
 * This function can be called under rcu_read_lock(), given that the leaf
 * pointers lifetimes are correctly managed.
 */
void *idr_find(struct idr *idp, int id)
{
	int n;
	struct idr_layer *p;
 
	p = rcu_dereference(idp->top);
	if (!p)
		return NULL;
	n = (p->layer+1) * IDR_BITS;
 
	/* Mask off upper bits we don't use for the search. */
	id &= MAX_ID_MASK;
 
	if (id >= (1 << n))
		return NULL;
	BUG_ON(n == 0);
 
	while (n > 0 && p) {
		n -= IDR_BITS;
		BUG_ON(n != p->layer*IDR_BITS);
		p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]);
	}
	return((void *)p);
}
 
#if 0
/**
 * idr_for_each - iterate through all stored pointers
 * @idp: idr handle
 * @fn: function to be called for each pointer
 * @data: data passed back to callback function
 *
 * Iterate over the pointers registered with the given idr.  The
 * callback function will be called for each pointer currently
 * registered, passing the id, the pointer and the data pointer passed
 * to this function.  It is not safe to modify the idr tree while in
 * the callback, so functions such as idr_get_new and idr_remove are
 * not allowed.
 *
 * We check the return of @fn each time. If it returns anything other
 * than %0, we break out and return that value.
 *
 * The caller must serialize idr_for_each() vs idr_get_new() and idr_remove().
 */
int idr_for_each(struct idr *idp,
		 int (*fn)(int id, void *p, void *data), void *data)
{
	int n, id, max, error = 0;
	struct idr_layer *p;
	struct idr_layer *pa[MAX_LEVEL];
	struct idr_layer **paa = &pa[0];
 
	n = idp->layers * IDR_BITS;
	p = rcu_dereference(idp->top);
	max = 1 << n;
 
	id = 0;
	while (id < max) {
		while (n > 0 && p) {
			n -= IDR_BITS;
			*paa++ = p;
			p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]);
		}
 
		if (p) {
			error = fn(id, (void *)p, data);
			if (error)
				break;
		}
 
		id += 1 << n;
		while (n < fls(id)) {
			n += IDR_BITS;
			p = *--paa;
		}
	}
 
	return error;
}
EXPORT_SYMBOL(idr_for_each);
 
/**
 * idr_get_next - lookup next object of id to given id.
 * @idp: idr handle
 * @nextidp:  pointer to lookup key
 *
 * Returns pointer to registered object with id, which is next number to
 * given id. After being looked up, *@nextidp will be updated for the next
 * iteration.
 */
 
void *idr_get_next(struct idr *idp, int *nextidp)
{
	struct idr_layer *p, *pa[MAX_LEVEL];
	struct idr_layer **paa = &pa[0];
	int id = *nextidp;
	int n, max;
 
	/* find first ent */
	n = idp->layers * IDR_BITS;
	max = 1 << n;
	p = rcu_dereference(idp->top);
	if (!p)
		return NULL;
 
	while (id < max) {
		while (n > 0 && p) {
			n -= IDR_BITS;
			*paa++ = p;
			p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]);
		}
 
		if (p) {
			*nextidp = id;
			return p;
		}
 
		id += 1 << n;
		while (n < fls(id)) {
			n += IDR_BITS;
			p = *--paa;
		}
	}
	return NULL;
}
 
 
 
/**
 * idr_replace - replace pointer for given id
 * @idp: idr handle
 * @ptr: pointer you want associated with the id
 * @id: lookup key
 *
 * Replace the pointer registered with an id and return the old value.
 * A %-ENOENT return indicates that @id was not found.
 * A %-EINVAL return indicates that @id was not within valid constraints.
 *
 * The caller must serialize with writers.
 */
void *idr_replace(struct idr *idp, void *ptr, int id)
{
	int n;
	struct idr_layer *p, *old_p;
 
	p = idp->top;
	if (!p)
		return ERR_PTR(-EINVAL);
 
	n = (p->layer+1) * IDR_BITS;
 
	id &= MAX_ID_MASK;
 
	if (id >= (1 << n))
		return ERR_PTR(-EINVAL);
 
	n -= IDR_BITS;
	while ((n > 0) && p) {
		p = p->ary[(id >> n) & IDR_MASK];
		n -= IDR_BITS;
	}
 
	n = id & IDR_MASK;
	if (unlikely(p == NULL || !test_bit(n, &p->bitmap)))
		return ERR_PTR(-ENOENT);
 
	old_p = p->ary[n];
	rcu_assign_pointer(p->ary[n], ptr);
 
	return old_p;
}
EXPORT_SYMBOL(idr_replace);
 
 
#endif
 
 
void idr_init_cache(void)
{
    //idr_layer_cache = kmem_cache_create("idr_layer_cache",
    //           sizeof(struct idr_layer), 0, SLAB_PANIC, NULL);
}
 
/**
 * 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)
{
	memset(idp, 0, sizeof(struct idr));
 //  spin_lock_init(&idp->lock);
}
 
#if 0
 
/*
 * IDA - IDR based ID allocator
 *
 * This is id allocator without id -> pointer translation.  Memory
 * usage is much lower than full blown idr because each id only
 * occupies a bit.  ida uses a custom leaf node which contains
 * IDA_BITMAP_BITS slots.
 *
 * 2007-04-25  written by Tejun Heo 
 */
 
static void free_bitmap(struct ida *ida, struct ida_bitmap *bitmap)
{
	unsigned long flags;
 
	if (!ida->free_bitmap) {
		spin_lock_irqsave(&ida->idr.lock, flags);
		if (!ida->free_bitmap) {
			ida->free_bitmap = bitmap;
			bitmap = NULL;
		}
		spin_unlock_irqrestore(&ida->idr.lock, flags);
	}
 
	kfree(bitmap);
}
 
/**
 * ida_pre_get - reserve resources for ida allocation
 * @ida:	ida handle
 * @gfp_mask:	memory allocation flag
 *
 * 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 ida_pre_get(struct ida *ida, gfp_t gfp_mask)
{
	/* allocate idr_layers */
	if (!idr_pre_get(&ida->idr, gfp_mask))
		return 0;
 
	/* allocate free_bitmap */
	if (!ida->free_bitmap) {
		struct ida_bitmap *bitmap;
 
		bitmap = kzalloc(sizeof(struct ida_bitmap), gfp_mask);
		if (!bitmap)
			return 0;
 
		free_bitmap(ida, bitmap);
	}
 
	return 1;
}
EXPORT_SYMBOL(ida_pre_get);
 
/**
 * ida_get_new_above - allocate new ID above or equal to a start id
 * @ida:	ida handle
 * @starting_id: id to start search at
 * @p_id:	pointer to the allocated handle
 *
 * Allocate new ID above or equal to @starting_id.  It should be called
 * with any required locks.
 *
 * If memory is required, it will return %-EAGAIN, you should unlock
 * and go back to the ida_pre_get() call.  If the ida is full, it will
 * return %-ENOSPC.
 *
 * @p_id returns a value in the range @starting_id ... %0x7fffffff.
 */
int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
{
	struct idr_layer *pa[MAX_LEVEL];
	struct ida_bitmap *bitmap;
	unsigned long flags;
	int idr_id = starting_id / IDA_BITMAP_BITS;
	int offset = starting_id % IDA_BITMAP_BITS;
	int t, id;
 
 restart:
	/* get vacant slot */
	t = idr_get_empty_slot(&ida->idr, idr_id, pa);
	if (t < 0)
		return _idr_rc_to_errno(t);
 
	if (t * IDA_BITMAP_BITS >= MAX_ID_BIT)
		return -ENOSPC;
 
	if (t != idr_id)
		offset = 0;
	idr_id = t;
 
	/* if bitmap isn't there, create a new one */
	bitmap = (void *)pa[0]->ary[idr_id & IDR_MASK];
	if (!bitmap) {
		spin_lock_irqsave(&ida->idr.lock, flags);
		bitmap = ida->free_bitmap;
		ida->free_bitmap = NULL;
		spin_unlock_irqrestore(&ida->idr.lock, flags);
 
		if (!bitmap)
			return -EAGAIN;
 
		memset(bitmap, 0, sizeof(struct ida_bitmap));
		rcu_assign_pointer(pa[0]->ary[idr_id & IDR_MASK],
				(void *)bitmap);
		pa[0]->count++;
	}
 
	/* lookup for empty slot */
	t = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, offset);
	if (t == IDA_BITMAP_BITS) {
		/* no empty slot after offset, continue to the next chunk */
		idr_id++;
		offset = 0;
		goto restart;
	}
 
	id = idr_id * IDA_BITMAP_BITS + t;
	if (id >= MAX_ID_BIT)
		return -ENOSPC;
 
	__set_bit(t, bitmap->bitmap);
	if (++bitmap->nr_busy == IDA_BITMAP_BITS)
		idr_mark_full(pa, idr_id);
 
	*p_id = id;
 
	/* Each leaf node can handle nearly a thousand slots and the
	 * whole idea of ida is to have small memory foot print.
	 * Throw away extra resources one by one after each successful
	 * allocation.
	 */
	if (ida->idr.id_free_cnt || ida->free_bitmap) {
		struct idr_layer *p = get_from_free_list(&ida->idr);
		if (p)
			kmem_cache_free(idr_layer_cache, p);
	}
 
	return 0;
}
EXPORT_SYMBOL(ida_get_new_above);
 
/**
 * ida_get_new - allocate new ID
 * @ida:	idr handle
 * @p_id:	pointer to the allocated handle
 *
 * Allocate new ID.  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.
 *
 * @p_id returns a value in the range %0 ... %0x7fffffff.
 */
int ida_get_new(struct ida *ida, int *p_id)
{
	return ida_get_new_above(ida, 0, p_id);
}
EXPORT_SYMBOL(ida_get_new);
 
/**
 * ida_remove - remove the given ID
 * @ida:	ida handle
 * @id:		ID to free
 */
void ida_remove(struct ida *ida, int id)
{
	struct idr_layer *p = ida->idr.top;
	int shift = (ida->idr.layers - 1) * IDR_BITS;
	int idr_id = id / IDA_BITMAP_BITS;
	int offset = id % IDA_BITMAP_BITS;
	int n;
	struct ida_bitmap *bitmap;
 
	/* clear full bits while looking up the leaf idr_layer */
	while ((shift > 0) && p) {
		n = (idr_id >> shift) & IDR_MASK;
		__clear_bit(n, &p->bitmap);
		p = p->ary[n];
		shift -= IDR_BITS;
	}
 
	if (p == NULL)
		goto err;
 
	n = idr_id & IDR_MASK;
	__clear_bit(n, &p->bitmap);
 
	bitmap = (void *)p->ary[n];
	if (!test_bit(offset, bitmap->bitmap))
		goto err;
 
	/* update bitmap and remove it if empty */
	__clear_bit(offset, bitmap->bitmap);
	if (--bitmap->nr_busy == 0) {
		__set_bit(n, &p->bitmap);	/* to please idr_remove() */
		idr_remove(&ida->idr, idr_id);
		free_bitmap(ida, bitmap);
	}
 
	return;
 
 err:
	printk(KERN_WARNING
	       "ida_remove called for id=%d which is not allocated.\n", id);
}
EXPORT_SYMBOL(ida_remove);
 
/**
 * ida_destroy - release all cached layers within an ida tree
 * @ida:		ida handle
 */
void ida_destroy(struct ida *ida)
{
	idr_destroy(&ida->idr);
	kfree(ida->free_bitmap);
}
EXPORT_SYMBOL(ida_destroy);
 
/**
 * ida_init - initialize ida handle
 * @ida:	ida handle
 *
 * This function is use to set up the handle (@ida) that you will pass
 * to the rest of the functions.
 */
void ida_init(struct ida *ida)
{
	memset(ida, 0, sizeof(struct ida));
	idr_init(&ida->idr);
 
}
EXPORT_SYMBOL(ida_init);
 
 
#endif

Rev 1412	Rev 2966
1	/*	1	/*
2	* 2002-10-18 written by Jim Houston jim.houston@ccur.com	2	* 2002-10-18 written by Jim Houston jim.houston@ccur.com
3	* Copyright (C) 2002 by Concurrent Computer Corporation	3	* Copyright (C) 2002 by Concurrent Computer Corporation
4	* Distributed under the GNU GPL license version 2.	4	* Distributed under the GNU GPL license version 2.
5	*	5	*
6	* Modified by George Anzinger to reuse immediately and to use	6	* Modified by George Anzinger to reuse immediately and to use
7	* find bit instructions. Also removed _irq on spinlocks.	7	* find bit instructions. Also removed _irq on spinlocks.
8	*	8	*
9	* Modified by Nadia Derbey to make it RCU safe.	9	* Modified by Nadia Derbey to make it RCU safe.
10	*	10	*
11	* Small id to pointer translation service.	11	* Small id to pointer translation service.
12	*	12	*
13	* It uses a radix tree like structure as a sparse array indexed	13	* It uses a radix tree like structure as a sparse array indexed
14	* by the id to obtain the pointer. The bitmap makes allocating	14	* by the id to obtain the pointer. The bitmap makes allocating
15	* a new id quick.	15	* a new id quick.
16	*	16	*
17	* You call it to allocate an id (an int) an associate with that id a	17	* You call it to allocate an id (an int) an associate with that id a
18	* pointer or what ever, we treat it as a (void *). You can pass this	18	* pointer or what ever, we treat it as a (void *). You can pass this
19	* id to a user for him to pass back at a later time. You then pass	19	* id to a user for him to pass back at a later time. You then pass
20	* that id to this code and it returns your pointer.	20	* that id to this code and it returns your pointer.
21		21
22	* You can release ids at any time. When all ids are released, most of	22	* You can release ids at any time. When all ids are released, most of
23	* the memory is returned (we keep IDR_FREE_MAX) in a local pool so we	23	* the memory is returned (we keep IDR_FREE_MAX) in a local pool so we
24	* don't need to go to the memory "store" during an id allocate, just	24	* don't need to go to the memory "store" during an id allocate, just
25	* so you don't need to be too concerned about locking and conflicts	25	* so you don't need to be too concerned about locking and conflicts
26	* with the slab allocator.	26	* with the slab allocator.
27	*/	27	*/
28		28
29	#include	29	#include
30	#include	30	#include
31	#include	31	#include
32	#include	32	#include
33	//#include	33	//#include
34		34
35	unsigned long find_first_bit(const unsigned long *addr, unsigned long size)	35	unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
36	{	36	{
37	const unsigned long *p = addr;	37	const unsigned long *p = addr;
38	unsigned long result = 0;	38	unsigned long result = 0;
39	unsigned long tmp;	39	unsigned long tmp;
40		40
41	while (size & ~(BITS_PER_LONG-1)) {	41	while (size & ~(BITS_PER_LONG-1)) {
42	if ((tmp = *(p++)))	42	if ((tmp = *(p++)))
43	goto found;	43	goto found;
44	result += BITS_PER_LONG;	44	result += BITS_PER_LONG;
45	size -= BITS_PER_LONG;	45	size -= BITS_PER_LONG;
46	}	46	}
47	if (!size)	47	if (!size)
48	return result;	48	return result;
49		49
50	tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));	50	tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
51	if (tmp == 0UL) /* Are any bits set? */	51	if (tmp == 0UL) /* Are any bits set? */
52	return result + size; /* Nope. */	52	return result + size; /* Nope. */
53	found:	53	found:
54	return result + __ffs(tmp);	54	return result + __ffs(tmp);
55	}	55	}
56		56
57	int find_next_bit(const unsigned long *addr, int size, int offset)	57	int find_next_bit(const unsigned long *addr, int size, int offset)
58	{	58	{
59	const unsigned long *p = addr + (offset >> 5);	59	const unsigned long *p = addr + (offset >> 5);
60	int set = 0, bit = offset & 31, res;	60	int set = 0, bit = offset & 31, res;
61		61
62	if (bit)	62	if (bit)
63	{	63	{
64	/*	64	/*
65	* Look for nonzero in the first 32 bits:	65	* Look for nonzero in the first 32 bits:
66	*/	66	*/
67	__asm__("bsfl %1,%0\n\t"	67	__asm__("bsfl %1,%0\n\t"
68	"jne 1f\n\t"	68	"jne 1f\n\t"
69	"movl $32, %0\n"	69	"movl $32, %0\n"
70	"1:"	70	"1:"
71	: "=r" (set)	71	: "=r" (set)
72	: "r" (*p >> bit));	72	: "r" (*p >> bit));
73	if (set < (32 - bit))	73	if (set < (32 - bit))
74	return set + offset;	74	return set + offset;
75	set = 32 - bit;	75	set = 32 - bit;
76	p++;	76	p++;
77	}	77	}
78	/*	78	/*
79	* No set bit yet, search remaining full words for a bit	79	* No set bit yet, search remaining full words for a bit
80	*/	80	*/
81	res = find_first_bit (p, size - 32 * (p - addr));	81	res = find_first_bit (p, size - 32 * (p - addr));
82	return (offset + set + res);	82	return (offset + set + res);
83	}	83	}
84		84
85	#define ACCESS_ONCE(x) ((volatile typeof(x) )&(x))	85	#define ACCESS_ONCE(x) ((volatile typeof(x) )&(x))
86		86
87	#define rcu_dereference(p) ({ \	87	#define rcu_dereference(p) ({ \
88	typeof(p) _________p1 = ACCESS_ONCE(p); \	88	typeof(p) _________p1 = ACCESS_ONCE(p); \
89	(_________p1); \	89	(_________p1); \
90	})	90	})
91		91
92	#define rcu_assign_pointer(p, v) \	92	#define rcu_assign_pointer(p, v) \
93	({ \	93	({ \
94	if (!__builtin_constant_p(v) \|\| \	94	if (!__builtin_constant_p(v) \|\| \
95	((v) != NULL)) \	95	((v) != NULL)) \
96	(p) = (v); \	96	(p) = (v); \
97	})	97	})
98		98
99	//static struct kmem_cache *idr_layer_cache;	99	//static struct kmem_cache *idr_layer_cache;
100		100
101		101
102		102
103		103
104		104
105	static struct idr_layer get_from_free_list(struct idr idp)	105	static struct idr_layer get_from_free_list(struct idr idp)
106	{	106	{
107	struct idr_layer *p;	107	struct idr_layer *p;
108	unsigned long flags;	108	unsigned long flags;
109		109
110	// spin_lock_irqsave(&idp->lock, flags);	110	// spin_lock_irqsave(&idp->lock, flags);
111	if ((p = idp->id_free)) {	111	if ((p = idp->id_free)) {
112	idp->id_free = p->ary[0];	112	idp->id_free = p->ary[0];
113	idp->id_free_cnt--;	113	idp->id_free_cnt--;
114	p->ary[0] = NULL;	114	p->ary[0] = NULL;
115	}	115	}
116	// spin_unlock_irqrestore(&idp->lock, flags);	116	// spin_unlock_irqrestore(&idp->lock, flags);
117	return(p);	117	return(p);
118	}	118	}
119		-
120		119
121	static void idr_layer_rcu_free(struct rcu_head *head)	120	static void idr_layer_rcu_free(struct rcu_head *head)
122	{	121	{
123	struct idr_layer *layer;	122	struct idr_layer *layer;
124		123
125	layer = container_of(head, struct idr_layer, rcu_head);	124	layer = container_of(head, struct idr_layer, rcu_head);
126	kfree(layer);	125	kfree(layer);
127	}	126	}
128		-
129		-
130		127
131	static inline void free_layer(struct idr_layer *p)	128	static inline void free_layer(struct idr_layer *p)
132	{	129	{
133	kfree(p);	130	kfree(p);
134	}	131	}
135		-
136		132
137	/* only called when idp->lock is held */	133	/* only called when idp->lock is held */
138	static void __move_to_free_list(struct idr idp, struct idr_layer p)	134	static void __move_to_free_list(struct idr idp, struct idr_layer p)
139	{	135	{
140	p->ary[0] = idp->id_free;	136	p->ary[0] = idp->id_free;
141	idp->id_free = p;	137	idp->id_free = p;
142	idp->id_free_cnt++;	138	idp->id_free_cnt++;
143	}	139	}
144		140
145	static void move_to_free_list(struct idr idp, struct idr_layer p)	141	static void move_to_free_list(struct idr idp, struct idr_layer p)
146	{	142	{
147	unsigned long flags;	143	unsigned long flags;
148		144
149	/*	145	/*
150	* Depends on the return element being zeroed.	146	* Depends on the return element being zeroed.
151	*/	147	*/
152	// spin_lock_irqsave(&idp->lock, flags);	148	// spin_lock_irqsave(&idp->lock, flags);
153	__move_to_free_list(idp, p);	149	__move_to_free_list(idp, p);
154	// spin_unlock_irqrestore(&idp->lock, flags);	150	// spin_unlock_irqrestore(&idp->lock, flags);
155	}	151	}
156		152
157	static void idr_mark_full(struct idr_layer **pa, int id)	153	static void idr_mark_full(struct idr_layer **pa, int id)
158	{	154	{
159	struct idr_layer *p = pa[0];	155	struct idr_layer *p = pa[0];
160	int l = 0;	156	int l = 0;
161		157
162	__set_bit(id & IDR_MASK, &p->bitmap);	158	__set_bit(id & IDR_MASK, &p->bitmap);
163	/*	159	/*
164	* If this layer is full mark the bit in the layer above to	160	* If this layer is full mark the bit in the layer above to
165	* show that this part of the radix tree is full. This may	161	* show that this part of the radix tree is full. This may
166	* complete the layer above and require walking up the radix	162	* complete the layer above and require walking up the radix
167	* tree.	163	* tree.
168	*/	164	*/
169	while (p->bitmap == IDR_FULL) {	165	while (p->bitmap == IDR_FULL) {
170	if (!(p = pa[++l]))	166	if (!(p = pa[++l]))
171	break;	167	break;
172	id = id >> IDR_BITS;	168	id = id >> IDR_BITS;
173	__set_bit((id & IDR_MASK), &p->bitmap);	169	__set_bit((id & IDR_MASK), &p->bitmap);
174	}	170	}
175	}	171	}
176		-
177		-
178		172
179	/**	173	/**
180	* idr_pre_get - reserver resources for idr allocation	174	* idr_pre_get - reserve resources for idr allocation
181	* @idp: idr handle	175	* @idp: idr handle
182	* @gfp_mask: memory allocation flags	176	* @gfp_mask: memory allocation flags
183	*	177	*
184	* This function should be called prior to locking and calling the	178	* This function should be called prior to calling the idr_get_new* functions.
185	* idr_get_new* functions. It preallocates enough memory to satisfy	179	* It preallocates enough memory to satisfy the worst possible allocation. The
-		180	* caller should pass in GFP_KERNEL if possible. This of course requires that
186	* the worst possible allocation.	181	* no spinning locks be held.
187	*	182	*
188	* If the system is REALLY out of memory this function returns 0,	183	* If the system is REALLY out of memory this function returns %0,
189	* otherwise 1.	184	* otherwise %1.
190	*/	185	*/
191	int idr_pre_get(struct idr *idp, u32_t gfp_mask)	186	int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
192	{	187	{
193	while (idp->id_free_cnt < IDR_FREE_MAX) {	188	while (idp->id_free_cnt < IDR_FREE_MAX) {
194	struct idr_layer *new;	189	struct idr_layer *new;
195	new = kzalloc(sizeof(struct idr_layer), gfp_mask);	190	new = kzalloc(sizeof(struct idr_layer), gfp_mask);
196	if (new == NULL)	191	if (new == NULL)
197	return (0);	192	return (0);
198	move_to_free_list(idp, new);	193	move_to_free_list(idp, new);
199	}	194	}
200	return 1;	195	return 1;
201	}	196	}
202		197
203	static int sub_alloc(struct idr idp, int starting_id, struct idr_layer **pa)	198	static int sub_alloc(struct idr idp, int starting_id, struct idr_layer **pa)
204	{	199	{
205	int n, m, sh;	200	int n, m, sh;
206	struct idr_layer p, new;	201	struct idr_layer p, new;
207	int l, id, oid;	202	int l, id, oid;
208	unsigned long bm;	203	unsigned long bm;
209		204
210	id = *starting_id;	205	id = *starting_id;
211	restart:	206	restart:
212	p = idp->top;	207	p = idp->top;
213	l = idp->layers;	208	l = idp->layers;
214	pa[l--] = NULL;	209	pa[l--] = NULL;
215	while (1) {	210	while (1) {
216	/*	211	/*
217	* We run around this while until we reach the leaf node...	212	* We run around this while until we reach the leaf node...
218	*/	213	*/
219	n = (id >> (IDR_BITS*l)) & IDR_MASK;	214	n = (id >> (IDR_BITS*l)) & IDR_MASK;
220	bm = ~p->bitmap;	215	bm = ~p->bitmap;
221	m = find_next_bit(&bm, IDR_SIZE, n);	216	m = find_next_bit(&bm, IDR_SIZE, n);
222	if (m == IDR_SIZE) {	217	if (m == IDR_SIZE) {
223	/* no space available go back to previous layer. */	218	/* no space available go back to previous layer. */
224	l++;	219	l++;
225	oid = id;	220	oid = id;
226	id = (id \| ((1 << (IDR_BITS * l)) - 1)) + 1;	221	id = (id \| ((1 << (IDR_BITS * l)) - 1)) + 1;
227		222
228	/* if already at the top layer, we need to grow */	223	/* if already at the top layer, we need to grow */
229	if (!(p = pa[l])) {	224	if (!(p = pa[l])) {
230	*starting_id = id;	225	*starting_id = id;
231	return IDR_NEED_TO_GROW;	226	return IDR_NEED_TO_GROW;
232	}	227	}
233		228
234	/* If we need to go up one layer, continue the	229	/* If we need to go up one layer, continue the
235	* loop; otherwise, restart from the top.	230	* loop; otherwise, restart from the top.
236	*/	231	*/
237	sh = IDR_BITS * (l + 1);	232	sh = IDR_BITS * (l + 1);
238	if (oid >> sh == id >> sh)	233	if (oid >> sh == id >> sh)
239	continue;	234	continue;
240	else	235	else
241	goto restart;	236	goto restart;
242	}	237	}
243	if (m != n) {	238	if (m != n) {
244	sh = IDR_BITS*l;	239	sh = IDR_BITS*l;
245	id = ((id >> sh) ^ n ^ m) << sh;	240	id = ((id >> sh) ^ n ^ m) << sh;
246	}	241	}
247	if ((id >= MAX_ID_BIT) \|\| (id < 0))	242	if ((id >= MAX_ID_BIT) \|\| (id < 0))
248	return IDR_NOMORE_SPACE;	243	return IDR_NOMORE_SPACE;
249	if (l == 0)	244	if (l == 0)
250	break;	245	break;
251	/*	246	/*
252	* Create the layer below if it is missing.	247	* Create the layer below if it is missing.
253	*/	248	*/
254	if (!p->ary[m]) {	249	if (!p->ary[m]) {
255	new = get_from_free_list(idp);	250	new = get_from_free_list(idp);
256	if (!new)	251	if (!new)
257	return -1;	252	return -1;
258	new->layer = l-1;	253	new->layer = l-1;
259	rcu_assign_pointer(p->ary[m], new);	254	rcu_assign_pointer(p->ary[m], new);
260	p->count++;	255	p->count++;
261	}	256	}
262	pa[l--] = p;	257	pa[l--] = p;
263	p = p->ary[m];	258	p = p->ary[m];
264	}	259	}
265		260
266	pa[l] = p;	261	pa[l] = p;
267	return id;	262	return id;
268	}	263	}
269		-
270		264
271	static int idr_get_empty_slot(struct idr *idp, int starting_id,	265	static int idr_get_empty_slot(struct idr *idp, int starting_id,
272	struct idr_layer **pa)	266	struct idr_layer **pa)
273	{	267	{
274	struct idr_layer p, new;	268	struct idr_layer p, new;
275	int layers, v, id;	269	int layers, v, id;
276	unsigned long flags;	270	unsigned long flags;
277		271
278	id = starting_id;	272	id = starting_id;
279	build_up:	273	build_up:
280	p = idp->top;	274	p = idp->top;
281	layers = idp->layers;	275	layers = idp->layers;
282	if (unlikely(!p)) {	276	if (unlikely(!p)) {
283	if (!(p = get_from_free_list(idp)))	277	if (!(p = get_from_free_list(idp)))
284	return -1;	278	return -1;
285	p->layer = 0;	279	p->layer = 0;
286	layers = 1;	280	layers = 1;
287	}	281	}
288	/*	282	/*
289	* Add a new layer to the top of the tree if the requested	283	* Add a new layer to the top of the tree if the requested
290	* id is larger than the currently allocated space.	284	* id is larger than the currently allocated space.
291	*/	285	*/
292	while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {	286	while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
293	layers++;	287	layers++;
294	if (!p->count) {	288	if (!p->count) {
295	/* special case: if the tree is currently empty,	289	/* special case: if the tree is currently empty,
296	* then we grow the tree by moving the top node	290	* then we grow the tree by moving the top node
297	* upwards.	291	* upwards.
298	*/	292	*/
299	p->layer++;	293	p->layer++;
300	continue;	294	continue;
301	}	295	}
302	if (!(new = get_from_free_list(idp))) {	296	if (!(new = get_from_free_list(idp))) {
303	/*	297	/*
304	* The allocation failed. If we built part of	298	* The allocation failed. If we built part of
305	* the structure tear it down.	299	* the structure tear it down.
306	*/	300	*/
307	// spin_lock_irqsave(&idp->lock, flags);	301	// spin_lock_irqsave(&idp->lock, flags);
308	for (new = p; p && p != idp->top; new = p) {	302	for (new = p; p && p != idp->top; new = p) {
309	p = p->ary[0];	303	p = p->ary[0];
310	new->ary[0] = NULL;	304	new->ary[0] = NULL;
311	new->bitmap = new->count = 0;	305	new->bitmap = new->count = 0;
312	__move_to_free_list(idp, new);	306	__move_to_free_list(idp, new);
313	}	307	}
314	// spin_unlock_irqrestore(&idp->lock, flags);	308	// spin_unlock_irqrestore(&idp->lock, flags);
315	return -1;	309	return -1;
316	}	310	}
317	new->ary[0] = p;	311	new->ary[0] = p;
318	new->count = 1;	312	new->count = 1;
319	new->layer = layers-1;	313	new->layer = layers-1;
320	if (p->bitmap == IDR_FULL)	314	if (p->bitmap == IDR_FULL)
321	__set_bit(0, &new->bitmap);	315	__set_bit(0, &new->bitmap);
322	p = new;	316	p = new;
323	}	317	}
324	rcu_assign_pointer(idp->top, p);	318	rcu_assign_pointer(idp->top, p);
325	idp->layers = layers;	319	idp->layers = layers;
326	v = sub_alloc(idp, &id, pa);	320	v = sub_alloc(idp, &id, pa);
327	if (v == IDR_NEED_TO_GROW)	321	if (v == IDR_NEED_TO_GROW)
328	goto build_up;	322	goto build_up;
329	return(v);	323	return(v);
330	}	324	}
331		325
332	static int idr_get_new_above_int(struct idr idp, void ptr, int starting_id)	326	static int idr_get_new_above_int(struct idr idp, void ptr, int starting_id)
333	{	327	{
334	struct idr_layer *pa[MAX_LEVEL];	328	struct idr_layer *pa[MAX_LEVEL];
335	int id;	329	int id;
336		330
337	id = idr_get_empty_slot(idp, starting_id, pa);	331	id = idr_get_empty_slot(idp, starting_id, pa);
338	if (id >= 0) {	332	if (id >= 0) {
339	/*	333	/*
340	* Successfully found an empty slot. Install the user	334	* Successfully found an empty slot. Install the user
341	* pointer and mark the slot full.	335	* pointer and mark the slot full.
342	*/	336	*/
343	rcu_assign_pointer(pa[0]->ary[id & IDR_MASK],	337	rcu_assign_pointer(pa[0]->ary[id & IDR_MASK],
344	(struct idr_layer *)ptr);	338	(struct idr_layer *)ptr);
345	pa[0]->count++;	339	pa[0]->count++;
346	idr_mark_full(pa, id);	340	idr_mark_full(pa, id);
347	}	341	}
348		342
349	return id;	343	return id;
350	}	344	}
351		345
352	/**	346	/**
353	* idr_get_new_above - allocate new idr entry above or equal to a start id	347	* idr_get_new_above - allocate new idr entry above or equal to a start id
354	* @idp: idr handle	348	* @idp: idr handle
355	* @ptr: pointer you want associated with the ide	349	* @ptr: pointer you want associated with the id
356	* @start_id: id to start search at	350	* @starting_id: id to start search at
357	* @id: pointer to the allocated handle	351	* @id: pointer to the allocated handle
358	*	352	*
359	* This is the allocate id function. It should be called with any	353	* This is the allocate id function. It should be called with any
360	* required locks.	354	* required locks.
361	*	355	*
362	* If memory is required, it will return -EAGAIN, you should unlock	356	* If allocation from IDR's private freelist fails, idr_get_new_above() will
363	* and go back to the idr_pre_get() call. If the idr is full, it will	357	* return %-EAGAIN. The caller should retry the idr_pre_get() call to refill
364	* return -ENOSPC.	358	* IDR's preallocation and then retry the idr_get_new_above() call.
365	*	359	*
-		360	* If the idr is full idr_get_new_above() will return %-ENOSPC.
-		361	*
366	* @id returns a value in the range @starting_id ... 0x7fffffff	362	* @id returns a value in the range @starting_id ... %0x7fffffff
367	*/	363	*/
368	int idr_get_new_above(struct idr idp, void ptr, int starting_id, int *id)	364	int idr_get_new_above(struct idr idp, void ptr, int starting_id, int *id)
369	{	365	{
370	int rv;	366	int rv;
-		367
371	rv = idr_get_new_above_int(idp, ptr, starting_id);	368	rv = idr_get_new_above_int(idp, ptr, starting_id);
372	/*	369	/*
373	* This is a cheap hack until the IDR code can be fixed to	370	* This is a cheap hack until the IDR code can be fixed to
374	* return proper error values.	371	* return proper error values.
375	*/	372	*/
376	if (rv < 0)	373	if (rv < 0)
377	{	374	{
378	dbgprintf("fail\n");	375	dbgprintf("fail\n");
379	return _idr_rc_to_errno(rv);	376	return _idr_rc_to_errno(rv);
380	};	377	};
381	*id = rv;	378	*id = rv;
382	return 0;	379	return 0;
383	}	380	}
384		381
385	/**	382	/**
386	* idr_get_new - allocate new idr entry	383	* idr_get_new - allocate new idr entry
387	* @idp: idr handle	384	* @idp: idr handle
388	* @ptr: pointer you want associated with the ide	385	* @ptr: pointer you want associated with the id
389	* @id: pointer to the allocated handle	386	* @id: pointer to the allocated handle
390	*	387	*
-		388	* If allocation from IDR's private freelist fails, idr_get_new_above() will
391	* This is the allocate id function. It should be called with any	389	* return %-EAGAIN. The caller should retry the idr_pre_get() call to refill
392	* required locks.	390	* IDR's preallocation and then retry the idr_get_new_above() call.
393	*	391	*
394	* If memory is required, it will return -EAGAIN, you should unlock	392	* If the idr is full idr_get_new_above() will return %-ENOSPC.
395	* and go back to the idr_pre_get() call. If the idr is full, it will	-
396	* return -ENOSPC.	-
397	*	393	*
398	* @id returns a value in the range 0 ... 0x7fffffff	394	* @id returns a value in the range %0 ... %0x7fffffff
399	*/	395	*/
400	int idr_get_new(struct idr idp, void ptr, int *id)	396	int idr_get_new(struct idr idp, void ptr, int *id)
401	{	397	{
402	int rv;	398	int rv;
403		399
404	rv = idr_get_new_above_int(idp, ptr, 0);	400	rv = idr_get_new_above_int(idp, ptr, 0);
405	/*	401	/*
406	* This is a cheap hack until the IDR code can be fixed to	402	* This is a cheap hack until the IDR code can be fixed to
407	* return proper error values.	403	* return proper error values.
408	*/	404	*/
409	if (rv < 0)	405	if (rv < 0)
410	return _idr_rc_to_errno(rv);	406	return _idr_rc_to_errno(rv);
411	*id = rv;	407	*id = rv;
412	return 0;	408	return 0;
413	}	409	}
414		410
415	static void idr_remove_warning(int id)	411	static void idr_remove_warning(int id)
416	{	412	{
417	printk(KERN_WARNING	413	printk(KERN_WARNING
418	"idr_remove called for id=%d which is not allocated.\n", id);	414	"idr_remove called for id=%d which is not allocated.\n", id);
419	// dump_stack();	415	// dump_stack();
420	}	416	}
421		417
422	static void sub_remove(struct idr *idp, int shift, int id)	418	static void sub_remove(struct idr *idp, int shift, int id)
423	{	419	{
424	struct idr_layer *p = idp->top;	420	struct idr_layer *p = idp->top;
425	struct idr_layer **pa[MAX_LEVEL];	421	struct idr_layer **pa[MAX_LEVEL];
426	struct idr_layer ***paa = &pa[0];	422	struct idr_layer ***paa = &pa[0];
427	struct idr_layer *to_free;	423	struct idr_layer *to_free;
428	int n;	424	int n;
429		425
430	*paa = NULL;	426	*paa = NULL;
431	*++paa = &idp->top;	427	*++paa = &idp->top;
432		428
433	while ((shift > 0) && p) {	429	while ((shift > 0) && p) {
434	n = (id >> shift) & IDR_MASK;	430	n = (id >> shift) & IDR_MASK;
435	__clear_bit(n, &p->bitmap);	431	__clear_bit(n, &p->bitmap);
436	*++paa = &p->ary[n];	432	*++paa = &p->ary[n];
437	p = p->ary[n];	433	p = p->ary[n];
438	shift -= IDR_BITS;	434	shift -= IDR_BITS;
439	}	435	}
440	n = id & IDR_MASK;	436	n = id & IDR_MASK;
441	if (likely(p != NULL && test_bit(n, &p->bitmap))){	437	if (likely(p != NULL && test_bit(n, &p->bitmap))){
442	__clear_bit(n, &p->bitmap);	438	__clear_bit(n, &p->bitmap);
443	rcu_assign_pointer(p->ary[n], NULL);	439	rcu_assign_pointer(p->ary[n], NULL);
444	to_free = NULL;	440	to_free = NULL;
445	while(paa && ! --((*paa)->count)){	441	while(paa && ! --((*paa)->count)){
446	if (to_free)	442	if (to_free)
447	free_layer(to_free);	443	free_layer(to_free);
448	to_free = **paa;	444	to_free = **paa;
449	**paa-- = NULL;	445	**paa-- = NULL;
450	}	446	}
451	if (!*paa)	447	if (!*paa)
452	idp->layers = 0;	448	idp->layers = 0;
453	if (to_free)	449	if (to_free)
454	free_layer(to_free);	450	free_layer(to_free);
455	} else	451	} else
456	idr_remove_warning(id);	452	idr_remove_warning(id);
457	}	453	}
458		454
459	/**	455	/**
460	* idr_remove - remove the given id and free it's slot	456	* idr_remove - remove the given id and free its slot
461	* @idp: idr handle	457	* @idp: idr handle
462	* @id: unique key	458	* @id: unique key
463	*/	459	*/
464	void idr_remove(struct idr *idp, int id)	460	void idr_remove(struct idr *idp, int id)
465	{	461	{
466	struct idr_layer *p;	462	struct idr_layer *p;
467	struct idr_layer *to_free;	463	struct idr_layer *to_free;
468		464
469	/* Mask off upper bits we don't use for the search. */	465	/* Mask off upper bits we don't use for the search. */
470	id &= MAX_ID_MASK;	466	id &= MAX_ID_MASK;
471		467
472	sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);	468	sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
473	if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&	469	if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
474	idp->top->ary[0]) {	470	idp->top->ary[0]) {
475	/*	471	/*
476	* Single child at leftmost slot: we can shrink the tree.	472	* Single child at leftmost slot: we can shrink the tree.
477	* This level is not needed anymore since when layers are	473	* This level is not needed anymore since when layers are
478	* inserted, they are inserted at the top of the existing	474	* inserted, they are inserted at the top of the existing
479	* tree.	475	* tree.
480	*/	476	*/
481	to_free = idp->top;	477	to_free = idp->top;
482	p = idp->top->ary[0];	478	p = idp->top->ary[0];
483	rcu_assign_pointer(idp->top, p);	479	rcu_assign_pointer(idp->top, p);
484	--idp->layers;	480	--idp->layers;
485	to_free->bitmap = to_free->count = 0;	481	to_free->bitmap = to_free->count = 0;
486	free_layer(to_free);	482	free_layer(to_free);
487	}	483	}
488	while (idp->id_free_cnt >= IDR_FREE_MAX) {	484	while (idp->id_free_cnt >= IDR_FREE_MAX) {
489	p = get_from_free_list(idp);	485	p = get_from_free_list(idp);
490	/*	486	/*
491	* Note: we don't call the rcu callback here, since the only	487	* Note: we don't call the rcu callback here, since the only
492	* layers that fall into the freelist are those that have been	488	* layers that fall into the freelist are those that have been
493	* preallocated.	489	* preallocated.
494	*/	490	*/
495	kfree(p);	491	kfree(p);

Subversion Repositories Kolibri OS

(root)/drivers/ddk/linux/idr.c – Rev 1412 → 2966