1 //===- unittests/Lex/HeaderMapTest.cpp - HeaderMap tests ----------===//
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 #include "clang/Basic/CharInfo.h"
10 #include "clang/Lex/HeaderMap.h"
11 #include "clang/Lex/HeaderMapTypes.h"
12 #include "llvm/ADT/SmallString.h"
13 #include "llvm/Support/SwapByteOrder.h"
14 #include "gtest/gtest.h"
15 #include <cassert>
16 #include <type_traits>
17 
18 using namespace clang;
19 using namespace llvm;
20 
21 namespace {
22 
23 // Lay out a header file for testing.
24 template <unsigned NumBuckets, unsigned NumBytes> struct MapFile {
25   HMapHeader Header;
26   HMapBucket Buckets[NumBuckets];
27   unsigned char Bytes[NumBytes];
28 
29   void init() {
30     memset(this, 0, sizeof(MapFile));
31     Header.Magic = HMAP_HeaderMagicNumber;
32     Header.Version = HMAP_HeaderVersion;
33     Header.NumBuckets = NumBuckets;
34     Header.StringsOffset = sizeof(Header) + sizeof(Buckets);
35   }
36 
37   void swapBytes() {
38     using llvm::sys::getSwappedBytes;
39     Header.Magic = getSwappedBytes(Header.Magic);
40     Header.Version = getSwappedBytes(Header.Version);
41     Header.NumBuckets = getSwappedBytes(Header.NumBuckets);
42     Header.StringsOffset = getSwappedBytes(Header.StringsOffset);
43   }
44 
45   std::unique_ptr<const MemoryBuffer> getBuffer() const {
46     return MemoryBuffer::getMemBuffer(
47         StringRef(reinterpret_cast<const char *>(this), sizeof(MapFile)),
48         "header",
49         /* RequresNullTerminator */ false);
50   }
51 };
52 
53 // The header map hash function.
54 static inline unsigned getHash(StringRef Str) {
55   unsigned Result = 0;
56   for (char C : Str)
57     Result += toLowercase(C) * 13;
58   return Result;
59 }
60 
61 template <class FileTy> struct FileMaker {
62   FileTy &File;
63   unsigned SI = 1;
64   unsigned BI = 0;
65   FileMaker(FileTy &File) : File(File) {}
66 
67   unsigned addString(StringRef S) {
68     assert(SI + S.size() + 1 <= sizeof(File.Bytes));
69     std::copy(S.begin(), S.end(), File.Bytes + SI);
70     auto OldSI = SI;
71     SI += S.size() + 1;
72     return OldSI;
73   }
74   void addBucket(unsigned Hash, unsigned Key, unsigned Prefix, unsigned Suffix) {
75     assert(!(File.Header.NumBuckets & (File.Header.NumBuckets - 1)));
76     unsigned I = Hash & (File.Header.NumBuckets - 1);
77     do {
78       if (!File.Buckets[I].Key) {
79         File.Buckets[I].Key = Key;
80         File.Buckets[I].Prefix = Prefix;
81         File.Buckets[I].Suffix = Suffix;
82         ++File.Header.NumEntries;
83         return;
84       }
85       ++I;
86       I &= File.Header.NumBuckets - 1;
87     } while (I != (Hash & (File.Header.NumBuckets - 1)));
88     llvm_unreachable("no empty buckets");
89   }
90 };
91 
92 TEST(HeaderMapTest, checkHeaderEmpty) {
93   bool NeedsSwap;
94   ASSERT_FALSE(HeaderMapImpl::checkHeader(
95       *MemoryBuffer::getMemBufferCopy("", "empty"), NeedsSwap));
96   ASSERT_FALSE(HeaderMapImpl::checkHeader(
97       *MemoryBuffer::getMemBufferCopy("", "empty"), NeedsSwap));
98 }
99 
100 TEST(HeaderMapTest, checkHeaderMagic) {
101   MapFile<1, 1> File;
102   File.init();
103   File.Header.Magic = 0;
104   bool NeedsSwap;
105   ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
106 }
107 
108 TEST(HeaderMapTest, checkHeaderReserved) {
109   MapFile<1, 1> File;
110   File.init();
111   File.Header.Reserved = 1;
112   bool NeedsSwap;
113   ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
114 }
115 
116 TEST(HeaderMapTest, checkHeaderVersion) {
117   MapFile<1, 1> File;
118   File.init();
119   ++File.Header.Version;
120   bool NeedsSwap;
121   ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
122 }
123 
124 TEST(HeaderMapTest, checkHeaderValidButEmpty) {
125   MapFile<1, 1> File;
126   File.init();
127   bool NeedsSwap;
128   ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
129   ASSERT_FALSE(NeedsSwap);
130 
131   File.swapBytes();
132   ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
133   ASSERT_TRUE(NeedsSwap);
134 }
135 
136 TEST(HeaderMapTest, checkHeader3Buckets) {
137   MapFile<3, 1> File;
138   ASSERT_EQ(3 * sizeof(HMapBucket), sizeof(File.Buckets));
139 
140   File.init();
141   bool NeedsSwap;
142   ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
143 }
144 
145 TEST(HeaderMapTest, checkHeader0Buckets) {
146   // Create with 1 bucket to avoid 0-sized arrays.
147   MapFile<1, 1> File;
148   File.init();
149   File.Header.NumBuckets = 0;
150   bool NeedsSwap;
151   ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
152 }
153 
154 TEST(HeaderMapTest, checkHeaderNotEnoughBuckets) {
155   MapFile<1, 1> File;
156   File.init();
157   File.Header.NumBuckets = 8;
158   bool NeedsSwap;
159   ASSERT_FALSE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
160 }
161 
162 TEST(HeaderMapTest, lookupFilename) {
163   typedef MapFile<2, 7> FileTy;
164   FileTy File;
165   File.init();
166 
167   FileMaker<FileTy> Maker(File);
168   auto a = Maker.addString("a");
169   auto b = Maker.addString("b");
170   auto c = Maker.addString("c");
171   Maker.addBucket(getHash("a"), a, b, c);
172 
173   bool NeedsSwap;
174   ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
175   ASSERT_FALSE(NeedsSwap);
176   HeaderMapImpl Map(File.getBuffer(), NeedsSwap);
177 
178   SmallString<8> DestPath;
179   ASSERT_EQ("bc", Map.lookupFilename("a", DestPath));
180 }
181 
182 template <class FileTy, class PaddingTy> struct PaddedFile {
183   FileTy File;
184   PaddingTy Padding;
185 };
186 
187 TEST(HeaderMapTest, lookupFilenameTruncatedSuffix) {
188   typedef MapFile<2, 64 - sizeof(HMapHeader) - 2 * sizeof(HMapBucket)> FileTy;
189   static_assert(std::is_standard_layout<FileTy>::value,
190                 "Expected standard layout");
191   static_assert(sizeof(FileTy) == 64, "check the math");
192   PaddedFile<FileTy, uint64_t> P;
193   auto &File = P.File;
194   auto &Padding = P.Padding;
195   File.init();
196 
197   FileMaker<FileTy> Maker(File);
198   auto a = Maker.addString("a");
199   auto b = Maker.addString("b");
200   auto c = Maker.addString("c");
201   Maker.addBucket(getHash("a"), a, b, c);
202 
203   // Add 'x' characters to cause an overflow into Padding.
204   ASSERT_EQ('c', File.Bytes[5]);
205   for (unsigned I = 6; I < sizeof(File.Bytes); ++I) {
206     ASSERT_EQ(0, File.Bytes[I]);
207     File.Bytes[I] = 'x';
208   }
209   Padding = 0xffffffff; // Padding won't stop it either.
210 
211   bool NeedsSwap;
212   ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
213   ASSERT_FALSE(NeedsSwap);
214   HeaderMapImpl Map(File.getBuffer(), NeedsSwap);
215 
216   // The string for "c" runs to the end of File.  Check that the suffix
217   // ("cxxxx...") is detected as truncated, and an empty string is returned.
218   SmallString<24> DestPath;
219   ASSERT_EQ("", Map.lookupFilename("a", DestPath));
220 }
221 
222 TEST(HeaderMapTest, lookupFilenameTruncatedPrefix) {
223   typedef MapFile<2, 64 - sizeof(HMapHeader) - 2 * sizeof(HMapBucket)> FileTy;
224   static_assert(std::is_standard_layout<FileTy>::value,
225                 "Expected standard layout");
226   static_assert(sizeof(FileTy) == 64, "check the math");
227   PaddedFile<FileTy, uint64_t> P;
228   auto &File = P.File;
229   auto &Padding = P.Padding;
230   File.init();
231 
232   FileMaker<FileTy> Maker(File);
233   auto a = Maker.addString("a");
234   auto c = Maker.addString("c");
235   auto b = Maker.addString("b"); // Store the prefix last.
236   Maker.addBucket(getHash("a"), a, b, c);
237 
238   // Add 'x' characters to cause an overflow into Padding.
239   ASSERT_EQ('b', File.Bytes[5]);
240   for (unsigned I = 6; I < sizeof(File.Bytes); ++I) {
241     ASSERT_EQ(0, File.Bytes[I]);
242     File.Bytes[I] = 'x';
243   }
244   Padding = 0xffffffff; // Padding won't stop it either.
245 
246   bool NeedsSwap;
247   ASSERT_TRUE(HeaderMapImpl::checkHeader(*File.getBuffer(), NeedsSwap));
248   ASSERT_FALSE(NeedsSwap);
249   HeaderMapImpl Map(File.getBuffer(), NeedsSwap);
250 
251   // The string for "b" runs to the end of File.  Check that the prefix
252   // ("bxxxx...") is detected as truncated, and an empty string is returned.
253   SmallString<24> DestPath;
254   ASSERT_EQ("", Map.lookupFilename("a", DestPath));
255 }
256 
257 } // end namespace
258