[Soot-list] How to obtain the topological graph in the
transactional transformation phase (wjtp.tn)?
Richard L. Halpert
richard.halpert at mail.mcgill.ca
Mon Nov 10 13:42:52 EST 2008
It's my pleasure. The changes I've made for your sake are all things that
needed to be done anyways... you're just the first to ask!
What you're asking for isn't particularly straightforward: it's not easy to
statically determine if lock1 and lock2 are different objects, so using them
as the nodes in such a graph isn't a particularly good idea. You have two
options that would be similar:
1) The LockAllocator uses a may-alias relationship to group locks together -
so if lock1 in *may* be the same as lock2, they would be treated as a single
lock (and the two critical sections would be put in the same
CriticalSectionGroup). The Lock allocator constructs this graph for the
sake of deadlock detection. You can use the deadlock detection graph by
calling
soot.jimple.toolkits.thread.synchronization.LockAllocation.getDeadlockGraph().
The nodes are CriticalSectionGroups, and the edges represent calls from a
critical section in one group to a critical section in another group. Be
sure to call Soot with "-p wjtp.tn avoid-deadlock:false", or else the
deadlock detector may stop constructing the graph early if it finds
potential deadlock.
2) Construct the graph with CriticalSections as nodes. You could then later
try to determine yourself which critical sections are using the same locks,
and which are using different locks.
Such a graph is not constructed by the wjtp.tn phase, but a simple
modification tot he code of
soot.jimple.toolkits.thread.synchronization.DeadlockDetector would do it. I
just checked in code to allow you to access the list of critical sections
found by wjtp.tn. Using that, you should be able to get the graph you want
with the code below (which is modified from DeadlockDetector.java). Note
that the graph would include transitive edges, and it doesn't check to see
if some kind of locking or other control flow would invalidate an edge.
import soot.*;
import soot.toolkits.graph.*;
import soot.jimple.toolkits.callgraph.*;
import soot.jimple.toolkits.thread.synchronization.*;
List<CriticalSection> criticalSections =
LockAllocator.v().getCriticalSections();
TransitiveTargets tt = new TransitiveTargets(Scene.v().getCallGraph(), new
Filter(new CriticalSectionVisibleEdgesPred(null)));
MutableDirectedGraph csOrder = new HashMutableDirectedGraph();
Iterator<CriticalSection> csit1 = criticalSections.iterator();
while(csit1.hasNext())
{
CriticalSection cs1 = csit1.next();
// add node for this cs
if( !csOrder.containsNode(cs1) )
csOrder.addNode(cs1);
// Get list of cs1's target methods
if(cs1.transitiveTargets == null)
{
cs1.transitiveTargets = new HashSet<MethodOrMethodContext>();
for(Unit cs1Invoke : cs1.invokes)
{
Iterator<MethodOrMethodContext> targetIt =
tt.iterator(cs1Invoke);
while(targetIt.hasNext())
cs1.transitiveTargets.add(targetIt.next());
}
}
// compare to each other tn
Iterator<CriticalSection> csit2 = criticalSections.iterator();
while(csit2.hasNext())
{
CriticalSection cs2 = deadlockIt2.next();
// add node for this cs
if( !csOrder.containsNode(cs2) )
csOrder.addNode(cs2);
if( cs1.transitiveTargets.contains(cs2.method) )
{
csOrder.addEdge(cs1.group, cs2.group);
}
}
}
-Richard
On Mon, Nov 10, 2008 at 5:59 AM, Marco Bakera
<marco.bakera at tu-dortmund.de>wrote:
> Hey Richard,
>
> thanks for your very fast support and your efforts. :)
>
> However, I am sorry to say that I'm in doubt whether the graph you created
> perfectly fits my needs. I assume the graph depicts the critical section
> interference graph.
>
> Anyhow, I need a graph that reflects synchronized blocks on lock objects as
> nodes and edges being introduced between two such nodes if one such
> synchronized block reaches the other one (e.g. via methods calls).
>
> Here is some example that will hopefully make everything clearer. :)
>
> class A {
> Object lock1 = new Object();
>
> void methodF() {
> synchronized(lock1) {
> new B().methodF();
> }
> }
>
> class B {
> Object lock2 = new Object();
>
> void methodF() {
> synchronized(lock2) {
> ;
> }
> }
> }
>
> will create a lock graph with two nodes for lock objects lock1 and lock2,
> and
> one edge lock1 -> lock2.
>
> Is there some kind of (intermediate) structure in your analysis that may
> support me on this?
> Do you know of another part of Soot that could help me?
>
>
> Best regards and thank you for your help,
> Marco.
>
> On Sunday 09 November 2008 05:33:43 RichardLHalpert at gmail.com wrote:
> > Marco,
> > Ok, I checked in a small change so that you can call
> >
> soot.jimple.toolkits.thread.synchronization.LockAllocator.v().getInterferen
> >ceGraph() after invoking Soot from your code. There wasn't an existing
> graph
> > interface in Soot that would be immediately appropriate for the
> > interference graph, so I didn't do anything on that front just yet. You
> can
> > use the CriticalSectionInterferenceGraph object directly. For historical
> > reasons, the CriticalSectionInterferenceGraph is stored in a rather
> unusual
> > way: as a set of groups of critical sections (nodes). Each group
> implements
> > Iterable<CriticalSection>. The (bidirectional) edges to/from a node are
> > stored in a field "public HashSet<CriticalSectionDataDependency> edges"
> on
> > the CriticalSection. Naturally, each edge is therefore stored twice, once
> > at each of its end nodes.
> >
> > -Rich
> >
> > On Nov 8, 2008 8:57am, "Richard L. Halpert"
> >
> > <richard.halpert at mail.mcgill.ca> wrote:
> > > Marco,
> > > Well, that's not really possible right now, but if you're willing to
> use
> >
> > a nightly build (rather than a released version of Soot), then I can
> > check-in some way to access the graph (hopefully today). Currently, the
> > graph is created as a local variable during the wjtp.tn phase, but I
> could
> > store in it a static variable and make it accessible by something like:
> >
> soot.jimple.toolkits.thread.synchronization.LockAllocator.v().getInterferen
> >ceGraph(), which you could call from your code after running Soot.
> >
> > > Right now the interference graph doesn't implement any normal
> graph-like
> >
> > interface. I'll see if I can throw one on there quickly, but if not, I'll
> > send you some info on how to use the data structure in its current form.
> >
> > > -Rich
> > >
> > > On Sat, Nov 8, 2008 at 8:11 AM, Marco Bakera
> marco.bakera at tu-dortmund.de>
> >
> > wrote:
> > > Thanks for that fast help. That's a commandline that looks more like
> >
> > Soot. ;)
> >
> > > Is it possible to obtain the generated graph directly by using Soot's
> >
> > API? I
> >
> > > would like to process this graph further in my Java application.
> > >
> > >
> > >
> > >
> > >
> > > Thanks for help and greetings from Germany,
> > >
> > > Marco.
> > >
> > > On Friday 07 November 2008 18:51:51 Richard L. Halpert wrote:
> > > > Copying this to the list, since it may be helpful to others.
> > > >
> > > >
> > > >
> > > > On Fri, Nov 7, 2008 at 9:50 AM, Richard L. Halpert
> > > >
> > > > richardlhalpert at gmail.com> wrote:
> > > > > The main problem is that you need to run in whole-program mode or
> > > > > wjtp
> > > > >
> > > > > will not be run. You also should use Spark for points-to analysis.
> > > > > Try
> > > > >
> > > > > this:
> > > > >
> > > > >
> > > > >
> > > > > java -Xmx1024m soot.Main -cp
> > >
> > >
> .:$JAVA_HOME/jre/lib/rt.jar:$JAVA_HOME/jre/lib/jce.jar:$JAVA_HOME/jre/lib
> > >
> > > > >/jsse.jar -w --app -p cg.cha enabled:false -p cg.spark enabled:true
> -p
> > > > >
> > > > >
> > > > > wjtp.tnenabled:true -p wjtp.tn locking-scheme:leave-original -p
> >
> > wjtp.tn
> >
> > > > > do-tlo:false -p wjtp.tndo-mhp:true -p wjtp.tn print-graph:true
> > > > >
> > > > >
> > > > > YourMainClass
> > > > >
> > > > >
> > > > >
> > > > > The print-graph:true option should cause Soot to print a .dot file
> to
> > > > >
> > > > > stdout (with a prefix on every line, which you will need to
> remove).
> >
> > You
> >
> > > > > will need the dot program to turn the .dot file into a graphic (it
> > > > >
> > > > > supports all kinds of outputs - png, svg, ps, etc.).
> > > > >
> > > > >
> > > > >
> > > > > -Rich
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > On Fri, Nov 7, 2008 at 7:53 AM, Marco Bakera
> > > > >
> > > > > marco.bakera at uni-dortmund.de
> > > > >
> > > > > > wrote:
> > > > >>
> > > > >> Hey everybody,
> > > > >>
> > > > >>
> > > > >>
> > > > >> I am currently looking for locking information in java code and
> >
> > stumpled
> >
> > > > >> upon
> > > > >>
> > > > >> your transactional transformation phase and especially the
> >
> > topological
> >
> > > > >> graph
> > > > >>
> > > > >> that will be created here.
> > > > >>
> > > > >>
> > > > >>
> > > > >> I tried to get some information about the transactional regions in
> >
> > java
> >
> > > > >> programs by calling
> > > > >>
> > > > >>
> > > > >>
> > > > >> java soot.Main -p wjtp.tn on -p wjtp.tn locking-scheme:leave -p
> >
> > wjtp.tn
> >
> > > > >> print-graph:true java.lang.Integer
> > > > >>
> > > > >>
> > > > >>
> > > > >> but did not get the desired topological graph.
> > > > >>
> > > > >>
> > > > >>
> > > > >> Do you have any suggestions what went wrong?
> > > > >>
> > > > >>
> > > > >>
> > > > >> Thanks for help.
> > > > >>
> > > > >>
> > > > >>
> > > > >>
> > > > >>
> > > > >> Best regards,
> > > > >>
> > > > >> Marco.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.CS.McGill.CA/pipermail/soot-list/attachments/20081110/0dd8969e/attachment.htm
More information about the Soot-list
mailing list