New MSan mapping layout (compiler-rt part)

[eugenis]

Summary

This is an implementation of https://github.com/google/sanitizers/issues/579

It has a number of advantages over the current mapping:

• works for non-PIE executables
• does not require ASLR; as a consequence, debugging MSan programs in gdb no longer requires "set disable-randomization off"
• supports linux kernels >=4.1.2
• the code is marginally faster and smaller

This is an ABI break. We never really promised ABI stability, but this patch includes a courtesy escape hatch: a compile-time macro that reverts back to the old mapping layout. The same macro will be used in the llvm part of the patch, their definitions have to match, of course.

[samsonov]

LGTM

Incredibly cool!

[eugenis]

r249754

lib/msan/msan.h

 //   High: 6000 0000 0000 - 7fff ffff ffff  ->  0000 0000 0000 - 1fff ffff ffff
 #define LINEARIZE_MEM(mem) \
   (((uptr)(mem) & ~0xc00000000000ULL) ^ 0x200000000000ULL)
 #define MEM_TO_SHADOW(mem) (LINEARIZE_MEM((mem)) + 0x100000000000ULL)
 #define SHADOW_TO_ORIGIN(shadow) (((uptr)(shadow)) + 0x280000000000)
 
 #elif SANITIZER_LINUX && SANITIZER_WORDSIZE == 64
 
+#ifdef MSAN_LINUX_X86_64_OLD_MAPPING
 // Requries PIE binary and ASLR enabled.
 // Main thread stack and DSOs at 0x7f0000000000 (sometimes 0x7e0000000000).
 // Heap at 0x600000000000.
 const MappingDesc kMemoryLayout[] = {
     {0x000000000000ULL, 0x200000000000ULL, MappingDesc::INVALID, "invalid"},
     {0x200000000000ULL, 0x400000000000ULL, MappingDesc::SHADOW, "shadow"},
     {0x400000000000ULL, 0x600000000000ULL, MappingDesc::ORIGIN, "origin"},
     {0x600000000000ULL, 0x800000000000ULL, MappingDesc::APP, "app"}};
 
 #define MEM_TO_SHADOW(mem) (((uptr)(mem)) & ~0x400000000000ULL)
 #define SHADOW_TO_ORIGIN(mem) (((uptr)(mem)) + 0x200000000000ULL)
+#else  // MSAN_LINUX_X86_64_OLD_MAPPING
+// All of the following configurations are supported.
+// ASLR disabled: main executable and DSOs at 0x555550000000
+// PIE and ASLR: main executable and DSOs at 0x7f0000000000
+// non-PIE: main executable below 0x100000000, DSOs at 0x7f0000000000
+// Heap at 0x700000000000.
+const MappingDesc kMemoryLayout[] = {
+    {0x000000000000ULL, 0x010000000000ULL, MappingDesc::APP, "app-1"},
+    {0x010000000000ULL, 0x100000000000ULL, MappingDesc::SHADOW, "shadow-2"},
+    {0x100000000000ULL, 0x110000000000ULL, MappingDesc::INVALID, "invalid"},
+    {0x110000000000ULL, 0x200000000000ULL, MappingDesc::ORIGIN, "origin-2"},
+    {0x200000000000ULL, 0x300000000000ULL, MappingDesc::SHADOW, "shadow-3"},
+    {0x300000000000ULL, 0x400000000000ULL, MappingDesc::ORIGIN, "origin-3"},
+    {0x400000000000ULL, 0x500000000000ULL, MappingDesc::INVALID, "invalid"},
+    {0x500000000000ULL, 0x510000000000ULL, MappingDesc::SHADOW, "shadow-1"},
+    {0x510000000000ULL, 0x600000000000ULL, MappingDesc::APP, "app-2"},
+    {0x600000000000ULL, 0x610000000000ULL, MappingDesc::ORIGIN, "origin-1"},
+    {0x610000000000ULL, 0x700000000000ULL, MappingDesc::INVALID, "invalid"},
+    {0x700000000000ULL, 0x800000000000ULL, MappingDesc::APP, "app-3"}};
+#define MEM_TO_SHADOW(mem) (((uptr)(mem)) ^ 0x500000000000ULL)
+#define SHADOW_TO_ORIGIN(mem) (((uptr)(mem)) + 0x100000000000ULL)
+#endif  // MSAN_LINUX_X86_64_OLD_MAPPING
 
 #else
 #error "Unsupported platform"
 #endif
 
 const uptr kMemoryLayoutSize = sizeof(kMemoryLayout) / sizeof(kMemoryLayout[0]);
 
 #define MEM_TO_ORIGIN(mem) (SHADOW_TO_ORIGIN(MEM_TO_SHADOW((mem))))

lib/msan/msan_allocator.cc

#if defined(__mips64)
   static const uptr kRegionSizeLog = 20;
   static const uptr kNumRegions = SANITIZER_MMAP_RANGE_SIZE >> kRegionSizeLog;
   typedef TwoLevelByteMap<(kNumRegions >> 12), 1 << 12> ByteMap;
   typedef CompactSizeClassMap SizeClassMap;
 
   typedef SizeClassAllocator32<0, SANITIZER_MMAP_RANGE_SIZE, sizeof(Metadata),
                                SizeClassMap, kRegionSizeLog, ByteMap,
                                MsanMapUnmapCallback> PrimaryAllocator;
-#elif defined(__x86_64__)
+
+#elif SANITIZER_FREEBSD && SANITIZER_WORDSIZE == 64
+  static const uptr kAllocatorSpace = 0x600000000000ULL;
+  static const uptr kAllocatorSize   = 0x80000000000;  // 8T.
+  static const uptr kMetadataSize  = sizeof(Metadata);
+  static const uptr kMaxAllowedMallocSize = 8UL << 30;
+
+  typedef SizeClassAllocator64<kAllocatorSpace, kAllocatorSize, kMetadataSize,
+                             DefaultSizeClassMap,
+                             MsanMapUnmapCallback> PrimaryAllocator;
+#elif SANITIZER_LINUX && SANITIZER_WORDSIZE == 64
+
+#ifdef MSAN_LINUX_X86_64_OLD_MAPPING
   static const uptr kAllocatorSpace = 0x600000000000ULL;
-  static const uptr kAllocatorSize   = 0x80000000000;  // 8T.
+#else
+  static const uptr kAllocatorSpace = 0x700000000000ULL;
+#endif
+  static const uptr kAllocatorSize = 0x80000000000; // 8T.
   static const uptr kMetadataSize  = sizeof(Metadata);
   static const uptr kMaxAllowedMallocSize = 8UL << 30;
 
   typedef SizeClassAllocator64<kAllocatorSpace, kAllocatorSize, kMetadataSize,
                                DefaultSizeClassMap,
                                MsanMapUnmapCallback> PrimaryAllocator;
+
 #elif defined(__powerpc64__)
   static const uptr kAllocatorSpace = 0x300000000000;
   static const uptr kAllocatorSize  = 0x020000000000;  // 2T
   static const uptr kMetadataSize  = sizeof(Metadata);
   static const uptr kMaxAllowedMallocSize = 2UL << 30;  // 2G
 
   typedef SizeClassAllocator64<kAllocatorSpace, kAllocatorSize, kMetadataSize,
                              DefaultSizeClassMap,

test/msan/mmap.cc

 #include <stdlib.h>
 #include "test.h"
 
 bool AddrIsApp(void *p) {
   uintptr_t addr = (uintptr_t)p;
 #if defined(__FreeBSD__) && defined(__x86_64__)
   return addr < 0x010000000000ULL || addr >= 0x600000000000ULL;
 #elif defined(__x86_64__)
-  return addr >= 0x600000000000ULL;
+  return (addr >= 0x000000000000ULL && addr < 0x010000000000ULL) ||
+         (addr >= 0x510000000000ULL && addr < 0x600000000000ULL) ||
+         (addr >= 0x700000000000ULL && addr < 0x800000000000ULL);
 #elif defined(__mips64)
   return addr >= 0x00e000000000ULL;
 #elif defined(__powerpc64__)
   return addr < 0x000100000000ULL || addr >= 0x300000000000ULL;
 #elif defined(__aarch64__)
   unsigned long vma = SystemVMA();
   if (vma == 39)
     return (addr >= 0x5500000000ULL && addr < 0x5600000000ULL) ||

test/msan/strlen_of_shadow.cc

 // RUN: %clangxx_msan -O0 %s -o %t && %run %t
 
 // Check that strlen() and similar intercepted functions can be called on shadow
 // memory.
 
 #include <assert.h>
 #include <stdint.h>
 #include <stdio.h>
 #include <string.h>
 #include <stdlib.h>
 #include "test.h"
 
 const char *mem_to_shadow(const char *p) {
 #if defined(__x86_64__)
-  return (char *)((uintptr_t)p & ~0x400000000000ULL);
+  return (char *)((uintptr_t)p ^ 0x500000000000ULL);
 #elif defined (__mips64)
   return (char *)((uintptr_t)p & ~0x4000000000ULL);
 #elif defined(__powerpc64__)
 #define LINEARIZE_MEM(mem) \
   (((uintptr_t)(mem) & ~0x200000000000ULL) ^ 0x100000000000ULL)
   return (char *)(LINEARIZE_MEM(p) + 0x080000000000ULL);
 #elif defined(__aarch64__)
   unsigned long vma = SystemVMA();

test/sanitizer_common/TestCases/Posix/decorate_proc_maps.cc

int main(void) {
   return (int)(size_t)res;
 }
 
 // CHECK-asan: rw-p {{.*}} [low shadow]
 // CHECK-asan: ---p {{.*}} [shadow gap]
 // CHECK-asan: rw-p {{.*}} [high shadow]
 
 // CHECK-msan: ---p {{.*}} [invalid]
-// CHECK-msan: rw-p {{.*}} [shadow]
-// CHECK-msan: ---p {{.*}} [origin]
+// CHECK-msan: rw-p {{.*}} [shadow{{.*}}]
+// CHECK-msan: ---p {{.*}} [origin{{.*}}]
 
 // CHECK-tsan: rw-p {{.*}} [shadow]
 // CHECK-tsan: rw-p {{.*}} [meta shadow]
 // CHECK-tsan: rw-p {{.*}} [trace 0]
 // CHECK-tsan: rw-p {{.*}} [trace header 0]
 // CHECK-tsan: rw-p {{.*}} [trace 1]
 // CHECK-tsan: rw-p {{.*}} [trace header 1]
 
 // Nothing interesting with standalone LSan.
 // CHECK-lsan: decorate_proc_maps