contrib/llvm/tools/clang/lib/Serialization/MultiOnDiskHashTable.h

   1 //===--- MultiOnDiskHashTable.h - Merged set of hash tables -----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file provides a hash table data structure suitable for incremental and
  11 //  distributed storage across a set of files.
  12 //
  13 //  Multiple hash tables from different files are implicitly merged to improve
  14 //  performance, and on reload the merged table will override those from other
  15 //  files.
  16 //
  17 //===----------------------------------------------------------------------===//
  18 #ifndef LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H
  19 #define LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H
  20
  21 #include "llvm/ADT/PointerUnion.h"
  22 #include "llvm/Support/EndianStream.h"
  23 #include "llvm/Support/OnDiskHashTable.h"
  24
  25 namespace clang {
  26 namespace serialization {
  27
  28 class ModuleFile;
  29
  30 /// \brief A collection of on-disk hash tables, merged when relevant for performance.
  31 template<typename Info> class MultiOnDiskHashTable {
  32 public:
  33   /// A handle to a file, used when overriding tables.
  34   typedef typename Info::file_type file_type;
  35   /// A pointer to an on-disk representation of the hash table.
  36   typedef const unsigned char *storage_type;
  37
  38   typedef typename Info::external_key_type external_key_type;
  39   typedef typename Info::internal_key_type internal_key_type;
  40   typedef typename Info::data_type data_type;
  41   typedef typename Info::data_type_builder data_type_builder;
  42   typedef unsigned hash_value_type;
  43
  44 private:
  45   /// \brief A hash table stored on disk.
  46   struct OnDiskTable {
  47     typedef llvm::OnDiskIterableChainedHashTable<Info> HashTable;
  48
  49     file_type File;
  50     HashTable Table;
  51
  52     OnDiskTable(file_type File, unsigned NumBuckets, unsigned NumEntries,
  53                 storage_type Buckets, storage_type Payload, storage_type Base,
  54                 const Info &InfoObj)
  55         : File(File),
  56           Table(NumBuckets, NumEntries, Buckets, Payload, Base, InfoObj) {}
  57   };
  58
  59   struct MergedTable {
  60     std::vector<file_type> Files;
  61     llvm::DenseMap<internal_key_type, data_type> Data;
  62   };
  63
  64   typedef llvm::PointerUnion<OnDiskTable*, MergedTable*> Table;
  65   typedef llvm::TinyPtrVector<void*> TableVector;
  66
  67   /// \brief The current set of on-disk and merged tables.
  68   /// We manually store the opaque value of the Table because TinyPtrVector
  69   /// can't cope with holding a PointerUnion directly.
  70   /// There can be at most one MergedTable in this vector, and if present,
  71   /// it is the first table.
  72   TableVector Tables;
  73
  74   /// \brief Files corresponding to overridden tables that we've not yet
  75   /// discarded.
  76   llvm::TinyPtrVector<file_type> PendingOverrides;
  77
  78   struct AsOnDiskTable {
  79     typedef OnDiskTable *result_type;
  80     result_type operator()(void *P) const {
  81       return Table::getFromOpaqueValue(P).template get<OnDiskTable *>();
  82     }
  83   };
  84   typedef llvm::mapped_iterator<TableVector::iterator, AsOnDiskTable>
  85       table_iterator;
  86   typedef llvm::iterator_range<table_iterator> table_range;
  87
  88   /// \brief The current set of on-disk tables.
  89   table_range tables() {
  90     auto Begin = Tables.begin(), End = Tables.end();
  91     if (getMergedTable())
  92       ++Begin;
  93     return llvm::make_range(llvm::map_iterator(Begin, AsOnDiskTable()),
  94                             llvm::map_iterator(End, AsOnDiskTable()));
  95   }
  96
  97   MergedTable *getMergedTable() const {
  98     // If we already have a merged table, it's the first one.
  99     return Tables.empty() ? nullptr : Table::getFromOpaqueValue(*Tables.begin())
 100                                           .template dyn_cast<MergedTable*>();
 101   }
 102
 103   /// \brief Delete all our current on-disk tables.
 104   void clear() {
 105     for (auto *T : tables())
 106       delete T;
 107     if (auto *M = getMergedTable())
 108       delete M;
 109     Tables.clear();
 110   }
 111
 112   void removeOverriddenTables() {
 113     llvm::DenseSet<file_type> Files;
 114     Files.insert(PendingOverrides.begin(), PendingOverrides.end());
 115     // Explicitly capture Files to work around an MSVC 2015 rejects-valid bug.
 116     auto ShouldRemove = [&Files](void *T) -> bool {
 117       auto *ODT = Table::getFromOpaqueValue(T).template get<OnDiskTable *>();
 118       bool Remove = Files.count(ODT->File);
 119       if (Remove)
 120         delete ODT;
 121       return Remove;
 122     };
 123     Tables.erase(std::remove_if(tables().begin().getCurrent(), Tables.end(),
 124                                 ShouldRemove),
 125                  Tables.end());
 126     PendingOverrides.clear();
 127   }
 128
 129   void condense() {
 130     MergedTable *Merged = getMergedTable();
 131     if (!Merged)
 132       Merged = new MergedTable;
 133
 134     // Read in all the tables and merge them together.
 135     // FIXME: Be smarter about which tables we merge.
 136     for (auto *ODT : tables()) {
 137       auto &HT = ODT->Table;
 138       Info &InfoObj = HT.getInfoObj();
 139
 140       for (auto I = HT.data_begin(), E = HT.data_end(); I != E; ++I) {
 141         auto *LocalPtr = I.getItem();
 142
 143         // FIXME: Don't rely on the OnDiskHashTable format here.
 144         auto L = InfoObj.ReadKeyDataLength(LocalPtr);
 145         const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first);
 146         data_type_builder ValueBuilder(Merged->Data[Key]);
 147         InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second,
 148                              ValueBuilder);
 149       }
 150
 151       Merged->Files.push_back(ODT->File);
 152       delete ODT;
 153     }
 154
 155     Tables.clear();
 156     Tables.push_back(Table(Merged).getOpaqueValue());
 157   }
 158
 159   /// The generator is permitted to read our merged table.
 160   template<typename ReaderInfo, typename WriterInfo>
 161   friend class MultiOnDiskHashTableGenerator;
 162
 163 public:
 164   MultiOnDiskHashTable() {}
 165   MultiOnDiskHashTable(MultiOnDiskHashTable &&O)
 166       : Tables(std::move(O.Tables)),
 167         PendingOverrides(std::move(O.PendingOverrides)) {
 168     O.Tables.clear();
 169   }
 170   MultiOnDiskHashTable &operator=(MultiOnDiskHashTable &&O) {
 171     if (&O == this)
 172       return *this;
 173     clear();
 174     Tables = std::move(O.Tables);
 175     O.Tables.clear();
 176     PendingOverrides = std::move(O.PendingOverrides);
 177     return *this;
 178   }
 179   ~MultiOnDiskHashTable() { clear(); }
 180
 181   /// \brief Add the table \p Data loaded from file \p File.
 182   void add(file_type File, storage_type Data, Info InfoObj = Info()) {
 183     using namespace llvm::support;
 184     storage_type Ptr = Data;
 185
 186     uint32_t BucketOffset = endian::readNext<uint32_t, little, unaligned>(Ptr);
 187
 188     // Read the list of overridden files.
 189     uint32_t NumFiles = endian::readNext<uint32_t, little, unaligned>(Ptr);
 190     // FIXME: Add a reserve() to TinyPtrVector so that we don't need to make
 191     // an additional copy.
 192     llvm::SmallVector<file_type, 16> OverriddenFiles;
 193     OverriddenFiles.reserve(NumFiles);
 194     for (/**/; NumFiles != 0; --NumFiles)
 195       OverriddenFiles.push_back(InfoObj.ReadFileRef(Ptr));
 196     PendingOverrides.insert(PendingOverrides.end(), OverriddenFiles.begin(),
 197                             OverriddenFiles.end());
 198
 199     // Read the OnDiskChainedHashTable header.
 200     storage_type Buckets = Data + BucketOffset;
 201     auto NumBucketsAndEntries =
 202         OnDiskTable::HashTable::readNumBucketsAndEntries(Buckets);
 203
 204     // Register the table.
 205     Table NewTable = new OnDiskTable(File, NumBucketsAndEntries.first,
 206                                      NumBucketsAndEntries.second,
 207                                      Buckets, Ptr, Data, std::move(InfoObj));
 208     Tables.push_back(NewTable.getOpaqueValue());
 209   }
 210
 211   /// \brief Find and read the lookup results for \p EKey.
 212   data_type find(const external_key_type &EKey) {
 213     data_type Result;
 214
 215     if (!PendingOverrides.empty())
 216       removeOverriddenTables();
 217
 218     if (Tables.size() > static_cast<unsigned>(Info::MaxTables))
 219       condense();
 220
 221     internal_key_type Key = Info::GetInternalKey(EKey);
 222     auto KeyHash = Info::ComputeHash(Key);
 223
 224     if (MergedTable *M = getMergedTable()) {
 225       auto It = M->Data.find(Key);
 226       if (It != M->Data.end())
 227         Result = It->second;
 228     }
 229
 230     data_type_builder ResultBuilder(Result);
 231
 232     for (auto *ODT : tables()) {
 233       auto &HT = ODT->Table;
 234       auto It = HT.find_hashed(Key, KeyHash);
 235       if (It != HT.end())
 236         HT.getInfoObj().ReadDataInto(Key, It.getDataPtr(), It.getDataLen(),
 237                                      ResultBuilder);
 238     }
 239
 240     return Result;
 241   }
 242
 243   /// \brief Read all the lookup results into a single value. This only makes
 244   /// sense if merging values across keys is meaningful.
 245   data_type findAll() {
 246     data_type Result;
 247     data_type_builder ResultBuilder(Result);
 248
 249     if (!PendingOverrides.empty())
 250       removeOverriddenTables();
 251
 252     if (MergedTable *M = getMergedTable()) {
 253       for (auto &KV : M->Data)
 254         Info::MergeDataInto(KV.second, ResultBuilder);
 255     }
 256
 257     for (auto *ODT : tables()) {
 258       auto &HT = ODT->Table;
 259       Info &InfoObj = HT.getInfoObj();
 260       for (auto I = HT.data_begin(), E = HT.data_end(); I != E; ++I) {
 261         auto *LocalPtr = I.getItem();
 262
 263         // FIXME: Don't rely on the OnDiskHashTable format here.
 264         auto L = InfoObj.ReadKeyDataLength(LocalPtr);
 265         const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first);
 266         InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second, ResultBuilder);
 267       }
 268     }
 269
 270     return Result;
 271   }
 272 };
 273
 274 /// \brief Writer for the on-disk hash table.
 275 template<typename ReaderInfo, typename WriterInfo>
 276 class MultiOnDiskHashTableGenerator {
 277   typedef MultiOnDiskHashTable<ReaderInfo> BaseTable;
 278   typedef llvm::OnDiskChainedHashTableGenerator<WriterInfo> Generator;
 279
 280   Generator Gen;
 281
 282 public:
 283   MultiOnDiskHashTableGenerator() : Gen() {}
 284
 285   void insert(typename WriterInfo::key_type_ref Key,
 286               typename WriterInfo::data_type_ref Data, WriterInfo &Info) {
 287     Gen.insert(Key, Data, Info);
 288   }
 289
 290   void emit(llvm::SmallVectorImpl<char> &Out, WriterInfo &Info,
 291             const BaseTable *Base) {
 292     using namespace llvm::support;
 293     llvm::raw_svector_ostream OutStream(Out);
 294
 295     // Write our header information.
 296     {
 297       endian::Writer<little> Writer(OutStream);
 298
 299       // Reserve four bytes for the bucket offset.
 300       Writer.write<uint32_t>(0);
 301
 302       if (auto *Merged = Base ? Base->getMergedTable() : nullptr) {
 303         // Write list of overridden files.
 304         Writer.write<uint32_t>(Merged->Files.size());
 305         for (const auto &F : Merged->Files)
 306           Info.EmitFileRef(OutStream, F);
 307
 308         // Add all merged entries from Base to the generator.
 309         for (auto &KV : Merged->Data) {
 310           if (!Gen.contains(KV.first, Info))
 311             Gen.insert(KV.first, Info.ImportData(KV.second), Info);
 312         }
 313       } else {
 314         Writer.write<uint32_t>(0);
 315       }
 316     }
 317
 318     // Write the table itself.
 319     uint32_t BucketOffset = Gen.Emit(OutStream, Info);
 320
 321     // Replace the first four bytes with the bucket offset.
 322     endian::write32le(Out.data(), BucketOffset);
 323   }
 324 };
 325
 326 } // end namespace clang::serialization
 327 } // end namespace clang
 328
 329
 330 #endif