lldb/source/Target/TraceDumper.cpp

   1 //===-- TraceDumper.cpp ---------------------------------------------------===//
   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 "lldb/Target/TraceDumper.h"
  10 #include "lldb/Core/Module.h"
  11 #include "lldb/Symbol/CompileUnit.h"
  12 #include "lldb/Symbol/Function.h"
  13 #include "lldb/Target/ExecutionContext.h"
  14 #include "lldb/Target/Process.h"
  15 #include "lldb/Target/SectionLoadList.h"
  16 #include <optional>
  17
  18 using namespace lldb;
  19 using namespace lldb_private;
  20 using namespace llvm;
  21
  22 /// \return
  23 ///   The given string or \b std::nullopt if it's empty.
  24 static std::optional<const char *> ToOptionalString(const char *s) {
  25   if (!s)
  26     return std::nullopt;
  27   return s;
  28 }
  29
  30 static const char *GetModuleName(const SymbolContext &sc) {
  31   if (!sc.module_sp)
  32     return nullptr;
  33   return sc.module_sp->GetFileSpec().GetFilename().AsCString();
  34 }
  35
  36 /// \return
  37 ///   The module name (basename if the module is a file, or the actual name if
  38 ///   it's a virtual module), or \b nullptr if no name nor module was found.
  39 static const char *GetModuleName(const TraceDumper::TraceItem &item) {
  40   if (!item.symbol_info)
  41     return nullptr;
  42   return GetModuleName(item.symbol_info->sc);
  43 }
  44
  45 // This custom LineEntry validator is neded because some line_entries have
  46 // 0 as line, which is meaningless. Notice that LineEntry::IsValid only
  47 // checks that line is not LLDB_INVALID_LINE_NUMBER, i.e. UINT32_MAX.
  48 static bool IsLineEntryValid(const LineEntry &line_entry) {
  49   return line_entry.IsValid() && line_entry.line > 0;
  50 }
  51
  52 /// \return
  53 ///     \b true if the provided line entries match line, column and source file.
  54 ///     This function assumes that the line entries are valid.
  55 static bool FileLineAndColumnMatches(const LineEntry &a, const LineEntry &b) {
  56   if (a.line != b.line)
  57     return false;
  58   if (a.column != b.column)
  59     return false;
  60   return a.GetFile() == b.GetFile();
  61 }
  62
  63 /// Compare the symbol contexts of the provided \a SymbolInfo
  64 /// objects.
  65 ///
  66 /// \return
  67 ///     \a true if both instructions belong to the same scope level analized
  68 ///     in the following order:
  69 ///       - module
  70 ///       - symbol
  71 ///       - function
  72 ///       - inlined function
  73 ///       - source line info
  74 static bool
  75 IsSameInstructionSymbolContext(const TraceDumper::SymbolInfo &prev_insn,
  76                                const TraceDumper::SymbolInfo &insn,
  77                                bool check_source_line_info = true) {
  78   // module checks
  79   if (insn.sc.module_sp != prev_insn.sc.module_sp)
  80     return false;
  81
  82   // symbol checks
  83   if (insn.sc.symbol != prev_insn.sc.symbol)
  84     return false;
  85
  86   // function checks
  87   if (!insn.sc.function && !prev_insn.sc.function)
  88     return true; // This means two dangling instruction in the same module. We
  89                  // can assume they are part of the same unnamed symbol
  90   else if (insn.sc.function != prev_insn.sc.function)
  91     return false;
  92
  93   Block *inline_block_a =
  94       insn.sc.block ? insn.sc.block->GetContainingInlinedBlock() : nullptr;
  95   Block *inline_block_b = prev_insn.sc.block
  96                               ? prev_insn.sc.block->GetContainingInlinedBlock()
  97                               : nullptr;
  98   if (inline_block_a != inline_block_b)
  99     return false;
 100
 101   // line entry checks
 102   if (!check_source_line_info)
 103     return true;
 104
 105   const bool curr_line_valid = IsLineEntryValid(insn.sc.line_entry);
 106   const bool prev_line_valid = IsLineEntryValid(prev_insn.sc.line_entry);
 107   if (curr_line_valid && prev_line_valid)
 108     return FileLineAndColumnMatches(insn.sc.line_entry,
 109                                     prev_insn.sc.line_entry);
 110   return curr_line_valid == prev_line_valid;
 111 }
 112
 113 class OutputWriterCLI : public TraceDumper::OutputWriter {
 114 public:
 115   OutputWriterCLI(Stream &s, const TraceDumperOptions &options, Thread &thread)
 116       : m_s(s), m_options(options) {
 117     m_s.Format("thread #{0}: tid = {1}\n", thread.GetIndexID(), thread.GetID());
 118   };
 119
 120   void NoMoreData() override { m_s << "    no more data\n"; }
 121
 122   void FunctionCallForest(
 123       const std::vector<TraceDumper::FunctionCallUP> &forest) override {
 124     for (size_t i = 0; i < forest.size(); i++) {
 125       m_s.Format("\n[call tree #{0}]\n", i);
 126       DumpFunctionCallTree(*forest[i]);
 127     }
 128   }
 129
 130   void TraceItem(const TraceDumper::TraceItem &item) override {
 131     if (item.symbol_info) {
 132       if (!item.prev_symbol_info ||
 133           !IsSameInstructionSymbolContext(*item.prev_symbol_info,
 134                                           *item.symbol_info)) {
 135         m_s << "  ";
 136         const char *module_name = GetModuleName(item);
 137         if (!module_name)
 138           m_s << "(none)";
 139         else if (!item.symbol_info->sc.function && !item.symbol_info->sc.symbol)
 140           m_s.Format("{0}`(none)", module_name);
 141         else
 142           item.symbol_info->sc.DumpStopContext(
 143               &m_s, item.symbol_info->exe_ctx.GetTargetPtr(),
 144               item.symbol_info->address,
 145               /*show_fullpaths=*/false,
 146               /*show_module=*/true, /*show_inlined_frames=*/false,
 147               /*show_function_arguments=*/true,
 148               /*show_function_name=*/true);
 149         m_s << "\n";
 150       }
 151     }
 152
 153     if (item.error && !m_was_prev_instruction_an_error)
 154       m_s << "    ...missing instructions\n";
 155
 156     m_s.Format("    {0}: ", item.id);
 157
 158     if (m_options.show_timestamps) {
 159       m_s.Format("[{0}] ", item.timestamp
 160                                ? formatv("{0:3} ns", *item.timestamp).str()
 161                                : "unavailable");
 162     }
 163
 164     if (item.event) {
 165       m_s << "(event) " << TraceCursor::EventKindToString(*item.event);
 166       switch (*item.event) {
 167       case eTraceEventCPUChanged:
 168         m_s.Format(" [new CPU={0}]",
 169                    item.cpu_id ? std::to_string(*item.cpu_id) : "unavailable");
 170         break;
 171       case eTraceEventHWClockTick:
 172         m_s.Format(" [{0}]", item.hw_clock ? std::to_string(*item.hw_clock)
 173                                            : "unavailable");
 174         break;
 175       case eTraceEventDisabledHW:
 176       case eTraceEventDisabledSW:
 177         break;
 178       case eTraceEventSyncPoint:
 179         m_s.Format(" [{0}]", item.sync_point_metadata);
 180         break;
 181       }
 182     } else if (item.error) {
 183       m_s << "(error) " << *item.error;
 184     } else {
 185       m_s.Format("{0:x+16}", item.load_address);
 186       if (item.symbol_info && item.symbol_info->instruction) {
 187         m_s << "    ";
 188         item.symbol_info->instruction->Dump(
 189             &m_s, /*max_opcode_byte_size=*/0,
 190             /*show_address=*/false,
 191             /*show_bytes=*/false, m_options.show_control_flow_kind,
 192             &item.symbol_info->exe_ctx, &item.symbol_info->sc,
 193             /*prev_sym_ctx=*/nullptr,
 194             /*disassembly_addr_format=*/nullptr,
 195             /*max_address_text_size=*/0);
 196       }
 197     }
 198
 199     m_was_prev_instruction_an_error = (bool)item.error;
 200     m_s << "\n";
 201   }
 202
 203 private:
 204   void
 205   DumpSegmentContext(const TraceDumper::FunctionCall::TracedSegment &segment) {
 206     if (segment.GetOwningCall().IsError()) {
 207       m_s << "<tracing errors>";
 208       return;
 209     }
 210
 211     const SymbolContext &first_sc = segment.GetFirstInstructionSymbolInfo().sc;
 212     first_sc.DumpStopContext(
 213         &m_s, segment.GetFirstInstructionSymbolInfo().exe_ctx.GetTargetPtr(),
 214         segment.GetFirstInstructionSymbolInfo().address,
 215         /*show_fullpaths=*/false,
 216         /*show_module=*/true, /*show_inlined_frames=*/false,
 217         /*show_function_arguments=*/true,
 218         /*show_function_name=*/true);
 219     m_s << " to ";
 220     const SymbolContext &last_sc = segment.GetLastInstructionSymbolInfo().sc;
 221     if (IsLineEntryValid(first_sc.line_entry) &&
 222         IsLineEntryValid(last_sc.line_entry)) {
 223       m_s.Format("{0}:{1}", last_sc.line_entry.line, last_sc.line_entry.column);
 224     } else {
 225       last_sc.DumpStopContext(
 226           &m_s, segment.GetFirstInstructionSymbolInfo().exe_ctx.GetTargetPtr(),
 227           segment.GetLastInstructionSymbolInfo().address,
 228           /*show_fullpaths=*/false,
 229           /*show_module=*/false, /*show_inlined_frames=*/false,
 230           /*show_function_arguments=*/false,
 231           /*show_function_name=*/false);
 232     }
 233   }
 234
 235   void DumpUntracedContext(const TraceDumper::FunctionCall &function_call) {
 236     if (function_call.IsError()) {
 237       m_s << "tracing error";
 238     }
 239     const SymbolContext &sc = function_call.GetSymbolInfo().sc;
 240
 241     const char *module_name = GetModuleName(sc);
 242     if (!module_name)
 243       m_s << "(none)";
 244     else if (!sc.function && !sc.symbol)
 245       m_s << module_name << "`(none)";
 246     else
 247       m_s << module_name << "`" << sc.GetFunctionName().AsCString();
 248   }
 249
 250   void DumpFunctionCallTree(const TraceDumper::FunctionCall &function_call) {
 251     if (function_call.GetUntracedPrefixSegment()) {
 252       m_s.Indent();
 253       DumpUntracedContext(function_call);
 254       m_s << "\n";
 255
 256       m_s.IndentMore();
 257       DumpFunctionCallTree(function_call.GetUntracedPrefixSegment()->GetNestedCall());
 258       m_s.IndentLess();
 259     }
 260
 261     for (const TraceDumper::FunctionCall::TracedSegment &segment :
 262          function_call.GetTracedSegments()) {
 263       m_s.Indent();
 264       DumpSegmentContext(segment);
 265       m_s.Format("  [{0}, {1}]\n", segment.GetFirstInstructionID(),
 266                  segment.GetLastInstructionID());
 267
 268       segment.IfNestedCall([&](const TraceDumper::FunctionCall &nested_call) {
 269         m_s.IndentMore();
 270         DumpFunctionCallTree(nested_call);
 271         m_s.IndentLess();
 272       });
 273     }
 274   }
 275
 276   Stream &m_s;
 277   TraceDumperOptions m_options;
 278   bool m_was_prev_instruction_an_error = false;
 279 };
 280
 281 class OutputWriterJSON : public TraceDumper::OutputWriter {
 282   /* schema:
 283     error_message: string
 284     | {
 285       "event": string,
 286       "id": decimal,
 287       "tsc"?: string decimal,
 288       "cpuId"? decimal,
 289     } | {
 290       "error": string,
 291       "id": decimal,
 292       "tsc"?: string decimal,
 293     | {
 294       "loadAddress": string decimal,
 295       "id": decimal,
 296       "hwClock"?: string decimal,
 297       "syncPointMetadata"?: string,
 298       "timestamp_ns"?: string decimal,
 299       "module"?: string,
 300       "symbol"?: string,
 301       "line"?: decimal,
 302       "column"?: decimal,
 303       "source"?: string,
 304       "mnemonic"?: string,
 305       "controlFlowKind"?: string,
 306     }
 307   */
 308 public:
 309   OutputWriterJSON(Stream &s, const TraceDumperOptions &options)
 310       : m_s(s), m_options(options),
 311         m_j(m_s.AsRawOstream(),
 312             /*IndentSize=*/options.pretty_print_json ? 2 : 0) {
 313     m_j.arrayBegin();
 314   };
 315
 316   ~OutputWriterJSON() { m_j.arrayEnd(); }
 317
 318   void FunctionCallForest(
 319       const std::vector<TraceDumper::FunctionCallUP> &forest) override {
 320     for (size_t i = 0; i < forest.size(); i++) {
 321       m_j.object([&] { DumpFunctionCallTree(*forest[i]); });
 322     }
 323   }
 324
 325   void DumpFunctionCallTree(const TraceDumper::FunctionCall &function_call) {
 326     if (function_call.GetUntracedPrefixSegment()) {
 327       m_j.attributeObject("untracedPrefixSegment", [&] {
 328         m_j.attributeObject("nestedCall", [&] {
 329           DumpFunctionCallTree(
 330               function_call.GetUntracedPrefixSegment()->GetNestedCall());
 331         });
 332       });
 333     }
 334
 335     if (!function_call.GetTracedSegments().empty()) {
 336       m_j.attributeArray("tracedSegments", [&] {
 337         for (const TraceDumper::FunctionCall::TracedSegment &segment :
 338              function_call.GetTracedSegments()) {
 339           m_j.object([&] {
 340             m_j.attribute("firstInstructionId",
 341                           std::to_string(segment.GetFirstInstructionID()));
 342             m_j.attribute("lastInstructionId",
 343                           std::to_string(segment.GetLastInstructionID()));
 344             segment.IfNestedCall(
 345                 [&](const TraceDumper::FunctionCall &nested_call) {
 346                   m_j.attributeObject(
 347                       "nestedCall", [&] { DumpFunctionCallTree(nested_call); });
 348                 });
 349           });
 350         }
 351       });
 352     }
 353   }
 354
 355   void DumpEvent(const TraceDumper::TraceItem &item) {
 356     m_j.attribute("event", TraceCursor::EventKindToString(*item.event));
 357     switch (*item.event) {
 358     case eTraceEventCPUChanged:
 359       m_j.attribute("cpuId", item.cpu_id);
 360       break;
 361     case eTraceEventHWClockTick:
 362       m_j.attribute("hwClock", item.hw_clock);
 363       break;
 364     case eTraceEventDisabledHW:
 365     case eTraceEventDisabledSW:
 366       break;
 367     case eTraceEventSyncPoint:
 368       m_j.attribute("syncPointMetadata", item.sync_point_metadata);
 369       break;
 370     }
 371   }
 372
 373   void DumpInstruction(const TraceDumper::TraceItem &item) {
 374     m_j.attribute("loadAddress", formatv("{0:x}", item.load_address));
 375     if (item.symbol_info) {
 376       m_j.attribute("module", ToOptionalString(GetModuleName(item)));
 377       m_j.attribute(
 378           "symbol",
 379           ToOptionalString(item.symbol_info->sc.GetFunctionName().AsCString()));
 380
 381       if (lldb::InstructionSP instruction = item.symbol_info->instruction) {
 382         ExecutionContext exe_ctx = item.symbol_info->exe_ctx;
 383         m_j.attribute("mnemonic",
 384                       ToOptionalString(instruction->GetMnemonic(&exe_ctx)));
 385         if (m_options.show_control_flow_kind) {
 386           lldb::InstructionControlFlowKind instruction_control_flow_kind =
 387               instruction->GetControlFlowKind(&exe_ctx);
 388           m_j.attribute("controlFlowKind",
 389                         ToOptionalString(
 390                             Instruction::GetNameForInstructionControlFlowKind(
 391                                 instruction_control_flow_kind)));
 392         }
 393       }
 394
 395       if (IsLineEntryValid(item.symbol_info->sc.line_entry)) {
 396         m_j.attribute(
 397             "source",
 398             ToOptionalString(
 399                 item.symbol_info->sc.line_entry.GetFile().GetPath().c_str()));
 400         m_j.attribute("line", item.symbol_info->sc.line_entry.line);
 401         m_j.attribute("column", item.symbol_info->sc.line_entry.column);
 402       }
 403     }
 404   }
 405
 406   void TraceItem(const TraceDumper::TraceItem &item) override {
 407     m_j.object([&] {
 408       m_j.attribute("id", item.id);
 409       if (m_options.show_timestamps)
 410         m_j.attribute("timestamp_ns", item.timestamp
 411                                           ? std::optional<std::string>(
 412                                                 std::to_string(*item.timestamp))
 413                                           : std::nullopt);
 414
 415       if (item.event) {
 416         DumpEvent(item);
 417       } else if (item.error) {
 418         m_j.attribute("error", *item.error);
 419       } else {
 420         DumpInstruction(item);
 421       }
 422     });
 423   }
 424
 425 private:
 426   Stream &m_s;
 427   TraceDumperOptions m_options;
 428   json::OStream m_j;
 429 };
 430
 431 static std::unique_ptr<TraceDumper::OutputWriter>
 432 CreateWriter(Stream &s, const TraceDumperOptions &options, Thread &thread) {
 433   if (options.json)
 434     return std::unique_ptr<TraceDumper::OutputWriter>(
 435         new OutputWriterJSON(s, options));
 436   else
 437     return std::unique_ptr<TraceDumper::OutputWriter>(
 438         new OutputWriterCLI(s, options, thread));
 439 }
 440
 441 TraceDumper::TraceDumper(lldb::TraceCursorSP cursor_sp, Stream &s,
 442                          const TraceDumperOptions &options)
 443     : m_cursor_sp(std::move(cursor_sp)), m_options(options),
 444       m_writer_up(CreateWriter(
 445           s, m_options, *m_cursor_sp->GetExecutionContextRef().GetThreadSP())) {
 446
 447   if (m_options.id)
 448     m_cursor_sp->GoToId(*m_options.id);
 449   else if (m_options.forwards)
 450     m_cursor_sp->Seek(0, lldb::eTraceCursorSeekTypeBeginning);
 451   else
 452     m_cursor_sp->Seek(0, lldb::eTraceCursorSeekTypeEnd);
 453
 454   m_cursor_sp->SetForwards(m_options.forwards);
 455   if (m_options.skip) {
 456     m_cursor_sp->Seek((m_options.forwards ? 1 : -1) * *m_options.skip,
 457                       lldb::eTraceCursorSeekTypeCurrent);
 458   }
 459 }
 460
 461 TraceDumper::TraceItem TraceDumper::CreatRawTraceItem() {
 462   TraceItem item = {};
 463   item.id = m_cursor_sp->GetId();
 464
 465   if (m_options.show_timestamps)
 466     item.timestamp = m_cursor_sp->GetWallClockTime();
 467   return item;
 468 }
 469
 470 /// Find the symbol context for the given address reusing the previous
 471 /// instruction's symbol context when possible.
 472 static SymbolContext
 473 CalculateSymbolContext(const Address &address,
 474                        const SymbolContext &prev_symbol_context) {
 475   lldb_private::AddressRange range;
 476   if (prev_symbol_context.GetAddressRange(eSymbolContextEverything, 0,
 477                                           /*inline_block_range*/ true, range) &&
 478       range.Contains(address))
 479     return prev_symbol_context;
 480
 481   SymbolContext sc;
 482   address.CalculateSymbolContext(&sc, eSymbolContextEverything);
 483   return sc;
 484 }
 485
 486 /// Find the disassembler for the given address reusing the previous
 487 /// instruction's disassembler when possible.
 488 static std::tuple<DisassemblerSP, InstructionSP>
 489 CalculateDisass(const TraceDumper::SymbolInfo &symbol_info,
 490                 const TraceDumper::SymbolInfo &prev_symbol_info,
 491                 const ExecutionContext &exe_ctx) {
 492   if (prev_symbol_info.disassembler) {
 493     if (InstructionSP instruction =
 494             prev_symbol_info.disassembler->GetInstructionList()
 495                 .GetInstructionAtAddress(symbol_info.address))
 496       return std::make_tuple(prev_symbol_info.disassembler, instruction);
 497   }
 498
 499   if (symbol_info.sc.function) {
 500     if (DisassemblerSP disassembler =
 501             symbol_info.sc.function->GetInstructions(exe_ctx, nullptr)) {
 502       if (InstructionSP instruction =
 503               disassembler->GetInstructionList().GetInstructionAtAddress(
 504                   symbol_info.address))
 505         return std::make_tuple(disassembler, instruction);
 506     }
 507   }
 508   // We fallback to a single instruction disassembler
 509   Target &target = exe_ctx.GetTargetRef();
 510   const ArchSpec arch = target.GetArchitecture();
 511   lldb_private::AddressRange range(symbol_info.address,
 512                                    arch.GetMaximumOpcodeByteSize());
 513   DisassemblerSP disassembler = Disassembler::DisassembleRange(
 514       arch, /*plugin_name=*/nullptr,
 515       /*flavor=*/nullptr, /*cpu=*/nullptr, /*features=*/nullptr, target, range);
 516   return std::make_tuple(
 517       disassembler,
 518       disassembler ? disassembler->GetInstructionList().GetInstructionAtAddress(
 519                          symbol_info.address)
 520                    : InstructionSP());
 521 }
 522
 523 static TraceDumper::SymbolInfo
 524 CalculateSymbolInfo(const ExecutionContext &exe_ctx, lldb::addr_t load_address,
 525                     const TraceDumper::SymbolInfo &prev_symbol_info) {
 526   TraceDumper::SymbolInfo symbol_info;
 527   symbol_info.exe_ctx = exe_ctx;
 528   symbol_info.address.SetLoadAddress(load_address, exe_ctx.GetTargetPtr());
 529   symbol_info.sc =
 530       CalculateSymbolContext(symbol_info.address, prev_symbol_info.sc);
 531   std::tie(symbol_info.disassembler, symbol_info.instruction) =
 532       CalculateDisass(symbol_info, prev_symbol_info, exe_ctx);
 533   return symbol_info;
 534 }
 535
 536 std::optional<lldb::user_id_t> TraceDumper::DumpInstructions(size_t count) {
 537   ThreadSP thread_sp = m_cursor_sp->GetExecutionContextRef().GetThreadSP();
 538
 539   SymbolInfo prev_symbol_info;
 540   std::optional<lldb::user_id_t> last_id;
 541
 542   ExecutionContext exe_ctx;
 543   thread_sp->GetProcess()->GetTarget().CalculateExecutionContext(exe_ctx);
 544
 545   for (size_t insn_seen = 0; insn_seen < count && m_cursor_sp->HasValue();
 546        m_cursor_sp->Next()) {
 547
 548     last_id = m_cursor_sp->GetId();
 549     TraceItem item = CreatRawTraceItem();
 550
 551     if (m_cursor_sp->IsEvent() && m_options.show_events) {
 552       item.event = m_cursor_sp->GetEventType();
 553       switch (*item.event) {
 554       case eTraceEventCPUChanged:
 555         item.cpu_id = m_cursor_sp->GetCPU();
 556         break;
 557       case eTraceEventHWClockTick:
 558         item.hw_clock = m_cursor_sp->GetHWClock();
 559         break;
 560       case eTraceEventDisabledHW:
 561       case eTraceEventDisabledSW:
 562         break;
 563       case eTraceEventSyncPoint:
 564         item.sync_point_metadata = m_cursor_sp->GetSyncPointMetadata();
 565         break;
 566       }
 567       m_writer_up->TraceItem(item);
 568     } else if (m_cursor_sp->IsError()) {
 569       item.error = m_cursor_sp->GetError();
 570       m_writer_up->TraceItem(item);
 571     } else if (m_cursor_sp->IsInstruction() && !m_options.only_events) {
 572       insn_seen++;
 573       item.load_address = m_cursor_sp->GetLoadAddress();
 574
 575       if (!m_options.raw) {
 576         SymbolInfo symbol_info =
 577             CalculateSymbolInfo(exe_ctx, item.load_address, prev_symbol_info);
 578         item.prev_symbol_info = prev_symbol_info;
 579         item.symbol_info = symbol_info;
 580         prev_symbol_info = symbol_info;
 581       }
 582       m_writer_up->TraceItem(item);
 583     }
 584   }
 585   if (!m_cursor_sp->HasValue())
 586     m_writer_up->NoMoreData();
 587   return last_id;
 588 }
 589
 590 void TraceDumper::FunctionCall::TracedSegment::AppendInsn(
 591     const TraceCursorSP &cursor_sp,
 592     const TraceDumper::SymbolInfo &symbol_info) {
 593   m_last_insn_id = cursor_sp->GetId();
 594   m_last_symbol_info = symbol_info;
 595 }
 596
 597 lldb::user_id_t
 598 TraceDumper::FunctionCall::TracedSegment::GetFirstInstructionID() const {
 599   return m_first_insn_id;
 600 }
 601
 602 lldb::user_id_t
 603 TraceDumper::FunctionCall::TracedSegment::GetLastInstructionID() const {
 604   return m_last_insn_id;
 605 }
 606
 607 void TraceDumper::FunctionCall::TracedSegment::IfNestedCall(
 608     std::function<void(const FunctionCall &function_call)> callback) const {
 609   if (m_nested_call)
 610     callback(*m_nested_call);
 611 }
 612
 613 const TraceDumper::FunctionCall &
 614 TraceDumper::FunctionCall::TracedSegment::GetOwningCall() const {
 615   return m_owning_call;
 616 }
 617
 618 TraceDumper::FunctionCall &
 619 TraceDumper::FunctionCall::TracedSegment::CreateNestedCall(
 620     const TraceCursorSP &cursor_sp,
 621     const TraceDumper::SymbolInfo &symbol_info) {
 622   m_nested_call = std::make_unique<FunctionCall>(cursor_sp, symbol_info);
 623   m_nested_call->SetParentCall(m_owning_call);
 624   return *m_nested_call;
 625 }
 626
 627 const TraceDumper::SymbolInfo &
 628 TraceDumper::FunctionCall::TracedSegment::GetFirstInstructionSymbolInfo()
 629     const {
 630   return m_first_symbol_info;
 631 }
 632
 633 const TraceDumper::SymbolInfo &
 634 TraceDumper::FunctionCall::TracedSegment::GetLastInstructionSymbolInfo() const {
 635   return m_last_symbol_info;
 636 }
 637
 638 const TraceDumper::FunctionCall &
 639 TraceDumper::FunctionCall::UntracedPrefixSegment::GetNestedCall() const {
 640   return *m_nested_call;
 641 }
 642
 643 TraceDumper::FunctionCall::FunctionCall(
 644     const TraceCursorSP &cursor_sp,
 645     const TraceDumper::SymbolInfo &symbol_info) {
 646   m_is_error = cursor_sp->IsError();
 647   AppendSegment(cursor_sp, symbol_info);
 648 }
 649
 650 void TraceDumper::FunctionCall::AppendSegment(
 651     const TraceCursorSP &cursor_sp,
 652     const TraceDumper::SymbolInfo &symbol_info) {
 653   m_traced_segments.emplace_back(cursor_sp, symbol_info, *this);
 654 }
 655
 656 const TraceDumper::SymbolInfo &
 657 TraceDumper::FunctionCall::GetSymbolInfo() const {
 658   return m_traced_segments.back().GetLastInstructionSymbolInfo();
 659 }
 660
 661 bool TraceDumper::FunctionCall::IsError() const { return m_is_error; }
 662
 663 const std::deque<TraceDumper::FunctionCall::TracedSegment> &
 664 TraceDumper::FunctionCall::GetTracedSegments() const {
 665   return m_traced_segments;
 666 }
 667
 668 TraceDumper::FunctionCall::TracedSegment &
 669 TraceDumper::FunctionCall::GetLastTracedSegment() {
 670   return m_traced_segments.back();
 671 }
 672
 673 const std::optional<TraceDumper::FunctionCall::UntracedPrefixSegment> &
 674 TraceDumper::FunctionCall::GetUntracedPrefixSegment() const {
 675   return m_untraced_prefix_segment;
 676 }
 677
 678 void TraceDumper::FunctionCall::SetUntracedPrefixSegment(
 679     TraceDumper::FunctionCallUP &&nested_call) {
 680   m_untraced_prefix_segment.emplace(std::move(nested_call));
 681 }
 682
 683 TraceDumper::FunctionCall *TraceDumper::FunctionCall::GetParentCall() const {
 684   return m_parent_call;
 685 }
 686
 687 void TraceDumper::FunctionCall::SetParentCall(
 688     TraceDumper::FunctionCall &parent_call) {
 689   m_parent_call = &parent_call;
 690 }
 691
 692 /// Given an instruction that happens after a return, find the ancestor function
 693 /// call that owns it. If this ancestor doesn't exist, create a new ancestor and
 694 /// make it the root of the tree.
 695 ///
 696 /// \param[in] last_function_call
 697 ///   The function call that performs the return.
 698 ///
 699 /// \param[in] symbol_info
 700 ///   The symbol information of the instruction after the return.
 701 ///
 702 /// \param[in] cursor_sp
 703 ///   The cursor pointing to the instruction after the return.
 704 ///
 705 /// \param[in,out] roots
 706 ///   The object owning the roots. It might be modified if a new root needs to
 707 ///   be created.
 708 ///
 709 /// \return
 710 ///   A reference to the function call that owns the new instruction
 711 static TraceDumper::FunctionCall &AppendReturnedInstructionToFunctionCallForest(
 712     TraceDumper::FunctionCall &last_function_call,
 713     const TraceDumper::SymbolInfo &symbol_info, const TraceCursorSP &cursor_sp,
 714     std::vector<TraceDumper::FunctionCallUP> &roots) {
 715
 716   // We omit the current node because we can't return to itself.
 717   TraceDumper::FunctionCall *ancestor = last_function_call.GetParentCall();
 718
 719   for (; ancestor; ancestor = ancestor->GetParentCall()) {
 720     // This loop traverses the tree until it finds a call that we can return to.
 721     if (IsSameInstructionSymbolContext(ancestor->GetSymbolInfo(), symbol_info,
 722                                        /*check_source_line_info=*/false)) {
 723       // We returned to this symbol, so we are assuming we are returning there
 724       // Note: If this is not robust enough, we should actually check if we
 725       // returning to the instruction that follows the last instruction from
 726       // that call, as that's the behavior of CALL instructions.
 727       ancestor->AppendSegment(cursor_sp, symbol_info);
 728       return *ancestor;
 729     }
 730   }
 731
 732   // We didn't find the call we were looking for, so we now create a synthetic
 733   // one that will contain the new instruction in its first traced segment.
 734   TraceDumper::FunctionCallUP new_root =
 735       std::make_unique<TraceDumper::FunctionCall>(cursor_sp, symbol_info);
 736   // This new root will own the previous root through an untraced prefix segment.
 737   new_root->SetUntracedPrefixSegment(std::move(roots.back()));
 738   roots.pop_back();
 739   // We update the roots container to point to the new root
 740   roots.emplace_back(std::move(new_root));
 741   return *roots.back();
 742 }
 743
 744 /// Append an instruction to a function call forest. The new instruction might
 745 /// be appended to the current segment, to a new nest call, or return to an
 746 /// ancestor call.
 747 ///
 748 /// \param[in] exe_ctx
 749 ///   The exeuction context of the traced thread.
 750 ///
 751 /// \param[in] last_function_call
 752 ///   The chronologically most recent function call before the new instruction.
 753 ///
 754 /// \param[in] prev_symbol_info
 755 ///   The symbol information of the previous instruction in the trace.
 756 ///
 757 /// \param[in] symbol_info
 758 ///   The symbol information of the new instruction.
 759 ///
 760 /// \param[in] cursor_sp
 761 ///   The cursor pointing to the new instruction.
 762 ///
 763 /// \param[in,out] roots
 764 ///   The object owning the roots. It might be modified if a new root needs to
 765 ///   be created.
 766 ///
 767 /// \return
 768 ///   A reference to the function call that owns the new instruction.
 769 static TraceDumper::FunctionCall &AppendInstructionToFunctionCallForest(
 770     const ExecutionContext &exe_ctx,
 771     TraceDumper::FunctionCall *last_function_call,
 772     const TraceDumper::SymbolInfo &prev_symbol_info,
 773     const TraceDumper::SymbolInfo &symbol_info, const TraceCursorSP &cursor_sp,
 774     std::vector<TraceDumper::FunctionCallUP> &roots) {
 775   if (!last_function_call || last_function_call->IsError()) {
 776     // We create a brand new root
 777     roots.emplace_back(
 778         std::make_unique<TraceDumper::FunctionCall>(cursor_sp, symbol_info));
 779     return *roots.back();
 780   }
 781
 782   lldb_private::AddressRange range;
 783   if (symbol_info.sc.GetAddressRange(
 784           eSymbolContextBlock | eSymbolContextFunction | eSymbolContextSymbol,
 785           0, /*inline_block_range*/ true, range)) {
 786     if (range.GetBaseAddress() == symbol_info.address) {
 787       // Our instruction is the first instruction of a function. This has
 788       // to be a call. This should also identify if a trampoline or the linker
 789       // is making a call using a non-CALL instruction.
 790       return last_function_call->GetLastTracedSegment().CreateNestedCall(
 791           cursor_sp, symbol_info);
 792     }
 793   }
 794   if (IsSameInstructionSymbolContext(prev_symbol_info, symbol_info,
 795                                      /*check_source_line_info=*/false)) {
 796     // We are still in the same function. This can't be a call because otherwise
 797     // we would be in the first instruction of the symbol.
 798     last_function_call->GetLastTracedSegment().AppendInsn(cursor_sp,
 799                                                           symbol_info);
 800     return *last_function_call;
 801   }
 802   // Now we are in a different symbol. Let's see if this is a return or a
 803   // call
 804   const InstructionSP &insn = last_function_call->GetLastTracedSegment()
 805                                   .GetLastInstructionSymbolInfo()
 806                                   .instruction;
 807   InstructionControlFlowKind insn_kind =
 808       insn ? insn->GetControlFlowKind(&exe_ctx)
 809            : eInstructionControlFlowKindOther;
 810
 811   switch (insn_kind) {
 812   case lldb::eInstructionControlFlowKindCall:
 813   case lldb::eInstructionControlFlowKindFarCall: {
 814     // This is a regular call
 815     return last_function_call->GetLastTracedSegment().CreateNestedCall(
 816         cursor_sp, symbol_info);
 817   }
 818   case lldb::eInstructionControlFlowKindFarReturn:
 819   case lldb::eInstructionControlFlowKindReturn: {
 820     // We should have caught most trampolines and linker functions earlier, so
 821     // let's assume this is a regular return.
 822     return AppendReturnedInstructionToFunctionCallForest(
 823         *last_function_call, symbol_info, cursor_sp, roots);
 824   }
 825   default:
 826     // we changed symbols not using a call or return and we are not in the
 827     // beginning of a symbol, so this should be something very artificial
 828     // or maybe a jump to some label in the middle of it section.
 829
 830     // We first check if it's a return from an inline method
 831     if (prev_symbol_info.sc.block &&
 832         prev_symbol_info.sc.block->GetContainingInlinedBlock()) {
 833       return AppendReturnedInstructionToFunctionCallForest(
 834           *last_function_call, symbol_info, cursor_sp, roots);
 835     }
 836     // Now We assume it's a call. We should revisit this in the future.
 837     // Ideally we should be able to decide whether to create a new tree,
 838     // or go deeper or higher in the stack.
 839     return last_function_call->GetLastTracedSegment().CreateNestedCall(
 840         cursor_sp, symbol_info);
 841   }
 842 }
 843
 844 /// Append an error to a function call forest. The new error might be appended
 845 /// to the current segment if it contains errors or will create a new root.
 846 ///
 847 /// \param[in] last_function_call
 848 ///   The chronologically most recent function call before the new error.
 849 ///
 850 /// \param[in] cursor_sp
 851 ///   The cursor pointing to the new error.
 852 ///
 853 /// \param[in,out] roots
 854 ///   The object owning the roots. It might be modified if a new root needs to
 855 ///   be created.
 856 ///
 857 /// \return
 858 ///   A reference to the function call that owns the new error.
 859 TraceDumper::FunctionCall &AppendErrorToFunctionCallForest(
 860     TraceDumper::FunctionCall *last_function_call, TraceCursorSP &cursor_sp,
 861     std::vector<TraceDumper::FunctionCallUP> &roots) {
 862   if (last_function_call && last_function_call->IsError()) {
 863     last_function_call->GetLastTracedSegment().AppendInsn(
 864         cursor_sp, TraceDumper::SymbolInfo{});
 865     return *last_function_call;
 866   } else {
 867     roots.emplace_back(std::make_unique<TraceDumper::FunctionCall>(
 868         cursor_sp, TraceDumper::SymbolInfo{}));
 869     return *roots.back();
 870   }
 871 }
 872
 873 static std::vector<TraceDumper::FunctionCallUP>
 874 CreateFunctionCallForest(TraceCursorSP &cursor_sp,
 875                          const ExecutionContext &exe_ctx) {
 876
 877   std::vector<TraceDumper::FunctionCallUP> roots;
 878   TraceDumper::SymbolInfo prev_symbol_info;
 879
 880   TraceDumper::FunctionCall *last_function_call = nullptr;
 881
 882   for (; cursor_sp->HasValue(); cursor_sp->Next()) {
 883     if (cursor_sp->IsError()) {
 884       last_function_call = &AppendErrorToFunctionCallForest(last_function_call,
 885                                                             cursor_sp, roots);
 886       prev_symbol_info = {};
 887     } else if (cursor_sp->IsInstruction()) {
 888       TraceDumper::SymbolInfo symbol_info = CalculateSymbolInfo(
 889           exe_ctx, cursor_sp->GetLoadAddress(), prev_symbol_info);
 890
 891       last_function_call = &AppendInstructionToFunctionCallForest(
 892           exe_ctx, last_function_call, prev_symbol_info, symbol_info, cursor_sp,
 893           roots);
 894       prev_symbol_info = symbol_info;
 895     } else if (cursor_sp->GetEventType() == eTraceEventCPUChanged) {
 896       // TODO: In case of a CPU change, we create a new root because we haven't
 897       // investigated yet if a call tree can safely continue or if interrupts
 898       // could have polluted the original call tree.
 899       last_function_call = nullptr;
 900       prev_symbol_info = {};
 901     }
 902   }
 903
 904   return roots;
 905 }
 906
 907 void TraceDumper::DumpFunctionCalls() {
 908   ThreadSP thread_sp = m_cursor_sp->GetExecutionContextRef().GetThreadSP();
 909   ExecutionContext exe_ctx;
 910   thread_sp->GetProcess()->GetTarget().CalculateExecutionContext(exe_ctx);
 911
 912   m_writer_up->FunctionCallForest(
 913       CreateFunctionCallForest(m_cursor_sp, exe_ctx));
 914 }