tsan: support pie binaries on newer kernels

[dvyukov]

Summary

4.1+ Linux kernels map pie binaries at 0x55:
https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=d1fd836dcf00d2028c700c7e44d2c23404062c90
Currently tsan does not support app memory at 0x55 (https://github.com/google/sanitizers/issues/503).
Older kernels also map pie binaries at 0x55 when ASLR is disables (most notably under gdb).

This change extends tsan mapping for linux/x86_64 to cover 0x554-0x568 app range and fixes both 4.1+ kernels and gdb.

This required to slightly shrink low and high app ranges and move heap. The mapping become even more non-linear, since now we xor lower bits. Now even a continuous app range maps to split, intermixed shadow ranges. This breaks ShadowToMemImpl as it assumes linear mapping at least within a continuous app range (however it turned out to be already broken at least on arm64/42-bit vma as uncovered by r281970). So also change ShadowToMemImpl to hopefully a more robust implementation that does not assume a linear mapping.

[dvyukov]

+Jakub,

If/when it lands, it would be useful to cherry-pick to gcc as it fixes a very real problem.

[jakubjelinek]

Well want to merge all the libsanitizer changes in the next month or two at most, but sure, this can be also desirable for release branch backporting eventually.

[kcc]

LGTM for this change, as unavoidable. (assuming you've tested it an various kernels)
But this is very sad.
Maybe you can file a bug against kernel to request some kind of feature that will protect us from changing the shadow in future?
E.g. if we can put something in the binary to tell the kernel to not touch (or to pre-allocate) certain ranges?

[dvyukov]

In D24769#547979, @kcc wrote:

Maybe you can file a bug against kernel to request some kind of feature that will protect us from changing the shadow in future?
E.g. if we can put something in the binary to tell the kernel to not touch (or to pre-allocate) certain ranges?

It seems that it will require extending ELF format, linkers, compiler drivers, dynamic loaders and kernel. Looks like a huge amount of work. Kernel bug tracker is for bugs, for features you just implement them and mail patches.

[dvyukov]

Submitted as 282152. Monitoring bots.

lib/tsan/rtl/tsan_platform.h

 
 namespace __tsan {
 
 #if !defined(SANITIZER_GO)
 
 #if defined(__x86_64__)
 /*
 C/C++ on linux/x86_64 and freebsd/x86_64
-0000 0000 1000 - 0100 0000 0000: main binary and/or MAP_32BIT mappings
-0100 0000 0000 - 0200 0000 0000: -
-0200 0000 0000 - 1000 0000 0000: shadow
+0000 0000 1000 - 0040 0000 0000: main binary and/or MAP_32BIT mappings (256GB)
+0040 0000 0000 - 0100 0000 0000: -
+0100 0000 0000 - 1000 0000 0000: shadow
 1000 0000 0000 - 3000 0000 0000: -
 3000 0000 0000 - 4000 0000 0000: metainfo (memory blocks and sync objects)
-4000 0000 0000 - 6000 0000 0000: -
[phone] - 5540 0000 0000: -
[phone] - 5680 0000 0000: pie binaries without ASLR or on 4.1+ kernels
[phone] - 6000 0000 0000: -
 6000 0000 0000 - 6200 0000 0000: traces
 6200 0000 0000 - 7d00 0000 0000: -
-7d00 0000 0000 - 7e00 0000 0000: heap
-7e00 0000 0000 - 7e80 0000 0000: -
-7e80 0000 0000 - 8000 0000 0000: modules and main thread stack
+7c40 0000 0000 - 7d40 0000 0000: heap
+7d40 0000 0000 - 7ec0 0000 0000: -
+7ec0 0000 0000 - 8000 0000 0000: modules and main thread stack
 */
 struct Mapping {
   static const uptr kMetaShadowBeg = 0x300000000000ull;
   static const uptr kMetaShadowEnd = 0x400000000000ull;
   static const uptr kTraceMemBeg   = 0x600000000000ull;
   static const uptr kTraceMemEnd   = 0x620000000000ull;
-  static const uptr kShadowBeg     = 0x020000000000ull;
+  static const uptr kShadowBeg     = 0x010000000000ull;
   static const uptr kShadowEnd     = 0x100000000000ull;
-  static const uptr kHeapMemBeg    = 0x7d0000000000ull;
-  static const uptr kHeapMemEnd    = 0x7e0000000000ull;
+  static const uptr kHeapMemBeg    = 0x7c4000000000ull;
+  static const uptr kHeapMemEnd    = 0x7d4000000000ull;
   static const uptr kLoAppMemBeg   = 0x000000001000ull;
-  static const uptr kLoAppMemEnd   = 0x010000000000ull;
-  static const uptr kHiAppMemBeg   = 0x7e8000000000ull;
+  static const uptr kLoAppMemEnd   = 0x004000000000ull;
+  static const uptr kMidAppMemBeg  = 0x554000000000ull;
+  static const uptr kMidAppMemEnd  = 0x568000000000ull;
+  static const uptr kMidShadowOff  = 0x540000000000ull;
+  static const uptr kHiAppMemBeg   = 0x7ec000000000ull;
   static const uptr kHiAppMemEnd   = 0x800000000000ull;
   static const uptr kAppMemMsk     = 0x7c0000000000ull;
-  static const uptr kAppMemXor     = 0x020000000000ull;
+  static const uptr kAppMemXor     = 0x028000000000ull;
   static const uptr kVdsoBeg       = 0xf000000000000000ull;
 };
+
+#define TSAN_MID_APP_RANGE 1
 #elif defined(__mips64)
 /*
 C/C++ on linux/mips64
 0100 0000 00 - 0200 0000 00: main binary
 0200 0000 00 - 1400 0000 00: -
 1400 0000 00 - 2400 0000 00: shadow
 2400 0000 00 - 3000 0000 00: -
 3000 0000 00 - 4000 0000 00: metainfo (memory blocks and sync objects)

 #endif
 }
 
 
 template<typename Mapping>
 uptr ShadowToMemImpl(uptr s) {
   DCHECK(IsShadowMem(s));
 #ifndef SANITIZER_GO
-  if (s >= MemToShadow(Mapping::kLoAppMemBeg)
-      && s <= MemToShadow(Mapping::kLoAppMemEnd - 1))
-    return (s / kShadowCnt) ^ Mapping::kAppMemXor;
+  // The shadow mapping is non-linear and we've lost some bits, so we don't have
+  // an easy way to restore the original app address. But the mapping is a
+  // bijection, so we try to restore the address as belonging to low/mid/high
+  // range consecutively and see if shadow->app->shadow mapping gives us the
+  // same address.
+  uptr p = (s / kShadowCnt) ^ Mapping::kAppMemXor;
+  if (MemToShadow(p) == s &&
+      p >= Mapping::kLoAppMemBeg && p < Mapping::kLoAppMemEnd)
+    return p;
 # ifdef TSAN_MID_APP_RANGE
-  if (s >= MemToShadow(Mapping::kMidAppMemBeg)
-      && s <= MemToShadow(Mapping::kMidAppMemEnd - 1))
-    return ((s / kShadowCnt) ^ Mapping::kAppMemXor) + Mapping::kMidShadowOff;
+  p = ((s / kShadowCnt) ^ Mapping::kAppMemXor) + Mapping::kMidShadowOff;
+  if (MemToShadow(p) == s &&
+      p >= Mapping::kMidAppMemBeg && p < Mapping::kMidAppMemEnd)
+    return p;
 # endif
-  else
-    return ((s / kShadowCnt) ^ Mapping::kAppMemXor) | Mapping::kAppMemMsk;
-#else
+#else  // #ifndef SANITIZER_GO
 # ifndef SANITIZER_WINDOWS
   return (s & ~Mapping::kShadowBeg) / kShadowCnt;
 # else
   return (s - Mapping::kShadowBeg) / kShadowCnt;
 # endif // SANITIZER_WINDOWS
 #endif
 }
 

test/tsan/pie_test.cc

 // Check if tsan work with PIE binaries.
 // RUN: %clang_tsan %s -pie -fpic -o %t && %run %t
 
-// Some kernels might map PIE segments outside the current segment
-// mapping defined for x86 [1].
-// [1] https://git.kernel.org/linus/d1fd836dcf00d2028c700c7e44d2c23404062c90
-
-// UNSUPPORTED: x86
-
 int main(void) {
   return 0;
 }