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 Content-Length: 3567 Lines: 102 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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/