Coverage Report

Created: 2019-07-24 05:18

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