Module tree_node

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.

Structs

Inner 🔒

The data contained inside a TreeNode.

TreeNode 🔒

A node of the cancellation tree structure

Functions

cancel 🔒

Cancels a node and its children.

child_node 🔒

Creates a child node

decrease_handle_refcount 🔒

Decreases the reference count of handles.

disconnect_children 🔒

Disconnects the given parent from all of its children.

increase_handle_refcount 🔒

Increases the reference count of handles.

is_cancelled 🔒

Returns whether or not the node is cancelled

move_children_to_parent 🔒

Moves all children from node to parent.

remove_child 🔒

Removes a child from the parent.

with_locked_node_and_parent 🔒

Figures out the parent of the node and locks the node and its parent atomically.