clang/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