linux-kernel - Re: Potentially Broken Address Dependency via test

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: <YYGFDUR5dJ784P88@Pauls-MacBook-Pro>
Date:   Tue, 2 Nov 2021 19:35:57 +0100
From:   Paul Heidekrüger <paul.heidekrueger@...tum.de>
To:     Alan Stern <stern@...land.harvard.edu>
Cc:     paulmck@...nel.org, will@...nel.org, peterz@...radead.org,
        boqun.feng@...il.com, parri.andrea@...il.com,
        linux-kernel@...r.kernel.org, llvm@...ts.linux.dev,
        elver@...gle.com, charalampos.mainas@...il.com,
        pramod.bhatotia@...tum.de
Subject: Re: Potentially Broken Address Dependency via test_bit() When
 Compiling With Clang

On Thu, Oct 28, 2021 at 10:34:46AM -0400, Alan Stern wrote:
> On Thu, Oct 28, 2021 at 02:37:47PM +0200, Paul Heidekrüger wrote:
> > On Wed, Oct 27, 2021 at 10:27:20AM -0400, Alan Stern wrote:
> > > On Wed, Oct 27, 2021 at 12:19:48PM +0200, Paul Heidekrüger wrote:
> 
> > > > Address dependency in source code, lines 373 - 375 in fs/afs/addr_list.c:
> > > > 
> > > > > [...]
> > > > >   index = READ_ONCE(ac->alist->preferred);
> > > > >   if (test_bit(index, &set))
> > > > >     goto selected;
> > > > > [...]
> > > > 
> > > > where test_bit() expands to the following in 
> > > > include/asm-generic/bitops/non-atomic.h, lines 115 - 122:
> > > > 
> > > > > static __always_inline int
> > > > > arch_test_bit(unsigned int nr, const volatile unsigned long *addr)
> > > > > {
> > > > >   return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
> > > > > }
> > > > > #define test_bit arch_test_bit
> 
> > > However, I can't follow the IR code.  Can you please explain in ordinary 
> > > English how the LLVM compiler manages to lose track of this dependency?
> > > 
> > > Alan Stern
> > 
> > Here's what we think might be going on:
> > - In 'arch_test_bit()', 'addr[BIT_WORD(nr)]' expands to 'addr[(nr) / 64]'.
> > - Since 'addr' points to an 'unsigned long', any other result than '0' for
> >   '(nr) / 64' would be out of bounds and therefore undefined.
> > - We assume LLVM is able to figure this out and use it to get rid of the
> >   address computation all together.
> 
> Ah, that explains it.  Yes, when set is a single unsigned long (or an 
> array of length 1), the address dependency is only syntactic, not 
> semantic.  As a result, we should expect that compilers will sometimes 
> not preserve it.

In LKMM's explanation.txt, lines 450 - 453 state:

> A read event and another memory access event are linked by an address
> dependency if the value obtained by the read affects the location
> accessed by the other event.

If we understand correctly, the ambiguity you're pointing out is that by
looking at 'addr[BIT_WORD(nr)]', one could deduce an address dependency by
seeing an array subscript operator, using a value which can be traced back to a
'READ_ONCE()' (syntactic).

However, since 'addr' points to an 'unsigned long', the 'READ_ONCE()' never
affects the location accessed in 'arch_test_bit()' as the offset computed in
the subscript operator can only be, as clang identified, '0' (semantic).

> The danger, of course, is that people relying on an ordering prescribed
> by the LKMM may get fooled because (unbeknownst to them) the dependency
> in question is not semantic.

Do you think this would warrant a change to LKMM's explanation.txt to make this
more explicit?

> It would be great if a static checker
> could detect such things -- but this would require some way for us to
> inform the checker about when the code does rely on a dependency
> ordering.

The compiler passes we're working on will hopefully be able to do exactly that,
not taking into account the programmer's intent of course.

Many thanks,
Paul