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

Subversion Repositories Kolibri OS

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