[sanitizer] Hook up LZW into stack store

[vitalybuka]

Summary

Depends on D114503.

[vitalybuka]

fixup

[vitalybuka]

updateupdate

[morehouse]

LGTM

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,
     Delta,
+    LZW,
   };
 
   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_lzw.h"
+#include "sanitizer_placement_new.h"
 #include "sanitizer_stacktrace.h"
 
 namespace __sanitizer {
 
 namespace {
 struct StackTraceHeader {
   static constexpr u32 kStackSizeBits = 8;
 
static uptr *UncompressDelta(const u8 *from, const u8 *from_end, uptr *to,
                              uptr *to_end) {
   SLeb128Decoder decoder(from, from_end);
   SLeb128Decoder end(from_end, from_end);
   for (; decoder != end; ++to, ++decoder) *to = *decoder;
   CHECK_EQ(to, to_end);
   return to;
 }
 
+static u8 *CompressLzw(const uptr *from, const uptr *from_end, u8 *to,
+                       u8 *to_end) {
+  SLeb128Encoder encoder(to, to_end);
+  encoder = LzwEncode<uptr>(from, from_end, encoder);
+  return encoder.base();
+}
+
+static uptr *UncompressLzw(const u8 *from, const u8 *from_end, uptr *to,
+                           uptr *to_end) {
+  SLeb128Decoder decoder(from, from_end);
+  SLeb128Decoder end(from_end, from_end);
+  to = LzwDecode<uptr>(decoder, end, to);
+  CHECK_EQ(to, to_end);
+  return to;
+}
+
 namespace {
 struct PackedHeader {
   uptr size;
   StackStore::Compression type;
   u8 data[];
 };
 }  // namespace
 
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;
+    case Compression::LZW:
+      unpacked_end = UncompressLzw(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);
uptr StackStore::BlockInfo::Pack(Compression type) {
   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;
+    case Compression::LZW:
+      packed_end =
+          CompressLzw(ptr, ptr + kBlockSizeFrames, header->data, alloc_end);
+      break;
     default:
       UNREACHABLE("Unexpected type");
       break;
   }
 
   header->type = type;
   header->size = packed_end - packed;
 

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::Delta,
                                       FIRST_32_SECOND_64(2, 6)),
+        StackStorePackTest::ParamType(StackStore::Compression::LZW,
+                                      FIRST_32_SECOND_64(60, 130)),
     }));
 
 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;

compiler-rt/test/sanitizer_common/TestCases/compress_stack_depot.cpp

 // RUN: %clangxx %s -fsanitize-memory-track-origins=1 -o %t
 // RUN: %env_tool_opts="compress_stack_depot=0:malloc_context_size=128:verbosity=1" %run %t 2>&1 | FileCheck %s --implicit-check-not="StackDepot released"
 // RUN: %env_tool_opts="compress_stack_depot=1:malloc_context_size=128:verbosity=1" %run %t 2>&1 | FileCheck %s --check-prefixes=COMPRESS
+// RUN: %env_tool_opts="compress_stack_depot=2:malloc_context_size=128:verbosity=1" %run %t 2>&1 | FileCheck %s --check-prefixes=COMPRESS
 
 // Ubsan does not store stacks.
 // UNSUPPORTED: ubsan
 
 // FIXME: Fails for unknown reason.
 // UNSUPPORTED: s390x
 
 #include <memory>