BIND - sorting of reverse domain.

[Kevin Darcy]

"D. Stussy" wrote:

> On 9 Jul 2002, Kevin Darcy wrote:
> >"D. Stussy" wrote:
> >> On 8 Jul 2002, Andris Kalnozols wrote:
> >> >Since this thread has gotten rather large (22 replies at last count),
> >> >I'll insert a few quotes before making my point.
> >> >
> >> >Original post:
> >> >
> >> >> D. Stussy <kd6lvw at bde-arc.ampr.org> wrote:
> >> >> It appears that BIND (I have version 9.2.1) sorts all its domain
> >> >> entries in the files it stores alphabetically ("machine sort order").
> >> >> That's fine for the forward domain file where domain/hostnames are
> >> >> usually alphabetic.  However, for the reverse domain file, it makes
> >> >> more sense to sort it in NUMERICAL value order, thus keeping adjacent
> >> >> IP addresses nearer to each other.  (Of course, I don't care what
> >> >> named does internally with the zone as a memory image ....)
> >> >
> >> >Selected replies:
> >> >
> >> >> Mark Andrews <mark_andrews at isc.org> replied:
> >> >> The order is DNSSEC order.  To support returning signed NXDOMAIN
> >> >> responses the namserver needs to know the node that appears
> >> >> immediately before the name in the query.  To do this it sorts the
> >> >> zone when it loads it into DNSSEC order.  When named writes out the
> >> >> zone it just walks the zone which results in records being emitted
> >> >> in DNSSEC order.
> >> >
> >> >> > Mark Andrews <mark_andrews at isc.org> replied:
> >> >> > BIND 9 sorts in DNSSEC order because it *needs* the zone to be
> >> >> > sorted this way to able to find the correct NXT record to be
> >> >> > returned with a NXDOMAIN response.
> >> >>
> >> >> D. Stussy <kd6lvw at bde-arc.ampr.org> wrote:
> >> >> Perhaps in the current implementation, but such need not be the case.
> >> >
> >> >> D. Stussy <kd6lvw at bde-arc.ampr.org> wrote:
> >> >> If true, then it must actively sort the zone file in order for
> >> >> it to be written out in alphabetical order (which is occuring
> >> >> with this version).  It is obviously bothering to take the time
> >> >> to do this, so while we're at it, why not write out the reverse
> >> >> domain files in numerical order where possible?  [We're back to
> >> >> my original question!]
> >> >
> >> >> D. Stussy <kd6lvw at bde-arc.ampr.org> wrote:
> >> >> ...How the RR records are ordered for a zone name is of no
> >> >> consequence whatsoever when determining whether or not the
> >> >> name EXISTS or not.  I couldn't care less about that - it is
> >> >> not relevent to the original question.
> >> >>
> >> >> My question was not one of how it IS coded - but one of how
> >> >> it MAY be coded.  How the current source code is actually
> >> >> written isn't of consequence because if the preference I asked
> >> >> about were to be accepted, the source program would have to be
> >> >> changed anyway.
> >> >>
> >> >> You all are too worried about the actual implementation while
> >> >> I'm talking about conceptual design - a separate step.
> >> >
> >> >After reading your comments, I get the distinct impression that
> >> >when DNSSEC is mentioned, you are not making the connection to
> >> >RFC-2535, the specification that implements it.  Here's what it
> >> >requires as a sort order:
> >> >
> >> >  8.2 Canonical DNS Name Order
> >> >
> >> >    For purposes of DNS security, the canonical ordering of owner names
> >> >    is to sort individual labels as unsigned left justified octet strings
> >> >    where the absence of a octet sorts before a zero value octet and
> >> >    upper case letters are treated as lower case letters.  Names in a
> >> >    zone are sorted by sorting on the highest level label and then,
> >> >    within those names with the same highest level label by the next
> >> >    lower label, etc. down to leaf node labels.  Within a zone, the zone
> >> >    name itself always exists and all other names are the zone name with
> >> >    some prefix of lower level labels.  Thus the zone name itself always
> >> >    sorts first.
> >> >
> >> >    Example:
> >> >          foo.example
> >> >          a.foo.example
> >> >          yljkjljk.a.foo.example
> >> >          Z.a.foo.example
> >> >          zABC.a.FOO.EXAMPLE
> >> >          z.foo.example
> >> >          *.z.foo.example
> >> >          \200.z.foo.example
> >> >
> >> >Since BIND 9 strives for strict compliance with IETF standards,
> >> >changing the internal sort order when a zone is loaded is not
> >> >an option if DNSSEC is to be implemented efficiently.
> >> >
> >> >To implement what you are asking means that the code for writing
> >> >out a zone to disk must first traverse the red-black tree to see
> >> >if the relative domain names consist solely of digits and, if so,
> >> >traverse the tree once again and resort the data numerically before
> >> >writing the disk file.  With all the essential work that name servers
> >> >(and BIND maintainers) have to do, do you still think that your idea
> >> >would be a good use of resources?
> >>
> >> Incorrect.  I have made that connection.  Note that this only talks about the
> >> name component, which is what I limited my query to.  DNSSEC order also takes
> >> into account the RR-set (a secondary sort key) order for a zone, and that falls
> >> OUTSIDE my query (by going beyond it).  Furthermore, the RFC requires an order
> >> for the MEMORY IMAGE, but again, that isn't relevent to the FILE image I queried
> >> about.
> >>
> >> Since others said that a zone ISN'T stored in alphabetical/machine order, but is
> >> written out as such, I properly concluded that before writing, an additional
> >> sort of the zone names was occuring so as to make the file listing of the zone
> >> appear in a human readable pattern.  It wasn't until later that they finally
> >> admitted that it was a side-effect of their tree-traversal (which
> >> coincidentally, did traverse the tree in machine order to write the file) -
> >> which means that it IS in fact sorted in machine order to begin with.  Beyond my
> >> query, my assertions were as a result of their false statements.
> >>
> >> However, there was also the contradiction.  At least one said that when
> >> searching for a zone by name, the search terminates when one hits a value
> >> greater (in machine order) than the target.  That only happens with a certain
> >> structure (a list) and is complete nonsense to others (e.g. a tree).  They then
> >> accuse me of misunderstanding.  That statement was clear but false once again.
> >>
> >> Had these responders to my query had not made these false statements, my
> >> question would have been mooted at the first response.  Their incorrect
> >> statements implied actions such as an additional sort before exportation to a
> >> file of the data.  I simply asked, if that's what you're doing (presumedly to
> >> make the file human readable), then why not make this adjustment (where both
> >> text values are completely numerical, compare on the numerical values) while
> >> performing this sort (which now I know doesn't exist).
> >>
> >> My follow-up question, once I overcame their falsehoods, then was:  Why was it
> >> chosen to save the file in machine order when that requires a tree-rebalance
> >> performance penalty when reading it back in (upon restart)?  If it is saved in
> >> this other tree traversal order, the rebalance penalty is completely avoided (as
> >> long as the zone file hadn't been tampered with in the meantime).  I still await
> >> an answer to that one.
> >
> >No-one really cares about squeezing an ounce of performance out of the zone-loading
> >process, especially if it has the potential to harm the human-readability of zone
> >files. There are much bigger fish to fry in the DNS world.
> >
> >If you want to send a patch to ISC, send a patch. Or subscribe yourself to
> >bind9-workers. bind-users is for *users* of BIND, and this discussion is off-topic
> >here. I intend this to be my last message in the thread.
>
> Of course, with the idiots here, I would expect no less than the above response
> - to subscribe to some sort of mailing list (which I assume that it is in
> absence of other statements) without telling me where the list is homed.
>
> Also, you are under the opinion that I am posting this to a list called
> "bind-users"?  Again, another wrong assertion, as I am posting this to a USENET
> newsgroup titled "comp.protocols.dns.bind".  My ISP's newsserver does not carry
> any other bind-specific newsgroups.  If my posts are being echoed into a mailing
> list, I have no knowledge of such, nor did I "design" my posts to accomodate
> such.  Again, another false assumption and/or statement by you.

Try the www.isc.org website if you want information on how to subscribe to an
ISC-hosted mailing list. You _are_ familiar with ISC, right? They're the folks that put
out BIND (among other things).

Through the magic of bi-directional gatewaying, this forum is *both* a mailing list
*and* a newsgroup. I'm not sure why you care whether it's one, or the other, or both.
All that really matters is that it is a technical, public forum, and that anything one
posts to it will be judged accordingly.


- Kevin

P.S. Yes, I did say that I *intended* my previous message to be the last in the thread.
But I thought some additional clarification might be helpful.