* [PATCH] f2fs: refactor __find_rev_next_{zero}_bit
@ 2015-10-21 21:16 Jaegeuk Kim
2015-10-21 22:29 ` Jaegeuk Kim
0 siblings, 1 reply; 7+ messages in thread
From: Jaegeuk Kim @ 2015-10-21 21:16 UTC (permalink / raw)
To: linux-kernel, linux-fsdevel, linux-f2fs-devel; +Cc: Jaegeuk Kim
This patch refactors __find_rev_next_{zero}_bit which was disabled previously
due to bugs.
Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
---
fs/f2fs/segment.c | 106 +++++++++++++++++++++++++-----------------------------
1 file changed, 49 insertions(+), 57 deletions(-)
diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c
index f37c212..50afc93 100644
--- a/fs/f2fs/segment.c
+++ b/fs/f2fs/segment.c
@@ -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)
--
2.1.1
^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH] f2fs: refactor __find_rev_next_{zero}_bit
2015-10-21 21:16 [PATCH] f2fs: refactor __find_rev_next_{zero}_bit Jaegeuk Kim
@ 2015-10-21 22:29 ` Jaegeuk Kim
0 siblings, 0 replies; 7+ messages in thread
From: Jaegeuk Kim @ 2015-10-21 22:29 UTC (permalink / raw)
To: linux-kernel, linux-fsdevel, linux-f2fs-devel
On Wed, Oct 21, 2015 at 02:16:43PM -0700, Jaegeuk Kim wrote:
> This patch refactors __find_rev_next_{zero}_bit which was disabled previously
> due to bugs.
>
> Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
> ---
> fs/f2fs/segment.c | 106 +++++++++++++++++++++++++-----------------------------
> 1 file changed, 49 insertions(+), 57 deletions(-)
>
> diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c
> index f37c212..50afc93 100644
> --- a/fs/f2fs/segment.c
> +++ b/fs/f2fs/segment.c
> @@ -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)
I fixed the sparse warning by modifying:
if ((word & 0xffffffff00000000UL) == 0)
Thanks,
> 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)
> --
> 2.1.1
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] f2fs: refactor __find_rev_next_{zero}_bit
@ 2015-10-21 22:29 ` Jaegeuk Kim
0 siblings, 0 replies; 7+ messages in thread
From: Jaegeuk Kim @ 2015-10-21 22:29 UTC (permalink / raw)
To: linux-kernel, linux-fsdevel, linux-f2fs-devel
On Wed, Oct 21, 2015 at 02:16:43PM -0700, Jaegeuk Kim wrote:
> This patch refactors __find_rev_next_{zero}_bit which was disabled previously
> due to bugs.
>
> Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
> ---
> fs/f2fs/segment.c | 106 +++++++++++++++++++++++++-----------------------------
> 1 file changed, 49 insertions(+), 57 deletions(-)
>
> diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c
> index f37c212..50afc93 100644
> --- a/fs/f2fs/segment.c
> +++ b/fs/f2fs/segment.c
> @@ -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)
I fixed the sparse warning by modifying:
if ((word & 0xffffffff00000000UL) == 0)
Thanks,
> 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)
> --
> 2.1.1
------------------------------------------------------------------------------
^ permalink raw reply [flat|nested] 7+ messages in thread
* RE: [f2fs-dev] [PATCH] f2fs: refactor __find_rev_next_{zero}_bit
2015-10-21 22:29 ` Jaegeuk Kim
(?)
@ 2015-10-22 11:24 ` Chao Yu
2015-10-22 16:36 ` Jaegeuk Kim
-1 siblings, 1 reply; 7+ messages in thread
From: Chao Yu @ 2015-10-22 11:24 UTC (permalink / raw)
To: 'Jaegeuk Kim'; +Cc: linux-kernel, linux-fsdevel, linux-f2fs-devel
Hi Jaegeuk,
> -----Original Message-----
> From: Jaegeuk Kim [mailto:jaegeuk@kernel.org]
> Sent: Thursday, October 22, 2015 6:30 AM
> To: linux-kernel@vger.kernel.org; linux-fsdevel@vger.kernel.org;
> linux-f2fs-devel@lists.sourceforge.net
> Subject: Re: [f2fs-dev] [PATCH] f2fs: refactor __find_rev_next_{zero}_bit
>
> On Wed, Oct 21, 2015 at 02:16:43PM -0700, Jaegeuk Kim wrote:
> > 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,
> >
> > Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
> > ---
> > fs/f2fs/segment.c | 106 +++++++++++++++++++++++++-----------------------------
> > 1 file changed, 49 insertions(+), 57 deletions(-)
> >
> > diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c
> > index f37c212..50afc93 100644
> > --- a/fs/f2fs/segment.c
> > +++ b/fs/f2fs/segment.c
> > @@ -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)
>
> I fixed the sparse warning by modifying:
> if ((word & 0xffffffff00000000UL) == 0)
>
> Thanks,
>
> > 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)
> > --
> > 2.1.1
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Linux-f2fs-devel mailing list
> Linux-f2fs-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [f2fs-dev] [PATCH] f2fs: refactor __find_rev_next_{zero}_bit
2015-10-22 11:24 ` [f2fs-dev] " Chao Yu
@ 2015-10-22 16:36 ` Jaegeuk Kim
2015-11-06 5:41 ` Fan Li
0 siblings, 1 reply; 7+ messages in thread
From: Jaegeuk Kim @ 2015-10-22 16:36 UTC (permalink / raw)
To: Chao Yu; +Cc: linux-kernel, linux-fsdevel, linux-f2fs-devel
Hi Chao,
On Thu, Oct 22, 2015 at 07:24:01PM +0800, Chao Yu wrote:
> Hi Jaegeuk,
>
> > -----Original Message-----
> > From: Jaegeuk Kim [mailto:jaegeuk@kernel.org]
> > Sent: Thursday, October 22, 2015 6:30 AM
> > To: linux-kernel@vger.kernel.org; linux-fsdevel@vger.kernel.org;
> > linux-f2fs-devel@lists.sourceforge.net
> > Subject: Re: [f2fs-dev] [PATCH] f2fs: refactor __find_rev_next_{zero}_bit
> >
> > On Wed, Oct 21, 2015 at 02:16:43PM -0700, Jaegeuk Kim wrote:
> > > 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 <jaegeuk@kernel.org>
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,
>
> Thanks,
>
> > >
> > > Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
> > > ---
> > > fs/f2fs/segment.c | 106 +++++++++++++++++++++++++-----------------------------
> > > 1 file changed, 49 insertions(+), 57 deletions(-)
> > >
> > > diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c
> > > index f37c212..50afc93 100644
> > > --- a/fs/f2fs/segment.c
> > > +++ b/fs/f2fs/segment.c
> > > @@ -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)
> >
> > I fixed the sparse warning by modifying:
> > if ((word & 0xffffffff00000000UL) == 0)
> >
> > Thanks,
> >
> > > 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)
> > > --
> > > 2.1.1
> >
> > ------------------------------------------------------------------------------
> > _______________________________________________
> > Linux-f2fs-devel mailing list
> > Linux-f2fs-devel@lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
^ permalink raw reply [flat|nested] 7+ messages in thread
* RE: [f2fs-dev] [PATCH] f2fs: refactor __find_rev_next_{zero}_bit
2015-10-22 16:36 ` Jaegeuk Kim
@ 2015-11-06 5:41 ` Fan Li
0 siblings, 0 replies; 7+ messages in thread
From: Fan Li @ 2015-11-06 5:41 UTC (permalink / raw)
To: 'Jaegeuk Kim', 'Chao Yu'
Cc: linux-fsdevel, linux-kernel, 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?
> -----Original Message-----
> From: Jaegeuk Kim [mailto:jaegeuk@kernel.org]
> Sent: Friday, October 23, 2015 12:36 AM
> To: Chao Yu
> Cc: linux-fsdevel@vger.kernel.org; linux-kernel@vger.kernel.org; linux-f2fs-devel@lists.sourceforge.net
> Subject: Re: [f2fs-dev] [PATCH] f2fs: refactor __find_rev_next_{zero}_bit
>
> Hi Chao,
>
> On Thu, Oct 22, 2015 at 07:24:01PM +0800, Chao Yu wrote:
> > Hi Jaegeuk,
> >
> > > -----Original Message-----
> > > From: Jaegeuk Kim [mailto:jaegeuk@kernel.org]
> > > Sent: Thursday, October 22, 2015 6:30 AM
> > > To: linux-kernel@vger.kernel.org; linux-fsdevel@vger.kernel.org;
> > > linux-f2fs-devel@lists.sourceforge.net
> > > Subject: Re: [f2fs-dev] [PATCH] f2fs: refactor
> > > __find_rev_next_{zero}_bit
> > >
> > > On Wed, Oct 21, 2015 at 02:16:43PM -0700, Jaegeuk Kim wrote:
> > > > 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 <jaegeuk@kernel.org>
> 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,
>
> >
> > Thanks,
> >
> > > >
> > > > Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
> > > > ---
> > > > fs/f2fs/segment.c | 106
> > > > +++++++++++++++++++++++++-----------------------------
> > > > 1 file changed, 49 insertions(+), 57 deletions(-)
> > > >
> > > > diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c index
> > > > f37c212..50afc93 100644
> > > > --- a/fs/f2fs/segment.c
> > > > +++ b/fs/f2fs/segment.c
> > > > @@ -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)
> > >
> > > I fixed the sparse warning by modifying:
> > > if ((word & 0xffffffff00000000UL) == 0)
> > >
> > > Thanks,
> > >
> > > > 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)
> > > > --
> > > > 2.1.1
> > >
> > > --------------------------------------------------------------------
> > > ---------- _______________________________________________
> > > Linux-f2fs-devel mailing list
> > > Linux-f2fs-devel@lists.sourceforge.net
> > > https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Linux-f2fs-devel mailing list
> Linux-f2fs-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] f2fs: refactor __find_rev_next_{zero}_bit
@ 2015-11-06 5:41 ` Fan Li
0 siblings, 0 replies; 7+ messages in thread
From: Fan Li @ 2015-11-06 5:41 UTC (permalink / raw)
To: 'Jaegeuk Kim', 'Chao Yu'
Cc: linux-fsdevel, linux-kernel, 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?
> -----Original Message-----
> From: Jaegeuk Kim [mailto:jaegeuk@kernel.org]
> Sent: Friday, October 23, 2015 12:36 AM
> To: Chao Yu
> Cc: linux-fsdevel@vger.kernel.org; linux-kernel@vger.kernel.org; linux-f2fs-devel@lists.sourceforge.net
> Subject: Re: [f2fs-dev] [PATCH] f2fs: refactor __find_rev_next_{zero}_bit
>
> Hi Chao,
>
> On Thu, Oct 22, 2015 at 07:24:01PM +0800, Chao Yu wrote:
> > Hi Jaegeuk,
> >
> > > -----Original Message-----
> > > From: Jaegeuk Kim [mailto:jaegeuk@kernel.org]
> > > Sent: Thursday, October 22, 2015 6:30 AM
> > > To: linux-kernel@vger.kernel.org; linux-fsdevel@vger.kernel.org;
> > > linux-f2fs-devel@lists.sourceforge.net
> > > Subject: Re: [f2fs-dev] [PATCH] f2fs: refactor
> > > __find_rev_next_{zero}_bit
> > >
> > > On Wed, Oct 21, 2015 at 02:16:43PM -0700, Jaegeuk Kim wrote:
> > > > 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 <jaegeuk@kernel.org>
> 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,
>
> >
> > Thanks,
> >
> > > >
> > > > Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
> > > > ---
> > > > fs/f2fs/segment.c | 106
> > > > +++++++++++++++++++++++++-----------------------------
> > > > 1 file changed, 49 insertions(+), 57 deletions(-)
> > > >
> > > > diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c index
> > > > f37c212..50afc93 100644
> > > > --- a/fs/f2fs/segment.c
> > > > +++ b/fs/f2fs/segment.c
> > > > @@ -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)
> > >
> > > I fixed the sparse warning by modifying:
> > > if ((word & 0xffffffff00000000UL) == 0)
> > >
> > > Thanks,
> > >
> > > > 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)
> > > > --
> > > > 2.1.1
> > >
> > > --------------------------------------------------------------------
> > > ---------- _______________________________________________
> > > Linux-f2fs-devel mailing list
> > > Linux-f2fs-devel@lists.sourceforge.net
> > > https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Linux-f2fs-devel mailing list
> Linux-f2fs-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
------------------------------------------------------------------------------
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2015-11-06 5:42 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-10-21 21:16 [PATCH] f2fs: refactor __find_rev_next_{zero}_bit Jaegeuk Kim
2015-10-21 22:29 ` Jaegeuk Kim
2015-10-21 22:29 ` Jaegeuk Kim
2015-10-22 11:24 ` [f2fs-dev] " Chao Yu
2015-10-22 16:36 ` Jaegeuk Kim
2015-11-06 5:41 ` Fan Li
2015-11-06 5:41 ` Fan Li
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.