277 lines · cpp
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-exception6//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 else28 OS << ' ';29 OS << Range;30 }31 OS << " Name = " << HEX32(II.Name) << ", CallFile = " << II.CallFile32 << ", 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. Otherwise43 // we have found an inline call stack that we need to insert.44 if (II.Name != 0)45 InlineStack.insert(InlineStack.begin(), &II);46 for (const auto &Child : II.Children) {47 if (::getInlineStackHelper(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(*this, Addr, 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 InlineInfo66/// objects where the addres ranges isn't contained in the InlineInfo object67/// or its children. This avoids allocations by not appending child InlineInfo68/// 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) != 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 an96/// InlineInfo object if the address falls within this object. This avoids97/// allocations by not appending child InlineInfo objects to the98/// InlineInfo::Children array and also skips any InlineInfo objects that do99/// 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 are106/// 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(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 if116 // 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 source123 // 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 the130 // 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 std::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 is172/// 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 was178/// 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 decodeRanges(Inline.Ranges, 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 the207 // 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 since231 // 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 encodeRanges(Ranges, 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 first243 // address in the Ranges for this object. This keeps the offsets244 // 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 address248 // 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 cause260 // the decodeAll() function above to return false and stop the decoding261 // of child InlineInfo objects that are siblings.262 O.writeULEB(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(Child);271 return NumChildren;272}273 274bool InlineInfo::operator<(const InlineInfo &RHS) const {275 return GetTotalNumChildren(*this) < GetTotalNumChildren(RHS);276}277