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/ObjectFile.h"
  18 #include "llvm/Support/Debug.h"
  19 #include "llvm/Support/LEB128.h"
  20
  21 using namespace llvm;
  22 using namespace coverage;
  23 using namespace object;
  24
  25 #define DEBUG_TYPE "coverage-mapping"
  26
  27 void CoverageMappingIterator::increment() {
  28   // Check if all the records were read or if an error occurred while reading
  29   // the next record.
  30   if (Reader->readNextRecord(Record))
  31     *this = CoverageMappingIterator();
  32 }
  33
  34 std::error_code RawCoverageReader::readULEB128(uint64_t &Result) {
  35   if (Data.size() < 1)
  36     return error(instrprof_error::truncated);
  37   unsigned N = 0;
  38   Result = decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
  39   if (N > Data.size())
  40     return error(instrprof_error::malformed);
  41   Data = Data.substr(N);
  42   return success();
  43 }
  44
  45 std::error_code RawCoverageReader::readIntMax(uint64_t &Result,
  46                                               uint64_t MaxPlus1) {
  47   if (auto Err = readULEB128(Result))
  48     return Err;
  49   if (Result >= MaxPlus1)
  50     return error(instrprof_error::malformed);
  51   return success();
  52 }
  53
  54 std::error_code RawCoverageReader::readSize(uint64_t &Result) {
  55   if (auto Err = readULEB128(Result))
  56     return Err;
  57   // Sanity check the number.
  58   if (Result > Data.size())
  59     return error(instrprof_error::malformed);
  60   return success();
  61 }
  62
  63 std::error_code RawCoverageReader::readString(StringRef &Result) {
  64   uint64_t Length;
  65   if (auto Err = readSize(Length))
  66     return Err;
  67   Result = Data.substr(0, Length);
  68   Data = Data.substr(Length);
  69   return success();
  70 }
  71
  72 std::error_code RawCoverageFilenamesReader::read() {
  73   uint64_t NumFilenames;
  74   if (auto Err = readSize(NumFilenames))
  75     return Err;
  76   for (size_t I = 0; I < NumFilenames; ++I) {
  77     StringRef Filename;
  78     if (auto Err = readString(Filename))
  79       return Err;
  80     Filenames.push_back(Filename);
  81   }
  82   return success();
  83 }
  84
  85 std::error_code RawCoverageMappingReader::decodeCounter(unsigned Value,
  86                                                         Counter &C) {
  87   auto Tag = Value & Counter::EncodingTagMask;
  88   switch (Tag) {
  89   case Counter::Zero:
  90     C = Counter::getZero();
  91     return success();
  92   case Counter::CounterValueReference:
  93     C = Counter::getCounter(Value >> Counter::EncodingTagBits);
  94     return success();
  95   default:
  96     break;
  97   }
  98   Tag -= Counter::Expression;
  99   switch (Tag) {
 100   case CounterExpression::Subtract:
 101   case CounterExpression::Add: {
 102     auto ID = Value >> Counter::EncodingTagBits;
 103     if (ID >= Expressions.size())
 104       return error(instrprof_error::malformed);
 105     Expressions[ID].Kind = CounterExpression::ExprKind(Tag);
 106     C = Counter::getExpression(ID);
 107     break;
 108   }
 109   default:
 110     return error(instrprof_error::malformed);
 111   }
 112   return success();
 113 }
 114
 115 std::error_code RawCoverageMappingReader::readCounter(Counter &C) {
 116   uint64_t EncodedCounter;
 117   if (auto Err =
 118           readIntMax(EncodedCounter, std::numeric_limits<unsigned>::max()))
 119     return Err;
 120   if (auto Err = decodeCounter(EncodedCounter, C))
 121     return Err;
 122   return success();
 123 }
 124
 125 static const unsigned EncodingExpansionRegionBit = 1
 126                                                    << Counter::EncodingTagBits;
 127
 128 /// \brief Read the sub-array of regions for the given inferred file id.
 129 /// \param NumFileIDs the number of file ids that are defined for this
 130 /// function.
 131 std::error_code RawCoverageMappingReader::readMappingRegionsSubArray(
 132     std::vector<CounterMappingRegion> &MappingRegions, unsigned InferredFileID,
 133     size_t NumFileIDs) {
 134   uint64_t NumRegions;
 135   if (auto Err = readSize(NumRegions))
 136     return Err;
 137   unsigned LineStart = 0;
 138   for (size_t I = 0; I < NumRegions; ++I) {
 139     Counter C;
 140     CounterMappingRegion::RegionKind Kind = CounterMappingRegion::CodeRegion;
 141
 142     // Read the combined counter + region kind.
 143     uint64_t EncodedCounterAndRegion;
 144     if (auto Err = readIntMax(EncodedCounterAndRegion,
 145                               std::numeric_limits<unsigned>::max()))
 146       return Err;
 147     unsigned Tag = EncodedCounterAndRegion & Counter::EncodingTagMask;
 148     uint64_t ExpandedFileID = 0;
 149     if (Tag != Counter::Zero) {
 150       if (auto Err = decodeCounter(EncodedCounterAndRegion, C))
 151         return Err;
 152     } else {
 153       // Is it an expansion region?
 154       if (EncodedCounterAndRegion & EncodingExpansionRegionBit) {
 155         Kind = CounterMappingRegion::ExpansionRegion;
 156         ExpandedFileID = EncodedCounterAndRegion >>
 157                          Counter::EncodingCounterTagAndExpansionRegionTagBits;
 158         if (ExpandedFileID >= NumFileIDs)
 159           return error(instrprof_error::malformed);
 160       } else {
 161         switch (EncodedCounterAndRegion >>
 162                 Counter::EncodingCounterTagAndExpansionRegionTagBits) {
 163         case CounterMappingRegion::CodeRegion:
 164           // Don't do anything when we have a code region with a zero counter.
 165           break;
 166         case CounterMappingRegion::SkippedRegion:
 167           Kind = CounterMappingRegion::SkippedRegion;
 168           break;
 169         default:
 170           return error(instrprof_error::malformed);
 171         }
 172       }
 173     }
 174
 175     // Read the source range.
 176     uint64_t LineStartDelta, CodeBeforeColumnStart, NumLines, ColumnEnd;
 177     if (auto Err =
 178             readIntMax(LineStartDelta, std::numeric_limits<unsigned>::max()))
 179       return Err;
 180     if (auto Err = readULEB128(CodeBeforeColumnStart))
 181       return Err;
 182     bool HasCodeBefore = CodeBeforeColumnStart & 1;
 183     uint64_t ColumnStart = CodeBeforeColumnStart >>
 184                            CounterMappingRegion::EncodingHasCodeBeforeBits;
 185     if (ColumnStart > std::numeric_limits<unsigned>::max())
 186       return error(instrprof_error::malformed);
 187     if (auto Err = readIntMax(NumLines, std::numeric_limits<unsigned>::max()))
 188       return Err;
 189     if (auto Err = readIntMax(ColumnEnd, std::numeric_limits<unsigned>::max()))
 190       return Err;
 191     LineStart += LineStartDelta;
 192     // Adjust the column locations for the empty regions that are supposed to
 193     // cover whole lines. Those regions should be encoded with the
 194     // column range (1 -> std::numeric_limits<unsigned>::max()), but because
 195     // the encoded std::numeric_limits<unsigned>::max() is several bytes long,
 196     // we set the column range to (0 -> 0) to ensure that the column start and
 197     // column end take up one byte each.
 198     // The std::numeric_limits<unsigned>::max() is used to represent a column
 199     // position at the end of the line without knowing the length of that line.
 200     if (ColumnStart == 0 && ColumnEnd == 0) {
 201       ColumnStart = 1;
 202       ColumnEnd = std::numeric_limits<unsigned>::max();
 203     }
 204
 205     DEBUG({
 206       dbgs() << "Counter in file " << InferredFileID << " " << LineStart << ":"
 207              << ColumnStart << " -> " << (LineStart + NumLines) << ":"
 208              << ColumnEnd << ", ";
 209       if (Kind == CounterMappingRegion::ExpansionRegion)
 210         dbgs() << "Expands to file " << ExpandedFileID;
 211       else
 212         CounterMappingContext(Expressions).dump(C, dbgs());
 213       dbgs() << "\n";
 214     });
 215
 216     MappingRegions.push_back(CounterMappingRegion(
 217         C, InferredFileID, LineStart, ColumnStart, LineStart + NumLines,
 218         ColumnEnd, HasCodeBefore, Kind));
 219     MappingRegions.back().ExpandedFileID = ExpandedFileID;
 220   }
 221   return success();
 222 }
 223
 224 std::error_code RawCoverageMappingReader::read(CoverageMappingRecord &Record) {
 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   Record.FunctionName = FunctionName;
 291   Record.Filenames = Filenames;
 292   Record.Expressions = Expressions;
 293   Record.MappingRegions = MappingRegions;
 294   return success();
 295 }
 296
 297 ObjectFileCoverageMappingReader::ObjectFileCoverageMappingReader(
 298     StringRef FileName)
 299     : CurrentRecord(0) {
 300   auto File = llvm::object::ObjectFile::createObjectFile(FileName);
 301   if (!File)
 302     error(File.getError());
 303   else
 304     Object = std::move(File.get());
 305 }
 306
 307 namespace {
 308 /// \brief The coverage mapping data for a single function.
 309 /// It points to the function's name.
 310 template <typename IntPtrT> struct CoverageMappingFunctionRecord {
 311   IntPtrT FunctionNamePtr;
 312   uint32_t FunctionNameSize;
 313   uint32_t CoverageMappingSize;
 314   uint64_t FunctionHash;
 315 };
 316
 317 /// \brief The coverage mapping data for a single translation unit.
 318 /// It points to the array of function coverage mapping records and the encoded
 319 /// filenames array.
 320 template <typename IntPtrT> struct CoverageMappingTURecord {
 321   uint32_t FunctionRecordsSize;
 322   uint32_t FilenamesSize;
 323   uint32_t CoverageMappingsSize;
 324   uint32_t Version;
 325 };
 326
 327 /// \brief A helper structure to access the data from a section
 328 /// in an object file.
 329 struct SectionData {
 330   StringRef Data;
 331   uint64_t Address;
 332
 333   std::error_code load(SectionRef &Section) {
 334     if (auto Err = Section.getContents(Data))
 335       return Err;
 336     return Section.getAddress(Address);
 337   }
 338
 339   std::error_code get(uint64_t Pointer, size_t Size, StringRef &Result) {
 340     if (Pointer < Address)
 341       return instrprof_error::malformed;
 342     auto Offset = Pointer - Address;
 343     if (Offset + Size > Data.size())
 344       return instrprof_error::malformed;
 345     Result = Data.substr(Pointer - Address, Size);
 346     return instrprof_error::success;
 347   }
 348 };
 349 }
 350
 351 template <typename T>
 352 std::error_code readCoverageMappingData(
 353     SectionData &ProfileNames, StringRef Data,
 354     std::vector<ObjectFileCoverageMappingReader::ProfileMappingRecord> &Records,
 355     std::vector<StringRef> &Filenames) {
 356   llvm::DenseSet<T> UniqueFunctionMappingData;
 357
 358   // Read the records in the coverage data section.
 359   while (!Data.empty()) {
 360     if (Data.size() < sizeof(CoverageMappingTURecord<T>))
 361       return instrprof_error::malformed;
 362     auto TU = reinterpret_cast<const CoverageMappingTURecord<T> *>(Data.data());
 363     Data = Data.substr(sizeof(CoverageMappingTURecord<T>));
 364     switch (TU->Version) {
 365     case CoverageMappingVersion1:
 366       break;
 367     default:
 368       return instrprof_error::unsupported_version;
 369     }
 370     auto Version = CoverageMappingVersion(TU->Version);
 371
 372     // Get the function records.
 373     auto FunctionRecords =
 374         reinterpret_cast<const CoverageMappingFunctionRecord<T> *>(Data.data());
 375     if (Data.size() <
 376         sizeof(CoverageMappingFunctionRecord<T>) * TU->FunctionRecordsSize)
 377       return instrprof_error::malformed;
 378     Data = Data.substr(sizeof(CoverageMappingFunctionRecord<T>) *
 379                        TU->FunctionRecordsSize);
 380
 381     // Get the filenames.
 382     if (Data.size() < TU->FilenamesSize)
 383       return instrprof_error::malformed;
 384     auto RawFilenames = Data.substr(0, TU->FilenamesSize);
 385     Data = Data.substr(TU->FilenamesSize);
 386     size_t FilenamesBegin = Filenames.size();
 387     RawCoverageFilenamesReader Reader(RawFilenames, Filenames);
 388     if (auto Err = Reader.read())
 389       return Err;
 390
 391     // Get the coverage mappings.
 392     if (Data.size() < TU->CoverageMappingsSize)
 393       return instrprof_error::malformed;
 394     auto CoverageMappings = Data.substr(0, TU->CoverageMappingsSize);
 395     Data = Data.substr(TU->CoverageMappingsSize);
 396
 397     for (unsigned I = 0; I < TU->FunctionRecordsSize; ++I) {
 398       auto &MappingRecord = FunctionRecords[I];
 399
 400       // Get the coverage mapping.
 401       if (CoverageMappings.size() < MappingRecord.CoverageMappingSize)
 402         return instrprof_error::malformed;
 403       auto Mapping =
 404           CoverageMappings.substr(0, MappingRecord.CoverageMappingSize);
 405       CoverageMappings =
 406           CoverageMappings.substr(MappingRecord.CoverageMappingSize);
 407
 408       // Ignore this record if we already have a record that points to the same
 409       // function name.
 410       // This is useful to ignore the redundant records for the functions
 411       // with ODR linkage.
 412       if (UniqueFunctionMappingData.count(MappingRecord.FunctionNamePtr))
 413         continue;
 414       UniqueFunctionMappingData.insert(MappingRecord.FunctionNamePtr);
 415       StringRef FunctionName;
 416       if (auto Err =
 417               ProfileNames.get(MappingRecord.FunctionNamePtr,
 418                                MappingRecord.FunctionNameSize, FunctionName))
 419         return Err;
 420       Records.push_back(ObjectFileCoverageMappingReader::ProfileMappingRecord(
 421           Version, FunctionName, MappingRecord.FunctionHash, Mapping,
 422           FilenamesBegin, Filenames.size() - FilenamesBegin));
 423     }
 424   }
 425
 426   return instrprof_error::success;
 427 }
 428
 429 static const char *TestingFormatMagic = "llvmcovmtestdata";
 430
 431 static std::error_code decodeTestingFormat(StringRef Data,
 432                                            SectionData &ProfileNames,
 433                                            StringRef &CoverageMapping) {
 434   Data = Data.substr(StringRef(TestingFormatMagic).size());
 435   if (Data.size() < 1)
 436     return instrprof_error::truncated;
 437   unsigned N = 0;
 438   auto ProfileNamesSize =
 439       decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
 440   if (N > Data.size())
 441     return instrprof_error::malformed;
 442   Data = Data.substr(N);
 443   if (Data.size() < 1)
 444     return instrprof_error::truncated;
 445   N = 0;
 446   ProfileNames.Address =
 447       decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
 448   if (N > Data.size())
 449     return instrprof_error::malformed;
 450   Data = Data.substr(N);
 451   if (Data.size() < ProfileNamesSize)
 452     return instrprof_error::malformed;
 453   ProfileNames.Data = Data.substr(0, ProfileNamesSize);
 454   CoverageMapping = Data.substr(ProfileNamesSize);
 455   return instrprof_error::success;
 456 }
 457
 458 ObjectFileCoverageMappingReader::ObjectFileCoverageMappingReader(
 459     std::unique_ptr<MemoryBuffer> &ObjectBuffer, sys::fs::file_magic Type)
 460     : CurrentRecord(0) {
 461   if (ObjectBuffer->getBuffer().startswith(TestingFormatMagic)) {
 462     // This is a special format used for testing.
 463     SectionData ProfileNames;
 464     StringRef CoverageMapping;
 465     if (auto Err = decodeTestingFormat(ObjectBuffer->getBuffer(), ProfileNames,
 466                                        CoverageMapping)) {
 467       error(Err);
 468       return;
 469     }
 470     error(readCoverageMappingData<uint64_t>(ProfileNames, CoverageMapping,
 471                                             MappingRecords, Filenames));
 472     Object = OwningBinary<ObjectFile>(std::unique_ptr<ObjectFile>(),
 473                                       std::move(ObjectBuffer));
 474     return;
 475   }
 476
 477   auto File = object::ObjectFile::createObjectFile(
 478       ObjectBuffer->getMemBufferRef(), Type);
 479   if (!File)
 480     error(File.getError());
 481   else
 482     Object = OwningBinary<ObjectFile>(std::move(File.get()),
 483                                       std::move(ObjectBuffer));
 484 }
 485
 486 std::error_code ObjectFileCoverageMappingReader::readHeader() {
 487   ObjectFile *OF = Object.getBinary().get();
 488   if (!OF)
 489     return getError();
 490   auto BytesInAddress = OF->getBytesInAddress();
 491   if (BytesInAddress != 4 && BytesInAddress != 8)
 492     return error(instrprof_error::malformed);
 493
 494   // Look for the sections that we are interested in.
 495   int FoundSectionCount = 0;
 496   SectionRef ProfileNames, CoverageMapping;
 497   for (const auto &Section : OF->sections()) {
 498     StringRef Name;
 499     if (auto Err = Section.getName(Name))
 500       return Err;
 501     if (Name == "__llvm_prf_names") {
 502       ProfileNames = Section;
 503     } else if (Name == "__llvm_covmap") {
 504       CoverageMapping = Section;
 505     } else
 506       continue;
 507     ++FoundSectionCount;
 508   }
 509   if (FoundSectionCount != 2)
 510     return error(instrprof_error::bad_header);
 511
 512   // Get the contents of the given sections.
 513   StringRef Data;
 514   if (auto Err = CoverageMapping.getContents(Data))
 515     return Err;
 516   SectionData ProfileNamesData;
 517   if (auto Err = ProfileNamesData.load(ProfileNames))
 518     return Err;
 519
 520   // Load the data from the found sections.
 521   std::error_code Err;
 522   if (BytesInAddress == 4)
 523     Err = readCoverageMappingData<uint32_t>(ProfileNamesData, Data,
 524                                             MappingRecords, Filenames);
 525   else
 526     Err = readCoverageMappingData<uint64_t>(ProfileNamesData, Data,
 527                                             MappingRecords, Filenames);
 528   if (Err)
 529     return error(Err);
 530
 531   return success();
 532 }
 533
 534 std::error_code
 535 ObjectFileCoverageMappingReader::readNextRecord(CoverageMappingRecord &Record) {
 536   if (CurrentRecord >= MappingRecords.size())
 537     return error(instrprof_error::eof);
 538
 539   FunctionsFilenames.clear();
 540   Expressions.clear();
 541   MappingRegions.clear();
 542   auto &R = MappingRecords[CurrentRecord];
 543   RawCoverageMappingReader Reader(
 544       R.FunctionName, R.CoverageMapping,
 545       makeArrayRef(Filenames.data() + R.FilenamesBegin, R.FilenamesSize),
 546       FunctionsFilenames, Expressions, MappingRegions);
 547   if (auto Err = Reader.read(Record))
 548     return Err;
 549   Record.FunctionHash = R.FunctionHash;
 550   ++CurrentRecord;
 551   return success();
 552 }