midx: verify MIDX checksum before reusing
cover midx: verify MIDX checksum before reusing
Here is a small series that came out of a corruption we noticed at GitHub. The corruption is described in the third patch, but the gist is this:
- After writing a MIDX, we experience a disk failure that corrupts the contents of the repository's MIDX.
- We later go to write another MIDX, notice that one is already there, and then blindly reuse its data without checking its validity, resulting in a MIDX that contains corrupt data, but whose trailing checksum matches the preceding contents.
This series checks the validity of the trailing checksum when reusing a MIDX while writing a new one, as well as a few other related fix-ups. That should be sufficient to avoid propagating corrupt data forward while writing a MIDX.
We could go further here and run 'git multi-pack-index verify' on the existing MIDX while writing a new one, but the point of this reuse is to avoid having to re-compute/verify the contents of an existing MIDX. So a more lightweight option is pursued here, but alternatives are discussed in 3/4.
Thanks in advance for your review.
Taylor Blau (4):
csum-file: introduce checksum_valid()
commit-graph: rewrite to use checksum_valid()
midx: don't reuse corrupt MIDXs when writing
midx: report checksum mismatches during 'verify'
commit-graph.c | 14 ++++++-------- csum-file.c | 16 ++++++++++++++++ csum-file.h | 3 +++ midx.c | 13 +++++++++++++ pack-check.c | 11 +---------- t/t5319-multi-pack-index.sh | 13 +++++++++++++ 6 files changed, 52 insertions(+), 18 deletions(-)
Signature · 1 line
2.31.1.163.ga65ce7f831
PATCH 1/4 csum-file: introduce checksum_valid()
Introduce a new function which checks the validity of a file's trailing checksum. This is similar to hashfd_check(), but different since it is intended to be used by callers who aren't writing the same data (like git index-pack --verify), but who instead want to validate the integrity of data that they are reading.
Rewrite the first of two callers which could benefit from this new function in pack-check.c. Subsequent callers will be added in the following patches.
--- csum-file.c | 16 ++++++++++++++++ csum-file.h | 3 +++ pack-check.c | 11 +---------- 3 files changed, 20 insertions(+), 10 deletions(-)
csum-file.c +16 -0
@@ -217,3 +217,19 @@ uint32_t crc32_end(struct hashfile *f) f->do_crc =0 ;return f->crc32; } + +int hashfile_checksum_valid (const unsigned char *data,size_t total_len) +{ +unsigned char got[GIT_MAX_RAWSZ ]; +git_hash_ctx ctx; +size_t data_len = total_len - the_hash_algo->rawsz; + +if (total_len < the_hash_algo->rawsz) +return 0 ;/* say "too short"? */ + + the_hash_algo->init_fn (&ctx); + the_hash_algo->update_fn (&ctx, data, data_len); + the_hash_algo->final_fn (got, &ctx); + +return hasheq (got, data + data_len); +}
csum-file.h +3 -0
@@ -44,6 +44,9 @@ void hashflush(struct hashfile *f);void crc32_begin (struct hashfile *);uint32_t crc32_end (struct hashfile *); +/* Verify checksum validity while reading. Returns non-zero on success. */ +int hashfile_checksum_valid (const unsigned char *data,size_t len); +/* * Returns the total number of bytes fed to the hashfile so far (including ones * that have not been written out to the descriptor yet).
pack-check.c +1 -10
@@ -164,22 +164,13 @@ static int verify_packfile(struct repository *r,int verify_pack_index (struct packed_git *p) { -size_t len; -const unsigned char *index_base; -git_hash_ctx ctx; -unsigned char hash[GIT_MAX_RAWSZ ];int err =0 ;if (open_pack_index (p))return error ("packfile %s index not opened" , p->pack_name); - index_base = p->index_data; - len = p->index_size - the_hash_algo->rawsz;/* Verify SHA1 sum of the index file */ - the_hash_algo->init_fn (&ctx); - the_hash_algo->update_fn (&ctx, index_base, len); - the_hash_algo->final_fn (hash, &ctx); -if (!hasheq (hash, index_base + len)) +if (!hashfile_checksum_valid (p->index_data, p->index_size)) err =error ("Packfile index for %s hash mismatch" , p->pack_name);return err;
Signature · 1 line
2.31.1.163.ga65ce7f831
Re: [PATCH 1/4] csum-file: introduce checksum_valid()
Quoted 5 lines · Taylor Blau
csum-file.c +5
-0+int hashfile_checksum_valid (const unsigned char *data,size_t total_len) +{ +unsigned char got[GIT_MAX_RAWSZ ]; +git_hash_ctx ctx; +size_t data_len = total_len - the_hash_algo->rawsz;
csum-file.c uint32_t crc32_end(struct hashfile *f) · line 235
Quoted 10 lines
csum-file.c +10
-0+ +if (total_len < the_hash_algo->rawsz) +return 0 ;/* say "too short"? */ + + the_hash_algo->init_fn (&ctx); + the_hash_algo->update_fn (&ctx, data, data_len); + the_hash_algo->final_fn (got, &ctx); + +return hasheq (got, data + data_len); +}
This "too short" comment is a little ugly, but I don't think it's easy to do better. This function does not otherwise print anything to stderr, so calling error() here would probably be bad. And having multiple return types would complicate the callers.
I _suspect_ it's hard to trigger anyway, because the callers would generally have complained about a too-short file in the first place. So possibly it could be a BUG(). But I think leaving it as-is is the more conservative choice, as we don't know what checks callers will have done.
In the long run, we might want to teach this function to actually write to stderr (or an error buffer), because it may be useful to say:
hash mismatch: trailer checksum claims 1234abcd, but we computed 5678cdef
or similar. In which case we could then say "too short" in the same way. I'm content to leave that for later if somebody cares. In every case of file corruption I've seen, things are sufficiently complicated and confusing that I turn to a hex dump of the file anyway. ;)
-Peff
PATCH 2/4 commit-graph: rewrite to use checksum_valid()
In reply to Taylor BlauRewrite an existing caller in git commit-graph verify to take advantage of checksum_valid().
Note that the replacement isn't a verbatim cut-and-paste, since the new function avoids using hashfile at all and instead talks to the_hash_algo directly, but it is functionally equivalent.
--- commit-graph.c | 14 ++++++-------- 1 file changed, 6 insertions(+), 8 deletions(-)
commit-graph.c +6 -8
@@ -2422,14 +2422,16 @@ static void graph_report(const char *fmt, ...)#define GENERATION_ZERO_EXISTS 1#define GENERATION_NUMBER_EXISTS 2 +static int commit_graph_checksum_valid (struct commit_graph *g) +{ +return hashfile_checksum_valid (g->data, g->data_len); +} +int verify_commit_graph (struct repository *r,struct commit_graph *g,int flags) {uint32_t i, cur_fanout_pos =0 ;struct object_id prev_oid, cur_oid; -unsigned char checksum[GIT_MAX_HEXSZ ];int generation_zero =0 ; -struct hashfile *f; -int devnull;struct progress *progress =NULL ;int local_error =0 ;
@@ -2442,11 +2444,7 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)if (verify_commit_graph_error)return verify_commit_graph_error; - devnull =open ("/dev/null" ,O_WRONLY ); - f =hashfd (devnull,NULL ); -hashwrite (f, g->data, g->data_len - g->hash_len); -finalize_hashfile (f, checksum,CSUM_CLOSE ); -if (!hasheq (checksum, g->data + g->data_len - g->hash_len)) { +if (!commit_graph_checksum_valid (g)) {graph_report (_ ("the commit-graph file has incorrect checksum and is likely corrupt" )); verify_commit_graph_error =VERIFY_COMMIT_GRAPH_ERROR_HASH ; }
Signature · 1 line
2.31.1.163.ga65ce7f831
Re: [PATCH 2/4] commit-graph: rewrite to use checksum_valid()
Quoted 6 lines · Taylor Blau
Rewrite an existing caller in
git commit-graph verifyto take advantage ofchecksum_valid().Note that the replacement isn't a verbatim cut-and-paste, since the new function avoids using hashfile at all and instead talks to
the_hash_algodirectly, but it is functionally equivalent.
Yay. IMHO the result is much nicer, as we do not have to wonder about open() returning an error.
-Peff
PATCH 3/4 midx: don't reuse corrupt MIDXs when writing
In reply to Taylor BlauWhen writing a new multi-pack index, Git tries to reuse as much of the data from an existing MIDX as possible, like object offsets. This is done to avoid re-opening a bunch of *.idx files unnecessarily, but can lead to problems if the data we are reusing is corrupt.
That's because we'll blindly reuse data from an existing MIDX without checking its trailing checksum for validity. So if there is memory corruption while writing a MIDX, or disk corruption in the intervening period between writing and reuse, we'll blindly propagate those bad values forward.
Suppose we experience a memory corruption while writing a MIDX such that we write an incorrect object offset (or alternatively, the disk corrupts the data after being written, but before being reused). Then when we go to write a new MIDX, we'll reuse the bad object offset without checking its validity. This means that the MIDX we just wrote is broken, but its trailing checksum is in-tact, since we never bothered to look at the values before writing.
In the above, a "git multi-pack-index verify" would have caught the problem before writing, but writing a new MIDX wouldn't have noticed anything wrong, blindly carrying forward the corrupt offset.
Individual pack indexes check their validity by verifying the crc32 attached to each entry when carrying data forward during a repack. We could solve this problem for MIDXs in the same way, but individual crc32's don't make much sense, since their entries are so small. Likewise, checking the whole file on every read may be prohibitively expensive if a repository has a lot of objects, packs, or both.
But we can check the trailing checksum when reusing an existing MIDX when writing a new one. And a corrupt MIDX need not stop us from writing a new one, since we can just avoid reusing the existing one at all and pretend as if we are writing a new MIDX from scratch.
--- midx.c | 10 ++++++++++ t/t5319-multi-pack-index.sh | 8 ++++++++ 2 files changed, 18 insertions(+)
midx.c +10 -0
@@ -885,6 +885,11 @@ static void write_midx_reverse_index(char *midx_name, unsigned char *midx_hash,static void clear_midx_files_ext (struct repository *r,const char *ext,unsigned char *keep_hash); +static int midx_checksum_valid (struct multi_pack_index *m) +{ +return hashfile_checksum_valid (m->data, m->data_len); +} + static int write_midx_internal(const char *object_dir, struct multi_pack_index *m, struct string_list *packs_to_drop, const char *preferred_pack_name,
@@ -911,6 +916,11 @@ static int write_midx_internal(const char *object_dir, struct multi_pack_index *else ctx.m =load_multi_pack_index (object_dir,1 ); +if (ctx.m && !midx_checksum_valid (ctx.m)) { +warning (_ ("ignoring existing multi-pack-index; checksum mismatch" )); + ctx.m =NULL ; + } + ctx.nr =0 ; ctx.alloc = ctx.m ? ctx.m->num_packs :16 ; ctx.info =NULL ;
t/t5319-multi-pack-index.sh +8 -0
@@ -410,6 +410,14 @@ test_expect_success 'git-fsck incorrect offset' ' "git -c core.multipackindex=true fsck" ' +test_expect_success 'corrupt MIDX is not reused' ' + corrupt_midx_and_verify $MIDX_BYTE_OFFSET "\377" $objdir \ + "incorrect object offset" && + git multi-pack-index write 2>err && + test_i18ngrep checksum.mismatch err && + git multi-pack-index verify +' + test_expect_success 'repack progress off for redirected stderr' ' GIT_PROGRESS_DELAY=0 git multi-pack-index --object-dir=$objdir repack 2>err && test_line_count = 0 err
Signature · 1 line
2.31.1.163.ga65ce7f831
Re: [PATCH 3/4] midx: don't reuse corrupt MIDXs when writing
Quoted 19 lines · Taylor Blau
Suppose we experience a memory corruption while writing a MIDX such that we write an incorrect object offset (or alternatively, the disk corrupts the data after being written, but before being reused). Then when we go to write a new MIDX, we'll reuse the bad object offset without checking its validity. This means that the MIDX we just wrote is broken, but its trailing checksum is in-tact, since we never bothered to look at the values before writing.
In the above, a "git multi-pack-index verify" would have caught the problem before writing, but writing a new MIDX wouldn't have noticed anything wrong, blindly carrying forward the corrupt offset.
Individual pack indexes check their validity by verifying the crc32 attached to each entry when carrying data forward during a repack. We could solve this problem for MIDXs in the same way, but individual crc32's don't make much sense, since their entries are so small. Likewise, checking the whole file on every read may be prohibitively expensive if a repository has a lot of objects, packs, or both.
Quoted 4 lines
But we can check the trailing checksum when reusing an existing MIDX when writing a new one. And a corrupt MIDX need not stop us from writing a new one, since we can just avoid reusing the existing one at all and pretend as if we are writing a new MIDX from scratch.
Nicely explained. This is not saving us from any corruption, but it is noticing it sooner and helping us better diagnose the root problem (e.g., in our real-world case it is still only a guess that the data was corrupted after write, though there was strong correlating evidence).
I wondered what the performance implications might be.
In my fully-packed clone of linux.git with no midx, I get (before your patch):
$ time git multi-pack-index write real 0m1.358s user 0m1.119s sys 0m0.185s
Running again immediately is much faster, because we realize there's nothing new to pack:
$ time git multi-pack-index write real 0m0.007s user 0m0.000s sys 0m0.007s
If we create a dummy pack, then we do real work, which seems to take about the same amount of time as generating from scratch:
$ git pack-objects .git/objects/pack/pack </dev/null 029d08823bd8a8eab510ad6ac75c823cfd3ed31e Total 0 (delta 0), reused 0 (delta 0), pack-reused 0
$ time git multi-pack-index write real 0m1.399s user 0m1.126s sys 0m0.209s
which makes sense. Even if we are reusing the midx, there is no speedup to be gained versus the original single-pack (whereas with many packs, it would be an improvement to use the midx rather than going back to each pack idx).
Running the same sequence (after deleting the midx and the dummy pack) using your patch, the initial write is the same (unsurprising, since there is no midx to check). The final case (with the dummy pack) becomes:
$ time git multi-pack-index write real 0m1.947s user 0m1.668s sys 0m0.216s
So we really do pay a 500-600ms penalty to to look at the checksum. IMHO that is worth it, given the overall cost of the write operation, but I was surprised how big it was as a relative cost.
There is one more interesting thing, though. The 7ms "noop" version where we don't write anything also gets more expensive:
$ time git multi-pack-index write real 0m0.550s user 0m0.537s sys 0m0.013s
I suspect we could avoid that by pushing our checksum validation down a bit further in the function, but I'm not sure if that creates further problems (i.e., if we'd already have started trusting some of the midx's data by then).
I'm not sure if this "noop" midx write is common enough to worry too much about. Presumably whatever triggers "multi-pack-index write" is doing so because it just created or removed some packs. If it knows that what it did was a noop, it's probably better off skipping the call to git-multi-pack-index entirely.
All of which is to say this looks just fine to me. But I think we should make a conscious decision on the performance implications (and seeing the real numbers, it is quite clear that checking the trailer checksum on normal reads is _way_ too expensive).
-Peff
PATCH 4/4 midx: report checksum mismatches during 'verify'
In reply to Taylor Blau'git multi-pack-index verify' inspects the data in an existing MIDX for correctness by checking that the recorded object offsets are correct, and so on.
But it does not check that the file's trailing checksum matches the data that it records. So, if an on-disk corruption happened to occur in the final few bytes (and all other data was recorded correctly), we would:
- get a clean result from 'git multi-pack-index verify', but
- be unable to reuse the existing MIDX when writing a new one (since we now check for checksum mismatches before reusing a MIDX)
Teach the 'verify' sub-command to recognize corruption in the checksum by calling midx_checksum_valid().
--- midx.c | 3 +++ t/t5319-multi-pack-index.sh | 5 +++++ 2 files changed, 8 insertions(+)
midx.c +3 -0
@@ -1228,6 +1228,9 @@ int verify_midx_file(struct repository *r, const char *object_dir, unsigned flagreturn result; } +if (!midx_checksum_valid (m)) +midx_report (_ ("incorrect checksum" )); +if (flags &MIDX_PROGRESS ) progress =start_delayed_progress (_ ("Looking for referenced packfiles" ), m->num_packs);
t/t5319-multi-pack-index.sh +5 -0
@@ -418,6 +418,11 @@ test_expect_success 'corrupt MIDX is not reused' ' git multi-pack-index verify ' +test_expect_success 'verify incorrect checksum' ' + pos=$(($(wc -c <$objdir/pack/multi-pack-index) - 1)) && + corrupt_midx_and_verify $pos "\377" $objdir "incorrect checksum" +' + test_expect_success 'repack progress off for redirected stderr' ' GIT_PROGRESS_DELAY=0 git multi-pack-index --object-dir=$objdir repack 2>err && test_line_count = 0 err
Signature · 1 line
2.31.1.163.ga65ce7f831
Re: [PATCH 4/4] midx: report checksum mismatches during 'verify'
Quoted 10 lines · Taylor Blau
But it does not check that the file's trailing checksum matches the data that it records. So, if an on-disk corruption happened to occur in the final few bytes (and all other data was recorded correctly), we would:
- get a clean result from 'git multi-pack-index verify', but
- be unable to reuse the existing MIDX when writing a new one (since we now check for checksum mismatches before reusing a MIDX)Teach the 'verify' sub-command to recognize corruption in the checksum by calling
midx_checksum_valid().
...
Quoted 3 lines
midx.c +3
-0+if (!midx_checksum_valid (m)) +midx_report (_ ("incorrect checksum" )); +
...
t/t5319-multi-pack-index.sh test_expect_success 'corrupt MIDX is not reused' ' · line 425
Quoted 5 lines
t/t5319-multi-pack-index.sh +5
-0+test_expect_success 'verify incorrect checksum' ' + pos=$(($(wc -c <$objdir/pack/multi-pack-index) - 1)) && + corrupt_midx_and_verify $pos "\377" $objdir "incorrect checksum" +' +
We're in the context of checksum mismatches because of on-disk corruption, so why didn't the message say "incorrect checksum, possibly corrupt"?
Signature · 1 line
An old man doll... just what I always wanted! - Clara
Re: [PATCH 4/4] midx: report checksum mismatches during 'verify'
In reply to Taylor BlauQuoted 8 lines · Taylor Blau
'git multi-pack-index verify' inspects the data in an existing MIDX for correctness by checking that the recorded object offsets are correct, and so on.
But it does not check that the file's trailing checksum matches the data that it records. So, if an on-disk corruption happened to occur in the final few bytes (and all other data was recorded correctly), we would:
Quoted 6 lines
- get a clean result from 'git multi-pack-index verify', but
- be unable to reuse the existing MIDX when writing a new one (since we now check for checksum mismatches before reusing a MIDX)Teach the 'verify' sub-command to recognize corruption in the checksum by calling
midx_checksum_valid().
Makes sense. I was a little surprised we didn't do this already, but I guess it does not do the same "regenerate and make sure hashfile produces the same checksum" trick that the pack idx verifier does (as an aside, I think what the midx code is doing here is much _better_, because it is looking at semantic problems in the file, and is more robust against irrelevant changes in the format).
Review int verify_midx_file(struct repository *r, const char *object_dir, unsigned flag · line 1232
Quoted 6 lines
(quoted diff) +2
-0@@ -1228,6 +1228,9 @@ int verify_midx_file(struct repository *r, const char *object_dir, unsigned flag return result; } + if (!midx_checksum_valid(m)) + midx_report(_("incorrect checksum"));
This "midx_report()" function doesn't provide much context on stderr. I get:
$ echo foo >>.git/objects/pack/multi-pack-index $ git multi-pack-index verify incorrect checksum Verifying OID order in multi-pack-index: 100% (282/282), done. Sorting objects by packfile: 100% (283/283), done. Verifying object offsets: 100% (283/283), done.
I think we should at least say "error:", but something along the lines of "midx file at %s does not match its trailing checksum (possibly corruption?)". Or something like that.
I think all of the existing calls to midx_report() share this issue, though. We probably want to at least say "error:" here, but maybe even something like:
midx.c +3 -1
@@ -1172,10 +1172,12 @@ void clear_midx_file(struct repository *r)static int verify_midx_error; -static void midx_report (const char *fmt, ...) +static void midx_report (struct multi_pack_index *m,const char *fmt, ...) {va_list ap; verify_midx_error =1 ; +/* do we need to care about the "next" pointer here? */ +fprintf (stderr, ("error: %s/multi-pack-index: " ), m->object_dir);va_start (ap, fmt);vfprintf (stderr, fmt, ap);fprintf (stderr,"\n" );
Also, a side note: we should use __attribute__((format)) on this function to get compile-time checks of our format strings.
-Peff
Re: [PATCH 4/4] midx: report checksum mismatches during 'verify'
In reply to Taylor BlauQuoted 41 lines · Taylor Blau
'git multi-pack-index verify' inspects the data in an existing MIDX for correctness by checking that the recorded object offsets are correct, and so on.
But it does not check that the file's trailing checksum matches the data that it records. So, if an on-disk corruption happened to occur in the final few bytes (and all other data was recorded correctly), we would:
- get a clean result from 'git multi-pack-index verify', but
- be unable to reuse the existing MIDX when writing a new one (since we now check for checksum mismatches before reusing a MIDX)Teach the 'verify' sub-command to recognize corruption in the checksum by calling
midx_checksum_valid().Suggested-by Derrick Stolee <[email protected]>Signed-off-by Taylor Blau <[email protected]>--- midx.c | 3 +++ t/t5319-multi-pack-index.sh | 5 +++++ 2 files changed, 8 insertions(+)midx.c +3
-0@@ -1228,6 +1228,9 @@ int verify_midx_file(struct repository *r, const char *object_dir, unsigned flagreturn result; } +if (!midx_checksum_valid (m)) +midx_report (_ ("incorrect checksum" )); +if (flags &MIDX_PROGRESS ) progress =start_delayed_progress (_ ("Looking for referenced packfiles" ), m->num_packs);t/t5319-multi-pack-index.sh +0
-0
t/t5319-multi-pack-index.sh test_expect_success 'corrupt MIDX is not reused' ' · line 423
Quoted 6 lines
t/t5319-multi-pack-index.sh +3
-0@@ -418,6 +418,11 @@ test_expect_success 'corrupt MIDX is not reused' ' git multi-pack-index verify ' +test_expect_success 'verify incorrect checksum' ' + pos=$(($(wc -c <$objdir/pack/multi-pack-index) - 1)) && + corrupt_midx_and_verify $pos "\377" $objdir "incorrect checksum"
This test is flaky and can fail with:
...
+ printf \377
+ dd of=.git/objects/pack/multi-pack-index bs=1 seek=3839 conv=notrunc 1+0 records in
1+0 records out
1 byte copied, 5.0656e-05 s, 19.7 kB/s
+ test_must_fail git multi-pack-index verify --object-dir=.git/objects
test_must_fail: command succeeded: git multi-pack-index verify --object-dir=.git/objects
error: last command exited with $?=1
+ mv midx-backup .git/objects/pack/multi-pack-index
not ok 44 - verify incorrect checksum
So the test corrupts the checksum trailer in the 'multi-pack-index' file by overwriting its last byte with 0xff, but if that byte were already 0xff, then the file would be left as is, and 'git multi-pack-index verify' wouldn't find anything amiss.
Since SHA1 is essentially random, there's a 1:256 chance of that happening, assuming that the file's content is random. That't not really the case, however, because both the test repository's objects and the resulting packfiles are deterministic, and, consequently, the content of the MIDX is somewhat deterministic. Only "somewhat", though, because several of those objects appear in multiple packfiles, and the MIDX selects a copy in the most recently modified packfile, so filesystem mtime resolution and second boundaries become significant, and cause some variance in the contents of the OOFF chunk.
Recently a laptop crossed my way that is somehow exceptionally good at generating MIDX files ending with 0xff:
# ad-hoc checksum statistics: $ git diff diff --git a/t/t5319-multi-pack-index.sh b/t/t5319-multi-pack-index.sh index f1ee2ce56d..605713b518 100755 --- a/t/t5319-multi-pack-index.sh +++ b/t/t5319-multi-pack-index.sh @@ -482,9 +482,13 @@ test_expect_success 'corrupt MIDX is not reused' ' '
test_expect_success 'verify incorrect checksum' ' + skip=$(($(wc -c <$objdir/pack/multi-pack-index) - 20)) && + printf "checksum: " >&5 && + od -x -w20 -j$skip --endian=big -An "$objdir/pack/multi-pack-index" >&5 && pos=$(($(wc -c <$objdir/pack/multi-pack-index) - 1)) && corrupt_midx_and_verify $pos "\377" $objdir "incorrect checksum" ' +test_done
test_expect_success 'repack progress off for redirected stderr' '
GIT_PROGRESS_DELAY=0 git multi-pack-index --object-dir=$objdir repack 2>err &&
$ for i in {1..500} ; do ./t5319-multi-pack-index.sh |sed -n -e 's/^checksum: //p' ; done |sort |uniq -c
31 1a70 3b1c 8ed3 56a6 5101 2a38 057e 698d 6faf fbaa
340 5fc0 552f 0ac0 c876 f229 d9e3 ef13 a314 5847 89ff
129 ce7d 3710 fd21 ef7b 8316 2b99 4e6c e5d5 5e7c 7b08That's almost 70% failure rate, though I haven't been able to trigger this failure on any of the other machines that I have access to.
Re: [PATCH 4/4] midx: report checksum mismatches during 'verify'
Quoted 4 lines · SZEDER Gábor
So the test corrupts the checksum trailer in the 'multi-pack-index' file by overwriting its last byte with
0xff, but if that byte were already0xff, then the file would be left as is, and 'git multi-pack-index verify' wouldn't find anything amiss.
Good find. I tried running with the patch you showed:
Quoted 4 lines
$ for i in {1..500} ; do ./t5319-multi-pack-index.sh |sed -n -e 's/^checksum: //p' ; done |sort |uniq -c
31 1a70 3b1c 8ed3 56a6 5101 2a38 057e 698d 6faf fbaa
340 5fc0 552f 0ac0 c876 f229 d9e3 ef13 a314 5847 89ff
129 ce7d 3710 fd21 ef7b 8316 2b99 4e6c e5d5 5e7c 7b08but I only ever got the last one, even under load. However, it's easy enough to tweak the mtimes to stimulate a failure:
diff --git a/t/t5319-multi-pack-index.sh b/t/t5319-multi-pack-index.sh index 3f69e43178..b84e96779f 100755 --- a/t/t5319-multi-pack-index.sh +++ b/t/t5319-multi-pack-index.sh @@ -481,10 +481,25 @@ test_expect_success 'corrupt MIDX is not reused' ' git multi-pack-index verify ' +while true; do test_expect_success 'verify incorrect checksum' ' + t=1234567890 && + for i in $(ls $objdir/pack/*.pack | shuf) + do + touch -d @$t $i && + t=$((t+100)) + done && + rm -f $objdir/pack/multi-pack-index && + git multi-pack-index write && + skip=$(($(wc -c <$objdir/pack/multi-pack-index) - 20)) && + printf "checksum: " >&5 && + od -x -w20 -j$skip --endian=big -An "$objdir/pack/multi-pack-index" >&5 && pos=$(($(wc -c <$objdir/pack/multi-pack-index) - 1)) && corrupt_midx_and_verify $pos "\377" $objdir "incorrect checksum" ' +done + +test_done
test_expect_success 'repack progress off for redirected stderr' '
GIT_PROGRESS_DELAY=0 git multi-pack-index --object-dir=$objdir repack 2>err &&
Brute force, but it fails after a few hundred attempts. :)
Quoted 2 lines
Since SHA1 is essentially random, there's a 1:256 chance of that happening, assuming that the file's content is random.
The most exact fix here would be to read the final byte, increment it mod-256, and write it back, which would ensure it was always changed. But that's a bit annoying to do in shell. Perhaps just corrupting more bytes is a good solution? The patch below should reduce your changes to 1 in 2^80.
t/t5319-multi-pack-index.sh +4 -2
@@ -482,8 +482,10 @@ test_expect_success 'corrupt MIDX is not reused' ' ' test_expect_success 'verify incorrect checksum' ' - pos=$(($(wc -c <$objdir/pack/multi-pack-index) - 1)) && - corrupt_midx_and_verify $pos "\377" $objdir "incorrect checksum" + pos=$(($(wc -c <$objdir/pack/multi-pack-index) - 10)) && + corrupt_midx_and_verify $pos \ + "\377\377\377\377\377\377\377\377\377\377" \ + $objdir "incorrect checksum" ' test_expect_success 'repack progress off for redirected stderr' '
There are other variants, of course. Just appending a single byte to the file is enough to give you a high probability of failing the checksum (since it shifts it all by one byte, making it essentially random), but the corrupt_midx() helper doesn't support that.
-Peff
Re: [PATCH 4/4] midx: report checksum mismatches during 'verify'
Quoted 27 lines · Jeff King
Quoted 2 lines
Since SHA1 is essentially random, there's a 1:256 chance of that happening, assuming that the file's content is random.
The most exact fix here would be to read the final byte, increment it mod-256, and write it back, which would ensure it was always changed. But that's a bit annoying to do in shell. Perhaps just corrupting more bytes is a good solution? The patch below should reduce your changes to 1 in 2^80.
t/t5319-multi-pack-index.sh +4
-2@@ -482,8 +482,10 @@ test_expect_success 'corrupt MIDX is not reused' ' ' test_expect_success 'verify incorrect checksum' ' - pos=$(($(wc -c <$objdir/pack/multi-pack-index) - 1)) && - corrupt_midx_and_verify $pos "\377" $objdir "incorrect checksum" + pos=$(($(wc -c <$objdir/pack/multi-pack-index) - 10)) && + corrupt_midx_and_verify $pos \ + "\377\377\377\377\377\377\377\377\377\377" \ + $objdir "incorrect checksum" ' test_expect_success 'repack progress off for redirected stderr' '
Quoted 4 lines
There are other variants, of course. Just appending a single byte to the file is enough to give you a high probability of failing the checksum (since it shifts it all by one byte, making it essentially random), but the
corrupt_midx()helper doesn't support that.
Thanks SZEDER for the report, and thanks Peff for the fix :).
I agree that it's annoyingly cumbersome to write back the last byte incremented mod-256. So I'm content to just make it astronomically unlikely to run into a collision in practice. (As a matter of fact, I'm surprised that the current implementation hasn't produced failures for us more often).
Peff: do you want me to turn this into a patch or were you planning on it?
Thanks,
Taylor
PATCH 1/1 t5319: corrupt more bytes of the midx checksum
Quoted 5 lines · Taylor Blau
I agree that it's annoyingly cumbersome to write back the last byte incremented mod-256. So I'm content to just make it astronomically unlikely to run into a collision in practice. (As a matter of fact, I'm surprised that the current implementation hasn't produced failures for us more often).
It's quite deterministic in practice. The randomness is driven by the mtimes of the packfiles, so there are only a handful of combinations you'd see in practice (though I'm still curious why one of Gábor's machines sees it so frequently).
Quoted 2 lines
Peff: do you want me to turn this into a patch or were you planning on it?
I hadn't thought that far ahead. ;)
One thing I did wonder is whether other corruption tests might have the same problem. But if they're not triggering in practice, I don't think it's worth spending a bunch of time looking at them.
So here's this fix wrapped up with a commit message.
-- >8 --
Subject: [PATCH] t5319: corrupt more bytes of the midx checksum
One of the tests in t5319 corrupts the checksum of the midx file by writing a single 0xff over the final byte, and then confirms that we detect the problem. This usually works fine, but would break if the actual checksum ended with that same byte already.
It seems like this should happen in 1 out of 256 test runs, but it turns out to be less often in practice. The contents of the midx are mostly deterministic because it's based on the objects, and we remove most sources of randomness by setting GIT_COMMITTER_DATE, etc. However, there's still some randomness: some objects are duplicated between packs, and the midx must decide which to use, which can be based on timing.
So very occasionally we can end up with a real 0xff byte, and the test fails. The most robust fix would be to read out the final byte and then change it to something else (e.g., adding 1 mod 256). But that's awkward to do in shell. Let's just blindly corrupt 10 bytes instead of 1, which reduces our chances of an accidental noop to 1 in 2^80.
--- t/t5319-multi-pack-index.sh | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)
t/t5319-multi-pack-index.sh +4 -2
@@ -482,8 +482,10 @@ test_expect_success 'corrupt MIDX is not reused' ' ' test_expect_success 'verify incorrect checksum' ' - pos=$(($(wc -c <$objdir/pack/multi-pack-index) - 1)) && - corrupt_midx_and_verify $pos "\377" $objdir "incorrect checksum" + pos=$(($(wc -c <$objdir/pack/multi-pack-index) - 10)) && + corrupt_midx_and_verify $pos \ + "\377\377\377\377\377\377\377\377\377\377" \ + $objdir "incorrect checksum" ' test_expect_success 'repack progress off for redirected stderr' '
Signature · 1 line
2.34.0.633.g181affe237
Re: [PATCH] t5319: corrupt more bytes of the midx checksum
Quoted 9 lines · Jeff King
Quoted 2 lines · Taylor Blau
Peff: do you want me to turn this into a patch or were you planning on it?
I hadn't thought that far ahead. ;)
One thing I did wonder is whether other corruption tests might have the same problem. But if they're not triggering in practice, I don't think it's worth spending a bunch of time looking at them.
Definitely agreed. We can apply a similar fix if and when any other spots become a problem.
Quoted 1 line
So here's this fix wrapped up with a commit message.
Thanks, what you wrote looks good to me.
Thanks,
Taylor
Re: [PATCH] t5319: corrupt more bytes of the midx checksum
In reply to Jeff KingQuoted 17 lines · Jeff King
So very occasionally we can end up with a real
0xffbyte, and the test fails. The most robust fix would be to read out the final byte and then change it to something else (e.g., adding 1 mod 256). But that's awkward to do in shell. Let's just blindly corrupt 10 bytes instead of 1, which reduces our chances of an accidental noop to 1 in 2^80.Reported-by SZEDER Gábor <[email protected]>Signed-off-by Jeff King <[email protected]>--- t/t5319-multi-pack-index.sh | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)t/t5319-multi-pack-index.sh +0
-0
t/t5319-multi-pack-index.sh test_expect_success 'corrupt MIDX is not reused' ' · line 489
Quoted 10 lines
t/t5319-multi-pack-index.sh +4
-2@@ -482,8 +482,10 @@ test_expect_success 'corrupt MIDX is not reused' ' ' test_expect_success 'verify incorrect checksum' ' - pos=$(($(wc -c <$objdir/pack/multi-pack-index) - 1)) && - corrupt_midx_and_verify $pos "\377" $objdir "incorrect checksum" + pos=$(($(wc -c <$objdir/pack/multi-pack-index) - 10)) && + corrupt_midx_and_verify $pos \ + "\377\377\377\377\377\377\377\377\377\377" \ + $objdir "incorrect checksum" '
Thanks for taking the time to make this a patch. This approach looks good to me.
Thanks,
-Stolee