linux-kernel - Re: fix int_sqrt() for very large numbers

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: <CAKv63uu+-gF_zci8NrRDB4g7ujkbz7dPnAEAjY6_ZVXB9NOWGA@mail.gmail.com>
Date:   Mon, 21 Jan 2019 21:25:00 +0100
From:   Crt Mori <cmo@...exis.com>
To:     Linus Torvalds <torvalds@...ux-foundation.org>
Cc:     Florian La Roche <florian.laroche@...glemail.com>,
        Linux List Kernel Mailing <linux-kernel@...r.kernel.org>,
        Joe Perches <joe@...ches.com>,
        Davidlohr Bueso <dave@...olabs.net>,
        Will Deacon <will.deacon@....com>,
        Peter Zijlstra <peterz@...radead.org>
Subject: Re: fix int_sqrt() for very large numbers

On Mon, 21 Jan 2019 at 01:20, Linus Torvalds
<torvalds@...ux-foundation.org> wrote:
>
> On Sun, Jan 20, 2019 at 4:15 AM Florian La Roche
> <florian.laroche@...glemail.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);
>
> I've applied this part of the patch as commit fbfaf851902c ("fix
> int_sqrt64() for very large numbers") with slightly edited commit
> log.
>

Thanks for the patch - I its indeed my copy-paste error, because
__fls64 does not exist on 32bit CPU, but the fls64 is not "equal"
replacement. I am very sorry for the bug.

> I still think there are some oddities in here in the types. I
> mentioned the caller that unnecessarily does the int_sqrt64() twice,
> even though the outer one doesn't actually take a 64-bit value.
>

True. This is oddity is originating from time where mlx90632 used its
own function for int_sqrt64 on 32bit.

> But in the very line above, there's another type oddity: the "& ~1ULL"
> is entirely the wrong type. The shift *count* shouldn't be an unsigned
> long long, so that type doesn't make much sense. It should be just a
> ~1, or even just "62".
>

This was also inline with above copy-paste and variable expansion to
force the 64bit everywhere. I will prepare a patch to clean this line
to ~1, question is why does the int_sqrt is having UL if this should
just be "62". I was thinking because we want to cast to the type
before we shift.

> But I didn't actually start micro-editing the patch, and just did that
> one-liner off-by-one fix.
>
>              Linus