1*06f32e7eSjoerg //===- MultiOnDiskHashTable.h - Merged set of hash tables -------*- C++ -*-===// 2*06f32e7eSjoerg // 3*06f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*06f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information. 5*06f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*06f32e7eSjoerg // 7*06f32e7eSjoerg //===----------------------------------------------------------------------===// 8*06f32e7eSjoerg // 9*06f32e7eSjoerg // This file provides a hash table data structure suitable for incremental and 10*06f32e7eSjoerg // distributed storage across a set of files. 11*06f32e7eSjoerg // 12*06f32e7eSjoerg // Multiple hash tables from different files are implicitly merged to improve 13*06f32e7eSjoerg // performance, and on reload the merged table will override those from other 14*06f32e7eSjoerg // files. 15*06f32e7eSjoerg // 16*06f32e7eSjoerg //===----------------------------------------------------------------------===// 17*06f32e7eSjoerg 18*06f32e7eSjoerg #ifndef LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H 19*06f32e7eSjoerg #define LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H 20*06f32e7eSjoerg 21*06f32e7eSjoerg #include "llvm/ADT/DenseMap.h" 22*06f32e7eSjoerg #include "llvm/ADT/DenseSet.h" 23*06f32e7eSjoerg #include "llvm/ADT/PointerUnion.h" 24*06f32e7eSjoerg #include "llvm/ADT/STLExtras.h" 25*06f32e7eSjoerg #include "llvm/ADT/SmallVector.h" 26*06f32e7eSjoerg #include "llvm/ADT/TinyPtrVector.h" 27*06f32e7eSjoerg #include "llvm/ADT/iterator_range.h" 28*06f32e7eSjoerg #include "llvm/Support/Endian.h" 29*06f32e7eSjoerg #include "llvm/Support/EndianStream.h" 30*06f32e7eSjoerg #include "llvm/Support/OnDiskHashTable.h" 31*06f32e7eSjoerg #include "llvm/Support/raw_ostream.h" 32*06f32e7eSjoerg #include <algorithm> 33*06f32e7eSjoerg #include <cstdint> 34*06f32e7eSjoerg #include <vector> 35*06f32e7eSjoerg 36*06f32e7eSjoerg namespace clang { 37*06f32e7eSjoerg namespace serialization { 38*06f32e7eSjoerg 39*06f32e7eSjoerg /// A collection of on-disk hash tables, merged when relevant for performance. 40*06f32e7eSjoerg template<typename Info> class MultiOnDiskHashTable { 41*06f32e7eSjoerg public: 42*06f32e7eSjoerg /// A handle to a file, used when overriding tables. 43*06f32e7eSjoerg using file_type = typename Info::file_type; 44*06f32e7eSjoerg 45*06f32e7eSjoerg /// A pointer to an on-disk representation of the hash table. 46*06f32e7eSjoerg using storage_type = const unsigned char *; 47*06f32e7eSjoerg 48*06f32e7eSjoerg using external_key_type = typename Info::external_key_type; 49*06f32e7eSjoerg using internal_key_type = typename Info::internal_key_type; 50*06f32e7eSjoerg using data_type = typename Info::data_type; 51*06f32e7eSjoerg using data_type_builder = typename Info::data_type_builder; 52*06f32e7eSjoerg using hash_value_type = unsigned; 53*06f32e7eSjoerg 54*06f32e7eSjoerg private: 55*06f32e7eSjoerg /// The generator is permitted to read our merged table. 56*06f32e7eSjoerg template<typename ReaderInfo, typename WriterInfo> 57*06f32e7eSjoerg friend class MultiOnDiskHashTableGenerator; 58*06f32e7eSjoerg 59*06f32e7eSjoerg /// A hash table stored on disk. 60*06f32e7eSjoerg struct OnDiskTable { 61*06f32e7eSjoerg using HashTable = llvm::OnDiskIterableChainedHashTable<Info>; 62*06f32e7eSjoerg 63*06f32e7eSjoerg file_type File; 64*06f32e7eSjoerg HashTable Table; 65*06f32e7eSjoerg OnDiskTableOnDiskTable66*06f32e7eSjoerg OnDiskTable(file_type File, unsigned NumBuckets, unsigned NumEntries, 67*06f32e7eSjoerg storage_type Buckets, storage_type Payload, storage_type Base, 68*06f32e7eSjoerg const Info &InfoObj) 69*06f32e7eSjoerg : File(File), 70*06f32e7eSjoerg Table(NumBuckets, NumEntries, Buckets, Payload, Base, InfoObj) {} 71*06f32e7eSjoerg }; 72*06f32e7eSjoerg 73*06f32e7eSjoerg struct MergedTable { 74*06f32e7eSjoerg std::vector<file_type> Files; 75*06f32e7eSjoerg llvm::DenseMap<internal_key_type, data_type> Data; 76*06f32e7eSjoerg }; 77*06f32e7eSjoerg 78*06f32e7eSjoerg using Table = llvm::PointerUnion<OnDiskTable *, MergedTable *>; 79*06f32e7eSjoerg using TableVector = llvm::TinyPtrVector<void *>; 80*06f32e7eSjoerg 81*06f32e7eSjoerg /// The current set of on-disk and merged tables. 82*06f32e7eSjoerg /// We manually store the opaque value of the Table because TinyPtrVector 83*06f32e7eSjoerg /// can't cope with holding a PointerUnion directly. 84*06f32e7eSjoerg /// There can be at most one MergedTable in this vector, and if present, 85*06f32e7eSjoerg /// it is the first table. 86*06f32e7eSjoerg TableVector Tables; 87*06f32e7eSjoerg 88*06f32e7eSjoerg /// Files corresponding to overridden tables that we've not yet 89*06f32e7eSjoerg /// discarded. 90*06f32e7eSjoerg llvm::TinyPtrVector<file_type> PendingOverrides; 91*06f32e7eSjoerg 92*06f32e7eSjoerg struct AsOnDiskTable { 93*06f32e7eSjoerg using result_type = OnDiskTable *; 94*06f32e7eSjoerg operatorAsOnDiskTable95*06f32e7eSjoerg result_type operator()(void *P) const { 96*06f32e7eSjoerg return Table::getFromOpaqueValue(P).template get<OnDiskTable *>(); 97*06f32e7eSjoerg } 98*06f32e7eSjoerg }; 99*06f32e7eSjoerg 100*06f32e7eSjoerg using table_iterator = 101*06f32e7eSjoerg llvm::mapped_iterator<TableVector::iterator, AsOnDiskTable>; 102*06f32e7eSjoerg using table_range = llvm::iterator_range<table_iterator>; 103*06f32e7eSjoerg 104*06f32e7eSjoerg /// The current set of on-disk tables. tables()105*06f32e7eSjoerg table_range tables() { 106*06f32e7eSjoerg auto Begin = Tables.begin(), End = Tables.end(); 107*06f32e7eSjoerg if (getMergedTable()) 108*06f32e7eSjoerg ++Begin; 109*06f32e7eSjoerg return llvm::make_range(llvm::map_iterator(Begin, AsOnDiskTable()), 110*06f32e7eSjoerg llvm::map_iterator(End, AsOnDiskTable())); 111*06f32e7eSjoerg } 112*06f32e7eSjoerg getMergedTable()113*06f32e7eSjoerg MergedTable *getMergedTable() const { 114*06f32e7eSjoerg // If we already have a merged table, it's the first one. 115*06f32e7eSjoerg return Tables.empty() ? nullptr : Table::getFromOpaqueValue(*Tables.begin()) 116*06f32e7eSjoerg .template dyn_cast<MergedTable*>(); 117*06f32e7eSjoerg } 118*06f32e7eSjoerg 119*06f32e7eSjoerg /// Delete all our current on-disk tables. clear()120*06f32e7eSjoerg void clear() { 121*06f32e7eSjoerg for (auto *T : tables()) 122*06f32e7eSjoerg delete T; 123*06f32e7eSjoerg if (auto *M = getMergedTable()) 124*06f32e7eSjoerg delete M; 125*06f32e7eSjoerg Tables.clear(); 126*06f32e7eSjoerg } 127*06f32e7eSjoerg removeOverriddenTables()128*06f32e7eSjoerg void removeOverriddenTables() { 129*06f32e7eSjoerg llvm::DenseSet<file_type> Files; 130*06f32e7eSjoerg Files.insert(PendingOverrides.begin(), PendingOverrides.end()); 131*06f32e7eSjoerg // Explicitly capture Files to work around an MSVC 2015 rejects-valid bug. 132*06f32e7eSjoerg auto ShouldRemove = [&Files](void *T) -> bool { 133*06f32e7eSjoerg auto *ODT = Table::getFromOpaqueValue(T).template get<OnDiskTable *>(); 134*06f32e7eSjoerg bool Remove = Files.count(ODT->File); 135*06f32e7eSjoerg if (Remove) 136*06f32e7eSjoerg delete ODT; 137*06f32e7eSjoerg return Remove; 138*06f32e7eSjoerg }; 139*06f32e7eSjoerg Tables.erase(std::remove_if(tables().begin().getCurrent(), Tables.end(), 140*06f32e7eSjoerg ShouldRemove), 141*06f32e7eSjoerg Tables.end()); 142*06f32e7eSjoerg PendingOverrides.clear(); 143*06f32e7eSjoerg } 144*06f32e7eSjoerg condense()145*06f32e7eSjoerg void condense() { 146*06f32e7eSjoerg MergedTable *Merged = getMergedTable(); 147*06f32e7eSjoerg if (!Merged) 148*06f32e7eSjoerg Merged = new MergedTable; 149*06f32e7eSjoerg 150*06f32e7eSjoerg // Read in all the tables and merge them together. 151*06f32e7eSjoerg // FIXME: Be smarter about which tables we merge. 152*06f32e7eSjoerg for (auto *ODT : tables()) { 153*06f32e7eSjoerg auto &HT = ODT->Table; 154*06f32e7eSjoerg Info &InfoObj = HT.getInfoObj(); 155*06f32e7eSjoerg 156*06f32e7eSjoerg for (auto I = HT.data_begin(), E = HT.data_end(); I != E; ++I) { 157*06f32e7eSjoerg auto *LocalPtr = I.getItem(); 158*06f32e7eSjoerg 159*06f32e7eSjoerg // FIXME: Don't rely on the OnDiskHashTable format here. 160*06f32e7eSjoerg auto L = InfoObj.ReadKeyDataLength(LocalPtr); 161*06f32e7eSjoerg const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first); 162*06f32e7eSjoerg data_type_builder ValueBuilder(Merged->Data[Key]); 163*06f32e7eSjoerg InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second, 164*06f32e7eSjoerg ValueBuilder); 165*06f32e7eSjoerg } 166*06f32e7eSjoerg 167*06f32e7eSjoerg Merged->Files.push_back(ODT->File); 168*06f32e7eSjoerg delete ODT; 169*06f32e7eSjoerg } 170*06f32e7eSjoerg 171*06f32e7eSjoerg Tables.clear(); 172*06f32e7eSjoerg Tables.push_back(Table(Merged).getOpaqueValue()); 173*06f32e7eSjoerg } 174*06f32e7eSjoerg 175*06f32e7eSjoerg public: 176*06f32e7eSjoerg MultiOnDiskHashTable() = default; 177*06f32e7eSjoerg MultiOnDiskHashTable(MultiOnDiskHashTable && O)178*06f32e7eSjoerg MultiOnDiskHashTable(MultiOnDiskHashTable &&O) 179*06f32e7eSjoerg : Tables(std::move(O.Tables)), 180*06f32e7eSjoerg PendingOverrides(std::move(O.PendingOverrides)) { 181*06f32e7eSjoerg O.Tables.clear(); 182*06f32e7eSjoerg } 183*06f32e7eSjoerg 184*06f32e7eSjoerg MultiOnDiskHashTable &operator=(MultiOnDiskHashTable &&O) { 185*06f32e7eSjoerg if (&O == this) 186*06f32e7eSjoerg return *this; 187*06f32e7eSjoerg clear(); 188*06f32e7eSjoerg Tables = std::move(O.Tables); 189*06f32e7eSjoerg O.Tables.clear(); 190*06f32e7eSjoerg PendingOverrides = std::move(O.PendingOverrides); 191*06f32e7eSjoerg return *this; 192*06f32e7eSjoerg } 193*06f32e7eSjoerg ~MultiOnDiskHashTable()194*06f32e7eSjoerg ~MultiOnDiskHashTable() { clear(); } 195*06f32e7eSjoerg 196*06f32e7eSjoerg /// Add the table \p Data loaded from file \p File. 197*06f32e7eSjoerg void add(file_type File, storage_type Data, Info InfoObj = Info()) { 198*06f32e7eSjoerg using namespace llvm::support; 199*06f32e7eSjoerg 200*06f32e7eSjoerg storage_type Ptr = Data; 201*06f32e7eSjoerg 202*06f32e7eSjoerg uint32_t BucketOffset = endian::readNext<uint32_t, little, unaligned>(Ptr); 203*06f32e7eSjoerg 204*06f32e7eSjoerg // Read the list of overridden files. 205*06f32e7eSjoerg uint32_t NumFiles = endian::readNext<uint32_t, little, unaligned>(Ptr); 206*06f32e7eSjoerg // FIXME: Add a reserve() to TinyPtrVector so that we don't need to make 207*06f32e7eSjoerg // an additional copy. 208*06f32e7eSjoerg llvm::SmallVector<file_type, 16> OverriddenFiles; 209*06f32e7eSjoerg OverriddenFiles.reserve(NumFiles); 210*06f32e7eSjoerg for (/**/; NumFiles != 0; --NumFiles) 211*06f32e7eSjoerg OverriddenFiles.push_back(InfoObj.ReadFileRef(Ptr)); 212*06f32e7eSjoerg PendingOverrides.insert(PendingOverrides.end(), OverriddenFiles.begin(), 213*06f32e7eSjoerg OverriddenFiles.end()); 214*06f32e7eSjoerg 215*06f32e7eSjoerg // Read the OnDiskChainedHashTable header. 216*06f32e7eSjoerg storage_type Buckets = Data + BucketOffset; 217*06f32e7eSjoerg auto NumBucketsAndEntries = 218*06f32e7eSjoerg OnDiskTable::HashTable::readNumBucketsAndEntries(Buckets); 219*06f32e7eSjoerg 220*06f32e7eSjoerg // Register the table. 221*06f32e7eSjoerg Table NewTable = new OnDiskTable(File, NumBucketsAndEntries.first, 222*06f32e7eSjoerg NumBucketsAndEntries.second, 223*06f32e7eSjoerg Buckets, Ptr, Data, std::move(InfoObj)); 224*06f32e7eSjoerg Tables.push_back(NewTable.getOpaqueValue()); 225*06f32e7eSjoerg } 226*06f32e7eSjoerg 227*06f32e7eSjoerg /// Find and read the lookup results for \p EKey. find(const external_key_type & EKey)228*06f32e7eSjoerg data_type find(const external_key_type &EKey) { 229*06f32e7eSjoerg data_type Result; 230*06f32e7eSjoerg 231*06f32e7eSjoerg if (!PendingOverrides.empty()) 232*06f32e7eSjoerg removeOverriddenTables(); 233*06f32e7eSjoerg 234*06f32e7eSjoerg if (Tables.size() > static_cast<unsigned>(Info::MaxTables)) 235*06f32e7eSjoerg condense(); 236*06f32e7eSjoerg 237*06f32e7eSjoerg internal_key_type Key = Info::GetInternalKey(EKey); 238*06f32e7eSjoerg auto KeyHash = Info::ComputeHash(Key); 239*06f32e7eSjoerg 240*06f32e7eSjoerg if (MergedTable *M = getMergedTable()) { 241*06f32e7eSjoerg auto It = M->Data.find(Key); 242*06f32e7eSjoerg if (It != M->Data.end()) 243*06f32e7eSjoerg Result = It->second; 244*06f32e7eSjoerg } 245*06f32e7eSjoerg 246*06f32e7eSjoerg data_type_builder ResultBuilder(Result); 247*06f32e7eSjoerg 248*06f32e7eSjoerg for (auto *ODT : tables()) { 249*06f32e7eSjoerg auto &HT = ODT->Table; 250*06f32e7eSjoerg auto It = HT.find_hashed(Key, KeyHash); 251*06f32e7eSjoerg if (It != HT.end()) 252*06f32e7eSjoerg HT.getInfoObj().ReadDataInto(Key, It.getDataPtr(), It.getDataLen(), 253*06f32e7eSjoerg ResultBuilder); 254*06f32e7eSjoerg } 255*06f32e7eSjoerg 256*06f32e7eSjoerg return Result; 257*06f32e7eSjoerg } 258*06f32e7eSjoerg 259*06f32e7eSjoerg /// Read all the lookup results into a single value. This only makes 260*06f32e7eSjoerg /// sense if merging values across keys is meaningful. findAll()261*06f32e7eSjoerg data_type findAll() { 262*06f32e7eSjoerg data_type Result; 263*06f32e7eSjoerg data_type_builder ResultBuilder(Result); 264*06f32e7eSjoerg 265*06f32e7eSjoerg if (!PendingOverrides.empty()) 266*06f32e7eSjoerg removeOverriddenTables(); 267*06f32e7eSjoerg 268*06f32e7eSjoerg if (MergedTable *M = getMergedTable()) { 269*06f32e7eSjoerg for (auto &KV : M->Data) 270*06f32e7eSjoerg Info::MergeDataInto(KV.second, ResultBuilder); 271*06f32e7eSjoerg } 272*06f32e7eSjoerg 273*06f32e7eSjoerg for (auto *ODT : tables()) { 274*06f32e7eSjoerg auto &HT = ODT->Table; 275*06f32e7eSjoerg Info &InfoObj = HT.getInfoObj(); 276*06f32e7eSjoerg for (auto I = HT.data_begin(), E = HT.data_end(); I != E; ++I) { 277*06f32e7eSjoerg auto *LocalPtr = I.getItem(); 278*06f32e7eSjoerg 279*06f32e7eSjoerg // FIXME: Don't rely on the OnDiskHashTable format here. 280*06f32e7eSjoerg auto L = InfoObj.ReadKeyDataLength(LocalPtr); 281*06f32e7eSjoerg const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first); 282*06f32e7eSjoerg InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second, ResultBuilder); 283*06f32e7eSjoerg } 284*06f32e7eSjoerg } 285*06f32e7eSjoerg 286*06f32e7eSjoerg return Result; 287*06f32e7eSjoerg } 288*06f32e7eSjoerg }; 289*06f32e7eSjoerg 290*06f32e7eSjoerg /// Writer for the on-disk hash table. 291*06f32e7eSjoerg template<typename ReaderInfo, typename WriterInfo> 292*06f32e7eSjoerg class MultiOnDiskHashTableGenerator { 293*06f32e7eSjoerg using BaseTable = MultiOnDiskHashTable<ReaderInfo>; 294*06f32e7eSjoerg using Generator = llvm::OnDiskChainedHashTableGenerator<WriterInfo>; 295*06f32e7eSjoerg 296*06f32e7eSjoerg Generator Gen; 297*06f32e7eSjoerg 298*06f32e7eSjoerg public: MultiOnDiskHashTableGenerator()299*06f32e7eSjoerg MultiOnDiskHashTableGenerator() : Gen() {} 300*06f32e7eSjoerg insert(typename WriterInfo::key_type_ref Key,typename WriterInfo::data_type_ref Data,WriterInfo & Info)301*06f32e7eSjoerg void insert(typename WriterInfo::key_type_ref Key, 302*06f32e7eSjoerg typename WriterInfo::data_type_ref Data, WriterInfo &Info) { 303*06f32e7eSjoerg Gen.insert(Key, Data, Info); 304*06f32e7eSjoerg } 305*06f32e7eSjoerg emit(llvm::SmallVectorImpl<char> & Out,WriterInfo & Info,const BaseTable * Base)306*06f32e7eSjoerg void emit(llvm::SmallVectorImpl<char> &Out, WriterInfo &Info, 307*06f32e7eSjoerg const BaseTable *Base) { 308*06f32e7eSjoerg using namespace llvm::support; 309*06f32e7eSjoerg 310*06f32e7eSjoerg llvm::raw_svector_ostream OutStream(Out); 311*06f32e7eSjoerg 312*06f32e7eSjoerg // Write our header information. 313*06f32e7eSjoerg { 314*06f32e7eSjoerg endian::Writer Writer(OutStream, little); 315*06f32e7eSjoerg 316*06f32e7eSjoerg // Reserve four bytes for the bucket offset. 317*06f32e7eSjoerg Writer.write<uint32_t>(0); 318*06f32e7eSjoerg 319*06f32e7eSjoerg if (auto *Merged = Base ? Base->getMergedTable() : nullptr) { 320*06f32e7eSjoerg // Write list of overridden files. 321*06f32e7eSjoerg Writer.write<uint32_t>(Merged->Files.size()); 322*06f32e7eSjoerg for (const auto &F : Merged->Files) 323*06f32e7eSjoerg Info.EmitFileRef(OutStream, F); 324*06f32e7eSjoerg 325*06f32e7eSjoerg // Add all merged entries from Base to the generator. 326*06f32e7eSjoerg for (auto &KV : Merged->Data) { 327*06f32e7eSjoerg if (!Gen.contains(KV.first, Info)) 328*06f32e7eSjoerg Gen.insert(KV.first, Info.ImportData(KV.second), Info); 329*06f32e7eSjoerg } 330*06f32e7eSjoerg } else { 331*06f32e7eSjoerg Writer.write<uint32_t>(0); 332*06f32e7eSjoerg } 333*06f32e7eSjoerg } 334*06f32e7eSjoerg 335*06f32e7eSjoerg // Write the table itself. 336*06f32e7eSjoerg uint32_t BucketOffset = Gen.Emit(OutStream, Info); 337*06f32e7eSjoerg 338*06f32e7eSjoerg // Replace the first four bytes with the bucket offset. 339*06f32e7eSjoerg endian::write32le(Out.data(), BucketOffset); 340*06f32e7eSjoerg } 341*06f32e7eSjoerg }; 342*06f32e7eSjoerg 343*06f32e7eSjoerg } // namespace serialization 344*06f32e7eSjoerg } // namespace clang 345*06f32e7eSjoerg 346*06f32e7eSjoerg #endif // LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H 347