Re: [PATCH v3 09/20] commit-graph: verify corrupt OID fanout and lookup

From: Jakub Narebski <jnareb@gmail.com>
Date: May 30, 2018, 13:34 UTC
Message-ID: <86in75w9m9.fsf@gmail.com>
In-Reply-To: <20180524162504.158394-10-dstolee@microsoft.com>

Derrick Stolee <dstolee@microsoft.com> writes:

Show 6 quoted lines

> In the commit-graph file, the OID fanout chunk provides an index into
> the OID lookup. The 'verify' subcommand should find incorrect values
> in the fanout.
>
> Similarly, the 'verify' subcommand should find out-of-order values in
> the OID lookup.

O.K., the OID Lookup chunk is checked together with OID Fanout chunk because those two chunks are tightly connected: OID Fanout is fanout into OID Lookup.

Show 17 quoted lines

>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  commit-graph.c          | 36 ++++++++++++++++++++++++++++++++++++
>  t/t5318-commit-graph.sh | 22 ++++++++++++++++++++++
>  2 files changed, 58 insertions(+)
>
> diff --git a/commit-graph.c b/commit-graph.c
> index 06e3e4f9ba..cbd1aae514 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -855,6 +855,9 @@ static void graph_report(const char *fmt, ...)
>  
>  int verify_commit_graph(struct commit_graph *g)
>  {
> +	uint32_t i, cur_fanout_pos = 0;
> +	struct object_id prev_oid, cur_oid;

Minor nitpick about the naming convention: why cur_*, and not curr_*?

Show 11 quoted lines

> +
>  	if (!g) {
>  		graph_report("no commit-graph file loaded");
>  		return 1;
> @@ -869,5 +872,38 @@ int verify_commit_graph(struct commit_graph *g)
>  	if (!g->chunk_commit_data)
>  		graph_report("commit-graph is missing the Commit Data chunk");
>  
> +	if (verify_commit_graph_error)
> +		return verify_commit_graph_error;
> +

Before checking that commits in OID Lookup are sorted, and that OID Fanout correctly points into OID Lookup (thus also checking that OID Lookup is sorted), it would be good to verify that sizes of those chunks are correct.

Out of 4 standrd chunks, 1 of them (OIDF) has constant size, and 2 of
them have size given by number of commits and hash size
 - OID Fanout is (256 * 4 bytes)
 - OID Lookup is (N * H bytes),
   where N is number of commits, and H is hash size

The one that is more significant is if number of commits gets corrupted upwards, and walking through OID Lookup would lead us out of bounds, outside the file size.

IIRC we have checked that all chunks fit within file size, isn't it?

> +	for (i = 0; i < g->num_commits; i++) {
> +		hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);

Why do you use hashcpy() here, but oidcpy() below?

> +
> +		if (i && oidcmp(&prev_oid, &cur_oid) >= 0)

All right, OIDs needs to be sorted in ascending lexicographical order, and the above condition checks that this constraint is fullfilled.

> +			graph_report("commit-graph has incorrect OID order: %s then %s",
> +				     oid_to_hex(&prev_oid),
> +				     oid_to_hex(&cur_oid));

Nice informative error message.

Show 11 quoted lines

> +
> +		oidcpy(&prev_oid, &cur_oid);
> +
> +		while (cur_oid.hash[0] > cur_fanout_pos) {
> +			uint32_t fanout_value = get_be32(g->chunk_oid_fanout + cur_fanout_pos);
> +			if (i != fanout_value)
> +				graph_report("commit-graph has incorrect fanout value: fanout[%d] = %u != %u",
> +					     cur_fanout_pos, fanout_value, i);
> +
> +			cur_fanout_pos++;
> +		}

The k-th entry of fanout, F[k], stores the number of OIDs with first byte at most k.

Let's examine it in detail on a simple example:

   fanout                     lookup
   ------                     ------
   0 : 0  ---------------> 0: 1xxxx....
   1 : 2  -----\           1: 1yyyy....
   2 : 2  ------\--------> 2: 3xxxx....
   3 : 3  ---------------> 3: 4xxxx....

We are checking that after most significant byte (first byte) changes, then all fanout position up to the current first byte value (exclusive) point to current position in OID Lookup chunk.

Seems all right; it would be nice to come up with rigorous proof that it is all right.

Show 11 quoted lines

> +	}
> +
> +	while (cur_fanout_pos < 256) {
> +		uint32_t fanout_value = get_be32(g->chunk_oid_fanout + cur_fanout_pos);
> +
> +		if (g->num_commits != fanout_value)
> +			graph_report("commit-graph has incorrect fanout value: fanout[%d] = %u != %u",
> +				     cur_fanout_pos, fanout_value, i);
> +
> +		cur_fanout_pos++;
> +	}

All right, this checks that all remaining fanout entries, up and including the 255-ith entry store the total number of commits, N.

Show 25 quoted lines

> +
>  	return verify_commit_graph_error;
>  }
> diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
> index 4ef3fe3dc2..c050ef980b 100755
> --- a/t/t5318-commit-graph.sh
> +++ b/t/t5318-commit-graph.sh
> @@ -247,6 +247,7 @@ test_expect_success 'git commit-graph verify' '
>  	git commit-graph verify >output
>  '
>  
> +HASH_LEN=20
>  GRAPH_BYTE_VERSION=4
>  GRAPH_BYTE_HASH=5
>  GRAPH_BYTE_CHUNK_COUNT=6
> @@ -258,6 +259,12 @@ GRAPH_BYTE_OID_LOOKUP_ID=`expr $GRAPH_CHUNK_LOOKUP_OFFSET + \
>  			      1 \* $GRAPH_CHUNK_LOOKUP_WIDTH`
>  GRAPH_BYTE_COMMIT_DATA_ID=`expr $GRAPH_CHUNK_LOOKUP_OFFSET + \
>  				2 \* $GRAPH_CHUNK_LOOKUP_WIDTH`
> +GRAPH_FANOUT_OFFSET=`expr $GRAPH_CHUNK_LOOKUP_OFFSET + \
> +			  $GRAPH_CHUNK_LOOKUP_WIDTH \* $GRAPH_CHUNK_LOOKUP_ROWS`
> +GRAPH_BYTE_FANOUT1=`expr $GRAPH_FANOUT_OFFSET + 4 \* 4`
> +GRAPH_BYTE_FANOUT2=`expr $GRAPH_FANOUT_OFFSET + 4 \* 255`
> +GRAPH_OID_LOOKUP_OFFSET=`expr $GRAPH_FANOUT_OFFSET + 4 \* 256`
> +GRAPH_BYTE_OID_LOOKUP_ORDER=`expr $GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN \* 8`

Something that I forgot to write about in previous patch.

POSIX shell includes $(( ... )) for arithmetic expansion, there is nowadays no need to use $(expr ...), and even more no need to use pre-POSIX `expr ...`.

TLDR: use $(( ... )), not `expr ... `.

Show 9 quoted lines

>  
>  # usage: corrupt_graph_and_verify <position> <data> <string>
>  # Manipulates the commit-graph file at the position
> @@ -312,4 +319,19 @@ test_expect_success 'detect missing commit data chunk' '
>  		"missing the Commit Data chunk"
>  '
>  
> +test_expect_success 'detect incorrect fanout' '
> +	corrupt_graph_and_verify $GRAPH_BYTE_FANOUT1 "\01" \

How can you be sure that this value is incorrect?

Show 7 quoted lines

> +		"fanout value"
> +'
> +
> +test_expect_success 'detect incorrect fanout' '
> +	corrupt_graph_and_verify $GRAPH_BYTE_FANOUT2 "\01" \
> +		"fanout value"
> +'

I would prefer if different tests had different description. Those two are both 'detect incorrect layout'. What is the difference between them?

Show 5 quoted lines

> +
> +test_expect_success 'detect incorrect OID order' '
> +	corrupt_graph_and_verify $GRAPH_BYTE_OID_LOOKUP_ORDER "\01" \
> +		"incorrect OID order"
> +'

How can you be sure that this value is incorrect, or rather that it would be always incorrect?

> +
>  test_done

-- 
Jakub Narębski