[msan] Refactor memory layout specification and setup

[eugenis]

Summary

A flexible way of describing MSan memory layout details on various platforms. No significant functional changes, but the memory layout description that you get at verbosity=1 looks slightly different. This change includes stronger sanity checks than before.

The goal of this change is to allow more than 2 application memory ranges for https://code.google.com/p/memory-sanitizer/issues/detail?id=76.

I don't have an easy way to verify that I did not break freebsd or mips, though I tried not too. I'd appreciate if you verified that layout descriptions for those platforms are accurate.

[eugenis]

Added #pragma unroll to addr_is_type. LLVM stops unrolling this function when the loop size reaches ~ 8, and ends up with dozens of memory loads instead of 3 or 4 constant comparisons.

[mohit.bhakkad]

Layout descriptions are correct, no issues for mips.

[glider]

Looks mostly good.

lib/msan/CMakeLists.txt

18

Please add a comment listing the concrete pragmae you're suppressing.

lib/msan/msan.h

72

Please add a comment about the restrictions that led to these particular memory layouts on each platform (like it's done for FreeBSD)

90

Please add a comment describing the necessity of unrolling this loop.
You may want to add something GCC-specific under an #ifdef (e.g. attribute((optimize("unroll-loops"))) or "pragma GCC unroll-loops")
(see http://stackoverflow.com/questions/4071690/tell-gcc-to-specifically-unroll-a-loop)

lib/msan/msan_linux.cc

80

Maybe also assert that "end - start" is sane (e.g. not less than a page).
I can imagine accidental zero-sized ranges.

109

Can this loop be joined with the loop above?

[eugenis]

lib/msan/CMakeLists.txt

18

Now that I've added gcc pragmas, this is not needed.

lib/msan/msan.h

72

done for linux/x86_64

90

done

lib/msan/msan_linux.cc

80

done

109

I'd prefer not to. They do different things, even though they iterate over the same array.
I've even moved the first loop to a separate function now.

[glider]

LGTM with a nit.

lib/msan/msan.h

39–48

Please add a "TODO(someone): add description" or ask Mohit for the description.

[eugenis]

Thanks, r227192.

lib/msan/msan.h

39–48

Committed version include a very short comment in the mips section.

lib/msan/CMakeLists.txt

 include_directories(..)
 
 # Runtime library sources and build flags.
 set(MSAN_RTL_SOURCES
   msan.cc
   msan_allocator.cc
   msan_chained_origin_depot.cc
   msan_interceptors.cc
   msan_linux.cc
   msan_new_delete.cc
   msan_report.cc
   msan_thread.cc
   msan_poisoning.cc
   )
 
-set(MSAN_RTL_CFLAGS ${SANITIZER_COMMON_CFLAGS})
+set(MSAN_RTL_CFLAGS
+  ${SANITIZER_COMMON_CFLAGS}
+  -Wno-unknown-pragmas
+)
 append_no_rtti_flag(MSAN_RTL_CFLAGS)
 append_list_if(COMPILER_RT_HAS_FPIE_FLAG -fPIE MSAN_RTL_CFLAGS)
 # Prevent clang from generating libc calls.
 append_list_if(COMPILER_RT_HAS_FFREESTANDING_FLAG -ffreestanding MSAN_RTL_CFLAGS)
 
 set(MSAN_RUNTIME_LIBRARIES)
 
 # Static runtime library.

lib/msan/msan.h

 #include "sanitizer_common/sanitizer_stacktrace.h"
 #include "msan_interface_internal.h"
 #include "msan_flags.h"
 
 #ifndef MSAN_REPLACE_OPERATORS_NEW_AND_DELETE
 # define MSAN_REPLACE_OPERATORS_NEW_AND_DELETE 1
 #endif
 
-/*
-C/C++ on FreeBSD
-0000 0000 0000 - 00ff ffff ffff: Low memory: main binary, MAP_32BIT mappings and modules
-0100 0000 0000 - 0fff ffff ffff: Bad1
-1000 0000 0000 - 30ff ffff ffff: Shadow
-3100 0000 0000 - 37ff ffff ffff: Bad2
-3800 0000 0000 - 58ff ffff ffff: Origins
-5900 0000 0000 - 5fff ffff ffff: Bad3
-6000 0000 0000 - 7fff ffff ffff: High memory: heap, modules and main thread stack
-
-C/C++ on Linux/PIE
-0000 0000 0000 - 1fff ffff ffff: Bad1
-2000 0000 0000 - 3fff ffff ffff: Shadow
-4000 0000 0000 - 5fff ffff ffff: Origins
-6000 0000 0000 - 7fff ffff ffff: Main memory
-
-C/C++ on Mips
-0000 0000 0000 - 009f ffff ffff: Bad1
-00a0 0000 0000 - 00bf ffff ffff: Shadow
-00c0 0000 0000 - 00df ffff ffff: Origins
-00e0 0000 0000 - 00ff ffff ffff: Main memory
-*/
+struct MappingDesc {
+  uptr start;
+  uptr end;
+  enum Type {
+    INVALID, APP, SHADOW, ORIGIN
+  } type;
+  const char *name;
+};
+
 
 #if SANITIZER_LINUX && defined(__mips64)
-const uptr kLowMemBeg   = 0;
-const uptr kLowMemSize  = 0;
-const uptr kHighMemBeg  = 0x00e000000000;
-const uptr kHighMemSize = 0x002000000000;
-const uptr kShadowBeg   = 0x00a000000000;
-const uptr kShadowSize  = 0x002000000000;
-const uptr kOriginsBeg  = 0x00c000000000;
-# define MEM_TO_SHADOW(mem) (((uptr)(mem)) & ~0x4000000000ULL)
+
+const MappingDesc kMemoryLayout[] = {
+    {0x000000000000ULL, 0x00a000000000ULL, MappingDesc::INVALID, "invalid"},
+    {0x00a000000000ULL, 0x00c000000000ULL, MappingDesc::SHADOW, "shadow"},
+    {0x00c000000000ULL, 0x00e000000000ULL, MappingDesc::ORIGIN, "origin"},
+    {0x00e000000000ULL, 0x010000000000ULL, MappingDesc::APP, "app"}};
+
+#define MEM_TO_SHADOW(mem) (((uptr)(mem)) & ~0x4000000000ULL)
+#define SHADOW_TO_ORIGIN(shadow) (((uptr)(shadow)) + 0x002000000000)
+
 #elif SANITIZER_FREEBSD && SANITIZER_WORDSIZE == 64
-const uptr kLowMemBeg   = 0x000000000000;
-const uptr kLowMemSize  = 0x010000000000;
-const uptr kHighMemBeg  = 0x600000000000;
-const uptr kHighMemSize = 0x200000000000;
-const uptr kShadowBeg   = 0x100000000000;
-const uptr kShadowSize  = 0x210000000000;
-const uptr kOriginsBeg  = 0x380000000000;
+
+// Low memory: main binary, MAP_32BIT mappings and modules
+// High memory: heap, modules and main thread stack
+const MappingDesc kMemoryLayout[] = {
+    {0x000000000000ULL, 0x010000000000ULL, MappingDesc::APP, "low memory"},
+    {0x010000000000ULL, 0x100000000000ULL, MappingDesc::INVALID, "invalid"},
+    {0x100000000000ULL, 0x310000000000ULL, MappingDesc::SHADOW, "shadow"},
+    {0x310000000000ULL, 0x380000000000ULL, MappingDesc::INVALID, "invalid"},
+    {0x380000000000ULL, 0x590000000000ULL, MappingDesc::ORIGIN, "origin"},
+    {0x590000000000ULL, 0x600000000000ULL, MappingDesc::INVALID, "invalid"},
+    {0x600000000000ULL, 0x800000000000ULL, MappingDesc::APP, "high memory"}};
+
 // Maps low and high app ranges to contiguous space with zero base:
 //   Low:  0000 0000 0000 - 00ff ffff ffff  ->  2000 0000 0000 - 20ff ffff ffff
 //   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 LINEARIZE_MEM(mem) \
+#define MEM_TO_SHADOW(mem) (LINEARIZE_MEM((mem)) + 0x100000000000ULL)
+#define SHADOW_TO_ORIGIN(shadow) (((uptr)(shadow)) + 0x280000000000)
+
 #elif SANITIZER_LINUX && SANITIZER_WORDSIZE == 64
-const uptr kLowMemBeg   = 0;
-const uptr kLowMemSize  = 0;
-const uptr kHighMemBeg  = 0x600000000000;
-const uptr kHighMemSize = 0x200000000000;
-const uptr kShadowBeg   = 0x200000000000;
-const uptr kShadowSize  = 0x200000000000;
-const uptr kOriginsBeg  = 0x400000000000;
-# define MEM_TO_SHADOW(mem) (((uptr)(mem)) & ~0x400000000000ULL)
+
+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
 #error "Unsupported platform"
 #endif
 
-const uptr kBad1Beg  = kLowMemBeg + kLowMemSize;
-const uptr kBad1Size = kShadowBeg - kBad1Beg;
-
-const uptr kBad2Beg  = kShadowBeg + kShadowSize;
-const uptr kBad2Size = kOriginsBeg - kBad2Beg;
-
-const uptr kOriginsSize = kShadowSize;
-
-const uptr kBad3Beg  = kOriginsBeg + kOriginsSize;
-const uptr kBad3Size = kHighMemBeg - kBad3Beg;
-
-#define SHADOW_TO_ORIGIN(shadow) \
-  (((uptr)(shadow)) + (kOriginsBeg - kShadowBeg))
+const uptr kMemoryLayoutSize = sizeof(kMemoryLayout) / sizeof(kMemoryLayout[0]);
 
 #define MEM_TO_ORIGIN(mem) (SHADOW_TO_ORIGIN(MEM_TO_SHADOW((mem))))
 
-#define MEM_IS_APP(mem) \
-  ((kLowMemSize > 0 && (uptr)(mem) < kLowMemSize) || \
-    (uptr)(mem) >= kHighMemBeg)
-
-#define MEM_IS_SHADOW(mem) \
-  ((uptr)(mem) >= kShadowBeg && (uptr)(mem) < kShadowBeg + kShadowSize)
-
-#define MEM_IS_ORIGIN(mem) \
-  ((uptr)(mem) >= kOriginsBeg && (uptr)(mem) < kOriginsBeg + kOriginsSize)
+inline bool addr_is_type(uptr addr, MappingDesc::Type mapping_type) {
+#pragma unroll
+  for (unsigned i = 0; i < kMemoryLayoutSize; ++i)
+    if (kMemoryLayout[i].type == mapping_type &&
+        addr >= kMemoryLayout[i].start && addr < kMemoryLayout[i].end)
+      return true;
+  return false;
+}
+
+#define MEM_IS_APP(mem) addr_is_type((uptr)(mem), MappingDesc::APP)
+#define MEM_IS_SHADOW(mem) addr_is_type((uptr)(mem), MappingDesc::SHADOW)
+#define MEM_IS_ORIGIN(mem) addr_is_type((uptr)(mem), MappingDesc::ORIGIN)
 
 // These constants must be kept in sync with the ones in MemorySanitizer.cc.
 const int kMsanParamTlsSize = 800;
 const int kMsanRetvalTlsSize = 800;
 
 namespace __msan {
 extern int msan_inited;
 extern bool msan_init_is_running;

lib/msan/msan_linux.cc

if (size > 0) {
     }
   }
   return true;
 }
 
 bool InitShadow(bool map_shadow, bool init_origins) {
   // Let user know mapping parameters first.
   VPrintf(1, "__msan_init %p\n", &__msan_init);
-  ReportMapRange("Low Memory ", kLowMemBeg, kLowMemSize);
-  ReportMapRange("Bad1       ", kBad1Beg, kBad1Size);
-  ReportMapRange("Shadow     ", kShadowBeg, kShadowSize);
-  ReportMapRange("Bad2       ", kBad2Beg, kBad2Size);
-  ReportMapRange("Origins    ", kOriginsBeg, kOriginsSize);
-  ReportMapRange("Bad3       ", kBad3Beg, kBad3Size);
-  ReportMapRange("High Memory", kHighMemBeg, kHighMemSize);
-
-  // Check mapping sanity (the invariant).
-  CHECK_EQ(kLowMemBeg, 0);
-  CHECK_EQ(kBad1Beg, kLowMemBeg + kLowMemSize);
-  CHECK_EQ(kShadowBeg, kBad1Beg + kBad1Size);
-  CHECK_GT(kShadowSize, 0);
-  CHECK_GE(kShadowSize, kLowMemSize + kHighMemSize);
-  CHECK_EQ(kBad2Beg, kShadowBeg + kShadowSize);
-  CHECK_EQ(kOriginsBeg, kBad2Beg + kBad2Size);
-  CHECK_EQ(kOriginsSize, kShadowSize);
-  CHECK_EQ(kBad3Beg, kOriginsBeg + kOriginsSize);
-  CHECK_EQ(kHighMemBeg, kBad3Beg + kBad3Size);
-  CHECK_GT(kHighMemSize, 0);
-  CHECK_GE(kHighMemBeg + kHighMemSize, kHighMemBeg);  // Tests for no overflow.
-
-  if (kLowMemSize > 0) {
-    CHECK(MEM_IS_SHADOW(MEM_TO_SHADOW(kLowMemBeg)));
-    CHECK(MEM_IS_SHADOW(MEM_TO_SHADOW(kLowMemBeg + kLowMemSize - 1)));
-    CHECK(MEM_IS_ORIGIN(MEM_TO_ORIGIN(kLowMemBeg)));
-    CHECK(MEM_IS_ORIGIN(MEM_TO_ORIGIN(kLowMemBeg + kLowMemSize - 1)));
-  }
-  CHECK(MEM_IS_SHADOW(MEM_TO_SHADOW(kHighMemBeg)));
-  CHECK(MEM_IS_SHADOW(MEM_TO_SHADOW(kHighMemBeg + kHighMemSize - 1)));
-  CHECK(MEM_IS_ORIGIN(MEM_TO_ORIGIN(kHighMemBeg)));
-  CHECK(MEM_IS_ORIGIN(MEM_TO_ORIGIN(kHighMemBeg + kHighMemSize - 1)));
+  for (unsigned i = 0; i < kMemoryLayoutSize; ++i)
+    VPrintf(1, "%s: %zx - %zx\n", kMemoryLayout[i].name, kMemoryLayout[i].start,
+            kMemoryLayout[i].end - 1);
+
+  // Check mapping sanity.
+  uptr prev_end = 0;
+  for (unsigned i = 0; i < kMemoryLayoutSize; ++i) {
+    uptr start = kMemoryLayout[i].start;
+    uptr end = kMemoryLayout[i].end;
+    MappingDesc::Type type = kMemoryLayout[i].type;
+    CHECK_EQ(prev_end, start);
+    CHECK(addr_is_type(start, type));
+    CHECK(addr_is_type((start + end) / 2, type));
+    CHECK(addr_is_type(end - 1, type));
+    if (type == MappingDesc::APP) {
+      uptr addr = start;
+      CHECK(MEM_IS_SHADOW(MEM_TO_SHADOW(addr)));
+      CHECK(MEM_IS_ORIGIN(MEM_TO_ORIGIN(addr)));
+      CHECK_EQ(MEM_TO_ORIGIN(addr), SHADOW_TO_ORIGIN(MEM_TO_SHADOW(addr)));
+
+      addr = (start + end) / 2;
+      CHECK(MEM_IS_SHADOW(MEM_TO_SHADOW(addr)));
+      CHECK(MEM_IS_ORIGIN(MEM_TO_ORIGIN(addr)));
+      CHECK_EQ(MEM_TO_ORIGIN(addr), SHADOW_TO_ORIGIN(MEM_TO_SHADOW(addr)));
+
+      addr = end - 1;
+      CHECK(MEM_IS_SHADOW(MEM_TO_SHADOW(addr)));
+      CHECK(MEM_IS_ORIGIN(MEM_TO_ORIGIN(addr)));
+      CHECK_EQ(MEM_TO_ORIGIN(addr), SHADOW_TO_ORIGIN(MEM_TO_SHADOW(addr)));
+    }
+    prev_end = end;
+  }
 
   if (!MEM_IS_APP(&__msan_init)) {
     Printf("FATAL: Code %p is out of application range. Non-PIE build?\n",
            (uptr)&__msan_init);
     return false;
   }
 
-  if (!CheckMemoryRangeAvailability(kShadowBeg, kShadowSize) ||
-      (init_origins &&
-        !CheckMemoryRangeAvailability(kOriginsBeg, kOriginsSize)) ||
-      !CheckMemoryRangeAvailability(kBad1Beg, kBad1Size) ||
-      !CheckMemoryRangeAvailability(kBad2Beg, kBad2Size) ||
-      !CheckMemoryRangeAvailability(kBad3Beg, kBad3Size)) {
-    return false;
+  for (unsigned i = 0; i < kMemoryLayoutSize; ++i) {
+    uptr start = kMemoryLayout[i].start;
+    uptr end = kMemoryLayout[i].end;
+    uptr size= end - start;
+    MappingDesc::Type type = kMemoryLayout[i].type;
+    if ((map_shadow && type == MappingDesc::SHADOW) ||
+        (init_origins && type == MappingDesc::ORIGIN)) {
+      if (!CheckMemoryRangeAvailability(start, size)) return false;
+      if ((uptr)MmapFixedNoReserve(start, size) != start) return false;
+    } else if (type == MappingDesc::INVALID) {
+      if (!CheckMemoryRangeAvailability(start, size)) return false;
+      if (!ProtectMemoryRange(start, size)) return false;
     }
-
-  if (!ProtectMemoryRange(kBad1Beg, kBad1Size) ||
-      !ProtectMemoryRange(kBad2Beg, kBad2Size) ||
-      !ProtectMemoryRange(kBad3Beg, kBad3Size)) {
-    return false;
   }
 
-  if (map_shadow) {
-    void *shadow = MmapFixedNoReserve(kShadowBeg, kShadowSize);
-    if (shadow != (void*)kShadowBeg) return false;
-  }
-  if (init_origins) {
-    void *origins = MmapFixedNoReserve(kOriginsBeg, kOriginsSize);
-    if (origins != (void*)kOriginsBeg) return false;
-  }
   return true;
 }
 
 void MsanDie() {
   if (common_flags()->coverage)
     __sanitizer_cov_dump();
   if (death_callback)
     death_callback();