1 //===- CoverageMappingReader.cpp - Code coverage mapping reader -----------===//
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 contains support for reading coverage mapping data for
10 // instrumentation based coverage.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/ProfileData/Coverage/CoverageMappingReader.h"
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/ADT/Triple.h"
22 #include "llvm/Object/Binary.h"
23 #include "llvm/Object/Error.h"
24 #include "llvm/Object/MachOUniversal.h"
25 #include "llvm/Object/ObjectFile.h"
26 #include "llvm/Object/COFF.h"
27 #include "llvm/ProfileData/InstrProf.h"
28 #include "llvm/Support/Casting.h"
29 #include "llvm/Support/Compression.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/Endian.h"
32 #include "llvm/Support/Error.h"
33 #include "llvm/Support/ErrorHandling.h"
34 #include "llvm/Support/LEB128.h"
35 #include "llvm/Support/MathExtras.h"
36 #include "llvm/Support/raw_ostream.h"
37 #include <vector>
38
39 using namespace llvm;
40 using namespace coverage;
41 using namespace object;
42
43 #define DEBUG_TYPE "coverage-mapping"
44
45 STATISTIC(CovMapNumRecords, "The # of coverage function records");
46 STATISTIC(CovMapNumUsedRecords, "The # of used coverage function records");
47
increment()48 void CoverageMappingIterator::increment() {
49 if (ReadErr != coveragemap_error::success)
50 return;
51
52 // Check if all the records were read or if an error occurred while reading
53 // the next record.
54 if (auto E = Reader->readNextRecord(Record))
55 handleAllErrors(std::move(E), [&](const CoverageMapError &CME) {
56 if (CME.get() == coveragemap_error::eof)
57 *this = CoverageMappingIterator();
58 else
59 ReadErr = CME.get();
60 });
61 }
62
readULEB128(uint64_t & Result)63 Error RawCoverageReader::readULEB128(uint64_t &Result) {
64 if (Data.empty())
65 return make_error<CoverageMapError>(coveragemap_error::truncated);
66 unsigned N = 0;
67 Result = decodeULEB128(Data.bytes_begin(), &N);
68 if (N > Data.size())
69 return make_error<CoverageMapError>(coveragemap_error::malformed);
70 Data = Data.substr(N);
71 return Error::success();
72 }
73
readIntMax(uint64_t & Result,uint64_t MaxPlus1)74 Error RawCoverageReader::readIntMax(uint64_t &Result, uint64_t MaxPlus1) {
75 if (auto Err = readULEB128(Result))
76 return Err;
77 if (Result >= MaxPlus1)
78 return make_error<CoverageMapError>(coveragemap_error::malformed);
79 return Error::success();
80 }
81
readSize(uint64_t & Result)82 Error RawCoverageReader::readSize(uint64_t &Result) {
83 if (auto Err = readULEB128(Result))
84 return Err;
85 // Sanity check the number.
86 if (Result > Data.size())
87 return make_error<CoverageMapError>(coveragemap_error::malformed);
88 return Error::success();
89 }
90
readString(StringRef & Result)91 Error RawCoverageReader::readString(StringRef &Result) {
92 uint64_t Length;
93 if (auto Err = readSize(Length))
94 return Err;
95 Result = Data.substr(0, Length);
96 Data = Data.substr(Length);
97 return Error::success();
98 }
99
read(CovMapVersion Version,BinaryCoverageReader::DecompressedData & Decompressed)100 Error RawCoverageFilenamesReader::read(
101 CovMapVersion Version,
102 BinaryCoverageReader::DecompressedData &Decompressed) {
103 uint64_t NumFilenames;
104 if (auto Err = readSize(NumFilenames))
105 return Err;
106 if (!NumFilenames)
107 return make_error<CoverageMapError>(coveragemap_error::malformed);
108
109 if (Version < CovMapVersion::Version4)
110 return readUncompressed(NumFilenames);
111
112 // The uncompressed length may exceed the size of the encoded filenames.
113 // Skip size validation.
114 uint64_t UncompressedLen;
115 if (auto Err = readULEB128(UncompressedLen))
116 return Err;
117
118 uint64_t CompressedLen;
119 if (auto Err = readSize(CompressedLen))
120 return Err;
121
122 if (CompressedLen > 0) {
123 if (!zlib::isAvailable())
124 return make_error<CoverageMapError>(
125 coveragemap_error::decompression_failed);
126
127 // Allocate memory for the decompressed filenames. Transfer ownership of
128 // the memory to BinaryCoverageReader.
129 auto DecompressedStorage = std::make_unique<SmallVector<char, 0>>();
130 SmallVectorImpl<char> &StorageBuf = *DecompressedStorage.get();
131 Decompressed.push_back(std::move(DecompressedStorage));
132
133 // Read compressed filenames.
134 StringRef CompressedFilenames = Data.substr(0, CompressedLen);
135 Data = Data.substr(CompressedLen);
136 auto Err =
137 zlib::uncompress(CompressedFilenames, StorageBuf, UncompressedLen);
138 if (Err) {
139 consumeError(std::move(Err));
140 return make_error<CoverageMapError>(
141 coveragemap_error::decompression_failed);
142 }
143
144 StringRef UncompressedFilenames(StorageBuf.data(), StorageBuf.size());
145 RawCoverageFilenamesReader Delegate(UncompressedFilenames, Filenames);
146 return Delegate.readUncompressed(NumFilenames);
147 }
148
149 return readUncompressed(NumFilenames);
150 }
151
readUncompressed(uint64_t NumFilenames)152 Error RawCoverageFilenamesReader::readUncompressed(uint64_t NumFilenames) {
153 // Read uncompressed filenames.
154 for (size_t I = 0; I < NumFilenames; ++I) {
155 StringRef Filename;
156 if (auto Err = readString(Filename))
157 return Err;
158 Filenames.push_back(Filename);
159 }
160 return Error::success();
161 }
162
decodeCounter(unsigned Value,Counter & C)163 Error RawCoverageMappingReader::decodeCounter(unsigned Value, Counter &C) {
164 auto Tag = Value & Counter::EncodingTagMask;
165 switch (Tag) {
166 case Counter::Zero:
167 C = Counter::getZero();
168 return Error::success();
169 case Counter::CounterValueReference:
170 C = Counter::getCounter(Value >> Counter::EncodingTagBits);
171 return Error::success();
172 default:
173 break;
174 }
175 Tag -= Counter::Expression;
176 switch (Tag) {
177 case CounterExpression::Subtract:
178 case CounterExpression::Add: {
179 auto ID = Value >> Counter::EncodingTagBits;
180 if (ID >= Expressions.size())
181 return make_error<CoverageMapError>(coveragemap_error::malformed);
182 Expressions[ID].Kind = CounterExpression::ExprKind(Tag);
183 C = Counter::getExpression(ID);
184 break;
185 }
186 default:
187 return make_error<CoverageMapError>(coveragemap_error::malformed);
188 }
189 return Error::success();
190 }
191
readCounter(Counter & C)192 Error RawCoverageMappingReader::readCounter(Counter &C) {
193 uint64_t EncodedCounter;
194 if (auto Err =
195 readIntMax(EncodedCounter, std::numeric_limits<unsigned>::max()))
196 return Err;
197 if (auto Err = decodeCounter(EncodedCounter, C))
198 return Err;
199 return Error::success();
200 }
201
202 static const unsigned EncodingExpansionRegionBit = 1
203 << Counter::EncodingTagBits;
204
205 /// Read the sub-array of regions for the given inferred file id.
206 /// \param NumFileIDs the number of file ids that are defined for this
207 /// function.
readMappingRegionsSubArray(std::vector<CounterMappingRegion> & MappingRegions,unsigned InferredFileID,size_t NumFileIDs)208 Error RawCoverageMappingReader::readMappingRegionsSubArray(
209 std::vector<CounterMappingRegion> &MappingRegions, unsigned InferredFileID,
210 size_t NumFileIDs) {
211 uint64_t NumRegions;
212 if (auto Err = readSize(NumRegions))
213 return Err;
214 unsigned LineStart = 0;
215 for (size_t I = 0; I < NumRegions; ++I) {
216 Counter C;
217 CounterMappingRegion::RegionKind Kind = CounterMappingRegion::CodeRegion;
218
219 // Read the combined counter + region kind.
220 uint64_t EncodedCounterAndRegion;
221 if (auto Err = readIntMax(EncodedCounterAndRegion,
222 std::numeric_limits<unsigned>::max()))
223 return Err;
224 unsigned Tag = EncodedCounterAndRegion & Counter::EncodingTagMask;
225 uint64_t ExpandedFileID = 0;
226 if (Tag != Counter::Zero) {
227 if (auto Err = decodeCounter(EncodedCounterAndRegion, C))
228 return Err;
229 } else {
230 // Is it an expansion region?
231 if (EncodedCounterAndRegion & EncodingExpansionRegionBit) {
232 Kind = CounterMappingRegion::ExpansionRegion;
233 ExpandedFileID = EncodedCounterAndRegion >>
234 Counter::EncodingCounterTagAndExpansionRegionTagBits;
235 if (ExpandedFileID >= NumFileIDs)
236 return make_error<CoverageMapError>(coveragemap_error::malformed);
237 } else {
238 switch (EncodedCounterAndRegion >>
239 Counter::EncodingCounterTagAndExpansionRegionTagBits) {
240 case CounterMappingRegion::CodeRegion:
241 // Don't do anything when we have a code region with a zero counter.
242 break;
243 case CounterMappingRegion::SkippedRegion:
244 Kind = CounterMappingRegion::SkippedRegion;
245 break;
246 default:
247 return make_error<CoverageMapError>(coveragemap_error::malformed);
248 }
249 }
250 }
251
252 // Read the source range.
253 uint64_t LineStartDelta, ColumnStart, NumLines, ColumnEnd;
254 if (auto Err =
255 readIntMax(LineStartDelta, std::numeric_limits<unsigned>::max()))
256 return Err;
257 if (auto Err = readULEB128(ColumnStart))
258 return Err;
259 if (ColumnStart > std::numeric_limits<unsigned>::max())
260 return make_error<CoverageMapError>(coveragemap_error::malformed);
261 if (auto Err = readIntMax(NumLines, std::numeric_limits<unsigned>::max()))
262 return Err;
263 if (auto Err = readIntMax(ColumnEnd, std::numeric_limits<unsigned>::max()))
264 return Err;
265 LineStart += LineStartDelta;
266
267 // If the high bit of ColumnEnd is set, this is a gap region.
268 if (ColumnEnd & (1U << 31)) {
269 Kind = CounterMappingRegion::GapRegion;
270 ColumnEnd &= ~(1U << 31);
271 }
272
273 // Adjust the column locations for the empty regions that are supposed to
274 // cover whole lines. Those regions should be encoded with the
275 // column range (1 -> std::numeric_limits<unsigned>::max()), but because
276 // the encoded std::numeric_limits<unsigned>::max() is several bytes long,
277 // we set the column range to (0 -> 0) to ensure that the column start and
278 // column end take up one byte each.
279 // The std::numeric_limits<unsigned>::max() is used to represent a column
280 // position at the end of the line without knowing the length of that line.
281 if (ColumnStart == 0 && ColumnEnd == 0) {
282 ColumnStart = 1;
283 ColumnEnd = std::numeric_limits<unsigned>::max();
284 }
285
286 LLVM_DEBUG({
287 dbgs() << "Counter in file " << InferredFileID << " " << LineStart << ":"
288 << ColumnStart << " -> " << (LineStart + NumLines) << ":"
289 << ColumnEnd << ", ";
290 if (Kind == CounterMappingRegion::ExpansionRegion)
291 dbgs() << "Expands to file " << ExpandedFileID;
292 else
293 CounterMappingContext(Expressions).dump(C, dbgs());
294 dbgs() << "\n";
295 });
296
297 auto CMR = CounterMappingRegion(C, InferredFileID, ExpandedFileID,
298 LineStart, ColumnStart,
299 LineStart + NumLines, ColumnEnd, Kind);
300 if (CMR.startLoc() > CMR.endLoc())
301 return make_error<CoverageMapError>(coveragemap_error::malformed);
302 MappingRegions.push_back(CMR);
303 }
304 return Error::success();
305 }
306
read()307 Error RawCoverageMappingReader::read() {
308 // Read the virtual file mapping.
309 SmallVector<unsigned, 8> VirtualFileMapping;
310 uint64_t NumFileMappings;
311 if (auto Err = readSize(NumFileMappings))
312 return Err;
313 for (size_t I = 0; I < NumFileMappings; ++I) {
314 uint64_t FilenameIndex;
315 if (auto Err = readIntMax(FilenameIndex, TranslationUnitFilenames.size()))
316 return Err;
317 VirtualFileMapping.push_back(FilenameIndex);
318 }
319
320 // Construct the files using unique filenames and virtual file mapping.
321 for (auto I : VirtualFileMapping) {
322 Filenames.push_back(TranslationUnitFilenames[I]);
323 }
324
325 // Read the expressions.
326 uint64_t NumExpressions;
327 if (auto Err = readSize(NumExpressions))
328 return Err;
329 // Create an array of dummy expressions that get the proper counters
330 // when the expressions are read, and the proper kinds when the counters
331 // are decoded.
332 Expressions.resize(
333 NumExpressions,
334 CounterExpression(CounterExpression::Subtract, Counter(), Counter()));
335 for (size_t I = 0; I < NumExpressions; ++I) {
336 if (auto Err = readCounter(Expressions[I].LHS))
337 return Err;
338 if (auto Err = readCounter(Expressions[I].RHS))
339 return Err;
340 }
341
342 // Read the mapping regions sub-arrays.
343 for (unsigned InferredFileID = 0, S = VirtualFileMapping.size();
344 InferredFileID < S; ++InferredFileID) {
345 if (auto Err = readMappingRegionsSubArray(MappingRegions, InferredFileID,
346 VirtualFileMapping.size()))
347 return Err;
348 }
349
350 // Set the counters for the expansion regions.
351 // i.e. Counter of expansion region = counter of the first region
352 // from the expanded file.
353 // Perform multiple passes to correctly propagate the counters through
354 // all the nested expansion regions.
355 SmallVector<CounterMappingRegion *, 8> FileIDExpansionRegionMapping;
356 FileIDExpansionRegionMapping.resize(VirtualFileMapping.size(), nullptr);
357 for (unsigned Pass = 1, S = VirtualFileMapping.size(); Pass < S; ++Pass) {
358 for (auto &R : MappingRegions) {
359 if (R.Kind != CounterMappingRegion::ExpansionRegion)
360 continue;
361 assert(!FileIDExpansionRegionMapping[R.ExpandedFileID]);
362 FileIDExpansionRegionMapping[R.ExpandedFileID] = &R;
363 }
364 for (auto &R : MappingRegions) {
365 if (FileIDExpansionRegionMapping[R.FileID]) {
366 FileIDExpansionRegionMapping[R.FileID]->Count = R.Count;
367 FileIDExpansionRegionMapping[R.FileID] = nullptr;
368 }
369 }
370 }
371
372 return Error::success();
373 }
374
isDummy()375 Expected<bool> RawCoverageMappingDummyChecker::isDummy() {
376 // A dummy coverage mapping data consists of just one region with zero count.
377 uint64_t NumFileMappings;
378 if (Error Err = readSize(NumFileMappings))
379 return std::move(Err);
380 if (NumFileMappings != 1)
381 return false;
382 // We don't expect any specific value for the filename index, just skip it.
383 uint64_t FilenameIndex;
384 if (Error Err =
385 readIntMax(FilenameIndex, std::numeric_limits<unsigned>::max()))
386 return std::move(Err);
387 uint64_t NumExpressions;
388 if (Error Err = readSize(NumExpressions))
389 return std::move(Err);
390 if (NumExpressions != 0)
391 return false;
392 uint64_t NumRegions;
393 if (Error Err = readSize(NumRegions))
394 return std::move(Err);
395 if (NumRegions != 1)
396 return false;
397 uint64_t EncodedCounterAndRegion;
398 if (Error Err = readIntMax(EncodedCounterAndRegion,
399 std::numeric_limits<unsigned>::max()))
400 return std::move(Err);
401 unsigned Tag = EncodedCounterAndRegion & Counter::EncodingTagMask;
402 return Tag == Counter::Zero;
403 }
404
create(SectionRef & Section)405 Error InstrProfSymtab::create(SectionRef &Section) {
406 Expected<StringRef> DataOrErr = Section.getContents();
407 if (!DataOrErr)
408 return DataOrErr.takeError();
409 Data = *DataOrErr;
410 Address = Section.getAddress();
411
412 // If this is a linked PE/COFF file, then we have to skip over the null byte
413 // that is allocated in the .lprfn$A section in the LLVM profiling runtime.
414 const ObjectFile *Obj = Section.getObject();
415 if (isa<COFFObjectFile>(Obj) && !Obj->isRelocatableObject())
416 Data = Data.drop_front(1);
417
418 return Error::success();
419 }
420
getFuncName(uint64_t Pointer,size_t Size)421 StringRef InstrProfSymtab::getFuncName(uint64_t Pointer, size_t Size) {
422 if (Pointer < Address)
423 return StringRef();
424 auto Offset = Pointer - Address;
425 if (Offset + Size > Data.size())
426 return StringRef();
427 return Data.substr(Pointer - Address, Size);
428 }
429
430 // Check if the mapping data is a dummy, i.e. is emitted for an unused function.
isCoverageMappingDummy(uint64_t Hash,StringRef Mapping)431 static Expected<bool> isCoverageMappingDummy(uint64_t Hash, StringRef Mapping) {
432 // The hash value of dummy mapping records is always zero.
433 if (Hash)
434 return false;
435 return RawCoverageMappingDummyChecker(Mapping).isDummy();
436 }
437
438 /// A range of filename indices. Used to specify the location of a batch of
439 /// filenames in a vector-like container.
440 struct FilenameRange {
441 unsigned StartingIndex;
442 unsigned Length;
443
FilenameRangeFilenameRange444 FilenameRange(unsigned StartingIndex, unsigned Length)
445 : StartingIndex(StartingIndex), Length(Length) {}
446
markInvalidFilenameRange447 void markInvalid() { Length = 0; }
isInvalidFilenameRange448 bool isInvalid() const { return Length == 0; }
449 };
450
451 namespace {
452
453 /// The interface to read coverage mapping function records for a module.
454 struct CovMapFuncRecordReader {
455 virtual ~CovMapFuncRecordReader() = default;
456
457 // Read a coverage header.
458 //
459 // \p CovBuf points to the buffer containing the \c CovHeader of the coverage
460 // mapping data associated with the module.
461 //
462 // Returns a pointer to the next \c CovHeader if it exists, or to an address
463 // greater than \p CovEnd if not.
464 virtual Expected<const char *>
465 readCoverageHeader(const char *CovBuf, const char *CovBufEnd,
466 BinaryCoverageReader::DecompressedData &Decompressed) = 0;
467
468 // Read function records.
469 //
470 // \p FuncRecBuf points to the buffer containing a batch of function records.
471 // \p FuncRecBufEnd points past the end of the batch of records.
472 //
473 // Prior to Version4, \p OutOfLineFileRange points to a sequence of filenames
474 // associated with the function records. It is unused in Version4.
475 //
476 // Prior to Version4, \p OutOfLineMappingBuf points to a sequence of coverage
477 // mappings associated with the function records. It is unused in Version4.
478 virtual Error readFunctionRecords(const char *FuncRecBuf,
479 const char *FuncRecBufEnd,
480 Optional<FilenameRange> OutOfLineFileRange,
481 const char *OutOfLineMappingBuf,
482 const char *OutOfLineMappingBufEnd) = 0;
483
484 template <class IntPtrT, support::endianness Endian>
485 static Expected<std::unique_ptr<CovMapFuncRecordReader>>
486 get(CovMapVersion Version, InstrProfSymtab &P,
487 std::vector<BinaryCoverageReader::ProfileMappingRecord> &R,
488 std::vector<StringRef> &F);
489 };
490
491 // A class for reading coverage mapping function records for a module.
492 template <CovMapVersion Version, class IntPtrT, support::endianness Endian>
493 class VersionedCovMapFuncRecordReader : public CovMapFuncRecordReader {
494 using FuncRecordType =
495 typename CovMapTraits<Version, IntPtrT>::CovMapFuncRecordType;
496 using NameRefType = typename CovMapTraits<Version, IntPtrT>::NameRefType;
497
498 // Maps function's name references to the indexes of their records
499 // in \c Records.
500 DenseMap<NameRefType, size_t> FunctionRecords;
501 InstrProfSymtab &ProfileNames;
502 std::vector<StringRef> &Filenames;
503 std::vector<BinaryCoverageReader::ProfileMappingRecord> &Records;
504
505 // Maps a hash of the filenames in a TU to a \c FileRange. The range
506 // specifies the location of the hashed filenames in \c Filenames.
507 DenseMap<uint64_t, FilenameRange> FileRangeMap;
508
509 // Add the record to the collection if we don't already have a record that
510 // points to the same function name. This is useful to ignore the redundant
511 // records for the functions with ODR linkage.
512 // In addition, prefer records with real coverage mapping data to dummy
513 // records, which were emitted for inline functions which were seen but
514 // not used in the corresponding translation unit.
insertFunctionRecordIfNeeded(const FuncRecordType * CFR,StringRef Mapping,FilenameRange FileRange)515 Error insertFunctionRecordIfNeeded(const FuncRecordType *CFR,
516 StringRef Mapping,
517 FilenameRange FileRange) {
518 ++CovMapNumRecords;
519 uint64_t FuncHash = CFR->template getFuncHash<Endian>();
520 NameRefType NameRef = CFR->template getFuncNameRef<Endian>();
521 auto InsertResult =
522 FunctionRecords.insert(std::make_pair(NameRef, Records.size()));
523 if (InsertResult.second) {
524 StringRef FuncName;
525 if (Error Err = CFR->template getFuncName<Endian>(ProfileNames, FuncName))
526 return Err;
527 if (FuncName.empty())
528 return make_error<InstrProfError>(instrprof_error::malformed);
529 ++CovMapNumUsedRecords;
530 Records.emplace_back(Version, FuncName, FuncHash, Mapping,
531 FileRange.StartingIndex, FileRange.Length);
532 return Error::success();
533 }
534 // Update the existing record if it's a dummy and the new record is real.
535 size_t OldRecordIndex = InsertResult.first->second;
536 BinaryCoverageReader::ProfileMappingRecord &OldRecord =
537 Records[OldRecordIndex];
538 Expected<bool> OldIsDummyExpected = isCoverageMappingDummy(
539 OldRecord.FunctionHash, OldRecord.CoverageMapping);
540 if (Error Err = OldIsDummyExpected.takeError())
541 return Err;
542 if (!*OldIsDummyExpected)
543 return Error::success();
544 Expected<bool> NewIsDummyExpected =
545 isCoverageMappingDummy(FuncHash, Mapping);
546 if (Error Err = NewIsDummyExpected.takeError())
547 return Err;
548 if (*NewIsDummyExpected)
549 return Error::success();
550 ++CovMapNumUsedRecords;
551 OldRecord.FunctionHash = FuncHash;
552 OldRecord.CoverageMapping = Mapping;
553 OldRecord.FilenamesBegin = FileRange.StartingIndex;
554 OldRecord.FilenamesSize = FileRange.Length;
555 return Error::success();
556 }
557
558 public:
VersionedCovMapFuncRecordReader(InstrProfSymtab & P,std::vector<BinaryCoverageReader::ProfileMappingRecord> & R,std::vector<StringRef> & F)559 VersionedCovMapFuncRecordReader(
560 InstrProfSymtab &P,
561 std::vector<BinaryCoverageReader::ProfileMappingRecord> &R,
562 std::vector<StringRef> &F)
563 : ProfileNames(P), Filenames(F), Records(R) {}
564
565 ~VersionedCovMapFuncRecordReader() override = default;
566
readCoverageHeader(const char * CovBuf,const char * CovBufEnd,BinaryCoverageReader::DecompressedData & Decompressed)567 Expected<const char *> readCoverageHeader(
568 const char *CovBuf, const char *CovBufEnd,
569 BinaryCoverageReader::DecompressedData &Decompressed) override {
570 using namespace support;
571
572 if (CovBuf + sizeof(CovMapHeader) > CovBufEnd)
573 return make_error<CoverageMapError>(coveragemap_error::malformed);
574 auto CovHeader = reinterpret_cast<const CovMapHeader *>(CovBuf);
575 uint32_t NRecords = CovHeader->getNRecords<Endian>();
576 uint32_t FilenamesSize = CovHeader->getFilenamesSize<Endian>();
577 uint32_t CoverageSize = CovHeader->getCoverageSize<Endian>();
578 assert((CovMapVersion)CovHeader->getVersion<Endian>() == Version);
579 CovBuf = reinterpret_cast<const char *>(CovHeader + 1);
580
581 // Skip past the function records, saving the start and end for later.
582 // This is a no-op in Version4 (function records are read after all headers
583 // are read).
584 const char *FuncRecBuf = nullptr;
585 const char *FuncRecBufEnd = nullptr;
586 if (Version < CovMapVersion::Version4)
587 FuncRecBuf = CovBuf;
588 CovBuf += NRecords * sizeof(FuncRecordType);
589 if (Version < CovMapVersion::Version4)
590 FuncRecBufEnd = CovBuf;
591
592 // Get the filenames.
593 if (CovBuf + FilenamesSize > CovBufEnd)
594 return make_error<CoverageMapError>(coveragemap_error::malformed);
595 size_t FilenamesBegin = Filenames.size();
596 StringRef FilenameRegion(CovBuf, FilenamesSize);
597 RawCoverageFilenamesReader Reader(FilenameRegion, Filenames);
598 if (auto Err = Reader.read(Version, Decompressed))
599 return std::move(Err);
600 CovBuf += FilenamesSize;
601 FilenameRange FileRange(FilenamesBegin, Filenames.size() - FilenamesBegin);
602
603 if (Version == CovMapVersion::Version4) {
604 // Map a hash of the filenames region to the filename range associated
605 // with this coverage header.
606 int64_t FilenamesRef =
607 llvm::IndexedInstrProf::ComputeHash(FilenameRegion);
608 auto Insert =
609 FileRangeMap.insert(std::make_pair(FilenamesRef, FileRange));
610 if (!Insert.second) {
611 // The same filenames ref was encountered twice. It's possible that
612 // the associated filenames are the same.
613 auto It = Filenames.begin();
614 FilenameRange &OrigRange = Insert.first->getSecond();
615 if (std::equal(It + OrigRange.StartingIndex,
616 It + OrigRange.StartingIndex + OrigRange.Length,
617 It + FileRange.StartingIndex,
618 It + FileRange.StartingIndex + FileRange.Length))
619 // Map the new range to the original one.
620 FileRange = OrigRange;
621 else
622 // This is a hash collision. Mark the filenames ref invalid.
623 OrigRange.markInvalid();
624 }
625 }
626
627 // We'll read the coverage mapping records in the loop below.
628 // This is a no-op in Version4 (coverage mappings are not affixed to the
629 // coverage header).
630 const char *MappingBuf = CovBuf;
631 if (Version == CovMapVersion::Version4 && CoverageSize != 0)
632 return make_error<CoverageMapError>(coveragemap_error::malformed);
633 CovBuf += CoverageSize;
634 const char *MappingEnd = CovBuf;
635
636 if (CovBuf > CovBufEnd)
637 return make_error<CoverageMapError>(coveragemap_error::malformed);
638
639 if (Version < CovMapVersion::Version4) {
640 // Read each function record.
641 if (Error E = readFunctionRecords(FuncRecBuf, FuncRecBufEnd, FileRange,
642 MappingBuf, MappingEnd))
643 return std::move(E);
644 }
645
646 // Each coverage map has an alignment of 8, so we need to adjust alignment
647 // before reading the next map.
648 CovBuf += offsetToAlignedAddr(CovBuf, Align(8));
649
650 return CovBuf;
651 }
652
readFunctionRecords(const char * FuncRecBuf,const char * FuncRecBufEnd,Optional<FilenameRange> OutOfLineFileRange,const char * OutOfLineMappingBuf,const char * OutOfLineMappingBufEnd)653 Error readFunctionRecords(const char *FuncRecBuf, const char *FuncRecBufEnd,
654 Optional<FilenameRange> OutOfLineFileRange,
655 const char *OutOfLineMappingBuf,
656 const char *OutOfLineMappingBufEnd) override {
657 auto CFR = reinterpret_cast<const FuncRecordType *>(FuncRecBuf);
658 while ((const char *)CFR < FuncRecBufEnd) {
659 // Validate the length of the coverage mapping for this function.
660 const char *NextMappingBuf;
661 const FuncRecordType *NextCFR;
662 std::tie(NextMappingBuf, NextCFR) =
663 CFR->template advanceByOne<Endian>(OutOfLineMappingBuf);
664 if (Version < CovMapVersion::Version4)
665 if (NextMappingBuf > OutOfLineMappingBufEnd)
666 return make_error<CoverageMapError>(coveragemap_error::malformed);
667
668 // Look up the set of filenames associated with this function record.
669 Optional<FilenameRange> FileRange;
670 if (Version < CovMapVersion::Version4) {
671 FileRange = OutOfLineFileRange;
672 } else {
673 uint64_t FilenamesRef = CFR->template getFilenamesRef<Endian>();
674 auto It = FileRangeMap.find(FilenamesRef);
675 if (It == FileRangeMap.end())
676 return make_error<CoverageMapError>(coveragemap_error::malformed);
677 else
678 FileRange = It->getSecond();
679 }
680
681 // Now, read the coverage data.
682 if (FileRange && !FileRange->isInvalid()) {
683 StringRef Mapping =
684 CFR->template getCoverageMapping<Endian>(OutOfLineMappingBuf);
685 if (Version == CovMapVersion::Version4 &&
686 Mapping.data() + Mapping.size() > FuncRecBufEnd)
687 return make_error<CoverageMapError>(coveragemap_error::malformed);
688 if (Error Err = insertFunctionRecordIfNeeded(CFR, Mapping, *FileRange))
689 return Err;
690 }
691
692 std::tie(OutOfLineMappingBuf, CFR) = std::tie(NextMappingBuf, NextCFR);
693 }
694 return Error::success();
695 }
696 };
697
698 } // end anonymous namespace
699
700 template <class IntPtrT, support::endianness Endian>
get(CovMapVersion Version,InstrProfSymtab & P,std::vector<BinaryCoverageReader::ProfileMappingRecord> & R,std::vector<StringRef> & F)701 Expected<std::unique_ptr<CovMapFuncRecordReader>> CovMapFuncRecordReader::get(
702 CovMapVersion Version, InstrProfSymtab &P,
703 std::vector<BinaryCoverageReader::ProfileMappingRecord> &R,
704 std::vector<StringRef> &F) {
705 using namespace coverage;
706
707 switch (Version) {
708 case CovMapVersion::Version1:
709 return std::make_unique<VersionedCovMapFuncRecordReader<
710 CovMapVersion::Version1, IntPtrT, Endian>>(P, R, F);
711 case CovMapVersion::Version2:
712 case CovMapVersion::Version3:
713 case CovMapVersion::Version4:
714 // Decompress the name data.
715 if (Error E = P.create(P.getNameData()))
716 return std::move(E);
717 if (Version == CovMapVersion::Version2)
718 return std::make_unique<VersionedCovMapFuncRecordReader<
719 CovMapVersion::Version2, IntPtrT, Endian>>(P, R, F);
720 else if (Version == CovMapVersion::Version3)
721 return std::make_unique<VersionedCovMapFuncRecordReader<
722 CovMapVersion::Version3, IntPtrT, Endian>>(P, R, F);
723 else if (Version == CovMapVersion::Version4)
724 return std::make_unique<VersionedCovMapFuncRecordReader<
725 CovMapVersion::Version4, IntPtrT, Endian>>(P, R, F);
726 }
727 llvm_unreachable("Unsupported version");
728 }
729
730 template <typename T, support::endianness Endian>
readCoverageMappingData(InstrProfSymtab & ProfileNames,StringRef CovMap,StringRef FuncRecords,std::vector<BinaryCoverageReader::ProfileMappingRecord> & Records,std::vector<StringRef> & Filenames,BinaryCoverageReader::DecompressedData & Decompressed)731 static Error readCoverageMappingData(
732 InstrProfSymtab &ProfileNames, StringRef CovMap, StringRef FuncRecords,
733 std::vector<BinaryCoverageReader::ProfileMappingRecord> &Records,
734 std::vector<StringRef> &Filenames,
735 BinaryCoverageReader::DecompressedData &Decompressed) {
736 using namespace coverage;
737
738 // Read the records in the coverage data section.
739 auto CovHeader =
740 reinterpret_cast<const CovMapHeader *>(CovMap.data());
741 CovMapVersion Version = (CovMapVersion)CovHeader->getVersion<Endian>();
742 if (Version > CovMapVersion::CurrentVersion)
743 return make_error<CoverageMapError>(coveragemap_error::unsupported_version);
744 Expected<std::unique_ptr<CovMapFuncRecordReader>> ReaderExpected =
745 CovMapFuncRecordReader::get<T, Endian>(Version, ProfileNames, Records,
746 Filenames);
747 if (Error E = ReaderExpected.takeError())
748 return E;
749 auto Reader = std::move(ReaderExpected.get());
750 const char *CovBuf = CovMap.data();
751 const char *CovBufEnd = CovBuf + CovMap.size();
752 const char *FuncRecBuf = FuncRecords.data();
753 const char *FuncRecBufEnd = FuncRecords.data() + FuncRecords.size();
754 while (CovBuf < CovBufEnd) {
755 // Read the current coverage header & filename data.
756 //
757 // Prior to Version4, this also reads all function records affixed to the
758 // header.
759 //
760 // Return a pointer to the next coverage header.
761 auto NextOrErr =
762 Reader->readCoverageHeader(CovBuf, CovBufEnd, Decompressed);
763 if (auto E = NextOrErr.takeError())
764 return E;
765 CovBuf = NextOrErr.get();
766 }
767 // In Version4, function records are not affixed to coverage headers. Read
768 // the records from their dedicated section.
769 if (Version == CovMapVersion::Version4)
770 return Reader->readFunctionRecords(FuncRecBuf, FuncRecBufEnd, None, nullptr,
771 nullptr);
772 return Error::success();
773 }
774
775 static const char *TestingFormatMagic = "llvmcovmtestdata";
776
777 Expected<std::unique_ptr<BinaryCoverageReader>>
createCoverageReaderFromBuffer(StringRef Coverage,std::string && FuncRecords,InstrProfSymtab && ProfileNames,uint8_t BytesInAddress,support::endianness Endian)778 BinaryCoverageReader::createCoverageReaderFromBuffer(
779 StringRef Coverage, std::string &&FuncRecords, InstrProfSymtab &&ProfileNames,
780 uint8_t BytesInAddress, support::endianness Endian) {
781 std::unique_ptr<BinaryCoverageReader> Reader(
782 new BinaryCoverageReader(std::move(FuncRecords)));
783 Reader->ProfileNames = std::move(ProfileNames);
784 StringRef FuncRecordsRef = Reader->FuncRecords;
785 if (BytesInAddress == 4 && Endian == support::endianness::little) {
786 if (Error E =
787 readCoverageMappingData<uint32_t, support::endianness::little>(
788 Reader->ProfileNames, Coverage, FuncRecordsRef,
789 Reader->MappingRecords, Reader->Filenames,
790 Reader->Decompressed))
791 return std::move(E);
792 } else if (BytesInAddress == 4 && Endian == support::endianness::big) {
793 if (Error E = readCoverageMappingData<uint32_t, support::endianness::big>(
794 Reader->ProfileNames, Coverage, FuncRecordsRef,
795 Reader->MappingRecords, Reader->Filenames, Reader->Decompressed))
796 return std::move(E);
797 } else if (BytesInAddress == 8 && Endian == support::endianness::little) {
798 if (Error E =
799 readCoverageMappingData<uint64_t, support::endianness::little>(
800 Reader->ProfileNames, Coverage, FuncRecordsRef,
801 Reader->MappingRecords, Reader->Filenames,
802 Reader->Decompressed))
803 return std::move(E);
804 } else if (BytesInAddress == 8 && Endian == support::endianness::big) {
805 if (Error E = readCoverageMappingData<uint64_t, support::endianness::big>(
806 Reader->ProfileNames, Coverage, FuncRecordsRef,
807 Reader->MappingRecords, Reader->Filenames, Reader->Decompressed))
808 return std::move(E);
809 } else
810 return make_error<CoverageMapError>(coveragemap_error::malformed);
811 return std::move(Reader);
812 }
813
814 static Expected<std::unique_ptr<BinaryCoverageReader>>
loadTestingFormat(StringRef Data)815 loadTestingFormat(StringRef Data) {
816 uint8_t BytesInAddress = 8;
817 support::endianness Endian = support::endianness::little;
818
819 Data = Data.substr(StringRef(TestingFormatMagic).size());
820 if (Data.empty())
821 return make_error<CoverageMapError>(coveragemap_error::truncated);
822 unsigned N = 0;
823 uint64_t ProfileNamesSize = decodeULEB128(Data.bytes_begin(), &N);
824 if (N > Data.size())
825 return make_error<CoverageMapError>(coveragemap_error::malformed);
826 Data = Data.substr(N);
827 if (Data.empty())
828 return make_error<CoverageMapError>(coveragemap_error::truncated);
829 N = 0;
830 uint64_t Address = decodeULEB128(Data.bytes_begin(), &N);
831 if (N > Data.size())
832 return make_error<CoverageMapError>(coveragemap_error::malformed);
833 Data = Data.substr(N);
834 if (Data.size() < ProfileNamesSize)
835 return make_error<CoverageMapError>(coveragemap_error::malformed);
836 InstrProfSymtab ProfileNames;
837 if (Error E = ProfileNames.create(Data.substr(0, ProfileNamesSize), Address))
838 return std::move(E);
839 StringRef CoverageMapping = Data.substr(ProfileNamesSize);
840 // Skip the padding bytes because coverage map data has an alignment of 8.
841 if (CoverageMapping.empty())
842 return make_error<CoverageMapError>(coveragemap_error::truncated);
843 size_t Pad = offsetToAlignedAddr(CoverageMapping.data(), Align(8));
844 if (CoverageMapping.size() < Pad)
845 return make_error<CoverageMapError>(coveragemap_error::malformed);
846 CoverageMapping = CoverageMapping.substr(Pad);
847 return BinaryCoverageReader::createCoverageReaderFromBuffer(
848 CoverageMapping, "", std::move(ProfileNames), BytesInAddress, Endian);
849 }
850
851 /// Find all sections that match \p Name. There may be more than one if comdats
852 /// are in use, e.g. for the __llvm_covfun section on ELF.
lookupSections(ObjectFile & OF,StringRef Name)853 static Expected<std::vector<SectionRef>> lookupSections(ObjectFile &OF,
854 StringRef Name) {
855 // On COFF, the object file section name may end in "$M". This tells the
856 // linker to sort these sections between "$A" and "$Z". The linker removes the
857 // dollar and everything after it in the final binary. Do the same to match.
858 bool IsCOFF = isa<COFFObjectFile>(OF);
859 auto stripSuffix = [IsCOFF](StringRef N) {
860 return IsCOFF ? N.split('$').first : N;
861 };
862 Name = stripSuffix(Name);
863
864 std::vector<SectionRef> Sections;
865 for (const auto &Section : OF.sections()) {
866 Expected<StringRef> NameOrErr = Section.getName();
867 if (!NameOrErr)
868 return NameOrErr.takeError();
869 if (stripSuffix(*NameOrErr) == Name)
870 Sections.push_back(Section);
871 }
872 if (Sections.empty())
873 return make_error<CoverageMapError>(coveragemap_error::no_data_found);
874 return Sections;
875 }
876
877 static Expected<std::unique_ptr<BinaryCoverageReader>>
loadBinaryFormat(std::unique_ptr<Binary> Bin,StringRef Arch)878 loadBinaryFormat(std::unique_ptr<Binary> Bin, StringRef Arch) {
879 std::unique_ptr<ObjectFile> OF;
880 if (auto *Universal = dyn_cast<MachOUniversalBinary>(Bin.get())) {
881 // If we have a universal binary, try to look up the object for the
882 // appropriate architecture.
883 auto ObjectFileOrErr = Universal->getMachOObjectForArch(Arch);
884 if (!ObjectFileOrErr)
885 return ObjectFileOrErr.takeError();
886 OF = std::move(ObjectFileOrErr.get());
887 } else if (isa<ObjectFile>(Bin.get())) {
888 // For any other object file, upcast and take ownership.
889 OF.reset(cast<ObjectFile>(Bin.release()));
890 // If we've asked for a particular arch, make sure they match.
891 if (!Arch.empty() && OF->getArch() != Triple(Arch).getArch())
892 return errorCodeToError(object_error::arch_not_found);
893 } else
894 // We can only handle object files.
895 return make_error<CoverageMapError>(coveragemap_error::malformed);
896
897 // The coverage uses native pointer sizes for the object it's written in.
898 uint8_t BytesInAddress = OF->getBytesInAddress();
899 support::endianness Endian = OF->isLittleEndian()
900 ? support::endianness::little
901 : support::endianness::big;
902
903 // Look for the sections that we are interested in.
904 auto ObjFormat = OF->getTripleObjectFormat();
905 auto NamesSection =
906 lookupSections(*OF, getInstrProfSectionName(IPSK_name, ObjFormat,
907 /*AddSegmentInfo=*/false));
908 if (auto E = NamesSection.takeError())
909 return std::move(E);
910 auto CoverageSection =
911 lookupSections(*OF, getInstrProfSectionName(IPSK_covmap, ObjFormat,
912 /*AddSegmentInfo=*/false));
913 if (auto E = CoverageSection.takeError())
914 return std::move(E);
915 std::vector<SectionRef> CoverageSectionRefs = *CoverageSection;
916 if (CoverageSectionRefs.size() != 1)
917 return make_error<CoverageMapError>(coveragemap_error::malformed);
918 auto CoverageMappingOrErr = CoverageSectionRefs.back().getContents();
919 if (!CoverageMappingOrErr)
920 return CoverageMappingOrErr.takeError();
921 StringRef CoverageMapping = CoverageMappingOrErr.get();
922
923 InstrProfSymtab ProfileNames;
924 std::vector<SectionRef> NamesSectionRefs = *NamesSection;
925 if (NamesSectionRefs.size() != 1)
926 return make_error<CoverageMapError>(coveragemap_error::malformed);
927 if (Error E = ProfileNames.create(NamesSectionRefs.back()))
928 return std::move(E);
929
930 // Look for the coverage records section (Version4 only).
931 std::string FuncRecords;
932 auto CoverageRecordsSections =
933 lookupSections(*OF, getInstrProfSectionName(IPSK_covfun, ObjFormat,
934 /*AddSegmentInfo=*/false));
935 if (auto E = CoverageRecordsSections.takeError())
936 consumeError(std::move(E));
937 else {
938 for (SectionRef Section : *CoverageRecordsSections) {
939 auto CoverageRecordsOrErr = Section.getContents();
940 if (!CoverageRecordsOrErr)
941 return CoverageRecordsOrErr.takeError();
942 FuncRecords += CoverageRecordsOrErr.get();
943 while (FuncRecords.size() % 8 != 0)
944 FuncRecords += '\0';
945 }
946 }
947
948 return BinaryCoverageReader::createCoverageReaderFromBuffer(
949 CoverageMapping, std::move(FuncRecords), std::move(ProfileNames),
950 BytesInAddress, Endian);
951 }
952
953 Expected<std::vector<std::unique_ptr<BinaryCoverageReader>>>
create(MemoryBufferRef ObjectBuffer,StringRef Arch,SmallVectorImpl<std::unique_ptr<MemoryBuffer>> & ObjectFileBuffers)954 BinaryCoverageReader::create(
955 MemoryBufferRef ObjectBuffer, StringRef Arch,
956 SmallVectorImpl<std::unique_ptr<MemoryBuffer>> &ObjectFileBuffers) {
957 std::vector<std::unique_ptr<BinaryCoverageReader>> Readers;
958
959 if (ObjectBuffer.getBuffer().startswith(TestingFormatMagic)) {
960 // This is a special format used for testing.
961 auto ReaderOrErr = loadTestingFormat(ObjectBuffer.getBuffer());
962 if (!ReaderOrErr)
963 return ReaderOrErr.takeError();
964 Readers.push_back(std::move(ReaderOrErr.get()));
965 return std::move(Readers);
966 }
967
968 auto BinOrErr = createBinary(ObjectBuffer);
969 if (!BinOrErr)
970 return BinOrErr.takeError();
971 std::unique_ptr<Binary> Bin = std::move(BinOrErr.get());
972
973 // MachO universal binaries which contain archives need to be treated as
974 // archives, not as regular binaries.
975 if (auto *Universal = dyn_cast<MachOUniversalBinary>(Bin.get())) {
976 for (auto &ObjForArch : Universal->objects()) {
977 // Skip slices within the universal binary which target the wrong arch.
978 std::string ObjArch = ObjForArch.getArchFlagName();
979 if (Arch != ObjArch)
980 continue;
981
982 auto ArchiveOrErr = ObjForArch.getAsArchive();
983 if (!ArchiveOrErr) {
984 // If this is not an archive, try treating it as a regular object.
985 consumeError(ArchiveOrErr.takeError());
986 break;
987 }
988
989 return BinaryCoverageReader::create(
990 ArchiveOrErr.get()->getMemoryBufferRef(), Arch, ObjectFileBuffers);
991 }
992 }
993
994 // Load coverage out of archive members.
995 if (auto *Ar = dyn_cast<Archive>(Bin.get())) {
996 Error Err = Error::success();
997 for (auto &Child : Ar->children(Err)) {
998 Expected<MemoryBufferRef> ChildBufOrErr = Child.getMemoryBufferRef();
999 if (!ChildBufOrErr)
1000 return ChildBufOrErr.takeError();
1001
1002 auto ChildReadersOrErr = BinaryCoverageReader::create(
1003 ChildBufOrErr.get(), Arch, ObjectFileBuffers);
1004 if (!ChildReadersOrErr)
1005 return ChildReadersOrErr.takeError();
1006 for (auto &Reader : ChildReadersOrErr.get())
1007 Readers.push_back(std::move(Reader));
1008 }
1009 if (Err)
1010 return std::move(Err);
1011
1012 // Thin archives reference object files outside of the archive file, i.e.
1013 // files which reside in memory not owned by the caller. Transfer ownership
1014 // to the caller.
1015 if (Ar->isThin())
1016 for (auto &Buffer : Ar->takeThinBuffers())
1017 ObjectFileBuffers.push_back(std::move(Buffer));
1018
1019 return std::move(Readers);
1020 }
1021
1022 auto ReaderOrErr = loadBinaryFormat(std::move(Bin), Arch);
1023 if (!ReaderOrErr)
1024 return ReaderOrErr.takeError();
1025 Readers.push_back(std::move(ReaderOrErr.get()));
1026 return std::move(Readers);
1027 }
1028
readNextRecord(CoverageMappingRecord & Record)1029 Error BinaryCoverageReader::readNextRecord(CoverageMappingRecord &Record) {
1030 if (CurrentRecord >= MappingRecords.size())
1031 return make_error<CoverageMapError>(coveragemap_error::eof);
1032
1033 FunctionsFilenames.clear();
1034 Expressions.clear();
1035 MappingRegions.clear();
1036 auto &R = MappingRecords[CurrentRecord];
1037 RawCoverageMappingReader Reader(
1038 R.CoverageMapping,
1039 makeArrayRef(Filenames).slice(R.FilenamesBegin, R.FilenamesSize),
1040 FunctionsFilenames, Expressions, MappingRegions);
1041 if (auto Err = Reader.read())
1042 return Err;
1043
1044 Record.FunctionName = R.FunctionName;
1045 Record.FunctionHash = R.FunctionHash;
1046 Record.Filenames = FunctionsFilenames;
1047 Record.Expressions = Expressions;
1048 Record.MappingRegions = MappingRegions;
1049
1050 ++CurrentRecord;
1051 return Error::success();
1052 }
1053