diff --git a/compiler-rt/lib/gwp_asan/CMakeLists.txt b/compiler-rt/lib/gwp_asan/CMakeLists.txt --- a/compiler-rt/lib/gwp_asan/CMakeLists.txt +++ b/compiler-rt/lib/gwp_asan/CMakeLists.txt @@ -7,6 +7,7 @@ platform_specific/mutex_posix.cpp guarded_pool_allocator.cpp random.cpp + stack_trace_compressor.cpp ) set(GWP_ASAN_HEADERS @@ -16,6 +17,7 @@ options.h options.inc random.h + stack_trace_compressor.h ) # Ensure that GWP-ASan meets the delegated requirements of some supporting @@ -96,6 +98,18 @@ SOURCES optional/backtrace_sanitizer_common.cpp ADDITIONAL_HEADERS ${GWP_ASAN_BACKTRACE_HEADERS} CFLAGS ${GWP_ASAN_CFLAGS} ${SANITIZER_COMMON_CFLAGS}) + + # Build the stack trace compressor fuzzer. + add_llvm_executable(stack_trace_compressor_fuzzer + stack_trace_compressor_fuzzer.cpp + ${GWP_ASAN_SOURCES} + ${GWP_ASAN_HEADERS}) + set_target_properties(stack_trace_compressor_fuzzer + PROPERTIES FOLDER "Fuzzers") + target_compile_options(stack_trace_compressor_fuzzer + PRIVATE -fsanitize=fuzzer-no-link) + target_link_options(stack_trace_compressor_fuzzer PRIVATE -fsanitize=fuzzer) + add_dependencies(gwp_asan stack_trace_compressor_fuzzer) endif() if(COMPILER_RT_INCLUDE_TESTS) diff --git a/compiler-rt/lib/gwp_asan/guarded_pool_allocator.h b/compiler-rt/lib/gwp_asan/guarded_pool_allocator.h --- a/compiler-rt/lib/gwp_asan/guarded_pool_allocator.h +++ b/compiler-rt/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 #include @@ -39,24 +40,26 @@ }; 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. + static constexpr size_t kStackFrameStorageBytes = 128; // Records the given allocation metadata into this struct. void RecordAllocation(uintptr_t Addr, size_t Size, - options::Backtrace_t Backtrace); + options::Backtrace_t Backtrace, + size_t MaxTraceLength); // Record that this allocation is now deallocated. - void RecordDeallocation(options::Backtrace_t Backtrace); + void RecordDeallocation(options::Backtrace_t Backtrace, + size_t MaxTraceLength); struct CallSiteInfo { - // The backtrace to the allocation/deallocation. - 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 length of the trace. Zero indicates that no trace was collected. - size_t TraceLength = 0; + // The size of the compressed trace (in bytes). Zero indicates that no + // trace was collected. + size_t TraceSize = 0; }; // The address of this allocation. @@ -213,6 +216,9 @@ // that we don't randomly choose to recycle a slot that previously had an // allocation before all the slots have been utilised. size_t NumSampledAllocations = 0; + // Maximum number of stack frames to collect during Backtrace(). See options + // for more details. + size_t MaxTraceLength = 128; // Pointer to the pool of guarded slots. Note that this points to the start of // the pool (which is a guard page), not a pointer to the first guarded page. uintptr_t GuardedPagePool = UINTPTR_MAX; diff --git a/compiler-rt/lib/gwp_asan/guarded_pool_allocator.cpp b/compiler-rt/lib/gwp_asan/guarded_pool_allocator.cpp --- a/compiler-rt/lib/gwp_asan/guarded_pool_allocator.cpp +++ b/compiler-rt/lib/gwp_asan/guarded_pool_allocator.cpp @@ -61,7 +61,8 @@ GuardedPoolAllocator *getSingleton() { return SingletonPtr; } void GuardedPoolAllocator::AllocationMetadata::RecordAllocation( - uintptr_t AllocAddr, size_t AllocSize, options::Backtrace_t Backtrace) { + uintptr_t AllocAddr, size_t AllocSize, options::Backtrace_t Backtrace, + size_t MaxTraceLength) { Addr = AllocAddr; Size = AllocSize; IsDeallocated = false; @@ -69,24 +70,35 @@ // 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.TraceLength = 0; - DeallocationTrace.TraceLength = 0; + AllocationTrace.TraceSize = 0; + DeallocationTrace.TraceSize = 0; DeallocationTrace.ThreadID = kInvalidThreadID; - if (Backtrace) - AllocationTrace.TraceLength = - Backtrace(AllocationTrace.Trace, kMaximumStackFrames); + + if (Backtrace) { + uintptr_t *UncompressedBuffer = + static_cast(alloca(MaxTraceLength * sizeof(uintptr_t))); + size_t BacktraceLength = Backtrace(UncompressedBuffer, MaxTraceLength); + AllocationTrace.TraceSize = compression::pack( + UncompressedBuffer, BacktraceLength, AllocationTrace.CompressedTrace, + kStackFrameStorageBytes); + } } void GuardedPoolAllocator::AllocationMetadata::RecordDeallocation( - options::Backtrace_t Backtrace) { + options::Backtrace_t Backtrace, size_t MaxTraceLength) { IsDeallocated = true; // Ensure that the unwinder is not called if the recursive flag is set, // otherwise non-reentrant unwinders may deadlock. - DeallocationTrace.TraceLength = 0; + DeallocationTrace.TraceSize = 0; if (Backtrace && !ThreadLocals.RecursiveGuard) { ScopedBoolean B(ThreadLocals.RecursiveGuard); - DeallocationTrace.TraceLength = - Backtrace(DeallocationTrace.Trace, kMaximumStackFrames); + + uintptr_t *UncompressedBuffer = + static_cast(alloca(MaxTraceLength * sizeof(uintptr_t))); + size_t BacktraceLength = Backtrace(UncompressedBuffer, MaxTraceLength); + DeallocationTrace.TraceSize = compression::pack( + UncompressedBuffer, BacktraceLength, DeallocationTrace.CompressedTrace, + kStackFrameStorageBytes); } DeallocationTrace.ThreadID = getThreadID(); } @@ -124,6 +136,7 @@ SingletonPtr = this; MaxSimultaneousAllocations = Opts.MaxSimultaneousAllocations; + MaxTraceLength = Opts.MaxTraceLength; PageSize = getPlatformPageSize(); @@ -199,7 +212,7 @@ // unmapped. markReadWrite(reinterpret_cast(getPageAddr(Ptr)), Size); - Meta->RecordAllocation(Ptr, Size, Backtrace); + Meta->RecordAllocation(Ptr, Size, Backtrace, MaxTraceLength); return reinterpret_cast(Ptr); } @@ -226,7 +239,7 @@ // Ensure that the deallocation is recorded before marking the page as // inaccessible. Otherwise, a racy use-after-free will have inconsistent // metadata. - Meta->RecordDeallocation(Backtrace); + Meta->RecordDeallocation(Backtrace, MaxTraceLength); } markInaccessible(reinterpret_cast(SlotStart), @@ -432,7 +445,8 @@ void printAllocDeallocTraces(uintptr_t AccessPtr, AllocationMetadata *Meta, options::Printf_t Printf, - options::PrintBacktrace_t PrintBacktrace) { + options::PrintBacktrace_t PrintBacktrace, + size_t MaxTraceLength) { assert(Meta != nullptr && "Metadata is non-null for printAllocDeallocTraces"); if (Meta->IsDeallocated) { @@ -443,8 +457,13 @@ Printf("0x%zx was deallocated by thread %zu here:\n", AccessPtr, Meta->DeallocationTrace.ThreadID); - PrintBacktrace(Meta->DeallocationTrace.Trace, - Meta->DeallocationTrace.TraceLength, Printf); + uintptr_t *UncompressedTrace = + static_cast(alloca(MaxTraceLength)); + size_t UncompressedLength = compression::unpack( + Meta->DeallocationTrace.CompressedTrace, + Meta->DeallocationTrace.TraceSize, UncompressedTrace, MaxTraceLength); + + PrintBacktrace(UncompressedTrace, UncompressedLength, Printf); } if (Meta->AllocationTrace.ThreadID == GuardedPoolAllocator::kInvalidThreadID) @@ -453,8 +472,13 @@ Printf("0x%zx was allocated by thread %zu here:\n", Meta->Addr, Meta->AllocationTrace.ThreadID); - PrintBacktrace(Meta->AllocationTrace.Trace, Meta->AllocationTrace.TraceLength, - Printf); + uintptr_t *UncompressedTrace = + static_cast(alloca(MaxTraceLength)); + size_t UncompressedLength = compression::unpack( + Meta->AllocationTrace.CompressedTrace, Meta->AllocationTrace.TraceSize, + UncompressedTrace, MaxTraceLength); + + PrintBacktrace(UncompressedTrace, UncompressedLength, Printf); } struct ScopedEndOfReportDecorator { @@ -504,7 +528,8 @@ } if (Meta) - printAllocDeallocTraces(AccessPtr, Meta, Printf, PrintBacktrace); + printAllocDeallocTraces(AccessPtr, Meta, Printf, PrintBacktrace, + MaxTraceLength); } TLS_INITIAL_EXEC diff --git a/compiler-rt/lib/gwp_asan/options.inc b/compiler-rt/lib/gwp_asan/options.inc --- a/compiler-rt/lib/gwp_asan/options.inc +++ b/compiler-rt/lib/gwp_asan/options.inc @@ -25,6 +25,12 @@ int, MaxSimultaneousAllocations, 16, "Number of usable guarded slots in the allocation pool. Defaults to 16.") +GWP_ASAN_OPTION( + int, MaxTraceLength, 128, + "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. Default is 128.") + GWP_ASAN_OPTION(int, SampleRate, 5000, "The probability (1 / SampleRate) that an allocation is " "selected for GWP-ASan sampling. Default is 5000. Sample rates " diff --git a/compiler-rt/lib/gwp_asan/stack_trace_compressor.h b/compiler-rt/lib/gwp_asan/stack_trace_compressor.h new file mode 100644 --- /dev/null +++ b/compiler-rt/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_COMPRESSION_ +#define GWP_ASAN_STACK_TRACE_COMPRESSION_ + +#include +#include + +// 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_COMPRESSION_ diff --git a/compiler-rt/lib/gwp_asan/stack_trace_compressor.cpp b/compiler-rt/lib/gwp_asan/stack_trace_compressor.cpp new file mode 100644 --- /dev/null +++ b/compiler-rt/lib/gwp_asan/stack_trace_compressor.cpp @@ -0,0 +1,146 @@ +//===-- 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 == 0) + return i + 1; + Out[i] |= 0x80; + } + + return 0; +} + +constexpr size_t kBytesForLargestVarInt = (sizeof(uintptr_t) * 8) / 7 + 1; + +// 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) { + if (i >= kBytesForLargestVarInt) + return 0; + + *Out |= (static_cast(In[i]) & 0x7f) << Shift; + Shift += 7; + + if (!(In[i] & 0x80)) + return i + 1; + } + return 0; +} + +// Converts the signed intptr_t to an unsigned uintptr_t with zigzag encoding. +uintptr_t zigZagEncode(intptr_t SignedPtr) { + if (SignedPtr < 0) { + if (SignedPtr == INTPTR_MIN) + return UINTPTR_MAX; + return (static_cast(-1 * SignedPtr) << 1) - 1; + } + return static_cast(SignedPtr) << 1; +} + +// Converts a zigzag encoded uintptr_t to a signed intptr_t. +intptr_t zigZagDecode(uintptr_t UnsignedPtr) { + if (UnsignedPtr & 0x01) { + if (UnsignedPtr == UINTPTR_MAX) + return INTPTR_MIN; + return -1 * static_cast((UnsignedPtr >> 1) + 1); + } + return static_cast(UnsignedPtr >> 1); +} +} // anonymous namespace + +size_t pack(const uintptr_t *Unpacked, size_t UnpackedSize, uint8_t *Packed, + size_t PackedMaxSize) { + if (UnpackedSize == 0) + return 0; + + size_t TotalBytesWritten = 0; + // Pack the first varint. + size_t BytesWritten = varIntEncode(Unpacked[0], Packed, PackedMaxSize); + if (BytesWritten == 0) + return 0; + TotalBytesWritten += BytesWritten; + + for (size_t i = 1; i < UnpackedSize; ++i) { + // Two integers `0 <= x <= UINTPTR_MAX` can be at most `0 <= y <= + // INTPTR_MAX` apart, due to overflow/underflow. We store the shortest + // distance between the two pointers in order to minimize the varint space + // required, as the difference is zigzag-encoded. + intptr_t Difference; + + uintptr_t SubDiff = Unpacked[i] - Unpacked[i - 1]; + if (SubDiff > INTPTR_MAX) + Difference = + INTPTR_MIN + (SubDiff % (static_cast(INTPTR_MAX) + 1)); + else + Difference = static_cast(SubDiff); + + uintptr_t ZigZagEncodedDifference = zigZagEncode(Difference); + + BytesWritten = + varIntEncode(ZigZagEncodedDifference, Packed + TotalBytesWritten, + PackedMaxSize - TotalBytesWritten); + if (BytesWritten == 0) + break; + TotalBytesWritten += BytesWritten; + } + return TotalBytesWritten; +} + +size_t unpack(const uint8_t *Packed, size_t PackedSize, uintptr_t *Unpacked, + size_t UnpackedMaxSize) { + uintptr_t Buffer; + + if (UnpackedMaxSize == 0) + return 0; + + // Decode the first varInt. + size_t BytesConsumed = varIntDecode(Packed, PackedSize, &Buffer); + if (BytesConsumed == 0) + return 0; + + size_t TotalBytesConsumed = BytesConsumed; + size_t EntriesUnpacked = 1; + Unpacked[0] = Buffer; + + for (size_t i = 1; i < UnpackedMaxSize && TotalBytesConsumed < PackedSize; + ++i) { + BytesConsumed = varIntDecode(Packed + TotalBytesConsumed, + PackedSize - TotalBytesConsumed, &Buffer); + if (BytesConsumed == 0) + break; + + TotalBytesConsumed += BytesConsumed; + + intptr_t Difference = zigZagDecode(Buffer); + Unpacked[i] = Unpacked[i - 1] + Difference; + EntriesUnpacked++; + } + return EntriesUnpacked; +} + +} // namespace compression +} // namespace gwp_asan diff --git a/compiler-rt/lib/gwp_asan/stack_trace_compressor_fuzzer.cpp b/compiler-rt/lib/gwp_asan/stack_trace_compressor_fuzzer.cpp new file mode 100644 --- /dev/null +++ b/compiler-rt/lib/gwp_asan/stack_trace_compressor_fuzzer.cpp @@ -0,0 +1,49 @@ +#include +#include +#include +#include +#include + +#include "gwp_asan/stack_trace_compressor.h" + +constexpr size_t kBytesForLargestVarInt = (sizeof(uintptr_t) * 8) / 7 + 1; + +extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + size_t BufferSize = kBytesForLargestVarInt * Size / sizeof(uintptr_t); + std::vector Buffer(BufferSize); + std::vector Buffer2(BufferSize); + + // Unpack the fuzz bytes. + gwp_asan::compression::unpack(Data, Size, + reinterpret_cast(Buffer2.data()), + BufferSize / sizeof(uintptr_t)); + + // Pack the fuzz bytes. + size_t BytesWritten = gwp_asan::compression::pack( + reinterpret_cast(Data), Size / sizeof(uintptr_t), + Buffer.data(), BufferSize); + + // Unpack the compressed buffer. + size_t DecodedElements = gwp_asan::compression::unpack( + Buffer.data(), BytesWritten, + reinterpret_cast(Buffer2.data()), + BufferSize / sizeof(uintptr_t)); + + // Ensure that every element was encoded and decoded properly. + if (DecodedElements != Size / sizeof(uintptr_t)) + abort(); + + // Ensure that the compression and uncompression resulted in the same trace. + const uintptr_t *FuzzPtrs = reinterpret_cast(Data); + const uintptr_t *DecodedPtrs = + reinterpret_cast(Buffer2.data()); + for (size_t i = 0; i < Size / sizeof(uintptr_t); ++i) { + if (FuzzPtrs[i] != DecodedPtrs[i]) { + fprintf(stderr, "FuzzPtrs[%zu] != DecodedPtrs[%zu] (0x%zx vs. 0x%zx)", i, + i, FuzzPtrs[i], DecodedPtrs[i]); + abort(); + } + } + + return 0; +} diff --git a/compiler-rt/lib/gwp_asan/tests/compression.cpp b/compiler-rt/lib/gwp_asan/tests/compression.cpp new file mode 100644 --- /dev/null +++ b/compiler-rt/lib/gwp_asan/tests/compression.cpp @@ -0,0 +1,255 @@ +//===-- compression.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" +#include "gtest/gtest.h" + +namespace gwp_asan { +namespace compression { + +TEST(GwpAsanCompressionTest, SingleByteVarInt) { + uint8_t Compressed[1]; + + uintptr_t Uncompressed = 0x00; + EXPECT_EQ(1u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[0], 0x00); + + Uncompressed = 0x01; + EXPECT_EQ(1u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[0], 0x01); + + Uncompressed = 0x7f; + EXPECT_EQ(1u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[0], 0x7f); +} + +TEST(GwpAsanCompressionTest, MultiByteVarInt) { + uint8_t Compressed[sizeof(uintptr_t) + 1]; + + uintptr_t Uncompressed = 0x80; + EXPECT_EQ(2u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[0], 0x80); + EXPECT_EQ(Compressed[1], 0x01); + + Uncompressed = 0x81; + EXPECT_EQ(2u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[0], 0x81); + EXPECT_EQ(Compressed[1], 0x01); + + Uncompressed = 0x3fff; + EXPECT_EQ(2u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[0], 0xff); + EXPECT_EQ(Compressed[1], 0x7f); + + Uncompressed = 0x4000; + EXPECT_EQ(3u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[0], 0x80); + EXPECT_EQ(Compressed[1], 0x80); + EXPECT_EQ(Compressed[2], 0x01); + + Uncompressed = 0x305080c101; + EXPECT_EQ(6u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[0], 0x81); + EXPECT_EQ(Compressed[1], 0x82); + EXPECT_EQ(Compressed[2], 0x83); + EXPECT_EQ(Compressed[3], 0x84); + EXPECT_EQ(Compressed[4], 0x85); + EXPECT_EQ(Compressed[5], 0x06); +} + +TEST(GwpAsanCompressionTest, ZigZagEncoding) { + uint8_t Compressed[10]; + uintptr_t Uncompressed[2] = {0x00, 0x00}; + + EXPECT_EQ(2u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t), + Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[1], 0x00); // +0 difference => 0 in zigzag. + + Uncompressed[1] = 0x01; + EXPECT_EQ(2u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t), + Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[1], 0x02); // +1 difference => 2 in zigzag. + + Uncompressed[1] = 0x02; + EXPECT_EQ(2u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t), + Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[1], 0x04); // +2 difference => 4 in zigzag. + + Uncompressed[1] = 0x80; + EXPECT_EQ(3u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t), + Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[1], 0x80); // +128 difference => +256 in zigzag (note the + EXPECT_EQ(Compressed[2], 0x02); // varint encoding here). + + Uncompressed[0] = 0x01; + Uncompressed[1] = 0x00; + EXPECT_EQ(2u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t), + Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[1], 0x01); // -1 difference => +1 in zigzag. + + Uncompressed[0] = 0x02; + EXPECT_EQ(2u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t), + Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[1], 0x03); // -2 difference => +3 in zigzag. + + Uncompressed[0] = 0x80; + EXPECT_EQ(4u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t), + Compressed, sizeof(Compressed))); + EXPECT_EQ(Compressed[0], 0x80); + EXPECT_EQ(Compressed[1], 0x01); + EXPECT_EQ(Compressed[2], 0xff); // -128 difference => +255 in zigzag (note the + EXPECT_EQ(Compressed[3], 0x01); // varint encoding here). +} + +// Space needed to encode the biggest uintptr_t as a varint is ceil((8 / 7) * +// sizeof(uintptr_t)), as each 7 bits requires 8 bits of space. +constexpr size_t kBytesForLargestVarInt = (sizeof(uintptr_t) * 8) / 7 + 1; + +// Ensures that when the closest diff between two pointers is via. overflow, +// that we take this option. +TEST(GwpAsanCompressionTest, ClosestDiffIsOverflow) { + uint8_t Compressed[kBytesForLargestVarInt + 1]; + uintptr_t Uncompressed[2] = {UINTPTR_MAX, 0x00}; + + EXPECT_EQ(kBytesForLargestVarInt + 1, + pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t), + Compressed, sizeof(Compressed))); + for (size_t i = 0; i < kBytesForLargestVarInt - 1; ++i) { + EXPECT_EQ(Compressed[i], 0xff); + } + EXPECT_EQ(Compressed[kBytesForLargestVarInt - 1], 0x01); + // +1 difference => +2 in zigzag. + EXPECT_EQ(Compressed[kBytesForLargestVarInt], 0x02); +} + +// Ensures that when the closest diff between two pointers is via. underflow, +// we take the underflow option. +TEST(GwpAsanCompressionTest, ClosestDiffIsUnderflow) { + uint8_t Compressed[2]; + uintptr_t Uncompressed[2] = {0x00, UINTPTR_MAX}; + + EXPECT_EQ(2u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t), + Compressed, sizeof(Compressed))); + // -1 difference => +1 in zigzag. + EXPECT_EQ(Compressed[1], 0x01); +} + +void runPackUnpack(uintptr_t *Test, size_t NumEntries) { + // Setup the input/output buffers based on the maximum possible size. + uintptr_t *Uncompressed = + static_cast(alloca(NumEntries * sizeof(uintptr_t))); + size_t CompressedBufferSize = NumEntries * kBytesForLargestVarInt; + uint8_t *Compressed = static_cast(alloca(CompressedBufferSize)); + + // Pack the provided testcase, recoding the number of bytes it took for + // storage. + size_t BytesUsedForPacking = + pack(Test, NumEntries, Compressed, CompressedBufferSize); + EXPECT_NE(BytesUsedForPacking, 0u); + + // Unpack the testcase and ensure that the correct number of entries was + // unpacked. + EXPECT_EQ(NumEntries, + unpack(Compressed, BytesUsedForPacking, Uncompressed, NumEntries)); + + // Ensure that the unpacked trace is the same as the original testcase. + for (size_t i = 0; i < NumEntries; ++i) { + EXPECT_EQ(Uncompressed[i], Test[i]); + } +} + +TEST(GwpAsanCompressionTest, UncompressVarInt) { + uint8_t Compressed[] = {0x00, 0xaa, 0xaf, 0xd0, 0xda, 0x24}; + uintptr_t Uncompressed[2]; + + EXPECT_EQ(2u, unpack(Compressed, sizeof(Compressed), Uncompressed, 2u)); + EXPECT_EQ(Uncompressed[0], 0x00u); + EXPECT_EQ(Uncompressed[1], 0x125aa0bd5u); +} + +TEST(GwpAsanCompressionTest, CompressUncompressAscending) { + uintptr_t Test[] = {1, 2, 3}; + runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t)); +} + +TEST(GwpAsanCompressionTest, CompressUncompressDescending) { + uintptr_t Test[] = {3, 2, 1}; + runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t)); +} + +TEST(GwpAsanCompressionTest, CompressUncompressRepeated) { + uintptr_t Test[] = {3, 3, 3}; + runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t)); +} + +TEST(GwpAsanCompressionTest, CompressUncompressZigZag) { + uintptr_t Test[] = {1, 3, 2, 4, 1, 2}; + runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t)); +} + +TEST(GwpAsanCompressionTest, CompressUncompressVarInt) { + uintptr_t Test[] = {0x1981561, 0x18560, 0x125ab9135, 0x1232562}; + runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t)); +} + +TEST(GwpAsanCompressionTest, CompressUncompressLargestDifference) { + uintptr_t Test[] = {0x00, INTPTR_MAX, UINTPTR_MAX, INTPTR_MAX, 0x00}; + runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t)); +} + +TEST(GwpAsanCompressionTest, UncompressFailsWithOutOfBoundsVarInt) { + uint8_t Compressed[kBytesForLargestVarInt + 1]; + for (size_t i = 0; i < kBytesForLargestVarInt + 1; ++i) { + Compressed[i] = 0x80; + } + Compressed[kBytesForLargestVarInt] = 0x00; + + uintptr_t Uncompressed; + EXPECT_EQ(unpack(Compressed, kBytesForLargestVarInt + 1, &Uncompressed, 1), + 0u); +} + +TEST(GwpAsanCompressionTest, UncompressFailsWithTooSmallBuffer) { + uint8_t Compressed[] = {0x80, 0x00}; + + uintptr_t Uncompressed; + EXPECT_EQ(unpack(Compressed, 1u, &Uncompressed, 1), 0u); +} + +TEST(GwpAsanCompressionTest, CompressPartiallySucceedsWithTooSmallBuffer) { + uintptr_t Uncompressed[] = { + 0x80, // Requires 2 bytes for varint. + 0x100, // Requires two bytes for varint difference of 0x80. + 0xff, // Requires single byte for varint difference of -0x01 + }; + uint8_t Compressed[3 * kBytesForLargestVarInt]; + + // Zero and one byte buffers shouldn't encode anything (see above for size + // requirements). + EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 0u), 0u); + EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 1u), 0u); + + // Two byte buffer should hold a single varint-encoded value. + EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 2u), 2u); + + // Three bytes isn't enough to cover the first two pointers, as both take two + // bytes each to store. Expect a single value to be compressed. + EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 3u), 2u); + + // Four bytes is enough for the first two pointers to be stored. + EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 4u), 4u); + + // And five is enough for all three pointers to be stored. + EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 5u), 5u); + // And a buffer that's bigger than five bytes should still only write five + // bytes. + EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 6u), 5u); + EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 3 * kBytesForLargestVarInt), 5u); +} +} // namespace compression +} // namespace gwp_asan