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:

quoted

On Wed, Oct 27, 2021 at 12:19:48PM +0200, Paul Heidekrüger wrote:

quoted

quoted

Address dependency in source code, lines 373 - 375 in fs/afs/addr_list.c:

quoted

[...]
  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:

quoted

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

quoted

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.

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.  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.

We ran some experiments to see how optimisations behave when 'set' is in fact
an array and / or in global scope.

1. Insert a 'barrier()' in 'arch_test_bit()' before the 'return':
The dependency gets broken.

2. Make 'set' an 'unsigned long' array of size '42', keep local scope: 
The dependency gets preserved.

3. Keep 'set' as 'unsigend long', move to global scope: 
The dependency gets preserved.

That one's a little strange.  I don't see why the scope should make any 
difference, so long as the compiler knows the actual type and length.

4. Make 'set' an 'unsigned long' array of size '42', move to global scope: 
The dependency gets preserved.

Alan