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

Re: [PATCH v3 00/17] bloom: changed-path Bloom filters v2 (& sundries)

From
Patrick Steinhardt <ps@pks.im>
Date
Oct 17, 2023, 08:45 UTC
Message-ID
<ZS5JsDKk8RioQfOA@tanuki>
In-Reply-To
<cover.1696969994.git.me@ttaylorr.com>
On Tue, Oct 10, 2023 at 04:33:17PM -0400, Taylor Blau wrote:
Show 23 quoted lines
> (Rebased onto the tip of 'master', which is 3a06386e31 (The fifteenth
> batch, 2023-10-04), at the time of writing).
> 
> This series is a reroll of the combined efforts of [1] and [2] to
> introduce the v2 changed-path Bloom filters, which fixes a bug in our
> existing implementation of murmur3 paths with non-ASCII characters (when
> the "char" type is signed).
> 
> In large part, this is the same as the previous round. But this round
> includes some extra bits that address issues pointed out by SZEDER
> Gábor, which are:
> 
>   - not reading Bloom filters for root commits
>   - corrupting Bloom filter reads by tweaking the filter settings
>     between layers.
> 
> These issues were discussed in (among other places) [3], and [4],
> respectively.
> 
> Thanks to Jonathan, Peff, and SZEDER who have helped a great deal in
> assembling these patches. As usual, a range-diff is included below.
> Thanks in advance for your
> review!

As this patch series has been sitting around without reviews for a week I've tried my best to give it a go. Note though that this area is mostly outside of my own comfort zone, so some of the questions and suggestions might ultimately not apply.

Patrick
Show 187 quoted lines
> [1]: https://lore.kernel.org/git/cover.1684790529.git.jonathantanmy@google.com/
> [2]: https://lore.kernel.org/git/cover.1691426160.git.me@ttaylorr.com/
> [3]: https://public-inbox.org/git/20201015132147.GB24954@szeder.dev/
> [4]: https://lore.kernel.org/git/20230830200218.GA5147@szeder.dev/
> 
> Jonathan Tan (4):
>   gitformat-commit-graph: describe version 2 of BDAT
>   t4216: test changed path filters with high bit paths
>   repo-settings: introduce commitgraph.changedPathsVersion
>   commit-graph: new filter ver. that fixes murmur3
> 
> Taylor Blau (13):
>   t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`
>   revision.c: consult Bloom filters for root commits
>   commit-graph: ensure Bloom filters are read with consistent settings
>   t/helper/test-read-graph.c: extract `dump_graph_info()`
>   bloom.h: make `load_bloom_filter_from_graph()` public
>   t/helper/test-read-graph: implement `bloom-filters` mode
>   bloom: annotate filters with hash version
>   bloom: prepare to discard incompatible Bloom filters
>   commit-graph.c: unconditionally load Bloom filters
>   commit-graph: drop unnecessary `graph_read_bloom_data_context`
>   object.h: fix mis-aligned flag bits table
>   commit-graph: reuse existing Bloom filters where possible
>   bloom: introduce `deinit_bloom_filters()`
> 
>  Documentation/config/commitgraph.txt     |  26 ++-
>  Documentation/gitformat-commit-graph.txt |   9 +-
>  bloom.c                                  | 208 ++++++++++++++++-
>  bloom.h                                  |  38 +++-
>  commit-graph.c                           |  61 ++++-
>  object.h                                 |   3 +-
>  oss-fuzz/fuzz-commit-graph.c             |   2 +-
>  repo-settings.c                          |   6 +-
>  repository.h                             |   2 +-
>  revision.c                               |  26 ++-
>  t/helper/test-bloom.c                    |   9 +-
>  t/helper/test-read-graph.c               |  67 ++++--
>  t/t0095-bloom.sh                         |   8 +
>  t/t4216-log-bloom.sh                     | 272 ++++++++++++++++++++++-
>  14 files changed, 682 insertions(+), 55 deletions(-)
> 
> Range-diff against v2:
> 10:  002a06d1e9 !  1:  fe671d616c t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`
>     @@ Commit message
>          indicating that no filters were used.
>      
>          Signed-off-by: Taylor Blau <me@ttaylorr.com>
>     -    Signed-off-by: Junio C Hamano <gitster@pobox.com>
>     -    Signed-off-by: Taylor Blau <me@ttaylorr.com>
>      
>       ## t/t4216-log-bloom.sh ##
>      @@ t/t4216-log-bloom.sh: test_bloom_filters_used () {
>  -:  ---------- >  2:  7d0fa93543 revision.c: consult Bloom filters for root commits
>  -:  ---------- >  3:  2ecc0a2d58 commit-graph: ensure Bloom filters are read with consistent settings
>  1:  5fa681b58e !  4:  17703ed89a gitformat-commit-graph: describe version 2 of BDAT
>     @@ Commit message
>          Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
>          Signed-off-by: Junio C Hamano <gitster@pobox.com>
>          Signed-off-by: Taylor Blau <me@ttaylorr.com>
>     -    Signed-off-by: Junio C Hamano <gitster@pobox.com>
>     -    Signed-off-by: Taylor Blau <me@ttaylorr.com>
>      
>       ## Documentation/gitformat-commit-graph.txt ##
>      @@ Documentation/gitformat-commit-graph.txt: All multi-byte numbers are in network byte order.
>  2:  623d840575 !  5:  94552abf45 t/helper/test-read-graph.c: extract `dump_graph_info()`
>     @@ Commit message
>          Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
>          Signed-off-by: Junio C Hamano <gitster@pobox.com>
>          Signed-off-by: Taylor Blau <me@ttaylorr.com>
>     -    Signed-off-by: Junio C Hamano <gitster@pobox.com>
>     -    Signed-off-by: Taylor Blau <me@ttaylorr.com>
>      
>       ## t/helper/test-read-graph.c ##
>      @@
>  3:  bc9d77ae60 !  6:  3d81efa27b bloom.h: make `load_bloom_filter_from_graph()` public
>     @@ Commit message
>          Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
>          Signed-off-by: Junio C Hamano <gitster@pobox.com>
>          Signed-off-by: Taylor Blau <me@ttaylorr.com>
>     -    Signed-off-by: Junio C Hamano <gitster@pobox.com>
>     -    Signed-off-by: Taylor Blau <me@ttaylorr.com>
>      
>       ## bloom.c ##
>      @@ bloom.c: static inline unsigned char get_bitmask(uint32_t pos)
>  4:  ac7008aed3 !  7:  d23cd89037 t/helper/test-read-graph: implement `bloom-filters` mode
>     @@ Commit message
>          Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
>          Signed-off-by: Junio C Hamano <gitster@pobox.com>
>          Signed-off-by: Taylor Blau <me@ttaylorr.com>
>     -    Signed-off-by: Junio C Hamano <gitster@pobox.com>
>     -    Signed-off-by: Taylor Blau <me@ttaylorr.com>
>      
>       ## t/helper/test-read-graph.c ##
>      @@ t/helper/test-read-graph.c: static void dump_graph_info(struct commit_graph *graph)
>     @@ t/helper/test-read-graph.c: int cmd__read_graph(int argc UNUSED, const char **ar
>      -	return 0;
>      +	return ret;
>       }
>     ++
>     ++
>  5:  71755ba856 !  8:  cba766f224 t4216: test changed path filters with high bit paths
>     @@ Commit message
>          Signed-off-by: Taylor Blau <me@ttaylorr.com>
>      
>       ## t/t4216-log-bloom.sh ##
>     -@@ t/t4216-log-bloom.sh: test_expect_success 'Bloom generation backfills empty commits' '
>     - 	)
>     +@@ t/t4216-log-bloom.sh: test_expect_success 'merge graph layers with incompatible Bloom settings' '
>     + 	! grep "disabling Bloom filters" err
>       '
>       
>      +get_first_changed_path_filter () {
>  6:  9768d92c0f !  9:  a08a961f41 repo-settings: introduce commitgraph.changedPathsVersion
>     @@ Commit message
>          Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
>          Signed-off-by: Junio C Hamano <gitster@pobox.com>
>          Signed-off-by: Taylor Blau <me@ttaylorr.com>
>     -    Signed-off-by: Junio C Hamano <gitster@pobox.com>
>     -    Signed-off-by: Taylor Blau <me@ttaylorr.com>
>      
>       ## Documentation/config/commitgraph.txt ##
>      @@ Documentation/config/commitgraph.txt: commitGraph.maxNewFilters::
>  7:  f911b4bfab = 10:  61d44519a5 commit-graph: new filter ver. that fixes murmur3
>  8:  35009900df ! 11:  a8c10f8de8 bloom: annotate filters with hash version
>     @@ Commit message
>          Bloom filter.
>      
>          Signed-off-by: Taylor Blau <me@ttaylorr.com>
>     -    Signed-off-by: Junio C Hamano <gitster@pobox.com>
>     -    Signed-off-by: Taylor Blau <me@ttaylorr.com>
>      
>       ## bloom.c ##
>      @@ bloom.c: int load_bloom_filter_from_graph(struct commit_graph *g,
>  9:  138bc16905 ! 12:  2ba10a4b4b bloom: prepare to discard incompatible Bloom filters
>     @@ Commit message
>          `get_or_compute_bloom_filter()`.
>      
>          Signed-off-by: Taylor Blau <me@ttaylorr.com>
>     -    Signed-off-by: Junio C Hamano <gitster@pobox.com>
>     -    Signed-off-by: Taylor Blau <me@ttaylorr.com>
>      
>       ## bloom.c ##
>      @@ bloom.c: static void init_truncated_large_filter(struct bloom_filter *filter,
> 11:  2437e62813 ! 13:  09d8669c3a commit-graph.c: unconditionally load Bloom filters
>     @@ Commit message
>          either "1" or "2".
>      
>          Signed-off-by: Taylor Blau <me@ttaylorr.com>
>     -    Signed-off-by: Junio C Hamano <gitster@pobox.com>
>     -    Signed-off-by: Taylor Blau <me@ttaylorr.com>
>      
>       ## commit-graph.c ##
>      @@ commit-graph.c: static int graph_read_bloom_data(const unsigned char *chunk_start,
> 12:  fe8fb2f5fe ! 14:  0d4f9dc4ee commit-graph: drop unnecessary `graph_read_bloom_data_context`
>     @@ Commit message
>      
>          Noticed-by: Jonathan Tan <jonathantanmy@google.com>
>          Signed-off-by: Taylor Blau <me@ttaylorr.com>
>     -    Signed-off-by: Junio C Hamano <gitster@pobox.com>
>     -    Signed-off-by: Taylor Blau <me@ttaylorr.com>
>      
>       ## commit-graph.c ##
>      @@ commit-graph.c: static int graph_read_oid_lookup(const unsigned char *chunk_start,
> 13:  825af91e11 ! 15:  1f7f27bc47 object.h: fix mis-aligned flag bits table
>     @@ Commit message
>          Bit position 23 is one column too far to the left.
>      
>          Signed-off-by: Taylor Blau <me@ttaylorr.com>
>     -    Signed-off-by: Junio C Hamano <gitster@pobox.com>
>     -    Signed-off-by: Taylor Blau <me@ttaylorr.com>
>      
>       ## object.h ##
>      @@ object.h: void object_array_init(struct object_array *array);
> 14:  593b317192 ! 16:  abbef95ae8 commit-graph: reuse existing Bloom filters where possible
>     @@ Commit message
>            commits by their generation number.
>      
>          Signed-off-by: Taylor Blau <me@ttaylorr.com>
>     -    Signed-off-by: Junio C Hamano <gitster@pobox.com>
>     -    Signed-off-by: Taylor Blau <me@ttaylorr.com>
>      
>       ## bloom.c ##
>      @@
> 15:  8bf2c9cf98 = 17:  ca362408d5 bloom: introduce `deinit_bloom_filters()`
> -- 
> 2.42.0.342.g8bb3a896ee
Previous: Taylor BlauNext: Taylor Blau
Message 75 of 76 in “bloom: changed-path Bloom filters v2”
  1. 00/15 bloom: changed-path Bloom filters v2Taylor Blau, Aug 21, 2023
  2. 01/15 gitformat-commit-graph: describe version 2 of BDATTaylor Blau, Aug 21, 2023
  3. 02/15 t/helper/test-read-graph.c: extract `dump_graph_info()`Taylor Blau, Aug 21, 2023
  4. 03/15 bloom.h: make `load_bloom_filter_from_graph()` publicTaylor Blau, Aug 21, 2023
  5. 04/15 t/helper/test-read-graph: implement `bloom-filters` modeTaylor Blau, Aug 21, 2023
  6. 05/15 t4216: test changed path filters with high bit pathsTaylor Blau, Aug 21, 2023
  7. 06/15 repo-settings: introduce commitgraph.changedPathsVersionTaylor Blau, Aug 21, 2023
  8. 07/15 commit-graph: new filter ver. that fixes murmur3Taylor Blau, Aug 21, 2023
  9. SZEDER GáborAug 26, 2023
  10. Jonathan TanAug 29, 2023
  11. SZEDER GáborAug 30, 2023
  12. Jonathan TanSep 1, 2023
  13. Taylor BlauSep 25, 2023
  14. SZEDER GáborOct 8, 2023
  15. Taylor BlauOct 9, 2023
  16. Taylor BlauOct 9, 2023
  17. Junio C HamanoOct 9, 2023
  18. Taylor BlauOct 10, 2023
  19. 08/15 bloom: annotate filters with hash versionTaylor Blau, Aug 21, 2023
  20. 09/15 bloom: prepare to discard incompatible Bloom filtersTaylor Blau, Aug 21, 2023
  21. 10/15 t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`Taylor Blau, Aug 21, 2023
  22. 11/15 commit-graph.c: unconditionally load Bloom filtersTaylor Blau, Aug 21, 2023
  23. 12/15 commit-graph: drop unnecessary `graph_read_bloom_data_context`Taylor Blau, Aug 21, 2023
  24. 13/15 object.h: fix mis-aligned flag bits tableTaylor Blau, Aug 21, 2023
  25. 14/15 commit-graph: reuse existing Bloom filters where possibleTaylor Blau, Aug 21, 2023
  26. 15/15 bloom: introduce `deinit_bloom_filters()`Taylor Blau, Aug 21, 2023
  27. Jonathan TanAug 24, 2023
  28. Jonathan TanAug 25, 2023
  29. Jonathan TanAug 29, 2023
  30. Junio C HamanoAug 29, 2023
  31. 00/15 bloom: changed-path Bloom filters v2Jonathan Tan, Aug 30, 2023
  32. 13/15 object.h: fix mis-aligned flag bits tableJonathan Tan, Aug 30, 2023
  33. 06/15 repo-settings: introduce commitgraph.changedPathsVersionJonathan Tan, Aug 30, 2023
  34. 04/15 t/helper/test-read-graph: implement `bloom-filters` modeJonathan Tan, Aug 30, 2023
  35. 08/15 bloom: annotate filters with hash versionJonathan Tan, Aug 30, 2023
  36. 01/15 gitformat-commit-graph: describe version 2 of BDATJonathan Tan, Aug 30, 2023
  37. 11/15 commit-graph.c: unconditionally load Bloom filtersJonathan Tan, Aug 30, 2023
  38. 10/15 t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`Jonathan Tan, Aug 30, 2023
  39. 09/15 bloom: prepare to discard incompatible Bloom filtersJonathan Tan, Aug 30, 2023
  40. 12/15 commit-graph: drop unnecessary `graph_read_bloom_data_context`Jonathan Tan, Aug 30, 2023
  41. 07/15 commit-graph: new filter ver. that fixes murmur3Jonathan Tan, Aug 30, 2023
  42. 02/15 t/helper/test-read-graph.c: extract `dump_graph_info()`Jonathan Tan, Aug 30, 2023
  43. 05/15 t4216: test changed path filters with high bit pathsJonathan Tan, Aug 30, 2023
  44. 14/15 commit-graph: reuse existing Bloom filters where possibleJonathan Tan, Aug 30, 2023
  45. 03/15 bloom.h: make `load_bloom_filter_from_graph()` publicJonathan Tan, Aug 30, 2023
  46. 15/15 bloom: introduce `deinit_bloom_filters()`Jonathan Tan, Aug 30, 2023
  47. Junio C HamanoAug 30, 2023
  48. 00/17 bloom: changed-path Bloom filters v2 (& sundries)Taylor Blau, Oct 10, 2023
  49. 01/17 t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`Taylor Blau, Oct 10, 2023
  50. 02/17 revision.c: consult Bloom filters for root commitsTaylor Blau, Oct 10, 2023
  51. 04/17 gitformat-commit-graph: describe version 2 of BDATTaylor Blau, Oct 10, 2023
  52. 05/17 t/helper/test-read-graph.c: extract `dump_graph_info()`Taylor Blau, Oct 10, 2023
  53. Patrick SteinhardtOct 17, 2023
  54. Taylor BlauOct 18, 2023
  55. Junio C HamanoOct 18, 2023
  56. 03/17 commit-graph: ensure Bloom filters are read with consistent settingsTaylor Blau, Oct 10, 2023
  57. Patrick SteinhardtOct 17, 2023
  58. 06/17 bloom.h: make `load_bloom_filter_from_graph()` publicTaylor Blau, Oct 10, 2023
  59. 07/17 t/helper/test-read-graph: implement `bloom-filters` modeTaylor Blau, Oct 10, 2023
  60. 09/17 repo-settings: introduce commitgraph.changedPathsVersionTaylor Blau, Oct 10, 2023
  61. 15/17 object.h: fix mis-aligned flag bits tableTaylor Blau, Oct 10, 2023
  62. 12/17 bloom: prepare to discard incompatible Bloom filtersTaylor Blau, Oct 10, 2023
  63. 13/17 commit-graph.c: unconditionally load Bloom filtersTaylor Blau, Oct 10, 2023
  64. Patrick SteinhardtOct 17, 2023
  65. 11/17 bloom: annotate filters with hash versionTaylor Blau, Oct 10, 2023
  66. 14/17 commit-graph: drop unnecessary `graph_read_bloom_data_context`Taylor Blau, Oct 10, 2023
  67. 10/17 commit-graph: new filter ver. that fixes murmur3Taylor Blau, Oct 10, 2023
  68. Patrick SteinhardtOct 17, 2023
  69. Taylor BlauOct 18, 2023
  70. 08/17 t4216: test changed path filters with high bit pathsTaylor Blau, Oct 10, 2023
  71. Patrick SteinhardtOct 17, 2023
  72. Taylor BlauOct 18, 2023
  73. 16/17 commit-graph: reuse existing Bloom filters where possibleTaylor Blau, Oct 10, 2023
  74. 17/17 bloom: introduce `deinit_bloom_filters()`Taylor Blau, Oct 10, 2023
  75. Patrick SteinhardtOct 17, 2023
  76. Taylor BlauOct 18, 2023

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.