Re: Transparent compression in the FS

From: jw schultz
Date: Fri Oct 17 2003 - 13:24:37 EST


On Fri, Oct 17, 2003 at 11:44:44AM +0200, Pavel Machek wrote:
> Hi!
>
> > Several months ago we encountered the hash collision problem
> > with rsync. This brought about a fair amount of discussion
>
> So you found collision in something like md5 or sha1?

Each block was done with md4 truncated to 16 bits and
adler32. The file as a whole is double checked with the
full 128 bit md4 and adler32.

The changes made were to improve block sizing to reduce the
number of blocks, and to scale the hash truncation according
to block count and size on a per-file basis.

The probability of false positives in rsync are orders of
magnitude smaller than they would be in a block hashing
filesystem. Yet we were seeing it happen (with truncated
hash) at measurable rates on files as small as a few hundred
megabytes. It was almost commonplace on iso images.

--
________________________________________________________________
J.W. Schultz Pegasystems Technologies
email address: jw@xxxxxxxxxx

Remember Cernan and Schmitt
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/