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