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
9 namespace __xray {
10 namespace {
11
12 using ::testing::SizeIs;
13
14 struct TestData {
15 s64 First;
16 s64 Second;
17
18 // Need a constructor for emplace operations.
TestData__xray::__anon467c9eb30111::TestData19 TestData(s64 F, s64 S) : First(F), Second(S) {}
20 };
21
PrintTo(const TestData & D,std::ostream * OS)22 void PrintTo(const TestData &D, std::ostream *OS) {
23 *OS << "{ " << D.First << ", " << D.Second << " }";
24 }
25
TEST(SegmentedArrayTest,ConstructWithAllocators)26 TEST(SegmentedArrayTest, ConstructWithAllocators) {
27 using AllocatorType = typename Array<TestData>::AllocatorType;
28 AllocatorType A(1 << 4);
29 Array<TestData> Data(A);
30 (void)Data;
31 }
32
TEST(SegmentedArrayTest,ConstructAndPopulate)33 TEST(SegmentedArrayTest, ConstructAndPopulate) {
34 using AllocatorType = typename Array<TestData>::AllocatorType;
35 AllocatorType A(1 << 4);
36 Array<TestData> data(A);
37 ASSERT_NE(data.Append(TestData{0, 0}), nullptr);
38 ASSERT_NE(data.Append(TestData{1, 1}), nullptr);
39 ASSERT_EQ(data.size(), 2u);
40 }
41
TEST(SegmentedArrayTest,ConstructPopulateAndLookup)42 TEST(SegmentedArrayTest, ConstructPopulateAndLookup) {
43 using AllocatorType = typename Array<TestData>::AllocatorType;
44 AllocatorType A(1 << 4);
45 Array<TestData> data(A);
46 ASSERT_NE(data.Append(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
TEST(SegmentedArrayTest,PopulateWithMoreElements)52 TEST(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(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
TEST(SegmentedArrayTest,AppendEmplace)67 TEST(SegmentedArrayTest, AppendEmplace) {
68 using AllocatorType = typename Array<TestData>::AllocatorType;
69 AllocatorType A(1 << 4);
70 Array<TestData> data(A);
71 ASSERT_NE(data.AppendEmplace(1, 1), nullptr);
72 ASSERT_EQ(data[0].First, 1);
73 ASSERT_EQ(data[0].Second, 1);
74 }
75
TEST(SegmentedArrayTest,AppendAndTrim)76 TEST(SegmentedArrayTest, AppendAndTrim) {
77 using AllocatorType = typename Array<TestData>::AllocatorType;
78 AllocatorType A(1 << 4);
79 Array<TestData> data(A);
80 ASSERT_NE(data.AppendEmplace(1, 1), nullptr);
81 ASSERT_EQ(data.size(), 1u);
82 data.trim(1);
83 ASSERT_EQ(data.size(), 0u);
84 ASSERT_TRUE(data.empty());
85 }
86
TEST(SegmentedArrayTest,IteratorAdvance)87 TEST(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(1, 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
TEST(SegmentedArrayTest,IteratorRetreat)108 TEST(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(1, 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
TEST(SegmentedArrayTest,IteratorTrimBehaviour)129 TEST(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(static_cast<s64>(i), 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(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(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(static_cast<s64>(i), static_cast<s64>(i));
171 }
172 EXPECT_EQ(Data.size(), SegmentX2);
173 }
174
TEST(SegmentedArrayTest,HandleExhaustedAllocator)175 TEST(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(static_cast<s64>(i), static_cast<s64>(i)),
183 nullptr);
184 EXPECT_EQ(Data.AppendEmplace(0, 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(MaxElements + 1);
189 EXPECT_THAT(Data, SizeIs(0u));
190 }
191
192 struct ShadowStackEntry {
193 uint64_t EntryTSC = 0;
194 uint64_t *NodePtr = nullptr;
ShadowStackEntry__xray::__anon467c9eb30111::ShadowStackEntry195 ShadowStackEntry(uint64_t T, uint64_t *N) : EntryTSC(T), NodePtr(N) {}
196 };
197
TEST(SegmentedArrayTest,SimulateStackBehaviour)198 TEST(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({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(1);
222 --Counter;
223 ASSERT_EQ(Data.size(), size_t(Counter));
224 }
225 }
226
TEST(SegmentedArrayTest,PlacementNewOnAlignedStorage)227 TEST(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({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(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({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({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(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({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
TEST(SegmentedArrayTest,ArrayOfPointersIteratorAccess)311 TEST(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(Integers.begin(), Integers.end(), 0);
318 for (auto &I : Integers)
319 ASSERT_NE(A.Append(&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
TEST(SegmentedArrayTest,ArrayOfPointersIteratorAccessExhaustion)328 TEST(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(Integers.begin(), Integers.end(), 0);
335 for (auto &I : Integers)
336 if (A.Append(&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