271 lines · cpp
1//===-- compression.cpp -----------------------------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "gwp_asan/stack_trace_compressor.h"10#include "gwp_asan/tests/harness.h"11 12namespace gwp_asan {13namespace compression {14namespace {15 16TEST(GwpAsanCompressionTest, SingleByteVarInt) {17 uint8_t Compressed[1];18 19 uintptr_t Uncompressed = 0x00;20 EXPECT_EQ(1u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed)));21 EXPECT_EQ(Compressed[0], 0x00);22 23 Uncompressed = 0x01;24 EXPECT_EQ(1u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed)));25 EXPECT_EQ(Compressed[0], 0x02); // +1 => 2 in zigzag.26 27 Uncompressed = 0x3f;28 EXPECT_EQ(1u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed)));29 EXPECT_EQ(Compressed[0], 0x7e); // +63 => 127 in zigzag.30}31 32TEST(GwpAsanCompressionTest, MultiByteVarInt) {33 uint8_t Compressed[sizeof(uintptr_t) + 1];34 35 uintptr_t Uncompressed = 0x40;36 EXPECT_EQ(2u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed)));37 EXPECT_EQ(Compressed[0], 0x80); // +64 => 128 in zigzag.38 EXPECT_EQ(Compressed[1], 0x01);39 40 Uncompressed = 0x41;41 EXPECT_EQ(2u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed)));42 EXPECT_EQ(Compressed[0], 0x82); // +65 => 130 in zigzag43 EXPECT_EQ(Compressed[1], 0x01);44 45 Uncompressed = 0x1fff;46 EXPECT_EQ(2u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed)));47 EXPECT_EQ(Compressed[0], 0xfe); // +8191 => 16382 in zigzag48 EXPECT_EQ(Compressed[1], 0x7f);49 50 Uncompressed = 0x2000;51 EXPECT_EQ(3u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed)));52 EXPECT_EQ(Compressed[0], 0x80); // +8192 => 16384 in zigzag53 EXPECT_EQ(Compressed[1], 0x80);54 EXPECT_EQ(Compressed[2], 0x01);55 56 Uncompressed = 0x7f010ff0;57 EXPECT_EQ(5u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed)));58 EXPECT_EQ(Compressed[0], 0xe0); // +0x7f010ff0 => 0xFE021FE0 in zigzag59 EXPECT_EQ(Compressed[1], 0xbf);60 EXPECT_EQ(Compressed[2], 0x88);61 EXPECT_EQ(Compressed[3], 0xf0);62 EXPECT_EQ(Compressed[4], 0x0f);63}64 65TEST(GwpAsanCompressionTest, CorrectDifference) {66 uint8_t Compressed[10];67 uintptr_t Uncompressed[2] = {0x00, 0x00};68 69 EXPECT_EQ(2u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t),70 Compressed, sizeof(Compressed)));71 EXPECT_EQ(Compressed[1], 0x00); // +0 difference => 0 in zigzag.72 73 Uncompressed[1] = 0x01;74 EXPECT_EQ(2u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t),75 Compressed, sizeof(Compressed)));76 EXPECT_EQ(Compressed[1], 0x02); // +1 difference => 2 in zigzag.77 78 Uncompressed[1] = 0x02;79 EXPECT_EQ(2u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t),80 Compressed, sizeof(Compressed)));81 EXPECT_EQ(Compressed[1], 0x04); // +2 difference => 4 in zigzag.82 83 Uncompressed[1] = 0x80;84 EXPECT_EQ(3u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t),85 Compressed, sizeof(Compressed)));86 EXPECT_EQ(Compressed[1], 0x80); // +128 difference => +256 in zigzag (note the87 EXPECT_EQ(Compressed[2], 0x02); // varint encoding here).88 89 Uncompressed[0] = 0x01;90 Uncompressed[1] = 0x00;91 EXPECT_EQ(2u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t),92 Compressed, sizeof(Compressed)));93 EXPECT_EQ(Compressed[1], 0x01); // -1 difference => +1 in zigzag.94 95 Uncompressed[0] = 0x02;96 EXPECT_EQ(2u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t),97 Compressed, sizeof(Compressed)));98 EXPECT_EQ(Compressed[1], 0x03); // -2 difference => +3 in zigzag.99 100 Uncompressed[0] = 0x80;101 EXPECT_EQ(4u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t),102 Compressed, sizeof(Compressed)));103 EXPECT_EQ(Compressed[2], 0xff); // -128 difference => +255 in zigzag (note the104 EXPECT_EQ(Compressed[3], 0x01); // varint encoding here).105}106 107// Space needed to encode the biggest uintptr_t as a varint is ceil((8 / 7) *108// sizeof(uintptr_t)), as each 7 bits requires 8 bits of space.109constexpr size_t kBytesForLargestVarInt = (sizeof(uintptr_t) * 8) / 7 + 1;110 111// Ensures that when the closest diff between two pointers is via. underflow,112// we take the underflow option.113TEST(GwpAsanCompressionTest, ClosestDiffIsUnderflow) {114 uint8_t Compressed[2];115 uintptr_t Uncompressed[2] = {0x00, UINTPTR_MAX};116 117 EXPECT_EQ(2u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t),118 Compressed, sizeof(Compressed)));119 // -1 difference => +1 in zigzag.120 EXPECT_EQ(Compressed[1], 0x01);121}122 123// Ensures that when the closest diff between two pointers is via. overflow,124// that we take this option.125TEST(GwpAsanCompressionTest, ClosestDiffIsOverflow) {126 uint8_t Compressed[2];127 uintptr_t Uncompressed[2] = {UINTPTR_MAX, 0x00};128 129 // Note here that the first element is encoded as the difference from zero.130 EXPECT_EQ(2u, pack(Uncompressed, sizeof(Uncompressed) / sizeof(uintptr_t),131 Compressed, sizeof(Compressed)));132 // -1 difference => +1 in zigzag (the first pointer is encoded as -1).133 EXPECT_EQ(Compressed[0], 0x01);134 // +1 difference => +2 in zigzag.135 EXPECT_EQ(Compressed[1], 0x02);136}137 138void runPackUnpack(uintptr_t *Test, size_t NumEntries) {139 // Setup the input/output buffers based on the maximum possible size.140 uintptr_t *Uncompressed =141 static_cast<uintptr_t *>(alloca(NumEntries * sizeof(uintptr_t)));142 size_t CompressedBufferSize = NumEntries * kBytesForLargestVarInt;143 uint8_t *Compressed = static_cast<uint8_t *>(alloca(CompressedBufferSize));144 145 // Pack the provided testcase, recoding the number of bytes it took for146 // storage.147 size_t BytesUsedForPacking =148 pack(Test, NumEntries, Compressed, CompressedBufferSize);149 EXPECT_NE(BytesUsedForPacking, 0u);150 151 // Unpack the testcase and ensure that the correct number of entries was152 // unpacked.153 EXPECT_EQ(NumEntries,154 unpack(Compressed, BytesUsedForPacking, Uncompressed, NumEntries));155 156 // Ensure that the unpacked trace is the same as the original testcase.157 for (size_t i = 0; i < NumEntries; ++i) {158 EXPECT_EQ(Uncompressed[i], Test[i]);159 }160}161 162TEST(GwpAsanCompressionTest, UncompressVarInt) {163 uint8_t Compressed[] = {0x00, 0xaa, 0xaf, 0xd0, 0xda, 0x04};164 uintptr_t Uncompressed[2];165 166 EXPECT_EQ(2u, unpack(Compressed, sizeof(Compressed), Uncompressed, 2u));167 EXPECT_EQ(Uncompressed[0], 0x00u);168 EXPECT_EQ(Uncompressed[1], 0x25aa0bd5u);169}170 171TEST(GwpAsanCompressionTest, UncompressVarIntUnderflow) {172 uint8_t Compressed[] = {0x00, 0xab, 0xaf, 0xd0, 0xda, 0x04};173 uintptr_t Uncompressed[2];174 175 EXPECT_EQ(2u, unpack(Compressed, sizeof(Compressed), Uncompressed, 2u));176 EXPECT_EQ(Uncompressed[0], 0x00u);177 EXPECT_EQ(Uncompressed[1], UINTPTR_MAX - 0x25aa0bd5u);178}179 180TEST(GwpAsanCompressionTest, CompressUncompressAscending) {181 uintptr_t Test[] = {1, 2, 3};182 runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t));183}184 185TEST(GwpAsanCompressionTest, CompressUncompressDescending) {186 uintptr_t Test[] = {3, 2, 1};187 runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t));188}189 190TEST(GwpAsanCompressionTest, CompressUncompressRepeated) {191 uintptr_t Test[] = {3, 3, 3};192 runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t));193}194 195TEST(GwpAsanCompressionTest, CompressUncompressZigZag) {196 uintptr_t Test[] = {1, 3, 2, 4, 1, 2};197 runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t));198}199 200TEST(GwpAsanCompressionTest, CompressUncompressVarInt) {201 uintptr_t Test[] = {0x1981561, 0x18560, 0x25ab9135, 0x1232562};202 runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t));203}204 205TEST(GwpAsanCompressionTest, CompressUncompressLargestDifference) {206 uintptr_t Test[] = {0x00, INTPTR_MAX, UINTPTR_MAX, INTPTR_MAX, 0x00};207 runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t));208}209 210TEST(GwpAsanCompressionTest, CompressUncompressBigPointers) {211 uintptr_t Test[] = {UINTPTR_MAX, UINTPTR_MAX - 10};212 runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t));213 214 uintptr_t Test2[] = {UINTPTR_MAX - 10, UINTPTR_MAX};215 runPackUnpack(Test2, sizeof(Test2) / sizeof(uintptr_t));216}217 218TEST(GwpAsanCompressionTest, UncompressFailsWithOutOfBoundsVarInt) {219 uint8_t Compressed[kBytesForLargestVarInt + 1];220 for (size_t i = 0; i < kBytesForLargestVarInt; ++i) {221 Compressed[i] = 0x80;222 }223 Compressed[kBytesForLargestVarInt] = 0x00;224 225 uintptr_t Uncompressed;226 EXPECT_EQ(unpack(Compressed, kBytesForLargestVarInt + 1, &Uncompressed, 1),227 0u);228}229 230TEST(GwpAsanCompressionTest, UncompressFailsWithTooSmallBuffer) {231 uint8_t Compressed[] = {0x80, 0x00};232 233 uintptr_t Uncompressed;234 EXPECT_EQ(unpack(Compressed, 1u, &Uncompressed, 1), 0u);235}236 237TEST(GwpAsanCompressionTest, CompressPartiallySucceedsWithTooSmallBuffer) {238 uintptr_t Uncompressed[] = {239 0x80, // Requires 2 bytes for varint.240 0x100, // Requires two bytes for varint difference of 0x80.241 0xff, // Requires single byte for varint difference of -0x01242 };243 uint8_t Compressed[3 * kBytesForLargestVarInt];244 245 // Zero and one byte buffers shouldn't encode anything (see above for size246 // requirements).247 EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 0u), 0u);248 EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 1u), 0u);249 250 // Two byte buffer should hold a single varint-encoded value.251 EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 2u), 2u);252 253 // Three bytes isn't enough to cover the first two pointers, as both take two254 // bytes each to store. Expect a single value to be compressed.255 EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 3u), 2u);256 257 // Four bytes is enough for the first two pointers to be stored.258 EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 4u), 4u);259 260 // And five is enough for all three pointers to be stored.261 EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 5u), 5u);262 // And a buffer that's bigger than five bytes should still only write five263 // bytes.264 EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 6u), 5u);265 EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 3 * kBytesForLargestVarInt), 5u);266}267 268} // namespace269} // namespace compression270} // namespace gwp_asan271