compiler-rt/lib/gwp_asan/tests/compression.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-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