This is an archive of the discontinued LLVM Phabricator instance.

Support for dead code stripping on Mach-O platforms
ClosedPublic

Authored by rgov on Jan 29 2016, 1:55 PM.

Details

Summary

ASAN global instrumentation prevents dead stripping of globals due to liveness being propagated from the __asan_global metadata structure.

On OS X El Capitan and iOS 9, the linker now supports a new section attribute, live_support, which inverts the direction of liveness propagation, so that the metadata is alive only if the global it references is alive. This allows dead stripping to remove dead globals along with the ASAN metadata about them.

In this proposed patch, __asan_global structures are emitted in a new __DATA,__asan_globals section. The runtime library learned a new function for locating this section for registering and unregistering globals.

Additionally, there is a __DATA,__asan_liveness section with the live_support attribute. Each entry in this section is simply a tuple that binds together the liveness of a global variable and its ASAN metadata structure. Thus the metadata structure will be alive if and only if the global it references is also alive.

This comes at a small overhead in binary size (two pointers per global, plus two new section headers), but this could be offset by savings from dead stripping. The __DATA,__asan_liveness section does not need to be kept around after linking, but the linker does not currently remove it.

Diff Detail

Event Timeline

rgov updated this revision to Diff 46423.Jan 29 2016, 1:55 PM
rgov retitled this revision from to Support for dead code stripping on Mach-O platforms.
rgov updated this object.
rgov updated this revision to Diff 46430.Jan 29 2016, 1:57 PM
rgov added reviewers: kubamracek, zaks.anna, samsonov, glider, kcc.
rgov added a reviewer: beanz.Jan 31 2016, 1:44 AM
rgov added a comment.Jan 31 2016, 11:25 PM

Quick illustration showing the idea:

Solid lines show references, while dotted lines show the propagation of liveness.

glider edited edge metadata.Feb 1 2016, 2:23 AM

This is great!
May I please ask you to split this patch into two (see below) and add tests for it?

Also, please consider adding uploading diffs with context (svn diff --diff-cmd=diff -x -U999999).

lib/Transforms/Instrumentation/AddressSanitizer.cpp
1438

What happens to globals that already belong to another sections in __DATA?

1448

How is this section treated on older systems? Is is safe to unconditionally emit it?

lib/asan/asan_globals.cc
224 ↗(On Diff #46430)

Can this part (putting globals into a separate section) be done in a separate patch?
You'll also need a test for it.

lib/asan/asan_interface_internal.h
59 ↗(On Diff #46430)

It's unclear from the comment what this function is used for.

samsonov edited edge metadata.Feb 1 2016, 1:55 PM

Thanks for working on this! Some high-level comments:

  1. Try to minimize the amount of platform-specific code and instrumentation. E.g. it's better to have __asan_apply_to_globals() declared/defined on all platforms, but have it actually implemented only on Mac.
  2. Add some way to test this.
  3. This is an ABI-breaking change, right? You may need to update asan_init_version.h.
lib/Transforms/Instrumentation/AddressSanitizer.cpp
1426

Please don't use one variable for two different entities.

lib/asan/asan_globals.cc
223 ↗(On Diff #46430)

Please put all Mac-specific code to asan_mac.cc. You can make __asan_apply_to_globals a dummy function that would delegate actual implementation to platform-specific functions, that will be UNIMPLEMENTED() on all platforms except for Mac.

lib/asan/asan_interface_internal.h
59 ↗(On Diff #46430)

+1. Also, just declare it unconditionally on all platforms.

rgov updated this revision to Diff 46742.Feb 2 2016, 10:05 PM
rgov edited edge metadata.
rgov marked 5 inline comments as done.

Now this differential covers just the LLVM changes.

lib/Transforms/Instrumentation/AddressSanitizer.cpp
1438

This only changes the section of the __asan_global metadata structure, so this would not affect anything.

1448

It looks like the toolchain has understood this section attribute since 2006 (!), but it did not have an effect on dead stripping behavior until recently.

If you were to use Clang with this new feature to produce an object file, and then link with that object file with an older ld64 with -dead_strip, then the __asan_global structures will all be stripped, because they have no live references. This would cause a failure.

rgov added a comment.EditedFeb 2 2016, 10:20 PM

To write a test, I'd use a source file like:

int alive[1] = {};
int dead[1] = {};

int main() {
	alive[1] = 0;
	return 0;
}

After compiling with -Xlinker -dead_strip I'd make sure that it still detects the out-of-bounds read on alive, and then I'd make sure that dead does not appear in the symbol table. However, I do not know how to set up such a test.

You will need two tests:
(1) LLVM test that verifies that you emit correct instrumentation on Mach-O: bundle together global_ptr and metadata_ptr, call __asan_apply_to_globals
(2) compiler-rt test in test/asan/TestCases/Darwin that actually invokes clang with -Xlinker,-dead-strip (if it's always available on Mach-O platforms), then runs "llvm-nm" on it to check that dead global is missing, and runs the executable to check that error is reported as expected.

rgov updated this revision to Diff 47096.Feb 6 2016, 12:57 PM

Add a test case, update the ABI version.

samsonov accepted this revision.Feb 9 2016, 4:40 PM
samsonov edited edge metadata.

LGTM. Please make sure to bump the ABI to v8, as it was changed to v7 recently.

lib/Transforms/Instrumentation/AddressSanitizer.cpp
103

This will be v8 now.

This revision is now accepted and ready to land.Feb 9 2016, 4:40 PM
zaks.anna added inline comments.Feb 9 2016, 5:29 PM
lib/Transforms/Instrumentation/AddressSanitizer.cpp
1511

What kind of failure will occur? Is it possible to diagnose that?

rgov added a comment.Feb 9 2016, 10:41 PM

Thanks for review everyone, I'll commit shortly.

lib/Transforms/Instrumentation/AddressSanitizer.cpp
1511

The shadow memory of the globals would not be properly initialized at image load time, so my guess is that this would be the same as disabling global instrumentation, but it might cause every access to a global to fail (I think this is unlikely).

I'm not sure how this situation could be detected. One way (which I do not like) would be to put a dummy variable in a live_support section like __DATA,__a, and have it point to a dead variable in __DATA,__b. You can tell at runtime that -dead_strip was a linker option if __b is zero-length, and you can tell if the new linker was used in this case if __a is also zero-length.

rgov added a comment.Feb 10 2016, 12:58 AM

Hm, holding off on committing. This regresses tests related to ODR.

==39927==ERROR: AddressSanitizer: odr-violation (0x00100060):
  [1] size=4 'coolestInteger' src/llvm/projects/compiler-rt/test/asan/TestCases/initialization-constexpr.cc:24:9
  [2] size=4 'coolestInteger' src/llvm/projects/compiler-rt/test/asan/TestCases/initialization-constexpr.cc:24:9
These globals were registered at these points:
  [1]:
    #0 0x1115bd in __asan_register_globals (build/llvm/./lib/clang/3.9.0/lib/darwin/libclang_rt.asan_osx_dynamic.dylib+0xd5bd)
    #1 0x15551e in __asan::AsanApplyToGlobals(void (*)(__asan_global*, unsigned long), void*) (build/llvm/./lib/clang/3.9.0/lib/darwin/libclang_rt.asan_osx_dynamic.dylib+0x5151e)
    #2 0x8fe3611f  (<unknown module>)
    #3 0x8fe31e2d  (<unknown module>)
    #4 0x8fe31cc0  (<unknown module>)
    #5 0x8fe31f20  (<unknown module>)
    #6 0x8fe23f7e  (<unknown module>)
    #7 0x8fe27cdf  (<unknown module>)
    #8 0x8fe23230  (<unknown module>)
    #9 0x8fe23046  (<unknown module>)
    #10 0x0  (<unknown module>)

  [2]:
    #0 0x1115bd in __asan_register_globals (build/llvm/./lib/clang/3.9.0/lib/darwin/libclang_rt.asan_osx_dynamic.dylib+0xd5bd)
    #1 0x15551e in __asan::AsanApplyToGlobals(void (*)(__asan_global*, unsigned long), void*) (build/llvm/./lib/clang/3.9.0/lib/darwin/libclang_rt.asan_osx_dynamic.dylib+0x5151e)
    #2 0x8fe3611f  (<unknown module>)
    #3 0x8fe31e2d  (<unknown module>)
    #4 0x8fe31cc0  (<unknown module>)
    #5 0x8fe31f20  (<unknown module>)
    #6 0x8fe23f7e  (<unknown module>)
    #7 0x8fe27cdf  (<unknown module>)
    #8 0x8fe23230  (<unknown module>)
    #9 0x8fe23046  (<unknown module>)
    #10 0x0  (<unknown module>)

==39927==HINT: if you don't care about these errors you may set ASAN_OPTIONS=detect_odr_violation=0
SUMMARY: AddressSanitizer: odr-violation: global 'coolestInteger' at src/llvm/projects/compiler-rt/test/asan/TestCases/initialization-constexpr.cc:24:9
==39927==ABORTING
rgov added a comment.Feb 10 2016, 2:13 AM

I understand why: Globals are being registered repeatedly (once per object file that contains any globals).

If there are two or more object files which declare globals, then when linked together, there are multiple calls to __asan_apply_to_globals(__asan_register_globals, __asan_needle) during execution of constructors. Each call registers *all* globals across all translation units. Before this change, each call to __asan_register_globals registered an individual translation unit's globals.

This could be fixed in the runtime by using a boolean to indicate whether globals have already been registered (or, less efficiently, by querying the list of registration sites). However, there are a few problems with this:

  1. It complicates the behavior of __asan_apply_to_globals, to "apply only if it hasn't been applied before."
  2. We still emit multiple calls to __asan_apply_to_globals even though only the first one does anything.

For (1), as a simple test, I changed the linkage of __asan_needle to link-one to coalesce them together, then treated the single needle as a boolean representing whether the globals from this image have been registered (n.b., this approach breaks unregistering).

void __asan_apply_to_globals(globals_op_fptr op, void *needle) {
  if (*(int *)needle != 0)
    return;
  *(int *)needle = 1;

  AsanApplyToGlobals(op, needle);
}

For (2), a simple way around this for registration is to just drop these calls from the constructor and put one during AsanInitInternal (which would have to learn a way to determine which shared library is calling it). But deregistration is less obvious.

rgov updated this revision to Diff 47542.Feb 10 2016, 3:13 PM
rgov edited edge metadata.

I added AddressSanitizerModule::ShouldUseMachOGlobalsSection and associated logic to disable this feature on unsupported target platforms.

I also changed the needle variable to now be a flag that indicates whether globals have been registered already. This allows us to prevent duplicate registration. The flag now has common linkage, which allows the linker to coalesce flag variables from multiple TUs into one.

Ah, right, I didn't notice that now you register *all* the globals in executable / dylib in a single call. I think that you can solve the de-registration problem with using link-once needle (to coalesce needles from multiple translation units when you link a single dylib) as suggested, and then use:

void __asan_register_module_globals(void *reg_needle) {
  if (*(int *)reg_needle != 0)
    return;
  *(int *)reg_needle = 1;
  AsanApplyToGlobals(__asan_register_globals, reg_needle);
}

void __asan_unregister_module_globals(void *unreg_needle) {
  if (*(int *)unreg_needle != 0)
    return;
  *(int *)unreg_needle = 1;
  AsanApplyToGlobals(__asan_unregister_globals, unreg_needle);
}

Now, technically when you dlclose() the library, you will unregister all the globals before all the TU destructors finish, which is not nice...

It's fine to emit several calls to __asan_register_module_globals although only one of them will be called: we do the same for __asan_init, for instance.

rgov updated this revision to Diff 50129.Mar 9 2016, 5:52 AM

Split into two functions per @samsonov's request.

rgov updated this revision to Diff 51783.Mar 28 2016, 6:09 AM

Renamed functions to __asan_(un)register_image_globals. image is the term used by lldb to refer to the main executable plus loaded libraries.

rgov updated this revision to Diff 51784.Mar 28 2016, 6:11 AM

Added comments per @samsonov's requests. Renamed functions to use image instead of module which is consistent with LLDB. Changed AsanApplyToGlobals parameter back to const void *needle since it is not used as a flag within that function as @samsonov pointed out.

LGTM. Feel free to submit after addressing a couple of comments below.

lib/asan/asan_globals.cc
292 ↗(On Diff #51784)

These comments are redundant, given the comment before the function. You may remove them.

test/asan/TestCases/Darwin/dead-strip.c
12 ↗(On Diff #51784)

I would still prefer this test case to not contain pragmas. Can you use smth. like

int main(int argc, char **argv) {
  alive[argc] = 0;
  return 0;
}

to avoid compiler warning?

rgov closed this revision.Mar 28 2016, 2:03 PM

Committed as r264645.