Re: Index format v5

From: Michael Haggerty <mhagger@alum.mit.edu>
Date: May 4, 2012, 07:12 UTC
Message-ID: <4FA3816E.8090005@alum.mit.edu>
In-Reply-To: <87obq5p1t0.fsf@thomas.inf.ethz.ch>

On 05/03/2012 08:16 PM, Thomas Rast wrote:

Show 25 quoted lines

> Thomas Gummerer<t.gummerer@gmail.com>  writes:
>
>>    32-bit crc32 checksum over ctime seconds, ctime nanoseconds,
>>      ino, file size, dev, uid, gid (All stat(2) data except mtime) [7]
> [...]
>> [7] Since all stat data (except mtime and ctime) is just used for
>>      checking if a file has changed a checksum of the data is enough.
>>      In addition to that Thomas Rast suggested ctime could be ditched
>>      completely (core.trustctime=false) and thus included in the
>>      checksum. This would save 24 bytes per index entry, which would
>>      be about 4 MB on the Webkit index.
>>      (Thanks for the suggestion to Michael Haggerty)
>
> This is the part I'm most curious about.  Are we missing anything?
> Michael brought it up on IRC: the stat() results are only used to test
> whether they are still the same, with the exception of the mtime (which
> also undergoes raciness checks).
>
> As far as I can see, none of st_{ino,dev,uid,gid} are useful for
> anything.  st_size might conceivably be used as a hint for a buffer
> size, but nobody actually does that.  The ctime undergoes stricter
> checks, but AFAICS it's also all about whether it has changed, and
> besides that can be turned off.  We think all of those fields can be
> replaced by an arbitrary hash/CRC and only tested for equality.  32 bits
> should be plenty, probably even if we just xor the values together.

XOR is definitely *not* adequate; for example, changing uid=gid="you" to uid=gid="me" would not affect the XOR of the values (assuming, as is often the case, that each user has his own uid/gid with the same numerical values).

Which hash to use depends on some estimate of the likelihood that the hashes collide and simultaneously that the other metadata coincide. It seems to me that CRC-32 would be adequate. But if not, a longer hash could be used (albeit with less space savings).

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/