lkml.org 
[lkml]   [2015]   [Nov]   [6]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    SubjectRE: [f2fs-dev] [PATCH] f2fs: refactor __find_rev_next_{zero}_bit
    Date
    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



    \
     
     \ /
      Last update: 2015-11-06 07:21    [W:5.344 / U:0.892 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site