Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
MIME-Version: 1.0
References: <20190119151450.26879-1-Florian.LaRoche@googlemail.com>
 <20190120000138.GI26876@brain-police> <CAHk-=wjKgJ-9ypvzq+CB_NKnRk6iAqFtgVPwSH17C5RqJoYF=A@mail.gmail.com>
In-Reply-To: <CAHk-=wjKgJ-9ypvzq+CB_NKnRk6iAqFtgVPwSH17C5RqJoYF=A@mail.gmail.com>
From:   Florian La Roche <florian.laroche@googlemail.com>
Date:   Sun, 20 Jan 2019 06:03:17 +0100
Message-ID: <CANZrA2YLtnv+PRBYzcLdFUg4uktx82G8dkoZCic8-ANK-3-7fA@mail.gmail.com>
Subject: Re: fix int_sqrt() for very large numbers
To:     Linus Torvalds <torvalds@linux-foundation.org>
Cc:     Will Deacon <will.deacon@arm.com>,
        Linux List Kernel Mailing <linux-kernel@vger.kernel.org>,
        Crt Mori <cmo@melexis.com>, Joe Perches <joe@perches.com>,
        Davidlohr Bueso <dave@stgolabs.net>,
        Peter Zijlstra <peterz@infradead.org>
Content-Type: text/plain; charset="UTF-8"
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

Hello all,

my comment said ffs(), but the code only uses fls() and that's what I meant.


Am So., 20. Jan. 2019 um 04:49 Uhr schrieb Linus Torvalds
<torvalds@linux-foundation.org>:
> But yes, our current int_sqrt64() does seem buggy as-is, because it's
> *supposed* to work on u64's, even if I don't think we really have any
> users that care.

Right. No real bug, just not 100% correct code.

> And as Will mentioned, the regular int_sqrt() looks perfectly fine,
> and subtracting 1 from the __fls() return value would actually
> _introduce_ a bug.

I think no bug introduced as the code handling 0 and 1 is already done.

For __fls() and fls64() I am actually using the folloing code:
/*
 * fls - find last (most-significant) bit set
 * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
 */
static __always_inline unsigned int flsl(unsigned long x)
{
    return x ? sizeof(x) * 8 - __builtin_clzl(x) : 0;
}

Please note the "_builtin_clzl()" instead of the "_builtin_clz()".

The real bug is that we compute 1 to 64 for bit 0 to bit 63, whereas
the algorithm
expects 0 to 63 for the value of m.

best regards,

Florian La Roche