| Message ID | cover.1696969994.git.me@ttaylorr.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | bloom: changed-path Bloom filters v2 (& sundries) | expand |
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/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
On Tue, Oct 17, 2023 at 10:45:36AM +0200, Patrick Steinhardt wrote: > > 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. Thanks for giving it a look! I generated a few small tweaks on top of what I already had here based on your review, so I'll send a reroll shortly. Thanks, Taylor
(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! [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()`