[bind10-dev] rbtree find implementation

[JINMEI Tatuya / 神明達哉]

At Sat, 25 Dec 2010 22:42:15 +0800,
"feng" <hanfeng at cnnic.cn> wrote:

> It only has down pointer, so the find call for any domain in the zone will
> always return PARTIALMATCH
> 
> which maybe not be what the user wants

Do you mean we can never return NXDOMAIN even if the searched name
isn't in the zone?  If so, you're right, our current (intermediate)
implementation has this problem.

> so the problem is that the check for root node if PARTIALMATCH returns
> should be put into rbtree or  memoryzone ?
> 
> If we define rbtree as a general map mapping domain to anything else , the
> check should be put into memoryzone. 
> 
> But if in this way, the find code in MemoryZone will look strange to me.

There may be a better way, but BIND 9 puts the smartness in the zone
DB.  So, in our case, it would be in MemoryZone.  And yes, the
resulting code will look tricky.  I suspect we cannot avoid some level
of tricks as the underlying search logic of domain names is non
trivial (there are many subtle corner cases: empty non terminal,
wildcard, zone cut handling, DNSSEC related consideration...).

For the short term work item of #447, however, I suggest we forget it
for now, and only consider the simple exact match case.  We'll cover
other trickier cases step by step.

> A more general question is that rbtree should be uses to store the zone data
> or used as a general map?

The original plan is to use it as a general map with less smartness
just because that's what BIND 9 does and our original plan is to begin
with a straightforward port of that implementation.  Once we complete
the initial implementation we can revisit whether there's a better
way.

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