Hashbrown help: concurrent iteration and modification

help
1

Yes, what I'm doing is evil and dangerous. I'm also open to alternative ways to accomplish my goal that manage to avoid doing borderline abusive things to hashmaps.

Here's my current progress: https://github.com/CAD97/sorbus/pull/53

I have an immutable Arc-managed tree. It's shape is roughly the following (but mangled by confounding implementation details):

pub struct Node {
    data: NodeData,
    children: Box<[Element]>,
}

pub struct Token {
    data: TokenData,
}

pub enum Element {
    Node(Arc<Node>),
    Token(Arc<Token>),
}

Construction of a tree is always proxied through a builder cache, such that equivalent nodes can be deduplicated and shared. The cached nodes (and leaf tokens) are stored in (the equivalent of) a hashbrown::HashSet in the builder cache.

My current goal is to allow garbage collection of any tree elements that are only being kept live by the cache. The simple version is map.retain(|node| Arc::strong_count(node) > 1). This works to collect some elements, but not all that are possible to collect.

The reason is that the nodes still own their children. Because hashmap iteration order is (effectively) random, we can visit child nodes that are owned by parents in the cache before the parent, which will later be collected as it has no more references keeping it alive.

There's possible ways of handling this that I see. The first, which I'm currently using, is just to keep doing this until no more nodes are deleted. This works, and is simple. However, it is (probabilistic) O(n log n) (probably): one pass through the cache requires checking n nodes, and will probably collect one and half "layers" from the tree. The tree is probably log n layers deep, giving log n passes over n elements for a complexity of O(n log n).

However, it's theoretically possible to do this in a single linear O(n) pass, using a mechanism similar to a tracing garbage collector. When we find a root node that we can collect, also (transitively) try to collect its children. However, this runs into the titular problem: mutating the hashset while iterating over it.

I honestly can't tell what kind of concurrent modification hashbrown's RawTable iterator allows while holding onto the iterator. It certainly allows deletion of the element you're currently on, as this is used to implement retain. Deletion of elements yet to be iterated, however, definitely is a logic error at least, as RawIter keeps track of how many items it has yet to iterate and checks that it iterated all of them when exhausting.

... and there, while writing this, I got a Miri run with a seed that showed use-after-free UB. I thought it might just be pure UB to delete elements "in front" of the iterator head, because of the group reading of control bytes that hashbrown does.

Based on my reading of the implementation, it should be sound to erase buckets "behind" the iterator head, and only doing so will still retain O(n) cache garbage collection. But I don't see hashbrown currently providing any guarantees to what kind of modification of the RawTable is allowed while holding a RawIter.

2

Have you considered just collecting all of the unreachable root nodes without modifying while iterating, and then removing them, and then trying to remove all of their children, and so on. This way you would not modify the hash set until after iterating.

1 Like
3

Can you store Weak<Node>s instead of Arc<Node>s in the cache? That’ll allow Drop to happen immediately when the client is done with all copies of an item, and your garbage collector just needs to remove the dead pointers.

Hash tables don’t generally like their keys changing identity while stored, though; maintaining that invariant for Weak keys might make this an intractable approach.

2 Likes
4

Weak doesn't implement Hash or Eq. So you can't put it in a HashSet directly. But I suppose you could pre-Hash these items and only store a Weak inside the set

struct PreHashed {
    hash: u64,
    node: Weak<Node>
}

Then this one only hashes based on hash

1 Like
5

That... actually might work fairly well, especially since the number of root nodes is going to be quite small. I think it might have the same asymptotic complexity and space usage, as well.

(Given n, the number of elements in the cache; m < n, the number of collectable elements; d, the depth of collectable elements; I think O(n) time to scan for free roots, O(m) time to collect the tree, O(d) space to collect the tree; for both approaches.)

This is definitely desirable, and I've considered how to do it a couple times. The problem is dealing with key invalidation and hash collisions in a principled manner.

I've floated one extremely cursèd approach where I abuse the fact that Weak<T> keeps the full T live, to access the "stack part" of Node even after it's been dropped, because the "stack part" is enough to calculate the (shallow) hash/eq. (In the real project, it's closer to Node(Data, [Element]), so dropping doesn't deallocate the children list.)

This is too cursèd even for me, though; it's perfectly valid for Weak::as_ptr to return an dangling/null invalid pointer when the strong count is zero, and I really don't know whether you're allowed to read post-drop pre-dealloc at all.

This could all be solved with a custom variant of Arc that guarantees being able to access the "zombie" from Weak pointers, but a large part of the reason I've laid out the tree like I have is to use standard containers.

Double the (node) cache size (and slightly slow down node creation) to get eager cleanup of the tree. The Eq identity would still change when the node is dropped, but the hash table is (required to be) resilient to that.

...Except, we don't even get the eager cleanup of the tree memory. We get eager dropping of the nodes and their payloads, but a) the payload is Copy anyway, and b) holding Weak<T> in the cache prevents deallocation of the arc payload. So all we're really getting is extra overhead in the cache without any benefit.

(This may be one spot where my inline node data and child array bites me. If they were separate allocations, then the children array would be freed by a drop even before the arc heap part is deallocated. Decreasing the number of allocations did show improvements when we did that, however.)

(And on top of all this, we're probably going to want to implement a smarter cache eviction strategy eventually; all this is just getting a baseline for best effort before trying to pick an effective cache eviction policy.)

1 Like
6

An approach (no idea how reasonable, also untested) that I came up with:

  • Make the cache an Arc<Mutex<HashSet<Node>>. (Are you also caching the tokens? The same could be done for those.)

  • Then place a Weak<Mutex<HashSet<Node>> as a field into each Element::Node, let’s say the fields are called node and cache. Edit: I also need the Arc<Node> inside a ManuallyDrop.

  • Implement Drop for Element, doing:

// self: &mut Element
if let Element::Node{node, cache} = self {
    // node: &mut ManuallyDrop<Arc<Node>>
    // cache: &mut Weak<Mutex<HashSet<Node>>
    let node_weak = node.downgrade();
    unsafe { ManuallyDrop::drop(node) };
    // ^^^ we won’t access node after this
    if node_weak.strong_count() == 1 {
        if let Some(cache) = cache.upgrade() {
            if let Some(node) = node_weak.upgrade()
                cache.lock().remove(&node);
            }
        }
    }
}

Edit: Just noticed I can’t drop node like this. This probably needs ManuallyDrop or something. Done.
Edit2: This idea assumes that an Arc<Node> is not really accessible publicly, so that all of the Arc<Node>, except for the one in the cache, reside inside Elements while being dropped. Not sure if this is what you had in mind. Alternatively one could build a new smart-pointer wrapper with the right impl for Drop around the ManuallyDrop<Arc<Node>> that offers Clone and Deref etc.. like an Arc. Then only expose this wrapper.

7

Things would be much easier if that were true :sweat_smile:

Thanks for the suggestions everyone; as it usually turns out, I ended up going with the just don't do the questionable stuff approach suggested by @alice.

8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.