src/third_party/llvm-project/compiler-rt/lib/xray/tests/unit/segmented_array_test.cc

#include "xray_segmented_array.h"
#include "gtest/gtest.h"

namespace __xray {
namespace {

struct TestData {
  s64 First;
  s64 Second;

  // Need a constructor for emplace operations.
  TestData(s64 F, s64 S) : First(F), Second(S) {}
};

TEST(SegmentedArrayTest, ConstructWithAllocators) {
  using AllocatorType = typename Array<TestData>::AllocatorType;
  AllocatorType A(1 << 4);
  Array<TestData> Data(A);
  (void)Data;
}

TEST(SegmentedArrayTest, ConstructAndPopulate) {
  using AllocatorType = typename Array<TestData>::AllocatorType;
  AllocatorType A(1 << 4);
  Array<TestData> data(A);
  ASSERT_NE(data.Append(TestData{0, 0}), nullptr);
  ASSERT_NE(data.Append(TestData{1, 1}), nullptr);
  ASSERT_EQ(data.size(), 2u);
}

TEST(SegmentedArrayTest, ConstructPopulateAndLookup) {
  using AllocatorType = typename Array<TestData>::AllocatorType;
  AllocatorType A(1 << 4);
  Array<TestData> data(A);
  ASSERT_NE(data.Append(TestData{0, 1}), nullptr);
  ASSERT_EQ(data.size(), 1u);
  ASSERT_EQ(data[0].First, 0);
  ASSERT_EQ(data[0].Second, 1);
}

TEST(SegmentedArrayTest, PopulateWithMoreElements) {
  using AllocatorType = typename Array<TestData>::AllocatorType;
  AllocatorType A(1 << 24);
  Array<TestData> data(A);
  static const auto kMaxElements = 100u;
  for (auto I = 0u; I < kMaxElements; ++I) {
    ASSERT_NE(data.Append(TestData{I, I + 1}), nullptr);
  }
  ASSERT_EQ(data.size(), kMaxElements);
  for (auto I = 0u; I < kMaxElements; ++I) {
    ASSERT_EQ(data[I].First, I);
    ASSERT_EQ(data[I].Second, I + 1);
  }
}

TEST(SegmentedArrayTest, AppendEmplace) {
  using AllocatorType = typename Array<TestData>::AllocatorType;
  AllocatorType A(1 << 4);
  Array<TestData> data(A);
  ASSERT_NE(data.AppendEmplace(1, 1), nullptr);
  ASSERT_EQ(data[0].First, 1);
  ASSERT_EQ(data[0].Second, 1);
}

TEST(SegmentedArrayTest, AppendAndTrim) {
  using AllocatorType = typename Array<TestData>::AllocatorType;
  AllocatorType A(1 << 4);
  Array<TestData> data(A);
  ASSERT_NE(data.AppendEmplace(1, 1), nullptr);
  ASSERT_EQ(data.size(), 1u);
  data.trim(1);
  ASSERT_EQ(data.size(), 0u);
  ASSERT_TRUE(data.empty());
}

TEST(SegmentedArrayTest, IteratorAdvance) {
  using AllocatorType = typename Array<TestData>::AllocatorType;
  AllocatorType A(1 << 4);
  Array<TestData> data(A);
  ASSERT_TRUE(data.empty());
  ASSERT_EQ(data.begin(), data.end());
  auto I0 = data.begin();
  ASSERT_EQ(I0++, data.begin());
  ASSERT_NE(I0, data.begin());
  for (const auto &D : data) {
    (void)D;
    FAIL();
  }
  ASSERT_NE(data.AppendEmplace(1, 1), nullptr);
  ASSERT_EQ(data.size(), 1u);
  ASSERT_NE(data.begin(), data.end());
  auto &D0 = *data.begin();
  ASSERT_EQ(D0.First, 1);
  ASSERT_EQ(D0.Second, 1);
}

TEST(SegmentedArrayTest, IteratorRetreat) {
  using AllocatorType = typename Array<TestData>::AllocatorType;
  AllocatorType A(1 << 4);
  Array<TestData> data(A);
  ASSERT_TRUE(data.empty());
  ASSERT_EQ(data.begin(), data.end());
  ASSERT_NE(data.AppendEmplace(1, 1), nullptr);
  ASSERT_EQ(data.size(), 1u);
  ASSERT_NE(data.begin(), data.end());
  auto &D0 = *data.begin();
  ASSERT_EQ(D0.First, 1);
  ASSERT_EQ(D0.Second, 1);

  auto I0 = data.end();
  ASSERT_EQ(I0--, data.end());
  ASSERT_NE(I0, data.end());
  ASSERT_EQ(I0, data.begin());
  ASSERT_EQ(I0->First, 1);
  ASSERT_EQ(I0->Second, 1);
}

TEST(SegmentedArrayTest, IteratorTrimBehaviour) {
  using AllocatorType = typename Array<TestData>::AllocatorType;
  AllocatorType A(1 << 20);
  Array<TestData> Data(A);
  ASSERT_TRUE(Data.empty());
  auto I0Begin = Data.begin(), I0End = Data.end();
  // Add enough elements in Data to have more than one chunk.
  constexpr auto Segment = Array<TestData>::SegmentSize;
  constexpr auto SegmentX2 = Segment * 2;
  for (auto i = SegmentX2; i > 0u; --i) {
    Data.AppendEmplace(static_cast<s64>(i), static_cast<s64>(i));
  }
  ASSERT_EQ(Data.size(), SegmentX2);
  {
    auto &Back = Data.back();
    ASSERT_EQ(Back.First, 1);
    ASSERT_EQ(Back.Second, 1);
  }

  // Trim one chunk's elements worth.
  Data.trim(Segment);
  ASSERT_EQ(Data.size(), Segment);

  // Check that we are still able to access 'back' properly.
  {
    auto &Back = Data.back();
    ASSERT_EQ(Back.First, static_cast<s64>(Segment + 1));
    ASSERT_EQ(Back.Second, static_cast<s64>(Segment + 1));
  }

  // Then trim until it's empty.
  Data.trim(Segment);
  ASSERT_TRUE(Data.empty());

  // Here our iterators should be the same.
  auto I1Begin = Data.begin(), I1End = Data.end();
  EXPECT_EQ(I0Begin, I1Begin);
  EXPECT_EQ(I0End, I1End);

  // Then we ensure that adding elements back works just fine.
  for (auto i = SegmentX2; i > 0u; --i) {
    Data.AppendEmplace(static_cast<s64>(i), static_cast<s64>(i));
  }
  EXPECT_EQ(Data.size(), SegmentX2);
}

struct ShadowStackEntry {
  uint64_t EntryTSC = 0;
  uint64_t *NodePtr = nullptr;
  ShadowStackEntry(uint64_t T, uint64_t *N) : EntryTSC(T), NodePtr(N) {}
};

TEST(SegmentedArrayTest, SimulateStackBehaviour) {
  using AllocatorType = typename Array<ShadowStackEntry>::AllocatorType;
  AllocatorType A(1 << 10);
  Array<ShadowStackEntry> Data(A);
  static uint64_t Dummy = 0;
  constexpr uint64_t Max = 9;

  for (uint64_t i = 0; i < Max; ++i) {
    auto P = Data.Append({i, &Dummy});
    ASSERT_NE(P, nullptr);
    ASSERT_EQ(P->NodePtr, &Dummy);
    auto &Back = Data.back();
    ASSERT_EQ(Back.NodePtr, &Dummy);
    ASSERT_EQ(Back.EntryTSC, i);
  }

  // Simulate a stack by checking the data from the end as we're trimming.
  auto Counter = Max;
  ASSERT_EQ(Data.size(), size_t(Max));
  while (!Data.empty()) {
    const auto &Top = Data.back();
    uint64_t *TopNode = Top.NodePtr;
    EXPECT_EQ(TopNode, &Dummy) << "Counter = " << Counter;
    Data.trim(1);
    --Counter;
    ASSERT_EQ(Data.size(), size_t(Counter));
  }
}

} // namespace
} // namespace __xray