1 //===-- ProfiledBinary.h - 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 #ifndef LLVM_TOOLS_LLVM_PROFGEN_PROFILEDBINARY_H
10 #define LLVM_TOOLS_LLVM_PROFGEN_PROFILEDBINARY_H
11 
12 #include "CallContext.h"
13 #include "llvm/ADT/StringRef.h"
14 #include "llvm/DebugInfo/Symbolize/Symbolize.h"
15 #include "llvm/MC/MCAsmInfo.h"
16 #include "llvm/MC/MCContext.h"
17 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
18 #include "llvm/MC/MCInst.h"
19 #include "llvm/MC/MCInstPrinter.h"
20 #include "llvm/MC/MCInstrAnalysis.h"
21 #include "llvm/MC/MCInstrInfo.h"
22 #include "llvm/MC/MCObjectFileInfo.h"
23 #include "llvm/MC/MCRegisterInfo.h"
24 #include "llvm/MC/MCSubtargetInfo.h"
25 #include "llvm/MC/MCTargetOptions.h"
26 #include "llvm/Object/ELFObjectFile.h"
27 #include "llvm/ProfileData/SampleProf.h"
28 #include "llvm/Support/Path.h"
29 #include <list>
30 #include <set>
31 #include <sstream>
32 #include <string>
33 #include <unordered_map>
34 #include <unordered_set>
35 #include <vector>
36 
37 using namespace llvm;
38 using namespace sampleprof;
39 using namespace llvm::object;
40 
41 namespace llvm {
42 namespace sampleprof {
43 
44 class ProfiledBinary;
45 
46 struct InstructionPointer {
47   ProfiledBinary *Binary;
48   union {
49     // Offset of the executable segment of the binary.
50     uint64_t Offset = 0;
51     // Also used as address in unwinder
52     uint64_t Address;
53   };
54   // Index to the sorted code address array of the binary.
55   uint64_t Index = 0;
56   InstructionPointer(ProfiledBinary *Binary, uint64_t Address,
57                      bool RoundToNext = false);
58   void advance();
59   void backward();
60   void update(uint64_t Addr);
61 };
62 
63 // PrologEpilog offset tracker, used to filter out broken stack samples
64 // Currently we use a heuristic size (two) to infer prolog and epilog
65 // based on the start address and return address. In the future,
66 // we will switch to Dwarf CFI based tracker
67 struct PrologEpilogTracker {
68   // A set of prolog and epilog offsets. Used by virtual unwinding.
69   std::unordered_set<uint64_t> PrologEpilogSet;
70   ProfiledBinary *Binary;
PrologEpilogTrackerPrologEpilogTracker71   PrologEpilogTracker(ProfiledBinary *Bin) : Binary(Bin){};
72 
73   // Take the two addresses from the start of function as prolog
inferPrologOffsetsPrologEpilogTracker74   void inferPrologOffsets(
75       std::unordered_map<uint64_t, std::string> &FuncStartAddrMap) {
76     for (auto I : FuncStartAddrMap) {
77       PrologEpilogSet.insert(I.first);
78       InstructionPointer IP(Binary, I.first);
79       IP.advance();
80       PrologEpilogSet.insert(IP.Offset);
81     }
82   }
83 
84   // Take the last two addresses before the return address as epilog
inferEpilogOffsetsPrologEpilogTracker85   void inferEpilogOffsets(std::unordered_set<uint64_t> &RetAddrs) {
86     for (auto Addr : RetAddrs) {
87       PrologEpilogSet.insert(Addr);
88       InstructionPointer IP(Binary, Addr);
89       IP.backward();
90       PrologEpilogSet.insert(IP.Offset);
91     }
92   }
93 };
94 
95 class ProfiledBinary {
96   // Absolute path of the binary.
97   std::string Path;
98   // The target triple.
99   Triple TheTriple;
100   // The runtime base address that the executable sections are loaded at.
101   mutable uint64_t BaseAddress = 0;
102   // The preferred base address that the executable sections are loaded at.
103   uint64_t PreferredBaseAddress = 0;
104   // Mutiple MC component info
105   std::unique_ptr<const MCRegisterInfo> MRI;
106   std::unique_ptr<const MCAsmInfo> AsmInfo;
107   std::unique_ptr<const MCSubtargetInfo> STI;
108   std::unique_ptr<const MCInstrInfo> MII;
109   std::unique_ptr<MCDisassembler> DisAsm;
110   std::unique_ptr<const MCInstrAnalysis> MIA;
111   std::unique_ptr<MCInstPrinter> IPrinter;
112   // A list of text sections sorted by start RVA and size. Used to check
113   // if a given RVA is a valid code address.
114   std::set<std::pair<uint64_t, uint64_t>> TextSections;
115   // Function offset to name mapping.
116   std::unordered_map<uint64_t, std::string> FuncStartAddrMap;
117   // Offset to context location map. Used to expand the context.
118   std::unordered_map<uint64_t, FrameLocationStack> Offset2LocStackMap;
119   // An array of offsets of all instructions sorted in increasing order. The
120   // sorting is needed to fast advance to the next forward/backward instruction.
121   std::vector<uint64_t> CodeAddrs;
122   // A set of call instruction offsets. Used by virtual unwinding.
123   std::unordered_set<uint64_t> CallAddrs;
124   // A set of return instruction offsets. Used by virtual unwinding.
125   std::unordered_set<uint64_t> RetAddrs;
126 
127   PrologEpilogTracker ProEpilogTracker;
128 
129   // The symbolizer used to get inline context for an instruction.
130   std::unique_ptr<symbolize::LLVMSymbolizer> Symbolizer;
131   void setPreferredBaseAddress(const ELFObjectFileBase *O);
132 
133   // Set up disassembler and related components.
134   void setUpDisassembler(const ELFObjectFileBase *Obj);
135   void setupSymbolizer();
136 
137   /// Dissassemble the text section and build various address maps.
138   void disassemble(const ELFObjectFileBase *O);
139 
140   /// Helper function to dissassemble the symbol and extract info for unwinding
141   bool dissassembleSymbol(std::size_t SI, ArrayRef<uint8_t> Bytes,
142                           SectionSymbolsTy &Symbols, const SectionRef &Section);
143   /// Symbolize a given instruction pointer and return a full call context.
144   FrameLocationStack symbolize(const InstructionPointer &IP,
145                                bool UseCanonicalFnName = false);
146 
147   /// Decode the interesting parts of the binary and build internal data
148   /// structures. On high level, the parts of interest are:
149   ///   1. Text sections, including the main code section and the PLT
150   ///   entries that will be used to handle cross-module call transitions.
151   ///   2. The .debug_line section, used by Dwarf-based profile generation.
152   ///   3. Pseudo probe related sections, used by probe-based profile
153   ///   generation.
154   void load();
getFrameLocationStack(uint64_t Offset)155   const FrameLocationStack &getFrameLocationStack(uint64_t Offset) const {
156     auto I = Offset2LocStackMap.find(Offset);
157     assert(I != Offset2LocStackMap.end() &&
158            "Can't find location for offset in the binary");
159     return I->second;
160   }
161 
162 public:
ProfiledBinary(StringRef Path)163   ProfiledBinary(StringRef Path) : Path(Path), ProEpilogTracker(this) {
164     setupSymbolizer();
165     load();
166   }
virtualAddrToOffset(uint64_t VitualAddress)167   uint64_t virtualAddrToOffset(uint64_t VitualAddress) const {
168     return VitualAddress - BaseAddress;
169   }
offsetToVirtualAddr(uint64_t Offset)170   uint64_t offsetToVirtualAddr(uint64_t Offset) const {
171     return Offset + BaseAddress;
172   }
getPath()173   const StringRef getPath() const { return Path; }
getName()174   const StringRef getName() const { return llvm::sys::path::filename(Path); }
getBaseAddress()175   uint64_t getBaseAddress() const { return BaseAddress; }
setBaseAddress(uint64_t Address)176   void setBaseAddress(uint64_t Address) { BaseAddress = Address; }
getPreferredBaseAddress()177   uint64_t getPreferredBaseAddress() const { return PreferredBaseAddress; }
178 
addressIsCode(uint64_t Address)179   bool addressIsCode(uint64_t Address) const {
180     uint64_t Offset = virtualAddrToOffset(Address);
181     return Offset2LocStackMap.find(Offset) != Offset2LocStackMap.end();
182   }
addressIsCall(uint64_t Address)183   bool addressIsCall(uint64_t Address) const {
184     uint64_t Offset = virtualAddrToOffset(Address);
185     return CallAddrs.count(Offset);
186   }
addressIsReturn(uint64_t Address)187   bool addressIsReturn(uint64_t Address) const {
188     uint64_t Offset = virtualAddrToOffset(Address);
189     return RetAddrs.count(Offset);
190   }
addressInPrologEpilog(uint64_t Address)191   bool addressInPrologEpilog(uint64_t Address) const {
192     uint64_t Offset = virtualAddrToOffset(Address);
193     return ProEpilogTracker.PrologEpilogSet.count(Offset);
194   }
195 
getAddressforIndex(uint64_t Index)196   uint64_t getAddressforIndex(uint64_t Index) const {
197     return offsetToVirtualAddr(CodeAddrs[Index]);
198   }
199 
200   // Get the index in CodeAddrs for the address
201   // As we might get an address which is not the code
202   // here it would round to the next valid code address by
203   // using lower bound operation
getIndexForAddr(uint64_t Address)204   uint32_t getIndexForAddr(uint64_t Address) const {
205     uint64_t Offset = virtualAddrToOffset(Address);
206     auto Low = std::lower_bound(CodeAddrs.begin(), CodeAddrs.end(), Offset);
207     return Low - CodeAddrs.begin();
208   }
209 
getCallAddrFromFrameAddr(uint64_t FrameAddr)210   uint64_t getCallAddrFromFrameAddr(uint64_t FrameAddr) const {
211     return getAddressforIndex(getIndexForAddr(FrameAddr) - 1);
212   }
213 
getFuncFromStartOffset(uint64_t Offset)214   StringRef getFuncFromStartOffset(uint64_t Offset) {
215     return FuncStartAddrMap[Offset];
216   }
217 
218   const FrameLocation &getInlineLeafFrameLoc(uint64_t Offset,
219                                              bool NameOnly = false) {
220     return getFrameLocationStack(Offset).back();
221   }
222 
223   // Compare two addresses' inline context
224   bool inlineContextEqual(uint64_t Add1, uint64_t Add2) const;
225 
226   // Get the context string of the current stack with inline context filled in.
227   // It will search the disassembling info stored in Offset2LocStackMap. This is
228   // used as the key of function sample map
229   std::string getExpandedContextStr(const std::list<uint64_t> &stack) const;
230 };
231 
232 } // end namespace sampleprof
233 } // end namespace llvm
234 
235 #endif
236