[Soot-list] Spark's TypeManager patch
Ondrej Lhotak
olhotak at uwaterloo.ca
Tue Jan 24 19:49:57 EST 2012
OK. Would it be possible to make a patch that only changes what actually
needs to change, so I can see what is changing? The current patch
appears to delete almost everything, and then add it all back again.
Ondrej
On Thu, Jan 19, 2012 at 09:50:08AM +0330, Hamid A. Toussi wrote:
> Hello Ondrej,
>
> Thank you for your reply.
>
> > 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.
> >
>
> This patch makes the type manager faster in case that on the fly
> call-graph is turned off. I didn't change "get" method of the current
> version so the behaviour of the current version is not changed in case
> that on the fly call-graph is used in any major way. Only creation of
> type masks before doing points-to propagation (and on the fly
> call-graph construction) are done 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.
> >
>
> The behaviour of type manager is not changed during points-to
> propagation (and on the fly call-graph construction) in the new
> version since the "get" method which is used during this phase is not
> changed. However, even the common case (where on the fly call-graph is
> used) gets benefit from this patch since some of the AllocNodes are
> created before doing points-to propagation and are known in advance.
>
> Hamid
>
> > 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
> >>
>
More information about the Soot-list
mailing list