1 //===--- HeaderMap.cpp - A file that acts like dir of symlinks ------------===// 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 implements the HeaderMap interface. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "clang/Lex/HeaderMap.h" 14 #include "clang/Lex/HeaderMapTypes.h" 15 #include "clang/Basic/CharInfo.h" 16 #include "clang/Basic/FileManager.h" 17 #include "llvm/ADT/SmallString.h" 18 #include "llvm/Support/Compiler.h" 19 #include "llvm/Support/DataTypes.h" 20 #include "llvm/Support/MathExtras.h" 21 #include "llvm/Support/MemoryBuffer.h" 22 #include "llvm/Support/SwapByteOrder.h" 23 #include "llvm/Support/Debug.h" 24 #include <cstring> 25 #include <memory> 26 #include <optional> 27 using namespace clang; 28 29 /// HashHMapKey - This is the 'well known' hash function required by the file 30 /// format, used to look up keys in the hash table. The hash table uses simple 31 /// linear probing based on this function. 32 static inline unsigned HashHMapKey(StringRef Str) { 33 unsigned Result = 0; 34 const char *S = Str.begin(), *End = Str.end(); 35 36 for (; S != End; S++) 37 Result += toLowercase(*S) * 13; 38 return Result; 39 } 40 41 42 43 //===----------------------------------------------------------------------===// 44 // Verification and Construction 45 //===----------------------------------------------------------------------===// 46 47 /// HeaderMap::Create - This attempts to load the specified file as a header 48 /// map. If it doesn't look like a HeaderMap, it gives up and returns null. 49 /// If it looks like a HeaderMap but is obviously corrupted, it puts a reason 50 /// into the string error argument and returns null. 51 std::unique_ptr<HeaderMap> HeaderMap::Create(FileEntryRef FE, FileManager &FM) { 52 // If the file is too small to be a header map, ignore it. 53 unsigned FileSize = FE.getSize(); 54 if (FileSize <= sizeof(HMapHeader)) return nullptr; 55 56 auto FileBuffer = FM.getBufferForFile(FE); 57 if (!FileBuffer || !*FileBuffer) 58 return nullptr; 59 bool NeedsByteSwap; 60 if (!checkHeader(**FileBuffer, NeedsByteSwap)) 61 return nullptr; 62 return std::unique_ptr<HeaderMap>(new HeaderMap(std::move(*FileBuffer), NeedsByteSwap)); 63 } 64 65 bool HeaderMapImpl::checkHeader(const llvm::MemoryBuffer &File, 66 bool &NeedsByteSwap) { 67 if (File.getBufferSize() <= sizeof(HMapHeader)) 68 return false; 69 const char *FileStart = File.getBufferStart(); 70 71 // We know the file is at least as big as the header, check it now. 72 const HMapHeader *Header = reinterpret_cast<const HMapHeader*>(FileStart); 73 74 // Sniff it to see if it's a headermap by checking the magic number and 75 // version. 76 if (Header->Magic == HMAP_HeaderMagicNumber && 77 Header->Version == HMAP_HeaderVersion) 78 NeedsByteSwap = false; 79 else if (Header->Magic == llvm::byteswap<uint32_t>(HMAP_HeaderMagicNumber) && 80 Header->Version == llvm::byteswap<uint16_t>(HMAP_HeaderVersion)) 81 NeedsByteSwap = true; // Mixed endianness headermap. 82 else 83 return false; // Not a header map. 84 85 if (Header->Reserved != 0) 86 return false; 87 88 // Check the number of buckets. It should be a power of two, and there 89 // should be enough space in the file for all of them. 90 uint32_t NumBuckets = 91 NeedsByteSwap ? llvm::byteswap(Header->NumBuckets) : Header->NumBuckets; 92 if (!llvm::isPowerOf2_32(NumBuckets)) 93 return false; 94 if (File.getBufferSize() < 95 sizeof(HMapHeader) + sizeof(HMapBucket) * NumBuckets) 96 return false; 97 98 // Okay, everything looks good. 99 return true; 100 } 101 102 //===----------------------------------------------------------------------===// 103 // Utility Methods 104 //===----------------------------------------------------------------------===// 105 106 107 /// getFileName - Return the filename of the headermap. 108 StringRef HeaderMapImpl::getFileName() const { 109 return FileBuffer->getBufferIdentifier(); 110 } 111 112 unsigned HeaderMapImpl::getEndianAdjustedWord(unsigned X) const { 113 if (!NeedsBSwap) return X; 114 return llvm::byteswap<uint32_t>(X); 115 } 116 117 /// getHeader - Return a reference to the file header, in unbyte-swapped form. 118 /// This method cannot fail. 119 const HMapHeader &HeaderMapImpl::getHeader() const { 120 // We know the file is at least as big as the header. Return it. 121 return *reinterpret_cast<const HMapHeader*>(FileBuffer->getBufferStart()); 122 } 123 124 /// getBucket - Return the specified hash table bucket from the header map, 125 /// bswap'ing its fields as appropriate. If the bucket number is not valid, 126 /// this return a bucket with an empty key (0). 127 HMapBucket HeaderMapImpl::getBucket(unsigned BucketNo) const { 128 assert(FileBuffer->getBufferSize() >= 129 sizeof(HMapHeader) + sizeof(HMapBucket) * BucketNo && 130 "Expected bucket to be in range"); 131 132 HMapBucket Result; 133 Result.Key = HMAP_EmptyBucketKey; 134 135 const HMapBucket *BucketArray = 136 reinterpret_cast<const HMapBucket*>(FileBuffer->getBufferStart() + 137 sizeof(HMapHeader)); 138 const HMapBucket *BucketPtr = BucketArray+BucketNo; 139 140 // Load the values, bswapping as needed. 141 Result.Key = getEndianAdjustedWord(BucketPtr->Key); 142 Result.Prefix = getEndianAdjustedWord(BucketPtr->Prefix); 143 Result.Suffix = getEndianAdjustedWord(BucketPtr->Suffix); 144 return Result; 145 } 146 147 std::optional<StringRef> HeaderMapImpl::getString(unsigned StrTabIdx) const { 148 // Add the start of the string table to the idx. 149 StrTabIdx += getEndianAdjustedWord(getHeader().StringsOffset); 150 151 // Check for invalid index. 152 if (StrTabIdx >= FileBuffer->getBufferSize()) 153 return std::nullopt; 154 155 const char *Data = FileBuffer->getBufferStart() + StrTabIdx; 156 unsigned MaxLen = FileBuffer->getBufferSize() - StrTabIdx; 157 unsigned Len = strnlen(Data, MaxLen); 158 159 // Check whether the buffer is null-terminated. 160 if (Len == MaxLen && Data[Len - 1]) 161 return std::nullopt; 162 163 return StringRef(Data, Len); 164 } 165 166 //===----------------------------------------------------------------------===// 167 // The Main Drivers 168 //===----------------------------------------------------------------------===// 169 170 /// dump - Print the contents of this headermap to stderr. 171 LLVM_DUMP_METHOD void HeaderMapImpl::dump() const { 172 const HMapHeader &Hdr = getHeader(); 173 unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets); 174 175 llvm::dbgs() << "Header Map " << getFileName() << ":\n " << NumBuckets 176 << ", " << getEndianAdjustedWord(Hdr.NumEntries) << "\n"; 177 178 auto getStringOrInvalid = [this](unsigned Id) -> StringRef { 179 if (std::optional<StringRef> S = getString(Id)) 180 return *S; 181 return "<invalid>"; 182 }; 183 184 for (unsigned i = 0; i != NumBuckets; ++i) { 185 HMapBucket B = getBucket(i); 186 if (B.Key == HMAP_EmptyBucketKey) continue; 187 188 StringRef Key = getStringOrInvalid(B.Key); 189 StringRef Prefix = getStringOrInvalid(B.Prefix); 190 StringRef Suffix = getStringOrInvalid(B.Suffix); 191 llvm::dbgs() << " " << i << ". " << Key << " -> '" << Prefix << "' '" 192 << Suffix << "'\n"; 193 } 194 } 195 196 StringRef HeaderMapImpl::lookupFilename(StringRef Filename, 197 SmallVectorImpl<char> &DestPath) const { 198 const HMapHeader &Hdr = getHeader(); 199 unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets); 200 201 // Don't probe infinitely. This should be checked before constructing. 202 assert(llvm::isPowerOf2_32(NumBuckets) && "Expected power of 2"); 203 204 // Linearly probe the hash table. 205 for (unsigned Bucket = HashHMapKey(Filename);; ++Bucket) { 206 HMapBucket B = getBucket(Bucket & (NumBuckets-1)); 207 if (B.Key == HMAP_EmptyBucketKey) return StringRef(); // Hash miss. 208 209 // See if the key matches. If not, probe on. 210 std::optional<StringRef> Key = getString(B.Key); 211 if (LLVM_UNLIKELY(!Key)) 212 continue; 213 if (!Filename.equals_insensitive(*Key)) 214 continue; 215 216 // If so, we have a match in the hash table. Construct the destination 217 // path. 218 std::optional<StringRef> Prefix = getString(B.Prefix); 219 std::optional<StringRef> Suffix = getString(B.Suffix); 220 221 DestPath.clear(); 222 if (LLVM_LIKELY(Prefix && Suffix)) { 223 DestPath.append(Prefix->begin(), Prefix->end()); 224 DestPath.append(Suffix->begin(), Suffix->end()); 225 } 226 return StringRef(DestPath.begin(), DestPath.size()); 227 } 228 } 229 230 StringRef HeaderMapImpl::reverseLookupFilename(StringRef DestPath) const { 231 if (!ReverseMap.empty()) 232 return ReverseMap.lookup(DestPath); 233 234 const HMapHeader &Hdr = getHeader(); 235 unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets); 236 StringRef RetKey; 237 for (unsigned i = 0; i != NumBuckets; ++i) { 238 HMapBucket B = getBucket(i); 239 if (B.Key == HMAP_EmptyBucketKey) 240 continue; 241 242 std::optional<StringRef> Key = getString(B.Key); 243 std::optional<StringRef> Prefix = getString(B.Prefix); 244 std::optional<StringRef> Suffix = getString(B.Suffix); 245 if (LLVM_LIKELY(Key && Prefix && Suffix)) { 246 SmallVector<char, 1024> Buf; 247 Buf.append(Prefix->begin(), Prefix->end()); 248 Buf.append(Suffix->begin(), Suffix->end()); 249 StringRef Value(Buf.begin(), Buf.size()); 250 ReverseMap[Value] = *Key; 251 252 if (DestPath == Value) 253 RetKey = *Key; 254 } 255 } 256 return RetKey; 257 } 258