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 "gtest/gtest.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 268