[Soot-list] Undeterministic processing order

[Saswat Anand]

I agree that the suggested fix will not take care of all cases,
especially when a
callgraph is built using spark or paddle. There are at least a few
other places in
Scene class and at least one place in SootResolver that needs to be fixed too.
Sometime back, I started to fix this problem, and following information is what
I had found. I am not sure if they cover all cases, but here they are in case
somebody wants to fix the problem.

In SootResolver class,

//classToTypesSignature.put( sc, new
ArrayList(dependencies.typesToSignature) );
//classToTypesHierarchy.put( sc, new
ArrayList(dependencies.typesToHierarchy) );
==>
classToTypesSignature.put( sc, sort(dependencies.typesToSignature) );
classToTypesHierarchy.put( sc, sort(dependencies.typesToHierarchy) );

In Scene class:
** field "basicclasses" is an array of HashSets. To take care of this,
loadBasicClasses()
needs to be fixed as:
//it = basicclasses[i].iterator();
==>
it = sort(basicclasses[i]).iterator();

** In loadDynamicClasses(), dynClasses local variable is a HashSet. To take care
of this:
//for (String className : dynClasses) {
//       dynamicClasses.add( Scene.v().loadClassAndSupport(className) );
//}
==>
for (String className : sort(dynClasses)) {
       dynamicClasses.add( Scene.v().loadClassAndSupport(className) );
}

** In prepareClasses, unProcessedClasses is a HashSet. I think the suggested
fix fixes this case.

** Finally, depending on whether SourceLocator.v().getClassesUnder(path)
behaves deterministically, all results returned by this method needs
to be sorted.

Where, sort method sorts a collection based on the alphabetic order on
toString()
representation of the elements.

Saswat

----- Original Message -----
From: "Patrick Lam" <plam at sable.mcgill.ca>
To: "David Mohr" <dmohr at cs.unm.edu>
Cc: "soot-list" <soot-list at sable.mcgill.ca>
Sent: Wednesday, October 21, 2009 3:19:45 PM GMT -05:00 US/Canada Eastern
Subject: Re: [Soot-list] Undeterministic processing order

Looks harmless enough to me. I've committed the change. Thanks for
looking into this!

(I'm not completely convinced, however, that prepareClasses is the only
method that determines who to Jimplify, especially when SPARK gets
involved. But if it works for you, it works for me.)

pat

David Mohr wrote:
> Thanks everyone for the comments.
>
> It's not that complicated after all: Soot uses mostly the nice Chain
> interface, but in Scene.prepareClasses() it mangles the classes using
> a HashSet, which destroys the order. The prepareClasses() function
> maybe could be improved, but it suffices to use a Chain instead of a
> Set in that function to preserve order.
>
> Attached is a patch against 2.3.0 which fixes this.
>
> Note that I haven't tested it with any excludes.
>
> ~David
>
> On Wed, Oct 21, 2009 at 9:33 AM, Patrick Lam <plam at sable.mcgill.ca> wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> Let me just comment that it's a bit tricky to figure out how Soot
>> figures out which classes to process. Last year, I started to figure out
>> how one might parallelize class processing; obviously, one has to find
>> the queue of classes to process to parallelize processing. However, I
>> ran out of time and had to do other things, like writing papers. Syed is
>> looking into finishing the job I did with parallelization, though, and
>> he might have something to say about this in a week or so.
>>
>> pat
>>
>> Prof. Laurie Hendren wrote:
>>>   David,
>>>
>>> Yes, it is annoying.  I know we removed some of these non-deterministic
>>> data structures for exactly that reason.   If you find where it is
>>> happening and have a suggested fix which wouldn't impact performance
>>> otherwise, please suggest it.
>>>
>>> Cheers, Laurie
>>>
>>>
>>> +-----------------------------------------------------------------
>>> | Laurie Hendren --- laurie.hendren at mcgill.ca <mailto:laurie.hendren at mcgill.ca>
>>> | Associate Dean (Academic), Faculty of Science,
>>> | Dawson Hall, McGill University, 853 Sherbrooke St W,
>>> | Montreal QC H3A 2T6 Canada, 514-398-7179, fax 514-398-1774
>>> +----------------------------------------------------------------
>>> | For contact and home page info as Professor, Computer Science:
>>> | http://www.sable.mcgill.ca/~hendren   ---  hendren at cs.mcgill.ca <mailto:hendren at cs.mcgill.ca>
>>> | Research: http://www.sable.mcgill.ca  http://aspectbench.org
>>> +----------------------------------------------------------------
>>>
>>>
>>>
>>> David Mohr wrote:
>>>> On Wed, Oct 21, 2009 at 9:17 AM, Patrick Lam <plam at sable.mcgill.ca> <mailto:plam at sable.mcgill.ca> wrote:
>>>>
>>> I'll bet that Soot puts classes into a non-list data structure that
>>> doesn't preserve order.
>>>
>>>>> Ah that makes sense.
>>>>>
>>>>> It is annoying when hunting bugs though, because if you rerun Soot
>>>>> after fixing something, you might encounter some other bug first.
>>>>>
>>>>> ~David
>>>>>
>>>>>
>>> David Mohr wrote:
>>>
>>>>>>> Hi,
>>>>>>> I've noticed that soot processes classes in some seemingly random
>>>>>>> order. At the very least, it's not always the same for identical
>>>>>>> invocations of Soot. Is there a particular reason for this behavior?
>>>>>>>
>>>>>>> ~David
>>>>>>> _______________________________________________
>>>>>>> Soot-list mailing list
>>>>>>> Soot-list at sable.mcgill.ca <mailto:Soot-list at sable.mcgill.ca>
>>>>>>> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>>>>>>>
>>>> _______________________________________________
>>>> Soot-list mailing list
>>>> Soot-list at sable.mcgill.ca <mailto:Soot-list at sable.mcgill.ca>
>>>> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>>>>
>> -----BEGIN PGP SIGNATURE-----
>> Version: GnuPG v1.4.10 (GNU/Linux)
>> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>>
>> iEYEARECAAYFAkrfKbgACgkQNTVxnNGEyOjnFgCfW6GnNZ/f35OUGZA393W4M0fB
>> AjEAnRMAHxjqYFJjVD5rmXEMixmuVIAD
>> =9n78
>> -----END PGP SIGNATURE-----
>>

_______________________________________________
Soot-list mailing list
Soot-list at sable.mcgill.ca
http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list