tsan: add notion of compressed addresses

[dvyukov]

Summary

New tsan runtime will need to compress addresses/PCs to fewer bits.
Add CompressAddr/RestoreAddr functions that compress/restore
addresses to 44 bits.

Depends on D107744.

[melver]

compiler-rt/lib/tsan/rtl/tsan_platform.h

906

Just an idea: does it in any way make sense to make the compressed addr a stronger type, i.e.:

class CompressedAddr {
 public:
  explicit constexpr CompressedAddr(uptr addr) ...

  template <typename Mapping>
  uptr Restore() ....
};

Might make misuse harder.

I may have not paid attention how you pass around the compressed addr, so if that's infeasible, that's fine.

[dvyukov]

compiler-rt/lib/tsan/rtl/tsan_platform.h

906

The only way compressed addresses will be used is within u64 bitfields, so even if use a strong enum class, we will need to cast to u64 immediately and back...
And it does not make sense to use compressed address in other contexts, because if it still takes whole u64, there is no point in compressing.

[dvyukov]

changed SelectMapping to use template Arg and rebased

[wolfgangp]

compiler-rt/lib/tsan/rtl/tsan_platform.h

935

This is causing a build error in our bot (maybe the formatting should be %zx?)

In file included from ../rtl/tsan_rtl.h:44:0,
                 from tsan_go.cpp:13:
../rtl/tsan_platform.h: In instantiation of 'static __tsan::RestoreAddrImpl::Result __tsan::RestoreAddrImpl::Apply(__sanitizer::uptr) [with Mapping = __tsan::MappingGo48; __tsan::RestoreAddrImpl::Result = long unsigned int; __sanitizer::uptr = long unsigned int]':
../rtl/tsan_platform.h:648:43:   required from 'auto __tsan::SelectMapping(Arg) [with Func = __tsan::RestoreAddrImpl; Arg = long unsigned int]'
../rtl/tsan_platform.h:934:45:   required from here
../rtl/tsan_platform.h:926:11: error: format '%p' expects argument of type 'void*', but argument 2 has type '__sanitizer::uptr {aka long unsigned int}' [-Werror=format=]
     Printf("ThreadSanitizer: failed to restore address %p\n", addr);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cc1plus: error: unrecognized command line option '-Wno-unknown-warning-option' [-Werror]
cc1plus: all warnings being treated as errors

compiler-rt/lib/tsan/rtl/tsan_defs.h

 
 // That many user bytes are mapped onto a single meta shadow cell.
 // Must be less or equal to minimal memory allocator alignment.
 const uptr kMetaShadowCell = 8;
 
 // Size of a single meta shadow value (u32).
 const uptr kMetaShadowSize = 4;
 
+// All addresses and PCs are assumed to be compressable to that many bits.
+const uptr kCompressedAddrBits = 44;
+
 #if TSAN_NO_HISTORY
 const bool kCollectHistory = false;
 #else
 const bool kCollectHistory = true;
 #endif
 
 // The following "build consistency" machinery ensures that all source files
 // are built in the same configuration. Inconsistent builds lead to

compiler-rt/lib/tsan/rtl/tsan_platform.h

struct ShadowToMemImpl {
   }
 };
 
 ALWAYS_INLINE
 uptr ShadowToMem(RawShadow *s) {
   return SelectMapping<ShadowToMemImpl>(reinterpret_cast<uptr>(s));
 }
 
+// Compresses addr to kCompressedAddrBits stored in least significant bits.
+ALWAYS_INLINE uptr CompressAddr(uptr addr) {
+  return addr & ((1ull << kCompressedAddrBits) - 1);
+}
+
+struct RestoreAddrImpl {
+  typedef uptr Result;
+  template <typename Mapping>
+  static Result Apply(uptr addr) {
+    // To restore the address we go over all app memory ranges and check if top
+    // 3 bits of the compressed addr match that of the app range. If yes, we
+    // assume that the compressed address come from that range and restore the
+    // missing top bits to match the app range address.
+    static constexpr uptr ranges[] = {
+        Mapping::kLoAppMemBeg,  Mapping::kLoAppMemEnd, Mapping::kMidAppMemBeg,
+        Mapping::kMidAppMemEnd, Mapping::kHiAppMemBeg, Mapping::kHiAppMemEnd,
+        Mapping::kHeapMemBeg,   Mapping::kHeapMemEnd,
+    };
+    const uptr indicator = 0x0e0000000000ull;
+    const uptr ind_lsb = 1ull << LeastSignificantSetBitIndex(indicator);
+    for (uptr i = 0; i < ARRAY_SIZE(ranges); i += 2) {
+      uptr beg = ranges[i];
+      uptr end = ranges[i + 1];
+      if (beg == end)
+        continue;
+      for (uptr p = beg; p < end; p = RoundDown(p + ind_lsb, ind_lsb)) {
+        if ((addr & indicator) == (p & indicator))
+          return addr | (p & ~(ind_lsb - 1));
+      }
+    }
+    Printf("ThreadSanitizer: failed to restore address %p\n", addr);
+    Die();
+  }
+};
+
+// Restores compressed addr from kCompressedAddrBits to full representation.
+// This is called only during reporting and is not performance-critical.
+inline uptr RestoreAddr(uptr addr) {
+  return SelectMapping<RestoreAddrImpl>(addr);
+}
+
 // The additional page is to catch shadow stack overflow as paging fault.
 // Windows wants 64K alignment for mmaps.
 const uptr kTotalTraceSize = (kTraceSize * sizeof(Event) + sizeof(Trace)
     + (64 << 10) + (64 << 10) - 1) & ~((64 << 10) - 1);
 
 struct GetThreadTraceImpl {
   typedef uptr Result;
   template <typename Mapping>

compiler-rt/lib/tsan/tests/unit/tsan_shadow_test.cpp

 //===-- tsan_shadow_test.cpp ----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file is a part of ThreadSanitizer (TSan), a race detector.
 //
 //===----------------------------------------------------------------------===//
 #include "tsan_platform.h"
 #include "tsan_rtl.h"
 #include "gtest/gtest.h"
 
 namespace __tsan {
 
 TEST(Shadow, FastState) {
   Shadow s(FastState(11, 22));
   EXPECT_EQ(s.tid(), (u64)11);
for (uptr p0 = beg; p0 <= end; p0 += (end - beg) / 256) {
         const uptr s = MemToShadowImpl::Apply<Mapping>(p);
         u32 *const m = MemToMetaImpl::Apply<Mapping>(p);
         const uptr r = ShadowToMemImpl::Apply<Mapping>(s);
         Printf("  addr=%p: shadow=%p meta=%p reverse=%p\n", p, s, m, r);
         CHECK(IsAppMemImpl::Apply<Mapping>(p));
         if (!broken<Mapping>(kBrokenMapping))
           CHECK(IsShadowMemImpl::Apply<Mapping>(s));
         CHECK(IsMetaMemImpl::Apply<Mapping>(reinterpret_cast<uptr>(m)));
+        CHECK_EQ(p, RestoreAddrImpl::Apply<Mapping>(CompressAddr(p)));
         if (!broken<Mapping>(kBrokenReverseMapping))
           CHECK_EQ(p, r);
         if (prev && !broken<Mapping>(kBrokenLinearity)) {
           // Ensure that shadow and meta mappings are linear within a single
           // user range. Lots of code that processes memory ranges assumes it.
           const uptr prev_s = MemToShadowImpl::Apply<Mapping>(prev);
           u32 *const prev_m = MemToMetaImpl::Apply<Mapping>(prev);
           CHECK_EQ(s - prev_s, (p - prev) * kShadowMultiplier);