Refactor RBTDB

Whereas #722 (closed) is about the rbt lookup data structure (used in lots of places in BIND), this is about the rbtdb that is built on rbt, and stores cache contents and authoritative zone data.

The problem is that rbtdb is a tangle of functionality that would ideally be separated, and the tangle is not isolated but ties in to other parts of the code.

I plan to use this issue to collect notes about rbtdb-related things that need cleaning up, so expect it to have an unclear scope, and plenty of edits as our understanding changes. When we find a problem that has a clear outline and a feasible solution, that will become a separate issue.

tangles - vertical

In principle there are a few parts in a DNS database that ideally would be separated:

• general-purpose lookup index structures, e.g. comparison tree, radix tree, hash table

• DNS-specific helper structures for handling the "tricky details" listed in the DB notes.

• representation of domain names and DNS rdata in memory

BIND's red-black tree contains extra fields that are just for the rbtdb, even though the rbt is used for a number of other purposes.

Similarly, rdataslab storage is notionally separated from rbtdb, but it is only used by rbtdb, and much of the rdataslab implementation is inside rbtdb.

The rdataset API is not clear whether it is just for accessing DNS rdata, because also helps with the DNS namespace. There isn't a distinct layer for that: it is handled partly by the basic RBT, partly by RBTDB, partly by the rdataset/rdataslab interface.

tangles - horizontal

The "tricky details" of a DNS cache are rather different from authoritative data, and it isn't obvious that it makes sense to use the same data structures for them both. In BIND the rbtdb mixes them together.

The separation between rdataslab and rbtdb might make more sense if the header part were different for the cache and for an authoritative zone, but this separation isn't used, and its implementation is so dirty that it probably would not make it easier to separate cache and auth.

BIND has multiple implementations of its dns_db interface for authoritative zones. They all use dns_rdataset_t to pass DNS records in and out. The rdataset structure has some support for this polymorphism, but it is woeful.

specific things to fix

• Refactor dns_rdataset_t->privateN #3273 (closed)

• make the rdataslab implementation more self-contained

  • can we split off the header structure that has the cache/auth details? or would that harm performance too much?

  • can we make the rdataslab implementation more typeful, less like hand-written serialization and deserialization code?

• the layout of an rdataslab is not the same for all rrtypes: RRSIG records have an extra byte to remember whether the corresponding key is offline or not

  • can the offline status of a key be stored with the key instead?

• when a struct is directly followed in memory by some specially structured data, use a flexible array member to indicate this

  • the domain name following an rbtnode

  • the raw rdata following an rdataslab header

• examine how the noqname and covers methods on rdatasets work: does it make sense to decouple them?

  • might need to do this before the flexible array member change, because of an interaction between rbtdb's rdataset raw pointer and its noqname and covers implementations