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