From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753109Ab2EWMaL (ORCPT ); Wed, 23 May 2012 08:30:11 -0400 Received: from cantor2.suse.de ([195.135.220.15]:37388 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750880Ab2EWMaI (ORCPT ); Wed, 23 May 2012 08:30:08 -0400 Date: Wed, 23 May 2012 14:29:54 +0200 From: Jan Kara To: Akinobu Mita Cc: Jan Kara , linux-kernel@vger.kernel.org, akpm@linux-foundation.org, Anders Larsen , Alasdair Kergon , dm-devel@redhat.com, linux-fsdevel@vger.kernel.org, Laurent Pinchart , linux-media@vger.kernel.org, Mark Fasheh , Joel Becker , ocfs2-devel@oss.oracle.com, linux-ext4@vger.kernel.org, Andreas Dilger , "Theodore Ts'o" Subject: Re: [PATCH 01/10] string: introduce memweight Message-ID: <20120523122954.GA17135@quack.suse.cz> References: <1337520203-29147-1-git-send-email-akinobu.mita@gmail.com> <20120523092113.GG10452@quack.suse.cz> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Wed 23-05-12 21:12:18, Akinobu Mita wrote: > 2012/5/23 Jan Kara : > > On Sun 20-05-12 22:23:14, Akinobu Mita wrote: > >> memweight() is the function that counts the total number of bits set > >> in memory area.  The memory area doesn't need to be aligned to > >> long-word boundary unlike bitmap_weight(). > >  Thanks for the patch. I have some comments below. > > Thanks for the review. > > >> @@ -824,3 +825,39 @@ void *memchr_inv(const void *start, int c, size_t bytes) > >>       return check_bytes8(start, value, bytes % 8); > >>  } > >>  EXPORT_SYMBOL(memchr_inv); > >> + > >> +/** > >> + * memweight - count the total number of bits set in memory area > >> + * @ptr: pointer to the start of the area > >> + * @bytes: the size of the area > >> + */ > >> +size_t memweight(const void *ptr, size_t bytes) > >> +{ > >> +     size_t w = 0; > >> +     size_t longs; > >> +     union { > >> +             const void *ptr; > >> +             const unsigned char *b; > >> +             unsigned long address; > >> +     } bitmap; > >  Ugh, this is ugly and mostly unnecessary. Just use "const unsigned char > > *bitmap". > > > >> + > >> +     for (bitmap.ptr = ptr; bytes > 0 && bitmap.address % sizeof(long); > >> +                     bytes--, bitmap.address++) > >> +             w += hweight8(*bitmap.b); > >  This can be: > >        count = ((unsigned long)bitmap) % sizeof(long); > > The count should be the size of unaligned area and it can be greater than > bytes. So > > count = min(bytes, > sizeof(long) - ((unsigned long)bitmap) % sizeof(long)); You are right, I didn't quite think this through. > >        while (count--) { > >                w += hweight(*bitmap); > >                bitmap++; > >                bytes--; > >        } > >> + > >> +     for (longs = bytes / sizeof(long); longs > 0; ) { > >> +             size_t bits = min_t(size_t, INT_MAX & ~(BITS_PER_LONG - 1), > >> +                                     longs * BITS_PER_LONG); > >  I find it highly unlikely that someone would have such a large bitmap > > (256 MB or more on 32-bit). Also the condition as you wrote it can just > > overflow so it won't have the desired effect. Just do > >        BUG_ON(longs >= ULONG_MAX / BITS_PER_LONG); > > The bits argument of bitmap_weight() is int type. So this should be > > BUG_ON(longs >= INT_MAX / BITS_PER_LONG); OK, I didn't check and thought it's size_t. > > and remove the loop completely. If someone comes with such a huge bitmap, > > the code can be modified easily (after really closely inspecting whether > > such a huge bitmap is really well justified). > > size_t memweight(const void *ptr, size_t bytes) > { > size_t w = 0; > size_t longs; > const unsigned char *bitmap = ptr; > > for (; bytes > 0 && ((unsigned long)bitmap) % sizeof(long); > bytes--, bitmap++) > w += hweight8(*bitmap); > > longs = bytes / sizeof(long); > BUG_ON(longs >= INT_MAX / BITS_PER_LONG); > w += bitmap_weight((unsigned long *)bitmap, longs * BITS_PER_LONG); > bytes -= longs * sizeof(long); > bitmap += longs * sizeof(long); > > for (; bytes > 0; bytes--, bitmap++) > w += hweight8(*bitmap); > > return w; > } Yup, this looks much more readable. Thanks! Honza -- Jan Kara SUSE Labs, CR