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 =
 203         endian::readNext<uint32_t, llvm::endianness::little>(Ptr);
 204
 205     // Read the list of overridden files.
 206     uint32_t NumFiles =
 207         endian::readNext<uint32_t, llvm::endianness::little>(Ptr);
 208     // FIXME: Add a reserve() to TinyPtrVector so that we don't need to make
 209     // an additional copy.
 210     llvm::SmallVector<file_type, 16> OverriddenFiles;
 211     OverriddenFiles.reserve(NumFiles);
 212     for (/**/; NumFiles != 0; --NumFiles)
 213       OverriddenFiles.push_back(InfoObj.ReadFileRef(Ptr));
 214     PendingOverrides.insert(PendingOverrides.end(), OverriddenFiles.begin(),
 215                             OverriddenFiles.end());
 216
 217     // Read the OnDiskChainedHashTable header.
 218     storage_type Buckets = Data + BucketOffset;
 219     auto NumBucketsAndEntries =
 220         OnDiskTable::HashTable::readNumBucketsAndEntries(Buckets);
 221
 222     // Register the table.
 223     Table NewTable = new OnDiskTable(File, NumBucketsAndEntries.first,
 224                                      NumBucketsAndEntries.second,
 225                                      Buckets, Ptr, Data, std::move(InfoObj));
 226     Tables.push_back(NewTable.getOpaqueValue());
 227   }
 228
 229   /// Find and read the lookup results for \p EKey.
 230   data_type find(const external_key_type &EKey) {
 231     data_type Result;
 232
 233     if (!PendingOverrides.empty())
 234       removeOverriddenTables();
 235
 236     if (Tables.size() > static_cast<unsigned>(Info::MaxTables))
 237       condense();
 238
 239     internal_key_type Key = Info::GetInternalKey(EKey);
 240     auto KeyHash = Info::ComputeHash(Key);
 241
 242     if (MergedTable *M = getMergedTable()) {
 243       auto It = M->Data.find(Key);
 244       if (It != M->Data.end())
 245         Result = It->second;
 246     }
 247
 248     data_type_builder ResultBuilder(Result);
 249
 250     for (auto *ODT : tables()) {
 251       auto &HT = ODT->Table;
 252       auto It = HT.find_hashed(Key, KeyHash);
 253       if (It != HT.end())
 254         HT.getInfoObj().ReadDataInto(Key, It.getDataPtr(), It.getDataLen(),
 255                                      ResultBuilder);
 256     }
 257
 258     return Result;
 259   }
 260
 261   /// Read all the lookup results into a single value. This only makes
 262   /// sense if merging values across keys is meaningful.
 263   data_type findAll() {
 264     data_type Result;
 265     data_type_builder ResultBuilder(Result);
 266
 267     if (!PendingOverrides.empty())
 268       removeOverriddenTables();
 269
 270     if (MergedTable *M = getMergedTable()) {
 271       for (auto &KV : M->Data)
 272         Info::MergeDataInto(KV.second, ResultBuilder);
 273     }
 274
 275     for (auto *ODT : tables()) {
 276       auto &HT = ODT->Table;
 277       Info &InfoObj = HT.getInfoObj();
 278       for (auto I = HT.data_begin(), E = HT.data_end(); I != E; ++I) {
 279         auto *LocalPtr = I.getItem();
 280
 281         // FIXME: Don't rely on the OnDiskHashTable format here.
 282         auto L = InfoObj.ReadKeyDataLength(LocalPtr);
 283         const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first);
 284         InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second, ResultBuilder);
 285       }
 286     }
 287
 288     return Result;
 289   }
 290 };
 291
 292 /// Writer for the on-disk hash table.
 293 template<typename ReaderInfo, typename WriterInfo>
 294 class MultiOnDiskHashTableGenerator {
 295   using BaseTable = MultiOnDiskHashTable<ReaderInfo>;
 296   using Generator = llvm::OnDiskChainedHashTableGenerator<WriterInfo>;
 297
 298   Generator Gen;
 299
 300 public:
 301   MultiOnDiskHashTableGenerator() : Gen() {}
 302
 303   void insert(typename WriterInfo::key_type_ref Key,
 304               typename WriterInfo::data_type_ref Data, WriterInfo &Info) {
 305     Gen.insert(Key, Data, Info);
 306   }
 307
 308   void emit(llvm::SmallVectorImpl<char> &Out, WriterInfo &Info,
 309             const BaseTable *Base) {
 310     using namespace llvm::support;
 311
 312     llvm::raw_svector_ostream OutStream(Out);
 313
 314     // Write our header information.
 315     {
 316       endian::Writer Writer(OutStream, llvm::endianness::little);
 317
 318       // Reserve four bytes for the bucket offset.
 319       Writer.write<uint32_t>(0);
 320
 321       if (auto *Merged = Base ? Base->getMergedTable() : nullptr) {
 322         // Write list of overridden files.
 323         Writer.write<uint32_t>(Merged->Files.size());
 324         for (const auto &F : Merged->Files)
 325           Info.EmitFileRef(OutStream, F);
 326
 327         // Add all merged entries from Base to the generator.
 328         for (auto &KV : Merged->Data) {
 329           if (!Gen.contains(KV.first, Info))
 330             Gen.insert(KV.first, Info.ImportData(KV.second), Info);
 331         }
 332       } else {
 333         Writer.write<uint32_t>(0);
 334       }
 335     }
 336
 337     // Write the table itself.
 338     uint32_t BucketOffset = Gen.Emit(OutStream, Info);
 339
 340     // Replace the first four bytes with the bucket offset.
 341     endian::write32le(Out.data(), BucketOffset);
 342   }
 343 };
 344
 345 } // namespace serialization
 346 } // namespace clang
 347
 348 #endif // LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H