vendor/compiler-rt/compiler-rt-trunk-r375505vendor/compiler-rt

10 files changed, 350 insertions, 69 deletions

diff --git a/lib/gwp_asan/guarded_pool_allocator.cpp b/lib/gwp_asan/guarded_pool_allocator.cpp
index 7e3628eba6ff..ef497336025f 100644
--- a/lib/gwp_asan/guarded_pool_allocator.cpp
+++ b/lib/gwp_asan/guarded_pool_allocator.cpp
@@ -13,7 +13,7 @@
 // RHEL creates the PRIu64 format macro (for printing uint64_t's) only when this
 // macro is defined before including <inttypes.h>.
 #ifndef __STDC_FORMAT_MACROS
-  #define __STDC_FORMAT_MACROS 1
+#define __STDC_FORMAT_MACROS 1
 #endif
 
 #include <assert.h>
@@ -44,11 +44,12 @@ private:
   bool &Bool;
 };
 
-void defaultPrintStackTrace(uintptr_t *Trace, options::Printf_t Printf) {
-  if (Trace[0] == 0)
+void defaultPrintStackTrace(uintptr_t *Trace, size_t TraceLength,
+                            options::Printf_t Printf) {
+  if (TraceLength == 0)
     Printf("  <unknown (does your allocator support backtracing?)>\n");
 
-  for (size_t i = 0; Trace[i] != 0; ++i) {
+  for (size_t i = 0; i < TraceLength; ++i) {
     Printf("  #%zu 0x%zx in <unknown>\n", i, Trace[i]);
   }
   Printf("\n");
@@ -68,12 +69,18 @@ void GuardedPoolAllocator::AllocationMetadata::RecordAllocation(
   // TODO(hctim): Ask the caller to provide the thread ID, so we don't waste
   // other thread's time getting the thread ID under lock.
   AllocationTrace.ThreadID = getThreadID();
+  AllocationTrace.TraceSize = 0;
+  DeallocationTrace.TraceSize = 0;
   DeallocationTrace.ThreadID = kInvalidThreadID;
-  if (Backtrace)
-    Backtrace(AllocationTrace.Trace, kMaximumStackFrames);
-  else
-    AllocationTrace.Trace[0] = 0;
-  DeallocationTrace.Trace[0] = 0;
+
+  if (Backtrace) {
+    uintptr_t UncompressedBuffer[kMaxTraceLengthToCollect];
+    size_t BacktraceLength =
+        Backtrace(UncompressedBuffer, kMaxTraceLengthToCollect);
+    AllocationTrace.TraceSize = compression::pack(
+        UncompressedBuffer, BacktraceLength, AllocationTrace.CompressedTrace,
+        kStackFrameStorageBytes);
+  }
 }
 
 void GuardedPoolAllocator::AllocationMetadata::RecordDeallocation(
@@ -81,11 +88,16 @@ void GuardedPoolAllocator::AllocationMetadata::RecordDeallocation(
   IsDeallocated = true;
   // Ensure that the unwinder is not called if the recursive flag is set,
   // otherwise non-reentrant unwinders may deadlock.
+  DeallocationTrace.TraceSize = 0;
   if (Backtrace && !ThreadLocals.RecursiveGuard) {
     ScopedBoolean B(ThreadLocals.RecursiveGuard);
-    Backtrace(DeallocationTrace.Trace, kMaximumStackFrames);
-  } else {
-    DeallocationTrace.Trace[0] = 0;
+
+    uintptr_t UncompressedBuffer[kMaxTraceLengthToCollect];
+    size_t BacktraceLength =
+        Backtrace(UncompressedBuffer, kMaxTraceLengthToCollect);
+    DeallocationTrace.TraceSize = compression::pack(
+        UncompressedBuffer, BacktraceLength, DeallocationTrace.CompressedTrace,
+        kStackFrameStorageBytes);
   }
   DeallocationTrace.ThreadID = getThreadID();
 }
@@ -161,7 +173,7 @@ void GuardedPoolAllocator::init(const options::Options &Opts) {
 
   // Ensure that signal handlers are installed as late as possible, as the class
   // is not thread-safe until init() is finished, and thus a SIGSEGV may cause a
-  // race to members if recieved during init().
+  // race to members if received during init().
   if (Opts.InstallSignalHandlers)
     installSignalHandlers();
 }
@@ -373,7 +385,7 @@ void printErrorType(Error E, uintptr_t AccessPtr, AllocationMetadata *Meta,
   case Error::UNKNOWN:
     ErrorString = "GWP-ASan couldn't automatically determine the source of "
                   "the memory error. It was likely caused by a wild memory "
-                  "access into the GWP-ASan pool. The error occured";
+                  "access into the GWP-ASan pool. The error occurred";
     break;
   case Error::USE_AFTER_FREE:
     ErrorString = "Use after free";
@@ -442,7 +454,13 @@ void printAllocDeallocTraces(uintptr_t AccessPtr, AllocationMetadata *Meta,
       Printf("0x%zx was deallocated by thread %zu here:\n", AccessPtr,
              Meta->DeallocationTrace.ThreadID);
 
-    PrintBacktrace(Meta->DeallocationTrace.Trace, Printf);
+    uintptr_t UncompressedTrace[AllocationMetadata::kMaxTraceLengthToCollect];
+    size_t UncompressedLength = compression::unpack(
+        Meta->DeallocationTrace.CompressedTrace,
+        Meta->DeallocationTrace.TraceSize, UncompressedTrace,
+        AllocationMetadata::kMaxTraceLengthToCollect);
+
+    PrintBacktrace(UncompressedTrace, UncompressedLength, Printf);
   }
 
   if (Meta->AllocationTrace.ThreadID == GuardedPoolAllocator::kInvalidThreadID)
@@ -451,7 +469,12 @@ void printAllocDeallocTraces(uintptr_t AccessPtr, AllocationMetadata *Meta,
     Printf("0x%zx was allocated by thread %zu here:\n", Meta->Addr,
            Meta->AllocationTrace.ThreadID);
 
-  PrintBacktrace(Meta->AllocationTrace.Trace, Printf);
+  uintptr_t UncompressedTrace[AllocationMetadata::kMaxTraceLengthToCollect];
+  size_t UncompressedLength = compression::unpack(
+      Meta->AllocationTrace.CompressedTrace, Meta->AllocationTrace.TraceSize,
+      UncompressedTrace, AllocationMetadata::kMaxTraceLengthToCollect);
+
+  PrintBacktrace(UncompressedTrace, UncompressedLength, Printf);
 }
 
 struct ScopedEndOfReportDecorator {
@@ -491,11 +514,11 @@ void GuardedPoolAllocator::reportErrorInternal(uintptr_t AccessPtr, Error E) {
   uint64_t ThreadID = getThreadID();
   printErrorType(E, AccessPtr, Meta, Printf, ThreadID);
   if (Backtrace) {
-    static constexpr unsigned kMaximumStackFramesForCrashTrace = 128;
+    static constexpr unsigned kMaximumStackFramesForCrashTrace = 512;
     uintptr_t Trace[kMaximumStackFramesForCrashTrace];
-    Backtrace(Trace, kMaximumStackFramesForCrashTrace);
+    size_t TraceLength = Backtrace(Trace, kMaximumStackFramesForCrashTrace);
 
-    PrintBacktrace(Trace, Printf);
+    PrintBacktrace(Trace, TraceLength, Printf);
   } else {
     Printf("  <unknown (does your allocator support backtracing?)>\n\n");
   }
diff --git a/lib/gwp_asan/guarded_pool_allocator.h b/lib/gwp_asan/guarded_pool_allocator.h
index 28a41110faed..57ad61e9cf4f 100644
--- a/lib/gwp_asan/guarded_pool_allocator.h
+++ b/lib/gwp_asan/guarded_pool_allocator.h
@@ -13,6 +13,7 @@
 #include "gwp_asan/mutex.h"
 #include "gwp_asan/options.h"
 #include "gwp_asan/random.h"
+#include "gwp_asan/stack_trace_compressor.h"
 
 #include <stddef.h>
 #include <stdint.h>
@@ -39,9 +40,15 @@ public:
   };
 
   struct AllocationMetadata {
-    // Maximum number of stack trace frames to collect for allocations + frees.
-    // TODO(hctim): Implement stack frame compression, a-la Chromium.
-    static constexpr size_t kMaximumStackFrames = 64;
+    // The number of bytes used to store a compressed stack frame. On 64-bit
+    // platforms, assuming a compression ratio of 50%, this should allow us to
+    // store ~64 frames per trace.
+    static constexpr size_t kStackFrameStorageBytes = 256;
+
+    // Maximum number of stack frames to collect on allocation/deallocation. The
+    // actual number of collected frames may be less than this as the stack
+    // frames are compressed into a fixed memory range.
+    static constexpr size_t kMaxTraceLengthToCollect = 128;
 
     // Records the given allocation metadata into this struct.
     void RecordAllocation(uintptr_t Addr, size_t Size,
@@ -51,11 +58,13 @@ public:
     void RecordDeallocation(options::Backtrace_t Backtrace);
 
     struct CallSiteInfo {
-      // The backtrace to the allocation/deallocation. If the first value is
-      // zero, we did not collect a trace.
-      uintptr_t Trace[kMaximumStackFrames] = {};
+      // The compressed backtrace to the allocation/deallocation.
+      uint8_t CompressedTrace[kStackFrameStorageBytes];
       // The thread ID for this trace, or kInvalidThreadID if not available.
       uint64_t ThreadID = kInvalidThreadID;
+      // The size of the compressed trace (in bytes). Zero indicates that no
+      // trace was collected.
+      size_t TraceSize = 0;
     };
 
     // The address of this allocation.
diff --git a/lib/gwp_asan/optional/backtrace.h b/lib/gwp_asan/optional/backtrace.h
index 2700970e5e8e..6c9ee9f6506d 100644
--- a/lib/gwp_asan/optional/backtrace.h
+++ b/lib/gwp_asan/optional/backtrace.h
@@ -14,7 +14,12 @@
 namespace gwp_asan {
 namespace options {
 // Functions to get the platform-specific and implementation-specific backtrace
-// and backtrace printing functions.
+// and backtrace printing functions when RTGwpAsanBacktraceLibc or
+// RTGwpAsanBacktraceSanitizerCommon are linked. Use these functions to get the
+// backtrace function for populating the Options::Backtrace and
+// Options::PrintBacktrace when initialising the GuardedPoolAllocator. Please
+// note any thread-safety descriptions for the implementation of these functions
+// that you use.
 Backtrace_t getBacktraceFunction();
 PrintBacktrace_t getPrintBacktraceFunction();
 } // namespace options
diff --git a/lib/gwp_asan/optional/backtrace_linux_libc.cpp b/lib/gwp_asan/optional/backtrace_linux_libc.cpp
index f20a3100927e..a656c9b41d5d 100644
--- a/lib/gwp_asan/optional/backtrace_linux_libc.cpp
+++ b/lib/gwp_asan/optional/backtrace_linux_libc.cpp
@@ -17,33 +17,23 @@
 #include "gwp_asan/options.h"
 
 namespace {
-void Backtrace(uintptr_t *TraceBuffer, size_t Size) {
-  // Grab (what seems to be) one more trace than we need. TraceBuffer needs to
-  // be null-terminated, but we wish to remove the frame of this function call.
+size_t Backtrace(uintptr_t *TraceBuffer, size_t Size) {
   static_assert(sizeof(uintptr_t) == sizeof(void *), "uintptr_t is not void*");
-  int NumTraces =
-      backtrace(reinterpret_cast<void **>(TraceBuffer), Size);
 
-  // Now shift the entire trace one place to the left and null-terminate.
-  memmove(TraceBuffer, TraceBuffer + 1, NumTraces * sizeof(void *));
-  TraceBuffer[NumTraces - 1] = 0;
+  return backtrace(reinterpret_cast<void **>(TraceBuffer), Size);
 }
 
-static void PrintBacktrace(uintptr_t *Trace,
+static void PrintBacktrace(uintptr_t *Trace, size_t TraceLength,
                            gwp_asan::options::Printf_t Printf) {
-  size_t NumTraces = 0;
-  for (; Trace[NumTraces] != 0; ++NumTraces) {
-  }
-
-  if (NumTraces == 0) {
+  if (TraceLength == 0) {
     Printf("  <not found (does your allocator support backtracing?)>\n\n");
     return;
   }
 
   char **BacktraceSymbols =
-      backtrace_symbols(reinterpret_cast<void **>(Trace), NumTraces);
+      backtrace_symbols(reinterpret_cast<void **>(Trace), TraceLength);
 
-  for (size_t i = 0; i < NumTraces; ++i) {
+  for (size_t i = 0; i < TraceLength; ++i) {
     if (!BacktraceSymbols)
       Printf("  #%zu %p\n", i, Trace[i]);
     else
diff --git a/lib/gwp_asan/optional/backtrace_sanitizer_common.cpp b/lib/gwp_asan/optional/backtrace_sanitizer_common.cpp
index 7d17eec0da2f..5e07fd6f465a 100644
--- a/lib/gwp_asan/optional/backtrace_sanitizer_common.cpp
+++ b/lib/gwp_asan/optional/backtrace_sanitizer_common.cpp
@@ -13,6 +13,9 @@
 
 #include "gwp_asan/optional/backtrace.h"
 #include "gwp_asan/options.h"
+#include "sanitizer_common/sanitizer_common.h"
+#include "sanitizer_common/sanitizer_flag_parser.h"
+#include "sanitizer_common/sanitizer_flags.h"
 #include "sanitizer_common/sanitizer_stacktrace.h"
 
 void __sanitizer::BufferedStackTrace::UnwindImpl(uptr pc, uptr bp,
@@ -26,7 +29,7 @@ void __sanitizer::BufferedStackTrace::UnwindImpl(uptr pc, uptr bp,
 }
 
 namespace {
-void Backtrace(uintptr_t *TraceBuffer, size_t Size) {
+size_t Backtrace(uintptr_t *TraceBuffer, size_t Size) {
   __sanitizer::BufferedStackTrace Trace;
   Trace.Reset();
   if (Size > __sanitizer::kStackTraceMax)
@@ -38,19 +41,14 @@ void Backtrace(uintptr_t *TraceBuffer, size_t Size) {
                /* fast unwind */ true, Size - 1);
 
   memcpy(TraceBuffer, Trace.trace, Trace.size * sizeof(uintptr_t));
-  TraceBuffer[Trace.size] = 0;
+  return Trace.size;
 }
 
-static void PrintBacktrace(uintptr_t *Trace,
+static void PrintBacktrace(uintptr_t *Trace, size_t TraceLength,
                            gwp_asan::options::Printf_t Printf) {
   __sanitizer::StackTrace StackTrace;
   StackTrace.trace = reinterpret_cast<__sanitizer::uptr *>(Trace);
-
-  for (StackTrace.size = 0; StackTrace.size < __sanitizer::kStackTraceMax;
-       ++StackTrace.size) {
-    if (Trace[StackTrace.size] == 0)
-      break;
-  }
+  StackTrace.size = TraceLength;
 
   if (StackTrace.size == 0) {
     Printf("  <unknown (does your allocator support backtracing?)>\n\n");
@@ -63,7 +61,18 @@ static void PrintBacktrace(uintptr_t *Trace,
 
 namespace gwp_asan {
 namespace options {
-Backtrace_t getBacktraceFunction() { return Backtrace; }
+// This function is thread-compatible. It must be synchronised in respect to any
+// other calls to getBacktraceFunction(), calls to getPrintBacktraceFunction(),
+// and calls to either of the functions that they return. Furthermore, this may
+// require synchronisation with any calls to sanitizer_common that use flags.
+// Generally, this function will be called during the initialisation of the
+// allocator, which is done in a thread-compatible manner.
+Backtrace_t getBacktraceFunction() {
+  // The unwinder requires the default flags to be set.
+  __sanitizer::SetCommonFlagsDefaults();
+  __sanitizer::InitializeCommonFlags();
+  return Backtrace;
+}
 PrintBacktrace_t getPrintBacktraceFunction() { return PrintBacktrace; }
 } // namespace options
 } // namespace gwp_asan
diff --git a/lib/gwp_asan/options.h b/lib/gwp_asan/options.h
index 6423e16526f4..ae3f3d45e946 100644
--- a/lib/gwp_asan/options.h
+++ b/lib/gwp_asan/options.h
@@ -14,22 +14,63 @@
 
 namespace gwp_asan {
 namespace options {
-// The function pointer type for printf(). Follows the standard format from the
-// sanitizers library. If the supported allocator exposes printing via a
-// different function signature, please provide a wrapper which has this
-// printf() signature, and pass the wrapper instead.
+// ================================ Requirements ===============================
+// This function is required to be implemented by the supporting allocator. The
+// sanitizer::Printf() function can be simply used here.
+// ================================ Description ================================
+// This function shall produce output according to a strict subset of the C
+// standard library's printf() family. This function must support printing the
+// following formats:
+//   1. integers: "%([0-9]*)?(z|ll)?{d,u,x,X}"
+//   2. pointers: "%p"
+//   3. strings:  "%[-]([0-9]*)?(\\.\\*)?s"
+//   4. chars:    "%c"
+// This function must be implemented in a signal-safe manner.
+// =================================== Notes ===================================
+// This function has a slightly different signature than the C standard
+// library's printf(). Notably, it returns 'void' rather than 'int'.
 typedef void (*Printf_t)(const char *Format, ...);
 
-// The function pointer type for backtrace information. Required to be
-// implemented by the supporting allocator. The callee should elide itself and
-// all frames below itself from TraceBuffer, i.e. the caller's frame should be
-// in TraceBuffer[0], and subsequent frames 1..n into TraceBuffer[1..n], where a
-// maximum of `MaximumDepth - 1` frames are stored. TraceBuffer should be
-// nullptr-terminated (i.e. if there are 5 frames; TraceBuffer[5] == nullptr).
-// If the allocator cannot supply backtrace information, it should set
-// TraceBuffer[0] == nullptr.
-typedef void (*Backtrace_t)(uintptr_t *TraceBuffer, size_t Size);
-typedef void (*PrintBacktrace_t)(uintptr_t *TraceBuffer, Printf_t Print);
+// ================================ Requirements ===============================
+// This function is required to be either implemented by the supporting
+// allocator, or one of the two provided implementations may be used
+// (RTGwpAsanBacktraceLibc or RTGwpAsanBacktraceSanitizerCommon).
+// ================================ Description ================================
+// This function shall collect the backtrace for the calling thread and place
+// the result in `TraceBuffer`. This function should elide itself and all frames
+// below itself from `TraceBuffer`, i.e. the caller's frame should be in
+// TraceBuffer[0], and subsequent frames 1..n into TraceBuffer[1..n], where a
+// maximum of `Size` frames are stored. Returns the number of frames stored into
+// `TraceBuffer`, and zero on failure. If the return value of this function is
+// equal to `Size`, it may indicate that the backtrace is truncated.
+// =================================== Notes ===================================
+// This function may directly or indirectly call malloc(), as the
+// GuardedPoolAllocator contains a reentrancy barrier to prevent infinite
+// recursion. Any allocation made inside this function will be served by the
+// supporting allocator, and will not have GWP-ASan protections.
+typedef size_t (*Backtrace_t)(uintptr_t *TraceBuffer, size_t Size);
+
+// ================================ Requirements ===============================
+// This function is optional for the supporting allocator, but one of the two
+// provided implementations may be used (RTGwpAsanBacktraceLibc or
+// RTGwpAsanBacktraceSanitizerCommon). If not provided, a default implementation
+// is used which prints the raw pointers only.
+// ================================ Description ================================
+// This function shall take the backtrace provided in `TraceBuffer`, and print
+// it in a human-readable format using `Print`. Generally, this function shall
+// resolve raw pointers to section offsets and print them with the following
+// sanitizer-common format:
+//      "  #{frame_number} {pointer} in {function name} ({binary name}+{offset}"
+// e.g. "  #5 0x420459 in _start (/tmp/uaf+0x420459)"
+// This format allows the backtrace to be symbolized offline successfully using
+// llvm-symbolizer.
+// =================================== Notes ===================================
+// This function may directly or indirectly call malloc(), as the
+// GuardedPoolAllocator contains a reentrancy barrier to prevent infinite
+// recursion. Any allocation made inside this function will be served by the
+// supporting allocator, and will not have GWP-ASan protections.
+typedef void (*PrintBacktrace_t)(uintptr_t *TraceBuffer, size_t TraceLength,
+                                 Printf_t Print);
 
 struct Options {
   Printf_t Printf = nullptr;
diff --git a/lib/gwp_asan/options.inc b/lib/gwp_asan/options.inc
index 9042b11895ae..df6c46e6e98f 100644
--- a/lib/gwp_asan/options.inc
+++ b/lib/gwp_asan/options.inc
@@ -21,9 +21,9 @@ GWP_ASAN_OPTION(
     "byte buffer-overflows for multibyte allocations at the cost of "
     "performance, and may be incompatible with some architectures.")
 
-GWP_ASAN_OPTION(
-    int, MaxSimultaneousAllocations, 16,
-    "Number of usable guarded slots in the allocation pool. Defaults to 16.")
+GWP_ASAN_OPTION(int, MaxSimultaneousAllocations, 16,
+                "Number of simultaneously-guarded allocations available in the "
+                "pool. Defaults to 16.")
 
 GWP_ASAN_OPTION(int, SampleRate, 5000,
                 "The probability (1 / SampleRate) that an allocation is "
diff --git a/lib/gwp_asan/scripts/symbolize.sh b/lib/gwp_asan/scripts/symbolize.sh
new file mode 100755
index 000000000000..fad9620a676e
--- /dev/null
+++ b/lib/gwp_asan/scripts/symbolize.sh
@@ -0,0 +1,55 @@
+#!/bin/bash
+
+# The lines that we're looking to symbolize look like this:
+  #0 ./a.out(_foo+0x3e6) [0x55a52e64c696]
+# ... which come from the backtrace_symbols() symbolisation function used by
+# default in Scudo's implementation of GWP-ASan.
+
+while read -r line; do
+  # Check that this line needs symbolization.
+  should_symbolize="$(echo $line |\
+     grep -E '^[ ]*\#.*\(.*\+0x[0-9a-f]+\) \[0x[0-9a-f]+\]$')"
+
+  if [ -z "$should_symbolize" ]; then
+    echo "$line"
+    continue
+  fi
+
+  # Carve up the input line into sections.
+  binary_name="$(echo $line | grep -oE ' .*\(' | rev | cut -c2- | rev |\
+      cut -c2-)"
+  function_name="$(echo $line | grep -oE '\([^+]*' | cut -c2-)"
+  function_offset="$(echo $line | grep -oE '\(.*\)' | grep -oE '\+.*\)' |\
+      cut -c2- | rev | cut -c2- | rev)"
+  frame_number="$(echo $line | grep -oE '\#[0-9]+ ')"
+
+  if [ -z "$function_name" ]; then
+    # If the offset is binary-relative, just resolve that.
+    symbolized="$(echo $function_offset | addr2line -e $binary_name)"
+  else
+    # Otherwise, the offset is function-relative. Get the address of the
+    # function, and add it to the offset, then symbolize.
+    function_addr="0x$(echo $function_offset |\
+       nm --defined-only $binary_name 2> /dev/null |\
+       grep -E " $function_name$" | cut -d' ' -f1)"
+
+    # Check that we could get the function address from nm.
+    if [ -z "$function_addr" ]; then
+      echo "$line"
+      continue
+    fi
+
+    # Add the function address and offset to get the offset into the binary.
+    binary_offset="$(printf "0x%X" "$((function_addr+function_offset))")"
+    symbolized="$(echo $binary_offset | addr2line -e $binary_name)"
+  fi
+
+  # Check that it symbolized properly. If it didn't, output the old line.
+  echo $symbolized | grep -E ".*\?.*:" > /dev/null
+  if [ "$?" -eq "0" ]; then
+    echo "$line"
+    continue
+  else
+    echo "${frame_number}${symbolized}"
+  fi
+done
diff --git a/lib/gwp_asan/stack_trace_compressor.cpp b/lib/gwp_asan/stack_trace_compressor.cpp
new file mode 100644
index 000000000000..ca3167fb83a8
--- /dev/null
+++ b/lib/gwp_asan/stack_trace_compressor.cpp
@@ -0,0 +1,111 @@
+//===-- stack_trace_compressor.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 "gwp_asan/stack_trace_compressor.h"
+
+namespace gwp_asan {
+namespace compression {
+namespace {
+// Encodes `Value` as a variable-length integer to `Out`. Returns zero if there
+// was not enough space in the output buffer to write the complete varInt.
+// Otherwise returns the length of the encoded integer.
+size_t varIntEncode(uintptr_t Value, uint8_t *Out, size_t OutLen) {
+  for (size_t i = 0; i < OutLen; ++i) {
+    Out[i] = Value & 0x7f;
+    Value >>= 7;
+    if (!Value)
+      return i + 1;
+
+    Out[i] |= 0x80;
+  }
+
+  return 0;
+}
+
+// Decodes a variable-length integer to `Out`. Returns zero if the integer was
+// too large to be represented in a uintptr_t, or if the input buffer finished
+// before the integer was decoded (either case meaning that the `In` does not
+// point to a valid varInt buffer). Otherwise, returns the number of bytes that
+// were used to store the decoded integer.
+size_t varIntDecode(const uint8_t *In, size_t InLen, uintptr_t *Out) {
+  *Out = 0;
+  uint8_t Shift = 0;
+
+  for (size_t i = 0; i < InLen; ++i) {
+    *Out |= (static_cast<uintptr_t>(In[i]) & 0x7f) << Shift;
+
+    if (In[i] < 0x80)
+      return i + 1;
+
+    Shift += 7;
+
+    // Disallow overflowing the range of the output integer.
+    if (Shift >= sizeof(uintptr_t) * 8)
+      return 0;
+  }
+  return 0;
+}
+
+uintptr_t zigzagEncode(uintptr_t Value) {
+  uintptr_t Encoded = Value << 1;
+  if (static_cast<intptr_t>(Value) >= 0)
+    return Encoded;
+  return ~Encoded;
+}
+
+uintptr_t zigzagDecode(uintptr_t Value) {
+  uintptr_t Decoded = Value >> 1;
+  if (!(Value & 1))
+    return Decoded;
+  return ~Decoded;
+}
+} // anonymous namespace
+
+size_t pack(const uintptr_t *Unpacked, size_t UnpackedSize, uint8_t *Packed,
+            size_t PackedMaxSize) {
+  size_t Index = 0;
+  for (size_t CurrentDepth = 0; CurrentDepth < UnpackedSize; CurrentDepth++) {
+    uintptr_t Diff = Unpacked[CurrentDepth];
+    if (CurrentDepth > 0)
+      Diff -= Unpacked[CurrentDepth - 1];
+    size_t EncodedLength =
+        varIntEncode(zigzagEncode(Diff), Packed + Index, PackedMaxSize - Index);
+    if (!EncodedLength)
+      break;
+
+    Index += EncodedLength;
+  }
+
+  return Index;
+}
+
+size_t unpack(const uint8_t *Packed, size_t PackedSize, uintptr_t *Unpacked,
+              size_t UnpackedMaxSize) {
+  size_t CurrentDepth;
+  size_t Index = 0;
+  for (CurrentDepth = 0; CurrentDepth < UnpackedMaxSize; CurrentDepth++) {
+    uintptr_t EncodedDiff;
+    size_t DecodedLength =
+        varIntDecode(Packed + Index, PackedSize - Index, &EncodedDiff);
+    if (!DecodedLength)
+      break;
+    Index += DecodedLength;
+
+    Unpacked[CurrentDepth] = zigzagDecode(EncodedDiff);
+    if (CurrentDepth > 0)
+      Unpacked[CurrentDepth] += Unpacked[CurrentDepth - 1];
+  }
+
+  if (Index != PackedSize && CurrentDepth != UnpackedMaxSize)
+    return 0;
+
+  return CurrentDepth;
+}
+
+} // namespace compression
+} // namespace gwp_asan
diff --git a/lib/gwp_asan/stack_trace_compressor.h b/lib/gwp_asan/stack_trace_compressor.h
new file mode 100644
index 000000000000..dcbd9a3c1f0a
--- /dev/null
+++ b/lib/gwp_asan/stack_trace_compressor.h
@@ -0,0 +1,38 @@
+//===-- stack_trace_compressor.h --------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef GWP_ASAN_STACK_TRACE_COMPRESSOR_
+#define GWP_ASAN_STACK_TRACE_COMPRESSOR_
+
+#include <stddef.h>
+#include <stdint.h>
+
+// These functions implement stack frame compression and decompression. We store
+// the zig-zag encoded pointer difference between frame[i] and frame[i - 1] as
+// a variable-length integer. This can reduce the memory overhead of stack
+// traces by 50%.
+
+namespace gwp_asan {
+namespace compression {
+
+// For the stack trace in `Unpacked` with length `UnpackedSize`, pack it into
+// the buffer `Packed` maximum length `PackedMaxSize`. The return value is the
+// number of bytes that were written to the output buffer.
+size_t pack(const uintptr_t *Unpacked, size_t UnpackedSize, uint8_t *Packed,
+            size_t PackedMaxSize);
+
+// From the packed stack trace in `Packed` of length `PackedSize`, write the
+// unpacked stack trace of maximum length `UnpackedMaxSize` into `Unpacked`.
+// Returns the number of full entries unpacked, or zero on error.
+size_t unpack(const uint8_t *Packed, size_t PackedSize, uintptr_t *Unpacked,
+              size_t UnpackedMaxSize);
+
+} // namespace compression
+} // namespace gwp_asan
+
+#endif // GWP_ASAN_STACK_TRACE_COMPRESSOR_