linux-kernel - Re: [PATCH 3/3] bitmap: Use memcmp optimisation in more situations

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAKwiHFgt6Twp5GjRoRKZJhbRWfVp5+=SQC9=CB81ZkYF69tAGQ@mail.gmail.com>
Date:   Thu, 8 Jun 2017 15:43:52 +0200
From:   Rasmus Villemoes <linux@...musvillemoes.dk>
To:     Andy Shevchenko <andy.shevchenko@...il.com>
Cc:     Matthew Wilcox <willy@...radead.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Martin Schwidefsky <schwidefsky@...ibm.com>,
        Matthew Wilcox <mawilcox@...rosoft.com>
Subject: Re: [PATCH 3/3] bitmap: Use memcmp optimisation in more situations

On 8 June 2017 at 14:31, Andy Shevchenko <andy.shevchenko@...il.com> wrote:
> On Thu, Jun 8, 2017 at 5:55 AM, Matthew Wilcox <willy@...radead.org> wrote:
>> We only need to know if the bottom 3 bits are 0 to apply this optimisation.
>> For example, if we have a user which does this:
>>
>>         nbits = 8;
>>         if (argle)
>>                 nbits += 8;
>>         if (bitmap_equal(ptr1, ptr2, nbits))
>>                 blah();
>>
>> then we can use memcmp() because gcc can deduce that the bottom 3 bits
>> are never set (try it!  it works!).  We don't need nbits as a whole to
>> be const.
>
> What I'm talking about is that by my opinion the both below are equivalent.
> __builtin_constant_p(nbits)
> __builtin_constant_p(nbits & 7)

They are not. Read Matthew's example again. Assuming that argle is
something non-constant (maybe an argument to the function), the value
of nbits at the time of the bitmap_equal call is _not_ a
compile-time-constant. However, if the compiler is smart (which at
least some versions of gcc are), the compiler may deduce that nbits is
either 8 or 16; there really are no other options. Hence it _is_
statically known that nbits is divisible by 8, so the expression
nbits&7 _is_ compile-time constant (0), so gcc can change the
bitmap_equal call to a memcmp call.

(It may then either pass a run-time value of nbits>>3 and emit a
single memcmp call, or it may decide to unroll the two options,
creating two memcmp calls with 1 and 2 as compile-time arguments;
these may or may not then in turn be "inlined" to code doing roughly
*(u8*)p1 == *(u8*)p2 and similarly for u16 casts).