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