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