Coverage Report

Created: 2022-01-25 06:29

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Serialization/MultiOnDiskHashTable.h
Line
Count
Source (jump to first uncovered line)
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
1.19M
          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
2.67M
    result_type operator()(void *P) const {
96
2.67M
      return Table::getFromOpaqueValue(P).template get<OnDiskTable *>();
97
2.67M
    }
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
3.78M
  table_range tables() {
106
3.78M
    auto Begin = Tables.begin(), End = Tables.end();
107
3.78M
    if (getMergedTable())
108
121k
      ++Begin;
109
3.78M
    return llvm::make_range(llvm::map_iterator(Begin, AsOnDiskTable()),
110
3.78M
                            llvm::map_iterator(End, AsOnDiskTable()));
111
3.78M
  }
112
113
7.57M
  MergedTable *getMergedTable() const {
114
    // If we already have a merged table, it's the first one.
115
7.57M
    return Tables.empty() ? 
nullptr3.09M
: Table::getFromOpaqueValue(*Tables.begin())
116
4.47M
                                          .template dyn_cast<MergedTable*>();
117
7.57M
  }
118
119
  /// Delete all our current on-disk tables.
120
2.51M
  void clear() {
121
2.51M
    for (auto *T : tables())
122
970k
      delete T;
123
2.51M
    if (auto *M = getMergedTable())
124
90
      delete M;
125
2.51M
    Tables.clear();
126
2.51M
  }
127
128
307
  void removeOverriddenTables() {
129
307
    llvm::DenseSet<file_type> Files;
130
307
    Files.insert(PendingOverrides.begin(), PendingOverrides.end());
131
    // Explicitly capture Files to work around an MSVC 2015 rejects-valid bug.
132
4.45k
    auto ShouldRemove = [&Files](void *T) -> bool {
133
4.45k
      auto *ODT = Table::getFromOpaqueValue(T).template get<OnDiskTable *>();
134
4.45k
      bool Remove = Files.count(ODT->File);
135
4.45k
      if (Remove)
136
3.74k
        delete ODT;
137
4.45k
      return Remove;
138
4.45k
    };
139
307
    Tables.erase(std::remove_if(tables().begin().getCurrent(), Tables.end(),
140
307
                                ShouldRemove),
141
307
                 Tables.end());
142
307
    PendingOverrides.clear();
143
307
  }
144
145
103
  void condense() {
146
103
    MergedTable *Merged = getMergedTable();
147
103
    if (!Merged)
148
91
      Merged = new MergedTable;
149
150
    // Read in all the tables and merge them together.
151
    // FIXME: Be smarter about which tables we merge.
152
532
    for (auto *ODT : tables()) {
153
532
      auto &HT = ODT->Table;
154
532
      Info &InfoObj = HT.getInfoObj();
155
156
1.08M
      for (auto I = HT.data_begin(), E = HT.data_end(); I != E; 
++I1.08M
) {
157
1.08M
        auto *LocalPtr = I.getItem();
158
159
        // FIXME: Don't rely on the OnDiskHashTable format here.
160
1.08M
        auto L = InfoObj.ReadKeyDataLength(LocalPtr);
161
1.08M
        const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first);
162
1.08M
        data_type_builder ValueBuilder(Merged->Data[Key]);
163
1.08M
        InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second,
164
1.08M
                             ValueBuilder);
165
1.08M
      }
166
167
532
      Merged->Files.push_back(ODT->File);
168
532
      delete ODT;
169
532
    }
170
171
103
    Tables.clear();
172
103
    Tables.push_back(Table(Merged).getOpaqueValue());
173
103
  }
174
175
public:
176
1.18M
  MultiOnDiskHashTable() = default;
177
178
  MultiOnDiskHashTable(MultiOnDiskHashTable &&O)
179
      : Tables(std::move(O.Tables)),
180
1.54M
        PendingOverrides(std::move(O.PendingOverrides)) {
181
1.54M
    O.Tables.clear();
182
1.54M
  }
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
2.51M
  ~MultiOnDiskHashTable() { clear(); }
195
196
  /// Add the table \p Data loaded from file \p File.
197
1.19M
  void add(file_type File, storage_type Data, Info InfoObj = Info()) {
198
1.19M
    using namespace llvm::support;
199
200
1.19M
    storage_type Ptr = Data;
201
202
1.19M
    uint32_t BucketOffset = endian::readNext<uint32_t, little, unaligned>(Ptr);
203
204
    // Read the list of overridden files.
205
1.19M
    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
1.19M
    llvm::SmallVector<file_type, 16> OverriddenFiles;
209
1.19M
    OverriddenFiles.reserve(NumFiles);
210
1.20M
    for (/**/; NumFiles != 0; 
--NumFiles8.88k
)
211
8.88k
      OverriddenFiles.push_back(InfoObj.ReadFileRef(Ptr));
212
1.19M
    PendingOverrides.insert(PendingOverrides.end(), OverriddenFiles.begin(),
213
1.19M
                            OverriddenFiles.end());
214
215
    // Read the OnDiskChainedHashTable header.
216
1.19M
    storage_type Buckets = Data + BucketOffset;
217
1.19M
    auto NumBucketsAndEntries =
218
1.19M
        OnDiskTable::HashTable::readNumBucketsAndEntries(Buckets);
219
220
    // Register the table.
221
1.19M
    Table NewTable = new OnDiskTable(File, NumBucketsAndEntries.first,
222
1.19M
                                     NumBucketsAndEntries.second,
223
1.19M
                                     Buckets, Ptr, Data, std::move(InfoObj));
224
1.19M
    Tables.push_back(NewTable.getOpaqueValue());
225
1.19M
  }
226
227
  /// Find and read the lookup results for \p EKey.
228
1.27M
  data_type find(const external_key_type &EKey) {
229
1.27M
    data_type Result;
230
231
1.27M
    if (!PendingOverrides.empty())
232
307
      removeOverriddenTables();
233
234
1.27M
    if (Tables.size() > static_cast<unsigned>(Info::MaxTables))
235
103
      condense();
236
237
1.27M
    internal_key_type Key = Info::GetInternalKey(EKey);
238
1.27M
    auto KeyHash = Info::ComputeHash(Key);
239
240
1.27M
    if (MergedTable *M = getMergedTable()) {
241
121k
      auto It = M->Data.find(Key);
242
121k
      if (It != M->Data.end())
243
4.16k
        Result = It->second;
244
121k
    }
245
246
1.27M
    data_type_builder ResultBuilder(Result);
247
248
1.70M
    for (auto *ODT : tables()) {
249
1.70M
      auto &HT = ODT->Table;
250
1.70M
      auto It = HT.find_hashed(Key, KeyHash);
251
1.70M
      if (It != HT.end())
252
506k
        HT.getInfoObj().ReadDataInto(Key, It.getDataPtr(), It.getDataLen(),
253
506k
                                     ResultBuilder);
254
1.70M
    }
255
256
1.27M
    return Result;
257
1.27M
  }
258
259
  /// Read all the lookup results into a single value. This only makes
260
  /// sense if merging values across keys is meaningful.
261
75
  data_type findAll() {
262
75
    data_type Result;
263
75
    data_type_builder ResultBuilder(Result);
264
265
75
    if (!PendingOverrides.empty())
266
0
      removeOverriddenTables();
267
268
75
    if (MergedTable *M = getMergedTable()) {
269
0
      for (auto &KV : M->Data)
270
0
        Info::MergeDataInto(KV.second, ResultBuilder);
271
0
    }
272
273
80
    for (auto *ODT : tables()) {
274
80
      auto &HT = ODT->Table;
275
80
      Info &InfoObj = HT.getInfoObj();
276
381
      for (auto I = HT.data_begin(), E = HT.data_end(); I != E; 
++I301
) {
277
301
        auto *LocalPtr = I.getItem();
278
279
        // FIXME: Don't rely on the OnDiskHashTable format here.
280
301
        auto L = InfoObj.ReadKeyDataLength(LocalPtr);
281
301
        const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first);
282
301
        InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second, ResultBuilder);
283
301
      }
284
80
    }
285
286
75
    return Result;
287
75
  }
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
116k
  MultiOnDiskHashTableGenerator() : Gen() {}
300
301
  void insert(typename WriterInfo::key_type_ref Key,
302
1.01M
              typename WriterInfo::data_type_ref Data, WriterInfo &Info) {
303
1.01M
    Gen.insert(Key, Data, Info);
304
1.01M
  }
305
306
  void emit(llvm::SmallVectorImpl<char> &Out, WriterInfo &Info,
307
116k
            const BaseTable *Base) {
308
116k
    using namespace llvm::support;
309
310
116k
    llvm::raw_svector_ostream OutStream(Out);
311
312
    // Write our header information.
313
116k
    {
314
116k
      endian::Writer Writer(OutStream, little);
315
316
      // Reserve four bytes for the bucket offset.
317
116k
      Writer.write<uint32_t>(0);
318
319
116k
      if (auto *Merged = Base ? Base->getMergedTable() : nullptr) {
320
        // Write list of overridden files.
321
67
        Writer.write<uint32_t>(Merged->Files.size());
322
67
        for (const auto &F : Merged->Files)
323
406
          Info.EmitFileRef(OutStream, F);
324
325
        // Add all merged entries from Base to the generator.
326
711k
        for (auto &KV : Merged->Data) {
327
711k
          if (!Gen.contains(KV.first, Info))
328
708k
            Gen.insert(KV.first, Info.ImportData(KV.second), Info);
329
711k
        }
330
116k
      } else {
331
116k
        Writer.write<uint32_t>(0);
332
116k
      }
333
116k
    }
334
335
    // Write the table itself.
336
116k
    uint32_t BucketOffset = Gen.Emit(OutStream, Info);
337
338
    // Replace the first four bytes with the bucket offset.
339
116k
    endian::write32le(Out.data(), BucketOffset);
340
116k
  }
341
};
342
343
} // namespace serialization
344
} // namespace clang
345
346
#endif // LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H