1 //=-- CoverageMappingReader.cpp - Code coverage mapping reader ----*- C++ -*-=//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains support for reading coverage mapping data for
11 // instrumentation based coverage.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/ProfileData/CoverageMappingReader.h"
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/Object/MachOUniversal.h"
18 #include "llvm/Object/ObjectFile.h"
19 #include "llvm/Support/Debug.h"
20 #include "llvm/Support/Endian.h"
21 #include "llvm/Support/LEB128.h"
22 #include "llvm/Support/MathExtras.h"
23 #include "llvm/Support/raw_ostream.h"
24 
25 using namespace llvm;
26 using namespace coverage;
27 using namespace object;
28 
29 #define DEBUG_TYPE "coverage-mapping"
30 
increment()31 void CoverageMappingIterator::increment() {
32   // Check if all the records were read or if an error occurred while reading
33   // the next record.
34   if (Reader->readNextRecord(Record))
35     *this = CoverageMappingIterator();
36 }
37 
readULEB128(uint64_t & Result)38 std::error_code RawCoverageReader::readULEB128(uint64_t &Result) {
39   if (Data.size() < 1)
40     return coveragemap_error::truncated;
41   unsigned N = 0;
42   Result = decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
43   if (N > Data.size())
44     return coveragemap_error::malformed;
45   Data = Data.substr(N);
46   return std::error_code();
47 }
48 
readIntMax(uint64_t & Result,uint64_t MaxPlus1)49 std::error_code RawCoverageReader::readIntMax(uint64_t &Result,
50                                               uint64_t MaxPlus1) {
51   if (auto Err = readULEB128(Result))
52     return Err;
53   if (Result >= MaxPlus1)
54     return coveragemap_error::malformed;
55   return std::error_code();
56 }
57 
readSize(uint64_t & Result)58 std::error_code RawCoverageReader::readSize(uint64_t &Result) {
59   if (auto Err = readULEB128(Result))
60     return Err;
61   // Sanity check the number.
62   if (Result > Data.size())
63     return coveragemap_error::malformed;
64   return std::error_code();
65 }
66 
readString(StringRef & Result)67 std::error_code RawCoverageReader::readString(StringRef &Result) {
68   uint64_t Length;
69   if (auto Err = readSize(Length))
70     return Err;
71   Result = Data.substr(0, Length);
72   Data = Data.substr(Length);
73   return std::error_code();
74 }
75 
read()76 std::error_code RawCoverageFilenamesReader::read() {
77   uint64_t NumFilenames;
78   if (auto Err = readSize(NumFilenames))
79     return Err;
80   for (size_t I = 0; I < NumFilenames; ++I) {
81     StringRef Filename;
82     if (auto Err = readString(Filename))
83       return Err;
84     Filenames.push_back(Filename);
85   }
86   return std::error_code();
87 }
88 
decodeCounter(unsigned Value,Counter & C)89 std::error_code RawCoverageMappingReader::decodeCounter(unsigned Value,
90                                                         Counter &C) {
91   auto Tag = Value & Counter::EncodingTagMask;
92   switch (Tag) {
93   case Counter::Zero:
94     C = Counter::getZero();
95     return std::error_code();
96   case Counter::CounterValueReference:
97     C = Counter::getCounter(Value >> Counter::EncodingTagBits);
98     return std::error_code();
99   default:
100     break;
101   }
102   Tag -= Counter::Expression;
103   switch (Tag) {
104   case CounterExpression::Subtract:
105   case CounterExpression::Add: {
106     auto ID = Value >> Counter::EncodingTagBits;
107     if (ID >= Expressions.size())
108       return coveragemap_error::malformed;
109     Expressions[ID].Kind = CounterExpression::ExprKind(Tag);
110     C = Counter::getExpression(ID);
111     break;
112   }
113   default:
114     return coveragemap_error::malformed;
115   }
116   return std::error_code();
117 }
118 
readCounter(Counter & C)119 std::error_code RawCoverageMappingReader::readCounter(Counter &C) {
120   uint64_t EncodedCounter;
121   if (auto Err =
122           readIntMax(EncodedCounter, std::numeric_limits<unsigned>::max()))
123     return Err;
124   if (auto Err = decodeCounter(EncodedCounter, C))
125     return Err;
126   return std::error_code();
127 }
128 
129 static const unsigned EncodingExpansionRegionBit = 1
130                                                    << Counter::EncodingTagBits;
131 
132 /// \brief Read the sub-array of regions for the given inferred file id.
133 /// \param NumFileIDs the number of file ids that are defined for this
134 /// function.
readMappingRegionsSubArray(std::vector<CounterMappingRegion> & MappingRegions,unsigned InferredFileID,size_t NumFileIDs)135 std::error_code RawCoverageMappingReader::readMappingRegionsSubArray(
136     std::vector<CounterMappingRegion> &MappingRegions, unsigned InferredFileID,
137     size_t NumFileIDs) {
138   uint64_t NumRegions;
139   if (auto Err = readSize(NumRegions))
140     return Err;
141   unsigned LineStart = 0;
142   for (size_t I = 0; I < NumRegions; ++I) {
143     Counter C;
144     CounterMappingRegion::RegionKind Kind = CounterMappingRegion::CodeRegion;
145 
146     // Read the combined counter + region kind.
147     uint64_t EncodedCounterAndRegion;
148     if (auto Err = readIntMax(EncodedCounterAndRegion,
149                               std::numeric_limits<unsigned>::max()))
150       return Err;
151     unsigned Tag = EncodedCounterAndRegion & Counter::EncodingTagMask;
152     uint64_t ExpandedFileID = 0;
153     if (Tag != Counter::Zero) {
154       if (auto Err = decodeCounter(EncodedCounterAndRegion, C))
155         return Err;
156     } else {
157       // Is it an expansion region?
158       if (EncodedCounterAndRegion & EncodingExpansionRegionBit) {
159         Kind = CounterMappingRegion::ExpansionRegion;
160         ExpandedFileID = EncodedCounterAndRegion >>
161                          Counter::EncodingCounterTagAndExpansionRegionTagBits;
162         if (ExpandedFileID >= NumFileIDs)
163           return coveragemap_error::malformed;
164       } else {
165         switch (EncodedCounterAndRegion >>
166                 Counter::EncodingCounterTagAndExpansionRegionTagBits) {
167         case CounterMappingRegion::CodeRegion:
168           // Don't do anything when we have a code region with a zero counter.
169           break;
170         case CounterMappingRegion::SkippedRegion:
171           Kind = CounterMappingRegion::SkippedRegion;
172           break;
173         default:
174           return coveragemap_error::malformed;
175         }
176       }
177     }
178 
179     // Read the source range.
180     uint64_t LineStartDelta, ColumnStart, NumLines, ColumnEnd;
181     if (auto Err =
182             readIntMax(LineStartDelta, std::numeric_limits<unsigned>::max()))
183       return Err;
184     if (auto Err = readULEB128(ColumnStart))
185       return Err;
186     if (ColumnStart > std::numeric_limits<unsigned>::max())
187       return coveragemap_error::malformed;
188     if (auto Err = readIntMax(NumLines, std::numeric_limits<unsigned>::max()))
189       return Err;
190     if (auto Err = readIntMax(ColumnEnd, std::numeric_limits<unsigned>::max()))
191       return Err;
192     LineStart += LineStartDelta;
193     // Adjust the column locations for the empty regions that are supposed to
194     // cover whole lines. Those regions should be encoded with the
195     // column range (1 -> std::numeric_limits<unsigned>::max()), but because
196     // the encoded std::numeric_limits<unsigned>::max() is several bytes long,
197     // we set the column range to (0 -> 0) to ensure that the column start and
198     // column end take up one byte each.
199     // The std::numeric_limits<unsigned>::max() is used to represent a column
200     // position at the end of the line without knowing the length of that line.
201     if (ColumnStart == 0 && ColumnEnd == 0) {
202       ColumnStart = 1;
203       ColumnEnd = std::numeric_limits<unsigned>::max();
204     }
205 
206     DEBUG({
207       dbgs() << "Counter in file " << InferredFileID << " " << LineStart << ":"
208              << ColumnStart << " -> " << (LineStart + NumLines) << ":"
209              << ColumnEnd << ", ";
210       if (Kind == CounterMappingRegion::ExpansionRegion)
211         dbgs() << "Expands to file " << ExpandedFileID;
212       else
213         CounterMappingContext(Expressions).dump(C, dbgs());
214       dbgs() << "\n";
215     });
216 
217     MappingRegions.push_back(CounterMappingRegion(
218         C, InferredFileID, ExpandedFileID, LineStart, ColumnStart,
219         LineStart + NumLines, ColumnEnd, Kind));
220   }
221   return std::error_code();
222 }
223 
read()224 std::error_code RawCoverageMappingReader::read() {
225 
226   // Read the virtual file mapping.
227   llvm::SmallVector<unsigned, 8> VirtualFileMapping;
228   uint64_t NumFileMappings;
229   if (auto Err = readSize(NumFileMappings))
230     return Err;
231   for (size_t I = 0; I < NumFileMappings; ++I) {
232     uint64_t FilenameIndex;
233     if (auto Err = readIntMax(FilenameIndex, TranslationUnitFilenames.size()))
234       return Err;
235     VirtualFileMapping.push_back(FilenameIndex);
236   }
237 
238   // Construct the files using unique filenames and virtual file mapping.
239   for (auto I : VirtualFileMapping) {
240     Filenames.push_back(TranslationUnitFilenames[I]);
241   }
242 
243   // Read the expressions.
244   uint64_t NumExpressions;
245   if (auto Err = readSize(NumExpressions))
246     return Err;
247   // Create an array of dummy expressions that get the proper counters
248   // when the expressions are read, and the proper kinds when the counters
249   // are decoded.
250   Expressions.resize(
251       NumExpressions,
252       CounterExpression(CounterExpression::Subtract, Counter(), Counter()));
253   for (size_t I = 0; I < NumExpressions; ++I) {
254     if (auto Err = readCounter(Expressions[I].LHS))
255       return Err;
256     if (auto Err = readCounter(Expressions[I].RHS))
257       return Err;
258   }
259 
260   // Read the mapping regions sub-arrays.
261   for (unsigned InferredFileID = 0, S = VirtualFileMapping.size();
262        InferredFileID < S; ++InferredFileID) {
263     if (auto Err = readMappingRegionsSubArray(MappingRegions, InferredFileID,
264                                               VirtualFileMapping.size()))
265       return Err;
266   }
267 
268   // Set the counters for the expansion regions.
269   // i.e. Counter of expansion region = counter of the first region
270   // from the expanded file.
271   // Perform multiple passes to correctly propagate the counters through
272   // all the nested expansion regions.
273   SmallVector<CounterMappingRegion *, 8> FileIDExpansionRegionMapping;
274   FileIDExpansionRegionMapping.resize(VirtualFileMapping.size(), nullptr);
275   for (unsigned Pass = 1, S = VirtualFileMapping.size(); Pass < S; ++Pass) {
276     for (auto &R : MappingRegions) {
277       if (R.Kind != CounterMappingRegion::ExpansionRegion)
278         continue;
279       assert(!FileIDExpansionRegionMapping[R.ExpandedFileID]);
280       FileIDExpansionRegionMapping[R.ExpandedFileID] = &R;
281     }
282     for (auto &R : MappingRegions) {
283       if (FileIDExpansionRegionMapping[R.FileID]) {
284         FileIDExpansionRegionMapping[R.FileID]->Count = R.Count;
285         FileIDExpansionRegionMapping[R.FileID] = nullptr;
286       }
287     }
288   }
289 
290   return std::error_code();
291 }
292 
create(SectionRef & Section)293 std::error_code InstrProfSymtab::create(SectionRef &Section) {
294   if (auto Err = Section.getContents(Data))
295     return Err;
296   Address = Section.getAddress();
297   return std::error_code();
298 }
299 
getFuncName(uint64_t Pointer,size_t Size)300 StringRef InstrProfSymtab::getFuncName(uint64_t Pointer, size_t Size) {
301   if (Pointer < Address)
302     return StringRef();
303   auto Offset = Pointer - Address;
304   if (Offset + Size > Data.size())
305     return StringRef();
306   return Data.substr(Pointer - Address, Size);
307 }
308 
309 template <typename T, support::endianness Endian>
readCoverageMappingData(InstrProfSymtab & ProfileNames,StringRef Data,std::vector<BinaryCoverageReader::ProfileMappingRecord> & Records,std::vector<StringRef> & Filenames)310 std::error_code readCoverageMappingData(
311     InstrProfSymtab &ProfileNames, StringRef Data,
312     std::vector<BinaryCoverageReader::ProfileMappingRecord> &Records,
313     std::vector<StringRef> &Filenames) {
314   using namespace support;
315   llvm::DenseSet<T> UniqueFunctionMappingData;
316 
317   // Read the records in the coverage data section.
318   for (const char *Buf = Data.data(), *End = Buf + Data.size(); Buf < End;) {
319     if (Buf + 4 * sizeof(uint32_t) > End)
320       return coveragemap_error::malformed;
321     uint32_t NRecords = endian::readNext<uint32_t, Endian, unaligned>(Buf);
322     uint32_t FilenamesSize = endian::readNext<uint32_t, Endian, unaligned>(Buf);
323     uint32_t CoverageSize = endian::readNext<uint32_t, Endian, unaligned>(Buf);
324     uint32_t Version = endian::readNext<uint32_t, Endian, unaligned>(Buf);
325 
326     switch (Version) {
327     case CoverageMappingVersion1:
328       break;
329     default:
330       return coveragemap_error::unsupported_version;
331     }
332 
333     // Skip past the function records, saving the start and end for later.
334     const char *FunBuf = Buf;
335     Buf += NRecords * sizeof(coverage::CovMapFunctionRecord<T>);
336     const char *FunEnd = Buf;
337 
338     // Get the filenames.
339     if (Buf + FilenamesSize > End)
340       return coveragemap_error::malformed;
341     size_t FilenamesBegin = Filenames.size();
342     RawCoverageFilenamesReader Reader(StringRef(Buf, FilenamesSize), Filenames);
343     if (auto Err = Reader.read())
344       return Err;
345     Buf += FilenamesSize;
346 
347     // We'll read the coverage mapping records in the loop below.
348     const char *CovBuf = Buf;
349     Buf += CoverageSize;
350     const char *CovEnd = Buf;
351 
352     if (Buf > End)
353       return coveragemap_error::malformed;
354     // Each coverage map has an alignment of 8, so we need to adjust alignment
355     // before reading the next map.
356     Buf += alignmentAdjustment(Buf, 8);
357 
358     auto CFR =
359         reinterpret_cast<const coverage::CovMapFunctionRecord<T> *>(FunBuf);
360     while ((const char *)CFR < FunEnd) {
361       // Read the function information
362       T NamePtr = endian::byte_swap<T, Endian>(CFR->NamePtr);
363       uint32_t NameSize = endian::byte_swap<uint32_t, Endian>(CFR->NameSize);
364       uint32_t DataSize = endian::byte_swap<uint32_t, Endian>(CFR->DataSize);
365       uint64_t FuncHash = endian::byte_swap<uint64_t, Endian>(CFR->FuncHash);
366       CFR++;
367 
368       // Now use that to read the coverage data.
369       if (CovBuf + DataSize > CovEnd)
370         return coveragemap_error::malformed;
371       auto Mapping = StringRef(CovBuf, DataSize);
372       CovBuf += DataSize;
373 
374       // Ignore this record if we already have a record that points to the same
375       // function name. This is useful to ignore the redundant records for the
376       // functions with ODR linkage.
377       if (!UniqueFunctionMappingData.insert(NamePtr).second)
378         continue;
379 
380       // Finally, grab the name and create a record.
381       StringRef FuncName = ProfileNames.getFuncName(NamePtr, NameSize);
382       if (NameSize && FuncName.empty())
383         return coveragemap_error::malformed;
384       Records.push_back(BinaryCoverageReader::ProfileMappingRecord(
385           CoverageMappingVersion(Version), FuncName, FuncHash, Mapping,
386           FilenamesBegin, Filenames.size() - FilenamesBegin));
387     }
388   }
389 
390   return std::error_code();
391 }
392 
393 static const char *TestingFormatMagic = "llvmcovmtestdata";
394 
loadTestingFormat(StringRef Data,InstrProfSymtab & ProfileNames,StringRef & CoverageMapping,uint8_t & BytesInAddress,support::endianness & Endian)395 static std::error_code loadTestingFormat(StringRef Data,
396                                          InstrProfSymtab &ProfileNames,
397                                          StringRef &CoverageMapping,
398                                          uint8_t &BytesInAddress,
399                                          support::endianness &Endian) {
400   BytesInAddress = 8;
401   Endian = support::endianness::little;
402 
403   Data = Data.substr(StringRef(TestingFormatMagic).size());
404   if (Data.size() < 1)
405     return coveragemap_error::truncated;
406   unsigned N = 0;
407   auto ProfileNamesSize =
408       decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
409   if (N > Data.size())
410     return coveragemap_error::malformed;
411   Data = Data.substr(N);
412   if (Data.size() < 1)
413     return coveragemap_error::truncated;
414   N = 0;
415   uint64_t Address =
416       decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
417   if (N > Data.size())
418     return coveragemap_error::malformed;
419   Data = Data.substr(N);
420   if (Data.size() < ProfileNamesSize)
421     return coveragemap_error::malformed;
422   ProfileNames.create(Data.substr(0, ProfileNamesSize), Address);
423   CoverageMapping = Data.substr(ProfileNamesSize);
424   return std::error_code();
425 }
426 
lookupSection(ObjectFile & OF,StringRef Name)427 static ErrorOr<SectionRef> lookupSection(ObjectFile &OF, StringRef Name) {
428   StringRef FoundName;
429   for (const auto &Section : OF.sections()) {
430     if (auto EC = Section.getName(FoundName))
431       return EC;
432     if (FoundName == Name)
433       return Section;
434   }
435   return coveragemap_error::no_data_found;
436 }
437 
438 static std::error_code
loadBinaryFormat(MemoryBufferRef ObjectBuffer,InstrProfSymtab & ProfileNames,StringRef & CoverageMapping,uint8_t & BytesInAddress,support::endianness & Endian,StringRef Arch)439 loadBinaryFormat(MemoryBufferRef ObjectBuffer, InstrProfSymtab &ProfileNames,
440                  StringRef &CoverageMapping, uint8_t &BytesInAddress,
441                  support::endianness &Endian, StringRef Arch) {
442   auto BinOrErr = object::createBinary(ObjectBuffer);
443   if (std::error_code EC = BinOrErr.getError())
444     return EC;
445   auto Bin = std::move(BinOrErr.get());
446   std::unique_ptr<ObjectFile> OF;
447   if (auto *Universal = dyn_cast<object::MachOUniversalBinary>(Bin.get())) {
448     // If we have a universal binary, try to look up the object for the
449     // appropriate architecture.
450     auto ObjectFileOrErr = Universal->getObjectForArch(Arch);
451     if (std::error_code EC = ObjectFileOrErr.getError())
452       return EC;
453     OF = std::move(ObjectFileOrErr.get());
454   } else if (isa<object::ObjectFile>(Bin.get())) {
455     // For any other object file, upcast and take ownership.
456     OF.reset(cast<object::ObjectFile>(Bin.release()));
457     // If we've asked for a particular arch, make sure they match.
458     if (!Arch.empty() && OF->getArch() != Triple(Arch).getArch())
459       return object_error::arch_not_found;
460   } else
461     // We can only handle object files.
462     return coveragemap_error::malformed;
463 
464   // The coverage uses native pointer sizes for the object it's written in.
465   BytesInAddress = OF->getBytesInAddress();
466   Endian = OF->isLittleEndian() ? support::endianness::little
467                                 : support::endianness::big;
468 
469   // Look for the sections that we are interested in.
470   auto NamesSection = lookupSection(*OF, getInstrProfNameSectionName(false));
471   if (auto EC = NamesSection.getError())
472     return EC;
473   auto CoverageSection =
474       lookupSection(*OF, getInstrProfCoverageSectionName(false));
475   if (auto EC = CoverageSection.getError())
476     return EC;
477 
478   // Get the contents of the given sections.
479   if (std::error_code EC = CoverageSection->getContents(CoverageMapping))
480     return EC;
481   if (std::error_code EC = ProfileNames.create(*NamesSection))
482     return EC;
483 
484   return std::error_code();
485 }
486 
487 ErrorOr<std::unique_ptr<BinaryCoverageReader>>
create(std::unique_ptr<MemoryBuffer> & ObjectBuffer,StringRef Arch)488 BinaryCoverageReader::create(std::unique_ptr<MemoryBuffer> &ObjectBuffer,
489                              StringRef Arch) {
490   std::unique_ptr<BinaryCoverageReader> Reader(new BinaryCoverageReader());
491 
492   InstrProfSymtab ProfileNames;
493   StringRef Coverage;
494   uint8_t BytesInAddress;
495   support::endianness Endian;
496   std::error_code EC;
497   if (ObjectBuffer->getBuffer().startswith(TestingFormatMagic))
498     // This is a special format used for testing.
499     EC = loadTestingFormat(ObjectBuffer->getBuffer(), ProfileNames, Coverage,
500                            BytesInAddress, Endian);
501   else
502     EC = loadBinaryFormat(ObjectBuffer->getMemBufferRef(), ProfileNames,
503                           Coverage, BytesInAddress, Endian, Arch);
504   if (EC)
505     return EC;
506 
507   if (BytesInAddress == 4 && Endian == support::endianness::little)
508     EC = readCoverageMappingData<uint32_t, support::endianness::little>(
509         ProfileNames, Coverage, Reader->MappingRecords, Reader->Filenames);
510   else if (BytesInAddress == 4 && Endian == support::endianness::big)
511     EC = readCoverageMappingData<uint32_t, support::endianness::big>(
512         ProfileNames, Coverage, Reader->MappingRecords, Reader->Filenames);
513   else if (BytesInAddress == 8 && Endian == support::endianness::little)
514     EC = readCoverageMappingData<uint64_t, support::endianness::little>(
515         ProfileNames, Coverage, Reader->MappingRecords, Reader->Filenames);
516   else if (BytesInAddress == 8 && Endian == support::endianness::big)
517     EC = readCoverageMappingData<uint64_t, support::endianness::big>(
518         ProfileNames, Coverage, Reader->MappingRecords, Reader->Filenames);
519   else
520     return coveragemap_error::malformed;
521   if (EC)
522     return EC;
523   return std::move(Reader);
524 }
525 
526 std::error_code
readNextRecord(CoverageMappingRecord & Record)527 BinaryCoverageReader::readNextRecord(CoverageMappingRecord &Record) {
528   if (CurrentRecord >= MappingRecords.size())
529     return coveragemap_error::eof;
530 
531   FunctionsFilenames.clear();
532   Expressions.clear();
533   MappingRegions.clear();
534   auto &R = MappingRecords[CurrentRecord];
535   RawCoverageMappingReader Reader(
536       R.CoverageMapping,
537       makeArrayRef(Filenames).slice(R.FilenamesBegin, R.FilenamesSize),
538       FunctionsFilenames, Expressions, MappingRegions);
539   if (auto Err = Reader.read())
540     return Err;
541 
542   Record.FunctionName = R.FunctionName;
543   Record.FunctionHash = R.FunctionHash;
544   Record.Filenames = FunctionsFilenames;
545   Record.Expressions = Expressions;
546   Record.MappingRegions = MappingRegions;
547 
548   ++CurrentRecord;
549   return std::error_code();
550 }
551