linux-kernel - Re: [PATCH] lib/clz_ctz.c: Fix __clzdi2() and _

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: <CAGG=3QX8AaTedPy-joWm6yp+TFHBVXm59OcvxkdLGsSuDjem5g@mail.gmail.com>
Date:   Fri, 25 Aug 2023 15:57:25 -0700
From:   Bill Wendling <morbo@...gle.com>
To:     Nick Desaulniers <ndesaulniers@...gle.com>
Cc:     Linus Torvalds <torvalds@...ux-foundation.org>,
        Helge Deller <deller@....de>,
        Nathan Chancellor <nathan@...nel.org>,
        linux-kernel@...r.kernel.org, linux-parisc@...r.kernel.org,
        Andrew Morton <akpm@...ux-foundation.org>,
        Chanho Min <chanho.min@....com>,
        Geert Uytterhoeven <geert@...ux-m68k.org>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
        Kees Cook <keescook@...omium.org>
Subject: Re: [PATCH] lib/clz_ctz.c: Fix __clzdi2() and __ctzdi2() for 32-bit kernels

On Fri, Aug 25, 2023 at 3:33 PM Bill Wendling <morbo@...gle.com> wrote:
>
> On Fri, Aug 25, 2023 at 2:01 PM Nick Desaulniers
> <ndesaulniers@...gle.com> wrote:
> >
> > On Fri, Aug 25, 2023 at 1:43 PM Linus Torvalds
> > <torvalds@...ux-foundation.org> wrote:
> > >
> > > [ Unrelated to this patch, except it made me look, adding clang build
> > > people to cc ]
> > >
> > > On Fri, 25 Aug 2023 at 13:25, Linus Torvalds
> > > <torvalds@...ux-foundation.org> wrote:
> > > >
> > > > On Fri, 25 Aug 2023 at 12:50, Helge Deller <deller@....de> wrote:
> > > > >
> > > > > This patch fixes the in-kernel functions __clzdi2() and __ctzdi2() [..]
> > > >
> > > > Applied,
> > >
> > > Bah. Still applied,  but actually building this (on 64-bit, so kind of
> > > pointless) I note that clang completely messes up this function on
> > > x86.
> > >
> > > Clang turns this:
> > >
> > >         return __ffs64(val);
> > >
> > > into this horror:
> > >
> > >         pushq   %rax
> > >         movq    %rdi, (%rsp)
> > >         #APP
> > >         rep
> > >         bsfq    (%rsp), %rax
> > >         #NO_APP
> > >         popq    %rcx
> > >
> > > which is just incredibly broken on so many levels. It *should* be a
> > > single instruction, like gcc does:
> > >
> > >         rep; bsf %rdi,%rax      # tmp87, word
> > >
> > > but clang decides that it really wants to put the argument on the
> > > stack, and apparently also wants to do that nonsensical stack
> > > alignment thing to make things even worse.
> > >
> > > We use this:
> > >
> > >   static __always_inline unsigned long variable__ffs(unsigned long word)
> > >   {
> > >         asm("rep; bsf %1,%0"
> > >                 : "=r" (word)
> > >                 : "rm" (word));
> > >         return word;
> > >   }
> > >
> > > for the definition, and it looks like clang royally just screws up
> > > here. Yes, "m" is _allowed_ in that input set, but it damn well
> > > shouldn't be used for something that is already in a register, since
> > > "r" is also allowed, and is the first choice.
> > >
> > > I think it's this clang bug:
> > >
> > >     https://github.com/llvm/llvm-project/issues/20571
> >
> > ^ yep, my comments at the end of that thread are the last time we've
> > had a chance to look into this.  Boy, it's been 9 months since the
> > last discussion of it.  I'm sorry for that.
> >
> > The TL;DR of that thread is that when both "r" and "m" constraints are
> > present, LLVM is conservative and always chooses "m" because at that
> > point it's not able to express to later passes that "m" is still a
> > valid fallback if "r" was chosen.
> >
> > Obviously "r" is preferable to "m" and we should fix that.  Seeing who
> > wants to roll up their sleeves and volunteer to understand LLVM's
> > register allocation code is like asking who wants to be the first to
> > jump into a black hole and see what happens.
>
> Yum! Human spaghetti! :-)
>
> I want to look into this myself. I'm a bit focussed on other things at
> the moment, but this is definitely on my list of "DO WANT"s.
>
Another idea is that there are __builtin_* functions for a lot of
functions that are currently in inline asm---__builtin_ctz{,l,ll,s]
and _builtin_ffs{,l,ll}. The major issue with the
`__builtin_ia32_readeflags_*` was its inability to take unrelated MSRs
into account during code motion. That may not be the same worry here?

-bw


> -bw
>
> >  I'm having a hard enough
> > time understanding the stack spilling code to better understand what
> > precisely exists in what stack slots in order to make progress on some
> > of our -Wframe-larger-than= warnings, but I need to suck it up and do
> > better.
> >
> > This came up previously in our discussion about __builtin_ia32_readeflags_*.
> > https://lore.kernel.org/all/20211215211847.206208-1-morbo@google.com/
> >
> > >     https://github.com/llvm/llvm-project/issues/30873
> > >     https://github.com/llvm/llvm-project/issues/34837
> > >
> > > and it doesn't matter for *this* case (since I don't think this
> > > library function is ever used on x86), but it looks like a generic
> > > clang issue.
> > >
> > >                  Linus
> >
> >
> >
> > --
> > Thanks,
> > ~Nick Desaulniers