11  * Small id to pointer translation service.
14  * by the id to obtain the pointer.  The bitmap makes allocating
15  * a new id quick.
17  * You call it to allocate an id (an int) an associate with that id a
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.
24  * don't need to go to the memory "store" during an id allocate, just
90 static void idr_mark_full(struct idr_layer **pa, int id)  in idr_mark_full()  argument
95 	__set_bit(id & IDR_MASK, &p->bitmap);  in idr_mark_full()
105 		id = id >> IDR_BITS;  in idr_mark_full()
106 		__set_bit((id & IDR_MASK), &p->bitmap);  in idr_mark_full()
140 	int l, id, oid;  in sub_alloc()  local
143 	id = *starting_id;  in sub_alloc()
152 		n = (id >> (IDR_BITS*l)) & IDR_MASK;  in sub_alloc()
158 			oid = id;  in sub_alloc()
159 			id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;  in sub_alloc()
162 			if (id >= 1 << (idp->layers * IDR_BITS)) {  in sub_alloc()
163 				*starting_id = id;  in sub_alloc()
173 			if (oid >> sh == id >> sh)  in sub_alloc()
180 			id = ((id >> sh) ^ n ^ m) << sh;  in sub_alloc()
182 		if ((id >= MAX_ID_BIT) || (id < 0))  in sub_alloc()
202 	return id;  in sub_alloc()
209 	int layers, v, id;  in idr_get_empty_slot()  local
212 	id = starting_id;  in idr_get_empty_slot()
224 	 * id is larger than the currently allocated space.  in idr_get_empty_slot()
226 	while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {  in idr_get_empty_slot()
260 	v = sub_alloc(idp, &id, pa);  in idr_get_empty_slot()
269 	int id;  in idr_get_new_above_int()  local
271 	id = idr_get_empty_slot(idp, starting_id, pa);  in idr_get_new_above_int()
272 	if (id >= 0) {  in idr_get_new_above_int()
277 		rcu_assign_pointer(pa[0]->ary[id & IDR_MASK],  in idr_get_new_above_int()
280 		idr_mark_full(pa, id);  in idr_get_new_above_int()
283 	return id;  in idr_get_new_above_int()
287  * idr_get_new_above - allocate new idr entry above or equal to a start id
289  * @ptr: pointer you want associated with the id
290  * @starting_id: id to start search at
291  * @id: pointer to the allocated handle
293  * This is the allocate id function.  It should be called with any
302  * @id returns a value in the range @starting_id ... %0x7fffffff
304 int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)  in idr_get_new_above()  argument
315 	*id = rv;  in idr_get_new_above()
323  * @ptr: pointer you want associated with the id
324  * @id: pointer to the allocated handle
332  * @id returns a value in the range %0 ... %0x7fffffff
334 int idr_get_new(struct idr *idp, void *ptr, int *id)  in idr_get_new()  argument
345 	*id = rv;  in idr_get_new()
350 static void idr_remove_warning(int id)  in idr_remove_warning()  argument
353 		"idr_remove called for id=%d which is not allocated.\n", id);  in idr_remove_warning()
357 static void sub_remove(struct idr *idp, int shift, int id)  in sub_remove()  argument
369 		n = (id >> shift) & IDR_MASK;  in sub_remove()
375 	n = id & IDR_MASK;  in sub_remove()
391 		idr_remove_warning(id);  in sub_remove()
395  * idr_remove - remove the given id and free its slot
397  * @id: unique key
399 void idr_remove(struct idr *idp, int id)  in idr_remove()  argument
405 	id &= MAX_ID_MASK;  in idr_remove()
407 	sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);  in idr_remove()
441  * function will remove all id mappings and leave all idp_layers
451 	int n, id, max;  in idr_remove_all()  local
462 	id = 0;  in idr_remove_all()
463 	while (id < max) {  in idr_remove_all()
467 			p = p->ary[(id >> n) & IDR_MASK];  in idr_remove_all()
470 		bt_mask = id;  in idr_remove_all()
471 		id += 1 << n;  in idr_remove_all()
473 		while (n < fls(id ^ bt_mask)) {  in idr_remove_all()
498  * idr_find - return pointer for given id
500  * @id: lookup key
502  * Return the pointer given the id it has been registered with.  A %NULL
503  * return indicates that @id is not valid or you passed %NULL in
509 void *idr_find(struct idr *idp, int id)  in idr_find()  argument
520 	id &= MAX_ID_MASK;  in idr_find()
522 	if (id >= (1 << n))  in idr_find()
529 		p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);  in idr_find()
543  * registered, passing the id, the pointer and the data pointer passed
554 		 int (*fn)(int id, void *p, void *data), void *data)  in idr_for_each()  argument
556 	int n, id, max, error = 0;  in idr_for_each()  local
565 	id = 0;  in idr_for_each()
566 	while (id < max) {  in idr_for_each()
570 			p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);  in idr_for_each()
574 			error = fn(id, (void *)p, data);  in idr_for_each()
579 		id += 1 << n;  in idr_for_each()
580 		while (n < fls(id)) {  in idr_for_each()
591  * idr_get_next - lookup next object of id to given id.
595  * Returns pointer to registered object with id, which is next number to
596  * given id. After being looked up, *@nextidp will be updated for the next
604 	int id = *nextidp;  in idr_get_next()  local
614 	while (id < max) {  in idr_get_next()
618 			p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);  in idr_get_next()
622 			*nextidp = id;  in idr_get_next()
626 		id += 1 << n;  in idr_get_next()
627 		while (n < fls(id)) {  in idr_get_next()
638  * idr_replace - replace pointer for given id
640  * @ptr: pointer you want associated with the id
641  * @id: lookup key
643  * Replace the pointer registered with an id and return the old value.
644  * A %-ENOENT return indicates that @id was not found.
645  * A %-EINVAL return indicates that @id was not within valid constraints.
649 void *idr_replace(struct idr *idp, void *ptr, int id)  in idr_replace()  argument
660 	id &= MAX_ID_MASK;  in idr_replace()
662 	if (id >= (1 << n))  in idr_replace()
667 		p = p->ary[(id >> n) & IDR_MASK];  in idr_replace()
671 	n = id & IDR_MASK;  in idr_replace()
705  * IDA - IDR based ID allocator
707  * This is id allocator without id -> pointer translation.  Memory
708  * usage is much lower than full blown idr because each id only
765  * ida_get_new_above - allocate new ID above or equal to a start id
767  * @starting_id: id to start search at
770  * Allocate new ID above or equal to @starting_id.  It should be called
786 	int t, id;  in ida_get_new_above()  local
827 	id = idr_id * IDA_BITMAP_BITS + t;  in ida_get_new_above()
828 	if (id >= MAX_ID_BIT)  in ida_get_new_above()
835 	*p_id = id;  in ida_get_new_above()
853  * ida_get_new - allocate new ID
857  * Allocate new ID.  It should be called with any required locks.
872  * ida_remove - remove the given ID
874  * @id:		ID to free
876 void ida_remove(struct ida *ida, int id)  in ida_remove()  argument
880 	int idr_id = id / IDA_BITMAP_BITS;  in ida_remove()
881 	int offset = id % IDA_BITMAP_BITS;  in ida_remove()
915 	       "ida_remove called for id=%d which is not allocated.\n", id);  in ida_remove()
931  * ida_simple_get - get a new id.
933  * @start: the minimum id (inclusive, < 0x8000000)
934  * @end: the maximum id (exclusive, < 0x8000000 or 0)
937  * Allocates an id in the range start <= id < end, or returns -ENOSPC.
940  * Use ida_simple_remove() to get rid of an id.
945 	int ret, id;  in ida_simple_get()  local
964 	ret = ida_get_new_above(ida, start, &id);  in ida_simple_get()
966 		if (id > max) {  in ida_simple_get()
967 			ida_remove(ida, id);  in ida_simple_get()
970 			ret = id;  in ida_simple_get()
983  * ida_simple_remove - remove an allocated id.
985  * @id: the id returned by ida_simple_get.
987 void ida_simple_remove(struct ida *ida, unsigned int id)  in ida_simple_remove()  argument
991 	BUG_ON((int)id < 0);  in ida_simple_remove()
993 	ida_remove(ida, id);  in ida_simple_remove()