Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756360AbcL0ENo (ORCPT ); Mon, 26 Dec 2016 23:13:44 -0500 Received: from mailout3.samsung.com ([203.254.224.33]:56558 "EHLO mailout3.samsung.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755952AbcL0ENl (ORCPT ); Mon, 26 Dec 2016 23:13:41 -0500 MIME-version: 1.0 Content-type: text/plain; charset=utf-8 X-AuditID: b6c32a3c-f79646d000004d82-b9-5861ea72be12 Content-transfer-encoding: 8BIT Subject: Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size To: Michal Nazarewicz , gregkh@linuxfoundation.org, akpm@linux-foundation.org Cc: labbott@redhat.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 From: Jaewon Kim Message-id: <5861EA98.50606@samsung.com> Date: Tue, 27 Dec 2016 13:14:16 +0900 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.7.2 In-reply-to: X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFtrAJsWRmVeSWpSXmKPExsWy7bCmnm7Rq8QIg+9XdS1eHehgtJizfg2b RfPi9WwW06ZvYLXo3jyT0WLlnh9MFp0Tl7BbXN41h83i3pr/rBZrj9xlt1hwvIXVgdtj56y7 7B6zO2ayemz6NInd48SM3ywe++euYfdY9+cVk8f7fVfZPPq2rGL0+LxJLoAzKtUmIzUxJbVI ITUvOT8lMy/dVsk7ON453tTMwFDX0NLCXEkhLzE31VbJxSdA1y0zB+hcJYWyxJxSoFBAYnGx kr6dTVF+aUmqQkZ+cYmtUrShoZGeoYG5npGRkZ6JeayVkSlQSUJqxuGvZxgLpitUfLnaw9LA uF+yi5GTQ0LAROLkvlfMELaYxIV769m6GLk4hAR2MEq8frSCGcJpZ5L4/7+FCabj67sbYLaQ wBxGib2neUFsXgFBiR+T77F0MXJwMAvISxy5lA0SZhbQlHjxZRILxJz7jBLH1r5jA0kICwRK vFm4HmyOiECSxLIJe8A2MwtcZJRYfvQFWBGbgLbE+wWTWCEWaEjs+7oI7FQWAVWJaTNPsYPY ogIREjvmfmQEsTkFtCQm7nnMBDJIQuARu8Sf4w+YQC6SEJCV2HQA6k0XifML+lggbGGJV8e3 sEPY0hKr/t2C6u1nlNi0sIEZwulhlOiY3w7VbSzR23OBGeI3Pol3X3tYIRbwSnS0CUGUeEhs erceaoGjxIf/e6DBuIdRYmffH6YJjPKzkEJsFiLEZiGF2AJG5lWMYqkFxbnpqcWGBRZ6xYm5 xaV56XrJ+bmbGMGpVctmB+Olcz6HGAU4GJV4eBnWJ0YIsSaWFVfmHmKU4GBWEuE9cBsoxJuS WFmVWpQfX1Sak1p8iNEUGH4TmaVEk/OBaT+vJN7QxNzC3NzM1MTSwNBYSZx3WaN1hJBAemJJ anZqakFqEUwfEwenVAPj0uWywiYrbvJxJIhXPztWPKt73YQbKwTTTQ01rJwiw+a+/DCvoVx0 jWn4nQUMFuctNPYU7f6bUB2txfKx9J729quM0k9euvIvz/YNVe2UnhNx+t3Ea9+UzhybtPcc V5bOjcdHBeWT1sRd+5CXMmmtsog+U6zivpfxUZN5LN4pXi59OMn7MctLJZbijERDLeai4kQA Msr988MDAAA= X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFrrFIsWRmVeSWpSXmKPExsVy+t9jQd2iV4kRBssW8Vu8OtDBaDFn/Ro2 i+bF69kspk3fwGrRvXkmo8XKPT+YLDonLmG3uLxrDpvFvTX/WS3WHrnLbrHgeAurA7fHzll3 2T1md8xk9dj0aRK7x4kZv1k89s9dw+6x7s8rJo/3+66yefRtWcXo8XmTXABnlJtNRmpiSmqR Qmpecn5KZl66rVJoiJuuhZJCXmJuqq1ShK5vSJCSQlliTimQZ2SABhycA9yDlfTtEtwyDn89 w1gwXaHiy9UelgbG/ZJdjJwcEgImEl/f3WCCsMUkLtxbzwZiCwnMYpT4NVMQxOYVEJT4Mfke SxcjBwezgLzEkUvZEKa6xJQpuV2MXEDVDxklVl96wwxSLizgL9HzdguYLSKQJPH2xWF2iKJ9 jBK39x5iBXGYBS4ySjya8R1sGZuAtsT7BZNYIZZpSOz7ugism0VAVWLazFPsILaoQITE6nXX wOKcAloSE/c8ZprACHQlwn2zEO6bhXDfAkbmVYwSqQXJBcVJ6bmGeanlesWJucWleel6yfm5 mxjB8fpMagfjwV3uhxgFOBiVeHh/LE+MEGJNLCuuzD3EKMHBrCTCe+A2UIg3JbGyKrUoP76o NCe1+BCjKdCJE5mlRJPzgakkryTe0MTcxNzYwMLc0tLESEmct3H2s3AhgfTEktTs1NSC1CKY PiYOTqkGRiveMxXW9/n5tlZ7zyie4ry86b6FQL5lQMfXm0v3XL12UtXz110Vy9y3Z8549HeV xxh9X5O4+cmtI7eWS9Rw/klrzPjmsDJChuVyouDa1FMuxlwmdWcYbMy07k/QPR8qmuAhvCjk yoFeucV3qo8KGM2fu8+n/3qci3dGRnPeS36e6eFyd3vfKbEUZyQaajEXFScCAISgw53tAgAA X-MTR: 20000000000000000@CPGS X-CMS-MailID: 20161227041338epcas1p384c02731ef4bdac0552287e1d15862ba X-Msg-Generator: CA X-Sender-IP: 203.254.230.26 X-Local-Sender: =?UTF-8?B?6rmA7J6s7JuQG1N5c3RlbSBTL1fqsJzrsJwy6re466O5KA==?= =?UTF-8?B?66y07ISgKRvsgrzshLHsoITsnpAbUzUo7LGF7J6EKS/ssYXsnoQ=?= X-Global-Sender: =?UTF-8?B?SmFld29uIEtpbRtTeXN0ZW0gUy9XIFImRCBHcm91cCAyG1Nh?= =?UTF-8?B?bXN1bmcgRWxlY3Ryb25pY3MbUzUvU2VuaW9yIEVuZ2luZWVy?= X-Sender-Code: =?UTF-8?B?QzEwG1RFTEUbQzEwRDkxMjI=?= CMS-TYPE: 101P DLP-Filter: Pass X-CFilter-Loop: Reflected X-HopCount: 7 X-CMS-RootMailID: 20161226041809epcas5p1981244de55764c10f1a80d80346f3664 X-RootMTR: 20161226041809epcas5p1981244de55764c10f1a80d80346f3664 References: <1482725891-10866-1-git-send-email-jaewon31.kim@samsung.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 4010 Lines: 111 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 >> --- >> 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 >>