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/Debug.h"
19 #include "llvm/Support/LEB128.h"
20
21 using namespace llvm;
22 using namespace coverage;
23 using namespace object;
24
25 #define DEBUG_TYPE "coverage-mapping"
26
increment()27 void CoverageMappingIterator::increment() {
28 // Check if all the records were read or if an error occurred while reading
29 // the next record.
30 if (Reader->readNextRecord(Record))
31 *this = CoverageMappingIterator();
32 }
33
readULEB128(uint64_t & Result)34 std::error_code RawCoverageReader::readULEB128(uint64_t &Result) {
35 if (Data.size() < 1)
36 return error(instrprof_error::truncated);
37 unsigned N = 0;
38 Result = decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
39 if (N > Data.size())
40 return error(instrprof_error::malformed);
41 Data = Data.substr(N);
42 return success();
43 }
44
readIntMax(uint64_t & Result,uint64_t MaxPlus1)45 std::error_code RawCoverageReader::readIntMax(uint64_t &Result,
46 uint64_t MaxPlus1) {
47 if (auto Err = readULEB128(Result))
48 return Err;
49 if (Result >= MaxPlus1)
50 return error(instrprof_error::malformed);
51 return success();
52 }
53
readSize(uint64_t & Result)54 std::error_code RawCoverageReader::readSize(uint64_t &Result) {
55 if (auto Err = readULEB128(Result))
56 return Err;
57 // Sanity check the number.
58 if (Result > Data.size())
59 return error(instrprof_error::malformed);
60 return success();
61 }
62
readString(StringRef & Result)63 std::error_code RawCoverageReader::readString(StringRef &Result) {
64 uint64_t Length;
65 if (auto Err = readSize(Length))
66 return Err;
67 Result = Data.substr(0, Length);
68 Data = Data.substr(Length);
69 return success();
70 }
71
read()72 std::error_code RawCoverageFilenamesReader::read() {
73 uint64_t NumFilenames;
74 if (auto Err = readSize(NumFilenames))
75 return Err;
76 for (size_t I = 0; I < NumFilenames; ++I) {
77 StringRef Filename;
78 if (auto Err = readString(Filename))
79 return Err;
80 Filenames.push_back(Filename);
81 }
82 return success();
83 }
84
decodeCounter(unsigned Value,Counter & C)85 std::error_code RawCoverageMappingReader::decodeCounter(unsigned Value,
86 Counter &C) {
87 auto Tag = Value & Counter::EncodingTagMask;
88 switch (Tag) {
89 case Counter::Zero:
90 C = Counter::getZero();
91 return success();
92 case Counter::CounterValueReference:
93 C = Counter::getCounter(Value >> Counter::EncodingTagBits);
94 return success();
95 default:
96 break;
97 }
98 Tag -= Counter::Expression;
99 switch (Tag) {
100 case CounterExpression::Subtract:
101 case CounterExpression::Add: {
102 auto ID = Value >> Counter::EncodingTagBits;
103 if (ID >= Expressions.size())
104 return error(instrprof_error::malformed);
105 Expressions[ID].Kind = CounterExpression::ExprKind(Tag);
106 C = Counter::getExpression(ID);
107 break;
108 }
109 default:
110 return error(instrprof_error::malformed);
111 }
112 return success();
113 }
114
readCounter(Counter & C)115 std::error_code RawCoverageMappingReader::readCounter(Counter &C) {
116 uint64_t EncodedCounter;
117 if (auto Err =
118 readIntMax(EncodedCounter, std::numeric_limits<unsigned>::max()))
119 return Err;
120 if (auto Err = decodeCounter(EncodedCounter, C))
121 return Err;
122 return success();
123 }
124
125 static const unsigned EncodingExpansionRegionBit = 1
126 << Counter::EncodingTagBits;
127
128 /// \brief Read the sub-array of regions for the given inferred file id.
129 /// \param NumFileIDs the number of file ids that are defined for this
130 /// function.
readMappingRegionsSubArray(std::vector<CounterMappingRegion> & MappingRegions,unsigned InferredFileID,size_t NumFileIDs)131 std::error_code RawCoverageMappingReader::readMappingRegionsSubArray(
132 std::vector<CounterMappingRegion> &MappingRegions, unsigned InferredFileID,
133 size_t NumFileIDs) {
134 uint64_t NumRegions;
135 if (auto Err = readSize(NumRegions))
136 return Err;
137 unsigned LineStart = 0;
138 for (size_t I = 0; I < NumRegions; ++I) {
139 Counter C;
140 CounterMappingRegion::RegionKind Kind = CounterMappingRegion::CodeRegion;
141
142 // Read the combined counter + region kind.
143 uint64_t EncodedCounterAndRegion;
144 if (auto Err = readIntMax(EncodedCounterAndRegion,
145 std::numeric_limits<unsigned>::max()))
146 return Err;
147 unsigned Tag = EncodedCounterAndRegion & Counter::EncodingTagMask;
148 uint64_t ExpandedFileID = 0;
149 if (Tag != Counter::Zero) {
150 if (auto Err = decodeCounter(EncodedCounterAndRegion, C))
151 return Err;
152 } else {
153 // Is it an expansion region?
154 if (EncodedCounterAndRegion & EncodingExpansionRegionBit) {
155 Kind = CounterMappingRegion::ExpansionRegion;
156 ExpandedFileID = EncodedCounterAndRegion >>
157 Counter::EncodingCounterTagAndExpansionRegionTagBits;
158 if (ExpandedFileID >= NumFileIDs)
159 return error(instrprof_error::malformed);
160 } else {
161 switch (EncodedCounterAndRegion >>
162 Counter::EncodingCounterTagAndExpansionRegionTagBits) {
163 case CounterMappingRegion::CodeRegion:
164 // Don't do anything when we have a code region with a zero counter.
165 break;
166 case CounterMappingRegion::SkippedRegion:
167 Kind = CounterMappingRegion::SkippedRegion;
168 break;
169 default:
170 return error(instrprof_error::malformed);
171 }
172 }
173 }
174
175 // Read the source range.
176 uint64_t LineStartDelta, CodeBeforeColumnStart, NumLines, ColumnEnd;
177 if (auto Err =
178 readIntMax(LineStartDelta, std::numeric_limits<unsigned>::max()))
179 return Err;
180 if (auto Err = readULEB128(CodeBeforeColumnStart))
181 return Err;
182 bool HasCodeBefore = CodeBeforeColumnStart & 1;
183 uint64_t ColumnStart = CodeBeforeColumnStart >>
184 CounterMappingRegion::EncodingHasCodeBeforeBits;
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, LineStart, ColumnStart, LineStart + NumLines,
218 ColumnEnd, HasCodeBefore, Kind));
219 MappingRegions.back().ExpandedFileID = ExpandedFileID;
220 }
221 return success();
222 }
223
read(CoverageMappingRecord & Record)224 std::error_code RawCoverageMappingReader::read(CoverageMappingRecord &Record) {
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 Record.FunctionName = FunctionName;
291 Record.Filenames = Filenames;
292 Record.Expressions = Expressions;
293 Record.MappingRegions = MappingRegions;
294 return success();
295 }
296
ObjectFileCoverageMappingReader(StringRef FileName)297 ObjectFileCoverageMappingReader::ObjectFileCoverageMappingReader(
298 StringRef FileName)
299 : CurrentRecord(0) {
300 auto File = llvm::object::ObjectFile::createObjectFile(FileName);
301 if (!File)
302 error(File.getError());
303 else
304 Object = std::move(File.get());
305 }
306
307 namespace {
308 /// \brief The coverage mapping data for a single function.
309 /// It points to the function's name.
310 template <typename IntPtrT> struct CoverageMappingFunctionRecord {
311 IntPtrT FunctionNamePtr;
312 uint32_t FunctionNameSize;
313 uint32_t CoverageMappingSize;
314 uint64_t FunctionHash;
315 };
316
317 /// \brief The coverage mapping data for a single translation unit.
318 /// It points to the array of function coverage mapping records and the encoded
319 /// filenames array.
320 template <typename IntPtrT> struct CoverageMappingTURecord {
321 uint32_t FunctionRecordsSize;
322 uint32_t FilenamesSize;
323 uint32_t CoverageMappingsSize;
324 uint32_t Version;
325 };
326
327 /// \brief A helper structure to access the data from a section
328 /// in an object file.
329 struct SectionData {
330 StringRef Data;
331 uint64_t Address;
332
load__anon2b1c99600111::SectionData333 std::error_code load(SectionRef &Section) {
334 if (auto Err = Section.getContents(Data))
335 return Err;
336 Address = Section.getAddress();
337 return instrprof_error::success;
338 }
339
get__anon2b1c99600111::SectionData340 std::error_code get(uint64_t Pointer, size_t Size, StringRef &Result) {
341 if (Pointer < Address)
342 return instrprof_error::malformed;
343 auto Offset = Pointer - Address;
344 if (Offset + Size > Data.size())
345 return instrprof_error::malformed;
346 Result = Data.substr(Pointer - Address, Size);
347 return instrprof_error::success;
348 }
349 };
350 }
351
352 template <typename T>
readCoverageMappingData(SectionData & ProfileNames,StringRef Data,std::vector<ObjectFileCoverageMappingReader::ProfileMappingRecord> & Records,std::vector<StringRef> & Filenames)353 std::error_code readCoverageMappingData(
354 SectionData &ProfileNames, StringRef Data,
355 std::vector<ObjectFileCoverageMappingReader::ProfileMappingRecord> &Records,
356 std::vector<StringRef> &Filenames) {
357 llvm::DenseSet<T> UniqueFunctionMappingData;
358
359 // Read the records in the coverage data section.
360 while (!Data.empty()) {
361 if (Data.size() < sizeof(CoverageMappingTURecord<T>))
362 return instrprof_error::malformed;
363 auto TU = reinterpret_cast<const CoverageMappingTURecord<T> *>(Data.data());
364 Data = Data.substr(sizeof(CoverageMappingTURecord<T>));
365 switch (TU->Version) {
366 case CoverageMappingVersion1:
367 break;
368 default:
369 return instrprof_error::unsupported_version;
370 }
371 auto Version = CoverageMappingVersion(TU->Version);
372
373 // Get the function records.
374 auto FunctionRecords =
375 reinterpret_cast<const CoverageMappingFunctionRecord<T> *>(Data.data());
376 if (Data.size() <
377 sizeof(CoverageMappingFunctionRecord<T>) * TU->FunctionRecordsSize)
378 return instrprof_error::malformed;
379 Data = Data.substr(sizeof(CoverageMappingFunctionRecord<T>) *
380 TU->FunctionRecordsSize);
381
382 // Get the filenames.
383 if (Data.size() < TU->FilenamesSize)
384 return instrprof_error::malformed;
385 auto RawFilenames = Data.substr(0, TU->FilenamesSize);
386 Data = Data.substr(TU->FilenamesSize);
387 size_t FilenamesBegin = Filenames.size();
388 RawCoverageFilenamesReader Reader(RawFilenames, Filenames);
389 if (auto Err = Reader.read())
390 return Err;
391
392 // Get the coverage mappings.
393 if (Data.size() < TU->CoverageMappingsSize)
394 return instrprof_error::malformed;
395 auto CoverageMappings = Data.substr(0, TU->CoverageMappingsSize);
396 Data = Data.substr(TU->CoverageMappingsSize);
397
398 for (unsigned I = 0; I < TU->FunctionRecordsSize; ++I) {
399 auto &MappingRecord = FunctionRecords[I];
400
401 // Get the coverage mapping.
402 if (CoverageMappings.size() < MappingRecord.CoverageMappingSize)
403 return instrprof_error::malformed;
404 auto Mapping =
405 CoverageMappings.substr(0, MappingRecord.CoverageMappingSize);
406 CoverageMappings =
407 CoverageMappings.substr(MappingRecord.CoverageMappingSize);
408
409 // Ignore this record if we already have a record that points to the same
410 // function name.
411 // This is useful to ignore the redundant records for the functions
412 // with ODR linkage.
413 if (!UniqueFunctionMappingData.insert(MappingRecord.FunctionNamePtr)
414 .second)
415 continue;
416 StringRef FunctionName;
417 if (auto Err =
418 ProfileNames.get(MappingRecord.FunctionNamePtr,
419 MappingRecord.FunctionNameSize, FunctionName))
420 return Err;
421 Records.push_back(ObjectFileCoverageMappingReader::ProfileMappingRecord(
422 Version, FunctionName, MappingRecord.FunctionHash, Mapping,
423 FilenamesBegin, Filenames.size() - FilenamesBegin));
424 }
425 }
426
427 return instrprof_error::success;
428 }
429
430 static const char *TestingFormatMagic = "llvmcovmtestdata";
431
decodeTestingFormat(StringRef Data,SectionData & ProfileNames,StringRef & CoverageMapping)432 static std::error_code decodeTestingFormat(StringRef Data,
433 SectionData &ProfileNames,
434 StringRef &CoverageMapping) {
435 Data = Data.substr(StringRef(TestingFormatMagic).size());
436 if (Data.size() < 1)
437 return instrprof_error::truncated;
438 unsigned N = 0;
439 auto ProfileNamesSize =
440 decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
441 if (N > Data.size())
442 return instrprof_error::malformed;
443 Data = Data.substr(N);
444 if (Data.size() < 1)
445 return instrprof_error::truncated;
446 N = 0;
447 ProfileNames.Address =
448 decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
449 if (N > Data.size())
450 return instrprof_error::malformed;
451 Data = Data.substr(N);
452 if (Data.size() < ProfileNamesSize)
453 return instrprof_error::malformed;
454 ProfileNames.Data = Data.substr(0, ProfileNamesSize);
455 CoverageMapping = Data.substr(ProfileNamesSize);
456 return instrprof_error::success;
457 }
458
ObjectFileCoverageMappingReader(std::unique_ptr<MemoryBuffer> & ObjectBuffer,sys::fs::file_magic Type)459 ObjectFileCoverageMappingReader::ObjectFileCoverageMappingReader(
460 std::unique_ptr<MemoryBuffer> &ObjectBuffer, sys::fs::file_magic Type)
461 : CurrentRecord(0) {
462 if (ObjectBuffer->getBuffer().startswith(TestingFormatMagic)) {
463 // This is a special format used for testing.
464 SectionData ProfileNames;
465 StringRef CoverageMapping;
466 if (auto Err = decodeTestingFormat(ObjectBuffer->getBuffer(), ProfileNames,
467 CoverageMapping)) {
468 error(Err);
469 return;
470 }
471 error(readCoverageMappingData<uint64_t>(ProfileNames, CoverageMapping,
472 MappingRecords, Filenames));
473 Object = OwningBinary<ObjectFile>(std::unique_ptr<ObjectFile>(),
474 std::move(ObjectBuffer));
475 return;
476 }
477
478 auto File = object::ObjectFile::createObjectFile(
479 ObjectBuffer->getMemBufferRef(), Type);
480 if (!File)
481 error(File.getError());
482 else
483 Object = OwningBinary<ObjectFile>(std::move(File.get()),
484 std::move(ObjectBuffer));
485 }
486
readHeader()487 std::error_code ObjectFileCoverageMappingReader::readHeader() {
488 const ObjectFile *OF = Object.getBinary();
489 if (!OF)
490 return getError();
491 auto BytesInAddress = OF->getBytesInAddress();
492 if (BytesInAddress != 4 && BytesInAddress != 8)
493 return error(instrprof_error::malformed);
494
495 // Look for the sections that we are interested in.
496 int FoundSectionCount = 0;
497 SectionRef ProfileNames, CoverageMapping;
498 for (const auto &Section : OF->sections()) {
499 StringRef Name;
500 if (auto Err = Section.getName(Name))
501 return Err;
502 if (Name == "__llvm_prf_names") {
503 ProfileNames = Section;
504 } else if (Name == "__llvm_covmap") {
505 CoverageMapping = Section;
506 } else
507 continue;
508 ++FoundSectionCount;
509 }
510 if (FoundSectionCount != 2)
511 return error(instrprof_error::bad_header);
512
513 // Get the contents of the given sections.
514 StringRef Data;
515 if (auto Err = CoverageMapping.getContents(Data))
516 return Err;
517 SectionData ProfileNamesData;
518 if (auto Err = ProfileNamesData.load(ProfileNames))
519 return Err;
520
521 // Load the data from the found sections.
522 std::error_code Err;
523 if (BytesInAddress == 4)
524 Err = readCoverageMappingData<uint32_t>(ProfileNamesData, Data,
525 MappingRecords, Filenames);
526 else
527 Err = readCoverageMappingData<uint64_t>(ProfileNamesData, Data,
528 MappingRecords, Filenames);
529 if (Err)
530 return error(Err);
531
532 return success();
533 }
534
535 std::error_code
readNextRecord(CoverageMappingRecord & Record)536 ObjectFileCoverageMappingReader::readNextRecord(CoverageMappingRecord &Record) {
537 if (CurrentRecord >= MappingRecords.size())
538 return error(instrprof_error::eof);
539
540 FunctionsFilenames.clear();
541 Expressions.clear();
542 MappingRegions.clear();
543 auto &R = MappingRecords[CurrentRecord];
544 RawCoverageMappingReader Reader(
545 R.FunctionName, R.CoverageMapping,
546 makeArrayRef(Filenames.data() + R.FilenamesBegin, R.FilenamesSize),
547 FunctionsFilenames, Expressions, MappingRegions);
548 if (auto Err = Reader.read(Record))
549 return Err;
550 Record.FunctionHash = R.FunctionHash;
551 ++CurrentRecord;
552 return success();
553 }
554