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 = 0xff010ff0;
56   EXPECT_EQ(5u, pack(&Uncompressed, 1u, Compressed, sizeof(Compressed)));
57   EXPECT_EQ(Compressed[0], 0xe0); // +0xff010ff0 => 0x1FE021FE0 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], 0x1f);
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, 0x24};
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], 0x125aa0bd5u);
168 }
169 
170 TEST(GwpAsanCompressionTest, CompressUncompressAscending) {
171   uintptr_t Test[] = {1, 2, 3};
172   runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t));
173 }
174 
175 TEST(GwpAsanCompressionTest, CompressUncompressDescending) {
176   uintptr_t Test[] = {3, 2, 1};
177   runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t));
178 }
179 
180 TEST(GwpAsanCompressionTest, CompressUncompressRepeated) {
181   uintptr_t Test[] = {3, 3, 3};
182   runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t));
183 }
184 
185 TEST(GwpAsanCompressionTest, CompressUncompressZigZag) {
186   uintptr_t Test[] = {1, 3, 2, 4, 1, 2};
187   runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t));
188 }
189 
190 TEST(GwpAsanCompressionTest, CompressUncompressVarInt) {
191   uintptr_t Test[] = {0x1981561, 0x18560, 0x125ab9135, 0x1232562};
192   runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t));
193 }
194 
195 TEST(GwpAsanCompressionTest, CompressUncompressLargestDifference) {
196   uintptr_t Test[] = {0x00, INTPTR_MAX, UINTPTR_MAX, INTPTR_MAX, 0x00};
197   runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t));
198 }
199 
200 TEST(GwpAsanCompressionTest, CompressUncompressBigPointers) {
201   uintptr_t Test[] = {UINTPTR_MAX, UINTPTR_MAX - 10};
202   runPackUnpack(Test, sizeof(Test) / sizeof(uintptr_t));
203 
204   uintptr_t Test2[] = {UINTPTR_MAX - 10, UINTPTR_MAX};
205   runPackUnpack(Test2, sizeof(Test2) / sizeof(uintptr_t));
206 }
207 
208 TEST(GwpAsanCompressionTest, UncompressFailsWithOutOfBoundsVarInt) {
209   uint8_t Compressed[kBytesForLargestVarInt + 1];
210   for (size_t i = 0; i < kBytesForLargestVarInt; ++i) {
211     Compressed[i] = 0x80;
212   }
213   Compressed[kBytesForLargestVarInt] = 0x00;
214 
215   uintptr_t Uncompressed;
216   EXPECT_EQ(unpack(Compressed, kBytesForLargestVarInt + 1, &Uncompressed, 1),
217             0u);
218 }
219 
220 TEST(GwpAsanCompressionTest, UncompressFailsWithTooSmallBuffer) {
221   uint8_t Compressed[] = {0x80, 0x00};
222 
223   uintptr_t Uncompressed;
224   EXPECT_EQ(unpack(Compressed, 1u, &Uncompressed, 1), 0u);
225 }
226 
227 TEST(GwpAsanCompressionTest, CompressPartiallySucceedsWithTooSmallBuffer) {
228   uintptr_t Uncompressed[] = {
229       0x80,  // Requires 2 bytes for varint.
230       0x100, // Requires two bytes for varint difference of 0x80.
231       0xff,  // Requires single byte for varint difference of -0x01
232   };
233   uint8_t Compressed[3 * kBytesForLargestVarInt];
234 
235   // Zero and one byte buffers shouldn't encode anything (see above for size
236   // requirements).
237   EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 0u), 0u);
238   EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 1u), 0u);
239 
240   // Two byte buffer should hold a single varint-encoded value.
241   EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 2u), 2u);
242 
243   // Three bytes isn't enough to cover the first two pointers, as both take two
244   // bytes each to store. Expect a single value to be compressed.
245   EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 3u), 2u);
246 
247   // Four bytes is enough for the first two pointers to be stored.
248   EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 4u), 4u);
249 
250   // And five is enough for all three pointers to be stored.
251   EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 5u), 5u);
252   // And a buffer that's bigger than five bytes should still only write five
253   // bytes.
254   EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 6u), 5u);
255   EXPECT_EQ(pack(Uncompressed, 3u, Compressed, 3 * kBytesForLargestVarInt), 5u);
256 }
257 } // namespace compression
258 } // namespace gwp_asan
259