[Soot-list] Spark's TypeManager patch
Ondrej Lhotak
olhotak at uwaterloo.ca
Wed Feb 1 16:30:53 EST 2012
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? If you do that, I expect that I will apply
the resulting patch to the Soot Subversion repository.
Ondrej
On Wed, Jan 25, 2012 at 08:40:22PM +0330, Hamid A. Toussi wrote:
> Hi Ondrej,
>
> I have attached a cleaner patch. I hope this would be useful.
>
> Thanks,
> Hamid
>
> On 1/25/12, Ondrej Lhotak <olhotak at uwaterloo.ca> wrote:
> > 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
> >> >>
> >>
> >
> --- 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