[trace] Add a TraceCursor class

[wallace]

Summary

As a follow up of D103588, I'm reinitiating the discussion with a new proposal for traversing instructions in a trace which uses the feedback gotten in that diff.

See the embedded documentation in TraceCursor for more information. The idea is to offer an OOP way to traverse instructions exposing a minimal interface that makes no assumptions on:

• the number of instructions in the trace (i.e. having indices for instructions might be impractical for gigantic intel-pt traces, as it would require to decode the entire trace). This renders the use of indices to point to instructions impractical. Traces are big and expensive, and the consumer should try to do look linear lookups (forwards and/or backwards) and avoid random accesses (the API could be extended though, but for now I want to dicard that funcionality and leave the API extensible if needed).
• the way the instructions are represented internally by each Trace plug-in. They could be mmap'ed from a file, exist in plain vector or generated on the fly as the user requests the data.
• the actual data structure used internally for each plug-in. Ideas like having a struct TraceInstruction have been discarded because that would make the plug-in follow a certain data type, which might be costly. Instead, the user can ask the cursor for each independent property of the instruction it's pointing at.

The way to get a cursor is to ask Trace.h for the end or being cursor or a thread's trace.

There are some benefits of this approach:

• there's little cost to create a cursor, and this allows for lazily decoding a trace as the user requests data.
• each trace plug-in could decide how to cache the instructions it generates. For example, if a trace is small, it might decide to keep everything in memory, or if the trace is massive, it might decide to keep around the last thousands of instructions to speed up local searches.
• a cursor can outlive a stop point, which makes trace comparison for live processes feasible. An application of this is to compare profiling data of two runs of the same function, which should be doable with intel pt.

[clayborg]

lldb/include/lldb/Target/Trace.h

224

If the trace cursor contains an error, do we need llvm::Expected here? Maybe return a std::unique_ptr<TraceCursor> since the cursor can indicate any errors. I am assuming you did a shared pointer to make it easier to eventually push this into the lldb::SB API? a unique pointer works great for the SBAPI and no one will ever need a shared reference to one of these.

226–227

We don' t need these arguments right? These are only needed for the TraceCursor::Next(...) and TraceCursor::Prev(...) right?

231

Ditto, return std::unique_ptr<TraceCursor>?

233–234

We don' t need these arguments right? These are only needed for the TraceCursor::Next(...) and TraceCursor::Prev(...) right?

235

Should there just be a single Trace::GetCursor() and then we can just add some more TraceInstructionType bits? My thinking is the cursor would always return an end cursor and we could do something like:

std::unique_ptr<TraceCursor> end_cursor_up = trace-GetCursor(thread);
std::unique_ptr<TraceCursor> begin_cursor_up = trace-GetCursor(thread);
begin_cursor_up->Prev(eTraceInstructionTypeBegin);

lldb/include/lldb/Target/TraceCursor.h

40

I am assuming all function calls need to be pure virtual here so that each plug-in can subclass this?

62

Do we not need the filter and ignore errors arguments for this as well?

73–76

Do we need this if we have GetError?

80

What is the intended ownership of this string? If this object would own it, maybe add a "std::string m_error;" member variable to this class to store any error strings.

89

describe what the size means a bit better? Is the size of instructions going to be larger if we go to the next Jump or call?

lldb/include/lldb/lldb-enumerations.h

963

Maybe "TraceCursorGranularity"? the "Type" suffix seems to indicate individual types

964–965

966–967

Maybe have two things for branches? Something like:

/// Any branch instruction even if the branch is conditional and not taken.
eTraceInstructionTypeBranch,
/// Only branches that are taken and cause the control flow to change.
eTraceInstructionTypeBranchTaken,

This might help avoid multiple calls to the cursor if the user doesn't need to worry about branches that aren't taken (like when single stepping maybe?)

[wallace]

• Simplified Trace.h by simply having lldb::TraceCursorUP GetCursor, as suggested.
• Improved the documentation including a sample code.
• Added methods to quickly move the trace to the beginning or the end.
• Renamed TraceInstructionType to TraceInstructionControlFlowType. I'm not happy with the long name though. I didn't stick to the granularity name because it's useful to know the control flow information of the current instruction, e.g. you might be traversing the instructions one by one but you want to log whenever you see a call.
• Also added a dummy "end of trace" invalid instruction. It helps iterating making sure that only the wanted instructions are seen. The other option, which I don't like, is to point to the last actual instruction of the trace, which might not be what the user wants and they would need to make a additional check for it before the loop.

[clayborg]

lldb/include/lldb/Target/TraceCursor.h

40–41

Should the TraceCursor point to the last instruction more like a begin() STL call?

88

SeekToEnd()?

91

SeekToStart()? SeekToBegin()?

117–118

Do we even need the instruction size in this cursor class interface? Clients can easily grab an instruction from GetLoadAddress() and do that themselves?

131

Zero is the invalid stop ID.

[wallace]

lldb/include/lldb/Target/TraceCursor.h

40–41

yes, i overcomplicated it

73–76

i imagine it might not always be a no-op to construct and error message

117–118

yes, this makes no sense. I sometimes use it for determining if two instructions are sequential, but i might as well use the control flow type to check that, i.e. if it's a normal or not taken branch, then the next instruction is sequential.

[wallace]

address comments:

• now simply pointing to the last instruction of the trace by default
• removed the GetInstructionSize, as it's really not needed
• made sure that the target lldbCore builds correctly
• improved documentation
• some other small fixes

[clayborg]

Just one issue regarding the stop ID for post mortem. Once this is resolved, we will be good to go!

lldb/include/lldb/Target/Trace.h

292

zero is invalid. We should just have post mortem use a valid stop ID like 1

367

As per my comment above, we will need to set this to 1 for post mortem, or maybe the process in post mortem already has its stop ID set to 1 so this will fix itself?

lldb/include/lldb/Target/TraceCursor.h

77

Is the cursor in an error state in the case where we return false? It should be and we should document it

lldb/source/Target/Trace.cpp

478

We should make sure for core file that the m_stop_id is set correctly somehow

[wallace]

lldb/include/lldb/Target/Trace.h

292

ahhhhh, good idea

lldb/source/Target/Trace.cpp

478

for a corefile the stop id is now set as 1 in Trace.h, which should be fine. RefreshLiveProcessState does nothing for a corefile, btw

[wallace]

address comments

[clayborg]

Just a few nits!

lldb/include/lldb/Target/Trace.h

292–293

No need to differentiate between line and post mortem stop IDs. Just say "The stop ID of the process being traced, or an invalid stop ID of zero if the trace is in an error state."

367

We really shouldn't have to set this manually. Probably best to start it at zero. It might even be better to create a LLDB_INVALID_STOPID define next to the LLDB_INVALID_ADDRESS define and use it.

lldb/source/Target/Trace.cpp

478

I would just allow the core file to set the process state like any other and start the m_stop_id at zero, the invalid value.

[wallace]

per comments

[wallace]

lldb/include/lldb/Target/Trace.h

367

this is a pretty good idea

lldb/source/Target/Trace.cpp

478

makes sense, i'll do the core file stuff in a different diff

[clayborg]

Just need to initialize the m_stop_id in the cursor to the invalid value and this is good to go.

lldb/include/lldb/Target/TraceCursor.h

133

This needs to be initialized right?

[vsk]

FTR, I'm quite happy with the new direction. Thanks!

[clayborg]

In D104422#2839895, @vsk wrote:

FTR, I'm quite happy with the new direction. Thanks!

Thanks for your input. It helped us come up with something we thought made sense given all the input!

lldb/include/lldb/Target/Trace.h

 //===-- Trace.h -------------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLDB_TARGET_TRACE_H
 #define LLDB_TARGET_TRACE_H
 
 #include <unordered_map>
 
 #include "llvm/Support/JSON.h"
 
 #include "lldb/Core/PluginInterface.h"
 #include "lldb/Target/Thread.h"
+#include "lldb/Target/TraceCursor.h"
 #include "lldb/Utility/ArchSpec.h"
 #include "lldb/Utility/TraceGDBRemotePackets.h"
 #include "lldb/Utility/UnimplementedError.h"
 #include "lldb/lldb-private.h"
 
 namespace lldb_private {
 
 /// \class Trace Trace.h "lldb/Target/Trace.h"
public:
   /// \param[in] callback
   ///     The callback to execute on each instruction. If it returns \b false,
   ///     the iteration stops.
   virtual void TraverseInstructions(
       Thread &thread, size_t position, TraceDirection direction,
       std::function<bool(size_t index, llvm::Expected<lldb::addr_t> load_addr)>
           callback) = 0;
 
+  /// Get a \a TraceCursor for the given thread's trace.
+  ///
+  /// \return
+  ///     A \a TraceCursorUP. If the thread is not traced or its trace
+  ///     information failed to load, the corresponding error is embedded in the
+  ///     trace.
+  virtual lldb::TraceCursorUP GetCursor(Thread &thread) = 0;
+
   /// Get the number of available instructions in the trace of the given thread.
   ///
   /// \param[in] thread
   ///     The thread whose trace will be inspected.
   ///
   /// \return
   ///     The total number of instructions in the trace, or \a llvm::None if the
   ///     thread is not being traced.
   virtual llvm::Optional<size_t> GetInstructionCount(Thread &thread) = 0;
 
   /// Check if a thread is currently traced by this object.
   ///
   /// \param[in] thread
   ///     The thread in question.
   ///
   /// \return
   ///     \b true if the thread is traced by this instance, \b false otherwise.
   virtual bool IsTraced(const Thread &thread) = 0;
 
   /// \return
   ///     A description of the parameters to use for the \a Trace::Start method.
   virtual const char *GetStartConfigurationHelp() = 0;
 
   /// Start tracing a live process.
   ///
   /// \param[in] configuration
   ///     See \a SBTrace::Start(const lldb::SBStructuredData &) for more
   ///     information.
public:
   /// \return
   ///     \a llvm::Error::success if the operation was successful, or
   ///     \a llvm::Error otherwise.
   llvm::Error Stop();
 
   /// Get the trace file of the given post mortem thread.
   llvm::Expected<const FileSpec &> GetPostMortemTraceFile(lldb::tid_t tid);
 
+  /// \return
+  ///     The stop ID of the live process being traced, or \b 0 if this is a
+  ///     post-mortem trace session.
+  uint32_t GetStopID();
+
 protected:
   /// Get binary data of a live thread given a data identifier.
   ///
   /// \param[in] tid
   ///     The thread whose data is requested.
   ///
   /// \param[in] kind
   ///     The kind of data requested.
protected:
   virtual void
   DoRefreshLiveProcessState(llvm::Expected<TraceGetStateResponse> state) = 0;
 
   /// Method to be invoked by the plug-in to refresh the live process state.
   ///
   /// The result is cached through the same process stop.
   void RefreshLiveProcessState();
 
+  uint32_t m_stop_id = 0;
   /// Process traced by this object if doing live tracing. Otherwise it's null.
-  int64_t m_stop_id = -1;
   Process *m_live_process = nullptr;
   /// tid -> data kind -> size
   std::map<lldb::tid_t, std::unordered_map<std::string, size_t>>
       m_live_thread_data;
   /// data kind -> size
   std::unordered_map<std::string, size_t> m_live_process_data;
 };
 
 } // namespace lldb_private
 
 #endif // LLDB_TARGET_TRACE_H

lldb/include/lldb/Target/TraceCursor.h

+//===-- TraceCursor.h -------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLDB_TARGET_TRACE_CURSOR_H
+#define LLDB_TARGET_TRACE_CURSOR_H
+
+#include "lldb/lldb-private.h"
+
+namespace lldb_private {
+
+/// Class used for iterating over the instructions of a thread's trace.
+///
+/// This class attempts to be a generic interface for accessing the instructions
+/// of the trace so that each Trace plug-in can reconstruct, represent and store
+/// the instruction data in an flexible way that is efficient for the given
+/// technology.
+///
+/// Live processes:
+///  In the case of a live process trace, an instance of a \a TraceCursor should
+///  point to the trace at the moment it was collected. If the process is later
+///  resumed and new trace data is collected, that should leave that old cursor
+///  unaffected.
+///
+/// Errors in the trace:
+///  As there could be errors when reconstructing the instructions of a trace,
+///  these errors are represented as failed instructions, and the cursor can
+///  point at them. The consumer should invoke \a TraceCursor::GetError() to
+///  check if the cursor is pointing to either a valid instruction or an error.
+///
+/// Instructions:
+///  A \a TraceCursor always points to a specific instruction or error in the
+///  trace.
+///
+///  The Trace initially points to the last item in the trace.
+///
+/// Sample usage:
+///
+///  TraceCursorUP cursor = trace.GetTrace(thread);
+///
+///  auto granularity = eTraceInstructionControlFlowTypeCall |
+///  eTraceInstructionControlFlowTypeReturn;
+///
+///  do {
+///     if (llvm::Error error = cursor->GetError())
+///       cout << "error found at: " << llvm::toString(error) << endl;
+///     else if (cursor->GetInstructionControlFlowType() &
+///     eTraceInstructionControlFlowTypeCall)
+///       std::cout << "call found at " << cursor->GetLoadAddress() <<
+///       std::endl;
+///     else if (cursor->GetInstructionControlFlowType() &
+///     eTraceInstructionControlFlowTypeReturn)
+///       std::cout << "return found at " << cursor->GetLoadAddress() <<
+///       std::endl;
+///  } while(cursor->Prev(granularity));
+class TraceCursor {
+public:
+  virtual ~TraceCursor() = default;
+
+  /// Move the cursor to the next instruction more recent chronologically in the
+  /// trace given the provided granularity. If such instruction is not found,
+  /// the cursor doesn't move.
+  ///
+  /// \param[in] granularity
+  ///     Bitmask granularity filter. The cursor stops at the next
+  ///     instruction that matches the specified granularity.
+  ///
+  /// \param[in] ignore_errors
+  ///     If \b false, the cursor stops as soon as it finds a failure in the
+  ///     trace and points at it.
+  ///
+  /// \return
+  ///     \b true if the cursor moved, \b false otherwise.
+  virtual bool Next(lldb::TraceInstructionControlFlowType granularity =
+                        lldb::eTraceInstructionControlFlowTypeInstruction,
+                    bool ignore_errors = false) = 0;
+
+  /// Similar to \a TraceCursor::Next(), but moves backwards chronologically.
+  virtual bool Prev(lldb::TraceInstructionControlFlowType granularity =
+                        lldb::eTraceInstructionControlFlowTypeInstruction,
+                    bool ignore_errors = false) = 0;
+
+  /// Force the cursor to point to the end of the trace, i.e. the most recent
+  /// item.
+  virtual void SeekToEnd() = 0;
+
+  /// Force the cursor to point to the beginning of the trace, i.e. the oldest
+  /// item.
+  virtual void SeekToBegin() = 0;
+
+  /// \return
+  ///   \b true if the trace corresponds to a live process who has resumed after
+  ///   the trace cursor was created. Otherwise, including the case in which the
+  ///   process is a post-mortem one, return \b false.
+  bool IsStale();
+
+  /// Instruction or error information
+  /// \{
+
+  /// Get the corresponding error message if the cursor points to an error in
+  /// the trace.
+  ///
+  /// \return
+  ///     \b llvm::Error::success if the cursor is not pointing to an error in
+  ///     the trace. Otherwise return an \a llvm::Error describing the issue.
+  virtual llvm::Error GetError() = 0;
+
+  /// \return
+  ///     The load address of the instruction the cursor is pointing at. If the
+  ///     cursor points to an error in the trace, return \b
+  ///     LLDB_INVALID_ADDRESS.
+  virtual lldb::addr_t GetLoadAddress() = 0;
+
+  /// \return
+  ///     The \a lldb::TraceInstructionControlFlowType categories the
+  ///     instruction the cursor is pointing at falls into. If the cursor points
+  ///     to an error in the trace, return \b 0.
+  virtual lldb::TraceInstructionControlFlowType
+  GetInstructionControlFlowType() = 0;
+
+  /// \}
+
+private:
+  /// The stop ID when the cursor was created.
+  uint32_t m_stop_id = 0;
+  /// The trace that owns this cursor.
+  lldb::TraceSP m_trace_sp;
+};
+
+} // namespace lldb_private
+
+#endif // LLDB_TARGET_TRACE_CURSOR_H

lldb/include/lldb/lldb-enumerations.h

 /// expression evaluation at the various points in its lifecycle.
 enum ExpressionEvaluationPhase {
   eExpressionEvaluationParse = 0,
   eExpressionEvaluationIRGen,
   eExpressionEvaluationExecution,
   eExpressionEvaluationComplete
 };
 
+/// Architecture-agnostic categorization of instructions for traversing the
+/// control flow of a trace.
+///
+/// A single instruction can match one or more of these categories.
+FLAGS_ENUM(TraceInstructionControlFlowType){
+    /// Any instruction.
+    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)};
+
+LLDB_MARK_AS_BITMASK_ENUM(TraceInstructionControlFlowType)
+
 /// Watchpoint Kind.
 ///
 /// Indicates what types of events cause the watchpoint to fire. Used by Native
 /// *Protocol-related classes.
 FLAGS_ENUM(WatchpointKind){eWatchpointKindWrite = (1u << 0),
                            eWatchpointKindRead = (1u << 1)};
 
 enum GdbSignal {

lldb/include/lldb/lldb-forward.h

 class ThreadPlanStepOut;
 class ThreadPlanStepOverBreakpoint;
 class ThreadPlanStepRange;
 class ThreadPlanStepThrough;
 class ThreadPlanTracer;
 class ThreadSpec;
 class ThreadPostMortemTrace;
 class Trace;
+class TraceCursor;
 class TraceSessionFileParser;
 class Type;
 class TypeAndOrName;
 class TypeCategoryImpl;
 class TypeCategoryMap;
 class TypeEnumMemberImpl;
 class TypeEnumMemberListImpl;
 class TypeFilterImpl;

 typedef std::weak_ptr<lldb_private::Thread> ThreadWP;
 typedef std::shared_ptr<lldb_private::ThreadCollection> ThreadCollectionSP;
 typedef std::shared_ptr<lldb_private::ThreadPlan> ThreadPlanSP;
 typedef std::shared_ptr<lldb_private::ThreadPostMortemTrace>
     ThreadPostMortemTraceSP;
 typedef std::weak_ptr<lldb_private::ThreadPlan> ThreadPlanWP;
 typedef std::shared_ptr<lldb_private::ThreadPlanTracer> ThreadPlanTracerSP;
 typedef std::shared_ptr<lldb_private::Trace> TraceSP;
+typedef std::unique_ptr<lldb_private::TraceCursor> TraceCursorUP;
 typedef std::shared_ptr<lldb_private::Type> TypeSP;
 typedef std::weak_ptr<lldb_private::Type> TypeWP;
 typedef std::shared_ptr<lldb_private::TypeCategoryImpl> TypeCategoryImplSP;
 typedef std::shared_ptr<lldb_private::TypeImpl> TypeImplSP;
 typedef std::shared_ptr<lldb_private::TypeMemberFunctionImpl>
     TypeMemberFunctionImplSP;
 typedef std::shared_ptr<lldb_private::TypeEnumMemberImpl> TypeEnumMemberImplSP;
 typedef std::shared_ptr<lldb_private::TypeFilterImpl> TypeFilterImplSP;

lldb/source/Target/CMakeLists.txt

add_lldb_library(lldbTarget
   ThreadPlanStepRange.cpp
   ThreadPlanStepThrough.cpp
   ThreadPlanStepUntil.cpp
   ThreadPlanTracer.cpp
   ThreadPlanStack.cpp
   ThreadSpec.cpp
   ThreadPostMortemTrace.cpp
   Trace.cpp
+  TraceCursor.cpp
   TraceSessionFileParser.cpp
   UnixSignals.cpp
   UnwindAssembly.cpp
   UnwindLLDB.cpp
 
   LINK_LIBS
     lldbBreakpoint
     lldbCore

lldb/source/Target/Trace.cpp

 //===-- Trace.cpp ---------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "lldb/Target/Trace.h"
 
 #include "llvm/Support/Format.h"
 
 #include "lldb/Core/Module.h"
 #include "lldb/Core/PluginManager.h"
 #include "lldb/Symbol/Function.h"
 #include "lldb/Target/ExecutionContext.h"
 #include "lldb/Target/Process.h"
for (const TraceBinaryData &item : thread_state.binaryData)
       m_live_thread_data[thread_state.tid][item.kind] = item.size;
   }
 
   for (const TraceBinaryData &item : live_process_state->processBinaryData)
     m_live_process_data[item.kind] = item.size;
 
   DoRefreshLiveProcessState(std::move(live_process_state));
 }
+
+uint32_t Trace::GetStopID() {
+  RefreshLiveProcessState();
+  return m_stop_id;
+}

lldb/source/Target/TraceCursor.cpp

+//===-- TraceCursor.cpp -----------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "lldb/Target/TraceCursor.h"
+
+#include "lldb/Target/Trace.h"
+
+using namespace lldb_private;
+
+bool TraceCursor::IsStale() { return m_stop_id != m_trace_sp->GetStopID(); }