git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 4/4] csum-file.c: use fast SHA-1 implementation when available

From
Patrick Steinhardt <ps@pks.im>
Date
Sep 2, 2024, 13:41 UTC
Message-ID
<ZtXAi9KYOKejJmOS@tanuki>
In-Reply-To
<e8f5cbd280cc07f68014bd4024d55a740374b349.1725206584.git.me@ttaylorr.com>
On Sun, Sep 01, 2024 at 12:03:32PM -0400, Taylor Blau wrote:
Show 37 quoted lines
> 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.

I of course wish that we just moved on and switched the default to SHA256, which should provide similar speedups. But that of course wouldn't help all the projects out there that will use SHA1 for the next couple decades.

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.

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?

Patrick
Previous: Taylor BlauNext: brian m. carlson
Message 18 of 99 in “hash.h: support choosing a separate SHA-1 for non-cryptographic uses”
  1. 0/4 hash.h: support choosing a separate SHA-1 for non-cryptographic usesTaylor Blau, Sep 1, 2024
  2. 1/4 sha1: do not redefine `platform_SHA_CTX` and friendsTaylor Blau, Sep 1, 2024
  3. Patrick SteinhardtSep 2, 2024
  4. Taylor BlauSep 3, 2024
  5. 2/4 hash.h: scaffolding for _fast hashing variantsTaylor Blau, Sep 1, 2024
  6. Patrick SteinhardtSep 2, 2024
  7. Junio C HamanoSep 3, 2024
  8. Taylor BlauSep 3, 2024
  9. Junio C HamanoSep 3, 2024
  10. Taylor BlauSep 3, 2024
  11. Patrick SteinhardtSep 4, 2024
  12. Junio C HamanoSep 4, 2024
  13. Taylor BlauSep 3, 2024
  14. 3/4 Makefile: allow specifying a SHA-1 for non-cryptographic usesTaylor Blau, Sep 1, 2024
  15. Patrick SteinhardtSep 2, 2024
  16. Taylor BlauSep 3, 2024
  17. 4/4 csum-file.c: use fast SHA-1 implementation when availableTaylor Blau, Sep 1, 2024
  18. Patrick SteinhardtSep 2, 2024
  19. brian m. carlsonSep 3, 2024
  20. Taylor BlauSep 3, 2024
  21. Junio C HamanoSep 2, 2024
  22. Taylor BlauSep 3, 2024
  23. Junio C HamanoSep 3, 2024
  24. brian m. carlsonSep 2, 2024
  25. Taylor BlauSep 3, 2024
  26. Junio C HamanoSep 3, 2024
  27. brian m. carlsonSep 4, 2024
  28. Jeff KingSep 5, 2024
  29. Junio C HamanoSep 5, 2024
  30. Taylor BlauSep 5, 2024
  31. Junio C HamanoSep 5, 2024
  32. Taylor BlauSep 5, 2024
  33. Taylor BlauSep 5, 2024
  34. Taylor BlauSep 5, 2024
  35. Jeff KingSep 5, 2024
  36. Junio C HamanoSep 5, 2024
  37. 0/4 hash.h: support choosing a separate SHA-1 for non-cryptographic usesTaylor Blau, Sep 5, 2024
  38. 1/4 sha1: do not redefine `platform_SHA_CTX` and friendsTaylor Blau, Sep 5, 2024
  39. 2/4 hash.h: scaffolding for _fast hashing variantsTaylor Blau, Sep 5, 2024
  40. 3/4 Makefile: allow specifying a SHA-1 for non-cryptographic usesTaylor Blau, Sep 5, 2024
  41. 4/4 csum-file.c: use fast SHA-1 implementation when availableTaylor Blau, Sep 5, 2024
  42. 0/9 hash.h: support choosing a separate SHA-1 for non-cryptographic usesTaylor Blau, Sep 6, 2024
  43. 1/9 finalize_object_file(): check for name collision before renamingTaylor Blau, Sep 6, 2024
  44. 2/9 finalize_object_file(): refactor unlink_or_warn() placementTaylor Blau, Sep 6, 2024
  45. 3/9 finalize_object_file(): implement collision checkTaylor Blau, Sep 6, 2024
  46. Junio C HamanoSep 6, 2024
  47. Chris TorekSep 6, 2024
  48. Jeff KingSep 10, 2024
  49. Junio C HamanoSep 10, 2024
  50. Patrick SteinhardtSep 16, 2024
  51. Taylor BlauSep 16, 2024
  52. Taylor BlauSep 16, 2024
  53. Junio C HamanoSep 17, 2024
  54. 4/9 pack-objects: use finalize_object_file() to rename pack/idx/etcTaylor Blau, Sep 6, 2024
  55. 5/9 i5500-git-daemon.sh: use compile-able version of Git without OpenSSLTaylor Blau, Sep 6, 2024
  56. Jeff KingSep 11, 2024
  57. Jeff KingSep 11, 2024
  58. Junio C HamanoSep 12, 2024
  59. Junio C HamanoSep 11, 2024
  60. Jeff KingSep 11, 2024
  61. 6/9 sha1: do not redefine `platform_SHA_CTX` and friendsTaylor Blau, Sep 6, 2024
  62. 7/9 hash.h: scaffolding for _fast hashing variantsTaylor Blau, Sep 6, 2024
  63. 8/9 Makefile: allow specifying a SHA-1 for non-cryptographic usesTaylor Blau, Sep 6, 2024
  64. 9/9 csum-file.c: use fast SHA-1 implementation when availableTaylor Blau, Sep 6, 2024
  65. Junio C HamanoSep 6, 2024
  66. 0/8 hash.h: support choosing a separate SHA-1 for non-cryptographic usesTaylor Blau, Sep 24, 2024
  67. 1/8 finalize_object_file(): check for name collision before renamingTaylor Blau, Sep 24, 2024
  68. Junio C HamanoSep 25, 2024
  69. 2/8 finalize_object_file(): refactor unlink_or_warn() placementTaylor Blau, Sep 24, 2024
  70. 3/8 finalize_object_file(): implement collision checkTaylor Blau, Sep 24, 2024
  71. Jeff KingSep 24, 2024
  72. Taylor BlauSep 24, 2024
  73. Jeff KingSep 24, 2024
  74. Taylor BlauSep 25, 2024
  75. Junio C HamanoSep 24, 2024
  76. Taylor BlauSep 24, 2024
  77. 4/8 pack-objects: use finalize_object_file() to rename pack/idx/etcTaylor Blau, Sep 24, 2024
  78. Junio C HamanoSep 24, 2024
  79. 5/8 sha1: do not redefine `platform_SHA_CTX` and friendsTaylor Blau, Sep 24, 2024
  80. 6/8 hash.h: scaffolding for _unsafe hashing variantsTaylor Blau, Sep 24, 2024
  81. 7/8 Makefile: allow specifying a SHA-1 for non-cryptographic usesTaylor Blau, Sep 24, 2024
  82. 8/8 csum-file.c: use unsafe SHA-1 implementation when availableTaylor Blau, Sep 24, 2024
  83. Jeff KingSep 24, 2024
  84. Elijah NewrenSep 25, 2024
  85. Junio C HamanoSep 25, 2024
  86. Taylor BlauSep 25, 2024
  87. Taylor BlauSep 25, 2024
  88. 0/8 hash.h: support choosing a separate SHA-1 for non-cryptographic usesTaylor Blau, Sep 26, 2024
  89. 1/8 finalize_object_file(): check for name collision before renamingTaylor Blau, Sep 26, 2024
  90. 2/8 finalize_object_file(): refactor unlink_or_warn() placementTaylor Blau, Sep 26, 2024
  91. 3/8 finalize_object_file(): implement collision checkTaylor Blau, Sep 26, 2024
  92. 4/8 pack-objects: use finalize_object_file() to rename pack/idx/etcTaylor Blau, Sep 26, 2024
  93. 5/8 sha1: do not redefine `platform_SHA_CTX` and friendsTaylor Blau, Sep 26, 2024
  94. 6/8 hash.h: scaffolding for _unsafe hashing variantsTaylor Blau, Sep 26, 2024
  95. 7/8 Makefile: allow specifying a SHA-1 for non-cryptographic usesTaylor Blau, Sep 26, 2024
  96. 8/8 csum-file.c: use unsafe SHA-1 implementation when availableTaylor Blau, Sep 26, 2024
  97. Elijah NewrenSep 26, 2024
  98. Junio C HamanoSep 27, 2024
  99. Jeff KingSep 27, 2024

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.