[PATCH v6 0/7] Changed path filter hash fix and version bump
- From
- Jonathan Tan <jonathantanmy@google.com>
- Date
- Jul 20, 2023, 21:46 UTC
- Message-ID
- <cover.1689889382.git.jonathantanmy@google.com>
- In-Reply-To
- <cover.1684790529.git.jonathantanmy@google.com>
Thanks, Junio and Taylor, for your reviews. I have included Taylor's patches in this patch set.
There seemed to be some merge conflicts when I tried to apply the patches Taylor provided on the base that I built my patches on (that is, the base of jt/path-filter-fix, namely, maint-2.40), so I have rebased all my patches onto latest master.
Jonathan Tan (4): gitformat-commit-graph: describe version 2 of BDAT t4216: test changed path filters with high bit paths repo-settings: introduce commitgraph.changedPathsVersion commit-graph: new filter ver. that fixes murmur3
Taylor Blau (3): 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
Documentation/config/commitgraph.txt | 26 +++++- Documentation/gitformat-commit-graph.txt | 9 +- bloom.c | 75 ++++++++++++++-- bloom.h | 13 ++- commit-graph.c | 33 +++++-- oss-fuzz/fuzz-commit-graph.c | 2 +- repo-settings.c | 6 +- repository.h | 2 +- t/helper/test-bloom.c | 9 +- t/helper/test-read-graph.c | 67 ++++++++++++--- t/t0095-bloom.sh | 8 ++ t/t4216-log-bloom.sh | 104 +++++++++++++++++++++++ 12 files changed, 315 insertions(+), 39 deletions(-)
Range-diff against v5:
1: efe7f40fed = 1: 3ce6090a4d gitformat-commit-graph: describe version 2 of BDAT
-: ---------- > 2: 1955734d1f t/helper/test-read-graph.c: extract `dump_graph_info()`
-: ---------- > 3: 4cf7c2f634 bloom.h: make `load_bloom_filter_from_graph()` public
-: ---------- > 4: 47b55758e6 t/helper/test-read-graph: implement `bloom-filters` mode
2: f684d07971 ! 5: 5276e6a90e t4216: test changed path filters with high bit paths
@@ t/t4216-log-bloom.sh: test_expect_success 'Bloom generation backfills empty comm
)
'
-+get_bdat_offset () {
-+ perl -0777 -ne \
-+ 'print unpack("N", "$1") if /BDAT\0\0\0\0(....)/ or exit 1' \
-+ .git/objects/info/commit-graph
-+}
-+
+get_first_changed_path_filter () {
-+ BDAT_OFFSET=$(get_bdat_offset) &&
-+ perl -0777 -ne \
-+ 'print unpack("H*", substr($_, '$BDAT_OFFSET' + 12, 2))' \
-+ .git/objects/info/commit-graph
++ test-tool read-graph bloom-filters >filters.dat &&
++ head -n 1 filters.dat
+}
+
+# chosen to be the same under all Unicode normalization forms
@@ t/t4216-log-bloom.sh: test_expect_success 'Bloom generation backfills empty comm
+
+test_expect_success 'setup check value of version 1 changed-path' '
+ (cd highbit1 &&
-+ printf "52a9" >expect &&
++ echo "52a9" >expect &&
+ get_first_changed_path_filter >actual &&
+ test_cmp expect actual)
+'
3: 2fadd87063 ! 6: dc3f6d2d4f repo-settings: introduce commitgraph.changedPathsVersion
@@ Documentation/config/commitgraph.txt: commitGraph.maxNewFilters::
- 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 changedPathsVersion=-1 if true, and
-+ changedPathsVersion=0 if false.
++ 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. Any changed-path Bloom filters on disk that do not
-+ match the version set in this config variable will be ignored.
++ write. May be -1, 0 or 1.
++
+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 write version 1 Bloom filters when instructed to write.
++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.
@@ commit-graph.c: struct commit_graph *parse_commit_graph(struct repo_settings *s,
}
- if (s->commit_graph_read_changed_paths) {
-+ if (s->commit_graph_changed_paths_version != 0) {
++ if (s->commit_graph_changed_paths_version) {
pair_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES,
&graph->chunk_bloom_indexes);
read_chunk(cf, GRAPH_CHUNKID_BLOOMDATA,
@@ repo-settings.c: void prepare_repo_settings(struct repository *r)
int value;
const char *strval;
int manyfiles;
-+ int readChangedPaths;
++ int read_changed_paths;
if (!r->gitdir)
BUG("Cannot add settings for uninitialized repository");
@@ repo-settings.c: void prepare_repo_settings(struct repository *r)
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", &readChangedPaths, 1);
++ repo_cfg_bool(r, "commitgraph.readchangedpaths", &read_changed_paths, 1);
+ repo_cfg_int(r, "commitgraph.changedpathsversion",
+ &r->settings.commit_graph_changed_paths_version,
-+ readChangedPaths ? -1 : 0);
++ 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);
@@ repository.h: struct repo_settings {
- int commit_graph_read_changed_paths;
+ int commit_graph_changed_paths_version;
int gc_write_commit_graph;
- int gc_cruft_packs;
int fetch_write_commit_graph;
+ int command_requires_full_index;
4: e31711ae85 ! 7: 6e2d797406 commit-graph: new filter ver. that fixes murmur3
@@ Commit message
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 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.
+ 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
@@ Documentation/config/commitgraph.txt: 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. Any changed-path Bloom filters on disk that do not
-+ write. May be -1, 0, 1, or 2. Any changed-path Bloom filters on disk that do not
- match the version set in this config variable will be ignored.
+- write. May be -1, 0 or 1.
++ write. May be -1, 0, 1, or 2.
+
Defaults to -1.
+ +
+@@ Documentation/config/commitgraph.txt: 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.
## bloom.c ##
-@@ bloom.c: static int load_bloom_filter_from_graph(struct commit_graph *g,
+@@ bloom.c: 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
*/
@@ bloom.c: void fill_bloom_key(const char *data,
const uint32_t seed1 = 0x7e646e2c;
- const uint32_t hash0 = murmur3_seeded(seed0, data, len);
- const uint32_t hash1 = murmur3_seeded(seed1, data, len);
-+ const uint32_t hash0 = (settings->hash_version == 2
-+ ? murmur3_seeded_v2 : murmur3_seeded_v1)(seed0, data, len);
-+ const uint32_t hash1 = (settings->hash_version == 2
-+ ? murmur3_seeded_v2 : murmur3_seeded_v1)(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++)
## bloom.h ##
-@@ bloom.h: struct repository;
+@@ bloom.h: struct commit_graph;
struct bloom_filter_settings {
/*
* The version of the hashing technique being used.
@@ bloom.h: struct repository;
*/
uint32_t hash_version;
-@@ bloom.h: struct bloom_key {
+@@ bloom.h: 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
*/
@@ commit-graph.c: static int graph_read_oid_lookup(const unsigned char *chunk_star
return 0;
}
-+struct graph_read_bloom_data_data {
++struct graph_read_bloom_data_context {
+ struct commit_graph *g;
+ int *commit_graph_changed_paths_version;
+};
@@ commit-graph.c: static int graph_read_oid_lookup(const unsigned char *chunk_star
size_t chunk_size, void *data)
{
- struct commit_graph *g = data;
-+ struct graph_read_bloom_data_data *d = data;
-+ struct commit_graph *g = d->g;
++ struct graph_read_bloom_data_context *c = data;
++ struct commit_graph *g = c->g;
uint32_t hash_version;
g->chunk_bloom_data = chunk_start;
hash_version = get_be32(chunk_start);
- if (hash_version != 1)
-+ if (*d->commit_graph_changed_paths_version == -1) {
-+ *d->commit_graph_changed_paths_version = hash_version;
-+ } else if (hash_version != *d->commit_graph_changed_paths_version) {
- return 0;
+- return 0;
++ 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->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));
@@ commit-graph.c: static int graph_read_oid_lookup(const unsigned char *chunk_star
@@ commit-graph.c: struct commit_graph *parse_commit_graph(struct repo_settings *s,
}
- if (s->commit_graph_changed_paths_version != 0) {
-+ struct graph_read_bloom_data_data data = {
+ 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
+ };
@@ commit-graph.c: struct commit_graph *parse_commit_graph(struct repo_settings *s,
&graph->chunk_bloom_indexes);
read_chunk(cf, GRAPH_CHUNKID_BLOOMDATA,
- graph_read_bloom_data, graph);
-+ graph_read_bloom_data, &data);
++ graph_read_bloom_data, &context);
}
if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) {
@@ 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: get_bdat_offset () {
- .git/objects/info/commit-graph
- }
-
-+get_changed_path_filter_version () {
-+ BDAT_OFFSET=$(get_bdat_offset) &&
-+ perl -0777 -ne \
-+ 'print unpack("H*", substr($_, '$BDAT_OFFSET', 4))' \
-+ .git/objects/info/commit-graph
-+}
-+
- get_first_changed_path_filter () {
- BDAT_OFFSET=$(get_bdat_offset) &&
- perl -0777 -ne \
@@ t/t4216-log-bloom.sh: test_expect_success 'set up repo with high bit path, version 1 changed-path' '
git -C highbit1 commit-graph write --reachable --changed-paths
'
@@ t/t4216-log-bloom.sh: test_expect_success 'set up repo with high bit path, versi
-test_expect_success 'setup check value of version 1 changed-path' '
+test_expect_success 'check value of version 1 changed-path' '
(cd highbit1 &&
- printf "52a9" >expect &&
+ echo "52a9" >expect &&
get_first_changed_path_filter >actual &&
@@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when version 1 requested' '
test_bloom_filters_used "-- $CENT")
@@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers
+ git -C highbit1 commit-graph write --reachable --changed-paths &&
+ (cd highbit1 &&
+ git config --add commitgraph.changedPathsVersion -1 &&
-+ printf "00000001" >expect &&
-+ get_changed_path_filter_version >actual &&
++ echo "options: bloom(1,10,7) read_generation_data" >expect &&
++ test-tool read-graph >full &&
++ grep options full >actual &&
+ test_cmp expect actual)
+'
+
@@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers
+
+test_expect_success 'check value of version 2 changed-path' '
+ (cd highbit2 &&
-+ printf "c01f" >expect &&
++ echo "c01f" >expect &&
+ get_first_changed_path_filter >actual &&
+ test_cmp expect actual)
+'
@@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers
+ git -C highbit2 commit-graph write --reachable --changed-paths &&
+ (cd highbit2 &&
+ git config --add commitgraph.changedPathsVersion -1 &&
-+ printf "00000002" >expect &&
-+ get_changed_path_filter_version >actual &&
++ echo "options: bloom(2,10,7) read_generation_data" >expect &&
++ test-tool read-graph >full &&
++ grep options full >actual &&
+ test_cmp expect actual)
+'
+-- 2.41.0.487.g6d72f3e995-goog