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; 27 DeltaInfo(int64_t D, uint32_t C) : Delta(D), Count(C) {} 28 }; 29 30 inline bool operator<(const DeltaInfo &LHS, int64_t Delta) { 31 return LHS.Delta < Delta; 32 } 33 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 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 122 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. 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. 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 284 raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const LineTable <) { 285 for (const auto &LineEntry : LT) 286 OS << LineEntry << '\n'; 287 return OS; 288 } 289