Don’t rely on Vec’s addresses being stable

[SabrinaJewson]

Currently this crate relies on references given out by Vec being stable, i.e. not invalidated by a &mut Vec<T>. However, this is not guaranteed to be the case and will in fact change if this rust-lang/rust PR is merged. Instead, this crate should use AliasableVec or its own pointer type so that it won’t be broken by this.

[koehlma]

Thank you very much for letting me know. 👍

I was under the impression that Vec guaranteed stable references. In particular, the statement

push and insert will never (re)allocate if the reported capacity is sufficient.

of the Guarantees section with the previous description of the memory layout makes it seem as if references are guaranteed to be stable when pushing onto a Vec whose length is less than its capacity. At least, this has been my reasoning at the time of implementing this crate. There is also another statement about converting the Vec into a Box without reallocating and “moving” the elements. I guess, the documentation could be more clear about that. I am not quite sure how to interpret these guarantees in case a &mut Vec<T> suffices to mess with the memory allocation. 🤔

Anyway, thanks again, I will address this issue as soon as possible it is clear how the implementation of Vec will be changed and whether these changes actually pose a problem for this crate. 👌

[conradludgate]

I don't think my PR raises any instability issues (we test for that https://github.com/rust-lang/rust/blob/master/library/alloc/tests/vec.rs#L1753-L1840), but I think the main point in question is the aliasing of said pointers.

Box and RawVec feature different aliasing rules and at the moment the people smarter than I are trying to figure out what those rules should be exactly.

I think the current intention is to make Box not be noalias to make it more like Vec currently, but I'm not 100% on that

[koehlma]

@conradludgate Thanks for your comment. Is it correct then that rust-lang/rust#94421 will not cause any problems for this crate, i.e., the example provided in rust-lang/rust#94421 (comment) is in fact not UB with just the PR rust-lang/rust#94421 but it would become UB with when rust-lang/rust#54470 gets addressed in a certain way?

[SabrinaJewson]

If the PR was merged as-is, it would mean that LLVM would have the potential to miscompile this crate, because this crate would result in LLVM UB. Rust now has to decide whether to make your crate UB — if not, the PR (and rustc) must somehow be changed to avoid miscompilations.

push and insert will never (re)allocate if the reported capacity is sufficient.

of the Guarantees section with the previous description of the memory layout makes it seem as if references are guaranteed to be stable when pushing onto a Vec whose length is less than its capacity.

There is a very subtle distinction there: Vec guarantees that the location of the values in-memory stay in the same place, but that does not equate to pointers to it not becoming invalidated. For example, this will absolutely never be UB:

let mut v = Vec::with_capacity(2);
v.push(0);
let address: *const i32 = &v[0];
v.push(0);
if !ptr::eq(address, &v[0]) {
    unsafe { unreachable_unchecked() };
}

But this might become UB:

let mut v = Vec::with_capacity(2);
v.push(0);
let mut address: *const i32 = &v[0];
v.push(0);
assert!(ptr::eq(address, &v[0]));
// Uncomment the below line to remove all the UB:
// address = &v[0];
dbg!(unsafe { &*address });

[koehlma]

@SabrinaJewson Thanks for the clarification. I see that those two examples are different, however, according to the link to the test case provided by @conradludgate they seem to test for the latter case:

https://github.com/rust-lang/rust/blob/master/library/alloc/tests/vec.rs#L1768-L1780

let mut v = Vec::with_capacity(128);
v.push(13);

// Laundering the lifetime -- we take care that `v` does not reallocate, so that's okay.
let v0 = &mut v[0];
let v0 = unsafe { &mut *(v0 as *mut _) };
// Now do a bunch of things and occasionally use `v0` again to assert it is still valid.

// Pushing/inserting and popping/removing
v.push(1);
v.push(2);
v.insert(1, 1);
assert_eq!(*v0, 13);

It seems to me that these lines of the the test case explicitly test that the reference v0 stays valid and does not cause UB after pushing onto the Vec or doing other operations to it. Is there any significant difference between this test case and your second example? I am sorry, but I am a bit confused right now.

[SabrinaJewson]

There isn’t actually, I didn’t know of that test case before. A test case doesn’t constitute a public API guarantee, but I suppose it indicates some level of commitment at a lower level of the Tower of Weakenings. Personally I would still like to see a strongly unaliased Vec and Box as long as we can opt-out (AliasableVec<T> / Vec<Aliasable<T>> / Vec<Aliasable<UnsafeCell<T>>>) but I’m not aware of how much ecosystem code relies on Vec’s weaker guarantees.

[koehlma]

I see. I do not say that there is a guarantee but I am not sure that there is no guarantee either.

I would like to wait until the remaining questions regarding aliasing guarantees of Vec are settled before addressing this issue. At the moment, everything seems to be fine although this may be due to implementation details. There also seem to be some other more popular crates relying on the above example not being UB (see rust-lang/rust#96607 (comment)). I do not have any preference for either solution but I think the documentation should be clarified. Evidently, I am not the only one who assumed that there is some guarantee (also MIRI does not seem to complain).

I would prefer using some kind of a AliasableVec<T> for this crate instead of doing raw pointer wizardry. In particular, Vec already deals with ZSTs and all that. The less manual fiddling with pointers, the better, IMHO.

[koehlma]

I did add a test for checking for stable references and a CI job for running Miri.