lib/ProfileData/CoverageMappingReader.cpp

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