libc/test/src/string/memory_utils/memory_check_utils.h

   1 //===-- Utils to test conformance of mem functions ------------------------===//
   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 #ifndef LIBC_TEST_SRC_STRING_MEMORY_UTILS_MEMORY_CHECK_UTILS_H
  10 #define LIBC_TEST_SRC_STRING_MEMORY_UTILS_MEMORY_CHECK_UTILS_H
  11
  12 #include "src/__support/CPP/span.h"
  13 #include "src/__support/libc_assert.h" // LIBC_ASSERT
  14 #include "src/__support/macros/config.h"
  15 #include "src/__support/macros/sanitizer.h"
  16 #include "src/string/memory_utils/utils.h"
  17 #include <stddef.h> // size_t
  18 #include <stdint.h> // uintxx_t
  19 #include <stdlib.h> // malloc/free
  20
  21 namespace LIBC_NAMESPACE_DECL {
  22
  23 // Simple structure to allocate a buffer of a particular size.
  24 // When ASAN is present it also poisons the whole memory.
  25 // This is a utility class to be used by Buffer below, do not use directly.
  26 struct PoisonedBuffer {
  27   PoisonedBuffer(size_t size) : ptr((char *)malloc(size)) {
  28     ASAN_POISON_MEMORY_REGION(ptr, size);
  29   }
  30   ~PoisonedBuffer() { free(ptr); }
  31
  32 protected:
  33   char *ptr = nullptr;
  34 };
  35
  36 // Simple structure to allocate a buffer (aligned or not) of a particular size.
  37 // It is backed by a wider buffer that is marked poisoned when ASAN is present.
  38 // The requested region is unpoisoned, this allows catching out of bounds
  39 // accesses.
  40 enum class Aligned : bool { NO = false, YES = true };
  41 struct Buffer : private PoisonedBuffer {
  42   static constexpr size_t kAlign = 64;
  43   static constexpr size_t kLeeway = 2 * kAlign;
  44   Buffer(size_t size, Aligned aligned = Aligned::YES)
  45       : PoisonedBuffer(size + kLeeway), size(size) {
  46     offset_ptr = ptr;
  47     offset_ptr += distance_to_next_aligned<kAlign>(ptr);
  48     if (aligned == Aligned::NO)
  49       ++offset_ptr;
  50     ASAN_UNPOISON_MEMORY_REGION(offset_ptr, size);
  51   }
  52   cpp::span<char> span() { return cpp::span<char>(offset_ptr, size); }
  53
  54 private:
  55   size_t size = 0;
  56   char *offset_ptr = nullptr;
  57 };
  58
  59 inline char GetRandomChar() {
  60   static constexpr const uint64_t a = 1103515245;
  61   static constexpr const uint64_t c = 12345;
  62   static constexpr const uint64_t m = 1ULL << 31;
  63   static uint64_t seed = 123456789;
  64   seed = (a * seed + c) % m;
  65   return static_cast<char>(seed);
  66 }
  67
  68 // Randomize the content of the buffer.
  69 inline void Randomize(cpp::span<char> buffer) {
  70   for (auto &current : buffer)
  71     current = GetRandomChar();
  72 }
  73
  74 // Copy one span to another.
  75 inline void ReferenceCopy(cpp::span<char> dst, const cpp::span<char> src) {
  76   for (size_t i = 0; i < dst.size(); ++i)
  77     dst[i] = src[i];
  78 }
  79
  80 inline bool IsEqual(const cpp::span<char> a, const cpp::span<char> b) {
  81   LIBC_ASSERT(a.size() == b.size());
  82   for (size_t i = 0; i < a.size(); ++i)
  83     if (a[i] != b[i])
  84       return false;
  85   return true;
  86 }
  87
  88 // Checks that FnImpl implements the memcpy semantic.
  89 template <auto FnImpl>
  90 inline bool CheckMemcpy(cpp::span<char> dst, cpp::span<char> src, size_t size) {
  91   Randomize(dst);
  92   FnImpl(dst, src, size);
  93   return IsEqual(dst, src);
  94 }
  95
  96 // Checks that FnImpl implements the memset semantic.
  97 template <auto FnImpl>
  98 inline bool CheckMemset(cpp::span<char> dst, uint8_t value, size_t size) {
  99   Randomize(dst);
 100   FnImpl(dst, value, size);
 101   for (char c : dst)
 102     if (c != (char)value)
 103       return false;
 104   return true;
 105 }
 106
 107 // Checks that FnImpl implements the bcmp semantic.
 108 template <auto FnImpl>
 109 inline bool CheckBcmp(cpp::span<char> span1, cpp::span<char> span2,
 110                       size_t size) {
 111   ReferenceCopy(span2, span1);
 112   // Compare equal
 113   if (int cmp = FnImpl(span1, span2, size); cmp != 0)
 114     return false;
 115   // Compare not equal if any byte differs
 116   for (size_t i = 0; i < size; ++i) {
 117     ++span2[i];
 118     if (int cmp = FnImpl(span1, span2, size); cmp == 0)
 119       return false;
 120     if (int cmp = FnImpl(span2, span1, size); cmp == 0)
 121       return false;
 122     --span2[i];
 123   }
 124   return true;
 125 }
 126
 127 // Checks that FnImpl implements the memcmp semantic.
 128 template <auto FnImpl>
 129 inline bool CheckMemcmp(cpp::span<char> span1, cpp::span<char> span2,
 130                         size_t size) {
 131   ReferenceCopy(span2, span1);
 132   // Compare equal
 133   if (int cmp = FnImpl(span1, span2, size); cmp != 0)
 134     return false;
 135   // Compare not equal if any byte differs
 136   for (size_t i = 0; i < size; ++i) {
 137     ++span2[i];
 138     int ground_truth = __builtin_memcmp(span1.data(), span2.data(), size);
 139     if (ground_truth > 0) {
 140       if (int cmp = FnImpl(span1, span2, size); cmp <= 0)
 141         return false;
 142       if (int cmp = FnImpl(span2, span1, size); cmp >= 0)
 143         return false;
 144     } else {
 145       if (int cmp = FnImpl(span1, span2, size); cmp >= 0)
 146         return false;
 147       if (int cmp = FnImpl(span2, span1, size); cmp <= 0)
 148         return false;
 149     }
 150     --span2[i];
 151   }
 152   return true;
 153 }
 154
 155 inline uint16_t Checksum(cpp::span<char> dst) {
 156   // We use Fletcher16 as it is trivial to implement.
 157   uint16_t sum1 = 0;
 158   uint16_t sum2 = 0;
 159   for (char c : dst) {
 160     sum1 = (sum1 + c) % 255U;
 161     sum2 = (sum2 + sum1) % 255U;
 162   }
 163   return static_cast<uint16_t>((sum2 << 8) | sum1);
 164 }
 165
 166 template <auto FnImpl>
 167 inline bool CheckMemmove(cpp::span<char> dst, cpp::span<char> src) {
 168   LIBC_ASSERT(dst.size() == src.size());
 169   // Memmove can override the src buffer. Technically we should save it into a
 170   // temporary buffer so we can check that 'dst' is equal to what 'src' was
 171   // before we called the function. To save on allocation and copy we use a
 172   // checksum instead.
 173   const auto src_checksum = Checksum(src);
 174   FnImpl(dst, src, dst.size());
 175   return Checksum(dst) == src_checksum;
 176 }
 177
 178 // Checks that FnImpl implements the memmove semantic.
 179 //  - Buffer size should be greater than 2 * size + 1.
 180 //  - Overlap refers to the number of bytes in common between the two buffers:
 181 //    - Negative means buffers are disjoint
 182 //    - zero mean they overlap exactly
 183 //  - Caller is responsible for randomizing the buffer.
 184 template <auto FnImpl>
 185 inline bool CheckMemmove(cpp::span<char> buffer, size_t size, int overlap) {
 186   LIBC_ASSERT(buffer.size() > (2 * size + 1));
 187   const size_t half_size = buffer.size() / 2;
 188   LIBC_ASSERT((size_t)(overlap >= 0 ? overlap : -overlap) < half_size);
 189   cpp::span<char> head = buffer.first(half_size + overlap).last(size);
 190   cpp::span<char> tail = buffer.last(half_size).first(size);
 191   LIBC_ASSERT(head.size() == size);
 192   LIBC_ASSERT(tail.size() == size);
 193   // dst before src
 194   if (!CheckMemmove<FnImpl>(head, tail))
 195     return false;
 196   // dst after src
 197   if (!CheckMemmove<FnImpl>(tail, head))
 198     return false;
 199   return true;
 200 }
 201
 202 } // namespace LIBC_NAMESPACE_DECL
 203
 204 #endif // LIBC_TEST_SRC_STRING_MEMORY_UTILS_MEMORY_CHECK_UTILS_H