On Mon, Sep 02, 2024 at 03:41:31PM +0200, Patrick Steinhardt wrote: > On Sun, Sep 01, 2024 at 12:03:32PM -0400, Taylor Blau wrote: > > Update hashwrite() and friends to use the fast_-variants of hashing > > functions, calling for e.g., "the_hash_algo->fast_update_fn()" instead > > of "the_hash_algo->update_fn()". > > > > These callers only use the_hash_algo to produce a checksum, which we > > depend on for data integrity, but not for cryptographic purposes, so > > these callers are safe to use the fast (and potentially non-collision > > detecting) SHA-1 implementation. > > > > To time this, I took a freshly packed copy of linux.git, and ran the > > following with and without the OPENSSL_SHA1_FAST=1 build-knob. Both > > versions were compiled with -O3: > > > > $ git for-each-ref --format='%(objectname)' refs/heads refs/tags >in > > $ valgrind --tool=callgrind ~/src/git/git-pack-objects \ > > --revs --stdout --all-progress --use-bitmap-index <in >/dev/null > > > > Without OPENSSL_SHA1_FAST=1 (that is, using the collision-detecting > > SHA-1 implementation for both cryptographic and non-cryptographic > > purposes), we spend a significant amount of our instruction count in > > hashwrite(): > > > > $ callgrind_annotate --inclusive=yes | grep hashwrite | head -n1 > > 159,998,868,413 (79.42%) /home/ttaylorr/src/git/csum-file.c:hashwrite [/home/ttaylorr/src/git/git-pack-objects] > > > > , and the resulting "clone" takes 19.219 seconds of wall clock time, > > 18.94 seconds of user time and 0.28 seconds of system time. > > > > Compiling with OPENSSL_SHA1_FAST=1, we spend ~60% fewer instructions in > > hashwrite(): > > > > $ callgrind_annotate --inclusive=yes | grep hashwrite | head -n1 > > 59,164,001,176 (58.79%) /home/ttaylorr/src/git/csum-file.c:hashwrite [/home/ttaylorr/src/git/git-pack-objects] > > > > , and generate the resulting "clone" much faster, in only 11.597 seconds > > of wall time, 11.37 seconds of user time, and 0.23 seconds of system > > time, for a ~40% speed-up. > > Neat. I knew that SHA1DC was slower, but I certainly didn't expect it to > make such a huge difference. Yeah, I was similarly surprised as you are. > One thing I'm missing is an analysis of users of "csum-file.c" so that > we can assess whether it is safe to switch over this subsystem to use > the fast variant. As far as I can see it's used for packfiles, commit > graphs, the index, packfile reverse indices, MIDXs. None of them strike > me as particularly critical, also because almost all of them would be > created locally by the user anyway. Right, the only case I believe we care about hash collisions is writing loose objects, and hashing packed objects from within a packfile. The loose object write path does not use hashfile(), so it is immune from these changes. The path where we read the objects packed in a packfile to determine their OID is also safe, because that happens in index-pack and does not use the _fast variants of these functions. > The only exception are of course packfiles, which get generated by the > remote. Is it possible to generate packfiles with colliding trailer > hashes? And if so, how would the client behave if it was served a > packfile with such a collision? I think the answer to this is "no", but let's consolidate this discussion into the sub-thread where brian and I are already chatting about this to avoid having the discussion in two places. Thanks, Taylor
