Pinned version of QCellOwner

[geeklint]

This adds another owner type for QCell, QCellOwnerPinned. Since we changed QCell to use memory addresses, we can get a fixed memory address from a pinned reference just as reliably as a from the memory allocator.

Pros:

• No global state.
• Fully no_std, usable without alloc.
• Performance. I hypothesize QCellOwnerPinned::new is significantly faster even than QCellOwner::fast_new.

Cons:

• While I believe this API is fully safe, Pin has historically not been something people new to Rust understand well. The existence of this API may encourage them to use unsafe to interact with Pin, and they might not uphold the contract. A user doing something unsound with unsafe is not the responsibility of qcell, but it would be understandable if you want to avoid that nontheless.
• This likely locks the internals into the implementation based on memory addresses. Going back to the original QCellOwnerID implementation likely wouldn't be possible without removing this (and triggering a SemVer breaking change).

I'm creating this as a draft PR without comprehensive tests to gather feedback. If it seems like a good idea, I can work on implementing tests for it.

[uazu]

The thing is that it doesn't have to be pinned to be sound. If someone has a QCellOwnerPinned and moves it somewhere else, all the old QCells which were created with it before that point are no longer accessible, and if the coder attempts to access them, they'll get a panic. If some other QCellOwnerPinned gets that address, the code that created it can now access all those cells (if it has a reference), but still only one owner can access the cells at any one time. So soundness doesn't require pinning.

(I was trying to think whether two threads could both think they have the same memory allocated to them, due to the freed memory being allocated to the other thread before the freeing code has fully finished executing, i.e. the free getting reordered before code still using that address. I think that should be impossible. I can't find anything about "free happens-before malloc" for the same address on the 'net, though.)

So the only thing the pinning is doing is trying to help the user not make a mistake by moving the owner. However moving the owner after creating cells is the kind of mistake you'll make only once, because you'll immediately get a panic and fix your bug. It's the same kind of bug as having two owners and using the wrong one -- you'll get a panic and then you'll fix your bug.

So the question is whether the complexity of pinning is worth it in this case. Every time I've hit something that needed pinning it's been a headache. Whilst at a byte level of course I understand the logic, at the language level it is just hugely messy and unintuitive.

My original idea was to have a type like yours, but not stop it being moved. Then I'd leave it up to the coder whether they wanted to pin it or not. I could imagine it being created and then moved into a larger struct which would then be boxed, and then afterwards it would be used from there where it would have a fixed address, in which case without pinning it needs no special handling at all.

To give better panics, I was imagining keeping the ID used for creating the first cell as a usize in the owner, which is then never used unless there is a panic, in which case it is examined to see whether the owner's present address is different to the one the first cell was created from, in which case the panic can mention that the owner was moved, which should be enough for the coder to identify their bug.

I wouldn't want to force pinning on the coder. I think having a good long explanation on this type in the docs and allowing it to be moved would be enough for the coder to take proper precautions, and pin it themselves if they really want to. Or do you think that is not strict enough?

Unlike in other uses of Pin, in this case it makes no different to soundness. Since it makes no difference to soundness, it's just a question of how best to help the coder not make a mistake -- force them into doing Pin handling, or give them enough info to make sure they use the type correctly.

What do you think?

[geeklint]

That's a good point, I'll have to think on it on it some more, but some initial reactions:

It's pretty easy to accidentally move things. I'm imagining a situation where someone accidentally passes the owner type as a function argument. The compiler may optimize out that move, in which case the code would work - until the compiler details change. That is, you could have a program that successfully compiles and runs one day, but panics when run under even slightly different compiler settings. Not a soundness issue, but not something I like the idea of.

Another perhaps just humorous semantic thing, if you use std::mem::swap on the owners, you wouldn't actually swap them.

[uazu]

I can see what you're saying. The difference should be noticeable between debug and release builds though. Also if they move the owner into a function by mistake, then the owner will no longer be available in the caller and the owner would be dropped in the called function. So that bug should be detected very early in development. Yes, swapping would do nothing! Mentioning that in the docs would maybe help the coder understand how things work.

The coder needs to understand that it's their job to make sure that an instance of this type has a stable address for the time they're using it, either through pinning or boxing or whatever.

Maybe it's not necessary to store the ID in a usize to give the improved panic. Maybe just saying "You're using the wrong owner, or you've moved the owner since creating the cell" is enough for the coder to debug it.

It's interesting really. In Java for example the runtime is free to move objects around and change the pointers behind your references, because those are not visible to the coder. In Rust, I was wondering whether any optimisation might move things around when we might not expect it, or optimise away boxing for example. Since it is easy to get an address in safe code, this is very visible to the coder. However Pin is specifically designed to not move, and Box can't be optimised away without breaking a lot of assumptions, as far as I can see -- and the docs specifically say that it is an allocation on the heap. I think Go is somewhere in between, i.e. they may optimise things, but if someone takes an address, that changes the optimisation.

[geeklint]

I asked around if, for example, it is possible for

println!("{:p}", &mut x);
println!("{:p}", &mut x); 

to print different values. The understanding seemed to be that none of Rust's guarantees prevents the compiler from doing so, even if it probably won't ever actually do it in practice. It would seem strange to me, to essentially rely on that unspecified behavior to avoid panics.

Additionally, in some circles (e.g. gamedev), it's not uncommon that people have their debug builds set to non-zero opt-levels, so it's not a guarantee that such misuse bugs would appear in debug builds.

if they move the owner into a function by mistake, then the owner will no longer be available in the caller

True, but that would only throw up flags if they used it after calling the function, which, maybe calling the function was the last thing they intended to do anyway.

I think there's too many questions about a non-pin variant for me to feel confident in it. On the other hand, because, Pin actually isn't required for safety, I think my concern about the Pin API being confusing isn't as big a deal as I initially thought. If a user unsafely messes up the Pin contract, then the worst that happens is exactly what happens if they mess up the non-pin version. It's sound even if their unsafe code is wrong.

[uazu]

I think I need to mock up a typical use of this with Pin to see how bad it would be, e.g. an owner stored as part of a larger struct in a Box or on the stack. I'll have a go later on.

[geeklint]

Do keep in mind the pin_project crate, as that will likely make the former case much cleaner.

[uazu]

Your doc example doesn't work. Some things are just obvious slips which I had no problem fixing up, but it seems to want to break out a Pin<&mut T> from a Pin<Box<T>>, but I can't see any obvious way to do that without going deep down the Pin rabbit-hole. So owner.rw( and owner.cell( both look like they're going to cause difficulty.

I think you've yet to convince me on the ergonomic side of this. Maybe if you can create a working doc example?

Really Pin seems immature as a feature in Rust. For example when it needs external crates for basic operation. If use of Pin is hidden deep in the implementation of something, then no problem. But exposing users to this doesn't seem fair. I've had to use it for FFI (with cxx crate) and for implementing an async/await executor. Both of these are very low-level, and are hidden in the local implementation and not exposed to the user of that code. So the complexity does not spread beyond the API of that small segment of code. This seems like the ideal situation to me

But right now we've got Pin issues in user code, and it looks like it's going to force my state structure to be pinned as well, and all accesses passed through project(), although I didn't get as far as trying that.

Who do we expect to want to use this type? Are they really going to be ready for so much inconvenience?

[geeklint]

You're right, I'm sorry the example was broken, I've fixed it and included it below.

break out a Pin<&mut T> from a Pin<Box>, but I can't see any obvious way to do that

Pin::as_mut does exactly this.

Pin seems immature as a feature in Rust. For example when it needs external crates for basic operation

Totally valid. I've seen elsewhere people really believe at least pin_utils::pin_mut! should be in std.

it's going to force my state structure to be pinned as well, and all accesses passed through project(),

Yes, that's how the pin_project crate works (and has to work, otherwise you could just move the state structure containing the #[pin] and break the contract). pin_project is actually just a (safe) implementation of the behavior described in the std Pin docs. I only specifically called out it out to make sure it was clear there is a unsafe-free way to implement projections.

Who do we expect to want to use this type? Are they really going to be ready for so much inconvenience?

I would probably use it, if it was there. But if it's too much API surface to add to qcell, I would understand and wouldn't miss it too much.

Fixed doc example:

use qcell::{QCell, QCellOwnerPinned};
use std::rc::Rc;
use std::pin::Pin;
let mut owner = Box::pin(QCellOwnerPinned::new());
let item = Rc::new(owner.as_ref().cell(Vec::<u8>::new()));
owner.as_mut().rw(&item).push(1);
test(owner.as_mut(), &item);

fn test(owner: Pin<&mut QCellOwnerPinned>, item: &Rc<QCell<Vec<u8>>>) {
    owner.rw(&item).push(2);
}

[uazu]

Okay, that's not looking too bad now. I was afraid it would require unsafe somewhere. So it's just an extra method call on each access. Essentially if you use pin_project crate you're adding an extra accessor method call to each struct access too. They really need to get the most important bits of these pin-supporting crates into std. Just working from std docs is too hard.

Okay, I am more convinced now. Let me think some more about the other questions, e.g. whether we want to commit 100% to using addresses and so on.

[uazu]

Sorry for the delay in getting back to this.

Thinking about Pin<Box<T>> and Pin<&mut T>, there are two aspects: guaranteeing that it doesn't change address, and guaranteeing that you can't move out of it. Unless Pin has some magic, it must be the Box or &mut that guarantees that it doesn't change address. Pin as a type only stops you moving out of it. Out of these two behaviours, it's the "not changing address" part that we care most about. So maybe passing around a &mut to a stack variable would be enough, which is what pin_mut! does to pin something on the stack. It seems like as soon as you have a &mut, it can't change address (or else pin_mut! would break).

However, maybe Pin could have some magic beyond what its code expresses, as it is a lang-item, i.e. the compiler is allowed to give it special treatment. (A quick search through the compiler source for LangItem::Pin doesn't seem to show any magic, though.) As far as I can see Box should always give a fixed address on the heap, according to the docs. However who knows what future optimisation might be done, e.g. moving boxed values to registers or stack or whatever, as is done in other languages. So maybe the Pin might be necessary to disable those optimisations if they were ever added. So based on that, I think using Pin is the correct choice, to protect our &mut or Box from optimisations.

So I think we should also use Pin<Box<...>> for QCellOwner, just to be sure we get a stable address in the face of any future changes to the language.

For QCellOwnerPinned, the boxed uses don't seem to give much advantage. For example Pin<Box<MyStruct>> where MyStruct contains a QCellOwnerPinned does save one allocation. However one allocation isn't much saving when considering that one owner will be used to create many cells. So for boxed allocations, I don't see much advantage.

However looking at storing a QCellOwnerPinned on the stack, it does do something unique. If I have MyStruct on the stack, and pin it using pin_mut! then pass around that Pin<&mut MyStruct> I think that means that it's possible to do qcell-style borrowing without alloc, e.g. in the case of some resource-constrained library that has smart pointers which allocate out of static arrays. So this could be valuable to someone, and so it is worth adding.

I think the examples should cover this stack-based use-case, since this is where it adds most value.

As to whether it's okay to commit to using addresses as the basis of IDs, as yet I can't think of any way this can go wrong. Even if some future optimisation might try to merge our allocations, we can get around it by storing some value based on the address, which would force the optimisation to be disabled. Even for chips with different address-spaces for different things, all of our allocations should go to the same address-space.

So, I think, if you have time, we can go ahead with this change.

[geeklint]

I believe I have incorporated your feedback on using Pin internally for QCellOwner and I've updated the QCellOwnerPinned documentation example to use pin-utils::pin_mut.

I've started writing some tests and will continue as I have time over the next couple days; my method is basically going to be to copy all the existing tests that cover QCell and mirror them for QCellOwnerPinned, unless you would like to provide some guidance for specific additional cases you would like to see covered.

[uazu]

This looks good, thanks. Before I do a release I will go over all the recent changes again and see whether I can see anything that could do with additional testing or documentation.

[geeklint]

I've now adapted the doctest_qcell module into a second one, doctest_qcell_noalloc, which tests most of the qcell functionality that doesn't require the alloc feature, including copies of all the original tests, but for QCellOwnerPinned. This generates new compiletest files.

Would you prefer I check-in the compiletest output so you can review it as part of this PR, or would you prefer to review it locally and check in the stderr files yourself?

Side note; when I updated the compiletest, one of the TCell and TLCell compiletests were flagged as changed (looked like a trivial whitespace difference). I didn't check that in since it wasn't relevant, but it might be something you want to double check.

[uazu]

Thanks for this. Don't worry, I'll do the compiletest stuff since I have some other changes planned. Yes, I'll double-check everything.

I've been thinking this through overnight. This is what I'm thinking of doing:

• Put all this in a new minor version 0.5.0 since it has some significant internal changes and a major new feature (no_std), even if the API is the same
• Split out fast_new as a new type QCellOwnerSeq (or QCellOwnerNoStd or QCellOwnerAtomic, not sure yet); I think the sequential-ID approach will still be convenient for some embedded-type environments
• See if I can factor out some of the shared code, maybe with a macro
• Maybe see if I can do no_std for TCell, using a small fixed-sized table as you suggested.
• Go through rewriting docs and adding comments to make things as clear as possible

Let me know if you see any problems with that approach. If you're interested in reviewing my changes, I'll put them through Github so that you can comment before merging.

Also, how do you want to be credited in the changelog? It's coming through as "Violet Leonard" in GitHub, so I'll use that and a link to your github page unless you have some other preference. Thanks

[geeklint]

* Put all this in a new minor version 0.5.0 since it has some significant internal changes and a major new feature (no_std), even if the API is the same
* Split out `fast_new` as a new type QCellOwnerSeq (or QCellOwnerNoStd or QCellOwnerAtomic, not sure yet); I think the sequential-ID approach will still be convenient for some embedded-type environments

Since this is some significant changes, even if not currently to the API, it's probably a good time to also make some breaking changes, so I think this plan is good. One thing I was thinking about when I was working on this was that most of the examples use QCell::new, which only works with the original QCellOwner. If there's going to be 3 variants of QCellOwner now, maybe it's a good idea to make QCell::new generic and work with any of them.

* See if I can factor out some of the shared code, maybe with a macro
* Maybe see if I can do no_std for TCell, using a small fixed-sized table as you suggested.
* Go through rewriting docs and adding comments to make things as clear as possible

Let me know if you see any problems with that approach. If you're interested in reviewing my changes, I'll put them through Github so that you can comment before merging.

This all sounds good to me. If you would appreciate the extra set of eyes I'm happy to look over something.

Also, how do you want to be credited in the changelog? It's coming through as "Violet Leonard" in GitHub, so I'll use that and a link to your github page unless you have some other preference. Thanks

I don't have another preference; thank you for the attribution.