Iteratively dropping an Arc tree

help
1

I have a tree roughly of the shape

enum Element {
    Node(ManuallyDrop<Arc<Node>>),
    Leaf(ManuallyDrop<Arc<Leaf>>),
}

struct Leaf {
    // ...
}

struct Node {
    // ...
    children: [Element],
}

(Yes, you read that right: I have the element array inline, using slice-dst. Element is also a union rather than a enum in the real code because of cursed shenanigans.)

I would like to drop this tree iteratively rather than recursively. (I'm hitting miri's recursion limit and would like to not.)

The tree root is just Arc<Node>; this is important because the user is allowed to hold an Arc<Node> to a node anywhere in the tree.

Is it possible to drop this tree iteratively in current Rust? As far as I can tell, even after guaranteeing that the Arc is unique, there is no way to drop the Arc (thus doing de-allocation) without also dropping the Node inside the Arc. (An iterative drop would drop it without recursing into the child's drop impl.)

This is because it is always UB to transmute between #[repr(Rust)] types, even if they're parameterized by transmute-compatible or even transparent-equivalent types. I could and would be able to iteratively drop this tree if I could transmute Arc<Node> => Arc<ManuallyDrop<Node>>.

Am I correct in thinking that this just isn't possible until a language or library guarantee that the above transmute is sound?

2

Unfortunately, I've just realized a big problem here: synchronization. Even with the language allowing me to transmute Arc<T> to Arc<ManuallyDrop<T>>, the manual dropping of the inner value needs to synchronize the same way that Drop for Arc does. Without being able to dig into the internals to fence on them, I don't think that it's possible to actually guarantee that exactly one dropper sees that their Arc is unique and drops the internal value. The best you could do without getting into the synchronization yourself is possibly doing an iterative drop (probably if only dropping on one thread), but potentially recursing if no drops see that they're unique before Arc's drop synchronization.

3

Could you potentially just always store Arc<ManualDrop<Node>>?

If it weren't a DST, I'd suggest using Arc::try_unwrap, but that seems to be a no-go.

Dealing with synchronization does seem hard.

How about a "best effort" iterative drop, though? Like, inside drop you could use Arc::get_mut - if it succeeds, you take all the children out of it, and proceed with iterative drop. If it fails, you just drop it like normal. There would be an edge case where two threads both fail, and it gets dropped recursively - but probability would be on your side, since recursive drop won't actually fail unless you hit the edge case hundreds of times in a row.

For the actual iterative drop, then, you could do the standard thing of pulling each child element out, then dropping the Arc only once its internal node has no children.

4

The problem comes from then it getting dropped normally, which would drop all of the children again.

I suppose that's solvable with a C++-style move (replace with a null object), as icky as that feels in a language with true destructive moves offered.

5

I was hoping we could solve this by mutating the node and taking its children out first. If you could do that, you could write something like:


impl Drop for Node {
    fn drop(&mut self) {
        let mut elements = Vec::new();
        // move all child Elements from self.elements into elements
        self.drain_into(elements);
        loop {
            let elem = elements.pop();
            if let Element::Node(n) = elem {
                if let Some(n) = Arc::as_mut(n) {
                    n.drain_into(elements);
                }
            }
        }
    }
}

and I think that would correctly drop things iteratively.

But I don't know enough about DSTs or your structure to know if implementing a drain function would be possible. What if we replaced [Elements] with something like [MaybeUnint<Element>] and added a flag for "elements have already been dropped/moved out"?

6

Huh, I didn't realize, but this (not the transmute, but written as from_raw(into_raw)) was actually documented as sound in #68099 in February. That PR marked the heap allocated types as #[repr(C)] and specified the type requirements of from_raw as

The raw pointer must have been previously returned by a call to Arc<U>::into_raw where U must have the same size and alignment as T . This is trivially true if U is T . Note that if U is not T but has the same size and alignment, this is basically like transmuting references of different types. See mem::transmute for more information on what restrictions apply in this case.

Yeah, I had that as an implementation for a bit. You can't change the length of [_], so you need to do some sort of flagging; in my case the elements included a ptr::NonNull so I just wrapped the pointer in an Option and added a null state to put them into. Basically a C++-style move, as icky as that feels to me in Rust.

Thankfully, even though the actual transmute isn't possible, I can get the same effect via from_raw(into_raw(_).cast()), which is now documented as sound as of Rust 1.44 (current beta).

3 Likes
7

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.