[PATCH v3 1/9] string: introduce memweight

[PATCH v3 1/9] string: introduce memweight

[Akinobu Mita]

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 <mfasheh@suse.com>
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 <matthew@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

[PATCH v3 7/9] ext2: use memweight()

[Akinobu Mita]

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

[PATCH v3 8/9] ext3: use memweight()

[Akinobu Mita]

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

[PATCH v3 9/9] ext4: use memweight()

[Akinobu Mita]

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

Re: [PATCH v3 1/9] string: introduce memweight

[Andrew Morton]

On Sat,  9 Jun 2012 09:50:30 +0900
Akinobu Mita <akinobu.mita@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);
_

Re: [PATCH v3 7/9] ext2: use memweight()

[Jan Kara]

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 <jack@suse.cz>

								Honza

> 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
> 
-- 
Jan Kara <jack@suse.cz>
SUSE Labs, CR

Re: [PATCH v3 8/9] ext3: use memweight()

[Jan Kara]

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 <jack@suse.cz>

								Honza

> 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
> 
-- 
Jan Kara <jack@suse.cz>
SUSE Labs, CR

Re: [PATCH v3 1/9] string: introduce memweight

[Tony Luck]

On Fri, Jun 8, 2012 at 5:50 PM, Akinobu Mita <akinobu.mita@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?

-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

Re: [PATCH v3 1/9] string: introduce memweight

[Akinobu Mita]

2012/6/21 Tony Luck <tony.luck@gmail.com>:
> On Fri, Jun 8, 2012 at 5:50 PM, Akinobu Mita <akinobu.mita@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.
--
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