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
25using namespace llvm;
26using namespace coverage;
27using namespace object;
28
29#define DEBUG_TYPE "coverage-mapping"
30
31void 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
38std::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
49std::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
58std::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
67std::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
76std::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
89std::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
119std::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
129static 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.
135std::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
224std::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
293std::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
300StringRef 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
309template <typename T, support::endianness Endian>
310static 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 + sizeof(CovMapHeader) > End)
320      return coveragemap_error::malformed;
321    auto CovHeader = reinterpret_cast<const coverage::CovMapHeader *>(Buf);
322    uint32_t NRecords = CovHeader->getNRecords<Endian>();
323    uint32_t FilenamesSize = CovHeader->getFilenamesSize<Endian>();
324    uint32_t CoverageSize = CovHeader->getCoverageSize<Endian>();
325    uint32_t Version = CovHeader->getVersion<Endian>();
326    Buf = reinterpret_cast<const char *>(++CovHeader);
327
328    if (Version > coverage::CoverageMappingCurrentVersion)
329      return coveragemap_error::unsupported_version;
330
331    // Skip past the function records, saving the start and end for later.
332    const char *FunBuf = Buf;
333    Buf += NRecords * sizeof(coverage::CovMapFunctionRecord<T>);
334    const char *FunEnd = Buf;
335
336    // Get the filenames.
337    if (Buf + FilenamesSize > End)
338      return coveragemap_error::malformed;
339    size_t FilenamesBegin = Filenames.size();
340    RawCoverageFilenamesReader Reader(StringRef(Buf, FilenamesSize), Filenames);
341    if (auto Err = Reader.read())
342      return Err;
343    Buf += FilenamesSize;
344
345    // We'll read the coverage mapping records in the loop below.
346    const char *CovBuf = Buf;
347    Buf += CoverageSize;
348    const char *CovEnd = Buf;
349
350    if (Buf > End)
351      return coveragemap_error::malformed;
352    // Each coverage map has an alignment of 8, so we need to adjust alignment
353    // before reading the next map.
354    Buf += alignmentAdjustment(Buf, 8);
355
356    auto CFR =
357        reinterpret_cast<const coverage::CovMapFunctionRecord<T> *>(FunBuf);
358    while ((const char *)CFR < FunEnd) {
359      // Read the function information
360      uint32_t DataSize = CFR->template getDataSize<Endian>();
361      uint64_t FuncHash = CFR->template getFuncHash<Endian>();
362
363      // Now use that to read the coverage data.
364      if (CovBuf + DataSize > CovEnd)
365        return coveragemap_error::malformed;
366      auto Mapping = StringRef(CovBuf, DataSize);
367      CovBuf += DataSize;
368
369      // Ignore this record if we already have a record that points to the same
370      // function name. This is useful to ignore the redundant records for the
371      // functions with ODR linkage.
372      T NameRef = CFR->template getFuncNameRef<Endian>();
373      if (!UniqueFunctionMappingData.insert(NameRef).second)
374        continue;
375
376      StringRef FuncName;
377      if (std::error_code EC =
378              CFR->template getFuncName<Endian>(ProfileNames, FuncName))
379        return EC;
380      Records.push_back(BinaryCoverageReader::ProfileMappingRecord(
381          CoverageMappingVersion(Version), FuncName, FuncHash, Mapping,
382          FilenamesBegin, Filenames.size() - FilenamesBegin));
383      CFR++;
384    }
385  }
386
387  return std::error_code();
388}
389
390static const char *TestingFormatMagic = "llvmcovmtestdata";
391
392static std::error_code loadTestingFormat(StringRef Data,
393                                         InstrProfSymtab &ProfileNames,
394                                         StringRef &CoverageMapping,
395                                         uint8_t &BytesInAddress,
396                                         support::endianness &Endian) {
397  BytesInAddress = 8;
398  Endian = support::endianness::little;
399
400  Data = Data.substr(StringRef(TestingFormatMagic).size());
401  if (Data.size() < 1)
402    return coveragemap_error::truncated;
403  unsigned N = 0;
404  auto ProfileNamesSize =
405      decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
406  if (N > Data.size())
407    return coveragemap_error::malformed;
408  Data = Data.substr(N);
409  if (Data.size() < 1)
410    return coveragemap_error::truncated;
411  N = 0;
412  uint64_t Address =
413      decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
414  if (N > Data.size())
415    return coveragemap_error::malformed;
416  Data = Data.substr(N);
417  if (Data.size() < ProfileNamesSize)
418    return coveragemap_error::malformed;
419  ProfileNames.create(Data.substr(0, ProfileNamesSize), Address);
420  CoverageMapping = Data.substr(ProfileNamesSize);
421  return std::error_code();
422}
423
424static ErrorOr<SectionRef> lookupSection(ObjectFile &OF, StringRef Name) {
425  StringRef FoundName;
426  for (const auto &Section : OF.sections()) {
427    if (auto EC = Section.getName(FoundName))
428      return EC;
429    if (FoundName == Name)
430      return Section;
431  }
432  return coveragemap_error::no_data_found;
433}
434
435static std::error_code
436loadBinaryFormat(MemoryBufferRef ObjectBuffer, InstrProfSymtab &ProfileNames,
437                 StringRef &CoverageMapping, uint8_t &BytesInAddress,
438                 support::endianness &Endian, StringRef Arch) {
439  auto BinOrErr = object::createBinary(ObjectBuffer);
440  if (std::error_code EC = BinOrErr.getError())
441    return EC;
442  auto Bin = std::move(BinOrErr.get());
443  std::unique_ptr<ObjectFile> OF;
444  if (auto *Universal = dyn_cast<object::MachOUniversalBinary>(Bin.get())) {
445    // If we have a universal binary, try to look up the object for the
446    // appropriate architecture.
447    auto ObjectFileOrErr = Universal->getObjectForArch(Arch);
448    if (std::error_code EC = ObjectFileOrErr.getError())
449      return EC;
450    OF = std::move(ObjectFileOrErr.get());
451  } else if (isa<object::ObjectFile>(Bin.get())) {
452    // For any other object file, upcast and take ownership.
453    OF.reset(cast<object::ObjectFile>(Bin.release()));
454    // If we've asked for a particular arch, make sure they match.
455    if (!Arch.empty() && OF->getArch() != Triple(Arch).getArch())
456      return object_error::arch_not_found;
457  } else
458    // We can only handle object files.
459    return coveragemap_error::malformed;
460
461  // The coverage uses native pointer sizes for the object it's written in.
462  BytesInAddress = OF->getBytesInAddress();
463  Endian = OF->isLittleEndian() ? support::endianness::little
464                                : support::endianness::big;
465
466  // Look for the sections that we are interested in.
467  auto NamesSection = lookupSection(*OF, getInstrProfNameSectionName(false));
468  if (auto EC = NamesSection.getError())
469    return EC;
470  auto CoverageSection =
471      lookupSection(*OF, getInstrProfCoverageSectionName(false));
472  if (auto EC = CoverageSection.getError())
473    return EC;
474
475  // Get the contents of the given sections.
476  if (std::error_code EC = CoverageSection->getContents(CoverageMapping))
477    return EC;
478  if (std::error_code EC = ProfileNames.create(*NamesSection))
479    return EC;
480
481  return std::error_code();
482}
483
484ErrorOr<std::unique_ptr<BinaryCoverageReader>>
485BinaryCoverageReader::create(std::unique_ptr<MemoryBuffer> &ObjectBuffer,
486                             StringRef Arch) {
487  std::unique_ptr<BinaryCoverageReader> Reader(new BinaryCoverageReader());
488
489  InstrProfSymtab ProfileNames;
490  StringRef Coverage;
491  uint8_t BytesInAddress;
492  support::endianness Endian;
493  std::error_code EC;
494  if (ObjectBuffer->getBuffer().startswith(TestingFormatMagic))
495    // This is a special format used for testing.
496    EC = loadTestingFormat(ObjectBuffer->getBuffer(), ProfileNames, Coverage,
497                           BytesInAddress, Endian);
498  else
499    EC = loadBinaryFormat(ObjectBuffer->getMemBufferRef(), ProfileNames,
500                          Coverage, BytesInAddress, Endian, Arch);
501  if (EC)
502    return EC;
503
504  if (BytesInAddress == 4 && Endian == support::endianness::little)
505    EC = readCoverageMappingData<uint32_t, support::endianness::little>(
506        ProfileNames, Coverage, Reader->MappingRecords, Reader->Filenames);
507  else if (BytesInAddress == 4 && Endian == support::endianness::big)
508    EC = readCoverageMappingData<uint32_t, support::endianness::big>(
509        ProfileNames, Coverage, Reader->MappingRecords, Reader->Filenames);
510  else if (BytesInAddress == 8 && Endian == support::endianness::little)
511    EC = readCoverageMappingData<uint64_t, support::endianness::little>(
512        ProfileNames, Coverage, Reader->MappingRecords, Reader->Filenames);
513  else if (BytesInAddress == 8 && Endian == support::endianness::big)
514    EC = readCoverageMappingData<uint64_t, support::endianness::big>(
515        ProfileNames, Coverage, Reader->MappingRecords, Reader->Filenames);
516  else
517    return coveragemap_error::malformed;
518  if (EC)
519    return EC;
520  return std::move(Reader);
521}
522
523std::error_code
524BinaryCoverageReader::readNextRecord(CoverageMappingRecord &Record) {
525  if (CurrentRecord >= MappingRecords.size())
526    return coveragemap_error::eof;
527
528  FunctionsFilenames.clear();
529  Expressions.clear();
530  MappingRegions.clear();
531  auto &R = MappingRecords[CurrentRecord];
532  RawCoverageMappingReader Reader(
533      R.CoverageMapping,
534      makeArrayRef(Filenames).slice(R.FilenamesBegin, R.FilenamesSize),
535      FunctionsFilenames, Expressions, MappingRegions);
536  if (auto Err = Reader.read())
537    return Err;
538
539  Record.FunctionName = R.FunctionName;
540  Record.FunctionHash = R.FunctionHash;
541  Record.Filenames = FunctionsFilenames;
542  Record.Expressions = Expressions;
543  Record.MappingRegions = MappingRegions;
544
545  ++CurrentRecord;
546  return std::error_code();
547}
548