RFC patch, 6 partsbloom: reuse existing Bloom filters when possible during upgrade

This series is based off of 'jt/path-filter-fix'.

These few patches implement an idea that we discussed in [1], where we attempt to reuse existing Bloom filters during an upgrade from v1 to v2 Bloom filters while rewriting the commit-graph.

The core idea is that Bloom filters are reusable when there aren't any non-ASCII paths in a commit's tree-diff against its first parent (or the empty tree, if none exists). If we assume that a commit's tree-diff meets those conditions, we can't conclude anything about whether either tree contains non-ASCII characters, since they could be unmodified on either side and thus excluded from the tree-diff.

But assuming the RHS (that there aren't any non-ASCII characters present in the tree's path set) *does* give us that there aren't any such paths present in the first-parent tree diff, either.

This series checks whether or not commits meet that criteria, and reuses the existing Bloom filter (if one exists) when possible. In practice, we end up visiting relatively few trees, since we mark trees we've already visited.

On both linux.git and git.git, this series gives a significant speed-up when upgrading Bloom filters from v1 to v2. On linux.git:

    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 (where we do have some non-ASCII paths), the change goes from 4.163 seconds to 3.348 seconds, for a 1.24x speed-up.

I'm sending this as an RFC, since we are in the middle of the -rc phase, and 'jt/path-filter-fix' isn't expected[2] to merge into 'master' until we're on the other side of 2.42.

The structure of this series is as follows:

  - The first three patches prepare to load the `BDAT` chunk, even when
    the graph's Bloom filter settings are incompatible with the value in
    `commitGraph.changedPathsVersion`.
  - The fourth patch begins loading `BDAT` chunks unconditionally.
  - The fifth patch is a clean-up.
  - The sixth and final patch implements the approach discussed above.

Thanks in advance for your thoughts and review :-).

[1]: https://lore.kernel.org/git/ZMKvsObx+uaKA8zF@nand.local/ [2]: https://lore.kernel.org/git/xmqqy1it6ykm.fsf@gitster.g/

Taylor Blau (6):
  bloom: annotate filters with hash version
  bloom: prepare to discard incompatible Bloom filters
  t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`
  commit-graph.c: unconditionally load Bloom filters
  object.h: fix mis-aligned flag bits table
  commit-graph: reuse existing Bloom filters where possible

 bloom.c              | 117 +++++++++++++++++++++++++++++++++++++++++--
 bloom.h              |  22 +++++++-
 commit-graph.c       |  24 +++++----
 object.h             |   3 +-
 t/t4216-log-bloom.sh |  49 ++++++++++++++++--
 5 files changed, 195 insertions(+), 20 deletions(-)

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 `commitGraph.changedPathVersion` 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(-)

In 9e4df4da07 (commit-graph: new filter ver. that fixes murmur3, 2023-08-01), 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 | 19 ++++++++++---------
 1 file changed, 10 insertions(+), 9 deletions(-)

Taylor Blau <me@ttaylorr.com> writes:

Lots of things to notice in this patch, but the summary is that this patch looks correct.

Here, we remove (1) the autodetection of changed paths version and (2) the storage of the result of that autodetection. (1) is restored in a subsequent code hunk, but (2) is never restored.

Prior to this patch set, we needed (2) because we only wanted to load Bloom filters that match a given version, so if we autodetected a version, that version must be in effect for all future loads (which is why we needed to store that result immediately). But with this patch set, we support the loading of Bloom filters of varying versions, so storing it immediately is no longer needed.

(Also, I don't think we need the commit_graph_changed_paths_version variable anymore.)

As stated in the commit message, normalization of the hash version is performed later.

Here is where the autodetection is restored.

Prior to this patch set, this part of the code does not perform autodetection - every hash_version in memory matches the version in commit_graph_changed_paths_version, so we're just copying over the value in that variable. But the nature of this part of the code has changed due to this patch set: all the g->bloom_filter_settings in memory may not have the same hash version, and may not match what the user specified in config. To compensate, we are more selective in what we propagate from g->bloom_filter_settings.

And here we restore the normalization.

Thanks - up to here looks good.

On Fri, Aug 11, 2023 at 03:00:30PM -0700, Jonathan Tan wrote:

Thanks for the detailed analysis here. This is definitely the patch that I was most nervous about while writing, but I appreciate the second set of eyes.

Great catch, thanks. I cleaned that up in a separate commit after this one, since I think that this patch is already intricate enough.

Thanks, Taylor

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(-)

Taylor Blau <me@ttaylorr.com> writes:

s/disabled/version incompatibility/, I think.

On Fri, Aug 11, 2023 at 02:48:06PM -0700, Jonathan Tan wrote:

Well spotted, thanks.

Thanks, Taylor

Taylor Blau <me@ttaylorr.com> writes:

I missed this the last time, but this should match what fill_bloom_key() does. Use get_bloom_filter_settings(), then compare filter->version to version 2 if hash_version is 2, and to version 1 otherwise.

Everything else looks good.
 

On Thu, Aug 24, 2023 at 03:20:51PM -0700, Jonathan Tan wrote:

I'm not sure I'm following. Are you saying that we should use get_bloom_filter_settings() instead of reading the value from r->settings directly?

Hmm. I think we're already doing the right thing here, no? IIUC, you're saying to do something like:

    struct bloom_filter_settings *s = get_bloom_filter_settings(r);
    struct bloom_filter *f = get_or_compute_bloom_filter(r, c, ...);
    int hash_version;

    if (!f)
      return NULL;

    prepare_repo_settings(r);
    hash_version = r->settings.commit_graph_changed_paths_version;

    if (!(hash_version == -1 || hash_version == s->hash_version))
      return NULL; /* incompatible */
    return f;

?

If so, I think that we're already OK here, since s->hash_version is always going to take the same value as f->version, since f->version is assigned in bloom.c::load_bloom_filter_from_graph(), which does:

    filter->version = g->bloom_filter_settings->hash_version;

Or are we talking about two different things entirely? ;-)

Thanks, Taylor

Taylor Blau <me@ttaylorr.com> writes:

Ah, sorry for not being clear. What I meant is in how you compute hash_version after we have found that filter is not NULL.

Up to here is fine.

Instead of doing this, do this (well, move the struct declaration to the top):

  struct bloom_filter_settings *s = get_bloom_filter_settings(r);
  hash_version = s->hash_version == 2 ? 2 : 1;
  

No need for the comparison to -1 here.

This is fine.

On Thu, Aug 24, 2023 at 04:05:27PM -0700, Jonathan Tan wrote:

Do we need this normalization? We assign s->hash_version in commit-graph.c::graph_read_bloom_data() by reading it from the start of the BDAT chunk, so this should only ever be 1 or 2.

I'm not sure I understand your suggestion. When we fetch the filter from get_or_compute_bloom_filter(), we have filter->version set to the hash_version from the containing graph's Bloom filter settings.

So (besides the normalization), I would think that:

    struct bloom_filter_settings *s = get_bloom_filter_settings(r);
    struct bloom_filter *f = get_bloom_filter(...);

    assert(s->hash_version == f->version);

would hold.

I think the check that we want to make is instead: is this Bloom filter's version (or equivalently, the hash version indicated by that graph's BDAT chunk) something that we can read? And I think "what we can read" here is dictated by the commit_graph_changed_paths_version member of our repository_settings, no?

Thanks, Taylor

Taylor Blau <me@ttaylorr.com> writes:

I'm not sure offhand if we do...I wrote it this way to match fill_bloom_key(), but fill_bloom_key() was written in that way because it was the clearest, not specifically because it needed to normalize.

My mention to avoid the comparison to -1 was just for completeness
- since we're normalizing the value of hash_version to 1 or 2, we no
longer need to compare it to -1.

As for whether s->hash_version is always equal to f->version, I think that it may not be true if for some reason, there are multiple commit graph files on disk, not all with the same Bloom filter version.

I think it's not "something that we can read" (eventually, we can read all versions, we just treat them differently) but "the version that fill_bloom_key" will use. We don't want this function to produce a Bloom filter of version X and then have the calling code subsequently use it with a Bloom key of version Y.

I don't think commit_graph_changed_paths_version always dictates something - it could be -1 (which you have probably seen, since you check it against -1 in the current version of the patch). One of the points of my suggestion is to avoid this field completely.

On Tue, Aug 29, 2023 at 09:49:26AM -0700, Jonathan Tan wrote:

Apologies for not quite grokking this, but I am still somewhat confused.

Suppose we applied something like your suggestion on top of this patch, like so:

--- 8< ---

Here are answers to your questions, but I'll also reply to the latest version stating that I'm OK with this patch set being merged (with my reasons).

Taylor Blau <me@ttaylorr.com> writes:

Ah, I discovered this independently too. I think it happens when we write version 2 Bloom filters to a repo that has no Bloom filters currently. So, r->settings.commit_graph_changed_paths_version is set to 2, but settings is NULL. I think the solution has to be a combination of both (use commit_graph_changed_paths_version, but if it is -1, check get_bloom_filter_settings()). But having said that, as I said above, we can go with what you have currently.

But this is my contention - sometimes commitGraph.changedPathsVersion is -1, so we need to find out which version is readable from elsewhere.

Yes, except add "or autodetected from the first commit graph file that we read if nothing is specified in commitGraph.changedPathsVersion" to the end.

By "emit" do you mean write filters to disk? If yes, I'm worried about reading them, not writing them - for example, when running "git log" with a path. I am worried precisely about the commit-graph chain in which different layers have different Bloom settings, yes.

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(-)

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 "filter" 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(-)

Taylor Blau <me@ttaylorr.com> writes:

You mean "version", I think.

We might want to shrink the sizes of len (we have a changed path limit so we know exactly how big Bloom filters can get) and version so that this struct doesn't take up more space. But if other reviewers think that this is OK, I'm fine with that.

Another thing that we might want to track is whether the Bloom filter is a reference to an existing buffer (and thus does not need to be freed) or a reference to a malloc-ed buffer that we must free. But both before and after this patch set, a malloc-ed buffer is never overridden by a reference-to-existing-buffer, so we should still be fine for now. (This patch set does add a scenario in which a reference-to-existing buffer is overridden by a malloc-ed buffer, but that's the only new scenario.)

On Fri, Aug 11, 2023 at 02:46:51PM -0700, Jonathan Tan wrote:

Oops, yes -- I'm not sure how my editor tab-completed "version" there, but oh, well :-).

I think that making len a size_t here is an appropriate choice. Even though the maximum length of a Bloom filter is well below the 2^64-1 threshold, we are often looking at a memory-mapped region here, so keeping track of it with a size_t / off_t seems reasonable to me.

Yeah, I think there is some opportunity for clean-up here. I'll take a look...

Thanks, Taylor

On Thu, Aug 17, 2023 at 03:55:06PM -0400, Taylor Blau wrote:

This ended up being pretty reasonable. I'm not sure whether I should include it here or not, since any leaks in the Bloom subsystem are definitely not new as of this series.

But the patch is relatively straightforward anyway, so I think throwing it on the end would be OK:

--- 8< ---

In 9e4df4da07 (commit-graph: new filter ver. that fixes murmur3, 2023-08-01), 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

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, 127 insertions(+), 5 deletions(-)

Taylor Blau <me@ttaylorr.com> writes:

There's a part in this function that's untouched by the diff that computes and stores a new Bloom filter if it was not possible to upgrade the filter (look at the part where filter->data is calloc-ed). That part unconditionally overrides the existing filter->data, which may at that point contain genuine data (a Bloom filter that does not match the version we want). Right now this is fine because all overrides that we do involve overriding references to existing buffers, so we do not need to free anything.

Taylor Blau <me@ttaylorr.com> writes:

My main concern is that this modifies the code somewhat pervasively (tracking the version of Bloom filters and removing assumptions about what Bloom filter versions are in memory) in return for what I think is a small speedup, when considering that we will perform this operation only once for a given repo. I'll defer to server operators on this (or other people handling large numbers of repos), though.

Putting that concern aside, I've reviewed the code and assuming that we're OK with modifying the code in this way, this patch set looks good to me, and hopefully my review will be of some help.

On Fri, Aug 11, 2023 at 03:13:37PM -0700, Jonathan Tan wrote:

Yeah, I think that this is certainly on the riskier side of things. But I have confidence in our test coverage here, and feel better with your thorough review.

FWIW, I think that the speed-up is worthwhile (though I'm obviously biased here). When we were rolling out changed-path Bloom filters to repositories on GitHub.com, it was apparent that computing them from scratch in a single shot was infeasible. This led to 809e0327f5 (builtin/commit-graph.c: introduce '--max-new-filters=<n>', 2020-09-18).

That would of course still save us here if we didn't have an upgrade path, since each recomputed filter would count against the maximum number we can generate in a single run.

We could introduce a configuration knob, but I'd rather avoid it if possible. That can also be done on top in a later patch, which should be easy enough to do if we hear of a compelling use-case for wanting to disable the upgrade path here.

Thanks very much -- it was more than helpful :-). I'll collect up this and your previous patches (as we have discussed off-list) and tie everything together in a single series for the maintainer.

Thanks, Taylor