[PATCH 0/4] git fsck: check pack rev-index files

[PATCH 0/4] git fsck: check pack rev-index files

[Derrick Stolee via GitGitGadget]

This series is based on tb/pack-revindex-on-disk.

The git fsck builtin does not look at the .rev files that pair with .pack
and .idx files, but should. If these files suffer a bit flip on disk, then
the invalid data may cause fetches and clones from that repository to start
failing. The fix is simple: delete the .rev file (and regenerate, if
necessary), but detection is the first step.

This series adds those checks. The initial check to verify the checksum is
probably sufficient for most real-world scenarios, but going the extra mile
to verify the rev-index contents against an in-memory rev-index helps us be
sure that there isn't a bug in the rev-index writing code of Git (which
would result in a valid checksum). Much like other file formats, an invalid
header needs to be handled separately as a malformed header may prevent the
data structures from being initialized in the first place.

This series does not validate a multi-pack-index-<hash>.rev file or the
rev-index chunk of a multi-pack-index file. These could be fast-follows,
except that there is no existing equivalent for an in-memory rev-index for
easy comparison. The rev-index chunk (which is the most-common way for a
multi-pack-index to have this information) is already covered by existing
checksum validation, at least.

Thanks, -Stolee

Derrick Stolee (4):
  fsck: create scaffolding for rev-index checks
  fsck: check rev-index checksums
  fsck: check rev-index position values
  fsck: validate .rev file header

 builtin/fsck.c           | 36 +++++++++++++++++++
 pack-bitmap.c            |  4 +--
 pack-revindex.c          | 43 +++++++++++++++++++++--
 pack-revindex.h          | 16 +++++++++
 t/t5325-reverse-index.sh | 74 ++++++++++++++++++++++++++++++++++++++++
 5 files changed, 169 insertions(+), 4 deletions(-)


base-commit: 9f7f10a282d8adeb9da0990aa0eb2adf93a47ca7
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1512%2Fderrickstolee%2Ffsck-rev-indexes-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1512/derrickstolee/fsck-rev-indexes-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1512
-- 
gitgitgadget

[PATCH 1/4] fsck: create scaffolding for rev-index checks

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <derrickstolee@github.com>

The 'fsck' builtin checks many of Git's on-disk data structures, but
does not currently validate the pack rev-index files (a .rev file to
pair with a .pack and .idx file).

Before doing a more-involved check process, create the scaffolding
within builtin/fsck.c to have a new error type and add that error type
when the API method verify_pack_revindex() returns an error. That method
does nothing currently, but we will add checks to it in later changes.

For now, check that 'git fsck' succeeds without any errors in the normal
case. Future checks will be paired with tests that corrupt the .rev file
appropriately.

Signed-off-by: Derrick Stolee <derrickstolee@github.com>
---
 builtin/fsck.c           | 30 ++++++++++++++++++++++++++++++
 pack-revindex.c          | 11 +++++++++++
 pack-revindex.h          |  8 ++++++++
 t/t5325-reverse-index.sh | 14 ++++++++++++++
 4 files changed, 63 insertions(+)

diff --git a/builtin/fsck.c b/builtin/fsck.c
index 095b39d3980..2ab78129bde 100644
--- a/builtin/fsck.c
+++ b/builtin/fsck.c
@@ -24,6 +24,7 @@
 #include "resolve-undo.h"
 #include "run-command.h"
 #include "worktree.h"
+#include "pack-revindex.h"
 
 #define REACHABLE 0x0001
 #define SEEN      0x0002
@@ -53,6 +54,7 @@ static int name_objects;
 #define ERROR_REFS 010
 #define ERROR_COMMIT_GRAPH 020
 #define ERROR_MULTI_PACK_INDEX 040
+#define ERROR_PACK_REV_INDEX 0100
 
 static const char *describe_object(const struct object_id *oid)
 {
@@ -856,6 +858,32 @@ static int mark_packed_for_connectivity(const struct object_id *oid,
 	return 0;
 }
 
+static int check_pack_rev_indexes(struct repository *r, int show_progress)
+{
+	struct progress *progress = NULL;
+	uint32_t pack_count = 0;
+	int res = 0;
+
+	if (show_progress) {
+		for (struct packed_git *p = get_all_packs(the_repository); p; p = p->next)
+			pack_count++;
+		progress = start_delayed_progress("Verifying reverse pack-indexes", pack_count);
+		pack_count = 0;
+	}
+
+	for (struct packed_git *p = get_all_packs(the_repository); p; p = p->next) {
+		if (!load_pack_revindex(the_repository, p) &&
+		    verify_pack_revindex(p)) {
+			error(_("invalid rev-index for pack '%s'"), p->pack_name);
+			res = ERROR_PACK_REV_INDEX;
+		}
+		display_progress(progress, ++pack_count);
+	}
+	stop_progress(&progress);
+
+	return res;
+}
+
 static char const * const fsck_usage[] = {
 	N_("git fsck [--tags] [--root] [--unreachable] [--cache] [--no-reflogs]\n"
 	   "         [--[no-]full] [--strict] [--verbose] [--lost-found]\n"
@@ -1019,6 +1047,8 @@ int cmd_fsck(int argc, const char **argv, const char *prefix)
 		free_worktrees(worktrees);
 	}
 
+	errors_found |= check_pack_rev_indexes(the_repository, show_progress);
+
 	check_connectivity();
 
 	if (the_repository->settings.core_commit_graph) {
diff --git a/pack-revindex.c b/pack-revindex.c
index 29f5358b256..c3f2aaa3fea 100644
--- a/pack-revindex.c
+++ b/pack-revindex.c
@@ -301,6 +301,17 @@ int load_pack_revindex(struct repository *r, struct packed_git *p)
 	return -1;
 }
 
+/*
+ * verify_pack_revindex verifies that the on-disk rev-index for the given
+ * pack-file is the same that would be created if written from scratch.
+ *
+ * A negative number is returned on error.
+ */
+int verify_pack_revindex(struct packed_git *p)
+{
+	return 0;
+}
+
 int load_midx_revindex(struct multi_pack_index *m)
 {
 	struct strbuf revindex_name = STRBUF_INIT;
diff --git a/pack-revindex.h b/pack-revindex.h
index 46e834064e1..c8861873b02 100644
--- a/pack-revindex.h
+++ b/pack-revindex.h
@@ -51,6 +51,14 @@ struct repository;
  */
 int load_pack_revindex(struct repository *r, struct packed_git *p);
 
+/*
+ * verify_pack_revindex verifies that the on-disk rev-index for the given
+ * pack-file is the same that would be created if written from scratch.
+ *
+ * A negative number is returned on error.
+ */
+int verify_pack_revindex(struct packed_git *p);
+
 /*
  * load_midx_revindex loads the '.rev' file corresponding to the given
  * multi-pack index by mmap-ing it and assigning pointers in the
diff --git a/t/t5325-reverse-index.sh b/t/t5325-reverse-index.sh
index 0548fce1aa6..206c412f50b 100755
--- a/t/t5325-reverse-index.sh
+++ b/t/t5325-reverse-index.sh
@@ -131,4 +131,18 @@ test_expect_success 'revindex in-memory vs on-disk' '
 		test_cmp on-disk in-core
 	)
 '
+
+test_expect_success 'fsck succeeds on good rev-index' '
+	test_when_finished rm -fr repo &&
+	git init repo &&
+	(
+		cd repo &&
+
+		test_commit commit &&
+		git -c pack.writeReverseIndex=true repack -ad &&
+		git fsck 2>err &&
+		test_must_be_empty err
+	)
+'
+
 test_done
-- 
gitgitgadget

[PATCH 2/4] fsck: check rev-index checksums

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <derrickstolee@github.com>

The previous change added calls to verify_pack_revindex() in
builtin/fsck.c, but the implementation of the method was left empty. Add
the first and most-obvious check to this method: checksum verification.

While here, create a helper method in the test script that makes it easy
to adjust the .rev file and check that 'git fsck' reports the correct
error message.

Signed-off-by: Derrick Stolee <derrickstolee@github.com>
---
 pack-revindex.c          | 10 ++++++++++
 t/t5325-reverse-index.sh | 40 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 50 insertions(+)

diff --git a/pack-revindex.c b/pack-revindex.c
index c3f2aaa3fea..007a806994f 100644
--- a/pack-revindex.c
+++ b/pack-revindex.c
@@ -5,6 +5,7 @@
 #include "packfile.h"
 #include "config.h"
 #include "midx.h"
+#include "csum-file.h"
 
 struct revindex_entry {
 	off_t offset;
@@ -309,6 +310,15 @@ int load_pack_revindex(struct repository *r, struct packed_git *p)
  */
 int verify_pack_revindex(struct packed_git *p)
 {
+	/* Do not bother checking if not initialized. */
+	if (!p->revindex_map)
+		return 0;
+
+	if (!hashfile_checksum_valid((const unsigned char *)p->revindex_map, p->revindex_size)) {
+		error(_("invalid checksum"));
+		return -1;
+	}
+
 	return 0;
 }
 
diff --git a/t/t5325-reverse-index.sh b/t/t5325-reverse-index.sh
index 206c412f50b..6b7c709a1f6 100755
--- a/t/t5325-reverse-index.sh
+++ b/t/t5325-reverse-index.sh
@@ -145,4 +145,44 @@ test_expect_success 'fsck succeeds on good rev-index' '
 	)
 '
 
+test_expect_success 'set up rev-index corruption tests' '
+	git init corrupt &&
+	(
+		cd corrupt &&
+
+		test_commit commit &&
+		git -c pack.writeReverseIndex=true repack -ad &&
+
+		revfile=$(ls .git/objects/pack/pack-*.rev) &&
+		chmod a+w $revfile &&
+		cp $revfile $revfile.bak
+	)
+'
+
+corrupt_rev_and_verify () {
+	(
+		pos="$1" &&
+		value="$2" &&
+		error="$3" &&
+
+		cd corrupt &&
+		revfile=$(ls .git/objects/pack/pack-*.rev) &&
+
+		# Reset to original rev-file.
+		cp $revfile.bak $revfile &&
+
+		printf "$value" | dd of=$revfile bs=1 seek="$pos" conv=notrunc &&
+		test_must_fail git fsck 2>err &&
+		grep "$error" err
+	)
+}
+
+test_expect_success 'fsck catches invalid checksum' '
+	revfile=$(ls corrupt/.git/objects/pack/pack-*.rev) &&
+	orig_size=$(wc -c <$revfile) &&
+	hashpos=$((orig_size - 10)) &&
+	corrupt_rev_and_verify $hashpos bogus \
+		"invalid checksum"
+'
+
 test_done
-- 
gitgitgadget

[PATCH 3/4] fsck: check rev-index position values

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <derrickstolee@github.com>

When checking a rev-index file, it may be helpful to identify exactly
which positions are incorrect. Compare the rev-index to a
freshly-computed in-memory rev-index and report the comparison failures.

This additional check (on top of the checksum validation) can help find
files that were corrupt by a single bit flip on-disk or perhaps were
written incorrectly due to a bug in Git.

Signed-off-by: Derrick Stolee <derrickstolee@github.com>
---
 pack-revindex.c          | 25 +++++++++++++++++++++----
 t/t5325-reverse-index.sh |  5 +++++
 2 files changed, 26 insertions(+), 4 deletions(-)

diff --git a/pack-revindex.c b/pack-revindex.c
index 007a806994f..62a9846470c 100644
--- a/pack-revindex.c
+++ b/pack-revindex.c
@@ -310,16 +310,33 @@ int load_pack_revindex(struct repository *r, struct packed_git *p)
  */
 int verify_pack_revindex(struct packed_git *p)
 {
+	int res = 0;
+
 	/* Do not bother checking if not initialized. */
-	if (!p->revindex_map)
-		return 0;
+	if (!p->revindex_map || !p->revindex_data)
+		return res;
 
 	if (!hashfile_checksum_valid((const unsigned char *)p->revindex_map, p->revindex_size)) {
 		error(_("invalid checksum"));
-		return -1;
+		res = -1;
 	}
 
-	return 0;
+	/* This may fail due to a broken .idx. */
+	if (create_pack_revindex_in_memory(p))
+		return res;
+
+	for (size_t i = 0; i < p->num_objects; i++) {
+		uint32_t nr = p->revindex[i].nr;
+		uint32_t rev_val = get_be32(p->revindex_data + i);
+
+		if (nr != rev_val) {
+			error(_("invalid rev-index position at %"PRIu64": %"PRIu32" != %"PRIu32""),
+			      (uint64_t)i, nr, rev_val);
+			res = -1;
+		}
+	}
+
+	return res;
 }
 
 int load_midx_revindex(struct multi_pack_index *m)
diff --git a/t/t5325-reverse-index.sh b/t/t5325-reverse-index.sh
index 6b7c709a1f6..5c3c80f88f0 100755
--- a/t/t5325-reverse-index.sh
+++ b/t/t5325-reverse-index.sh
@@ -185,4 +185,9 @@ test_expect_success 'fsck catches invalid checksum' '
 		"invalid checksum"
 '
 
+test_expect_success 'fsck catches invalid row position' '
+	corrupt_rev_and_verify 14 "\07" \
+		"invalid rev-index position"
+'
+
 test_done
-- 
gitgitgadget

[PATCH 4/4] fsck: validate .rev file header

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <derrickstolee@github.com>

While parsing a .rev file, we check the header information to be sure it
makes sense. This happens before doing any additional validation such as
a checksum or value check. In order to differentiate between a bad
header and a non-existent file, we need to update the API for loading a
reverse index.

Make load_pack_revindex_from_disk() non-static and specify that a
positive value means "the file does not exist" while other errors during
parsing are negative values. Since an invalid header prevents setting up
the structures we would use for further validations, we can stop at that
point.

The place where we can distinguish between a missing file and a corrupt
file is inside load_revindex_from_disk(), which is used both by pack
rev-indexes and multi-pack-index rev-indexes. Some tests in t5326
demonstrate that it is critical to take some conditions to allow
positive error signals.

Add tests that check the three header values.

Signed-off-by: Derrick Stolee <derrickstolee@github.com>
---
 builtin/fsck.c           | 10 ++++++++--
 pack-bitmap.c            |  4 ++--
 pack-revindex.c          |  5 +++--
 pack-revindex.h          |  8 ++++++++
 t/t5325-reverse-index.sh | 15 +++++++++++++++
 5 files changed, 36 insertions(+), 6 deletions(-)

diff --git a/builtin/fsck.c b/builtin/fsck.c
index 2ab78129bde..2414190c049 100644
--- a/builtin/fsck.c
+++ b/builtin/fsck.c
@@ -872,8 +872,14 @@ static int check_pack_rev_indexes(struct repository *r, int show_progress)
 	}
 
 	for (struct packed_git *p = get_all_packs(the_repository); p; p = p->next) {
-		if (!load_pack_revindex(the_repository, p) &&
-		    verify_pack_revindex(p)) {
+		int load_error = load_pack_revindex_from_disk(p);
+
+		if (load_error < 0) {
+			error(_("unable to load rev-index for pack '%s'"), p->pack_name);
+			res = ERROR_PACK_REV_INDEX;
+		} else if (!load_error &&
+			   !load_pack_revindex(the_repository, p) &&
+			   verify_pack_revindex(p)) {
 			error(_("invalid rev-index for pack '%s'"), p->pack_name);
 			res = ERROR_PACK_REV_INDEX;
 		}
diff --git a/pack-bitmap.c b/pack-bitmap.c
index 38b35c48237..3828aab612a 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -379,7 +379,7 @@ static int open_midx_bitmap_1(struct bitmap_index *bitmap_git,
 		goto cleanup;
 	}
 
-	if (load_midx_revindex(bitmap_git->midx) < 0) {
+	if (load_midx_revindex(bitmap_git->midx)) {
 		warning(_("multi-pack bitmap is missing required reverse index"));
 		goto cleanup;
 	}
@@ -2140,7 +2140,7 @@ uint32_t *create_bitmap_mapping(struct bitmap_index *bitmap_git,
 
 	if (!bitmap_is_midx(bitmap_git))
 		load_reverse_index(r, bitmap_git);
-	else if (load_midx_revindex(bitmap_git->midx) < 0)
+	else if (load_midx_revindex(bitmap_git->midx))
 		BUG("rebuild_existing_bitmaps: missing required rev-cache "
 		    "extension");
 
diff --git a/pack-revindex.c b/pack-revindex.c
index 62a9846470c..146334e2c96 100644
--- a/pack-revindex.c
+++ b/pack-revindex.c
@@ -212,7 +212,8 @@ static int load_revindex_from_disk(char *revindex_name,
 	fd = git_open(revindex_name);
 
 	if (fd < 0) {
-		ret = -1;
+		/* "No file" means return 1. */
+		ret = 1;
 		goto cleanup;
 	}
 	if (fstat(fd, &st)) {
@@ -264,7 +265,7 @@ cleanup:
 	return ret;
 }
 
-static int load_pack_revindex_from_disk(struct packed_git *p)
+int load_pack_revindex_from_disk(struct packed_git *p)
 {
 	char *revindex_name;
 	int ret;
diff --git a/pack-revindex.h b/pack-revindex.h
index c8861873b02..6dd47efea10 100644
--- a/pack-revindex.h
+++ b/pack-revindex.h
@@ -51,6 +51,14 @@ struct repository;
  */
 int load_pack_revindex(struct repository *r, struct packed_git *p);
 
+/*
+ * Specifically load a pack revindex from disk.
+ *
+ * Returns 0 on success, 1 on "no .rev file", and -1 when there is an
+ * error parsing the .rev file.
+ */
+int load_pack_revindex_from_disk(struct packed_git *p);
+
 /*
  * verify_pack_revindex verifies that the on-disk rev-index for the given
  * pack-file is the same that would be created if written from scratch.
diff --git a/t/t5325-reverse-index.sh b/t/t5325-reverse-index.sh
index 5c3c80f88f0..431a603ca0e 100755
--- a/t/t5325-reverse-index.sh
+++ b/t/t5325-reverse-index.sh
@@ -190,4 +190,19 @@ test_expect_success 'fsck catches invalid row position' '
 		"invalid rev-index position"
 '
 
+test_expect_success 'fsck catches invalid header: magic number' '
+	corrupt_rev_and_verify 1 "\07" \
+		"reverse-index file .* has unknown signature"
+'
+
+test_expect_success 'fsck catches invalid header: version' '
+	corrupt_rev_and_verify 7 "\02" \
+		"reverse-index file .* has unsupported version"
+'
+
+test_expect_success 'fsck catches invalid header: hash function' '
+	corrupt_rev_and_verify 11 "\03" \
+		"reverse-index file .* has unsupported hash id"
+'
+
 test_done
-- 
gitgitgadget

Re: [PATCH 0/4] git fsck: check pack rev-index files

[Junio C Hamano]

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

> This series is based on tb/pack-revindex-on-disk.
>
> The git fsck builtin does not look at the .rev files that pair with .pack
> and .idx files, but should.

Yes, it should.

> ... The fix is simple: delete the .rev file (and regenerate, if
> necessary), but detection is the first step.

> This series adds those checks. The initial check to verify the checksum is
> probably sufficient for most real-world scenarios, but going the extra mile
> to verify the rev-index contents against an in-memory rev-index helps us be
> sure that there isn't a bug in the rev-index writing code of Git (which
> would result in a valid checksum).

Good description.

> Much like other file formats, an invalid
> header needs to be handled separately as a malformed header may prevent the
> data structures from being initialized in the first place.

> This series does not validate a multi-pack-index-<hash>.rev file or the
> rev-index chunk of a multi-pack-index file. These could be fast-follows,
> except that there is no existing equivalent for an in-memory rev-index for
> easy comparison. The rev-index chunk (which is the most-common way for a
> multi-pack-index to have this information) is already covered by existing
> checksum validation, at least.

TIL what "fast-follow" means ;-)

Re: [PATCH 3/4] fsck: check rev-index position values

[Junio C Hamano]

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

>  	if (!hashfile_checksum_valid((const unsigned char *)p->revindex_map, p->revindex_size)) {
>  		error(_("invalid checksum"));
> -		return -1;
> +		res = -1;
>  	}
>  
> -	return 0;
> +	/* This may fail due to a broken .idx. */
> +	if (create_pack_revindex_in_memory(p))
> +		return res;

Here, if the revindex file itself is self consistent, res would
still be 0, so we will end up silently returning.  Is the idea that
while whatever causes in-memory revindex fail to be computed is a
concern from the point of view of the repository's health, it would
be caught elsewhere as a problem for the <pack,idx> pair we are
seeing here?

> +	for (size_t i = 0; i < p->num_objects; i++) {
> +		uint32_t nr = p->revindex[i].nr;
> +		uint32_t rev_val = get_be32(p->revindex_data + i);
> +
> +		if (nr != rev_val) {
> +			error(_("invalid rev-index position at %"PRIu64": %"PRIu32" != %"PRIu32""),
> +			      (uint64_t)i, nr, rev_val);
> +			res = -1;
> +		}
> +	}
> +
> +	return res;
>  }
>  
>  int load_midx_revindex(struct multi_pack_index *m)
> diff --git a/t/t5325-reverse-index.sh b/t/t5325-reverse-index.sh
> index 6b7c709a1f6..5c3c80f88f0 100755
> --- a/t/t5325-reverse-index.sh
> +++ b/t/t5325-reverse-index.sh
> @@ -185,4 +185,9 @@ test_expect_success 'fsck catches invalid checksum' '
>  		"invalid checksum"
>  '
>  
> +test_expect_success 'fsck catches invalid row position' '
> +	corrupt_rev_and_verify 14 "\07" \

;-)

I wondered how the patch made this "\07" portably available; it is
fed as the format string to printf in the helper, which is clever
but obviously correct way to do this.  Nice.

> +		"invalid rev-index position"
> +'
> +
>  test_done

Re: [PATCH 2/4] fsck: check rev-index checksums

[Junio C Hamano]

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

> +corrupt_rev_and_verify () {
> +	(
> +		pos="$1" &&
> +...
> +		grep "$error" err
> +	)
> +}

Curious.  Would it work equally well to write

	corrupt_rev_and_verify () (
		pos="$1" &&
		...
		grep "$error" err
	)

without an extra level of indentation?

Re: [PATCH 1/4] fsck: create scaffolding for rev-index checks

[Taylor Blau]

On Mon, Apr 17, 2023 at 04:21:38PM +0000, Derrick Stolee via GitGitGadget wrote:
> From: Derrick Stolee <derrickstolee@github.com>
>
> The 'fsck' builtin checks many of Git's on-disk data structures, but
> does not currently validate the pack rev-index files (a .rev file to
> pair with a .pack and .idx file).
>
> Before doing a more-involved check process, create the scaffolding
> within builtin/fsck.c to have a new error type and add that error type
> when the API method verify_pack_revindex() returns an error. That method
> does nothing currently, but we will add checks to it in later changes.
>
> For now, check that 'git fsck' succeeds without any errors in the normal
> case. Future checks will be paired with tests that corrupt the .rev file
> appropriately.
>
> Signed-off-by: Derrick Stolee <derrickstolee@github.com>
> ---
>  builtin/fsck.c           | 30 ++++++++++++++++++++++++++++++
>  pack-revindex.c          | 11 +++++++++++
>  pack-revindex.h          |  8 ++++++++
>  t/t5325-reverse-index.sh | 14 ++++++++++++++
>  4 files changed, 63 insertions(+)
>
> diff --git a/builtin/fsck.c b/builtin/fsck.c
> index 095b39d3980..2ab78129bde 100644
> --- a/builtin/fsck.c
> +++ b/builtin/fsck.c
> @@ -24,6 +24,7 @@
>  #include "resolve-undo.h"
>  #include "run-command.h"
>  #include "worktree.h"
> +#include "pack-revindex.h"
>
>  #define REACHABLE 0x0001
>  #define SEEN      0x0002
> @@ -53,6 +54,7 @@ static int name_objects;
>  #define ERROR_REFS 010
>  #define ERROR_COMMIT_GRAPH 020
>  #define ERROR_MULTI_PACK_INDEX 040
> +#define ERROR_PACK_REV_INDEX 0100
>
>  static const char *describe_object(const struct object_id *oid)
>  {
> @@ -856,6 +858,32 @@ static int mark_packed_for_connectivity(const struct object_id *oid,
>  	return 0;
>  }
>
> +static int check_pack_rev_indexes(struct repository *r, int show_progress)
> +{
> +	struct progress *progress = NULL;
> +	uint32_t pack_count = 0;
> +	int res = 0;
> +
> +	if (show_progress) {
> +		for (struct packed_git *p = get_all_packs(the_repository); p; p = p->next)

It's going to take me a while to get used to these declarations inside
of for-loops!

> +			pack_count++;
> +		progress = start_delayed_progress("Verifying reverse pack-indexes", pack_count);

I wonder if we want to count over the sum of objects in packs rather
than the number of packs themselves. My worry would be that a rather
large pack would make it appear as if nothing is happening when in
reality we're just churning through a lot of objects.

> +		pack_count = 0;
> +	}
> +
> +	for (struct packed_git *p = get_all_packs(the_repository); p; p = p->next) {
> +		if (!load_pack_revindex(the_repository, p) &&

I was going to comment that I wasn't sure if `load_pack_revindex()` was
the right thing here, since we don't care about validating the
on-the-fly reverse indexes that we generate.

But I see in your 3/4 that you are comparing the values on disk to those
in memory, which is very nice.

> +		    verify_pack_revindex(p)) {

Inside of verify_pack_revindex(), it says that a negative number is
returned on error. Do we care about disambiguating >= 0 here? IOW,
should this be:

    if (!load_pack_revindex(the_repository, p) || verify_pack_revindex(p) < 0)

?

All looking good otherwise.

Thanks,
Taylor

Re: [PATCH 2/4] fsck: check rev-index checksums

[Taylor Blau]

On Mon, Apr 17, 2023 at 04:21:39PM +0000, Derrick Stolee via GitGitGadget wrote:
> @@ -309,6 +310,15 @@ int load_pack_revindex(struct repository *r, struct packed_git *p)
>   */
>  int verify_pack_revindex(struct packed_git *p)
>  {
> +	/* Do not bother checking if not initialized. */

Yep, makes sense; if we don't have an on-disk reverse index (which is
mmap'd into `revindex_map` we don't have anything to verify), so we can
bail here.

> +	if (!p->revindex_map)
> +		return 0;
> +
> +	if (!hashfile_checksum_valid((const unsigned char *)p->revindex_map, p->revindex_size)) {
> +		error(_("invalid checksum"));
> +		return -1;
> +	}
> +
>  	return 0;
>  }
>
> diff --git a/t/t5325-reverse-index.sh b/t/t5325-reverse-index.sh
> index 206c412f50b..6b7c709a1f6 100755
> --- a/t/t5325-reverse-index.sh
> +++ b/t/t5325-reverse-index.sh
> @@ -145,4 +145,44 @@ test_expect_success 'fsck succeeds on good rev-index' '
>  	)
>  '
>
> +test_expect_success 'set up rev-index corruption tests' '

s/set up/setup for easy `--run`-ing (e.g., ./t5325-*.sh --run=setup,fsck).

> +	git init corrupt &&
> +	(
> +		cd corrupt &&
> +
> +		test_commit commit &&
> +		git -c pack.writeReverseIndex=true repack -ad &&
> +
> +		revfile=$(ls .git/objects/pack/pack-*.rev) &&
> +		chmod a+w $revfile &&
> +		cp $revfile $revfile.bak
> +	)
> +'
> +
> +corrupt_rev_and_verify () {
> +	(
> +		pos="$1" &&
> +		value="$2" &&
> +		error="$3" &&
> +
> +		cd corrupt &&
> +		revfile=$(ls .git/objects/pack/pack-*.rev) &&
> +
> +		# Reset to original rev-file.
> +		cp $revfile.bak $revfile &&
> +
> +		printf "$value" | dd of=$revfile bs=1 seek="$pos" conv=notrunc &&
> +		test_must_fail git fsck 2>err &&
> +		grep "$error" err
> +	)
> +}
> +
> +test_expect_success 'fsck catches invalid checksum' '
> +	revfile=$(ls corrupt/.git/objects/pack/pack-*.rev) &&

Would this test be tighter if we introduced a sub-shell and cd'd into
"corrupt" here?

> +	orig_size=$(wc -c <$revfile) &&

I'm nitpicking, but we may want to use `test_file_size` here instead of
`wc -c`. The latter outnumbers the former in terms of number of uses,
but I think we consider `test_file_size` to be canonical these days.

> +	hashpos=$((orig_size - 10)) &&
> +	corrupt_rev_and_verify $hashpos bogus \
> +		"invalid checksum"
> +'

This looks good.

Thanks,
Taylor

Re: [PATCH 3/4] fsck: check rev-index position values

[Taylor Blau]

On Mon, Apr 17, 2023 at 04:21:40PM +0000, Derrick Stolee via GitGitGadget wrote:
> +	for (size_t i = 0; i < p->num_objects; i++) {
> +		uint32_t nr = p->revindex[i].nr;
> +		uint32_t rev_val = get_be32(p->revindex_data + i);
> +
> +		if (nr != rev_val) {
> +			error(_("invalid rev-index position at %"PRIu64": %"PRIu32" != %"PRIu32""),
> +			      (uint64_t)i, nr, rev_val);
> +			res = -1;
> +		}
> +	}
> +
> +	return res;

Very clever.

I thought about it for a while, and I am pretty confident that this is
the cleanest you can get this loop to be. You could do something like
building the forward index out of inverting the values in the .rev file,
but everything I came up with based on that ended up being circular and
not demonstrating anything interesting at all.

Thanks,
Taylor

Re: [PATCH 2/4] fsck: check rev-index checksums

[Derrick Stolee]

On 4/17/2023 6:15 PM, Junio C Hamano wrote:
> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
> 
>> +corrupt_rev_and_verify () {
>> +	(
>> +		pos="$1" &&
>> +...
>> +		grep "$error" err
>> +	)
>> +}
> 
> Curious.  Would it work equally well to write
> 
> 	corrupt_rev_and_verify () (
> 		pos="$1" &&
> 		...
> 		grep "$error" err
> 	)
> 
> without an extra level of indentation?

I've never seen that replacement (and it only exists in our tree
in t4018/bash-arithmetic-function and t4018/bash-subshell-function)
but it works and looks nicer.

Thanks,
-Stolee

Re: [PATCH 2/4] fsck: check rev-index checksums

[Derrick Stolee]

On 4/17/2023 6:24 PM, Taylor Blau wrote:
> On Mon, Apr 17, 2023 at 04:21:39PM +0000, Derrick Stolee via GitGitGadget wrote:

>> +test_expect_success 'set up rev-index corruption tests' '
> 
> s/set up/setup for easy `--run`-ing (e.g., ./t5325-*.sh --run=setup,fsck).

Makes sense.

>> +test_expect_success 'fsck catches invalid checksum' '
>> +	revfile=$(ls corrupt/.git/objects/pack/pack-*.rev) &&
> 
> Would this test be tighter if we introduced a sub-shell and cd'd into
> "corrupt" here?

corrupt_rev_and_verify does the subshell thing. Why should we do that
here in the test?
 
>> +	orig_size=$(wc -c <$revfile) &&
> 
> I'm nitpicking, but we may want to use `test_file_size` here instead of
> `wc -c`. The latter outnumbers the former in terms of number of uses,
> but I think we consider `test_file_size` to be canonical these days.

Makes sense.

Thanks,
-Stolee

Re: [PATCH 3/4] fsck: check rev-index position values

[Derrick Stolee]

On 4/17/2023 6:01 PM, Junio C Hamano wrote:
> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
> 
>>  	if (!hashfile_checksum_valid((const unsigned char *)p->revindex_map, p->revindex_size)) {
>>  		error(_("invalid checksum"));
>> -		return -1;
>> +		res = -1;
>>  	}
>>  
>> -	return 0;
>> +	/* This may fail due to a broken .idx. */
>> +	if (create_pack_revindex_in_memory(p))
>> +		return res;
> 
> Here, if the revindex file itself is self consistent, res would
> still be 0, so we will end up silently returning.  Is the idea that
> while whatever causes in-memory revindex fail to be computed is a
> concern from the point of view of the repository's health, it would
> be caught elsewhere as a problem for the <pack,idx> pair we are
> seeing here?

This is something I noticed during a test suite run, where the .idx
was corrupt, so the .rev file could not be checked. In this situation,
we are not using the .rev file for anything since Git processes would
fail to lookup objects in the associated packfile.

In this case, we have no way to validate the rest of the .rev file's
contents, but at least we checked its header and checksum, which is
the best we can hope to do in this case.

Thanks,
-Stolee

Re: [PATCH 2/4] fsck: check rev-index checksums

[Taylor Blau]

On Tue, Apr 18, 2023 at 10:27:57AM -0400, Derrick Stolee wrote:
> >> +test_expect_success 'fsck catches invalid checksum' '
> >> +	revfile=$(ls corrupt/.git/objects/pack/pack-*.rev) &&
> >
> > Would this test be tighter if we introduced a sub-shell and cd'd into
> > "corrupt" here?
>
> corrupt_rev_and_verify does the subshell thing. Why should we do that
> here in the test?

I was thinking that it might be more concise if you moved the subshell
to the test and out of corrupt_rev_and_verify. In addition to making
corrupt_rev_and_verify work in other instances where the repository
isn't required to be in a directory named "corrupt", I think it
simplifies the result.

Here's what I was thinking, as a diff on top of this patch:

--- >8 ---
diff --git a/t/t5325-reverse-index.sh b/t/t5325-reverse-index.sh
index 6b7c709a1f..7dfbaf6b37 100755
--- a/t/t5325-reverse-index.sh
+++ b/t/t5325-reverse-index.sh
@@ -160,29 +160,30 @@ test_expect_success 'set up rev-index corruption tests' '
 '

 corrupt_rev_and_verify () {
-	(
-		pos="$1" &&
-		value="$2" &&
-		error="$3" &&
+	pos="$1" &&
+	value="$2" &&
+	error="$3" &&

-		cd corrupt &&
-		revfile=$(ls .git/objects/pack/pack-*.rev) &&
+	revfile=$(ls .git/objects/pack/pack-*.rev) &&

-		# Reset to original rev-file.
-		cp $revfile.bak $revfile &&
+	# Reset to original rev-file.
+	cp $revfile.bak $revfile &&

-		printf "$value" | dd of=$revfile bs=1 seek="$pos" conv=notrunc &&
-		test_must_fail git fsck 2>err &&
-		grep "$error" err
-	)
+	printf "$value" | dd of=$revfile bs=1 seek="$pos" conv=notrunc &&
+	test_must_fail git fsck 2>err &&
+	grep "$error" err
 }

 test_expect_success 'fsck catches invalid checksum' '
-	revfile=$(ls corrupt/.git/objects/pack/pack-*.rev) &&
-	orig_size=$(wc -c <$revfile) &&
-	hashpos=$((orig_size - 10)) &&
-	corrupt_rev_and_verify $hashpos bogus \
-		"invalid checksum"
+	(
+		cd corrupt &&
+
+		revfile=$(ls .git/objects/pack/pack-*.rev) &&
+		orig_size=$(wc -c <$revfile) &&
+		hashpos=$((orig_size - 10)) &&
+		corrupt_rev_and_verify $hashpos bogus \
+			"invalid checksum"
+	)
 '

 test_done
--- 8< ---

If you do take my suggestion, make sure to remember to come back in
patches 3/4 and 4/4 and adjust those instances of
'corrupt_rev_and_verify' to first change into "corrupt".

Thanks,
Taylor

Re: [PATCH 2/4] fsck: check rev-index checksums

[Derrick Stolee]

On 4/18/2023 10:51 AM, Taylor Blau wrote:
> On Tue, Apr 18, 2023 at 10:27:57AM -0400, Derrick Stolee wrote:
>>>> +test_expect_success 'fsck catches invalid checksum' '
>>>> +	revfile=$(ls corrupt/.git/objects/pack/pack-*.rev) &&
>>>
>>> Would this test be tighter if we introduced a sub-shell and cd'd into
>>> "corrupt" here?
>>
>> corrupt_rev_and_verify does the subshell thing. Why should we do that
>> here in the test?
> 
> I was thinking that it might be more concise if you moved the subshell
> to the test and out of corrupt_rev_and_verify. In addition to making
> corrupt_rev_and_verify work in other instances where the repository
> isn't required to be in a directory named "corrupt", I think it
> simplifies the result.

I don't think there is a good reason to allow using a different repo
name. This is the only test that requires doing anything but calling
corrupt_rev_and_verify with different parameters, so I think this
makes the test script at the end of the series noisier.

Thanks,
-Stolee

Re: [PATCH 2/4] fsck: check rev-index checksums

[Taylor Blau]

On Tue, Apr 18, 2023 at 10:57:15AM -0400, Derrick Stolee wrote:
> On 4/18/2023 10:51 AM, Taylor Blau wrote:
> > On Tue, Apr 18, 2023 at 10:27:57AM -0400, Derrick Stolee wrote:
> >>>> +test_expect_success 'fsck catches invalid checksum' '
> >>>> +	revfile=$(ls corrupt/.git/objects/pack/pack-*.rev) &&
> >>>
> >>> Would this test be tighter if we introduced a sub-shell and cd'd into
> >>> "corrupt" here?
> >>
> >> corrupt_rev_and_verify does the subshell thing. Why should we do that
> >> here in the test?
> >
> > I was thinking that it might be more concise if you moved the subshell
> > to the test and out of corrupt_rev_and_verify. In addition to making
> > corrupt_rev_and_verify work in other instances where the repository
> > isn't required to be in a directory named "corrupt", I think it
> > simplifies the result.
>
> I don't think there is a good reason to allow using a different repo
> name. This is the only test that requires doing anything but calling
> corrupt_rev_and_verify with different parameters, so I think this
> makes the test script at the end of the series noisier.

No worries. I was thinking that it might be convenient in the future if
we wanted to corrupt a .rev file in a different repository, but that's
absolutely a bridge we can cross if/when we get to it.

Thanks,
Taylor

Re: [PATCH 0/4] git fsck: check pack rev-index files

[Taylor Blau]

On Mon, Apr 17, 2023 at 04:21:37PM +0000, Derrick Stolee via GitGitGadget wrote:
>  builtin/fsck.c           | 36 +++++++++++++++++++
>  pack-bitmap.c            |  4 +--
>  pack-revindex.c          | 43 +++++++++++++++++++++--
>  pack-revindex.h          | 16 +++++++++
>  t/t5325-reverse-index.sh | 74 ++++++++++++++++++++++++++++++++++++++++
>  5 files changed, 169 insertions(+), 4 deletions(-)

I gave this a thorough look and it all looks good to me.

I left a couple of minor comments throughout, e.g., s/set up/setup, and
replacing 'wc -c' with 'test_file_size', but I doubt either of those are
a big enough deal to merit a reroll.

So I'd be happy to see this start moving forward as-is. I think that the
topic it depends on, tb/pack-revindex-on-disk is similarly ready for
merging.

Thanks,
Taylor

Re: [PATCH 0/4] git fsck: check pack rev-index files

[Junio C Hamano]

Taylor Blau <me@ttaylorr.com> writes:

> On Mon, Apr 17, 2023 at 04:21:37PM +0000, Derrick Stolee via GitGitGadget wrote:
>>  builtin/fsck.c           | 36 +++++++++++++++++++
>>  pack-bitmap.c            |  4 +--
>>  pack-revindex.c          | 43 +++++++++++++++++++++--
>>  pack-revindex.h          | 16 +++++++++
>>  t/t5325-reverse-index.sh | 74 ++++++++++++++++++++++++++++++++++++++++
>>  5 files changed, 169 insertions(+), 4 deletions(-)
>
> I gave this a thorough look and it all looks good to me.

This looked good to me, too.  I was planning to wait for a few days
to see what others find.

Thanks.