| //===- MultiOnDiskHashTable.h - Merged set of hash tables -------*- C++ -*-===// | |
| // | |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |
| // See https://llvm.org/LICENSE.txt for license information. | |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |
| // | |
| //===----------------------------------------------------------------------===// | |
| // | |
| // This file provides a hash table data structure suitable for incremental and | |
| // distributed storage across a set of files. | |
| // | |
| // Multiple hash tables from different files are implicitly merged to improve | |
| // performance, and on reload the merged table will override those from other | |
| // files. | |
| // | |
| //===----------------------------------------------------------------------===// | |
| #ifndef LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H | |
| #define LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H | |
| #include "llvm/ADT/DenseMap.h" | |
| #include "llvm/ADT/DenseSet.h" | |
| #include "llvm/ADT/PointerUnion.h" | |
| #include "llvm/ADT/STLExtras.h" | |
| #include "llvm/ADT/SmallVector.h" | |
| #include "llvm/ADT/TinyPtrVector.h" | |
| #include "llvm/ADT/iterator_range.h" | |
| #include "llvm/Support/Endian.h" | |
| #include "llvm/Support/EndianStream.h" | |
| #include "llvm/Support/OnDiskHashTable.h" | |
| #include "llvm/Support/raw_ostream.h" | |
| #include <algorithm> | |
| #include <cstdint> | |
| #include <vector> | |
| namespace clang { | |
| namespace serialization { | |
| /// A collection of on-disk hash tables, merged when relevant for performance. | |
| template<typename Info> class MultiOnDiskHashTable { | |
| public: | |
| /// A handle to a file, used when overriding tables. | |
| using file_type = typename Info::file_type; | |
| /// A pointer to an on-disk representation of the hash table. | |
| using storage_type = const unsigned char *; | |
| using external_key_type = typename Info::external_key_type; | |
| using internal_key_type = typename Info::internal_key_type; | |
| using data_type = typename Info::data_type; | |
| using data_type_builder = typename Info::data_type_builder; | |
| using hash_value_type = unsigned; | |
| private: | |
| /// The generator is permitted to read our merged table. | |
| template<typename ReaderInfo, typename WriterInfo> | |
| friend class MultiOnDiskHashTableGenerator; | |
| /// A hash table stored on disk. | |
| struct OnDiskTable { | |
| using HashTable = llvm::OnDiskIterableChainedHashTable<Info>; | |
| file_type File; | |
| HashTable Table; | |
| OnDiskTable(file_type File, unsigned NumBuckets, unsigned NumEntries, | |
| storage_type Buckets, storage_type Payload, storage_type Base, | |
| const Info &InfoObj) | |
| : File(File), | |
| Table(NumBuckets, NumEntries, Buckets, Payload, Base, InfoObj) {} | |
| }; | |
| struct MergedTable { | |
| std::vector<file_type> Files; | |
| llvm::DenseMap<internal_key_type, data_type> Data; | |
| }; | |
| using Table = llvm::PointerUnion<OnDiskTable *, MergedTable *>; | |
| using TableVector = llvm::TinyPtrVector<void *>; | |
| /// The current set of on-disk and merged tables. | |
| /// We manually store the opaque value of the Table because TinyPtrVector | |
| /// can't cope with holding a PointerUnion directly. | |
| /// There can be at most one MergedTable in this vector, and if present, | |
| /// it is the first table. | |
| TableVector Tables; | |
| /// Files corresponding to overridden tables that we've not yet | |
| /// discarded. | |
| llvm::TinyPtrVector<file_type> PendingOverrides; | |
| struct AsOnDiskTable { | |
| using result_type = OnDiskTable *; | |
| result_type operator()(void *P) const { | |
| return llvm::cast<OnDiskTable *>(Table::getFromOpaqueValue(P)); | |
| } | |
| }; | |
| using table_iterator = | |
| llvm::mapped_iterator<TableVector::iterator, AsOnDiskTable>; | |
| using table_range = llvm::iterator_range<table_iterator>; | |
| /// The current set of on-disk tables. | |
| table_range tables() { | |
| unsigned DropBegin = getMergedTable() ? 1 : 0; | |
| return llvm::map_range(llvm::drop_begin(Tables, DropBegin), | |
| AsOnDiskTable()); | |
| } | |
| MergedTable *getMergedTable() const { | |
| // If we already have a merged table, it's the first one. | |
| return Tables.empty() ? nullptr : Table::getFromOpaqueValue(*Tables.begin()) | |
| .template dyn_cast<MergedTable*>(); | |
| } | |
| /// Delete all our current on-disk tables. | |
| void clear() { | |
| for (auto *T : tables()) | |
| delete T; | |
| if (auto *M = getMergedTable()) | |
| delete M; | |
| Tables.clear(); | |
| } | |
| void removeOverriddenTables() { | |
| llvm::DenseSet<file_type> Files; | |
| Files.insert_range(PendingOverrides); | |
| // Explicitly capture Files to work around an MSVC 2015 rejects-valid bug. | |
| auto ShouldRemove = [&Files](void *T) -> bool { | |
| auto *ODT = llvm::cast<OnDiskTable *>(Table::getFromOpaqueValue(T)); | |
| bool Remove = Files.count(ODT->File); | |
| if (Remove) | |
| delete ODT; | |
| return Remove; | |
| }; | |
| Tables.erase(std::remove_if(tables().begin().getCurrent(), Tables.end(), | |
| ShouldRemove), | |
| Tables.end()); | |
| PendingOverrides.clear(); | |
| } | |
| void condense() { | |
| MergedTable *Merged = getMergedTable(); | |
| if (!Merged) | |
| Merged = new MergedTable; | |
| // Read in all the tables and merge them together. | |
| // FIXME: Be smarter about which tables we merge. | |
| for (auto *ODT : tables()) { | |
| auto &HT = ODT->Table; | |
| Info &InfoObj = HT.getInfoObj(); | |
| for (auto I = HT.data_begin(), E = HT.data_end(); I != E; ++I) { | |
| auto *LocalPtr = I.getItem(); | |
| // FIXME: Don't rely on the OnDiskHashTable format here. | |
| auto L = InfoObj.ReadKeyDataLength(LocalPtr); | |
| const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first); | |
| data_type_builder ValueBuilder(Merged->Data[Key]); | |
| InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second, | |
| ValueBuilder); | |
| } | |
| Merged->Files.push_back(ODT->File); | |
| delete ODT; | |
| } | |
| Tables.clear(); | |
| Tables.push_back(Table(Merged).getOpaqueValue()); | |
| } | |
| public: | |
| MultiOnDiskHashTable() = default; | |
| MultiOnDiskHashTable(MultiOnDiskHashTable &&O) | |
| : Tables(std::move(O.Tables)), | |
| PendingOverrides(std::move(O.PendingOverrides)) { | |
| O.Tables.clear(); | |
| } | |
| MultiOnDiskHashTable &operator=(MultiOnDiskHashTable &&O) { | |
| if (&O == this) | |
| return *this; | |
| clear(); | |
| Tables = std::move(O.Tables); | |
| O.Tables.clear(); | |
| PendingOverrides = std::move(O.PendingOverrides); | |
| return *this; | |
| } | |
| ~MultiOnDiskHashTable() { clear(); } | |
| /// Add the table \p Data loaded from file \p File. | |
| void add(file_type File, storage_type Data, Info InfoObj = Info()) { | |
| using namespace llvm::support; | |
| storage_type Ptr = Data; | |
| uint32_t BucketOffset = | |
| endian::readNext<uint32_t, llvm::endianness::little>(Ptr); | |
| // Read the list of overridden files. | |
| uint32_t NumFiles = | |
| endian::readNext<uint32_t, llvm::endianness::little>(Ptr); | |
| // FIXME: Add a reserve() to TinyPtrVector so that we don't need to make | |
| // an additional copy. | |
| llvm::SmallVector<file_type, 16> OverriddenFiles; | |
| OverriddenFiles.reserve(NumFiles); | |
| for (/**/; NumFiles != 0; --NumFiles) | |
| OverriddenFiles.push_back(InfoObj.ReadFileRef(Ptr)); | |
| llvm::append_range(PendingOverrides, OverriddenFiles); | |
| // Read the OnDiskChainedHashTable header. | |
| storage_type Buckets = Data + BucketOffset; | |
| auto NumBucketsAndEntries = | |
| OnDiskTable::HashTable::readNumBucketsAndEntries(Buckets); | |
| // Register the table. | |
| Table NewTable = new OnDiskTable(File, NumBucketsAndEntries.first, | |
| NumBucketsAndEntries.second, | |
| Buckets, Ptr, Data, std::move(InfoObj)); | |
| Tables.push_back(NewTable.getOpaqueValue()); | |
| } | |
| /// Find and read the lookup results for \p EKey. | |
| data_type find(const external_key_type &EKey) { | |
| data_type Result; | |
| if (!PendingOverrides.empty()) | |
| removeOverriddenTables(); | |
| if (Tables.size() > static_cast<unsigned>(Info::MaxTables)) | |
| condense(); | |
| internal_key_type Key = Info::GetInternalKey(EKey); | |
| auto KeyHash = Info::ComputeHash(Key); | |
| if (MergedTable *M = getMergedTable()) { | |
| auto It = M->Data.find(Key); | |
| if (It != M->Data.end()) | |
| Result = It->second; | |
| } | |
| data_type_builder ResultBuilder(Result); | |
| for (auto *ODT : tables()) { | |
| auto &HT = ODT->Table; | |
| auto It = HT.find_hashed(Key, KeyHash); | |
| if (It != HT.end()) | |
| HT.getInfoObj().ReadDataInto(Key, It.getDataPtr(), It.getDataLen(), | |
| ResultBuilder); | |
| } | |
| return Result; | |
| } | |
| /// Read all the lookup results into a single value. This only makes | |
| /// sense if merging values across keys is meaningful. | |
| data_type findAll() { | |
| data_type Result; | |
| data_type_builder ResultBuilder(Result); | |
| if (!PendingOverrides.empty()) | |
| removeOverriddenTables(); | |
| if (MergedTable *M = getMergedTable()) { | |
| for (auto &KV : M->Data) | |
| Info::MergeDataInto(KV.second, ResultBuilder); | |
| } | |
| for (auto *ODT : tables()) { | |
| auto &HT = ODT->Table; | |
| Info &InfoObj = HT.getInfoObj(); | |
| for (auto I = HT.data_begin(), E = HT.data_end(); I != E; ++I) { | |
| auto *LocalPtr = I.getItem(); | |
| // FIXME: Don't rely on the OnDiskHashTable format here. | |
| auto L = InfoObj.ReadKeyDataLength(LocalPtr); | |
| const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first); | |
| InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second, ResultBuilder); | |
| } | |
| } | |
| return Result; | |
| } | |
| }; | |
| /// Writer for the on-disk hash table. | |
| template<typename ReaderInfo, typename WriterInfo> | |
| class MultiOnDiskHashTableGenerator { | |
| using BaseTable = MultiOnDiskHashTable<ReaderInfo>; | |
| using Generator = llvm::OnDiskChainedHashTableGenerator<WriterInfo>; | |
| Generator Gen; | |
| public: | |
| MultiOnDiskHashTableGenerator() : Gen() {} | |
| void insert(typename WriterInfo::key_type_ref Key, | |
| typename WriterInfo::data_type_ref Data, WriterInfo &Info) { | |
| Gen.insert(Key, Data, Info); | |
| } | |
| void emit(llvm::SmallVectorImpl<char> &Out, WriterInfo &Info, | |
| const BaseTable *Base) { | |
| using namespace llvm::support; | |
| llvm::raw_svector_ostream OutStream(Out); | |
| // Write our header information. | |
| { | |
| endian::Writer Writer(OutStream, llvm::endianness::little); | |
| // Reserve four bytes for the bucket offset. | |
| Writer.write<uint32_t>(0); | |
| if (auto *Merged = Base ? Base->getMergedTable() : nullptr) { | |
| // Write list of overridden files. | |
| Writer.write<uint32_t>(Merged->Files.size()); | |
| for (const auto &F : Merged->Files) | |
| Info.EmitFileRef(OutStream, F); | |
| // Add all merged entries from Base to the generator. | |
| for (auto &KV : Merged->Data) { | |
| if (!Gen.contains(KV.first, Info)) | |
| Gen.insert(KV.first, Info.ImportData(KV.second), Info); | |
| } | |
| } else { | |
| Writer.write<uint32_t>(0); | |
| } | |
| } | |
| // Write the table itself. | |
| uint32_t BucketOffset = Gen.Emit(OutStream, Info); | |
| // Replace the first four bytes with the bucket offset. | |
| endian::write32le(Out.data(), BucketOffset); | |
| } | |
| }; | |
| } // namespace serialization | |
| } // namespace clang | |
| #endif // LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H |