[v2,07/11] commit-graph: write Bloom filters to commit graph file

Commit Message

Linus Arver via GitGitGadget Feb. 5, 2020, 10:56 p.m. UTC

From: Garima Singh <[e-mail]>

Update the technical documentation for commit-graph-format with the formats for
the Bloom filter index (BIDX) and Bloom filter data (BDAT) chunks. Write the
computed Bloom filters information to the commit graph file using this format.

Helped-by: Derrick Stolee <[e-mail]>
Signed-off-by: Garima Singh <[e-mail]>
---
 .../technical/commit-graph-format.txt         |  24 ++++
 commit-graph.c                                | 118 +++++++++++++++++-
 commit-graph.h                                |   7 +-
 3 files changed, 145 insertions(+), 4 deletions(-)

Comments

Jakub Narębski Feb. 19, 2020, 3:13 p.m. UTC | #1

"Garima Singh via GitGitGadget" <[e-mail]> writes:

> From: Garima Singh <[e-mail]>
>
> Update the technical documentation for commit-graph-format with the formats for
> the Bloom filter index (BIDX) and Bloom filter data (BDAT) chunks. Write the
> computed Bloom filters information to the commit graph file using this format.

Nice description.

The only minor nitpick is with the formating: it is 80-character wide,
which is a bit wide.

>
> Helped-by: Derrick Stolee <[e-mail]>
> Signed-off-by: Garima Singh <[e-mail]>
> ---
>  .../technical/commit-graph-format.txt         |  24 ++++
>  commit-graph.c                                | 118 +++++++++++++++++-
>  commit-graph.h                                |   7 +-
>  3 files changed, 145 insertions(+), 4 deletions(-)
>
> diff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt
> index a4f17441ae..22e511643d 100644
> --- a/Documentation/technical/commit-graph-format.txt
> +++ b/Documentation/technical/commit-graph-format.txt
> @@ -17,6 +17,9 @@ metadata, including:
>  - The parents of the commit, stored using positional references within
>    the graph file.
>  
> +- The Bloom filter of the commit carrying the paths that were changed between
> +  the commit and its first parent.
> +

All right.

Should we also state that it is optional (meta)data?  This would be
first optional piece of data stored in commit-graph, I think.

>  These positional references are stored as unsigned 32-bit integers
>  corresponding to the array position within the list of commit OIDs. Due
>  to some special constants we use to track parents, we can store at most
> @@ -93,6 +96,27 @@ CHUNK DATA:
>        positions for the parents until reaching a value with the most-significant
>        bit on. The other bits correspond to the position of the last parent.
>  
> +  Bloom Filter Index (ID: {'B', 'I', 'D', 'X'}) (N * 4 bytes) [Optional]
> +    * The ith entry, BIDX[i], stores the number of 8-byte word blocks in all
> +      Bloom filters from commit 0 to commit i (inclusive) in lexicographic
> +      order. The Bloom filter for the i-th commit spans from BIDX[i-1] to
> +      BIDX[i] (plus header length), where BIDX[-1] is 0.
> +    * The BIDX chunk is ignored if the BDAT chunk is not present.

All right.  Looks good.

> +
> +  Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]
> +    * It starts with header consisting of three unsigned 32-bit integers:
> +      - Version of the hash algorithm being used. We currently only support
> +	value 1 which implies the murmur3 hash implemented exactly as described
> +	in https://en.wikipedia.org/wiki/MurmurHash#Algorithm

First a minor issue: shouldn't this nested unordered list be indented
with a hanging indent formatted with spaces?  That is be formatted like
the following:

  +  Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]
  +    * It starts with header consisting of three unsigned 32-bit integers:
  +      - Version of the hash algorithm being used. We currently only support
  +        value 1 which implies the murmur3 hash implemented exactly as
  +        described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm

But the existing formatting with spaces and tabs might be fine as it is,
that is it renders as nested list with Asciidoc; it only looks a bit
weird as patch, not so as text.

Second, and more important: it is in my opinion not enough information,
at least if we are assuming that the information in this document should
be enough for clean-room reimplementation of Bloom filter functionality
(for example by JGit).  To generate compatible Bloom filters, one needs
also the information on how to create $k$ functionally-independent hash
functions out of murmur3 hash.  We do it currently using double hashing
technique; if that changes then the exact set of bits in the Bloom
filter would also change.

The additional description could look something like the following:

  +    * It starts with header consisting of three unsigned 32-bit integers:
  +      - Version of the hash algorithm being used. We currently only support
  +        value 1 which implies the murmur3_32 hash implemented exactly as
  +        described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
  +        and double hashing technique with 0x293ae76f and 0x7e646e2c seeds
  +        as described in https://doi.org/10.1007/978-3-540-30494-4_26
  +        "Bloom Filters in Probabilistic Verification"

Also, it should be explicitly noted that we use murmur3_32, because
there is also 128-bit version of murmur3 hash.

> +      - The number of times a path is hashed and hence the number of bit positions
> +	that cumulatively determine whether a file is present in the commit.

All right, in the original Bloom filter it was the number of different
hash functions.  With the double hashing technique, it is the number of
times a path is hashed.

> +      - The minimum number of bits 'b' per entry in the Bloom filter. If the filter
> +	contains 'n' entries, then the filter size is the minimum number of 64-bit
> +	words that contain n*b bits.

All right, that means empty Bloom filter, representing "no changes",
with 'n' equal 0 entries, is represented as size 0 filter.  That is, if
we read this rule exactly as written.

Should we add the information that size 0 / length 0 filter is
considered "no data" case?  Or should we leave it to implementation?

There are two corner cases:
- "no changes" case, where all queries are answered with "no"
  can be represented as filter of size 0, or as Bloom filter with all
  bits set to 0
- "no data" case (used when there are more than 512 changed files)
  where all queries are answered with "maybe", currently represented
  as filter of size 0; can also be represented as Bloom filter with all
  bits set to 1

> +    * The rest of the chunk is the concatenation of all the computed Bloom
> +      filters for the commits in lexicographic order.

All right.

> +    * The BDAT chunk is present iff BIDX is present.

Perhaps we should spell 'iff' in full, that is 'if and only if'?

> +
>    Base Graphs List (ID: {'B', 'A', 'S', 'E'}) [Optional]
>        This list of H-byte hashes describe a set of B commit-graph files that
>        form a commit-graph chain. The graph position for the ith commit in this
> diff --git a/commit-graph.c b/commit-graph.c
> index 32a315058f..4585b3b702 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -24,8 +24,10 @@
>  #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
>  #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
>  #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
> +#define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
> +#define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */
>  #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
> -#define MAX_NUM_CHUNKS 5
> +#define MAX_NUM_CHUNKS 7
>  
>  #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
>  
> @@ -325,6 +327,32 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
>  				chunk_repeated = 1;
>  			else
>  				graph->chunk_base_graphs = data + chunk_offset;
> +			break;
> +
> +		case GRAPH_CHUNKID_BLOOMINDEXES:
> +			if (graph->chunk_bloom_indexes)
> +				chunk_repeated = 1;
> +			else
> +				graph->chunk_bloom_indexes = data + chunk_offset;
> +			break;
> +
> +		case GRAPH_CHUNKID_BLOOMDATA:
> +			if (graph->chunk_bloom_data)
> +				chunk_repeated = 1;
> +			else {
> +				uint32_t hash_version;
> +				graph->chunk_bloom_data = data + chunk_offset;
> +				hash_version = get_be32(data + chunk_offset);
> +
> +				if (hash_version != 1)
> +					break;

Shouldn't we mark Bloom filter as not to be used?  Or is it left for
later commit?

In the future it might be good idea to notify the user (perhaps
protected with some advice.* option) that there is problem with Bloom
filter data, namely that we have encountered unsupported hash version.

> +
> +				graph->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));

Why is this structure allocated dynamically?  We are leaking admittedly
a small amount of memory because we never free this xmalloc() result.

If we need this field being a pointer to struct to have NULL mean no
supported Bloom filter data, we could have instead use chunk_bloom_*
fields instead - we can set at least one of them to NULL.

> +				graph->bloom_filter_settings->hash_version = hash_version;
> +				graph->bloom_filter_settings->num_hashes = get_be32(data + chunk_offset + 4);
> +				graph->bloom_filter_settings->bits_per_entry = get_be32(data + chunk_offset + 8);

All right; these 4 and 8 are sizeof(uint32_t) and 2*sizeof(uint32_t),
respectively.

> +			}
> +			break;
>  		}
>  
>  		if (chunk_repeated) {
> @@ -343,6 +371,17 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
>  		last_chunk_offset = chunk_offset;
>  	}
>  
> +	/* We need both the bloom chunks to exist together. Else ignore the data */
> +	if ((graph->chunk_bloom_indexes && !graph->chunk_bloom_data)
> +		 || (!graph->chunk_bloom_indexes && graph->chunk_bloom_data)) {
> +		graph->chunk_bloom_indexes = NULL;
> +		graph->chunk_bloom_data = NULL;
> +		graph->bloom_filter_settings = NULL;
> +	}
> +
> +	if (graph->chunk_bloom_indexes && graph->chunk_bloom_data)
> +		load_bloom_filters();

Wouldn't it be simpler to rely on the fact that both Bloom chunks must
exists for it to matter, and write it like this:

  +	if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) {
  +		load_bloom_filters();
  +	} else {
  +		graph->chunk_bloom_indexes = NULL;
  +		graph->chunk_bloom_data = NULL;
  +		graph->bloom_filter_settings = NULL;
  +	}

> +
>  	hashcpy(graph->oid.hash, graph->data + graph->data_len - graph->hash_len);
>  
>  	if (verify_commit_graph_lite(graph)) {
> @@ -1040,6 +1079,59 @@ static void write_graph_chunk_extra_edges(struct hashfile *f,
>  	}
>  }
>  
> +static void write_graph_chunk_bloom_indexes(struct hashfile *f,
> +					    struct write_commit_graph_context *ctx)
> +{
> +	struct commit **list = ctx->commits.list;
> +	struct commit **last = ctx->commits.list + ctx->commits.nr;
> +	uint32_t cur_pos = 0;
> +	struct progress *progress = NULL;
> +	int i = 0;
> +
> +	if (ctx->report_progress)
> +		progress = start_delayed_progress(
> +			_("Writing changed paths Bloom filters index"),
> +			ctx->commits.nr);
> +
> +	while (list < last) {
> +		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
> +		cur_pos += filter->len;
> +		display_progress(progress, ++i);
> +		hashwrite_be32(f, cur_pos);
> +		list++;
> +	}
> +
> +	stop_progress(&progress);
> +}

All right, looks good.

> +
> +static void write_graph_chunk_bloom_data(struct hashfile *f,
> +					 struct write_commit_graph_context *ctx,
> +					 struct bloom_filter_settings *settings)
> +{
> +	struct commit **list = ctx->commits.list;
> +	struct commit **last = ctx->commits.list + ctx->commits.nr;
> +	struct progress *progress = NULL;
> +	int i = 0;
> +
> +	if (ctx->report_progress)
> +		progress = start_delayed_progress(
> +			_("Writing changed paths Bloom filters data"),
> +			ctx->commits.nr);
> +
> +	hashwrite_be32(f, settings->hash_version);
> +	hashwrite_be32(f, settings->num_hashes);
> +	hashwrite_be32(f, settings->bits_per_entry);
> +
> +	while (list < last) {
> +		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
> +		display_progress(progress, ++i);
> +		hashwrite(f, filter->data, filter->len * sizeof(uint64_t));
> +		list++;
> +	}
> +
> +	stop_progress(&progress);
> +}

All right, looks good.

Side note: why have while loop here instead of for loop, like in
previous patches?  I'm not saying this is a bad idea (especially with
same names for same variables).

> +
>  static int oid_compare(const void *_a, const void *_b)
>  {
>  	const struct object_id *a = (const struct object_id *)_a;
> @@ -1198,8 +1290,8 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
>  	load_bloom_filters();
>  
>  	if (ctx->report_progress)
> -		progress = start_progress(
> -			_("Computing commit diff Bloom filters"),
> +		progress = start_delayed_progress(
> +			_("Computing changed paths Bloom filters"),
>  			ctx->commits.nr);
>

Ooops.  This look like a fixup which should be made to the original
earlier commit instead, isn't it?

>  	ALLOC_ARRAY(sorted_by_pos, ctx->commits.nr);
> @@ -1444,6 +1536,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
>  	struct strbuf progress_title = STRBUF_INIT;
>  	int num_chunks = 3;
>  	struct object_id file_hash;
> +	struct bloom_filter_settings bloom_settings = DEFAULT_BLOOM_FILTER_SETTINGS;
>  
>  	if (ctx->split) {
>  		struct strbuf tmp_file = STRBUF_INIT;
> @@ -1488,6 +1581,12 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
>  		chunk_ids[num_chunks] = GRAPH_CHUNKID_EXTRAEDGES;
>  		num_chunks++;
>  	}
> +	if (ctx->changed_paths) {
> +		chunk_ids[num_chunks] = GRAPH_CHUNKID_BLOOMINDEXES;
> +		num_chunks++;
> +		chunk_ids[num_chunks] = GRAPH_CHUNKID_BLOOMDATA;
> +		num_chunks++;
> +	}

All right, adding chunks and counting them.

>  	if (ctx->num_commit_graphs_after > 1) {
>  		chunk_ids[num_chunks] = GRAPH_CHUNKID_BASE;
>  		num_chunks++;
> @@ -1506,6 +1605,15 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
>  						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++;
> +	}

All right, calculating chunk offsets.

>  	if (ctx->num_commit_graphs_after > 1) {
>  		chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] +
>  						hashsz * (ctx->num_commit_graphs_after - 1);
> @@ -1543,6 +1651,10 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
>  	write_graph_chunk_data(f, hashsz, ctx);
>  	if (ctx->num_extra_edges)
>  		write_graph_chunk_extra_edges(f, ctx);
> +	if (ctx->changed_paths) {
> +		write_graph_chunk_bloom_indexes(f, ctx);
> +		write_graph_chunk_bloom_data(f, ctx, &bloom_settings);
> +	}

All right, writing BIDX and BDAT chunks with default settings.

By the way, in the future, when appending to existing commit-graph file,
shouldn't we re-use existing settings even if they are different from
default settings?  But that is question for the future...

>  	if (ctx->num_commit_graphs_after > 1 &&
>  	    write_graph_chunk_base(f, ctx)) {
>  		return -1;
> diff --git a/commit-graph.h b/commit-graph.h
> index 952a4b83be..25fefefb3e 100644
> --- a/commit-graph.h
> +++ b/commit-graph.h
> @@ -10,6 +10,7 @@
>  #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD "GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD"
>  
>  struct commit;
> +struct bloom_filter_settings;
>  
>  char *get_commit_graph_filename(const char *obj_dir);
>  int open_commit_graph(const char *graph_file, int *fd, struct stat *st);
> @@ -58,6 +59,10 @@ struct commit_graph {
>  	const unsigned char *chunk_commit_data;
>  	const unsigned char *chunk_extra_edges;
>  	const unsigned char *chunk_base_graphs;
> +	const unsigned char *chunk_bloom_indexes;
> +	const unsigned char *chunk_bloom_data;

All right.

> +
> +	struct bloom_filter_settings *bloom_filter_settings;

Why it is pointer to struct, instead of being just struct type?
Is there reason for that?

>  };
>  
>  struct commit_graph *load_commit_graph_one_fd_st(int fd, struct stat *st);
> @@ -77,7 +82,7 @@ enum commit_graph_write_flags {
>  	COMMIT_GRAPH_WRITE_SPLIT      = (1 << 2),
>  	/* Make sure that each OID in the input is a valid commit OID. */
>  	COMMIT_GRAPH_WRITE_CHECK_OIDS = (1 << 3),
> -	COMMIT_GRAPH_WRITE_BLOOM_FILTERS = (1 << 4)
> +	COMMIT_GRAPH_WRITE_BLOOM_FILTERS = (1 << 4),

This looks like accidental change; if we want to use trailing comma in
enum, this change should be in my opinion done in the commit that added
COMMIT_GRAPH_WRITE_BLOOM_FILTERS (as I have written in a comment there).

>  };
>  
>  struct split_commit_graph_opts {

Thank you for your work on this series.

Best,

Garima Singh Feb. 24, 2020, 9:14 p.m. UTC | #2

On 2/19/2020 10:13 AM, Jakub Narebski wrote:
> "Garima Singh via GitGitGadget" <[e-mail]> writes:
> 
>> From: Garima Singh <[e-mail]>
>>
>> Update the technical documentation for commit-graph-format with the formats for
>> the Bloom filter index (BIDX) and Bloom filter data (BDAT) chunks. Write the
>> computed Bloom filters information to the commit graph file using this format.
> 
> Nice description.
> 
> The only minor nitpick is with the formating: it is 80-character wide,
> which is a bit wide.
> 

Fixed in v3. Thanks! 

>>
>> Helped-by: Derrick Stolee <[e-mail]>
>> Signed-off-by: Garima Singh <[e-mail]>
>> ---
>>  .../technical/commit-graph-format.txt         |  24 ++++
>>  commit-graph.c                                | 118 +++++++++++++++++-
>>  commit-graph.h                                |   7 +-
>>  3 files changed, 145 insertions(+), 4 deletions(-)
>>
>> diff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt
>> index a4f17441ae..22e511643d 100644
>> --- a/Documentation/technical/commit-graph-format.txt
>> +++ b/Documentation/technical/commit-graph-format.txt
>> @@ -17,6 +17,9 @@ metadata, including:
>>  - The parents of the commit, stored using positional references within
>>    the graph file.
>>  
>> +- The Bloom filter of the commit carrying the paths that were changed between
>> +  the commit and its first parent.
>> +
> 
> All right.
> 
> Should we also state that it is optional (meta)data?  This would be
> first optional piece of data stored in commit-graph, I think.
> 

However the entire commit graph file is non critical metadata since git commands
work just fine without it, just slower. The same applies to the changed path
bloom filters. 

Based on the definition of optional you are suggesting, edge data is optional
because not every commit-graph has octopus merges. 

>> +
>> +  Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]
>> +    * It starts with header consisting of three unsigned 32-bit integers:
>> +      - Version of the hash algorithm being used. We currently only support
>> +	value 1 which implies the murmur3 hash implemented exactly as described
>> +	in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
> 
> First a minor issue: shouldn't this nested unordered list be indented
> with a hanging indent formatted with spaces?  That is be formatted like
> the following:
> 
>   +  Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]
>   +    * It starts with header consisting of three unsigned 32-bit integers:
>   +      - Version of the hash algorithm being used. We currently only support
>   +        value 1 which implies the murmur3 hash implemented exactly as
>   +        described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
> 
> But the existing formatting with spaces and tabs might be fine as it is,
> that is it renders as nested list with Asciidoc; it only looks a bit
> weird as patch, not so as text.
> 
> Second, and more important: it is in my opinion not enough information,
> at least if we are assuming that the information in this document should
> be enough for clean-room reimplementation of Bloom filter functionality
> (for example by JGit).  To generate compatible Bloom filters, one needs
> also the information on how to create $k$ functionally-independent hash
> functions out of murmur3 hash.  We do it currently using double hashing
> technique; if that changes then the exact set of bits in the Bloom
> filter would also change.
> 
> The additional description could look something like the following:
> 
>   +    * It starts with header consisting of three unsigned 32-bit integers:
>   +      - Version of the hash algorithm being used. We currently only support
>   +        value 1 which implies the murmur3_32 hash implemented exactly as
>   +        described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
>   +        and double hashing technique with 0x293ae76f and 0x7e646e2c seeds
>   +        as described in https://doi.org/10.1007/978-3-540-30494-4_26
>   +        "Bloom Filters in Probabilistic Verification"
> 
> Also, it should be explicitly noted that we use murmur3_32, because
> there is also 128-bit version of murmur3 hash.
> 

I will incorporate this in. Thanks! 


>> +    * The BDAT chunk is present iff BIDX is present.
> 
> Perhaps we should spell 'iff' in full, that is 'if and only if'?
> 

Sure. 

>> +
>>    Base Graphs List (ID: {'B', 'A', 'S', 'E'}) [Optional]
>>        This list of H-byte hashes describe a set of B commit-graph files that
>>        form a commit-graph chain. The graph position for the ith commit in this
>> diff --git a/commit-graph.c b/commit-graph.c
>> index 32a315058f..4585b3b702 100644
>> --- a/commit-graph.c
>> +++ b/commit-graph.c
>> @@ -24,8 +24,10 @@
>>  #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
>>  #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
>>  #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
>> +#define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
>> +#define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */
>>  #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
>> -#define MAX_NUM_CHUNKS 5
>> +#define MAX_NUM_CHUNKS 7
>>  
>>  #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
>>  
>> @@ -325,6 +327,32 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
>>  				chunk_repeated = 1;
>>  			else
>>  				graph->chunk_base_graphs = data + chunk_offset;
>> +			break;
>> +
>> +		case GRAPH_CHUNKID_BLOOMINDEXES:
>> +			if (graph->chunk_bloom_indexes)
>> +				chunk_repeated = 1;
>> +			else
>> +				graph->chunk_bloom_indexes = data + chunk_offset;
>> +			break;
>> +
>> +		case GRAPH_CHUNKID_BLOOMDATA:
>> +			if (graph->chunk_bloom_data)
>> +				chunk_repeated = 1;
>> +			else {
>> +				uint32_t hash_version;
>> +				graph->chunk_bloom_data = data + chunk_offset;
>> +				hash_version = get_be32(data + chunk_offset);
>> +
>> +				if (hash_version != 1)
>> +					break;
> 
> Shouldn't we mark Bloom filter as not to be used?  Or is it left for
> later commit?
> 

We take care of this in line 375. 

> In the future it might be good idea to notify the user (perhaps
> protected with some advice.* option) that there is problem with Bloom
> filter data, namely that we have encountered unsupported hash version.
> 
>> +
>> +				graph->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));
> 
> Why is this structure allocated dynamically?  We are leaking admittedly
> a small amount of memory because we never free this xmalloc() result.
> 
> If we need this field being a pointer to struct to have NULL mean no
> supported Bloom filter data, we could have instead use chunk_bloom_*
> fields instead - we can set at least one of them to NULL.
> 

I am freeing this up in free_commit_graph but I messed up putting it in the right commit. 
Sorry about that. Fixed in v3. 

Also as discussed in https://lore.kernel.org/git/[e-mail]/
there is a bug in commit-graph.c where we should be calling free_commit_graph() instead of 
just free(graph). I will do this in a separate series. 

>> +			}
>> +			break;
>>  		}
>>  
>>  		if (chunk_repeated) {
>> @@ -343,6 +371,17 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
>>  		last_chunk_offset = chunk_offset;
>>  	}
>>  
>> +	/* We need both the bloom chunks to exist together. Else ignore the data */
>> +	if ((graph->chunk_bloom_indexes && !graph->chunk_bloom_data)
>> +		 || (!graph->chunk_bloom_indexes && graph->chunk_bloom_data)) {
>> +		graph->chunk_bloom_indexes = NULL;
>> +		graph->chunk_bloom_data = NULL;
>> +		graph->bloom_filter_settings = NULL;
>> +	}
>> +
>> +	if (graph->chunk_bloom_indexes && graph->chunk_bloom_data)
>> +		load_bloom_filters();
> 
> Wouldn't it be simpler to rely on the fact that both Bloom chunks must
> exists for it to matter, and write it like this:
> 
>   +	if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) {
>   +		load_bloom_filters();
>   +	} else {
>   +		graph->chunk_bloom_indexes = NULL;
>   +		graph->chunk_bloom_data = NULL;
>   +		graph->bloom_filter_settings = NULL;
>   +	}
> 

:) Yes. Fixed in v3. 

>> +
>>  static int oid_compare(const void *_a, const void *_b)
>>  {
>>  	const struct object_id *a = (const struct object_id *)_a;
>> @@ -1198,8 +1290,8 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
>>  	load_bloom_filters();
>>  
>>  	if (ctx->report_progress)
>> -		progress = start_progress(
>> -			_("Computing commit diff Bloom filters"),
>> +		progress = start_delayed_progress(
>> +			_("Computing changed paths Bloom filters"),
>>  			ctx->commits.nr);
>>
> 
> Ooops.  This look like a fixup which should be made to the original
> earlier commit instead, isn't it?


Yes. Should have been in a previous commit. Fixed in v3. 


>>  };
>>  
>>  struct commit_graph *load_commit_graph_one_fd_st(int fd, struct stat *st);
>> @@ -77,7 +82,7 @@ enum commit_graph_write_flags {
>>  	COMMIT_GRAPH_WRITE_SPLIT      = (1 << 2),
>>  	/* Make sure that each OID in the input is a valid commit OID. */
>>  	COMMIT_GRAPH_WRITE_CHECK_OIDS = (1 << 3),
>> -	COMMIT_GRAPH_WRITE_BLOOM_FILTERS = (1 << 4)
>> +	COMMIT_GRAPH_WRITE_BLOOM_FILTERS = (1 << 4),
> 
> This looks like accidental change; if we want to use trailing comma in
> enum, this change should be in my opinion done in the commit that added
> COMMIT_GRAPH_WRITE_BLOOM_FILTERS (as I have written in a comment there).
> 

Yes, I noticed the lack of the comma later and forgot to move it to the right
commit. Fixed in v3. 

> 
> Thank you for your work on this series.
> 
> Best,
>

Jakub Narębski Feb. 25, 2020, 11:40 a.m. UTC | #3

Garima Singh <[e-mail]> writes:
> On 2/19/2020 10:13 AM, Jakub Narebski wrote:
>> "Garima Singh via GitGitGadget" <[e-mail]> writes:
[...]
>>> diff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt
>>> index a4f17441ae..22e511643d 100644
>>> --- a/Documentation/technical/commit-graph-format.txt
>>> +++ b/Documentation/technical/commit-graph-format.txt
>>> @@ -17,6 +17,9 @@ metadata, including:
>>>  - The parents of the commit, stored using positional references within
>>>    the graph file.
>>>  
>>> +- The Bloom filter of the commit carrying the paths that were changed between
>>> +  the commit and its first parent.
>>> +
>> 
>> All right.
>> 
>> Should we also state that it is optional (meta)data?  This would be
>> first optional piece of data stored in commit-graph, I think.
>> 
>
> However the entire commit graph file is non critical metadata since git commands
> work just fine without it, just slower. The same applies to the changed path
> bloom filters. 
>
> Based on the definition of optional you are suggesting, edge data is optional
> because not every commit-graph has octopus merges. 

Well, edge data (EDGE chunk) is optional in different way from Bloom
filter data.  The former depends on the repository (whether there are
octopus merges used), the latter is opt-in user choice (whether to run
`git commit-graph write` with the `--changed-paths` option, or in the
future equivalent config option).

To provide some advise that can be acted upon: perhaps it would be
better to start with "It can store", or end with "if requested" or
"optionally".  For example the change could look like the following
suggestion:


 The Git commit graph stores a list of commit OIDs and some associated
 metadata, including:
[...]
+- The Bloom filter of the commit carrying the paths that were changed between
+  the commit and its first parent, if requested.
+

Best,

Garima Singh Feb. 25, 2020, 3:58 p.m. UTC | #4

On 2/25/2020 6:40 AM, Jakub Narebski wrote:
> Garima Singh <[e-mail]> writes:
>> On 2/19/2020 10:13 AM, Jakub Narebski wrote:
>>> "Garima Singh via GitGitGadget" <[e-mail]> writes:
> [...]
>>>> diff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt
>>>> index a4f17441ae..22e511643d 100644
>>>> --- a/Documentation/technical/commit-graph-format.txt
>>>> +++ b/Documentation/technical/commit-graph-format.txt
>>>> @@ -17,6 +17,9 @@ metadata, including:
>>>>  - The parents of the commit, stored using positional references within
>>>>    the graph file.
>>>>  
>>>> +- The Bloom filter of the commit carrying the paths that were changed between
>>>> +  the commit and its first parent.
>>>> +
>>>
>>> All right.
>>>
>>> Should we also state that it is optional (meta)data?  This would be
>>> first optional piece of data stored in commit-graph, I think.
>>>
>>
>> However the entire commit graph file is non critical metadata since git commands
>> work just fine without it, just slower. The same applies to the changed path
>> bloom filters. 
>>
>> Based on the definition of optional you are suggesting, edge data is optional
>> because not every commit-graph has octopus merges. 
> 
> Well, edge data (EDGE chunk) is optional in different way from Bloom
> filter data.  The former depends on the repository (whether there are
> octopus merges used), the latter is opt-in user choice (whether to run
> `git commit-graph write` with the `--changed-paths` option, or in the
> future equivalent config option).
> 
> To provide some advise that can be acted upon: perhaps it would be
> better to start with "It can store", or end with "if requested" or
> "optionally".  For example the change could look like the following
> suggestion:
> 
> 
>  The Git commit graph stores a list of commit OIDs and some associated
>  metadata, including:
> [...]
> +- The Bloom filter of the commit carrying the paths that were changed between
> +  the commit and its first parent, if requested.
> +
> 
> Best,
> 

Sure. That makes sense. Will incorporate in v3. 

Cheers!
Garima Singh

Patch

diff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt
index a4f17441ae..22e511643d 100644
--- a/Documentation/technical/commit-graph-format.txt
+++ b/Documentation/technical/commit-graph-format.txt
@@ -17,6 +17,9 @@  metadata, including:
 - The parents of the commit, stored using positional references within
   the graph file.
 
+- The Bloom filter of the commit carrying the paths that were changed between
+  the commit and its first parent.
+
 These positional references are stored as unsigned 32-bit integers
 corresponding to the array position within the list of commit OIDs. Due
 to some special constants we use to track parents, we can store at most
@@ -93,6 +96,27 @@  CHUNK DATA:
       positions for the parents until reaching a value with the most-significant
       bit on. The other bits correspond to the position of the last parent.
 
+  Bloom Filter Index (ID: {'B', 'I', 'D', 'X'}) (N * 4 bytes) [Optional]
+    * The ith entry, BIDX[i], stores the number of 8-byte word blocks in all
+      Bloom filters from commit 0 to commit i (inclusive) in lexicographic
+      order. The Bloom filter for the i-th commit spans from BIDX[i-1] to
+      BIDX[i] (plus header length), where BIDX[-1] is 0.
+    * The BIDX chunk is ignored if the BDAT chunk is not present.
+
+  Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]
+    * It starts with header consisting of three unsigned 32-bit integers:
+      - Version of the hash algorithm being used. We currently only support
+	value 1 which implies the murmur3 hash implemented exactly as described
+	in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
+      - The number of times a path is hashed and hence the number of bit positions
+	that cumulatively determine whether a file is present in the commit.
+      - The minimum number of bits 'b' per entry in the Bloom filter. If the filter
+	contains 'n' entries, then the filter size is the minimum number of 64-bit
+	words that contain n*b bits.
+    * The rest of the chunk is the concatenation of all the computed Bloom
+      filters for the commits in lexicographic order.
+    * The BDAT chunk is present iff BIDX is present.
+
   Base Graphs List (ID: {'B', 'A', 'S', 'E'}) [Optional]
       This list of H-byte hashes describe a set of B commit-graph files that
       form a commit-graph chain. The graph position for the ith commit in this
diff --git a/commit-graph.c b/commit-graph.c
index 32a315058f..4585b3b702 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -24,8 +24,10 @@ 
 #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
 #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
+#define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
+#define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */
 #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
-#define MAX_NUM_CHUNKS 5
+#define MAX_NUM_CHUNKS 7
 
 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
 
@@ -325,6 +327,32 @@  struct commit_graph *parse_commit_graph(void *graph_map, int fd,
 				chunk_repeated = 1;
 			else
 				graph->chunk_base_graphs = data + chunk_offset;
+			break;
+
+		case GRAPH_CHUNKID_BLOOMINDEXES:
+			if (graph->chunk_bloom_indexes)
+				chunk_repeated = 1;
+			else
+				graph->chunk_bloom_indexes = data + chunk_offset;
+			break;
+
+		case GRAPH_CHUNKID_BLOOMDATA:
+			if (graph->chunk_bloom_data)
+				chunk_repeated = 1;
+			else {
+				uint32_t hash_version;
+				graph->chunk_bloom_data = data + chunk_offset;
+				hash_version = get_be32(data + chunk_offset);
+
+				if (hash_version != 1)
+					break;
+
+				graph->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));
+				graph->bloom_filter_settings->hash_version = hash_version;
+				graph->bloom_filter_settings->num_hashes = get_be32(data + chunk_offset + 4);
+				graph->bloom_filter_settings->bits_per_entry = get_be32(data + chunk_offset + 8);
+			}
+			break;
 		}
 
 		if (chunk_repeated) {
@@ -343,6 +371,17 @@  struct commit_graph *parse_commit_graph(void *graph_map, int fd,
 		last_chunk_offset = chunk_offset;
 	}
 
+	/* We need both the bloom chunks to exist together. Else ignore the data */
+	if ((graph->chunk_bloom_indexes && !graph->chunk_bloom_data)
+		 || (!graph->chunk_bloom_indexes && graph->chunk_bloom_data)) {
+		graph->chunk_bloom_indexes = NULL;
+		graph->chunk_bloom_data = NULL;
+		graph->bloom_filter_settings = NULL;
+	}
+
+	if (graph->chunk_bloom_indexes && graph->chunk_bloom_data)
+		load_bloom_filters();
+
 	hashcpy(graph->oid.hash, graph->data + graph->data_len - graph->hash_len);
 
 	if (verify_commit_graph_lite(graph)) {
@@ -1040,6 +1079,59 @@  static void write_graph_chunk_extra_edges(struct hashfile *f,
 	}
 }
 
+static void write_graph_chunk_bloom_indexes(struct hashfile *f,
+					    struct write_commit_graph_context *ctx)
+{
+	struct commit **list = ctx->commits.list;
+	struct commit **last = ctx->commits.list + ctx->commits.nr;
+	uint32_t cur_pos = 0;
+	struct progress *progress = NULL;
+	int i = 0;
+
+	if (ctx->report_progress)
+		progress = start_delayed_progress(
+			_("Writing changed paths Bloom filters index"),
+			ctx->commits.nr);
+
+	while (list < last) {
+		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
+		cur_pos += filter->len;
+		display_progress(progress, ++i);
+		hashwrite_be32(f, cur_pos);
+		list++;
+	}
+
+	stop_progress(&progress);
+}
+
+static void write_graph_chunk_bloom_data(struct hashfile *f,
+					 struct write_commit_graph_context *ctx,
+					 struct bloom_filter_settings *settings)
+{
+	struct commit **list = ctx->commits.list;
+	struct commit **last = ctx->commits.list + ctx->commits.nr;
+	struct progress *progress = NULL;
+	int i = 0;
+
+	if (ctx->report_progress)
+		progress = start_delayed_progress(
+			_("Writing changed paths Bloom filters data"),
+			ctx->commits.nr);
+
+	hashwrite_be32(f, settings->hash_version);
+	hashwrite_be32(f, settings->num_hashes);
+	hashwrite_be32(f, settings->bits_per_entry);
+
+	while (list < last) {
+		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
+		display_progress(progress, ++i);
+		hashwrite(f, filter->data, filter->len * sizeof(uint64_t));
+		list++;
+	}
+
+	stop_progress(&progress);
+}
+
 static int oid_compare(const void *_a, const void *_b)
 {
 	const struct object_id *a = (const struct object_id *)_a;
@@ -1198,8 +1290,8 @@  static void compute_bloom_filters(struct write_commit_graph_context *ctx)
 	load_bloom_filters();
 
 	if (ctx->report_progress)
-		progress = start_progress(
-			_("Computing commit diff Bloom filters"),
+		progress = start_delayed_progress(
+			_("Computing changed paths Bloom filters"),
 			ctx->commits.nr);
 
 	ALLOC_ARRAY(sorted_by_pos, ctx->commits.nr);
@@ -1444,6 +1536,7 @@  static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 	struct strbuf progress_title = STRBUF_INIT;
 	int num_chunks = 3;
 	struct object_id file_hash;
+	struct bloom_filter_settings bloom_settings = DEFAULT_BLOOM_FILTER_SETTINGS;
 
 	if (ctx->split) {
 		struct strbuf tmp_file = STRBUF_INIT;
@@ -1488,6 +1581,12 @@  static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 		chunk_ids[num_chunks] = GRAPH_CHUNKID_EXTRAEDGES;
 		num_chunks++;
 	}
+	if (ctx->changed_paths) {
+		chunk_ids[num_chunks] = GRAPH_CHUNKID_BLOOMINDEXES;
+		num_chunks++;
+		chunk_ids[num_chunks] = GRAPH_CHUNKID_BLOOMDATA;
+		num_chunks++;
+	}
 	if (ctx->num_commit_graphs_after > 1) {
 		chunk_ids[num_chunks] = GRAPH_CHUNKID_BASE;
 		num_chunks++;
@@ -1506,6 +1605,15 @@  static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 						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);
@@ -1543,6 +1651,10 @@  static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 	write_graph_chunk_data(f, hashsz, ctx);
 	if (ctx->num_extra_edges)
 		write_graph_chunk_extra_edges(f, ctx);
+	if (ctx->changed_paths) {
+		write_graph_chunk_bloom_indexes(f, ctx);
+		write_graph_chunk_bloom_data(f, ctx, &bloom_settings);
+	}
 	if (ctx->num_commit_graphs_after > 1 &&
 	    write_graph_chunk_base(f, ctx)) {
 		return -1;
diff --git a/commit-graph.h b/commit-graph.h
index 952a4b83be..25fefefb3e 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -10,6 +10,7 @@ 
 #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD "GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD"
 
 struct commit;
+struct bloom_filter_settings;
 
 char *get_commit_graph_filename(const char *obj_dir);
 int open_commit_graph(const char *graph_file, int *fd, struct stat *st);
@@ -58,6 +59,10 @@  struct commit_graph {
 	const unsigned char *chunk_commit_data;
 	const unsigned char *chunk_extra_edges;
 	const unsigned char *chunk_base_graphs;
+	const unsigned char *chunk_bloom_indexes;
+	const unsigned char *chunk_bloom_data;
+
+	struct bloom_filter_settings *bloom_filter_settings;
 };
 
 struct commit_graph *load_commit_graph_one_fd_st(int fd, struct stat *st);
@@ -77,7 +82,7 @@  enum commit_graph_write_flags {
 	COMMIT_GRAPH_WRITE_SPLIT      = (1 << 2),
 	/* Make sure that each OID in the input is a valid commit OID. */
 	COMMIT_GRAPH_WRITE_CHECK_OIDS = (1 << 3),
-	COMMIT_GRAPH_WRITE_BLOOM_FILTERS = (1 << 4)
+	COMMIT_GRAPH_WRITE_BLOOM_FILTERS = (1 << 4),
 };
 
 struct split_commit_graph_opts {