LineTable.cpp revision 360784 
1//===- LineTable.cpp --------------------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/DebugInfo/GSYM/LineTable.h"
10#include "llvm/DebugInfo/GSYM/FileWriter.h"
11#include "llvm/Support/DataExtractor.h"
12
13using namespace llvm;
14using namespace gsym;
15
16enum LineTableOpCode {
17  EndSequence = 0x00,  ///< End of the line table.
18  SetFile = 0x01,      ///< Set LineTableRow.file_idx, don't push a row.
19  AdvancePC = 0x02,    ///< Increment LineTableRow.address, and push a row.
20  AdvanceLine = 0x03,  ///< Set LineTableRow.file_line, don't push a row.
21  FirstSpecial = 0x04, ///< All special opcodes push a row.
22};
23
24struct DeltaInfo {
25  int64_t Delta;
26  uint32_t Count;
27  DeltaInfo(int64_t D, uint32_t C) : Delta(D), Count(C) {}
28};
29
30inline bool operator<(const DeltaInfo &LHS, int64_t Delta) {
31  return LHS.Delta < Delta;
32}
33
34static bool encodeSpecial(int64_t MinLineDelta, int64_t MaxLineDelta,
35                          int64_t LineDelta, uint64_t AddrDelta,
36                          uint8_t &SpecialOp) {
37  if (LineDelta < MinLineDelta)
38    return false;
39  if (LineDelta > MaxLineDelta)
40    return false;
41  int64_t LineRange = MaxLineDelta - MinLineDelta + 1;
42  int64_t AdjustedOp = ((LineDelta - MinLineDelta) + AddrDelta * LineRange);
43  int64_t Op = AdjustedOp + FirstSpecial;
44  if (Op < 0)
45    return false;
46  if (Op > 255)
47    return false;
48  SpecialOp = (uint8_t)Op;
49  return true;
50}
51
52typedef std::function<bool(const LineEntry &Row)> LineEntryCallback;
53
54static llvm::Error parse(DataExtractor &Data, uint64_t BaseAddr,
55                         LineEntryCallback const &Callback) {
56  uint64_t Offset = 0;
57  if (!Data.isValidOffset(Offset))
58    return createStringError(std::errc::io_error,
59        "0x%8.8" PRIx64 ": missing LineTable MinDelta", Offset);
60  int64_t MinDelta = Data.getSLEB128(&Offset);
61  if (!Data.isValidOffset(Offset))
62    return createStringError(std::errc::io_error,
63        "0x%8.8" PRIx64 ": missing LineTable MaxDelta", Offset);
64  int64_t MaxDelta = Data.getSLEB128(&Offset);
65  int64_t LineRange = MaxDelta - MinDelta + 1;
66  if (!Data.isValidOffset(Offset))
67    return createStringError(std::errc::io_error,
68        "0x%8.8" PRIx64 ": missing LineTable FirstLine", Offset);
69  const uint32_t FirstLine = (uint32_t)Data.getULEB128(&Offset);
70  LineEntry Row(BaseAddr, 1, FirstLine);
71  bool Done = false;
72  while (!Done) {
73    if (!Data.isValidOffset(Offset))
74      return createStringError(std::errc::io_error,
75          "0x%8.8" PRIx64 ": EOF found before EndSequence", Offset);
76    uint8_t Op = Data.getU8(&Offset);
77    switch (Op) {
78    case EndSequence:
79      Done = true;
80      break;
81    case SetFile:
82      if (!Data.isValidOffset(Offset))
83        return createStringError(std::errc::io_error,
84            "0x%8.8" PRIx64 ": EOF found before SetFile value",
85            Offset);
86      Row.File = (uint32_t)Data.getULEB128(&Offset);
87      break;
88    case AdvancePC:
89      if (!Data.isValidOffset(Offset))
90        return createStringError(std::errc::io_error,
91            "0x%8.8" PRIx64 ": EOF found before AdvancePC value",
92            Offset);
93      Row.Addr += Data.getULEB128(&Offset);
94      // If the function callback returns false, we stop parsing.
95      if (Callback(Row) == false)
96        return Error::success();
97      break;
98    case AdvanceLine:
99      if (!Data.isValidOffset(Offset))
100        return createStringError(std::errc::io_error,
101            "0x%8.8" PRIx64 ": EOF found before AdvanceLine value",
102            Offset);
103      Row.Line += Data.getSLEB128(&Offset);
104      break;
105    default: {
106        // A byte that contains both address and line increment.
107        uint8_t AdjustedOp = Op - FirstSpecial;
108        int64_t LineDelta = MinDelta + (AdjustedOp % LineRange);
109        uint64_t AddrDelta = (AdjustedOp / LineRange);
110        Row.Line += LineDelta;
111        Row.Addr += AddrDelta;
112        // If the function callback returns false, we stop parsing.
113        if (Callback(Row) == false)
114          return Error::success();
115        break;
116      }
117    }
118  }
119  return Error::success();
120}
121
122llvm::Error LineTable::encode(FileWriter &Out, uint64_t BaseAddr) const {
123  // Users must verify the LineTable is valid prior to calling this funtion.
124  // We don't want to emit any LineTable objects if they are not valid since
125  // it will waste space in the GSYM file.
126  if (!isValid())
127    return createStringError(std::errc::invalid_argument,
128                             "attempted to encode invalid LineTable object");
129
130  int64_t MinLineDelta = INT64_MAX;
131  int64_t MaxLineDelta = INT64_MIN;
132  std::vector<DeltaInfo> DeltaInfos;
133  if (Lines.size() == 1) {
134    MinLineDelta = 0;
135    MaxLineDelta = 0;
136  } else {
137    int64_t PrevLine = 1;
138    bool First = true;
139    for (const auto &line_entry : Lines) {
140      if (First)
141        First = false;
142      else {
143        int64_t LineDelta = (int64_t)line_entry.Line - PrevLine;
144        auto End = DeltaInfos.end();
145        auto Pos = std::lower_bound(DeltaInfos.begin(), End, LineDelta);
146        if (Pos != End && Pos->Delta == LineDelta)
147          ++Pos->Count;
148        else
149          DeltaInfos.insert(Pos, DeltaInfo(LineDelta, 1));
150        if (LineDelta < MinLineDelta)
151          MinLineDelta = LineDelta;
152        if (LineDelta > MaxLineDelta)
153          MaxLineDelta = LineDelta;
154      }
155      PrevLine = (int64_t)line_entry.Line;
156    }
157    assert(MinLineDelta <= MaxLineDelta);
158  }
159  // Set the min and max line delta intelligently based on the counts of
160  // the line deltas. if our range is too large.
161  const int64_t MaxLineRange = 14;
162  if (MaxLineDelta - MinLineDelta > MaxLineRange) {
163    uint32_t BestIndex = 0;
164    uint32_t BestEndIndex = 0;
165    uint32_t BestCount = 0;
166    const size_t NumDeltaInfos = DeltaInfos.size();
167    for (uint32_t I = 0; I < NumDeltaInfos; ++I) {
168      const int64_t FirstDelta = DeltaInfos[I].Delta;
169      uint32_t CurrCount = 0;
170      uint32_t J;
171      for (J = I; J < NumDeltaInfos; ++J) {
172        auto LineRange = DeltaInfos[J].Delta - FirstDelta;
173        if (LineRange > MaxLineRange)
174          break;
175        CurrCount += DeltaInfos[J].Count;
176      }
177      if (CurrCount > BestCount) {
178        BestIndex = I;
179        BestEndIndex = J - 1;
180        BestCount = CurrCount;
181      }
182    }
183    MinLineDelta = DeltaInfos[BestIndex].Delta;
184    MaxLineDelta = DeltaInfos[BestEndIndex].Delta;
185  }
186  if (MinLineDelta == MaxLineDelta && MinLineDelta > 0 &&
187      MinLineDelta < MaxLineRange)
188    MinLineDelta = 0;
189  assert(MinLineDelta <= MaxLineDelta);
190
191  // Initialize the line entry state as a starting point. All line entries
192  // will be deltas from this.
193  LineEntry Prev(BaseAddr, 1, Lines.front().Line);
194
195  // Write out the min and max line delta as signed LEB128.
196  Out.writeSLEB(MinLineDelta);
197  Out.writeSLEB(MaxLineDelta);
198  // Write out the starting line number as a unsigned LEB128.
199  Out.writeULEB(Prev.Line);
200
201  for (const auto &Curr : Lines) {
202    if (Curr.Addr < BaseAddr)
203      return createStringError(std::errc::invalid_argument,
204                               "LineEntry has address 0x%" PRIx64 " which is "
205                               "less than the function start address 0x%"
206                               PRIx64, Curr.Addr, BaseAddr);
207    if (Curr.Addr < Prev.Addr)
208      return createStringError(std::errc::invalid_argument,
209                               "LineEntry in LineTable not in ascending order");
210    const uint64_t AddrDelta = Curr.Addr - Prev.Addr;
211    int64_t LineDelta = 0;
212    if (Curr.Line > Prev.Line)
213      LineDelta = Curr.Line - Prev.Line;
214    else if (Prev.Line > Curr.Line)
215      LineDelta = -((int32_t)(Prev.Line - Curr.Line));
216
217    // Set the file if it doesn't match the current one.
218    if (Curr.File != Prev.File) {
219      Out.writeU8(SetFile);
220      Out.writeULEB(Curr.File);
221    }
222
223    uint8_t SpecialOp;
224    if (encodeSpecial(MinLineDelta, MaxLineDelta, LineDelta, AddrDelta,
225                      SpecialOp)) {
226      // Advance the PC and line and push a row.
227      Out.writeU8(SpecialOp);
228    } else {
229      // We can't encode the address delta and line delta into
230      // a single special opcode, we must do them separately.
231
232      // Advance the line.
233      if (LineDelta != 0) {
234        Out.writeU8(AdvanceLine);
235        Out.writeSLEB(LineDelta);
236      }
237
238      // Advance the PC and push a row.
239      Out.writeU8(AdvancePC);
240      Out.writeULEB(AddrDelta);
241    }
242    Prev = Curr;
243  }
244  Out.writeU8(EndSequence);
245  return Error::success();
246}
247
248// Parse all line table entries into the "LineTable" vector. We can
249// cache the results of this if needed, or we can call LineTable::lookup()
250// below.
251llvm::Expected<LineTable> LineTable::decode(DataExtractor &Data,
252                                            uint64_t BaseAddr) {
253  LineTable LT;
254  llvm::Error Err = parse(Data, BaseAddr, [&](const LineEntry &Row) -> bool {
255    LT.Lines.push_back(Row);
256    return true; // Keep parsing by returning true.
257  });
258  if (Err)
259    return std::move(Err);
260  return LT;
261}
262// Parse the line table on the fly and find the row we are looking for.
263// We will need to determine if we need to cache the line table by calling
264// LineTable::parseAllEntries(...) or just call this function each time.
265// There is a CPU vs memory tradeoff we will need to determined.
266Expected<LineEntry> LineTable::lookup(DataExtractor &Data, uint64_t BaseAddr, uint64_t Addr) {
267  LineEntry Result;
268  llvm::Error Err = parse(Data, BaseAddr,
269                          [Addr, &Result](const LineEntry &Row) -> bool {
270    if (Addr < Row.Addr)
271      return false; // Stop parsing, result contains the line table row!
272    Result = Row;
273    if (Addr == Row.Addr) {
274      // Stop parsing, this is the row we are looking for since the address
275      // matches.
276      return false;
277    }
278    return true; // Keep parsing till we find the right row.
279  });
280  if (Err)
281    return std::move(Err);
282  if (Result.isValid())
283    return Result;
284  return createStringError(std::errc::invalid_argument,
285                           "address 0x%" PRIx64 " is not in the line table",
286                           Addr);
287}
288
289raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const LineTable &LT) {
290  for (const auto &LineEntry : LT)
291    OS << LineEntry << '\n';
292  return OS;
293}
294