llvm/lib/DebugInfo/GSYM/InlineInfo.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-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
  17 using namespace llvm;
  18 using namespace gsym;
  19
  20
  21 raw_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
  39 static 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
  56 llvm::Optional<InlineInfo::InlineArray> InlineInfo::getInlineStack(uint64_t Addr) const {
  57   InlineArray Result;
  58   if (getInlineStackHelper(*this, Addr, Result))
  59     return Result;
  60   return llvm::None;
  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
  76 static bool skip(DataExtractor &Data, uint64_t &Offset, bool SkippedRanges) {
  77   if (!SkippedRanges) {
  78     if (AddressRanges::skip(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 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
 108 static 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   Inline.Ranges.decode(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, 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) != 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 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, ChildBaseAddr, Addr, SrcLocs, Err);
 135   }
 136
 137   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
 159 llvm::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.
 179 static 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   Inline.Ranges.decode(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 the
 207     // 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
 222 llvm::Expected<InlineInfo> InlineInfo::decode(DataExtractor &Data,
 223                                               uint64_t BaseAddr) {
 224   uint64_t Offset = 0;
 225   return ::decode(Data, Offset, BaseAddr);
 226 }
 227
 228 llvm::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(std::errc::invalid_argument,
 234                              "attempted to encode invalid InlineInfo object");
 235   Ranges.encode(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 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(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 cause
 260     // the decodeAll() function above to return false and stop the decoding
 261     // of child InlineInfo objects that are siblings.
 262     O.writeULEB(0);
 263   }
 264   return Error::success();
 265 }