RE: [PATCH] exfat/balloc: using ffs instead of internal logic

["Sungjong Seo" <sj1557.seo@samsung.com>]

> Replaced the internal table lookup algorithm with ffs of the bitops
> library with better performance.
> 
> Use it to increase the single processing length of the
> exfat_find_free_bitmap function, from single-byte search to long type.
> 
> Signed-off-by: John Sanpe <sanpeqf@gmail.com>

Looks good. Thanks for your patch.
Acked-by: Sungjong Seo <sj1557.seo@samsung.com>

> ---
>  fs/exfat/balloc.c   | 41 +++++++++++++++--------------------------
>  fs/exfat/exfat_fs.h |  3 +--
>  2 files changed, 16 insertions(+), 28 deletions(-)
> 
> diff --git a/fs/exfat/balloc.c b/fs/exfat/balloc.c index
> 3e3e9e4cce2f..4bacbb0cf5da 100644
> --- a/fs/exfat/balloc.c
> +++ b/fs/exfat/balloc.c
> @@ -14,29 +14,15 @@
>  #if BITS_PER_LONG == 32
>  #define __le_long __le32
>  #define lel_to_cpu(A) le32_to_cpu(A)
> +#define cpu_to_lel(A) cpu_to_le32(A)
>  #elif BITS_PER_LONG == 64
>  #define __le_long __le64
>  #define lel_to_cpu(A) le64_to_cpu(A)
> +#define cpu_to_lel(A) cpu_to_le64(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*/
> -	0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,/* 40 ~
> 59*/
> -	0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,/* 60 ~
> 79*/
> -	0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2,/* 80 ~
> 99*/
> -	0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3,/*100 ~
> 119*/
> -	0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,/*120 ~
> 139*/
> -	0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,/*140 ~
> 159*/
> -	0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2,/*160 ~
> 179*/
> -	0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3,/*180 ~
> 199*/
> -	0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,/*200 ~
> 219*/
> -	0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,/*220 ~
> 239*/
> -	0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0                /*240 ~
> 254*/
> -};
> -
>  /*
>   *  Allocation Bitmap Management Functions
>   */
> @@ -195,32 +181,35 @@ unsigned int exfat_find_free_bitmap(struct
> super_block *sb, unsigned int clu)  {
>  	unsigned int i, map_i, map_b, ent_idx;
>  	unsigned int clu_base, clu_free;
> -	unsigned char k, clu_mask;
> +	unsigned long clu_bits, clu_mask;
>  	struct exfat_sb_info *sbi = EXFAT_SB(sb);
> +	__le_long bitval;
> 
>  	WARN_ON(clu < EXFAT_FIRST_CLUSTER);
> -	ent_idx = CLUSTER_TO_BITMAP_ENT(clu);
> -	clu_base = BITMAP_ENT_TO_CLUSTER(ent_idx & ~(BITS_PER_BYTE_MASK));
> +	ent_idx = ALIGN_DOWN(CLUSTER_TO_BITMAP_ENT(clu), BITS_PER_LONG);
> +	clu_base = BITMAP_ENT_TO_CLUSTER(ent_idx);
>  	clu_mask = IGNORED_BITS_REMAINED(clu, clu_base);
> 
>  	map_i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx);
>  	map_b = BITMAP_OFFSET_BYTE_IN_SECTOR(sb, ent_idx);
> 
>  	for (i = EXFAT_FIRST_CLUSTER; i < sbi->num_clusters;
> -	     i += BITS_PER_BYTE) {
> -		k = *(sbi->vol_amap[map_i]->b_data + map_b);
> +	     i += BITS_PER_LONG) {
> +		bitval = *(__le_long *)(sbi->vol_amap[map_i]->b_data +
> map_b);
>  		if (clu_mask > 0) {
> -			k |= clu_mask;
> +			bitval |= cpu_to_lel(clu_mask);
>  			clu_mask = 0;
>  		}
> -		if (k < 0xFF) {
> -			clu_free = clu_base + free_bit[k];
> +		if (bitval != ULONG_MAX) {
> +			clu_bits = lel_to_cpu(bitval);
> +			clu_free = clu_base + ffz(clu_bits);
>  			if (clu_free < sbi->num_clusters)
>  				return clu_free;
>  		}
> -		clu_base += BITS_PER_BYTE;
> +		clu_base += BITS_PER_LONG;
> +		map_b += sizeof(long);
> 
> -		if (++map_b >= sb->s_blocksize ||
> +		if (map_b >= sb->s_blocksize ||
>  		    clu_base >= sbi->num_clusters) {
>  			if (++map_i >= sbi->map_sectors) {
>  				clu_base = EXFAT_FIRST_CLUSTER;
> diff --git a/fs/exfat/exfat_fs.h b/fs/exfat/exfat_fs.h index
> a7a2c35d74fb..8030780a199b 100644
> --- a/fs/exfat/exfat_fs.h
> +++ b/fs/exfat/exfat_fs.h
> @@ -135,8 +135,7 @@ enum {
>  #define BITMAP_OFFSET_BIT_IN_SECTOR(sb, ent) (ent &
> BITS_PER_SECTOR_MASK(sb))  #define BITMAP_OFFSET_BYTE_IN_SECTOR(sb, ent) \
>  	((ent / BITS_PER_BYTE) & ((sb)->s_blocksize - 1))
> -#define BITS_PER_BYTE_MASK	0x7
> -#define IGNORED_BITS_REMAINED(clu, clu_base) ((1 << ((clu) - (clu_base)))
> - 1)
> +#define IGNORED_BITS_REMAINED(clu, clu_base) ((1UL << ((clu) -
> +(clu_base))) - 1)
> 
>  #define ES_ENTRY_NUM(name_len)	(ES_IDX_LAST_FILENAME(name_len) + 1)
>  /* 19 entries = 1 file entry + 1 stream entry + 17 filename entries */
> --
> 2.43.0