Index: compiler-rt/trunk/lib/asan/asan_internal.h
===================================================================
--- compiler-rt/trunk/lib/asan/asan_internal.h
+++ compiler-rt/trunk/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: compiler-rt/trunk/lib/asan/asan_linux.cc
===================================================================
--- compiler-rt/trunk/lib/asan/asan_linux.cc
+++ compiler-rt/trunk/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: compiler-rt/trunk/lib/asan/asan_mac.cc
===================================================================
--- compiler-rt/trunk/lib/asan/asan_mac.cc
+++ compiler-rt/trunk/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: compiler-rt/trunk/lib/asan/asan_rtl.cc
===================================================================
--- compiler-rt/trunk/lib/asan/asan_rtl.cc
+++ compiler-rt/trunk/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: compiler-rt/trunk/lib/asan/asan_win.cc
===================================================================
--- compiler-rt/trunk/lib/asan/asan_win.cc
+++ compiler-rt/trunk/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: compiler-rt/trunk/lib/sanitizer_common/CMakeLists.txt
===================================================================
--- compiler-rt/trunk/lib/sanitizer_common/CMakeLists.txt
+++ compiler-rt/trunk/lib/sanitizer_common/CMakeLists.txt
@@ -58,6 +58,7 @@
   sanitizer_coverage_libcdep_new.cc
   sanitizer_coverage_win_sections.cc
   sanitizer_linux_libcdep.cc
+  sanitizer_mac_libcdep.cc
   sanitizer_posix_libcdep.cc
   sanitizer_stacktrace_libcdep.cc
   sanitizer_stoptheworld_linux_libcdep.cc
Index: compiler-rt/trunk/lib/sanitizer_common/sanitizer_common.h
===================================================================
--- compiler-rt/trunk/lib/sanitizer_common/sanitizer_common.h
+++ compiler-rt/trunk/lib/sanitizer_common/sanitizer_common.h
@@ -107,7 +107,8 @@
 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);
 
 // Used to check if we can map shadow memory to a fixed location.
 bool MemoryRangeIsAvailable(uptr range_start, uptr range_end);
Index: compiler-rt/trunk/lib/sanitizer_common/sanitizer_linux.cc
===================================================================
--- compiler-rt/trunk/lib/sanitizer_common/sanitizer_linux.cc
+++ compiler-rt/trunk/lib/sanitizer_common/sanitizer_linux.cc
@@ -1671,7 +1671,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: compiler-rt/trunk/lib/sanitizer_common/sanitizer_mac.h
===================================================================
--- compiler-rt/trunk/lib/sanitizer_common/sanitizer_mac.h
+++ compiler-rt/trunk/lib/sanitizer_common/sanitizer_mac.h
@@ -36,6 +36,8 @@
 
 char **GetEnviron();
 
+void RestrictMemoryToMaxAddress(uptr max_address);
+
 }  // namespace __sanitizer
 
 extern "C" {
Index: compiler-rt/trunk/lib/sanitizer_common/sanitizer_mac.cc
===================================================================
--- compiler-rt/trunk/lib/sanitizer_common/sanitizer_mac.cc
+++ compiler-rt/trunk/lib/sanitizer_common/sanitizer_mac.cc
@@ -840,7 +840,8 @@
 
 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 +852,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;
@@ -860,10 +862,15 @@
                                 (vm_region_info_t)&vminfo, &count);
     if (free_begin != address) {
       // 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) {
-        return shadow_address;
+      uptr gap_start = RoundUpTo((uptr)free_begin + left_padding, alignment);
+      uptr gap_end = RoundDownTo((uptr)address, alignment);
+      uptr gap_size = gap_end > gap_start ? gap_end - gap_start : 0;
+      if (shadow_size < gap_size) {
+        return gap_start;
+      }
+
+      if (largest_gap_found && *largest_gap_found < gap_size) {
+        *largest_gap_found = gap_size;
       }
     }
     // Move to the next region.
Index: compiler-rt/trunk/lib/sanitizer_common/sanitizer_mac_libcdep.cc
===================================================================
--- compiler-rt/trunk/lib/sanitizer_common/sanitizer_mac_libcdep.cc
+++ compiler-rt/trunk/lib/sanitizer_common/sanitizer_mac_libcdep.cc
@@ -0,0 +1,30 @@
+//===-- sanitizer_mac_libcdep.cc ------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is shared between various sanitizers' runtime libraries and
+// implements OSX-specific functions.
+//===----------------------------------------------------------------------===//
+
+#include "sanitizer_platform.h"
+#if SANITIZER_MAC
+#include "sanitizer_mac.h"
+
+#include <sys/mman.h>
+
+namespace __sanitizer {
+
+void RestrictMemoryToMaxAddress(uptr max_address) {
+  uptr size_to_mmap = GetMaxVirtualAddress() + 1 - max_address;
+  void *res = MmapFixedNoAccess(max_address, size_to_mmap, "high gap");
+  CHECK(res != MAP_FAILED);
+}
+
+}  // namespace __sanitizer
+
+#endif  // SANITIZER_MAC
Index: compiler-rt/trunk/lib/sanitizer_common/sanitizer_win.cc
===================================================================
--- compiler-rt/trunk/lib/sanitizer_common/sanitizer_win.cc
+++ compiler-rt/trunk/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;