[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@gmail.com>
Cc: Anders Larsen <al@alarsen.net>
Cc: Alasdair Kergon <agk@redhat.com>
Cc: dm-devel@redhat.com
Cc: linux-fsdevel@vger.kernel.org
Cc: Laurent Pinchart <laurent.pinchart@ideasonboard.com>
Cc: linux-media@vger.kernel.org
Cc: Mark Fasheh <redacted>
Cc: Joel Becker <jlbec@evilplan.org>
Cc: ocfs2-devel@oss.oracle.com
Cc: Jan Kara <jack@suse.cz>
Cc: linux-ext4@vger.kernel.org
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andreas Dilger <adilger.kernel@dilger.ca>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Matthew Wilcox <redacted>
---
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

Convert ext2_count_free() to use memweight() instead of table lookup
based counting clear bits implementation.  This change only affects
the code segments enabled by EXT2FS_DEBUG.

Note that this memweight() call can't be replaced with a single
bitmap_weight() call, although the pointer to the memory area is
aligned to long-word boundary.  Because the size of the memory area
may not be a multiple of BITS_PER_LONG, then it returns wrong value on
big-endian architecture.

This also includes the following changes.

- Remove unnecessary map == NULL check in ext2_count_free() which
  always takes non-null pointer as the memory area.

- Fix printk format warning that only reveals with EXT2FS_DEBUG.

Signed-off-by: Akinobu Mita <akinobu.mita@gmail.com>
Cc: Jan Kara <jack@suse.cz>
Cc: linux-ext4@vger.kernel.org
---
v3: rewrite to keep ext2_count_free() as a wrapper for memweight()

 fs/ext2/balloc.c |   14 ++------------
 fs/ext2/ialloc.c |    1 +
 2 files changed, 3 insertions(+), 12 deletions(-)

diff --git a/fs/ext2/balloc.c b/fs/ext2/balloc.c
index 1c36139..376aa77 100644
--- a/fs/ext2/balloc.c
+++ b/fs/ext2/balloc.c

@@ -1444,19 +1444,9 @@ ext2_fsblk_t ext2_new_block(struct inode *inode, unsigned long goal, int *errp)
 
 #ifdef EXT2FS_DEBUG
 
-static const int nibblemap[] = {4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0};
-
-unsigned long ext2_count_free (struct buffer_head * map, unsigned int numchars)
+unsigned long ext2_count_free(struct buffer_head *map, unsigned int numchars)
 {
-	unsigned int i;
-	unsigned long sum = 0;
-
-	if (!map)
-		return (0);
-	for (i = 0; i < numchars; i++)
-		sum += nibblemap[map->b_data[i] & 0xf] +
-			nibblemap[(map->b_data[i] >> 4) & 0xf];
-	return (sum);
+	return numchars * BITS_PER_BYTE - memweight(map->b_data, numchars);
 }
 
 #endif  /*  EXT2FS_DEBUG  */

diff --git a/fs/ext2/ialloc.c b/fs/ext2/ialloc.c
index c13eb7b..8f370e01 100644
--- a/fs/ext2/ialloc.c
+++ b/fs/ext2/ialloc.c

@@ -644,6 +644,7 @@ unsigned long ext2_count_free_inodes (struct super_block * sb)
 	}
 	brelse(bitmap_bh);
 	printk("ext2_count_free_inodes: stored = %lu, computed = %lu, %lu\n",
+		(unsigned long)
 		percpu_counter_read(&EXT2_SB(sb)->s_freeinodes_counter),
 		desc_count, bitmap_count);
 	return desc_count;

-- 
1.7.7.6

On Sat 09-06-12 09:50:36, Akinobu Mita wrote:

Convert ext2_count_free() to use memweight() instead of table lookup
based counting clear bits implementation.  This change only affects
the code segments enabled by EXT2FS_DEBUG.

Note that this memweight() call can't be replaced with a single
bitmap_weight() call, although the pointer to the memory area is
aligned to long-word boundary.  Because the size of the memory area
may not be a multiple of BITS_PER_LONG, then it returns wrong value on
big-endian architecture.

This also includes the following changes.

- Remove unnecessary map == NULL check in ext2_count_free() which
  always takes non-null pointer as the memory area.

- Fix printk format warning that only reveals with EXT2FS_DEBUG.

Signed-off-by: Akinobu Mita <akinobu.mita@gmail.com>
Cc: Jan Kara <jack@suse.cz>

  Acked-by: Jan Kara [off-list ref]

								Honza

-- 
Jan Kara [off-list ref]
SUSE Labs, CR

Convert ext3_count_free() to use memweight() instead of table lookup
based counting clear bits implementation.  This change only affects
the code segments enabled by EXT3FS_DEBUG.

Note that this memweight() call can't be replaced with a single
bitmap_weight() call, although the pointer to the memory area is
aligned to long-word boundary.  Because the size of the memory area
may not be a multiple of BITS_PER_LONG, then it returns wrong value on
big-endian architecture.

This also includes the following changes.

- Remove unnecessary map == NULL check in ext3_count_free() which
  always takes non-null pointer as the memory area.

- Fix printk format warning that only reveals with EXT3FS_DEBUG.

Signed-off-by: Akinobu Mita <akinobu.mita@gmail.com>
Cc: Jan Kara <jack@suse.cz>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andreas Dilger <adilger.kernel@dilger.ca>
Cc: linux-ext4@vger.kernel.org
---
v3: rewrite to keep ext3_count_free() as a wrapper for memweight()

 fs/ext3/balloc.c |    2 +-
 fs/ext3/bitmap.c |   12 +-----------
 2 files changed, 2 insertions(+), 12 deletions(-)

diff --git a/fs/ext3/balloc.c b/fs/ext3/balloc.c
index 25cd608..90d901f 100644
--- a/fs/ext3/balloc.c
+++ b/fs/ext3/balloc.c

@@ -1813,7 +1813,7 @@ ext3_fsblk_t ext3_count_free_blocks(struct super_block *sb)
 	brelse(bitmap_bh);
 	printk("ext3_count_free_blocks: stored = "E3FSBLK
 		", computed = "E3FSBLK", "E3FSBLK"\n",
-	       le32_to_cpu(es->s_free_blocks_count),
+	       (ext3_fsblk_t)le32_to_cpu(es->s_free_blocks_count),
 		desc_count, bitmap_count);
 	return bitmap_count;
 #else

diff --git a/fs/ext3/bitmap.c b/fs/ext3/bitmap.c
index 909d13e..ef9c643 100644
--- a/fs/ext3/bitmap.c
+++ b/fs/ext3/bitmap.c

@@ -11,19 +11,9 @@
 
 #ifdef EXT3FS_DEBUG
 
-static const int nibblemap[] = {4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0};
-
 unsigned long ext3_count_free (struct buffer_head * map, unsigned int numchars)
 {
-	unsigned int i;
-	unsigned long sum = 0;
-
-	if (!map)
-		return (0);
-	for (i = 0; i < numchars; i++)
-		sum += nibblemap[map->b_data[i] & 0xf] +
-			nibblemap[(map->b_data[i] >> 4) & 0xf];
-	return (sum);
+	return numchars * BITS_PER_BYTE - memweight(map->b_data, numchars);
 }
 
 #endif  /*  EXT3FS_DEBUG  */

-- 
1.7.7.6

On Sat 09-06-12 09:50:37, Akinobu Mita wrote:

Convert ext3_count_free() to use memweight() instead of table lookup
based counting clear bits implementation.  This change only affects
the code segments enabled by EXT3FS_DEBUG.

Note that this memweight() call can't be replaced with a single
bitmap_weight() call, although the pointer to the memory area is
aligned to long-word boundary.  Because the size of the memory area
may not be a multiple of BITS_PER_LONG, then it returns wrong value on
big-endian architecture.

This also includes the following changes.

- Remove unnecessary map == NULL check in ext3_count_free() which
  always takes non-null pointer as the memory area.

- Fix printk format warning that only reveals with EXT3FS_DEBUG.

Signed-off-by: Akinobu Mita <akinobu.mita@gmail.com>
Cc: Jan Kara <jack@suse.cz>

  Acked-by: Jan Kara [off-list ref]

								Honza

-- 
Jan Kara [off-list ref]
SUSE Labs, CR

Convert ext4_count_free() to use memweight() instead of table lookup
based counting clear bits implementation.  This change only affects
the code segments enabled by EXT4FS_DEBUG.

Note that this memweight() call can't be replaced with a single
bitmap_weight() call, although the pointer to the memory area is
aligned to long-word boundary.  Because the size of the memory area
may not be a multiple of BITS_PER_LONG, then it returns wrong value on
big-endian architecture.

This also includes the following change.

- Remove unnecessary map == NULL check in ext4_count_free() which
  always takes non-null pointer as the memory area.

Signed-off-by: Akinobu Mita <akinobu.mita@gmail.com>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Andreas Dilger <adilger.kernel@dilger.ca>
Cc: linux-ext4@vger.kernel.org
---
v3: rewrite to keep ext4_count_free() as a wrapper for memweight()
v2: don't remove bitmap.c which now has other than ext4_count_free()

 fs/ext4/bitmap.c |   11 +----------
 1 files changed, 1 insertions(+), 10 deletions(-)

diff --git a/fs/ext4/bitmap.c b/fs/ext4/bitmap.c
index b319721..ff53d5d 100644
--- a/fs/ext4/bitmap.c
+++ b/fs/ext4/bitmap.c

@@ -13,18 +13,9 @@
 
 #ifdef EXT4FS_DEBUG
 
-static const int nibblemap[] = {4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0};
-
 unsigned int ext4_count_free(struct buffer_head *map, unsigned int numchars)
 {
-	unsigned int i, sum = 0;
-
-	if (!map)
-		return 0;
-	for (i = 0; i < numchars; i++)
-		sum += nibblemap[map->b_data[i] & 0xf] +
-			nibblemap[(map->b_data[i] >> 4) & 0xf];
-	return sum;
+	return numchars * BITS_PER_BYTE - memweight(map->b_data, numchars);
 }
 
 #endif  /*  EXT4FS_DEBUG  */

-- 
1.7.7.6

On Sat,  9 Jun 2012 09:50:30 +0900
Akinobu Mita [off-list ref] 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);

_

On Fri, Jun 8, 2012 at 5:50 PM, Akinobu Mita [off-list ref] 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?

-Tony
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

2012/6/21 Tony Luck [off-list ref]:

On Fri, Jun 8, 2012 at 5:50 PM, Akinobu Mita [off-list ref] wrote:

quoted

 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.
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html