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 
13 using namespace llvm;
14 using namespace gsym;
15 
16 enum 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 
24 struct DeltaInfo {
25   int64_t Delta;
26   uint32_t Count;
DeltaInfoDeltaInfo27   DeltaInfo(int64_t D, uint32_t C) : Delta(D), Count(C) {}
28 };
29 
operator <(const DeltaInfo & LHS,int64_t Delta)30 inline bool operator<(const DeltaInfo &LHS, int64_t Delta) {
31   return LHS.Delta < Delta;
32 }
33 
encodeSpecial(int64_t MinLineDelta,int64_t MaxLineDelta,int64_t LineDelta,uint64_t AddrDelta,uint8_t & SpecialOp)34 static 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 
52 typedef std::function<bool(const LineEntry &Row)> LineEntryCallback;
53 
parse(DataExtractor & Data,uint64_t BaseAddr,LineEntryCallback const & Callback)54 static 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 
encode(FileWriter & Out,uint64_t BaseAddr) const122 llvm::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.
decode(DataExtractor & Data,uint64_t BaseAddr)251 llvm::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.
lookup(DataExtractor & Data,uint64_t BaseAddr,uint64_t Addr)266 Expected<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     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(std::errc::invalid_argument,
280                            "address 0x%" PRIx64 " is not in the line table",
281                            Addr);
282 }
283 
operator <<(raw_ostream & OS,const LineTable & LT)284 raw_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