[trace] Add a flag to the decoder to output the instruction type

[persona0220]

Summary

To build complex binding upon instruction trace, additional metadata 'instruction type' is needed.

This diff has followings:

• Add a flag -k / --kind for instruction dump
• Remove SetGranularity and SetIgnoreErros from Trace cursor

Sample output:

(lldb) thread trace dump instruction -k
thread #1: tid = 3198805
  libc.so.6`_IO_puts + 356
    2107: 0x00007ffff7163594 (    return)     retq
    2106: 0x00007ffff7163592 (     other)     popq   %r13
    2105: 0x00007ffff7163590 (     other)     popq   %r12
    2104: 0x00007ffff716358f (     other)     popq   %rbp
    2103: 0x00007ffff716358e (     other)     popq   %rbx
    2102: 0x00007ffff716358c (     other)     movl   %ebx, %eax
    2101: 0x00007ffff7163588 (     other)     addq   $0x8, %rsp
    2100: 0x00007ffff7163570 ( cond jump)     je     0x89588                   ; <+344>
    2099: 0x00007ffff716356e (     other)     decl   (%rdx)
    2098: 0x00007ffff7163565 ( cond jump)     je     0x8956e                   ; <+318>
    2097: 0x00007ffff716355e (     other)     cmpl   $0x0, 0x33c02b(%rip)      ; __libc_multiple_threads
    2096: 0x00007ffff7163556 (     other)     movq   $0x0, 0x8(%rdx)
    2095: 0x00007ffff7163554 ( cond jump)     jne    0x89588                   ; <+344>
    2094: 0x00007ffff7163550 (     other)     subl   $0x1, 0x4(%rdx)
    2093: 0x00007ffff7163549 (     other)     movq   0x88(%rbp), %rdx
    2092: 0x00007ffff7163547 ( cond jump)     jne    0x89588                   ; <+344>
    2091: 0x00007ffff7163540 (     other)     testl  $0x8000, (%rbp)           ; imm = 0x8000
    2090: 0x00007ffff716353c (     other)     cmovaq %rax, %rbx
    2089: 0x00007ffff7163535 (     other)     cmpq   $0x7fffffff, %rbx         ; imm = 0x7FFFFFFF
    2088: 0x00007ffff7163530 (     other)     movl   $0x7fffffff, %eax         ; imm = 0x7FFFFFFF

[jingham]

This categorization seems like it is relevant for any instruction, not just instructions found in a trace buffer. Is there any reason why this isn't just an annotation added by the standard instruction printer, that you then turn on with the -k flag to thread trace dump (but which might also be useful for the regular disassemble command)?

[wallace]

@jingham, that's a pretty good idea. We'll see how to implement it

[jj10306]

Thanks for working on this 🙂
Looks good overall, just left some minor comments.

lldb/include/lldb/Target/TraceCursor.h

64

For some reason I can't make inline suggestions, so I'll just put my suggested edit below:

s/which direction/which uses the current direction of the trace

lldb/include/lldb/Target/TraceInstructionDumper.h

105–107

Don't forget to rebase onto mainline, @wallace's recent diff (https://reviews.llvm.org/D128316) refactored some of this code, so that will effect where some of these new changes should live.

lldb/source/Commands/Options.td

1132

nit: add a period at the end of the description (:

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.cpp

46–50

Apologies again bc I can't "Suggest Edits" inline, so leaving my suggestion in a code block below:

IIUC, we previously had a while loop here because the possibility of "skipping" instructions due to ignoring errors or not matching the granularity. Since this diff removes those two things, this logic can now be simplified since the trace cursor can no longer skip the instructions - below is roughly what I'm thinking:

bool TraceCursorIntelPT::Next() {
  auto canMoveOne = [&]() {
    if (IsForwards())
      return m_pos + 1 < GetInternalInstructionSize();
    return m_pos > 0;
  };

  if (!canMoveOne())
    return false;

  m_pos += IsForwards() ? 1 : -1;
  if (m_tsc_range && !m_tsc_range->InRange(m_pos))
    m_tsc_range = IsForwards() ? m_tsc_range->Next() : m_tsc_range->Prev();

  return true;
}

@wallace wdyt?

[persona0220]

This new diff attach additional metadata 'control flow kind' for instruction.
Add '-k / --kind' flag for both disassemble and thread trace dump command.

Thanks to @jingham for the suggestion!

Sample output:

(lldb) disas -k
a.out`main:
    0x4005b6 <+0>:  other     pushq  %rbp
    0x4005b7 <+1>:  other     movq   %rsp, %rbp
    0x4005ba <+4>:  other     movl   $0x400668, %edi           ; imm = 0x400668
    0x4005bf <+9>:  call      callq  0x4004c0                  ; symbol stub for: puts
->  0x4005c4 <+14>: other     movl   $0x0, %eax
    0x4005c9 <+19>: other     popq   %rbp
    0x4005ca <+20>: return    retq

(lldb) thread trace dump instruction --kind
    thread #1: tid = 1893259
  libc.so.6`write + 30
    2027: 0x00007ffff71fa86e    cond jump ja     0x1208c8                  ; <+120>
    2026: 0x00007ffff71fa868    other     cmpq   $-0x1000, %rax            ; imm = 0xF000
    2025: 0x00007ffff71fa866    far call  syscall
    2024: 0x00007ffff71fa861    other     movl   $0x1, %eax
    2023: 0x00007ffff71fa85f    cond jump jne    0x120878                  ; <+40>
    2022: 0x00007ffff71fa85d    other     testl  %eax, %eax
    2021: 0x00007ffff71fa85b    other     movl   (%rax), %eax
    2020: 0x00007ffff71fa854    other     leaq   0x2a4d35(%rip), %rax      ; __libc_multiple_threads
    2019: 0x00007ffff71fa850    other     endbr64

[wallace]

remove unwanted files

[wallace]

lldb/include/lldb/Core/Disassembler.h

82–86 ↗

(On Diff #440806)

as this code is new, please write documentation and function names should be in PascalCase. Try to have a more descriptive name as well, because instruction_decode is very vague.

152 ↗

(On Diff #440806)

let's try to be more explicit with the naming

226–233 ↗

(On Diff #440806)

add documentation. Also, if this mapping is intel-specific, I recommend moving this to the cpp file so that it's not exposed publicly. The Disassembler is architecture agnostic, so its API should try to remain that way

341 ↗

(On Diff #440806)

name

398 ↗

(On Diff #440806)

lldb/include/lldb/Target/TraceCursor.h

35

this file has changed, could you rebase from upstream/main.

230–234

when you rebase, could you delete any references to this method and its implementation as well? We won't use it anymore

lldb/include/lldb/Target/TraceInstructionDumper.h

38

name

lldb/include/lldb/lldb-enumerations.h

973

this doesn't need to be a FLAGS_ENUM anymore (i.e. bitmask), you can use a simple enum instead, like the ExpressionEvaluationPhase above

lldb/source/API/SBInstruction.cpp

244 ↗

(On Diff #440806)

include this kind of comment wherever you have added this parameter

lldb/source/Commands/CommandObjectDisassemble.h

49 ↗

(On Diff #440806)

ame

[wallace]

nice job!!

lldb/source/Commands/Options.td

304

mention here the enum to inspect for documentation. Besides that, you can quickly mention here that far jumps and far returns often indicate a kernel calls and returns. That might be enough because the other categories are pretty intuitive

1156

same here

lldb/source/Core/Disassembler.cpp

680 ↗

(On Diff #440808)

you have to check here that the triple of the current architecture of the current target (you can get that from exe_ctx) is x86, otherwise directly return eInstructionControlFlowTypeUnknown. You can just rely on the check you are doing in line 685 because that check might fail in the future

681 ↗

(On Diff #440808)

from this point on, the code is specifically meant for x86, so I recommend creating a x86 namespace in this file and include a GetControlFlowInstructionKind method along with the instruction_decode method there. That way we organize the code in a more cleaner manner

681 ↗

(On Diff #440808)

add a comment explaining what these variables are

692 ↗

(On Diff #440808)

add a comment explaining what this prefix handling is actually doing

715 ↗

(On Diff #440808)

you can move this to the beginning of the function and assume that this mapping is x86 only, which is how it should be

773 ↗

(On Diff #440808)

you can also mention here how this mapping is actually generated and were you got inspiration from, like libipt

846 ↗

(On Diff #440808)

should you remove this?

849 ↗

(On Diff #440808)

unknown

lldb/source/Plugins/Trace/intel-pt/DecodedThread.cpp

63

remove this, because we won't use it anymore

[persona0220]

• Modify function name instruction_decode into DecodeInstructionOpcode
• explicit naming for flag show_kind -> show_control_flow_kind
• Convert InstructionControlFlowType FLAG_ENUM into simple enum
• Create x86 namespace in Disassembler.cpp to decode instruction.

[persona0220]

nit

[wallace]

much better! Thanks for doing this.

There are two main things to do.

1. The algorithm you are using to classify the instructions uses too many acronyms and it's very well documented. Try to make it understandable enough so that anyone with little familiarity can have an idea of what is happening
2. write a unit test. For this, you can follow any of the tests in lldb/unittests/Disassembler/. In order to run it, you'll need to do ninja DisassemblerTests and then run the output path printed by that command. It uses gtest. You can see the tests in that folder for inspiration.

lldb/include/lldb/Core/Disassembler.h

82 ↗

(On Diff #441230)

better this

84 ↗

(On Diff #441230)

Rename this to

GetControlFlowKind

because we are already inside the Instruction

lldb/include/lldb/lldb-enumerations.h

976

lldb/source/API/SBInstruction.cpp

244 ↗

(On Diff #441230)

the llvm style requires a =

279 ↗

(On Diff #441230)

same here

lldb/source/API/SBInstructionList.cpp

169 ↗

(On Diff #441230)

ditto

lldb/source/Commands/Options.td

306

1160

copy the changes from above

lldb/source/Core/Disassembler.cpp

575 ↗

(On Diff #441230)

add documentation mentioning what a PTI_MAP is. Try to make the documentation clear enough for anyone without knowledge of this matter. Also, mention what modrm is why it's important here.
Also, it's better if don't use the PTI acronym but instead use the full name. It'd make it easier to read.
Also, this is an enum and not a map, so better use an identifier different than a map

584–586 ↗

(On Diff #441230)

let's be more specific

695–696 ↗

(On Diff #441230)

another reference to opcode, modrm, and map bytes. I recommend writing extensive documentation in PTI_MAP and then mention here that the full documentation can be found in the PTI_MAP definition

703–704 ↗

(On Diff #441230)

this comment is not useful because this method is in the x86 namespace

710–713 ↗

(On Diff #441230)

789–790 ↗

(On Diff #441230)

you use exe_ctx->GetTargetRef().GetArchitecture().GetMachine() != llvm::Triple::ArchType::x86_64 a lot. What about creating a variable that holds this comparison?

847–848 ↗

(On Diff #441230)

use { } in this else, because the if already used it

[persona0220]

• Terms ‘control flow kind’ and ‘control flow type’ was mixed across source codes -> Unify into ‘control flow kind’
• Divide the ‘GetControlFlowKind’ function into two functions:
  • InstructionLengthDecode: Decode raw instruction bytes into opcode, modrm and map.
  • MapOpcodeIntoControlFlowKind: Get control flow find from opcode, modrm and map.
• Add detailed comments for each new functions.

[persona0220]

Add some more documentation

[wallace]

let's try to have tests soon. It seems that the code can be simplified and tests will be very handy

lldb/include/lldb/lldb-enumerations.h

976

lldb/source/Core/Disassembler.cpp

730–740 ↗

(On Diff #442420)

I'm noticing that MapOpcodeIntoControlFlowKind only uses PTI_MAP_0 and PTI_MAP_1, which are opcodes of 1 and 2 bytes. Any opcode of 3 bytes and even amd3dnow is not used at all. That means that you don't need that enum, so please delete it. Instead, use the length of the opcode throughout the code.

882 ↗

(On Diff #442420)

does this mean that all x86 and x86_64 instructions are categorized as Opcode::Type::eTypeBytes?
I'm asking because after reading GetOpcodeBytes, it only returns data if the type is eTypeBytes. Did you check that?

885 ↗

(On Diff #442420)

you don't need to copy GetOpcodeBytes, you can just pass it directly to InstructionLengthDecode

[persona0220]

• Delete PTI_MAP enum and use opcode_len instead.
• Add a unit test
  • Divide existing Disassembler test into x86 / ARM subdirectory
  • Unittests/Disassembler/x86/TestGetControlFlowKindx86.cpp tests categorizing x86_64 instructions
• Modify GetControlFlowKind function to get ArchSpec instead of exe_ctx

[wallace]

almost there! I like the tests btw :)

lldb/source/Commands/Options.td

304

1159

same

lldb/source/Core/Disassembler.cpp

578 ↗

(On Diff #443281)

588 ↗

(On Diff #443281)

592–594 ↗

(On Diff #443281)

705 ↗

(On Diff #443281)

734–736 ↗

(On Diff #443281)

We try not to use out parameters this way. Instead, create a new struct InstructionOpcodeAndModrm with the three values that are important to you. Then, change this function to return Optional<InstructionOpcodeAndModrm>, where the None case means that decoding failed

lldb/unittests/Disassembler/x86/TestGetControlFlowKindx86.cpp

28–29 ↗

(On Diff #443281)

delete if not used

[persona0220]

Added a struct InstructionOpcodeAndModrm, which contains primary_opcode, opcode_len and modrm bytes decoded from InstructionLengthDecode function.

[wallace]

I'll commit this for you

lldb/include/lldb/Target/TraceCursor.h

 ///
 /// Defaults:
 ///   By default, the cursor points at the end item of the trace, moves
-///   backwards, has a move granularity of \a
-///   eTraceInstructionControlFlowTypeInstruction (i.e. visit every instruction)
-///   and stops at every error (the "ignore errors" flag is \b false). See the
-///   \a TraceCursor::Next() method for more documentation.
+///   backwards, and stops at every error.
+//    See the \a TraceCursor::Next() method for more documentation.
 ///
 /// Sample usage:
 ///
 ///  TraceCursorUP cursor = trace.GetTrace(thread);
 ///
-///  cursor->SetGranularity(eTraceInstructionControlFlowTypeCall |
-///    eTraceInstructionControlFlowTypeReturn);
-///
 ///  do {
 ///     if (llvm::Error error = cursor->GetError())
 ///       cout << "error found at: " << llvm::toString(error) << endl;

 ///  } while(cursor->Next());
 ///
 /// Low level traversal:
-///   Unlike the \a TraceCursor::Next() API, which uses a given granularity and
-///   direction to advance the cursor, the \a TraceCursor::Seek() method can be
+///   Unlike the \a TraceCursor::Next() API, which direction to advance
+//    the cursor, the \a TraceCursor::Seek() method can be
 ///   used to reposition the cursor to an offset of the end, beginning, or
 ///   current position of the trace.
 class TraceCursor {

 
   virtual ~TraceCursor() = default;
 
-  /// Set the granularity to use in the \a TraceCursor::Next() method.
-  void SetGranularity(lldb::TraceInstructionControlFlowType granularity);
-
-  /// Set the "ignore errors" flag to use in the \a TraceCursor::Next() method.
-  void SetIgnoreErrors(bool ignore_errors);
-
   /// Set the direction to use in the \a TraceCursor::Next() method.
   ///
   /// \param[in] forwards

   ///     \b true if the current direction is forwards, \b false if backwards.
   bool IsForwards() const;
 
-  /// Move the cursor to the next instruction that matches the current
-  /// granularity.
+  /// Move the cursor to the next instruction
   ///
   /// Direction:
   ///     The traversal is done following the current direction of the trace. If
   ///     it is forwards, the instructions are visited forwards
   ///     chronologically. Otherwise, the traversal is done in
   ///     the opposite direction. By default, a cursor moves backwards unless
   ///     changed with \a TraceCursor::SetForwards().
   ///
-  /// Granularity:
-  ///     The cursor will traverse the trace looking for the first instruction
-  ///     that matches the current granularity. If there aren't any matching
-  ///     instructions, the cursor won't move, to give the opportunity of
-  ///     changing granularities.
-  ///
-  /// Ignore errors:
-  ///     If the "ignore errors" flags is \b false, the traversal will stop as
-  ///     soon as it finds an error in the trace and the cursor will point at
-  ///     it.
-  ///
   /// \return
   ///     \b true if the cursor effectively moved, \b false otherwise.
   virtual bool Next() = 0;

 protected:
   ExecutionContextRef m_exe_ctx_ref;
 
-  lldb::TraceInstructionControlFlowType m_granularity =
-      lldb::eTraceInstructionControlFlowTypeInstruction;
-  bool m_ignore_errors = false;
   bool m_forwards = false;
 };
 

lldb/include/lldb/Target/TraceInstructionDumper.h

   /// Dump only instruction addresses without disassembly nor symbol
   /// information.
   bool raw = false;
+  /// For each instruction, print the instruction type.
+  bool show_kind = false;
   /// For each instruction, print the corresponding timestamp counter if
   /// available.
   bool show_tsc = false;

 
   void PrintInstructionHeader();
 
+  void PrintInstructionType();
+
   void DumpInstructionDisassembly(const InstructionSymbolInfo &insn);
 
   /// Dump the symbol context of the given instruction address if it's different

lldb/include/lldb/lldb-enumerations.h

 ///
 /// A single instruction can match one or more of these categories.
 FLAGS_ENUM(TraceInstructionControlFlowType){
-    /// Any instruction.
+    /// The instruction could not be classified.
+    eTraceInstructionControlFlowTypeError = 0,
+    /// The instruction is something not listed below.
     eTraceInstructionControlFlowTypeInstruction = (1u << 1),
-    /// A conditional or unconditional branch/jump.
-    eTraceInstructionControlFlowTypeBranch = (1u << 2),
-    /// A conditional or unconditional branch/jump that changed
-    /// the control flow of the program.
-    eTraceInstructionControlFlowTypeTakenBranch = (1u << 3),
-    /// A call to a function.
-    eTraceInstructionControlFlowTypeCall = (1u << 4),
-    /// A return from a function.
-    eTraceInstructionControlFlowTypeReturn = (1u << 5)};
+    /// The instruction is a near (function) call.
+    eTraceInstructionControlFlowTypeCall = (1u << 2),
+    /// The instruction is a near (function) return.
+    eTraceInstructionControlFlowTypeReturn = (1u << 3),
+    /// The instruction is a near unconditional jump.
+    eTraceInstructionControlFlowTypeJump = (1u << 4),
+    /// The instruction is a near conditional jump.
+    eTraceInstructionControlFlowTypeCondJump = (1u << 5),
+    /// The instruction is a call-like far transfer.
+    /// E.g. SYSCALL, SYSENTER, or FAR CALL.
+    eTraceInstructionControlFlowTypeFarCall = (1u << 6),
+    /// The instruction is a return-like far transfer.
+    /// E.g. SYSRET, SYSEXIT, IRET, or FAR RET.
+    eTraceInstructionControlFlowTypeFarReturn = (1u << 7),
+    /// The instruction is a jump-like far transfer.
+    /// E.g. FAR JMP.
+    eTraceInstructionControlFlowTypeFarJump = (1u << 8)};
 
 LLDB_MARK_AS_BITMASK_ENUM(TraceInstructionControlFlowType)
 

lldb/source/Commands/CommandObjectThread.cpp

         m_dumper_options.forwards = true;
         break;
       }
+      case 'k': {
+        m_dumper_options.show_kind = true;
+        break;
+      }
       case 't': {
         m_dumper_options.show_tsc = true;
         break;

lldb/source/Commands/Options.td

     Group<1>,
     Desc<"Dump only instruction address without disassembly nor symbol "
     "information.">;
+  def thread_trace_dump_instructions_show_kind : Option<"kind", "k">, Group<1>,
+    Desc<"For each instruction, print the instruction type">;
   def thread_trace_dump_instructions_show_tsc : Option<"tsc", "t">, Group<1>,
     Desc<"For each instruction, print the corresponding timestamp counter if "
     "available.">;

lldb/source/Plugins/Trace/intel-pt/DecodedThread.cpp

 TraceInstructionControlFlowType
 DecodedThread::GetInstructionControlFlowType(size_t insn_index) const {
   if (IsInstructionAnError(insn_index))
-    return (TraceInstructionControlFlowType)0;
+    return eTraceInstructionControlFlowTypeError;
 
   TraceInstructionControlFlowType mask =
       eTraceInstructionControlFlowTypeInstruction;
 
-  lldb::addr_t load_address = m_instruction_ips[insn_index];
-  uint8_t insn_byte_size = m_instruction_sizes[insn_index];
   pt_insn_class iclass = m_instruction_classes[insn_index];
 
   switch (iclass) {
-  case ptic_cond_jump:
-  case ptic_jump:
-  case ptic_far_jump:
-    mask |= eTraceInstructionControlFlowTypeBranch;
-    if (insn_index + 1 < m_instruction_ips.size() &&
-        load_address + insn_byte_size != m_instruction_ips[insn_index + 1])
-      mask |= eTraceInstructionControlFlowTypeTakenBranch;
+  case ptic_call:
+    mask |= eTraceInstructionControlFlowTypeCall;
     break;
   case ptic_return:
-  case ptic_far_return:
     mask |= eTraceInstructionControlFlowTypeReturn;
     break;
-  case ptic_call:
+  case ptic_jump:
+    mask |= eTraceInstructionControlFlowTypeJump;
+    break;
+  case ptic_cond_jump:
+    mask |= eTraceInstructionControlFlowTypeCondJump;
+    break;
   case ptic_far_call:
-    mask |= eTraceInstructionControlFlowTypeCall;
+    mask |= eTraceInstructionControlFlowTypeFarCall;
+    break;
+  case ptic_far_return:
+    mask |= eTraceInstructionControlFlowTypeFarReturn;
+    break;
+  case ptic_far_jump:
+    mask |= eTraceInstructionControlFlowTypeFarJump;
     break;
   default:
     break;

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.cpp

     if (m_tsc_range && !m_tsc_range->InRange(m_pos))
       m_tsc_range = IsForwards() ? m_tsc_range->Next() : m_tsc_range->Prev();
 
-    if (!m_ignore_errors && IsError())
-      return true;
-    if (GetInstructionControlFlowType() & m_granularity)
-      return true;
+    return true;
   }
 
   // Didn't find any matching instructions

lldb/source/Target/TraceCursor.cpp

   return m_exe_ctx_ref;
 }
 
-void TraceCursor::SetGranularity(
-    lldb::TraceInstructionControlFlowType granularity) {
-  m_granularity = granularity;
-}
-
-void TraceCursor::SetIgnoreErrors(bool ignore_errors) {
-  m_ignore_errors = ignore_errors;
-}
-
 void TraceCursor::SetForwards(bool forwards) { m_forwards = forwards; }
 
 bool TraceCursor::IsForwards() const { return m_forwards; }

lldb/source/Target/TraceInstructionDumper.cpp

   }
 }
 
+void TraceInstructionDumper::PrintInstructionType() {
+  if (m_options.show_kind) {
+    m_s << " (";
+
+    if (m_cursor_up->GetInstructionControlFlowType() ==
+        eTraceInstructionControlFlowTypeError) {
+      m_s.Format("{0,10}", "error) ");
+      return;
+    }
+
+    switch (m_cursor_up->GetInstructionControlFlowType() ^
+            eTraceInstructionControlFlowTypeInstruction) {
+    case eTraceInstructionControlFlowTypeCall:
+      m_s.Format("{0,10}", "call");
+      break;
+    case eTraceInstructionControlFlowTypeReturn:
+      m_s.Format("{0,10}", "return");
+      break;
+    case eTraceInstructionControlFlowTypeJump:
+      m_s.Format("{0,10}", "jump");
+      break;
+    case eTraceInstructionControlFlowTypeCondJump:
+      m_s.Format("{0,10}", "cond jump");
+      break;
+    case eTraceInstructionControlFlowTypeFarCall:
+      m_s.Format("{0,10}", "far call");
+      break;
+    case eTraceInstructionControlFlowTypeFarReturn:
+      m_s.Format("{0,10}", "far return");
+      break;
+    case eTraceInstructionControlFlowTypeFarJump:
+      m_s.Format("{0,10}", "far jump");
+      break;
+    default:
+      m_s.Format("{0,10}", "other");
+      break;
+    }
+    m_s << ") ";
+  }
+}
+
 void TraceInstructionDumper::PrintEvents() {
   if (!m_options.show_events)
     return;

 
       PrintInstructionHeader();
       m_s.Format("{0:x+16}", m_cursor_up->GetLoadAddress());
+      PrintInstructionType();
 
       if (!m_options.raw)
         DumpInstructionDisassembly(insn_info);