From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1750986AbdAQDXY (ORCPT ); Mon, 16 Jan 2017 22:23:24 -0500 Received: from mailout3.samsung.com ([203.254.224.33]:42702 "EHLO mailout3.samsung.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750787AbdAQDXW (ORCPT ); Mon, 16 Jan 2017 22:23:22 -0500 MIME-version: 1.0 Content-type: text/plain; charset=UTF-8 X-AuditID: b6c32a39-f793d6d000000fd7-e0-587d8dc77b6f Content-transfer-encoding: 8BIT Subject: Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size To: Yury Norov Cc: gregkh@linuxfoundation.org, akpm@linux-foundation.org, 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 From: Jaewon Kim Message-id: <587D8DE5.6040408@samsung.com> Date: Tue, 17 Jan 2017 12:22:13 +0900 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.7.2 In-reply-to: <20170115071726.GB6474@yury-N73SV> X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFtrNJsWRmVeSWpSXmKPExsWy7bCmvu7x3toIgzcbxCxeHehgtJizfg2b RfPi9WwW06ZvYLXo3jyT0WLlnh9MFp0Tl7BbXN41h83i3pr/rBZrj9xlt1hwvIXV4nTjfWYH Ho8NJ/pZPXbOusvuMbtjJqvHpk+T2D1OzPjN4rF/7hp2j3V/XjF5vN93lc2jb8sqRo/Pm+QC uKJSbTJSE1NSixRS85LzUzLz0m2VvIPjneNNzQwMdQ0tLcyVFPISc1NtlVx8AnTdMnOADldS KEvMKQUKBSQWFyvp29kU5ZeWpCpk5BeX2CpFGxoa6RkamOsZGRnpmZjHWhmZApUkpGas/nSX rWCSaMXV7f8YGxj/CHQxcnJICJhIXHlxkQ3CFpO4cG89kM3FISSwg1Hi8ca97BBOO5PE46ez WGE6mjccY4JILGeU2HZzKViCV0BQ4sfkeyxdjBwczALyEkcuZYOEmQU0JbbuXg816D6jxPMd s5lBEsICgRJvFq5nArFFBLQkpu3dAFbELDCfSWLzgm6woWwC2hLvF0yCWqAl8fbhaxYQm0VA VWJKewfY3aICERI75n5kBLE5BfQlLu66B3adhMBfdolD/fuZQC6SEJCV2HSAGeIDF4nV589A fSMs8er4FnYIW1pi1b9bUL39jBKbFjYwQzg9jBId89uhuo0lensuMEP8xifx7msPK8QCXomO NiGIEg+JTe/Ws0DYjhIf/u9hhnj/IKPEoytTWCcwys9CCrFZiBCbhRRiCxiZVzGKpRYU56an FhsWmOoVJ+YWl+al6yXn525iBCdcLcsdjMfO+RxiFOBgVOLhnXG3JkKINbGsuDL3EKMEB7OS CG9GV22EEG9KYmVValF+fFFpTmrxIUZTYPhNZJYSTc4HZoO8knhDE3MLc3MzE2NDC3NTJXHe xY3WEUIC6YklqdmpqQWpRTB9TBycUg2MnXdSwuIiPZRnnGsR2LervHTK9vDXq/bUr2X70RHR nnSm8NYMIQebgBzVY39PvOSve+nuwbpy7b7yWRb+zWp8QQJhivxvJffMduzjzBPNF9n++c2u slmn3mzICsm/9/ZqT9CcbRPvuP22l7pxfu+PvNM1VwxXWfivstp2qO/tr9Opm3ZVfbDar8RS nJFoqMVcVJwIAGldLrrOAwAA X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFnrOIsWRmVeSWpSXmKPExsVy+t9jAd3jvbURBlfes1u8OtDBaDFn/Ro2 i+bF69kspk3fwGrRvXkmo8XKPT+YLDonLmG3uLxrDpvFvTX/WS3WHrnLbrHgeAurxenG+8wO PB4bTvSzeuycdZfdY3bHTFaPTZ8msXucmPGbxWP/3DXsHuv+vGLyeL/vKptH35ZVjB6fN8kF cEW52WSkJqakFimk5iXnp2TmpdsqhYa46VooKeQl5qbaKkXo+oYEKSmUJeaUAnlGBmjAwTnA PVhJ3y7BLWP1p7tsBZNEK65u/8fYwPhHoIuRk0NCwESiecMxJghbTOLCvfVsXYxcHEICSxkl Hm29ywiS4BUQlPgx+R5LFyMHB7OAvMSRS9kgYWYBdYlJ8xYxQ9Q/ZJT49eAX2CBhAX+Jnrdb mEFsEQEtiWl7N7BDFB1mlJi+8yQLiMMsMJdJ4njfcnaQKjYBbYn3CyaxQmzTknj78DULiM0i oCoxpb2DDcQWFYiQWL3uGthUTgF9iYu77jFNYBSYheTAWQgHzkJy4AJG5lWMEqkFyQXFSem5 hnmp5XrFibnFpXnpesn5uZsYwZH8TGoH48Fd7ocYBTgYlXh4CwJqI4RYE8uKK3MPMUpwMCuJ 8GZ0AYV4UxIrq1KL8uOLSnNSiw8xmgLdOJFZSjQ5H5hk8kriDU3MTcyNDSzMLS1NjJTEeRtn PwsXEkhPLEnNTk0tSC2C6WPi4JRqYFzwYunj0tWc4eHOqx8G3XvWLrZ2KY9l7xw9mzR/lwtn VLy+1u/vq/g8lzvvRU2v5D+hE9FL327Tidq94+26f/XXjuTMyVjkbK7PdNVG+Fd9mvb6koDe D48cHq20ilqjpuOcnOFsn/Zlo7rNsXWfOs03B6lVL7N21yn4cvPRIv4NB9dlbON5/FKJpTgj 0VCLuag4EQDFHMTU+gIAAA== X-MTR: 20000000000000000@CPGS X-CMS-MailID: 20170117032143epcas1p45c76e6742748f9a57d8abf3cebf7ca86 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> <20170115071726.GB6474@yury-N73SV> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 > 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. > > > From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pg0-f72.google.com (mail-pg0-f72.google.com [74.125.83.72]) by kanga.kvack.org (Postfix) with ESMTP id 0CB886B0033 for ; Mon, 16 Jan 2017 22:21:51 -0500 (EST) Received: by mail-pg0-f72.google.com with SMTP id t6so89267733pgt.6 for ; Mon, 16 Jan 2017 19:21:51 -0800 (PST) Received: from mailout3.samsung.com (mailout3.samsung.com. [203.254.224.33]) by mx.google.com with ESMTPS id 21si15883312pga.271.2017.01.16.19.21.49 for (version=TLS1 cipher=AES128-SHA bits=128/128); Mon, 16 Jan 2017 19:21:49 -0800 (PST) MIME-version: 1.0 Content-type: text/plain; charset=UTF-8 Received: from epcas1p2.samsung.com (unknown [182.195.41.46]) by mailout3.samsung.com (Oracle Communications Messaging Server 7.0.5.31.0 64bit (built May 5 2014)) with ESMTP id <0OJW01SLNMO7E150@mailout3.samsung.com> for linux-mm@kvack.org; Tue, 17 Jan 2017 12:21:43 +0900 (KST) Content-transfer-encoding: 8BIT Subject: Re: [PATCH] lib: bitmap: introduce bitmap_find_next_zero_area_and_size From: Jaewon Kim Message-id: <587D8DE5.6040408@samsung.com> Date: Tue, 17 Jan 2017 12:22:13 +0900 In-reply-to: <20170115071726.GB6474@yury-N73SV> References: <1482725891-10866-1-git-send-email-jaewon31.kim@samsung.com> <20170115071726.GB6474@yury-N73SV> Sender: owner-linux-mm@kvack.org List-ID: To: Yury Norov Cc: gregkh@linuxfoundation.org, akpm@linux-foundation.org, 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 On 2017e?? 01i?? 15i? 1/4 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 > 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. > > > -- 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: email@kvack.org