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

[JINMEI Tatuya / 神明達哉]

At Fri, 30 Aug 2013 12:47:50 +0530,
Mukund Sivaraman <muks at isc.org> wrote:

> On Fri, Aug 30, 2013 at 08:58:03AM +0200, Michal 'vorner' Vaner wrote:
> > On the other side. Does the documentation promise that we preserve
> > pointers through all the operations? Does it say at insert? I don't
> > think so (but I did not check). Do we rely on such thing anywhere? It
> > seems quite common to have a delete operation on container classes
> > that invalidates all the iterators ‒ which are abstracted pointers. So
> > I think it would be OK to invalidate the pointers on delete.
> 
> Do we rely on such thing anywhere? I remember seeing code in the tree
> some months ago and thinking to myself "oh so this is why we rewrote
> nodeFission() to preserve the pointer". I don't remember where it was
> now. :)
> 
> Also nodeFission() originally did the reverse of what it does now with
> nodes. It used to make the new node the child node, and keep the old
> node as the parent "upper node". It was rewritten to have the opposite
> behavior with a specific ticket for it, so it didn't invalidate existing
> pointers to nodes.

We did so in case we want to provide shortcut links between the nodes,
most specifically if we want to optimize lookup for query processing
further by providing shortcut links from NS RDATA to the corresponding
DomainTree node.

As for the original question itself, I'd first point out the idea of
"fusion on delete" was originally tried in BIND 9 and then rejected.
See the long comment for lib/dns/rbt.c:dns_rbt_deletenode().  Since
the usage and expectation are not completely the same for BIND 9 and
BIND 10, we do not necessarily have to adopt the same conclusion, but
we should at least learn from previous lessons.

If I were to vote, I'd rather keep the implementation simpler by not
trying fusion.  The fusion operation would require allocating another
node, which can fail, so this means either remove() can fail (which
would normally be unexpected) or we need some effort for handling the
error case (making the implementation more complicated).  Regarding
the memory (and possibly subsequent lookup) efficiency I tend to agree
with Michal (i.e., wouldn't be a serious issue in practice).  Also, if
we really need to worry about it I suspect we'll also need to think
about "compacting" the memory image (here I assume we'd mainly use
mapped memory image).  If and when we need to do this, we can also
reorganize the tree naturally.

--
JINMEI, Tatuya