18bcb0991SDimitry Andric //===- LineTable.cpp --------------------------------------------*- C++ -*-===//
28bcb0991SDimitry Andric //
38bcb0991SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
48bcb0991SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
58bcb0991SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
68bcb0991SDimitry Andric //
78bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
88bcb0991SDimitry Andric
98bcb0991SDimitry Andric #include "llvm/DebugInfo/GSYM/LineTable.h"
108bcb0991SDimitry Andric #include "llvm/DebugInfo/GSYM/FileWriter.h"
118bcb0991SDimitry Andric #include "llvm/Support/DataExtractor.h"
128bcb0991SDimitry Andric
138bcb0991SDimitry Andric using namespace llvm;
148bcb0991SDimitry Andric using namespace gsym;
158bcb0991SDimitry Andric
168bcb0991SDimitry Andric enum LineTableOpCode {
178bcb0991SDimitry Andric EndSequence = 0x00, ///< End of the line table.
188bcb0991SDimitry Andric SetFile = 0x01, ///< Set LineTableRow.file_idx, don't push a row.
198bcb0991SDimitry Andric AdvancePC = 0x02, ///< Increment LineTableRow.address, and push a row.
208bcb0991SDimitry Andric AdvanceLine = 0x03, ///< Set LineTableRow.file_line, don't push a row.
218bcb0991SDimitry Andric FirstSpecial = 0x04, ///< All special opcodes push a row.
228bcb0991SDimitry Andric };
238bcb0991SDimitry Andric
248bcb0991SDimitry Andric struct DeltaInfo {
258bcb0991SDimitry Andric int64_t Delta;
268bcb0991SDimitry Andric uint32_t Count;
DeltaInfoDeltaInfo278bcb0991SDimitry Andric DeltaInfo(int64_t D, uint32_t C) : Delta(D), Count(C) {}
288bcb0991SDimitry Andric };
298bcb0991SDimitry Andric
operator <(const DeltaInfo & LHS,int64_t Delta)308bcb0991SDimitry Andric inline bool operator<(const DeltaInfo &LHS, int64_t Delta) {
318bcb0991SDimitry Andric return LHS.Delta < Delta;
328bcb0991SDimitry Andric }
338bcb0991SDimitry Andric
encodeSpecial(int64_t MinLineDelta,int64_t MaxLineDelta,int64_t LineDelta,uint64_t AddrDelta,uint8_t & SpecialOp)348bcb0991SDimitry Andric static bool encodeSpecial(int64_t MinLineDelta, int64_t MaxLineDelta,
358bcb0991SDimitry Andric int64_t LineDelta, uint64_t AddrDelta,
368bcb0991SDimitry Andric uint8_t &SpecialOp) {
378bcb0991SDimitry Andric if (LineDelta < MinLineDelta)
388bcb0991SDimitry Andric return false;
398bcb0991SDimitry Andric if (LineDelta > MaxLineDelta)
408bcb0991SDimitry Andric return false;
418bcb0991SDimitry Andric int64_t LineRange = MaxLineDelta - MinLineDelta + 1;
428bcb0991SDimitry Andric int64_t AdjustedOp = ((LineDelta - MinLineDelta) + AddrDelta * LineRange);
438bcb0991SDimitry Andric int64_t Op = AdjustedOp + FirstSpecial;
448bcb0991SDimitry Andric if (Op < 0)
458bcb0991SDimitry Andric return false;
468bcb0991SDimitry Andric if (Op > 255)
478bcb0991SDimitry Andric return false;
488bcb0991SDimitry Andric SpecialOp = (uint8_t)Op;
498bcb0991SDimitry Andric return true;
508bcb0991SDimitry Andric }
518bcb0991SDimitry Andric
528bcb0991SDimitry Andric typedef std::function<bool(const LineEntry &Row)> LineEntryCallback;
538bcb0991SDimitry Andric
parse(DataExtractor & Data,uint64_t BaseAddr,LineEntryCallback const & Callback)548bcb0991SDimitry Andric static llvm::Error parse(DataExtractor &Data, uint64_t BaseAddr,
558bcb0991SDimitry Andric LineEntryCallback const &Callback) {
568bcb0991SDimitry Andric uint64_t Offset = 0;
578bcb0991SDimitry Andric if (!Data.isValidOffset(Offset))
588bcb0991SDimitry Andric return createStringError(std::errc::io_error,
598bcb0991SDimitry Andric "0x%8.8" PRIx64 ": missing LineTable MinDelta", Offset);
608bcb0991SDimitry Andric int64_t MinDelta = Data.getSLEB128(&Offset);
618bcb0991SDimitry Andric if (!Data.isValidOffset(Offset))
628bcb0991SDimitry Andric return createStringError(std::errc::io_error,
638bcb0991SDimitry Andric "0x%8.8" PRIx64 ": missing LineTable MaxDelta", Offset);
648bcb0991SDimitry Andric int64_t MaxDelta = Data.getSLEB128(&Offset);
658bcb0991SDimitry Andric int64_t LineRange = MaxDelta - MinDelta + 1;
668bcb0991SDimitry Andric if (!Data.isValidOffset(Offset))
678bcb0991SDimitry Andric return createStringError(std::errc::io_error,
688bcb0991SDimitry Andric "0x%8.8" PRIx64 ": missing LineTable FirstLine", Offset);
698bcb0991SDimitry Andric const uint32_t FirstLine = (uint32_t)Data.getULEB128(&Offset);
708bcb0991SDimitry Andric LineEntry Row(BaseAddr, 1, FirstLine);
718bcb0991SDimitry Andric bool Done = false;
728bcb0991SDimitry Andric while (!Done) {
738bcb0991SDimitry Andric if (!Data.isValidOffset(Offset))
748bcb0991SDimitry Andric return createStringError(std::errc::io_error,
758bcb0991SDimitry Andric "0x%8.8" PRIx64 ": EOF found before EndSequence", Offset);
768bcb0991SDimitry Andric uint8_t Op = Data.getU8(&Offset);
778bcb0991SDimitry Andric switch (Op) {
788bcb0991SDimitry Andric case EndSequence:
798bcb0991SDimitry Andric Done = true;
808bcb0991SDimitry Andric break;
818bcb0991SDimitry Andric case SetFile:
828bcb0991SDimitry Andric if (!Data.isValidOffset(Offset))
838bcb0991SDimitry Andric return createStringError(std::errc::io_error,
848bcb0991SDimitry Andric "0x%8.8" PRIx64 ": EOF found before SetFile value",
858bcb0991SDimitry Andric Offset);
868bcb0991SDimitry Andric Row.File = (uint32_t)Data.getULEB128(&Offset);
878bcb0991SDimitry Andric break;
888bcb0991SDimitry Andric case AdvancePC:
898bcb0991SDimitry Andric if (!Data.isValidOffset(Offset))
908bcb0991SDimitry Andric return createStringError(std::errc::io_error,
918bcb0991SDimitry Andric "0x%8.8" PRIx64 ": EOF found before AdvancePC value",
928bcb0991SDimitry Andric Offset);
938bcb0991SDimitry Andric Row.Addr += Data.getULEB128(&Offset);
948bcb0991SDimitry Andric // If the function callback returns false, we stop parsing.
958bcb0991SDimitry Andric if (Callback(Row) == false)
968bcb0991SDimitry Andric return Error::success();
978bcb0991SDimitry Andric break;
988bcb0991SDimitry Andric case AdvanceLine:
998bcb0991SDimitry Andric if (!Data.isValidOffset(Offset))
1008bcb0991SDimitry Andric return createStringError(std::errc::io_error,
1018bcb0991SDimitry Andric "0x%8.8" PRIx64 ": EOF found before AdvanceLine value",
1028bcb0991SDimitry Andric Offset);
1038bcb0991SDimitry Andric Row.Line += Data.getSLEB128(&Offset);
1048bcb0991SDimitry Andric break;
1058bcb0991SDimitry Andric default: {
1068bcb0991SDimitry Andric // A byte that contains both address and line increment.
1078bcb0991SDimitry Andric uint8_t AdjustedOp = Op - FirstSpecial;
1088bcb0991SDimitry Andric int64_t LineDelta = MinDelta + (AdjustedOp % LineRange);
1098bcb0991SDimitry Andric uint64_t AddrDelta = (AdjustedOp / LineRange);
1108bcb0991SDimitry Andric Row.Line += LineDelta;
1118bcb0991SDimitry Andric Row.Addr += AddrDelta;
1128bcb0991SDimitry Andric // If the function callback returns false, we stop parsing.
1138bcb0991SDimitry Andric if (Callback(Row) == false)
1148bcb0991SDimitry Andric return Error::success();
1158bcb0991SDimitry Andric break;
1168bcb0991SDimitry Andric }
1178bcb0991SDimitry Andric }
1188bcb0991SDimitry Andric }
1198bcb0991SDimitry Andric return Error::success();
1208bcb0991SDimitry Andric }
1218bcb0991SDimitry Andric
encode(FileWriter & Out,uint64_t BaseAddr) const1228bcb0991SDimitry Andric llvm::Error LineTable::encode(FileWriter &Out, uint64_t BaseAddr) const {
1238bcb0991SDimitry Andric // Users must verify the LineTable is valid prior to calling this funtion.
1248bcb0991SDimitry Andric // We don't want to emit any LineTable objects if they are not valid since
1258bcb0991SDimitry Andric // it will waste space in the GSYM file.
1268bcb0991SDimitry Andric if (!isValid())
1278bcb0991SDimitry Andric return createStringError(std::errc::invalid_argument,
1288bcb0991SDimitry Andric "attempted to encode invalid LineTable object");
1298bcb0991SDimitry Andric
1308bcb0991SDimitry Andric int64_t MinLineDelta = INT64_MAX;
1318bcb0991SDimitry Andric int64_t MaxLineDelta = INT64_MIN;
1328bcb0991SDimitry Andric std::vector<DeltaInfo> DeltaInfos;
1338bcb0991SDimitry Andric if (Lines.size() == 1) {
1348bcb0991SDimitry Andric MinLineDelta = 0;
1358bcb0991SDimitry Andric MaxLineDelta = 0;
1368bcb0991SDimitry Andric } else {
1378bcb0991SDimitry Andric int64_t PrevLine = 1;
1388bcb0991SDimitry Andric bool First = true;
1398bcb0991SDimitry Andric for (const auto &line_entry : Lines) {
1408bcb0991SDimitry Andric if (First)
1418bcb0991SDimitry Andric First = false;
1428bcb0991SDimitry Andric else {
1438bcb0991SDimitry Andric int64_t LineDelta = (int64_t)line_entry.Line - PrevLine;
1448bcb0991SDimitry Andric auto End = DeltaInfos.end();
1458bcb0991SDimitry Andric auto Pos = std::lower_bound(DeltaInfos.begin(), End, LineDelta);
1468bcb0991SDimitry Andric if (Pos != End && Pos->Delta == LineDelta)
1478bcb0991SDimitry Andric ++Pos->Count;
1488bcb0991SDimitry Andric else
1498bcb0991SDimitry Andric DeltaInfos.insert(Pos, DeltaInfo(LineDelta, 1));
1508bcb0991SDimitry Andric if (LineDelta < MinLineDelta)
1518bcb0991SDimitry Andric MinLineDelta = LineDelta;
1528bcb0991SDimitry Andric if (LineDelta > MaxLineDelta)
1538bcb0991SDimitry Andric MaxLineDelta = LineDelta;
1548bcb0991SDimitry Andric }
1558bcb0991SDimitry Andric PrevLine = (int64_t)line_entry.Line;
1568bcb0991SDimitry Andric }
1578bcb0991SDimitry Andric assert(MinLineDelta <= MaxLineDelta);
1588bcb0991SDimitry Andric }
1598bcb0991SDimitry Andric // Set the min and max line delta intelligently based on the counts of
1608bcb0991SDimitry Andric // the line deltas. if our range is too large.
1618bcb0991SDimitry Andric const int64_t MaxLineRange = 14;
1628bcb0991SDimitry Andric if (MaxLineDelta - MinLineDelta > MaxLineRange) {
1638bcb0991SDimitry Andric uint32_t BestIndex = 0;
1648bcb0991SDimitry Andric uint32_t BestEndIndex = 0;
1658bcb0991SDimitry Andric uint32_t BestCount = 0;
1668bcb0991SDimitry Andric const size_t NumDeltaInfos = DeltaInfos.size();
1678bcb0991SDimitry Andric for (uint32_t I = 0; I < NumDeltaInfos; ++I) {
1688bcb0991SDimitry Andric const int64_t FirstDelta = DeltaInfos[I].Delta;
1698bcb0991SDimitry Andric uint32_t CurrCount = 0;
1708bcb0991SDimitry Andric uint32_t J;
1718bcb0991SDimitry Andric for (J = I; J < NumDeltaInfos; ++J) {
1728bcb0991SDimitry Andric auto LineRange = DeltaInfos[J].Delta - FirstDelta;
1738bcb0991SDimitry Andric if (LineRange > MaxLineRange)
1748bcb0991SDimitry Andric break;
1758bcb0991SDimitry Andric CurrCount += DeltaInfos[J].Count;
1768bcb0991SDimitry Andric }
1778bcb0991SDimitry Andric if (CurrCount > BestCount) {
1788bcb0991SDimitry Andric BestIndex = I;
1798bcb0991SDimitry Andric BestEndIndex = J - 1;
1808bcb0991SDimitry Andric BestCount = CurrCount;
1818bcb0991SDimitry Andric }
1828bcb0991SDimitry Andric }
1838bcb0991SDimitry Andric MinLineDelta = DeltaInfos[BestIndex].Delta;
1848bcb0991SDimitry Andric MaxLineDelta = DeltaInfos[BestEndIndex].Delta;
1858bcb0991SDimitry Andric }
1868bcb0991SDimitry Andric if (MinLineDelta == MaxLineDelta && MinLineDelta > 0 &&
1878bcb0991SDimitry Andric MinLineDelta < MaxLineRange)
1888bcb0991SDimitry Andric MinLineDelta = 0;
1898bcb0991SDimitry Andric assert(MinLineDelta <= MaxLineDelta);
1908bcb0991SDimitry Andric
1918bcb0991SDimitry Andric // Initialize the line entry state as a starting point. All line entries
1928bcb0991SDimitry Andric // will be deltas from this.
1938bcb0991SDimitry Andric LineEntry Prev(BaseAddr, 1, Lines.front().Line);
1948bcb0991SDimitry Andric
1958bcb0991SDimitry Andric // Write out the min and max line delta as signed LEB128.
1968bcb0991SDimitry Andric Out.writeSLEB(MinLineDelta);
1978bcb0991SDimitry Andric Out.writeSLEB(MaxLineDelta);
1988bcb0991SDimitry Andric // Write out the starting line number as a unsigned LEB128.
1998bcb0991SDimitry Andric Out.writeULEB(Prev.Line);
2008bcb0991SDimitry Andric
2018bcb0991SDimitry Andric for (const auto &Curr : Lines) {
2028bcb0991SDimitry Andric if (Curr.Addr < BaseAddr)
2038bcb0991SDimitry Andric return createStringError(std::errc::invalid_argument,
2048bcb0991SDimitry Andric "LineEntry has address 0x%" PRIx64 " which is "
2058bcb0991SDimitry Andric "less than the function start address 0x%"
2068bcb0991SDimitry Andric PRIx64, Curr.Addr, BaseAddr);
2078bcb0991SDimitry Andric if (Curr.Addr < Prev.Addr)
2088bcb0991SDimitry Andric return createStringError(std::errc::invalid_argument,
2098bcb0991SDimitry Andric "LineEntry in LineTable not in ascending order");
2108bcb0991SDimitry Andric const uint64_t AddrDelta = Curr.Addr - Prev.Addr;
2118bcb0991SDimitry Andric int64_t LineDelta = 0;
2128bcb0991SDimitry Andric if (Curr.Line > Prev.Line)
2138bcb0991SDimitry Andric LineDelta = Curr.Line - Prev.Line;
2148bcb0991SDimitry Andric else if (Prev.Line > Curr.Line)
2158bcb0991SDimitry Andric LineDelta = -((int32_t)(Prev.Line - Curr.Line));
2168bcb0991SDimitry Andric
2178bcb0991SDimitry Andric // Set the file if it doesn't match the current one.
2188bcb0991SDimitry Andric if (Curr.File != Prev.File) {
2198bcb0991SDimitry Andric Out.writeU8(SetFile);
2208bcb0991SDimitry Andric Out.writeULEB(Curr.File);
2218bcb0991SDimitry Andric }
2228bcb0991SDimitry Andric
2238bcb0991SDimitry Andric uint8_t SpecialOp;
2248bcb0991SDimitry Andric if (encodeSpecial(MinLineDelta, MaxLineDelta, LineDelta, AddrDelta,
2258bcb0991SDimitry Andric SpecialOp)) {
2268bcb0991SDimitry Andric // Advance the PC and line and push a row.
2278bcb0991SDimitry Andric Out.writeU8(SpecialOp);
2288bcb0991SDimitry Andric } else {
2298bcb0991SDimitry Andric // We can't encode the address delta and line delta into
2308bcb0991SDimitry Andric // a single special opcode, we must do them separately.
2318bcb0991SDimitry Andric
2328bcb0991SDimitry Andric // Advance the line.
2338bcb0991SDimitry Andric if (LineDelta != 0) {
2348bcb0991SDimitry Andric Out.writeU8(AdvanceLine);
2358bcb0991SDimitry Andric Out.writeSLEB(LineDelta);
2368bcb0991SDimitry Andric }
2378bcb0991SDimitry Andric
2388bcb0991SDimitry Andric // Advance the PC and push a row.
2398bcb0991SDimitry Andric Out.writeU8(AdvancePC);
2408bcb0991SDimitry Andric Out.writeULEB(AddrDelta);
2418bcb0991SDimitry Andric }
2428bcb0991SDimitry Andric Prev = Curr;
2438bcb0991SDimitry Andric }
2448bcb0991SDimitry Andric Out.writeU8(EndSequence);
2458bcb0991SDimitry Andric return Error::success();
2468bcb0991SDimitry Andric }
2478bcb0991SDimitry Andric
2488bcb0991SDimitry Andric // Parse all line table entries into the "LineTable" vector. We can
2498bcb0991SDimitry Andric // cache the results of this if needed, or we can call LineTable::lookup()
2508bcb0991SDimitry Andric // below.
decode(DataExtractor & Data,uint64_t BaseAddr)2518bcb0991SDimitry Andric llvm::Expected<LineTable> LineTable::decode(DataExtractor &Data,
2528bcb0991SDimitry Andric uint64_t BaseAddr) {
2538bcb0991SDimitry Andric LineTable LT;
2548bcb0991SDimitry Andric llvm::Error Err = parse(Data, BaseAddr, [&](const LineEntry &Row) -> bool {
2558bcb0991SDimitry Andric LT.Lines.push_back(Row);
2568bcb0991SDimitry Andric return true; // Keep parsing by returning true.
2578bcb0991SDimitry Andric });
2588bcb0991SDimitry Andric if (Err)
2598bcb0991SDimitry Andric return std::move(Err);
2608bcb0991SDimitry Andric return LT;
2618bcb0991SDimitry Andric }
2628bcb0991SDimitry Andric // Parse the line table on the fly and find the row we are looking for.
2638bcb0991SDimitry Andric // We will need to determine if we need to cache the line table by calling
2648bcb0991SDimitry Andric // LineTable::parseAllEntries(...) or just call this function each time.
265*480093f4SDimitry Andric // There is a CPU vs memory tradeoff we will need to determined.
lookup(DataExtractor & Data,uint64_t BaseAddr,uint64_t Addr)266*480093f4SDimitry Andric Expected<LineEntry> LineTable::lookup(DataExtractor &Data, uint64_t BaseAddr, uint64_t Addr) {
2678bcb0991SDimitry Andric LineEntry Result;
2688bcb0991SDimitry Andric llvm::Error Err = parse(Data, BaseAddr,
2698bcb0991SDimitry Andric [Addr, &Result](const LineEntry &Row) -> bool {
2708bcb0991SDimitry Andric if (Addr < Row.Addr)
2718bcb0991SDimitry Andric return false; // Stop parsing, result contains the line table row!
2728bcb0991SDimitry Andric Result = Row;
2738bcb0991SDimitry Andric return true; // Keep parsing till we find the right row.
2748bcb0991SDimitry Andric });
275*480093f4SDimitry Andric if (Err)
276*480093f4SDimitry Andric return std::move(Err);
277*480093f4SDimitry Andric if (Result.isValid())
2788bcb0991SDimitry Andric return Result;
279*480093f4SDimitry Andric return createStringError(std::errc::invalid_argument,
280*480093f4SDimitry Andric "address 0x%" PRIx64 " is not in the line table",
281*480093f4SDimitry Andric Addr);
2828bcb0991SDimitry Andric }
2838bcb0991SDimitry Andric
operator <<(raw_ostream & OS,const LineTable & LT)2848bcb0991SDimitry Andric raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const LineTable <) {
2858bcb0991SDimitry Andric for (const auto &LineEntry : LT)
2868bcb0991SDimitry Andric OS << LineEntry << '\n';
2878bcb0991SDimitry Andric return OS;
2888bcb0991SDimitry Andric }
289