Alignment problems in Clang's internal data structures?

Clang Frontend
1

Hi all,

I've been looking into what might be alignment issues throughout clang.

Consider "DeclRefExpr::Create(.., NameInfo, ..)". It allocates itself
and a few other structs in a single allocation, using the well-known
pattern:

  std::size_t Size = sizeof(DeclRefExpr);
  if (...)
    Size += sizeof(...);
  ...
  void *Mem = Context.Allocate(Size, llvm::alignOf<DeclRefExpr>());

The alignment should also take into account the trailing classes,
really. In every Allocate call that has a non-trivial size, the
alignment should be correspondingly non-trivial. Some calls just use
ASTContext's default, 8 (enough for most purposes, at least; better
than the explicit alignOf, which might be 4).

[skip forward if you don't care about the investigation]

Currently, I think we get away with this because 1) X86 is lenient, 2)
most people don't self-host on another architecture, and 3) at least
on ARM, alignment checking has to be explicitly enabled, statically or
dynamically.

On ARM, if you try running clang with either:
- SCTRL.A==1 (alignment checking on non-strict-aligned instructions)
(I should say I couldn't get this to work); or
- different LLVM CodeGen picking stricter instructions that actually
enforce alignment (what made me investigate),

it should crash, at some point. On the LIT-tests, the first (of many)
to fail was
  test/Analysis/dead-stores.cpp
Indeed, on trunk clang, the "this" pointer in
  ASTTemplateArgumentListInfo::initializeFrom(Info, b, b, b)
is sometimes dynamically 4-aligned, whereas it is supposed to be
8-aligned (according to alignof and the IR we generate.)

This pattern is pervasive throughout clang, and even though a few
classes try to get it right (with a trailing AlignedCharArray), most
don't. What do clang developers think? Did I miss something,
perhaps?

UBSan's alignment sanitizer would be *very* useful here, but my
understanding is, ARM isn't currently supported, and running it on X86
is futile (at least x86_64, maybe i386 could reproduce though; that's
on my todo list.)

Thanks!

-Ahmed

2

Of all the sanitizer runtimes, this would be by far the easiest to port. It
should be *very* easy in fact, boring on trivial.

And we even support -fsanitize-undefined-trap-on-error which require no
runtime support at all and is suitable for use in embedded code, etc.

3

UBSan's alignment sanitizer would be *very* useful here, but my
understanding is, ARM isn't currently supported

Of all the sanitizer runtimes, this would be by far the easiest to port. It
should be *very* easy in fact, boring on trivial.

Yep, that was my fallback plan if i386 doesn't exhibit the issues =)

-Ahmed

4

  std::size_t Size = sizeof(DeclRefExpr);
  if (...)
    Size += sizeof(...);
  ...
  void *Mem = Context.Allocate(Size, llvm::alignOf<DeclRefExpr>());

This sounds wrong. You should have something like:

   std::size_t Size = sizeof(DeclRefExpr);
   std::size_t Align = llvm::alignOf<DeclRefExpr>();
   if (...) {
     Size += sizeof(...);
     Align = std::max(Align, llvm::alignOf<...>());
   }
   ...
   void *Mem = Context.Allocate(Size, Align);

UBSan's alignment sanitizer would be *very* useful here, but my
understanding is, ARM isn't currently supported, and running it on X86
is futile (at least x86_64, maybe i386 could reproduce though; that's
on my todo list.)

It'd be great to have UBSAN working on ARM, at least that small part. :slight_smile:

But that also mean we'd have to actually run it as a buildbot to make
sure we don't re-introduce the pattern.

Another thing we could do is to run as many santisers as we can during
releases, at least when running the test-suite. But first, I need to
set this up and actually run it with all SANs and fix all bugs before
the next release (3.7). We'll get there, eventually. :slight_smile:

cheers,
--renato

5

It would probably be a relatively simple feature to add a private
system call to an x86-system [in Linux, doing this for Windows or
MacOS would be noticeably harder as it is not so easy to add code to
the OS there] to set he AM flag in CR0 and AC flag in EFLAGS, which
would cause unaligned accesses to trap in x86 (only in usermode). Of
course, you would have to then rely on for example libc and libc++ etc
to have correct alignment accesses...

6

Another thing to consider is the alignment of the beginning of the
extra elements.

Say you have a structure and an array of doubles. If your structure
aligns to 4 and ends at byte 1, you'll have to add 7 bytes padding, or
the access to each of the elements in the double array will be
unaligned. This is, of course, target dependent, but alignOf() should
do the trick.

So, just adding padding to the structure's alignment is not enough,
you have to check the other elements (per element) and add a padding
before each one of them, if needed. The problem this creates is that
the reading end will know nothing of the padding and may need
additional logic to use the padding accordingly.

cheers,
--renato

7

It turns out the alignment sanitizer, though "unsupported", works fine
on ARM when building with clang (I was using gcc as the stage1
compiler, which actively complains).

I stopped because it's not even possible to build llvm-tblgen, since
there is some undefined behavior in libstdc++, uncovered by the
sanitizer.. I'll try to give it another look.

In the meantime, filed
  http://llvm.org/bugs/show_bug.cgi?id=22728

-Ahmed

8

This isn't enough either. You need to update the accessors to account for
alignment. They currently look like this:

  NamedDecl *&getInternalFoundDecl() {
    assert(hasFoundDecl());
    if (hasQualifier())
      return *reinterpret_cast<NamedDecl **>(&getInternalQualifierLoc() +
1);
    return *reinterpret_cast<NamedDecl **>(this + 1);
  }

I do *not* want to audit Clang for the 'reinterpret_cast<Foo*>(this + 1)'
pattern and add extra alignment code. We should just make sure that
anything allocated this way requires only pointer-size alignment.

I put this on http://llvm.org/pr22727.