[Question] (BoC) unintentional move in Vec<Request> cause dangling pointer.

[Foreverhighness]

First of all, thanks to all CS431 course instructors for providing such good learning materials about Concurrent Programming.

Pitfall

When I implement BoC runtime, I wrote this code snip.

// requests: Vec<Request> is consumed
for req in behaviour.requests { unsafe { // buggy
    // req is Request, moved from heap onto stack
    req.release();
}}

It turns out that this simple code contains a nasty bug.

Initial State:
┌────────────────────────────────────────────────┐
│Heap                                            │
│ ┌────────────────┐                             │
│ │   Behaviour    │ ┌─────────┐  last  ┌──────┐ │
│ │ ┌────────────┐ │ │         │◄───────┤      │ │
│ │ │    Vec     ├─┼►│ Request │        │ Cown │ │
│ │ │            │ │ │         ├───────►│      │ │
│ │ └────────────┘ │ └─────────┘ target └──────┘ │
│ └────────────────┘                             │
└────────────────────────────────────────────────┘
After:
┌────────────────────────────────────────────────┐
│Heap                                            │
│ ┌────────────────┐        (Oops dangling!)     │
│ │   Behaviour    │ ...........  last  ┌──────┐ │
│ │ ┌────────────┐ │ .         .◄───────┤      │ │
│ │ │    Vec     │ │ . Request .        │ Cown │ │
│ │ │ (Consumed) │ │ .         .┌──────►│      │ │
│ │ └────────────┘ │ ...........│target └──────┘ │
│ └────────────────┘       │    │                │
└──────────────────────────┼────┼────────────────┘
┌──────────────────────────┼────┼────────────────┐
│Stack       move to stack ▼    │                │
│                    ┌─────────┐│                │
│                    │         ├┘                │
│                    │ Request │                 │
│                    │         │                 │
│                    └─────────┘                 │
└────────────────────────────────────────────────┘

The correct way to iterate through requests is:

// requests: Vec<Request>
for req in &behaviour.requests { unsafe { // correct
    // req is &Request, still reference to the instance on heap
    req.release();
}}

Solution

Regarding that, I think request should be marked as immovable.
One solution to this issue would be to modify Vec<Request> to Pin<Box<[Request]>>, which would prevent the unintentional move.

// requests: Pin<Box<[Request]>>
for req in behaviour.requests { unsafe { // complier error: `Pin<Box<[Request]>>` is not an iterator
    req.release();
}}
// requests: Pin<Box<[Request]>>
for req in behaviour.requests.into_iter() { unsafe { // ok: req is &Request
    req.release();
}}

Drawback

Now, if we want to iterate through requests, we need to call iter() or dereference it first.

for req in behaviour.requests             // complier error: `Pin<Box<[Request]>>` is not an iterator
for req in &behaviour.requests            // complier error: `&Pin<Box<[Request]>>` is not an iterator
for req in &*behaviour.requests           // ok
for req in behaviour.requests.iter()      // ok
for req in behaviour.requests.into_iter() // ok

Unresolved questions

There is still a way to invalidate the last pointer.

let mut behaviour;
behaviour.requests.swap(0, 1); // 1
core::mem::swap(&mut b1.requests[0], &mut b2.requests[0]); // 2

Fortunately, these two examples could both be considered logical errors.

1. It breaks requests must be sorted assumption.
2. Behavior should only access its own requests.

And these errors are easy to avoid, just: Don't let behaviour mutable.
In fact, I think it's a logical error to declare a mutable behavior variable.

The optimal solution to this problem may be to utilize either Vec<Pin<Box<Request>>>> or Vec<Arc<Request>>, I haven't tested it yet.
But both approaches incur some overhead costs, so I think Pin<Box<[Request]>> is sufficient.

[Lee-Janggun]

Hmm... I think you are correct. IIRC efficiently implementing boc while making sure move between heap/stack was ok was really annoying, and we had many problems similar to the one you have now.

I'm busy right now, so won't be able to look at it for a couple of weeks. But I will make sure to fix it.

[Foreverhighness]

@Lee-Janggun

I think there are only two pointers that may be dangling:

1. CownBase.last(): AtomicPtr<Request>
2. Request.next: AtomicPtr<Behavior>

For (1) this can be solved by changing Vec<Request> to Pin<Box<[Request], which is exactly what I did in my PR.

For (2) this can be solved by moving behavior onto the heap via Box::new(behavior) or Box::pin(behavior).

In fact, I suggest changing the Behavior api design to this:

fn new<C, F>(cowns: C, f: F) -> Pin<Box<Behavior>>.
fn schedule(self: Pin<Box<Self>>) -> ManuallyDrop<Pin<Box<Self>>>;

However, this change may greatly reduce the difficulty of the BoC homework.

Interestingly, it's safe to move behavior onto the stack in resolve_one() because there is no longer a next pointer to this behavior. (I set next to null in the last line of release())

unsafe fn resolve_one(this: *const Self) {
    /* ... */
    let behavior: Box<Behavior> = unsafe { Box::from_raw(this) };
    let behavior = *behavior; // It is safe but useless
    rayon::spawn(move || { /* ... */ });
}