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