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/DebugInfo/GSYM/FileEntry.h"
11#include "llvm/DebugInfo/GSYM/FileWriter.h"
12#include "llvm/DebugInfo/GSYM/GsymReader.h"
13#include "llvm/Support/DataExtractor.h"
14#include <inttypes.h>
15
16using namespace llvm;
17using namespace gsym;
18
19
20raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const InlineInfo &II) {
21 if (!II.isValid())
22 return OS;
23 bool First = true;
24 for (auto Range : II.Ranges) {
25 if (First)
26 First = false;
27 else
28 OS << ' ';
29 OS << Range;
30 }
31 OS << " Name = " << HEX32(II.Name) << ", CallFile = " << II.CallFile
32 << ", CallLine = " << II.CallFile << '\n';
33 for (const auto &Child : II.Children)
34 OS << Child;
35 return OS;
36}
37
38static bool getInlineStackHelper(const InlineInfo &II, uint64_t Addr,
39 std::vector<const InlineInfo *> &InlineStack) {
40 if (II.Ranges.contains(Addr)) {
41 // If this is the top level that represents the concrete function,
42 // there will be no name and we shoud clear the inline stack. Otherwise
43 // we have found an inline call stack that we need to insert.
44 if (II.Name != 0)
45 InlineStack.insert(position: InlineStack.begin(), x: &II);
46 for (const auto &Child : II.Children) {
47 if (::getInlineStackHelper(II: Child, Addr, InlineStack))
48 break;
49 }
50 return !InlineStack.empty();
51 }
52 return false;
53}
54
55std::optional<InlineInfo::InlineArray>
56InlineInfo::getInlineStack(uint64_t Addr) const {
57 InlineArray Result;
58 if (getInlineStackHelper(II: *this, Addr, InlineStack&: Result))
59 return Result;
60 return std::nullopt;
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 (skipRanges(Data, Offset) == 0)
79 return false;
80 }
81 bool HasChildren = Data.getU8(offset_ptr: &Offset) != 0;
82 Data.getU32(offset_ptr: &Offset); // Skip Inline.Name.
83 Data.getULEB128(offset_ptr: &Offset); // Skip Inline.CallFile.
84 Data.getULEB128(offset_ptr: &Offset); // Skip Inline.CallLine.
85 if (HasChildren) {
86 while (skip(Data, Offset, SkippedRanges: 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 decodeRanges(Ranges&: Inline.Ranges, 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, SkippedRanges: 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_ptr: &Offset) != 0;
125 Inline.Name = Data.getU32(offset_ptr: &Offset);
126 Inline.CallFile = (uint32_t)Data.getULEB128(offset_ptr: &Offset);
127 Inline.CallLine = (uint32_t)Data.getULEB128(offset_ptr: &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, BaseAddr: ChildBaseAddr, Addr, SrcLocs, Err);
135 }
136
137 std::optional<FileEntry> CallFile = GR.getFile(Index: Inline.CallFile);
138 if (!CallFile) {
139 Err = createStringError(EC: std::errc::invalid_argument,
140 Fmt: "failed to extract file[%" PRIu32 "]",
141 Vals: 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(Offset: CallFile->Dir);
150 SrcLoc.Base = GR.getString(Offset: CallFile->Base);
151 SrcLoc.Line = Inline.CallLine;
152 SrcLocs.back().Name = GR.getString(Offset: Inline.Name);
153 SrcLocs.back().Offset = Addr - Inline.Ranges[0].start();
154 SrcLocs.push_back(x: 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: Offset))
183 return createStringError(EC: std::errc::io_error,
184 Fmt: "0x%8.8" PRIx64 ": missing InlineInfo address ranges data", Vals: Offset);
185 decodeRanges(Ranges&: Inline.Ranges, Data, BaseAddr, Offset);
186 if (Inline.Ranges.empty())
187 return Inline;
188 if (!Data.isValidOffsetForDataOfSize(offset: Offset, length: 1))
189 return createStringError(EC: std::errc::io_error,
190 Fmt: "0x%8.8" PRIx64 ": missing InlineInfo uint8_t indicating children",
191 Vals: Offset);
192 bool HasChildren = Data.getU8(offset_ptr: &Offset) != 0;
193 if (!Data.isValidOffsetForDataOfSize(offset: Offset, length: 4))
194 return createStringError(EC: std::errc::io_error,
195 Fmt: "0x%8.8" PRIx64 ": missing InlineInfo uint32_t for name", Vals: Offset);
196 Inline.Name = Data.getU32(offset_ptr: &Offset);
197 if (!Data.isValidOffset(offset: Offset))
198 return createStringError(EC: std::errc::io_error,
199 Fmt: "0x%8.8" PRIx64 ": missing ULEB128 for InlineInfo call file", Vals: Offset);
200 Inline.CallFile = (uint32_t)Data.getULEB128(offset_ptr: &Offset);
201 if (!Data.isValidOffset(offset: Offset))
202 return createStringError(EC: std::errc::io_error,
203 Fmt: "0x%8.8" PRIx64 ": missing ULEB128 for InlineInfo call line", Vals: Offset);
204 Inline.CallLine = (uint32_t)Data.getULEB128(offset_ptr: &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, BaseAddr: 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(args: 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(EC: std::errc::invalid_argument,
234 Fmt: "attempted to encode invalid InlineInfo object");
235 encodeRanges(Ranges, O, BaseAddr);
236 bool HasChildren = !Children.empty();
237 O.writeU8(Value: HasChildren);
238 O.writeU32(Value: Name);
239 O.writeULEB(Value: CallFile);
240 O.writeULEB(Value: 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(Range: ChildRange))
251 return createStringError(EC: std::errc::invalid_argument,
252 Fmt: "child range not contained in parent");
253 }
254 llvm::Error Err = Child.encode(O, BaseAddr: 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(Value: 0);
263 }
264 return Error::success();
265}
266
267static uint64_t GetTotalNumChildren(const InlineInfo &II) {
268 uint64_t NumChildren = II.Children.size();
269 for (const auto &Child : II.Children)
270 NumChildren += GetTotalNumChildren(II: Child);
271 return NumChildren;
272}
273
274bool InlineInfo::operator<(const InlineInfo &RHS) const {
275 return GetTotalNumChildren(II: *this) < GetTotalNumChildren(II: RHS);
276}
277