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