[v2] exfat/balloc: using hweight instead of internal logic

Commit Message

John Sanpe Dec. 5, 2023, 4:33 a.m. UTC

Replace the internal table lookup algorithm with the hweight
library, which has instruction set acceleration capabilities.

Use it to increase the length of a single calculation of
the exfat_find_free_bitmap function to the long type.

Signed-off-by: John Sanpe <[e-mail]>
---
 fs/exfat/balloc.c   | 47 +++++++++++++++++++--------------------------
 fs/exfat/exfat_fs.h |  1 +
 2 files changed, 21 insertions(+), 27 deletions(-)

Comments

Matthew Wilcox Dec. 5, 2023, 2:33 p.m. UTC | #1

On Tue, Dec 05, 2023 at 12:33:05PM +0800, John Sanpe wrote:
> Replace the internal table lookup algorithm with the hweight
> library, which has instruction set acceleration capabilities.
> 
> Use it to increase the length of a single calculation of
> the exfat_find_free_bitmap function to the long type.

Have you run sparse over this?  "make C=2" will do it for you if you
have sparse installed.  I think it's going to complain about missing
endianness annotations.

> +	for (i = 0; i < total_clus; i += BITS_PER_LONG) {
> +		bitmap = (void *)(sbi->vol_amap[map_i]->b_data + map_b);
> +		clu_bits = lel_to_cpu(*bitmap);

I understand why you need to byteswap at the end, but I don't understand
why you need to byteswap here.  You're asking how many bits are set,
and that's the same answer no matter whether you calculate it on
0x12345678 or on 0x78563412.

> +++ b/fs/exfat/exfat_fs.h
> @@ -136,6 +136,7 @@ enum {
>  #define BITMAP_OFFSET_BYTE_IN_SECTOR(sb, ent) \
>  	((ent / BITS_PER_BYTE) & ((sb)->s_blocksize - 1))
>  #define BITS_PER_BYTE_MASK	0x7
> +#define BITS_PER_LONG_MASK	(BITS_PER_LONG - 1)

I don't think this adds any value over just using (BITS_PER_LONG - 1)
directly.

Patch

diff --git a/fs/exfat/balloc.c b/fs/exfat/balloc.c
index e918decb3735..a7b3a234ba9b 100644
--- a/fs/exfat/balloc.c
+++ b/fs/exfat/balloc.c
@@ -5,11 +5,20 @@ 
 
 #include <linux/blkdev.h>
 #include <linux/slab.h>
+#include <linux/bitmap.h>
 #include <linux/buffer_head.h>
 
 #include "exfat_raw.h"
 #include "exfat_fs.h"
 
+#if BITS_PER_LONG == 32
+# define lel_to_cpu(A) le32_to_cpu(A)
+#elif BITS_PER_LONG == 64
+# define lel_to_cpu(A) le64_to_cpu(A)
+#else
+# error "BITS_PER_LONG not 32 or 64"
+#endif
+
 static const unsigned char free_bit[] = {
 	0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2,/*  0 ~  19*/
 	0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3,/* 20 ~  39*/
@@ -26,22 +35,6 @@  static const unsigned char free_bit[] = {
 	0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0                /*240 ~ 254*/
 };
 
-static const unsigned char used_bit[] = {
-	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3,/*  0 ~  19*/
-	2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4,/* 20 ~  39*/
-	2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5,/* 40 ~  59*/
-	4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,/* 60 ~  79*/
-	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,/* 80 ~  99*/
-	3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,/*100 ~ 119*/
-	4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,/*120 ~ 139*/
-	3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,/*140 ~ 159*/
-	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5,/*160 ~ 179*/
-	4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,/*180 ~ 199*/
-	3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6,/*200 ~ 219*/
-	5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,/*220 ~ 239*/
-	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8             /*240 ~ 255*/
-};
-
 /*
  *  Allocation Bitmap Management Functions
  */
@@ -244,25 +237,25 @@  int exfat_count_used_clusters(struct super_block *sb, unsigned int *ret_count)
 	unsigned int count = 0;
 	unsigned int i, map_i = 0, map_b = 0;
 	unsigned int total_clus = EXFAT_DATA_CLUSTER_COUNT(sbi);
-	unsigned int last_mask = total_clus & BITS_PER_BYTE_MASK;
-	unsigned char clu_bits;
-	const unsigned char last_bit_mask[] = {0, 0b00000001, 0b00000011,
-		0b00000111, 0b00001111, 0b00011111, 0b00111111, 0b01111111};
+	unsigned int last_mask = total_clus & BITS_PER_LONG_MASK;
+	unsigned long *bitmap, clu_bits;
 
 	total_clus &= ~last_mask;
-	for (i = 0; i < total_clus; i += BITS_PER_BYTE) {
-		clu_bits = *(sbi->vol_amap[map_i]->b_data + map_b);
-		count += used_bit[clu_bits];
-		if (++map_b >= (unsigned int)sb->s_blocksize) {
+	for (i = 0; i < total_clus; i += BITS_PER_LONG) {
+		bitmap = (void *)(sbi->vol_amap[map_i]->b_data + map_b);
+		clu_bits = lel_to_cpu(*bitmap);
+		count += hweight_long(clu_bits);
+		map_b += sizeof(long);
+		if (map_b >= (unsigned int)sb->s_blocksize) {
 			map_i++;
 			map_b = 0;
 		}
 	}
 
 	if (last_mask) {
-		clu_bits = *(sbi->vol_amap[map_i]->b_data + map_b);
-		clu_bits &= last_bit_mask[last_mask];
-		count += used_bit[clu_bits];
+		bitmap = (void *)(sbi->vol_amap[map_i]->b_data + map_b);
+		clu_bits = lel_to_cpu(*bitmap) & BITMAP_LAST_WORD_MASK(last_mask);
+		count += hweight_long(clu_bits);
 	}
 
 	*ret_count = count;
diff --git a/fs/exfat/exfat_fs.h b/fs/exfat/exfat_fs.h
index a7a2c35d74fb..1cb3bf1851c8 100644
--- a/fs/exfat/exfat_fs.h
+++ b/fs/exfat/exfat_fs.h
@@ -136,6 +136,7 @@  enum {
 #define BITMAP_OFFSET_BYTE_IN_SECTOR(sb, ent) \
 	((ent / BITS_PER_BYTE) & ((sb)->s_blocksize - 1))
 #define BITS_PER_BYTE_MASK	0x7
+#define BITS_PER_LONG_MASK	(BITS_PER_LONG - 1)
 #define IGNORED_BITS_REMAINED(clu, clu_base) ((1 << ((clu) - (clu_base))) - 1)
 
 #define ES_ENTRY_NUM(name_len)	(ES_IDX_LAST_FILENAME(name_len) + 1)