[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: reversible fingerprint comment in membuffer code

From: Stefan Fuhrmann <stefan.fuhrmann_at_wandisco.com>
Date: Wed, 20 May 2015 08:36:23 +0200

On Tue, May 19, 2015 at 8:25 PM, Philip Martin <philip.martin_at_wandisco.com>
wrote:

> Philip Martin <philip.martin_at_wandisco.com> writes:
>
> > Is this comment in cache-membuffer.c:combine_key correct?
> >
> > /* scramble key DATA. All of this must be reversible to prevent
> key
> > * collisions. So, we limit ourselves to xor and permutations. */
> > data[1] = (data[1] << 27) | (data[1] >> 37);
> > data[1] ^= data[0] & 0xffff;
> > data[0] ^= data[1] & APR_UINT64_C(0xffffffffffff0000);
> >
> > I don't see why this needs to be reversible, and it's not clear it is
> > reversible.
>
> I talked to Stefan and I believe I can explain. Reversibility is not a
> hard requirement on trunk or 1.9 at present, since we store the full
> key, but may be a requirement in future. This code is for keys that fit
> in the fingerprint and when generating the fingerprint from such keys we
> want to avoid introducing collisions, i.e. distinct keys should generate
> distinct fingerprints. The cache would cope with collisions but is
> better without. A reversible scramble is one way to ensure no
> collisions are introduced.
>

Yes. While the restriction implied by the comment does
not apply as strictly to /trunk, it will apply again once the
1.10-cache-improvements branch gets merged.

The other reason for the scramble is that it spreads the variation for
> small keys across more bytes of the fingerprint and thus across the
> cache.
>

Exactly.

-- Stefan^2.
Received on 2015-05-20 08:36:32 CEST

This is an archived mail posted to the Subversion Dev mailing list.