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