[compiler-rt] Add support for the dynamic shadow allocation

[etienneb]

Summary

This patch is adding support for dynamic shadow allocation.

This is a merge and re-commit of the following patches.

[compiler-rt] Fix Asan build on Android
  https://reviews.llvm.org/D24768
[compiler-rt] Add support for the dynamic shadow allocation
  https://reviews.llvm.org/D23363

This patch needed to re-land at the same time:

[asan] Support dynamic shadow address instrumentation
  https://reviews.llvm.org/D23354

[rnk]

looks good

lib/sanitizer_common/sanitizer_posix.cc

362–363

I think UNREACHABLE("...") is preferred

Also, this API is not really implementable on Posix. You can parse /proc/self/maps on Linux and some BSDs, which doesn't even work if you don't have access to /proc. I think at some point we'll want to come back and redesign the abstractions we're using for virtual memory allocation, but today is not that day. We already discussed how the other APIs are way too Posix-y.

[zaks.anna]

Thanks for working on this! Dynamic offset is very useful for iOS as well.

lib/asan/asan_interface_internal.h

extern "C" {
   SANITIZER_INTERFACE_ATTRIBUTE SANITIZER_WEAK_ATTRIBUTE
   /* OPTIONAL */ void __asan_on_error();
 
   SANITIZER_INTERFACE_ATTRIBUTE void __asan_print_accumulated_stats();
 
   SANITIZER_INTERFACE_ATTRIBUTE SANITIZER_WEAK_ATTRIBUTE
   /* OPTIONAL */ const char* __asan_default_options();
 
+  SANITIZER_INTERFACE_ATTRIBUTE
+  extern uptr __asan_shadow_memory_dynamic_address;
+
   // Global flag, copy of ASAN_OPTIONS=detect_stack_use_after_return
   SANITIZER_INTERFACE_ATTRIBUTE
   extern int __asan_option_detect_stack_use_after_return;
 
   SANITIZER_INTERFACE_ATTRIBUTE
   extern uptr *__asan_test_only_reported_buggy_pointer;
 
   SANITIZER_INTERFACE_ATTRIBUTE void __asan_load1(uptr p);

lib/asan/asan_mapping.h

 //  on WoW64, /LARGEADDRESSAWARE, etc).
 // || `[0x50000000, 0xffffffff]` || HighMem    ||
 // || `[0x3a000000, 0x4fffffff]` || HighShadow ||
 // || `[0x36000000, 0x39ffffff]` || ShadowGap  ||
 // || `[0x30000000, 0x35ffffff]` || LowShadow  ||
 // || `[0x00000000, 0x2fffffff]` || LowMem     ||
 
 static const u64 kDefaultShadowScale = 3;
+static const u64 kDefaultShadowSentinel = ~(uptr)0;
 static const u64 kDefaultShadowOffset32 = 1ULL << 29;  // 0x20000000
 static const u64 kDefaultShadowOffset64 = 1ULL << 44;
 static const u64 kDefaultShort64bitShadowOffset = 0x7FFF8000;  // < 2G.
 static const u64 kIosShadowOffset32 = 1ULL << 30;  // 0x40000000
 static const u64 kIosShadowOffset64 = 0x120200000;
 static const u64 kIosSimShadowOffset32 = 1ULL << 30;
 static const u64 kIosSimShadowOffset64 = kDefaultShadowOffset64;
 static const u64 kAArch64_ShadowOffset64 = 1ULL << 36;
 static const u64 kMIPS32_ShadowOffset32 = 0x0aaa0000;
 static const u64 kMIPS64_ShadowOffset64 = 1ULL << 37;
 static const u64 kPPC64_ShadowOffset64 = 1ULL << 41;
 static const u64 kSystemZ_ShadowOffset64 = 1ULL << 52;
 static const u64 kFreeBSD_ShadowOffset32 = 1ULL << 30;  // 0x40000000
 static const u64 kFreeBSD_ShadowOffset64 = 1ULL << 46;  // 0x400000000000
 static const u64 kWindowsShadowOffset32 = 3ULL << 28;  // 0x30000000
-static const u64 kWindowsShadowOffset64 = 1ULL << 45;  // 32TB
 
 #define SHADOW_SCALE kDefaultShadowScale
 
 
 #if SANITIZER_WORDSIZE == 32
 #  if SANITIZER_ANDROID
 #    define SHADOW_OFFSET (0)
 #  elif defined(__mips__)

 #    define SHADOW_OFFSET kSystemZ_ShadowOffset64
 #  elif SANITIZER_FREEBSD
 #    define SHADOW_OFFSET kFreeBSD_ShadowOffset64
 #  elif SANITIZER_MAC
 #   define SHADOW_OFFSET kDefaultShadowOffset64
 #  elif defined(__mips64)
 #   define SHADOW_OFFSET kMIPS64_ShadowOffset64
 #  elif SANITIZER_WINDOWS64
-#   define SHADOW_OFFSET kWindowsShadowOffset64
+#   define SHADOW_OFFSET __asan_shadow_memory_dynamic_address
 #  else
 #   define SHADOW_OFFSET kDefaultShort64bitShadowOffset
 #  endif
 #endif
 
 #define SHADOW_GRANULARITY (1ULL << SHADOW_SCALE)
 #define MEM_TO_SHADOW(mem) (((mem) >> SHADOW_SCALE) + (SHADOW_OFFSET))
 #define SHADOW_TO_MEM(shadow) (((shadow) - SHADOW_OFFSET) << SHADOW_SCALE)

lib/asan/asan_rtl.cc

 #include "sanitizer_common/sanitizer_atomic.h"
 #include "sanitizer_common/sanitizer_flags.h"
 #include "sanitizer_common/sanitizer_libc.h"
 #include "sanitizer_common/sanitizer_symbolizer.h"
 #include "lsan/lsan_common.h"
 #include "ubsan/ubsan_init.h"
 #include "ubsan/ubsan_platform.h"
 
+uptr __asan_shadow_memory_dynamic_address;  // Global interface symbol.
 int __asan_option_detect_stack_use_after_return;  // Global interface symbol.
 uptr *__asan_test_only_reported_buggy_pointer;  // Used only for testing asan.
 
 namespace __asan {
 
 uptr AsanMappingProfile[kAsanMappingProfileSize];
 
 static void AsanDie() {
static void AsanInitInternal() {
 
   // Enable system log ("adb logcat") on Android.
   // Doing this before interceptors are initialized crashes in:
   // AsanInitInternal -> android_log_write -> __interceptor_strcmp
   AndroidLogInit();
 
   ReplaceSystemMalloc();
 
+  // Set the shadow memory address to uninitialized.
+  __asan_shadow_memory_dynamic_address = kDefaultShadowSentinel;
+
   uptr shadow_start = kLowShadowBeg;
+  // Detect if a dynamic shadow address must used and find a available location
+  // when necessary. When dynamic address is used, the macro |kLowShadowBeg|
+  // expands to |__asan_shadow_memory_dynamic_address| which is
+  // |kDefaultShadowSentinel|.
+  if (shadow_start == kDefaultShadowSentinel) {
+    __asan_shadow_memory_dynamic_address = 0;
+    CHECK_EQ(0, kLowShadowBeg);
+
+    uptr granularity = GetMmapGranularity();
+    uptr alignment = 8 * granularity;
+    uptr left_padding = granularity;
+    uptr space_size = kHighShadowEnd + left_padding;
+
+    shadow_start = FindAvailableMemoryRange(space_size, alignment, granularity);
+    CHECK_NE((uptr)0, shadow_start);
+    CHECK(IsAligned(shadow_start, alignment));
+  }
+  // Update the shadow memory address (potentially) used by instrumentation.
+  __asan_shadow_memory_dynamic_address = shadow_start;
+
   if (kLowShadowBeg)
     shadow_start -= GetMmapGranularity();
   bool full_shadow_is_available =
       MemoryRangeIsAvailable(shadow_start, kHighShadowEnd);
 
 #if SANITIZER_LINUX && defined(__x86_64__) && defined(_LP64) &&                \
     !ASAN_FIXED_MAPPING
   if (!full_shadow_is_available) {
     kMidMemBeg = kLowMemEnd < 0x3000000000ULL ? 0x3000000000ULL : 0;
     kMidMemEnd = kLowMemEnd < 0x3000000000ULL ? 0x4fffffffffULL : 0;
   }
-#elif SANITIZER_WINDOWS64
-  // Disable the "mid mem" shadow layout.
-  if (!full_shadow_is_available) {
-    kMidMemBeg = 0;
-    kMidMemEnd = 0;
-  }
 #endif
 
   if (Verbosity()) PrintAddressSpaceLayout();
 
   DisableCoreDumperIfNecessary();
 
   if (full_shadow_is_available) {
     // mmap the low shadow plus at least one page at the left.

lib/asan/asan_win.cc

 
 extern "C" {
 SANITIZER_INTERFACE_ATTRIBUTE
 int __asan_should_detect_stack_use_after_return() {
   __asan_init();
   return __asan_option_detect_stack_use_after_return;
 }
 
+SANITIZER_INTERFACE_ATTRIBUTE
+uptr __asan_get_shadow_memory_dynamic_address() {
+  __asan_init();
+  return __asan_shadow_memory_dynamic_address;
+}
+
 // -------------------- A workaround for the absence of weak symbols ----- {{{
 // We don't have a direct equivalent of weak symbols when using MSVC, but we can
 // use the /alternatename directive to tell the linker to default a specific
 // symbol to a specific value, which works nicely for allocator hooks and
 // __asan_default_options().
 void __sanitizer_default_malloc_hook(void *ptr, uptr size) { }
 void __sanitizer_default_free_hook(void *ptr) { }
 const char* __asan_default_default_options() { return ""; }

lib/asan/asan_win_dll_thunk.cc

#define WRAP_W_WWWWWW(name)                                                    \
   }                                                                            \
   INTERCEPT_WHEN_POSSIBLE(#name, name);
 // }}}
 
 // ----------------- ASan own interface functions --------------------
 // Don't use the INTERFACE_FUNCTION machinery for this function as we actually
 // want to call it in the __asan_init interceptor.
 WRAP_W_V(__asan_should_detect_stack_use_after_return)
+WRAP_W_V(__asan_get_shadow_memory_dynamic_address)
 
 extern "C" {
   int __asan_option_detect_stack_use_after_return;
+  uptr __asan_shadow_memory_dynamic_address;
 
   // Manually wrap __asan_init as we need to initialize
   // __asan_option_detect_stack_use_after_return afterwards.
   void __asan_init() {
     typedef void (*fntype)();
     static fntype fn = 0;
     // __asan_init is expected to be called by only one thread.
     if (fn) return;
 
     fn = (fntype)getRealProcAddressOrDie("__asan_init");
     fn();
     __asan_option_detect_stack_use_after_return =
         (__asan_should_detect_stack_use_after_return() != 0);
-
+    __asan_shadow_memory_dynamic_address =
+        (uptr)__asan_get_shadow_memory_dynamic_address();
     InterceptHooks();
   }
 }
 
 extern "C" void __asan_version_mismatch_check() {
   // Do nothing.
 }
 

lib/asan/asan_win_dynamic_runtime_thunk.cc

 // Since in general we don't know if a given TU is going to be used
 // with a MT or MD runtime and we don't want to use ugly __imp_ names on Windows
 // just to work around this issue, let's clone the variable that is constant
 // after initialization anyways.
 extern "C" {
 __declspec(dllimport) int __asan_should_detect_stack_use_after_return();
 int __asan_option_detect_stack_use_after_return =
     __asan_should_detect_stack_use_after_return();
+
+__declspec(dllimport) void* __asan_get_shadow_memory_dynamic_address();
+void* __asan_shadow_memory_dynamic_address =
+    __asan_get_shadow_memory_dynamic_address();
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 // For some reason, the MD CRT doesn't call the C/C++ terminators during on DLL
 // unload or on exit.  ASan relies on LLVM global_dtors to call
 // __asan_unregister_globals on these events, which unfortunately doesn't work
 // with the MD runtime, see PR22545 for the details.
 // To work around this, for each DLL we schedule a call to UnregisterGlobals

lib/sanitizer_common/sanitizer_common.h

 void *MmapNoAccess(uptr size);
 // Map aligned chunk of address space; size and alignment are powers of two.
 void *MmapAlignedOrDie(uptr size, uptr alignment, const char *mem_type);
 // Disallow access to a memory range.  Use MmapFixedNoAccess to allocate an
 // unaccessible memory.
 bool MprotectNoAccess(uptr addr, uptr size);
 bool MprotectReadOnly(uptr addr, uptr size);
 
+// Find an available address space.
+uptr FindAvailableMemoryRange(uptr size, uptr alignment, uptr left_padding);
+
 // Used to check if we can map shadow memory to a fixed location.
 bool MemoryRangeIsAvailable(uptr range_start, uptr range_end);
 void ReleaseMemoryToOS(uptr addr, uptr size);
 void IncreaseTotalMmap(uptr size);
 void DecreaseTotalMmap(uptr size);
 uptr GetRSS();
 void NoHugePagesInRegion(uptr addr, uptr length);
 void DontDumpShadowMemory(uptr addr, uptr length);

lib/sanitizer_common/sanitizer_posix.cc

SignalContext SignalContext::Create(void *siginfo, void *context) {
   uptr addr = (uptr)si->si_addr;
   uptr pc, sp, bp;
   GetPcSpBp(context, &pc, &sp, &bp);
   WriteFlag write_flag = GetWriteFlag(context);
   bool is_memory_access = si->si_signo == SIGSEGV;
   return SignalContext(context, addr, pc, sp, bp, is_memory_access, write_flag);
 }
 
+uptr FindAvailableMemoryRange(uptr size, uptr alignment, uptr left_padding) {
+  CHECK("FindAvailableMemoryRange is not available" && 0);
+  return 0;
+}
+
 } // namespace __sanitizer
 
 #endif // SANITIZER_POSIX

lib/sanitizer_common/sanitizer_win.cc

void NoHugePagesInRegion(uptr addr, uptr size) {
   // FIXME: probably similar to ReleaseMemoryToOS.
 }
 
 void DontDumpShadowMemory(uptr addr, uptr length) {
   // This is almost useless on 32-bits.
   // FIXME: add madvise-analog when we move to 64-bits.
 }
 
+uptr FindAvailableMemoryRange(uptr size, uptr alignment, uptr left_padding) {
+  uptr address = 0;
+  while (true) {
+    MEMORY_BASIC_INFORMATION info;
+    if (!::VirtualQuery((void*)address, &info, sizeof(info)))
+      return 0;
+
+    if (info.State == MEM_FREE) {
+      uptr shadow_address = RoundUpTo((uptr)info.BaseAddress + left_padding,
+                                      alignment);
+      if (shadow_address + size < (uptr)info.BaseAddress + info.RegionSize)
+        return shadow_address;
+    }
+
+    // Move to the next region.
+    address = (uptr)info.BaseAddress + info.RegionSize;
+  }
+  return 0;
+}
+
 bool MemoryRangeIsAvailable(uptr range_start, uptr range_end) {
   MEMORY_BASIC_INFORMATION mbi;
   CHECK(VirtualQuery((void *)range_start, &mbi, sizeof(mbi)));
   return mbi.Protect == PAGE_NOACCESS &&
          (uptr)mbi.BaseAddress + mbi.RegionSize >= range_end;
 }
 
 void *MapFileToMemory(const char *file_name, uptr *buff_size) {