[Soot-list] Spark's TypeManager patch
Hamid A. Toussi
hamid2c at gmail.com
Thu Jan 19 01:20:08 EST 2012
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