Re: Thinking aloud.

Hi.

On 10/26/2012 03:06 AM, Theodore Ts'o wrote:
> On Thu, Oct 25, 2012 at 08:32:10PM +1100, Nigel Cunningham wrote:
>> I started some work on this today, and it occurred to me (wrongly?)
>> that if I go down the Fletcher-32 path, it's pointless. If the
>> Fletcher-32 checksums match, I have to do the SHA1 to check the
>> pages really are the same. If they don't match, I still have to
>> calculate the SHA1 of the new contents so I can store it. So I may
>> as well just calculate the SHA1 for every page and compare them. Am
>> I making a mistake somewhere?
> Hmm, good point.  I forgot that in the case where they don't match,
> you need to calculate the SHA1 for the next suspend/resume cycle.
Taking it one step further, would you agree with the assertions of 
others that even if the SHA1s match, I still need to memcmp the pages to 
check they're actually the same (so SHA1 is effectively reducing an 
O(n^2) comparison of pages with each other to O(n)).
> I like the page flags idea... I'll look into it some more. Would it
> work on non-x86?
> It should.  As long as the VM supports read-only pages (which is
> pretty much all of the major ones, since you can't have any kind of
> security if you don't --- imagine what might happen if a bad guy can
> modify the text page of the shared libc image, for example).
Cool. Makes perfect sense; I guess I misunderstood something I read on 
LKML long ago and now can't remember :) Okay; I'll give that a go then, 
particularly having seen the cost of calculating the SHA1 for every page.

Following on the other thread a bit longer, MD5 was faster (429MB/s) 
than SHA1 (320MB/s). It would be interesting to see whether the 
increased speed of MD5 results in a significantly greater number of 
pages that are false positives.

Regards,

Nigel