348 lines · cpp
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(TestData{0, 0}), nullptr);38 ASSERT_NE(data.Append(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(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(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(1, 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(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 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(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 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(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 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(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 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(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 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({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 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({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 and272 // 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 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(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 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(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} // namespace347} // namespace __xray348