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