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