Index: include/llvm/DebugInfo/GSYM/FunctionInfo.h =================================================================== --- include/llvm/DebugInfo/GSYM/FunctionInfo.h +++ include/llvm/DebugInfo/GSYM/FunctionInfo.h @@ -9,8 +9,9 @@ #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/LineEntry.h" +#include "llvm/DebugInfo/GSYM/LineTable.h" #include "llvm/DebugInfo/GSYM/Range.h" #include "llvm/DebugInfo/GSYM/StringTable.h" #include @@ -32,8 +33,8 @@ struct FunctionInfo { AddressRange Range; uint32_t Name; ///< String table offset in the string table. - std::vector Lines; - InlineInfo Inline; + llvm::Optional LineTable; + llvm::Optional Inline; FunctionInfo(uint64_t Addr = 0, uint64_t Size = 0, uint32_t N = 0) : Range(Addr, Addr + Size), Name(N) {} @@ -43,7 +44,7 @@ /// converting information from a symbol table and from debug info, we /// might end up with multiple FunctionInfo objects for the same range /// and we need to be able to tell which one is the better object to use. - return !Lines.empty() || Inline.isValid(); + return LineTable.hasValue() || Inline.hasValue(); } bool isValid() const { @@ -65,14 +66,14 @@ void clear() { Range = {0, 0}; Name = 0; - Lines.clear(); - Inline.clear(); + LineTable = llvm::None; + Inline = llvm::None; } }; inline bool operator==(const FunctionInfo &LHS, const FunctionInfo &RHS) { return LHS.Range == RHS.Range && LHS.Name == RHS.Name && - LHS.Lines == RHS.Lines && LHS.Inline == RHS.Inline; + LHS.LineTable == RHS.LineTable && LHS.Inline == RHS.Inline; } inline bool operator!=(const FunctionInfo &LHS, const FunctionInfo &RHS) { return !(LHS == RHS); @@ -88,14 +89,10 @@ return LHS.Range < RHS.Range; // Then sort by inline - if (LHS.Inline.isValid() != RHS.Inline.isValid()) - return RHS.Inline.isValid(); + if (LHS.Inline.hasValue() != RHS.Inline.hasValue()) + return RHS.Inline.hasValue(); - // If the number of lines is the same, then compare line table entries - if (LHS.Lines.size() == RHS.Lines.size()) - return LHS.Lines < RHS.Lines; - // Then sort by number of line table entries (more is better) - return LHS.Lines.size() < RHS.Lines.size(); + return LHS.LineTable < RHS.LineTable; } raw_ostream &operator<<(raw_ostream &OS, const FunctionInfo &R); Index: include/llvm/DebugInfo/GSYM/LineTable.h =================================================================== --- include/llvm/DebugInfo/GSYM/LineTable.h +++ include/llvm/DebugInfo/GSYM/LineTable.h @@ -0,0 +1,198 @@ +//===- LineTable.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_LINETABLE_H +#define LLVM_DEBUGINFO_GSYM_LINETABLE_H + +#include "llvm/DebugInfo/GSYM/LineEntry.h" +#include "llvm/Support/Error.h" +#include +#include + +namespace llvm { +namespace gsym { + +struct FunctionInfo; +class FileWriter; + +/// LineTable class contains deserialized versions of line tables for each +/// function's address ranges. +/// +/// When saved to disk, the line table is encoded using a modified version of +/// the DWARF line tables that only tracks address to source file and line. +/// +/// ENCODING +/// +/// The line table starts with a small prolog that contains the following +/// values: +/// +/// ENCODING NAME DESCRIPTION +/// ======== =========== ==================================================== +/// SLEB MinDelta The min line delta for special opcodes that advance +/// the address and line number. +/// SLEB MaxDelta The max line delta for single byte opcodes that +/// advance the address and line number. +/// ULEB FirstLine The value of the first source line number to +/// initialize the LineEntry with. +/// +/// Once these prolog items are read, we initialize a LineEntry struct with +/// the start address of the function from the FunctionInfo's address range, +/// a default file index of 1, and the line number set to "FirstLine" from +/// the prolog above: +/// +/// LineEntry Row(BaseAddr, 1, FirstLine); +/// +/// The line table state machine is now initialized and ready to be parsed. +/// The stream that follows this encodes the line entries in a compact +/// form. Some opcodes cause "Row" to be modified and some opcodes may also +/// push "Row" onto the end of the "LineTable.Lines" vector. The end result +/// is a vector of LineEntry structs that is sorted in ascending address +/// order. +/// +/// NORMAL OPCODES +/// +/// The opcodes 0 through 3 are normal in opcodes. Their encoding and +/// descriptions are listed below: +/// +/// ENCODING ENUMERATION VALUE DESCRIPTION +/// ======== ================ ===== ======================================== +/// LTOC_EndSequence 0x00 Parsing is done. +/// ULEB LTOC_SetFile 0x01 Row.File = ULEB +/// ULEB LTOC_AdvancePC 0x02 Row.Addr += ULEB, push "Row". +/// SLEB LTOC_AdvanceLine 0x03 Row.Line += SLEB +/// LTOC_FirstSpecial 0x04 First special opcode (see SPECIAL +/// OPCODES below). +/// +/// SPECIAL OPCODES +/// +/// Opcodes LTOC_FirstSpecial through 255 are special opcodes that always +/// increment both the Row.Addr and Row.Line and push "Row" onto the +/// LineEntry.Lines array. They do this by using some of the bits to +/// increment/decrement the source line number, and some of the bits to +/// increment the address. Line numbers can go up or down when making line +/// tables, where addresses always only increase since line tables are sorted +/// by address. +/// +/// In order to calculate the amount to increment the line and address for +/// these special opcodes, we calculate the number of values reserved for the +/// line increment/decrement using the "MinDelta" and "MaxDelta" from the +/// prolog: +/// +/// const int64_t LineRange = MaxDelta - MinDelta + 1; +/// +/// Then we can adjust the opcode to not include any of the normal opcodes: +/// +/// const uint8_t AdjustedOp = Opcode - LTOC_FirstSpecial; +/// +/// And we can calculate the line offset, and address offset: +/// +/// const int64_t LineDelta = MinDelta + (AdjustedOp % LineRange); +/// const uint64_t AddrDelta = (AdjustedOp / LineRange); +/// +/// And use these to modify our "Row": +/// +/// Row.Line += LineDelta; +/// Row.Addr += AddrDelta; +/// +/// And push a row onto the line table: +/// +/// Lines.push_back(Row); +/// +/// This is verify similar to the way that DWARF encodes its line tables. The +/// only difference is the DWARF line tables have more normal opcodes and the +/// "Row" contains more members, like source column number, bools for end of +/// prologue, beginnging of epilogue, is statement and many others. There are +/// also more complex rules that happen for the extra normal opcodes. By +/// leaving these extra opcodes out, we leave more bits for the special +/// opcodes that allows us to encode line tables in fewer bytes than standard +/// DWARF encodings. +/// +/// 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 Collection; + Collection Lines; ///< All line entries in the line table. +public: + static 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. + /// 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 LineTable or an error describing the issue that was + /// encountered during decoding. + static llvm::Expected decode(DataExtractor &Data, + uint64_t BaseAddr); + /// Encode this LineTable 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 decoding the line table. + /// This will be the FunctionInfo's start address. + /// + /// \returns An error object that indicates success or failure or the + /// encoding process. + llvm::Error encode(FileWriter &O, uint64_t BaseAddr) const; + bool empty() const { return Lines.empty(); } + void clear() { Lines.clear(); } + void push(const LineEntry &LE) { + Lines.push_back(LE); + } + size_t isValid() const { + return !Lines.empty(); + } + size_t size() const { + return Lines.size(); + } + LineEntry &get(size_t i) { + assert(i < Lines.size()); + return Lines[i]; + } + const LineEntry &get(size_t i) const { + assert(i < Lines.size()); + return Lines[i]; + } + LineEntry &operator[](size_t i) { + return get(i); + } + const LineEntry &operator[](size_t i) const { + return get(i); + } + bool operator==(const LineTable &RHS) const { + return Lines == RHS.Lines; + } + bool operator!=(const LineTable &RHS) const { + return Lines != RHS.Lines; + } + bool operator<(const LineTable &RHS) const { + const auto LHSSize = Lines.size(); + const auto RHSSize = RHS.Lines.size(); + if (LHSSize == RHSSize) + return Lines < RHS.Lines; + return LHSSize < RHSSize; + } + Collection::const_iterator begin() const { return Lines.begin(); } + Collection::const_iterator end() const { return Lines.end(); } + +}; + +raw_ostream &operator<<(raw_ostream &OS, const gsym::LineTable <); + +} // namespace gsym +} // namespace llvm + +#endif // #ifndef LLVM_DEBUGINFO_GSYM_LINETABLE_H Index: lib/DebugInfo/GSYM/CMakeLists.txt =================================================================== --- lib/DebugInfo/GSYM/CMakeLists.txt +++ lib/DebugInfo/GSYM/CMakeLists.txt @@ -2,6 +2,7 @@ FileWriter.cpp FunctionInfo.cpp InlineInfo.cpp + LineTable.cpp Range.cpp ADDITIONAL_HEADER_DIRS Index: lib/DebugInfo/GSYM/FunctionInfo.cpp =================================================================== --- lib/DebugInfo/GSYM/FunctionInfo.cpp +++ lib/DebugInfo/GSYM/FunctionInfo.cpp @@ -14,9 +14,6 @@ raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const FunctionInfo &FI) { OS << '[' << HEX64(FI.Range.Start) << '-' << HEX64(FI.Range.End) << "): " - << "Name=" << HEX32(FI.Name) << '\n'; - for (const auto &Line : FI.Lines) - OS << Line << '\n'; - OS << FI.Inline; + << "Name=" << HEX32(FI.Name) << '\n' << FI.LineTable << FI.Inline; return OS; } Index: lib/DebugInfo/GSYM/LineTable.cpp =================================================================== --- lib/DebugInfo/GSYM/LineTable.cpp +++ lib/DebugInfo/GSYM/LineTable.cpp @@ -0,0 +1,287 @@ +//===- LineTable.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/LineTable.h" +#include "llvm/DebugInfo/GSYM/FileWriter.h" +#include "llvm/Support/DataExtractor.h" + +using namespace llvm; +using namespace gsym; + +enum LineTableOpCode { + EndSequence = 0x00, ///< End of the line table + SetFile = 0x01, ///< Set LineTableRow.file_idx, don't push a row + AdvancePC = 0x02, ///< Increment LineTableRow.address, and push a row + AdvanceLine = 0x03, ///< Set LineTableRow.file_line, don't push a row + FirstSpecial = 0x04, ///< All special opcodes push a row +}; + +struct DeltaInfo { + int64_t Delta; + uint32_t Count; + DeltaInfo(int64_t D, uint32_t C) : Delta(D), Count(C) {} +}; + +inline bool operator<(const DeltaInfo &LHS, int64_t Delta) { + return LHS.Delta < Delta; +} + +static bool encodeSpecial(int64_t MinLineDelta, int64_t MaxLineDelta, + int64_t LineDelta, uint64_t AddrDelta, + uint8_t &SpecialOp) { + if (LineDelta < MinLineDelta) + return false; + if (LineDelta > MaxLineDelta) + return false; + int64_t LineRange = MaxLineDelta - MinLineDelta + 1; + int64_t AdjustedOp = ((LineDelta - MinLineDelta) + AddrDelta * LineRange); + int64_t Op = AdjustedOp + FirstSpecial; + if (Op < 0) + return false; + if (Op > 255) + return false; + SpecialOp = (uint8_t)Op; + return true; +} + +typedef std::function LineEntryCallback; + +static llvm::Error parse(DataExtractor &Data, uint64_t BaseAddr, + LineEntryCallback const &Callback) { + uint64_t Offset = 0; + if (!Data.isValidOffset(Offset)) + return createStringError(std::errc::io_error, + "0x%8.8" PRIx64 ": missing LineTable MinDelta", Offset); + int64_t MinDelta = Data.getSLEB128(&Offset); + if (!Data.isValidOffset(Offset)) + return createStringError(std::errc::io_error, + "0x%8.8" PRIx64 ": missing LineTable MaxDelta", Offset); + int64_t MaxDelta = Data.getSLEB128(&Offset); + int64_t LineRange = MaxDelta - MinDelta + 1; + if (!Data.isValidOffset(Offset)) + return createStringError(std::errc::io_error, + "0x%8.8" PRIx64 ": missing LineTable FirstLine", Offset); + const uint32_t FirstLine = (uint32_t)Data.getULEB128(&Offset); + LineEntry Row(BaseAddr, 1, FirstLine); + bool Done = false; + while (!Done) { + if (!Data.isValidOffset(Offset)) + return createStringError(std::errc::io_error, + "0x%8.8" PRIx64 ": EOF found before EndSequence", Offset); + uint8_t Op = Data.getU8(&Offset); + switch (Op) { + case EndSequence: + Done = true; + break; + case SetFile: + if (!Data.isValidOffset(Offset)) + return createStringError(std::errc::io_error, + "0x%8.8" PRIx64 ": EOF found before SetFile value", + Offset); + Row.File = (uint32_t)Data.getULEB128(&Offset); + break; + case AdvancePC: + if (!Data.isValidOffset(Offset)) + return createStringError(std::errc::io_error, + "0x%8.8" PRIx64 ": EOF found before AdvancePC value", + Offset); + Row.Addr += Data.getULEB128(&Offset); + // If the function callback returns false, we stop parsing + if (Callback(Row) == false) + return Error::success(); + break; + case AdvanceLine: + if (!Data.isValidOffset(Offset)) + return createStringError(std::errc::io_error, + "0x%8.8" PRIx64 ": EOF found before AdvanceLine value", + Offset); + Row.Line += Data.getSLEB128(&Offset); + break; + default: { + // A byte that contains both address and line increment + uint8_t AdjustedOp = Op - FirstSpecial; + int64_t LineDelta = MinDelta + (AdjustedOp % LineRange); + uint64_t AddrDelta = (AdjustedOp / LineRange); + Row.Line += LineDelta; + Row.Addr += AddrDelta; + // If the function callback returns false, we stop parsing + if (Callback(Row) == false) + return Error::success(); + break; + } + } + } + return Error::success(); +} + +llvm::Error LineTable::encode(FileWriter &Out, uint64_t BaseAddr) const { + // Users must verify the LineTable is valid prior to calling this funtion. + // We don't want to emit any LineTable 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 LineTable object"); + + int64_t MinLineDelta = INT64_MAX; + int64_t MaxLineDelta = INT64_MIN; + std::vector DeltaInfos; + if (Lines.size() == 1) { + MinLineDelta = 0; + MaxLineDelta = 0; + } else { + int64_t PrevLine = 1; + bool First = true; + for (const auto &line_entry : Lines) { + if (First) + First = false; + else { + int64_t LineDelta = (int64_t)line_entry.Line - PrevLine; + auto End = DeltaInfos.end(); + auto Pos = std::lower_bound(DeltaInfos.begin(), End, LineDelta); + if (Pos != End && Pos->Delta == LineDelta) + ++Pos->Count; + else + DeltaInfos.insert(Pos, DeltaInfo(LineDelta, 1)); + if (LineDelta < MinLineDelta) + MinLineDelta = LineDelta; + if (LineDelta > MaxLineDelta) + MaxLineDelta = LineDelta; + } + PrevLine = (int64_t)line_entry.Line; + } + assert(MinLineDelta <= MaxLineDelta); + } + // Set the min and max line delta intelligently based on the counts of + // the line deltas. if our range is too large. + const int64_t MaxLineRange = 14; + if (MaxLineDelta - MinLineDelta > MaxLineRange) { + uint32_t BestIndex = 0; + uint32_t BestEndIndex = 0; + uint32_t BestCount = 0; + const size_t NumDeltaInfos = DeltaInfos.size(); + for (uint32_t I = 0; I < NumDeltaInfos; ++I) { + const int64_t FirstDelta = DeltaInfos[I].Delta; + uint32_t CurrCount = 0; + uint32_t J; + for (J = I; J < NumDeltaInfos; ++J) { + auto LineRange = DeltaInfos[J].Delta - FirstDelta; + if (LineRange > MaxLineRange) + break; + CurrCount += DeltaInfos[J].Count; + } + if (CurrCount > BestCount) { + BestIndex = I; + BestEndIndex = J - 1; + BestCount = CurrCount; + } + } + MinLineDelta = DeltaInfos[BestIndex].Delta; + MaxLineDelta = DeltaInfos[BestEndIndex].Delta; + } + if (MinLineDelta == MaxLineDelta && MinLineDelta > 0 && + MinLineDelta < MaxLineRange) + MinLineDelta = 0; + assert(MinLineDelta <= MaxLineDelta); + + // Initialize the line entry state as a starting point. All line entries + // will be deltas from this. + LineEntry Prev(BaseAddr, 1, Lines.front().Line); + + // Write out the min and max line delta as signed LEB128 + Out.writeSLEB(MinLineDelta); + Out.writeSLEB(MaxLineDelta); + // Write out the starting line number as a unsigned LEB128 + Out.writeULEB(Prev.Line); + + for (const auto &Curr : Lines) { + if (Curr.Addr < BaseAddr) + return createStringError(std::errc::invalid_argument, + "LineEntry has address 0x%" PRIx64 " which is " + "less than the function start address 0x%" + PRIx64, Curr.Addr, BaseAddr); + if (Curr.Addr < Prev.Addr) + return createStringError(std::errc::invalid_argument, + "LineEntry in LineTable not in ascending order"); + const uint64_t AddrDelta = Curr.Addr - Prev.Addr; + int64_t LineDelta = 0; + if (Curr.Line > Prev.Line) + LineDelta = Curr.Line - Prev.Line; + else if (Prev.Line > Curr.Line) + LineDelta = -((int32_t)(Prev.Line - Curr.Line)); + + // Set the file if it doesn't match the current one. + if (Curr.File != Prev.File) { + Out.writeU8(SetFile); + Out.writeULEB(Curr.File); + } + + uint8_t SpecialOp; + if (encodeSpecial(MinLineDelta, MaxLineDelta, LineDelta, AddrDelta, + SpecialOp)) { + // Advance the PC and line and push a row + Out.writeU8(SpecialOp); + } else { + // We can't encode the address delta and line delta into + // a single special opcode, we must do them separately + + // Advance the line + if (LineDelta != 0) { + Out.writeU8(AdvanceLine); + Out.writeSLEB(LineDelta); + } + + // Advance the PC and push a row + Out.writeU8(AdvancePC); + Out.writeULEB(AddrDelta); + } + Prev = Curr; + } + Out.writeU8(EndSequence); + return Error::success(); +} + +// Parse all line table entries into the "LineTable" vector. We can +// cache the results of this if needed, or we can call LineTable::lookup() +// below. +llvm::Expected LineTable::decode(DataExtractor &Data, + uint64_t BaseAddr) { + LineTable LT; + llvm::Error Err = parse(Data, BaseAddr, [&](const LineEntry &Row) -> bool { + LT.Lines.push_back(Row); + return true; // Keep parsing by returning true + }); + 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) { + 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 + }); + return Result; +} + +raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const LineTable <) { + for (const auto &LineEntry : LT) + OS << LineEntry << '\n'; + return OS; +} Index: unittests/DebugInfo/GSYM/GSYMTest.cpp =================================================================== --- unittests/DebugInfo/GSYM/GSYMTest.cpp +++ unittests/DebugInfo/GSYM/GSYMTest.cpp @@ -74,7 +74,8 @@ EXPECT_EQ(FI.size(), Size); const uint32_t FileIdx = 1; const uint32_t Line = 12; - FI.Lines.push_back(LineEntry(StartAddr, FileIdx, Line)); + FI.LineTable = LineTable(); + FI.LineTable->push(LineEntry(StartAddr,FileIdx,Line)); EXPECT_TRUE(FI.hasRichInfo()); FI.clear(); EXPECT_FALSE(FI.isValid()); @@ -109,13 +110,15 @@ // best version of a function info. FunctionInfo FISymtab(StartAddr, Size, NameOffset); FunctionInfo FIWithLines(StartAddr, Size, NameOffset); - FIWithLines.Lines.push_back(LineEntry(StartAddr, FileIdx, Line)); + FIWithLines.LineTable = LineTable(); + FIWithLines.LineTable->push(LineEntry(StartAddr,FileIdx,Line)); // Test that a FunctionInfo with just a name and size is less than one // that has name, size and any number of line table entries EXPECT_LT(FISymtab, FIWithLines); FunctionInfo FIWithLinesAndInline = FIWithLines; - FIWithLinesAndInline.Inline.Ranges.insert( + FIWithLinesAndInline.Inline = InlineInfo(); + FIWithLinesAndInline.Inline->Ranges.insert( AddressRange(StartAddr, StartAddr + 0x10)); // Test that a FunctionInfo with name, size, and line entries is less than // the same one with valid inline info @@ -124,13 +127,13 @@ // Test if we have an entry with lines and one with more lines for the same // range, the ones with more lines is greater than the one with less. FunctionInfo FIWithMoreLines = FIWithLines; - FIWithMoreLines.Lines.push_back(LineEntry(StartAddr, FileIdx, Line + 5)); + FIWithMoreLines.LineTable->push(LineEntry(StartAddr,FileIdx,Line+5)); EXPECT_LT(FIWithLines, FIWithMoreLines); // Test that if we have the same number of lines we compare the line entries - // in the FunctionInfo.Lines vector. + // in the FunctionInfo.LineTable.Lines vector. FunctionInfo FIWithLinesWithHigherAddress = FIWithLines; - FIWithLinesWithHigherAddress.Lines[0].Addr += 0x10; + FIWithLinesWithHigherAddress.LineTable->get(0).Addr += 0x10; EXPECT_LT(FIWithLines, FIWithLinesWithHigherAddress); } @@ -633,3 +636,156 @@ Ranges.insert(AddressRange(0x1050, 0x1070)); TestAddressRangeEncodeDecodeHelper(Ranges, BaseAddr); } + +static void TestLineTableHelper(llvm::support::endianness ByteOrder, + const LineTable <) { + SmallString<512> Str; + raw_svector_ostream OutStrm(Str); + FileWriter FW(OutStrm, ByteOrder); + const uint64_t BaseAddr = LT[0].Addr; + llvm::Error Err = LT.encode(FW, BaseAddr); + ASSERT_FALSE(Err); + std::string Bytes(OutStrm.str()); + uint8_t AddressSize = 4; + DataExtractor Data(Bytes, ByteOrder == llvm::support::little, AddressSize); + llvm::Expected Decoded = LineTable::decode(Data, BaseAddr); + // Make sure decoding succeeded. + ASSERT_TRUE((bool)Decoded); + // Make sure decoded object is the same as the one we encoded. + EXPECT_EQ(LT, Decoded.get()); +} + +TEST(GSYMTest, TestLineTable) { + const uint64_t StartAddr = 0x1000; + const uint32_t FileIdx = 1; + LineTable LT; + LineEntry Line0(StartAddr+0x000, FileIdx, 10); + LineEntry Line1(StartAddr+0x010, FileIdx, 11); + LineEntry Line2(StartAddr+0x100, FileIdx, 1000); + ASSERT_TRUE(LT.empty()); + ASSERT_EQ(LT.size(), (size_t)0); + LT.push(Line0); + ASSERT_EQ(LT.size(), (size_t)1); + LT.push(Line1); + LT.push(Line2); + LT.push(LineEntry(StartAddr+0x120, FileIdx, 900)); + LT.push(LineEntry(StartAddr+0x120, FileIdx, 2000)); + LT.push(LineEntry(StartAddr+0x121, FileIdx, 2001)); + LT.push(LineEntry(StartAddr+0x122, FileIdx, 2002)); + LT.push(LineEntry(StartAddr+0x123, FileIdx, 2003)); + ASSERT_FALSE(LT.empty()); + ASSERT_EQ(LT.size(), (size_t)8); + // Test operator[]. + ASSERT_EQ(LT[0], Line0); + ASSERT_EQ(LT[1], Line1); + ASSERT_EQ(LT[2], Line2); + + // Test encoding and decoding line tables. + TestLineTableHelper(llvm::support::little, LT); + TestLineTableHelper(llvm::support::big, LT); + + // Verify the clear method works as expected. + LT.clear(); + ASSERT_TRUE(LT.empty()); + ASSERT_EQ(LT.size(), (size_t)0); + + LineTable LT1; + LineTable LT2; + + // Test that two empty line tables are equal and neither are less than + // each other. + ASSERT_EQ(LT1, LT2); + ASSERT_FALSE(LT1 < LT2); + ASSERT_FALSE(LT2 < LT2); + + // Test that a line table with less number of line entries is less than a + // line table with more line entries and that they are not equal. + LT2.push(Line0); + ASSERT_LT(LT1, LT2); + ASSERT_NE(LT1, LT2); + + // Test that two line tables with the same entries are equal. + LT1.push(Line0); + ASSERT_EQ(LT1, LT2); + ASSERT_FALSE(LT1 < LT2); + ASSERT_FALSE(LT2 < LT2); +} + +static void TestLineTableDecodeError(llvm::support::endianness ByteOrder, + std::string Bytes, + const uint64_t BaseAddr, + std::string ExpectedErrorMsg) { + uint8_t AddressSize = 4; + DataExtractor Data(Bytes, ByteOrder == llvm::support::little, AddressSize); + llvm::Expected Decoded = LineTable::decode(Data, BaseAddr); + // Make sure decoding fails. + ASSERT_FALSE((bool)Decoded); + // Make sure decoded object is the same as the one we encoded. + checkError(ExpectedErrorMsg, Decoded.takeError()); +} + +TEST(GSYMTest, TestLineTableDecodeErrors) { + // Test decoding InlineInfo objects that ensure we report an appropriate + // error message. + const llvm::support::endianness ByteOrder = llvm::support::little; + SmallString<512> Str; + raw_svector_ostream OutStrm(Str); + FileWriter FW(OutStrm, ByteOrder); + const uint64_t BaseAddr = 0x100; + TestLineTableDecodeError(ByteOrder, OutStrm.str(), BaseAddr, + "0x00000000: missing LineTable MinDelta"); + FW.writeU8(1); // MinDelta (ULEB) + TestLineTableDecodeError(ByteOrder, OutStrm.str(), BaseAddr, + "0x00000001: missing LineTable MaxDelta"); + FW.writeU8(10); // MaxDelta (ULEB) + TestLineTableDecodeError(ByteOrder, OutStrm.str(), BaseAddr, + "0x00000002: missing LineTable FirstLine"); + FW.writeU8(20); // FirstLine (ULEB) + TestLineTableDecodeError(ByteOrder, OutStrm.str(), BaseAddr, + "0x00000003: EOF found before EndSequence"); + // Test a SetFile with the argument missing from the stream + FW.writeU8(1); // SetFile opcode (uint8_t) + TestLineTableDecodeError(ByteOrder, OutStrm.str(), BaseAddr, + "0x00000004: EOF found before SetFile value"); + FW.writeU8(5); // SetFile value as index (ULEB) + // Test a AdvancePC with the argument missing from the stream + FW.writeU8(2); // AdvancePC opcode (uint8_t) + TestLineTableDecodeError(ByteOrder, OutStrm.str(), BaseAddr, + "0x00000006: EOF found before AdvancePC value"); + FW.writeU8(20); // AdvancePC value as offset (ULEB) + // Test a AdvancePC with the argument missing from the stream + FW.writeU8(3); // AdvanceLine opcode (uint8_t) + TestLineTableDecodeError(ByteOrder, OutStrm.str(), BaseAddr, + "0x00000008: EOF found before AdvanceLine value"); + FW.writeU8(20); // AdvanceLine value as offset (LLEB) +} + +TEST(GSYMTest, TestLineTableEncodeErrors) { + const uint64_t BaseAddr = 0x1000; + const uint32_t FileIdx = 1; + const llvm::support::endianness ByteOrder = llvm::support::little; + SmallString<512> Str; + raw_svector_ostream OutStrm(Str); + FileWriter FW(OutStrm, ByteOrder); + LineTable LT; + checkError("attempted to encode invalid LineTable object", + LT.encode(FW, BaseAddr)); + + // Try to encode a line table where a line entry has an address that is less + // than BaseAddr and verify we get an appropriate error. + LineEntry Line0(BaseAddr+0x000, FileIdx, 10); + LineEntry Line1(BaseAddr+0x010, FileIdx, 11); + LT.push(Line0); + LT.push(Line1); + checkError("LineEntry has address 0x1000 which is less than the function " + "start address 0x1010", LT.encode(FW, BaseAddr+0x10)); + LT.clear(); + + // Try to encode a line table where a line entries has an address that is less + // than BaseAddr and verify we get an appropriate error. + LT.push(Line1); + LT.push(Line0); + checkError("LineEntry in LineTable not in ascending order", + LT.encode(FW, BaseAddr)); + LT.clear(); +}