Add lookup functions for efficient lookups of addresses when using GsymReader classes.

[clayborg]

Summary

Lookup functions are designed to not fully decode a FunctionInfo, LineTable or InlineInfo, they decode only what is needed into a LookupResult object. This allows lookups to avoid costly memory allocations and avoid parsing large amounts of information one a suitable match is found.

LookupResult objects contain the address that was looked up, the concrete function address range, the name of the concrete function, and a list of source locations. One for each inline function, and one for the concrete function. This allows one address to turn into multiple frames and improves the signal you get when symbolicating addresses in GSYM files.

[labath]

The code reads ok, given that I have very little knowledge of how gsym actually works. However, overall, I don't feel qualified to review patches in this area.

llvm/lib/DebugInfo/GSYM/InlineInfo.cpp

76–108

It looks like these functions should be static

llvm/unittests/DebugInfo/GSYM/GSYMTest.cpp

1353

So, if there's a bug here, then the entire test will just succeed? It looks like it would be better to ASSERT that this succeeded?

1356

ASSERT_THAT_EXPECTED(LR, Succeeded()) would be better as it would actually print the error message if it failed.

1373–1381

I'd consider defining operator== and << on SourceLocation and then writing this as EXPECT_THAT(LR->Locations, testing::ElementsAre(SourceLocation{"inline1", 10u, "/tmp", "foo.h"}, SourceLocation{"main", 6u, "/tmp", "main.c"}));

[aprantl]

The interfaces seem fine.

llvm/lib/DebugInfo/GSYM/LookupResult.cpp

6

wrong license again

[clayborg]

Fixed:

• Updates LLVM license
• Added gsym::SourceLocation operator==
• Added gsym::SourceLocation operator<< for raw_ostream
• Change gsym::LookupResult::dump to operator<< for raw_ostream
• Converted tests to use testing::ElementsAre to make tests easier to read

[clayborg]

llvm/unittests/DebugInfo/GSYM/GSYMTest.cpp

1353

This was a copy/paste error from older code updated it to match other tests.

[clayborg]

Change over to using ASSERT_THAT_EXPECTED(LR, Succeeded())

[stella.stamenova]

This broke the Windows LLDB Buildbot:

http://lab.llvm.org:8011/builders/lldb-x64-windows-ninja/builds/13723

It already had a test failure, so you probably didn't get the notification.

llvm/include/llvm/DebugInfo/GSYM/FunctionInfo.h

 //===- FunctionInfo.h -------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_GSYM_FUNCTIONINFO_H
 #define LLVM_DEBUGINFO_GSYM_FUNCTIONINFO_H
 
 #include "llvm/ADT/Optional.h"
 #include "llvm/DebugInfo/GSYM/InlineInfo.h"
 #include "llvm/DebugInfo/GSYM/LineTable.h"
+#include "llvm/DebugInfo/GSYM/LookupResult.h"
 #include "llvm/DebugInfo/GSYM/Range.h"
 #include "llvm/DebugInfo/GSYM/StringTable.h"
 #include <tuple>
 #include <vector>
 
 namespace llvm {
 class raw_ostream;
 namespace gsym {
 
+class GsymReader;
 /// Function information in GSYM files encodes information for one contiguous
 /// address range. If a function has discontiguous address ranges, they will
 /// need to be encoded using multiple FunctionInfo objects.
 ///
 /// ENCODING
 ///
 /// The function information gets the function start address as an argument
 /// to the FunctionInfo::decode(...) function. This information is calculated
struct FunctionInfo {
   ///
   /// \param O The binary stream to write the data to at the current file
   /// position.
   ///
   /// \returns An error object that indicates failure or the offset of the
   /// function info that was successfully written into the stream.
   llvm::Expected<uint64_t> encode(FileWriter &O) const;
 
+
+  /// Lookup an address within a FunctionInfo object's data stream.
+  ///
+  /// Instead of decoding an entire FunctionInfo object when doing lookups,
+  /// we can decode only the information we need from the FunctionInfo's data
+  /// for the specific address. The lookup result information is returned as
+  /// a LookupResult.
+  ///
+  /// \param Data The binary stream to read the data from. This object must
+  /// have the data for the object starting at offset zero. The data
+  /// can contain more data than needed.
+  ///
+  /// \param GR The GSYM reader that contains the string and file table that
+  /// will be used to fill in information in the returned result.
+  ///
+  /// \param FuncAddr The function start address decoded from the GsymReader.
+  ///
+  /// \param Addr The address to lookup.
+  ///
+  /// \returns An LookupResult or an error describing the issue that was
+  /// encountered during decoding. An error should only be returned if the
+  /// address is not contained in the FunctionInfo or if the data is corrupted.
+  static llvm::Expected<LookupResult> lookup(DataExtractor &Data,
+                                             const GsymReader &GR,
+                                             uint64_t FuncAddr,
+                                             uint64_t Addr);
+
   uint64_t startAddress() const { return Range.Start; }
   uint64_t endAddress() const { return Range.End; }
   uint64_t size() const { return Range.size(); }
   void setStartAddress(uint64_t Addr) { Range.Start = Addr; }
   void setEndAddress(uint64_t Addr) { Range.End = Addr; }
   void setSize(uint64_t Size) { Range.End = Range.Start + Size; }
 
   void clear() {

llvm/include/llvm/DebugInfo/GSYM/GsymReader.h

 //===- GsymReader.h ---------------------------------------------*- C++ -*-===//
 //
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_GSYM_GSYMREADER_H
 #define LLVM_DEBUGINFO_GSYM_GSYMREADER_H
 
 
 #include "llvm/ADT/ArrayRef.h"
public:
   static llvm::Expected<GsymReader> copyBuffer(StringRef Bytes);
 
   /// Access the GSYM header.
   /// \returns A native endian version of the GSYM header.
   const Header &getHeader() const;
 
   /// Get the full function info for an address.
   ///
+  /// This should be called when a client will store a copy of the complete
+  /// FunctionInfo for a given address. For one off lookups, use the lookup()
+  /// function below.
+  ///
+  /// Symbolication server processes might want to parse the entire function
+  /// info for a given address and cache it if the process stays around to
+  /// service many symbolication addresses, like for parsing profiling
+  /// information.
+  ///
   /// \param Addr A virtual address from the orignal object file to lookup.
+  ///
   /// \returns An expected FunctionInfo that contains the function info object
   /// or an error object that indicates reason for failing to lookup the
-  /// address,
+  /// address.
   llvm::Expected<FunctionInfo> getFunctionInfo(uint64_t Addr) const;
 
+  /// Lookup an address in the a GSYM.
+  ///
+  /// Lookup just the information needed for a specific address \a Addr. This
+  /// function is faster that calling getFunctionInfo() as it will only return
+  /// information that pertains to \a Addr and allows the parsing to skip any
+  /// extra information encoded for other addresses. For example the line table
+  /// parsing can stop when a matching LineEntry has been fouhnd, and the
+  /// InlineInfo can stop parsing early once a match has been found and also
+  /// skip information that doesn't match. This avoids memory allocations and
+  /// is much faster for lookups.
+  ///
+  /// \param Addr A virtual address from the orignal object file to lookup.
+  /// \returns An expected LookupResult that contains only the information
+  /// needed for the current address, or an error object that indicates reason
+  /// for failing to lookup the address.
+  llvm::Expected<LookupResult> lookup(uint64_t Addr) const;
+
   /// Get a string from the string table.
   ///
   /// \param Offset The string table offset for the string to retrieve.
   /// \returns The string from the strin table.
   StringRef getString(uint32_t Offset) const { return StrTab[Offset]; }
 
-protected:
-  /// Gets an address from the address table.
-  ///
-  /// Addresses are stored as offsets frrom the gsym::Header::BaseAddress.
-  ///
-  /// \param Index A index into the address table.
-  /// \returns A resolved virtual address for adddress in the address table
-  /// or llvm::None if Index is out of bounds.
-  Optional<uint64_t> getAddress(size_t Index) const;
-
   /// Get the a file entry for the suppplied file index.
   ///
   /// Used to convert any file indexes in the FunctionInfo data back into
   /// files. This function can be used for iteration, but is more commonly used
   /// for random access when doing lookups.
   ///
   /// \param Index An index into the file table.
   /// \returns An optional FileInfo that will be valid if the file index is
   /// valid, or llvm::None if the file index is out of bounds,
   Optional<FileEntry> getFile(uint32_t Index) const {
     if (Index < Files.size())
       return Files[Index];
     return llvm::None;
   }
 
+protected:
+  /// Gets an address from the address table.
+  ///
+  /// Addresses are stored as offsets frrom the gsym::Header::BaseAddress.
+  ///
+  /// \param Index A index into the address table.
+  /// \returns A resolved virtual address for adddress in the address table
+  /// or llvm::None if Index is out of bounds.
+  Optional<uint64_t> getAddress(size_t Index) const;
+
   /// Get an appropriate address info offsets array.
   ///
   /// The address table in the GSYM file is stored as array of 1, 2, 4 or 8
   /// byte offsets from the The gsym::Header::BaseAddress. The table is stored
   /// internally as a array of bytes that are in the correct endianness. When
   /// we access this table we must get an array that matches those sizes. This
   /// templatized helper function is used when accessing address offsets in the
   /// AddrOffsets member variable.

llvm/include/llvm/DebugInfo/GSYM/InlineInfo.h

 //===- InlineInfo.h ---------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_GSYM_INLINEINFO_H
 #define LLVM_DEBUGINFO_GSYM_INLINEINFO_H
 
 #include "llvm/ADT/Optional.h"
+#include "llvm/DebugInfo/GSYM/LineEntry.h"
+#include "llvm/DebugInfo/GSYM/LookupResult.h"
 #include "llvm/DebugInfo/GSYM/Range.h"
 #include "llvm/Support/Error.h"
 #include <stdint.h>
 #include <vector>
 
 
 namespace llvm {
 class raw_ostream;
 
 namespace gsym {
 
+class GsymReader;
 /// Inline information stores the name of the inline function along with
 /// an array of address ranges. It also stores the call file and call line
 /// 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
void clear() {
     CallLine = 0;
     Ranges.clear();
     Children.clear();
   }
   bool isValid() const { return !Ranges.empty(); }
 
   using InlineArray = std::vector<const InlineInfo *>;
 
+  /// Lookup a single address within the inline info data.
+  ///
+  /// Clients have the option to decode an entire InlineInfo object (using
+  /// InlineInfo::decode() ) or just find the matching inline info using this
+  /// function. The benefit of using this function is that only the information
+  /// needed for the lookup will be extracted, other info can be skipped and
+  /// parsing can stop as soon as the deepest match is found. This allows
+  /// symbolication tools to be fast and efficient and avoid allocation costs
+  /// when doing lookups.
+  ///
+  /// This function will augment the SourceLocations array \a SrcLocs with any
+  /// inline information that pertains to \a Addr. If no inline information
+  /// exists for \a Addr, then \a SrcLocs will be left untouched. If there is
+  /// inline information for \a Addr, then \a SrcLocs will be modifiied to
+  /// contain the deepest most inline function's SourceLocation at index zero
+  /// in the array and proceed up the the concrete function source file and
+  /// line at the end of the array.
+  ///
+  /// \param GR The GSYM reader that contains the string and file table that
+  /// will be used to fill in the source locations.
+  ///
+  /// \param Data The binary stream to read the data from. This object must
+  /// have the data for the LineTable object starting at offset zero. The data
+  /// can contain more data than needed.
+  ///
+  /// \param BaseAddr The base address to use when decoding the line table.
+  /// This will be the FunctionInfo's start address and will be used to
+  /// decode the correct addresses for the inline information.
+  ///
+  /// \param Addr The address to lookup.
+  ///
+  /// \param SrcLocs The inline source locations that matches \a Addr. This
+  ///                array must be initialized with the matching line entry
+  ///                from the line table upon entry. The name of the concrete
+  ///                function must be supplied since it will get pushed to
+  ///                the last SourceLocation entry and the inline information
+  ///                will fill in the source file and line from the inline
+  ///                information.
+  ///
+  /// \returns An error if the inline information is corrupt, or
+  ///          Error::success() for all other cases, even when no information
+  ///          is added to \a SrcLocs.
+  static llvm::Error lookup(const GsymReader &GR, DataExtractor &Data,
+                            uint64_t BaseAddr, uint64_t Addr,
+                            SourceLocations &SrcLocs);
+
   /// Lookup an address in the InlineInfo object
   ///
   /// This function is used to symbolicate an inline call stack and can
   /// turn one address in the program into one or more inline call stacks
   /// and have the stack trace show the original call site from
   /// non-inlined code.
   ///
   /// \param Addr the address to lookup

llvm/include/llvm/DebugInfo/GSYM/LineTable.h

 ///
 /// Opcodes that will push "Row" onto the LineEntry.Lines include the
 /// LTOC_AdvancePC opcode and all special opcodes. All other opcodes
 /// only modify the current "Row", or cause the line table to end.
 class LineTable {
   typedef std::vector<gsym::LineEntry> Collection;
   Collection Lines; ///< All line entries in the line table.
 public:
-  static LineEntry lookup(DataExtractor &Data, uint64_t BaseAddr,
+  /// Lookup a single address within a line table's data.
+  ///
+  /// Clients have the option to decode an entire line table using
+  /// LineTable::decode() or just find a single matching entry using this
+  /// function. The benefit of using this function is that parsed LineEntry
+  /// objects that do not match will not be stored in an array. This will avoid
+  /// memory allocation costs and parsing can stop once a match has been found.
+  ///
+  /// \param Data The binary stream to read the data from. This object must
+  /// have the data for the LineTable object starting at offset zero. The data
+  /// can contain more data than needed.
+  ///
+  /// \param BaseAddr The base address to use when decoding the line table.
+  /// This will be the FunctionInfo's start address and will be used to
+  /// initialize the line table row prior to parsing any opcodes.
+  ///
+  /// \returns An LineEntry object if a match is found, error otherwise.
+  static Expected<LineEntry> lookup(DataExtractor &Data, uint64_t BaseAddr,
                                     uint64_t Addr);
 
   /// Decode an LineTable object from a binary data stream.
   ///
   /// \param Data The binary stream to read the data from. This object must
   /// have the data for the LineTable object starting at offset zero. The data
   /// can contain more data than needed.
   ///
   /// \param BaseAddr The base address to use when decoding the line table.

llvm/include/llvm/DebugInfo/GSYM/LookupResult.h

+//===- LookupResult.h -------------------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_GSYM_LOOKUPRESULT_H
+#define LLVM_DEBUGINFO_GSYM_LOOKUPRESULT_H
+
+#include "llvm/DebugInfo/GSYM/Range.h"
+#include "llvm/ADT/StringRef.h"
+#include <inttypes.h>
+#include <vector>
+
+namespace llvm {
+class raw_ostream;
+namespace gsym {
+struct FileEntry;
+
+struct SourceLocation {
+  StringRef Name; ///< Function or symbol name.
+  StringRef Dir; ///< Line entry source file directory path.
+  StringRef Base; ///< Line entry source file basename.
+  uint32_t Line = 0; ///< Source file line number.
+};
+
+inline bool operator==(const SourceLocation &LHS, const SourceLocation &RHS) {
+  return LHS.Name == RHS.Name && LHS.Dir == RHS.Dir &&
+         LHS.Base == RHS.Base && LHS.Line == RHS.Line;
+}
+
+raw_ostream &operator<<(raw_ostream &OS, const SourceLocation &R);
+
+using SourceLocations = std::vector<SourceLocation>;
+
+
+struct LookupResult {
+  uint64_t LookupAddr = 0; ///< The address that this lookup pertains to.
+  AddressRange FuncRange; ///< The concrete function address range.
+  StringRef FuncName; ///< The concrete function name that contains LookupAddr.
+  /// The source locations that match this address. This information will only
+  /// be filled in if the FunctionInfo contains a line table. If an address is
+  /// for a concrete function with no inlined functions, this array will have
+  /// one entry. If an address points to an inline function, there will be one
+  /// SourceLocation for each inlined function with the last entry pointing to
+  /// the concrete function itself. This allows one address to generate
+  /// multiple locations and allows unwinding of inline call stacks. The
+  /// deepest inline function will appear at index zero in the source locations
+  /// array, and the concrete function will appear at the end of the array.
+  SourceLocations Locations;
+  std::string getSourceFile(uint32_t Index) const;
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const LookupResult &R);
+
+} // namespace gsym
+} // namespace llvm
+
+#endif // #ifndef LLVM_DEBUGINFO_GSYM_LOOKUPRESULT_H

llvm/include/llvm/DebugInfo/GSYM/Range.h

struct AddressRange {
   /// 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
   /// encoded addresses easy to relocate as we just need to relocate one base
   /// address.
   /// @{
   void decode(DataExtractor &Data, uint64_t BaseAddr, uint64_t &Offset);
   void encode(FileWriter &O, uint64_t BaseAddr) const;
   /// @}
+
+  /// Skip an address range object in the specified data a the specified
+  /// offset.
+  ///
+  /// \param Data The binary stream to read the data from.
+  ///
+  /// \param Offset The byte offset within \a Data.
+  static void skip(DataExtractor &Data, uint64_t &Offset);
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const AddressRange &R);
 
 /// The AddressRanges class helps normalize address range collections.
 /// This class keeps a sorted vector of AddressRange objects and can perform
 /// insertions and searches efficiently. The address ranges are always sorted
 /// and never contain any invalid or empty address ranges. This allows us to
public:
 
   /// Address ranges are decoded and encoded to be relative to a base address.
   /// See the AddressRange comment for the encode and decode methods for full
   /// details.
   /// @{
   void decode(DataExtractor &Data, uint64_t BaseAddr, uint64_t &Offset);
   void encode(FileWriter &O, uint64_t BaseAddr) const;
   /// @}
+
+  /// Skip an address range object in the specified data a the specified
+  /// offset.
+  ///
+  /// \param Data The binary stream to read the data from.
+  ///
+  /// \param Offset The byte offset within \a Data.
+  ///
+  /// \returns The number of address ranges that were skipped.
+  static uint64_t skip(DataExtractor &Data, uint64_t &Offset);
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const AddressRanges &AR);
 
 } // namespace gsym
 } // namespace llvm
 
 #endif // #ifndef LLVM_DEBUGINFO_GSYM_RANGE_H

llvm/lib/DebugInfo/GSYM/CMakeLists.txt

 add_llvm_component_library(LLVMDebugInfoGSYM
   Header.cpp
   FileWriter.cpp
   FunctionInfo.cpp
   GsymCreator.cpp
   GsymReader.cpp
   InlineInfo.cpp
   LineTable.cpp
+  LookupResult.cpp
   Range.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/DebugInfo/GSYM
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/DebugInfo
 
   DEPENDS
   LLVMMC
   )

llvm/lib/DebugInfo/GSYM/FunctionInfo.cpp

 //===- FunctionInfo.cpp ---------------------------------------------------===//
 //
 // 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/FunctionInfo.h"
 #include "llvm/DebugInfo/GSYM/FileWriter.h"
+#include "llvm/DebugInfo/GSYM/GsymReader.h"
 #include "llvm/DebugInfo/GSYM/LineTable.h"
 #include "llvm/DebugInfo/GSYM/InlineInfo.h"
 #include "llvm/Support/DataExtractor.h"
 
 using namespace llvm;
 using namespace gsym;
 
 /// FunctionInfo information type that is used to encode the optional data
if (Inline.hasValue()) {
     O.fixup32(static_cast<uint32_t>(Length), StartOffset - 4);
   }
 
   // Terminate the data chunks with and end of list with zero size
   O.writeU32(InfoType::EndOfList);
   O.writeU32(0);
   return FuncInfoOffset;
 }
+
+
+llvm::Expected<LookupResult> FunctionInfo::lookup(DataExtractor &Data,
+                                                  const GsymReader &GR,
+                                                  uint64_t FuncAddr,
+                                                  uint64_t Addr) {
+  LookupResult LR;
+  LR.LookupAddr = Addr;
+  LR.FuncRange.Start = FuncAddr;
+  uint64_t Offset = 0;
+  LR.FuncRange.End = FuncAddr + Data.getU32(&Offset);
+  uint32_t NameOffset = Data.getU32(&Offset);
+  // The "lookup" functions doesn't report errors as accurately as the "decode"
+  // function as it is meant to be fast. For more accurage errors we could call
+  // "decode".
+  if (!Data.isValidOffset(Offset))
+    return createStringError(std::errc::io_error,
+                              "FunctionInfo data is truncated");
+  // This function will be called with the result of a binary search of the
+  // address table, we must still make sure the address does not fall into a
+  // gap between functions are after the last function.
+  if (Addr >= LR.FuncRange.End)
+    return createStringError(std::errc::io_error,
+        "address 0x%" PRIx64 " is not in GSYM", Addr);
+
+  if (NameOffset == 0)
+    return createStringError(std::errc::io_error,
+        "0x%8.8" PRIx64 ": invalid FunctionInfo Name value 0x00000000",
+        Offset - 4);
+  LR.FuncName = GR.getString(NameOffset);
+  bool Done = false;
+  Optional<LineEntry> LineEntry;
+  Optional<DataExtractor> InlineInfoData;
+  while (!Done) {
+    if (!Data.isValidOffsetForDataOfSize(Offset, 8))
+      return createStringError(std::errc::io_error,
+                               "FunctionInfo data is truncated");
+    const uint32_t InfoType = Data.getU32(&Offset);
+    const uint32_t InfoLength = Data.getU32(&Offset);
+    const StringRef InfoBytes = Data.getData().substr(Offset, InfoLength);
+    if (InfoLength != InfoBytes.size())
+      return createStringError(std::errc::io_error,
+                               "FunctionInfo data is truncated");
+    DataExtractor InfoData(InfoBytes, Data.isLittleEndian(),
+                           Data.getAddressSize());
+    switch (InfoType) {
+      case InfoType::EndOfList:
+        Done = true;
+        break;
+
+      case InfoType::LineTableInfo:
+        if (auto ExpectedLE = LineTable::lookup(InfoData, FuncAddr, Addr))
+          LineEntry = ExpectedLE.get();
+        else
+          return ExpectedLE.takeError();
+        break;
+
+      case InfoType::InlineInfo:
+        // We will parse the inline info after our line table, but only if
+        // we have a line entry.
+        InlineInfoData = InfoData;
+        break;
+
+      default:
+        break;
+    }
+    Offset += InfoLength;
+  }
+
+  if (!LineEntry) {
+    // We don't have a valid line entry for our address, fill in our source
+    // location as best we can and return.
+    SourceLocation SrcLoc;
+    SrcLoc.Name = LR.FuncName;
+    LR.Locations.push_back(SrcLoc);
+    return LR;
+  }
+
+  Optional<FileEntry> LineEntryFile = GR.getFile(LineEntry->File);
+  if (!LineEntryFile)
+    return createStringError(std::errc::invalid_argument,
+                              "failed to extract file[%" PRIu32 "]",
+                              LineEntry->File);
+
+  SourceLocation SrcLoc;
+  SrcLoc.Name = LR.FuncName;
+  SrcLoc.Dir = GR.getString(LineEntryFile->Dir);
+  SrcLoc.Base = GR.getString(LineEntryFile->Base);
+  SrcLoc.Line = LineEntry->Line;
+  LR.Locations.push_back(SrcLoc);
+  // If we don't have inline information, we are done.
+  if (!InlineInfoData)
+    return LR;
+  // We have inline information. Try to augment the lookup result with this
+  // data.
+  llvm::Error Err = InlineInfo::lookup(GR, *InlineInfoData, FuncAddr, Addr,
+                                       LR.Locations);
+  if (Err)
+    return std::move(Err);
+  return LR;
+}

llvm/lib/DebugInfo/GSYM/GsymReader.cpp

 //===- GsymReader.cpp -----------------------------------------------------===//
 //
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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/GsymReader.h"
 
 #include <assert.h>
 #include <inttypes.h>
 #include <stdio.h>
if (ExpectedFI) {
       return createStringError(std::errc::invalid_argument,
                                 "address 0x%" PRIx64 " not in GSYM", Addr);
     }
   }
   return createStringError(std::errc::invalid_argument,
                            "failed to extract address[%" PRIu64 "]",
                            *AddressIndex);
 }
+
+llvm::Expected<LookupResult> GsymReader::lookup(uint64_t Addr) const {
+  Expected<uint64_t> AddressIndex = getAddressIndex(Addr);
+  if (!AddressIndex)
+    return AddressIndex.takeError();
+  // Address info offsets size should have been checked in parse().
+  assert(*AddressIndex < AddrInfoOffsets.size());
+  auto AddrInfoOffset = AddrInfoOffsets[*AddressIndex];
+  DataExtractor Data(MemBuffer->getBuffer().substr(AddrInfoOffset), Endian, 4);
+  if (Optional<uint64_t> OptAddr = getAddress(*AddressIndex))
+    return FunctionInfo::lookup(Data, *this, *OptAddr, Addr);
+  return createStringError(std::errc::invalid_argument,
+                           "failed to extract address[%" PRIu64 "]",
+                           *AddressIndex);
+}

llvm/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.
+// 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;
 

 
 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;
+  }
+
+  SourceLocation SrcLoc;
+  SrcLoc.Name = SrcLocs.back().Name;
+  SrcLoc.Dir = GR.getString(CallFile->Dir);
+  SrcLoc.Base = GR.getString(CallFile->Base);
+  SrcLoc.Line = Inline.CallLine;
+  SrcLocs.back().Name = GR.getString(Inline.Name);
+  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.

llvm/lib/DebugInfo/GSYM/LineTable.cpp

llvm::Expected<LineTable> LineTable::decode(DataExtractor &Data,
   });
   if (Err)
     return std::move(Err);
   return LT;
 }
 // Parse the line table on the fly and find the row we are looking for.
 // We will need to determine if we need to cache the line table by calling
 // LineTable::parseAllEntries(...) or just call this function each time.
-// There is a CPU vs memory tradeoff we will need to determine.
-LineEntry LineTable::lookup(DataExtractor &Data, uint64_t BaseAddr, uint64_t Addr) {
+// There is a CPU vs memory tradeoff we will need to determined.
+Expected<LineEntry> LineTable::lookup(DataExtractor &Data, uint64_t BaseAddr, uint64_t Addr) {
   LineEntry Result;
   llvm::Error Err = parse(Data, BaseAddr,
                           [Addr, &Result](const LineEntry &Row) -> bool {
     if (Addr < Row.Addr)
       return false; // Stop parsing, result contains the line table row!
     Result = Row;
     if (Addr == Row.Addr) {
       // Stop parsing, this is the row we are looking for since the address
       // matches.
       return false;
     }
     return true; // Keep parsing till we find the right row.
   });
+  if (Err)
+    return std::move(Err);
+  if (Result.isValid())
     return Result;
+  return createStringError(std::errc::invalid_argument,
+                           "address 0x%" PRIx64 " is not in the line table",
+                           Addr);
 }
 
 raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const LineTable &LT) {
   for (const auto &LineEntry : LT)
     OS << LineEntry << '\n';
   return OS;
 }

llvm/lib/DebugInfo/GSYM/LookupResult.cpp

+//===- LookupResult.cpp -------------------------------------------------*-===//
+//
+// 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/LookupResult.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+using namespace gsym;
+
+std::string LookupResult::getSourceFile(uint32_t Index) const {
+  std::string Fullpath;
+  if (Index < Locations.size()) {
+    if (!Locations[Index].Dir.empty()) {
+      if (Locations[Index].Base.empty()) {
+        Fullpath = Locations[Index].Dir;
+      } else {
+        llvm::SmallString<64> Storage;
+        llvm::sys::path::append(Storage, Locations[Index].Dir,
+                                Locations[Index].Base);
+        Fullpath.assign(Storage.begin(), Storage.end());
+      }
+    } else if (!Locations[Index].Base.empty())
+      Fullpath = Locations[Index].Base;
+  }
+  return Fullpath;
+}
+
+raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const SourceLocation &SL) {
+  OS << SL.Name << " @ ";
+  if (!SL.Dir.empty()) {
+    OS << SL.Dir;
+    if (SL.Dir.contains('\\') and not SL.Dir.contains('/'))
+      OS << '\\';
+    else
+      OS << '/';
+  }
+  if (SL.Base.empty())
+    OS << "<invalid-file>";
+  else
+    OS << SL.Base;
+  OS << ':' << SL.Line;
+  return OS;
+}
+
+raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const LookupResult &LR) {
+  OS << HEX64(LR.LookupAddr) << ": ";
+  auto NumLocations = LR.Locations.size();
+  for (size_t I = 0; I < NumLocations; ++I) {
+    if (I > 0) {
+      OS << '\n';
+      OS.indent(20);
+    }
+    const bool IsInlined = I + 1 != NumLocations;
+    OS << LR.Locations[I];
+    if (IsInlined)
+      OS << " [inlined]";
+  }
+  OS << '\n';
+  return OS;
+}

llvm/lib/DebugInfo/GSYM/Range.cpp

void AddressRanges::decode(DataExtractor &Data, uint64_t BaseAddr,
   clear();
   uint64_t NumRanges = Data.getULEB128(&Offset);
   if (NumRanges == 0)
     return;
   Ranges.resize(NumRanges);
   for (auto &Range : Ranges)
     Range.decode(Data, BaseAddr, Offset);
 }
+
+void AddressRange::skip(DataExtractor &Data, uint64_t &Offset) {
+  Data.getULEB128(&Offset);
+  Data.getULEB128(&Offset);
+}
+
+uint64_t AddressRanges::skip(DataExtractor &Data, uint64_t &Offset) {
+  uint64_t NumRanges = Data.getULEB128(&Offset);
+  for (uint64_t I=0; I<NumRanges; ++I)
+    AddressRange::skip(Data, Offset);
+  return NumRanges;
+}

llvm/unittests/DebugInfo/GSYM/GSYMTest.cpp

 #include "llvm/DebugInfo/GSYM/FunctionInfo.h"
 #include "llvm/DebugInfo/GSYM/GsymCreator.h"
 #include "llvm/DebugInfo/GSYM/GsymReader.h"
 #include "llvm/DebugInfo/GSYM/InlineInfo.h"
 #include "llvm/DebugInfo/GSYM/Range.h"
 #include "llvm/DebugInfo/GSYM/StringTable.h"
 #include "llvm/Support/DataExtractor.h"
 #include "llvm/Support/Endian.h"
+#include "llvm/Testing/Support/Error.h"
 
 #include "gtest/gtest.h"
+#include "gmock/gmock.h"
 #include <string>
 
 using namespace llvm;
 using namespace gsym;
 
 void checkError(ArrayRef<std::string> ExpectedMsgs, Error Err) {
   ASSERT_TRUE(bool(Err));
   size_t WhichMsg = 0;
if (auto ExpectedGR = GsymReader::copyBuffer(OutStrm.str())) {
     FunctionInfo Func2(Func2Addr, FuncSize, Func2Name);
     VerifyFunctionInfo(GR, Func2Addr, Func2);
     VerifyFunctionInfo(GR, Func2Addr+1, Func2);
     VerifyFunctionInfo(GR, Func2Addr+FuncSize-1, Func2);
     VerifyFunctionInfoError(GR, Func2Addr+FuncSize,
                             "address 0x1030 not in GSYM");
   }
 }
+
+TEST(GSYMTest, TestGsymLookups) {
+  // Test creating a GSYM file with a function that has a inline information.
+  // Verify that lookups work correctly. Lookups do not decode the entire
+  // FunctionInfo or InlineInfo, they only extract information needed for the
+  // lookup to happen which avoids allocations which can slow down
+  // symbolication.
+  GsymCreator GC;
+  FunctionInfo FI(0x1000, 0x100, GC.insertString("main"));
+  const auto ByteOrder = support::endian::system_endianness();
+  FI.OptLineTable = LineTable();
+  const uint32_t MainFileIndex = GC.insertFile("/tmp/main.c");
+  const uint32_t FooFileIndex = GC.insertFile("/tmp/foo.h");
+  FI.OptLineTable->push(LineEntry(0x1000, MainFileIndex, 5));
+  FI.OptLineTable->push(LineEntry(0x1010, FooFileIndex, 10));
+  FI.OptLineTable->push(LineEntry(0x1012, FooFileIndex, 20));
+  FI.OptLineTable->push(LineEntry(0x1014, FooFileIndex, 11));
+  FI.OptLineTable->push(LineEntry(0x1016, FooFileIndex, 30));
+  FI.OptLineTable->push(LineEntry(0x1018, FooFileIndex, 12));
+  FI.OptLineTable->push(LineEntry(0x1020, MainFileIndex, 8));
+  FI.Inline = InlineInfo();
+
+  FI.Inline->Name = GC.insertString("inline1");
+  FI.Inline->CallFile = MainFileIndex;
+  FI.Inline->CallLine = 6;
+  FI.Inline->Ranges.insert(AddressRange(0x1010, 0x1020));
+  InlineInfo Inline2;
+  Inline2.Name = GC.insertString("inline2");
+  Inline2.CallFile = FooFileIndex;
+  Inline2.CallLine = 33;
+  Inline2.Ranges.insert(AddressRange(0x1012, 0x1014));
+  FI.Inline->Children.emplace_back(Inline2);
+  InlineInfo Inline3;
+  Inline3.Name = GC.insertString("inline3");
+  Inline3.CallFile = FooFileIndex;
+  Inline3.CallLine = 35;
+  Inline3.Ranges.insert(AddressRange(0x1016, 0x1018));
+  FI.Inline->Children.emplace_back(Inline3);
+  GC.addFunctionInfo(std::move(FI));
+  Error FinalizeErr = GC.finalize(llvm::nulls());
+  ASSERT_FALSE(FinalizeErr);
+  SmallString<512> Str;
+  raw_svector_ostream OutStrm(Str);
+  FileWriter FW(OutStrm, ByteOrder);
+  llvm::Error Err = GC.encode(FW);
+  ASSERT_FALSE((bool)Err);
+  Expected<GsymReader> GR = GsymReader::copyBuffer(OutStrm.str());
+  ASSERT_TRUE(bool(GR));
+
+  // Verify inline info is correct when doing lookups.
+  auto LR = GR->lookup(0x1000);
+  ASSERT_THAT_EXPECTED(LR, Succeeded());
+  EXPECT_THAT(LR->Locations,
+    testing::ElementsAre(SourceLocation{"main", "/tmp", "main.c", 5}));
+  LR = GR->lookup(0x100F);
+  ASSERT_THAT_EXPECTED(LR, Succeeded());
+  EXPECT_THAT(LR->Locations,
+    testing::ElementsAre(SourceLocation{"main", "/tmp", "main.c", 5}));
+
+  LR = GR->lookup(0x1010);
+  ASSERT_THAT_EXPECTED(LR, Succeeded());
+
+  EXPECT_THAT(LR->Locations,
+    testing::ElementsAre(SourceLocation{"inline1", "/tmp", "foo.h", 10},
+                         SourceLocation{"main", "/tmp", "main.c", 6}));
+
+  LR = GR->lookup(0x1012);
+  ASSERT_THAT_EXPECTED(LR, Succeeded());
+  EXPECT_THAT(LR->Locations,
+    testing::ElementsAre(SourceLocation{"inline2", "/tmp", "foo.h", 20},
+                         SourceLocation{"inline1", "/tmp", "foo.h", 33},
+                         SourceLocation{"main", "/tmp", "main.c", 6}));
+
+  LR = GR->lookup(0x1014);
+  ASSERT_THAT_EXPECTED(LR, Succeeded());
+  EXPECT_THAT(LR->Locations,
+    testing::ElementsAre(SourceLocation{"inline1", "/tmp", "foo.h", 11},
+                         SourceLocation{"main", "/tmp", "main.c", 6}));
+
+  LR = GR->lookup(0x1016);
+  ASSERT_THAT_EXPECTED(LR, Succeeded());
+  EXPECT_THAT(LR->Locations,
+    testing::ElementsAre(SourceLocation{"inline3", "/tmp", "foo.h", 30},
+                         SourceLocation{"inline1", "/tmp", "foo.h", 35},
+                         SourceLocation{"main", "/tmp", "main.c", 6}));
+
+  LR = GR->lookup(0x1018);
+  ASSERT_THAT_EXPECTED(LR, Succeeded());
+  EXPECT_THAT(LR->Locations,
+    testing::ElementsAre(SourceLocation{"inline1", "/tmp", "foo.h", 12},
+                         SourceLocation{"main", "/tmp", "main.c", 6}));
+
+  LR = GR->lookup(0x1020);
+  ASSERT_THAT_EXPECTED(LR, Succeeded());
+  EXPECT_THAT(LR->Locations,
+    testing::ElementsAre(SourceLocation{"main", "/tmp", "main.c", 8}));
+}