Profiling: when matching events between threads, the matching ID must be UNIQUE (per process)

[therault]

Description

When debugging memory leaks, I used the returned pointer as the ID for events.

That pointer is temporally unique (at any given time, it represents a single allocation), but it is often re-used during the execution.

Now, consider a case when a thread can free the allocation of another thread. We can have the following scenario:

• stream 0 allocates ID 1 at time 1
• stream 1 frees ID 1 at time 2
• stream 1 allocates ID 1 time 3
• stream 0 frees ID 1 at time 4

The inter-stream matching of the profiling will do the following:

• 1 event starts on stream 0 at time 1, and ends on stream 0 at time 4
• 1 event start on stream 1 at time 2, and ends on stream 0 at time 4

This is because of the strategy 'find the matching end on the same stream first, and if not, then find any matching event that occurs after the current timestamp on another stream'.

That strategy is also flawed in this scenario, if we add a stream 2, that ends the allocation of ID 1 from stream 1, we will still match the end with stream 0 because we tried stream 0 first...

Describe the solution you'd like

To properly match end events when reusing the IDs, the only correct solution is to BFS the matching end on ALL threads simultaneously (advancing on the global ordering of events by timestamp). ALL events (including the ones that have their matching end on the same thread) will have to follow the same strategy. Even with the acceleration for lookup in PR #372, this will probably too costly.

We could mark the events as 'REUSE_ID', to tell the parser that those need BFS matching to circumvent that problem...

I think the best solution is to forbid this behavior: if cross-thread matching is necessary, the user cannot re-use IDs during the run, and matching IDs must be unique. The documentation should reflect this.

Describe alternatives you've considered

1. For cross-thread matching, matching IDs must be unique for the run, and the documentation should state this more clearly
2. Change the matching to do a full BFS matching for ALL events (extremely costly)
3. Change the matching to do a full BFS matching for events marked as 'REUSE_ID'

Additional context

Memory allocation tracking in the PaRSEC engine also suffers from that problem... For my use case in TTG, I can easily fix by providing a run-wise unique ID for each allocation.