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: "avarab@gmail.com" <avarab@gmail.com>,
	"sbeller@google.com" <sbeller@google.com>,
	"jnareb@gmail.com" <jnareb@gmail.com>,
	"marten.agren@gmail.com" <marten.agren@gmail.com>,
	"gitster@pobox.com" <gitster@pobox.com>,
	Derrick Stolee <dstolee@microsoft.com>
Subject: [PATCH v6 13/21] commit-graph: verify generation number
Date: Fri, 8 Jun 2018 13:56:23 +0000	[thread overview]
Message-ID: <20180608135548.216405-14-dstolee@microsoft.com> (raw)
In-Reply-To: <20180608135548.216405-1-dstolee@microsoft.com>

While iterating through the commit parents, perform the generation
number calculation and compare against the value stored in the
commit-graph.

The tests demonstrate that having a different set of parents affects
the generation number calculation, and this value propagates to
descendants. Hence, we drop the single-line condition on the output.

Since Git will ship with the commit-graph feature without generation
numbers, we need to accept commit-graphs with all generation numbers
equal to zero. In this case, ignore the generation number calculation.

However, verify that we should never have a mix of zero and non-zero
generation numbers. Create a test that sets one commit to generation
zero and all following commits report a failure as they have non-zero
generation in a file that contains generation number zero.

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

diff --git a/commit-graph.c b/commit-graph.c
index 6d8d774eb0..e0f71658da 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -846,10 +846,14 @@ static void graph_report(const char *fmt, ...)
 	va_end(ap);
 }
 
+#define GENERATION_ZERO_EXISTS 1
+#define GENERATION_NUMBER_EXISTS 2
+
 int verify_commit_graph(struct repository *r, struct commit_graph *g)
 {
 	uint32_t i, cur_fanout_pos = 0;
 	struct object_id prev_oid, cur_oid;
+	int generation_zero = 0;
 
 	if (!g) {
 		graph_report("no commit-graph file loaded");
@@ -911,6 +915,7 @@ int verify_commit_graph(struct repository *r, 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;
+		uint32_t max_generation = 0;
 
 		hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
 
@@ -945,6 +950,9 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g)
 					     oid_to_hex(&graph_parents->item->object.oid),
 					     oid_to_hex(&odb_parents->item->object.oid));
 
+			if (graph_parents->item->generation > max_generation)
+				max_generation = graph_parents->item->generation;
+
 			graph_parents = graph_parents->next;
 			odb_parents = odb_parents->next;
 		}
@@ -952,6 +960,32 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g)
 		if (odb_parents != NULL)
 			graph_report("commit-graph parent list for commit %s terminates early",
 				     oid_to_hex(&cur_oid));
+
+		if (!graph_commit->generation) {
+			if (generation_zero == GENERATION_NUMBER_EXISTS)
+				graph_report("commit-graph has generation number zero for commit %s, but non-zero elsewhere",
+					     oid_to_hex(&cur_oid));
+			generation_zero = GENERATION_ZERO_EXISTS;
+		} else if (generation_zero == GENERATION_ZERO_EXISTS)
+			graph_report("commit-graph has non-zero generation number for commit %s, but zero elsewhere",
+				     oid_to_hex(&cur_oid));
+
+		if (generation_zero == GENERATION_ZERO_EXISTS)
+			continue;
+
+		/*
+		 * If one of our parents has generation GENERATION_NUMBER_MAX, then
+		 * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid
+		 * extra logic in the following condition.
+		 */
+		if (max_generation == GENERATION_NUMBER_MAX)
+			max_generation--;
+
+		if (graph_commit->generation != max_generation + 1)
+			graph_report("commit-graph generation for commit %s is %u != %u",
+				     oid_to_hex(&cur_oid),
+				     graph_commit->generation,
+				     max_generation + 1);
 	}
 
 	return verify_commit_graph_error;
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index 9a3481c30f..5b75c4dca2 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -272,6 +272,7 @@ 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))
+GRAPH_BYTE_COMMIT_GENERATION=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 11))
 
 # usage: corrupt_graph_and_verify <position> <data> <string>
 # Manipulates the commit-graph file at the position
@@ -366,4 +367,14 @@ test_expect_success 'detect wrong parent' '
 		"commit-graph parent for"
 '
 
+test_expect_success 'detect incorrect generation number' '
+	corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION "\070" \
+		"generation for commit"
+'
+
+test_expect_success 'detect incorrect generation number' '
+	corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION "\01" \
+		"non-zero generation number"
+'
+
 test_done
-- 
2.18.0.rc1


  parent reply	other threads:[~2018-06-08 13:57 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 ` [PATCH v4 12/21] commit-graph: verify parent list Derrick Stolee
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 02/21] commit-graph: fix GRAPH_MIN_SIZE 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 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 03/21] commit-graph: parse commit from chosen graph 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 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 11/21] commit-graph: verify root tree OIDs 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     ` Derrick Stolee [this message]
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 18/21] commit-graph: use string-list API for input 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 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=20180608135548.216405-14-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=sbeller@google.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).