tsan: add kBrokenAliasedMetas condition and test

[thurston]

Summary

This fills in a gap in the tsan_shadow_test coverage:
it is possible that the meta regions are aliased
(e.g., the heap meta region overlaps the high app meta
region). Indeed, the Aarch64_39 mapping has been
silently broken in this way for quite some time.

This CL checks whether the individual meta regions
(for low/mid/high/heap) overlap. Note that
(!kBrokenAliasedMetas && !kBrokenLinearity) implies
that MemToMeta is invertible; we cannot directly
test MetaToMem because that function does not exist.

[vitalybuka]

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

170

I don't see these constants uses anywhere other than tests?

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

18

134

this code still uses Google style
region_a
num_regions
etc.

211

237–245

[thurston]

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

170

Yes, they are just annotations for documenting known issues with the mappings, to prevent tsan_shadow_test from failing.

Ideally the mappings would be corrected, such that they do not need any kBroken annotations. (I plan to fix the Aarch64_39 mapping in a follow-up CL.)

[thurston]

Fix style per Vitaly's comments

[thurston]

Change printf format string to avoid typecast warning

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

enum {
   // Mapping app memory and back does not produce the same address,
   // this can lead to wrong addresses in reports and potentially
   // other bad consequences.
   kBrokenReverseMapping = 1 << 1,
   // Mapping is non-linear for linear user range.
   // This is bad and can lead to unpredictable memory corruptions, etc
   // because range access functions assume linearity.
   kBrokenLinearity = 1 << 2,
+  // Meta for an app region overlaps with the meta of another app region.
+  // This is determined by recomputing the individual meta regions for
+  // each app region.
+  //
+  // N.B. There is no "kBrokenReverseMetaMapping" constant because there
+  // is no MetaToMem function. However, note that (!kBrokenLinearity
+  // && !kBrokenAliasedMetas) implies that MemToMeta is invertible.
+  kBrokenAliasedMetas = 1 << 3,
 };
 
 /*
 C/C++ on linux/x86_64 and freebsd/x86_64
 0000 0000 1000 - 0080 0000 0000: main binary and/or MAP_32BIT mappings (512GB)
 0040 0000 0000 - 0100 0000 0000: -
 0100 0000 0000 - 1000 0000 0000: shadow
 1000 0000 0000 - 3000 0000 0000: -

 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 - 7c00 0000 00: -
 7c00 0000 00 - 7d00 0000 00: heap
 7d00 0000 00 - 7fff ffff ff: modules and main thread stack
 */
 struct MappingAarch64_39 {
+  static const uptr kBroken = kBrokenAliasedMetas;
   static const uptr kLoAppMemBeg   = 0x0000001000ull;
   static const uptr kLoAppMemEnd   = 0x0100000000ull;
   static const uptr kShadowBeg = 0x0400000000ull;
   static const uptr kShadowEnd = 0x1000000000ull;
   static const uptr kMetaShadowBeg = 0x3100000000ull;
   static const uptr kMetaShadowEnd = 0x3400000000ull;
   static const uptr kMidAppMemBeg  = 0x5500000000ull;
   static const uptr kMidAppMemEnd = 0x5600000000ull;

 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 - 3e000 0000 00: -
 3e000 0000 00 - 3f000 0000 00: heap
 3f000 0000 00 - 3ffff ffff ff: modules and main thread stack
 */
 struct MappingAarch64_42 {
-  static const uptr kBroken = kBrokenReverseMapping;
+  static const uptr kBroken = kBrokenReverseMapping | kBrokenAliasedMetas;
   static const uptr kLoAppMemBeg   = 0x00000001000ull;
   static const uptr kLoAppMemEnd   = 0x01000000000ull;
   static const uptr kShadowBeg = 0x08000000000ull;
   static const uptr kShadowEnd = 0x10000000000ull;
   static const uptr kMetaShadowBeg = 0x26000000000ull;
   static const uptr kMetaShadowEnd = 0x28000000000ull;
   static const uptr kMidAppMemBeg  = 0x2aa00000000ull;
   static const uptr kMidAppMemEnd = 0x2ab00000000ull;

 0b00 0000 0000 - 0b00 0000 0000: -
 0b00 0000 0000 - 0d00 0000 0000: metainfo (memory blocks and sync objects)
 0d00 0000 0000 - 0f00 0000 0000: -
 0f00 0000 0000 - 0f50 0000 0000: heap
 0f50 0000 0000 - 0f60 0000 0000: -
 0f60 0000 0000 - 1000 0000 0000: modules and main thread stack
 */
 struct MappingPPC64_44 {
-  static const uptr kBroken =
-      kBrokenMapping | kBrokenReverseMapping | kBrokenLinearity;
+  static const uptr kBroken = kBrokenMapping | kBrokenReverseMapping |
+                              kBrokenLinearity | kBrokenAliasedMetas;
   static const uptr kMetaShadowBeg = 0x0b0000000000ull;
   static const uptr kMetaShadowEnd = 0x0d0000000000ull;
   static const uptr kShadowBeg     = 0x000100000000ull;
   static const uptr kShadowEnd     = 0x0b0000000000ull;
   static const uptr kLoAppMemBeg   = 0x000000000100ull;
   static const uptr kLoAppMemEnd   = 0x000100000000ull;
   static const uptr kHeapMemBeg    = 0x0f0000000000ull;
   static const uptr kHeapMemEnd    = 0x0f5000000000ull;
   static const uptr kHiAppMemBeg   = 0x0f6000000000ull;
   static const uptr kHiAppMemEnd   = 0x100000000000ull; // 44 bits
+
   static const uptr kShadowMsk = 0x0f0000000000ull;
   static const uptr kShadowXor = 0x002100000000ull;
   static const uptr kShadowAdd = 0x000000000000ull;
   static const uptr kVdsoBeg       = 0x3c0000000000000ull;
   static const uptr kMidAppMemBeg = 0;
   static const uptr kMidAppMemEnd = 0;
 };
 

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

 //
 //===----------------------------------------------------------------------===//
 #include "tsan_platform.h"
 #include "tsan_rtl.h"
 #include "gtest/gtest.h"
 
 namespace __tsan {
 
+struct Region {
+  uptr start;
+  uptr end;
+};
+
 void CheckShadow(const Shadow *s, Sid sid, Epoch epoch, uptr addr, uptr size,
                  AccessType typ) {
   uptr addr1 = 0;
   uptr size1 = 0;
   AccessType typ1 = 0;
   s->GetAccess(&addr1, &size1, &typ1);
   CHECK_EQ(s->sid(), sid);
   CHECK_EQ(s->epoch(), epoch);
bool broken(...) {
   return false;
 }
 
 template <typename Mapping>
 bool broken(uptr what, typename Has<Mapping::kBroken>::Result = false) {
   return Mapping::kBroken & what;
 }
 
+static int CompareRegion(const void *region_a, const void *region_b) {
+  uptr start_a = ((struct Region *)region_a)->start;
+  uptr start_b = ((struct Region *)region_b)->start;
+
+  if (start_a < start_b) {
+    return -1;
+  } else if (start_a > start_b) {
+    return 1;
+  } else {
+    return 0;
+  }
+}
+
+template <typename Mapping>
+static void AddMetaRegion(struct Region *shadows, int *num_regions, uptr start,
+                          uptr end) {
+  // If the app region is not empty, add its meta to the array.
+  if (start != end) {
+    shadows[*num_regions].start = (uptr)MemToMetaImpl::Apply<Mapping>(start);
+    shadows[*num_regions].end = (uptr)MemToMetaImpl::Apply<Mapping>(end - 1);
+    *num_regions = (*num_regions) + 1;
+  }
+}
+
 struct MappingTest {
   template <typename Mapping>
   static void Apply() {
     // Easy (but ugly) way to print the mapping name.
     Printf("%s\n", __PRETTY_FUNCTION__);
     TestRegion<Mapping>(Mapping::kLoAppMemBeg, Mapping::kLoAppMemEnd);
     TestRegion<Mapping>(Mapping::kMidAppMemBeg, Mapping::kMidAppMemEnd);
     TestRegion<Mapping>(Mapping::kHiAppMemBeg, Mapping::kHiAppMemEnd);
     TestRegion<Mapping>(Mapping::kHeapMemBeg, Mapping::kHeapMemEnd);
+
+    TestDisjointMetas<Mapping>();
+
+    // Not tested: the ordering of regions (low app vs. shadow vs. mid app
+    // etc.). That is enforced at runtime by CheckAndProtect.
   }
 
   template <typename Mapping>
   static void TestRegion(uptr beg, uptr end) {
     if (beg == end)
       return;
     Printf("checking region [0x%zx-0x%zx)\n", beg, end);
     uptr prev = 0;
for (uptr p0 = beg; p0 <= end; p0 += (end - beg) / 256) {
           u32 *const prev_m = MemToMetaImpl::Apply<Mapping>(prev);
           CHECK_EQ(s - prev_s, (p - prev) * kShadowMultiplier);
           CHECK_EQ(m - prev_m, (p - prev) / kMetaShadowCell);
         }
         prev = p;
       }
     }
   }
+
+  template <typename Mapping>
+  static void TestDisjointMetas() {
+    // Checks that the meta for each app region does not overlap with
+    // the meta for other app regions. For example, the meta for a high
+    // app pointer shouldn't be aliased to the meta of a mid app pointer.
+    // Notice that this is important even though there does not exist a
+    // MetaToMem function.
+    // (If a MetaToMem function did exist, we could simply
+    // check in the TestRegion function that it inverts MemToMeta.)
+    //
+    // We don't try to be clever by allowing the non-PIE (low app)
+    // and PIE (mid and high app) meta regions to overlap.
+    struct Region metas[4];
+    int num_regions = 0;
+    AddMetaRegion<Mapping>(metas, &num_regions, Mapping::kLoAppMemBeg,
+                           Mapping::kLoAppMemEnd);
+    AddMetaRegion<Mapping>(metas, &num_regions, Mapping::kMidAppMemBeg,
+                           Mapping::kMidAppMemEnd);
+    AddMetaRegion<Mapping>(metas, &num_regions, Mapping::kHiAppMemBeg,
+                           Mapping::kHiAppMemEnd);
+    AddMetaRegion<Mapping>(metas, &num_regions, Mapping::kHeapMemBeg,
+                           Mapping::kHeapMemEnd);
+
+    // It is not required that the low app shadow is below the mid app
+    // shadow etc., hence we sort the shadows.
+    qsort(metas, num_regions, sizeof(struct Region), CompareRegion);
+
+    for (int i = 0; i < num_regions; i++)
+      Printf("[0x%lu, 0x%lu]\n", metas[i].start, metas[i].end);
+
+    if (!broken<Mapping>(kBrokenAliasedMetas))
+      for (int i = 1; i < num_regions; i++)
+        CHECK(metas[i - 1].end <= metas[i].start);
+  }
 };
 
 TEST(Shadow, AllMappings) { ForEachMapping<MappingTest>(); }
 
 }  // namespace __tsan