Re: [linuxtools-dev] TMF: Expressing dependency information and displayi

[Michel Dagenais <michel.dagenais@xxxxxxxxxx>]

> As trace analysis tools become available in TMF (trace synchronization, 
> critical path calculation, latency, etc), a requirement is to be able to 
> express dependencies between events.

Yes, an example is a process A writing to a pipe to send a request to process B, and waiting and receiving the answer from B later. The critical path for that "task" is first in A, then in B while it serves the request and back to A when the answer is received from B, unblocking A.

> I'd propose to use a graph structure to represent those dependencies
> (a set of vertices - an object at a given timestamp - and edges - a link
> between two vertices).

Do the "vertices" already exist or you plan to "add" new objects. Currently, events in the trace may be seen as vertices. Similarly, state begin and end could be seen as vertices. State intervals may be seen as some sort of edge. 

The dependency links added by the analysis link a state change in one process to the state change in another process. For example, the wake-up of A by B connects the two and "reroutes" the critical path from B to A. However, this happen at a well defined time, (unlike state intervals having a duration). You mention later another example of two processes interacting through the network. In that case, the network latency could be represented by another state interval (packet in the network) or included into the dependency link?

> Each type of trace analysis would produce its own graph of dependencies, 
> as the edges needed by each are not the same.  Each graph will be saved 
> to disk as a supplementary file.

State history is tricky because each state interval has a variable duration, hence the tree like index to search for all intervals intersecting the current time. If the dependency links are punctual in time, it then becomes more like the events in traces which are sorted by time and easily accessed by binary search.

> As for displaying those dependencies, it could be done through layers on 
> the Control flow view.  Just like in Google Map, one could select the
> layers to display and the corresponding graphs will be drawn over the
> control flow view.

The control flow view could indeed be annotated with a red line on top or just over each process interval within the critical path. You could also show a resource view, each interval in the critical path, (just like what is done for each CPU when each process interval on that CPU is shown). You could also highlight the critical path on the multi-CPU resource view.

> The dependency graph could be displayed also as a sequence diagram. It
> could also be exported as a dot file and visualized in external tool 
> like graphviz.

Yes.

> This is the big idea.  I would like to get some feedback on this 
> proposal.  Does that make sense?  Any complications ahead?  Better
> ideas?

Looks good! Brings more questions though:

What is the typical usage scenario for this data? As you proceed to build the state, you uncover depedencies (mostly wake-up actions from one thread to another) which you may write as punctual "events". Other dependencies require more work, for instance matching packets. Thereafter, you need to search the resulting graph to find the critical path: start of A, follow each state interval of A until a packet is sent to B and A blocks, follow state intervals in B until B replies and unblocks A, follow intervals in A until the end of A.

Once you have the critical path, you must be able to use that information to annotate the control flow view. Should it be a property of the state interval? Alternatively, when you are about to draw a state interval, you could check if, at its start time, it is connected to the critical path?