[hwasan] Record and display stack history in stack-based reports.

Summary:
Display a list of recent stack frames (not a stack trace!) when
tag-mismatch is detected on a stack address.

The implementation uses alignment tricks to get both the address of
the history buffer, and the base address of the shadow with a single
8-byte load. See the comment in hwasan_thread_list.h for more
details.

Developed in collaboration with Kostya Serebryany.

Reviewers: kcc

Subscribers: srhines, kubamracek, mgorny, hiraditya, jfb, llvm-commits

Differential Revision: https://reviews.llvm.org/D52249

llvm-svn: 342921

2 files changed, 102 insertions, 1 deletions

diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_ring_buffer.h b/compiler-rt/lib/sanitizer_common/sanitizer_ring_buffer.h
index c4649c2be9f..d15f27fd4a8 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_ring_buffer.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_ring_buffer.h
@@ -72,12 +72,91 @@ class RingBuffer {
   // L: last_, always points to the last data element.
   // N: next_, initially equals to last_, is decremented on every push,
   //    wraps around if it's less or equal than its own address.
-
   T *last_;
   T *next_;
   T data_[1];  // flexible array.
 };
 
+// A ring buffer with externally provided storage that encodes its state in 8
+// bytes. Has significant constraints on size and alignment of storage.
+// See a comment in hwasan/hwasan_thread_list.h for the motivation behind this.
+#if SANITIZER_WORDSIZE == 64
+template <class T>
+class CompactRingBuffer {
+  // Top byte of long_ stores the buffer size in pages.
+  // Lower bytes store the address of the next buffer element.
+  static constexpr int kPageSizeBits = 12;
+  static constexpr int kSizeShift = 56;
+  static constexpr uptr kNextMask = (1ULL << kSizeShift) - 1;
+
+  uptr GetStorageSize() const { return (long_ >> kSizeShift) << kPageSizeBits; }
+
+  void Init(void *storage, uptr size) {
+    CHECK_EQ(sizeof(CompactRingBuffer<T>), sizeof(void *));
+    CHECK(IsPowerOfTwo(size));
+    CHECK_GE(size, 1 << kPageSizeBits);
+    CHECK_LE(size, 128 << kPageSizeBits);
+    CHECK_EQ(size % 4096, 0);
+    CHECK_EQ(size % sizeof(T), 0);
+    CHECK_EQ((uptr)storage % (size * 2), 0);
+    long_ = (uptr)storage | ((size >> kPageSizeBits) << kSizeShift);
+  }
+
+  void SetNext(const T *next) {
+    long_ = (long_ & ~kNextMask) | (uptr)next;
+  }
+
+ public:
+  CompactRingBuffer(void *storage, uptr size) {
+    Init(storage, size);
+  }
+
+  // A copy constructor of sorts.
+  CompactRingBuffer(const CompactRingBuffer &other, void *storage) {
+    uptr size = other.GetStorageSize();
+    internal_memcpy(storage, other.StartOfStorage(), size);
+    Init(storage, size);
+    uptr Idx = other.Next() - (const T *)other.StartOfStorage();
+    SetNext((const T *)storage + Idx);
+  }
+
+  T *Next() const { return (T *)(long_ & kNextMask); }
+
+  void *StartOfStorage() const {
+    return (void *)((uptr)Next() & ~(GetStorageSize() - 1));
+  }
+
+  void *EndOfStorage() const {
+    return (void *)((uptr)StartOfStorage() + GetStorageSize());
+  }
+
+  uptr size() const { return GetStorageSize() / sizeof(T); }
+
+  void push(T t) {
+    T *next = Next();
+    *next = t;
+    next++;
+    next = (T *)((uptr)next & ~GetStorageSize());
+    SetNext(next);
+  }
+
+  T operator[](uptr Idx) const {
+    CHECK_LT(Idx, size());
+    const T *Begin = (const T *)StartOfStorage();
+    sptr StorageIdx = Next() - Begin;
+    StorageIdx -= (sptr)(Idx + 1);
+    if (StorageIdx < 0)
+      StorageIdx += size();
+    return Begin[StorageIdx];
+  }
+
+ public:
+  ~CompactRingBuffer() {}
+  CompactRingBuffer(const CompactRingBuffer &) = delete;
+
+  uptr long_;
+};
+#endif
 }  // namespace __sanitizer
 
 #endif  // SANITIZER_RING_BUFFER_H
diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_ring_buffer_test.cc b/compiler-rt/lib/sanitizer_common/tests/sanitizer_ring_buffer_test.cc
index a9286ce6d3e..80aa57c5290 100644
--- a/compiler-rt/lib/sanitizer_common/tests/sanitizer_ring_buffer_test.cc
+++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_ring_buffer_test.cc
@@ -66,6 +66,7 @@ template <class T> void TestRB() {
 #undef EXPECT_RING_BUFFER
 }
 
+#if SANITIZER_WORDSIZE == 64
 TEST(RingBuffer, int64) {
   TestRB<int64_t>();
 }
@@ -74,4 +75,25 @@ TEST(RingBuffer, LargeStruct) {
   TestRB<LargeStruct>();
 }
 
+template<typename T>
+CompactRingBuffer<T> *AllocCompactRingBuffer(size_t count) {
+  size_t sz = sizeof(T) * count;
+  EXPECT_EQ(0ULL, sz % 4096);
+  void *p = MmapAlignedOrDieOnFatalError(sz, sz * 2, "CompactRingBuffer");
+  return new CompactRingBuffer<T>(p, sz);
+}
+
+TEST(CompactRingBuffer, int64) {
+  const size_t page_sizes[] = {1, 2, 4, 128};
+
+  for (size_t pages : page_sizes) {
+    size_t count = 4096 * pages / sizeof(int64_t);
+    auto R = AllocCompactRingBuffer<int64_t>(count);
+    int64_t top = count * 3 + 13;
+    for (int64_t i = 0; i < top; ++i) R->push(i);
+    for (int64_t i = 0; i < (int64_t)count; ++i)
+      EXPECT_EQ(top - i - 1, (*R)[i]);
+  }
+}
+#endif
 }  // namespace __sanitizer