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: Offset))
58 return createStringError(EC: std::errc::io_error,
59 Fmt: "0x%8.8" PRIx64 ": missing LineTable MinDelta", Vals: Offset);
60 int64_t MinDelta = Data.getSLEB128(OffsetPtr: &Offset);
61 if (!Data.isValidOffset(offset: Offset))
62 return createStringError(EC: std::errc::io_error,
63 Fmt: "0x%8.8" PRIx64 ": missing LineTable MaxDelta", Vals: Offset);
64 int64_t MaxDelta = Data.getSLEB128(OffsetPtr: &Offset);
65 int64_t LineRange = MaxDelta - MinDelta + 1;
66 if (!Data.isValidOffset(offset: Offset))
67 return createStringError(EC: std::errc::io_error,
68 Fmt: "0x%8.8" PRIx64 ": missing LineTable FirstLine", Vals: Offset);
69 const uint32_t FirstLine = (uint32_t)Data.getULEB128(offset_ptr: &Offset);
70 LineEntry Row(BaseAddr, 1, FirstLine);
71 bool Done = false;
72 while (!Done) {
73 if (!Data.isValidOffset(offset: Offset))
74 return createStringError(EC: std::errc::io_error,
75 Fmt: "0x%8.8" PRIx64 ": EOF found before EndSequence", Vals: Offset);
76 uint8_t Op = Data.getU8(offset_ptr: &Offset);
77 switch (Op) {
78 case EndSequence:
79 Done = true;
80 break;
81 case SetFile:
82 if (!Data.isValidOffset(offset: Offset))
83 return createStringError(EC: std::errc::io_error,
84 Fmt: "0x%8.8" PRIx64 ": EOF found before SetFile value",
85 Vals: Offset);
86 Row.File = (uint32_t)Data.getULEB128(offset_ptr: &Offset);
87 break;
88 case AdvancePC:
89 if (!Data.isValidOffset(offset: Offset))
90 return createStringError(EC: std::errc::io_error,
91 Fmt: "0x%8.8" PRIx64 ": EOF found before AdvancePC value",
92 Vals: Offset);
93 Row.Addr += Data.getULEB128(offset_ptr: &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: Offset))
100 return createStringError(EC: std::errc::io_error,
101 Fmt: "0x%8.8" PRIx64 ": EOF found before AdvanceLine value",
102 Vals: Offset);
103 Row.Line += Data.getSLEB128(OffsetPtr: &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(EC: std::errc::invalid_argument,
128 Fmt: "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(first: DeltaInfos.begin(), last: End, val: LineDelta);
146 if (Pos != End && Pos->Delta == LineDelta)
147 ++Pos->Count;
148 else
149 DeltaInfos.insert(position: Pos, x: 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(Value: MinLineDelta);
197 Out.writeSLEB(Value: MaxLineDelta);
198 // Write out the starting line number as a unsigned LEB128.
199 Out.writeULEB(Value: Prev.Line);
200
201 for (const auto &Curr : Lines) {
202 if (Curr.Addr < BaseAddr)
203 return createStringError(EC: std::errc::invalid_argument,
204 Fmt: "LineEntry has address 0x%" PRIx64 " which is "
205 "less than the function start address 0x%"
206 PRIx64, Vals: Curr.Addr, Vals: BaseAddr);
207 if (Curr.Addr < Prev.Addr)
208 return createStringError(EC: std::errc::invalid_argument,
209 Fmt: "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(Value: SetFile);
220 Out.writeULEB(Value: 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(Value: 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(Value: AdvanceLine);
235 Out.writeSLEB(Value: LineDelta);
236 }
237
238 // Advance the PC and push a row.
239 Out.writeU8(Value: AdvancePC);
240 Out.writeULEB(Value: AddrDelta);
241 }
242 Prev = Curr;
243 }
244 Out.writeU8(Value: 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, Callback: [&](const LineEntry &Row) -> bool {
255 LT.Lines.push_back(x: 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 Callback: [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 return true; // Keep parsing till we find the right row.
274 });
275 if (Err)
276 return std::move(Err);
277 if (Result.isValid())
278 return Result;
279 return createStringError(EC: std::errc::invalid_argument,
280 Fmt: "address 0x%" PRIx64 " is not in the line table",
281 Vals: Addr);
282}
283
284raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const LineTable &LT) {
285 for (const auto &LineEntry : LT)
286 OS << LineEntry << '\n';
287 return OS;
288}
289