make `ItemSliceSync` safe

[martinvonz]

Current behavior 😯

ItemSliceSync::get_mut() takes an non-mutable reference and an index. It doesn't check if there are multiple callers accessing the same index, so that's left to the caller to do (the function is therefore marked unsafe). I can't tell if the callers are actually guaranteed not to access the same index concurrently. My guess - without looking very carefully - is that the requirement can be violated by a bad packfile.

Expected behavior 🤔

Maybe ItemSliceSync should be replaced by a list of RefCell to make it safe?

[Byron]

Thanks for bringing this up!

I also would love to get rid of all unsafe. In this case, it's used to allow access to a size-optimized vec of items that form a tree, and we need to access it concurrently with each thread taking its own root node, and working its way through all the reachable leaves. The tree was built by decoding a pack whose entries refer to its bases only by OFS_DELTA - they are pointing backwards only which assures a correct tree. REF_DELTA entries aren't supported here, and cause immediate failure - they are expected to have been resolved before as part of the thin-pack handling. This is also the reason for this unsurmountable issue.

If we somehow would allow REF_DELTA entries to point to an in-pack object, then in theory malicious packs could cause all kinds of graphs as they can point anywhere in the pack, but they still can't link an entry to more than one base. And that's what one would really have to do for two threads to encounter the same child.

Thus I believe it's impossible for this data structure to end up in a place where it violates its assumption. Maybe that's wrong somehow, but I don't see it yet.

Maybe ItemSliceSync should be replaced by a list of RefCell to make it safe?

Even if the performance-drop when doing that would be negligible I'd think that the increase in memory consumption will not be that. Last time I eyeballed the memory consumption gitoxide came in with ~20% less than Git when dealing with the linux kernel pack, and that was hard-earned already.

Would you consider closing the issue until there is more evidence something needs to be done?

[martinvonz]

The tree was built by decoding a pack whose entries refer to its bases only by OFS_DELTA - they are pointing backwards only which assures a correct tree.

Ah, I see. I agree that it should be safe then.

Would you consider closing the issue until there is more evidence something needs to be done?

I'll defer that to @Manishearth who did the unsafe review of gix-pack this time. Manish, do you think a comment explaining why it's safe would be sufficient?

[Manishearth]

Would you consider closing the issue until there is more evidence something needs to be done?

As an unsafe reviewer the standard I tend to apply is that it should be very easy to verify that the invariant us upheld (not just a comment claiming it is). So I think what I would need is:

• A comment and sufficent access control on the fields that have these invariants
• (Ideally) methods that impact these fields are marked unsafe
• Code which modifies these fields should justify that the invariants are upheld. This is easier if the methods that modify/construct the fields are all marked unsafe.

Unless the comment is sufficiently self-evident and does not require jumping around a lot of code to verify. Even then I'd like the code it references to also have comments to that effect.

[Byron]

Thanks for chiming in - I like your standard as it's easy to follow and thus hopefully just as easy to apply.

Trying just that, I created #1233.

• A comment and sufficent access control on the fields that have these invariants

Access control was improved by restricting it more.

• (Ideally) methods that impact these fields are marked unsafe
• Code which modifies these fields should justify that the invariants are upheld. This is easier if the methods that modify/construct the fields are all marked unsafe.

I didn't propagate-up the unsafe just yet, but reviewed and improved the safety comments. The reason it's safe lies in the way the data structure is built and traversed, and that I tried to make clearer.

It's interesting that the ItemSliceMut (and related types in gix-features) are only needed after a change in rustc which prevented the usage of raw pointers - previously this type would just have been a pointer access. I think this was done to enforce the declaration of Send and Sync accordingly, but it's just a guess. I don't know of this information could help to improve the documentation further, or the way it is used.

[Manishearth]

@Byron I think that's a start but still not easily reviewed.

I'm also not convinced on that Send and Sync bound, the safety comments on the Send and Sync bounds are definitely not correct at the very least.

[Byron]

I think the main culprit is that ItemSliceMut is really a way to access T: Send items mutably from multiple threads, and there are no guardrails at all. There was a time when this was *const T and that was transmuted into *mut T as needed. That, however, stopped working probably because of the Send + Sync bounds, and ItemSliceSync was born.

By itself there is no way this can be considered safe, as it is only 'not unsafe' if its used correctly, and that usage is described in detail, but the code for that is in a couple of places and certainly not too easy to follow.

With that said, I don't know what else to do about this.

[Manishearth]

Yeah the main thing to be careful about is that &T is Send only if T is both Sync and Send, which is not reflected in those bounds.

a RefCell is Send, but not Sync, so an &RefCell is not Send

[Byron]

I wish this could be reflected somehow, after all the T that's actually stored is Send + Sync, and it was never the intention to allow T that are &Type or Type<'_>. Maybe T can be constrained to not be a reference somehow?