compiler-rt/test/asan/TestCases/contiguous_container.cpp

   1 // RUN: %clangxx_asan -fexceptions -O %s -o %t && %env_asan_opts=detect_stack_use_after_return=0 %run %t
   2 //
   3 // Test __sanitizer_annotate_contiguous_container.
   4
   5 #include <algorithm>
   6 #include <numeric>
   7 #include <vector>
   8
   9 #include <assert.h>
  10 #include <sanitizer/asan_interface.h>
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13 #include <string.h>
  14
  15 static constexpr size_t kGranularity = 8;
  16
  17 template <class T> static constexpr T RoundDown(T x) {
  18   return reinterpret_cast<T>(reinterpret_cast<uintptr_t>(x) &
  19                              ~(kGranularity - 1));
  20 }
  21
  22 static std::vector<int> GetPoisonedState(char *begin, char *end) {
  23   std::vector<int> result;
  24   for (; begin != end;) {
  25     int poisoned = 0;
  26     for (; begin != end && __asan_address_is_poisoned(begin); ++begin)
  27       ++poisoned;
  28     result.push_back(poisoned);
  29     int unpoisoned = 0;
  30     for (; begin != end && !__asan_address_is_poisoned(begin); ++begin)
  31       ++unpoisoned;
  32     result.push_back(unpoisoned);
  33   }
  34   return result;
  35 }
  36
  37 static int GetFirstMismatch(const std::vector<int> &a,
  38                             const std::vector<int> &b) {
  39   auto mismatch = std::mismatch(a.begin(), a.end(), b.begin(), b.end());
  40   return std::accumulate(a.begin(), mismatch.first, 0) +
  41          std::min(*mismatch.first, *mismatch.second);
  42 }
  43
  44 void TestContainer(size_t capacity, size_t off_begin, bool poison_buffer) {
  45   size_t buffer_size = capacity + off_begin + kGranularity * 2;
  46   char *buffer = new char[buffer_size];
  47   if (poison_buffer)
  48     __asan_poison_memory_region(buffer, buffer_size);
  49   char *st_beg = buffer + off_begin;
  50   char *st_end = st_beg + capacity;
  51   char *end = poison_buffer ? st_beg : st_end;
  52
  53   for (int i = 0; i < 1000; i++) {
  54     size_t size = rand() % (capacity + 1);
  55     assert(size <= capacity);
  56     char *old_end = end;
  57     end = st_beg + size;
  58     __sanitizer_annotate_contiguous_container(st_beg, st_end, old_end, end);
  59
  60     char *cur = buffer;
  61     for (; cur < RoundDown(st_beg); ++cur)
  62       assert(__asan_address_is_poisoned(cur) == poison_buffer);
  63     // The prefix of the first incomplete granule can switch from poisoned to
  64     // unpoisoned but not otherwise.
  65     for (; cur < st_beg; ++cur)
  66       assert(poison_buffer || !__asan_address_is_poisoned(cur));
  67     for (; cur < end; ++cur)
  68       assert(!__asan_address_is_poisoned(cur));
  69     for (; cur < RoundDown(st_end); ++cur)
  70       assert(__asan_address_is_poisoned(cur));
  71     // The suffix of the last incomplete granule must be poisoned the same as
  72     // bytes after the end.
  73     for (; cur != st_end + kGranularity; ++cur)
  74       assert(__asan_address_is_poisoned(cur) == poison_buffer);
  75   }
  76
  77   // Precalculate masks.
  78   std::vector<std::vector<int>> masks(capacity + 1);
  79   for (int i = 0; i <= capacity; i++) {
  80     char *old_end = end;
  81     end = st_beg + i;
  82     __sanitizer_annotate_contiguous_container(st_beg, st_end, old_end, end);
  83     masks[i] = GetPoisonedState(st_beg, st_end);
  84   }
  85   for (int i = 0; i <= capacity; i++) {
  86     char *old_end = end;
  87     end = st_beg + i;
  88     __sanitizer_annotate_contiguous_container(st_beg, st_end, old_end, end);
  89
  90     char *cur_first = std::max(end - 2 * kGranularity, st_beg);
  91     char *cur_last = std::min(end + 2 * kGranularity, st_end);
  92     for (char *cur = cur_first; cur <= cur_last; ++cur) {
  93       bool is_valid =
  94           __sanitizer_verify_contiguous_container(st_beg, cur, st_end);
  95       const void *bad_address =
  96           __sanitizer_contiguous_container_find_bad_address(st_beg, cur,
  97                                                             st_end);
  98       if (cur == end ||
  99           // The last unaligned granule of the storage followed by unpoisoned
 100           // bytes looks the same.
 101           (!poison_buffer && RoundDown(st_end) <= std::min(cur, end))) {
 102         assert(is_valid);
 103         assert(!bad_address);
 104         continue;
 105       }
 106       assert(!is_valid);
 107       assert(bad_address == std::min(cur, end));
 108       assert(bad_address ==
 109              st_beg + GetFirstMismatch(masks[i], masks[cur - st_beg]));
 110     }
 111   }
 112
 113   __asan_unpoison_memory_region(buffer, buffer_size);
 114   delete[] buffer;
 115 }
 116
 117 void TestDoubleEndedContainer(size_t capacity, size_t off_begin,
 118                               bool poison_buffer) {
 119   size_t buffer_size = capacity + off_begin + kGranularity * 2;
 120   char *buffer = new char[buffer_size];
 121   if (poison_buffer)
 122     __asan_poison_memory_region(buffer, buffer_size);
 123   char *st_beg = buffer + off_begin;
 124   char *st_end = st_beg + capacity;
 125   char *beg = st_beg;
 126   char *end = poison_buffer ? st_beg : st_end;
 127
 128   for (int i = 0; i < 1000; i++) {
 129     size_t size = rand() % (capacity + 1);
 130     size_t skipped = rand() % (capacity - size + 1);
 131     assert(size <= capacity);
 132     char *old_beg = beg;
 133     char *old_end = end;
 134     beg = st_beg + skipped;
 135     end = beg + size;
 136
 137     __sanitizer_annotate_double_ended_contiguous_container(
 138         st_beg, st_end, old_beg, old_end, beg, end);
 139
 140     char *cur = buffer;
 141     for (; cur < RoundDown(st_beg); ++cur)
 142       assert(__asan_address_is_poisoned(cur) == poison_buffer);
 143     // The prefix of the first incomplete granule can switch from poisoned to
 144     // unpoisoned but not otherwise.
 145     for (; cur < st_beg; ++cur)
 146       assert(poison_buffer || !__asan_address_is_poisoned(cur));
 147     if (beg != end) {
 148       for (; cur < RoundDown(beg); ++cur)
 149         assert(__asan_address_is_poisoned(cur));
 150
 151       for (; cur < end; ++cur)
 152         assert(!__asan_address_is_poisoned(cur));
 153     }
 154     for (; cur < RoundDown(st_end); ++cur)
 155       assert(__asan_address_is_poisoned(cur));
 156     // The suffix of the last incomplete granule must be poisoned the same as
 157     // bytes after the end.
 158     for (; cur != st_end + kGranularity; ++cur)
 159       assert(__asan_address_is_poisoned(cur) == poison_buffer);
 160   }
 161
 162   if (capacity < 32) {
 163
 164     // Precalculate masks.
 165     std::vector<std::vector<std::vector<int>>> masks(
 166         capacity + 1, std::vector<std::vector<int>>(capacity + 1));
 167     for (int i = 0; i <= capacity; i++) {
 168       for (int j = i; j <= capacity; j++) {
 169         char *old_beg = beg;
 170         char *old_end = end;
 171         beg = st_beg + i;
 172         end = st_beg + j;
 173         __sanitizer_annotate_double_ended_contiguous_container(
 174             st_beg, st_end, old_beg, old_end, beg, end);
 175         masks[i][j] = GetPoisonedState(st_beg, st_end);
 176       }
 177     }
 178
 179     for (int i = 0; i <= capacity; i++) {
 180       for (int j = i; j <= capacity; j++) {
 181         char *old_beg = beg;
 182         char *old_end = end;
 183         beg = st_beg + i;
 184         end = st_beg + j;
 185         __sanitizer_annotate_double_ended_contiguous_container(
 186             st_beg, st_end, old_beg, old_end, beg, end);
 187
 188         // Try to mismatch the end of the container.
 189         char *cur_first = std::max(end - 2 * kGranularity, beg);
 190         char *cur_last = std::min(end + 2 * kGranularity, st_end);
 191         for (char *cur = cur_first; cur <= cur_last; ++cur) {
 192           bool is_valid = __sanitizer_verify_double_ended_contiguous_container(
 193               st_beg, beg, cur, st_end);
 194           const void *bad_address =
 195               __sanitizer_double_ended_contiguous_container_find_bad_address(
 196                   st_beg, beg, cur, st_end);
 197
 198           if (cur == end ||
 199               // The last unaligned granule of the storage followed by unpoisoned
 200               // bytes looks the same.
 201               (!poison_buffer && RoundDown(st_end) <= std::min(cur, end))) {
 202             assert(is_valid);
 203             assert(!bad_address);
 204             continue;
 205           }
 206
 207           assert(!is_valid);
 208           assert(bad_address);
 209           assert(bad_address ==
 210                  st_beg +
 211                      GetFirstMismatch(masks[i][j], masks[i][cur - st_beg]));
 212         }
 213
 214         // Try to mismatch the begin of the container.
 215         cur_first = std::max(beg - 2 * kGranularity, st_beg);
 216         cur_last = std::min(beg + 2 * kGranularity, end);
 217         for (char *cur = cur_first; cur <= cur_last; ++cur) {
 218           bool is_valid = __sanitizer_verify_double_ended_contiguous_container(
 219               st_beg, cur, end, st_end);
 220           const void *bad_address =
 221               __sanitizer_double_ended_contiguous_container_find_bad_address(
 222                   st_beg, cur, end, st_end);
 223
 224           if (cur == beg ||
 225               // The last unaligned granule of the storage followed by unpoisoned
 226               // bytes looks the same.
 227               (!poison_buffer && RoundDown(st_end) <= std::min(cur, beg) ||
 228                // The first unaligned granule of non-empty container looks the
 229                // same.
 230                (std::max(beg, cur) < end &&
 231                 RoundDown(beg) == RoundDown(cur)))) {
 232             assert(is_valid);
 233             assert(!bad_address);
 234             continue;
 235           }
 236           assert(!is_valid);
 237           assert(bad_address);
 238           assert(bad_address ==
 239                  st_beg +
 240                      GetFirstMismatch(masks[i][j], masks[cur - st_beg][j]));
 241         }
 242       }
 243     }
 244   }
 245
 246   __asan_unpoison_memory_region(buffer, buffer_size);
 247   delete[] buffer;
 248 }
 249
 250 __attribute__((noinline)) void Throw() { throw 1; }
 251
 252 __attribute__((noinline)) void ThrowAndCatch() {
 253   try {
 254     Throw();
 255   } catch (...) {
 256   }
 257 }
 258
 259 void TestThrow() {
 260   char x[32];
 261   __sanitizer_annotate_contiguous_container(x, x + 32, x + 32, x + 14);
 262   assert(!__asan_address_is_poisoned(x + 13));
 263   assert(__asan_address_is_poisoned(x + 14));
 264   ThrowAndCatch();
 265   assert(!__asan_address_is_poisoned(x + 13));
 266   assert(!__asan_address_is_poisoned(x + 14));
 267   __sanitizer_annotate_contiguous_container(x, x + 32, x + 14, x + 32);
 268   assert(!__asan_address_is_poisoned(x + 13));
 269   assert(!__asan_address_is_poisoned(x + 14));
 270 }
 271
 272 int main(int argc, char **argv) {
 273   int n = argc == 1 ? 64 : atoi(argv[1]);
 274   for (int i = 0; i <= n; i++) {
 275     for (int j = 0; j < kGranularity * 2; j++) {
 276       for (int poison = 0; poison < 2; ++poison) {
 277         TestContainer(i, j, poison);
 278         TestDoubleEndedContainer(i, j, poison);
 279       }
 280     }
 281   }
 282   TestThrow();
 283 }