lib/DebugInfo/GSYM/InlineInfo.cpp - llvm-project/llvm - Git at Google

 //===- InlineInfo.cpp -------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//

 #include "llvm/DebugInfo/GSYM/FileEntry.h"
 #include "llvm/DebugInfo/GSYM/FileWriter.h"
 #include "llvm/DebugInfo/GSYM/GsymReader.h"
 #include "llvm/DebugInfo/GSYM/InlineInfo.h"
 #include "llvm/Support/DataExtractor.h"
 #include <algorithm>
 #include <inttypes.h>

 using namespace llvm;
 using namespace gsym;


 raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const InlineInfo &II) {
   if (!II.isValid())
     return OS;
   bool First = true;
   for (auto Range : II.Ranges) {
     if (First)
       First = false;
     else
       OS << ' ';
     OS << Range;
   }
   OS << " Name = " << HEX32(II.Name) << ", CallFile = " << II.CallFile
      << ", CallLine = " << II.CallFile << '\n';
   for (const auto &Child : II.Children)
     OS << Child;
   return OS;
 }

 static bool getInlineStackHelper(const InlineInfo &II, uint64_t Addr,
     std::vector<const InlineInfo *> &InlineStack) {
   if (II.Ranges.contains(Addr)) {
     // If this is the top level that represents the concrete function,
     // there will be no name and we shoud clear the inline stack. Otherwise
     // we have found an inline call stack that we need to insert.
     if (II.Name != 0)
       InlineStack.insert(InlineStack.begin(), &II);
     for (const auto &Child : II.Children) {
       if (::getInlineStackHelper(Child, Addr, InlineStack))
         break;
     }
     return !InlineStack.empty();
   }
   return false;
 }

 llvm::Optional<InlineInfo::InlineArray> InlineInfo::getInlineStack(uint64_t Addr) const {
   InlineArray Result;
   if (getInlineStackHelper(*this, Addr, Result))
     return Result;
   return llvm::None;
 }

 /// Skip an InlineInfo object in the specified data at the specified offset.
 ///
 /// Used during the InlineInfo::lookup() call to quickly skip child InlineInfo
 /// objects where the addres ranges isn't contained in the InlineInfo object
 /// or its children. This avoids allocations by not appending child InlineInfo
 /// objects to the InlineInfo::Children array.
 ///
 /// \param Data The binary stream to read the data from.
 ///
 /// \param Offset The byte offset within \a Data.
 ///
 /// \param SkippedRanges If true, address ranges have already been skipped.

 static bool skip(DataExtractor &Data, uint64_t &Offset, bool SkippedRanges) {
   if (!SkippedRanges) {
     if (AddressRanges::skip(Data, Offset) == 0)
       return false;
   }
   bool HasChildren = Data.getU8(&Offset) != 0;
   Data.getU32(&Offset); // Skip Inline.Name.
   Data.getULEB128(&Offset); // Skip Inline.CallFile.
   Data.getULEB128(&Offset); // Skip Inline.CallLine.
   if (HasChildren) {
     while (skip(Data, Offset, false /* SkippedRanges */))
       /* Do nothing */;
   }
   // We skipped a valid InlineInfo.
   return true;
 }

 /// A Lookup helper functions.
 ///
 /// Used during the InlineInfo::lookup() call to quickly only parse an
 /// InlineInfo object if the address falls within this object. This avoids
 /// allocations by not appending child InlineInfo objects to the
 /// InlineInfo::Children array and also skips any InlineInfo objects that do
 /// not contain the address we are looking up.
 ///
 /// \param Data The binary stream to read the data from.
 ///
 /// \param Offset The byte offset within \a Data.
 ///
 /// \param BaseAddr The address that the relative address range offsets are
 ///                 relative to.

 static bool lookup(const GsymReader &GR, DataExtractor &Data, uint64_t &Offset,
                    uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs,
                    llvm::Error &Err) {
   InlineInfo Inline;
   Inline.Ranges.decode(Data, BaseAddr, Offset);
   if (Inline.Ranges.empty())
     return true;
   // Check if the address is contained within the inline information, and if
   // not, quickly skip this InlineInfo object and all its children.
   if (!Inline.Ranges.contains(Addr)) {
     skip(Data, Offset, true /* SkippedRanges */);
     return false;
   }

   // The address range is contained within this InlineInfo, add the source
   // location for this InlineInfo and any children that contain the address.
   bool HasChildren = Data.getU8(&Offset) != 0;
   Inline.Name = Data.getU32(&Offset);
   Inline.CallFile = (uint32_t)Data.getULEB128(&Offset);
   Inline.CallLine = (uint32_t)Data.getULEB128(&Offset);
   if (HasChildren) {
     // Child address ranges are encoded relative to the first address in the
     // parent InlineInfo object.
     const auto ChildBaseAddr = Inline.Ranges[0].Start;
     bool Done = false;
     while (!Done)
       Done = lookup(GR, Data, Offset, ChildBaseAddr, Addr, SrcLocs, Err);
   }

   Optional<FileEntry> CallFile = GR.getFile(Inline.CallFile);
   if (!CallFile) {
     Err = createStringError(std::errc::invalid_argument,
                             "failed to extract file[%" PRIu32 "]",
                             Inline.CallFile);
     return false;
   }

   if (CallFile->Dir || CallFile->Base) {
     SourceLocation SrcLoc;
     SrcLoc.Name = SrcLocs.back().Name;
     SrcLoc.Offset = SrcLocs.back().Offset;
     SrcLoc.Dir = GR.getString(CallFile->Dir);
     SrcLoc.Base = GR.getString(CallFile->Base);
     SrcLoc.Line = Inline.CallLine;
     SrcLocs.back().Name = GR.getString(Inline.Name);
     SrcLocs.back().Offset = Addr - Inline.Ranges[0].Start;
     SrcLocs.push_back(SrcLoc);
   }
   return true;
 }

 llvm::Error InlineInfo::lookup(const GsymReader &GR, DataExtractor &Data,
                                uint64_t BaseAddr, uint64_t Addr,
                                SourceLocations &SrcLocs) {
   // Call our recursive helper function starting at offset zero.
   uint64_t Offset = 0;
   llvm::Error Err = Error::success();
   ::lookup(GR, Data, Offset, BaseAddr, Addr, SrcLocs, Err);
   return Err;
 }

 /// Decode an InlineInfo in Data at the specified offset.
 ///
 /// A local helper function to decode InlineInfo objects. This function is
 /// called recursively when parsing child InlineInfo objects.
 ///
 /// \param Data The data extractor to decode from.
 /// \param Offset The offset within \a Data to decode from.
 /// \param BaseAddr The base address to use when decoding address ranges.
 /// \returns An InlineInfo or an error describing the issue that was
 /// encountered during decoding.
 static llvm::Expected<InlineInfo> decode(DataExtractor &Data, uint64_t &Offset,
                                          uint64_t BaseAddr) {
   InlineInfo Inline;
   if (!Data.isValidOffset(Offset))
     return createStringError(std::errc::io_error,
         "0x%8.8" PRIx64 ": missing InlineInfo address ranges data", Offset);
   Inline.Ranges.decode(Data, BaseAddr, Offset);
   if (Inline.Ranges.empty())
     return Inline;
   if (!Data.isValidOffsetForDataOfSize(Offset, 1))
     return createStringError(std::errc::io_error,
         "0x%8.8" PRIx64 ": missing InlineInfo uint8_t indicating children",
         Offset);
   bool HasChildren = Data.getU8(&Offset) != 0;
   if (!Data.isValidOffsetForDataOfSize(Offset, 4))
     return createStringError(std::errc::io_error,
         "0x%8.8" PRIx64 ": missing InlineInfo uint32_t for name", Offset);
   Inline.Name = Data.getU32(&Offset);
   if (!Data.isValidOffset(Offset))
     return createStringError(std::errc::io_error,
         "0x%8.8" PRIx64 ": missing ULEB128 for InlineInfo call file", Offset);
   Inline.CallFile = (uint32_t)Data.getULEB128(&Offset);
   if (!Data.isValidOffset(Offset))
     return createStringError(std::errc::io_error,
         "0x%8.8" PRIx64 ": missing ULEB128 for InlineInfo call line", Offset);
   Inline.CallLine = (uint32_t)Data.getULEB128(&Offset);
   if (HasChildren) {
     // Child address ranges are encoded relative to the first address in the
     // parent InlineInfo object.
     const auto ChildBaseAddr = Inline.Ranges[0].Start;
     while (true) {
       llvm::Expected<InlineInfo> Child = decode(Data, Offset, ChildBaseAddr);
       if (!Child)
         return Child.takeError();
       // InlineInfo with empty Ranges termintes a child sibling chain.
       if (Child.get().Ranges.empty())
         break;
       Inline.Children.emplace_back(std::move(*Child));
     }
   }
   return Inline;
 }

 llvm::Expected<InlineInfo> InlineInfo::decode(DataExtractor &Data,
                                               uint64_t BaseAddr) {
   uint64_t Offset = 0;
   return ::decode(Data, Offset, BaseAddr);
 }

 llvm::Error InlineInfo::encode(FileWriter &O, uint64_t BaseAddr) const {
   // Users must verify the InlineInfo is valid prior to calling this funtion.
   // We don't want to emit any InlineInfo objects if they are not valid since
   // it will waste space in the GSYM file.
   if (!isValid())
     return createStringError(std::errc::invalid_argument,
                              "attempted to encode invalid InlineInfo object");
   Ranges.encode(O, BaseAddr);
   bool HasChildren = !Children.empty();
   O.writeU8(HasChildren);
   O.writeU32(Name);
   O.writeULEB(CallFile);
   O.writeULEB(CallLine);
   if (HasChildren) {
     // Child address ranges are encoded as relative to the first
     // address in the Ranges for this object. This keeps the offsets
     // small and allows for efficient encoding using ULEB offsets.
     const uint64_t ChildBaseAddr = Ranges[0].Start;
     for (const auto &Child : Children) {
       // Make sure all child address ranges are contained in the parent address
       // ranges.
       for (const auto &ChildRange: Child.Ranges) {
         if (!Ranges.contains(ChildRange))
           return createStringError(std::errc::invalid_argument,
                                    "child range not contained in parent");
       }
       llvm::Error Err = Child.encode(O, ChildBaseAddr);
       if (Err)
         return Err;
     }

     // Terminate child sibling chain by emitting a zero. This zero will cause
     // the decodeAll() function above to return false and stop the decoding
     // of child InlineInfo objects that are siblings.
     O.writeULEB(0);
   }
   return Error::success();
 }
	//===- InlineInfo.cpp -------------------------------------------- C++ --===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//

	#include "llvm/DebugInfo/GSYM/FileEntry.h"
	#include "llvm/DebugInfo/GSYM/FileWriter.h"
	#include "llvm/DebugInfo/GSYM/GsymReader.h"
	#include "llvm/DebugInfo/GSYM/InlineInfo.h"
	#include "llvm/Support/DataExtractor.h"
	#include <algorithm>
	#include <inttypes.h>

	using namespace llvm;
	using namespace gsym;


	raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const InlineInfo &II) {
	if (!II.isValid())
	return OS;
	bool First = true;
	for (auto Range : II.Ranges) {
	if (First)
	First = false;
	else
	OS << ' ';
	OS << Range;
	}
	OS << " Name = " << HEX32(II.Name) << ", CallFile = " << II.CallFile
	<< ", CallLine = " << II.CallFile << '\n';
	for (const auto &Child : II.Children)
	OS << Child;
	return OS;
	}

	static bool getInlineStackHelper(const InlineInfo &II, uint64_t Addr,
	std::vector<const InlineInfo *> &InlineStack) {
	if (II.Ranges.contains(Addr)) {
	// If this is the top level that represents the concrete function,
	// there will be no name and we shoud clear the inline stack. Otherwise
	// we have found an inline call stack that we need to insert.
	if (II.Name != 0)
	InlineStack.insert(InlineStack.begin(), &II);
	for (const auto &Child : II.Children) {
	if (::getInlineStackHelper(Child, Addr, InlineStack))
	break;
	}
	return !InlineStack.empty();
	}
	return false;
	}

	llvm::Optional<InlineInfo::InlineArray> InlineInfo::getInlineStack(uint64_t Addr) const {
	InlineArray Result;
	if (getInlineStackHelper(*this, Addr, Result))
	return Result;
	return llvm::None;
	}

	/// Skip an InlineInfo object in the specified data at the specified offset.
	///
	/// Used during the InlineInfo::lookup() call to quickly skip child InlineInfo
	/// objects where the addres ranges isn't contained in the InlineInfo object
	/// or its children. This avoids allocations by not appending child InlineInfo
	/// objects to the InlineInfo::Children array.
	///
	/// \param Data The binary stream to read the data from.
	///
	/// \param Offset The byte offset within \a Data.
	///
	/// \param SkippedRanges If true, address ranges have already been skipped.

	static bool skip(DataExtractor &Data, uint64_t &Offset, bool SkippedRanges) {
	if (!SkippedRanges) {
	if (AddressRanges::skip(Data, Offset) == 0)
	return false;
	}
	bool HasChildren = Data.getU8(&Offset) != 0;
	Data.getU32(&Offset); // Skip Inline.Name.
	Data.getULEB128(&Offset); // Skip Inline.CallFile.
	Data.getULEB128(&Offset); // Skip Inline.CallLine.
	if (HasChildren) {
	while (skip(Data, Offset, false /* SkippedRanges */))
	/* Do nothing */;
	}
	// We skipped a valid InlineInfo.
	return true;
	}

	/// A Lookup helper functions.
	///
	/// Used during the InlineInfo::lookup() call to quickly only parse an
	/// InlineInfo object if the address falls within this object. This avoids
	/// allocations by not appending child InlineInfo objects to the
	/// InlineInfo::Children array and also skips any InlineInfo objects that do
	/// not contain the address we are looking up.
	///
	/// \param Data The binary stream to read the data from.
	///
	/// \param Offset The byte offset within \a Data.
	///
	/// \param BaseAddr The address that the relative address range offsets are
	/// relative to.

	static bool lookup(const GsymReader &GR, DataExtractor &Data, uint64_t &Offset,
	uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs,
	llvm::Error &Err) {
	InlineInfo Inline;
	Inline.Ranges.decode(Data, BaseAddr, Offset);
	if (Inline.Ranges.empty())
	return true;
	// Check if the address is contained within the inline information, and if
	// not, quickly skip this InlineInfo object and all its children.
	if (!Inline.Ranges.contains(Addr)) {
	skip(Data, Offset, true /* SkippedRanges */);
	return false;
	}

	// The address range is contained within this InlineInfo, add the source
	// location for this InlineInfo and any children that contain the address.
	bool HasChildren = Data.getU8(&Offset) != 0;
	Inline.Name = Data.getU32(&Offset);
	Inline.CallFile = (uint32_t)Data.getULEB128(&Offset);
	Inline.CallLine = (uint32_t)Data.getULEB128(&Offset);
	if (HasChildren) {
	// Child address ranges are encoded relative to the first address in the
	// parent InlineInfo object.
	const auto ChildBaseAddr = Inline.Ranges[0].Start;
	bool Done = false;
	while (!Done)
	Done = lookup(GR, Data, Offset, ChildBaseAddr, Addr, SrcLocs, Err);
	}

	Optional<FileEntry> CallFile = GR.getFile(Inline.CallFile);
	if (!CallFile) {
	Err = createStringError(std::errc::invalid_argument,
	"failed to extract file[%" PRIu32 "]",
	Inline.CallFile);
	return false;
	}

	if (CallFile->Dir \|\| CallFile->Base) {
	SourceLocation SrcLoc;
	SrcLoc.Name = SrcLocs.back().Name;
	SrcLoc.Offset = SrcLocs.back().Offset;
	SrcLoc.Dir = GR.getString(CallFile->Dir);
	SrcLoc.Base = GR.getString(CallFile->Base);
	SrcLoc.Line = Inline.CallLine;
	SrcLocs.back().Name = GR.getString(Inline.Name);
	SrcLocs.back().Offset = Addr - Inline.Ranges[0].Start;
	SrcLocs.push_back(SrcLoc);
	}
	return true;
	}

	llvm::Error InlineInfo::lookup(const GsymReader &GR, DataExtractor &Data,
	uint64_t BaseAddr, uint64_t Addr,
	SourceLocations &SrcLocs) {
	// Call our recursive helper function starting at offset zero.
	uint64_t Offset = 0;
	llvm::Error Err = Error::success();
	::lookup(GR, Data, Offset, BaseAddr, Addr, SrcLocs, Err);
	return Err;
	}

	/// Decode an InlineInfo in Data at the specified offset.
	///
	/// A local helper function to decode InlineInfo objects. This function is
	/// called recursively when parsing child InlineInfo objects.
	///
	/// \param Data The data extractor to decode from.
	/// \param Offset The offset within \a Data to decode from.
	/// \param BaseAddr The base address to use when decoding address ranges.
	/// \returns An InlineInfo or an error describing the issue that was
	/// encountered during decoding.
	static llvm::Expected<InlineInfo> decode(DataExtractor &Data, uint64_t &Offset,
	uint64_t BaseAddr) {
	InlineInfo Inline;
	if (!Data.isValidOffset(Offset))
	return createStringError(std::errc::io_error,
	"0x%8.8" PRIx64 ": missing InlineInfo address ranges data", Offset);
	Inline.Ranges.decode(Data, BaseAddr, Offset);
	if (Inline.Ranges.empty())
	return Inline;
	if (!Data.isValidOffsetForDataOfSize(Offset, 1))
	return createStringError(std::errc::io_error,
	"0x%8.8" PRIx64 ": missing InlineInfo uint8_t indicating children",
	Offset);
	bool HasChildren = Data.getU8(&Offset) != 0;
	if (!Data.isValidOffsetForDataOfSize(Offset, 4))
	return createStringError(std::errc::io_error,
	"0x%8.8" PRIx64 ": missing InlineInfo uint32_t for name", Offset);
	Inline.Name = Data.getU32(&Offset);
	if (!Data.isValidOffset(Offset))
	return createStringError(std::errc::io_error,
	"0x%8.8" PRIx64 ": missing ULEB128 for InlineInfo call file", Offset);
	Inline.CallFile = (uint32_t)Data.getULEB128(&Offset);
	if (!Data.isValidOffset(Offset))
	return createStringError(std::errc::io_error,
	"0x%8.8" PRIx64 ": missing ULEB128 for InlineInfo call line", Offset);
	Inline.CallLine = (uint32_t)Data.getULEB128(&Offset);
	if (HasChildren) {
	// Child address ranges are encoded relative to the first address in the
	// parent InlineInfo object.
	const auto ChildBaseAddr = Inline.Ranges[0].Start;
	while (true) {
	llvm::Expected<InlineInfo> Child = decode(Data, Offset, ChildBaseAddr);
	if (!Child)
	return Child.takeError();
	// InlineInfo with empty Ranges termintes a child sibling chain.
	if (Child.get().Ranges.empty())
	break;
	Inline.Children.emplace_back(std::move(*Child));
	}
	}
	return Inline;
	}

	llvm::Expected<InlineInfo> InlineInfo::decode(DataExtractor &Data,
	uint64_t BaseAddr) {
	uint64_t Offset = 0;
	return ::decode(Data, Offset, BaseAddr);
	}

	llvm::Error InlineInfo::encode(FileWriter &O, uint64_t BaseAddr) const {
	// Users must verify the InlineInfo is valid prior to calling this funtion.
	// We don't want to emit any InlineInfo objects if they are not valid since
	// it will waste space in the GSYM file.
	if (!isValid())
	return createStringError(std::errc::invalid_argument,
	"attempted to encode invalid InlineInfo object");
	Ranges.encode(O, BaseAddr);
	bool HasChildren = !Children.empty();
	O.writeU8(HasChildren);
	O.writeU32(Name);
	O.writeULEB(CallFile);
	O.writeULEB(CallLine);
	if (HasChildren) {
	// Child address ranges are encoded as relative to the first
	// address in the Ranges for this object. This keeps the offsets
	// small and allows for efficient encoding using ULEB offsets.
	const uint64_t ChildBaseAddr = Ranges[0].Start;
	for (const auto &Child : Children) {
	// Make sure all child address ranges are contained in the parent address
	// ranges.
	for (const auto &ChildRange: Child.Ranges) {
	if (!Ranges.contains(ChildRange))
	return createStringError(std::errc::invalid_argument,
	"child range not contained in parent");
	}
	llvm::Error Err = Child.encode(O, ChildBaseAddr);
	if (Err)
	return Err;
	}

	// Terminate child sibling chain by emitting a zero. This zero will cause
	// the decodeAll() function above to return false and stop the decoding
	// of child InlineInfo objects that are siblings.
	O.writeULEB(0);
	}
	return Error::success();
	}