1//===--- PseudoProbe.cpp - Pseudo probe decoding utilities  ------*- 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 "PseudoProbe.h"
10#include "ErrorHandling.h"
11#include "llvm/Support/Endian.h"
12#include "llvm/Support/LEB128.h"
13#include "llvm/Support/raw_ostream.h"
14#include <limits>
15#include <memory>
16
17using namespace llvm;
18using namespace sampleprof;
19using namespace support;
20
21namespace llvm {
22namespace sampleprof {
23
24static StringRef getProbeFNameForGUID(const GUIDProbeFunctionMap &GUID2FuncMAP,
25                                      uint64_t GUID) {
26  auto It = GUID2FuncMAP.find(GUID);
27  assert(It != GUID2FuncMAP.end() &&
28         "Probe function must exist for a valid GUID");
29  return It->second.FuncName;
30}
31
32void PseudoProbeFuncDesc::print(raw_ostream &OS) {
33  OS << "GUID: " << FuncGUID << " Name: " << FuncName << "\n";
34  OS << "Hash: " << FuncHash << "\n";
35}
36
37void PseudoProbe::getInlineContext(SmallVectorImpl<std::string> &ContextStack,
38                                   const GUIDProbeFunctionMap &GUID2FuncMAP,
39                                   bool ShowName) const {
40  uint32_t Begin = ContextStack.size();
41  PseudoProbeInlineTree *Cur = InlineTree;
42  // It will add the string of each node's inline site during iteration.
43  // Note that it won't include the probe's belonging function(leaf location)
44  while (Cur->hasInlineSite()) {
45    std::string ContextStr;
46    if (ShowName) {
47      StringRef FuncName =
48          getProbeFNameForGUID(GUID2FuncMAP, std::get<0>(Cur->ISite));
49      ContextStr += FuncName.str();
50    } else {
51      ContextStr += Twine(std::get<0>(Cur->ISite)).str();
52    }
53    ContextStr += ":";
54    ContextStr += Twine(std::get<1>(Cur->ISite)).str();
55    ContextStack.emplace_back(ContextStr);
56    Cur = Cur->Parent;
57  }
58  // Make the ContextStack in caller-callee order
59  std::reverse(ContextStack.begin() + Begin, ContextStack.end());
60}
61
62std::string
63PseudoProbe::getInlineContextStr(const GUIDProbeFunctionMap &GUID2FuncMAP,
64                                 bool ShowName) const {
65  std::ostringstream OContextStr;
66  SmallVector<std::string, 16> ContextStack;
67  getInlineContext(ContextStack, GUID2FuncMAP, ShowName);
68  for (auto &CxtStr : ContextStack) {
69    if (OContextStr.str().size())
70      OContextStr << " @ ";
71    OContextStr << CxtStr;
72  }
73  return OContextStr.str();
74}
75
76static const char *PseudoProbeTypeStr[3] = {"Block", "IndirectCall",
77                                            "DirectCall"};
78
79void PseudoProbe::print(raw_ostream &OS,
80                        const GUIDProbeFunctionMap &GUID2FuncMAP,
81                        bool ShowName) {
82  OS << "FUNC: ";
83  if (ShowName) {
84    StringRef FuncName = getProbeFNameForGUID(GUID2FuncMAP, GUID);
85    OS << FuncName.str() << " ";
86  } else {
87    OS << GUID << " ";
88  }
89  OS << "Index: " << Index << "  ";
90  OS << "Type: " << PseudoProbeTypeStr[static_cast<uint8_t>(Type)] << "  ";
91  if (isDangling()) {
92    OS << "Dangling  ";
93  }
94  if (isTailCall()) {
95    OS << "TailCall  ";
96  }
97  std::string InlineContextStr = getInlineContextStr(GUID2FuncMAP, ShowName);
98  if (InlineContextStr.size()) {
99    OS << "Inlined: @ ";
100    OS << InlineContextStr;
101  }
102  OS << "\n";
103}
104
105template <typename T> T PseudoProbeDecoder::readUnencodedNumber() {
106  if (Data + sizeof(T) > End) {
107    exitWithError("Decode unencoded number error in " + SectionName +
108                  " section");
109  }
110  T Val = endian::readNext<T, little, unaligned>(Data);
111  return Val;
112}
113
114template <typename T> T PseudoProbeDecoder::readUnsignedNumber() {
115  unsigned NumBytesRead = 0;
116  uint64_t Val = decodeULEB128(Data, &NumBytesRead);
117  if (Val > std::numeric_limits<T>::max() || (Data + NumBytesRead > End)) {
118    exitWithError("Decode number error in " + SectionName + " section");
119  }
120  Data += NumBytesRead;
121  return static_cast<T>(Val);
122}
123
124template <typename T> T PseudoProbeDecoder::readSignedNumber() {
125  unsigned NumBytesRead = 0;
126  int64_t Val = decodeSLEB128(Data, &NumBytesRead);
127  if (Val > std::numeric_limits<T>::max() || (Data + NumBytesRead > End)) {
128    exitWithError("Decode number error in " + SectionName + " section");
129  }
130  Data += NumBytesRead;
131  return static_cast<T>(Val);
132}
133
134StringRef PseudoProbeDecoder::readString(uint32_t Size) {
135  StringRef Str(reinterpret_cast<const char *>(Data), Size);
136  if (Data + Size > End) {
137    exitWithError("Decode string error in " + SectionName + " section");
138  }
139  Data += Size;
140  return Str;
141}
142
143void PseudoProbeDecoder::buildGUID2FuncDescMap(const uint8_t *Start,
144                                               std::size_t Size) {
145  // The pseudo_probe_desc section has a format like:
146  // .section .pseudo_probe_desc,"",@progbits
147  // .quad -5182264717993193164   // GUID
148  // .quad 4294967295             // Hash
149  // .uleb 3                      // Name size
150  // .ascii "foo"                 // Name
151  // .quad -2624081020897602054
152  // .quad 174696971957
153  // .uleb 34
154  // .ascii "main"
155#ifndef NDEBUG
156  SectionName = "pseudo_probe_desc";
157#endif
158  Data = Start;
159  End = Data + Size;
160
161  while (Data < End) {
162    uint64_t GUID = readUnencodedNumber<uint64_t>();
163    uint64_t Hash = readUnencodedNumber<uint64_t>();
164    uint32_t NameSize = readUnsignedNumber<uint32_t>();
165    StringRef Name = FunctionSamples::getCanonicalFnName(readString(NameSize));
166
167    // Initialize PseudoProbeFuncDesc and populate it into GUID2FuncDescMap
168    GUID2FuncDescMap.emplace(GUID, PseudoProbeFuncDesc(GUID, Hash, Name));
169  }
170  assert(Data == End && "Have unprocessed data in pseudo_probe_desc section");
171}
172
173void PseudoProbeDecoder::buildAddress2ProbeMap(const uint8_t *Start,
174                                               std::size_t Size) {
175  // The pseudo_probe section encodes an inline forest and each tree has a
176  // format like:
177  //  FUNCTION BODY (one for each uninlined function present in the text
178  //  section)
179  //     GUID (uint64)
180  //         GUID of the function
181  //     NPROBES (ULEB128)
182  //         Number of probes originating from this function.
183  //     NUM_INLINED_FUNCTIONS (ULEB128)
184  //         Number of callees inlined into this function, aka number of
185  //         first-level inlinees
186  //     PROBE RECORDS
187  //         A list of NPROBES entries. Each entry contains:
188  //           INDEX (ULEB128)
189  //           TYPE (uint4)
190  //             0 - block probe, 1 - indirect call, 2 - direct call
191  //           ATTRIBUTE (uint3)
192  //             1 - tail call, 2 - dangling
193  //           ADDRESS_TYPE (uint1)
194  //             0 - code address, 1 - address delta
195  //           CODE_ADDRESS (uint64 or ULEB128)
196  //             code address or address delta, depending on Flag
197  //     INLINED FUNCTION RECORDS
198  //         A list of NUM_INLINED_FUNCTIONS entries describing each of the
199  //         inlined callees.  Each record contains:
200  //           INLINE SITE
201  //             Index of the callsite probe (ULEB128)
202  //           FUNCTION BODY
203  //             A FUNCTION BODY entry describing the inlined function.
204#ifndef NDEBUG
205  SectionName = "pseudo_probe";
206#endif
207  Data = Start;
208  End = Data + Size;
209
210  PseudoProbeInlineTree *Root = &DummyInlineRoot;
211  PseudoProbeInlineTree *Cur = &DummyInlineRoot;
212  uint64_t LastAddr = 0;
213  uint32_t Index = 0;
214  // A DFS-based decoding
215  while (Data < End) {
216    if (Root == Cur) {
217      // Use a sequential id for top level inliner.
218      Index = Root->getChildren().size();
219    } else {
220      // Read inline site for inlinees
221      Index = readUnsignedNumber<uint32_t>();
222    }
223    // Switch/add to a new tree node(inlinee)
224    Cur = Cur->getOrAddNode(std::make_tuple(Cur->GUID, Index));
225    // Read guid
226    Cur->GUID = readUnencodedNumber<uint64_t>();
227    // Read number of probes in the current node.
228    uint32_t NodeCount = readUnsignedNumber<uint32_t>();
229    // Read number of direct inlinees
230    Cur->ChildrenToProcess = readUnsignedNumber<uint32_t>();
231    // Read all probes in this node
232    for (std::size_t I = 0; I < NodeCount; I++) {
233      // Read index
234      uint32_t Index = readUnsignedNumber<uint32_t>();
235      // Read type | flag.
236      uint8_t Value = readUnencodedNumber<uint8_t>();
237      uint8_t Kind = Value & 0xf;
238      uint8_t Attr = (Value & 0x70) >> 4;
239      // Read address
240      uint64_t Addr = 0;
241      if (Value & 0x80) {
242        int64_t Offset = readSignedNumber<int64_t>();
243        Addr = LastAddr + Offset;
244      } else {
245        Addr = readUnencodedNumber<int64_t>();
246      }
247      // Populate Address2ProbesMap
248      auto &Probes = Address2ProbesMap[Addr];
249      Probes.emplace_back(Addr, Cur->GUID, Index, PseudoProbeType(Kind), Attr,
250                          Cur);
251      Cur->addProbes(&Probes.back());
252      LastAddr = Addr;
253    }
254
255    // Look for the parent for the next node by subtracting the current
256    // node count from tree counts along the parent chain. The first node
257    // in the chain that has a non-zero tree count is the target.
258    while (Cur != Root) {
259      if (Cur->ChildrenToProcess == 0) {
260        Cur = Cur->Parent;
261        if (Cur != Root) {
262          assert(Cur->ChildrenToProcess > 0 &&
263                 "Should have some unprocessed nodes");
264          Cur->ChildrenToProcess -= 1;
265        }
266      } else {
267        break;
268      }
269    }
270  }
271
272  assert(Data == End && "Have unprocessed data in pseudo_probe section");
273  assert(Cur == Root &&
274         " Cur should point to root when the forest is fully built up");
275}
276
277void PseudoProbeDecoder::printGUID2FuncDescMap(raw_ostream &OS) {
278  OS << "Pseudo Probe Desc:\n";
279  // Make the output deterministic
280  std::map<uint64_t, PseudoProbeFuncDesc> OrderedMap(GUID2FuncDescMap.begin(),
281                                                     GUID2FuncDescMap.end());
282  for (auto &I : OrderedMap) {
283    I.second.print(OS);
284  }
285}
286
287void PseudoProbeDecoder::printProbeForAddress(raw_ostream &OS,
288                                              uint64_t Address) {
289  auto It = Address2ProbesMap.find(Address);
290  if (It != Address2ProbesMap.end()) {
291    for (auto &Probe : It->second) {
292      OS << " [Probe]:\t";
293      Probe.print(OS, GUID2FuncDescMap, true);
294    }
295  }
296}
297
298const PseudoProbe *
299PseudoProbeDecoder::getCallProbeForAddr(uint64_t Address) const {
300  auto It = Address2ProbesMap.find(Address);
301  if (It == Address2ProbesMap.end())
302    return nullptr;
303  const auto &Probes = It->second;
304
305  const PseudoProbe *CallProbe = nullptr;
306  for (const auto &Probe : Probes) {
307    if (Probe.isCall()) {
308      assert(!CallProbe &&
309             "There should be only one call probe corresponding to address "
310             "which is a callsite.");
311      CallProbe = &Probe;
312    }
313  }
314  return CallProbe;
315}
316
317const PseudoProbeFuncDesc *
318PseudoProbeDecoder::getFuncDescForGUID(uint64_t GUID) const {
319  auto It = GUID2FuncDescMap.find(GUID);
320  assert(It != GUID2FuncDescMap.end() && "Function descriptor doesn't exist");
321  return &It->second;
322}
323
324void PseudoProbeDecoder::getInlineContextForProbe(
325    const PseudoProbe *Probe, SmallVectorImpl<std::string> &InlineContextStack,
326    bool IncludeLeaf) const {
327  Probe->getInlineContext(InlineContextStack, GUID2FuncDescMap, true);
328  if (!IncludeLeaf)
329    return;
330  // Note that the context from probe doesn't include leaf frame,
331  // hence we need to retrieve and prepend leaf if requested.
332  const auto *FuncDesc = getFuncDescForGUID(Probe->GUID);
333  InlineContextStack.emplace_back(FuncDesc->FuncName + ":" +
334                                  Twine(Probe->Index).str());
335}
336
337const PseudoProbeFuncDesc *
338PseudoProbeDecoder::getInlinerDescForProbe(const PseudoProbe *Probe) const {
339  PseudoProbeInlineTree *InlinerNode = Probe->InlineTree;
340  if (!InlinerNode->hasInlineSite())
341    return nullptr;
342  return getFuncDescForGUID(std::get<0>(InlinerNode->ISite));
343}
344
345} // end namespace sampleprof
346} // end namespace llvm
347