* Re: [PATCH 1/9] reftable: introduce macros to grow arrays
From: Junio C Hamano @ 2024-01-31 20:35 UTC (permalink / raw)
To: Patrick Steinhardt; +Cc: git
In-Reply-To: <0597e6944a1a65720d050f47bc82766d5bcf860b.1706687982.git.ps@pks.im>
Patrick Steinhardt <ps@pks.im> writes:
> patterns in the reftable library. For In most cases, we end up only having a
> single item in the array, so the initial capacity that our global growth
> factor uses (which is 24), significantly overallocates in a lot of code
> paths.
You need to know not just that you very often initially have only
one but you rarely grow it beyond 3, or something like that to
explain "significantly overallocates", though.
> This effect is indeed measurable:
And measuring is very good, but I somehow expected that you would
measure not the time (if you often under-allocate and end up
reallocating too many times, it might consume more time, though) but
the peak memory usage. I cannot quite tell what to think of that 2%
time difference.
> Convert the reftable library to use these new macros.
In any case, the conversion shortens the code and is a good thing.
I wish we had a way to tell these macros that we are actually using
the same single allocator (which we are doing in our code when
linking the reftable thing to us anyway), which would have made this
even simpler because you did not have to introduce separate macros..
> Signed-off-by: Patrick Steinhardt <ps@pks.im>
> ---
> reftable/basics.c | 8 ++------
> reftable/basics.h | 11 +++++++++++
> reftable/block.c | 7 +------
> reftable/merged_test.c | 20 ++++++--------------
> reftable/pq.c | 8 ++------
> reftable/stack.c | 29 ++++++++++++-----------------
> reftable/writer.c | 14 ++------------
> 7 files changed, 36 insertions(+), 61 deletions(-)
>
> diff --git a/reftable/basics.c b/reftable/basics.c
> index f761e48028..af9004cec2 100644
> --- a/reftable/basics.c
> +++ b/reftable/basics.c
> @@ -89,17 +89,13 @@ void parse_names(char *buf, int size, char ***namesp)
> next = end;
> }
> if (p < next) {
> - if (names_len == names_cap) {
> - names_cap = 2 * names_cap + 1;
> - names = reftable_realloc(
> - names, names_cap * sizeof(*names));
> - }
> + REFTABLE_ALLOC_GROW(names, names_len + 1, names_cap);
> names[names_len++] = xstrdup(p);
> }
> p = next + 1;
> }
>
> - names = reftable_realloc(names, (names_len + 1) * sizeof(*names));
> + REFTABLE_REALLOC_ARRAY(names, names_len + 1);
> names[names_len] = NULL;
> *namesp = names;
> }
> diff --git a/reftable/basics.h b/reftable/basics.h
> index 096b36862b..2f855cd724 100644
> --- a/reftable/basics.h
> +++ b/reftable/basics.h
> @@ -53,6 +53,17 @@ void *reftable_realloc(void *p, size_t sz);
> void reftable_free(void *p);
> void *reftable_calloc(size_t sz);
>
> +#define REFTABLE_REALLOC_ARRAY(x, alloc) (x) = reftable_realloc((x), st_mult(sizeof(*(x)), (alloc)))
> +#define REFTABLE_ALLOC_GROW(x, nr, alloc) \
> + do { \
> + if ((nr) > alloc) { \
> + alloc = 2 * (alloc) + 1; \
> + if (alloc < (nr)) \
> + alloc = (nr); \
> + REFTABLE_REALLOC_ARRAY(x, alloc); \
> + } \
> + } while (0)
> +
> /* Find the longest shared prefix size of `a` and `b` */
> struct strbuf;
> int common_prefix_size(struct strbuf *a, struct strbuf *b);
> diff --git a/reftable/block.c b/reftable/block.c
> index 1df3d8a0f0..6952d0facf 100644
> --- a/reftable/block.c
> +++ b/reftable/block.c
> @@ -51,12 +51,7 @@ static int block_writer_register_restart(struct block_writer *w, int n,
> if (2 + 3 * rlen + n > w->block_size - w->next)
> return -1;
> if (is_restart) {
> - if (w->restart_len == w->restart_cap) {
> - w->restart_cap = w->restart_cap * 2 + 1;
> - w->restarts = reftable_realloc(
> - w->restarts, sizeof(uint32_t) * w->restart_cap);
> - }
> -
> + REFTABLE_ALLOC_GROW(w->restarts, w->restart_len + 1, w->restart_cap);
> w->restarts[w->restart_len++] = w->next;
> }
>
> diff --git a/reftable/merged_test.c b/reftable/merged_test.c
> index 46908f738f..e05351e035 100644
> --- a/reftable/merged_test.c
> +++ b/reftable/merged_test.c
> @@ -231,14 +231,10 @@ static void test_merged(void)
> while (len < 100) { /* cap loops/recursion. */
> struct reftable_ref_record ref = { NULL };
> int err = reftable_iterator_next_ref(&it, &ref);
> - if (err > 0) {
> + if (err > 0)
> break;
> - }
> - if (len == cap) {
> - cap = 2 * cap + 1;
> - out = reftable_realloc(
> - out, sizeof(struct reftable_ref_record) * cap);
> - }
> +
> + REFTABLE_ALLOC_GROW(out, len + 1, cap);
> out[len++] = ref;
> }
> reftable_iterator_destroy(&it);
> @@ -368,14 +364,10 @@ static void test_merged_logs(void)
> while (len < 100) { /* cap loops/recursion. */
> struct reftable_log_record log = { NULL };
> int err = reftable_iterator_next_log(&it, &log);
> - if (err > 0) {
> + if (err > 0)
> break;
> - }
> - if (len == cap) {
> - cap = 2 * cap + 1;
> - out = reftable_realloc(
> - out, sizeof(struct reftable_log_record) * cap);
> - }
> +
> + REFTABLE_ALLOC_GROW(out, len + 1, cap);
> out[len++] = log;
> }
> reftable_iterator_destroy(&it);
> diff --git a/reftable/pq.c b/reftable/pq.c
> index dcefeb793a..2461daf5ff 100644
> --- a/reftable/pq.c
> +++ b/reftable/pq.c
> @@ -75,13 +75,9 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry
> {
> int i = 0;
>
> - if (pq->len == pq->cap) {
> - pq->cap = 2 * pq->cap + 1;
> - pq->heap = reftable_realloc(pq->heap,
> - pq->cap * sizeof(struct pq_entry));
> - }
> -
> + REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
> pq->heap[pq->len++] = *e;
> +
> i = pq->len - 1;
> while (i > 0) {
> int j = (i - 1) / 2;
> diff --git a/reftable/stack.c b/reftable/stack.c
> index bf3869ce70..1dfab99e96 100644
> --- a/reftable/stack.c
> +++ b/reftable/stack.c
> @@ -551,7 +551,7 @@ struct reftable_addition {
> struct reftable_stack *stack;
>
> char **new_tables;
> - int new_tables_len;
> + size_t new_tables_len, new_tables_cap;
> uint64_t next_update_index;
> };
>
> @@ -602,8 +602,9 @@ static int reftable_stack_init_addition(struct reftable_addition *add,
>
> static void reftable_addition_close(struct reftable_addition *add)
> {
> - int i = 0;
> struct strbuf nm = STRBUF_INIT;
> + size_t i;
> +
> for (i = 0; i < add->new_tables_len; i++) {
> stack_filename(&nm, add->stack, add->new_tables[i]);
> unlink(nm.buf);
> @@ -613,6 +614,7 @@ static void reftable_addition_close(struct reftable_addition *add)
> reftable_free(add->new_tables);
> add->new_tables = NULL;
> add->new_tables_len = 0;
> + add->new_tables_cap = 0;
>
> delete_tempfile(&add->lock_file);
> strbuf_release(&nm);
> @@ -631,8 +633,8 @@ int reftable_addition_commit(struct reftable_addition *add)
> {
> struct strbuf table_list = STRBUF_INIT;
> int lock_file_fd = get_tempfile_fd(add->lock_file);
> - int i = 0;
> int err = 0;
> + size_t i;
>
> if (add->new_tables_len == 0)
> goto done;
> @@ -660,12 +662,12 @@ int reftable_addition_commit(struct reftable_addition *add)
> }
>
> /* success, no more state to clean up. */
> - for (i = 0; i < add->new_tables_len; i++) {
> + for (i = 0; i < add->new_tables_len; i++)
> reftable_free(add->new_tables[i]);
> - }
> reftable_free(add->new_tables);
> add->new_tables = NULL;
> add->new_tables_len = 0;
> + add->new_tables_cap = 0;
>
> err = reftable_stack_reload_maybe_reuse(add->stack, 1);
> if (err)
> @@ -792,11 +794,9 @@ int reftable_addition_add(struct reftable_addition *add,
> goto done;
> }
>
> - add->new_tables = reftable_realloc(add->new_tables,
> - sizeof(*add->new_tables) *
> - (add->new_tables_len + 1));
> - add->new_tables[add->new_tables_len] = strbuf_detach(&next_name, NULL);
> - add->new_tables_len++;
> + REFTABLE_ALLOC_GROW(add->new_tables, add->new_tables_len + 1,
> + add->new_tables_cap);
> + add->new_tables[add->new_tables_len++] = strbuf_detach(&next_name, NULL);
> done:
> if (tab_fd > 0) {
> close(tab_fd);
> @@ -1367,17 +1367,12 @@ static int stack_check_addition(struct reftable_stack *st,
> while (1) {
> struct reftable_ref_record ref = { NULL };
> err = reftable_iterator_next_ref(&it, &ref);
> - if (err > 0) {
> + if (err > 0)
> break;
> - }
> if (err < 0)
> goto done;
>
> - if (len >= cap) {
> - cap = 2 * cap + 1;
> - refs = reftable_realloc(refs, cap * sizeof(refs[0]));
> - }
> -
> + REFTABLE_ALLOC_GROW(refs, len + 1, cap);
> refs[len++] = ref;
> }
>
> diff --git a/reftable/writer.c b/reftable/writer.c
> index ee4590e20f..4483bb21c3 100644
> --- a/reftable/writer.c
> +++ b/reftable/writer.c
> @@ -200,12 +200,7 @@ static void writer_index_hash(struct reftable_writer *w, struct strbuf *hash)
> return;
> }
>
> - if (key->offset_len == key->offset_cap) {
> - key->offset_cap = 2 * key->offset_cap + 1;
> - key->offsets = reftable_realloc(
> - key->offsets, sizeof(uint64_t) * key->offset_cap);
> - }
> -
> + REFTABLE_ALLOC_GROW(key->offsets, key->offset_len + 1, key->offset_cap);
> key->offsets[key->offset_len++] = off;
> }
>
> @@ -674,12 +669,7 @@ static int writer_flush_nonempty_block(struct reftable_writer *w)
> if (err < 0)
> return err;
>
> - if (w->index_cap == w->index_len) {
> - w->index_cap = 2 * w->index_cap + 1;
> - w->index = reftable_realloc(
> - w->index,
> - sizeof(struct reftable_index_record) * w->index_cap);
> - }
> + REFTABLE_ALLOC_GROW(w->index, w->index_len + 1, w->index_cap);
>
> ir.offset = w->next;
> strbuf_reset(&ir.last_key);
^ permalink raw reply
* Re: [PATCH v3 03/10] trailer: unify trailer formatting machinery
From: Junio C Hamano @ 2024-01-31 22:16 UTC (permalink / raw)
To: Linus Arver via GitGitGadget
Cc: git, Christian Couder, Emily Shaffer, Josh Steadmon,
Randall S. Becker, Linus Arver
In-Reply-To: <xmqqy1c545y0.fsf@gitster.g>
Junio C Hamano <gitster@pobox.com> writes:
>> + if (opts->unfold)
>> + unfold_value(&val);
>
> So, ... how would this affect an invocation of
>
> $ git interpret-trailers --unfold
>
> which would have set opts.unfold to true in cmd_interpret_trailers()
> and eventually called process_trailers() with it, which eventually
> called print_all(), which conditionally called print_tok_val() but
> never gave the val to unfold_value()?
>
> ... goes and digs a bit more ...
>
> Ahhhh, original process_trailers() did this by calling
> parse_trailers() that munged the value. So its print_all()
> codepath only had to print what has already been munged.
>
> But then in this new code, do we unfold only here? I thought that
> in the new code you moved around, the caller, whose name is now
> interpret_trailers(), still calls parse_trailers() and that calls
> the unfold_value(). So, are we doing redundant work that may merely
> be unneeded (if we are lucky) or could be harmful (if things, other
> than the unfold thing I just noticed, that are done both in
> parse_trailers() and this function are not idempotent)?
I was too confused by the code flow and resorted to tracing what
happens when "git interpret-trailers --unfold" is run in a way
similar to how t7513 does in gdb. Shame shame.
In any case, the updated code does try to call unfold_value() in
format_trailers() on "val" that has already been unfolded in
parse_trailers(). This may not produce an incorrect result if
unfold_value() is truly idempotent (I do not know), but even if it
is correct for its handling of .unfold bit, this episode lowered my
confidence level on the new code significantly, as I do not know
what unintended effects [*] all the other new things done in this
function have, or if none of these unintended effects are
error-free.
> It could be that a bit more preparatory refactoring would clarify.
> I dunno.
Thanks.
[Footnote]
* I am assuming that calling unfold twice on the same value and
relying for its idempotent-ness for correctness was not your
intention.
^ permalink raw reply
* Re: [PATCH v3 0/2] index-pack: fsck honor checks
From: Jonathan Tan @ 2024-01-31 22:30 UTC (permalink / raw)
To: John Cai; +Cc: Jonathan Tan, Junio C Hamano, John Cai via GitGitGadget, git
In-Reply-To: <BE30DB47-1488-40A3-BD0C-804F97DE0C88@gmail.com>
John Cai <johncai86@gmail.com> writes:
> Hi Jonathan,
>
> On 26 Jan 2024, at 17:13, Jonathan Tan wrote:
>
> > Junio C Hamano <gitster@pobox.com> writes:
> >>> ++--fsck-objects[=<msg-id>=<severity>...]::
> >>> ++ Die if the pack contains broken objects. If the pack contains a tree
> >>> ++ pointing to a .gitmodules blob that does not exist, prints the hash of
> >>> ++ that blob (for the caller to check) after the hash that goes into the
> >>> ++ name of the pack/idx file (see "Notes").
> Thanks for clarifying! Would you mind providing a patch to revise the wording
> here to make it clearer? I would try but I feel like I might get the wording
> wrong.
I think the wording there is already mostly correct, except maybe make
everything plural (a tree -> trees, a .gitmodules blob -> .gitmodules
blobs, hash of that blob -> hashes of those blobs). We might also need
to modify a test to show that the current code indeed handles the plural
situation correctly. I don't have time right now to get to this, so
hopefully someone could pick this up.
^ permalink raw reply
* Re: [PATCH] ci: update FreeBSD cirrus job
From: Junio C Hamano @ 2024-01-31 22:35 UTC (permalink / raw)
To: Carlo Marcelo Arenas Belón; +Cc: git, Johannes.Schindelin
In-Reply-To: <20240131191325.33228-1-carenas@gmail.com>
Carlo Marcelo Arenas Belón <carenas@gmail.com> writes:
> FreeBSD 12 is EOL and no longer available, causing errors in this job.
>
> Upgrade to 13.2, which is the next oldest release with support and that
> should keep it for at least another 4 months.
>
> This will be upgraded again once 13.3 is released to avoid furtheer
> surprises.
Thanks.
> "Not enough compute credits to prioritize tasks!" seems to be just a
> reminder that the credit allocate for the Free Tier by Cirrus is all
> used up and which might result in additional delays getting a result.
This statement does not quite help future readers of "git log",
unless they still remember that it was how Dscho noticed the
problem. Either moving it under "---" line (meaning: remove from
the proposed log message), or adding reference to the original
report, would be more appropriate. For now, I'd amend the log
message to read:
The original report [*] of this problem mentions an error message
"Not enough compute credits to prioritize tasks!". It seems to be
just a reminder that the credit allocate for the Free Tier by
Cirrus is all used up and which might result in additional delays
getting a result.
[*] https://lore.kernel.org/git/d2d7da84-e2a3-a7b2-3f95-c8d53ad4dd5f@gmx.de/
or something like that while queuing.
Thanks.
>
> Signed-off-by: Carlo Marcelo Arenas Belón <carenas@gmail.com>
> ---
> .cirrus.yml | 4 ++--
> 1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/.cirrus.yml b/.cirrus.yml
> index b6280692d2..77346a4929 100644
> --- a/.cirrus.yml
> +++ b/.cirrus.yml
> @@ -1,7 +1,7 @@
> env:
> CIRRUS_CLONE_DEPTH: 1
>
> -freebsd_12_task:
> +freebsd_task:
> env:
> GIT_PROVE_OPTS: "--timer --jobs 10"
> GIT_TEST_OPTS: "--no-chain-lint --no-bin-wrappers"
> @@ -9,7 +9,7 @@ freebsd_12_task:
> DEFAULT_TEST_TARGET: prove
> DEVELOPER: 1
> freebsd_instance:
> - image_family: freebsd-12-3
> + image_family: freebsd-13-2
> memory: 2G
> install_script:
> pkg install -y gettext gmake perl5
^ permalink raw reply
* [PATCH v6 00/16] bloom: changed-path Bloom filters v2 (& sundries)
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
(Rebased onto the tip of 'master', which is now bc7ee2e5e1 (The twelfth
batch, 2024-01-30), at the time of writing).
This series is a minor 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).
This version is nearly identical to the previous round, modulo some
patch reorganization prompted by a test failure noticed by SZEDER [3].
I'm still not sure how that failure got through, but this round fixes
it, and I've double checked that 'git rebase -ix "make test"' passes on
across all revisions.
Thanks again 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://lore.kernel.org/git/20240129212614.GB9612@szeder.dev/
Jonathan Tan (1):
gitformat-commit-graph: describe version 2 of BDAT
Taylor Blau (15):
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
t4216: test changed path filters with high bit paths
repo-settings: introduce commitgraph.changedPathsVersion
bloom: annotate filters with hash version
bloom: prepare to discard incompatible Bloom filters
commit-graph: unconditionally load Bloom filters
commit-graph: new Bloom filter version that fixes murmur3
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 | 29 ++-
Documentation/gitformat-commit-graph.txt | 9 +-
bloom.c | 208 ++++++++++++++-
bloom.h | 38 ++-
commit-graph.c | 64 ++++-
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 | 310 ++++++++++++++++++++++-
14 files changed, 723 insertions(+), 58 deletions(-)
Range-diff against v5:
1: 6292e974c5 = 1: 9df34a2f4f t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`
2: 6437cf5888 = 2: a6dc377f1b revision.c: consult Bloom filters for root commits
3: d5a73b9fa6 ! 3: a77ab941bc commit-graph: ensure Bloom filters are read with consistent settings
@@ t/t4216-log-bloom.sh: test_expect_success 'Bloom generation backfills empty comm
+ done
+'
+
-+test_expect_success 'ensure incompatible Bloom filters are ignored' '
++test_expect_success 'ensure Bloom filters with incompatible settings are ignored' '
+ # Compute Bloom filters with "unusual" settings.
+ git -C $repo rev-parse one >in &&
+ GIT_TEST_BLOOM_SETTINGS_NUM_HASHES=3 git -C $repo commit-graph write \
4: 85af5e80ef = 4: 56a9fdaff0 gitformat-commit-graph: describe version 2 of BDAT
5: b5ff3a9b34 = 5: 7484a82f7f t/helper/test-read-graph.c: extract `dump_graph_info()`
6: 1b45dc8d85 = 6: 48343f93a2 bloom.h: make `load_bloom_filter_from_graph()` public
7: 42b5126016 = 7: 286fd7dcdb t/helper/test-read-graph: implement `bloom-filters` mode
8: 2029a2e30c = 8: 7de7b89da0 t4216: test changed path filters with high bit paths
9: 79c6c3025a ! 9: b13c9b8ff9 repo-settings: introduce commitgraph.changedPathsVersion
@@ repository.h: struct repo_settings {
int gc_write_commit_graph;
int fetch_write_commit_graph;
int command_requires_full_index;
-
- ## t/t4216-log-bloom.sh ##
-@@ t/t4216-log-bloom.sh: test_expect_success 'setup for mixed Bloom setting tests' '
- done
- '
-
--test_expect_success 'ensure incompatible Bloom filters are ignored' '
-+test_expect_success 'ensure Bloom filters with incompatible settings are ignored' '
- # Compute Bloom filters with "unusual" settings.
- git -C $repo rev-parse one >in &&
- GIT_TEST_BLOOM_SETTINGS_NUM_HASHES=3 git -C $repo commit-graph write \
-@@ t/t4216-log-bloom.sh: test_expect_success 'merge graph layers with incompatible Bloom settings' '
- test_must_be_empty err
- '
-
-+test_expect_success 'ensure Bloom filter with incompatible versions are ignored' '
-+ rm "$repo/$graph" &&
-+
-+ git -C $repo log --oneline --no-decorate -- $CENT >expect &&
-+
-+ # Compute v1 Bloom filters for commits at the bottom.
-+ git -C $repo rev-parse HEAD^ >in &&
-+ git -C $repo commit-graph write --stdin-commits --changed-paths \
-+ --split <in &&
-+
-+ # Compute v2 Bloomfilters for the rest of the commits at the top.
-+ git -C $repo rev-parse HEAD >in &&
-+ git -C $repo -c commitGraph.changedPathsVersion=2 commit-graph write \
-+ --stdin-commits --changed-paths --split=no-merge <in &&
-+
-+ test_line_count = 2 $repo/$chain &&
-+
-+ git -C $repo log --oneline --no-decorate -- $CENT >actual 2>err &&
-+ test_cmp expect actual &&
-+
-+ layer="$(head -n 1 $repo/$chain)" &&
-+ cat >expect.err <<-EOF &&
-+ warning: disabling Bloom filters for commit-graph layer $SQ$layer$SQ due to incompatible settings
-+ EOF
-+ test_cmp expect.err err
-+'
-+
- get_first_changed_path_filter () {
- test-tool read-graph bloom-filters >filters.dat &&
- head -n 1 filters.dat
11: a73c77a5ba = 10: 09c44c51a5 bloom: annotate filters with hash version
12: 0c62b36206 = 11: d4995ef600 bloom: prepare to discard incompatible Bloom filters
13: ff348fc49d ! 12: c8e9bb7c88 commit-graph.c: unconditionally load Bloom filters
@@ Metadata
Author: Taylor Blau <me@ttaylorr.com>
## Commit message ##
- commit-graph.c: unconditionally load Bloom filters
+ commit-graph: unconditionally load Bloom filters
In an earlier commit, we began ignoring the Bloom data ("BDAT") chunk
for commit-graphs whose Bloom filters were computed using a hash version
- incompatible with the value of `commitGraph.changedPathVersion`.
+ incompatible with the value of `commitGraph.changedPathVersion`.
Now that the Bloom API has been hardened to discard these incompatible
filters (with the exception of low-level APIs), we can safely load these
@@ Commit message
## commit-graph.c ##
@@ commit-graph.c: static int graph_read_bloom_data(const unsigned char *chunk_start,
-
+ g->chunk_bloom_data_size = chunk_size;
hash_version = get_be32(chunk_start);
-- if (*c->commit_graph_changed_paths_version == -1)
-- *c->commit_graph_changed_paths_version = hash_version;
-- else if (hash_version != *c->commit_graph_changed_paths_version)
+- if (hash_version != 1)
- return 0;
-
- g->chunk_bloom_data = chunk_start;
- g->chunk_bloom_data_size = chunk_size;
g->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));
+ g->bloom_filter_settings->hash_version = hash_version;
+ g->bloom_filter_settings->num_hashes = get_be32(chunk_start + 4);
@@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
ctx->write_generation_data = (get_configured_generation_version(r) == 2);
ctx->num_generation_data_overflows = 0;
-- bloom_settings.hash_version = r->settings.commit_graph_changed_paths_version == 2
-- ? 2 : 1;
+ bloom_settings.hash_version = r->settings.commit_graph_changed_paths_version;
bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
bloom_settings.bits_per_entry);
bloom_settings.num_hashes = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES",
@@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
/* We have changed-paths already. Keep them in the next graph */
- if (g && g->bloom_filter_settings) {
+ if (g && g->chunk_bloom_data) {
ctx->changed_paths = 1;
- ctx->bloom_settings = g->bloom_filter_settings;
+
10: cfa5c358f8 ! 13: d2f11c082d commit-graph: new Bloom filter version that fixes murmur3
@@ bloom.h: int load_bloom_filter_from_graph(struct commit_graph *g,
size_t len,
## commit-graph.c ##
-@@ commit-graph.c: static int graph_read_bloom_index(const unsigned char *chunk_start,
- return 0;
- }
-
-+struct graph_read_bloom_data_context {
-+ struct commit_graph *g;
-+ int *commit_graph_changed_paths_version;
-+};
-+
- static int graph_read_bloom_data(const unsigned char *chunk_start,
+@@ commit-graph.c: static int graph_read_bloom_data(const unsigned char *chunk_start,
size_t chunk_size, void *data)
{
-- struct commit_graph *g = data;
-+ struct graph_read_bloom_data_context *c = data;
-+ struct commit_graph *g = c->g;
- uint32_t hash_version;
+ struct commit_graph *g = data;
+- uint32_t hash_version;
if (chunk_size < BLOOMDATA_CHUNK_HEADER_SIZE) {
+ warning(_("ignoring too-small changed-path chunk"
@@ commit-graph.c: static int graph_read_bloom_data(const unsigned char *chunk_start,
- return -1;
- }
-+ hash_version = get_be32(chunk_start);
-+
-+ if (*c->commit_graph_changed_paths_version == -1)
-+ *c->commit_graph_changed_paths_version = hash_version;
-+ else if (hash_version != *c->commit_graph_changed_paths_version)
-+ return 0;
-+
g->chunk_bloom_data = chunk_start;
g->chunk_bloom_data_size = chunk_size;
- hash_version = get_be32(chunk_start);
--
-- if (hash_version != 1)
-- return 0;
--
+
g->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));
- g->bloom_filter_settings->hash_version = hash_version;
+- g->bloom_filter_settings->hash_version = hash_version;
++ g->bloom_filter_settings->hash_version = get_be32(chunk_start);
g->bloom_filter_settings->num_hashes = get_be32(chunk_start + 4);
-@@ commit-graph.c: struct commit_graph *parse_commit_graph(struct repo_settings *s,
- }
-
- if (s->commit_graph_changed_paths_version) {
-+ struct graph_read_bloom_data_context context = {
-+ .g = graph,
-+ .commit_graph_changed_paths_version = &s->commit_graph_changed_paths_version
-+ };
- read_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES,
- graph_read_bloom_index, graph);
- read_chunk(cf, GRAPH_CHUNKID_BLOOMDATA,
-- graph_read_bloom_data, graph);
-+ graph_read_bloom_data, &context);
- }
-
- if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) {
+ g->bloom_filter_settings->bits_per_entry = get_be32(chunk_start + 8);
+ g->bloom_filter_settings->max_changed_paths = DEFAULT_BLOOM_MAX_CHANGES;
@@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
}
if (!commit_graph_compatible(r))
@@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
CALLOC_ARRAY(ctx, 1);
ctx->r = r;
-@@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
- ctx->write_generation_data = (get_configured_generation_version(r) == 2);
- ctx->num_generation_data_overflows = 0;
-
-+ bloom_settings.hash_version = r->settings.commit_graph_changed_paths_version == 2
-+ ? 2 : 1;
- bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
- bloom_settings.bits_per_entry);
- bloom_settings.num_hashes = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES",
@@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
g = ctx->r->objects->commit_graph;
@@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
- if (g && g->chunk_bloom_data) {
+ if (g && g->bloom_filter_settings) {
ctx->changed_paths = 1;
- ctx->bloom_settings = g->bloom_filter_settings;
- }
+
+ /* don't propagate the hash_version unless unspecified */
## t/helper/test-bloom.c ##
@@ t/helper/test-bloom.c: static void get_bloom_filter_for_commit(const struct object_id *commit_oid)
@@ t/t0095-bloom.sh: test_expect_success 'compute unseeded murmur3 hash for test st
Hashes:0x5615800c|0x5b966560|0x61174ab4|0x66983008|0x6c19155c|0x7199fab0|0x771ae004|
## t/t4216-log-bloom.sh ##
+@@ t/t4216-log-bloom.sh: test_expect_success 'merge graph layers with incompatible Bloom settings' '
+ test_must_be_empty err
+ '
+
++test_expect_success 'ensure Bloom filter with incompatible versions are ignored' '
++ rm "$repo/$graph" &&
++
++ git -C $repo log --oneline --no-decorate -- $CENT >expect &&
++
++ # Compute v1 Bloom filters for commits at the bottom.
++ git -C $repo rev-parse HEAD^ >in &&
++ git -C $repo commit-graph write --stdin-commits --changed-paths \
++ --split <in &&
++
++ # Compute v2 Bloomfilters for the rest of the commits at the top.
++ git -C $repo rev-parse HEAD >in &&
++ git -C $repo -c commitGraph.changedPathsVersion=2 commit-graph write \
++ --stdin-commits --changed-paths --split=no-merge <in &&
++
++ test_line_count = 2 $repo/$chain &&
++
++ git -C $repo log --oneline --no-decorate -- $CENT >actual 2>err &&
++ test_cmp expect actual &&
++
++ layer="$(head -n 1 $repo/$chain)" &&
++ cat >expect.err <<-EOF &&
++ warning: disabling Bloom filters for commit-graph layer $SQ$layer$SQ due to incompatible settings
++ EOF
++ test_cmp expect.err err
++'
++
+ get_first_changed_path_filter () {
+ test-tool read-graph bloom-filters >filters.dat &&
+ head -n 1 filters.dat
@@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when version 1 requested' '
)
'
14: acc0a097b3 < -: ---------- commit-graph: drop unnecessary `graph_read_bloom_data_context`
15: da401c8853 = 14: 9f54a376fb object.h: fix mis-aligned flag bits table
16: 2674967309 = 15: 67991dea7c commit-graph: reuse existing Bloom filters where possible
17: bea7ec7b3f ! 16: 12058a074d bloom: introduce `deinit_bloom_filters()`
@@ bloom.h: void add_key_to_filter(const struct bloom_key *key,
BLOOM_NOT_COMPUTED = (1 << 0),
## commit-graph.c ##
-@@ commit-graph.c: struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r)
- void close_commit_graph(struct raw_object_store *o)
- {
+@@ commit-graph.c: void close_commit_graph(struct raw_object_store *o)
+ return;
+
clear_commit_graph_data_slab(&commit_graph_data_slab);
+ deinit_bloom_filters();
free_commit_graph(o->commit_graph);
base-commit: bc7ee2e5e16f0d1e710ef8fab3db59ab11f2bbe7
--
2.43.0.509.g253f65a7fc
^ permalink raw reply
* [PATCH v6 01/16] t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
The existing implementation of test_bloom_filters_not_used() asserts
that the Bloom filter sub-system has not been initialized at all, by
checking for the absence of any data from it from trace2.
In the following commit, it will become possible to load Bloom filters
without using them (e.g., because the `commitGraph.changedPathVersion`
introduced later in this series is incompatible with the hash version
with which the commit-graph's Bloom filters were written).
When this is the case, it's possible to initialize the Bloom filter
sub-system, while still not using any Bloom filters. When this is the
case, check that the data dump from the Bloom sub-system is all zeros,
indicating that no filters were used.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
t/t4216-log-bloom.sh | 14 +++++++++++++-
1 file changed, 13 insertions(+), 1 deletion(-)
diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
index 2ba0324a69..b7baf49d62 100755
--- a/t/t4216-log-bloom.sh
+++ b/t/t4216-log-bloom.sh
@@ -82,7 +82,19 @@ test_bloom_filters_used () {
test_bloom_filters_not_used () {
log_args=$1
setup "$log_args" &&
- ! grep -q "statistics:{\"filter_not_present\":" "$TRASH_DIRECTORY/trace.perf" &&
+
+ if grep -q "statistics:{\"filter_not_present\":" "$TRASH_DIRECTORY/trace.perf"
+ then
+ # if the Bloom filter system is initialized, ensure that no
+ # filters were used
+ data="statistics:{"
+ data="$data\"filter_not_present\":0,"
+ data="$data\"maybe\":0,"
+ data="$data\"definitely_not\":0,"
+ data="$data\"false_positive\":0}"
+
+ grep -q "$data" "$TRASH_DIRECTORY/trace.perf"
+ fi &&
test_cmp log_wo_bloom log_w_bloom
}
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 02/16] revision.c: consult Bloom filters for root commits
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
The commit-graph stores changed-path Bloom filters which represent the
set of paths included in a tree-level diff between a commit's root tree
and that of its parent.
When a commit has no parents, the tree-diff is computed against that
commit's root tree and the empty tree. In other words, every path in
that commit's tree is stored in the Bloom filter (since they all appear
in the diff).
Consult these filters during pathspec-limited traversals in the function
`rev_same_tree_as_empty()`. Doing so yields a performance improvement
where we can avoid enumerating the full set of paths in a parentless
commit's root tree when we know that the path(s) of interest were not
listed in that commit's changed-path Bloom filter.
Suggested-by: SZEDER Gábor <szeder.dev@gmail.com>
Original-patch-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
revision.c | 26 ++++++++++++++++++++++----
t/t4216-log-bloom.sh | 8 ++++++--
2 files changed, 28 insertions(+), 6 deletions(-)
diff --git a/revision.c b/revision.c
index 2424c9bd67..0e6f7d02b6 100644
--- a/revision.c
+++ b/revision.c
@@ -833,17 +833,28 @@ static int rev_compare_tree(struct rev_info *revs,
return tree_difference;
}
-static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)
+static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit,
+ int nth_parent)
{
struct tree *t1 = repo_get_commit_tree(the_repository, commit);
+ int bloom_ret = -1;
if (!t1)
return 0;
+ if (!nth_parent && revs->bloom_keys_nr) {
+ bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
+ if (!bloom_ret)
+ return 1;
+ }
+
tree_difference = REV_TREE_SAME;
revs->pruning.flags.has_changes = 0;
diff_tree_oid(NULL, &t1->object.oid, "", &revs->pruning);
+ if (bloom_ret == 1 && tree_difference == REV_TREE_SAME)
+ count_bloom_filter_false_positive++;
+
return tree_difference == REV_TREE_SAME;
}
@@ -881,7 +892,7 @@ static int compact_treesame(struct rev_info *revs, struct commit *commit, unsign
if (nth_parent != 0)
die("compact_treesame %u", nth_parent);
old_same = !!(commit->object.flags & TREESAME);
- if (rev_same_tree_as_empty(revs, commit))
+ if (rev_same_tree_as_empty(revs, commit, nth_parent))
commit->object.flags |= TREESAME;
else
commit->object.flags &= ~TREESAME;
@@ -977,7 +988,14 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
return;
if (!commit->parents) {
- if (rev_same_tree_as_empty(revs, commit))
+ /*
+ * Pretend as if we are comparing ourselves to the
+ * (non-existent) first parent of this commit object. Even
+ * though no such parent exists, its changed-path Bloom filter
+ * (if one exists) is relative to the empty tree, using Bloom
+ * filters is allowed here.
+ */
+ if (rev_same_tree_as_empty(revs, commit, 0))
commit->object.flags |= TREESAME;
return;
}
@@ -1058,7 +1076,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
case REV_TREE_NEW:
if (revs->remove_empty_trees &&
- rev_same_tree_as_empty(revs, p)) {
+ rev_same_tree_as_empty(revs, p, nth_parent)) {
/* We are adding all the specified
* paths from this parent, so the
* history beyond this parent is not
diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
index b7baf49d62..cc6ebc8140 100755
--- a/t/t4216-log-bloom.sh
+++ b/t/t4216-log-bloom.sh
@@ -88,7 +88,11 @@ test_bloom_filters_not_used () {
# if the Bloom filter system is initialized, ensure that no
# filters were used
data="statistics:{"
- data="$data\"filter_not_present\":0,"
+ # unusable filters (e.g., those computed with a
+ # different value of commitGraph.changedPathsVersion)
+ # are counted in the filter_not_present bucket, so any
+ # value is OK there.
+ data="$data\"filter_not_present\":[0-9][0-9]*,"
data="$data\"maybe\":0,"
data="$data\"definitely_not\":0,"
data="$data\"false_positive\":0}"
@@ -175,7 +179,7 @@ test_expect_success 'setup - add commit-graph to the chain with Bloom filters' '
test_bloom_filters_used_when_some_filters_are_missing () {
log_args=$1
- bloom_trace_prefix="statistics:{\"filter_not_present\":3,\"maybe\":6,\"definitely_not\":9"
+ bloom_trace_prefix="statistics:{\"filter_not_present\":3,\"maybe\":6,\"definitely_not\":10"
setup "$log_args" &&
grep -q "$bloom_trace_prefix" "$TRASH_DIRECTORY/trace.perf" &&
test_cmp log_wo_bloom log_w_bloom
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 03/16] commit-graph: ensure Bloom filters are read with consistent settings
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
The changed-path Bloom filter mechanism is parameterized by a couple of
variables, notably the number of bits per hash (typically "m" in Bloom
filter literature) and the number of hashes themselves (typically "k").
It is critically important that filters are read with the Bloom filter
settings that they were written with. Failing to do so would mean that
each query is liable to compute different fingerprints, meaning that the
filter itself could return a false negative. This goes against a basic
assumption of using Bloom filters (that they may return false positives,
but never false negatives) and can lead to incorrect results.
We have some existing logic to carry forward existing Bloom filter
settings from one layer to the next. In `write_commit_graph()`, we have
something like:
if (!(flags & COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS)) {
struct commit_graph *g = ctx->r->objects->commit_graph;
/* We have changed-paths already. Keep them in the next graph */
if (g && g->chunk_bloom_data) {
ctx->changed_paths = 1;
ctx->bloom_settings = g->bloom_filter_settings;
}
}
, which drags forward Bloom filter settings across adjacent layers.
This doesn't quite address all cases, however, since it is possible for
intermediate layers to contain no Bloom filters at all. For example,
suppose we have two layers in a commit-graph chain, say, {G1, G2}. If G1
contains Bloom filters, but G2 doesn't, a new G3 (whose base graph is
G2) may be written with arbitrary Bloom filter settings, because we only
check the immediately adjacent layer's settings for compatibility.
This behavior has existed since the introduction of changed-path Bloom
filters. But in practice, this is not such a big deal, since the only
way up until this point to modify the Bloom filter settings at write
time is with the undocumented environment variables:
- GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY
- GIT_TEST_BLOOM_SETTINGS_NUM_HASHES
- GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS
(it is still possible to tweak MAX_CHANGED_PATHS between layers, but
this does not affect reads, so is allowed to differ across multiple
graph layers).
But in future commits, we will introduce another parameter to change the
hash algorithm used to compute Bloom fingerprints itself. This will be
exposed via a configuration setting, making this foot-gun easier to use.
To prevent this potential issue, validate that all layers of a split
commit-graph have compatible settings with the newest layer which
contains Bloom filters.
Reported-by: SZEDER Gábor <szeder.dev@gmail.com>
Original-test-by: SZEDER Gábor <szeder.dev@gmail.com>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
commit-graph.c | 25 +++++++++++++++++
t/t4216-log-bloom.sh | 65 +++++++++++++++++++++++++++++++++++++++++++-
2 files changed, 89 insertions(+), 1 deletion(-)
diff --git a/commit-graph.c b/commit-graph.c
index 45417d7412..216cf03da1 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -543,6 +543,30 @@ static int validate_mixed_generation_chain(struct commit_graph *g)
return 0;
}
+static void validate_mixed_bloom_settings(struct commit_graph *g)
+{
+ struct bloom_filter_settings *settings = NULL;
+ for (; g; g = g->base_graph) {
+ if (!g->bloom_filter_settings)
+ continue;
+ if (!settings) {
+ settings = g->bloom_filter_settings;
+ continue;
+ }
+
+ if (g->bloom_filter_settings->bits_per_entry != settings->bits_per_entry ||
+ g->bloom_filter_settings->num_hashes != settings->num_hashes) {
+ g->chunk_bloom_indexes = NULL;
+ g->chunk_bloom_data = NULL;
+ FREE_AND_NULL(g->bloom_filter_settings);
+
+ warning(_("disabling Bloom filters for commit-graph "
+ "layer '%s' due to incompatible settings"),
+ oid_to_hex(&g->oid));
+ }
+ }
+}
+
static int add_graph_to_chain(struct commit_graph *g,
struct commit_graph *chain,
struct object_id *oids,
@@ -666,6 +690,7 @@ struct commit_graph *load_commit_graph_chain_fd_st(struct repository *r,
}
validate_mixed_generation_chain(graph_chain);
+ validate_mixed_bloom_settings(graph_chain);
free(oids);
fclose(fp);
diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
index cc6ebc8140..64737b6ee9 100755
--- a/t/t4216-log-bloom.sh
+++ b/t/t4216-log-bloom.sh
@@ -421,8 +421,71 @@ test_expect_success 'Bloom generation backfills empty commits' '
)
'
+graph=.git/objects/info/commit-graph
+graphdir=.git/objects/info/commit-graphs
+chain=$graphdir/commit-graph-chain
+
+test_expect_success 'setup for mixed Bloom setting tests' '
+ repo=mixed-bloom-settings &&
+
+ git init $repo &&
+ for i in one two three
+ do
+ test_commit -C $repo $i file || return 1
+ done
+'
+
+test_expect_success 'ensure Bloom filters with incompatible settings are ignored' '
+ # Compute Bloom filters with "unusual" settings.
+ git -C $repo rev-parse one >in &&
+ GIT_TEST_BLOOM_SETTINGS_NUM_HASHES=3 git -C $repo commit-graph write \
+ --stdin-commits --changed-paths --split <in &&
+ layer=$(head -n 1 $repo/$chain) &&
+
+ # A commit-graph layer without Bloom filters "hides" the layers
+ # below ...
+ git -C $repo rev-parse two >in &&
+ git -C $repo commit-graph write --stdin-commits --no-changed-paths \
+ --split=no-merge <in &&
+
+ # Another commit-graph layer that has Bloom filters, but with
+ # standard settings, and is thus incompatible with the base
+ # layer written above.
+ git -C $repo rev-parse HEAD >in &&
+ git -C $repo commit-graph write --stdin-commits --changed-paths \
+ --split=no-merge <in &&
+
+ test_line_count = 3 $repo/$chain &&
+
+ # Ensure that incompatible Bloom filters are ignored.
+ git -C $repo -c core.commitGraph=false log --oneline --no-decorate -- file \
+ >expect 2>err &&
+ git -C $repo log --oneline --no-decorate -- file >actual 2>err &&
+ test_cmp expect actual &&
+ grep "disabling Bloom filters for commit-graph layer .$layer." err
+'
+
+test_expect_success 'merge graph layers with incompatible Bloom settings' '
+ # Ensure that incompatible Bloom filters are ignored when
+ # merging existing layers.
+ git -C $repo commit-graph write --reachable --changed-paths 2>err &&
+ grep "disabling Bloom filters for commit-graph layer .$layer." err &&
+
+ test_path_is_file $repo/$graph &&
+ test_dir_is_empty $repo/$graphdir &&
+
+ git -C $repo -c core.commitGraph=false log --oneline --no-decorate -- \
+ file >expect &&
+ trace_out="$(pwd)/trace.perf" &&
+ GIT_TRACE2_PERF="$trace_out" \
+ git -C $repo log --oneline --no-decorate -- file >actual 2>err &&
+
+ test_cmp expect actual &&
+ grep "statistics:{\"filter_not_present\":0," trace.perf &&
+ test_must_be_empty err
+'
+
corrupt_graph () {
- graph=.git/objects/info/commit-graph &&
test_when_finished "rm -rf $graph" &&
git commit-graph write --reachable --changed-paths &&
corrupt_chunk_file $graph "$@"
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 04/16] gitformat-commit-graph: describe version 2 of BDAT
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
From: Jonathan Tan <jonathantanmy@google.com>
The code change to Git to support version 2 will be done in subsequent
commits.
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>
---
Documentation/gitformat-commit-graph.txt | 9 ++++++---
1 file changed, 6 insertions(+), 3 deletions(-)
diff --git a/Documentation/gitformat-commit-graph.txt b/Documentation/gitformat-commit-graph.txt
index 31cad585e2..3e906e8030 100644
--- a/Documentation/gitformat-commit-graph.txt
+++ b/Documentation/gitformat-commit-graph.txt
@@ -142,13 +142,16 @@ All multi-byte numbers are in network byte order.
==== Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]
* It starts with header consisting of three unsigned 32-bit integers:
- - Version of the hash algorithm being used. We currently only support
- value 1 which corresponds to the 32-bit version of the murmur3 hash
+ - Version of the hash algorithm being used. We currently support
+ value 2 which corresponds to the 32-bit version of the murmur3 hash
implemented exactly as described in
https://en.wikipedia.org/wiki/MurmurHash#Algorithm and the double
hashing technique using seed values 0x293ae76f and 0x7e646e2 as
described in https://doi.org/10.1007/978-3-540-30494-4_26 "Bloom Filters
- in Probabilistic Verification"
+ in Probabilistic Verification". Version 1 Bloom filters have a bug that appears
+ when char is signed and the repository has path names that have characters >=
+ 0x80; Git supports reading and writing them, but this ability will be removed
+ in a future version of Git.
- The number of times a path is hashed and hence the number of bit positions
that cumulatively determine whether a file is present in the commit.
- The minimum number of bits 'b' per entry in the Bloom filter. If the filter
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 05/16] t/helper/test-read-graph.c: extract `dump_graph_info()`
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
Prepare for the 'read-graph' test helper to perform other tasks besides
dumping high-level information about the commit-graph by extracting its
main routine into a separate function.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
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>
---
t/helper/test-read-graph.c | 31 ++++++++++++++++++-------------
1 file changed, 18 insertions(+), 13 deletions(-)
diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c
index 8c7a83f578..3375392f6c 100644
--- a/t/helper/test-read-graph.c
+++ b/t/helper/test-read-graph.c
@@ -5,20 +5,8 @@
#include "bloom.h"
#include "setup.h"
-int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)
+static void dump_graph_info(struct commit_graph *graph)
{
- struct commit_graph *graph = NULL;
- struct object_directory *odb;
-
- setup_git_directory();
- odb = the_repository->objects->odb;
-
- prepare_repo_settings(the_repository);
-
- graph = read_commit_graph_one(the_repository, odb);
- if (!graph)
- return 1;
-
printf("header: %08x %d %d %d %d\n",
ntohl(*(uint32_t*)graph->data),
*(unsigned char*)(graph->data + 4),
@@ -57,6 +45,23 @@ int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)
if (graph->topo_levels)
printf(" topo_levels");
printf("\n");
+}
+
+int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)
+{
+ struct commit_graph *graph = NULL;
+ struct object_directory *odb;
+
+ setup_git_directory();
+ odb = the_repository->objects->odb;
+
+ prepare_repo_settings(the_repository);
+
+ graph = read_commit_graph_one(the_repository, odb);
+ if (!graph)
+ return 1;
+
+ dump_graph_info(graph);
UNLEAK(graph);
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 06/16] bloom.h: make `load_bloom_filter_from_graph()` public
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
Prepare for a future commit to use the load_bloom_filter_from_graph()
function directly to load specific Bloom filters out of the commit-graph
for manual inspection (to be used during tests).
Signed-off-by: Taylor Blau <me@ttaylorr.com>
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>
---
bloom.c | 6 +++---
bloom.h | 5 +++++
2 files changed, 8 insertions(+), 3 deletions(-)
diff --git a/bloom.c b/bloom.c
index e529f7605c..401999ed3c 100644
--- a/bloom.c
+++ b/bloom.c
@@ -48,9 +48,9 @@ static int check_bloom_offset(struct commit_graph *g, uint32_t pos,
return -1;
}
-static int load_bloom_filter_from_graph(struct commit_graph *g,
- struct bloom_filter *filter,
- uint32_t graph_pos)
+int load_bloom_filter_from_graph(struct commit_graph *g,
+ struct bloom_filter *filter,
+ uint32_t graph_pos)
{
uint32_t lex_pos, start_index, end_index;
diff --git a/bloom.h b/bloom.h
index adde6dfe21..1e4f612d2c 100644
--- a/bloom.h
+++ b/bloom.h
@@ -3,6 +3,7 @@
struct commit;
struct repository;
+struct commit_graph;
struct bloom_filter_settings {
/*
@@ -68,6 +69,10 @@ struct bloom_key {
uint32_t *hashes;
};
+int load_bloom_filter_from_graph(struct commit_graph *g,
+ struct bloom_filter *filter,
+ uint32_t graph_pos);
+
/*
* Calculate the murmur3 32-bit hash value for the given data
* using the given seed.
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 07/16] t/helper/test-read-graph: implement `bloom-filters` mode
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
Implement a mode of the "read-graph" test helper to dump out the
hexadecimal contents of the Bloom filter(s) contained in a commit-graph.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
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>
---
t/helper/test-read-graph.c | 44 +++++++++++++++++++++++++++++++++-----
1 file changed, 39 insertions(+), 5 deletions(-)
diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c
index 3375392f6c..da9ac8584d 100644
--- a/t/helper/test-read-graph.c
+++ b/t/helper/test-read-graph.c
@@ -47,10 +47,32 @@ static void dump_graph_info(struct commit_graph *graph)
printf("\n");
}
-int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)
+static void dump_graph_bloom_filters(struct commit_graph *graph)
+{
+ uint32_t i;
+
+ for (i = 0; i < graph->num_commits + graph->num_commits_in_base; i++) {
+ struct bloom_filter filter = { 0 };
+ size_t j;
+
+ if (load_bloom_filter_from_graph(graph, &filter, i) < 0) {
+ fprintf(stderr, "missing Bloom filter for graph "
+ "position %"PRIu32"\n", i);
+ continue;
+ }
+
+ for (j = 0; j < filter.len; j++)
+ printf("%02x", filter.data[j]);
+ if (filter.len)
+ printf("\n");
+ }
+}
+
+int cmd__read_graph(int argc, const char **argv)
{
struct commit_graph *graph = NULL;
struct object_directory *odb;
+ int ret = 0;
setup_git_directory();
odb = the_repository->objects->odb;
@@ -58,12 +80,24 @@ int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)
prepare_repo_settings(the_repository);
graph = read_commit_graph_one(the_repository, odb);
- if (!graph)
- return 1;
+ if (!graph) {
+ ret = 1;
+ goto done;
+ }
- dump_graph_info(graph);
+ if (argc <= 1)
+ dump_graph_info(graph);
+ else if (!strcmp(argv[1], "bloom-filters"))
+ dump_graph_bloom_filters(graph);
+ else {
+ fprintf(stderr, "unknown sub-command: '%s'\n", argv[1]);
+ ret = 1;
+ }
+done:
UNLEAK(graph);
- return 0;
+ return ret;
}
+
+
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 08/16] t4216: test changed path filters with high bit paths
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
Subsequent commits will teach Git another version of changed path
filter that has different behavior with paths that contain at least
one character with its high bit set, so test the existing behavior as
a baseline.
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/t4216-log-bloom.sh | 51 ++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 51 insertions(+)
diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
index 64737b6ee9..93b8d096cf 100755
--- a/t/t4216-log-bloom.sh
+++ b/t/t4216-log-bloom.sh
@@ -485,6 +485,57 @@ test_expect_success 'merge graph layers with incompatible Bloom settings' '
test_must_be_empty err
'
+get_first_changed_path_filter () {
+ test-tool read-graph bloom-filters >filters.dat &&
+ head -n 1 filters.dat
+}
+
+# chosen to be the same under all Unicode normalization forms
+CENT=$(printf "\302\242")
+
+test_expect_success 'set up repo with high bit path, version 1 changed-path' '
+ git init highbit1 &&
+ test_commit -C highbit1 c1 "$CENT" &&
+ git -C highbit1 commit-graph write --reachable --changed-paths
+'
+
+test_expect_success 'setup check value of version 1 changed-path' '
+ (
+ cd highbit1 &&
+ echo "52a9" >expect &&
+ get_first_changed_path_filter >actual
+ )
+'
+
+# expect will not match actual if char is unsigned by default. Write the test
+# in this way, so that a user running this test script can still see if the two
+# files match. (It will appear as an ordinary success if they match, and a skip
+# if not.)
+if test_cmp highbit1/expect highbit1/actual
+then
+ test_set_prereq SIGNED_CHAR_BY_DEFAULT
+fi
+test_expect_success SIGNED_CHAR_BY_DEFAULT 'check value of version 1 changed-path' '
+ # Only the prereq matters for this test.
+ true
+'
+
+test_expect_success 'setup make another commit' '
+ # "git log" does not use Bloom filters for root commits - see how, in
+ # revision.c, rev_compare_tree() (the only code path that eventually calls
+ # get_bloom_filter()) is only called by try_to_simplify_commit() when the commit
+ # has one parent. Therefore, make another commit so that we perform the tests on
+ # a non-root commit.
+ test_commit -C highbit1 anotherc1 "another$CENT"
+'
+
+test_expect_success 'version 1 changed-path used when version 1 requested' '
+ (
+ cd highbit1 &&
+ test_bloom_filters_used "-- another$CENT"
+ )
+'
+
corrupt_graph () {
test_when_finished "rm -rf $graph" &&
git commit-graph write --reachable --changed-paths &&
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 09/16] repo-settings: introduce commitgraph.changedPathsVersion
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
A subsequent commit will introduce another version of the changed-path
filter in the commit graph file. In order to control which version to
write (and read), a config variable is needed.
Therefore, introduce this config variable. For forwards compatibility,
teach Git to not read commit graphs when the config variable
is set to an unsupported version. Because we teach Git this,
commitgraph.readChangedPaths is now redundant, so deprecate it and
define its behavior in terms of the config variable we introduce.
This commit does not change the behavior of writing (Git writes changed
path filters when explicitly instructed regardless of any config
variable), but a subsequent commit will restrict Git such that it will
only write when commitgraph.changedPathsVersion is a recognized value.
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>
---
Documentation/config/commitgraph.txt | 26 +++++++++++++++++++++++---
commit-graph.c | 5 +++--
oss-fuzz/fuzz-commit-graph.c | 2 +-
repo-settings.c | 6 +++++-
repository.h | 2 +-
5 files changed, 33 insertions(+), 8 deletions(-)
diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt
index 30604e4a4c..e68cdededa 100644
--- a/Documentation/config/commitgraph.txt
+++ b/Documentation/config/commitgraph.txt
@@ -9,6 +9,26 @@ commitGraph.maxNewFilters::
commit-graph write` (c.f., linkgit:git-commit-graph[1]).
commitGraph.readChangedPaths::
- If true, then git will use the changed-path Bloom filters in the
- commit-graph file (if it exists, and they are present). Defaults to
- true. See linkgit:git-commit-graph[1] for more information.
+ Deprecated. Equivalent to commitGraph.changedPathsVersion=-1 if true, and
+ commitGraph.changedPathsVersion=0 if false. (If commitGraph.changedPathVersion
+ is also set, commitGraph.changedPathsVersion takes precedence.)
+
+commitGraph.changedPathsVersion::
+ Specifies the version of the changed-path Bloom filters that Git will read and
+ write. May be -1, 0 or 1. Note that values greater than 1 may be
+ incompatible with older versions of Git which do not yet understand
+ those versions. Use caution when operating in a mixed-version
+ environment.
++
+Defaults to -1.
++
+If -1, Git will use the version of the changed-path Bloom filters in the
+repository, defaulting to 1 if there are none.
++
+If 0, Git will not read any Bloom filters, and will write version 1 Bloom
+filters when instructed to write.
++
+If 1, Git will only read version 1 Bloom filters, and will write version 1
+Bloom filters.
++
+See linkgit:git-commit-graph[1] for more information.
diff --git a/commit-graph.c b/commit-graph.c
index 216cf03da1..b80bf36720 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -459,7 +459,7 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s,
graph->read_generation_data = 1;
}
- if (s->commit_graph_read_changed_paths) {
+ if (s->commit_graph_changed_paths_version) {
read_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES,
graph_read_bloom_index, graph);
read_chunk(cf, GRAPH_CHUNKID_BLOOMDATA,
@@ -555,7 +555,8 @@ static void validate_mixed_bloom_settings(struct commit_graph *g)
}
if (g->bloom_filter_settings->bits_per_entry != settings->bits_per_entry ||
- g->bloom_filter_settings->num_hashes != settings->num_hashes) {
+ g->bloom_filter_settings->num_hashes != settings->num_hashes ||
+ g->bloom_filter_settings->hash_version != settings->hash_version) {
g->chunk_bloom_indexes = NULL;
g->chunk_bloom_data = NULL;
FREE_AND_NULL(g->bloom_filter_settings);
diff --git a/oss-fuzz/fuzz-commit-graph.c b/oss-fuzz/fuzz-commit-graph.c
index 2992079dd9..325c0b991a 100644
--- a/oss-fuzz/fuzz-commit-graph.c
+++ b/oss-fuzz/fuzz-commit-graph.c
@@ -19,7 +19,7 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
* possible.
*/
the_repository->settings.commit_graph_generation_version = 2;
- the_repository->settings.commit_graph_read_changed_paths = 1;
+ the_repository->settings.commit_graph_changed_paths_version = 1;
g = parse_commit_graph(&the_repository->settings, (void *)data, size);
repo_clear(the_repository);
free_commit_graph(g);
diff --git a/repo-settings.c b/repo-settings.c
index 30cd478762..c821583fe5 100644
--- a/repo-settings.c
+++ b/repo-settings.c
@@ -23,6 +23,7 @@ void prepare_repo_settings(struct repository *r)
int value;
const char *strval;
int manyfiles;
+ int read_changed_paths;
if (!r->gitdir)
BUG("Cannot add settings for uninitialized repository");
@@ -53,7 +54,10 @@ void prepare_repo_settings(struct repository *r)
/* Commit graph config or default, does not cascade (simple) */
repo_cfg_bool(r, "core.commitgraph", &r->settings.core_commit_graph, 1);
repo_cfg_int(r, "commitgraph.generationversion", &r->settings.commit_graph_generation_version, 2);
- repo_cfg_bool(r, "commitgraph.readchangedpaths", &r->settings.commit_graph_read_changed_paths, 1);
+ repo_cfg_bool(r, "commitgraph.readchangedpaths", &read_changed_paths, 1);
+ repo_cfg_int(r, "commitgraph.changedpathsversion",
+ &r->settings.commit_graph_changed_paths_version,
+ read_changed_paths ? -1 : 0);
repo_cfg_bool(r, "gc.writecommitgraph", &r->settings.gc_write_commit_graph, 1);
repo_cfg_bool(r, "fetch.writecommitgraph", &r->settings.fetch_write_commit_graph, 0);
diff --git a/repository.h b/repository.h
index 7a250a6605..1edc4d4a67 100644
--- a/repository.h
+++ b/repository.h
@@ -32,7 +32,7 @@ struct repo_settings {
int core_commit_graph;
int commit_graph_generation_version;
- int commit_graph_read_changed_paths;
+ int commit_graph_changed_paths_version;
int gc_write_commit_graph;
int fetch_write_commit_graph;
int command_requires_full_index;
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 10/16] bloom: annotate filters with hash version
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
In subsequent commits, we will want to load existing Bloom filters out
of a commit-graph, even when the hash version they were computed with
does not match the value of `commitGraph.changedPathVersion`.
In order to differentiate between the two, add a "version" field to each
Bloom filter.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
bloom.c | 11 ++++++++---
bloom.h | 1 +
2 files changed, 9 insertions(+), 3 deletions(-)
diff --git a/bloom.c b/bloom.c
index 401999ed3c..e64e53bc4c 100644
--- a/bloom.c
+++ b/bloom.c
@@ -88,6 +88,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g,
filter->data = (unsigned char *)(g->chunk_bloom_data +
sizeof(unsigned char) * start_index +
BLOOMDATA_CHUNK_HEADER_SIZE);
+ filter->version = g->bloom_filter_settings->hash_version;
return 1;
}
@@ -210,11 +211,13 @@ static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED,
return strcmp(e1->path, e2->path);
}
-static void init_truncated_large_filter(struct bloom_filter *filter)
+static void init_truncated_large_filter(struct bloom_filter *filter,
+ int version)
{
filter->data = xmalloc(1);
filter->data[0] = 0xFF;
filter->len = 1;
+ filter->version = version;
}
struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
@@ -299,13 +302,15 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
}
if (hashmap_get_size(&pathmap) > settings->max_changed_paths) {
- init_truncated_large_filter(filter);
+ init_truncated_large_filter(filter,
+ settings->hash_version);
if (computed)
*computed |= BLOOM_TRUNC_LARGE;
goto cleanup;
}
filter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;
+ filter->version = settings->hash_version;
if (!filter->len) {
if (computed)
*computed |= BLOOM_TRUNC_EMPTY;
@@ -325,7 +330,7 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
} else {
for (i = 0; i < diff_queued_diff.nr; i++)
diff_free_filepair(diff_queued_diff.queue[i]);
- init_truncated_large_filter(filter);
+ init_truncated_large_filter(filter, settings->hash_version);
if (computed)
*computed |= BLOOM_TRUNC_LARGE;
diff --git a/bloom.h b/bloom.h
index 1e4f612d2c..c9dd7d4022 100644
--- a/bloom.h
+++ b/bloom.h
@@ -53,6 +53,7 @@ struct bloom_filter_settings {
struct bloom_filter {
unsigned char *data;
size_t len;
+ int version;
};
/*
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 11/16] bloom: prepare to discard incompatible Bloom filters
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
Callers use the inline `get_bloom_filter()` implementation as a thin
wrapper around `get_or_compute_bloom_filter()`. The former calls the
latter with a value of "0" for `compute_if_not_present`, making
`get_bloom_filter()` the default read-only path for fetching an existing
Bloom filter.
Callers expect the value returned from `get_bloom_filter()` is usable,
that is that it's compatible with the configured value corresponding to
`commitGraph.changedPathsVersion`.
This is OK, since the commit-graph machinery only initializes its BDAT
chunk (thereby enabling it to service Bloom filter queries) when the
Bloom filter hash_version is compatible with our settings. So any value
returned by `get_bloom_filter()` is trivially useable.
However, subsequent commits will load the BDAT chunk even when the Bloom
filters are built with incompatible hash versions. Prepare to handle
this by teaching `get_bloom_filter()` to discard filters that are
incompatible with the configured hash version.
Callers who wish to read incompatible filters (e.g., for upgrading
filters from v1 to v2) may use the lower level routine,
`get_or_compute_bloom_filter()`.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
bloom.c | 20 +++++++++++++++++++-
bloom.h | 20 ++++++++++++++++++--
2 files changed, 37 insertions(+), 3 deletions(-)
diff --git a/bloom.c b/bloom.c
index e64e53bc4c..c24489dbcf 100644
--- a/bloom.c
+++ b/bloom.c
@@ -220,6 +220,23 @@ static void init_truncated_large_filter(struct bloom_filter *filter,
filter->version = version;
}
+struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)
+{
+ struct bloom_filter *filter;
+ int hash_version;
+
+ filter = get_or_compute_bloom_filter(r, c, 0, NULL, NULL);
+ if (!filter)
+ return NULL;
+
+ prepare_repo_settings(r);
+ hash_version = r->settings.commit_graph_changed_paths_version;
+
+ if (!(hash_version == -1 || hash_version == filter->version))
+ return NULL; /* unusable filter */
+ return filter;
+}
+
struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
struct commit *c,
int compute_if_not_present,
@@ -245,7 +262,8 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
filter, graph_pos);
}
- if (filter->data && filter->len)
+ if ((filter->data && filter->len) &&
+ (!settings || settings->hash_version == filter->version))
return filter;
if (!compute_if_not_present)
return NULL;
diff --git a/bloom.h b/bloom.h
index c9dd7d4022..052a993aab 100644
--- a/bloom.h
+++ b/bloom.h
@@ -108,8 +108,24 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
const struct bloom_filter_settings *settings,
enum bloom_filter_computed *computed);
-#define get_bloom_filter(r, c) get_or_compute_bloom_filter( \
- (r), (c), 0, NULL, NULL)
+/*
+ * Find the Bloom filter associated with the given commit "c".
+ *
+ * If any of the following are true
+ *
+ * - the repository does not have a commit-graph, or
+ * - the repository disables reading from the commit-graph, or
+ * - the given commit does not have a Bloom filter computed, or
+ * - there is a Bloom filter for commit "c", but it cannot be read
+ * because the filter uses an incompatible version of murmur3
+ *
+ * , then `get_bloom_filter()` will return NULL. Otherwise, the corresponding
+ * Bloom filter will be returned.
+ *
+ * For callers who wish to inspect Bloom filters with incompatible hash
+ * versions, use get_or_compute_bloom_filter().
+ */
+struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c);
int bloom_filter_contains(const struct bloom_filter *filter,
const struct bloom_key *key,
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 12/16] commit-graph: unconditionally load Bloom filters
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
In an earlier commit, we began ignoring the Bloom data ("BDAT") chunk
for commit-graphs whose Bloom filters were computed using a hash version
incompatible with the value of `commitGraph.changedPathVersion`.
Now that the Bloom API has been hardened to discard these incompatible
filters (with the exception of low-level APIs), we can safely load these
Bloom filters unconditionally.
We no longer want to return early from `graph_read_bloom_data()`, and
similarly do not want to set the bloom_settings' `hash_version` field as
a side-effect. The latter is because we want to wait until we know which
Bloom settings we're using (either the defaults, from the GIT_TEST
variables, or from the previous commit-graph layer) before deciding what
hash_version to use.
If we detect an existing BDAT chunk, we'll infer the rest of the
settings (e.g., number of hashes, bits per entry, and maximum number of
changed paths) from the earlier graph layer. The hash_version will be
inferred from the previous layer as well, unless one has already been
specified via configuration.
Once all of that is done, we normalize the value of the hash_version to
either "1" or "2".
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
commit-graph.c | 14 ++++++++++----
1 file changed, 10 insertions(+), 4 deletions(-)
diff --git a/commit-graph.c b/commit-graph.c
index b80bf36720..6c3fbae142 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -358,9 +358,6 @@ static int graph_read_bloom_data(const unsigned char *chunk_start,
g->chunk_bloom_data_size = chunk_size;
hash_version = get_be32(chunk_start);
- if (hash_version != 1)
- return 0;
-
g->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));
g->bloom_filter_settings->hash_version = hash_version;
g->bloom_filter_settings->num_hashes = get_be32(chunk_start + 4);
@@ -2516,6 +2513,7 @@ int write_commit_graph(struct object_directory *odb,
ctx->write_generation_data = (get_configured_generation_version(r) == 2);
ctx->num_generation_data_overflows = 0;
+ bloom_settings.hash_version = r->settings.commit_graph_changed_paths_version;
bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
bloom_settings.bits_per_entry);
bloom_settings.num_hashes = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES",
@@ -2547,10 +2545,18 @@ int write_commit_graph(struct object_directory *odb,
/* We have changed-paths already. Keep them in the next graph */
if (g && g->chunk_bloom_data) {
ctx->changed_paths = 1;
- ctx->bloom_settings = g->bloom_filter_settings;
+
+ /* don't propagate the hash_version unless unspecified */
+ if (bloom_settings.hash_version == -1)
+ bloom_settings.hash_version = g->bloom_filter_settings->hash_version;
+ bloom_settings.bits_per_entry = g->bloom_filter_settings->bits_per_entry;
+ bloom_settings.num_hashes = g->bloom_filter_settings->num_hashes;
+ bloom_settings.max_changed_paths = g->bloom_filter_settings->max_changed_paths;
}
}
+ bloom_settings.hash_version = bloom_settings.hash_version == 2 ? 2 : 1;
+
if (ctx->split) {
struct commit_graph *g = ctx->r->objects->commit_graph;
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 13/16] commit-graph: new Bloom filter version that fixes murmur3
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
The murmur3 implementation in bloom.c has a bug when converting series
of 4 bytes into network-order integers when char is signed (which is
controllable by a compiler option, and the default signedness of char is
platform-specific). When a string contains characters with the high bit
set, this bug causes results that, although internally consistent within
Git, does not accord with other implementations of murmur3 (thus,
the changed path filters wouldn't be readable by other off-the-shelf
implementatios of murmur3) and even with Git binaries that were compiled
with different signedness of char. This bug affects both how Git writes
changed path filters to disk and how Git interprets changed path filters
on disk.
Therefore, introduce a new version (2) of changed path filters that
corrects this problem. The existing version (1) is still supported and
is still the default, but users should migrate away from it as soon
as possible.
Because this bug only manifests with characters that have the high bit
set, it may be possible that some (or all) commits in a given repo would
have the same changed path filter both before and after this fix is
applied. However, in order to determine whether this is the case, the
changed paths would first have to be computed, at which point it is not
much more expensive to just compute a new changed path filter.
So this patch does not include any mechanism to "salvage" changed path
filters from repositories. There is also no "mixed" mode - for each
invocation of Git, reading and writing changed path filters are done
with the same version number; this version number may be explicitly
stated (typically if the user knows which version they need) or
automatically determined from the version of the existing changed path
filters in the repository.
There is a change in write_commit_graph(). graph_read_bloom_data()
makes it possible for chunk_bloom_data to be non-NULL but
bloom_filter_settings to be NULL, which causes a segfault later on. I
produced such a segfault while developing this patch, but couldn't find
a way to reproduce it neither after this complete patch (or before),
but in any case it seemed like a good thing to include that might help
future patch authors.
The value in t0095 was obtained from another murmur3 implementation
using the following Go source code:
package main
import "fmt"
import "github.com/spaolacci/murmur3"
func main() {
fmt.Printf("%x\n", murmur3.Sum32([]byte("Hello world!")))
fmt.Printf("%x\n", murmur3.Sum32([]byte{0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee, 0xff}))
}
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 | 5 +-
bloom.c | 69 ++++++++++++-
bloom.h | 8 +-
commit-graph.c | 13 ++-
t/helper/test-bloom.c | 9 +-
t/t0095-bloom.sh | 8 ++
t/t4216-log-bloom.sh | 141 +++++++++++++++++++++++++++
7 files changed, 241 insertions(+), 12 deletions(-)
diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt
index e68cdededa..7f8c9d6638 100644
--- a/Documentation/config/commitgraph.txt
+++ b/Documentation/config/commitgraph.txt
@@ -15,7 +15,7 @@ commitGraph.readChangedPaths::
commitGraph.changedPathsVersion::
Specifies the version of the changed-path Bloom filters that Git will read and
- write. May be -1, 0 or 1. Note that values greater than 1 may be
+ write. May be -1, 0, 1, or 2. Note that values greater than 1 may be
incompatible with older versions of Git which do not yet understand
those versions. Use caution when operating in a mixed-version
environment.
@@ -31,4 +31,7 @@ filters when instructed to write.
If 1, Git will only read version 1 Bloom filters, and will write version 1
Bloom filters.
+
+If 2, Git will only read version 2 Bloom filters, and will write version 2
+Bloom filters.
++
See linkgit:git-commit-graph[1] for more information.
diff --git a/bloom.c b/bloom.c
index c24489dbcf..323d8012b8 100644
--- a/bloom.c
+++ b/bloom.c
@@ -100,7 +100,64 @@ int load_bloom_filter_from_graph(struct commit_graph *g,
* Not considered to be cryptographically secure.
* Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
*/
-uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)
+uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len)
+{
+ const uint32_t c1 = 0xcc9e2d51;
+ const uint32_t c2 = 0x1b873593;
+ const uint32_t r1 = 15;
+ const uint32_t r2 = 13;
+ const uint32_t m = 5;
+ const uint32_t n = 0xe6546b64;
+ int i;
+ uint32_t k1 = 0;
+ const char *tail;
+
+ int len4 = len / sizeof(uint32_t);
+
+ uint32_t k;
+ for (i = 0; i < len4; i++) {
+ uint32_t byte1 = (uint32_t)(unsigned char)data[4*i];
+ uint32_t byte2 = ((uint32_t)(unsigned char)data[4*i + 1]) << 8;
+ uint32_t byte3 = ((uint32_t)(unsigned char)data[4*i + 2]) << 16;
+ uint32_t byte4 = ((uint32_t)(unsigned char)data[4*i + 3]) << 24;
+ k = byte1 | byte2 | byte3 | byte4;
+ k *= c1;
+ k = rotate_left(k, r1);
+ k *= c2;
+
+ seed ^= k;
+ seed = rotate_left(seed, r2) * m + n;
+ }
+
+ tail = (data + len4 * sizeof(uint32_t));
+
+ switch (len & (sizeof(uint32_t) - 1)) {
+ case 3:
+ k1 ^= ((uint32_t)(unsigned char)tail[2]) << 16;
+ /*-fallthrough*/
+ case 2:
+ k1 ^= ((uint32_t)(unsigned char)tail[1]) << 8;
+ /*-fallthrough*/
+ case 1:
+ k1 ^= ((uint32_t)(unsigned char)tail[0]) << 0;
+ k1 *= c1;
+ k1 = rotate_left(k1, r1);
+ k1 *= c2;
+ seed ^= k1;
+ break;
+ }
+
+ seed ^= (uint32_t)len;
+ seed ^= (seed >> 16);
+ seed *= 0x85ebca6b;
+ seed ^= (seed >> 13);
+ seed *= 0xc2b2ae35;
+ seed ^= (seed >> 16);
+
+ return seed;
+}
+
+static uint32_t murmur3_seeded_v1(uint32_t seed, const char *data, size_t len)
{
const uint32_t c1 = 0xcc9e2d51;
const uint32_t c2 = 0x1b873593;
@@ -165,8 +222,14 @@ void fill_bloom_key(const char *data,
int i;
const uint32_t seed0 = 0x293ae76f;
const uint32_t seed1 = 0x7e646e2c;
- const uint32_t hash0 = murmur3_seeded(seed0, data, len);
- const uint32_t hash1 = murmur3_seeded(seed1, data, len);
+ uint32_t hash0, hash1;
+ if (settings->hash_version == 2) {
+ hash0 = murmur3_seeded_v2(seed0, data, len);
+ hash1 = murmur3_seeded_v2(seed1, data, len);
+ } else {
+ hash0 = murmur3_seeded_v1(seed0, data, len);
+ hash1 = murmur3_seeded_v1(seed1, data, len);
+ }
key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t));
for (i = 0; i < settings->num_hashes; i++)
diff --git a/bloom.h b/bloom.h
index 052a993aab..bfe389e29c 100644
--- a/bloom.h
+++ b/bloom.h
@@ -8,9 +8,11 @@ struct commit_graph;
struct bloom_filter_settings {
/*
* The version of the hashing technique being used.
- * We currently only support version = 1 which is
+ * The newest version is 2, which is
* the seeded murmur3 hashing technique implemented
- * in bloom.c.
+ * in bloom.c. Bloom filters of version 1 were created
+ * with prior versions of Git, which had a bug in the
+ * implementation of the hash function.
*/
uint32_t hash_version;
@@ -81,7 +83,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g,
* Not considered to be cryptographically secure.
* Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
*/
-uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len);
+uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len);
void fill_bloom_key(const char *data,
size_t len,
diff --git a/commit-graph.c b/commit-graph.c
index 6c3fbae142..6f9cab181e 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -344,7 +344,6 @@ static int graph_read_bloom_data(const unsigned char *chunk_start,
size_t chunk_size, void *data)
{
struct commit_graph *g = data;
- uint32_t hash_version;
if (chunk_size < BLOOMDATA_CHUNK_HEADER_SIZE) {
warning(_("ignoring too-small changed-path chunk"
@@ -356,10 +355,9 @@ static int graph_read_bloom_data(const unsigned char *chunk_start,
g->chunk_bloom_data = chunk_start;
g->chunk_bloom_data_size = chunk_size;
- hash_version = get_be32(chunk_start);
g->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));
- g->bloom_filter_settings->hash_version = hash_version;
+ g->bloom_filter_settings->hash_version = get_be32(chunk_start);
g->bloom_filter_settings->num_hashes = get_be32(chunk_start + 4);
g->bloom_filter_settings->bits_per_entry = get_be32(chunk_start + 8);
g->bloom_filter_settings->max_changed_paths = DEFAULT_BLOOM_MAX_CHANGES;
@@ -2501,6 +2499,13 @@ int write_commit_graph(struct object_directory *odb,
}
if (!commit_graph_compatible(r))
return 0;
+ if (r->settings.commit_graph_changed_paths_version < -1
+ || r->settings.commit_graph_changed_paths_version > 2) {
+ warning(_("attempting to write a commit-graph, but "
+ "'commitgraph.changedPathsVersion' (%d) is not supported"),
+ r->settings.commit_graph_changed_paths_version);
+ return 0;
+ }
CALLOC_ARRAY(ctx, 1);
ctx->r = r;
@@ -2543,7 +2548,7 @@ int write_commit_graph(struct object_directory *odb,
g = ctx->r->objects->commit_graph;
/* We have changed-paths already. Keep them in the next graph */
- if (g && g->chunk_bloom_data) {
+ if (g && g->bloom_filter_settings) {
ctx->changed_paths = 1;
/* don't propagate the hash_version unless unspecified */
diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c
index 1281e66876..eefc1668c7 100644
--- a/t/helper/test-bloom.c
+++ b/t/helper/test-bloom.c
@@ -49,6 +49,7 @@ static void get_bloom_filter_for_commit(const struct object_id *commit_oid)
static const char *bloom_usage = "\n"
" test-tool bloom get_murmur3 <string>\n"
+" test-tool bloom get_murmur3_seven_highbit\n"
" test-tool bloom generate_filter <string> [<string>...]\n"
" test-tool bloom get_filter_for_commit <commit-hex>\n";
@@ -63,7 +64,13 @@ int cmd__bloom(int argc, const char **argv)
uint32_t hashed;
if (argc < 3)
usage(bloom_usage);
- hashed = murmur3_seeded(0, argv[2], strlen(argv[2]));
+ hashed = murmur3_seeded_v2(0, argv[2], strlen(argv[2]));
+ printf("Murmur3 Hash with seed=0:0x%08x\n", hashed);
+ }
+
+ if (!strcmp(argv[1], "get_murmur3_seven_highbit")) {
+ uint32_t hashed;
+ hashed = murmur3_seeded_v2(0, "\x99\xaa\xbb\xcc\xdd\xee\xff", 7);
printf("Murmur3 Hash with seed=0:0x%08x\n", hashed);
}
diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh
index b567383eb8..c8d84ab606 100755
--- a/t/t0095-bloom.sh
+++ b/t/t0095-bloom.sh
@@ -29,6 +29,14 @@ test_expect_success 'compute unseeded murmur3 hash for test string 2' '
test_cmp expect actual
'
+test_expect_success 'compute unseeded murmur3 hash for test string 3' '
+ cat >expect <<-\EOF &&
+ Murmur3 Hash with seed=0:0xa183ccfd
+ EOF
+ test-tool bloom get_murmur3_seven_highbit >actual &&
+ test_cmp expect actual
+'
+
test_expect_success 'compute bloom key for empty string' '
cat >expect <<-\EOF &&
Hashes:0x5615800c|0x5b966560|0x61174ab4|0x66983008|0x6c19155c|0x7199fab0|0x771ae004|
diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
index 93b8d096cf..a7bf3a7dca 100755
--- a/t/t4216-log-bloom.sh
+++ b/t/t4216-log-bloom.sh
@@ -485,6 +485,33 @@ test_expect_success 'merge graph layers with incompatible Bloom settings' '
test_must_be_empty err
'
+test_expect_success 'ensure Bloom filter with incompatible versions are ignored' '
+ rm "$repo/$graph" &&
+
+ git -C $repo log --oneline --no-decorate -- $CENT >expect &&
+
+ # Compute v1 Bloom filters for commits at the bottom.
+ git -C $repo rev-parse HEAD^ >in &&
+ git -C $repo commit-graph write --stdin-commits --changed-paths \
+ --split <in &&
+
+ # Compute v2 Bloomfilters for the rest of the commits at the top.
+ git -C $repo rev-parse HEAD >in &&
+ git -C $repo -c commitGraph.changedPathsVersion=2 commit-graph write \
+ --stdin-commits --changed-paths --split=no-merge <in &&
+
+ test_line_count = 2 $repo/$chain &&
+
+ git -C $repo log --oneline --no-decorate -- $CENT >actual 2>err &&
+ test_cmp expect actual &&
+
+ layer="$(head -n 1 $repo/$chain)" &&
+ cat >expect.err <<-EOF &&
+ warning: disabling Bloom filters for commit-graph layer $SQ$layer$SQ due to incompatible settings
+ EOF
+ test_cmp expect.err err
+'
+
get_first_changed_path_filter () {
test-tool read-graph bloom-filters >filters.dat &&
head -n 1 filters.dat
@@ -536,6 +563,120 @@ test_expect_success 'version 1 changed-path used when version 1 requested' '
)
'
+test_expect_success 'version 1 changed-path not used when version 2 requested' '
+ (
+ cd highbit1 &&
+ git config --add commitgraph.changedPathsVersion 2 &&
+ test_bloom_filters_not_used "-- another$CENT"
+ )
+'
+
+test_expect_success 'version 1 changed-path used when autodetect requested' '
+ (
+ cd highbit1 &&
+ git config --add commitgraph.changedPathsVersion -1 &&
+ test_bloom_filters_used "-- another$CENT"
+ )
+'
+
+test_expect_success 'when writing another commit graph, preserve existing version 1 of changed-path' '
+ test_commit -C highbit1 c1double "$CENT$CENT" &&
+ git -C highbit1 commit-graph write --reachable --changed-paths &&
+ (
+ cd highbit1 &&
+ git config --add commitgraph.changedPathsVersion -1 &&
+ echo "options: bloom(1,10,7) read_generation_data" >expect &&
+ test-tool read-graph >full &&
+ grep options full >actual &&
+ test_cmp expect actual
+ )
+'
+
+test_expect_success 'set up repo with high bit path, version 2 changed-path' '
+ git init highbit2 &&
+ git -C highbit2 config --add commitgraph.changedPathsVersion 2 &&
+ test_commit -C highbit2 c2 "$CENT" &&
+ git -C highbit2 commit-graph write --reachable --changed-paths
+'
+
+test_expect_success 'check value of version 2 changed-path' '
+ (
+ cd highbit2 &&
+ echo "c01f" >expect &&
+ get_first_changed_path_filter >actual &&
+ test_cmp expect actual
+ )
+'
+
+test_expect_success 'setup make another commit' '
+ # "git log" does not use Bloom filters for root commits - see how, in
+ # revision.c, rev_compare_tree() (the only code path that eventually calls
+ # get_bloom_filter()) is only called by try_to_simplify_commit() when the commit
+ # has one parent. Therefore, make another commit so that we perform the tests on
+ # a non-root commit.
+ test_commit -C highbit2 anotherc2 "another$CENT"
+'
+
+test_expect_success 'version 2 changed-path used when version 2 requested' '
+ (
+ cd highbit2 &&
+ test_bloom_filters_used "-- another$CENT"
+ )
+'
+
+test_expect_success 'version 2 changed-path not used when version 1 requested' '
+ (
+ cd highbit2 &&
+ git config --add commitgraph.changedPathsVersion 1 &&
+ test_bloom_filters_not_used "-- another$CENT"
+ )
+'
+
+test_expect_success 'version 2 changed-path used when autodetect requested' '
+ (
+ cd highbit2 &&
+ git config --add commitgraph.changedPathsVersion -1 &&
+ test_bloom_filters_used "-- another$CENT"
+ )
+'
+
+test_expect_success 'when writing another commit graph, preserve existing version 2 of changed-path' '
+ test_commit -C highbit2 c2double "$CENT$CENT" &&
+ git -C highbit2 commit-graph write --reachable --changed-paths &&
+ (
+ cd highbit2 &&
+ git config --add commitgraph.changedPathsVersion -1 &&
+ echo "options: bloom(2,10,7) read_generation_data" >expect &&
+ test-tool read-graph >full &&
+ grep options full >actual &&
+ test_cmp expect actual
+ )
+'
+
+test_expect_success 'when writing commit graph, do not reuse changed-path of another version' '
+ git init doublewrite &&
+ test_commit -C doublewrite c "$CENT" &&
+ git -C doublewrite config --add commitgraph.changedPathsVersion 1 &&
+ git -C doublewrite commit-graph write --reachable --changed-paths &&
+ for v in -2 3
+ do
+ git -C doublewrite config --add commitgraph.changedPathsVersion $v &&
+ git -C doublewrite commit-graph write --reachable --changed-paths 2>err &&
+ cat >expect <<-EOF &&
+ warning: attempting to write a commit-graph, but ${SQ}commitgraph.changedPathsVersion${SQ} ($v) is not supported
+ EOF
+ test_cmp expect err || return 1
+ done &&
+ git -C doublewrite config --add commitgraph.changedPathsVersion 2 &&
+ git -C doublewrite commit-graph write --reachable --changed-paths &&
+ (
+ cd doublewrite &&
+ echo "c01f" >expect &&
+ get_first_changed_path_filter >actual &&
+ test_cmp expect actual
+ )
+'
+
corrupt_graph () {
test_when_finished "rm -rf $graph" &&
git commit-graph write --reachable --changed-paths &&
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 14/16] object.h: fix mis-aligned flag bits table
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
Bit position 23 is one column too far to the left.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
object.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/object.h b/object.h
index 114d45954d..db25714b4e 100644
--- a/object.h
+++ b/object.h
@@ -62,7 +62,7 @@ void object_array_init(struct object_array *array);
/*
* object flag allocation:
- * revision.h: 0---------10 15 23------27
+ * revision.h: 0---------10 15 23------27
* fetch-pack.c: 01 67
* negotiator/default.c: 2--5
* walker.c: 0-2
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 15/16] commit-graph: reuse existing Bloom filters where possible
From: Taylor Blau @ 2024-01-31 22:52 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
In an earlier commit, a bug was described where it's possible for Git to
produce non-murmur3 hashes when the platform's "char" type is signed,
and there are paths with characters whose highest bit is set (i.e. all
characters >= 0x80).
That patch allows the caller to control which version of Bloom filters
are read and written. However, even on platforms with a signed "char"
type, it is possible to reuse existing Bloom filters if and only if
there are no changed paths in any commit's first parent tree-diff whose
characters have their highest bit set.
When this is the case, we can reuse the existing filter without having
to compute a new one. This is done by marking trees which are known to
have (or not have) any such paths. When a commit's root tree is verified
to not have any such paths, we mark it as such and declare that the
commit's Bloom filter is reusable.
Note that this heuristic only goes in one direction. If neither a commit
nor its first parent have any paths in their trees with non-ASCII
characters, then we know for certain that a path with non-ASCII
characters will not appear in a tree-diff against that commit's first
parent. The reverse isn't necessarily true: just because the tree-diff
doesn't contain any such paths does not imply that no such paths exist
in either tree.
So we end up recomputing some Bloom filters that we don't strictly have
to (i.e. their bits are the same no matter which version of murmur3 we
use). But culling these out is impossible, since we'd have to perform
the full tree-diff, which is the same effort as computing the Bloom
filter from scratch.
But because we can cache our results in each tree's flag bits, we can
often avoid recomputing many filters, thereby reducing the time it takes
to run
$ git commit-graph write --changed-paths --reachable
when upgrading from v1 to v2 Bloom filters.
To benchmark this, let's generate a commit-graph in linux.git with v1
changed-paths in generation order[^1]:
$ git clone git@github.com:torvalds/linux.git
$ cd linux
$ git commit-graph write --reachable --changed-paths
$ graph=".git/objects/info/commit-graph"
$ mv $graph{,.bak}
Then let's time how long it takes to go from v1 to v2 filters (with and
without the upgrade path enabled), resetting the state of the
commit-graph each time:
$ git config commitGraph.changedPathsVersion 2
$ hyperfine -p 'cp -f $graph.bak $graph' -L v 0,1 \
'GIT_TEST_UPGRADE_BLOOM_FILTERS={v} git.compile commit-graph write --reachable --changed-paths'
On linux.git (where there aren't any non-ASCII paths), the timings
indicate that this patch represents a speed-up over recomputing all
Bloom filters from scratch:
Benchmark 1: GIT_TEST_UPGRADE_BLOOM_FILTERS=0 git.compile commit-graph write --reachable --changed-paths
Time (mean ± σ): 124.873 s ± 0.316 s [User: 124.081 s, System: 0.643 s]
Range (min … max): 124.621 s … 125.227 s 3 runs
Benchmark 2: GIT_TEST_UPGRADE_BLOOM_FILTERS=1 git.compile commit-graph write --reachable --changed-paths
Time (mean ± σ): 79.271 s ± 0.163 s [User: 74.611 s, System: 4.521 s]
Range (min … max): 79.112 s … 79.437 s 3 runs
Summary
'GIT_TEST_UPGRADE_BLOOM_FILTERS=1 git.compile commit-graph write --reachable --changed-paths' ran
1.58 ± 0.01 times faster than 'GIT_TEST_UPGRADE_BLOOM_FILTERS=0 git.compile commit-graph write --reachable --changed-paths'
On git.git, we do have some non-ASCII paths, giving us a more modest
improvement from 4.163 seconds to 3.348 seconds, for a 1.24x speed-up.
On my machine, the stats for git.git are:
- 8,285 Bloom filters computed from scratch
- 10 Bloom filters generated as empty
- 4 Bloom filters generated as truncated due to too many changed paths
- 65,114 Bloom filters were reused when transitioning from v1 to v2.
[^1]: Note that this is is important, since `--stdin-packs` or
`--stdin-commits` orders commits in the commit-graph by their pack
position (with `--stdin-packs`) or in the raw input (with
`--stdin-commits`).
Since we compute Bloom filters in the same order that commits appear
in the graph, we must see a commit's (first) parent before we process
the commit itself. This is only guaranteed to happen when sorting
commits by their generation number.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
bloom.c | 90 ++++++++++++++++++++++++++++++++++++++++++--
bloom.h | 1 +
commit-graph.c | 5 +++
object.h | 1 +
t/t4216-log-bloom.sh | 35 ++++++++++++++++-
5 files changed, 128 insertions(+), 4 deletions(-)
diff --git a/bloom.c b/bloom.c
index 323d8012b8..a1c616bc71 100644
--- a/bloom.c
+++ b/bloom.c
@@ -6,6 +6,9 @@
#include "commit-graph.h"
#include "commit.h"
#include "commit-slab.h"
+#include "tree.h"
+#include "tree-walk.h"
+#include "config.h"
define_commit_slab(bloom_filter_slab, struct bloom_filter);
@@ -283,6 +286,73 @@ static void init_truncated_large_filter(struct bloom_filter *filter,
filter->version = version;
}
+#define VISITED (1u<<21)
+#define HIGH_BITS (1u<<22)
+
+static int has_entries_with_high_bit(struct repository *r, struct tree *t)
+{
+ if (parse_tree(t))
+ return 1;
+
+ if (!(t->object.flags & VISITED)) {
+ struct tree_desc desc;
+ struct name_entry entry;
+
+ init_tree_desc(&desc, t->buffer, t->size);
+ while (tree_entry(&desc, &entry)) {
+ size_t i;
+ for (i = 0; i < entry.pathlen; i++) {
+ if (entry.path[i] & 0x80) {
+ t->object.flags |= HIGH_BITS;
+ goto done;
+ }
+ }
+
+ if (S_ISDIR(entry.mode)) {
+ struct tree *sub = lookup_tree(r, &entry.oid);
+ if (sub && has_entries_with_high_bit(r, sub)) {
+ t->object.flags |= HIGH_BITS;
+ goto done;
+ }
+ }
+
+ }
+
+done:
+ t->object.flags |= VISITED;
+ }
+
+ return !!(t->object.flags & HIGH_BITS);
+}
+
+static int commit_tree_has_high_bit_paths(struct repository *r,
+ struct commit *c)
+{
+ struct tree *t;
+ if (repo_parse_commit(r, c))
+ return 1;
+ t = repo_get_commit_tree(r, c);
+ if (!t)
+ return 1;
+ return has_entries_with_high_bit(r, t);
+}
+
+static struct bloom_filter *upgrade_filter(struct repository *r, struct commit *c,
+ struct bloom_filter *filter,
+ int hash_version)
+{
+ struct commit_list *p = c->parents;
+ if (commit_tree_has_high_bit_paths(r, c))
+ return NULL;
+
+ if (p && commit_tree_has_high_bit_paths(r, p->item))
+ return NULL;
+
+ filter->version = hash_version;
+
+ return filter;
+}
+
struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)
{
struct bloom_filter *filter;
@@ -325,9 +395,23 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
filter, graph_pos);
}
- if ((filter->data && filter->len) &&
- (!settings || settings->hash_version == filter->version))
- return filter;
+ if (filter->data && filter->len) {
+ struct bloom_filter *upgrade;
+ if (!settings || settings->hash_version == filter->version)
+ return filter;
+
+ /* version mismatch, see if we can upgrade */
+ if (compute_if_not_present &&
+ git_env_bool("GIT_TEST_UPGRADE_BLOOM_FILTERS", 1)) {
+ upgrade = upgrade_filter(r, c, filter,
+ settings->hash_version);
+ if (upgrade) {
+ if (computed)
+ *computed |= BLOOM_UPGRADED;
+ return upgrade;
+ }
+ }
+ }
if (!compute_if_not_present)
return NULL;
diff --git a/bloom.h b/bloom.h
index bfe389e29c..e3a9b68905 100644
--- a/bloom.h
+++ b/bloom.h
@@ -102,6 +102,7 @@ enum bloom_filter_computed {
BLOOM_COMPUTED = (1 << 1),
BLOOM_TRUNC_LARGE = (1 << 2),
BLOOM_TRUNC_EMPTY = (1 << 3),
+ BLOOM_UPGRADED = (1 << 4),
};
struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
diff --git a/commit-graph.c b/commit-graph.c
index 6f9cab181e..320ac856ca 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1168,6 +1168,7 @@ struct write_commit_graph_context {
int count_bloom_filter_not_computed;
int count_bloom_filter_trunc_empty;
int count_bloom_filter_trunc_large;
+ int count_bloom_filter_upgraded;
};
static int write_graph_chunk_fanout(struct hashfile *f,
@@ -1775,6 +1776,8 @@ static void trace2_bloom_filter_write_statistics(struct write_commit_graph_conte
ctx->count_bloom_filter_trunc_empty);
trace2_data_intmax("commit-graph", ctx->r, "filter-trunc-large",
ctx->count_bloom_filter_trunc_large);
+ trace2_data_intmax("commit-graph", ctx->r, "filter-upgraded",
+ ctx->count_bloom_filter_upgraded);
}
static void compute_bloom_filters(struct write_commit_graph_context *ctx)
@@ -1816,6 +1819,8 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
ctx->count_bloom_filter_trunc_empty++;
if (computed & BLOOM_TRUNC_LARGE)
ctx->count_bloom_filter_trunc_large++;
+ } else if (computed & BLOOM_UPGRADED) {
+ ctx->count_bloom_filter_upgraded++;
} else if (computed & BLOOM_NOT_COMPUTED)
ctx->count_bloom_filter_not_computed++;
ctx->total_bloom_filter_data_size += filter
diff --git a/object.h b/object.h
index db25714b4e..2e5e08725f 100644
--- a/object.h
+++ b/object.h
@@ -75,6 +75,7 @@ void object_array_init(struct object_array *array);
* commit-reach.c: 16-----19
* sha1-name.c: 20
* list-objects-filter.c: 21
+ * bloom.c: 2122
* builtin/fsck.c: 0--3
* builtin/gc.c: 0
* builtin/index-pack.c: 2021
diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
index a7bf3a7dca..823d1cf773 100755
--- a/t/t4216-log-bloom.sh
+++ b/t/t4216-log-bloom.sh
@@ -222,6 +222,10 @@ test_filter_trunc_large () {
grep "\"key\":\"filter-trunc-large\",\"value\":\"$1\"" $2
}
+test_filter_upgraded () {
+ grep "\"key\":\"filter-upgraded\",\"value\":\"$1\"" $2
+}
+
test_expect_success 'correctly report changes over limit' '
git init limits &&
(
@@ -656,7 +660,13 @@ test_expect_success 'when writing another commit graph, preserve existing versio
test_expect_success 'when writing commit graph, do not reuse changed-path of another version' '
git init doublewrite &&
test_commit -C doublewrite c "$CENT" &&
+
git -C doublewrite config --add commitgraph.changedPathsVersion 1 &&
+ GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
+ git -C doublewrite commit-graph write --reachable --changed-paths &&
+ test_filter_computed 1 trace2.txt &&
+ test_filter_upgraded 0 trace2.txt &&
+
git -C doublewrite commit-graph write --reachable --changed-paths &&
for v in -2 3
do
@@ -667,8 +677,13 @@ test_expect_success 'when writing commit graph, do not reuse changed-path of ano
EOF
test_cmp expect err || return 1
done &&
+
git -C doublewrite config --add commitgraph.changedPathsVersion 2 &&
- git -C doublewrite commit-graph write --reachable --changed-paths &&
+ GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
+ git -C doublewrite commit-graph write --reachable --changed-paths &&
+ test_filter_computed 1 trace2.txt &&
+ test_filter_upgraded 0 trace2.txt &&
+
(
cd doublewrite &&
echo "c01f" >expect &&
@@ -677,6 +692,24 @@ test_expect_success 'when writing commit graph, do not reuse changed-path of ano
)
'
+test_expect_success 'when writing commit graph, reuse changed-path of another version where possible' '
+ git init upgrade &&
+
+ test_commit -C upgrade base no-high-bits &&
+
+ git -C upgrade config --add commitgraph.changedPathsVersion 1 &&
+ GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
+ git -C upgrade commit-graph write --reachable --changed-paths &&
+ test_filter_computed 1 trace2.txt &&
+ test_filter_upgraded 0 trace2.txt &&
+
+ git -C upgrade config --add commitgraph.changedPathsVersion 2 &&
+ GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
+ git -C upgrade commit-graph write --reachable --changed-paths &&
+ test_filter_computed 0 trace2.txt &&
+ test_filter_upgraded 1 trace2.txt
+'
+
corrupt_graph () {
test_when_finished "rm -rf $graph" &&
git commit-graph write --reachable --changed-paths &&
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* [PATCH v6 16/16] bloom: introduce `deinit_bloom_filters()`
From: Taylor Blau @ 2024-01-31 22:53 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio C Hamano, Jonathan Tan, SZEDER Gábor
In-Reply-To: <cover.1706741516.git.me@ttaylorr.com>
After we are done using Bloom filters, we do not currently clean up any
memory allocated by the commit slab used to store those filters in the
first place.
Besides the bloom_filter structures themselves, there is mostly nothing
to free() in the first place, since in the read-only path all Bloom
filter's `data` members point to a memory mapped region in the
commit-graph file itself.
But when generating Bloom filters from scratch (or initializing
truncated filters) we allocate additional memory to store the filter's
data.
Keep track of when we need to free() this additional chunk of memory by
using an extra pointer `to_free`. Most of the time this will be NULL
(indicating that we are representing an existing Bloom filter stored in
a memory mapped region). When it is non-NULL, free it before discarding
the Bloom filters slab.
Suggested-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>
---
bloom.c | 16 +++++++++++++++-
bloom.h | 3 +++
commit-graph.c | 4 ++++
3 files changed, 22 insertions(+), 1 deletion(-)
diff --git a/bloom.c b/bloom.c
index a1c616bc71..dbcc0f4f50 100644
--- a/bloom.c
+++ b/bloom.c
@@ -92,6 +92,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g,
sizeof(unsigned char) * start_index +
BLOOMDATA_CHUNK_HEADER_SIZE);
filter->version = g->bloom_filter_settings->hash_version;
+ filter->to_free = NULL;
return 1;
}
@@ -264,6 +265,18 @@ void init_bloom_filters(void)
init_bloom_filter_slab(&bloom_filters);
}
+static void free_one_bloom_filter(struct bloom_filter *filter)
+{
+ if (!filter)
+ return;
+ free(filter->to_free);
+}
+
+void deinit_bloom_filters(void)
+{
+ deep_clear_bloom_filter_slab(&bloom_filters, free_one_bloom_filter);
+}
+
static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED,
const struct hashmap_entry *eptr,
const struct hashmap_entry *entry_or_key,
@@ -280,7 +293,7 @@ static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED,
static void init_truncated_large_filter(struct bloom_filter *filter,
int version)
{
- filter->data = xmalloc(1);
+ filter->data = filter->to_free = xmalloc(1);
filter->data[0] = 0xFF;
filter->len = 1;
filter->version = version;
@@ -482,6 +495,7 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
filter->len = 1;
}
CALLOC_ARRAY(filter->data, filter->len);
+ filter->to_free = filter->data;
hashmap_for_each_entry(&pathmap, &iter, e, entry) {
struct bloom_key key;
diff --git a/bloom.h b/bloom.h
index e3a9b68905..d20e64bfbb 100644
--- a/bloom.h
+++ b/bloom.h
@@ -56,6 +56,8 @@ struct bloom_filter {
unsigned char *data;
size_t len;
int version;
+
+ void *to_free;
};
/*
@@ -96,6 +98,7 @@ void add_key_to_filter(const struct bloom_key *key,
const struct bloom_filter_settings *settings);
void init_bloom_filters(void);
+void deinit_bloom_filters(void);
enum bloom_filter_computed {
BLOOM_NOT_COMPUTED = (1 << 0),
diff --git a/commit-graph.c b/commit-graph.c
index 320ac856ca..6f5f8f158f 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -831,6 +831,7 @@ void close_commit_graph(struct raw_object_store *o)
return;
clear_commit_graph_data_slab(&commit_graph_data_slab);
+ deinit_bloom_filters();
free_commit_graph(o->commit_graph);
o->commit_graph = NULL;
}
@@ -2649,6 +2650,9 @@ int write_commit_graph(struct object_directory *odb,
res = write_commit_graph_file(ctx);
+ if (ctx->changed_paths)
+ deinit_bloom_filters();
+
if (ctx->split)
mark_commit_graphs(ctx);
--
2.43.0.509.g253f65a7fc
^ permalink raw reply related
* Re: [PATCH] ci: update FreeBSD cirrus job
From: Junio C Hamano @ 2024-01-31 22:57 UTC (permalink / raw)
To: Carlo Marcelo Arenas Belón; +Cc: git, Johannes.Schindelin
In-Reply-To: <20240131191325.33228-1-carenas@gmail.com>
Carlo Marcelo Arenas Belón <carenas@gmail.com> writes:
> This will be upgraded again once 13.3 is released to avoid furtheer
I've typofixed this to "further" while queuing; no need to resend
the patch only to fix it.
^ permalink raw reply
* Re: [PATCH v2 3/3] t/Makefile: get UNIT_TESTS list from C sources
From: Junio C Hamano @ 2024-01-31 22:58 UTC (permalink / raw)
To: Jeff King
Cc: git, Phillip Wood, SZEDER Gábor, Adam Dinwoodie,
Patrick Steinhardt
In-Reply-To: <20240130054037.GC166699@coredump.intra.peff.net>
Jeff King <peff@peff.net> writes:
> 1. It will notice if we failed to build one or more unit-tests for
> some reason (wheras the current code just runs whatever made it to
> the bin/ directory).
"whereas"
> would be true even if we had acess to the top-level's UNIT_TEST_PROGRAMS
"access"
I've typofixed them while queuing; no need to resend the patch only
to fix it.
Thanks.
^ permalink raw reply
* Re: [PATCH 2/2] Makefile: simplify output of the libpath_template
From: Junio C Hamano @ 2024-01-31 22:59 UTC (permalink / raw)
To: git
In-Reply-To: <20240131174220.4160560-3-gitster@pobox.com>
Junio C Hamano <gitster@pobox.com> writes:
> by a directory name. This way,
>
> $(call libpath_tempate,$(SOMELIBDIR))
"libpath_template" obviously.
^ permalink raw reply
* Re: [PATCH v3 02/10] trailer: move interpret_trailers() to interpret-trailers.c
From: Linus Arver @ 2024-01-31 23:20 UTC (permalink / raw)
To: Junio C Hamano, Linus Arver via GitGitGadget
Cc: git, Christian Couder, Emily Shaffer, Josh Steadmon,
Randall S. Becker
In-Reply-To: <xmqqy1c55o6a.fsf@gitster.g>
Junio C Hamano <gitster@pobox.com> writes:
> "Linus Arver via GitGitGadget" <gitgitgadget@gmail.com> writes:
>
>> From: Linus Arver <linusa@google.com>
>>
>> The interpret-trailers.c builtin is the only place we need to call
>> interpret_trailers(), so move its definition there.
>
> A few helper functions that are only called by interpret_trailers()
> are also moved, naturally. I would have less surprised to see
> the addtion near the beginning of builtin/interpret-trailers.c if
> this part said:
>
> ..., so move its definition there, together with a few helper
> functions called only by it, and remove its external declaration
> from <trailer.h>.
Will add in next reroll.
>> Delete the corresponding declaration from trailer.h, which then forces
>> us to expose the working innards of that function.
>
> This was a bit confusing, at least to me. The reason why several
> other helper functions that are called by interpret_trailers() need
> to be declared in trailer.h is not because the declaration of
> interpret_trailers() is deleted from trailer.h but that is how I
> read the above.
>
> Several helper functions that are called by interpret_trailers()
> remain in trailer.c because other callers in the same file still
> call them, so add declaration for them to <trailer.h>.
I've adopted most of this language in the next reroll to make the
reasoning a bit easier to follow. Thanks.
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox