Re: Building packages three times in a row
paddy@panici.net writes:
> On Mon, Sep 24, 2007 at 08:35:50PM +0200, Goswin von Brederlow wrote:
>>
>> Some tools use randomization to get out of worst case situations or
>> general optimization. For example when you look for an optimal
>> allocation of register usage you can do a search by picking a random
>> register allocation and repeat that a few thousand times to find a
>> suitable minimum.
>>
>> Or a randomized heap that gives you O(1) time for
>> all operations instead of O(lg n).
>>
>> By requiring bit-to-bit identical results you eliminate all such
>> randomness and could seriously hinder the algorithm available for
>> tools.
>
> While I have a hard time understanding why true randomness is
> required to solve such problems, I have no problem accepting that
> practically this is a big obstacle.
You could probably fix the seed for the random number generator and
thereby make the build fixed. But then some joker would construct a
source code that would run into the worst case with specifically that
seed.
> It will not be trivial to establish the equivalence of two such
> pieces of object code.
>
> Thank you for sharing this insight. I think you have helped me to
> finally see the problem that others have pointed to.
>
> Taking etch as the example, could you give any idea what percentage
> of package we might expect this to turn up in ?
I think was doing some randomness with register allocation in some
cases. But I'm not sure if that is still the case with all the changes
gcc had over the years.
But if then you could get for example r0 and r1 interchanged in a
function causing a change in all opcaodes involving them.
> In any case it sounds very much like this idea would be much harder
> to do than I had originally hoped :-(
It will be impossible if you don't excude a lot of known timestamps.
> Regards,
> Paddy
MfG
Goswin
Reply to: