Support for dead code stripping on Mach-O platforms

[rgov]

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.

[rgov]

Quick illustration showing the idea:

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

[glider]

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

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

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

[samsonov]

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

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

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

[rgov]

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]

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.

[samsonov]

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]

Add a test case, update the ABI version.

[samsonov]

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

lib/Transforms/Instrumentation/AddressSanitizer.cpp

100

This will be v8 now.

[zaks.anna]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

1448

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

[rgov]

Thanks for review everyone, I'll commit shortly.

lib/Transforms/Instrumentation/AddressSanitizer.cpp

1448

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]

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]

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]

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.

[samsonov]

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]

Split into two functions per @samsonov's request.

[samsonov]

LGTM

[rgov]

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]

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.

[samsonov]

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

lib/asan/asan_globals.cc

292

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]

Committed as r264645.

lib/Transforms/Instrumentation/AddressSanitizer.cpp

 static const char *const kAsanModuleDtorName = "asan.module_dtor";
 static const uint64_t kAsanCtorAndDtorPriority = 1;
 static const char *const kAsanReportErrorTemplate = "__asan_report_";
+static const char *const kAsanApplyToGlobalsName = "__asan_apply_to_globals";
 static const char *const kAsanRegisterGlobalsName = "__asan_register_globals";
 static const char *const kAsanUnregisterGlobalsName =
     "__asan_unregister_globals";

   Function *AsanUnpoisonGlobals;
   Function *AsanRegisterGlobals;
   Function *AsanUnregisterGlobals;
+  Function *AsanApplyToGlobals;
 };
 
 // Stack poisoning does not play well with exception handling.

       M.getOrInsertFunction(kAsanUnregisterGlobalsName, IRB.getVoidTy(),
                             IntptrTy, IntptrTy, nullptr));
   AsanUnregisterGlobals->setLinkage(Function::ExternalLinkage);
+
+  if (TargetTriple.isOSBinFormatMachO()) {
+    AsanApplyToGlobals = checkSanitizerInterfaceFunction(
+        M.getOrInsertFunction(kAsanApplyToGlobalsName,
+        IRB.getVoidTy(), IntptrTy, IntptrTy, nullptr));
+    AsanApplyToGlobals->setLinkage(Function::ExternalLinkage);
+  }
 }
 
 // This function replaces all global variables with new variables that have

     DEBUG(dbgs() << "NEW GLOBAL: " << *NewGlobal << "\n");
   }
 
-  ArrayType *ArrayOfGlobalStructTy = ArrayType::get(GlobalStructTy, n);
-  GlobalVariable *AllGlobals = new GlobalVariable(
-      M, ArrayOfGlobalStructTy, false, GlobalVariable::InternalLinkage,
-      ConstantArray::get(ArrayOfGlobalStructTy, Initializers), "");
+
+  GlobalVariable *AllGlobals = nullptr;
+
+  // On Mach-O platforms, we emit the global metadata in a way that allows the
+  // linker to properly strip dead globals.
+  if (TargetTriple.isOSBinFormatMachO()) {
+    // We use AllGlobals as a dummy symbol which lets us look up the header
+    // of the library that contains it later.
+    AllGlobals = new GlobalVariable(
+        M, IntptrTy, false, GlobalVariable::InternalLinkage,
+        ConstantInt::get(IntptrTy, 0), "");
+    
+    // We also emit a structure which binds the liveness of the global
+    // variable to the metadata struct.
+    StructType *LivenessTy = StructType::get(IntptrTy, IntptrTy, nullptr);
+
+    for (size_t i = 0; i < n; i++) {
+      GlobalVariable *Metadata = new GlobalVariable(
+          M, GlobalStructTy, false, GlobalVariable::InternalLinkage,
+          Initializers[i], "");
+      Metadata->setSection("__DATA,__asan_globals,regular");
+      Metadata->setAlignment(1); // don't leave padding in between
+
+      auto LivenessBinder = ConstantStruct::get(LivenessTy,
+          Initializers[i]->getAggregateElement(0u),
+          ConstantExpr::getPointerCast(Metadata, IntptrTy),
+          nullptr);
+      GlobalVariable *Liveness = new GlobalVariable(
+          M, LivenessTy, false, GlobalVariable::InternalLinkage,
+          LivenessBinder, "");
+      Liveness->setSection("__DATA,__asan_liveness,regular,live_support");
+    }
+  } else {
+    ArrayType *ArrayOfGlobalStructTy = ArrayType::get(GlobalStructTy, n);
+    AllGlobals = new GlobalVariable(
+        M, ArrayOfGlobalStructTy, false, GlobalVariable::InternalLinkage,
+        ConstantArray::get(ArrayOfGlobalStructTy, Initializers), "");
+  }
 
   // Create calls for poisoning before initializers run and unpoisoning after.
   if (HasDynamicallyInitializedGlobals)
     createInitializerPoisonCalls(M, ModuleName);
-  IRB.CreateCall(AsanRegisterGlobals,
-                 {IRB.CreatePointerCast(AllGlobals, IntptrTy),
-                  ConstantInt::get(IntptrTy, n)});
+
+  if (TargetTriple.isOSBinFormatMachO()) {
+    IRB.CreateCall(AsanApplyToGlobals,
+                   {IRB.CreatePointerCast(AsanRegisterGlobals, IntptrTy),
+                    IRB.CreatePointerCast(AllGlobals, IntptrTy)});
+  } else {
+    IRB.CreateCall(AsanRegisterGlobals,
+                   {IRB.CreatePointerCast(AllGlobals, IntptrTy),
+                    ConstantInt::get(IntptrTy, n)});
+  }
 
   // We also need to unregister globals at the end, e.g. when a shared library
   // gets closed.

                        GlobalValue::InternalLinkage, kAsanModuleDtorName, &M);
   BasicBlock *AsanDtorBB = BasicBlock::Create(*C, "", AsanDtorFunction);
   IRBuilder<> IRB_Dtor(ReturnInst::Create(*C, AsanDtorBB));
-  IRB_Dtor.CreateCall(AsanUnregisterGlobals,
-                      {IRB.CreatePointerCast(AllGlobals, IntptrTy),
-                       ConstantInt::get(IntptrTy, n)});
+
+  if (TargetTriple.isOSBinFormatMachO()) {
+    IRB_Dtor.CreateCall(AsanApplyToGlobals,
+                        {IRB.CreatePointerCast(AsanUnregisterGlobals, IntptrTy),
+                         IRB.CreatePointerCast(AllGlobals, IntptrTy)});
+  } else {
+    IRB_Dtor.CreateCall(AsanUnregisterGlobals,
+                        {IRB.CreatePointerCast(AllGlobals, IntptrTy),
+                         ConstantInt::get(IntptrTy, n)});
+  }
+
   appendToGlobalDtors(M, AsanDtorFunction, kAsanCtorAndDtorPriority);
 
   DEBUG(dbgs() << M);

lib/asan/asan_globals.cc

 #include "sanitizer_common/sanitizer_placement_new.h"
 #include "sanitizer_common/sanitizer_stackdepot.h"
 
+#if SANITIZER_MAC
+#include <mach-o/getsect.h>
+#include <dlfcn.h>
+#endif
+
+
 namespace __asan {
 
 typedef __asan_global Global;

 // ---------------------- Interface ---------------- {{{1
 using namespace __asan;  // NOLINT
 
+
+#if SANITIZER_MAC
+// Apply __asan_(un)register_globals to globals found listed in the
+// __DATA,__asan_globals section.
+void __asan_apply_to_globals(global_func func, void *canary) {
+  // Find the Mach-O header for the image containing the canary
+  Dl_info info;
+  int err = dladdr(canary, &info);
+  if (err == 0) return;
+
+#if __LP64__
+  const struct mach_header_64 *mh = (struct mach_header_64 *)info.dli_fbase;
+#else
+  const struct mach_header *mh = (struct mach_header *)info.dli_fbase;
+#endif
+
+  // Look up the __asan_globals section in that image and register its globals
+  unsigned long size = 0;
+  __asan_global *globals = (__asan_global *)getsectiondata(
+      mh,
+      "__DATA", "__asan_globals",
+      &size);
+
+  if (!globals) return;
+  if (size % sizeof(__asan_global) != 0) return;
+  func(globals, size / sizeof(__asan_global));
+}
+#endif
+
 // Register an array of globals.
 void __asan_register_globals(__asan_global *globals, uptr n) {
   if (!flags()->report_globals) return;

lib/asan/asan_interface_internal.h

                                               // or NULL if it is unknown.
   };
 
+  // This function can be called by instrumented code on Mach-O platforms.
+#if SANITIZER_MAC
+  typedef void (*global_func)(__asan_global *, uptr);
+  SANITIZER_INTERFACE_ATTRIBUTE
+  void __asan_apply_to_globals(global_func foo, void *canary);
+#endif
+
   // These two functions should be called by the instrumented code.
   // 'globals' is an array of structures describing 'n' globals.
   SANITIZER_INTERFACE_ATTRIBUTE