Index: lib/asan/asan_internal.h
===================================================================
--- lib/asan/asan_internal.h
+++ lib/asan/asan_internal.h
@@ -75,6 +75,7 @@
 void ReplaceSystemMalloc();
 
 // asan_linux.cc / asan_mac.cc / asan_win.cc
+uptr FindDynamicShadowStart();
 void *AsanDoesNotSupportStaticLinkage();
 void AsanCheckDynamicRTPrereqs();
 void AsanCheckIncompatibleRT();
Index: lib/asan/asan_linux.cc
===================================================================
--- lib/asan/asan_linux.cc
+++ lib/asan/asan_linux.cc
@@ -77,6 +77,11 @@
   return &_DYNAMIC;  // defined in link.h
 }
 
+uptr FindDynamicShadowStart() {
+  UNREACHABLE("FindDynamicShadowStart is not available");
+  return 0;
+}
+
 void AsanApplyToGlobals(globals_op_fptr op, const void *needle) {
   UNIMPLEMENTED();
 }
Index: lib/asan/asan_mac.cc
===================================================================
--- lib/asan/asan_mac.cc
+++ lib/asan/asan_mac.cc
@@ -55,6 +55,29 @@
   return 0;
 }
 
+uptr FindDynamicShadowStart() {
+  uptr granularity = GetMmapGranularity();
+  uptr alignment = 8 * granularity;
+  uptr left_padding = granularity;
+  uptr space_size = kHighShadowEnd + left_padding;
+
+  uptr largest_gap_found = 0;
+  uptr shadow_start = FindAvailableMemoryRange(space_size, alignment,
+                                               granularity, &largest_gap_found);
+  // If the shadow doesn't fit, restrict the address space to make it fit.
+  if (shadow_start == 0) {
+    uptr new_max_vm = RoundDownTo(largest_gap_found << SHADOW_SCALE, alignment);
+    RestrictMemoryToMaxAddress(new_max_vm);
+    kHighMemEnd = new_max_vm - 1;
+    space_size = kHighShadowEnd + left_padding;
+    shadow_start =
+        FindAvailableMemoryRange(space_size, alignment, granularity, nullptr);
+  }
+  CHECK_NE((uptr)0, shadow_start);
+  CHECK(IsAligned(shadow_start, alignment));
+  return shadow_start;
+}
+
 // No-op. Mac does not support static linkage anyway.
 void AsanCheckDynamicRTPrereqs() {}
 
Index: lib/asan/asan_rtl.cc
===================================================================
--- lib/asan/asan_rtl.cc
+++ lib/asan/asan_rtl.cc
@@ -438,15 +438,7 @@
   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));
+    shadow_start = FindDynamicShadowStart();
   }
   // Update the shadow memory address (potentially) used by instrumentation.
   __asan_shadow_memory_dynamic_address = shadow_start;
Index: lib/asan/asan_win.cc
===================================================================
--- lib/asan/asan_win.cc
+++ lib/asan/asan_win.cc
@@ -217,6 +217,18 @@
   return 0;
 }
 
+uptr FindDynamicShadowStart() {
+  uptr granularity = GetMmapGranularity();
+  uptr alignment = 8 * granularity;
+  uptr left_padding = granularity;
+  uptr space_size = kHighShadowEnd + left_padding;
+  uptr shadow_start =
+      FindAvailableMemoryRange(space_size, alignment, granularity, nullptr);
+  CHECK_NE((uptr)0, shadow_start);
+  CHECK(IsAligned(shadow_start, alignment));
+  return shadow_start;
+}
+
 void AsanCheckDynamicRTPrereqs() {}
 
 void AsanCheckIncompatibleRT() {}
Index: lib/sanitizer_common/sanitizer_common.h
===================================================================
--- lib/sanitizer_common/sanitizer_common.h
+++ lib/sanitizer_common/sanitizer_common.h
@@ -107,7 +107,9 @@
 bool MprotectReadOnly(uptr addr, uptr size);
 
 // Find an available address space.
-uptr FindAvailableMemoryRange(uptr size, uptr alignment, uptr left_padding);
+uptr FindAvailableMemoryRange(uptr size, uptr alignment, uptr left_padding,
+                              uptr *largest_gap_found);
+void RestrictMemoryToMaxAddress(uptr max_address);
 
 // Used to check if we can map shadow memory to a fixed location.
 bool MemoryRangeIsAvailable(uptr range_start, uptr range_end);
Index: lib/sanitizer_common/sanitizer_linux.cc
===================================================================
--- lib/sanitizer_common/sanitizer_linux.cc
+++ lib/sanitizer_common/sanitizer_linux.cc
@@ -1677,7 +1677,8 @@
 #endif
 }
 
-uptr FindAvailableMemoryRange(uptr size, uptr alignment, uptr left_padding) {
+uptr FindAvailableMemoryRange(uptr size, uptr alignment, uptr left_padding,
+                              uptr *largest_gap_found) {
   UNREACHABLE("FindAvailableMemoryRange is not available");
   return 0;
 }
Index: lib/sanitizer_common/sanitizer_mac.cc
===================================================================
--- lib/sanitizer_common/sanitizer_mac.cc
+++ lib/sanitizer_common/sanitizer_mac.cc
@@ -838,9 +838,15 @@
 #endif  // SANITIZER_WORDSIZE
 }
 
+void RestrictMemoryToMaxAddress(uptr max_address) {
+  uptr size_to_mmap = GetMaxVirtualAddress() + 1 - max_address;
+  MmapFixedNoAccess(max_address, size_to_mmap, "high gap");
+}
+
 uptr FindAvailableMemoryRange(uptr shadow_size,
                               uptr alignment,
-                              uptr left_padding) {
+                              uptr left_padding,
+                              uptr *largest_gap_found) {
   typedef vm_region_submap_short_info_data_64_t RegionInfo;
   enum { kRegionInfoSize = VM_REGION_SUBMAP_SHORT_INFO_COUNT_64 };
   // Start searching for available memory region past PAGEZERO, which is
@@ -851,6 +857,7 @@
   mach_vm_address_t address = start_address;
   mach_vm_address_t free_begin = start_address;
   kern_return_t kr = KERN_SUCCESS;
+  if (largest_gap_found) *largest_gap_found = 0;
   while (kr == KERN_SUCCESS) {
     mach_vm_size_t vmsize = 0;
     natural_t depth = 0;
@@ -862,9 +869,14 @@
       // We found a free region [free_begin..address-1].
       uptr shadow_address = RoundUpTo((uptr)free_begin + left_padding,
                                       alignment);
-      if (shadow_address + shadow_size < (uptr)address) {
+      uptr possible_gap_size = (uptr)address - shadow_address;
+      if (shadow_size < possible_gap_size) {
         return shadow_address;
       }
+
+      if (largest_gap_found && *largest_gap_found < possible_gap_size) {
+        *largest_gap_found = possible_gap_size;
+      }
     }
     // Move to the next region.
     address += vmsize;
Index: lib/sanitizer_common/sanitizer_win.cc
===================================================================
--- lib/sanitizer_common/sanitizer_win.cc
+++ lib/sanitizer_common/sanitizer_win.cc
@@ -291,7 +291,8 @@
   // FIXME: add madvise-analog when we move to 64-bits.
 }
 
-uptr FindAvailableMemoryRange(uptr size, uptr alignment, uptr left_padding) {
+uptr FindAvailableMemoryRange(uptr size, uptr alignment, uptr left_padding,
+                              uptr *largest_gap_found) {
   uptr address = 0;
   while (true) {
     MEMORY_BASIC_INFORMATION info;