2 #include <linux/bitmap.h>
336  * each entry.  The XA_FREE_MARK is only cleared when all bits in the bitmap
343  * leaf bitmap before doing a radix tree lookup.
346  * leaf, instead of allocating a 128-byte bitmap, we store the bits
348  * because we can always convert them into a bitmap entry.
351  * single 128-byte bitmap, we currently switch to a 576-byte node, put
352  * the 128-byte bitmap in the first entry and then start allocating extra
354  * data as a bitmap before moving to that scheme.  I do not believe this
363  * RCU head in the bitmap, which adds a 2-pointer overhead to each 128-byte
364  * bitmap, which is excessive.
388 	struct ida_bitmap *bitmap, *alloc = NULL;  in ida_alloc_range()  local
399 	bitmap = xas_find_marked(&xas, max / IDA_BITMAP_BITS, XA_FREE_MARK);  in ida_alloc_range()
405 	if (xa_is_value(bitmap)) {  in ida_alloc_range()
406 		unsigned long tmp = xa_to_value(bitmap);  in ida_alloc_range()
418 		bitmap = alloc;  in ida_alloc_range()
419 		if (!bitmap)  in ida_alloc_range()
420 			bitmap = kzalloc_obj(*bitmap, GFP_NOWAIT);  in ida_alloc_range()
421 		if (!bitmap)  in ida_alloc_range()
423 		bitmap->bitmap[0] = tmp;  in ida_alloc_range()
424 		xas_store(&xas, bitmap);  in ida_alloc_range()
426 			bitmap->bitmap[0] = 0;  in ida_alloc_range()
431 	if (bitmap) {  in ida_alloc_range()
432 		bit = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, bit);  in ida_alloc_range()
438 		__set_bit(bit, bitmap->bitmap);  in ida_alloc_range()
439 		if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS))  in ida_alloc_range()
443 			bitmap = xa_mk_value(1UL << bit);  in ida_alloc_range()
445 			bitmap = alloc;  in ida_alloc_range()
446 			if (!bitmap)  in ida_alloc_range()
447 				bitmap = kzalloc_obj(*bitmap, GFP_NOWAIT);  in ida_alloc_range()
448 			if (!bitmap)  in ida_alloc_range()
450 			__set_bit(bit, bitmap->bitmap);  in ida_alloc_range()
452 		xas_store(&xas, bitmap);  in ida_alloc_range()
461 	if (bitmap != alloc)  in ida_alloc_range()
468 	alloc = kzalloc_obj(*bitmap, gfp);  in ida_alloc_range()
528 		addr = ((struct ida_bitmap *)entry)->bitmap;  in ida_find_first_range()
560 	struct ida_bitmap *bitmap;  in ida_free()  local
567 	bitmap = xas_load(&xas);  in ida_free()
569 	if (xa_is_value(bitmap)) {  in ida_free()
570 		unsigned long v = xa_to_value(bitmap);  in ida_free()
580 		if (!bitmap || !test_bit(bit, bitmap->bitmap))  in ida_free()
582 		__clear_bit(bit, bitmap->bitmap);  in ida_free()
584 		if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) {  in ida_free()
585 			kfree(bitmap);  in ida_free()
613 	struct ida_bitmap *bitmap;  in ida_destroy()  local
617 	xas_for_each(&xas, bitmap, ULONG_MAX) {  in ida_destroy()
618 		if (!xa_is_value(bitmap))  in ida_destroy()
619 			kfree(bitmap);  in ida_destroy()
651 		struct ida_bitmap *bitmap = entry;  in ida_dump_entry()  local
654 		pr_cont("bitmap: %p data", bitmap);  in ida_dump_entry()
656 			pr_cont(" %lx", bitmap->bitmap[i]);  in ida_dump_entry()