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

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
```

Reviewers: rnk, zaks.anna

Subscribers: tberghammer, danalbert, kubabrecka, dberris, chrisha, llvm-commits

Differential Revision: https://reviews.llvm.org/D25104

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@282882 91177308-0d34-0410-b5e6-96231b3b80d8

9 files changed, 71 insertions, 9 deletions

diff --git a/lib/asan/asan_interface_internal.h b/lib/asan/asan_interface_internal.h
index f9a1eb5a2..8cd424cc0 100644
--- a/lib/asan/asan_interface_internal.h
+++ b/lib/asan/asan_interface_internal.h
@@ -172,6 +172,9 @@ extern "C" {
   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;
diff --git a/lib/asan/asan_mapping.h b/lib/asan/asan_mapping.h
index 52c4f67a5..24584e94f 100644
--- a/lib/asan/asan_mapping.h
+++ b/lib/asan/asan_mapping.h
@@ -125,6 +125,7 @@
 // || `[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.
@@ -140,7 +141,6 @@ 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
 
@@ -183,7 +183,7 @@ static const u64 kWindowsShadowOffset64 = 1ULL << 45;  // 32TB
 #  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
diff --git a/lib/asan/asan_rtl.cc b/lib/asan/asan_rtl.cc
index 5a1128d6e..462867be0 100644
--- a/lib/asan/asan_rtl.cc
+++ b/lib/asan/asan_rtl.cc
@@ -32,6 +32,7 @@
 #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.
 
@@ -460,7 +461,30 @@ static void AsanInitInternal() {
 
   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 =
@@ -472,12 +496,6 @@ static void AsanInitInternal() {
     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();
diff --git a/lib/asan/asan_win.cc b/lib/asan/asan_win.cc
index 58649139e..c3f7943c2 100644
--- a/lib/asan/asan_win.cc
+++ b/lib/asan/asan_win.cc
@@ -37,6 +37,12 @@ int __asan_should_detect_stack_use_after_return() {
   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
diff --git a/lib/asan/asan_win_dll_thunk.cc b/lib/asan/asan_win_dll_thunk.cc
index 4b8a08c5e..607af703b 100644
--- a/lib/asan/asan_win_dll_thunk.cc
+++ b/lib/asan/asan_win_dll_thunk.cc
@@ -200,9 +200,11 @@ static void InterceptHooks();
 // 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.
@@ -216,7 +218,8 @@ extern "C" {
     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();
   }
 }
diff --git a/lib/asan/asan_win_dynamic_runtime_thunk.cc b/lib/asan/asan_win_dynamic_runtime_thunk.cc
index c6e2a65a4..a0224f699 100644
--- a/lib/asan/asan_win_dynamic_runtime_thunk.cc
+++ b/lib/asan/asan_win_dynamic_runtime_thunk.cc
@@ -48,6 +48,10 @@ 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();
 }
 
 ////////////////////////////////////////////////////////////////////////////////
diff --git a/lib/sanitizer_common/sanitizer_common.h b/lib/sanitizer_common/sanitizer_common.h
index 2de93ebae..779e96fe6 100644
--- a/lib/sanitizer_common/sanitizer_common.h
+++ b/lib/sanitizer_common/sanitizer_common.h
@@ -98,6 +98,9 @@ void *MmapAlignedOrDie(uptr size, uptr alignment, const char *mem_type);
 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);
diff --git a/lib/sanitizer_common/sanitizer_posix.cc b/lib/sanitizer_common/sanitizer_posix.cc
index c70d5a40c..ad5db8829 100644
--- a/lib/sanitizer_common/sanitizer_posix.cc
+++ b/lib/sanitizer_common/sanitizer_posix.cc
@@ -358,6 +358,11 @@ SignalContext SignalContext::Create(void *siginfo, void *context) {
   return SignalContext(context, addr, pc, sp, bp, is_memory_access, write_flag);
 }
 
+uptr FindAvailableMemoryRange(uptr size, uptr alignment, uptr left_padding) {
+  UNREACHABLE("FindAvailableMemoryRange is not available");
+  return 0;
+}
+
 } // namespace __sanitizer
 
 #endif // SANITIZER_POSIX
diff --git a/lib/sanitizer_common/sanitizer_win.cc b/lib/sanitizer_common/sanitizer_win.cc
index 7555360c6..1fd79231d 100644
--- a/lib/sanitizer_common/sanitizer_win.cc
+++ b/lib/sanitizer_common/sanitizer_win.cc
@@ -249,6 +249,26 @@ void DontDumpShadowMemory(uptr addr, uptr length) {
   // 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)));