66 static struct idr_layer *get_from_free_list(struct idr *idp)  in get_from_free_list()  argument
71 	spin_lock_irqsave(&idp->lock, flags);  in get_from_free_list()
72 	if ((p = idp->id_free)) {  in get_from_free_list()
73 		idp->id_free = p->ary[0];  in get_from_free_list()
74 		idp->id_free_cnt--;  in get_from_free_list()
77 	spin_unlock_irqrestore(&idp->lock, flags);  in get_from_free_list()
153 static void __move_to_free_list(struct idr *idp, struct idr_layer *p)  in __move_to_free_list()  argument
155 	p->ary[0] = idp->id_free;  in __move_to_free_list()
156 	idp->id_free = p;  in __move_to_free_list()
157 	idp->id_free_cnt++;  in __move_to_free_list()
160 static void move_to_free_list(struct idr *idp, struct idr_layer *p)  in move_to_free_list()  argument
167 	spin_lock_irqsave(&idp->lock, flags);  in move_to_free_list()
168 	__move_to_free_list(idp, p);  in move_to_free_list()
169 	spin_unlock_irqrestore(&idp->lock, flags);  in move_to_free_list()
192 static int __idr_pre_get(struct idr *idp, gfp_t gfp_mask)  in __idr_pre_get()  argument
194 	while (idp->id_free_cnt < MAX_IDR_FREE) {  in __idr_pre_get()
199 		move_to_free_list(idp, new);  in __idr_pre_get()
220 static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa,  in sub_alloc()  argument
229 	p = idp->top;  in sub_alloc()
230 	l = idp->layers;  in sub_alloc()
245 			if (id > idr_max(idp->layers)) {  in sub_alloc()
289 static int idr_get_empty_slot(struct idr *idp, int starting_id,  in idr_get_empty_slot()  argument
299 	p = idp->top;  in idr_get_empty_slot()
300 	layers = idp->layers;  in idr_get_empty_slot()
327 			spin_lock_irqsave(&idp->lock, flags);  in idr_get_empty_slot()
328 			for (new = p; p && p != idp->top; new = p) {  in idr_get_empty_slot()
333 				__move_to_free_list(idp, new);  in idr_get_empty_slot()
335 			spin_unlock_irqrestore(&idp->lock, flags);  in idr_get_empty_slot()
346 	rcu_assign_pointer(idp->top, p);  in idr_get_empty_slot()
347 	idp->layers = layers;  in idr_get_empty_slot()
348 	v = sub_alloc(idp, &id, pa, gfp_mask, layer_idr);  in idr_get_empty_slot()
508 static void sub_remove(struct idr *idp, int shift, int id)  in sub_remove()  argument
510 	struct idr_layer *p = idp->top;  in sub_remove()
517 	*++paa = &idp->top;  in sub_remove()
533 				free_layer(idp, to_free);  in sub_remove()
538 			idp->layers = 0;  in sub_remove()
540 			free_layer(idp, to_free);  in sub_remove()
550 void idr_remove(struct idr *idp, int id)  in idr_remove()  argument
558 	if (id > idr_max(idp->layers)) {  in idr_remove()
563 	sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);  in idr_remove()
564 	if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&  in idr_remove()
565 	    idp->top->ary[0]) {  in idr_remove()
572 		to_free = idp->top;  in idr_remove()
573 		p = idp->top->ary[0];  in idr_remove()
574 		rcu_assign_pointer(idp->top, p);  in idr_remove()
575 		--idp->layers;  in idr_remove()
578 		free_layer(idp, to_free);  in idr_remove()
583 static void __idr_remove_all(struct idr *idp)  in __idr_remove_all()  argument
591 	n = idp->layers * IDR_BITS;  in __idr_remove_all()
592 	*paa = idp->top;  in __idr_remove_all()
593 	RCU_INIT_POINTER(idp->top, NULL);  in __idr_remove_all()
594 	max = idr_max(idp->layers);  in __idr_remove_all()
610 				free_layer(idp, *paa);  in __idr_remove_all()
615 	idp->layers = 0;  in __idr_remove_all()
631 void idr_destroy(struct idr *idp)  in idr_destroy()  argument
633 	__idr_remove_all(idp);  in idr_destroy()
635 	while (idp->id_free_cnt) {  in idr_destroy()
636 		struct idr_layer *p = get_from_free_list(idp);  in idr_destroy()
642 void *idr_find_slowpath(struct idr *idp, int id)  in idr_find_slowpath()  argument
650 	p = rcu_dereference_raw(idp->top);  in idr_find_slowpath()
686 int idr_for_each(struct idr *idp,  in idr_for_each()  argument
694 	n = idp->layers * IDR_BITS;  in idr_for_each()
695 	*paa = rcu_dereference_raw(idp->top);  in idr_for_each()
696 	max = idr_max(idp->layers);  in idr_for_each()
736 void *idr_get_next(struct idr *idp, int *nextidp)  in idr_get_next()  argument
744 	p = *paa = rcu_dereference_raw(idp->top);  in idr_get_next()
793 void *idr_replace(struct idr *idp, void *ptr, int id)  in idr_replace()  argument
801 	p = idp->top;  in idr_replace()
838 void idr_init(struct idr *idp)  in idr_init()  argument
840 	memset(idp, 0, sizeof(struct idr));  in idr_init()
841 	spin_lock_init(&idp->lock);  in idr_init()
850 bool idr_is_empty(struct idr *idp)  in idr_is_empty()  argument
852 	return !idr_for_each(idp, idr_has_entry, NULL);  in idr_is_empty()