On Wednesday 30 January 2008 03:05, Konstantin Serebryany wrote:
> Few observations regarding MSMProp1:
>
> When in exclusive state (i.e. state is Read or Write and #SS == 1) and we
> access the memory from the same thread, HB(SS,currS) is always true.
> This means that each access that leaves us in the same thread rewrites the
> shadow value with SS={currS}; LS=currLS.
> In other words, while in exclusive state we do not track the history, but
> only store information about the last access.
> This helps us to avoid false positives on tests like test{37,43,44,45},
> while still reporting a (true) race on test10.My impression of MSMProp1 is that it is like a pure happens-before detector, except that it deals with locks using locksets rather than by generating happens-before edges in the graph. Indeed, I wonder if it is possible to take the formal description of MSMProp1 and from it derive the formal description of a pure happens- before detector I posted earlier in this thread (Wed Jan 23 14:30:21 2008) by (1) removing all locksets from the MSMProp1 description, and (2) adding happens-before edges for lock/unlock events. It would be interesting to try. > Both MSMProp1 and MSMHelgrind have false negative on test46: > // > // First: Second: > // 1. write > // 2. MU.Lock() > // 3. write > // 4. MU.Unlock() (sleep) > // a. MU.Lock() > // b. write > // c. MU.Unlock(); I don't think you can have zero false positives and zero false negatives at the same time (holy grail ...), because all these state machines are different approximations to something which is NP-complete (and therefore which we cannot compute exactly). > With MSMProp1 we no longer need to scan all memory at thread_join. Good. > We, however, still have this scan-all-memory in shadow_mem_make_NoAccess. > The comment says: > 7. Modify all shadow words, by removing ToDelete from the lockset > of all ShM and ShR states. Note this involves a complete scan > over map_shmem, which is very expensive... > > Do we really need this? > If we don't do that and if a new lock gets allocated at the same memory > location we may miss some very weird race. > Any other reason for doing this? I only did it to be clean / safe. Otherwise I think if you deallocate a lock and allocate a new one at the same address, very strange things will happen. Is it really needed? I don't know. But I don't know how to prove/argue that it is not needed. Alternative question is, is it possible to do this cheaply/incrementally? There is also a different problem for the scaling of Helgrind to very large programs: the Lock structures are freed when locks are destroyed, but Segment and Thread are never freed. So a program which generates a very large number of Segments, or Threads, will eventually cause Helgrind to run out of memory. I can see that Helgrind's storage management strategy will need to be redesigned at some future point. Are you intending to make a revised MSMProp1 patch that can deal with larger programs? I would like to compare it to MSMHelgrind on OpenOffice and Firefox. J ------------------------------------------------------------------------- This SF.net email is sponsored by: Microsoft Defy all challenges. Microsoft(R) Visual Studio 2008. http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ _______________________________________________ Valgrind-developers mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/valgrind-developers
