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

source code of libc/test/src/string/memory_utils/memory_check_utils.h