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

[etienneb]

Summary

This patch is adding the needed code to compiler-rt to support
dynamic shadow.

This is to support this patch:

https://reviews.llvm.org/D23354

It's adding support for using a shadow placed at a dynamic address determined
at runtime.

The dynamic shadow is required to work on windows 64-bits.

[kcc]

I am not a fan of this change because it adds extra complexity and makes asan slower.
As I've commented in the other patch, I first want to know for sure that having a fixed address is impossible.
So far I have not seen an explanation.

[etienneb]

In D23363#511583, @kcc wrote:

I am not a fan of this change because it adds extra complexity and makes asan slower.
As I've commented in the other patch, I first want to know for sure that having a fixed address is impossible.
So far I have not seen an explanation.

This is not making ASAN slower, except for the cases where it's configured to use a dynamic shadow.
So, Asan on every plateform should be the same.... except on win64.

[etienneb]

With these two patches, asan unittests are passing on windows 64-bit.

https://reviews.llvm.org/D23354
https://reviews.llvm.org/D23363

D:\src\llvm\ninja64>ninja check-asan
-- Testing: 536 tests, 16 threads --
Testing: 0 .. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90..
Testing Time: 68.45s
  Expected Passes    : 374
  Expected Failures  : 15
  Unsupported Tests  : 147

[kubamracek]

lib/asan/asan_interface_internal.h

33

Can we get argument names here?

[etienneb]

rebased, conflicts resolved.

[etienneb]

nit

[etienneb]

nit

[etienneb]

rebased + cleanup

[vitalybuka]

lib/asan/asan_rtl.cc

472

Not sure how this going to link. This code is going to be compiled for all platforms, but
FindAvailableMemoryRange is defined only for windows.
Probably we need some default {return nulltpr;} implementation.

662

please clang-format this

[etienneb]

fix linking issue (debug mode)

[etienneb]

thx, it was a good catch.
The build was broken in debug. Optimisation was taking away the need for FindAvailableMemoryAddress.

lib/asan/asan_rtl.cc

472

It was compiling on linux because of the compiler optimisaiton.
This is a good catch. Thx!

[vitalybuka]

Maybe CHECK(!"FindAvailableMemoryRange is not available");
LGTM

[pcc]

Hi Etienne, I think your change caused asan test failures on the bot:

http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux/builds/25405
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux/builds/25406

Can you please take a look?

lib/asan/asan_allocator.h

 const uptr kAllocatorSpace =  0xa0000000000ULL;
 const uptr kAllocatorSize  =  0x20000000000ULL;  // 2T.
 # elif defined(__aarch64__)
 // AArch64/SANITIZIER_CAN_USER_ALLOCATOR64 is only for 42-bit VMA
 // so no need to different values for different VMA.
 const uptr kAllocatorSpace =  0x10000000000ULL;
 const uptr kAllocatorSize  =  0x10000000000ULL;  // 3T.
 # else
+#  if SANITIZER_WINDOWS
+const uptr kAllocatorSpace = ~(uptr)0;
+const uptr kAllocatorSize  =  0x8000000000ULL;  // 500G
+#  else
 const uptr kAllocatorSpace = 0x600000000000ULL;
 const uptr kAllocatorSize  =  0x40000000000ULL;  // 4T.
-# endif
+#  endif
+# endif
 typedef DefaultSizeClassMap SizeClassMap;
 struct AP64 {  // Allocator64 parameters. Deliberately using a short name.
   static const uptr kSpaceBeg = kAllocatorSpace;
   static const uptr kSpaceSize = kAllocatorSize;
   static const uptr kMetadataSize = 0;
   typedef __asan::SizeClassMap SizeClassMap;
   typedef AsanMapUnmapCallback MapUnmapCallback;
   static const uptr kFlags = 0;

lib/asan/asan_interface_internal.h

 
 using __sanitizer::uptr;
 
 extern "C" {
   // This function should be called at the very beginning of the process,
   // before any instrumented code is executed and before any call to malloc.
   SANITIZER_INTERFACE_ATTRIBUTE void __asan_init();
 
+  // This function should be called by a loaded instrumented module.
+  SANITIZER_INTERFACE_ATTRIBUTE void __asan_init_from_dll(
+      int *detect_stack_use_after_return, uptr *shadow_memory_dynamic_address);
+
   // This function exists purely to get a linker/loader error when using
   // incompatible versions of instrumentation and runtime library. Please note
   // that __asan_version_mismatch_check is a macro that is replaced with
   // __asan_version_mismatch_check_vXXX at compile-time.
   SANITIZER_INTERFACE_ATTRIBUTE void __asan_version_mismatch_check();
 
   // This structure is used to describe the source location of a place where
   // global was defined.
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

 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();
 
+  __asan_shadow_memory_dynamic_address = 0;
   uptr shadow_start = kLowShadowBeg;
+  if (shadow_start == 0) {
+    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));
+  }
+  __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.

 
 // Initialize as requested from instrumented application code.
 // We use this call as a trigger to wake up ASan from deactivated state.
 void __asan_init() {
   AsanActivate();
   AsanInitInternal();
 }
 
+// Called by a loaded DLL to initialize itself.
+void __asan_init_from_dll(
+    int* detect_stack_use_after_return,
+    uptr* shadow_memory_dynamic_address) {
+  __asan_init();
+  *detect_stack_use_after_return = __asan_option_detect_stack_use_after_return;
+  *shadow_memory_dynamic_address = __asan_shadow_memory_dynamic_address;
+}
+
 void __asan_version_mismatch_check() {
   // Do nothing.
 }

lib/asan/asan_win_dll_thunk.cc

extern "C" void *name(void *arg1, void *arg2, void *arg3, void *arg4,        \
     return fn(arg1, arg2, arg3, arg4, arg5, arg6);                             \
   }                                                                            \
   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)
-
 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)();
+     typedef void (*fntype)(int*, uptr*);
     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);
+    fn = (fntype)getRealProcAddressOrDie("__asan_init_from_dll");
+    fn(&__asan_option_detect_stack_use_after_return,
+       &__asan_shadow_memory_dynamic_address);
 
     InterceptHooks();
   }
 }
 
 extern "C" void __asan_version_mismatch_check() {
   // Do nothing.
 }

lib/asan/asan_win_dynamic_runtime_thunk.cc

 
 // First, declare CRT sections we'll be using in this file
 #pragma section(".CRT$XID", long, read)  // NOLINT
 #pragma section(".CRT$XCAB", long, read)  // NOLINT
 #pragma section(".CRT$XTW", long, read)  // NOLINT
 #pragma section(".CRT$XTY", long, read)  // NOLINT
 
 ////////////////////////////////////////////////////////////////////////////////
-// Define a copy of __asan_option_detect_stack_use_after_return that should be
-// used when linking an MD runtime with a set of object files on Windows.
-//
-// The ASan MD runtime dllexports '__asan_option_detect_stack_use_after_return',
-// so normally we would just dllimport it.  Unfortunately, the dllimport
-// attribute adds __imp_ prefix to the symbol name of a variable.
-// 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();
-}
-
-////////////////////////////////////////////////////////////////////////////////
 // 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
 // using atexit() that calls a small subset of C terminators
 // where LLVM global_dtors is placed.  Fingers crossed, no other C terminators
 // are there.

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_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) {