1 //===-- Unittests for memory_utils ----------------------------------------===//
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 "src/string/memory_utils/memcpy_utils.h"
10 #include "utils/CPP/Array.h"
11 #include "utils/UnitTest/Test.h"
12
13 #include <assert.h>
14 #include <stdint.h> // uintptr_t
15
16 #ifndef LLVM_LIBC_MEMCPY_MONITOR
17 #error LLVM_LIBC_MEMCPY_MONITOR must be defined for this test.
18 #endif
19
20 namespace __llvm_libc {
21
22 struct Buffer {
23 static constexpr size_t kMaxBuffer = 1024;
24 char buffer[kMaxBuffer + 1];
25 size_t last = 0;
26
Clear__llvm_libc::Buffer27 void Clear() {
28 last = 0;
29 for (size_t i = 0; i < kMaxBuffer; ++i)
30 buffer[i] = '0';
31 buffer[kMaxBuffer] = '\0';
32 }
33
Increment__llvm_libc::Buffer34 void Increment(const void *ptr) {
35 const auto offset = reinterpret_cast<uintptr_t>(ptr);
36 assert(offset < kMaxBuffer);
37 ++buffer[offset];
38 if (offset > last)
39 last = offset;
40 }
41
Finish__llvm_libc::Buffer42 char *Finish() {
43 assert(last < kMaxBuffer);
44 buffer[last + 1] = '\0';
45 return buffer;
46 }
47 };
48
49 struct Trace {
50 Buffer read;
51 Buffer write;
52
Add__llvm_libc::Trace53 void Add(char *__restrict dst, const char *__restrict src, size_t count) {
54 for (size_t i = 0; i < count; ++i)
55 read.Increment(src + i);
56 for (size_t i = 0; i < count; ++i)
57 write.Increment(dst + i);
58 }
59
Clear__llvm_libc::Trace60 void Clear() {
61 read.Clear();
62 write.Clear();
63 }
64
Read__llvm_libc::Trace65 char *Read() { return read.Finish(); }
Write__llvm_libc::Trace66 char *Write() { return write.Finish(); }
67 };
68
GetTrace()69 static Trace &GetTrace() {
70 static thread_local Trace events;
71 return events;
72 }
73
LLVM_LIBC_MEMCPY_MONITOR(char * __restrict dst,const char * __restrict src,size_t count)74 extern "C" void LLVM_LIBC_MEMCPY_MONITOR(char *__restrict dst,
75 const char *__restrict src,
76 size_t count) {
77 GetTrace().Add(dst, src, count);
78 }
79
I(uintptr_t offset)80 char *I(uintptr_t offset) { return reinterpret_cast<char *>(offset); }
81
TEST(MemcpyUtilsTest,CopyTrivial)82 TEST(MemcpyUtilsTest, CopyTrivial) {
83 auto &trace = GetTrace();
84
85 trace.Clear();
86 CopyBlock<1>(I(0), I(0));
87 EXPECT_STREQ(trace.Write(), "1");
88 EXPECT_STREQ(trace.Read(), "1");
89
90 trace.Clear();
91 CopyBlock<2>(I(0), I(0));
92 EXPECT_STREQ(trace.Write(), "11");
93 EXPECT_STREQ(trace.Read(), "11");
94
95 trace.Clear();
96 CopyBlock<4>(I(0), I(0));
97 EXPECT_STREQ(trace.Write(), "1111");
98 EXPECT_STREQ(trace.Read(), "1111");
99
100 trace.Clear();
101 CopyBlock<8>(I(0), I(0));
102 EXPECT_STREQ(trace.Write(), "11111111");
103 EXPECT_STREQ(trace.Read(), "11111111");
104
105 trace.Clear();
106 CopyBlock<16>(I(0), I(0));
107 EXPECT_STREQ(trace.Write(), "1111111111111111");
108 EXPECT_STREQ(trace.Read(), "1111111111111111");
109
110 trace.Clear();
111 CopyBlock<32>(I(0), I(0));
112 EXPECT_STREQ(trace.Write(), "11111111111111111111111111111111");
113 EXPECT_STREQ(trace.Read(), "11111111111111111111111111111111");
114
115 trace.Clear();
116 CopyBlock<64>(I(0), I(0));
117 EXPECT_STREQ(
118 trace.Write(),
119 "1111111111111111111111111111111111111111111111111111111111111111");
120 EXPECT_STREQ(
121 trace.Read(),
122 "1111111111111111111111111111111111111111111111111111111111111111");
123 }
124
TEST(MemcpyUtilsTest,CopyOffset)125 TEST(MemcpyUtilsTest, CopyOffset) {
126 auto &trace = GetTrace();
127
128 trace.Clear();
129 CopyBlock<1>(I(3), I(1));
130 EXPECT_STREQ(trace.Write(), "0001");
131 EXPECT_STREQ(trace.Read(), "01");
132
133 trace.Clear();
134 CopyBlock<1>(I(2), I(1));
135 EXPECT_STREQ(trace.Write(), "001");
136 EXPECT_STREQ(trace.Read(), "01");
137 }
138
TEST(MemcpyUtilsTest,CopyBlockOverlap)139 TEST(MemcpyUtilsTest, CopyBlockOverlap) {
140 auto &trace = GetTrace();
141
142 trace.Clear();
143 CopyBlockOverlap<2>(I(0), I(0), 2);
144 EXPECT_STREQ(trace.Write(), "22");
145 EXPECT_STREQ(trace.Read(), "22");
146
147 trace.Clear();
148 CopyBlockOverlap<2>(I(0), I(0), 3);
149 EXPECT_STREQ(trace.Write(), "121");
150 EXPECT_STREQ(trace.Read(), "121");
151
152 trace.Clear();
153 CopyBlockOverlap<2>(I(0), I(0), 4);
154 EXPECT_STREQ(trace.Write(), "1111");
155 EXPECT_STREQ(trace.Read(), "1111");
156
157 trace.Clear();
158 CopyBlockOverlap<4>(I(2), I(1), 7);
159 EXPECT_STREQ(trace.Write(), "001112111");
160 EXPECT_STREQ(trace.Read(), "01112111");
161 }
162
TEST(MemcpyUtilsTest,CopyAlignedBlocks)163 TEST(MemcpyUtilsTest, CopyAlignedBlocks) {
164 auto &trace = GetTrace();
165 // Destination is aligned and multiple of alignment.
166 // "1111"
167 trace.Clear();
168 CopyAlignedBlocks<4>(I(0), I(0), 4);
169 EXPECT_STREQ(trace.Write(), "2222");
170 EXPECT_STREQ(trace.Read(), "2222");
171
172 // Destination is aligned and multiple of alignment.
173 // "11110000"
174 // + "00001111"
175 // = "11111111"
176 trace.Clear();
177 CopyAlignedBlocks<4>(I(0), I(0), 8);
178 EXPECT_STREQ(trace.Write(), "11111111");
179 EXPECT_STREQ(trace.Read(), "11111111");
180
181 // Destination is aligned already overlap at end.
182 // "1111000000000"
183 // + "0000111100000"
184 // + "0000000011110"
185 // + "0000000001111"
186 // = "1111111112221"
187 trace.Clear();
188 CopyAlignedBlocks<4>(I(0), I(0), 13);
189 EXPECT_STREQ(trace.Write(), "1111111112221");
190 EXPECT_STREQ(trace.Read(), "1111111112221");
191
192 // Misaligned destination.
193 // "01111000000000"
194 // + "00001111000000"
195 // + "00000000111100"
196 // + "00000000001111"
197 // = "01112111112211"
198 trace.Clear();
199 CopyAlignedBlocks<4>(I(1), I(0), 13);
200 EXPECT_STREQ(trace.Write(), "01112111112211");
201 EXPECT_STREQ(trace.Read(), "1112111112211");
202
203 // Misaligned destination aligned at end.
204 // "011110000000"
205 // + "000011110000"
206 // + "000000001111"
207 // = "011121111111"
208 trace.Clear();
209 CopyAlignedBlocks<4>(I(1), I(0), 11);
210 EXPECT_STREQ(trace.Write(), "011121111111");
211 EXPECT_STREQ(trace.Read(), "11121111111");
212 }
213
TEST(MemcpyUtilsTest,MaxReloads)214 TEST(MemcpyUtilsTest, MaxReloads) {
215 auto &trace = GetTrace();
216 for (size_t alignment = 0; alignment < 32; ++alignment) {
217 for (size_t count = 64; count < 768; ++count) {
218 trace.Clear();
219 // We should never reload more than twice when copying from count = 2x32.
220 CopyAlignedBlocks<32>(I(alignment), I(0), count);
221 const char *const written = trace.Write();
222 // First bytes are untouched.
223 for (size_t i = 0; i < alignment; ++i)
224 EXPECT_EQ(written[i], '0');
225 // Next bytes are loaded once or twice but no more.
226 for (size_t i = alignment; i < count; ++i) {
227 EXPECT_GE(written[i], '1');
228 EXPECT_LE(written[i], '2');
229 }
230 }
231 }
232 }
233
234 } // namespace __llvm_libc
235