[asan] For iOS/AArch64, if the dynamic shadow doesn't fit, restrict the VM space

[kubamracek]

Summary

On iOS/AArch64, the address space is very limited and has a dynamic maximum address based on the configuration of the device. We're already using a dynamic shadow, and we find a large-enough "gap" in the VM where we place the shadow memory. In some cases and some device configuration, we might not be able to find a large-enough gap: E.g. if the main executable is linked against a large number of libraries that are not part of the system, these libraries can fragment the address space, and this happens before ASan starts initializing.

This patch has a solution, where we have a "backup plan" when we cannot find a large-enough gap: We will restrict the address space (via MmapFixedNoAccess) to a limit, for which the shadow limit will fit.

[vitalybuka]

lib/asan/asan_linux.cc

80

Maybe it's better to not define function at all and trigger linking error?

[vitalybuka]

LGTM

lib/asan/asan_linux.cc

80

Please ignore this, I see this is called from branch which should not be executed on linux.

[alekseyshl]

lib/asan/asan_mac.cc

70

Why to 1 MB? Is it a Mac requirement?

lib/sanitizer_common/sanitizer_common.h

112

Why does it have to be in sanitizer_common.h? There's sanitizer_mac.h

lib/sanitizer_common/sanitizer_common_nolibc.cc

41

I wonder what target fails without this definition?

lib/sanitizer_common/sanitizer_mac.cc

843

Can mmap fail here?

[kubamracek]

lib/asan/asan_mac.cc

70

Not really, this is purely for convenience and debugging - it's nice to see the memory map nicely aligned. I can drop this (but we'll still need to round down to at least 8*PAGE_SIZE, maybe more).

lib/sanitizer_common/sanitizer_common.h

112

Right.

lib/sanitizer_common/sanitizer_common_nolibc.cc

41

Actually, it's safestack.a, which uses sanitizer_common, but links in a nolibc mode.

lib/sanitizer_common/sanitizer_mac.cc

843

I'll add an assert.

[alekseyshl]

lib/asan/asan_mac.cc

70

No, it's fine, just add a comment that it is arbitrary and purely for the debugging convenience.

lib/sanitizer_common/sanitizer_common_nolibc.cc

41

I presume it's RestrictMemoryToMaxAddress what needs MmapFixedNoAccess. How about moving it into sanitizer_mac_libcdep.cc?

[kubamracek]

lib/sanitizer_common/sanitizer_common_nolibc.cc

41

sanitizer_mac_libcdep.cc doesn't currently exist... Do you want me to create it?

[alekseyshl]

lib/sanitizer_common/sanitizer_common_nolibc.cc

41

Yes, please do create it, it seems like a cleaner solution than an unreachable function.

[kubamracek]

sanitizer_mac_libcdep.cc doesn't currently exist... Do you want me to create it?

Yes, please do create it, it seems like a cleaner solution than an unreachable function.

Done.

[eugenis]

lib/asan/asan_mac.cc

70

Why does it have to be aligned to 8*PAGE_SIZE?

[eugenis]

lib/asan/asan_mac.cc

70

No matter, I got it. Sorry for the stupid question.

lib/asan/asan_internal.h

 
 // asan_rtl.cc
 void NORETURN ShowStatsAndAbort();
 
 // asan_malloc_linux.cc / asan_malloc_mac.cc
 void ReplaceSystemMalloc();
 
 // asan_linux.cc / asan_mac.cc / asan_win.cc
+uptr FindDynamicShadowStart();
 void *AsanDoesNotSupportStaticLinkage();
 void AsanCheckDynamicRTPrereqs();
 void AsanCheckIncompatibleRT();
 
 // Support function for __asan_(un)register_image_globals. Searches for the
 // loaded image containing `needle' and then enumerates all global metadata
 // structures declared in that image, applying `op' (e.g.,
 // __asan_(un)register_globals) to them.

lib/asan/asan_linux.cc

 void InitializePlatformExceptionHandlers() {}
 bool IsSystemHeapAddress (uptr addr) { return false; }
 
 void *AsanDoesNotSupportStaticLinkage() {
   // This will fail to link with -static.
   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();
 }
 
 #if SANITIZER_ANDROID
 // FIXME: should we do anything for Android?
 void AsanCheckDynamicRTPrereqs() {}
 void AsanCheckIncompatibleRT() {}

lib/asan/asan_mac.cc

 void InitializePlatformExceptionHandlers() {}
 bool IsSystemHeapAddress (uptr addr) { return false; }
 
 // No-op. Mac does not support static linkage anyway.
 void *AsanDoesNotSupportStaticLinkage() {
   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) {
+    // Round down to multiplies of 1 MB.
+    uptr new_max_vm = RoundDownTo(largest_gap_found << SHADOW_SCALE, 0x100000);
+    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() {}
 
 // No-op. Mac does not support static linkage anyway.
 void AsanCheckIncompatibleRT() {}
 
 void AsanApplyToGlobals(globals_op_fptr op, const void *needle) {
   // Find the Mach-O header for the image containing the needle

lib/asan/asan_rtl.cc

static void InitializeShadowMemory() {
   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));
+    shadow_start = FindDynamicShadowStart();
   }
   // 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);

lib/asan/asan_win.cc

 // ---------------------- Various stuff ---------------- {{{
 void *AsanDoesNotSupportStaticLinkage() {
 #if defined(_DEBUG)
 #error Please build the runtime with a non-debug CRT: /MD or /MT
 #endif
   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() {}
 
 void ReadContextStack(void *context, uptr *stack, uptr *ssize) {
   UNIMPLEMENTED();
 }
 

lib/sanitizer_common/sanitizer_common.h

 void *MmapAlignedOrDieOnFatalError(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);
+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);
 // Releases memory pages entirely within the [beg, end] address range. Noop if
 // the provided range does not contain at least one entire page.
 void ReleaseMemoryPagesToOS(uptr beg, uptr end);
 void IncreaseTotalMmap(uptr size);
 void DecreaseTotalMmap(uptr size);

lib/sanitizer_common/sanitizer_common_nolibc.cc

 void Abort() { internal__exit(1); }
 void SleepForSeconds(int seconds) { internal_sleep(seconds); }
 #endif // !SANITIZER_WINDOWS
 
 #if !SANITIZER_WINDOWS && !SANITIZER_MAC
 void ListOfModules::init() {}
 #endif
 
+#if SANITIZER_POSIX
+void *MmapFixedNoAccess(uptr fixed_addr, uptr size, const char *name) {
+  UNREACHABLE("MmapFixedNoAccess requires libc");
+  return nullptr;
+}
+#endif
+
 }  // namespace __sanitizer

lib/sanitizer_common/sanitizer_linux.cc

Report(
         "). If you want to run %s library under sanitizers please remove "
         "RTLD_DEEPBIND from dlopen flags.\n",
         filename, filename);
     Die();
   }
 #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;
 }
 
 bool GetRandom(void *buffer, uptr length) {
   if (!buffer || !length || length > 256)
     return false;
 #if defined(__NR_getrandom)

lib/sanitizer_common/sanitizer_mac.cc

 # else
   return (1ULL << 47) - 1;  // 0x00007fffffffffffUL;
 # endif
 #else  // SANITIZER_WORDSIZE == 32
   return (1ULL << 32) - 1;  // 0xffffffff;
 #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
   // 4KB on 32-bit and 4GB on 64-bit.
   mach_vm_address_t start_address =
     (SANITIZER_WORDSIZE == 32) ? 0x000000001000 : 0x000100000000;
 
   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;
     RegionInfo vminfo;
     mach_msg_type_number_t count = kRegionInfoSize;
     kr = mach_vm_region_recurse(mach_task_self(), &address, &vmsize, &depth,
                                 (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.
     address += vmsize;
     free_begin = address;
   }
 
   // We looked at all free regions and could not find one large enough.

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 FindAvailableMemoryRange(uptr size, uptr alignment, uptr left_padding,
+                              uptr *largest_gap_found) {
   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,