1 //===-- ProfiledBinary.cpp - Binary decoder ---------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "ProfiledBinary.h"
10 #include "ErrorHandling.h"
11 #include "ProfileGenerator.h"
12 #include "llvm/ADT/Triple.h"
13 #include "llvm/Demangle/Demangle.h"
14 #include "llvm/IR/DebugInfoMetadata.h"
15 #include "llvm/Support/CommandLine.h"
16 #include "llvm/Support/Format.h"
17 #include "llvm/Support/TargetRegistry.h"
18 #include "llvm/Support/TargetSelect.h"
19 
20 #define DEBUG_TYPE "load-binary"
21 
22 using namespace llvm;
23 using namespace sampleprof;
24 
25 cl::opt<bool> ShowDisassemblyOnly("show-disassembly-only", cl::ReallyHidden,
26                                   cl::init(false), cl::ZeroOrMore,
27                                   cl::desc("Print disassembled code."));
28 
29 cl::opt<bool> ShowSourceLocations("show-source-locations", cl::ReallyHidden,
30                                   cl::init(false), cl::ZeroOrMore,
31                                   cl::desc("Print source locations."));
32 
33 cl::opt<bool> ShowCanonicalFnName("show-canonical-fname", cl::ReallyHidden,
34                                   cl::init(false), cl::ZeroOrMore,
35                                   cl::desc("Print canonical function name."));
36 
37 cl::opt<bool> ShowPseudoProbe(
38     "show-pseudo-probe", cl::ReallyHidden, cl::init(false), cl::ZeroOrMore,
39     cl::desc("Print pseudo probe section and disassembled info."));
40 
41 namespace llvm {
42 namespace sampleprof {
43 
44 static const Target *getTarget(const ObjectFile *Obj) {
45   Triple TheTriple = Obj->makeTriple();
46   std::string Error;
47   std::string ArchName;
48   const Target *TheTarget =
49       TargetRegistry::lookupTarget(ArchName, TheTriple, Error);
50   if (!TheTarget)
51     exitWithError(Error, Obj->getFileName());
52   return TheTarget;
53 }
54 
55 void BinarySizeContextTracker::addInstructionForContext(
56     const FrameLocationStack &Context, uint32_t InstrSize) {
57   ContextTrieNode *CurNode = &RootContext;
58   bool IsLeaf = true;
59   for (const auto &Callsite : reverse(Context)) {
60     StringRef CallerName = Callsite.first;
61     LineLocation CallsiteLoc = IsLeaf ? LineLocation(0, 0) : Callsite.second;
62     CurNode = CurNode->getOrCreateChildContext(CallsiteLoc, CallerName);
63     IsLeaf = false;
64   }
65 
66   CurNode->setFunctionSize(CurNode->getFunctionSize() + InstrSize);
67 }
68 
69 uint32_t
70 BinarySizeContextTracker::getFuncSizeForContext(const SampleContext &Context) {
71   ContextTrieNode *CurrNode = &RootContext;
72   ContextTrieNode *PrevNode = nullptr;
73   StringRef ContextRemain = Context;
74   StringRef ChildContext;
75   StringRef CallerName;
76   uint32_t Size = 0;
77 
78   // Start from top-level context-less function, travese down the reverse
79   // context trie to find the best/longest match for given context, then
80   // retrieve the size.
81   while (CurrNode && !ContextRemain.empty()) {
82     // rsplit so we process from leaf function to callers (added to context).
83     auto ContextSplit = SampleContext::rsplitContextString(ContextRemain);
84     ChildContext = ContextSplit.second;
85     ContextRemain = ContextSplit.first;
86     LineLocation CallSiteLoc(0, 0);
87     SampleContext::decodeContextString(ChildContext, CallerName, CallSiteLoc);
88     PrevNode = CurrNode;
89     CurrNode = CurrNode->getChildContext(CallSiteLoc, CallerName);
90     if (CurrNode && CurrNode->getFunctionSize())
91       Size = CurrNode->getFunctionSize();
92   }
93 
94   // If we traversed all nodes along the path of the context and haven't
95   // found a size yet, pivot to look for size from sibling nodes, i.e size
96   // of inlinee under different context.
97   if (!Size) {
98     if (!CurrNode)
99       CurrNode = PrevNode;
100     while (!Size && CurrNode) {
101       CurrNode = &CurrNode->getAllChildContext().begin()->second;
102       Size = CurrNode->getFunctionSize();
103     }
104   }
105 
106   return Size;
107 }
108 
109 void ProfiledBinary::load() {
110   // Attempt to open the binary.
111   OwningBinary<Binary> OBinary = unwrapOrError(createBinary(Path), Path);
112   Binary &Binary = *OBinary.getBinary();
113 
114   auto *Obj = dyn_cast<ELFObjectFileBase>(&Binary);
115   if (!Obj)
116     exitWithError("not a valid Elf image", Path);
117 
118   TheTriple = Obj->makeTriple();
119   // Current only support X86
120   if (!TheTriple.isX86())
121     exitWithError("unsupported target", TheTriple.getTriple());
122   LLVM_DEBUG(dbgs() << "Loading " << Path << "\n");
123 
124   // Find the preferred load address for text sections.
125   setPreferredTextSegmentAddresses(Obj);
126 
127   // Decode pseudo probe related section
128   decodePseudoProbe(Obj);
129 
130   // Disassemble the text sections.
131   disassemble(Obj);
132 
133   // Use function start and return address to infer prolog and epilog
134   ProEpilogTracker.inferPrologOffsets(FuncStartAddrMap);
135   ProEpilogTracker.inferEpilogOffsets(RetAddrs);
136 
137   // TODO: decode other sections.
138 }
139 
140 bool ProfiledBinary::inlineContextEqual(uint64_t Address1,
141                                         uint64_t Address2) const {
142   uint64_t Offset1 = virtualAddrToOffset(Address1);
143   uint64_t Offset2 = virtualAddrToOffset(Address2);
144   const FrameLocationStack &Context1 = getFrameLocationStack(Offset1);
145   const FrameLocationStack &Context2 = getFrameLocationStack(Offset2);
146   if (Context1.size() != Context2.size())
147     return false;
148   if (Context1.empty())
149     return false;
150   // The leaf frame contains location within the leaf, and it
151   // needs to be remove that as it's not part of the calling context
152   return std::equal(Context1.begin(), Context1.begin() + Context1.size() - 1,
153                     Context2.begin(), Context2.begin() + Context2.size() - 1);
154 }
155 
156 std::string
157 ProfiledBinary::getExpandedContextStr(const SmallVectorImpl<uint64_t> &Stack,
158                                       bool &WasLeafInlined) const {
159   std::string ContextStr;
160   SmallVector<std::string, 16> ContextVec;
161   // Process from frame root to leaf
162   for (auto Address : Stack) {
163     uint64_t Offset = virtualAddrToOffset(Address);
164     const FrameLocationStack &ExpandedContext = getFrameLocationStack(Offset);
165     // An instruction without a valid debug line will be ignored by sample
166     // processing
167     if (ExpandedContext.empty())
168       return std::string();
169     // Set WasLeafInlined to the size of inlined frame count for the last
170     // address which is leaf
171     WasLeafInlined = (ExpandedContext.size() > 1);
172     for (const auto &Loc : ExpandedContext) {
173       ContextVec.push_back(getCallSite(Loc));
174     }
175   }
176 
177   assert(ContextVec.size() && "Context length should be at least 1");
178   // Compress the context string except for the leaf frame
179   std::string LeafFrame = ContextVec.back();
180   ContextVec.pop_back();
181   CSProfileGenerator::compressRecursionContext<std::string>(ContextVec);
182   CSProfileGenerator::trimContext<std::string>(ContextVec);
183 
184   std::ostringstream OContextStr;
185   for (uint32_t I = 0; I < (uint32_t)ContextVec.size(); I++) {
186     if (OContextStr.str().size()) {
187       OContextStr << " @ ";
188     }
189     OContextStr << ContextVec[I];
190   }
191   // Only keep the function name for the leaf frame
192   if (OContextStr.str().size())
193     OContextStr << " @ ";
194   OContextStr << StringRef(LeafFrame).split(":").first.str();
195   return OContextStr.str();
196 }
197 
198 template <class ELFT>
199 void ProfiledBinary::setPreferredTextSegmentAddresses(const ELFFile<ELFT> &Obj, StringRef FileName) {
200   const auto &PhdrRange = unwrapOrError(Obj.program_headers(), FileName);
201   for (const typename ELFT::Phdr &Phdr : PhdrRange) {
202     if ((Phdr.p_type == ELF::PT_LOAD) && (Phdr.p_flags & ELF::PF_X)) {
203         // Segments will always be loaded at a page boundary.
204         PreferredTextSegmentAddresses.push_back(Phdr.p_vaddr & ~(Phdr.p_align - 1U));
205         TextSegmentOffsets.push_back(Phdr.p_offset & ~(Phdr.p_align - 1U));
206       }
207   }
208 
209   if (PreferredTextSegmentAddresses.empty())
210     exitWithError("no executable segment found", FileName);
211 }
212 
213 void ProfiledBinary::setPreferredTextSegmentAddresses(const ELFObjectFileBase *Obj) {
214   if (const auto *ELFObj = dyn_cast<ELF32LEObjectFile>(Obj))
215     setPreferredTextSegmentAddresses(ELFObj->getELFFile(), Obj->getFileName());
216   else if (const auto *ELFObj = dyn_cast<ELF32BEObjectFile>(Obj))
217     setPreferredTextSegmentAddresses(ELFObj->getELFFile(), Obj->getFileName());
218   else if (const auto *ELFObj = dyn_cast<ELF64LEObjectFile>(Obj))
219     setPreferredTextSegmentAddresses(ELFObj->getELFFile(), Obj->getFileName());
220   else if (const auto *ELFObj = cast<ELF64BEObjectFile>(Obj))
221     setPreferredTextSegmentAddresses(ELFObj->getELFFile(), Obj->getFileName());
222   else
223     llvm_unreachable("invalid ELF object format");
224 }
225 
226 void ProfiledBinary::decodePseudoProbe(const ELFObjectFileBase *Obj) {
227   StringRef FileName = Obj->getFileName();
228   for (section_iterator SI = Obj->section_begin(), SE = Obj->section_end();
229        SI != SE; ++SI) {
230     const SectionRef &Section = *SI;
231     StringRef SectionName = unwrapOrError(Section.getName(), FileName);
232 
233     if (SectionName == ".pseudo_probe_desc") {
234       StringRef Contents = unwrapOrError(Section.getContents(), FileName);
235       if (!ProbeDecoder.buildGUID2FuncDescMap(
236               reinterpret_cast<const uint8_t *>(Contents.data()),
237               Contents.size()))
238         exitWithError("Pseudo Probe decoder fail in .pseudo_probe_desc section");
239     } else if (SectionName == ".pseudo_probe") {
240       StringRef Contents = unwrapOrError(Section.getContents(), FileName);
241       if (!ProbeDecoder.buildAddress2ProbeMap(
242               reinterpret_cast<const uint8_t *>(Contents.data()),
243               Contents.size()))
244         exitWithError("Pseudo Probe decoder fail in .pseudo_probe section");
245       // set UsePseudoProbes flag, used for PerfReader
246       UsePseudoProbes = true;
247     }
248   }
249 
250   if (ShowPseudoProbe)
251     ProbeDecoder.printGUID2FuncDescMap(outs());
252 }
253 
254 bool ProfiledBinary::dissassembleSymbol(std::size_t SI, ArrayRef<uint8_t> Bytes,
255                                         SectionSymbolsTy &Symbols,
256                                         const SectionRef &Section) {
257   std::size_t SE = Symbols.size();
258   uint64_t SectionOffset = Section.getAddress() - getPreferredBaseAddress();
259   uint64_t SectSize = Section.getSize();
260   uint64_t StartOffset = Symbols[SI].Addr - getPreferredBaseAddress();
261   uint64_t EndOffset = (SI + 1 < SE)
262                            ? Symbols[SI + 1].Addr - getPreferredBaseAddress()
263                            : SectionOffset + SectSize;
264   if (StartOffset >= EndOffset)
265     return true;
266 
267   StringRef SymbolName =
268       ShowCanonicalFnName
269           ? FunctionSamples::getCanonicalFnName(Symbols[SI].Name)
270           : Symbols[SI].Name;
271   if (ShowDisassemblyOnly)
272     outs() << '<' << SymbolName << ">:\n";
273 
274   auto WarnInvalidInsts = [](uint64_t Start, uint64_t End) {
275     WithColor::warning() << "Invalid instructions at "
276                          << format("%8" PRIx64, Start) << " - "
277                          << format("%8" PRIx64, End) << "\n";
278   };
279 
280   uint64_t Offset = StartOffset;
281   // Size of a consecutive invalid instruction range starting from Offset -1
282   // backwards.
283   uint64_t InvalidInstLength = 0;
284   while (Offset < EndOffset) {
285     MCInst Inst;
286     uint64_t Size;
287     // Disassemble an instruction.
288     bool Disassembled =
289         DisAsm->getInstruction(Inst, Size, Bytes.slice(Offset - SectionOffset),
290                                Offset + getPreferredBaseAddress(), nulls());
291     if (Size == 0)
292       Size = 1;
293 
294     if (ShowDisassemblyOnly) {
295       if (ShowPseudoProbe) {
296         ProbeDecoder.printProbeForAddress(outs(),
297                                           Offset + getPreferredBaseAddress());
298       }
299       outs() << format("%8" PRIx64 ":", Offset + getPreferredBaseAddress());
300       size_t Start = outs().tell();
301       if (Disassembled)
302         IPrinter->printInst(&Inst, Offset + Size, "", *STI.get(), outs());
303       else
304         outs() << "\t<unknown>";
305       if (ShowSourceLocations) {
306         unsigned Cur = outs().tell() - Start;
307         if (Cur < 40)
308           outs().indent(40 - Cur);
309         InstructionPointer IP(this, Offset);
310         outs() << getReversedLocWithContext(
311             symbolize(IP, ShowCanonicalFnName, ShowPseudoProbe));
312       }
313       outs() << "\n";
314     }
315 
316     if (Disassembled) {
317       const MCInstrDesc &MCDesc = MII->get(Inst.getOpcode());
318       // Populate a vector of the symbolized callsite at this location
319       // We don't need symbolized info for probe-based profile, just use an
320       // empty stack as an entry to indicate a valid binary offset
321 
322       if (!UsePseudoProbes || TrackFuncContextSize) {
323         InstructionPointer IP(this, Offset);
324         // TODO: reallocation of Offset2LocStackMap will lead to dangling
325         // strings We need ProfiledBinary to owned these string.
326         Offset2LocStackMap[Offset] = symbolize(IP, true, UsePseudoProbes);
327         FrameLocationStack &SymbolizedCallStack = Offset2LocStackMap[Offset];
328         // Record instruction size for the corresponding context
329         if (TrackFuncContextSize && !SymbolizedCallStack.empty())
330           FuncSizeTracker.addInstructionForContext(Offset2LocStackMap[Offset],
331                                                    Size);
332       } else {
333         Offset2LocStackMap[Offset] = FrameLocationStack();
334       }
335 
336       // Populate address maps.
337       CodeAddrs.push_back(Offset);
338       if (MCDesc.isCall())
339         CallAddrs.insert(Offset);
340       else if (MCDesc.isReturn())
341         RetAddrs.insert(Offset);
342 
343       if (InvalidInstLength) {
344         WarnInvalidInsts(Offset - InvalidInstLength, Offset - 1);
345         InvalidInstLength = 0;
346       }
347     } else {
348       InvalidInstLength += Size;
349     }
350 
351     Offset += Size;
352   }
353 
354   if (InvalidInstLength)
355     WarnInvalidInsts(Offset - InvalidInstLength, Offset - 1);
356 
357   if (ShowDisassemblyOnly)
358     outs() << "\n";
359 
360   FuncStartAddrMap[StartOffset] = Symbols[SI].Name.str();
361   return true;
362 }
363 
364 void ProfiledBinary::setUpDisassembler(const ELFObjectFileBase *Obj) {
365   const Target *TheTarget = getTarget(Obj);
366   std::string TripleName = TheTriple.getTriple();
367   StringRef FileName = Obj->getFileName();
368 
369   MRI.reset(TheTarget->createMCRegInfo(TripleName));
370   if (!MRI)
371     exitWithError("no register info for target " + TripleName, FileName);
372 
373   MCTargetOptions MCOptions;
374   AsmInfo.reset(TheTarget->createMCAsmInfo(*MRI, TripleName, MCOptions));
375   if (!AsmInfo)
376     exitWithError("no assembly info for target " + TripleName, FileName);
377 
378   SubtargetFeatures Features = Obj->getFeatures();
379   STI.reset(
380       TheTarget->createMCSubtargetInfo(TripleName, "", Features.getString()));
381   if (!STI)
382     exitWithError("no subtarget info for target " + TripleName, FileName);
383 
384   MII.reset(TheTarget->createMCInstrInfo());
385   if (!MII)
386     exitWithError("no instruction info for target " + TripleName, FileName);
387 
388   MCContext Ctx(Triple(TripleName), AsmInfo.get(), MRI.get(), STI.get());
389   std::unique_ptr<MCObjectFileInfo> MOFI(
390       TheTarget->createMCObjectFileInfo(Ctx, /*PIC=*/false));
391   Ctx.setObjectFileInfo(MOFI.get());
392   DisAsm.reset(TheTarget->createMCDisassembler(*STI, Ctx));
393   if (!DisAsm)
394     exitWithError("no disassembler for target " + TripleName, FileName);
395 
396   MIA.reset(TheTarget->createMCInstrAnalysis(MII.get()));
397 
398   int AsmPrinterVariant = AsmInfo->getAssemblerDialect();
399   IPrinter.reset(TheTarget->createMCInstPrinter(
400       Triple(TripleName), AsmPrinterVariant, *AsmInfo, *MII, *MRI));
401   IPrinter->setPrintBranchImmAsAddress(true);
402 }
403 
404 void ProfiledBinary::disassemble(const ELFObjectFileBase *Obj) {
405   // Set up disassembler and related components.
406   setUpDisassembler(Obj);
407 
408   // Create a mapping from virtual address to symbol name. The symbols in text
409   // sections are the candidates to dissassemble.
410   std::map<SectionRef, SectionSymbolsTy> AllSymbols;
411   StringRef FileName = Obj->getFileName();
412   for (const SymbolRef &Symbol : Obj->symbols()) {
413     const uint64_t Addr = unwrapOrError(Symbol.getAddress(), FileName);
414     const StringRef Name = unwrapOrError(Symbol.getName(), FileName);
415     section_iterator SecI = unwrapOrError(Symbol.getSection(), FileName);
416     if (SecI != Obj->section_end())
417       AllSymbols[*SecI].push_back(SymbolInfoTy(Addr, Name, ELF::STT_NOTYPE));
418   }
419 
420   // Sort all the symbols. Use a stable sort to stabilize the output.
421   for (std::pair<const SectionRef, SectionSymbolsTy> &SecSyms : AllSymbols)
422     stable_sort(SecSyms.second);
423 
424   if (ShowDisassemblyOnly)
425     outs() << "\nDisassembly of " << FileName << ":\n";
426 
427   // Dissassemble a text section.
428   for (section_iterator SI = Obj->section_begin(), SE = Obj->section_end();
429        SI != SE; ++SI) {
430     const SectionRef &Section = *SI;
431     if (!Section.isText())
432       continue;
433 
434     uint64_t ImageLoadAddr = getPreferredBaseAddress();
435     uint64_t SectionOffset = Section.getAddress() - ImageLoadAddr;
436     uint64_t SectSize = Section.getSize();
437     if (!SectSize)
438       continue;
439 
440     // Register the text section.
441     TextSections.insert({SectionOffset, SectSize});
442 
443     if (ShowDisassemblyOnly) {
444       StringRef SectionName = unwrapOrError(Section.getName(), FileName);
445       outs() << "\nDisassembly of section " << SectionName;
446       outs() << " [" << format("0x%" PRIx64, Section.getAddress()) << ", "
447              << format("0x%" PRIx64, Section.getAddress() + SectSize)
448              << "]:\n\n";
449     }
450 
451     // Get the section data.
452     ArrayRef<uint8_t> Bytes =
453         arrayRefFromStringRef(unwrapOrError(Section.getContents(), FileName));
454 
455     // Get the list of all the symbols in this section.
456     SectionSymbolsTy &Symbols = AllSymbols[Section];
457 
458     // Disassemble symbol by symbol.
459     for (std::size_t SI = 0, SE = Symbols.size(); SI != SE; ++SI) {
460       if (!dissassembleSymbol(SI, Bytes, Symbols, Section))
461         exitWithError("disassembling error", FileName);
462     }
463   }
464 }
465 
466 void ProfiledBinary::setupSymbolizer() {
467   symbolize::LLVMSymbolizer::Options SymbolizerOpts;
468   SymbolizerOpts.PrintFunctions =
469       DILineInfoSpecifier::FunctionNameKind::LinkageName;
470   SymbolizerOpts.Demangle = false;
471   SymbolizerOpts.DefaultArch = TheTriple.getArchName().str();
472   SymbolizerOpts.UseSymbolTable = false;
473   SymbolizerOpts.RelativeAddresses = false;
474   Symbolizer = std::make_unique<symbolize::LLVMSymbolizer>(SymbolizerOpts);
475 }
476 
477 FrameLocationStack ProfiledBinary::symbolize(const InstructionPointer &IP,
478                                              bool UseCanonicalFnName,
479                                              bool UseProbeDiscriminator) {
480   assert(this == IP.Binary &&
481          "Binary should only symbolize its own instruction");
482   auto Addr = object::SectionedAddress{IP.Offset + getPreferredBaseAddress(),
483                                        object::SectionedAddress::UndefSection};
484   DIInliningInfo InlineStack =
485       unwrapOrError(Symbolizer->symbolizeInlinedCode(Path, Addr), getName());
486 
487   FrameLocationStack CallStack;
488   for (int32_t I = InlineStack.getNumberOfFrames() - 1; I >= 0; I--) {
489     const auto &CallerFrame = InlineStack.getFrame(I);
490     if (CallerFrame.FunctionName == "<invalid>")
491       break;
492 
493     StringRef FunctionName(CallerFrame.FunctionName);
494     if (UseCanonicalFnName)
495       FunctionName = FunctionSamples::getCanonicalFnName(FunctionName);
496 
497     uint32_t Discriminator = CallerFrame.Discriminator;
498     uint32_t LineOffset = CallerFrame.Line - CallerFrame.StartLine;
499     if (UseProbeDiscriminator) {
500       LineOffset =
501           PseudoProbeDwarfDiscriminator::extractProbeIndex(Discriminator);
502       Discriminator = 0;
503     } else {
504       Discriminator = DILocation::getBaseDiscriminatorFromDiscriminator(
505           CallerFrame.Discriminator,
506           /* IsFSDiscriminator */ false);
507     }
508 
509     LineLocation Line(LineOffset, Discriminator);
510     FrameLocation Callsite(FunctionName.str(), Line);
511     CallStack.push_back(Callsite);
512   }
513 
514   return CallStack;
515 }
516 
517 InstructionPointer::InstructionPointer(ProfiledBinary *Binary, uint64_t Address,
518                                        bool RoundToNext)
519     : Binary(Binary), Address(Address) {
520   Index = Binary->getIndexForAddr(Address);
521   if (RoundToNext) {
522     // we might get address which is not the code
523     // it should round to the next valid address
524     this->Address = Binary->getAddressforIndex(Index);
525   }
526 }
527 
528 void InstructionPointer::advance() {
529   Index++;
530   Address = Binary->getAddressforIndex(Index);
531 }
532 
533 void InstructionPointer::backward() {
534   Index--;
535   Address = Binary->getAddressforIndex(Index);
536 }
537 
538 void InstructionPointer::update(uint64_t Addr) {
539   Address = Addr;
540   Index = Binary->getIndexForAddr(Address);
541 }
542 
543 } // end namespace sampleprof
544 } // end namespace llvm
545