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 {
PoisonedBufferPoisonedBuffer27 PoisonedBuffer(size_t size) : ptr((char *)malloc(size)) {
28 ASAN_POISON_MEMORY_REGION(ptr, size);
29 }
~PoisonedBufferPoisonedBuffer30 ~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 }
spanBuffer52 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
GetRandomChar()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.
Randomize(cpp::span<char> buffer)69 inline void Randomize(cpp::span<char> buffer) {
70 for (auto ¤t : buffer)
71 current = GetRandomChar();
72 }
73
74 // Copy one span to another.
ReferenceCopy(cpp::span<char> dst,const cpp::span<char> src)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
IsEqual(const cpp::span<char> a,const cpp::span<char> b)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>
CheckMemcpy(cpp::span<char> dst,cpp::span<char> src,size_t size)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>
CheckMemset(cpp::span<char> dst,uint8_t value,size_t size)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>
CheckBcmp(cpp::span<char> span1,cpp::span<char> span2,size_t size)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>
CheckMemcmp(cpp::span<char> span1,cpp::span<char> span2,size_t size)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
Checksum(cpp::span<char> dst)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>
CheckMemmove(cpp::span<char> dst,cpp::span<char> src)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>
CheckMemmove(cpp::span<char> buffer,size_t size,int overlap)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
205