2 #include <linux/bitmap.h>
334  * each entry.  The XA_FREE_MARK is only cleared when all bits in the bitmap
341  * leaf bitmap before doing a radix tree lookup.
344  * leaf, instead of allocating a 128-byte bitmap, we store the bits
346  * because we can always convert them into a bitmap entry.
349  * single 128-byte bitmap, we currently switch to a 576-byte node, put
350  * the 128-byte bitmap in the first entry and then start allocating extra
352  * data as a bitmap before moving to that scheme.  I do not believe this
361  * RCU head in the bitmap, which adds a 2-pointer overhead to each 128-byte
362  * bitmap, which is excessive.
386 	struct ida_bitmap *bitmap, *alloc = NULL;  in ida_alloc_range()  local
397 	bitmap = xas_find_marked(&xas, max / IDA_BITMAP_BITS, XA_FREE_MARK);  in ida_alloc_range()
403 	if (xa_is_value(bitmap)) {  in ida_alloc_range()
404 		unsigned long tmp = xa_to_value(bitmap);  in ida_alloc_range()
416 		bitmap = alloc;  in ida_alloc_range()
417 		if (!bitmap)  in ida_alloc_range()
418 			bitmap = kzalloc(sizeof(*bitmap), GFP_NOWAIT);  in ida_alloc_range()
419 		if (!bitmap)  in ida_alloc_range()
421 		bitmap->bitmap[0] = tmp;  in ida_alloc_range()
422 		xas_store(&xas, bitmap);  in ida_alloc_range()
424 			bitmap->bitmap[0] = 0;  in ida_alloc_range()
429 	if (bitmap) {  in ida_alloc_range()
430 		bit = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, bit);  in ida_alloc_range()
436 		__set_bit(bit, bitmap->bitmap);  in ida_alloc_range()
437 		if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS))  in ida_alloc_range()
441 			bitmap = xa_mk_value(1UL << bit);  in ida_alloc_range()
443 			bitmap = alloc;  in ida_alloc_range()
444 			if (!bitmap)  in ida_alloc_range()
445 				bitmap = kzalloc(sizeof(*bitmap), GFP_NOWAIT);  in ida_alloc_range()
446 			if (!bitmap)  in ida_alloc_range()
448 			__set_bit(bit, bitmap->bitmap);  in ida_alloc_range()
450 		xas_store(&xas, bitmap);  in ida_alloc_range()
459 	if (bitmap != alloc)  in ida_alloc_range()
466 	alloc = kzalloc(sizeof(*bitmap), gfp);  in ida_alloc_range()
491 	struct ida_bitmap *bitmap;  in ida_free()  local
498 	bitmap = xas_load(&xas);  in ida_free()
500 	if (xa_is_value(bitmap)) {  in ida_free()
501 		unsigned long v = xa_to_value(bitmap);  in ida_free()
511 		if (!test_bit(bit, bitmap->bitmap))  in ida_free()
513 		__clear_bit(bit, bitmap->bitmap);  in ida_free()
515 		if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) {  in ida_free()
516 			kfree(bitmap);  in ida_free()
544 	struct ida_bitmap *bitmap;  in ida_destroy()  local
548 	xas_for_each(&xas, bitmap, ULONG_MAX) {  in ida_destroy()
549 		if (!xa_is_value(bitmap))  in ida_destroy()
550 			kfree(bitmap);  in ida_destroy()
582 		struct ida_bitmap *bitmap = entry;  in ida_dump_entry()  local
585 		pr_cont("bitmap: %p data", bitmap);  in ida_dump_entry()
587 			pr_cont(" %lx", bitmap->bitmap[i]);  in ida_dump_entry()