git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: Derrick Stolee <dstolee@microsoft.com>
To: "git@vger.kernel.org" <git@vger.kernel.org>
Cc: "stolee@gmail.com" <stolee@gmail.com>,
	"jnareb@gmail.com" <jnareb@gmail.com>,
	"avarab@gmail.com" <avarab@gmail.com>,
	"marten.agren@gmail.com" <marten.agren@gmail.com>,
	"gitster@pobox.com" <gitster@pobox.com>,
	Derrick Stolee <dstolee@microsoft.com>
Subject: [PATCH v4 12/21] commit-graph: verify parent list
Date: Mon, 4 Jun 2018 16:52:41 +0000	[thread overview]
Message-ID: <20180604165200.29261-13-dstolee@microsoft.com> (raw)
In-Reply-To: <20180604165200.29261-1-dstolee@microsoft.com>

The commit-graph file stores parents in a two-column portion of the
commit data chunk. If there is only one parent, then the second column
stores 0xFFFFFFFF to indicate no second parent.

The 'verify' subcommand checks the parent list for the commit loaded
from the commit-graph and the one parsed from the object database. Test
these checks for corrupt parents, too many parents, and wrong parents.

Add a boundary check to insert_parent_or_die() for when the parent
position value is out of range.

The octopus merge will be tested in a later commit.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c          | 28 ++++++++++++++++++++++++++++
 t/t5318-commit-graph.sh | 18 ++++++++++++++++++
 2 files changed, 46 insertions(+)

diff --git a/commit-graph.c b/commit-graph.c
index 50a8e27910..d2a86e329e 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -240,6 +240,9 @@ static struct commit_list **insert_parent_or_die(struct commit_graph *g,
 	struct commit *c;
 	struct object_id oid;
 
+	if (pos >= g->num_commits)
+		die("invalid parent position %"PRIu64, pos);
+
 	hashcpy(oid.hash, g->chunk_oid_lookup + g->hash_len * pos);
 	c = lookup_commit(&oid);
 	if (!c)
@@ -903,6 +906,7 @@ int verify_commit_graph(struct commit_graph *g)
 
 	for (i = 0; i < g->num_commits; i++) {
 		struct commit *graph_commit, *odb_commit;
+		struct commit_list *graph_parents, *odb_parents;
 
 		hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
 
@@ -920,6 +924,30 @@ int verify_commit_graph(struct commit_graph *g)
 				     oid_to_hex(&cur_oid),
 				     oid_to_hex(get_commit_tree_oid(graph_commit)),
 				     oid_to_hex(get_commit_tree_oid(odb_commit)));
+
+		graph_parents = graph_commit->parents;
+		odb_parents = odb_commit->parents;
+
+		while (graph_parents) {
+			if (odb_parents == NULL) {
+				graph_report("commit-graph parent list for commit %s is too long",
+					     oid_to_hex(&cur_oid));
+				break;
+			}
+
+			if (oidcmp(&graph_parents->item->object.oid, &odb_parents->item->object.oid))
+				graph_report("commit-graph parent for %s is %s != %s",
+					     oid_to_hex(&cur_oid),
+					     oid_to_hex(&graph_parents->item->object.oid),
+					     oid_to_hex(&odb_parents->item->object.oid));
+
+			graph_parents = graph_parents->next;
+			odb_parents = odb_parents->next;
+		}
+
+		if (odb_parents != NULL)
+			graph_report("commit-graph parent list for commit %s terminates early",
+				     oid_to_hex(&cur_oid));
 	}
 
 	return verify_commit_graph_error;
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index c0c1248eda..ec0964112a 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -269,6 +269,9 @@ GRAPH_BYTE_OID_LOOKUP_ORDER=$(($GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN \* 8))
 GRAPH_BYTE_OID_LOOKUP_MISSING=$(($GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN \* 4 + 10))
 GRAPH_COMMIT_DATA_OFFSET=$(($GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN \* $NUM_COMMITS))
 GRAPH_BYTE_COMMIT_TREE=$GRAPH_COMMIT_DATA_OFFSET
+GRAPH_BYTE_COMMIT_PARENT=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN))
+GRAPH_BYTE_COMMIT_EXTRA_PARENT=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 4))
+GRAPH_BYTE_COMMIT_WRONG_PARENT=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 3))
 
 # usage: corrupt_graph_and_verify <position> <data> <string>
 # Manipulates the commit-graph file at the position
@@ -348,4 +351,19 @@ test_expect_success 'detect incorrect tree OID' '
 		"root tree OID for commit"
 '
 
+test_expect_success 'detect incorrect parent int-id' '
+	corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_PARENT "\01" \
+		"invalid parent"
+'
+
+test_expect_success 'detect extra parent int-id' '
+	corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_EXTRA_PARENT "\00" \
+		"is too long"
+'
+
+test_expect_success 'detect wrong parent' '
+	corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_WRONG_PARENT "\01" \
+		"commit-graph parent for"
+'
+
 test_done
-- 
2.18.0.rc1


  parent reply	other threads:[~2018-06-04 16:52 UTC|newest]

Thread overview: 125+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-06-04 16:52 [PATCH v4 00/21] Integrate commit-graph into 'fsck' and 'gc' Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 01/21] commit-graph: UNLEAK before die() Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 02/21] commit-graph: fix GRAPH_MIN_SIZE Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 03/21] commit-graph: parse commit from chosen graph Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 04/21] commit: force commit to parse from object database Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 05/21] commit-graph: load a root tree from specific graph Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 06/21] commit-graph: add 'verify' subcommand Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 07/21] commit-graph: verify catches corrupt signature Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 08/21] commit-graph: verify required chunks are present Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 09/21] commit-graph: verify corrupt OID fanout and lookup Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 10/21] commit-graph: verify objects exist Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 11/21] commit-graph: verify root tree OIDs Derrick Stolee
2018-06-04 16:52 ` Derrick Stolee [this message]
2018-06-04 16:52 ` [PATCH v4 13/21] commit-graph: verify generation number Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 14/21] commit-graph: verify commit date Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 15/21] commit-graph: test for corrupted octopus edge Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 16/21] commit-graph: verify contents match checksum Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 17/21] fsck: verify commit-graph Derrick Stolee
2018-06-06 11:08   ` Ævar Arnfjörð Bjarmason
2018-06-06 11:31     ` Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 18/21] commit-graph: use string-list API for input Derrick Stolee
2018-06-04 16:52 ` [PATCH v4 19/21] commit-graph: add '--reachable' option Derrick Stolee
2018-06-04 16:53 ` [PATCH v4 20/21] gc: automatically write commit-graph files Derrick Stolee
2018-06-06 11:11   ` Ævar Arnfjörð Bjarmason
2018-06-04 16:53 ` [PATCH v4 21/21] commit-graph: update design document Derrick Stolee
2018-06-04 17:02 ` [PATCH v4 00/21] Integrate commit-graph into 'fsck' and 'gc' Derrick Stolee
2018-06-05 14:51 ` Ævar Arnfjörð Bjarmason
2018-06-05 16:37   ` Derrick Stolee
2018-06-06 11:36 ` [PATCH v5 " Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 01/21] commit-graph: UNLEAK before die() Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 03/21] commit-graph: parse commit from chosen graph Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 02/21] commit-graph: fix GRAPH_MIN_SIZE Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 04/21] commit: force commit to parse from object database Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 05/21] commit-graph: load a root tree from specific graph Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 06/21] commit-graph: add 'verify' subcommand Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 07/21] commit-graph: verify catches corrupt signature Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 08/21] commit-graph: verify required chunks are present Derrick Stolee
2018-06-06 12:21     ` Ævar Arnfjörð Bjarmason
2018-06-06 11:36   ` [PATCH v5 09/21] commit-graph: verify corrupt OID fanout and lookup Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 10/21] commit-graph: verify objects exist Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 11/21] commit-graph: verify root tree OIDs Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 12/21] commit-graph: verify parent list Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 13/21] commit-graph: verify generation number Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 14/21] commit-graph: verify commit date Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 15/21] commit-graph: test for corrupted octopus edge Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 16/21] commit-graph: verify contents match checksum Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 17/21] fsck: verify commit-graph Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 18/21] commit-graph: use string-list API for input Derrick Stolee
2018-06-06 12:11     ` Ævar Arnfjörð Bjarmason
2018-06-06 12:15       ` Derrick Stolee
2018-06-06 12:26         ` Ævar Arnfjörð Bjarmason
2018-06-06 12:45           ` Derrick Stolee
2018-06-08 12:48             ` Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 19/21] commit-graph: add '--reachable' option Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 20/21] gc: automatically write commit-graph files Derrick Stolee
2018-06-06 11:36   ` [PATCH v5 21/21] commit-graph: update design document Derrick Stolee
2018-06-08 13:56   ` [PATCH v6 00/21] Integrate commit-graph into 'fsck' and 'gc' Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 01/21] commit-graph: UNLEAK before die() Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 02/21] commit-graph: fix GRAPH_MIN_SIZE Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 03/21] commit-graph: parse commit from chosen graph Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 04/21] commit: force commit to parse from object database Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 05/21] commit-graph: load a root tree from specific graph Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 06/21] commit-graph: add 'verify' subcommand Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 07/21] commit-graph: verify catches corrupt signature Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 08/21] commit-graph: verify required chunks are present Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 09/21] commit-graph: verify corrupt OID fanout and lookup Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 10/21] commit-graph: verify objects exist Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 12/21] commit-graph: verify parent list Derrick Stolee
2018-06-12 16:55       ` Junio C Hamano
2018-06-08 13:56     ` [PATCH v6 11/21] commit-graph: verify root tree OIDs Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 13/21] commit-graph: verify generation number Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 14/21] commit-graph: verify commit date Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 15/21] commit-graph: test for corrupted octopus edge Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 16/21] commit-graph: verify contents match checksum Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 17/21] fsck: verify commit-graph Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 19/21] commit-graph: add '--reachable' option Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 18/21] commit-graph: use string-list API for input Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 20/21] gc: automatically write commit-graph files Derrick Stolee
2018-06-08 22:24       ` SZEDER Gábor
2018-06-25 14:48         ` Derrick Stolee
2018-06-08 13:56     ` [PATCH v6 21/21] commit-graph: update design document Derrick Stolee
2018-06-08 15:05     ` [PATCH v6 00/21] Integrate commit-graph into 'fsck' and 'gc' Jakub Narębski
2018-06-08 15:11       ` Derrick Stolee
2018-06-27 13:24     ` [PATCH v7 00/22] " Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 01/22] t5318-commit-graph.sh: use core.commitGraph Derrick Stolee
2018-06-27 17:38         ` Junio C Hamano
2018-06-27 13:24       ` [PATCH v7 02/22] commit-graph: UNLEAK before die() Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 03/22] commit-graph: fix GRAPH_MIN_SIZE Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 04/22] commit-graph: parse commit from chosen graph Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 05/22] commit: force commit to parse from object database Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 06/22] commit-graph: load a root tree from specific graph Derrick Stolee
2018-07-11  9:38         ` SZEDER Gábor
2018-07-13 16:30           ` [PATCH] coccinelle: update commit.cocci Derrick Stolee
2018-07-13 17:45             ` Eric Sunshine
2018-06-27 13:24       ` [PATCH v7 07/22] commit-graph: add 'verify' subcommand Derrick Stolee
2018-06-27 21:59         ` Jonathan Tan
2018-06-29 12:47           ` Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 08/22] commit-graph: verify catches corrupt signature Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 09/22] commit-graph: verify required chunks are present Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 10/22] commit-graph: verify corrupt OID fanout and lookup Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 11/22] commit-graph: verify objects exist Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 12/22] commit-graph: verify root tree OIDs Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 13/22] commit-graph: verify parent list Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 14/22] commit-graph: verify generation number Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 15/22] commit-graph: verify commit date Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 16/22] commit-graph: test for corrupted octopus edge Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 17/22] commit-graph: verify contents match checksum Derrick Stolee
2018-06-27 17:51         ` Junio C Hamano
2018-06-27 13:24       ` [PATCH v7 18/22] fsck: verify commit-graph Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 19/22] commit-graph: use string-list API for input Derrick Stolee
2018-06-27 13:24       ` [PATCH v7 20/22] commit-graph: add '--reachable' option Derrick Stolee
2018-06-27 17:53         ` Junio C Hamano
2018-09-11  5:22         ` Christian Couder
2018-09-11 11:19           ` Derrick Stolee
2018-09-11 15:13             ` Christian Couder
2018-06-27 13:24       ` [PATCH v7 21/22] gc: automatically write commit-graph files Derrick Stolee
2018-06-27 18:09         ` Junio C Hamano
2018-06-27 18:24           ` Derrick Stolee
2018-08-03  9:39         ` SZEDER Gábor
2018-08-12 20:18         ` [PATCH] t5318: use 'test_cmp_bin' to compare " SZEDER Gábor
2018-08-13 11:24           ` Derrick Stolee
2018-08-13 11:41             ` SZEDER Gábor
2018-08-13 11:52               ` [PATCH v2] " SZEDER Gábor
2018-06-27 13:24       ` [PATCH v7 22/22] commit-graph: update design document Derrick Stolee
2018-06-27 18:09         ` Junio C Hamano

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20180604165200.29261-13-dstolee@microsoft.com \
    --to=dstolee@microsoft.com \
    --cc=avarab@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=jnareb@gmail.com \
    --cc=marten.agren@gmail.com \
    --cc=stolee@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).