1#include "test_helpers.h"
2#include "xray_segmented_array.h"
3#include "gmock/gmock.h"
4#include "gtest/gtest.h"
5#include <algorithm>
6#include <numeric>
7#include <vector>
8
9namespace __xray {
10namespace {
11
12using ::testing::SizeIs;
13
14struct TestData {
15 s64 First;
16 s64 Second;
17
18 // Need a constructor for emplace operations.
19 TestData(s64 F, s64 S) : First(F), Second(S) {}
20};
21
22void PrintTo(const TestData &D, std::ostream *OS) {
23 *OS << "{ " << D.First << ", " << D.Second << " }";
24}
25
26TEST(SegmentedArrayTest, ConstructWithAllocators) {
27 using AllocatorType = typename Array<TestData>::AllocatorType;
28 AllocatorType A(1 << 4);
29 Array<TestData> Data(A);
30 (void)Data;
31}
32
33TEST(SegmentedArrayTest, ConstructAndPopulate) {
34 using AllocatorType = typename Array<TestData>::AllocatorType;
35 AllocatorType A(1 << 4);
36 Array<TestData> data(A);
37 ASSERT_NE(data.Append(E: TestData{0, 0}), nullptr);
38 ASSERT_NE(data.Append(E: TestData{1, 1}), nullptr);
39 ASSERT_EQ(data.size(), 2u);
40}
41
42TEST(SegmentedArrayTest, ConstructPopulateAndLookup) {
43 using AllocatorType = typename Array<TestData>::AllocatorType;
44 AllocatorType A(1 << 4);
45 Array<TestData> data(A);
46 ASSERT_NE(data.Append(E: TestData{0, 1}), nullptr);
47 ASSERT_EQ(data.size(), 1u);
48 ASSERT_EQ(data[0].First, 0);
49 ASSERT_EQ(data[0].Second, 1);
50}
51
52TEST(SegmentedArrayTest, PopulateWithMoreElements) {
53 using AllocatorType = typename Array<TestData>::AllocatorType;
54 AllocatorType A(1 << 24);
55 Array<TestData> data(A);
56 static const auto kMaxElements = 100u;
57 for (auto I = 0u; I < kMaxElements; ++I) {
58 ASSERT_NE(data.Append(E: TestData{I, I + 1}), nullptr);
59 }
60 ASSERT_EQ(data.size(), kMaxElements);
61 for (auto I = 0u; I < kMaxElements; ++I) {
62 ASSERT_EQ(data[I].First, I);
63 ASSERT_EQ(data[I].Second, I + 1);
64 }
65}
66
67TEST(SegmentedArrayTest, AppendEmplace) {
68 using AllocatorType = typename Array<TestData>::AllocatorType;
69 AllocatorType A(1 << 4);
70 Array<TestData> data(A);
71 ASSERT_NE(data.AppendEmplace(args: 1, args: 1), nullptr);
72 ASSERT_EQ(data[0].First, 1);
73 ASSERT_EQ(data[0].Second, 1);
74}
75
76TEST(SegmentedArrayTest, AppendAndTrim) {
77 using AllocatorType = typename Array<TestData>::AllocatorType;
78 AllocatorType A(1 << 4);
79 Array<TestData> data(A);
80 ASSERT_NE(data.AppendEmplace(args: 1, args: 1), nullptr);
81 ASSERT_EQ(data.size(), 1u);
82 data.trim(Elements: 1);
83 ASSERT_EQ(data.size(), 0u);
84 ASSERT_TRUE(data.empty());
85}
86
87TEST(SegmentedArrayTest, IteratorAdvance) {
88 using AllocatorType = typename Array<TestData>::AllocatorType;
89 AllocatorType A(1 << 4);
90 Array<TestData> data(A);
91 ASSERT_TRUE(data.empty());
92 ASSERT_EQ(data.begin(), data.end());
93 auto I0 = data.begin();
94 ASSERT_EQ(I0++, data.begin());
95 ASSERT_NE(I0, data.begin());
96 for (const auto &D : data) {
97 (void)D;
98 FAIL();
99 }
100 ASSERT_NE(data.AppendEmplace(args: 1, args: 1), nullptr);
101 ASSERT_EQ(data.size(), 1u);
102 ASSERT_NE(data.begin(), data.end());
103 auto &D0 = *data.begin();
104 ASSERT_EQ(D0.First, 1);
105 ASSERT_EQ(D0.Second, 1);
106}
107
108TEST(SegmentedArrayTest, IteratorRetreat) {
109 using AllocatorType = typename Array<TestData>::AllocatorType;
110 AllocatorType A(1 << 4);
111 Array<TestData> data(A);
112 ASSERT_TRUE(data.empty());
113 ASSERT_EQ(data.begin(), data.end());
114 ASSERT_NE(data.AppendEmplace(args: 1, args: 1), nullptr);
115 ASSERT_EQ(data.size(), 1u);
116 ASSERT_NE(data.begin(), data.end());
117 auto &D0 = *data.begin();
118 ASSERT_EQ(D0.First, 1);
119 ASSERT_EQ(D0.Second, 1);
120
121 auto I0 = data.end();
122 ASSERT_EQ(I0--, data.end());
123 ASSERT_NE(I0, data.end());
124 ASSERT_EQ(I0, data.begin());
125 ASSERT_EQ(I0->First, 1);
126 ASSERT_EQ(I0->Second, 1);
127}
128
129TEST(SegmentedArrayTest, IteratorTrimBehaviour) {
130 using AllocatorType = typename Array<TestData>::AllocatorType;
131 AllocatorType A(1 << 20);
132 Array<TestData> Data(A);
133 ASSERT_TRUE(Data.empty());
134 auto I0Begin = Data.begin(), I0End = Data.end();
135 // Add enough elements in Data to have more than one chunk.
136 constexpr auto Segment = Array<TestData>::SegmentSize;
137 constexpr auto SegmentX2 = Segment * 2;
138 for (auto i = SegmentX2; i > 0u; --i) {
139 Data.AppendEmplace(args: static_cast<s64>(i), args: static_cast<s64>(i));
140 }
141 ASSERT_EQ(Data.size(), SegmentX2);
142 {
143 auto &Back = Data.back();
144 ASSERT_EQ(Back.First, 1);
145 ASSERT_EQ(Back.Second, 1);
146 }
147
148 // Trim one chunk's elements worth.
149 Data.trim(Elements: Segment);
150 ASSERT_EQ(Data.size(), Segment);
151
152 // Check that we are still able to access 'back' properly.
153 {
154 auto &Back = Data.back();
155 ASSERT_EQ(Back.First, static_cast<s64>(Segment + 1));
156 ASSERT_EQ(Back.Second, static_cast<s64>(Segment + 1));
157 }
158
159 // Then trim until it's empty.
160 Data.trim(Elements: Segment);
161 ASSERT_TRUE(Data.empty());
162
163 // Here our iterators should be the same.
164 auto I1Begin = Data.begin(), I1End = Data.end();
165 EXPECT_EQ(I0Begin, I1Begin);
166 EXPECT_EQ(I0End, I1End);
167
168 // Then we ensure that adding elements back works just fine.
169 for (auto i = SegmentX2; i > 0u; --i) {
170 Data.AppendEmplace(args: static_cast<s64>(i), args: static_cast<s64>(i));
171 }
172 EXPECT_EQ(Data.size(), SegmentX2);
173}
174
175TEST(SegmentedArrayTest, HandleExhaustedAllocator) {
176 using AllocatorType = typename Array<TestData>::AllocatorType;
177 constexpr auto Segment = Array<TestData>::SegmentSize;
178 constexpr auto MaxElements = Array<TestData>::ElementsPerSegment;
179 AllocatorType A(Segment);
180 Array<TestData> Data(A);
181 for (auto i = MaxElements; i > 0u; --i)
182 EXPECT_NE(Data.AppendEmplace(args: static_cast<s64>(i), args: static_cast<s64>(i)),
183 nullptr);
184 EXPECT_EQ(Data.AppendEmplace(args: 0, args: 0), nullptr);
185 EXPECT_THAT(Data, SizeIs(MaxElements));
186
187 // Trimming more elements than there are in the container should be fine.
188 Data.trim(Elements: MaxElements + 1);
189 EXPECT_THAT(Data, SizeIs(0u));
190}
191
192struct ShadowStackEntry {
193 uint64_t EntryTSC = 0;
194 uint64_t *NodePtr = nullptr;
195 ShadowStackEntry(uint64_t T, uint64_t *N) : EntryTSC(T), NodePtr(N) {}
196};
197
198TEST(SegmentedArrayTest, SimulateStackBehaviour) {
199 using AllocatorType = typename Array<ShadowStackEntry>::AllocatorType;
200 AllocatorType A(1 << 10);
201 Array<ShadowStackEntry> Data(A);
202 static uint64_t Dummy = 0;
203 constexpr uint64_t Max = 9;
204
205 for (uint64_t i = 0; i < Max; ++i) {
206 auto P = Data.Append(E: {i, &Dummy});
207 ASSERT_NE(P, nullptr);
208 ASSERT_EQ(P->NodePtr, &Dummy);
209 auto &Back = Data.back();
210 ASSERT_EQ(Back.NodePtr, &Dummy);
211 ASSERT_EQ(Back.EntryTSC, i);
212 }
213
214 // Simulate a stack by checking the data from the end as we're trimming.
215 auto Counter = Max;
216 ASSERT_EQ(Data.size(), size_t(Max));
217 while (!Data.empty()) {
218 const auto &Top = Data.back();
219 uint64_t *TopNode = Top.NodePtr;
220 EXPECT_EQ(TopNode, &Dummy) << "Counter = " << Counter;
221 Data.trim(Elements: 1);
222 --Counter;
223 ASSERT_EQ(Data.size(), size_t(Counter));
224 }
225}
226
227TEST(SegmentedArrayTest, PlacementNewOnAlignedStorage) {
228 using AllocatorType = typename Array<ShadowStackEntry>::AllocatorType;
229 alignas(AllocatorType) std::byte AllocatorStorage[sizeof(AllocatorType)];
230 new (&AllocatorStorage) AllocatorType(1 << 10);
231 auto *A = reinterpret_cast<AllocatorType *>(&AllocatorStorage);
232 alignas(Array<ShadowStackEntry>)
233 std::byte ArrayStorage[sizeof(Array<ShadowStackEntry>)];
234 new (&ArrayStorage) Array<ShadowStackEntry>(*A);
235 auto *Data = reinterpret_cast<Array<ShadowStackEntry> *>(&ArrayStorage);
236
237 static uint64_t Dummy = 0;
238 constexpr uint64_t Max = 9;
239
240 for (uint64_t i = 0; i < Max; ++i) {
241 auto P = Data->Append(E: {i, &Dummy});
242 ASSERT_NE(P, nullptr);
243 ASSERT_EQ(P->NodePtr, &Dummy);
244 auto &Back = Data->back();
245 ASSERT_EQ(Back.NodePtr, &Dummy);
246 ASSERT_EQ(Back.EntryTSC, i);
247 }
248
249 // Simulate a stack by checking the data from the end as we're trimming.
250 auto Counter = Max;
251 ASSERT_EQ(Data->size(), size_t(Max));
252 while (!Data->empty()) {
253 const auto &Top = Data->back();
254 uint64_t *TopNode = Top.NodePtr;
255 EXPECT_EQ(TopNode, &Dummy) << "Counter = " << Counter;
256 Data->trim(Elements: 1);
257 --Counter;
258 ASSERT_EQ(Data->size(), size_t(Counter));
259 }
260
261 // Once the stack is exhausted, we re-use the storage.
262 for (uint64_t i = 0; i < Max; ++i) {
263 auto P = Data->Append(E: {i, &Dummy});
264 ASSERT_NE(P, nullptr);
265 ASSERT_EQ(P->NodePtr, &Dummy);
266 auto &Back = Data->back();
267 ASSERT_EQ(Back.NodePtr, &Dummy);
268 ASSERT_EQ(Back.EntryTSC, i);
269 }
270
271 // We re-initialize the storage, by calling the destructor and
272 // placement-new'ing again.
273 Data->~Array();
274 A->~AllocatorType();
275 new (A) AllocatorType(1 << 10);
276 new (Data) Array<ShadowStackEntry>(*A);
277
278 // Then re-do the test.
279 for (uint64_t i = 0; i < Max; ++i) {
280 auto P = Data->Append(E: {i, &Dummy});
281 ASSERT_NE(P, nullptr);
282 ASSERT_EQ(P->NodePtr, &Dummy);
283 auto &Back = Data->back();
284 ASSERT_EQ(Back.NodePtr, &Dummy);
285 ASSERT_EQ(Back.EntryTSC, i);
286 }
287
288 // Simulate a stack by checking the data from the end as we're trimming.
289 Counter = Max;
290 ASSERT_EQ(Data->size(), size_t(Max));
291 while (!Data->empty()) {
292 const auto &Top = Data->back();
293 uint64_t *TopNode = Top.NodePtr;
294 EXPECT_EQ(TopNode, &Dummy) << "Counter = " << Counter;
295 Data->trim(Elements: 1);
296 --Counter;
297 ASSERT_EQ(Data->size(), size_t(Counter));
298 }
299
300 // Once the stack is exhausted, we re-use the storage.
301 for (uint64_t i = 0; i < Max; ++i) {
302 auto P = Data->Append(E: {i, &Dummy});
303 ASSERT_NE(P, nullptr);
304 ASSERT_EQ(P->NodePtr, &Dummy);
305 auto &Back = Data->back();
306 ASSERT_EQ(Back.NodePtr, &Dummy);
307 ASSERT_EQ(Back.EntryTSC, i);
308 }
309}
310
311TEST(SegmentedArrayTest, ArrayOfPointersIteratorAccess) {
312 using PtrArray = Array<int *>;
313 PtrArray::AllocatorType Alloc(16384);
314 Array<int *> A(Alloc);
315 static constexpr size_t Count = 100;
316 std::vector<int> Integers(Count);
317 std::iota(first: Integers.begin(), last: Integers.end(), value: 0);
318 for (auto &I : Integers)
319 ASSERT_NE(A.Append(E: &I), nullptr);
320 int V = 0;
321 ASSERT_EQ(A.size(), Count);
322 for (auto P : A) {
323 ASSERT_NE(P, nullptr);
324 ASSERT_EQ(*P, V++);
325 }
326}
327
328TEST(SegmentedArrayTest, ArrayOfPointersIteratorAccessExhaustion) {
329 using PtrArray = Array<int *>;
330 PtrArray::AllocatorType Alloc(4096);
331 Array<int *> A(Alloc);
332 static constexpr size_t Count = 1000;
333 std::vector<int> Integers(Count);
334 std::iota(first: Integers.begin(), last: Integers.end(), value: 0);
335 for (auto &I : Integers)
336 if (A.Append(E: &I) == nullptr)
337 break;
338 int V = 0;
339 ASSERT_LT(A.size(), Count);
340 for (auto P : A) {
341 ASSERT_NE(P, nullptr);
342 ASSERT_EQ(*P, V++);
343 }
344}
345
346} // namespace
347} // namespace __xray
348

source code of compiler-rt/lib/xray/tests/unit/segmented_array_test.cpp