lib/DebugInfo/GSYM/LineTable.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-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 determine.
 266 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   return Result;
 281 }
 282
 283 raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const LineTable &LT) {
 284   for (const auto &LineEntry : LT)
 285     OS << LineEntry << '\n';
 286   return OS;
 287 }