1 //===- TypeHashing.h ---------------------------------------------*- 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 #ifndef LLVM_DEBUGINFO_CODEVIEW_TYPEHASHING_H
10 #define LLVM_DEBUGINFO_CODEVIEW_TYPEHASHING_H
11 
12 #include "llvm/ADT/DenseMapInfo.h"
13 #include "llvm/ADT/Hashing.h"
14 
15 #include "llvm/DebugInfo/CodeView/CodeView.h"
16 #include "llvm/DebugInfo/CodeView/TypeCollection.h"
17 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
18 
19 #include "llvm/Support/FormatProviders.h"
20 
21 #include <type_traits>
22 
23 namespace llvm {
24 namespace codeview {
25 
26 /// A locally hashed type represents a straightforward hash code of a serialized
27 /// record.  The record is simply serialized, and then the bytes are hashed by
28 /// a standard algorithm.  This is sufficient for the case of de-duplicating
29 /// records within a single sequence of types, because if two records both have
30 /// a back-reference to the same type in the same stream, they will both have
31 /// the same numeric value for the TypeIndex of the back reference.
32 struct LocallyHashedType {
33   hash_code Hash;
34   ArrayRef<uint8_t> RecordData;
35 
36   /// Given a type, compute its local hash.
37   static LocallyHashedType hashType(ArrayRef<uint8_t> RecordData);
38 
39   /// Given a sequence of types, compute all of the local hashes.
40   template <typename Range>
hashTypesLocallyHashedType41   static std::vector<LocallyHashedType> hashTypes(Range &&Records) {
42     std::vector<LocallyHashedType> Hashes;
43     Hashes.reserve(std::distance(std::begin(Records), std::end(Records)));
44     for (const auto &R : Records)
45       Hashes.push_back(hashType(R));
46 
47     return Hashes;
48   }
49 
50   static std::vector<LocallyHashedType>
hashTypeCollectionLocallyHashedType51   hashTypeCollection(TypeCollection &Types) {
52     std::vector<LocallyHashedType> Hashes;
53     Types.ForEachRecord([&Hashes](TypeIndex TI, const CVType &Type) {
54       Hashes.push_back(hashType(Type.RecordData));
55     });
56     return Hashes;
57   }
58 };
59 
60 enum class GlobalTypeHashAlg : uint16_t {
61   SHA1 = 0, // standard 20-byte SHA1 hash
62   SHA1_8    // last 8-bytes of standard SHA1 hash
63 };
64 
65 /// A globally hashed type represents a hash value that is sufficient to
66 /// uniquely identify a record across multiple type streams or type sequences.
67 /// This works by, for any given record A which references B, replacing the
68 /// TypeIndex that refers to B with a previously-computed global hash for B.  As
69 /// this is a recursive algorithm (e.g. the global hash of B also depends on the
70 /// global hashes of the types that B refers to), a global hash can uniquely
71 /// identify identify that A occurs in another stream that has a completely
72 /// different graph structure.  Although the hash itself is slower to compute,
73 /// probing is much faster with a globally hashed type, because the hash itself
74 /// is considered "as good as" the original type.  Since type records can be
75 /// quite large, this makes the equality comparison of the hash much faster than
76 /// equality comparison of a full record.
77 struct GloballyHashedType {
78   GloballyHashedType() = default;
GloballyHashedTypeGloballyHashedType79   GloballyHashedType(StringRef H)
80       : GloballyHashedType(ArrayRef<uint8_t>(H.bytes_begin(), H.bytes_end())) {}
GloballyHashedTypeGloballyHashedType81   GloballyHashedType(ArrayRef<uint8_t> H) {
82     assert(H.size() == 8);
83     ::memcpy(Hash.data(), H.data(), 8);
84   }
85   std::array<uint8_t, 8> Hash;
86 
emptyGloballyHashedType87   bool empty() const { return *(const uint64_t*)Hash.data() == 0; }
88 
89   /// Given a sequence of bytes representing a record, compute a global hash for
90   /// this record.  Due to the nature of global hashes incorporating the hashes
91   /// of referenced records, this function requires a list of types and ids
92   /// that RecordData might reference, indexable by TypeIndex.
93   static GloballyHashedType hashType(ArrayRef<uint8_t> RecordData,
94                                      ArrayRef<GloballyHashedType> PreviousTypes,
95                                      ArrayRef<GloballyHashedType> PreviousIds);
96 
97   /// Given a sequence of bytes representing a record, compute a global hash for
98   /// this record.  Due to the nature of global hashes incorporating the hashes
99   /// of referenced records, this function requires a list of types and ids
100   /// that RecordData might reference, indexable by TypeIndex.
hashTypeGloballyHashedType101   static GloballyHashedType hashType(CVType Type,
102                                      ArrayRef<GloballyHashedType> PreviousTypes,
103                                      ArrayRef<GloballyHashedType> PreviousIds) {
104     return hashType(Type.RecordData, PreviousTypes, PreviousIds);
105   }
106 
107   /// Given a sequence of combined type and ID records, compute global hashes
108   /// for each of them, returning the results in a vector of hashed types.
109   template <typename Range>
hashTypesGloballyHashedType110   static std::vector<GloballyHashedType> hashTypes(Range &&Records) {
111     std::vector<GloballyHashedType> Hashes;
112     bool UnresolvedRecords = false;
113     for (const auto &R : Records) {
114       GloballyHashedType H = hashType(R, Hashes, Hashes);
115       if (H.empty())
116         UnresolvedRecords = true;
117       Hashes.push_back(H);
118     }
119 
120     // In some rare cases, there might be records with forward references in the
121     // stream. Several passes might be needed to fully hash each record in the
122     // Type stream. However this occurs on very small OBJs generated by MASM,
123     // with a dozen records at most. Therefore this codepath isn't
124     // time-critical, as it isn't taken in 99% of cases.
125     while (UnresolvedRecords) {
126       UnresolvedRecords = false;
127       auto HashIt = Hashes.begin();
128       for (const auto &R : Records) {
129         if (HashIt->empty()) {
130           GloballyHashedType H = hashType(R, Hashes, Hashes);
131           if (H.empty())
132             UnresolvedRecords = true;
133           else
134             *HashIt = H;
135         }
136         ++HashIt;
137       }
138     }
139 
140     return Hashes;
141   }
142 
143   /// Given a sequence of combined type and ID records, compute global hashes
144   /// for each of them, returning the results in a vector of hashed types.
145   template <typename Range>
146   static std::vector<GloballyHashedType>
hashIdsGloballyHashedType147   hashIds(Range &&Records, ArrayRef<GloballyHashedType> TypeHashes) {
148     std::vector<GloballyHashedType> IdHashes;
149     for (const auto &R : Records)
150       IdHashes.push_back(hashType(R, TypeHashes, IdHashes));
151 
152     return IdHashes;
153   }
154 
155   static std::vector<GloballyHashedType>
hashTypeCollectionGloballyHashedType156   hashTypeCollection(TypeCollection &Types) {
157     std::vector<GloballyHashedType> Hashes;
158     Types.ForEachRecord([&Hashes](TypeIndex TI, const CVType &Type) {
159       Hashes.push_back(hashType(Type.RecordData, Hashes, Hashes));
160     });
161     return Hashes;
162   }
163 };
164 #if defined(_MSC_VER)
165 // is_trivially_copyable is not available in older versions of libc++, but it is
166 // available in all supported versions of MSVC, so at least this gives us some
167 // coverage.
168 static_assert(std::is_trivially_copyable<GloballyHashedType>::value,
169               "GloballyHashedType must be trivially copyable so that we can "
170               "reinterpret_cast arrays of hash data to arrays of "
171               "GloballyHashedType");
172 #endif
173 } // namespace codeview
174 
175 template <> struct DenseMapInfo<codeview::LocallyHashedType> {
176   static codeview::LocallyHashedType Empty;
177   static codeview::LocallyHashedType Tombstone;
178 
179   static codeview::LocallyHashedType getEmptyKey() { return Empty; }
180 
181   static codeview::LocallyHashedType getTombstoneKey() { return Tombstone; }
182 
183   static unsigned getHashValue(codeview::LocallyHashedType Val) {
184     return Val.Hash;
185   }
186 
187   static bool isEqual(codeview::LocallyHashedType LHS,
188                       codeview::LocallyHashedType RHS) {
189     if (LHS.Hash != RHS.Hash)
190       return false;
191     return LHS.RecordData == RHS.RecordData;
192   }
193 };
194 
195 template <> struct DenseMapInfo<codeview::GloballyHashedType> {
196   static codeview::GloballyHashedType Empty;
197   static codeview::GloballyHashedType Tombstone;
198 
199   static codeview::GloballyHashedType getEmptyKey() { return Empty; }
200 
201   static codeview::GloballyHashedType getTombstoneKey() { return Tombstone; }
202 
203   static unsigned getHashValue(codeview::GloballyHashedType Val) {
204     return *reinterpret_cast<const unsigned *>(Val.Hash.data());
205   }
206 
207   static bool isEqual(codeview::GloballyHashedType LHS,
208                       codeview::GloballyHashedType RHS) {
209     return LHS.Hash == RHS.Hash;
210   }
211 };
212 
213 template <> struct format_provider<codeview::LocallyHashedType> {
214 public:
215   static void format(const codeview::LocallyHashedType &V,
216                      llvm::raw_ostream &Stream, StringRef Style) {
217     write_hex(Stream, V.Hash, HexPrintStyle::Upper, 8);
218   }
219 };
220 
221 template <> struct format_provider<codeview::GloballyHashedType> {
222 public:
223   static void format(const codeview::GloballyHashedType &V,
224                      llvm::raw_ostream &Stream, StringRef Style) {
225     for (uint8_t B : V.Hash) {
226       write_hex(Stream, B, HexPrintStyle::Upper, 2);
227     }
228   }
229 };
230 
231 } // namespace llvm
232 
233 #endif
234