221 lines · cpp
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/CAS/OnDiskTrieRawHashMap.h"10#include "llvm/ADT/ArrayRef.h"11#include "llvm/Config/llvm-config.h"12#include "llvm/Support/Alignment.h"13#include "llvm/Testing/Support/Error.h"14#include "llvm/Testing/Support/SupportHelpers.h"15#include "gtest/gtest.h"16 17#if LLVM_ENABLE_ONDISK_CAS18using namespace llvm;19using namespace llvm::cas;20 21namespace {22 23struct OnDiskTrieRawHashMapTestFixture24 : public ::testing::TestWithParam<size_t> {25 static constexpr size_t MB = 1024u * 1024u;26 static constexpr size_t DataSize = 8; // Multiple of 8B.27 28 std::optional<unittest::TempDir> Temp;29 size_t NumHashBytes;30 31 void SetUp() override {32 Temp.emplace("trie-raw-hash-map", /*Unique=*/true);33 NumHashBytes = GetParam();34 }35 void TearDown() override { Temp.reset(); }36 37 Expected<OnDiskTrieRawHashMap> createTrie() {38 size_t NumHashBits = NumHashBytes * 8;39 return OnDiskTrieRawHashMap::create(40 Temp->path((Twine(NumHashBytes) + "B").str()), "index",41 /*NumHashBits=*/NumHashBits, DataSize, /*MaxFileSize=*/MB,42 /*NewInitialFileSize=*/std::nullopt);43 }44};45 46// Create tries with various sizes of hash and with data.47TEST_P(OnDiskTrieRawHashMapTestFixture, General) {48 std::optional<OnDiskTrieRawHashMap> Trie1;49 ASSERT_THAT_ERROR(createTrie().moveInto(Trie1), Succeeded());50 std::optional<OnDiskTrieRawHashMap> Trie2;51 ASSERT_THAT_ERROR(createTrie().moveInto(Trie2), Succeeded());52 53 uint8_t Hash0Bytes[8] = {0, 0, 0, 0, 0, 0, 0, 0};54 uint8_t Hash1Bytes[8] = {1, 0, 0, 0, 0, 0, 0, 0};55 auto Hash0 = ArrayRef(Hash0Bytes).take_front(NumHashBytes);56 auto Hash1 = ArrayRef(Hash1Bytes).take_front(NumHashBytes);57 constexpr StringLiteral Data0v1Bytes = "data0.v1";58 constexpr StringLiteral Data0v2Bytes = "data0.v2";59 constexpr StringLiteral Data1Bytes = "data1...";60 static_assert(Data0v1Bytes.size() == DataSize, "math error");61 static_assert(Data0v2Bytes.size() == DataSize, "math error");62 static_assert(Data1Bytes.size() == DataSize, "math error");63 ArrayRef<char> Data0v1 = ArrayRef(Data0v1Bytes.data(), Data0v1Bytes.size());64 ArrayRef<char> Data0v2 = ArrayRef(Data0v2Bytes.data(), Data0v2Bytes.size());65 ArrayRef<char> Data1 = ArrayRef(Data1Bytes.data(), Data1Bytes.size());66 67 // Lookup when trie is empty.68 EXPECT_FALSE(Trie1->find(Hash0));69 70 // Insert.71 std::optional<FileOffset> Offset;72 std::optional<MutableArrayRef<char>> Data;73 {74 std::optional<OnDiskTrieRawHashMap::OnDiskPtr> Insertion;75 ASSERT_THAT_ERROR(Trie1->insert({Hash0, Data0v1}).moveInto(Insertion),76 Succeeded());77 EXPECT_EQ(Hash0, (*Insertion)->Hash);78 EXPECT_EQ(Data0v1, (*Insertion)->Data);79 EXPECT_TRUE(isAddrAligned(Align(8), (*Insertion)->Data.data()));80 81 Offset = Insertion->getOffset();82 Data = (*Insertion)->Data;83 }84 85 // Find.86 {87 auto Lookup = Trie1->find(Hash0);88 ASSERT_TRUE(Lookup);89 EXPECT_EQ(Hash0, Lookup->Hash);90 EXPECT_EQ(Data0v1, Lookup->Data);91 EXPECT_EQ(Offset->get(), Lookup.getOffset().get());92 }93 94 // Find in a different instance of the same on-disk trie that existed95 // before the insertion.96 {97 auto Lookup = Trie2->find(Hash0);98 ASSERT_TRUE(Lookup);99 EXPECT_EQ(Hash0, Lookup->Hash);100 EXPECT_EQ(Data0v1, Lookup->Data);101 EXPECT_EQ(Offset->get(), Lookup.getOffset().get());102 }103 104 // Create a new instance and check that too.105 Trie2.reset();106 ASSERT_THAT_ERROR(createTrie().moveInto(Trie2), Succeeded());107 {108 auto Lookup = Trie2->find(Hash0);109 ASSERT_TRUE(Lookup);110 EXPECT_EQ(Hash0, Lookup->Hash);111 EXPECT_EQ(Data0v1, Lookup->Data);112 EXPECT_EQ(Offset->get(), Lookup.getOffset().get());113 }114 115 // Change the data.116 llvm::copy(Data0v2, Data->data());117 {118 auto Lookup = Trie2->find(Hash0);119 ASSERT_TRUE(Lookup);120 EXPECT_EQ(Hash0, Lookup->Hash);121 EXPECT_EQ(Data0v2, Lookup->Data);122 EXPECT_EQ(Offset->get(), Lookup.getOffset().get());123 }124 125 // Find different hash.126 EXPECT_FALSE(Trie1->find(Hash1));127 EXPECT_FALSE(Trie2->find(Hash1));128 129 // Recover from an offset.130 {131 OnDiskTrieRawHashMap::ConstOnDiskPtr Recovered;132 ASSERT_THAT_ERROR(Trie1->recoverFromFileOffset(*Offset).moveInto(Recovered),133 Succeeded());134 ASSERT_TRUE(Recovered);135 EXPECT_EQ(Offset->get(), Recovered.getOffset().get());136 EXPECT_EQ(Hash0, Recovered->Hash);137 EXPECT_EQ(Data0v2, Recovered->Data);138 }139 140 // Recover from a bad offset.141 {142 FileOffset BadOffset(1);143 OnDiskTrieRawHashMap::ConstOnDiskPtr Recovered;144 ASSERT_THAT_ERROR(145 Trie1->recoverFromFileOffset(BadOffset).moveInto(Recovered), Failed());146 }147 148 // Insert another thing.149 {150 std::optional<OnDiskTrieRawHashMap::OnDiskPtr> Insertion;151 ASSERT_THAT_ERROR(Trie1->insert({Hash1, Data1}).moveInto(Insertion),152 Succeeded());153 EXPECT_EQ(Hash1, (*Insertion)->Hash);154 EXPECT_EQ(Data1, (*Insertion)->Data);155 EXPECT_TRUE(isAddrAligned(Align(8), (*Insertion)->Data.data()));156 157 EXPECT_NE(Offset->get(), Insertion->getOffset().get());158 }159 160 // Validate.161 {162 auto RecordVerify =163 [&](FileOffset Offset,164 OnDiskTrieRawHashMap::ConstValueProxy Proxy) -> Error {165 if (Proxy.Hash.size() != NumHashBytes)166 return createStringError("wrong hash size");167 if (Proxy.Data.size() != DataSize)168 return createStringError("wrong data size");169 170 return Error::success();171 };172 ASSERT_THAT_ERROR(Trie1->validate(RecordVerify), Succeeded());173 ASSERT_THAT_ERROR(Trie2->validate(RecordVerify), Succeeded());174 }175 176 // Size and capacity.177 {178 EXPECT_EQ(Trie1->capacity(), MB);179 EXPECT_EQ(Trie2->capacity(), MB);180 EXPECT_LE(Trie1->size(), MB);181 EXPECT_LE(Trie2->size(), MB);182 }183}184 185INSTANTIATE_TEST_SUITE_P(OnDiskTrieRawHashMapTest,186 OnDiskTrieRawHashMapTestFixture,187 ::testing::Values(1, 2, 4, 8));188 189TEST(OnDiskTrieRawHashMapTest, OutOfSpace) {190 unittest::TempDir Temp("trie-raw-hash-map", /*Unique=*/true);191 std::optional<OnDiskTrieRawHashMap> Trie;192 193 // Too small to create header.194 ASSERT_THAT_ERROR(OnDiskTrieRawHashMap::create(195 Temp.path("NoSpace1").str(), "index",196 /*NumHashBits=*/8, /*DataSize=*/8, /*MaxFileSize=*/8,197 /*NewInitialFileSize=*/std::nullopt)198 .moveInto(Trie),199 Failed());200 201 // Just enough for root node but not enough for any insertion.202 ASSERT_THAT_ERROR(OnDiskTrieRawHashMap::create(203 Temp.path("NoSpace2").str(), "index",204 /*NumHashBits=*/8, /*DataSize=*/8, /*MaxFileSize=*/118,205 /*NewInitialFileSize=*/std::nullopt,206 /*NewTableNumRootBits=*/1, /*NewTableNumSubtrieBits=*/1)207 .moveInto(Trie),208 Succeeded());209 uint8_t Hash0Bytes[1] = {0};210 auto Hash0 = ArrayRef(Hash0Bytes);211 constexpr StringLiteral Data0v1Bytes = "data0.v1";212 ArrayRef<char> Data0v1 = ArrayRef(Data0v1Bytes.data(), Data0v1Bytes.size());213 std::optional<OnDiskTrieRawHashMap::OnDiskPtr> Insertion;214 ASSERT_THAT_ERROR(Trie->insert({Hash0, Data0v1}).moveInto(Insertion),215 Failed());216}217 218} // namespace219 220#endif // LLVM_ENABLE_ONDISK_CAS221