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