1 //===- HashTable.cpp - PDB Hash Table -------------------------------------===//
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 #include "llvm/DebugInfo/PDB/Native/HashTable.h"
11 #include "llvm/ADT/Optional.h"
12 #include "llvm/DebugInfo/PDB/Native/RawError.h"
13 #include "llvm/Support/BinaryStreamReader.h"
14 #include "llvm/Support/BinaryStreamWriter.h"
15 #include "llvm/Support/Error.h"
16 #include "llvm/Support/MathExtras.h"
17 #include <algorithm>
18 #include <cassert>
19 #include <cstdint>
20 #include <utility>
21 
22 using namespace llvm;
23 using namespace llvm::pdb;
24 
25 namespace {
26 struct IdentityTraits {
27   static uint32_t hash(uint32_t K, const HashTable &Ctx) { return K; }
28   static uint32_t realKey(uint32_t K, const HashTable &Ctx) { return K; }
29   static uint32_t lowerKey(uint32_t K, const HashTable &Ctx) { return K; }
30 };
31 } // namespace
32 
33 HashTable::HashTable() : HashTable(8) {}
34 
35 HashTable::HashTable(uint32_t Capacity) { Buckets.resize(Capacity); }
36 
37 Error HashTable::load(BinaryStreamReader &Stream) {
38   const Header *H;
39   if (auto EC = Stream.readObject(H))
40     return EC;
41   if (H->Capacity == 0)
42     return make_error<RawError>(raw_error_code::corrupt_file,
43                                 "Invalid Hash Table Capacity");
44   if (H->Size > maxLoad(H->Capacity))
45     return make_error<RawError>(raw_error_code::corrupt_file,
46                                 "Invalid Hash Table Size");
47 
48   Buckets.resize(H->Capacity);
49 
50   if (auto EC = readSparseBitVector(Stream, Present))
51     return EC;
52   if (Present.count() != H->Size)
53     return make_error<RawError>(raw_error_code::corrupt_file,
54                                 "Present bit vector does not match size!");
55 
56   if (auto EC = readSparseBitVector(Stream, Deleted))
57     return EC;
58   if (Present.intersects(Deleted))
59     return make_error<RawError>(raw_error_code::corrupt_file,
60                                 "Present bit vector interesects deleted!");
61 
62   for (uint32_t P : Present) {
63     if (auto EC = Stream.readInteger(Buckets[P].first))
64       return EC;
65     if (auto EC = Stream.readInteger(Buckets[P].second))
66       return EC;
67   }
68 
69   return Error::success();
70 }
71 
72 uint32_t HashTable::calculateSerializedLength() const {
73   uint32_t Size = sizeof(Header);
74 
75   int NumBitsP = Present.find_last() + 1;
76   int NumBitsD = Deleted.find_last() + 1;
77 
78   // Present bit set number of words, followed by that many actual words.
79   Size += sizeof(uint32_t);
80   Size += alignTo(NumBitsP, sizeof(uint32_t));
81 
82   // Deleted bit set number of words, followed by that many actual words.
83   Size += sizeof(uint32_t);
84   Size += alignTo(NumBitsD, sizeof(uint32_t));
85 
86   // One (Key, Value) pair for each entry Present.
87   Size += 2 * sizeof(uint32_t) * size();
88 
89   return Size;
90 }
91 
92 Error HashTable::commit(BinaryStreamWriter &Writer) const {
93   Header H;
94   H.Size = size();
95   H.Capacity = capacity();
96   if (auto EC = Writer.writeObject(H))
97     return EC;
98 
99   if (auto EC = writeSparseBitVector(Writer, Present))
100     return EC;
101 
102   if (auto EC = writeSparseBitVector(Writer, Deleted))
103     return EC;
104 
105   for (const auto &Entry : *this) {
106     if (auto EC = Writer.writeInteger(Entry.first))
107       return EC;
108     if (auto EC = Writer.writeInteger(Entry.second))
109       return EC;
110   }
111   return Error::success();
112 }
113 
114 void HashTable::clear() {
115   Buckets.resize(8);
116   Present.clear();
117   Deleted.clear();
118 }
119 
120 uint32_t HashTable::capacity() const { return Buckets.size(); }
121 
122 uint32_t HashTable::size() const { return Present.count(); }
123 
124 HashTableIterator HashTable::begin() const { return HashTableIterator(*this); }
125 
126 HashTableIterator HashTable::end() const {
127   return HashTableIterator(*this, 0, true);
128 }
129 
130 HashTableIterator HashTable::find(uint32_t K) const {
131   return find_as<IdentityTraits>(K, *this);
132 }
133 
134 void HashTable::set(uint32_t K, uint32_t V) {
135   set_as<IdentityTraits, uint32_t>(K, V, *this);
136 }
137 
138 void HashTable::remove(uint32_t K) { remove_as<IdentityTraits>(K, *this); }
139 
140 uint32_t HashTable::get(uint32_t K) {
141   auto I = find(K);
142   assert(I != end());
143   return (*I).second;
144 }
145 
146 uint32_t HashTable::maxLoad(uint32_t capacity) { return capacity * 2 / 3 + 1; }
147 
148 Error HashTable::readSparseBitVector(BinaryStreamReader &Stream,
149                                      SparseBitVector<> &V) {
150   uint32_t NumWords;
151   if (auto EC = Stream.readInteger(NumWords))
152     return joinErrors(
153         std::move(EC),
154         make_error<RawError>(raw_error_code::corrupt_file,
155                              "Expected hash table number of words"));
156 
157   for (uint32_t I = 0; I != NumWords; ++I) {
158     uint32_t Word;
159     if (auto EC = Stream.readInteger(Word))
160       return joinErrors(std::move(EC),
161                         make_error<RawError>(raw_error_code::corrupt_file,
162                                              "Expected hash table word"));
163     for (unsigned Idx = 0; Idx < 32; ++Idx)
164       if (Word & (1U << Idx))
165         V.set((I * 32) + Idx);
166   }
167   return Error::success();
168 }
169 
170 Error HashTable::writeSparseBitVector(BinaryStreamWriter &Writer,
171                                       SparseBitVector<> &Vec) {
172   int ReqBits = Vec.find_last() + 1;
173   uint32_t NumWords = alignTo(ReqBits, sizeof(uint32_t)) / sizeof(uint32_t);
174   if (auto EC = Writer.writeInteger(NumWords))
175     return joinErrors(
176         std::move(EC),
177         make_error<RawError>(raw_error_code::corrupt_file,
178                              "Could not write linear map number of words"));
179 
180   uint32_t Idx = 0;
181   for (uint32_t I = 0; I != NumWords; ++I) {
182     uint32_t Word = 0;
183     for (uint32_t WordIdx = 0; WordIdx < 32; ++WordIdx, ++Idx) {
184       if (Vec.test(Idx))
185         Word |= (1 << WordIdx);
186     }
187     if (auto EC = Writer.writeInteger(Word))
188       return joinErrors(std::move(EC), make_error<RawError>(
189                                            raw_error_code::corrupt_file,
190                                            "Could not write linear map word"));
191   }
192   return Error::success();
193 }
194 
195 HashTableIterator::HashTableIterator(const HashTable &Map, uint32_t Index,
196                                      bool IsEnd)
197     : Map(&Map), Index(Index), IsEnd(IsEnd) {}
198 
199 HashTableIterator::HashTableIterator(const HashTable &Map) : Map(&Map) {
200   int I = Map.Present.find_first();
201   if (I == -1) {
202     Index = 0;
203     IsEnd = true;
204   } else {
205     Index = static_cast<uint32_t>(I);
206     IsEnd = false;
207   }
208 }
209 
210 HashTableIterator &HashTableIterator::operator=(const HashTableIterator &R) {
211   Map = R.Map;
212   return *this;
213 }
214 
215 bool HashTableIterator::operator==(const HashTableIterator &R) const {
216   if (IsEnd && R.IsEnd)
217     return true;
218   if (IsEnd != R.IsEnd)
219     return false;
220 
221   return (Map == R.Map) && (Index == R.Index);
222 }
223 
224 const std::pair<uint32_t, uint32_t> &HashTableIterator::operator*() const {
225   assert(Map->Present.test(Index));
226   return Map->Buckets[Index];
227 }
228 
229 HashTableIterator &HashTableIterator::operator++() {
230   while (Index < Map->Buckets.size()) {
231     ++Index;
232     if (Map->Present.test(Index))
233       return *this;
234   }
235 
236   IsEnd = true;
237   return *this;
238 }
239