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