[bind10-dev] DomainTree::remove() and node fusion behavior

[Mukund Sivaraman]

Hi all

[NOTE: this will mainly make sense to an existing BIND 10 developer.
 I don't want to explain DomainTree in detail here.]

trac2750 is the branch where DomainTree::remove() is being
implemented. The implementation is now mostly complete, and there are
some documentation and other bits that are left to be done before
putting it to review.

I want to discuss the fusion behavior of DomainTree (the opposite of
node fission).

As you know, DomainTree is a forest of BSTs. If there are 2 nodes in a
subtree, and remove() is called on one of them, that node is
deleted. Only 1 node then remains in the sub-tree and node fusion is
attempted.  If the parent node ("upper node") of the remaining node does
not have any data (is empty), the nodes are valid candidates for node
fusion.

The label data of a node is stored at address (this + 1), i.e.,
following right after the node's object in memory. During insertion if
*node fission* occurs, to make sure that any node pointers held by user
code are not invalidated, we create a new node with the "super-domain"
part of the label sequence and set it as the old node's parent, and we
right-truncate the child label. The child's buffer still has space to
store the parent's label appended to the child's label. The existing
user pointer points to the child node and is valid.

During fusion, we cannot rely on the fact that this exact child will
re-appear as the candidate for fusion with its parent. The child node
may have been deleted since, and other new nodes may exist in the tree
which certainly do not have space to store the entire child+parent label
data.

What is done in trac2750 is that if a child and parent are candidates
for node fusion, a new node is created to replace both the parent and
child. Its data is set to what should correctly exist at that place, and
the old parent and child are removed from the tree.

Within a single remove() call, such node fusion can occur several times
iteratively up the tree when conditions permit. As an example:

                   .
                   |
                   b
                 /   \
                a    d.e.f
                    /  |   \
                   c   |    g.h
                       |     |
                      w.y    i
                       |      \
                       |       k
                       |
                       p
                     /   \
                    o     q
      

If "o" and "q" are removed from the tree, and "d.e.f" and "w.y" do not
contain any data at that point in time, "p" is first fused with "w.y" to
form "p.w.y", and then "p.w.y" is fused with "d.e.f" to form
"p.w.y.d.e.f". See the unittests in trac2750 for this in action.

There is an unintended consequence to node fusion which replaces
existing nodes. If client code (that uses DomainTree) has
DomainTreeNode* pointers in its code, they could become invalid (as both
the old parent and child nodes are deleted) and the user will have to
re-lookup the required nodes with find() or other seek methods such as
nextNode() and previousNode(). This is a drawback, but on the other
hand, we cannot avoid performing node fusion on a long-living tree as
the tree will simply grow otherwise. Please comment on this.

One alternative is to add a bool argument to remove() that conditionally
enables or disables node fusion. When node fusion is disabled, the old
pointers do not become invalid after a delete operation. The tree is
perfectly valid without node fusion, but is sub-optimal.

		Mukund
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 2881 bytes
Desc: not available
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20130830/390e8bd0/attachment.bin>