MultiOnDiskHashTable.h source code [clang_source_code/lib/Serialization/MultiOnDiskHashTable.h]

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