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

From: Patrick Steinhardt <[email-masked]>
Date: Tue, 17 Oct 2023 10:45:36 +0200

On Tue, Oct 10, 2023 at 04:33:17PM -0400, Taylor Blau wrote:
> (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

> [1]: https://lore.kernel.org/git/[email-masked]/
> [2]: https://lore.kernel.org/git/[email-masked]/
> [3]: https://public-inbox.org/git/[email-masked]/
> [4]: https://lore.kernel.org/git/[email-masked]/
> 
> 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 <[email-masked]>
>     -    Signed-off-by: Junio C Hamano <[email-masked]>
>     -    Signed-off-by: Taylor Blau <[email-masked]>
>      
>       ## 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 <[email-masked]>
>          Signed-off-by: Junio C Hamano <[email-masked]>
>          Signed-off-by: Taylor Blau <[email-masked]>
>     -    Signed-off-by: Junio C Hamano <[email-masked]>
>     -    Signed-off-by: Taylor Blau <[email-masked]>
>      
>       ## 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 <[email-masked]>
>          Signed-off-by: Junio C Hamano <[email-masked]>
>          Signed-off-by: Taylor Blau <[email-masked]>
>     -    Signed-off-by: Junio C Hamano <[email-masked]>
>     -    Signed-off-by: Taylor Blau <[email-masked]>
>      
>       ## 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 <[email-masked]>
>          Signed-off-by: Junio C Hamano <[email-masked]>
>          Signed-off-by: Taylor Blau <[email-masked]>
>     -    Signed-off-by: Junio C Hamano <[email-masked]>
>     -    Signed-off-by: Taylor Blau <[email-masked]>
>      
>       ## 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 <[email-masked]>
>          Signed-off-by: Junio C Hamano <[email-masked]>
>          Signed-off-by: Taylor Blau <[email-masked]>
>     -    Signed-off-by: Junio C Hamano <[email-masked]>
>     -    Signed-off-by: Taylor Blau <[email-masked]>
>      
>       ## 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 <[email-masked]>
>      
>       ## 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 <[email-masked]>
>          Signed-off-by: Junio C Hamano <[email-masked]>
>          Signed-off-by: Taylor Blau <[email-masked]>
>     -    Signed-off-by: Junio C Hamano <[email-masked]>
>     -    Signed-off-by: Taylor Blau <[email-masked]>
>      
>       ## 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 <[email-masked]>
>     -    Signed-off-by: Junio C Hamano <[email-masked]>
>     -    Signed-off-by: Taylor Blau <[email-masked]>
>      
>       ## 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 <[email-masked]>
>     -    Signed-off-by: Junio C Hamano <[email-masked]>
>     -    Signed-off-by: Taylor Blau <[email-masked]>
>      
>       ## 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 <[email-masked]>
>     -    Signed-off-by: Junio C Hamano <[email-masked]>
>     -    Signed-off-by: Taylor Blau <[email-masked]>
>      
>       ## 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 <[email-masked]>
>          Signed-off-by: Taylor Blau <[email-masked]>
>     -    Signed-off-by: Junio C Hamano <[email-masked]>
>     -    Signed-off-by: Taylor Blau <[email-masked]>
>      
>       ## 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 <[email-masked]>
>     -    Signed-off-by: Junio C Hamano <[email-masked]>
>     -    Signed-off-by: Taylor Blau <[email-masked]>
>      
>       ## 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 <[email-masked]>
>     -    Signed-off-by: Junio C Hamano <[email-masked]>
>     -    Signed-off-by: Taylor Blau <[email-masked]>
>      
>       ## bloom.c ##
>      @@
> 15:  8bf2c9cf98 = 17:  ca362408d5 bloom: introduce `deinit_bloom_filters()`
> -- 
> 2.42.0.342.g8bb3a896ee