• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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::__anon1daaea770111::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::__anon1daaea770111::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    typename std::aligned_storage<sizeof(AllocatorType),
230                                  alignof(AllocatorType)>::type AllocatorStorage;
231    new (&AllocatorStorage) AllocatorType(1 << 10);
232    auto *A = reinterpret_cast<AllocatorType *>(&AllocatorStorage);
233    typename std::aligned_storage<sizeof(Array<ShadowStackEntry>),
234                                  alignof(Array<ShadowStackEntry>)>::type
235        ArrayStorage;
236    new (&ArrayStorage) Array<ShadowStackEntry>(*A);
237    auto *Data = reinterpret_cast<Array<ShadowStackEntry> *>(&ArrayStorage);
238  
239    static uint64_t Dummy = 0;
240    constexpr uint64_t Max = 9;
241  
242    for (uint64_t i = 0; i < Max; ++i) {
243      auto P = Data->Append({i, &Dummy});
244      ASSERT_NE(P, nullptr);
245      ASSERT_EQ(P->NodePtr, &Dummy);
246      auto &Back = Data->back();
247      ASSERT_EQ(Back.NodePtr, &Dummy);
248      ASSERT_EQ(Back.EntryTSC, i);
249    }
250  
251    // Simulate a stack by checking the data from the end as we're trimming.
252    auto Counter = Max;
253    ASSERT_EQ(Data->size(), size_t(Max));
254    while (!Data->empty()) {
255      const auto &Top = Data->back();
256      uint64_t *TopNode = Top.NodePtr;
257      EXPECT_EQ(TopNode, &Dummy) << "Counter = " << Counter;
258      Data->trim(1);
259      --Counter;
260      ASSERT_EQ(Data->size(), size_t(Counter));
261    }
262  
263    // Once the stack is exhausted, we re-use the storage.
264    for (uint64_t i = 0; i < Max; ++i) {
265      auto P = Data->Append({i, &Dummy});
266      ASSERT_NE(P, nullptr);
267      ASSERT_EQ(P->NodePtr, &Dummy);
268      auto &Back = Data->back();
269      ASSERT_EQ(Back.NodePtr, &Dummy);
270      ASSERT_EQ(Back.EntryTSC, i);
271    }
272  
273    // We re-initialize the storage, by calling the destructor and
274    // placement-new'ing again.
275    Data->~Array();
276    A->~AllocatorType();
277    new (A) AllocatorType(1 << 10);
278    new (Data) Array<ShadowStackEntry>(*A);
279  
280    // Then re-do the test.
281    for (uint64_t i = 0; i < Max; ++i) {
282      auto P = Data->Append({i, &Dummy});
283      ASSERT_NE(P, nullptr);
284      ASSERT_EQ(P->NodePtr, &Dummy);
285      auto &Back = Data->back();
286      ASSERT_EQ(Back.NodePtr, &Dummy);
287      ASSERT_EQ(Back.EntryTSC, i);
288    }
289  
290    // Simulate a stack by checking the data from the end as we're trimming.
291    Counter = Max;
292    ASSERT_EQ(Data->size(), size_t(Max));
293    while (!Data->empty()) {
294      const auto &Top = Data->back();
295      uint64_t *TopNode = Top.NodePtr;
296      EXPECT_EQ(TopNode, &Dummy) << "Counter = " << Counter;
297      Data->trim(1);
298      --Counter;
299      ASSERT_EQ(Data->size(), size_t(Counter));
300    }
301  
302    // Once the stack is exhausted, we re-use the storage.
303    for (uint64_t i = 0; i < Max; ++i) {
304      auto P = Data->Append({i, &Dummy});
305      ASSERT_NE(P, nullptr);
306      ASSERT_EQ(P->NodePtr, &Dummy);
307      auto &Back = Data->back();
308      ASSERT_EQ(Back.NodePtr, &Dummy);
309      ASSERT_EQ(Back.EntryTSC, i);
310    }
311  }
312  
TEST(SegmentedArrayTest,ArrayOfPointersIteratorAccess)313  TEST(SegmentedArrayTest, ArrayOfPointersIteratorAccess) {
314    using PtrArray = Array<int *>;
315    PtrArray::AllocatorType Alloc(16384);
316    Array<int *> A(Alloc);
317    static constexpr size_t Count = 100;
318    std::vector<int> Integers(Count);
319    std::iota(Integers.begin(), Integers.end(), 0);
320    for (auto &I : Integers)
321      ASSERT_NE(A.Append(&I), nullptr);
322    int V = 0;
323    ASSERT_EQ(A.size(), Count);
324    for (auto P : A) {
325      ASSERT_NE(P, nullptr);
326      ASSERT_EQ(*P, V++);
327    }
328  }
329  
TEST(SegmentedArrayTest,ArrayOfPointersIteratorAccessExhaustion)330  TEST(SegmentedArrayTest, ArrayOfPointersIteratorAccessExhaustion) {
331    using PtrArray = Array<int *>;
332    PtrArray::AllocatorType Alloc(4096);
333    Array<int *> A(Alloc);
334    static constexpr size_t Count = 1000;
335    std::vector<int> Integers(Count);
336    std::iota(Integers.begin(), Integers.end(), 0);
337    for (auto &I : Integers)
338      if (A.Append(&I) == nullptr)
339        break;
340    int V = 0;
341    ASSERT_LT(A.size(), Count);
342    for (auto P : A) {
343      ASSERT_NE(P, nullptr);
344      ASSERT_EQ(*P, V++);
345    }
346  }
347  
348  } // namespace
349  } // namespace __xray
350