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