Assertion failed on Bundle::write_to_directory

[mellowagain]

With some (not all!) git receive-pack payloads and their PACK files, Bundle::write_to_directory will fail an assert and panic with:

thread 'actix-rt:worker:0' panicked at 'assertion failed: `(left == right)`
  left: `4`,
 right: `3`: This should not happen unless we added more nodes than were declared in the constructor'

Sending the payload normally just into git receive-pack does not cause an error and Git correctly handles it and applies the changes.

Backtrace:

stack backtrace:
  0..17: <Rust standard library panic calls>
  18:     0x7ff6383c1a9c - git_pack::cache::delta::Tree<git_pack::index::write::TreeEntry>::iter_root_chunks<git_pack::index::write::TreeEntry>
                               at C:\Users\Mari\.cargo\git\checkouts\gitoxide-c24b7a97d5eace1a\c0fc4f6\git-pack\src\cache\delta\iter.rs:8
  19:     0x7ff6383c2152 - git_pack::cache::delta::Tree<git_pack::index::write::TreeEntry>::traverse<git_pack::index::write::TreeEntry,git_pack::bundle::write::new_pack_file_resolver::closure$1,prodash::progress::utils::Discard,git_pack::index::write::impl$1::write_data_iter_to_str
                               at C:\Users\Mari\.cargo\git\checkouts\gitoxide-c24b7a97d5eace1a\c0fc4f6\git-pack\src\cache\delta\traverse\mod.rs:101
  20:     0x7ff63860c071 - git_pack::index::File::write_data_iter_to_stream<git_pack::bundle::write::impl$0::inner_write::closure$0,git_pack::bundle::write::new_pack_file_resolver::closure$1,alloc::boxed::Box<dyn$<core::iter::traits::iterator::Iterator,assoc$<Item,enum$<core::resul
                               at C:\Users\Mari\.cargo\git\checkouts\gitoxide-c24b7a97d5eace1a\c0fc4f6\git-pack\src\index\write\mod.rs:168
  21:     0x7ff63850c608 - git_pack::Bundle::inner_write<ref$<ref$<tempfile::dir::TempDir> >,prodash::progress::utils::Discard,alloc::boxed::Box<dyn$<core::iter::traits::iterator::Iterator,assoc$<Item,enum$<core::result::Result<git_pack::data::input::Entry,enum$<git_pack::data::inp
                               at C:\Users\Mari\.cargo\git\checkouts\gitoxide-c24b7a97d5eace1a\c0fc4f6\git-pack\src\bundle\write\mod.rs:233
  22:     0x7ff63850dad7 - git_pack::Bundle::write_to_directory<std::io::buffered::bufreader::BufReader<slice$<u8> >,ref$<ref$<tempfile::dir::TempDir> >,prodash::progress::utils::Discard>
                               at C:\Users\Mari\.cargo\git\checkouts\gitoxide-c24b7a97d5eace1a\c0fc4f6\git-pack\src\bundle\write\mod.rs:110
  23:     0x7ff6384a24cc - gitarena::git::pack::write_to_fs::generator$0::generator$0::generator$0<ref_mut$<sqlx_core::transaction::Transaction<sqlx_core::postgres::database::Postgres> > >
                               at C:\Users\Mari\Programming\gitarena\src\git\pack.rs:45

Example payload that does cause the assertion failure

[Byron]

Thank you, and sorry for the hassle!

Especially with this reproducible payload it should be an easy fix, and a very interesting one as I am curious how 'the impossible is actually possible'.

[Byron]

I looked into it and recovered a thin pack (dee964511215f6bfcf8b6d6536b63d423c26d80a.pack) from the payload provided here.

As thin packs can't be resolved without a repository, that's where I have to ask if it's possible to get the repository that contains the ref-delta objects as well to be able to run the pack file writer. The first missing object is 16f05440b93d89bac5ecde61a072b3d87a3ab90f.

It sounds like the error is always reproducible, is that truly the case? I'd like to rule out there is a race condition, which would also mean the error sometimes occurs.

dee964511215f6bfcf8b6d6536b63d423c26d80a.pack.zip.

[Byron]

Here is additional data I could gather from the pack above:

• it has 2 root objects
• it has only 1 base-delta object

It was expected to have 3 roots accounted for and 4 roots actually present (the cause of the assertion firing), so the numbers don't seem to be consistent.

What I am most puzzled about is how it's possible for this at all as the root count is adjusted each time one is added. In conjunction with the assertion message this should mean the underlying VecDeque can change the midpoint and alter the size of the front/back slices if it grows which, to my mind, it shouldn't do despite shuffling things around as it grows.

If this is true, then the client seems to send a pack with an incorrect object count, which even if that happens, should not result in an assertion error.

Putting this to the test, if the initial capacity is 0, all tests fail with a similar assertion failure, and I wonder how the VecDeque actually works. Is it possible for there to be 'too many roots' so adding children will cause a shift in its front and back buffers?

And I think I have found the culprit:

https://github.com/Byron/gitoxide/blob/5e0edbadb39673d4de640f112fa306349fb11814/git-pack/src/data/input/lookup_ref_delta_objects.rs#L93-L95

This iterator implementation is resolving ref-delta objects (those that are unique to thin packs) and places the respective base into the stream of entries. That way the actual amount of objects encountered will change, triggering the assertion as growing the VecDeque appears to change front and back buffers, something I absolutely wasn't aware of.

For now this means that as a quick fix, we can assume the worst case and heavily over-allocate if thin-packs are possible.

[Byron]

@taralx, I wonder if it's also possible for a pack to exist that has too many child nodes, such that the front and back buffers are misaligned even without growing, thus triggering this assertion?

If so, can you think of an alternative implementation that doesn't have this constraint?

[Byron]

Here is a playground link that exhibits the vecdeque behavior I think we are exposed to here.

If we are lucky, this is now fixed for good thanks to more generous overallocation done in 20b3994 , but it would be great to find a way to make such issues impossible.

[taralx]

Oh yeah, we cheated and got caught. The right answer is to do it ourselves, sadly. I wonder how much it would cost us to track the expected split point and do a "fixup" if the resulting slices are wrong?

[Byron]

The question might also be if the issue can even happen again - thus far I was unable to reproduce it if the initial capacity was chosen correctly to avoid reallocation, which is what's implemented now.

[Byron]

@mellowagain git-pack was released with the fix, which included re-releases of git-repository. As these are minor version bumps you should be able to upgrade to them explicitly.

Please let me know if the issue is seemingly fixed with the update.

[mellowagain]

Thank you very much for the quick fix, it seems to indeed work. I wasn't able to reproduce the assertion error again based on the quick testing I did with this payload as well as a few others.