ldionne / d2 Goto Github PK

The ABBA_redundant_diff_functions integration test fails intermittently.

The Repository class should be usable under different modes (read/write at least).

Desirable behavior: Opening an inexistant repository in read only mode should be an error (a little bit like the standard streams).

The command line utility should be aware of mutually exclusive options and an error should be reported when mutually exclusive options are specified.

See libs/program_options/example/real.cpp for help.

std::thread::ids may be reused after a thread has joined. This is probably the same for boost::thread::ids. We really need a way of handling this. For example, when loading events, if a thread with the same id has already been started and terminated, we could create a new artificial id and store the original one for diagnostic purposes. The analysis would use the artificial thread id (because they all need to be different) but the diagnostic could refer to the other one (and specify that the thread id was reused).

While we use an artificial dyno::thread_id for logging purposes, we could store the system thread id for diagnostic purposes. Since system thread ids may be reused, we could also specify the number of times that thread id has been reused (that could help the programmer to locate the deadlock?).

It should be possible to identify unique events using some kind of coordinate system. Every event would have different coordinates.

Possible coordinates:

• Process
  To which process the event belongs
• Thread
  Inside the process, to which thread the event belongs
• Segment
  Inside the thread, in which segment is the event located
• Some other id
  Inside a segment, an event is the nth event.

Integration with Boost is currently only partial, and the provided patch is not really helpful.

The readme should be meaningful, with explanations about how to build, etc..

The cyclic_permutation.hpp header contains dubious use of rvalue references for perfect forwarding. This was initially required because template parameters would not deduce to the same type if two iterators were passed with different value categories, i.e. lvalue and rvalue.

I gotta see whether:

1. My understanding of rvalue references is completely broken (plzplzplz no)
2. I am just abusing the feature
3. I am doing the right thing, and things ought to be ugly

The mixed_events unit test should be parametrized so it can be run with different combinations and numbers of mixed events.

There are several BOOST_ASSERTs in the api implementation in src/api/api.cpp. They should not be assertions and we should decide of a way to handle these cases.

Possible solution: Generate special events such that the graph construction algorithms do not explode.

A DSEL should be used to define event characteristics. From a specification created using template metaprogramming, serialization code, accessors and such could probably be generated.

Locking ABBA and then BAAB in the same thread does not yield a deadlock potential because both groups are in the same thread. However, the happens-before would return that both happen at the same time. Clearly, they can't happen at the same time because they are in the same thread, i.e. they are executed in serie. Is this a design flaw?

For an example of where the current analysis falls short, see the ABBA_gatelock_in_parent_thread scenario. Adding support for this might require non-trivial changes, but it is quite important since this pattern will probably appear frequently in real applications.

It would be nice to have a way to detect synchronization objects that are never unlocked.
This can be done by looking at the locks still held by a thread at the end of this thread's construction in the lock graph.

Since we're now using tiernan_all_cycles to detect cycles, the ABBA_noise scenario can't even finish in a reasonable amount of time. Some possibilities for improvement are:

• Use an iterative approach to seek cycles of smaller length first. Fewer deadlocks should
  happen between large number of threads, anyway.
• Split the analysis by spotting connected components in the graph. Obviously, deadlocks
  can't happen between objects in different connected components.
• Use an approximative algorithm. For example, our previous algorithm can find some
  deadlocks very fast. We could maybe mix the two approaches.
• Try using Johson's elementary circuits; the worst case has a better complexity.