289 lines · cpp
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-exception6//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 since125 // 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 else149 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 of160 // 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 entries192 // 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 into230 // 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 can249// 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 calling264// 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 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 284raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const LineTable <) {285 for (const auto &LineEntry : LT)286 OS << LineEntry << '\n';287 return OS;288}289