[PATCH] bitops: simplify generic bit finding functions - Kernel

This is a discussion on [PATCH] bitops: simplify generic bit finding functions - Kernel ; No need for a sentinal if we explicitly catch the no bits/all bits set cases, make it clear they are special cases returning size/BITS_PER_LONG. Signed-off-by: Harvey Harrison --- include/linux/bitops.h | 93 ++++++++++++++++++++---------------------------- 1 files changed, 39 insertions(+), 54 deletions(-) diff ...

+ Reply to Thread
Page 1 of 2 1 2 LastLast
Results 1 to 20 of 27

Thread: [PATCH] bitops: simplify generic bit finding functions

  1. [PATCH] bitops: simplify generic bit finding functions

    No need for a sentinal if we explicitly catch the no bits/all bits set
    cases, make it clear they are special cases returning size/BITS_PER_LONG.

    Signed-off-by: Harvey Harrison
    ---
    include/linux/bitops.h | 93 ++++++++++++++++++++----------------------------
    1 files changed, 39 insertions(+), 54 deletions(-)

    diff --git a/include/linux/bitops.h b/include/linux/bitops.h
    index 48bde60..d9eb58a 100644
    --- a/include/linux/bitops.h
    +++ b/include/linux/bitops.h
    @@ -127,18 +127,17 @@ extern unsigned long __find_first_bit(const unsigned long *addr,
    static __always_inline unsigned long
    find_first_bit(const unsigned long *addr, unsigned long size)
    {
    - /* Avoid a function call if the bitmap size is a constant */
    - /* and not bigger than BITS_PER_LONG. */
    -
    - /* insert a sentinel so that __ffs returns size if there */
    - /* are no set bits in the bitmap */
    - if (__builtin_constant_p(size) && (size < BITS_PER_LONG))
    - return __ffs((*addr) | (1ul << size));
    -
    - /* the result of __ffs(0) is undefined, so it needs to be */
    - /* handled separately */
    - if (__builtin_constant_p(size) && (size == BITS_PER_LONG))
    - return ((*addr) == 0) ? BITS_PER_LONG : __ffs(*addr);
    + /*
    + * Avoid a function call if the bitmap size is a constant and not
    + * bigger than BITS_PER_LONG. Ensure we return size if there are
    + * no set bits.
    + */
    + if (__builtin_constant_p(size) && (size <= BITS_PER_LONG)) {
    + if (*addr == 0)
    + return (size < BITS_PER_LONG) ? size : BITS_PER_LONG;
    + else
    + return __ffs(*addr);
    + }

    /* size is not constant or too big */
    return __find_first_bit(addr, size);
    @@ -157,20 +156,17 @@ extern unsigned long __find_first_zero_bit(const unsigned long *addr,
    static __always_inline unsigned long
    find_first_zero_bit(const unsigned long *addr, unsigned long size)
    {
    - /* Avoid a function call if the bitmap size is a constant */
    - /* and not bigger than BITS_PER_LONG. */
    -
    - /* insert a sentinel so that __ffs returns size if there */
    - /* are no set bits in the bitmap */
    - if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
    - return __ffs(~(*addr) | (1ul << size));
    + /*
    + * Avoid a function call if the bitmap size is a constant and not
    + * bigger than BITS_PER_LONG. Ensure we return size if all bits set.
    + */
    + if (__builtin_constant_p(size) && (size <= BITS_PER_LONG)) {
    + if ((~(*addr)) == 0)
    + return (size < BITS_PER_LONG) ? size : BITS_PER_LONG;
    + else
    + return __ffs(~(*addr));
    }

    - /* the result of __ffs(0) is undefined, so it needs to be */
    - /* handled separately */
    - if (__builtin_constant_p(size) && (size == BITS_PER_LONG))
    - return (~(*addr) == 0) ? BITS_PER_LONG : __ffs(~(*addr));
    -
    /* size is not constant or too big */
    return __find_first_zero_bit(addr, size);
    }
    @@ -192,22 +188,17 @@ find_next_bit(const unsigned long *addr, unsigned long size,
    {
    unsigned long value;

    - /* Avoid a function call if the bitmap size is a constant */
    - /* and not bigger than BITS_PER_LONG. */
    -
    - /* insert a sentinel so that __ffs returns size if there */
    - /* are no set bits in the bitmap */
    - if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
    + /*
    + * Avoid a function call if the bitmap size is a constant and not
    + * bigger than BITS_PER_LONG. Ensure we return size if there are
    + * no set bits.
    + */
    + if (__builtin_constant_p(size) && (size <= BITS_PER_LONG)) {
    value = (*addr) & ((~0ul) << offset);
    - value |= (1ul << size);
    - return __ffs(value);
    - }
    -
    - /* the result of __ffs(0) is undefined, so it needs to be */
    - /* handled separately */
    - if (__builtin_constant_p(size) && (size == BITS_PER_LONG)) {
    - value = (*addr) & ((~0ul) << offset);
    - return (value == 0) ? BITS_PER_LONG : __ffs(value);
    + if (value == 0)
    + return (size < BITS_PER_LONG) ? size : BITS_PER_LONG;
    + else
    + return __ffs(value);
    }

    /* size is not constant or too big */
    @@ -229,22 +220,16 @@ find_next_zero_bit(const unsigned long *addr, unsigned long size,
    {
    unsigned long value;

    - /* Avoid a function call if the bitmap size is a constant */
    - /* and not bigger than BITS_PER_LONG. */
    -
    - /* insert a sentinel so that __ffs returns size if there */
    - /* are no set bits in the bitmap */
    - if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
    - value = (~(*addr)) & ((~0ul) << offset);
    - value |= (1ul << size);
    - return __ffs(value);
    - }
    -
    - /* the result of __ffs(0) is undefined, so it needs to be */
    - /* handled separately */
    - if (__builtin_constant_p(size) && (size == BITS_PER_LONG)) {
    + /*
    + * Avoid a function call if the bitmap size is a constant and not
    + * bigger than BITS_PER_LONG. Ensure we return size if all bits set.
    + */
    + if (__builtin_constant_p(size) && (size <= BITS_PER_LONG)) {
    value = (~(*addr)) & ((~0ul) << offset);
    - return (value == 0) ? BITS_PER_LONG : __ffs(value);
    + if (value == 0)
    + return (size < BITS_PER_LONG) ? size : BITS_PER_LONG;
    + else
    + return __ffs(value);
    }

    /* size is not constant or too big */
    --
    1.5.5.1.270.g89765



    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  2. Re: [PATCH] bitops: simplify generic bit finding functions



    On Sun, 27 Apr 2008, Harvey Harrison wrote:
    >
    > No need for a sentinal if we explicitly catch the no bits/all bits set
    > cases, make it clear they are special cases returning size/BITS_PER_LONG.


    These things need to be re-done anyway. David already complained that the
    thing inlines to something much much too big.

    Let's just make it not be an inline at all.

    Linus
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  3. Re: [PATCH] bitops: simplify generic bit finding functions

    On Sun, 2008-04-27 at 13:26 -0700, Linus Torvalds wrote:
    >
    > On Sun, 27 Apr 2008, Harvey Harrison wrote:
    > >
    > > No need for a sentinal if we explicitly catch the no bits/all bits set
    > > cases, make it clear they are special cases returning size/BITS_PER_LONG.

    >
    > These things need to be re-done anyway. David already complained that the
    > thing inlines to something much much too big.
    >
    > Let's just make it not be an inline at all.


    Oh, I didn't realize, I only did this because sparse started spewing out
    lots of:
    include/linux/bitops.h:166:32: warning: shift too big (65536) for type unsigned long

    due to shift by size there, and again on line 202...I just wanted something
    that sparse wouldn't warn about and was a little easier to understand to boot.

    Cheers,

    Harvey

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  4. Re: [PATCH] bitops: simplify generic bit finding functions



    On Sun, 27 Apr 2008, Harvey Harrison wrote:
    >
    > Oh, I didn't realize, I only did this because sparse started spewing out
    > lots of:
    > include/linux/bitops.h:166:32: warning: shift too big (65536) for type unsigned long


    Well, that's really just a sparse bug/misfeature that didn't matter
    before.

    It happens because the warning is done as part of constant expression
    evaluation, but then the expression isn't actually *used*, so when we
    optimize it away - at a later date - it's too late to undo the warning.

    I don't rightly know how to fix it. We do want to do the constant
    evaluation early (since all the optimizations that may then make it a
    non-issue depends on constants being constants!), but in order to not
    output the warning we'd have to turn the constant into a "constant with
    warning 'xyz' if used".

    Which we have no support for in sparse yet.

    Linus
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  5. Re: [PATCH] bitops: simplify generic bit finding functions

    On Sun, Apr 27, 2008 at 01:29:21PM -0700, Harvey Harrison wrote:

    > Oh, I didn't realize, I only did this because sparse started spewing out
    > lots of:
    > include/linux/bitops.h:166:32: warning: shift too big (65536) for type unsigned long
    >
    > due to shift by size there, and again on line 202...I just wanted something
    > that sparse wouldn't warn about and was a little easier to understand to boot.


    That's a sparse problem, really. I wonder if we simply should introduce a
    new node type: EXPR_WARN. So that expand would generate those from things
    like division by zero/overflow/bad shift *and* emitting an insn for those
    would generate a stored warning.

    Objections?
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  6. Re: [PATCH] bitops: simplify generic bit finding functions

    On Sun, 2008-04-27 at 21:36 +0100, Al Viro wrote:
    > On Sun, Apr 27, 2008 at 01:29:21PM -0700, Harvey Harrison wrote:
    >
    > > Oh, I didn't realize, I only did this because sparse started spewing out
    > > lots of:
    > > include/linux/bitops.h:166:32: warning: shift too big (65536) for type unsigned long
    > >
    > > due to shift by size there, and again on line 202...I just wanted something
    > > that sparse wouldn't warn about and was a little easier to understand to boot.

    >
    > That's a sparse problem, really. I wonder if we simply should introduce a
    > new node type: EXPR_WARN. So that expand would generate those from things
    > like division by zero/overflow/bad shift *and* emitting an insn for those
    > would generate a stored warning.


    Well, even though it is a sparse problem, I think my revised version was
    cleaner code anyway.

    >
    > Objections?


    None here

    Harvey

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  7. Re: [PATCH] bitops: simplify generic bit finding functions

    On Sun, Apr 27, 2008 at 01:38:34PM -0700, Linus Torvalds wrote:

    > It happens because the warning is done as part of constant expression
    > evaluation, but then the expression isn't actually *used*, so when we
    > optimize it away - at a later date - it's too late to undo the warning.
    >
    > I don't rightly know how to fix it. We do want to do the constant
    > evaluation early (since all the optimizations that may then make it a
    > non-issue depends on constants being constants!), but in order to not
    > output the warning we'd have to turn the constant into a "constant with
    > warning 'xyz' if used".
    >
    > Which we have no support for in sparse yet.


    It's not even a constant, really... What we need is
    * don't fold further if that sucker would be evaluated (i.e. 0 && <...>
    is folded, 0 & <...> is not)
    * don't consider an integer constant expression with value 0 for
    purposes of null pointer constant handling
    * emit corresponding insn in linearize_expression() when we run into
    such sucker.
    * somewhere around the call of vrfy_flow() walk through insns in
    remaining bb (we'd done dead code elimination already) and spew postponed
    warning on each such insn. Probably. Assuming that I'm not entirely
    confused about what's going on in that area - which is quite possible.

    Folks, could somebody familiar with the backend comment on the last part?
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  8. Re: [PATCH] bitops: simplify generic bit finding functions

    On Sun, 27 Apr 2008, Linus Torvalds wrote:
    > On Sun, 27 Apr 2008, Harvey Harrison wrote:
    > >
    > > No need for a sentinal if we explicitly catch the no bits/all bits set
    > > cases, make it clear they are special cases returning size/BITS_PER_LONG.

    >
    > These things need to be re-done anyway. David already complained that the
    > thing inlines to something much much too big.


    The delta between the inlined version including the constant
    optimizations and the original non inlined version is exactly 1400
    bytes on a sparc64 defconfig build.

    > Let's just make it not be an inline at all.


    Which makes the whole constant optimization moot.

    How about making the optimization controlled by a config switch so
    arch maintainers can decide whether they want to enable the constant
    optimization or unconditionally call the lib function ?

    See patch below. It gives back the 1400 bytes on SPARC64 and other
    platforms that have no instruction for find bit.

    Thanks,
    tglx

    ---------->

    Subject: bitops: optional bitops mapsize optimization on config switch
    From: Thomas Gleixner
    Date: Mon, 28 Apr 2008 00:22:06 +0200

    The mapsize optimizations which were moved from x86 to the generic
    code in commit 64970b68d2b3ed32b964b0b30b1b98518fde388e increased the
    binary size on non x86 architectures.

    Make the optimization depend on a config switch so architecture
    maintainers can decide.

    Signed-off-by: Thomas Gleixner
    Acked-by: Ingo Molnar

    ---
    arch/x86/Kconfig.cpu | 1 +
    include/linux/bitops.h | 6 ++++--
    2 files changed, 5 insertions(+), 2 deletions(-)

    Index: linux-2.6/arch/x86/Kconfig.cpu
    ================================================== =================
    --- linux-2.6.orig/arch/x86/Kconfig.cpu
    +++ linux-2.6/arch/x86/Kconfig.cpu
    @@ -282,6 +282,7 @@ config X86_CPU
    def_bool y
    select GENERIC_FIND_FIRST_BIT
    select GENERIC_FIND_NEXT_BIT
    + select GENERIC_FIND_BIT_MAPSIZE_OPTIMIZE

    config X86_GENERIC
    bool "Generic x86 support"
    Index: linux-2.6/include/linux/bitops.h
    ================================================== =================
    --- linux-2.6.orig/include/linux/bitops.h
    +++ linux-2.6/include/linux/bitops.h
    @@ -190,6 +190,7 @@ static __always_inline unsigned long
    find_next_bit(const unsigned long *addr, unsigned long size,
    unsigned long offset)
    {
    +#ifdef CONFIG_GENERIC_FIND_BIT_MAPSIZE_OPTIMIZE
    unsigned long value;

    /* Avoid a function call if the bitmap size is a constant */
    @@ -209,7 +210,7 @@ find_next_bit(const unsigned long *addr,
    value = (*addr) & ((~0ul) << offset);
    return (value == 0) ? BITS_PER_LONG : __ffs(value);
    }
    -
    +#endif
    /* size is not constant or too big */
    return __find_next_bit(addr, size, offset);
    }
    @@ -227,6 +228,7 @@ static __always_inline unsigned long
    find_next_zero_bit(const unsigned long *addr, unsigned long size,
    unsigned long offset)
    {
    +#ifdef CONFIG_GENERIC_FIND_BIT_MAPSIZE_OPTIMIZE
    unsigned long value;

    /* Avoid a function call if the bitmap size is a constant */
    @@ -246,7 +248,7 @@ find_next_zero_bit(const unsigned long *
    value = (~(*addr)) & ((~0ul) << offset);
    return (value == 0) ? BITS_PER_LONG : __ffs(value);
    }
    -
    +#endif
    /* size is not constant or too big */
    return __find_next_zero_bit(addr, size, offset);
    }
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  9. Re: [PATCH] bitops: simplify generic bit finding functions

    Hi,

    Ingo just pointed me to this thread.

    On Sun, 27 Apr 2008 13:19:51 -0700, "Harvey Harrison"
    said:
    > No need for a sentinal if we explicitly catch the no bits/all bits set
    > cases, make it clear they are special cases returning size/BITS_PER_LONG.
    >
    > Signed-off-by: Harvey Harrison
    > ---
    > include/linux/bitops.h | 93
    > ++++++++++++++++++++----------------------------
    > 1 files changed, 39 insertions(+), 54 deletions(-)
    >
    > diff --git a/include/linux/bitops.h b/include/linux/bitops.h
    > index 48bde60..d9eb58a 100644
    > --- a/include/linux/bitops.h
    > +++ b/include/linux/bitops.h
    > @@ -127,18 +127,17 @@ extern unsigned long __find_first_bit(const
    > unsigned long *addr,
    > static __always_inline unsigned long
    > find_first_bit(const unsigned long *addr, unsigned long size)
    > {
    > - /* Avoid a function call if the bitmap size is a constant */
    > - /* and not bigger than BITS_PER_LONG. */
    > -
    > - /* insert a sentinel so that __ffs returns size if there */
    > - /* are no set bits in the bitmap */
    > - if (__builtin_constant_p(size) && (size < BITS_PER_LONG))
    > - return __ffs((*addr) | (1ul << size));
    > -
    > - /* the result of __ffs(0) is undefined, so it needs to be */
    > - /* handled separately */
    > - if (__builtin_constant_p(size) && (size == BITS_PER_LONG))
    > - return ((*addr) == 0) ? BITS_PER_LONG : __ffs(*addr);
    > + /*
    > + * Avoid a function call if the bitmap size is a constant and not
    > + * bigger than BITS_PER_LONG. Ensure we return size if there are
    > + * no set bits.
    > + */
    > + if (__builtin_constant_p(size) && (size <= BITS_PER_LONG)) {
    > + if (*addr == 0)
    > + return (size < BITS_PER_LONG) ? size : BITS_PER_LONG;
    > + else
    > + return __ffs(*addr);
    > + }


    Ehm... assume size=16 and *addr=0x80000000
    then __ffs(*addr) = 31. Not 16.

    > /* size is not constant or too big */
    > return __find_first_bit(addr, size);
    > @@ -157,20 +156,17 @@ extern unsigned long __find_first_zero_bit(const
    > unsigned long *addr,
    > static __always_inline unsigned long
    > find_first_zero_bit(const unsigned long *addr, unsigned long size)
    > {
    > - /* Avoid a function call if the bitmap size is a constant */
    > - /* and not bigger than BITS_PER_LONG. */
    > -
    > - /* insert a sentinel so that __ffs returns size if there */
    > - /* are no set bits in the bitmap */
    > - if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
    > - return __ffs(~(*addr) | (1ul << size));
    > + /*
    > + * Avoid a function call if the bitmap size is a constant and not
    > + * bigger than BITS_PER_LONG. Ensure we return size if all bits set.
    > + */
    > + if (__builtin_constant_p(size) && (size <= BITS_PER_LONG)) {
    > + if ((~(*addr)) == 0)
    > + return (size < BITS_PER_LONG) ? size : BITS_PER_LONG;
    > + else
    > + return __ffs(~(*addr));
    > }
    >
    > - /* the result of __ffs(0) is undefined, so it needs to be */
    > - /* handled separately */
    > - if (__builtin_constant_p(size) && (size == BITS_PER_LONG))
    > - return (~(*addr) == 0) ? BITS_PER_LONG : __ffs(~(*addr));
    > -
    > /* size is not constant or too big */
    > return __find_first_zero_bit(addr, size);
    > }
    > @@ -192,22 +188,17 @@ find_next_bit(const unsigned long *addr, unsigned
    > long size,
    > {
    > unsigned long value;
    >
    > - /* Avoid a function call if the bitmap size is a constant */
    > - /* and not bigger than BITS_PER_LONG. */
    > -
    > - /* insert a sentinel so that __ffs returns size if there */
    > - /* are no set bits in the bitmap */
    > - if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
    > + /*
    > + * Avoid a function call if the bitmap size is a constant and not
    > + * bigger than BITS_PER_LONG. Ensure we return size if there are
    > + * no set bits.
    > + */
    > + if (__builtin_constant_p(size) && (size <= BITS_PER_LONG)) {
    > value = (*addr) & ((~0ul) << offset);
    > - value |= (1ul << size);
    > - return __ffs(value);
    > - }
    > -
    > - /* the result of __ffs(0) is undefined, so it needs to be */
    > - /* handled separately */
    > - if (__builtin_constant_p(size) && (size == BITS_PER_LONG)) {
    > - value = (*addr) & ((~0ul) << offset);
    > - return (value == 0) ? BITS_PER_LONG : __ffs(value);
    > + if (value == 0)
    > + return (size < BITS_PER_LONG) ? size : BITS_PER_LONG;
    > + else
    > + return __ffs(value);
    > }
    >
    > /* size is not constant or too big */
    > @@ -229,22 +220,16 @@ find_next_zero_bit(const unsigned long *addr,
    > unsigned long size,
    > {
    > unsigned long value;
    >
    > - /* Avoid a function call if the bitmap size is a constant */
    > - /* and not bigger than BITS_PER_LONG. */
    > -
    > - /* insert a sentinel so that __ffs returns size if there */
    > - /* are no set bits in the bitmap */
    > - if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
    > - value = (~(*addr)) & ((~0ul) << offset);
    > - value |= (1ul << size);
    > - return __ffs(value);
    > - }
    > -
    > - /* the result of __ffs(0) is undefined, so it needs to be */
    > - /* handled separately */
    > - if (__builtin_constant_p(size) && (size == BITS_PER_LONG)) {
    > + /*
    > + * Avoid a function call if the bitmap size is a constant and not
    > + * bigger than BITS_PER_LONG. Ensure we return size if all bits set.
    > + */
    > + if (__builtin_constant_p(size) && (size <= BITS_PER_LONG)) {
    > value = (~(*addr)) & ((~0ul) << offset);
    > - return (value == 0) ? BITS_PER_LONG : __ffs(value);
    > + if (value == 0)
    > + return (size < BITS_PER_LONG) ? size : BITS_PER_LONG;
    > + else
    > + return __ffs(value);
    > }
    >
    > /* size is not constant or too big */
    > --
    > 1.5.5.1.270.g89765

    --
    Alexander van Heukelum
    heukelum@fastmail.fm

    --
    http://www.fastmail.fm - mmm... Fastmail...

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  10. Re: [PATCH] bitops: simplify generic bit finding functions

    On Sun, 27 Apr 2008 13:26:34 -0700 (PDT), "Linus Torvalds"
    said:
    > On Sun, 27 Apr 2008, Harvey Harrison wrote:
    > >
    > > No need for a sentinal if we explicitly catch the no bits/all bits set
    > > cases, make it clear they are special cases returning size/BITS_PER_LONG.

    >
    > These things need to be re-done anyway. David already complained that the
    > thing inlines to something much much too big.
    >
    > Let's just make it not be an inline at all.


    Hello,

    I think that's the wrong way to go about it. The problem that David
    Miller pointed out was that the small-bitmap optimization caused an
    inliningdisaster. Apparently, the generic version of __ffs is very
    big on sparc64. In my opinion the implementation of __ffs should be
    made out of line. If you move the wrapper of find_first_bit etc
    out of line, all possibilities of optimization will be destroyed.
    Better to remove them completely, then.

    Greetings,
    Alexander

    > Linus
    > --
    > To unsubscribe from this list: send the line "unsubscribe linux-kernel"
    > in
    > the body of a message to majordomo@vger.kernel.org
    > More majordomo info at http://vger.kernel.org/majordomo-info.html
    > Please read the FAQ at http://www.tux.org/lkml/
    >
    >

    --
    Alexander van Heukelum
    heukelum@fastmail.fm

    --
    http://www.fastmail.fm - Accessible with your email software
    or over the web

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  11. Re: [PATCH] bitops: simplify generic bit finding functions

    > See patch below. It gives back the 1400 bytes on SPARC64 and other
    > platforms that have no instruction for find bit.


    Hi,

    I, personally, see this patch as a stopgap measure. The real problem
    is that the generic __ffs is inlined and ends up generating a lot
    of instructions.

    Until the generic implementation of __ffs is fixed not to be an
    enormous inline function, this seems to be a reasonable thing
    to do, though it's a shame that the optimization is now default-
    off for architectures with a good implementation of __ffs.

    Greetings,
    Alexander

    > Thanks,
    > tglx
    >
    > ---------->
    >
    > Subject: bitops: optional bitops mapsize optimization on config switch
    > From: Thomas Gleixner
    > Date: Mon, 28 Apr 2008 00:22:06 +0200
    >
    > The mapsize optimizations which were moved from x86 to the generic
    > code in commit 64970b68d2b3ed32b964b0b30b1b98518fde388e increased the
    > binary size on non x86 architectures.
    >
    > Make the optimization depend on a config switch so architecture
    > maintainers can decide.
    >
    > Signed-off-by: Thomas Gleixner
    > Acked-by: Ingo Molnar
    >
    > ---
    > arch/x86/Kconfig.cpu | 1 +
    > include/linux/bitops.h | 6 ++++--
    > 2 files changed, 5 insertions(+), 2 deletions(-)
    >
    > Index: linux-2.6/arch/x86/Kconfig.cpu
    > ================================================== =================
    > --- linux-2.6.orig/arch/x86/Kconfig.cpu
    > +++ linux-2.6/arch/x86/Kconfig.cpu
    > @@ -282,6 +282,7 @@ config X86_CPU
    > def_bool y
    > select GENERIC_FIND_FIRST_BIT
    > select GENERIC_FIND_NEXT_BIT
    > + select GENERIC_FIND_BIT_MAPSIZE_OPTIMIZE
    >
    > config X86_GENERIC
    > bool "Generic x86 support"
    > Index: linux-2.6/include/linux/bitops.h
    > ================================================== =================
    > --- linux-2.6.orig/include/linux/bitops.h
    > +++ linux-2.6/include/linux/bitops.h
    > @@ -190,6 +190,7 @@ static __always_inline unsigned long
    > find_next_bit(const unsigned long *addr, unsigned long size,
    > unsigned long offset)
    > {
    > +#ifdef CONFIG_GENERIC_FIND_BIT_MAPSIZE_OPTIMIZE
    > unsigned long value;
    >
    > /* Avoid a function call if the bitmap size is a constant */
    > @@ -209,7 +210,7 @@ find_next_bit(const unsigned long *addr,
    > value = (*addr) & ((~0ul) << offset);
    > return (value == 0) ? BITS_PER_LONG : __ffs(value);
    > }
    > -
    > +#endif
    > /* size is not constant or too big */
    > return __find_next_bit(addr, size, offset);
    > }
    > @@ -227,6 +228,7 @@ static __always_inline unsigned long
    > find_next_zero_bit(const unsigned long *addr, unsigned long size,
    > unsigned long offset)
    > {
    > +#ifdef CONFIG_GENERIC_FIND_BIT_MAPSIZE_OPTIMIZE
    > unsigned long value;
    >
    > /* Avoid a function call if the bitmap size is a constant */
    > @@ -246,7 +248,7 @@ find_next_zero_bit(const unsigned long *
    > value = (~(*addr)) & ((~0ul) << offset);
    > return (value == 0) ? BITS_PER_LONG : __ffs(value);
    > }
    > -
    > +#endif
    > /* size is not constant or too big */
    > return __find_next_zero_bit(addr, size, offset);
    > }
    > --
    > To unsubscribe from this list: send the line "unsubscribe linux-kernel"
    > in
    > the body of a message to majordomo@vger.kernel.org
    > More majordomo info at http://vger.kernel.org/majordomo-info.html
    > Please read the FAQ at http://www.tux.org/lkml/
    >
    >

    --
    Alexander van Heukelum
    heukelum@fastmail.fm

    --
    http://www.fastmail.fm - mmm... Fastmail...

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  12. Re: [PATCH] bitops: simplify generic bit finding functions

    On Mon, 28 Apr 2008, Alexander van Heukelum wrote:
    > > See patch below. It gives back the 1400 bytes on SPARC64 and other
    > > platforms that have no instruction for find bit.

    >
    > Hi,
    >
    > I, personally, see this patch as a stopgap measure. The real problem
    > is that the generic __ffs is inlined and ends up generating a lot
    > of instructions.
    >
    > Until the generic implementation of __ffs is fixed not to be an
    > enormous inline function, this seems to be a reasonable thing
    > to do, though it's a shame that the optimization is now default-
    > off for architectures with a good implementation of __ffs.


    Yup, it hasn't been there before and we explicitely enable it on
    x86. If there are other archs which have a good one it's a nobrainer
    to enable it.

    Thanks,
    tglx

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  13. Re: [PATCH] bitops: simplify generic bit finding functions



    On Mon, 28 Apr 2008, Thomas Gleixner wrote:
    >
    > How about making the optimization controlled by a config switch so
    > arch maintainers can decide whether they want to enable the constant
    > optimization or unconditionally call the lib function ?


    No.

    This is just making that damn header line look worse and worse.

    Is there a _reason_ to optimize this stupid function this way?

    Linus
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  14. Re: [PATCH] bitops: simplify generic bit finding functions

    On Mon, 28 Apr 2008, Linus Torvalds wrote:
    > >
    > > How about making the optimization controlled by a config switch so
    > > arch maintainers can decide whether they want to enable the constant
    > > optimization or unconditionally call the lib function ?

    >
    > No.
    >
    > This is just making that damn header line look worse and worse.
    >
    > Is there a _reason_ to optimize this stupid function this way?


    On architectures which have a find bit instruction we can replace the
    call to the library function by a single instruction when the size of
    the bitmap is less/equal bits per long and when the bitnr is a
    constant.

    Thanks,
    tglx


    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  15. Re: [PATCH] bitops: simplify generic bit finding functions



    On Mon, 28 Apr 2008, Thomas Gleixner wrote:

    > On Mon, 28 Apr 2008, Linus Torvalds wrote:
    > > >
    > > > How about making the optimization controlled by a config switch so
    > > > arch maintainers can decide whether they want to enable the constant
    > > > optimization or unconditionally call the lib function ?

    > >
    > > No.
    > >
    > > This is just making that damn header line look worse and worse.
    > >
    > > Is there a _reason_ to optimize this stupid function this way?

    >
    > On architectures which have a find bit instruction we can replace the
    > call to the library function by a single instruction when the size of
    > the bitmap is less/equal bits per long and when the bitnr is a
    > constant.


    That's not what I asked.

    I asked whether there is a *reason* to optimize this and cause all these
    stupid problems.

    Is there a real hot path anywhere that actually uses this and depends on
    it?

    Linus
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  16. Re: [PATCH] bitops: simplify generic bit finding functions

    On Mon, 28 Apr 2008, Linus Torvalds wrote:
    > > > > How about making the optimization controlled by a config switch so
    > > > > arch maintainers can decide whether they want to enable the constant
    > > > > optimization or unconditionally call the lib function ?
    > > >
    > > > No.
    > > >
    > > > This is just making that damn header line look worse and worse.
    > > >
    > > > Is there a _reason_ to optimize this stupid function this way?

    > >
    > > On architectures which have a find bit instruction we can replace the
    > > call to the library function by a single instruction when the size of
    > > the bitmap is less/equal bits per long and when the bitnr is a
    > > constant.

    >
    > That's not what I asked.
    >
    > I asked whether there is a *reason* to optimize this and cause all these
    > stupid problems.
    >
    > Is there a real hot path anywhere that actually uses this and depends on
    > it?


    Sorry, misunderstood your question.

    I checked the use cases and have not found a single one for
    find_next_(zero_)bit() which makes use of this micro optimization. In
    fact the .text section of vmlinux of the "optimized" and the straight
    function call are identical. So the effect of those micro
    optimizations is exactly zero.

    find_first_(zero_)bit() has a couple of places where the optimization
    hits, but the code size reduction is mere 21 bytes and the use cases
    are not in real hot pathes AFAICT.

    I doubt that that is worth the trouble and we should just remove those
    inlines alltogether. This was discussed before, but Andi objected to
    remove those micro optimizations and nobody had time to actually
    verify the real benefits.

    I'll whip up a patch.

    Thanks,

    tglx
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  17. Re: [PATCH] bitops: simplify generic bit finding functions



    On Mon, 28 Apr 2008, Thomas Gleixner wrote:
    >
    > I doubt that that is worth the trouble and we should just remove those
    > inlines alltogether. This was discussed before, but Andi objected to
    > remove those micro optimizations and nobody had time to actually
    > verify the real benefits.


    Thanks for checking.

    In general, I think we should act the other way: we should *assume* that
    inlines and complex macros in header files are not worth it and we'd be
    better off with just plain function calls, unless it's really obvious that
    the inline function is always worth it.

    We have tons of good examples of inline functions in headers that really
    *really* want to be that way: is generally a collection of
    things that clearly expand to somthing that is (a) easily critical and (b)
    inlining things generally really causes a smaller code footprint than
    having a "call" instruction and all the argument setup - regardless of how
    many times it is done.

    So we do have cases where the inlines are obviously worth it. But in
    general, I think we should try to move things from the header files into
    *.c files unless there is a really clear reason for keeping it that way.

    (Some inline functions do depend on things like constant arguments goign
    away, with kmalloc() being a good example of some really nasty header file
    tricks that are likely worth it despite their extreme ugliness)

    Linus
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  18. Re: [PATCH] bitops: simplify generic bit finding functions

    Linus Torvalds writes:
    >
    > Is there a real hot path anywhere that actually uses this and depends on
    > it?


    A long time ago during profiling I found that in the scheduler back then
    for_each_cpu() with find_next_bit() was somewhat hot. But I'm not sure it
    still would be in the new scheduler anyways and the test case a little
    dumb anyways (overscheduling user space)

    Still I think for_each_cpu() should be reasonably stream lined code.

    -Andi
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  19. Re: [PATCH] bitops: simplify generic bit finding functions


    * Linus Torvalds wrote:

    > So we do have cases where the inlines are obviously worth it. But in
    > general, I think we should try to move things from the header files
    > into *.c files unless there is a really clear reason for keeping it
    > that way.


    there's another benefit, and in asm-x86 we prefer to move inlines to .c
    files even in borderline cases because it simplifies the type
    dependencies: not having to fully define all types at the function
    prototype site avoids include file dependency hell.

    Putting things like a task struct dereference into a lowlevel inline
    file easily causes dependency problems that causes people to use macros
    instead - which have their own set of readability and side-effect
    problems.

    a third argument is that inlines seldom get smaller. So if they are
    borderline and we move them into a .c, and later on the function gets
    larger, no harm is done. But if we keep the inline in a .h in the
    borderline case and we grow the inline later on, the whole kernel bloats
    in a multiplied way, without any apparent direct feedback to the
    developer that something wrong and harmful just happened.

    Ingo
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  20. Re: [PATCH] bitops: remove "optimizations"

    From: Thomas Gleixner
    Date: Tue, 29 Apr 2008 12:01:02 +0200 (CEST)

    > The mapsize optimizations which were moved from x86 to the generic
    > code in commit 64970b68d2b3ed32b964b0b30b1b98518fde388e increased the
    > binary size on non x86 architectures.
    >
    > Looking into the real effects of the "optimizations" it turned out
    > that they are not used in find_next_bit() and find_next_zero_bit().
    >
    > The ones in find_first_bit() and find_first_zero_bit() are used in a
    > couple of places but none of them is a real hot path.
    >
    > Remove the "optimizations" all together and call the library functions
    > unconditionally.
    >
    > Boot-tested on x86 and compile tested on every cross compiler I have.
    >
    > Signed-off-by: Thomas Gleixner


    Acked-by: David S. Miller
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

+ Reply to Thread
Page 1 of 2 1 2 LastLast