[Soot-list] Spark's TypeManager patch

[Ondrej Lhotak]

The patch appears to essentially be a rewrite rather than a
modification, so I cannot really comment on its correctness.

I don't think I understand the use case in which the existing version is
insufficient, or in which the new version would be faster.

In the common use case, AllocNodes are added to the type masks gradually
as they are discovered on the fly, and the current implementation has
been designed for this case. The new version appears to target the
alternative use case when all (or most) AllocNodes are known in advance,
and thus all the type masks can be made at once. In the common use
case, I would expect the new version to be significantly slower than
the current version (unless I'm misunderstanding something), since it
recalculates the whole type mask for each type by oring the masks of its
subtypes, even when only a small number of AllocNodes are added.

On Sun, Jan 08, 2012 at 12:00:38PM +0100, Eric Bodden wrote:
> Thanks a lot Hamid.
> 
> Ondrej would you be able to have a look if this patch makes sense to
> you? I don't think I am qualified to judge this...
> 
> Eric
> 
> On 7 January 2012 17:16, Hamid A. Toussi <hamid2c at gmail.com> wrote:
> > Hello all,
> >
> > This patch makes TypeManager of Spark significantly faster specially
> > in cases that on-fly-cg is turned off. TypeManager is responsible for
> > making type masks before doing points-to sets propagation.
> >
> > Below is an overview:
> > 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. Type-mask
> > of each interface is achieved by ORing type-masks of its top-level
> > concrete implementers. In fact, Reference types are visited in
> > reversed-topological-order.
> >
> > A patch is attached that can be applied to
> > soot/jimple/spark/internal/TypeManager.java.
> > A Java class is also attached which can be used for testing this patch
> > as follows:
> >
> >        Date startFTM = new Date();
> >        FastTypeManager ftm = new FastTypeManager(pag);
> >        if (!opts.ignore_types())
> >                ftm.setFastHierarchy(Scene.v().getFastHierarchy());
> >        ftm.makeTypeMask();
> >        Date endFTM = new Date();
> >        reportTime("Fast Type masks", startFTM, endFTM);
> >
> >        Set<AllocNode> set = new HashSet<AllocNode>();
> >        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( FastTypeManager.isUnresolved(t) ) continue;
> >            BitVector orig = pag.getTypeManager().get(t);
> >            BitVector nmask = ftm.get(t);
> >            if (orig.equals(nmask)) continue;
> >            BitVector temp = new BitVector(nmask);
> >            temp.xor(orig);
> >            for (BitSetIterator it = temp.iterator(); it.hasNext(); ) {
> >                int n = it.next();
> >                AllocNode an = (AllocNode)pag.getAllocNodeNumberer().get(n);
> >                set.add(an);
> >            }
> >        }
> >        for (AllocNode an : set) G.v().out.println(an);
> >        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( FastTypeManager.isUnresolved(t) ) continue;
> >            BitVector orig = pag.getTypeManager().get(t);
> >            BitVector nmask = ftm.get(t);
> >            for (AllocNode an : set) {
> >                if (orig.get(an.getNumber()) && !nmask.get(an.getNumber())) {
> >                        G.v().out.print(t +" mask should contain "+an+": ");
> >                        if (!(t instanceof RefType)) throw new RuntimeException();
> >                        SootClass sc = ((RefType)t).getSootClass();
> >                        if (!sc.isInterface()) G.v().out.print(" not interface");
> >                        G.v().out.println(Scene.v().getFastHierarchy().
> >                                        getAllImplementersOfInterface(sc).size());
> >                }
> >                if (!orig.get(an.getNumber()) && nmask.get(an.getNumber())) {
> >                        G.v().out.println(t +" shouldn't contain "+an);
> >                }
> >            }
> >        }
> >
> > Testing should be done before applying the patch using the original TypeManager.
> >
> > Thanks,
> > Hamid
> >
> > _______________________________________________
> > Soot-list mailing list
> > Soot-list at sable.mcgill.ca
> > http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> >
> 
> 
> 
> -- 
> Eric Bodden, Ph.D., http://bodden.de/
> Head of Secure Software Engineering Group at EC SPRIDE
> Principal Investigator in Secure Services at CASED
> Tel: +49 6151 16-75422    Fax: +49 6151 16-72051
> Room 3.2.14, Mornewegstr. 30, 64293 Darmstadt
>