[Soot-list] Data dependencies between Threads?

[Richard L. Halpert]

Armand,
As Eric mentioned, we have a may happen in parallel (MHP) analysis, and a
thread-local-objects (TLO) analysis.  The MHP analysis ignores the effects
of locks, which may or may not be what you want.  There is also an MHP
analysis in Soot that *does* consider locks, but it's not particularly
robust.  It tends to choke on most programs.  Feel free to fix it if you'd
like!

We also have a thread-based side effect (TBSE) analysis that combines
traditional side effect information with some thread-specific
approximations.  If you use this analysis on two chunks of code that might
run in parallel, you can compare the resulting read/write sets to determine
if there might be a data dependency.  TBSE can take a TLO analysis object as
a parameter, in which case it ignores reads and writes to thread-local
objects.  All of these analyses depend on the use of Spark for points-to
information.  If you have the latest CVS version of Soot, you could
construct the TBSE object as follows to get generally-relevant results:

MhpTester mhp = new UnsynchronizedMhpAnalysis(); // You need to use Spark or
this will throw a runtime exception
ThreadLocalObjectsAnalysis tlo = new ThreadLocalObjectsAnalysis(mhp);
TransactionAwareSideEffectAnalysis tasea = new
TransactionAwareSideEffectAnalysis(Scene.v().getPointsToAnalysis(),
Scene.v().getCallGraph(),
null, tlo);

Then, to find the read set for a statement, you would do "RWSet reads =
tasea.readSet(method, statement, null, new HashSet())".  The HashSet is used
to store a list of used local values, which you can throw away like this if
you'd like.  As you can see, the interface for some of this stuff is still
maturing.

You may pass "null" instead of a ThreadLocalObjectsAnalysis object if you
want.  TLO takes quite a while to compute, so you may find it's not worth
it.

Note that TBSE makes some approximations that may or may not be suitable for
your analysis.  TBSE performs a very rough approximation of the
thread-relevant effects of calls to the Java libraries.  Most static calls
are ignored, and most instance calls are treated like a read or write to the
receiver object of the call.  This works great for programs that manipulate
Collection objects, but is surely unsafe for some more sophisticated uses of
the library.  There are also some cases where the effects of inheritance and
virtual dispatch are not dealt with properly, especially in the TLO
analysis.  Again, in most programs it won't matter, but there WILL be cases
where it does.  If you need more details, send me an email about it
off-list.

I'm curious to know: what are you trying to accomplish?

-Richard





On 9/4/07, Eric Bodden <eric.bodden at mail.mcgill.ca> wrote:
>
> Yes, we have a new analysis that determines what "may happen in
> parallel" and also thread-local variables. See
> http://www.sable.mcgill.ca/publications/techreports/#report2007-3 for
> details.
>
> Maybe Richard can tell a bit more.
>
> Eric
>
> On 04/09/07, Armand Navabi <anavabi at purdue.edu> wrote:
> > Does Soot provide a way to find control and data-dependencies between
> > threads?
> > I have read previous posts on the mailing list about Indus and Kaveri.
> > Does anyone
> > know if Indus, Kaveri, or any other such tools can do this form of
> > program dependence
> > analyses (control- and data-dependencies for multithreaded Java
> programs)?
> >
> > Thanks,
> > Armand
> >
> > _______________________________________________
> > Soot-list mailing list
> > Soot-list at sable.mcgill.ca
> > http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> >
>
>
> --
> Eric Bodden
> Sable Research Group
> McGill University, Montréal, Canada
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.CS.McGill.CA/pipermail/soot-list/attachments/20070904/f5bb7b56/attachment.htm