| guard.rs |
|
836 |
- |
| guard_ref.rs |
|
969 |
- |
| tree_node.rs |
This mod provides the logic for the inner tree structure of the `CancellationToken`.
`CancellationTokens` are only light handles with references to [`TreeNode`].
All the logic is actually implemented in the [`TreeNode`].
A [`TreeNode`] is part of the cancellation tree and may have one parent and an arbitrary number of
children.
A [`TreeNode`] can receive the request to perform a cancellation through a `CancellationToken`.
This cancellation request will cancel the node and all of its descendants.
As soon as a node cannot get cancelled any more (because it was already cancelled or it has no
more `CancellationTokens` pointing to it any more), it gets removed from the tree, to keep the
tree as small as possible.
# Invariants
Those invariants shall be true at any time.
1. A node that has no parents and no handles can no longer be cancelled.
This is important during both cancellation and refcounting.
2. If node B *is* or *was* a child of node A, then node B was created *after* node A.
This is important for deadlock safety, as it is used for lock order.
Node B can only become the child of node A in two ways:
- being created with `child_node()`, in which case it is trivially true that
node A already existed when node B was created
- being moved A->C->B to A->B because node C was removed in `decrease_handle_refcount()`
or `cancel()`. In this case the invariant still holds, as B was younger than C, and C
was younger than A, therefore B is also younger than A.
3. If two nodes are both unlocked and node A is the parent of node B, then node B is a child of
node A. It is important to always restore that invariant before dropping the lock of a node.
# Deadlock safety
We always lock in the order of creation time. We can prove this through invariant #2.
Specifically, through invariant #2, we know that we always have to lock a parent
before its child.
|
14143 |
- |