[PATCH v2 01/10] string: introduce memweight

[PATCH v2 01/10] 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>
---

v2: simplify memweight(), adviced by Jan Kara

 include/linux/string.h |    3 +++
 lib/string.c           |   32 ++++++++++++++++++++++++++++++++
 2 files changed, 35 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..bf4d5a8 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,34 @@ 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);
+	}
+
+	for (; bytes > 0; bytes--, bitmap++)
+		w += hweight8(*bitmap);
+
+	return w;
+}
+EXPORT_SYMBOL(memweight);
-- 
1.7.7.6

[PATCH v2 08/10] ext2: use memweight()

[Akinobu Mita]

Use memweight() to count the total number of bits clear in memory area.
This change only affects the code segments enabled by EXT2FS_DEBUG.

This also fixes 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
---

No changes from v1

 fs/ext2/balloc.c |   22 ++--------------------
 fs/ext2/ext2.h   |    1 -
 fs/ext2/ialloc.c |    5 ++++-
 3 files changed, 6 insertions(+), 22 deletions(-)

diff --git a/fs/ext2/balloc.c b/fs/ext2/balloc.c
index 1c36139..9095500 100644
--- a/fs/ext2/balloc.c
+++ b/fs/ext2/balloc.c
@@ -1442,25 +1442,6 @@ ext2_fsblk_t ext2_new_block(struct inode *inode, unsigned long goal, int *errp)
 	return ext2_new_blocks(inode, goal, &count, 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 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);
-}
-
-#endif  /*  EXT2FS_DEBUG  */
-
 unsigned long ext2_count_free_blocks (struct super_block * sb)
 {
 	struct ext2_group_desc * desc;
@@ -1484,7 +1465,8 @@ unsigned long ext2_count_free_blocks (struct super_block * sb)
 		if (!bitmap_bh)
 			continue;
 		
-		x = ext2_count_free(bitmap_bh, sb->s_blocksize);
+		x = sb->s_blocksize * BITS_PER_BYTE -
+			memweight(bitmap_bh->b_data, sb->s_blocksize);
 		printk ("group %d: stored = %d, counted = %lu\n",
 			i, le16_to_cpu(desc->bg_free_blocks_count), x);
 		bitmap_count += x;
diff --git a/fs/ext2/ext2.h b/fs/ext2/ext2.h
index d9a17d0..5d3a974 100644
--- a/fs/ext2/ext2.h
+++ b/fs/ext2/ext2.h
@@ -745,7 +745,6 @@ extern struct inode * ext2_new_inode (struct inode *, umode_t, const struct qstr
 extern void ext2_free_inode (struct inode *);
 extern unsigned long ext2_count_free_inodes (struct super_block *);
 extern void ext2_check_inodes_bitmap (struct super_block *);
-extern unsigned long ext2_count_free (struct buffer_head *, unsigned);
 
 /* inode.c */
 extern struct inode *ext2_iget (struct super_block *, unsigned long);
diff --git a/fs/ext2/ialloc.c b/fs/ext2/ialloc.c
index c13eb7b..eb9ca7b 100644
--- a/fs/ext2/ialloc.c
+++ b/fs/ext2/ialloc.c
@@ -637,13 +637,16 @@ unsigned long ext2_count_free_inodes (struct super_block * sb)
 		if (!bitmap_bh)
 			continue;
 
-		x = ext2_count_free(bitmap_bh, EXT2_INODES_PER_GROUP(sb) / 8);
+		x = EXT2_INODES_PER_GROUP(sb) / 8 * BITS_PER_BYTE -
+			memweight(bitmap_bh->b_data,
+				EXT2_INODES_PER_GROUP(sb) / 8);
 		printk("group %d: stored = %d, counted = %u\n",
 			i, le16_to_cpu(desc->bg_free_inodes_count), x);
 		bitmap_count += x;
 	}
 	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 v2 09/10] ext3: use memweight()

[Akinobu Mita]

Use memweight() to count the total number of bits clear in memory area.
This change only affects the code segments enabled by EXT3FS_DEBUG.

This also fixes 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
---

No changes from v1

 fs/ext3/Makefile |    2 +-
 fs/ext3/balloc.c |    5 +++--
 fs/ext3/bitmap.c |   30 ------------------------------
 fs/ext3/ext3.h   |    2 --
 fs/ext3/ialloc.c |    4 +++-
 5 files changed, 7 insertions(+), 36 deletions(-)
 delete mode 100644 fs/ext3/bitmap.c

diff --git a/fs/ext3/Makefile b/fs/ext3/Makefile
index e77766a..ce93e94 100644
--- a/fs/ext3/Makefile
+++ b/fs/ext3/Makefile
@@ -4,7 +4,7 @@
 
 obj-$(CONFIG_EXT3_FS) += ext3.o
 
-ext3-y	:= balloc.o bitmap.o dir.o file.o fsync.o ialloc.o inode.o \
+ext3-y	:= balloc.o dir.o file.o fsync.o ialloc.o inode.o \
 	   ioctl.o namei.o super.o symlink.o hash.o resize.o ext3_jbd.o
 
 ext3-$(CONFIG_EXT3_FS_XATTR)	 += xattr.o xattr_user.o xattr_trusted.o
diff --git a/fs/ext3/balloc.c b/fs/ext3/balloc.c
index 25cd608..1298c74 100644
--- a/fs/ext3/balloc.c
+++ b/fs/ext3/balloc.c
@@ -1805,7 +1805,8 @@ ext3_fsblk_t ext3_count_free_blocks(struct super_block *sb)
 		if (bitmap_bh == NULL)
 			continue;
 
-		x = ext3_count_free(bitmap_bh, sb->s_blocksize);
+		x = sb->s_blocksize * BITS_PER_BYTE -
+			memweight(bitmap_bh->b_data, sb->s_blocksize);
 		printk("group %d: stored = %d, counted = %lu\n",
 			i, le16_to_cpu(gdp->bg_free_blocks_count), x);
 		bitmap_count += x;
@@ -1813,7 +1814,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
deleted file mode 100644
index 909d13e..0000000
--- a/fs/ext3/bitmap.c
+++ /dev/null
@@ -1,30 +0,0 @@
-/*
- *  linux/fs/ext3/bitmap.c
- *
- * Copyright (C) 1992, 1993, 1994, 1995
- * Remy Card (card@masi.ibp.fr)
- * Laboratoire MASI - Institut Blaise Pascal
- * Universite Pierre et Marie Curie (Paris VI)
- */
-
-#include "ext3.h"
-
-#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);
-}
-
-#endif  /*  EXT3FS_DEBUG  */
-
diff --git a/fs/ext3/ext3.h b/fs/ext3/ext3.h
index e85ff15..8823466 100644
--- a/fs/ext3/ext3.h
+++ b/fs/ext3/ext3.h
@@ -1033,8 +1033,6 @@ extern struct inode * ext3_orphan_get (struct super_block *, unsigned long);
 extern unsigned long ext3_count_free_inodes (struct super_block *);
 extern unsigned long ext3_count_dirs (struct super_block *);
 extern void ext3_check_inodes_bitmap (struct super_block *);
-extern unsigned long ext3_count_free (struct buffer_head *, unsigned);
-
 
 /* inode.c */
 int ext3_forget(handle_t *handle, int is_metadata, struct inode *inode,
diff --git a/fs/ext3/ialloc.c b/fs/ext3/ialloc.c
index 082afd7..2862ff1 100644
--- a/fs/ext3/ialloc.c
+++ b/fs/ext3/ialloc.c
@@ -667,7 +667,9 @@ unsigned long ext3_count_free_inodes (struct super_block * sb)
 		if (!bitmap_bh)
 			continue;
 
-		x = ext3_count_free(bitmap_bh, EXT3_INODES_PER_GROUP(sb) / 8);
+		x = EXT3_INODES_PER_GROUP(sb) / 8 * BITS_PER_BYTE -
+			memweight(bitmap_bh->b_data,
+				EXT3_INODES_PER_GROUP(sb) / 8);
 		printk("group %d: stored = %d, counted = %lu\n",
 			i, le16_to_cpu(gdp->bg_free_inodes_count), x);
 		bitmap_count += x;
-- 
1.7.7.6

[PATCH v2 10/10] ext4: use memweight()

[Akinobu Mita]

Use memweight() to count the total number of bits clear in memory area.
This change only affects the code segments enabled by EXT4FS_DEBUG.

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
---

v2: don't remove bitmap.c which now has other than ext4_count_free()

 fs/ext4/balloc.c |    3 ++-
 fs/ext4/bitmap.c |   18 ------------------
 fs/ext4/ext4.h   |    1 -
 fs/ext4/ialloc.c |    4 +++-
 4 files changed, 5 insertions(+), 21 deletions(-)

diff --git a/fs/ext4/balloc.c b/fs/ext4/balloc.c
index 99b6324..e5eadfe 100644
--- a/fs/ext4/balloc.c
+++ b/fs/ext4/balloc.c
@@ -609,7 +609,8 @@ ext4_fsblk_t ext4_count_free_clusters(struct super_block *sb)
 		if (bitmap_bh == NULL)
 			continue;
 
-		x = ext4_count_free(bitmap_bh, sb->s_blocksize);
+		x = sb->s_blocksize * BITS_PER_BYTE -
+			memweight(bitmap_bh->b_data, sb->s_blocksize);
 		printk(KERN_DEBUG "group %u: stored = %d, counted = %u\n",
 			i, ext4_free_group_clusters(sb, gdp), x);
 		bitmap_count += x;
diff --git a/fs/ext4/bitmap.c b/fs/ext4/bitmap.c
index b319721..3c67c97 100644
--- a/fs/ext4/bitmap.c
+++ b/fs/ext4/bitmap.c
@@ -11,24 +11,6 @@
 #include <linux/jbd2.h>
 #include "ext4.h"
 
-#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;
-}
-
-#endif  /*  EXT4FS_DEBUG  */
-
 int ext4_inode_bitmap_csum_verify(struct super_block *sb, ext4_group_t group,
 				  struct ext4_group_desc *gdp,
 				  struct buffer_head *bh, int sz)
diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
index cfc4e01..3a3511d 100644
--- a/fs/ext4/ext4.h
+++ b/fs/ext4/ext4.h
@@ -1852,7 +1852,6 @@ struct mmpd_data {
 # define NORET_AND	noreturn,
 
 /* bitmap.c */
-extern unsigned int ext4_count_free(struct buffer_head *, unsigned);
 void ext4_inode_bitmap_csum_set(struct super_block *sb, ext4_group_t group,
 				struct ext4_group_desc *gdp,
 				struct buffer_head *bh, int sz);
diff --git a/fs/ext4/ialloc.c b/fs/ext4/ialloc.c
index d48e8b1..1310108 100644
--- a/fs/ext4/ialloc.c
+++ b/fs/ext4/ialloc.c
@@ -1054,7 +1054,9 @@ unsigned long ext4_count_free_inodes(struct super_block *sb)
 		if (!bitmap_bh)
 			continue;
 
-		x = ext4_count_free(bitmap_bh, EXT4_INODES_PER_GROUP(sb) / 8);
+		x = EXT4_INODES_PER_GROUP(sb) / 8 * BITS_PER_BYTE -
+			memweight(bitmap_bh->b_data,
+				EXT4_INODES_PER_GROUP(sb) / 8);
 		printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n",
 			(unsigned long) i, ext4_free_inodes_count(sb, gdp), x);
 		bitmap_count += x;
-- 
1.7.7.6

Re: [PATCH v2 10/10] ext4: use memweight()

[Andreas Dilger]

On 2012-06-02, at 7:40, Akinobu Mita <akinobu.mita@gmail.com> wrote:

> Use memweight() to count the total number of bits clear in memory area.
> This change only affects the code segments enabled by EXT4FS_DEBUG.

Personally, I'd rather still keep a thin wrapper ext4_count_free() and put the memweight() call and math inside that. The function name ext4_count_free() is meaningful to readers, while memweight() is much less so. 

Cheers, Andreas

> 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
> ---
> 
> v2: don't remove bitmap.c which now has other than ext4_count_free()
> 
> fs/ext4/balloc.c |    3 ++-
> fs/ext4/bitmap.c |   18 ------------------
> fs/ext4/ext4.h   |    1 -
> fs/ext4/ialloc.c |    4 +++-
> 4 files changed, 5 insertions(+), 21 deletions(-)
> 
> diff --git a/fs/ext4/balloc.c b/fs/ext4/balloc.c
> index 99b6324..e5eadfe 100644
> --- a/fs/ext4/balloc.c
> +++ b/fs/ext4/balloc.c
> @@ -609,7 +609,8 @@ ext4_fsblk_t ext4_count_free_clusters(struct super_block *sb)
>        if (bitmap_bh == NULL)
>            continue;
> 
> -        x = ext4_count_free(bitmap_bh, sb->s_blocksize);
> +        x = sb->s_blocksize * BITS_PER_BYTE -
> +            memweight(bitmap_bh->b_data, sb->s_blocksize);
>        printk(KERN_DEBUG "group %u: stored = %d, counted = %u\n",
>            i, ext4_free_group_clusters(sb, gdp), x);
>        bitmap_count += x;
> diff --git a/fs/ext4/bitmap.c b/fs/ext4/bitmap.c
> index b319721..3c67c97 100644
> --- a/fs/ext4/bitmap.c
> +++ b/fs/ext4/bitmap.c
> @@ -11,24 +11,6 @@
> #include <linux/jbd2.h>
> #include "ext4.h"
> 
> -#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;
> -}
> -
> -#endif  /*  EXT4FS_DEBUG  */
> -
> int ext4_inode_bitmap_csum_verify(struct super_block *sb, ext4_group_t group,
>                  struct ext4_group_desc *gdp,
>                  struct buffer_head *bh, int sz)
> diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
> index cfc4e01..3a3511d 100644
> --- a/fs/ext4/ext4.h
> +++ b/fs/ext4/ext4.h
> @@ -1852,7 +1852,6 @@ struct mmpd_data {
> # define NORET_AND    noreturn,
> 
> /* bitmap.c */
> -extern unsigned int ext4_count_free(struct buffer_head *, unsigned);
> void ext4_inode_bitmap_csum_set(struct super_block *sb, ext4_group_t group,
>                struct ext4_group_desc *gdp,
>                struct buffer_head *bh, int sz);
> diff --git a/fs/ext4/ialloc.c b/fs/ext4/ialloc.c
> index d48e8b1..1310108 100644
> --- a/fs/ext4/ialloc.c
> +++ b/fs/ext4/ialloc.c
> @@ -1054,7 +1054,9 @@ unsigned long ext4_count_free_inodes(struct super_block *sb)
>        if (!bitmap_bh)
>            continue;
> 
> -        x = ext4_count_free(bitmap_bh, EXT4_INODES_PER_GROUP(sb) / 8);
> +        x = EXT4_INODES_PER_GROUP(sb) / 8 * BITS_PER_BYTE -
> +            memweight(bitmap_bh->b_data,
> +                EXT4_INODES_PER_GROUP(sb) / 8);
>        printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n",
>            (unsigned long) i, ext4_free_inodes_count(sb, gdp), x);
>        bitmap_count += x;
> -- 
> 1.7.7.6
> 

Re: [PATCH v2 10/10] ext4: use memweight()

[Akinobu Mita]

2012/6/2 Andreas Dilger <adilger@dilger.ca>:
> On 2012-06-02, at 7:40, Akinobu Mita <akinobu.mita@gmail.com> wrote:
>
>> Use memweight() to count the total number of bits clear in memory area.
>> This change only affects the code segments enabled by EXT4FS_DEBUG.
>
> Personally, I'd rather still keep a thin wrapper ext4_count_free() and put the memweight() call and math inside that. The function name ext4_count_free() is meaningful to readers, while memweight() is much less so.

OK, I'll make such change to ext[234] if no other people disagree with it.

Re: [PATCH v2 08/10] ext2: use memweight()

[Jan Kara]

On Sat 02-06-12 22:40:14, Akinobu Mita wrote:
> Use memweight() to count the total number of bits clear in memory area.
> This change only affects the code segments enabled by EXT2FS_DEBUG.
> 
> This also fixes 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
> ---
> 
> No changes from v1
> 
>  fs/ext2/balloc.c |   22 ++--------------------
>  fs/ext2/ext2.h   |    1 -
>  fs/ext2/ialloc.c |    5 ++++-
>  3 files changed, 6 insertions(+), 22 deletions(-)
> 
> diff --git a/fs/ext2/balloc.c b/fs/ext2/balloc.c
> index 1c36139..9095500 100644
> --- a/fs/ext2/balloc.c
> +++ b/fs/ext2/balloc.c
> @@ -1442,25 +1442,6 @@ ext2_fsblk_t ext2_new_block(struct inode *inode, unsigned long goal, int *errp)
>  	return ext2_new_blocks(inode, goal, &count, 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 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);
> -}
> -
> -#endif  /*  EXT2FS_DEBUG  */
> -
  So actually if you look at this function, you see that it counts bits in
map->b_data. That is guaranteed to be long aligned pointer so there's no
need for your memweight(). bitmap_weight() would be enough, especially
given that it can handle number of bits which is not a multiple of
BITS_PER_LONG.

  For ext3 it's the same BTW.

								Honza
-- 
Jan Kara <jack@suse.cz>
SUSE Labs, CR

Re: [PATCH v2 01/10] string: introduce memweight

[Jan Kara]

On Sat 02-06-12 22:40:07, Akinobu Mita 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.
> 
> 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>
> ---
> 
> v2: simplify memweight(), adviced by Jan Kara
> 
>  include/linux/string.h |    3 +++
>  lib/string.c           |   32 ++++++++++++++++++++++++++++++++
>  2 files changed, 35 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..bf4d5a8 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,34 @@ 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);
> +	}
> +
> +	for (; bytes > 0; bytes--, bitmap++)
> +		w += hweight8(*bitmap);
  Looking at bitmap_weight() it seems this last loop is not needed. Just
pass to bitmap_weight() bytes*BITS_PER_BYTE. Also generally this function
doesn't seem necessary at all at least for ext2 & ext3 (sorry for not
noticing this earlier...).

								Honza
-- 
Jan Kara <jack@suse.cz>
SUSE Labs, CR

Re: [PATCH v2 01/10] string: introduce memweight

[Akinobu Mita]

2012/6/4 Jan Kara <jack@suse.cz>:
> On Sat 02-06-12 22:40:07, Akinobu Mita 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.
>>
>> 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>
>> ---
>>
>> v2: simplify memweight(), adviced by Jan Kara
>>
>>  include/linux/string.h |    3 +++
>>  lib/string.c           |   32 ++++++++++++++++++++++++++++++++
>>  2 files changed, 35 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..bf4d5a8 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,34 @@ 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);
>> +     }
>> +
>> +     for (; bytes > 0; bytes--, bitmap++)
>> +             w += hweight8(*bitmap);
>  Looking at bitmap_weight() it seems this last loop is not needed. Just
> pass to bitmap_weight() bytes*BITS_PER_BYTE. Also generally this function
> doesn't seem necessary at all at least for ext2 & ext3 (sorry for not
> noticing this earlier...).

This last loop is necessary for big-endian architecture.
if bytes % sizeof(long) != 0, bitmap_weight() counts one-bits in wrong
byte-field
of the last long word.
--
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 v2 01/10] string: introduce memweight

[Jan Kara]

On Mon 04-06-12 20:46:14, Akinobu Mita wrote:
> 2012/6/4 Jan Kara <jack@suse.cz>:
> > On Sat 02-06-12 22:40:07, Akinobu Mita 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.
> >>
> >> 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>
> >> ---
> >>
> >> v2: simplify memweight(), adviced by Jan Kara
> >>
> >>  include/linux/string.h |    3 +++
> >>  lib/string.c           |   32 ++++++++++++++++++++++++++++++++
> >>  2 files changed, 35 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..bf4d5a8 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,34 @@ 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);
> >> +     }
> >> +
> >> +     for (; bytes > 0; bytes--, bitmap++)
> >> +             w += hweight8(*bitmap);
> >  Looking at bitmap_weight() it seems this last loop is not needed. Just
> > pass to bitmap_weight() bytes*BITS_PER_BYTE. Also generally this function
> > doesn't seem necessary at all at least for ext2 & ext3 (sorry for not
> > noticing this earlier...).
> 
> This last loop is necessary for big-endian architecture.
> if bytes % sizeof(long) != 0, bitmap_weight() counts one-bits in wrong
> byte-field
> of the last long word.
  Ah, right. OK. Add this to the comment before the loop please. You save
yourself some explanations :)

								Honza
-- 
Jan Kara <jack@suse.cz>
SUSE Labs, CR
--
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 v2 01/10] string: introduce memweight

[Akinobu Mita]

2012/6/4 Jan Kara <jack@suse.cz>:
> On Mon 04-06-12 20:46:14, Akinobu Mita wrote:
>> 2012/6/4 Jan Kara <jack@suse.cz>:
>> > On Sat 02-06-12 22:40:07, Akinobu Mita 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.
>> >>
>> >> 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>
>> >> ---
>> >>
>> >> v2: simplify memweight(), adviced by Jan Kara
>> >>
>> >> áinclude/linux/string.h | á á3 +++
>> >> álib/string.c á á á á á | á 32 ++++++++++++++++++++++++++++++++
>> >> á2 files changed, 35 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..bf4d5a8 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,34 @@ 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);
>> >> + á á }
>> >> +
>> >> + á á for (; bytes > 0; bytes--, bitmap++)
>> >> + á á á á á á w += hweight8(*bitmap);
>> > áLooking at bitmap_weight() it seems this last loop is not needed. Just
>> > pass to bitmap_weight() bytes*BITS_PER_BYTE. Also generally this function
>> > doesn't seem necessary at all at least for ext2 & ext3 (sorry for not
>> > noticing this earlier...).
>>
>> This last loop is necessary for big-endian architecture.
>> if bytes % sizeof(long) != 0, bitmap_weight() counts one-bits in wrong
>> byte-field
>> of the last long word.
>  Ah, right. OK. Add this to the comment before the loop please. You save
> yourself some explanations :)

OK.  Thanks for your advice again.