* [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).