[PATCH 18/34] commit-graph: write "empty" Modified Path Bloom Filter Index chunk

From

SZEDER Gábor <szeder.dev@gmail.com>

Date

May 29, 2020, 08:50 UTC

Message-ID

<20200529085038.26008-19-szeder.dev@gmail.com>

In-Reply-To

<20200529085038.26008-1-szeder.dev@gmail.com>

The format of the various modified path Bloom filter-related chunks
are not (yet) compatible with split commit-graph files, so ignore the
config setting and don't write modifed path Bloom filters with
'--split'.
---
 Documentation/config/core.txt |  6 ++++++
 commit-graph.c                | 40 +++++++++++++++++++++++++++++++++++
 2 files changed, 46 insertions(+)

diff --git a/Documentation/config/core.txt b/Documentation/config/core.txt
index 9e440b160d..820f7d3bcf 100644
--- a/Documentation/config/core.txt
+++ b/Documentation/config/core.txt
@@ -588,6 +588,12 @@ core.commitGraph::
 	to parse the graph structure of commits. Defaults to true. See
 	linkgit:git-commit-graph[1] for more information.
 
+core.modifiedPathBloomFilters::
+	EXPERIMENTAL!!
+	If true, then Git will store and use Bloom filters in the
+	commit-graph file to speed up pathspec-limited revision walks.
+	Defaults to false.
+
 core.useReplaceRefs::
 	If set to `false`, behave as if the `--no-replace-objects`
 	option was given on the command line. See linkgit:git[1] and
diff --git a/commit-graph.c b/commit-graph.c
index e3adffd58b..28f147a418 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -21,6 +21,7 @@
 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
 #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
 #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
+#define GRAPH_CHUNKID_MODIFIED_PATH_BLOOM_FILTER_INDEX 0x4d504249 /* "MPBI" */
 
 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
 
@@ -33,6 +34,10 @@
 
 #define GRAPH_LAST_EDGE 0x80000000
 
+#define GRAPH_MODIFIED_PATH_BLOOM_FILTER_NONE 0xffffffffffffffff
+
+#define GRAPH_MODIFIED_PATH_BLOOM_FILTER_DEFAULT_NR_HASHES 7
+
 #define GRAPH_HEADER_SIZE 8
 #define GRAPH_FANOUT_SIZE (4 * 256)
 #define GRAPH_CHUNKLOOKUP_WIDTH 12
@@ -791,6 +796,11 @@ struct write_commit_graph_context {
 		 check_oids:1;
 
 	const struct split_commit_graph_opts *split_opts;
+
+	struct modified_path_bloom_filter_context {
+		unsigned use_modified_path_bloom_filters:1;
+		unsigned int num_hashes;
+	} mpbfctx;
 };
 
 static int write_graph_chunk_fanout(struct hashfile *f,
@@ -990,6 +1000,20 @@ static int write_graph_chunk_extra_edges(struct hashfile *f,
 	return 0;
 }
 
+static int write_graph_chunk_modified_path_bloom_index(struct hashfile *f,
+		struct write_commit_graph_context *ctx)
+{
+	const uint64_t no_bloom_filter = GRAPH_MODIFIED_PATH_BLOOM_FILTER_NONE;
+	int i;
+
+	hashwrite(f, &ctx->mpbfctx.num_hashes, sizeof(uint8_t));
+	for (i = 0; i < ctx->commits.nr; i++) {
+		display_progress(ctx->progress, ++ctx->progress_cnt);
+		hashwrite(f, &no_bloom_filter, sizeof(no_bloom_filter));
+	}
+	return 0;
+}
+
 static int oid_compare(const void *_a, const void *_b)
 {
 	const struct object_id *a = (const struct object_id *)_a;
@@ -1428,6 +1452,14 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 		chunks[chunks_nr].write_fn = write_graph_chunk_extra_edges;
 		chunks_nr++;
 	}
+	if (ctx->mpbfctx.use_modified_path_bloom_filters) {
+		ALLOC_GROW(chunks, chunks_nr + 1, chunks_alloc);
+		chunks[chunks_nr].id = GRAPH_CHUNKID_MODIFIED_PATH_BLOOM_FILTER_INDEX;
+		chunks[chunks_nr].size = sizeof(uint8_t) +
+					 ctx->commits.nr * sizeof(uint64_t);
+		chunks[chunks_nr].write_fn = write_graph_chunk_modified_path_bloom_index;
+		chunks_nr++;
+	}
 	if (ctx->num_commit_graphs_after > 1) {
 		ALLOC_GROW(chunks, chunks_nr + 1, chunks_alloc);
 		chunks[chunks_nr].id = GRAPH_CHUNKID_BASE;
@@ -1824,6 +1856,14 @@ int write_commit_graph(const char *obj_dir,
 	ctx->check_oids = flags & COMMIT_GRAPH_WRITE_CHECK_OIDS ? 1 : 0;
 	ctx->split_opts = split_opts;
 
+	git_config_get_bool("core.modifiedPathBloomFilters", &res);
+	if (res && ctx->split) {
+		warning("not writing modified path Bloom filters with --split");
+	} else if (res) {
+		ctx->mpbfctx.use_modified_path_bloom_filters = 1;
+		ctx->mpbfctx.num_hashes = GRAPH_MODIFIED_PATH_BLOOM_FILTER_DEFAULT_NR_HASHES;
+	}
+
 	if (ctx->split) {
 		struct commit_graph *g;
 		prepare_commit_graph(ctx->r);

-- 
2.27.0.rc1.431.g5c813f95dc