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