Page MenuHomePhabricator

[trace] Add a TraceCursor class

Authored by wallace on Jun 16 2021, 2:30 PM.



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.

Diff Detail

Event Timeline

wallace requested review of this revision.Jun 16 2021, 2:30 PM
wallace created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptJun 16 2021, 2:30 PM
clayborg added inline comments.Jun 16 2021, 5:17 PM

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.


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


Ditto, return std::unique_ptr<TraceCursor>?


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


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);

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


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


Do we need this if we have GetError?


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.


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?


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


Maybe have two things for branches? Something like:

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

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 updated this revision to Diff 352605.Jun 16 2021, 7:32 PM
  • 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 added inline comments.Jun 16 2021, 9:13 PM

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




SeekToStart()? SeekToBegin()?


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


Zero is the invalid stop ID.

wallace marked 11 inline comments as done.Jun 17 2021, 3:59 PM
wallace added inline comments.

yes, i overcomplicated it


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


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 updated this revision to Diff 352872.Jun 17 2021, 4:33 PM
wallace marked 2 inline comments as done.

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
wallace marked 7 inline comments as done.Jun 17 2021, 4:34 PM
clayborg requested changes to this revision.Jun 18 2021, 12:04 PM

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


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


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?


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


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

This revision now requires changes to proceed.Jun 18 2021, 12:04 PM
wallace marked 2 inline comments as done.Jun 18 2021, 3:44 PM
wallace added inline comments.

ahhhhh, good idea


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 updated this revision to Diff 353117.Jun 18 2021, 3:45 PM
wallace marked an inline comment as done.

address comments

clayborg requested changes to this revision.Jun 18 2021, 4:28 PM

Just a few nits!


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."


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.


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.

This revision now requires changes to proceed.Jun 18 2021, 4:28 PM
wallace updated this revision to Diff 353135.Jun 18 2021, 5:23 PM
wallace marked 3 inline comments as done.

per comments

wallace added inline comments.Jun 18 2021, 5:43 PM

this is a pretty good idea


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

clayborg accepted this revision.Jun 23 2021, 2:44 PM

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


This needs to be initialized right?

This revision is now accepted and ready to land.Jun 23 2021, 2:44 PM
This revision was landed with ongoing or failed builds.Jun 23 2021, 10:35 PM
This revision was automatically updated to reflect the committed changes.
vsk added a comment.Jun 24 2021, 4:53 PM

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

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!