[PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size

[PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size

[Jaewon Kim]

There was no bitmap API which returns both next zero index and size of zeros
from that index.

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@samsung.com>
---
 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

Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size

[Michal Nazarewicz]

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?

>
> 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@samsung.com>
> ---
>  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
>

-- 
Best regards
ミハウ “𝓶𝓲𝓷𝓪86” ナザレヴイツ
«If at first you don’t succeed, give up skydiving»

Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size

[Jaewon Kim]

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@samsung.com>
>> ---
>>  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
>>

Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size

[Michal Hocko]

On Mon 26-12-16 13:18:11, Jaewon Kim wrote:
> There was no bitmap API which returns both next zero index and size of zeros
> from that index.
> 
> 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);

Who is going to use this function? I do not see any caller introduced by
this patch.

> Signed-off-by: Jaewon Kim <jaewon31.kim@samsung.com>
> ---
>  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
> 
> --
> To unsubscribe, send a message with 'unsubscribe linux-mm' in
> the body to majordomo@kvack.org.  For more info on Linux MM,
> see: http://www.linux-mm.org/ .
> Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

-- 
Michal Hocko
SUSE Labs

Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size

[Jaewon Kim]

On 2016년 12월 27일 19:05, Michal Hocko wrote:
> On Mon 26-12-16 13:18:11, Jaewon Kim wrote:
>> There was no bitmap API which returns both next zero index and size of zeros
>> from that index.
>>
>> 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);
> Who is going to use this function? I do not see any caller introduced by
> this patch.
Hi
I did not add caller in this patch.
I am using the patch in cma_alloc function like below to show available page status.
+               printk("number of available pages: ");
+               start = 0;
+               for (;;) {
+                       bitmap_no = bitmap_find_next_zero_area_and_size(cma->bitmap,
+                                               cma->count, start, &nr);
+                       if (bitmap_no >= cma->count)
+                               break;
+                       if (nr_total == 0)
+                               printk("%u", nr);
+                       else
+                               printk("+%u", nr);
+                       nr_total += nr;
+                       start = bitmap_no + nr;
+               }
+               printk("=>%u pages, total: %lu pages\n", nr_total, cma->count);
>
>> Signed-off-by: Jaewon Kim <jaewon31.kim@samsung.com>
>> ---
>>  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
>>
>> --
>> To unsubscribe, send a message with 'unsubscribe linux-mm' in
>> the body to majordomo@kvack.org.  For more info on Linux MM,
>> see: http://www.linux-mm.org/ .
>> Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size

[Michal Hocko]

On Wed 28-12-16 13:41:24, Jaewon Kim wrote:
> 
> 
> On 2016년 12월 27일 19:05, Michal Hocko wrote:
[...]
> > Who is going to use this function? I do not see any caller introduced by
> > this patch.
>
> Hi
> I did not add caller in this patch.

it is preferable to add the caller(s) in the same patch to see the
benefit of the new helper.
-- 
Michal Hocko
SUSE Labs

Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size

[Michal Nazarewicz]

On Wed, Dec 28 2016, Jaewon Kim wrote:
> I did not add caller in this patch.
> I am using the patch in cma_alloc function like below to show
> available page status.
>
> +               printk("number of available pages: ");
> +               start = 0;
> +               for (;;) {
> +                       bitmap_no = bitmap_find_next_zero_area_and_size(cma->bitmap,
> +                                               cma->count, start, &nr);
> +                       if (bitmap_no >= cma->count)
> +                               break;
> +                       if (nr_total == 0)
> +                               printk("%u", nr);
> +                       else
> +                               printk("+%u", nr);
> +                       nr_total += nr;
> +                       start = bitmap_no + nr;
> +               }
> +               printk("=>%u pages, total: %lu pages\n", nr_total, cma->count);

I would be happier should you find other existing places where this
function can be used.  With just one caller, I’m not convinced it is
worth it.

>>> Signed-off-by: Jaewon Kim <jaewon31.kim@samsung.com>

The code itself is good, so

Acked-by: Michal Nazarewicz <mina86@mina86.com>

and I’ll leave deciding whether it improves the kernel overall to
maintainers. ;)

>>> ---
>>>  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 would remove this check.  find_next_bit handles situation when index
== size and without this early return, *nr is always set.

>>> +	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
>>>
>>> --
>>> To unsubscribe, send a message with 'unsubscribe linux-mm' in
>>> the body to majordomo@kvack.org.  For more info on Linux MM,
>>> see: http://www.linux-mm.org/ .
>>> Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
>

-- 
Best regards
ミハウ “𝓶𝓲𝓷𝓪86” ナザレヴイツ
«If at first you don’t succeed, give up skydiving»

Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size

[Jaewon Kim]

Hello Mical Hocko and Michal Nazarewicz

Thank you for your comment.
I agree with you on that the new bitmap API may not be used widely yet.
Let me give up the bitmap API and resend another patch regarding CMA allocation failure.

Thank you.

On 2016년 12월 28일 23:14, Michal Nazarewicz wrote:
> On Wed, Dec 28 2016, Jaewon Kim wrote:
>> I did not add caller in this patch.
>> I am using the patch in cma_alloc function like below to show
>> available page status.
>>
>> +               printk("number of available pages: ");
>> +               start = 0;
>> +               for (;;) {
>> +                       bitmap_no = bitmap_find_next_zero_area_and_size(cma->bitmap,
>> +                                               cma->count, start, &nr);
>> +                       if (bitmap_no >= cma->count)
>> +                               break;
>> +                       if (nr_total == 0)
>> +                               printk("%u", nr);
>> +                       else
>> +                               printk("+%u", nr);
>> +                       nr_total += nr;
>> +                       start = bitmap_no + nr;
>> +               }
>> +               printk("=>%u pages, total: %lu pages\n", nr_total, cma->count);
> I would be happier should you find other existing places where this
> function can be used.  With just one caller, I’m not convinced it is
> worth it.
>
>>>> Signed-off-by: Jaewon Kim <jaewon31.kim@samsung.com>
> The code itself is good, so
>
> Acked-by: Michal Nazarewicz <mina86@mina86.com>
>
> and I’ll leave deciding whether it improves the kernel overall to
> maintainers. ;)
>
>>>> ---
>>>>  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 would remove this check.  find_next_bit handles situation when index
> == size and without this early return, *nr is always set.
>
>>>> +	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
>>>>
>>>> --
>>>> To unsubscribe, send a message with 'unsubscribe linux-mm' in
>>>> the body to majordomo@kvack.org.  For more info on Linux MM,
>>>> see: http://www.linux-mm.org/ .
>>>> Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size

[Yury Norov]

Hi Jaewon,

with all comments above, some of my concerns.

On Mon, Dec 26, 2016 at 01:18:11PM +0900, Jaewon Kim wrote:
> There was no bitmap API which returns both next zero index and size of zeros
> from that index.

Yes, there is. Most probably because this function is not needed.
Typical usecase is looking for the area of N free bits, were caller
knows N, and doesn't care of free areas smaller than N. There is 
bitmap_find_next_zero_area() for exactly that.

> 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@samsung.com>

This usecase is problematic in real world. Consider 1-byte bitmap
'01010101'. To store fragmentation information for further analysis,
you have to allocate 4 pairs of address and size. On 64-bit machine
it's 64 bytes of additional memory. Brief grepping of kernel sources
shows that no one does it. Correct me if I missed something.

If you still think this API is useful, you'd walk over kernel
and find bins of code that will become better with your function,
and send the patch that adds the use of your function there. Probable
candidates for search are bitmap_find_next_zero_area() and find_next_bit()
functions.

If the only suitable place for new function is your example below, I
think it's better not to introduce new API and reconsider your
implementation instead.

Yury.

Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size

[Jaewon Kim]

On 2017년 01월 15일 16:17, Yury Norov wrote:
> Hi Jaewon,
>
> with all comments above, some of my concerns.
>
> On Mon, Dec 26, 2016 at 01:18:11PM +0900, Jaewon Kim wrote:
>> There was no bitmap API which returns both next zero index and size of zeros
>> from that index.
> Yes, there is. Most probably because this function is not needed.
> Typical usecase is looking for the area of N free bits, were caller
> knows N, and doesn't care of free areas smaller than N. There is 
> bitmap_find_next_zero_area() for exactly that.
Hi Yuri
Thank you for comment.
I did not mean finding free area but wanted to know its size.
So bitmap_find_next_zero_area is not what I wanted.
I will not submit this patch though.
>
>> 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@samsung.com>
> This usecase is problematic in real world. Consider 1-byte bitmap
> '01010101'. To store fragmentation information for further analysis,
> you have to allocate 4 pairs of address and size. On 64-bit machine
> it's 64 bytes of additional memory. Brief grepping of kernel sources
> shows that no one does it. Correct me if I missed something.
Sorry but I did not understand for "you have to allocate 4 pairs of address and size"
I used just local variables.
>
> If you still think this API is useful, you'd walk over kernel
> and find bins of code that will become better with your function,
> and send the patch that adds the use of your function there. Probable
> candidates for search are bitmap_find_next_zero_area() and find_next_bit()
> functions.
>
> If the only suitable place for new function is your example below, I
> think it's better not to introduce new API and reconsider your
> implementation instead.
>
> Yury.
>
>
>

Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size

[Andy Shevchenko]

On Mon, Dec 26, 2016 at 6:18 AM, Jaewon Kim <jaewon31.kim@samsung.com> wrote:
> There was no bitmap API which returns both next zero index and size of zeros
> from that index.
>
> 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);

Tests should be added to corresponding test module. See lib/*test*
files for details.

-- 
With Best Regards,
Andy Shevchenko