[sanitizer] Add delta compression stack depot

[vitalybuka]

Summary

Compress by factor 4x, takes about 10ms per 8 MiB block.

Depends on D114498.

[dvyukov]

compiler-rt/lib/sanitizer_common/sanitizer_stack_store.cpp

225–262

Can the packed data be larger than the unpacked data?

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_stack_store.cpp

225–262

Practically no. For the compression in this patch we need (at average) ptr difference with highest bits set to overflow leb128 to add additional byte.

CompressDelta has CHECK_LT(from, from_end) to protect agains that, but I can add graceful failure?

[vitalybuka]

rebase

[morehouse]

compiler-rt/lib/sanitizer_common/sanitizer_stack_store.cpp

200

For consistency.

228

230

247

For consistency with surrounding style.

250

[vitalybuka]

rebase

[vitalybuka]

unpack fallback

[hans]

This broke building the asan runtime on Windows. Can you revert if this can't be fixed quickly?

[hans]

In D114503#3164874, @hans wrote:

This broke building the asan runtime on Windows. Can you revert if this can't be fixed quickly?

Phrabricator ate my comment. The breakage is because MprotectReadOnly() isn't defined on Windows, see e.g. https://logs.chromium.org/logs/chromium/buildbucket/cr-buildbucket/8829028791639816401/+/u/package_clang/stdout

I've reverted in b1bc627e7e9965e6ec15e106ee4b2c21f6c36923 in the meantime.

[vitalybuka]

In D114503#3164929, @hans wrote:

In D114503#3164874, @hans wrote:

This broke building the asan runtime on Windows. Can you revert if this can't be fixed quickly?

Phrabricator ate my comment. The breakage is because MprotectReadOnly() isn't defined on Windows, see e.g. https://logs.chromium.org/logs/chromium/buildbucket/cr-buildbucket/8829028791639816401/+/u/package_clang/stdout

I've reverted in b1bc627e7e9965e6ec15e106ee4b2c21f6c36923 in the meantime.

Sorry, I just noticed this. Thanks for revert.

[vitalybuka]

rebase

compiler-rt/lib/sanitizer_common/sanitizer_stack_store.h

 class StackStore {
   static constexpr uptr kBlockSizeFrames = 0x100000;
   static constexpr uptr kBlockCount = 0x1000;
   static constexpr uptr kBlockSizeBytes = kBlockSizeFrames * sizeof(uptr);
 
  public:
   enum class Compression : u8 {
     None = 0,
-    Test,
+    Delta,
   };
 
   constexpr StackStore() = default;
 
   using Id = u32;  // Enough for 2^32 * sizeof(uptr) bytes of traces.
   static_assert(u64(kBlockCount) * kBlockSizeFrames == 1ull << (sizeof(Id) * 8),
                 "");
 

compiler-rt/lib/sanitizer_common/sanitizer_stack_store.cpp

 //===-- sanitizer_stack_store.cpp -------------------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "sanitizer_stack_store.h"
 
 #include "sanitizer_atomic.h"
 #include "sanitizer_common.h"
+#include "sanitizer_internal_defs.h"
+#include "sanitizer_leb128.h"
 #include "sanitizer_stacktrace.h"
 
 namespace __sanitizer {
 
 namespace {
 struct StackTraceHeader {
   static constexpr u32 kStackSizeBits = 8;
 

 
 uptr *StackStore::BlockInfo::GetOrCreate() {
   uptr *ptr = Get();
   if (LIKELY(ptr))
     return ptr;
   return Create();
 }
 
+static u8 *CompressDelta(const uptr *from, const uptr *from_end, u8 *to,
+                         u8 *to_end) {
+  uptr prev = 0;
+  for (; from < from_end; ++from) {
+    sptr diff = *from - prev;
+    to = EncodeSLEB128(diff, to, to_end);
+    prev += diff;
+  }
+  return to;
+}
+
+static uptr *UncompressDelta(const u8 *from, const u8 *from_end, uptr *to,
+                             uptr *to_end) {
+  uptr prev = 0;
+  for (; to < to_end; ++to) {
+    sptr diff;
+    from = DecodeSLEB128<sptr>(from, from_end, &diff);
+    prev += diff;
+    *to = prev;
+  }
+  return to;
+}
+
+namespace {
+struct PackedHeader {
+  uptr size;
+  StackStore::Compression type;
+  u8 data[];
+};
+}  // namespace
+
 uptr *StackStore::BlockInfo::GetOrUnpack() {
   SpinMutexLock l(&mtx_);
   switch (state) {
     case State::Storing:
       state = State::Unpacked;
       FALLTHROUGH;
     case State::Unpacked:
       return Get();
     case State::Packed:
       break;
   }
 
-  uptr *ptr = Get();
+  u8 *ptr = reinterpret_cast<u8 *>(Get());
   CHECK_NE(nullptr, ptr);
-  // Fake unpacking.
-  for (uptr i = 0; i < kBlockSizeFrames; ++i) ptr[i] = ~ptr[i];
+  const PackedHeader *header = reinterpret_cast<const PackedHeader *>(ptr);
+  CHECK_LE(header->size, kBlockSizeBytes);
+  CHECK_GE(header->size, sizeof(PackedHeader));
+
+  uptr packed_size_aligned = RoundUpTo(header->size, GetPageSizeCached());
+
+  uptr *unpacked = reinterpret_cast<uptr *>(
+      MmapNoReserveOrDie(kBlockSizeBytes, "StackStoreUnpack"));
+
+  uptr *unpacked_end;
+  switch (header->type) {
+    case Compression::Delta:
+      unpacked_end = UncompressDelta(header->data, ptr + header->size, unpacked,
+                                     unpacked + kBlockSizeFrames);
+      break;
+    default:
+      UNREACHABLE("Unexpected type");
+      break;
+  }
+
+  CHECK_EQ(kBlockSizeFrames, unpacked_end - unpacked);
+
+  MprotectReadOnly(reinterpret_cast<uptr>(unpacked), kBlockSizeBytes);
+  atomic_store(&data_, reinterpret_cast<uptr>(unpacked), memory_order_release);
+  UnmapOrDie(ptr, packed_size_aligned);
+
   state = State::Unpacked;
   return Get();
 }
 
 uptr StackStore::BlockInfo::Pack(Compression type) {
   if (type == Compression::None)
     return 0;
 
   SpinMutexLock l(&mtx_);
   switch (state) {
     case State::Unpacked:
     case State::Packed:
       return 0;
     case State::Storing:
       break;
   }
 
   uptr *ptr = Get();
   if (!ptr || !Stored(0))
     return 0;
 
-  // Fake packing.
-  for (uptr i = 0; i < kBlockSizeFrames; ++i) ptr[i] = ~ptr[i];
+  u8 *packed = reinterpret_cast<u8 *>(
+      MmapNoReserveOrDie(kBlockSizeBytes, "StackStorePack"));
+  PackedHeader *header = reinterpret_cast<PackedHeader *>(packed);
+  u8 *alloc_end = packed + kBlockSizeBytes;
+
+  u8 *packed_end = nullptr;
+  switch (type) {
+    case Compression::Delta:
+      packed_end =
+          CompressDelta(ptr, ptr + kBlockSizeFrames, header->data, alloc_end);
+      break;
+    default:
+      UNREACHABLE("Unexpected type");
+      break;
+  }
+
+  header->type = type;
+  header->size = packed_end - packed;
+
+  VPrintf(1, "Packed block of %zu KiB to %zu KiB\n", kBlockSizeBytes >> 10,
+          header->size >> 10);
+
+  if (kBlockSizeBytes - header->size < kBlockSizeBytes / 8) {
+    VPrintf(1, "Undo and keep block unpacked\n");
+    MprotectReadOnly(reinterpret_cast<uptr>(ptr), kBlockSizeBytes);
+    UnmapOrDie(packed, kBlockSizeBytes);
+    state = State::Unpacked;
+    return 0;
+  }
+
+  uptr packed_size_aligned = RoundUpTo(header->size, GetPageSizeCached());
+  UnmapOrDie(packed + packed_size_aligned,
+             kBlockSizeBytes - packed_size_aligned);
+  MprotectReadOnly(reinterpret_cast<uptr>(packed), packed_size_aligned);
+
+  atomic_store(&data_, reinterpret_cast<uptr>(packed), memory_order_release);
+  UnmapOrDie(ptr, kBlockSizeBytes);
+
   state = State::Packed;
-  return kBlockSizeBytes - kBlockSizeBytes / 10;
+  return kBlockSizeBytes - packed_size_aligned;
 }
 
 uptr StackStore::BlockInfo::Allocated() const {
   SpinMutexLock l(&mtx_);
   switch (state) {
-    case State::Packed:
-      return kBlockSizeBytes / 10;
+    case State::Packed: {
+      const PackedHeader *ptr = reinterpret_cast<const PackedHeader *>(Get());
+      CHECK_NE(nullptr, ptr);
+      return RoundUpTo(ptr->size, GetPageSizeCached());
+    }
     case State::Unpacked:
     case State::Storing:
       return kBlockSizeBytes;
   }
 }
 
 void StackStore::BlockInfo::TestOnlyUnmap() {
   if (uptr *ptr = Get())
-    UnmapOrDie(ptr, StackStore::kBlockSizeBytes);
+    UnmapOrDie(ptr, kBlockSizeBytes);
 }
 
 bool StackStore::BlockInfo::Stored(uptr n) {
   return n + atomic_fetch_add(&stored_, n, memory_order_release) ==
          kBlockSizeFrames;
 }
 
 bool StackStore::BlockInfo::IsPacked() const {
   SpinMutexLock l(&mtx_);
   return state == State::Packed;
 }
 
 }  // namespace __sanitizer

compiler-rt/lib/sanitizer_common/tests/sanitizer_stack_store_test.cpp

 
 struct StackStorePackTest : public StackStoreTest,
                             public ::testing::WithParamInterface<
                                 std::pair<StackStore::Compression, uptr>> {};
 
 INSTANTIATE_TEST_SUITE_P(
     PackUnpacks, StackStorePackTest,
     ::testing::ValuesIn({
-        StackStorePackTest::ParamType(StackStore::Compression::Test, 4),
+        StackStorePackTest::ParamType(StackStore::Compression::Delta,
+                                      FIRST_32_SECOND_64(2, 6)),
     }));
 
 TEST_P(StackStorePackTest, PackUnpack) {
   std::vector<StackStore::Id> ids;
   StackStore::Compression type = GetParam().first;
   uptr expected_ratio = GetParam().second;
   ForEachTrace([&](const StackTrace& s) {
     uptr pack = 0;
EXPECT_EQ(std::vector<uptr>(s.trace, s.trace + s.size),
               std::vector<uptr>(trace.trace, trace.trace + trace.size));
   });
   EXPECT_EQ(0u, CountPackedBlocks());
 
   EXPECT_EQ(0u, store_.Pack(type));
   EXPECT_EQ(0u, CountPackedBlocks());
 }
 
+TEST_P(StackStorePackTest, Failed) {
+  MurMur2Hash64Builder h(0);
+  StackStore::Compression type = GetParam().first;
+  std::vector<uptr> frames(200);
+  for (uptr i = 0; i < kBlockSizeFrames * 4 / frames.size(); ++i) {
+    for (uptr& f : frames) {
+      h.add(1);
+      // Make it difficult to pack.
+      f = h.get();
+    }
+    uptr pack = 0;
+    store_.Store(StackTrace(frames.data(), frames.size()), &pack);
+    if (pack)
+      EXPECT_EQ(0u, store_.Pack(type));
+  }
+
+  EXPECT_EQ(0u, CountPackedBlocks());
+}
+
 }  // namespace __sanitizer