Add encode and decode methods to InlineInfo and document encoding format to the GSYM file format

[clayborg]

Summary

The full GSYM patch started with: https://reviews.llvm.org/D53379

This patch adds the ability to encode and decode InlineInfo objects and adds test coverage.

[aprantl]

lib/DebugInfo/GSYM/InlineInfo.cpp

63

This returns a bool.. what does that mean?

84

and here the return value is ignored?

[clayborg]

lib/DebugInfo/GSYM/InlineInfo.cpp

63

returns true if a InlineInfo is successfully decoded. This is a static function that is called recursively from within this function. The while statement on line 74 uses the return value.

84

I will clear the InlineInfo if this returns false.

[clayborg]

• document arguments to "static bool decodeAll(...)" in InlineInfo.cpp
• If decodeAll() returns false, clear the InlineInfo

[aprantl]

lib/DebugInfo/GSYM/InlineInfo.cpp

101

This also seems weird. Why wouldn't decode() guarantee that it leaves the object in a consistent state? Why silently swallow the error?

Perhaps it would be cleaner if decode returned an expected<InlineInfo> object? Then you don't need a clear() method in the first place.

[clayborg]

lib/DebugInfo/GSYM/InlineInfo.cpp

98–101

We could leave it out as it was before. The decodeAll just returning a bool was for the recursion. It would actually be nice to have this fail with the data it was able to decode. Not sure what error we can really return besides "not enough data"?

[clayborg]

Don't clear the inline info when decodeAll returns false so that we can see what was actually decoded. Not sure how great of an error we can return other than "not enough data". I am open to suggestions?

[MaskRay]

lib/DebugInfo/GSYM/InlineInfo.cpp

103

Doesn't it need a few bytes to represent an empty Ranges? Or is it just unexpected to call encode on an empty Ranges (in this case an assert or llvm_unreachable might be better)

[clayborg]

lib/DebugInfo/GSYM/InlineInfo.cpp

102–103

I think you are correct in that we should avoid calling this function in this case and have the user verify the data is good since this data will eventually be in a blob in the GSYM file that won't make sense to encode it at all of the data is not valid as it will just waste file space.

[clayborg]

• use llvm_unreachable when encoding InlineInfo objects. We don't want them emitted into the GSYM file and taking up space if they aren't valid.
• improve comment about terminating child InlineInfo object siblings.

[JDevlieghere]

lib/DebugInfo/GSYM/InlineInfo.cpp

63

I think Adrian means that an llvm:Error might be a better fit. That way the error can propagate up.

86

This could be an early return.

113

This could be an early return.

[clayborg]

Added error handling to InlineInfo::encode and InlineInfo::decode with full testing.

For encoding return an error when we try to encode an invalid InlineInfo and when a child InlineInfo has an address range that isn't contained in the parent's address range. This will help detect clients that use bad debug info data to create GSYM InlineInfo objects ensure that they correctly construct valid InlineInfo hierarchies. Added the ability to check if an address range is contained within an AddressRanges object to support this feature.

For decoding detect when data is missing from the steam and report an error with the exact offset with an appropriate error message.

[aprantl]

Thanks for implementing the error handling! There is one more comment inline.

lib/DebugInfo/GSYM/InlineInfo.cpp

127

What's the advantage of having invalid InlineInfo objects? Could we just have whoever creates them return a a valid object or an error otherwise?

[MaskRay]

lib/DebugInfo/GSYM/Range.cpp

53 ↗

(On Diff #218136)

Did you intend to use It[-1].End twice?

I am not certain what this function intends to do, but
should it be return Range.End <= It[-1].End;?

[MaskRay]

lib/DebugInfo/GSYM/InlineInfo.cpp

149

if (llvm::Error E = ...)
  return E

(Avoid Error which is also a type name)

[clayborg]

lib/DebugInfo/GSYM/InlineInfo.cpp

127

InlineInfo objects will be created by converting debug info into these objects. So they start out default constructed and then get populated as we parse the attributes. Clients should ensure these objects are valid prior to adding them to a GSYM file or into another InlineInfo object.

[clayborg]

$ svn commit
Sending include/llvm/DebugInfo/GSYM/InlineInfo.h
Sending include/llvm/DebugInfo/GSYM/Range.h
Sending lib/DebugInfo/GSYM/InlineInfo.cpp
Sending lib/DebugInfo/GSYM/Range.cpp
Sending unittests/DebugInfo/GSYM/GSYMTest.cpp
Transmitting file data .....done
Committing transaction...
Committed revision 370936.

[MaskRay]

lib/DebugInfo/GSYM/Range.cpp

46 ↗

(On Diff #218136)

Do you know why it returns false if Range.size() == 0?

If I remove Range.size() == 0, the following test will break

EXPECT_FALSE(Ranges.contains(AddressRange(0x1000, 0x1000)));

[clayborg]

lib/DebugInfo/GSYM/Range.cpp

46 ↗

(On Diff #218136)

This is looking forward to the time when we convert debug info into GSYM. Many compilers will make the low PC and high PC the same for debug info that has been optimized out. Also, an address range with no size is not a valid address range, so it can't be contained inside of another.

include/llvm/DebugInfo/GSYM/InlineInfo.h

 /// that called this inline function. This allows us to unwind inline call
 /// stacks back to the inline or concrete function that called this
 /// function. Inlined functions contained in this function are stored in the
 /// "Children" variable. All address ranges must be sorted and all address
 /// ranges of all children must be contained in the ranges of this function.
 /// Any clients that encode information will need to ensure the ranges are
 /// all contined correctly or lookups could fail. Add ranges in these objects
 /// must be contained in the top level FunctionInfo address ranges as well.
+///
+/// ENCODING
+///
+/// When saved to disk, the inline info encodes all ranges to be relative to
+/// a parent address range. This will be the FunctionInfo's start address if
+/// the InlineInfo is directly contained in a FunctionInfo, or a the start
+/// address of the containing parent InlineInfo's first "Ranges" member. This
+/// allows address ranges to be efficiently encoded using ULEB128 encodings as
+/// we encode the offset and size of each range instead of full addresses. This
+/// also makes any encoded addresses easy to relocate as we just need to
+/// relocate the FunctionInfo's start address.
+///
+/// - The AddressRanges member "Ranges" is encoded using an approriate base
+///   address as described above.
+/// - UINT8 boolean value that specifies if the InlineInfo object has children.
+/// - UINT32 string table offset that points to the name of the inline
+///   function.
+/// - ULEB128 integer that specifies the file of the call site that called
+///   this function.
+/// - ULEB128 integer that specifies the source line of the call site that
+///   called this function.
+/// - if this object has children, enocode each child InlineInfo using the
+///   the first address range's start address as the base address.
+///
 struct InlineInfo {
 
   uint32_t Name; ///< String table offset in the string table.
   uint32_t CallFile; ///< 1 based file index in the file table.
   uint32_t CallLine; ///< Source line number.
   AddressRanges Ranges;
   std::vector<InlineInfo> Children;
   InlineInfo() : Name(0), CallFile(0), CallLine(0) {}
struct InlineInfo {
   /// and have the stack trace show the original call site from
   /// non-inlined code.
   ///
   /// \param Addr the address to lookup
   ///
   /// \returns optional vector of InlineInfo objects that describe the
   /// inline call stack for a given address, false otherwise.
   llvm::Optional<InlineArray> getInlineStack(uint64_t Addr) const;
+
+  /// Decode an InlineInfo object from a binary data stream.
+  ///
+  /// \param Data The binary stream to read the data from. This object must
+  /// have the data for the InlineInfo object starting at offset zero. The data
+  /// can contain more data than needed.
+  ///
+  /// \param BaseAddr The base address to use when decoding all address ranges.
+  /// This will be the FunctionInfo's start address if this object is directly
+  /// contained in a FunctionInfo object, or the start address of the first
+  /// address range in an InlineInfo object of this object is a child of
+  /// another InlineInfo object.
+  void decode(DataExtractor &Data, uint64_t BaseAddr);
+
+  /// Encode this InlineInfo object into FileWriter stream.
+  ///
+  /// \param O The binary stream to write the data to at the current file
+  /// position.
+  ///
+  /// \param BaseAddr The base address to use when encoding all address ranges.
+  /// This will be the FunctionInfo's start address if this object is directly
+  /// contained in a FunctionInfo object, or the start address of the first
+  /// address range in an InlineInfo object of this object is a child of
+  /// another InlineInfo object.
+  void encode(FileWriter &O, uint64_t BaseAddr) const;
 };
 
 inline bool operator==(const InlineInfo &LHS, const InlineInfo &RHS) {
   return LHS.Name == RHS.Name && LHS.CallFile == RHS.CallFile &&
          LHS.CallLine == RHS.CallLine && LHS.Ranges == RHS.Ranges &&
          LHS.Children == RHS.Children;
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const InlineInfo &FI);
 
 } // namespace gsym
 } // namespace llvm
 
 #endif // #ifndef LLVM_DEBUGINFO_GSYM_INLINEINFO_H

lib/DebugInfo/GSYM/InlineInfo.cpp

 //===- InlineInfo.cpp -------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/GSYM/FileEntry.h"
+#include "llvm/DebugInfo/GSYM/FileWriter.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) {

 }
 
 llvm::Optional<InlineInfo::InlineArray> InlineInfo::getInlineStack(uint64_t Addr) const {
   InlineArray Result;
   if (getInlineStackHelper(*this, Addr, Result))
     return Result;
   return llvm::None;
 }
+
+/// 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 Inline The InlineInfo object to decode into.
+/// \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.
+/// \return A boolean value that indicates wether to keep decoding. Child
+/// InlineInfo object sibling chains are terminated with an empty address
+/// range object and this return value is used by this function when making
+/// recursive calls to itself to indicate when to stop parsing a sibling
+/// chain.
+static bool decodeAll(InlineInfo &Inline, DataExtractor &Data,
+                      uint64_t &Offset, uint64_t BaseAddr) {
+  Inline.Ranges.decode(Data, BaseAddr, Offset);
+  if (Inline.Ranges.empty())
+    return false;
+  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) {
+    InlineInfo Child;
+    while (decodeAll(Child, Data, Offset, Inline.Ranges[0].Start)) {
+      Inline.Children.emplace_back(std::move(Child));
+      Child.clear();
+    }
+  }
+  return true;
+}
+
+void InlineInfo::decode(DataExtractor &Data, uint64_t BaseAddr) {
+  uint64_t Offset = 0;
+  if (!decodeAll(*this, Data, Offset, BaseAddr)) {
+    // If parsing failed, clear the object
+    clear();
+  }
+}
+
+void InlineInfo::encode(FileWriter &O, uint64_t BaseAddr) const {
+  if (Ranges.empty())
+    return;
+  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)
+      Child.encode(O, ChildBaseAddr);
+    // Terminate child sibling chain by emitting a zero for
+    O.writeULEB(0);
+  }
+}

unittests/DebugInfo/GSYM/GSYMTest.cpp

TEST(GSYMTest, TestInlineInfo) {
   ASSERT_EQ(InlineInfos->size(), 2u);
   ASSERT_EQ(*InlineInfos->at(0), Inline1Sub2);
   ASSERT_EQ(*InlineInfos->at(1), Inline1);
   InlineInfos = Root.getInlineStack(Inline1Sub2.Ranges[0].End - 1);
   EXPECT_TRUE(InlineInfos);
   ASSERT_EQ(InlineInfos->size(), 2u);
   ASSERT_EQ(*InlineInfos->at(0), Inline1Sub2);
   ASSERT_EQ(*InlineInfos->at(1), Inline1);
-}
+
+  // Test encoding and decoding InlineInfo objects
+  SmallString<512> Str;
+  raw_svector_ostream OutStrm(Str);
+  const auto ByteOrder = llvm::support::endian::system_endianness();
+  FileWriter FW(OutStrm, ByteOrder);
+  const uint64_t BaseAddr = Root.Ranges[0].Start;
+  Root.encode(FW, BaseAddr);
+  std::string Bytes(OutStrm.str());
+  uint8_t AddressSize = 4;
+  DataExtractor Data(Bytes, ByteOrder == llvm::support::little, AddressSize);
+  InlineInfo DecodedRoot;
+  DecodedRoot.decode(Data, BaseAddr);
+  EXPECT_EQ(Root, DecodedRoot);
+} 
 
 TEST(GSYMTest, TestLineEntry) {
   // test llvm::gsym::LineEntry structs.
   const uint64_t ValidAddr = 0x1000;
   const uint64_t InvalidFileIdx = 0;
   const uint32_t ValidFileIdx = 1;
   const uint32_t ValidLine = 5;