Messages in this thread | | | Date | Tue, 2 Nov 2021 19:35:57 +0100 | From | Paul Heidekrüger <> | 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
| |