Derrick Stolee via GitGitGadgetThis is based on ds/line-log-on-bloom.
Since Szeder so kindly shared his alternate Bloom filter implementation [1], I thought it worth my time to start the process of updating the patches to apply to more recent code in Git. Here is the effort to update the almost obviously-good commit-graph cleanups that he presented in that series.
[1] https://lore.kernel.org/git/20200529085038.26008-1-szeder.dev@gmail.com/
The range-diff below was created by applying his entire series onto v2.25.0 and then doing cherry-picks as appropriate onto ds/line-log-on-bloom and correcting conflicts. I have Szeder's original series available as "szeder-bloom" on my fork [2].
[2] https://github.com/derrickstolee/git/tree/szeder-bloom
As expected, the write_commit_graph_file() cleanups were the most difficult, in part because we added extra chunks with the changed-path Bloom filters.
I did not include this commit since we already handle it mostly with the MAX_NUM_CHUNKS macro from 08fd81c9 (commit-graph: implement write_commit_graph(), 2018-04-02):
11: 56e3c4f57b3 < -: ----------- commit-graph: allocate the 'struct chunk_info' array dinamically
There were a few cleanups that I did not apply because they are more involved to handle the conflicts with the changed-path Bloom filters, especially because we pass a "struct bloom_filter_settings" in the method signatures for the write_graph_chunk_bloom_*() functions:
12: 28fb1b5bdfe < -: ----------- commit-graph: unify the signatures of all write_graph_chunk_*() functions 13: 1e1e59e2592 < -: ----------- commit-graph: simplify write_commit_graph_file() #3 14: 6f0d912e4b8 < -: ----------- commit-graph: check chunk sizes after writing
I'm not saying that we shouldn't do these changes. I'm just saying that they are more involved and can wait for a second series. No need to rush things.
The rest will need to be completely re-implemented to keep the other things in mind, like split commit-graphs and the existing changed-path Bloom filters. However, the following commits would be particularly interesting to have equivalents on top of our existing Bloom filter implementation. That would allow a more fair comparison between the two options:
26: 3951fdedf6a < -: ----------- commit-graph: deduplicate modified path Bloom filters 27: 5aba19a2766 < -: ----------- commit-graph: load modified path Bloom filters for merge commits 29: f87b37bf08e < -: ----------- commit-graph: extract init and free write_commit_graph_context 34: 8b40ec4cd30 < -: ----------- commit-graph: use modified path Bloom filters with wildcards, if possible
Full range diff:
1: 7a8dbfba53a ! 1: af84c253b24 tree-walk.c: don't match submodule entries for 'submod/anything'
@@ Commit message
Fix this by rejecting submodules as partial pathnames when their
trailing slash is followed by anything. Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
+ Signed-off-by: Derrick Stolee <dstolee@microsoft.com> ## t/t4010-diff-pathspec.sh ##
@@ t/t4010-diff-pathspec.sh: test_expect_success 'setup submodules' '
2: df25e984c58 ! 2: 1e1671e7c69 commit-graph: fix parsing the Chunk Lookup table
@@ Commit message
but that is a more invasive change, less suitable for 'maint', so that
will be done in later patches. + This additional flexibility of scanning more chunks breaks a test for
+ "git commit-graph verify" so alter that test to mutate the commit-graph
+ to have an even lower chunk count.
+
Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
+ Signed-off-by: Derrick Stolee <dstolee@microsoft.com> ## commit-graph.c ##
@@ commit-graph.c: struct commit_graph *parse_commit_graph(void *graph_map, int fd,
@@ commit-graph.c: struct commit_graph *parse_commit_graph(void *graph_map, int fd,
uint32_t chunk_id;
uint64_t chunk_offset;
int chunk_repeated = 0;
+
+ ## t/t5318-commit-graph.sh ##
+@@ t/t5318-commit-graph.sh: test_expect_success 'detect bad hash version' '
+ '
+
+ test_expect_success 'detect low chunk count' '
+- corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\02" \
++ corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\01" \
+ "missing the .* chunk"
+ '
+
3: 598f7f9a978 ! 3: a09d0bd5b7a commit-graph-format.txt: all multi-byte numbers are in network byte order
@@ Commit messageClarify that all multi-byte integers are in network byte order.
Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
+ Signed-off-by: Derrick Stolee <dstolee@microsoft.com> ## Documentation/technical/commit-graph-format.txt ##
@@ Documentation/technical/commit-graph-format.txt: the body into "chunks" and provide a binary lookup table at the beginning
4: b29e5d39ed6 ! 4: 32a6f11cc47 commit-slab: add a function to deep free entries on the slab
@@ Commit message
Use it in get_shallow_commits() in 'shallow.c' to replace an
open-coded iteration over a commit slab's entries. Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
+ Signed-off-by: Derrick Stolee <dstolee@microsoft.com> ## commit-slab-decl.h ##
@@ commit-slab-decl.h: struct slabname { \
@@ shallow.c: int is_repository_shallow(struct repository *r)
* supports a "valid" flag.
*/
define_commit_slab(commit_depth, int *);
-+void free_depth_in_slab(int **ptr)
++static void free_depth_in_slab(int **ptr)
+{
+ FREE_AND_NULL(*ptr);
+}
5: 18f4db7bfb9 ! 5: 1a70ff05aea diff.h: drop diff_tree_oid() & friends' return value
@@ Commit message
[2] diff_tree_oid() traces back to diff-tree.c:main() in 9174026cfe as
well. Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
+ Signed-off-by: Derrick Stolee <dstolee@microsoft.com> ## diff.h ##
@@ diff.h: struct combine_diff_path *diff_tree_paths(
@@ revision.c: static int rev_compare_tree(struct rev_info *revs,
- &revs->pruning) < 0)
- return REV_TREE_DIFFERENT;
+ diff_tree_oid(&t1->object.oid, &t2->object.oid, "", &revs->pruning);
- return tree_difference;
- }
+
+ if (!nth_parent)
+ if (bloom_ret == 1 && tree_difference == REV_TREE_SAME)
+@@ revision.c: static int rev_compare_tree(struct rev_info *revs, static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)
{
@@ tree-diff.c: static struct combine_diff_path *ll_diff_tree_paths(
const struct object_id **parents_oid, int nparent,
struct strbuf *base, struct diff_options *opt);
-static int ll_diff_tree_oid(const struct object_id *old_oid,
+- const struct object_id *new_oid,
+- struct strbuf *base, struct diff_options *opt);
+static void ll_diff_tree_oid(const struct object_id *old_oid,
- const struct object_id *new_oid,
- struct strbuf *base, struct diff_options *opt);
++ const struct object_id *new_oid,
++ struct strbuf *base, struct diff_options *opt); + /*
+ * Compare two tree entries, taking into account only path/S_ISDIR(mode),
@@ tree-diff.c: static void try_to_follow_renames(const struct object_id *old_oid,
q->nr = 1;
} -static int ll_diff_tree_oid(const struct object_id *old_oid,
+- const struct object_id *new_oid,
+- struct strbuf *base, struct diff_options *opt)
+static void ll_diff_tree_oid(const struct object_id *old_oid,
- const struct object_id *new_oid,
- struct strbuf *base, struct diff_options *opt)
++ const struct object_id *new_oid,
++ struct strbuf *base, struct diff_options *opt)
{
+ struct combine_diff_path phead, *p;
+ pathchange_fn_t pathchange_old = opt->pathchange;
@@ tree-diff.c: static int ll_diff_tree_oid(const struct object_id *old_oid,
} @@ tree-diff.c: static int ll_diff_tree_oid(const struct object_id *old_oid,
} -int diff_root_tree_oid(const struct object_id *new_oid, const char *base, struct diff_options *opt)
-+void diff_root_tree_oid(const struct object_id *new_oid, const char *base,
++void diff_root_tree_oid(const struct object_id *new_oid,
++ const char *base,
+ struct diff_options *opt)
{
- return diff_tree_oid(NULL, new_oid, base, opt);
6: bf336f109e6 ! 6: 636c2069659 commit-graph: clean up #includes
@@ Commit message
'commit-graph.c' includes 'dir.h', but doesn't actually use anything
from there, so let's drop that #include as well. Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
+ Signed-off-by: Derrick Stolee <dstolee@microsoft.com> ## commit-graph.c ##
@@
@@ commit-graph.h
-#include "repository.h"
-#include "string-list.h"
-#include "cache.h"
-+#include "hash.h"
+ #include "object-store.h" #define GIT_TEST_COMMIT_GRAPH "GIT_TEST_COMMIT_GRAPH"
- #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD "GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD"
+@@ commit-graph.h: void git_test_write_commit_graph_or_die(void); struct commit;
+ struct bloom_filter_settings;
+struct repository;
+struct raw_object_store;
+struct string_list; - char *get_commit_graph_filename(const char *obj_dir);
+ char *get_commit_graph_filename(struct object_directory *odb);
int open_commit_graph(const char *graph_file, int *fd, struct stat *st);
7: b7f0f831bcf ! 7: cd9e033d1b1 commit-graph: simplify parse_commit_graph() #1
@@ Commit message
and, consequently, have to update the 'detect incorrect chunk count'
test in 't5318-commit-graph.sh' as well. Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
+ Signed-off-by: Derrick Stolee <dstolee@microsoft.com> ## commit-graph.c ##
@@ commit-graph.c: struct commit_graph *parse_commit_graph(void *graph_map, int fd,
8: f2752000052 ! 8: 83641b5e49e commit-graph: simplify parse_commit_graph() #2
@@ Commit message
iteration, so we can calculate the size of each chunk right away,
right where we store its starting offset. Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
+ Signed-off-by: Derrick Stolee <dstolee@microsoft.com> ## commit-graph.c ##
@@ commit-graph.c: struct commit_graph *parse_commit_graph(void *graph_map, int fd,
@@ commit-graph.c: struct commit_graph *parse_commit_graph(void *graph_map, int fd,
+ next_chunk_offset = get_be64(chunk_lookup + 4);
+ for (i = 0; i < graph->num_chunks; i++) {
uint32_t chunk_id;
- uint64_t chunk_offset;
+- uint64_t chunk_offset;
++ uint64_t chunk_offset = next_chunk_offset;
int chunk_repeated = 0; chunk_id = get_be32(chunk_lookup + 0);
- chunk_offset = get_be64(chunk_lookup + 4);
-+ chunk_offset = next_chunk_offset;
-+ next_chunk_offset = get_be64(chunk_lookup + 4 +
-+ GRAPH_CHUNKLOOKUP_WIDTH); chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
++ next_chunk_offset = get_be64(chunk_lookup + 4); + if (chunk_offset > graph_size - the_hash_algo->rawsz) {
+ error(_("commit-graph improper chunk offset %08x%08x"), (uint32_t)(chunk_offset >> 32),
@@ commit-graph.c: struct commit_graph *parse_commit_graph(void *graph_map, int fd,
case GRAPH_CHUNKID_OIDLOOKUP:
if (graph->chunk_oid_lookup)
@@ commit-graph.c: struct commit_graph *parse_commit_graph(void *graph_map, int fd,
- last_chunk_offset = chunk_offset;
} - hashcpy(graph->oid.hash, graph->data + graph->data_len - graph->hash_len);
+ if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) {I'm stepping out of the range-diff to point out that this change is mostly stylistic.
9: 4e184b8743c ! 9: 9b818b9cb91 commit-graph: simplify write_commit_graph_file() #1
@@ Commit message
fill the arrays of chunk IDs and sizes in one go, eliminating one set
of repeated conditions. Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
+ Signed-off-by: Derrick Stolee <dstolee@microsoft.com> ## commit-graph.c ##
@@ commit-graph.c: static int write_commit_graph_file(struct write_commit_graph_context *ctx)
struct hashfile *f;
struct lock_file lk = LOCK_INIT;
- uint32_t chunk_ids[6];
-- uint64_t chunk_offsets[6];
-+ uint64_t chunk_sizes[6];
+ uint32_t chunk_ids[MAX_NUM_CHUNKS + 1];
+- uint64_t chunk_offsets[MAX_NUM_CHUNKS + 1];
++ uint64_t chunk_sizes[MAX_NUM_CHUNKS + 1];
const unsigned hashsz = the_hash_algo->rawsz;
struct strbuf progress_title = STRBUF_INIT;
int num_chunks = 3;
+ uint64_t chunk_offset;
struct object_id file_hash;
+ const struct bloom_filter_settings bloom_settings = DEFAULT_BLOOM_FILTER_SETTINGS; - if (ctx->split) {
@@ commit-graph.c: static int write_commit_graph_file(struct write_commit_graph_context *ctx)
} @@ commit-graph.c: static int write_commit_graph_file(struct write_commit_graph_con
+ chunk_sizes[1] = hashsz * ctx->commits.nr;
chunk_ids[2] = GRAPH_CHUNKID_DATA;
+ chunk_sizes[2] = (hashsz + 16) * ctx->commits.nr;
++
if (ctx->num_extra_edges) {
chunk_ids[num_chunks] = GRAPH_CHUNKID_EXTRAEDGES;
-+ chunk_sizes[3] = 4 * ctx->num_extra_edges;
++ chunk_sizes[num_chunks] = 4 * ctx->num_extra_edges;
+ num_chunks++;
+ }
+ if (ctx->changed_paths) {
+ chunk_ids[num_chunks] = GRAPH_CHUNKID_BLOOMINDEXES;
++ chunk_sizes[num_chunks] = sizeof(uint32_t) * ctx->commits.nr;
+ num_chunks++;
+ chunk_ids[num_chunks] = GRAPH_CHUNKID_BLOOMDATA;
++ chunk_sizes[num_chunks] = sizeof(uint32_t) * 3
++ + ctx->total_bloom_filter_data_size;
num_chunks++;
}
if (ctx->num_commit_graphs_after > 1) {
chunk_ids[num_chunks] = GRAPH_CHUNKID_BASE;
-+ chunk_sizes[4] = hashsz * (ctx->num_commit_graphs_after - 1);
++ chunk_sizes[num_chunks] = hashsz * (ctx->num_commit_graphs_after - 1);
num_chunks++;
} @@ commit-graph.c: static int write_commit_graph_file(struct write_commit_graph_con
- 4 * ctx->num_extra_edges;
- num_chunks++;
- }
+- if (ctx->changed_paths) {
+- chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] +
+- sizeof(uint32_t) * ctx->commits.nr;
+- num_chunks++;
+-
+- chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] +
+- sizeof(uint32_t) * 3 + ctx->total_bloom_filter_data_size;
+- num_chunks++;
+- }
- if (ctx->num_commit_graphs_after > 1) {
- chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] +
- hashsz * (ctx->num_commit_graphs_after - 1);
10: 344dd337da5 ! 10: 5984fb01ebc commit-graph: simplify write_commit_graph_file() #2
@@ Commit message
'struct chunk_info'. This will allow more cleanups in the following
patches. Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
+ Signed-off-by: Derrick Stolee <dstolee@microsoft.com> ## commit-graph.c ##
@@ commit-graph.c: static int write_graph_chunk_base(struct hashfile *f,
@@ commit-graph.c: static int write_graph_chunk_base(struct hashfile *f,
int fd;
struct hashfile *f;
struct lock_file lk = LOCK_INIT;
-- uint32_t chunk_ids[6];
-- uint64_t chunk_sizes[6];
-+ struct chunk_info chunks[6];
+- uint32_t chunk_ids[MAX_NUM_CHUNKS + 1];
+- uint64_t chunk_sizes[MAX_NUM_CHUNKS + 1];
++ struct chunk_info chunks[MAX_NUM_CHUNKS + 1];
const unsigned hashsz = the_hash_algo->rawsz;
struct strbuf progress_title = STRBUF_INIT;
int num_chunks = 3;
@@ commit-graph.c: static int write_commit_graph_file(struct write_commit_graph_con
- chunk_sizes[1] = hashsz * ctx->commits.nr;
- chunk_ids[2] = GRAPH_CHUNKID_DATA;
- chunk_sizes[2] = (hashsz + 16) * ctx->commits.nr;
+-
+ chunks[0].id = GRAPH_CHUNKID_OIDFANOUT;
+ chunks[0].size = GRAPH_FANOUT_SIZE;
+ chunks[1].id = GRAPH_CHUNKID_OIDLOOKUP;
@@ commit-graph.c: static int write_commit_graph_file(struct write_commit_graph_con
+ chunks[2].size = (hashsz + 16) * ctx->commits.nr;
if (ctx->num_extra_edges) {
- chunk_ids[num_chunks] = GRAPH_CHUNKID_EXTRAEDGES;
-- chunk_sizes[3] = 4 * ctx->num_extra_edges;
+- chunk_sizes[num_chunks] = 4 * ctx->num_extra_edges;
+ chunks[num_chunks].id = GRAPH_CHUNKID_EXTRAEDGES;
+ chunks[num_chunks].size = 4 * ctx->num_extra_edges;
num_chunks++;
}
+ if (ctx->changed_paths) {
+- chunk_ids[num_chunks] = GRAPH_CHUNKID_BLOOMINDEXES;
+- chunk_sizes[num_chunks] = sizeof(uint32_t) * ctx->commits.nr;
++ chunks[num_chunks].id = GRAPH_CHUNKID_BLOOMINDEXES;
++ chunks[num_chunks].size = sizeof(uint32_t) * ctx->commits.nr;
+ num_chunks++;
+- chunk_ids[num_chunks] = GRAPH_CHUNKID_BLOOMDATA;
+- chunk_sizes[num_chunks] = sizeof(uint32_t) * 3
++ chunks[num_chunks].id = GRAPH_CHUNKID_BLOOMDATA;
++ chunks[num_chunks].size = sizeof(uint32_t) * 3
+ + ctx->total_bloom_filter_data_size;
+ num_chunks++;
+ }
if (ctx->num_commit_graphs_after > 1) {
- chunk_ids[num_chunks] = GRAPH_CHUNKID_BASE;
-- chunk_sizes[4] = hashsz * (ctx->num_commit_graphs_after - 1);
+- chunk_sizes[num_chunks] = hashsz * (ctx->num_commit_graphs_after - 1);
+ chunks[num_chunks].id = GRAPH_CHUNKID_BASE;
+ chunks[num_chunks].size = hashsz * (ctx->num_commit_graphs_after - 1);
num_chunks++;
11: 56e3c4f57b3 < -: ----------- commit-graph: allocate the 'struct chunk_info' array dinamically
12: 28fb1b5bdfe < -: ----------- commit-graph: unify the signatures of all write_graph_chunk_*() functions
13: 1e1e59e2592 < -: ----------- commit-graph: simplify write_commit_graph_file() #3
14: 6f0d912e4b8 < -: ----------- commit-graph: check chunk sizes after writing
15: 0ab955aac32 < -: ----------- commit-graph-format.txt: document the modified path Bloom filter chunks
16: 4c128d51dfe < -: ----------- Add a generic and minimal Bloom filter implementation
17: 41f02bc38f7 < -: ----------- Import a streaming-capable Murmur3 hash function implementation
18: e5fd1da48d4 < -: ----------- commit-graph: write "empty" Modified Path Bloom Filter Index chunk
19: 2dd882ec601 < -: ----------- commit-graph: add commit slab for modified path Bloom filters
20: f30e495c2b0 < -: ----------- commit-graph: fill the Modified Path Bloom Filter Index chunk
21: e904cb58301 < -: ----------- commit-graph: load and use the Modified Path Bloom Filter Index chunk
22: c71647ca374 < -: ----------- commit-graph: write the Modified Path Bloom Filters chunk
23: 50898d42291 < -: ----------- commit-graph: load and use the Modified Path Bloom Filters chunk
24: dc96f0d9822 < -: ----------- commit-graph: check all leading directories in modified path Bloom filters
25: 7cbf1bc6b66 < -: ----------- commit-graph: check embedded modified path Bloom filters with a mask
26: 3951fdedf6a < -: ----------- commit-graph: deduplicate modified path Bloom filters
27: 5aba19a2766 < -: ----------- commit-graph: load modified path Bloom filters for merge commits
28: 93fc6af1d2f < -: ----------- commit-graph: write Modified Path Bloom Filter Merge Index chunk
29: f87b37bf08e < -: ----------- commit-graph: extract init and free write_commit_graph_context
30: 943b0d9554c < -: ----------- commit-graph: move write_commit_graph_reachable below write_commit_graph
31: 47b26ea61aa < -: ----------- t7007-show: make the first test compatible with the next patch
32: 9201b71071c < -: ----------- PoC commit-graph: use revision walk machinery for '--reachable'
33: 5c72d97e5e9 < -: ----------- commit-graph: write modified path Bloom filters in "history order"
34: 8b40ec4cd30 < -: ----------- commit-graph: use modified path Bloom filters with wildcards, if possibleThanks, -Stolee
SZEDER Gábor (10):
tree-walk.c: don't match submodule entries for 'submod/anything'
commit-graph: fix parsing the Chunk Lookup table
commit-graph-format.txt: all multi-byte numbers are in network byte
order
commit-slab: add a function to deep free entries on the slab
diff.h: drop diff_tree_oid() & friends' return value
commit-graph: clean up #includes
commit-graph: simplify parse_commit_graph() #1
commit-graph: simplify parse_commit_graph() #2
commit-graph: simplify write_commit_graph_file() #1
commit-graph: simplify write_commit_graph_file() #2.../technical/commit-graph-format.txt | 2 +- commit-graph.c | 113 ++++++++---------- commit-graph.h | 6 +- commit-slab-decl.h | 1 + commit-slab-impl.h | 13 ++ commit-slab.h | 10 ++ diff.h | 10 +- revision.c | 9 +- shallow.c | 14 +-- t/t4010-diff-pathspec.sh | 4 +- t/t5318-commit-graph.sh | 5 +- tree-diff.c | 30 +++-- tree-walk.c | 9 +- 13 files changed, 117 insertions(+), 109 deletions(-)
base-commit: f32dde8c12d941065be848a9f66239df96bde216 Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-650%2Fderrickstolee%2Fbloom-improvements-v1 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-650/derrickstolee/bloom-improvements-v1 Pull-Request: https://github.com/gitgitgadget/git/pull/650
-- gitgitgadget
