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 using namespace clang; 27 28 /// HashHMapKey - This is the 'well known' hash function required by the file 29 /// format, used to look up keys in the hash table. The hash table uses simple 30 /// linear probing based on this function. 31 static inline unsigned HashHMapKey(StringRef Str) { 32 unsigned Result = 0; 33 const char *S = Str.begin(), *End = Str.end(); 34 35 for (; S != End; S++) 36 Result += toLowercase(*S) * 13; 37 return Result; 38 } 39 40 41 42 //===----------------------------------------------------------------------===// 43 // Verification and Construction 44 //===----------------------------------------------------------------------===// 45 46 /// HeaderMap::Create - This attempts to load the specified file as a header 47 /// map. If it doesn't look like a HeaderMap, it gives up and returns null. 48 /// If it looks like a HeaderMap but is obviously corrupted, it puts a reason 49 /// into the string error argument and returns null. 50 std::unique_ptr<HeaderMap> HeaderMap::Create(const FileEntry *FE, 51 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_32(HMAP_HeaderMagicNumber) && 80 Header->Version == llvm::ByteSwap_16(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 = NeedsByteSwap 91 ? llvm::sys::getSwappedBytes(Header->NumBuckets) 92 : 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_32(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 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 None; 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 None; 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 (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 /// LookupFile - Check to see if the specified relative filename is located in 198 /// this HeaderMap. If so, open it and return its FileEntry. 199 Optional<FileEntryRef> HeaderMap::LookupFile(StringRef Filename, 200 FileManager &FM) const { 201 202 SmallString<1024> Path; 203 StringRef Dest = HeaderMapImpl::lookupFilename(Filename, Path); 204 if (Dest.empty()) 205 return None; 206 207 return FM.getOptionalFileRef(Dest); 208 } 209 210 StringRef HeaderMapImpl::lookupFilename(StringRef Filename, 211 SmallVectorImpl<char> &DestPath) const { 212 const HMapHeader &Hdr = getHeader(); 213 unsigned NumBuckets = getEndianAdjustedWord(Hdr.NumBuckets); 214 215 // Don't probe infinitely. This should be checked before constructing. 216 assert(llvm::isPowerOf2_32(NumBuckets) && "Expected power of 2"); 217 218 // Linearly probe the hash table. 219 for (unsigned Bucket = HashHMapKey(Filename);; ++Bucket) { 220 HMapBucket B = getBucket(Bucket & (NumBuckets-1)); 221 if (B.Key == HMAP_EmptyBucketKey) return StringRef(); // Hash miss. 222 223 // See if the key matches. If not, probe on. 224 Optional<StringRef> Key = getString(B.Key); 225 if (LLVM_UNLIKELY(!Key)) 226 continue; 227 if (!Filename.equals_lower(*Key)) 228 continue; 229 230 // If so, we have a match in the hash table. Construct the destination 231 // path. 232 Optional<StringRef> Prefix = getString(B.Prefix); 233 Optional<StringRef> Suffix = getString(B.Suffix); 234 235 DestPath.clear(); 236 if (LLVM_LIKELY(Prefix && Suffix)) { 237 DestPath.append(Prefix->begin(), Prefix->end()); 238 DestPath.append(Suffix->begin(), Suffix->end()); 239 } 240 return StringRef(DestPath.begin(), DestPath.size()); 241 } 242 } 243