* [PATCH v3] exfat/balloc: using hweight instead of internal logic
@ 2023-12-05 15:58 ` John Sanpe
2023-12-07 2:40 ` Sungjong Seo
0 siblings, 1 reply; 3+ messages in thread
From: John Sanpe @ 2023-12-05 15:58 UTC (permalink / raw)
To: linkinjeon, sj1557.seo, willy
Cc: linux-fsdevel, Andy.Wu, Wataru.Aoyama, cpgs, John Sanpe
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 <sanpeqf@gmail.com>
---
fs/exfat/balloc.c | 48 +++++++++++++++++++++--------------------------
1 file changed, 21 insertions(+), 27 deletions(-)
diff --git a/fs/exfat/balloc.c b/fs/exfat/balloc.c
index e918decb3735..69804a1b92d0 100644
--- a/fs/exfat/balloc.c
+++ b/fs/exfat/balloc.c
@@ -5,11 +5,22 @@
#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 __le_long __le32
+# define lel_to_cpu(A) le32_to_cpu(A)
+#elif BITS_PER_LONG == 64
+# define __le_long __le64
+# 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 +37,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 +239,24 @@ 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 - 1);
+ 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);
+ count += hweight_long(*bitmap);
+ 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(*(__le_long *)bitmap);
+ count += hweight_long(clu_bits & BITMAP_LAST_WORD_MASK(last_mask));
}
*ret_count = count;
--
2.43.0
^ permalink raw reply related [flat|nested] 3+ messages in thread
* RE: [PATCH v3] exfat/balloc: using hweight instead of internal logic
2023-12-05 15:58 ` [PATCH v3] exfat/balloc: using hweight instead of internal logic John Sanpe
@ 2023-12-07 2:40 ` Sungjong Seo
2023-12-07 12:38 ` Namjae Jeon
0 siblings, 1 reply; 3+ messages in thread
From: Sungjong Seo @ 2023-12-07 2:40 UTC (permalink / raw)
To: 'John Sanpe', linkinjeon, willy
Cc: linux-fsdevel, Andy.Wu, Wataru.Aoyama, cpgs
> 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 <sanpeqf@gmail.com>
Thanks for your patch.
Acked-by: Sungjong Seo <sj1557.seo@samsung.com>
> ---
> fs/exfat/balloc.c | 48 +++++++++++++++++++++--------------------------
> 1 file changed, 21 insertions(+), 27 deletions(-)
>
> diff --git a/fs/exfat/balloc.c b/fs/exfat/balloc.c
> index e918decb3735..69804a1b92d0 100644
> --- a/fs/exfat/balloc.c
> +++ b/fs/exfat/balloc.c
> @@ -5,11 +5,22 @@
>
> #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 __le_long __le32
> +# define lel_to_cpu(A) le32_to_cpu(A)
> +#elif BITS_PER_LONG == 64
> +# define __le_long __le64
> +# 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 +37,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 +239,24 @@ 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 - 1);
> + 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);
> + count += hweight_long(*bitmap);
> + 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(*(__le_long *)bitmap);
> + count += hweight_long(clu_bits &
> BITMAP_LAST_WORD_MASK(last_mask));
> }
>
> *ret_count = count;
> --
> 2.43.0
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH v3] exfat/balloc: using hweight instead of internal logic
2023-12-07 2:40 ` Sungjong Seo
@ 2023-12-07 12:38 ` Namjae Jeon
0 siblings, 0 replies; 3+ messages in thread
From: Namjae Jeon @ 2023-12-07 12:38 UTC (permalink / raw)
To: John Sanpe
Cc: willy, linux-fsdevel, Andy.Wu, Wataru.Aoyama, cpgs, Sungjong Seo
2023-12-07 11:40 GMT+09:00, Sungjong Seo <sj1557.seo@samsung.com>:
>> 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 <sanpeqf@gmail.com>
>
> Thanks for your patch.
> Acked-by: Sungjong Seo <sj1557.seo@samsung.com>
Applied it to #dev.
Thanks for your patch.
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2023-12-07 12:39 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
[not found] <CGME20231205160306epcas1p35c3e3fc9ef2c8651eac58a8d6c194880@epcas1p3.samsung.com>
2023-12-05 15:58 ` [PATCH v3] exfat/balloc: using hweight instead of internal logic John Sanpe
2023-12-07 2:40 ` Sungjong Seo
2023-12-07 12:38 ` Namjae Jeon
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).