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
12namespace gwp_asan {
13namespace compression {
14
15TEST(GwpAsanCompressionTest, SingleByteVarInt) {
16 uint8_t Compressed[1];
17
18 uintptr_t Uncompressed = 0x00;
19 EXPECT_EQ(1u, pack(Unpacked: &Uncompressed, UnpackedSize: 1u, Packed: Compressed, PackedMaxSize: sizeof(Compressed)));
20 EXPECT_EQ(Compressed[0], 0x00);
21
22 Uncompressed = 0x01;
23 EXPECT_EQ(1u, pack(Unpacked: &Uncompressed, UnpackedSize: 1u, Packed: Compressed, PackedMaxSize: sizeof(Compressed)));
24 EXPECT_EQ(Compressed[0], 0x02); // +1 => 2 in zigzag.
25
26 Uncompressed = 0x3f;
27 EXPECT_EQ(1u, pack(Unpacked: &Uncompressed, UnpackedSize: 1u, Packed: Compressed, PackedMaxSize: sizeof(Compressed)));
28 EXPECT_EQ(Compressed[0], 0x7e); // +63 => 127 in zigzag.
29}
30
31TEST(GwpAsanCompressionTest, MultiByteVarInt) {
32 uint8_t Compressed[sizeof(uintptr_t) + 1];
33
34 uintptr_t Uncompressed = 0x40;
35 EXPECT_EQ(2u, pack(Unpacked: &Uncompressed, UnpackedSize: 1u, Packed: Compressed, PackedMaxSize: 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(Unpacked: &Uncompressed, UnpackedSize: 1u, Packed: Compressed, PackedMaxSize: 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(Unpacked: &Uncompressed, UnpackedSize: 1u, Packed: Compressed, PackedMaxSize: 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(Unpacked: &Uncompressed, UnpackedSize: 1u, Packed: Compressed, PackedMaxSize: 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(Unpacked: &Uncompressed, UnpackedSize: 1u, Packed: Compressed, PackedMaxSize: 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
64TEST(GwpAsanCompressionTest, CorrectDifference) {
65 uint8_t Compressed[10];
66 uintptr_t Uncompressed[2] = {0x00, 0x00};
67
68 EXPECT_EQ(2u, pack(Unpacked: Uncompressed, UnpackedSize: sizeof(Uncompressed) / sizeof(uintptr_t),
69 Packed: Compressed, PackedMaxSize: sizeof(Compressed)));
70 EXPECT_EQ(Compressed[1], 0x00); // +0 difference => 0 in zigzag.
71
72 Uncompressed[1] = 0x01;
73 EXPECT_EQ(2u, pack(Unpacked: Uncompressed, UnpackedSize: sizeof(Uncompressed) / sizeof(uintptr_t),
74 Packed: Compressed, PackedMaxSize: sizeof(Compressed)));
75 EXPECT_EQ(Compressed[1], 0x02); // +1 difference => 2 in zigzag.
76
77 Uncompressed[1] = 0x02;
78 EXPECT_EQ(2u, pack(Unpacked: Uncompressed, UnpackedSize: sizeof(Uncompressed) / sizeof(uintptr_t),
79 Packed: Compressed, PackedMaxSize: sizeof(Compressed)));
80 EXPECT_EQ(Compressed[1], 0x04); // +2 difference => 4 in zigzag.
81
82 Uncompressed[1] = 0x80;
83 EXPECT_EQ(3u, pack(Unpacked: Uncompressed, UnpackedSize: sizeof(Uncompressed) / sizeof(uintptr_t),
84 Packed: Compressed, PackedMaxSize: 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(Unpacked: Uncompressed, UnpackedSize: sizeof(Uncompressed) / sizeof(uintptr_t),
91 Packed: Compressed, PackedMaxSize: sizeof(Compressed)));
92 EXPECT_EQ(Compressed[1], 0x01); // -1 difference => +1 in zigzag.
93
94 Uncompressed[0] = 0x02;
95 EXPECT_EQ(2u, pack(Unpacked: Uncompressed, UnpackedSize: sizeof(Uncompressed) / sizeof(uintptr_t),
96 Packed: Compressed, PackedMaxSize: sizeof(Compressed)));
97 EXPECT_EQ(Compressed[1], 0x03); // -2 difference => +3 in zigzag.
98
99 Uncompressed[0] = 0x80;
100 EXPECT_EQ(4u, pack(Unpacked: Uncompressed, UnpackedSize: sizeof(Uncompressed) / sizeof(uintptr_t),
101 Packed: Compressed, PackedMaxSize: 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.
108constexpr 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.
112TEST(GwpAsanCompressionTest, ClosestDiffIsUnderflow) {
113 uint8_t Compressed[2];
114 uintptr_t Uncompressed[2] = {0x00, UINTPTR_MAX};
115
116 EXPECT_EQ(2u, pack(Unpacked: Uncompressed, UnpackedSize: sizeof(Uncompressed) / sizeof(uintptr_t),
117 Packed: Compressed, PackedMaxSize: 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.
124TEST(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(Unpacked: Uncompressed, UnpackedSize: sizeof(Uncompressed) / sizeof(uintptr_t),
130 Packed: Compressed, PackedMaxSize: 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
137void 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(Unpacked: Test, UnpackedSize: NumEntries, Packed: Compressed, PackedMaxSize: 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(Packed: Compressed, PackedSize: BytesUsedForPacking, Unpacked: Uncompressed, UnpackedMaxSize: 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
161TEST(GwpAsanCompressionTest, UncompressVarInt) {
162 uint8_t Compressed[] = {0x00, 0xaa, 0xaf, 0xd0, 0xda, 0x04};
163 uintptr_t Uncompressed[2];
164
165 EXPECT_EQ(2u, unpack(Packed: Compressed, PackedSize: sizeof(Compressed), Unpacked: Uncompressed, UnpackedMaxSize: 2u));
166 EXPECT_EQ(Uncompressed[0], 0x00u);
167 EXPECT_EQ(Uncompressed[1], 0x25aa0bd5u);
168}
169
170TEST(GwpAsanCompressionTest, UncompressVarIntUnderflow) {
171 uint8_t Compressed[] = {0x00, 0xab, 0xaf, 0xd0, 0xda, 0x04};
172 uintptr_t Uncompressed[2];
173
174 EXPECT_EQ(2u, unpack(Packed: Compressed, PackedSize: sizeof(Compressed), Unpacked: Uncompressed, UnpackedMaxSize: 2u));
175 EXPECT_EQ(Uncompressed[0], 0x00u);
176 EXPECT_EQ(Uncompressed[1], UINTPTR_MAX - 0x25aa0bd5u);
177}
178
179TEST(GwpAsanCompressionTest, CompressUncompressAscending) {
180 uintptr_t Test[] = {1, 2, 3};
181 runPackUnpack(Test, NumEntries: sizeof(Test) / sizeof(uintptr_t));
182}
183
184TEST(GwpAsanCompressionTest, CompressUncompressDescending) {
185 uintptr_t Test[] = {3, 2, 1};
186 runPackUnpack(Test, NumEntries: sizeof(Test) / sizeof(uintptr_t));
187}
188
189TEST(GwpAsanCompressionTest, CompressUncompressRepeated) {
190 uintptr_t Test[] = {3, 3, 3};
191 runPackUnpack(Test, NumEntries: sizeof(Test) / sizeof(uintptr_t));
192}
193
194TEST(GwpAsanCompressionTest, CompressUncompressZigZag) {
195 uintptr_t Test[] = {1, 3, 2, 4, 1, 2};
196 runPackUnpack(Test, NumEntries: sizeof(Test) / sizeof(uintptr_t));
197}
198
199TEST(GwpAsanCompressionTest, CompressUncompressVarInt) {
200 uintptr_t Test[] = {0x1981561, 0x18560, 0x25ab9135, 0x1232562};
201 runPackUnpack(Test, NumEntries: sizeof(Test) / sizeof(uintptr_t));
202}
203
204TEST(GwpAsanCompressionTest, CompressUncompressLargestDifference) {
205 uintptr_t Test[] = {0x00, INTPTR_MAX, UINTPTR_MAX, INTPTR_MAX, 0x00};
206 runPackUnpack(Test, NumEntries: sizeof(Test) / sizeof(uintptr_t));
207}
208
209TEST(GwpAsanCompressionTest, CompressUncompressBigPointers) {
210 uintptr_t Test[] = {UINTPTR_MAX, UINTPTR_MAX - 10};
211 runPackUnpack(Test, NumEntries: sizeof(Test) / sizeof(uintptr_t));
212
213 uintptr_t Test2[] = {UINTPTR_MAX - 10, UINTPTR_MAX};
214 runPackUnpack(Test: Test2, NumEntries: sizeof(Test2) / sizeof(uintptr_t));
215}
216
217TEST(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(Packed: Compressed, PackedSize: kBytesForLargestVarInt + 1, Unpacked: &Uncompressed, UnpackedMaxSize: 1),
226 0u);
227}
228
229TEST(GwpAsanCompressionTest, UncompressFailsWithTooSmallBuffer) {
230 uint8_t Compressed[] = {0x80, 0x00};
231
232 uintptr_t Uncompressed;
233 EXPECT_EQ(unpack(Packed: Compressed, PackedSize: 1u, Unpacked: &Uncompressed, UnpackedMaxSize: 1), 0u);
234}
235
236TEST(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(Unpacked: Uncompressed, UnpackedSize: 3u, Packed: Compressed, PackedMaxSize: 0u), 0u);
247 EXPECT_EQ(pack(Unpacked: Uncompressed, UnpackedSize: 3u, Packed: Compressed, PackedMaxSize: 1u), 0u);
248
249 // Two byte buffer should hold a single varint-encoded value.
250 EXPECT_EQ(pack(Unpacked: Uncompressed, UnpackedSize: 3u, Packed: Compressed, PackedMaxSize: 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(Unpacked: Uncompressed, UnpackedSize: 3u, Packed: Compressed, PackedMaxSize: 3u), 2u);
255
256 // Four bytes is enough for the first two pointers to be stored.
257 EXPECT_EQ(pack(Unpacked: Uncompressed, UnpackedSize: 3u, Packed: Compressed, PackedMaxSize: 4u), 4u);
258
259 // And five is enough for all three pointers to be stored.
260 EXPECT_EQ(pack(Unpacked: Uncompressed, UnpackedSize: 3u, Packed: Compressed, PackedMaxSize: 5u), 5u);
261 // And a buffer that's bigger than five bytes should still only write five
262 // bytes.
263 EXPECT_EQ(pack(Unpacked: Uncompressed, UnpackedSize: 3u, Packed: Compressed, PackedMaxSize: 6u), 5u);
264 EXPECT_EQ(pack(Unpacked: Uncompressed, UnpackedSize: 3u, Packed: Compressed, PackedMaxSize: 3 * kBytesForLargestVarInt), 5u);
265}
266} // namespace compression
267} // namespace gwp_asan
268

source code of compiler-rt/lib/gwp_asan/tests/compression.cpp