Ocfs2 devel - Jun 2012 - [PATCH v3 1/9] string: introduce memweight

memweight() is the function that counts the total number of bits set
in memory area.  Unlike bitmap_weight(), memweight() takes pointer
and size in bytes to specify a memory area which does not need to be
aligned to long-word boundary.

Signed-off-by: Akinobu Mita <akinobu.mita at gmail.com>
Cc: Anders Larsen <al at alarsen.net>
Cc: Alasdair Kergon <agk at redhat.com>
Cc: dm-devel at redhat.com
Cc: linux-fsdevel at vger.kernel.org
Cc: Laurent Pinchart <laurent.pinchart at ideasonboard.com>
Cc: linux-media at vger.kernel.org
Cc: Mark Fasheh <mfasheh at suse.com>
Cc: Joel Becker <jlbec at evilplan.org>
Cc: ocfs2-devel at oss.oracle.com
Cc: Jan Kara <jack at suse.cz>
Cc: linux-ext4 at vger.kernel.org
Cc: Andrew Morton <akpm at linux-foundation.org>
Cc: Andreas Dilger <adilger.kernel at dilger.ca>
Cc: "Theodore Ts'o" <tytso at mit.edu>
Cc: Matthew Wilcox <matthew at wil.cx>
---
v3: add comment for the last loop, adviced by Jan Kara
v2: simplify memweight(), adviced by Jan Kara

 include/linux/string.h |    3 +++
 lib/string.c           |   36 ++++++++++++++++++++++++++++++++++++
 2 files changed, 39 insertions(+), 0 deletions(-)

diff --git a/include/linux/string.h b/include/linux/string.h
index e033564..ffe0442 100644
--- a/include/linux/string.h
+++ b/include/linux/string.h
@@ -145,4 +145,7 @@ static inline bool strstarts(const char *str, const char
*prefix)
 	return strncmp(str, prefix, strlen(prefix)) == 0;
 }
 #endif
+
+extern size_t memweight(const void *ptr, size_t bytes);
+
 #endif /* _LINUX_STRING_H_ */
diff --git a/lib/string.c b/lib/string.c
index e5878de..e467186 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -26,6 +26,7 @@
 #include <linux/export.h>
 #include <linux/bug.h>
 #include <linux/errno.h>
+#include <linux/bitmap.h>
 
 #ifndef __HAVE_ARCH_STRNICMP
 /**
@@ -824,3 +825,38 @@ 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;
+	const unsigned char *bitmap = ptr;
+
+	for (; bytes > 0 && ((unsigned long)bitmap) % sizeof(long);
+			bytes--, bitmap++)
+		w += hweight8(*bitmap);
+
+	longs = bytes / sizeof(long);
+	if (longs) {
+		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);
+	}
+	/*
+	 * The reason that this last loop is distinct from the preceding
+	 * bitmap_weight() call is to compute 1-bits in the last region smaller
+	 * than sizeof(long) properly on big-endian systems.
+	 */
+	for (; bytes > 0; bytes--, bitmap++)
+		w += hweight8(*bitmap);
+
+	return w;
+}
+EXPORT_SYMBOL(memweight);
-- 
1.7.7.6

Use memweight to count the total number of bits set in memory area.

Signed-off-by: Akinobu Mita <akinobu.mita at gmail.com>
Cc: Mark Fasheh <mfasheh at suse.com>
Cc: Joel Becker <jlbec at evilplan.org>
Cc: ocfs2-devel at oss.oracle.com
---
No changes from v1

 fs/ocfs2/localalloc.c |    8 ++------
 1 files changed, 2 insertions(+), 6 deletions(-)

diff --git a/fs/ocfs2/localalloc.c b/fs/ocfs2/localalloc.c
index 210c352..a9f78c7 100644
--- a/fs/ocfs2/localalloc.c
+++ b/fs/ocfs2/localalloc.c
@@ -784,14 +784,10 @@ bail:
 
 static u32 ocfs2_local_alloc_count_bits(struct ocfs2_dinode *alloc)
 {
-	int i;
-	u8 *buffer;
-	u32 count = 0;
+	u32 count;
 	struct ocfs2_local_alloc *la = OCFS2_LOCAL_ALLOC(alloc);
 
-	buffer = la->la_bitmap;
-	for (i = 0; i < le16_to_cpu(la->la_size); i++)
-		count += hweight8(buffer[i]);
+	count = memweight(la->la_bitmap, le16_to_cpu(la->la_size));
 
 	trace_ocfs2_local_alloc_count_bits(count);
 	return count;
-- 
1.7.7.6

On Sat,  9 Jun 2012 09:50:30 +0900
Akinobu Mita <akinobu.mita at gmail.com> wrote:
> memweight() is the function that counts the total number of bits set
> in memory area.  Unlike bitmap_weight(), memweight() takes pointer
> and size in bytes to specify a memory area which does not need to be
> aligned to long-word boundary.
> 
> ...
>
> +/**
> + * 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;
Calling the return value "ret" is a useful convention and fits well
here.
> +	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);
> +	if (longs) {
> +		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);
> +	}
> +	/*
> +	 * The reason that this last loop is distinct from the preceding
> +	 * bitmap_weight() call is to compute 1-bits in the last region smaller
> +	 * than sizeof(long) properly on big-endian systems.
> +	 */
> +	for (; bytes > 0; bytes--, bitmap++)
> +		w += hweight8(*bitmap);
> +
> +	return w;
> +}
> +EXPORT_SYMBOL(memweight);
diff -puN lib/string.c~string-introduce-memweight-fix lib/string.c
--- a/lib/string.c~string-introduce-memweight-fix
+++ a/lib/string.c
@@ -833,18 +833,18 @@ EXPORT_SYMBOL(memchr_inv);
  */
 size_t memweight(const void *ptr, size_t bytes)
 {
-	size_t w = 0;
+	size_t ret = 0;
 	size_t longs;
 	const unsigned char *bitmap = ptr;
 
 	for (; bytes > 0 && ((unsigned long)bitmap) % sizeof(long);
 			bytes--, bitmap++)
-		w += hweight8(*bitmap);
+		ret += hweight8(*bitmap);
 
 	longs = bytes / sizeof(long);
 	if (longs) {
 		BUG_ON(longs >= INT_MAX / BITS_PER_LONG);
-		w += bitmap_weight((unsigned long *)bitmap,
+		ret += bitmap_weight((unsigned long *)bitmap,
 				longs * BITS_PER_LONG);
 		bytes -= longs * sizeof(long);
 		bitmap += longs * sizeof(long);
@@ -855,8 +855,8 @@ size_t memweight(const void *ptr, size_t
 	 * than sizeof(long) properly on big-endian systems.
 	 */
 	for (; bytes > 0; bytes--, bitmap++)
-		w += hweight8(*bitmap);
+		ret += hweight8(*bitmap);
 
-	return w;
+	return ret;
 }
 EXPORT_SYMBOL(memweight);
_

2012/6/21 Tony Luck <tony.luck at gmail.com>:
> On Fri, Jun 8, 2012 at 5:50 PM, Akinobu Mita <akinobu.mita at
gmail.com> wrote:
>> ?lib/string.c ? ? ? ? ? | ? 36 ++++++++++++++++++++++++++++++++++++
>
> Is lib/string.c the right place for this? ?I get a build error on the
> ia64 sim_defconfig:
>
> ?LD ? ? ?arch/ia64/hp/sim/boot/bootloader
>
> It fails because it pulls in lib/lib.a(string.o) to get some
> innocuous function like strcpy() ... but it also gets
> given memweight() which relies on __bitmap_weight()
> which it doesn't have, because it doesn't include lib/built-in.o
> (which is where bitmap.o, the definer of __bitmap_weight(), has
> been linked).
>
> Moving memweight() to lib/bitmap.c fixes the problem. But it
> isn't really clear that it belongs there either. ?Perhaps it should
> be its own file lib/memweight.c that gets included in lib/lib.a?
I'll fix it by making lib/memweight.c as you suggested.
Thanks for your report and suggestion.