1//===- InlineInfo.cpp -------------------------------------------*- 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 "llvm/DebugInfo/GSYM/FileEntry.h"
10#include "llvm/DebugInfo/GSYM/FileWriter.h"
11#include "llvm/DebugInfo/GSYM/GsymReader.h"
12#include "llvm/DebugInfo/GSYM/InlineInfo.h"
13#include "llvm/Support/DataExtractor.h"
14#include <algorithm>
15#include <inttypes.h>
16
17using namespace llvm;
18using namespace gsym;
19
20
21raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const InlineInfo &II) {
22  if (!II.isValid())
23    return OS;
24  bool First = true;
25  for (auto Range : II.Ranges) {
26    if (First)
27      First = false;
28    else
29      OS << ' ';
30    OS << Range;
31  }
32  OS << " Name = " << HEX32(II.Name) << ", CallFile = " << II.CallFile
33     << ", CallLine = " << II.CallFile << '\n';
34  for (const auto &Child : II.Children)
35    OS << Child;
36  return OS;
37}
38
39static bool getInlineStackHelper(const InlineInfo &II, uint64_t Addr,
40    std::vector<const InlineInfo *> &InlineStack) {
41  if (II.Ranges.contains(Addr)) {
42    // If this is the top level that represents the concrete function,
43    // there will be no name and we shoud clear the inline stack. Otherwise
44    // we have found an inline call stack that we need to insert.
45    if (II.Name != 0)
46      InlineStack.insert(InlineStack.begin(), &II);
47    for (const auto &Child : II.Children) {
48      if (::getInlineStackHelper(Child, Addr, InlineStack))
49        break;
50    }
51    return !InlineStack.empty();
52  }
53  return false;
54}
55
56llvm::Optional<InlineInfo::InlineArray> InlineInfo::getInlineStack(uint64_t Addr) const {
57  InlineArray Result;
58  if (getInlineStackHelper(*this, Addr, Result))
59    return Result;
60  return llvm::None;
61}
62
63/// Skip an InlineInfo object in the specified data at the specified offset.
64///
65/// Used during the InlineInfo::lookup() call to quickly skip child InlineInfo
66/// objects where the addres ranges isn't contained in the InlineInfo object
67/// or its children. This avoids allocations by not appending child InlineInfo
68/// objects to the InlineInfo::Children array.
69///
70/// \param Data The binary stream to read the data from.
71///
72/// \param Offset The byte offset within \a Data.
73///
74/// \param SkippedRanges If true, address ranges have already been skipped.
75
76static bool skip(DataExtractor &Data, uint64_t &Offset, bool SkippedRanges) {
77  if (!SkippedRanges) {
78    if (AddressRanges::skip(Data, Offset) == 0)
79      return false;
80  }
81  bool HasChildren = Data.getU8(&Offset) != 0;
82  Data.getU32(&Offset); // Skip Inline.Name.
83  Data.getULEB128(&Offset); // Skip Inline.CallFile.
84  Data.getULEB128(&Offset); // Skip Inline.CallLine.
85  if (HasChildren) {
86    while (skip(Data, Offset, false /* SkippedRanges */))
87      /* Do nothing */;
88  }
89  // We skipped a valid InlineInfo.
90  return true;
91}
92
93/// A Lookup helper functions.
94///
95/// Used during the InlineInfo::lookup() call to quickly only parse an
96/// InlineInfo object if the address falls within this object. This avoids
97/// allocations by not appending child InlineInfo objects to the
98/// InlineInfo::Children array and also skips any InlineInfo objects that do
99/// not contain the address we are looking up.
100///
101/// \param Data The binary stream to read the data from.
102///
103/// \param Offset The byte offset within \a Data.
104///
105/// \param BaseAddr The address that the relative address range offsets are
106///                 relative to.
107
108static bool lookup(const GsymReader &GR, DataExtractor &Data, uint64_t &Offset,
109                   uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs,
110                   llvm::Error &Err) {
111  InlineInfo Inline;
112  Inline.Ranges.decode(Data, BaseAddr, Offset);
113  if (Inline.Ranges.empty())
114    return true;
115  // Check if the address is contained within the inline information, and if
116  // not, quickly skip this InlineInfo object and all its children.
117  if (!Inline.Ranges.contains(Addr)) {
118    skip(Data, Offset, true /* SkippedRanges */);
119    return false;
120  }
121
122  // The address range is contained within this InlineInfo, add the source
123  // location for this InlineInfo and any children that contain the address.
124  bool HasChildren = Data.getU8(&Offset) != 0;
125  Inline.Name = Data.getU32(&Offset);
126  Inline.CallFile = (uint32_t)Data.getULEB128(&Offset);
127  Inline.CallLine = (uint32_t)Data.getULEB128(&Offset);
128  if (HasChildren) {
129    // Child address ranges are encoded relative to the first address in the
130    // parent InlineInfo object.
131    const auto ChildBaseAddr = Inline.Ranges[0].Start;
132    bool Done = false;
133    while (!Done)
134      Done = lookup(GR, Data, Offset, ChildBaseAddr, Addr, SrcLocs, Err);
135  }
136
137  Optional<FileEntry> CallFile = GR.getFile(Inline.CallFile);
138  if (!CallFile) {
139    Err = createStringError(std::errc::invalid_argument,
140                            "failed to extract file[%" PRIu32 "]",
141                            Inline.CallFile);
142    return false;
143  }
144
145  if (CallFile->Dir || CallFile->Base) {
146    SourceLocation SrcLoc;
147    SrcLoc.Name = SrcLocs.back().Name;
148    SrcLoc.Offset = SrcLocs.back().Offset;
149    SrcLoc.Dir = GR.getString(CallFile->Dir);
150    SrcLoc.Base = GR.getString(CallFile->Base);
151    SrcLoc.Line = Inline.CallLine;
152    SrcLocs.back().Name = GR.getString(Inline.Name);
153    SrcLocs.back().Offset = Addr - Inline.Ranges[0].Start;
154    SrcLocs.push_back(SrcLoc);
155  }
156  return true;
157}
158
159llvm::Error InlineInfo::lookup(const GsymReader &GR, DataExtractor &Data,
160                               uint64_t BaseAddr, uint64_t Addr,
161                               SourceLocations &SrcLocs) {
162  // Call our recursive helper function starting at offset zero.
163  uint64_t Offset = 0;
164  llvm::Error Err = Error::success();
165  ::lookup(GR, Data, Offset, BaseAddr, Addr, SrcLocs, Err);
166  return Err;
167}
168
169/// Decode an InlineInfo in Data at the specified offset.
170///
171/// A local helper function to decode InlineInfo objects. This function is
172/// called recursively when parsing child InlineInfo objects.
173///
174/// \param Data The data extractor to decode from.
175/// \param Offset The offset within \a Data to decode from.
176/// \param BaseAddr The base address to use when decoding address ranges.
177/// \returns An InlineInfo or an error describing the issue that was
178/// encountered during decoding.
179static llvm::Expected<InlineInfo> decode(DataExtractor &Data, uint64_t &Offset,
180                                         uint64_t BaseAddr) {
181  InlineInfo Inline;
182  if (!Data.isValidOffset(Offset))
183    return createStringError(std::errc::io_error,
184        "0x%8.8" PRIx64 ": missing InlineInfo address ranges data", Offset);
185  Inline.Ranges.decode(Data, BaseAddr, Offset);
186  if (Inline.Ranges.empty())
187    return Inline;
188  if (!Data.isValidOffsetForDataOfSize(Offset, 1))
189    return createStringError(std::errc::io_error,
190        "0x%8.8" PRIx64 ": missing InlineInfo uint8_t indicating children",
191        Offset);
192  bool HasChildren = Data.getU8(&Offset) != 0;
193  if (!Data.isValidOffsetForDataOfSize(Offset, 4))
194    return createStringError(std::errc::io_error,
195        "0x%8.8" PRIx64 ": missing InlineInfo uint32_t for name", Offset);
196  Inline.Name = Data.getU32(&Offset);
197  if (!Data.isValidOffset(Offset))
198    return createStringError(std::errc::io_error,
199        "0x%8.8" PRIx64 ": missing ULEB128 for InlineInfo call file", Offset);
200  Inline.CallFile = (uint32_t)Data.getULEB128(&Offset);
201  if (!Data.isValidOffset(Offset))
202    return createStringError(std::errc::io_error,
203        "0x%8.8" PRIx64 ": missing ULEB128 for InlineInfo call line", Offset);
204  Inline.CallLine = (uint32_t)Data.getULEB128(&Offset);
205  if (HasChildren) {
206    // Child address ranges are encoded relative to the first address in the
207    // parent InlineInfo object.
208    const auto ChildBaseAddr = Inline.Ranges[0].Start;
209    while (true) {
210      llvm::Expected<InlineInfo> Child = decode(Data, Offset, ChildBaseAddr);
211      if (!Child)
212        return Child.takeError();
213      // InlineInfo with empty Ranges termintes a child sibling chain.
214      if (Child.get().Ranges.empty())
215        break;
216      Inline.Children.emplace_back(std::move(*Child));
217    }
218  }
219  return Inline;
220}
221
222llvm::Expected<InlineInfo> InlineInfo::decode(DataExtractor &Data,
223                                              uint64_t BaseAddr) {
224  uint64_t Offset = 0;
225  return ::decode(Data, Offset, BaseAddr);
226}
227
228llvm::Error InlineInfo::encode(FileWriter &O, uint64_t BaseAddr) const {
229  // Users must verify the InlineInfo is valid prior to calling this funtion.
230  // We don't want to emit any InlineInfo objects if they are not valid since
231  // it will waste space in the GSYM file.
232  if (!isValid())
233    return createStringError(std::errc::invalid_argument,
234                             "attempted to encode invalid InlineInfo object");
235  Ranges.encode(O, BaseAddr);
236  bool HasChildren = !Children.empty();
237  O.writeU8(HasChildren);
238  O.writeU32(Name);
239  O.writeULEB(CallFile);
240  O.writeULEB(CallLine);
241  if (HasChildren) {
242    // Child address ranges are encoded as relative to the first
243    // address in the Ranges for this object. This keeps the offsets
244    // small and allows for efficient encoding using ULEB offsets.
245    const uint64_t ChildBaseAddr = Ranges[0].Start;
246    for (const auto &Child : Children) {
247      // Make sure all child address ranges are contained in the parent address
248      // ranges.
249      for (const auto &ChildRange: Child.Ranges) {
250        if (!Ranges.contains(ChildRange))
251          return createStringError(std::errc::invalid_argument,
252                                   "child range not contained in parent");
253      }
254      llvm::Error Err = Child.encode(O, ChildBaseAddr);
255      if (Err)
256        return Err;
257    }
258
259    // Terminate child sibling chain by emitting a zero. This zero will cause
260    // the decodeAll() function above to return false and stop the decoding
261    // of child InlineInfo objects that are siblings.
262    O.writeULEB(0);
263  }
264  return Error::success();
265}
266