| Message ID | 47ba89c565d3383a8a14272fe52ac274be82d0be.1689283789.git.jonathantanmy@google.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | Changed path filter hash fix and version bump | expand |
On Thu, Jul 13, 2023 at 02:42:11PM -0700, Jonathan Tan wrote: > 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 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. I think that you make a worthwhile point that the existing implementation is internally consistent, but doesn't actually implement a conventional murmur3. I wonder if it's worth being explicit where you mention its internal consistency to say that the existing implementation would never cause us to produce wrong results, but wouldn't be readable by other off-the-shelf implementations of murmur3. (To be clear, I think that you already make this point, I'm just suggesting that it may be worth spelling it out even more explicitly than what is written above). > 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. Makes sense. > 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. Hmm. I think in the general case that is true, but I wonder if there's a shortcut we could take for trees that are known to not have *any* characters with their high-order bits set. That is, if we scan both of the first parent's trees and determine that no such paths exist, the contents of the Bloom filter would be the same in either version, right? I think that that would be faster than recomputing all filters from scratch. In either case, we have to load the whole tree. But if we can quickly scan (and cache our results by setting some bit--indicating the absence of paths with characters having their highest bit set--on the tree objects' `flags` field), then we should be able to copy forward the existing representation of the filter. I think the early checks would be more expensive, since in the worst case you have to walk the entire tree, only to realize that you actually wanted to compute a first-parent tree diff, meaning you have to essentially repeat the whole walk over again. But for repositories that have few or no commits whose Bloom filters need computing, I think it would be significantly faster, since many of the sub-trees wouldn't need to be visited again. > 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. Hmm. Interesting, I'd love to know more about what you were doing that produced the segfault. I think it would be worth it to prove to ourselves that this segfault can't occur in the wild. Or if it can, it would be worth it to understand the bug and prevent it from happening. > +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; > @@ -130,8 +187,10 @@ 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); > + 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); I do admire the ternary operator over the function being called, as I think that Stolee pointed out earlier in this series. But I worry that these two checks could fall out of sync with each other, causing us to pick incosistent values for hash0, and hash1, respectively. FWIW, I would probably write this as: const 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); } I suppose that there isn't anything keeping the calls within each arm of the if-statement above in sync with each other (i.e., I could call murmur3_seeded_v1() immediately before dispatching a call to murmur3_seeded_v2()). So in that sense I think that this is no more or less safe than what's already written. But IMHO I think this one reads more cleanly, so I might prefer it over what you have in this patch. But I don't feel so strongly about it either way. > diff --git a/commit-graph.c b/commit-graph.c > index 9b72319450..c50107eed5 100644 > --- a/commit-graph.c > +++ b/commit-graph.c > @@ -302,16 +302,25 @@ static int graph_read_oid_lookup(const unsigned char *chunk_start, > return 0; > } > > +struct graph_read_bloom_data_data { > + struct commit_graph *g; > + int *commit_graph_changed_paths_version; > +}; > + Nit: maybe `graph_read_bloom_data_context`, to avoid repeating "data"? I don't have strong feelings here, FWIW. The rest of the implementation and tests look good to me. Thanks, Taylor
Taylor Blau <me@ttaylorr.com> writes: > On Thu, Jul 13, 2023 at 02:42:11PM -0700, Jonathan Tan wrote: > > 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 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. > > I think that you make a worthwhile point that the existing > implementation is internally consistent, but doesn't actually implement > a conventional murmur3. I wonder if it's worth being explicit where you > mention its internal consistency to say that the existing implementation > would never cause us to produce wrong results, but wouldn't be readable > by other off-the-shelf implementations of murmur3. > > (To be clear, I think that you already make this point, I'm just > suggesting that it may be worth spelling it out even more explicitly > than what is written above). OK, I've added some more text describing this. > > 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. > > Hmm. I think in the general case that is true, but I wonder if there's a > shortcut we could take for trees that are known to not have *any* > characters with their high-order bits set. That is, if we scan both of > the first parent's trees and determine that no such paths exist, the > contents of the Bloom filter would be the same in either version, right? > > I think that that would be faster than recomputing all filters from > scratch. In either case, we have to load the whole tree. But if we can > quickly scan (and cache our results by setting some bit--indicating the > absence of paths with characters having their highest bit set--on the tree > objects' `flags` field), then we should be able to copy forward the > existing representation of the filter. > > I think the early checks would be more expensive, since in the worst > case you have to walk the entire tree, only to realize that you actually > wanted to compute a first-parent tree diff, meaning you have to > essentially repeat the whole walk over again. But for repositories that > have few or no commits whose Bloom filters need computing, I think it > would be significantly faster, since many of the sub-trees wouldn't need > to be visited again. So for repositories that need little-to-no recomputation of Bloom filters, your idea likely means that each tree needs to be read once, as compared to recomputing everything in which, I think, each tree needs to be read roughly twice (once when computing the Bloom filter for the commit that introduces it, and once for the commit that substitutes a different tree in place). I could change the text of the commit message to discuss this (instead of the blanket statement that it would be too hard), although I think that an implementation of this can be done after this patchset. What do you think? > > 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. > > Hmm. Interesting, I'd love to know more about what you were doing that > produced the segfault. I think it would be worth it to prove to > ourselves that this segfault can't occur in the wild. Or if it can, it > would be worth it to understand the bug and prevent it from happening. If I remember correctly, I changed the version in DEFAULT_BLOOM_FILTER_SETTINGS to 2 and ran it to see what broke. This was a while back so I don't remember it exactly, though. > > @@ -130,8 +187,10 @@ 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); > > + 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); > > I do admire the ternary operator over the function being called, as I > think that Stolee pointed out earlier in this series. But I worry that > these two checks could fall out of sync with each other, causing us to > pick incosistent values for hash0, and hash1, respectively. > > FWIW, I would probably write this as: > > const 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); > } > > I suppose that there isn't anything keeping the calls within each arm of > the if-statement above in sync with each other (i.e., I could call > murmur3_seeded_v1() immediately before dispatching a call to > murmur3_seeded_v2()). So in that sense I think that this is no more or > less safe than what's already written. > > But IMHO I think this one reads more cleanly, so I might prefer it over > what you have in this patch. But I don't feel so strongly about it > either way. I'm OK either way, so I'll go with your approach (except the "const", since my compiler doesn't like that). > > @@ -302,16 +302,25 @@ static int graph_read_oid_lookup(const unsigned char *chunk_start, > > return 0; > > } > > > > +struct graph_read_bloom_data_data { > > + struct commit_graph *g; > > + int *commit_graph_changed_paths_version; > > +}; > > + > > Nit: maybe `graph_read_bloom_data_context`, to avoid repeating "data"? I > don't have strong feelings here, FWIW. I'll use "context". > The rest of the implementation and tests look good to me. > > Thanks, > Taylor Thanks for the review.
On Thu, Jul 20, 2023 at 02:27:53PM -0700, Jonathan Tan wrote: > > I think the early checks would be more expensive, since in the worst > > case you have to walk the entire tree, only to realize that you actually > > wanted to compute a first-parent tree diff, meaning you have to > > essentially repeat the whole walk over again. But for repositories that > > have few or no commits whose Bloom filters need computing, I think it > > would be significantly faster, since many of the sub-trees wouldn't need > > to be visited again. > > So for repositories that need little-to-no recomputation of Bloom > filters, your idea likely means that each tree needs to be read once, > as compared to recomputing everything in which, I think, each tree needs > to be read roughly twice (once when computing the Bloom filter for the > commit that introduces it, and once for the commit that substitutes a > different tree in place). > > I could change the text of the commit message to discuss this (instead > of the blanket statement that it would be too hard), although I think > that an implementation of this can be done after this patchset. What do > you think? Right, I think that a sizeable portion of repositories will need to compute relatively few Bloom filters overall. If you feel strongly that it shouldn't be included in this series, I could live with that since this is all behind a configuration variable anyway. I think at minimum we should call it out in the documentation, at least until such functionality is implemented, since unsuspecting users/forge operators may bump the filter version forward and be surprised when they suddenly have to recompute every existing Bloom filter. Thanks, Taylor
diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt index 07f3799e05..b93ccfba8f 100644 --- a/Documentation/config/commitgraph.txt +++ b/Documentation/config/commitgraph.txt @@ -14,7 +14,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. 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. + Defaults to -1. diff --git a/bloom.c b/bloom.c index d0730525da..915d8e5a31 100644 --- a/bloom.c +++ b/bloom.c @@ -65,7 +65,64 @@ static 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; @@ -130,8 +187,10 @@ 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); + 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); 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 adde6dfe21..0c33ae282c 100644 --- a/bloom.h +++ b/bloom.h @@ -7,9 +7,11 @@ struct repository; 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; @@ -75,7 +77,7 @@ struct bloom_key { * 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 9b72319450..c50107eed5 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -302,16 +302,25 @@ static int graph_read_oid_lookup(const unsigned char *chunk_start, return 0; } +struct graph_read_bloom_data_data { + struct commit_graph *g; + int *commit_graph_changed_paths_version; +}; + 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_data *d = data; + struct commit_graph *g = d->g; uint32_t hash_version; g->chunk_bloom_data = chunk_start; hash_version = get_be32(chunk_start); - if (hash_version != 1) - return 0; + 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; + } g->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings)); g->bloom_filter_settings->hash_version = hash_version; @@ -400,10 +409,14 @@ 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 = { + .g = graph, + .commit_graph_changed_paths_version = &s->commit_graph_changed_paths_version + }; pair_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES, &graph->chunk_bloom_indexes); read_chunk(cf, GRAPH_CHUNKID_BLOOMDATA, - graph_read_bloom_data, graph); + graph_read_bloom_data, &data); } if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) { @@ -2302,6 +2315,14 @@ int write_commit_graph(struct object_directory *odb, ctx->write_generation_data = (get_configured_generation_version(r) == 2); ctx->num_generation_data_overflows = 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; + } + 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", @@ -2331,7 +2352,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; ctx->bloom_settings = g->bloom_filter_settings; } diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c index 6c900ca668..34b8dd9164 100644 --- a/t/helper/test-bloom.c +++ b/t/helper/test-bloom.c @@ -48,6 +48,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"; @@ -62,7 +63,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 0cf208fdf5..6ff26e5af5 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -410,6 +410,13 @@ 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 \ @@ -426,7 +433,7 @@ test_expect_success 'set up repo with high bit path, version 1 changed-path' ' git -C highbit1 commit-graph write --reachable --changed-paths ' -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 && get_first_changed_path_filter >actual && @@ -451,4 +458,67 @@ test_expect_success 'version 1 changed-path used when version 1 requested' ' test_bloom_filters_used "-- $CENT") ' +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 "-- $CENT") +' + +test_expect_success 'version 1 changed-path used when autodetect requested' ' + (cd highbit1 && + git config --add commitgraph.changedPathsVersion -1 && + test_bloom_filters_used "-- $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 && + printf "00000001" >expect && + get_changed_path_filter_version >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 && + printf "c01f" >expect && + get_first_changed_path_filter >actual && + test_cmp expect actual) +' + +test_expect_success 'version 2 changed-path used when version 2 requested' ' + (cd highbit2 && + test_bloom_filters_used "-- $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 "-- $CENT") +' + +test_expect_success 'version 2 changed-path used when autodetect requested' ' + (cd highbit2 && + git config --add commitgraph.changedPathsVersion -1 && + test_bloom_filters_used "-- $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 && + printf "00000002" >expect && + get_changed_path_filter_version >actual && + test_cmp expect actual) +' + test_done
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 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> --- Documentation/config/commitgraph.txt | 2 +- bloom.c | 65 +++++++++++++++++++++++-- bloom.h | 8 ++-- commit-graph.c | 31 ++++++++++-- t/helper/test-bloom.c | 9 +++- t/t0095-bloom.sh | 8 ++++ t/t4216-log-bloom.sh | 72 +++++++++++++++++++++++++++- 7 files changed, 181 insertions(+), 14 deletions(-)