WebSVN – Kolibri OS – Diff – /drivers/video/drm/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 "drm.h"
#include "drmP.h"
#include "drm_crtc.h"
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
#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 - reserver resources for idr allocation
 * @idp:	idr handle
 * @gfp_mask:	memory allocation flags
 *
 * This function should be called prior to locking and calling the
 * idr_get_new* functions. 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, u32_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;
}
EXPORT_SYMBOL(idr_pre_get);
 
 
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 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 @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;
}
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)
		return _idr_rc_to_errno(rv);
	*id = rv;
	return 0;
}
EXPORT_SYMBOL(idr_get_new);
 
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 it's 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;
}
EXPORT_SYMBOL(idr_remove);
 
 
/**
 * 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;
	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];
		}
 
		id += 1 << n;
		while (n < fls(id)) {
			if (p)
				free_layer(p);
			n += IDR_BITS;
			p = *--paa;
		}
	}
	idp->layers = 0;
}
EXPORT_SYMBOL(idr_remove_all);
 
/**
 * 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);
	}
}
EXPORT_SYMBOL(idr_destroy);
 
 
/**
 * 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);
}
EXPORT_SYMBOL(idr_find);
 
#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
 * @id:  pointer to lookup key
 *
 * Returns pointer to registered object with id, which is next number to
 * given id.
 */
 
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);
}
EXPORT_SYMBOL(idr_init);
 
#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
 * @staring_id:	id to start search at
 * @p_id:	pointer to the allocated handle
 *
 * Allocate new ID above or equal to @ida.  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.
 *
 * @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 1246	Rev 1403
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
-		29	#include
28		30
29	#include	31	#include
30	#include	32	//#include
31	#include "drm.h"	33	#include "drm.h"
32	#include "drmP.h"	34	#include "drmP.h"
33	#include "drm_crtc.h"	35	#include "drm_crtc.h"
34		-
35	#define ADDR "=m" ((volatile long ) addr)	-
36		-
37	static inline void __set_bit(int nr, volatile void *addr)	-
38	{	-
39	asm volatile("bts %1,%0"	-
40	: ADDR	-
41	: "Ir" (nr) : "memory");	-
42	}	-
43		-
44	static inline void __clear_bit(int nr, volatile void *addr)	-
45	{	-
46	asm volatile("btr %1,%0" : ADDR : "Ir" (nr));	-
47	}	-
48		-
49	static inline int constant_test_bit(int nr, const volatile void *addr)	-
50	{	-
51	return ((1UL << (nr % 32)) &	-
52	(((unsigned long *)addr)[nr / 32])) != 0;	-
53	}	-
54		-
55	static inline int variable_test_bit(int nr, volatile const void *addr)	-
56	{	-
57	int oldbit;	-
58		-
59	asm volatile("bt %2,%1\n\t"	-
60	"sbb %0,%0"	-
61	: "=r" (oldbit)	-
62	: "m" ((unsigned long )addr), "Ir" (nr));	-
63		-
64	return oldbit;	-
65	};	-
66		-
67		-
68	#define test_bit(nr,addr) \	-
69	(__builtin_constant_p(nr) ? \	-
70	constant_test_bit((nr),(addr)) : \	-
71	variable_test_bit((nr),(addr)))	-
72		-
73		-
74	static inline int fls(int x)	-
75	{	-
76	int r;	-
77		-
78	__asm__("bsrl %1,%0\n\t"	-
79	"jnz 1f\n\t"	-
80	"movl $-1,%0\n"	-
81	"1:" : "=r" (r) : "rm" (x));	-
82	return r+1;	-
83	}	-
84		-
85	static inline unsigned long __ffs(unsigned long word)	-
86	{	-
87	__asm__("bsfl %1,%0"	-
88	:"=r" (word)	-
89	:"rm" (word));	-
90	return word;	-
91	}	-
92		-
93		-
94	static inline unsigned find_first_bit(const unsigned long *addr, unsigned size)	-
95	{	-
96	unsigned x = 0;	-
97		-
98	while (x < size) {	-
99	unsigned long val = *addr++;	-
100	if (val)	-
101	return __ffs(val) + x;	-
102	x += (sizeof(*addr)<<3);	-
103	}	-
104	return x;	-
105	}	-
106		-
107		-
108	int find_next_bit(const unsigned long *addr, int size, int offset)	-
109	{	-
110	const unsigned long *p = addr + (offset >> 5);	-
111	int set = 0, bit = offset & 31, res;	-
112		-
113	if (bit)	-
114	{	-
115	/*	-
116	* Look for nonzero in the first 32 bits:	-
117	*/	-
118	__asm__("bsfl %1,%0\n\t"	-
119	"jne 1f\n\t"	-
120	"movl $32, %0\n"	-
121	"1:"	-
122	: "=r" (set)	-
123	: "r" (*p >> bit));	-
124	if (set < (32 - bit))	-
125	return set + offset;	-
126	set = 32 - bit;	-
127	p++;	-
128	}	-
129	/*	-
130	* No set bit yet, search remaining full words for a bit	-
131	*/	-
132	res = find_first_bit (p, size - 32 * (p - addr));	-
133	return (offset + set + res);	-
134	}	-
135		36
136		37
137	#define ACCESS_ONCE(x) ((volatile typeof(x) )&(x))	38	#define ACCESS_ONCE(x) ((volatile typeof(x) )&(x))
138		39
139	#define rcu_dereference(p) ({ \	40	#define rcu_dereference(p) ({ \
140	typeof(p) _________p1 = ACCESS_ONCE(p); \	41	typeof(p) _________p1 = ACCESS_ONCE(p); \
141	(_________p1); \	42	(_________p1); \
142	})	43	})
143		44
144	#define rcu_assign_pointer(p, v) \	45	#define rcu_assign_pointer(p, v) \
145	({ \	46	({ \
146	if (!__builtin_constant_p(v) \|\| \	47	if (!__builtin_constant_p(v) \|\| \
147	((v) != NULL)) \	48	((v) != NULL)) \
148	(p) = (v); \	49	(p) = (v); \
149	})	50	})
150		51
151	//static struct kmem_cache *idr_layer_cache;	52	//static struct kmem_cache *idr_layer_cache;
152		53
153		54
154		55
155		56
156		57
157	static struct idr_layer get_from_free_list(struct idr idp)	58	static struct idr_layer get_from_free_list(struct idr idp)
158	{	59	{
159	struct idr_layer *p;	60	struct idr_layer *p;
160	unsigned long flags;	61	unsigned long flags;
161		62
162	// spin_lock_irqsave(&idp->lock, flags);	63	// spin_lock_irqsave(&idp->lock, flags);
163	if ((p = idp->id_free)) {	64	if ((p = idp->id_free)) {
164	idp->id_free = p->ary[0];	65	idp->id_free = p->ary[0];
165	idp->id_free_cnt--;	66	idp->id_free_cnt--;
166	p->ary[0] = NULL;	67	p->ary[0] = NULL;
167	}	68	}
168	// spin_unlock_irqrestore(&idp->lock, flags);	69	// spin_unlock_irqrestore(&idp->lock, flags);
169	return(p);	70	return(p);
170	}	71	}
171		72
172		73
173	static void idr_layer_rcu_free(struct rcu_head *head)	74	static void idr_layer_rcu_free(struct rcu_head *head)
174	{	75	{
175	struct idr_layer *layer;	76	struct idr_layer *layer;
176		77
177	layer = container_of(head, struct idr_layer, rcu_head);	78	layer = container_of(head, struct idr_layer, rcu_head);
178	kfree(layer);	79	kfree(layer);
179	}	80	}
180		81
181		82
182		83
183	static inline void free_layer(struct idr_layer *p)	84	static inline void free_layer(struct idr_layer *p)
184	{	85	{
185	kfree(p);	86	kfree(p);
186	}	87	}
187		88
188		89
189	/* only called when idp->lock is held */	90	/* only called when idp->lock is held */
190	static void __move_to_free_list(struct idr idp, struct idr_layer p)	91	static void __move_to_free_list(struct idr idp, struct idr_layer p)
191	{	92	{
192	p->ary[0] = idp->id_free;	93	p->ary[0] = idp->id_free;
193	idp->id_free = p;	94	idp->id_free = p;
194	idp->id_free_cnt++;	95	idp->id_free_cnt++;
195	}	96	}
196		97
197	static void move_to_free_list(struct idr idp, struct idr_layer p)	98	static void move_to_free_list(struct idr idp, struct idr_layer p)
198	{	99	{
199	unsigned long flags;	100	unsigned long flags;
200		101
201	/*	102	/*
202	* Depends on the return element being zeroed.	103	* Depends on the return element being zeroed.
203	*/	104	*/
204	// spin_lock_irqsave(&idp->lock, flags);	105	// spin_lock_irqsave(&idp->lock, flags);
205	__move_to_free_list(idp, p);	106	__move_to_free_list(idp, p);
206	// spin_unlock_irqrestore(&idp->lock, flags);	107	// spin_unlock_irqrestore(&idp->lock, flags);
207	}	108	}
208		109
209	static void idr_mark_full(struct idr_layer **pa, int id)	110	static void idr_mark_full(struct idr_layer **pa, int id)
210	{	111	{
211	struct idr_layer *p = pa[0];	112	struct idr_layer *p = pa[0];
212	int l = 0;	113	int l = 0;
213		114
214	__set_bit(id & IDR_MASK, &p->bitmap);	115	__set_bit(id & IDR_MASK, &p->bitmap);
215	/*	116	/*
216	* If this layer is full mark the bit in the layer above to	117	* If this layer is full mark the bit in the layer above to
217	* show that this part of the radix tree is full. This may	118	* show that this part of the radix tree is full. This may
218	* complete the layer above and require walking up the radix	119	* complete the layer above and require walking up the radix
219	* tree.	120	* tree.
220	*/	121	*/
221	while (p->bitmap == IDR_FULL) {	122	while (p->bitmap == IDR_FULL) {
222	if (!(p = pa[++l]))	123	if (!(p = pa[++l]))
223	break;	124	break;
224	id = id >> IDR_BITS;	125	id = id >> IDR_BITS;
225	__set_bit((id & IDR_MASK), &p->bitmap);	126	__set_bit((id & IDR_MASK), &p->bitmap);
226	}	127	}
227	}	128	}
228		129
229		130
230		131
231	/**	132	/**
232	* idr_pre_get - reserver resources for idr allocation	133	* idr_pre_get - reserver resources for idr allocation
233	* @idp: idr handle	134	* @idp: idr handle
234	* @gfp_mask: memory allocation flags	135	* @gfp_mask: memory allocation flags
235	*	136	*
236	* This function should be called prior to locking and calling the	137	* This function should be called prior to locking and calling the
237	* idr_get_new* functions. It preallocates enough memory to satisfy	138	* idr_get_new* functions. It preallocates enough memory to satisfy
238	* the worst possible allocation.	139	* the worst possible allocation.
239	*	140	*
240	* If the system is REALLY out of memory this function returns 0,	141	* If the system is REALLY out of memory this function returns 0,
241	* otherwise 1.	142	* otherwise 1.
242	*/	143	*/
243	int idr_pre_get(struct idr *idp, u32_t gfp_mask)	144	int idr_pre_get(struct idr *idp, u32_t gfp_mask)
244	{	145	{
245	while (idp->id_free_cnt < IDR_FREE_MAX) {	146	while (idp->id_free_cnt < IDR_FREE_MAX) {
246	struct idr_layer *new;	147	struct idr_layer *new;
247	new = kzalloc(sizeof(struct idr_layer), gfp_mask);	148	new = kzalloc(sizeof(struct idr_layer), gfp_mask);
248	if (new == NULL)	149	if (new == NULL)
249	return (0);	150	return (0);
250	move_to_free_list(idp, new);	151	move_to_free_list(idp, new);
251	}	152	}
252	return 1;	153	return 1;
253	}	154	}
254	EXPORT_SYMBOL(idr_pre_get);	155	EXPORT_SYMBOL(idr_pre_get);
255		156
256		157
257	static int sub_alloc(struct idr idp, int starting_id, struct idr_layer **pa)	158	static int sub_alloc(struct idr idp, int starting_id, struct idr_layer **pa)
258	{	159	{
259	int n, m, sh;	160	int n, m, sh;
260	struct idr_layer p, new;	161	struct idr_layer p, new;
261	int l, id, oid;	162	int l, id, oid;
262	unsigned long bm;	163	unsigned long bm;
263		164
264	id = *starting_id;	165	id = *starting_id;
265	restart:	166	restart:
266	p = idp->top;	167	p = idp->top;
267	l = idp->layers;	168	l = idp->layers;
268	pa[l--] = NULL;	169	pa[l--] = NULL;
269	while (1) {	170	while (1) {
270	/*	171	/*
271	* We run around this while until we reach the leaf node...	172	* We run around this while until we reach the leaf node...
272	*/	173	*/
273	n = (id >> (IDR_BITS*l)) & IDR_MASK;	174	n = (id >> (IDR_BITS*l)) & IDR_MASK;
274	bm = ~p->bitmap;	175	bm = ~p->bitmap;
275	m = find_next_bit(&bm, IDR_SIZE, n);	176	m = find_next_bit(&bm, IDR_SIZE, n);
276	if (m == IDR_SIZE) {	177	if (m == IDR_SIZE) {
277	/* no space available go back to previous layer. */	178	/* no space available go back to previous layer. */
278	l++;	179	l++;
279	oid = id;	180	oid = id;
280	id = (id \| ((1 << (IDR_BITS * l)) - 1)) + 1;	181	id = (id \| ((1 << (IDR_BITS * l)) - 1)) + 1;
281		182
282	/* if already at the top layer, we need to grow */	183	/* if already at the top layer, we need to grow */
283	if (!(p = pa[l])) {	184	if (!(p = pa[l])) {
284	*starting_id = id;	185	*starting_id = id;
285	return IDR_NEED_TO_GROW;	186	return IDR_NEED_TO_GROW;
286	}	187	}
287		188
288	/* If we need to go up one layer, continue the	189	/* If we need to go up one layer, continue the
289	* loop; otherwise, restart from the top.	190	* loop; otherwise, restart from the top.
290	*/	191	*/
291	sh = IDR_BITS * (l + 1);	192	sh = IDR_BITS * (l + 1);
292	if (oid >> sh == id >> sh)	193	if (oid >> sh == id >> sh)
293	continue;	194	continue;
294	else	195	else
295	goto restart;	196	goto restart;
296	}	197	}
297	if (m != n) {	198	if (m != n) {
298	sh = IDR_BITS*l;	199	sh = IDR_BITS*l;
299	id = ((id >> sh) ^ n ^ m) << sh;	200	id = ((id >> sh) ^ n ^ m) << sh;
300	}	201	}
301	if ((id >= MAX_ID_BIT) \|\| (id < 0))	202	if ((id >= MAX_ID_BIT) \|\| (id < 0))
302	return IDR_NOMORE_SPACE;	203	return IDR_NOMORE_SPACE;
303	if (l == 0)	204	if (l == 0)
304	break;	205	break;
305	/*	206	/*
306	* Create the layer below if it is missing.	207	* Create the layer below if it is missing.
307	*/	208	*/
308	if (!p->ary[m]) {	209	if (!p->ary[m]) {
309	new = get_from_free_list(idp);	210	new = get_from_free_list(idp);
310	if (!new)	211	if (!new)
311	return -1;	212	return -1;
312	new->layer = l-1;	213	new->layer = l-1;
313	rcu_assign_pointer(p->ary[m], new);	214	rcu_assign_pointer(p->ary[m], new);
314	p->count++;	215	p->count++;
315	}	216	}
316	pa[l--] = p;	217	pa[l--] = p;
317	p = p->ary[m];	218	p = p->ary[m];
318	}	219	}
319		220
320	pa[l] = p;	221	pa[l] = p;
321	return id;	222	return id;
322	}	223	}
323		224
324		225
325	static int idr_get_empty_slot(struct idr *idp, int starting_id,	226	static int idr_get_empty_slot(struct idr *idp, int starting_id,
326	struct idr_layer **pa)	227	struct idr_layer **pa)
327	{	228	{
328	struct idr_layer p, new;	229	struct idr_layer p, new;
329	int layers, v, id;	230	int layers, v, id;
330	unsigned long flags;	231	unsigned long flags;
331		232
332	id = starting_id;	233	id = starting_id;
333	build_up:	234	build_up:
334	p = idp->top;	235	p = idp->top;
335	layers = idp->layers;	236	layers = idp->layers;
336	if (unlikely(!p)) {	237	if (unlikely(!p)) {
337	if (!(p = get_from_free_list(idp)))	238	if (!(p = get_from_free_list(idp)))
338	return -1;	239	return -1;
339	p->layer = 0;	240	p->layer = 0;
340	layers = 1;	241	layers = 1;
341	}	242	}
342	/*	243	/*
343	* Add a new layer to the top of the tree if the requested	244	* Add a new layer to the top of the tree if the requested
344	* id is larger than the currently allocated space.	245	* id is larger than the currently allocated space.
345	*/	246	*/
346	while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {	247	while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
347	layers++;	248	layers++;
348	if (!p->count) {	249	if (!p->count) {
349	/* special case: if the tree is currently empty,	250	/* special case: if the tree is currently empty,
350	* then we grow the tree by moving the top node	251	* then we grow the tree by moving the top node
351	* upwards.	252	* upwards.
352	*/	253	*/
353	p->layer++;	254	p->layer++;
354	continue;	255	continue;
355	}	256	}
356	if (!(new = get_from_free_list(idp))) {	257	if (!(new = get_from_free_list(idp))) {
357	/*	258	/*
358	* The allocation failed. If we built part of	259	* The allocation failed. If we built part of
359	* the structure tear it down.	260	* the structure tear it down.
360	*/	261	*/
361	// spin_lock_irqsave(&idp->lock, flags);	262	// spin_lock_irqsave(&idp->lock, flags);
362	for (new = p; p && p != idp->top; new = p) {	263	for (new = p; p && p != idp->top; new = p) {
363	p = p->ary[0];	264	p = p->ary[0];
364	new->ary[0] = NULL;	265	new->ary[0] = NULL;
365	new->bitmap = new->count = 0;	266	new->bitmap = new->count = 0;
366	__move_to_free_list(idp, new);	267	__move_to_free_list(idp, new);
367	}	268	}
368	// spin_unlock_irqrestore(&idp->lock, flags);	269	// spin_unlock_irqrestore(&idp->lock, flags);
369	return -1;	270	return -1;
370	}	271	}
371	new->ary[0] = p;	272	new->ary[0] = p;
372	new->count = 1;	273	new->count = 1;
373	new->layer = layers-1;	274	new->layer = layers-1;
374	if (p->bitmap == IDR_FULL)	275	if (p->bitmap == IDR_FULL)
375	__set_bit(0, &new->bitmap);	276	__set_bit(0, &new->bitmap);
376	p = new;	277	p = new;
377	}	278	}
378	rcu_assign_pointer(idp->top, p);	279	rcu_assign_pointer(idp->top, p);
379	idp->layers = layers;	280	idp->layers = layers;
380	v = sub_alloc(idp, &id, pa);	281	v = sub_alloc(idp, &id, pa);
381	if (v == IDR_NEED_TO_GROW)	282	if (v == IDR_NEED_TO_GROW)
382	goto build_up;	283	goto build_up;
383	return(v);	284	return(v);
384	}	285	}
385		286
386	static int idr_get_new_above_int(struct idr idp, void ptr, int starting_id)	287	static int idr_get_new_above_int(struct idr idp, void ptr, int starting_id)
387	{	288	{
388	struct idr_layer *pa[MAX_LEVEL];	289	struct idr_layer *pa[MAX_LEVEL];
389	int id;	290	int id;
390		291
391	id = idr_get_empty_slot(idp, starting_id, pa);	292	id = idr_get_empty_slot(idp, starting_id, pa);
392	if (id >= 0) {	293	if (id >= 0) {
393	/*	294	/*
394	* Successfully found an empty slot. Install the user	295	* Successfully found an empty slot. Install the user
395	* pointer and mark the slot full.	296	* pointer and mark the slot full.
396	*/	297	*/
397	rcu_assign_pointer(pa[0]->ary[id & IDR_MASK],	298	rcu_assign_pointer(pa[0]->ary[id & IDR_MASK],
398	(struct idr_layer *)ptr);	299	(struct idr_layer *)ptr);
399	pa[0]->count++;	300	pa[0]->count++;
400	idr_mark_full(pa, id);	301	idr_mark_full(pa, id);
401	}	302	}
402		303
403	return id;	304	return id;
404	}	305	}
405		306
406	/**	307	/**
407	* idr_get_new_above - allocate new idr entry above or equal to a start id	308	* idr_get_new_above - allocate new idr entry above or equal to a start id
408	* @idp: idr handle	309	* @idp: idr handle
409	* @ptr: pointer you want associated with the ide	310	* @ptr: pointer you want associated with the ide
410	* @start_id: id to start search at	311	* @start_id: id to start search at
411	* @id: pointer to the allocated handle	312	* @id: pointer to the allocated handle
412	*	313	*
413	* This is the allocate id function. It should be called with any	314	* This is the allocate id function. It should be called with any
414	* required locks.	315	* required locks.
415	*	316	*
416	* If memory is required, it will return -EAGAIN, you should unlock	317	* If memory is required, it will return -EAGAIN, you should unlock
417	* and go back to the idr_pre_get() call. If the idr is full, it will	318	* and go back to the idr_pre_get() call. If the idr is full, it will
418	* return -ENOSPC.	319	* return -ENOSPC.
419	*	320	*
420	* @id returns a value in the range @starting_id ... 0x7fffffff	321	* @id returns a value in the range @starting_id ... 0x7fffffff
421	*/	322	*/
422	int idr_get_new_above(struct idr idp, void ptr, int starting_id, int *id)	323	int idr_get_new_above(struct idr idp, void ptr, int starting_id, int *id)
423	{	324	{
424	int rv;	325	int rv;
425	rv = idr_get_new_above_int(idp, ptr, starting_id);	326	rv = idr_get_new_above_int(idp, ptr, starting_id);
426	/*	327	/*
427	* This is a cheap hack until the IDR code can be fixed to	328	* This is a cheap hack until the IDR code can be fixed to
428	* return proper error values.	329	* return proper error values.
429	*/	330	*/
430	if (rv < 0)	331	if (rv < 0)
431	{	332	{
432	dbgprintf("fail\n");	333	dbgprintf("fail\n");
433	return _idr_rc_to_errno(rv);	334	return _idr_rc_to_errno(rv);
434	};	335	};
435	*id = rv;	336	*id = rv;
436	return 0;	337	return 0;
437	}	338	}
438	EXPORT_SYMBOL(idr_get_new_above);	339	EXPORT_SYMBOL(idr_get_new_above);
439		340
440	/**	341	/**
441	* idr_get_new - allocate new idr entry	342	* idr_get_new - allocate new idr entry
442	* @idp: idr handle	343	* @idp: idr handle
443	* @ptr: pointer you want associated with the ide	344	* @ptr: pointer you want associated with the ide
444	* @id: pointer to the allocated handle	345	* @id: pointer to the allocated handle
445	*	346	*
446	* This is the allocate id function. It should be called with any	347	* This is the allocate id function. It should be called with any
447	* required locks.	348	* required locks.
448	*	349	*
449	* If memory is required, it will return -EAGAIN, you should unlock	350	* If memory is required, it will return -EAGAIN, you should unlock
450	* and go back to the idr_pre_get() call. If the idr is full, it will	351	* and go back to the idr_pre_get() call. If the idr is full, it will
451	* return -ENOSPC.	352	* return -ENOSPC.
452	*	353	*
453	* @id returns a value in the range 0 ... 0x7fffffff	354	* @id returns a value in the range 0 ... 0x7fffffff
454	*/	355	*/
455	int idr_get_new(struct idr idp, void ptr, int *id)	356	int idr_get_new(struct idr idp, void ptr, int *id)
456	{	357	{
457	int rv;	358	int rv;
458		359
459	rv = idr_get_new_above_int(idp, ptr, 0);	360	rv = idr_get_new_above_int(idp, ptr, 0);
460	/*	361	/*
461	* This is a cheap hack until the IDR code can be fixed to	362	* This is a cheap hack until the IDR code can be fixed to
462	* return proper error values.	363	* return proper error values.
463	*/	364	*/
464	if (rv < 0)	365	if (rv < 0)
465	return _idr_rc_to_errno(rv);	366	return _idr_rc_to_errno(rv);
466	*id = rv;	367	*id = rv;
467	return 0;	368	return 0;
468	}	369	}
469	EXPORT_SYMBOL(idr_get_new);	370	EXPORT_SYMBOL(idr_get_new);
470		371
471	static void idr_remove_warning(int id)	372	static void idr_remove_warning(int id)
472	{	373	{
473	printk(KERN_WARNING	374	printk(KERN_WARNING
474	"idr_remove called for id=%d which is not allocated.\n", id);	375	"idr_remove called for id=%d which is not allocated.\n", id);
475	// dump_stack();	376	// dump_stack();
476	}	377	}
477		378
478	static void sub_remove(struct idr *idp, int shift, int id)	379	static void sub_remove(struct idr *idp, int shift, int id)
479	{	380	{
480	struct idr_layer *p = idp->top;	381	struct idr_layer *p = idp->top;
481	struct idr_layer **pa[MAX_LEVEL];	382	struct idr_layer **pa[MAX_LEVEL];
482	struct idr_layer ***paa = &pa[0];	383	struct idr_layer ***paa = &pa[0];
483	struct idr_layer *to_free;	384	struct idr_layer *to_free;
484	int n;	385	int n;
485		386
486	*paa = NULL;	387	*paa = NULL;
487	*++paa = &idp->top;	388	*++paa = &idp->top;
488		389
489	while ((shift > 0) && p) {	390	while ((shift > 0) && p) {
490	n = (id >> shift) & IDR_MASK;	391	n = (id >> shift) & IDR_MASK;
491	__clear_bit(n, &p->bitmap);	392	__clear_bit(n, &p->bitmap);
492	*++paa = &p->ary[n];	393	*++paa = &p->ary[n];
493	p = p->ary[n];	394	p = p->ary[n];
494	shift -= IDR_BITS;	395	shift -= IDR_BITS;
495	}	396	}
496	n = id & IDR_MASK;	397	n = id & IDR_MASK;
497	if (likely(p != NULL && test_bit(n, &p->bitmap))){	398	if (likely(p != NULL && test_bit(n, &p->bitmap))){
498	__clear_bit(n, &p->bitmap);	399	__clear_bit(n, &p->bitmap);

Subversion Repositories Kolibri OS

(root)/drivers/video/drm/idr.c @ 1403 – Rev 1246 → 1403