[tsan] Dynamically detect heap range for aarch64.

[yabinc]

Summary

After patch https://lkml.org/lkml/2015/12/21/340 is introduced in
linux kernel, the random gap between stack and heap is increased
from 128M to 36G on 39-bit aarch64. As it is hard to cover this
big range, I think we need to detect heap range dynamically.

[yabinc]

I only tested this on android with 39-bit aarch64 platform. Let me know if it breaks on other 39-bit aarch64 platforms, or if we have other ways to make things work.

[rengolin]

Adhemerval, CC'd, should know better, as he was the one implementing VMA options for AArch64.

[zatrazz]

Checking on kernel patch it looks like it is not specific to 39-bit VMA, but to all kernel configuration.
So instead of just setting it to 39-bit VMA I would rather make it default for aarch64 on all current
supported VMAs.

lib/tsan/rtl/tsan_platform_linux.cc

274

llvm-lit is accusing "Line ends in whitespace. Consider deleting these extra spaces." for lini 272.

[yabinc]

Add support for 42-bit aarch64.

[yabinc]

Done. I didn't add 42-bit version because I don't have a machine to test it.

[rengolin]

lib/tsan/rtl/tsan_platform.h

669

This sounds odd... I thought we had moved TSAN to dynamic VMA detection, too...

[dvyukov]

The mapping become more and more messy. But I don't see any simple solution, so I guess I am OK with this.
Are there any objections from ARM people?

We also have problems on x86, modules have moved to 0x5555 without ASRL.
If we agree to have 1 memory access in mem->shadow translation, we could split address space into, say, 256 parts and have arbitrary mapping between these parts. Something long the lines of:

uptr mapping[256];

uptr MemToShadow(uptr x) {

return (x << 2) ^ mapping[x >> kAddressShift];

}

This would allow a platform to have up to 50 regions with user memory arbitrary mapped onto 50*4 shadow regions.
Just thinking aloud.

lib/tsan/rtl/tsan_platform.h

610

It should be faster to use [kHeapMemBeg, kHeapMemBeg + kHeapMemSize) instead of [kHeapMemBeg, kHeapMemEnd). Because kHeapMemSize is a const.

[yabinc]

use kHeapMemBeg + kHeapMemSize for efficiency.

[yabinc]

I think using uptr mapping[256]; is a better solution to remove current complex logic.

[dvyukov]

I think using uptr mapping[256]; is a better solution to remove current complex logic.

Just in case, don't start working on it yet :)
That was just a quick idea, we need at least kcc@ input and benchmark numbers to decide (because currently x86 does not do any memory accesses during translation).

[kcc]

mapping[256];

I have not touched tsan for a while, but if my understanding is still correct an extra load on fast path may cost us 10% of CPU.
That's too much.
Don't do it unless you really have to, and get perf numbers before sending such a CL.

This change also introduces more instructions on the main path .
From reading the patch it seems to be AArch64-specific, so I am fine with that,
but I'd like to have the new functions like MemToShadowImplWithDynamicHeap to be under ifdef AArch64,
so that they can not be possibly used for x86

lib/tsan/rtl/tsan_platform.h

609

Here and below, can we use if (SANITIZER_GO) instead of #ifdef?

[rengolin]

In D16689#346952, @kcc wrote:

This change also introduces more instructions on the main path .
From reading the patch it seems to be AArch64-specific, so I am fine with that,

I'm not. :)

AArch64 already suffers from bloat from the VMA selection, adding more main path run time slow down is not the way to go, especially when that involved division and multiplication.

Also, these sources are outdated, the AArch64 part is not like that any more for a good number of months.

cheers,
--renato

[yabinc]

profiling results on N5X(aarch64) as below:
mini_bench_local
without tsan: 2.50s
tsan before: 131s
tsan after change: 138s

mini_bench_shared
without tsan: 3.60s
tsan before: 126s
tsan after change: 130s

start_many_threads
without tsan: 0.05s
tsan before: 0.39s
tsan after change: 0.47s

vts_many_threads
without tsan: 1.64s
tsan before: 165s
tsan after change: 163s

According to the results, the performance lose when accessing
memory may be about 5%, which seems acceptable.

[yabinc]

Sorry for not updating this so long, I was struggling with other stuff.
I don't understand "these sources are outdated, the AArch64 part is not like that any more for a good number of months." When I downloaded the latest linux kernel, the code of arch/arm64/mm/mmap.c is not changed:

unsigned long arch_mmap_rnd(void)
{
unsigned long rnd;

#ifdef CONFIG_COMPAT
if (test_thread_flag(TIF_32BIT))

		rnd = (unsigned long)get_random_int() & ((1 << mmap_rnd_compat_bits) - 1);

else
#endif

		rnd = (unsigned long)get_random_int() & ((1 <<** mmap_rnd_bits**) - 1);

return rnd << PAGE_SHIFT;
}

And I think at least we should support it on android. The division and multiplication are in current code like MemToShadowImpl as well, and they should be compiled into shift instructions.

lib/tsan/rtl/tsan_platform.h

609

I use #if !defined(SANITIZER_GO) instead of #if !(SANITIZER_GO), because other places make compilation decision based on whether SANITIZER_GO is defined.

[rengolin]

In D16689#359285, @yabinc wrote:

profiling results on N5X(aarch64) as below:
mini_bench_local
without tsan: 2.50s
tsan before: 131s
tsan after change: 138s

Ouch!

According to the results, the performance lose when accessing
memory may be about 5%, which seems acceptable.

5% of 5200% is 262% of the initial value!!

I personally don't think that 52x slow down on TSAN is acceptable as it is. This may be AArch64 specific, as I heard from Kostya 2 years ago that it was around 10x for x86_64, but it's definitely not usable.

Thread analysis depends on timing issues too much to make any analysis that runs 52x slower either bogus or very noisy.

This patch is adding a huge list of new instructions to the hot path, and I don't think this will help in any way.

As it happened before multiple times, I think we need to sit down and discuss this issue with kernel and sanitizer engineers. There will be a Linaro Connect in two weeks, and I'll bring that up with the kernel folks this topic, as well as try to reduce the already almost useless slow down.

cheers,
--renato

[dvyukov]

There will be a Linaro Connect in two weeks, and I'll bring that up with the kernel folks this topic, as well as try to reduce the already almost useless slow down.

It would be great if kernel provided a "sanitizer-friendly" mapping.

FWIW, some time ago we had support for so called "COMPAT" mapping for x86. In that mode kernel mapped modules around 0x2a0000000000. The shadow mapping for that mode was not a bijection, instead it was a injection. Several user regions mapped onto the same shadow, but during runtime only one of the user regions was occupied so no clashes happened. This allowed us to support huge user memory range (like in this case) and map it onto smaller shadow. The problem was with the reverse mapping, though (e.g. when we print racy address in report). You can find that code in history.

[yabinc]

As recommended by dvyukov, I find that we can use personality(ADDR_NO_RANDOMIZE) to disable randomized virtual address space. The patch is uploaded at http://reviews.llvm.org/D18003

[yabinc]

This patch is uploaded because I misunderstood kHeapMem as mapped area. And the correct fix has been submitted in http://reviews.llvm.org/D18003.

lib/tsan/rtl/tsan_platform.h

struct Mapping {
   static const uptr kVdsoBeg       = 0xfffff00000ull;
 };
 #elif defined(__aarch64__)
 // AArch64 supports multiple VMA which leads to multiple address transformation
 // functions.  To support these multiple VMAS transformations and mappings TSAN
 // runtime for AArch64 uses an external memory read (vmaSize) to select which
 // mapping to use.  Although slower, it make a same instrumented binary run on
 // multiple kernels.
+// According to https://lkml.org/lkml/2015/12/21/340, the mmap random gap
+// between heap and stack is determined at runtime, and can be too huge
+// to create shadow memory for it. So we need to find heap space at runtime.
 
 /*
 C/C++ on linux/aarch64 (39-bit VMA)
+
 0000 0010 00 - 0100 0000 00: main binary
 0100 0000 00 - 0800 0000 00: -
 0800 0000 00 - 2000 0000 00: shadow memory
 2000 0000 00 - 3100 0000 00: -
 3100 0000 00 - 3400 0000 00: metainfo
 3400 0000 00 - 5500 0000 00: -
 5500 0000 00 - 5600 0000 00: main binary (PIE)
 5600 0000 00 - 6000 0000 00: -
 6000 0000 00 - 6200 0000 00: traces
-6200 0000 00 - 7d00 0000 00: -
-7c00 0000 00 - 7d00 0000 00: heap
-7d00 0000 00 - 7fff ffff ff: modules and main thread stack
[phone] - xx00 0000 00: -
+xx00 0000 00 - yy00 0000 00: heap
+yy00 0000 00 - 7f00 0000 00: - memory random gap
+7f00 0000 00 - 7fff ffff ff: main thread stack
 */
 struct Mapping39 {
   static const uptr kLoAppMemBeg   = 0x0000001000ull;
   static const uptr kLoAppMemEnd   = 0x0100000000ull;
   static const uptr kShadowBeg     = 0x0800000000ull;
   static const uptr kShadowEnd     = 0x2000000000ull;
   static const uptr kMetaShadowBeg = 0x3100000000ull;
   static const uptr kMetaShadowEnd = 0x3400000000ull;
   static const uptr kMidAppMemBeg  = 0x5500000000ull;
   static const uptr kMidAppMemEnd  = 0x5600000000ull;
   static const uptr kMidShadowOff  = 0x5000000000ull;
   static const uptr kTraceMemBeg   = 0x6000000000ull;
   static const uptr kTraceMemEnd   = 0x6200000000ull;
-  static const uptr kHeapMemBeg    = 0x7c00000000ull;
-  static const uptr kHeapMemEnd    = 0x7d00000000ull;
-  static const uptr kHiAppMemBeg   = 0x7e00000000ull;
+  static       uptr kHeapMemBeg;
+  static       uptr kHeapMemEnd;
+  static const uptr kHeapMemSize   = 0x0100000000ull;
+  static const uptr kHeapShadowBeg = 0x1800000000ull;
+  static const uptr kHeapMetaBeg   = 0x3200000000ull;
+  static const uptr kHiAppMemBeg   = 0x7f00000000ull;
   static const uptr kHiAppMemEnd   = 0x7fffffffffull;
   static const uptr kAppMemMsk     = 0x7800000000ull;
   static const uptr kAppMemXor     = 0x0200000000ull;
   static const uptr kVdsoBeg       = 0x7f00000000ull;
 };
 
 /*
 C/C++ on linux/aarch64 (42-bit VMA)
 00000 0010 00 - 01000 0000 00: main binary
 01000 0000 00 - 10000 0000 00: -
 10000 0000 00 - 20000 0000 00: shadow memory
 20000 0000 00 - 26000 0000 00: -
 26000 0000 00 - 28000 0000 00: metainfo
 28000 0000 00 - 2aa00 0000 00: -
 2aa00 0000 00 - 2ab00 0000 00: main binary (PIE)
 2ab00 0000 00 - 36200 0000 00: -
 36200 0000 00 - 36240 0000 00: traces
-36240 0000 00 - 3e000 0000 00: -
-3e000 0000 00 - 3f000 0000 00: heap
[phone] - xxxx0 0000 00: -
+xxxx0 0000 00 - yyyy0 0000 00: heap
+yyyy0 0000 00 - 3f000 0000 00: - memory random gap
 3f000 0000 00 - 3ffff ffff ff: modules and main thread stack
 */
 struct Mapping42 {
   static const uptr kLoAppMemBeg   = 0x00000001000ull;
   static const uptr kLoAppMemEnd   = 0x01000000000ull;
   static const uptr kShadowBeg     = 0x10000000000ull;
   static const uptr kShadowEnd     = 0x20000000000ull;
   static const uptr kMetaShadowBeg = 0x26000000000ull;
   static const uptr kMetaShadowEnd = 0x28000000000ull;
   static const uptr kMidAppMemBeg  = 0x2aa00000000ull;
   static const uptr kMidAppMemEnd  = 0x2ab00000000ull;
   static const uptr kMidShadowOff  = 0x28000000000ull;
   static const uptr kTraceMemBeg   = 0x36200000000ull;
   static const uptr kTraceMemEnd   = 0x36400000000ull;
-  static const uptr kHeapMemBeg    = 0x3e000000000ull;
-  static const uptr kHeapMemEnd    = 0x3f000000000ull;
+  static       uptr kHeapMemBeg;
+  static       uptr kHeapMemEnd;
+  static const uptr kHeapMemSize   = 0x01000000000ull;
+  static const uptr kHeapShadowBeg = 0x14000000000ull;
+  static const uptr kHeapMetaBeg   = 0x26800000000ull;
   static const uptr kHiAppMemBeg   = 0x3f000000000ull;
   static const uptr kHiAppMemEnd   = 0x3ffffffffffull;
   static const uptr kAppMemMsk     = 0x3c000000000ull;
   static const uptr kAppMemXor     = 0x04000000000ull;
-  static const uptr kVdsoBeg       = 0x37f00000000ull;
+  static const uptr kVdsoBeg       = 0x3f000000000ull;
 };
 
 // Indicates the runtime will define the memory regions at runtime.
 #define TSAN_RUNTIME_VMA 1
 // Indicates that mapping defines a mid range memory segment.
 #define TSAN_MID_APP_RANGE 1
 #elif defined(__powerpc64__)
 // PPC64 supports multiple VMA which leads to multiple address transformation

 #ifndef SANITIZER_GO
   return (((x) & ~(Mapping::kAppMemMsk | (kShadowCell - 1)))
       ^ Mapping::kAppMemXor) * kShadowCnt;
 #else
   return ((x & ~(kShadowCell - 1)) * kShadowCnt) | Mapping::kShadowBeg;
 #endif
 }
 
+template<typename Mapping>
+uptr MemToShadowImplWithDynamicHeap(uptr x) {
+  DCHECK(IsAppMem(x));
+#ifndef SANITIZER_GO
+  if (x >= Mapping::kHeapMemBeg &&
+      x < Mapping::kHeapMemBeg + Mapping::kHeapMemSize)
+    return ((x - Mapping::kHeapMemBeg) & ~(kShadowCell - 1)) * kShadowCnt
+        + Mapping::kHeapShadowBeg;
+#endif
+  return MemToShadowImpl<Mapping>(x);
+}
+
 ALWAYS_INLINE
 uptr MemToShadow(uptr x) {
 #ifdef __aarch64__
   if (vmaSize == 39)
-    return MemToShadowImpl<Mapping39>(x);
+    return MemToShadowImplWithDynamicHeap<Mapping39>(x);
   else
-    return MemToShadowImpl<Mapping42>(x);
+    return MemToShadowImplWithDynamicHeap<Mapping42>(x);
   DCHECK(0);
 #elif defined(__powerpc64__)
   if (vmaSize == 44)
     return MemToShadowImpl<Mapping44>(x);
   else
     return MemToShadowImpl<Mapping46>(x);
   DCHECK(0);
 #else
return (u32*)(((((x) & ~(Mapping::kAppMemMsk | (kMetaShadowCell - 1)))
         ^ Mapping::kAppMemXor) / kMetaShadowCell * kMetaShadowSize)
           | Mapping::kMetaShadowBeg);
 #else
   return (u32*)(((x & ~(kMetaShadowCell - 1)) / \
       kMetaShadowCell * kMetaShadowSize) | Mapping::kMetaShadowBeg);
 #endif
 }
 
+template<typename Mapping>
+u32 *MemToMetaImplWithDynamicHeap(uptr x) {
+  DCHECK(IsAppMem(x));
+#ifndef SANITIZER_GO
+  if (x >= Mapping::kHeapMemBeg &&
+      x < Mapping::kHeapMemBeg + Mapping::kHeapMemSize)
+    return (u32*)(((x - Mapping::kHeapMemBeg) & ~(kMetaShadowCell - 1))
+        / kMetaShadowCell * kMetaShadowSize + Mapping::kHeapMetaBeg);
+#endif
+  return MemToMetaImpl<Mapping>(x);
+}
+
 ALWAYS_INLINE
 u32 *MemToMeta(uptr x) {
 #ifdef __aarch64__
   if (vmaSize == 39)
-    return MemToMetaImpl<Mapping39>(x);
+    return MemToMetaImplWithDynamicHeap<Mapping39>(x);
   else
-    return MemToMetaImpl<Mapping42>(x);
+    return MemToMetaImplWithDynamicHeap<Mapping42>(x);
   DCHECK(0);
 #elif defined(__powerpc64__)
   if (vmaSize == 44)
     return MemToMetaImpl<Mapping44>(x);
   else
     return MemToMetaImpl<Mapping46>(x);
   DCHECK(0);
 #else
# ifndef SANITIZER_WINDOWS
   return (s & ~Mapping::kShadowBeg) / kShadowCnt;
 # else
   // FIXME(dvyukov): this is most likely wrong as the mapping is not bijection.
   return (s - Mapping::kShadowBeg) / kShadowCnt;
 # endif // SANITIZER_WINDOWS
 #endif
 }
 
+template<typename Mapping>
+uptr ShadowToMemImplWithDynamicHeap(uptr s) {
+  DCHECK(IsShadowMem(s));
+#ifndef SANITIZER_GO
+  if (s >= MemToShadow(Mapping::kHeapMemBeg)
+      && s <= MemToShadow(Mapping::kHeapMemEnd - 1))
+    return (s - Mapping::kHeapShadowBeg) / kShadowCnt + Mapping::kHeapMemBeg;
+#endif
+  return ShadowToMemImpl<Mapping>(s);
+}
+
 ALWAYS_INLINE
 uptr ShadowToMem(uptr s) {
 #ifdef __aarch64__
   if (vmaSize == 39)
-    return ShadowToMemImpl<Mapping39>(s);
+    return ShadowToMemImplWithDynamicHeap<Mapping39>(s);
   else
-    return ShadowToMemImpl<Mapping42>(s);
+    return ShadowToMemImplWithDynamicHeap<Mapping42>(s);
   DCHECK(0);
 #elif defined(__powerpc64__)
   if (vmaSize == 44)
     return ShadowToMemImpl<Mapping44>(s);
   else
     return ShadowToMemImpl<Mapping46>(s);
   DCHECK(0);
 #else

lib/tsan/rtl/tsan_platform_linux.cc

#else
   }
 #endif
   DPrintf("guessed data_start=%p data_end=%p\n",  g_data_start, g_data_end);
   CHECK_LT(g_data_start, g_data_end);
   CHECK_GE((uptr)&g_data_start, g_data_start);
   CHECK_LT((uptr)&g_data_start, g_data_end);
 }
 
+#ifdef __aarch64__
+uptr Mapping39::kHeapMemBeg = 0;
+uptr Mapping39::kHeapMemEnd = 0;
+uptr Mapping42::kHeapMemBeg = 0;
+uptr Mapping42::kHeapMemEnd = 0;
+#endif
+
 #endif  // #ifndef SANITIZER_GO
 
 void InitializePlatformEarly() {
 #ifdef TSAN_RUNTIME_VMA
   vmaSize =
     (MostSignificantSetBitIndex(GET_CURRENT_FRAME()) + 1);
 #if defined(__aarch64__)
   if (vmaSize != 39 && vmaSize != 42) {
     Printf("FATAL: ThreadSanitizer: unsupported VMA range\n");
     Printf("FATAL: Found %d - Supported 39 and 42\n", vmaSize);
     Die();
   }
+  MemoryMappingLayout proc_maps(true);
+  uptr heap_end = 0;
+  uptr start, end, prot;
+  while (proc_maps.Next(&start, &end, 0, 0, 0, &prot)) {
+    // Omit stack
+    if (start <= (uptr)&heap_end && (uptr)&heap_end < end)
+      continue;
+    if (end > heap_end)
+      heap_end = end;
+  }
+  if (vmaSize == 39) {
+    if (heap_end > Mapping39::kHiAppMemBeg)
+      heap_end = Mapping39::kHiAppMemBeg;
+    Mapping39::kHeapMemEnd = heap_end;
+    Mapping39::kHeapMemBeg = heap_end - Mapping39::kHeapMemSize;
+    DPrintf("Mapping39::kHeapMem = 0x%llx - 0x%llx\n", Mapping39::kHeapMemBeg,
+            Mapping39::kHeapMemEnd);
+  } else {
+    if (heap_end > Mapping42::kHiAppMemBeg)
+      heap_end = Mapping42::kHiAppMemBeg;
+    Mapping42::kHeapMemEnd = heap_end;
+    Mapping42::kHeapMemBeg = heap_end - Mapping42::kHeapMemSize;
+    DPrintf("Mapping42::kHeapMem = 0x%llx - 0x%llx\n", Mapping42::kHeapMemBeg,
+            Mapping42::kHeapMemEnd);
+  }
 #elif defined(__powerpc64__)
   if (vmaSize != 44 && vmaSize != 46) {
     Printf("FATAL: ThreadSanitizer: unsupported VMA range\n");
     Printf("FATAL: Found %d - Supported 44 and 46\n", vmaSize);
     Die();
   }
 #endif
 #endif