[Soot-list] Spark's TypeManager patch
Hamid A. Toussi
hamid2c at gmail.com
Wed Jan 25 12:10:22 EST 2012
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
>> >>
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ftm-clean.patch
Type: text/x-patch
Size: 5601 bytes
Desc: not available
Url : http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20120125/70f75a73/attachment.bin
More information about the Soot-list
mailing list