[Soot-list] Spark's TypeManager patch
Ondrej Lhotak
olhotak at uwaterloo.ca
Thu Feb 2 14:22:27 EST 2012
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