[Soot-list] Spark's TypeManager patch
Hamid A. Toussi
hamid2c at gmail.com
Fri Feb 3 03:01:43 EST 2012
Hi Ondrej,
Thanks a lot for reviewing and applying my patch. I really appreciate it.
Best wishes,
Hamid
On 2/2/12, Ondrej Lhotak <olhotak at uwaterloo.ca> wrote:
> OK, thanks for the explanation. I didn't realize that the
> makeClassTypeMask and makeMaskOfInterface methods would not
> be called when fh is null.
>
> I have applied the patch to Subversion r3692.
>
> Ondrej
>
> On Thu, Feb 02, 2012 at 05:27:09PM +0330, Hamid A. Toussi wrote:
>> Hi Ondrej,
>>
>> Thanks a lot for reviewing the patch.
>> > Hello Hamid...
>> >
>> > Thank you for the cleaner patch. I reviewed it carefully, and I think it
>> > is almost ready for me to check in, except for one issue. In the case
>> > that Spark is run with the option ignore-types, the fh field of the
>> > TypeManager remains null. As far as I can see, in this case, the patched
>> > version of the TypeManager will crash with a null pointer exception.
>> > Could you please modify the patch accordingly and run your tests with
>> > the ignore-types option?
>>
>> The patched version of TypeManager does not raise any exception when
>> it is run with ignore-types in my environment. If you have encountered
>> an exception in this case, would it be possible to tell me the list of
>> options you passed to Spark and Soot.
>>
>> Anyway, I think the patched version of TypeManager would not encounter
>> any problem when fh is null (ignore-types is turned on). The only
>> method which is changed by the patch is "makeTypeMask" (plus a number
>> of new methods which were not present in the original). As you can see
>> in this method (below), in case that fh is null, it would return
>> without invoking any of the patched parts of the code (The first three
>> lines of this method are not changed by the patch).
>>
>> final public void makeTypeMask() {
>> RefType.v( "java.lang.Class" );
>> typeMask = new LargeNumberedMap( Scene.v().getTypeNumberer() );
>> if( fh == null ) return;
>>
>> int numTypes = Scene.v().getTypeNumberer().size();
>> if( pag.getOpts().verbose() )
>> G.v().out.println( "Total types: "+numTypes );
>> // **
>> initClass2allocs();
>> makeClassTypeMask(Scene.v().getSootClass("java.lang.Object"));
>> // **
>> ....
>>
>> "makeTypeMask" method is called before doing points-to propagation.
>> "get" would be called during the propagation and it is not changed by
>> the patch.
>>
>> Best wishes,
>> Hamid
>>
>> >
>> >> --- TypeManager.java.orig 2012-01-25 18:41:15.000000000 +0330
>> >> +++ TypeManager.java 2012-01-25 20:25:06.000000000 +0330
>> >> @@ -18,6 +18,7 @@
>> >> */
>> >>
>> >> package soot.jimple.spark.internal;
>> >> +import java.util.*;
>> >> import soot.jimple.spark.pag.*;
>> >> import soot.*;
>> >> import soot.util.*;
>> >> @@ -27,8 +28,22 @@
>> >>
>> >> /** A map of bit-vectors representing subtype relationships.
>> >> * @author Ondrej Lhotak
>> >> + *
>> >> + * @author Hamid A. Toussi (hamid2c at gmail.com):
>> >> + * Making TypeManager faster by making type masks during a
>> >> + * depth-first-traversal on the class hierarchy. First, type-masks of
>> >> the
>> >> + * leaves of Class Hierarchy are created and then the type mask of
>> >> each
>> >> + * type T is obtained by ORing type maks of T’s sub-types and setting
>> >> the
>> >> + * bit-numbers associated with Allocation Nodes of type T. The
>> >> type-mask
>> >> + * of each interface is achieved by ORing the type-masks of its
>> >> top-level
>> >> + * concrete implementers. In fact, Reference types are visited in
>> >> + * reversed-topological-order.
>> >> */
>> >> public final class TypeManager {
>> >> + private Map<SootClass, List<AllocNode>> class2allocs =
>> >> + new HashMap<SootClass, List<AllocNode>>(1024);
>> >> + private List<AllocNode> anySubtypeAllocs = new
>> >> LinkedList<AllocNode>();
>> >> +
>> >> public TypeManager( PAG pag ) {
>> >> this.pag = pag;
>> >> }
>> >> @@ -79,13 +94,28 @@
>> >> int numTypes = Scene.v().getTypeNumberer().size();
>> >> if( pag.getOpts().verbose() )
>> >> G.v().out.println( "Total types: "+numTypes );
>> >> -
>> >> + // **
>> >> + initClass2allocs();
>> >> + makeClassTypeMask(Scene.v().getSootClass("java.lang.Object"));
>> >> + // **
>> >> ArrayNumberer allocNodes = pag.getAllocNodeNumberer();
>> >> for( Iterator tIt = Scene.v().getTypeNumberer().iterator();
>> >> tIt.hasNext(); ) {
>> >> final Type t = (Type) tIt.next();
>> >> if( !(t instanceof RefLikeType) ) continue;
>> >> if( t instanceof AnySubType ) continue;
>> >> if( isUnresolved(t) ) continue;
>> >> + // **
>> >> + if (t instanceof RefType &&
>> >> !t.equals(RefType.v("java.lang.Object"))
>> >> + && !t.equals(RefType.v("java.io.Serializable"))
>> >> + && !t.equals(RefType.v("java.lang.Cloneable"))) {
>> >> +
>> >> + SootClass sc = ((RefType)t).getSootClass();
>> >> + if (sc.isInterface()) {
>> >> + makeMaskOfInterface(sc);
>> >> + }
>> >> + continue;
>> >> + }
>> >> + // **
>> >> BitVector mask = new BitVector( allocNodes.size() );
>> >> for( Iterator nIt = allocNodes.iterator(); nIt.hasNext();
>> >> ) {
>> >> final Node n = (Node) nIt.next();
>> >> @@ -118,5 +148,82 @@
>> >> protected FastHierarchy fh = null;
>> >> protected PAG pag;
>> >> protected QueueReader allocNodeListener = null;
>> >> + // ** new methods
>> >> + private void initClass2allocs() {
>> >> + Iterator allocIt = pag.getAllocNodeNumberer().iterator();
>> >> + while (allocIt.hasNext()) {
>> >> + AllocNode an = (AllocNode) allocIt.next();
>> >> + addAllocNode(an);
>> >> + }
>> >> + }
>> >> +
>> >> + final private void addAllocNode(final AllocNode alloc) {
>> >> + alloc.getType().apply(new TypeSwitch() {
>> >> + final public void caseRefType(RefType t) {
>> >> + SootClass cl = t.getSootClass();
>> >> + List<AllocNode> list ;
>> >> + if ((list = class2allocs.get(cl)) == null) {
>> >> + list = new LinkedList<AllocNode>();
>> >> + class2allocs.put(cl, list);
>> >> + }
>> >> + list.add(alloc);
>> >> + }
>> >> + final public void caseAnySubType(AnySubType t) {
>> >> + anySubtypeAllocs.add(alloc);
>> >> + }
>> >> + });
>> >> + }
>> >> +
>> >> + final private BitVector makeClassTypeMask(SootClass clazz) {
>> >> + int nBits = pag.getAllocNodeNumberer().size();
>> >> + final BitVector mask = new BitVector(nBits);
>> >> +
>> >> + List<AllocNode> allocs = null;
>> >> + if (clazz.isConcrete()) {
>> >> + allocs = class2allocs.get(clazz);
>> >> + }
>> >> + if (allocs != null){
>> >> + for (AllocNode an : allocs) {
>> >> + mask.set(an.getNumber());
>> >> + }
>> >> + }
>> >> +
>> >> + Collection<SootClass> subclasses = fh.getSubclassesOf(clazz);
>> >> + if (subclasses == Collections.EMPTY_LIST) {
>> >> + for (AllocNode an : anySubtypeAllocs) {
>> >> + mask.set(an.getNumber());
>> >> + }
>> >> + typeMask.put(clazz.getType(), mask);
>> >> + return mask;
>> >> + }
>> >> +
>> >> + for (SootClass subcl : subclasses) {
>> >> + mask.or(makeClassTypeMask(subcl));
>> >> + }
>> >> +
>> >> + typeMask.put(clazz.getType(), mask);
>> >> + return mask;
>> >> + }
>> >> +
>> >> + final private BitVector makeMaskOfInterface(SootClass interf) {
>> >> + if (!(interf.isInterface())) throw new RuntimeException();
>> >> +
>> >> + BitVector ret = new
>> >> BitVector(pag.getAllocNodeNumberer().size());
>> >> + typeMask.put(interf.getType(), ret);
>> >> + Collection<SootClass> implementers =
>> >> fh.getAllImplementersOfInterface(interf);
>> >> +
>> >> + for (SootClass impl : implementers) {
>> >> + BitVector other = (BitVector)typeMask.get(impl.getType());
>> >> + if (other == null) throw new
>> >> RuntimeException(impl.toString());
>> >> + ret.or(other);
>> >> + }
>> >> + // I think, the following can be eliminated. It is added to
>> >> make
>> >> + // type-masks exactly the same as the original type-masks
>> >> + if (implementers.size() == 0) {
>> >> + for (AllocNode an : anySubtypeAllocs)
>> >> ret.set(an.getNumber());
>> >> + }
>> >> + return ret;
>> >> + }
>> >> +
>> >> }
>> >>
>> >
>> >
>>
>
More information about the Soot-list
mailing list