[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:47:46 EST 2008
Correction: the end of the code should have read:
csOrder.addEdge(cs1, cs2);
instead of
csOrder.addEdge(cs1.group, cs2.group);
-Richard
On Mon, Nov 10, 2008 at 10:42 AM, Richard L. Halpert <
richard.halpert at mail.mcgill.ca> wrote:
> 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/93dc3a4d/attachment-0001.htm
More information about the Soot-list
mailing list