Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size

From: Jaewon Kim
Date: Mon Dec 26 2016 - 23:14:06 EST




On 2016ë 12ì 27ì 06:09, Michal Nazarewicz wrote:
> On Mon, Dec 26 2016, Jaewon Kim wrote:
>> There was no bitmap API which returns both next zero index and size of zeros
>> from that index.
> Is it really needed? Does it noticeably simplifies callers? Why canât
> caller get the size by themselves if they need it?
Hi thank you for your comment.
As some other functions, this is a helper function to use easily.
Without this patch, we can get the size by using two bitmap functions.
>> This is helpful to look fragmentation. This is an test code to look size of zeros.
>> Test result is '10+9+994=>1013 found of total: 1024'
>>
>> unsigned long search_idx, found_idx, nr_found_tot;
>> unsigned long bitmap_max;
>> unsigned int nr_found;
>> unsigned long *bitmap;
>>
>> search_idx = nr_found_tot = 0;
>> bitmap_max = 1024;
>> bitmap = kzalloc(BITS_TO_LONGS(bitmap_max) * sizeof(long),
>> GFP_KERNEL);
>>
>> /* test bitmap_set offset, count */
>> bitmap_set(bitmap, 10, 1);
>> bitmap_set(bitmap, 20, 10);
>>
>> for (;;) {
>> found_idx = bitmap_find_next_zero_area_and_size(bitmap,
>> bitmap_max, search_idx, &nr_found);
>> if (found_idx >= bitmap_max)
>> break;
>> if (nr_found_tot == 0)
>> printk("%u", nr_found);
>> else
>> printk("+%u", nr_found);
>> nr_found_tot += nr_found;
>> search_idx = found_idx + nr_found;
>> }
>> printk("=>%lu found of total: %lu\n", nr_found_tot, bitmap_max);
>>
>> Signed-off-by: Jaewon Kim <jaewon31.kim@xxxxxxxxxxx>
>> ---
>> include/linux/bitmap.h | 6 ++++++
>> lib/bitmap.c | 25 +++++++++++++++++++++++++
>> 2 files changed, 31 insertions(+)
>>
>> diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
>> index 3b77588..b724a6c 100644
>> --- a/include/linux/bitmap.h
>> +++ b/include/linux/bitmap.h
>> @@ -46,6 +46,7 @@
>> * bitmap_clear(dst, pos, nbits) Clear specified bit area
>> * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area
>> * bitmap_find_next_zero_area_off(buf, len, pos, n, mask) as above
>> + * bitmap_find_next_zero_area_and_size(buf, len, pos, n, mask) Find bit free area and its size
>> * bitmap_shift_right(dst, src, n, nbits) *dst = *src >> n
>> * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n
>> * bitmap_remap(dst, src, old, new, nbits) *dst = map(old, new)(src)
>> @@ -123,6 +124,11 @@ extern unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
>> unsigned long align_mask,
>> unsigned long align_offset);
>>
>> +extern unsigned long bitmap_find_next_zero_area_and_size(unsigned long *map,
>> + unsigned long size,
>> + unsigned long start,
>> + unsigned int *nr);
>> +
>> /**
>> * bitmap_find_next_zero_area - find a contiguous aligned zero area
>> * @map: The address to base the search on
>> diff --git a/lib/bitmap.c b/lib/bitmap.c
>> index 0b66f0e..d02817c 100644
>> --- a/lib/bitmap.c
>> +++ b/lib/bitmap.c
>> @@ -332,6 +332,31 @@ unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
>> }
>> EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
>>
>> +/**
>> + * bitmap_find_next_zero_area_and_size - find a contiguous aligned zero area
>> + * @map: The address to base the search on
>> + * @size: The bitmap size in bits
>> + * @start: The bitnumber to start searching at
>> + * @nr: The number of zeroed bits we've found
>> + */
>> +unsigned long bitmap_find_next_zero_area_and_size(unsigned long *map,
>> + unsigned long size,
>> + unsigned long start,
>> + unsigned int *nr)
>> +{
>> + unsigned long index, i;
>> +
>> + *nr = 0;
>> + index = find_next_zero_bit(map, size, start);
>> +
>> + if (index >= size)
>> + return index;
>> + i = find_next_bit(map, size, index);
>> + *nr = i - index;
>> + return index;
>> +}
>> +EXPORT_SYMBOL(bitmap_find_next_zero_area_and_size);
>> +
>> /*
>> * Bitmap printing & parsing functions: first version by Nadia Yvette Chambers,
>> * second version by Paul Jackson, third by Joe Korty.
>> --
>> 1.9.1
>>