[bind10-dev] new in-memory zone data design

[JINMEI Tatuya / 神明達哉]

At Thu, 21 Jun 2012 10:35:10 +0200,
Michal 'vorner' Vaner <michal.vaner at nic.cz> wrote:

> > >  * Again, when we delete something and something else pointed to it, what
> > >    happens?
> > 
> > With reference counting, we cannot delete anything as long as
> > something points to it.
> 
> So, are we going to do our own manual reference counting? Or can we combine the
> offset pointers with shared_ptr somehow?

Hmm, I didn't think about it from this angle.  It might be possible to
introduce something like "shared offset pointer" for this purpose, but
it at least won't be straightforward.

Assume we are removing all RRs for a name (which would normally mean
we remove the name from the zone(=tree) as well unless it becomes an
empty non terminal).  The most straightforward implementation is to
introduce a refcount member in each pointer object, but in our case
this means it increases the necessary memory footprint for the zone
accordingly.  It may be possible to implement this concept while
keeping the shared_ptr like convenient semantics, but we'll need to do
it ourselves (it's unlikely we cannot use, e.g., existing boost
objects), and I'm not sure whether it's more lightweight than having
and maintaining reference counter in each node in terms of development
and maintenance complexity.

> > >  * Is it possible to deduce the name from the node only, or do we need the
> > >    path?
> > 
> > It's not possible without the path in the initially proposed version.
> > Depending on a tradeoff between memory efficiency and processing
> > efficiency, there can be other choices.
> 
> So, if there's a shortcut-link to another node, how do we know the name?

By following the tree links back up to the absolute label.  Conceptual
code that implements this is:

  // for given "node"
  name_data = "";
  while (true) {
      name_data += node->name_data;
      if (node->is_absolute) {
         return (name_data);
      }
      do {
          node = node->parent;
      } while (!node->is_root);
      // at this point we've reached the node at one level upper
  }

Here we assume not-yet-described extensions: is_root indicates whether
the node is located at the root of the level (i.e., root of a single
subtree of tree-in-trees); node->parent of such node points to the
node at the upper level whose "down" link points to that node.  This
is how BIND 9 works, btw.

As an optimization, we could introduce another pointer in each node
that points to the node that would be identified in the "do" loop in
the above pseudo code.  It trades implementation complexity and memory
footprint for operation performance.  NSD works that way.

---
JINMEI, Tatuya
Internet Systems Consortium, Inc.