From: Jaewon Kim <jaewon31.kim@samsung.com> To: gregkh@linuxfoundation.org, akpm@linux-foundation.org Cc: labbott@redhat.com, mina86@mina86.com, m.szyprowski@samsung.com, gregory.0xf0@gmail.com, laurent.pinchart@ideasonboard.com, akinobu.mita@gmail.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org, jaewon31.kim@gmail.com, Jaewon Kim <jaewon31.kim@samsung.com> Subject: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size Date: Mon, 26 Dec 2016 13:18:11 +0900 [thread overview] Message-ID: <1482725891-10866-1-git-send-email-jaewon31.kim@samsung.com> (raw) In-Reply-To: CGME20161226041809epcas5p1981244de55764c10f1a80d80346f3664@epcas5p1.samsung.com 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
WARNING: multiple messages have this Message-ID (diff)
From: Jaewon Kim <jaewon31.kim@samsung.com> To: gregkh@linuxfoundation.org, akpm@linux-foundation.org Cc: labbott@redhat.com, mina86@mina86.com, m.szyprowski@samsung.com, gregory.0xf0@gmail.com, laurent.pinchart@ideasonboard.com, akinobu.mita@gmail.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org, jaewon31.kim@gmail.com, Jaewon Kim <jaewon31.kim@samsung.com> Subject: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size Date: Mon, 26 Dec 2016 13:18:11 +0900 [thread overview] Message-ID: <1482725891-10866-1-git-send-email-jaewon31.kim@samsung.com> (raw) In-Reply-To: CGME20161226041809epcas5p1981244de55764c10f1a80d80346f3664@epcas5p1.samsung.com 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 -- 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>
next parent reply other threads:[~2016-12-26 4:18 UTC|newest] Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top [not found] <CGME20161226041809epcas5p1981244de55764c10f1a80d80346f3664@epcas5p1.samsung.com> 2016-12-26 4:18 ` Jaewon Kim [this message] 2016-12-26 4:18 ` [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size Jaewon Kim 2016-12-26 21:09 ` Michal Nazarewicz 2016-12-26 21:09 ` Michal Nazarewicz 2016-12-27 4:14 ` Jaewon Kim 2016-12-27 4:14 ` Jaewon Kim 2016-12-27 10:05 ` Michal Hocko 2016-12-27 10:05 ` Michal Hocko 2016-12-28 4:41 ` Jaewon Kim 2016-12-28 4:41 ` Jaewon Kim 2016-12-28 8:32 ` Michal Hocko 2016-12-28 8:32 ` Michal Hocko 2016-12-28 14:14 ` Michal Nazarewicz 2016-12-28 14:14 ` Michal Nazarewicz 2016-12-29 2:13 ` Jaewon Kim 2016-12-29 2:13 ` Jaewon Kim 2017-01-15 7:17 ` Yury Norov 2017-01-15 7:17 ` Yury Norov 2017-01-17 3:22 ` Jaewon Kim 2017-01-17 3:22 ` Jaewon Kim 2017-01-16 17:59 ` Andy Shevchenko 2017-01-16 17:59 ` Andy Shevchenko
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=1482725891-10866-1-git-send-email-jaewon31.kim@samsung.com \ --to=jaewon31.kim@samsung.com \ --cc=akinobu.mita@gmail.com \ --cc=akpm@linux-foundation.org \ --cc=gregkh@linuxfoundation.org \ --cc=gregory.0xf0@gmail.com \ --cc=jaewon31.kim@gmail.com \ --cc=labbott@redhat.com \ --cc=laurent.pinchart@ideasonboard.com \ --cc=linux-kernel@vger.kernel.org \ --cc=linux-mm@kvack.org \ --cc=m.szyprowski@samsung.com \ --cc=mina86@mina86.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.