From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from pigeon.gentoo.org ([69.77.167.62] helo=lists.gentoo.org)
	by finch.gentoo.org with esmtp (Exim 4.60)
	(envelope-from <gentoo-dev+bounces-34224-garchives=archives.gentoo.org@lists.gentoo.org>)
	id 1LWHWX-0002xU-RJ
	for garchives@archives.gentoo.org; Sun, 08 Feb 2009 21:49:10 +0000
Received: from pigeon.gentoo.org (localhost [127.0.0.1])
	by pigeon.gentoo.org (Postfix) with SMTP id 77181E03CF;
	Sun,  8 Feb 2009 21:49:08 +0000 (UTC)
Received: from smtp.gentoo.org (smtp.gentoo.org [140.211.166.183])
	by pigeon.gentoo.org (Postfix) with ESMTP id 36B8DE03CF
	for <gentoo-dev@lists.gentoo.org>; Sun,  8 Feb 2009 21:49:08 +0000 (UTC)
Received: from [192.168.0.100] (173-224.1-85.cust.bluewin.ch [85.1.224.173])
	(using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits))
	(No client certificate requested)
	by smtp.gentoo.org (Postfix) with ESMTP id 85603651FF
	for <gentoo-dev@lists.gentoo.org>; Sun,  8 Feb 2009 21:49:06 +0000 (UTC)
Subject: Re: [gentoo-dev] [RFC] DIGESTS metadata variable for cache
 validation
From: Tiziano =?ISO-8859-1?Q?M=FCller?= <dev-zero@gentoo.org>
To: gentoo-dev@lists.gentoo.org
In-Reply-To: <498F423A.8040604@gentoo.org>
References: <498758E6.5080609@gentoo.org>
	 <1234045916.24784.1373.camel@localhost>  <498E17E6.8060407@gentoo.org>
	 <1234080464.24784.2517.camel@localhost>  <498E9EFE.2030807@gentoo.org>
	 <1234093879.24784.2819.camel@localhost>  <498F423A.8040604@gentoo.org>
Content-Type: multipart/signed; micalg="pgp-sha1"; protocol="application/pgp-signature"; boundary="=-+SbFaXhXAFeG2ippu8sC"
Organization: Gentoo
Date: Sun, 08 Feb 2009 22:48:57 +0100
Message-Id: <1234129737.18160.191.camel@localhost>
Precedence: bulk
List-Post: <mailto:gentoo-dev@lists.gentoo.org>
List-Help: <mailto:gentoo-dev+help@lists.gentoo.org>
List-Unsubscribe: <mailto:gentoo-dev+unsubscribe@lists.gentoo.org>
List-Subscribe: <mailto:gentoo-dev+subscribe@lists.gentoo.org>
List-Id: Gentoo Linux mail <gentoo-dev.gentoo.org>
X-BeenThere: gentoo-dev@lists.gentoo.org
Reply-to: gentoo-dev@lists.gentoo.org
Mime-Version: 1.0
X-Mailer: Evolution 2.24.4 
X-Archives-Salt: 10f2385c-4ff7-485d-ac54-1e51bf398f9e
X-Archives-Hash: fc7555b034a95182fd6b2681b7e87e48


--=-+SbFaXhXAFeG2ippu8sC
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Am Sonntag, den 08.02.2009, 12:36 -0800 schrieb Zac Medico:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>=20
> Tiziano M=C3=BCller wrote:
> > Am Sonntag, den 08.02.2009, 00:59 -0800 schrieb Zac Medico:
> >> -----BEGIN PGP SIGNED MESSAGE-----
> >> Hash: SHA1
> >>
> >> Tiziano M=C3=BCller wrote:
> >>> Am Samstag, den 07.02.2009, 15:23 -0800 schrieb Zac Medico:
> >>>> -----BEGIN PGP SIGNED MESSAGE-----
> >>>> Hash: SHA1
> >>>>
> >>>> Tiziano M=C3=BCller wrote:
> >>>>> Am Montag, den 02.02.2009, 12:34 -0800 schrieb Zac Medico:
> >>>> I like that idea. That way it's not necessary to bump the EAPI in
> >>>> order to change the hash function. So, a typical DIGESTS value might
> >>>> look like this:
> > You still have to bump the EAPI in case you want to use a new hash not
> > already available now (like SHA-3). The advantage of noting the used
> > hash is that new PMs can handle old metadata cache.
>=20
> That's true.
>=20
> >>>> SHA1 02021be38b a28b191904 3992945426 6ec21b29a3
> >>> Sleeping over it again I don't think that truncating a hash is a good
> >>> idea (truncating it from 40 to 10 digits makes the possibility of
> >>> collisions much much higher).
> >> The probability of collision is much higher, but it's still
> >> relatively small. Given the "avalanche effect" that is typical of
> >> cryptographic hash functions, it's extremely unlikely that collision
> >> will occur in such a way that it will cause a problem for cache
> >> validation.
> > The "avalanche effect" as I understood it is required for a hash
> > function to avoid simple calculations of collisions (what the diffusion
> > is for crypto algorithms). So, small changes should affect as many
> > numbers in the hash as possible. But you don't have only small changes
> > here in case somebody patches an eclass, so, the only thing which count=
s
> > is the probability of a collision.
>=20
> Well, the avalanche effect helps in the sense that the leftmost 10
> digits would serve approximately as well as any other 10 digits out
> of all of them. But you're right about the probability of a
> collision being what really matters. With 10 hex digits, we've got a
> space of 16^10 =3D 1.1e12 possible combinations. Given a space that
> large, the probability of a collision pretty small.
>=20
> >>> But if you want to go this way, I'd say you should use something like
> >>> SHA1t (t for truncated) to make sure we can use full hashes once we f=
eel
> >>> it's appropriate.
> >> We could, but I think SHA1 would also be fine since one can infer
> >> from the length of the string that it's been truncated.
> > No, guessing is a bad thing here because it could be truncated because
> > of faulty metadata. But the main motivation is that if you write SHA1
> > everyone reading it expects it to be a full SHA1 hash, which it isn't.
>=20
> Well, if the metadata is faulty then the digests are unlikely to
> match and the cache will be discarded anyway as invalid. However, I
> think your point is still somewhat valid, so SHA1t is fine with me
> if that makes more people happy. Does anyone else have a preference
> here?
>=20
> > But if your target is to reduce the size of the metadata cache, why
> > store the hashes of the eclasses in the ebuild's metadata and not in a
> > seperate dir? They have to be the same for every ebuild, don't they?
> > In case you have an average number of eclasses which is bigger than 4,
> > you can even store the full hash with less space used than with
> > truncated hashes for all eclasses.
>=20
> The problem with having eclass integrity data shared in a separate
> file is that it creates a requirement for all cache entries which
> reference the same eclasses to be consistent with one another. This
> means that a single cache entry can no longer be updated atomically.
> For example, before updating the shared eclass integrity data, you'd
> want to make sure that you first discard all of the cache entries
> which reference it. Although it can be done this way, I think it's
> much more convenient to have all of the integrity data encapsulated
> within each individual cache entry.
Ok, let me see if I get this: Since parts of the content of a
metadata-entry (like the DEPEND/RDEPEND vars) depend on the contents of
the eclass used by the time a cache entry got generated, you want to
store the eclass' hash in the ebuild entry to make sure the entry gets
invalidated once the eclass changes. Is that correct?


--=20
=EF=BB=BF-------------------------------------------------------
Tiziano M=C3=BCller
Gentoo Linux Developer, Council Member
Areas of responsibility:
  Samba, PostgreSQL, CPP, Python, sysadmin
E-Mail     : dev-zero@gentoo.org
GnuPG FP   : F327 283A E769 2E36 18D5  4DE2 1B05 6A63 AE9C 1E30

--=-+SbFaXhXAFeG2ippu8sC
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Dies ist ein digital signierter Nachrichtenteil

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)

iEYEABECAAYFAkmPU0kACgkQGwVqY66cHjDQqQCcCxkhy0ap0/Kk9ZsJwvOgfa9e
uy0An2nq7jUOarD5IkeNq+QYBoWPXvRR
=5jqf
-----END PGP SIGNATURE-----

--=-+SbFaXhXAFeG2ippu8sC--