linux-kernel - Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Tue, 27 Dec 2016 11:05:35 +0100
From:   Michal Hocko <mhocko@...nel.org>
To:     Jaewon Kim <jaewon31.kim@...sung.com>
Cc:     gregkh@...uxfoundation.org, akpm@...ux-foundation.org,
        labbott@...hat.com, mina86@...a86.com, m.szyprowski@...sung.com,
        gregory.0xf0@...il.com, laurent.pinchart@...asonboard.com,
        akinobu.mita@...il.com, linux-mm@...ck.org,
        linux-kernel@...r.kernel.org, jaewon31.kim@...il.com
Subject: Re: [PATCH] lib: bitmap: introduce
 bitmap_find_next_zero_area_and_size

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@...sung.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@...ck.org.  For more info on Linux MM,
> see: http://www.linux-mm.org/ .
> Don't email: <a href=mailto:"dont@...ck.org"> email@...ck.org </a>

-- 
Michal Hocko
SUSE Labs