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>
In-Reply-To: <20190120000138.GI26876@brain-police>
From:   Linus Torvalds <torvalds@linux-foundation.org>
Date:   Sun, 20 Jan 2019 15:48:49 +1200
Message-ID: <CAHk-=wjKgJ-9ypvzq+CB_NKnRk6iAqFtgVPwSH17C5RqJoYF=A@mail.gmail.com>
Subject: Re: fix int_sqrt() for very large numbers
To:     Will Deacon <will.deacon@arm.com>
Cc:     Florian La Roche <florian.laroche@googlemail.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

On Sun, Jan 20, 2019 at 12:01 PM Will Deacon <will.deacon@arm.com> wrote:
>
> > @@ -52,7 +52,7 @@ u32 int_sqrt64(u64 x)
> >       if (x <= ULONG_MAX)
> >               return int_sqrt((unsigned long) x);
> >
> > -     m = 1ULL << (fls64(x) & ~1ULL);
> > +     m = 1ULL << ((fls64(x) - 1) & ~1ULL);
>
> This just looks like a copy-paste error because there isn't an __fls64().
> But I think your suggestion here is ok, given the previous check against
> ULONG_MAX.

Hmm. We probably *should* add a __fls64().

There looks to be only one user of int_sqrt64(), and that one is
confused. It does int_sqrt64() twice, but since the inner one will
reduce the range to 32 bits, the outer one is just silly.

That one user also had better not be overflowing into the high bit -
it uses "s64" as a type and does seem to use signed operatons, so high
bit set really means negative. sqrt() returning something odd for a
negative number wouldn't be all that odd in that context.

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.

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

            Linus