f2fs: refactor __find_rev_next_{zero}_bit
Subsystems (2)
Jaegeuk Kim
maintainerPATCH 1/1 f2fs: refactor __find_rev_next_{zero}_bit
This patch refactors __find_rev_next_{zero}_bit which was disabled previously due to bugs.
Signed-off-by Jaegeuk Kim <[email protected]>
--- fs/f2fs/segment.c | 106 +++++++++++++++++++++++++----------------------------- 1 file changed, 49 insertions(+), 57 deletions(-)
fs/f2fs/segment.c +49 -57
@@ -29,6 +29,21 @@ static struct kmem_cache *discard_entry_slab;static struct kmem_cache *sit_entry_set_slab;static struct kmem_cache *inmem_entry_slab; +static unsigned long __reverse_ulong (unsigned char *str) +{ +unsigned long tmp =0 ; +int shift =24 , idx =0 ; + +#if BITS_PER_LONG ==64 + shift =56 ; +#endif +while (shift >=0 ) { + tmp |= (unsigned long )str[idx++] << shift; + shift -=BITS_PER_BYTE ; + } +return tmp; +} +/* * __reverse_ffs is copied from include/asm-generic/bitops/__ffs.h since * MSB and LSB are reversed in a byte by f2fs_set_bit.
@@ -38,27 +53,31 @@ static inline unsigned long __reverse_ffs(unsigned long word)int num =0 ;#if BITS_PER_LONG ==64 -if ((word &0xffffffff ) ==0 ) { +if ((word &0xffffffff00000000 ) ==0 ) num +=32 ; +else word >>=32 ; - }#endif -if ((word &0xffff ) ==0 ) { +if ((word &0xffff0000 ) ==0 ) num +=16 ; +else word >>=16 ; - } -if ((word &0xff ) ==0 ) { + +if ((word &0xff00 ) ==0 ) num +=8 ; +else word >>=8 ; - } +if ((word &0xf0 ) ==0 ) num +=4 ;else word >>=4 ; +if ((word &0xc ) ==0 ) num +=2 ;else word >>=2 ; +if ((word &0x2 ) ==0 ) num +=1 ;return num;
@@ -68,26 +87,16 @@ static inline unsigned long __reverse_ffs(unsigned long word)* __find_rev_next(_zero)_bit is copied from lib/find_next_bit.c because * f2fs_set_bit makes MSB and LSB reversed in a byte. * Example: -* LSB <--> MSB -* f2fs_set_bit(0, bitmap) => 0000 0001 -* f2fs_set_bit(7, bitmap) => 1000 0000 +* MSB <--> LSB +* f2fs_set_bit(0, bitmap) => 1000 0000 +* f2fs_set_bit(7, bitmap) => 0000 0001 */ static unsigned long __find_rev_next_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { -while (!f2fs_test_bit (offset, (unsigned char *)addr)) - offset++; - -if (offset > size) - offset = size; - -return offset; -#if 0 const unsigned long *p = addr +BIT_WORD (offset);unsigned long result = offset & ~(BITS_PER_LONG -1 );unsigned long tmp; -unsigned long mask, submask; -unsigned long quot, rest;if (offset >= size)return size;
@@ -97,14 +106,9 @@ static unsigned long __find_rev_next_bit(const unsigned long *addr,if (!offset) goto aligned; - tmp = *(p++); - quot = (offset >>3 ) <<3 ; - rest = offset &0x7 ; - mask = ~0UL << quot; - submask = (unsigned char )(0xff << rest) >> rest; - submask <<= quot; - mask &= submask; - tmp &= mask; + tmp =__reverse_ulong ((unsigned char *)p); + tmp &= ~0UL >> offset; +if (size <BITS_PER_LONG ) goto found_first;if (tmp)
@@ -112,42 +116,34 @@ static unsigned long __find_rev_next_bit(const unsigned long *addr, size -=BITS_PER_LONG ; result +=BITS_PER_LONG ; + p++; aligned:while (size & ~(BITS_PER_LONG -1 )) { - tmp = *(p++); + tmp =__reverse_ulong ((unsigned char *)p);if (tmp) goto found_middle; result +=BITS_PER_LONG ; size -=BITS_PER_LONG ; + p++; }if (!size)return result; - tmp = *p; + + tmp =__reverse_ulong ((unsigned char *)p); found_first: - tmp &= (~0UL >> (BITS_PER_LONG - size)); -if (tmp ==0UL )/* Are any bits set? */ + tmp &= (~0UL << (BITS_PER_LONG - size)); +if (!tmp)/* Are any bits set? */ return result + size;/* Nope. */ found_middle:return result +__reverse_ffs (tmp); -#endif }static unsigned long __find_rev_next_zero_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { -while (f2fs_test_bit (offset, (unsigned char *)addr)) - offset++; - -if (offset > size) - offset = size; - -return offset; -#if 0 const unsigned long *p = addr +BIT_WORD (offset);unsigned long result = offset & ~(BITS_PER_LONG -1 );unsigned long tmp; -unsigned long mask, submask; -unsigned long quot, rest;if (offset >= size)return size;
@@ -157,40 +153,36 @@ static unsigned long __find_rev_next_zero_bit(const unsigned long *addr,if (!offset) goto aligned; - tmp = *(p++); - quot = (offset >>3 ) <<3 ; - rest = offset &0x7 ; - mask = ~(~0UL << quot); - submask = (unsigned char )~((unsigned char )(0xff << rest) >> rest); - submask <<= quot; - mask += submask; - tmp |= mask; + tmp =__reverse_ulong ((unsigned char *)p); + tmp |= ~((~0UL << offset) >> offset); +if (size <BITS_PER_LONG ) goto found_first; -if (~tmp) +if (tmp != ~0UL ) goto found_middle; size -=BITS_PER_LONG ; result +=BITS_PER_LONG ; + p++; aligned:while (size & ~(BITS_PER_LONG -1 )) { - tmp = *(p++); -if (~tmp) + tmp =__reverse_ulong ((unsigned char *)p); +if (tmp != ~0UL ) goto found_middle; result +=BITS_PER_LONG ; size -=BITS_PER_LONG ; + p++; }if (!size)return result; - tmp = *p; + tmp =__reverse_ulong ((unsigned char *)p); found_first: - tmp |= ~0UL << size; -if (tmp == ~0UL )/* Are any bits zero? */ + tmp |= ~(~0UL << (BITS_PER_LONG - size)); +if (tmp == ~0UL )/* Are any bits zero? */ return result + size;/* Nope. */ found_middle:return result +__reverse_ffz (tmp); -#endif }void register_inmem_page (struct inode *inode,struct page *page)
Signature · 1 line
2.1.1
Jaegeuk Kim
maintainerQuoted 35 lines · Jaegeuk Kim
This patch refactors __find_rev_next_{zero}_bit which was disabled previously due to bugs.
Signed-off-by Jaegeuk Kim <[email protected]>--- fs/f2fs/segment.c | 106 +++++++++++++++++++++++++----------------------------- 1 file changed, 49 insertions(+), 57 deletions(-)fs/f2fs/segment.c +15
-0@@ -29,6 +29,21 @@ static struct kmem_cache *discard_entry_slab;static struct kmem_cache *sit_entry_set_slab;static struct kmem_cache *inmem_entry_slab; +static unsigned long __reverse_ulong (unsigned char *str) +{ +unsigned long tmp =0 ; +int shift =24 , idx =0 ; + +#if BITS_PER_LONG ==64 + shift =56 ; +#endif +while (shift >=0 ) { + tmp |= (unsigned long )str[idx++] << shift; + shift -=BITS_PER_BYTE ; + } +return tmp; +} +/* * __reverse_ffs is copied from include/asm-generic/bitops/__ffs.h since * MSB and LSB are reversed in a byte by f2fs_set_bit.
fs/f2fs/segment.c static inline unsigned long __reverse_ffs(unsigned long word) · line 56
Quoted 5 lines
fs/f2fs/segment.c +1
-1@@ -38,27 +53,31 @@ static inline unsigned long __reverse_ffs(unsigned long word)int num =0 ;#if BITS_PER_LONG ==64 -if ((word &0xffffffff ) ==0 ) { +if ((word &0xffffffff00000000 ) ==0 )
I fixed the sparse warning by modifying:
if ((word & 0xffffffff00000000UL) == 0)
Thanks,
Quoted 184 lines
fs/f2fs/segment.c +33
-56num +=32 ; + else word >>= 32; - }#endif -if ((word &0xffff ) ==0 ) { +if ((word &0xffff0000 ) ==0 ) num +=16 ; +else word >>=16 ; - } -if ((word &0xff ) ==0 ) { + +if ((word &0xff00 ) ==0 ) num +=8 ; +else word >>=8 ; - } +if ((word &0xf0 ) ==0 ) num +=4 ;else word >>=4 ; +if ((word &0xc ) ==0 ) num +=2 ;else word >>=2 ; +if ((word &0x2 ) ==0 ) num +=1 ;return num;@@ -68,26 +87,16 @@ static inline unsigned long __reverse_ffs(unsigned long word)* __find_rev_next(_zero)_bit is copied from lib/find_next_bit.c because * f2fs_set_bit makes MSB and LSB reversed in a byte. * Example: -* LSB <--> MSB -* f2fs_set_bit(0, bitmap) => 0000 0001 -* f2fs_set_bit(7, bitmap) => 1000 0000 +* MSB <--> LSB +* f2fs_set_bit(0, bitmap) => 1000 0000 +* f2fs_set_bit(7, bitmap) => 0000 0001 */ static unsigned long __find_rev_next_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { -while (!f2fs_test_bit (offset, (unsigned char *)addr)) - offset++; - -if (offset > size) - offset = size; - -return offset; -#if 0 const unsigned long *p = addr +BIT_WORD (offset);unsigned long result = offset & ~(BITS_PER_LONG -1 );unsigned long tmp; -unsigned long mask, submask; -unsigned long quot, rest;if (offset >= size)return size;@@ -97,14 +106,9 @@ static unsigned long __find_rev_next_bit(const unsigned long *addr,if (!offset) goto aligned; - tmp = *(p++); - quot = (offset >>3 ) <<3 ; - rest = offset &0x7 ; - mask = ~0UL << quot; - submask = (unsigned char )(0xff << rest) >> rest; - submask <<= quot; - mask &= submask; - tmp &= mask; + tmp =__reverse_ulong ((unsigned char *)p); + tmp &= ~0UL >> offset; +if (size <BITS_PER_LONG ) goto found_first;if (tmp)@@ -112,42 +116,34 @@ static unsigned long __find_rev_next_bit(const unsigned long *addr, size -=BITS_PER_LONG ; result +=BITS_PER_LONG ; + p++; aligned:while (size & ~(BITS_PER_LONG -1 )) { - tmp = *(p++); + tmp =__reverse_ulong ((unsigned char *)p);if (tmp) goto found_middle; result +=BITS_PER_LONG ; size -=BITS_PER_LONG ; + p++; }if (!size)return result; - tmp = *p; + + tmp =__reverse_ulong ((unsigned char *)p); found_first: - tmp &= (~0UL >> (BITS_PER_LONG - size)); -if (tmp ==0UL )/* Are any bits set? */ + tmp &= (~0UL << (BITS_PER_LONG - size)); +if (!tmp)/* Are any bits set? */ return result + size;/* Nope. */ found_middle:return result +__reverse_ffs (tmp); -#endif }static unsigned long __find_rev_next_zero_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { -while (f2fs_test_bit (offset, (unsigned char *)addr)) - offset++; - -if (offset > size) - offset = size; - -return offset; -#if 0 const unsigned long *p = addr +BIT_WORD (offset);unsigned long result = offset & ~(BITS_PER_LONG -1 );unsigned long tmp; -unsigned long mask, submask; -unsigned long quot, rest;if (offset >= size)return size;@@ -157,40 +153,36 @@ static unsigned long __find_rev_next_zero_bit(const unsigned long *addr,if (!offset) goto aligned; - tmp = *(p++); - quot = (offset >>3 ) <<3 ; - rest = offset &0x7 ; - mask = ~(~0UL << quot); - submask = (unsigned char )~((unsigned char )(0xff << rest) >> rest); - submask <<= quot; - mask += submask; - tmp |= mask; + tmp =__reverse_ulong ((unsigned char *)p); + tmp |= ~((~0UL << offset) >> offset); +if (size <BITS_PER_LONG ) goto found_first; -if (~tmp) +if (tmp != ~0UL ) goto found_middle; size -=BITS_PER_LONG ; result +=BITS_PER_LONG ; + p++; aligned:while (size & ~(BITS_PER_LONG -1 )) { - tmp = *(p++); -if (~tmp) + tmp =__reverse_ulong ((unsigned char *)p); +if (tmp != ~0UL ) goto found_middle; result +=BITS_PER_LONG ; size -=BITS_PER_LONG ; + p++; }if (!size)return result; - tmp = *p; + tmp =__reverse_ulong ((unsigned char *)p); found_first: - tmp |= ~0UL << size; -if (tmp == ~0UL )/* Are any bits zero? */ + tmp |= ~(~0UL << (BITS_PER_LONG - size)); +if (tmp == ~0UL )/* Are any bits zero? */ return result + size;/* Nope. */ found_middle:return result +__reverse_ffz (tmp); -#endif }void register_inmem_page (struct inode *inode,struct page *page)Signature · 1 line
2.1.1
------------------------------------------------------------------------------
Hi Jaegeuk,
Quoted 10 lines
-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Thursday, October 22, 2015 6:30 AM
To: [email protected]; [email protected]; [email protected]
Subject: Re: [f2fs-dev] [PATCH] f2fs: refactor __find_rev_next_{zero}_bitQuoted 2 lines · Jaegeuk Kim
This patch refactors __find_rev_next_{zero}_bit which was disabled previously due to bugs.
Actually I didn't know the history here, could you please explain details about the bugs? then I can do the review.
Thanks,
Quoted 234 lines
Quoted 33 lines
Signed-off-by Jaegeuk Kim <[email protected]>--- fs/f2fs/segment.c | 106 +++++++++++++++++++++++++----------------------------- 1 file changed, 49 insertions(+), 57 deletions(-)fs/f2fs/segment.c +15
-0@@ -29,6 +29,21 @@ static struct kmem_cache *discard_entry_slab;static struct kmem_cache *sit_entry_set_slab;static struct kmem_cache *inmem_entry_slab; +static unsigned long __reverse_ulong (unsigned char *str) +{ +unsigned long tmp =0 ; +int shift =24 , idx =0 ; + +#if BITS_PER_LONG ==64 + shift =56 ; +#endif +while (shift >=0 ) { + tmp |= (unsigned long )str[idx++] << shift; + shift -=BITS_PER_BYTE ; + } +return tmp; +} +/* * __reverse_ffs is copied from include/asm-generic/bitops/__ffs.h since * MSB and LSB are reversed in a byte by f2fs_set_bit. fs/f2fs/segment.c static inline unsigned long __reverse_ffs(unsigned long word) · line 56
Quoted 5 lines
fs/f2fs/segment.c +1
-1@@ -38,27 +53,31 @@ static inline unsigned long __reverse_ffs(unsigned long word)int num =0 ;#if BITS_PER_LONG ==64 -if ((word &0xffffffff ) ==0 ) { +if ((word &0xffffffff00000000 ) ==0 )I fixed the sparse warning by modifying:
if ((word & 0xffffffff00000000UL) == 0)Thanks,
Quoted 183 lines
fs/f2fs/segment.c +33
-57num +=32 ; + else word >>= 32; - }#endif -if ((word &0xffff ) ==0 ) { +if ((word &0xffff0000 ) ==0 ) num +=16 ; +else word >>=16 ; - } -if ((word &0xff ) ==0 ) { + +if ((word &0xff00 ) ==0 ) num +=8 ; +else word >>=8 ; - } +if ((word &0xf0 ) ==0 ) num +=4 ;else word >>=4 ; +if ((word &0xc ) ==0 ) num +=2 ;else word >>=2 ; +if ((word &0x2 ) ==0 ) num +=1 ;return num;@@ -68,26 +87,16 @@ static inline unsigned long __reverse_ffs(unsigned long word)* __find_rev_next(_zero)_bit is copied from lib/find_next_bit.c because * f2fs_set_bit makes MSB and LSB reversed in a byte. * Example: -* LSB <--> MSB -* f2fs_set_bit(0, bitmap) => 0000 0001 -* f2fs_set_bit(7, bitmap) => 1000 0000 +* MSB <--> LSB +* f2fs_set_bit(0, bitmap) => 1000 0000 +* f2fs_set_bit(7, bitmap) => 0000 0001 */ static unsigned long __find_rev_next_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { -while (!f2fs_test_bit (offset, (unsigned char *)addr)) - offset++; - -if (offset > size) - offset = size; - -return offset; -#if 0 const unsigned long *p = addr +BIT_WORD (offset);unsigned long result = offset & ~(BITS_PER_LONG -1 );unsigned long tmp; -unsigned long mask, submask; -unsigned long quot, rest;if (offset >= size)return size;@@ -97,14 +106,9 @@ static unsigned long __find_rev_next_bit(const unsigned long *addr,if (!offset) goto aligned; - tmp = *(p++); - quot = (offset >>3 ) <<3 ; - rest = offset &0x7 ; - mask = ~0UL << quot; - submask = (unsigned char )(0xff << rest) >> rest; - submask <<= quot; - mask &= submask; - tmp &= mask; + tmp =__reverse_ulong ((unsigned char *)p); + tmp &= ~0UL >> offset; +if (size <BITS_PER_LONG ) goto found_first;if (tmp)@@ -112,42 +116,34 @@ static unsigned long __find_rev_next_bit(const unsigned long *addr, size -=BITS_PER_LONG ; result +=BITS_PER_LONG ; + p++; aligned:while (size & ~(BITS_PER_LONG -1 )) { - tmp = *(p++); + tmp =__reverse_ulong ((unsigned char *)p);if (tmp) goto found_middle; result +=BITS_PER_LONG ; size -=BITS_PER_LONG ; + p++; }if (!size)return result; - tmp = *p; + + tmp =__reverse_ulong ((unsigned char *)p); found_first: - tmp &= (~0UL >> (BITS_PER_LONG - size)); -if (tmp ==0UL )/* Are any bits set? */ + tmp &= (~0UL << (BITS_PER_LONG - size)); +if (!tmp)/* Are any bits set? */ return result + size;/* Nope. */ found_middle:return result +__reverse_ffs (tmp); -#endif }static unsigned long __find_rev_next_zero_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { -while (f2fs_test_bit (offset, (unsigned char *)addr)) - offset++; - -if (offset > size) - offset = size; - -return offset; -#if 0 const unsigned long *p = addr +BIT_WORD (offset);unsigned long result = offset & ~(BITS_PER_LONG -1 );unsigned long tmp; -unsigned long mask, submask; -unsigned long quot, rest;if (offset >= size)return size;@@ -157,40 +153,36 @@ static unsigned long __find_rev_next_zero_bit(const unsigned long *addr,if (!offset) goto aligned; - tmp = *(p++); - quot = (offset >>3 ) <<3 ; - rest = offset &0x7 ; - mask = ~(~0UL << quot); - submask = (unsigned char )~((unsigned char )(0xff << rest) >> rest); - submask <<= quot; - mask += submask; - tmp |= mask; + tmp =__reverse_ulong ((unsigned char *)p); + tmp |= ~((~0UL << offset) >> offset); +if (size <BITS_PER_LONG ) goto found_first; -if (~tmp) +if (tmp != ~0UL ) goto found_middle; size -=BITS_PER_LONG ; result +=BITS_PER_LONG ; + p++; aligned:while (size & ~(BITS_PER_LONG -1 )) { - tmp = *(p++); -if (~tmp) + tmp =__reverse_ulong ((unsigned char *)p); +if (tmp != ~0UL ) goto found_middle; result +=BITS_PER_LONG ; size -=BITS_PER_LONG ; + p++; }if (!size)return result; - tmp = *p; + tmp =__reverse_ulong ((unsigned char *)p); found_first: - tmp |= ~0UL << size; -if (tmp == ~0UL )/* Are any bits zero? */ + tmp |= ~(~0UL << (BITS_PER_LONG - size)); +if (tmp == ~0UL )/* Are any bits zero? */ return result + size;/* Nope. */ found_middle:return result +__reverse_ffz (tmp); -#endif }void register_inmem_page (struct inode *inode,struct page *page) --Quoted 1 line
2.1.1
------------------------------------------------------------------------------
_______________________________________________
Linux-f2fs-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
Jaegeuk Kim
maintainerHi Chao,
Quoted 9 lines · Chao Yu
Hi Jaegeuk,
Quoted 7 lines
-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Thursday, October 22, 2015 6:30 AM
To: [email protected]; [email protected]; [email protected]
Subject: Re: [f2fs-dev] [PATCH] f2fs: refactor __find_rev_next_{zero}_bit
Quoted 6 lines
Quoted 3 lines · Jaegeuk Kim
Quoted 2 lines
This patch refactors __find_rev_next_{zero}_bit which was disabled previously due to bugs.
Actually I didn't know the history here, could you please explain details about the bugs? then I can do the review.
When I disabled the existing function by:
commit e19ef527aa32f057710ec842fe656bffc263b0bb
Author: Jaegeuk Kim <[email protected]> Date: Mon May 18 11:45:15 2015 -0700
f2fs: avoid buggy functions
I found a mismatch of results between the existing __find_rev_next_bit and f2fs_test_bit work. I remember it happened on __find_rev_next_bit sometimes by xfstests which include trim_fs.
(I didn't get an error from __find_rev_zero_bit though.)
Since I have no time to investigate the bug in more detail at that time, I just disabled it. But, now I'm trying to refactor the flow to fix this.
Thanks,
Quoted 237 lines
Thanks,
Quoted 234 lines
Quoted 33 lines
Signed-off-by Jaegeuk Kim <[email protected]>--- fs/f2fs/segment.c | 106 +++++++++++++++++++++++++----------------------------- 1 file changed, 49 insertions(+), 57 deletions(-)fs/f2fs/segment.c +15
-0@@ -29,6 +29,21 @@ static struct kmem_cache *discard_entry_slab;static struct kmem_cache *sit_entry_set_slab;static struct kmem_cache *inmem_entry_slab; +static unsigned long __reverse_ulong (unsigned char *str) +{ +unsigned long tmp =0 ; +int shift =24 , idx =0 ; + +#if BITS_PER_LONG ==64 + shift =56 ; +#endif +while (shift >=0 ) { + tmp |= (unsigned long )str[idx++] << shift; + shift -=BITS_PER_BYTE ; + } +return tmp; +} +/* * __reverse_ffs is copied from include/asm-generic/bitops/__ffs.h since * MSB and LSB are reversed in a byte by f2fs_set_bit. fs/f2fs/segment.c static inline unsigned long __reverse_ffs(unsigned long word) · line 56
Quoted 5 lines
fs/f2fs/segment.c +1
-1@@ -38,27 +53,31 @@ static inline unsigned long __reverse_ffs(unsigned long word)int num =0 ;#if BITS_PER_LONG ==64 -if ((word &0xffffffff ) ==0 ) { +if ((word &0xffffffff00000000 ) ==0 )I fixed the sparse warning by modifying:
if ((word & 0xffffffff00000000UL) == 0)Thanks,
Quoted 183 lines
fs/f2fs/segment.c +33
-57num +=32 ; + else word >>= 32; - }#endif -if ((word &0xffff ) ==0 ) { +if ((word &0xffff0000 ) ==0 ) num +=16 ; +else word >>=16 ; - } -if ((word &0xff ) ==0 ) { + +if ((word &0xff00 ) ==0 ) num +=8 ; +else word >>=8 ; - } +if ((word &0xf0 ) ==0 ) num +=4 ;else word >>=4 ; +if ((word &0xc ) ==0 ) num +=2 ;else word >>=2 ; +if ((word &0x2 ) ==0 ) num +=1 ;return num;@@ -68,26 +87,16 @@ static inline unsigned long __reverse_ffs(unsigned long word)* __find_rev_next(_zero)_bit is copied from lib/find_next_bit.c because * f2fs_set_bit makes MSB and LSB reversed in a byte. * Example: -* LSB <--> MSB -* f2fs_set_bit(0, bitmap) => 0000 0001 -* f2fs_set_bit(7, bitmap) => 1000 0000 +* MSB <--> LSB +* f2fs_set_bit(0, bitmap) => 1000 0000 +* f2fs_set_bit(7, bitmap) => 0000 0001 */ static unsigned long __find_rev_next_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { -while (!f2fs_test_bit (offset, (unsigned char *)addr)) - offset++; - -if (offset > size) - offset = size; - -return offset; -#if 0 const unsigned long *p = addr +BIT_WORD (offset);unsigned long result = offset & ~(BITS_PER_LONG -1 );unsigned long tmp; -unsigned long mask, submask; -unsigned long quot, rest;if (offset >= size)return size;@@ -97,14 +106,9 @@ static unsigned long __find_rev_next_bit(const unsigned long *addr,if (!offset) goto aligned; - tmp = *(p++); - quot = (offset >>3 ) <<3 ; - rest = offset &0x7 ; - mask = ~0UL << quot; - submask = (unsigned char )(0xff << rest) >> rest; - submask <<= quot; - mask &= submask; - tmp &= mask; + tmp =__reverse_ulong ((unsigned char *)p); + tmp &= ~0UL >> offset; +if (size <BITS_PER_LONG ) goto found_first;if (tmp)@@ -112,42 +116,34 @@ static unsigned long __find_rev_next_bit(const unsigned long *addr, size -=BITS_PER_LONG ; result +=BITS_PER_LONG ; + p++; aligned:while (size & ~(BITS_PER_LONG -1 )) { - tmp = *(p++); + tmp =__reverse_ulong ((unsigned char *)p);if (tmp) goto found_middle; result +=BITS_PER_LONG ; size -=BITS_PER_LONG ; + p++; }if (!size)return result; - tmp = *p; + + tmp =__reverse_ulong ((unsigned char *)p); found_first: - tmp &= (~0UL >> (BITS_PER_LONG - size)); -if (tmp ==0UL )/* Are any bits set? */ + tmp &= (~0UL << (BITS_PER_LONG - size)); +if (!tmp)/* Are any bits set? */ return result + size;/* Nope. */ found_middle:return result +__reverse_ffs (tmp); -#endif }static unsigned long __find_rev_next_zero_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { -while (f2fs_test_bit (offset, (unsigned char *)addr)) - offset++; - -if (offset > size) - offset = size; - -return offset; -#if 0 const unsigned long *p = addr +BIT_WORD (offset);unsigned long result = offset & ~(BITS_PER_LONG -1 );unsigned long tmp; -unsigned long mask, submask; -unsigned long quot, rest;if (offset >= size)return size;@@ -157,40 +153,36 @@ static unsigned long __find_rev_next_zero_bit(const unsigned long *addr,if (!offset) goto aligned; - tmp = *(p++); - quot = (offset >>3 ) <<3 ; - rest = offset &0x7 ; - mask = ~(~0UL << quot); - submask = (unsigned char )~((unsigned char )(0xff << rest) >> rest); - submask <<= quot; - mask += submask; - tmp |= mask; + tmp =__reverse_ulong ((unsigned char *)p); + tmp |= ~((~0UL << offset) >> offset); +if (size <BITS_PER_LONG ) goto found_first; -if (~tmp) +if (tmp != ~0UL ) goto found_middle; size -=BITS_PER_LONG ; result +=BITS_PER_LONG ; + p++; aligned:while (size & ~(BITS_PER_LONG -1 )) { - tmp = *(p++); -if (~tmp) + tmp =__reverse_ulong ((unsigned char *)p); +if (tmp != ~0UL ) goto found_middle; result +=BITS_PER_LONG ; size -=BITS_PER_LONG ; + p++; }if (!size)return result; - tmp = *p; + tmp =__reverse_ulong ((unsigned char *)p); found_first: - tmp |= ~0UL << size; -if (tmp == ~0UL )/* Are any bits zero? */ + tmp |= ~(~0UL << (BITS_PER_LONG - size)); +if (tmp == ~0UL )/* Are any bits zero? */ return result + size;/* Nope. */ found_middle:return result +__reverse_ffz (tmp); -#endif }void register_inmem_page (struct inode *inode,struct page *page) --Quoted 1 line
2.1.1
------------------------------------------------------------------------------
_______________________________________________
Linux-f2fs-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
In bitmaps of f2fs, bytes are sorted in ascending order, but bits in a byte are sorted in descending order. It seems to be the reason why __reverse_ulong is needed.
May I ask why f2fs bitmap apply such order?
Quoted 33 lines
-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Friday, October 23, 2015 12:36 AM
To: Chao Yu
Cc: [email protected]; [email protected]; [email protected]
Subject: Re: [f2fs-dev] [PATCH] f2fs: refactor __find_rev_next_{zero}_bitHi Chao,
Quoted 10 lines · Chao Yu
Hi Jaegeuk,
Quoted 8 lines
-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Thursday, October 22, 2015 6:30 AM
To: [email protected]; [email protected]; [email protected]
Subject: Re: [f2fs-dev] [PATCH] f2fs: refactor __find_rev_next_{zero}_bitQuoted 6 lines
Quoted 3 lines · Jaegeuk Kim
Quoted 2 lines
This patch refactors __find_rev_next_{zero}_bit which was disabled previously due to bugs.
Actually I didn't know the history here, could you please explain details about the bugs? then I can do the review.
When I disabled the existing function by:
commit
e19ef527aa32f057710ec842fe656bffc263b0bbAuthor: Jaegeuk Kim <[email protected]> Date: Mon May 18 11:45:15 2015 -0700
Quoted 7 lines
f2fs: avoid buggy functions
I found a mismatch of results between the existing
__find_rev_next_bitandf2fs_test_bitwork. I remember it happened on__find_rev_next_bitsometimes by xfstests which includetrim_fs.
(I didn't get an error from__find_rev_zero_bitthough.)Since I have no time to investigate the bug in more detail at that time, I just disabled it. But, now I'm trying to refactor the
flow to fix
Quoted 237 lines
this.
Thanks,
Quoted 232 lines
Thanks,
Quoted 229 lines
Quoted 33 lines
Signed-off-by Jaegeuk Kim <[email protected]>--- fs/f2fs/segment.c | 106 +++++++++++++++++++++++++----------------------------- 1 file changed, 49 insertions(+), 57 deletions(-)fs/f2fs/segment.c index renamed from fs/f2fs/segment.c +0
-0f37c212..50afc93 100644
fs/f2fs/segment.c +0
-0@@ -29,6 +29,21 @@ static struct kmem_cache *discard_entry_slab;static struct
kmem_cache*sit_entry_set_slab; static structkmem_cache*inmem_entry_slab;fs/f2fs/segment.c +14
-0+static unsigned long __reverse_ulong (unsigned char *str) { +unsigned long tmp =0 ; +int shift =24 , idx =0 ; + +#if BITS_PER_LONG ==64 + shift =56 ; +#endif +while (shift >=0 ) { + tmp |= (unsigned long )str[idx++] << shift; + shift -=BITS_PER_BYTE ; + } +return tmp; +} +/* * __reverse_ffs is copied from include/asm-generic/bitops/__ffs.h since * MSB and LSB are reversed in a byte by f2fs_set_bit. fs/f2fs/segment.c static inline unsigned long __reverse_ffs(unsigned long word) · line 56
Quoted 5 lines
fs/f2fs/segment.c +1
-1@@ -38,27 +53,31 @@ static inline unsigned long __reverse_ffs(unsigned long word)int num =0 ;#if BITS_PER_LONG ==64 -if ((word &0xffffffff ) ==0 ) { +if ((word &0xffffffff00000000 ) ==0 )I fixed the sparse warning by modifying:
if ((word & 0xffffffff00000000UL) == 0)Thanks,
Quoted 178 lines
fs/f2fs/segment.c +33
-55num +=32 ; + else word >>= 32; - }#endif -if ((word &0xffff ) ==0 ) { +if ((word &0xffff0000 ) ==0 ) num +=16 ; +else word >>=16 ; - } -if ((word &0xff ) ==0 ) { + +if ((word &0xff00 ) ==0 ) num +=8 ; +else word >>=8 ; - } +if ((word &0xf0 ) ==0 ) num +=4 ;else word >>=4 ; +if ((word &0xc ) ==0 ) num +=2 ;else word >>=2 ; +if ((word &0x2 ) ==0 ) num +=1 ;return num;@@ -68,26 +87,16 @@ static inline unsigned long __reverse_ffs(unsigned long word)* __find_rev_next(_zero)_bit is copied from lib/find_next_bit.c because * f2fs_set_bit makes MSB and LSB reversed in a byte. * Example: -* LSB <--> MSB -* f2fs_set_bit(0, bitmap) => 0000 0001 -* f2fs_set_bit(7, bitmap) => 1000 0000 +* MSB <--> LSB +* f2fs_set_bit(0, bitmap) => 1000 0000 +* f2fs_set_bit(7, bitmap) => 0000 0001 */ static unsigned long __find_rev_next_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { -while (!f2fs_test_bit (offset, (unsigned char *)addr)) - offset++; - -if (offset > size) - offset = size; - -return offset; -#if 0 const unsigned long *p = addr +BIT_WORD (offset);unsigned long result = offset & ~(BITS_PER_LONG -1 );unsigned long tmp; -unsigned long mask, submask; -unsigned long quot, rest;if (offset >= size)return size;@@ -97,14 +106,9 @@ static unsigned long __find_rev_next_bit(const unsigned long *addr,if (!offset) goto aligned; - tmp = *(p++); - quot = (offset >>3 ) <<3 ; - rest = offset &0x7 ; - mask = ~0UL << quot; - submask = (unsigned char )(0xff << rest) >> rest; - submask <<= quot; - mask &= submask; - tmp &= mask; + tmp =__reverse_ulong ((unsigned char *)p); + tmp &= ~0UL >> offset; +if (size <BITS_PER_LONG ) goto found_first;if (tmp)@@ -112,42 +116,34 @@ static unsigned long __find_rev_next_bit(const unsigned long *addr, size -= BITS_PER_LONG; result +=BITS_PER_LONG ; + p++; aligned:while (size & ~(BITS_PER_LONG -1 )) { - tmp = *(p++); + tmp =__reverse_ulong ((unsigned char *)p);if (tmp) goto found_middle; result +=BITS_PER_LONG ; size -=BITS_PER_LONG ; + p++; }if (!size)return result; - tmp = *p; + + tmp =__reverse_ulong ((unsigned char *)p); found_first: - tmp &= (~0UL >> (BITS_PER_LONG - size)); -if (tmp ==0UL )/* Are any bits set? */ + tmp &= (~0UL << (BITS_PER_LONG - size)); +if (!tmp)/* Are any bits set? */ return result + size;/* Nope. */ found_middle: return result + __reverse_ffs(tmp); -#endif }static unsigned long __find_rev_next_zero_bit (const unsigned long *addr,unsigned long size,unsigned long offset) { -while (f2fs_test_bit (offset, (unsigned char *)addr)) - offset++; - -if (offset > size) - offset = size; - -return offset; -#if 0 const unsigned long *p = addr +BIT_WORD (offset);unsigned long result = offset & ~(BITS_PER_LONG -1 );unsigned long tmp; -unsigned long mask, submask; -unsigned long quot, rest;if (offset >= size)return size;@@ -157,40 +153,36 @@ static unsigned long __find_rev_next_zero_bit(const unsigned long *addr,if (!offset) goto aligned; - tmp = *(p++); - quot = (offset >>3 ) <<3 ; - rest = offset &0x7 ; - mask = ~(~0UL << quot); - submask = (unsigned char )~((unsigned char )(0xff << rest) >> rest); - submask <<= quot; - mask += submask; - tmp |= mask; + tmp =__reverse_ulong ((unsigned char *)p); + tmp |= ~((~0UL << offset) >> offset); +if (size <BITS_PER_LONG ) goto found_first; -if (~tmp) +if (tmp != ~0UL ) goto found_middle; size -=BITS_PER_LONG ; result +=BITS_PER_LONG ; + p++; aligned:while (size & ~(BITS_PER_LONG -1 )) { - tmp = *(p++); -if (~tmp) + tmp =__reverse_ulong ((unsigned char *)p); +if (tmp != ~0UL ) goto found_middle; result +=BITS_PER_LONG ; size -=BITS_PER_LONG ; + p++; }if (!size)return result; - tmp = *p; + tmp =__reverse_ulong ((unsigned char *)p); found_first: - tmp |= ~0UL << size; -if (tmp == ~0UL )/* Are any bits zero? */ + tmp |= ~(~0UL << (BITS_PER_LONG - size)); +if (tmp == ~0UL )/* Are any bits zero? */ return result + size;/* Nope. */ found_middle: return result + __reverse_ffz(tmp); -#endif }void register_inmem_page (struct inode *inode,struct page *page) --Quoted 1 line
2.1.1
--------------------------------------------------------------------
---------- _______________________________________________ Linux-f2fs-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
Quoted 5 lines
------------------------------------------------------------------------------
_______________________________________________
Linux-f2fs-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
------------------------------------------------------------------------------