BIND 10 #2056: ZoneFinder::Context::getNegativeProof

[BIND 10 Development]

#2056: ZoneFinder::Context::getNegativeProof
-------------------------------------+-------------------------------------
                   Reporter:         |                 Owner:
  jinmei                             |                Status:  new
                       Type:  task   |             Milestone:  Next-Sprint-
                   Priority:         |  Proposed
  medium                             |            Resolution:
                  Component:  data   |             Sensitive:  0
  source                             |           Sub-Project:  DNS
                   Keywords:         |  Estimated Difficulty:  8
            Defect Severity:  N/A    |           Total Hours:  0
Feature Depending on Ticket:         |
        Add Hours to Ticket:  0      |
                  Internal?:  0      |
-------------------------------------+-------------------------------------
Description changed by jinmei:

Old description:

> When we revise the in-memory zone data in a memory-efficient manner,
> getting the owner name of an RRset will probably become relatively
> expensive because it's quite likely that the underlying specialized
> `RRset` implementation doesn't hold it in the form of dns::Name
> object.
>
> So, in order to make this revision without sacrificing lookup
> performance too much, we'll probably need to make it possible for the
> in-memory implementation to customize post-lookup operation where the
> default behavior would rely on using the owner name of the returned
> RRset of the initial lookup.
>
> This is one such case, and already experimentally tried in trac1607exp
> branch.  Referring to that branch, what should be implemented is:
>
> {{{#!cpp
>     // Called for NXDOMAIN/NXRRSET cases and return NSEC/NSEC3 RRsets
>     // for the corresponding DNSSEC proof.  It (will) consist of small
> helper
>     // private methods for specific cases (NSEC or NSEC3, NXDOMAIN or
> NXRRSET).
>     //
>     // - NSEC + NXRRSET
>     //   find() already returns the direct proof.  So it should already
>     //   be efficient.  The ramining issue is the corresponding wildcard
>     //   proof.
>     //   Default version: calls find() for the qname again, with the
>     //     NO_WILDCARD option and add the returned NSEC.
>     //   Optimized in-memory version: it should know where in the rbtree
> the
>     //     original (non wildcard) search stopped and can use the
> information
>     //     to get the NSEC proof for the non existence of the qname
> itself.
>     // - NSEC + NXDOMAIN
>     //   find() already returns the NSEC for the non existent proof, so
> it
>     //   should be already efficient.  The ramining issue is the proof
> that
>     //   there's even no wildcard match.
>     //   Default version: construct the best possible wildcard name from
> qname
>     //     and the NSEC that proves non-existent of the name, and
> internally
>     //     calls find(NSEC) for that name.
>     //   Optimized in-memory version: it should know the closest encloser
> in
>     //     the previous search and can identify the wildcard name and its
>     //     previous name, then subsequently its NSEC.
>     //
>     // - NSEC3 + NXDOMAIN
>     //   Default version: use findNSEC3() to get closest encloser proof,
> use
>     //     the result to identify the possible wildcard, and use
> findNSEC3()
>     //     to get proof for its non-existence.
>     //   Optimized in-memory version: it should know the closest encloser
> in
>     //     the original search.  get corresponding NSEC3 directly,
> construct
>     //     next closer and wildcard from the closest encloser, calculate
> hash
>     //     and get the covering NSEC3.
>     // - NSEC3 + NXRRSET (no wildcard)
>     //   Default version: use findNSEC3() to get either closest encloser
> proof
>     //     (optout DS case) or matching NSEC3.
>     //   Optimized in-memory version: it knows the corresponding rbtnode
>     //     for the qname.  Get the hash value from it and get its NSEC3.
>     //     If it doesn't exist and qtype was DS, search the tree back
> toward
>     //     the root until it finds a matching NSEC3.
>     // - NSEC3 + NXRRSET (wildcard)
>     //   Default version: use findNSEC3() to get the closest encloser
> proof,
>     //     construct the wildcard name based on the result, and get the
> NSEC3
>     //     for it.
>     //   Optimized in-memory version: similar to the NSEC3 + NXDOMAIN
> case.
>     //     But the wildcard name should exist so it could even more
> optimize
>     //     it by directly getting the wildcard node and its NSEC3.
> }}}
>
> And in this ticket we'll only need to do the "default version".  It
> should be essentially straightforward refactoring.

New description:

 When we revise the in-memory zone data in a memory-efficient manner,
 getting the owner name of an RRset will probably become relatively
 expensive because it's quite likely that the underlying specialized
 `RRset` implementation doesn't hold it in the form of dns::Name
 object.

 So, in order to make this revision without sacrificing lookup
 performance too much, we'll probably need to make it possible for the
 in-memory implementation to customize post-lookup operation where the
 default behavior would rely on using the owner name of the returned
 RRset of the initial lookup.

 This is one such case, and already experimentally tried in trac1607exp
 branch.  Referring to that branch, what should be implemented is:

 {{{#!cpp
     // Called for NXDOMAIN/NXRRSET cases and return NSEC/NSEC3 RRsets
     // for the corresponding DNSSEC proof.  It (will) consist of small
 helper
     // private methods for specific cases (NSEC or NSEC3, NXDOMAIN or
 NXRRSET).
     //
     // - NSEC + NXRRSET
     //   find() already returns the direct proof.  So it should already
     //   be efficient.  The ramining issue is the corresponding wildcard
     //   proof.
     //   Default version: calls find() for the qname again, with the
     //     NO_WILDCARD option and add the returned NSEC.
     //   Optimized in-memory version: it should know where in the rbtree
 the
     //     original (non wildcard) search stopped and can use the
 information
     //     to get the NSEC proof for the non existence of the qname
 itself.
     // - NSEC + NXDOMAIN
     //   find() already returns the NSEC for the non existent proof, so it
     //   should be already efficient.  The ramining issue is the proof
 that
     //   there's even no wildcard match.
     //   Default version: construct the best possible wildcard name from
 qname
     //     and the NSEC that proves non-existent of the name, and
 internally
     //     calls find(NSEC) for that name.
     //   Optimized in-memory version: it should know the closest encloser
 in
     //     the previous search and can identify the wildcard name and its
     //     previous name, then subsequently its NSEC.
     //
     // - NSEC3 + NXDOMAIN
     //   Default version: use findNSEC3() to get closest encloser proof,
 use
     //     the result to identify the possible wildcard, and use
 findNSEC3()
     //     to get proof for its non-existence.
     //   Optimized in-memory version: it should know the closest encloser
 in
     //     the original search.  get corresponding NSEC3 directly,
 construct
     //     next closer and wildcard from the closest encloser, calculate
 hash
     //     and get the covering NSEC3.
     // - NSEC3 + NXRRSET (no wildcard)
     //   Default version: use findNSEC3() to get either closest encloser
 proof
     //     (optout DS case) or matching NSEC3.
     //   Optimized in-memory version: it knows the corresponding rbtnode
     //     for the qname.  Get the hash value from it and get its NSEC3.
     //     If it doesn't exist and qtype was DS, search the tree back
 toward
     //     the root until it finds a matching NSEC3.
     // - NSEC3 + NXRRSET (wildcard)
     //   Default version: use findNSEC3() to get the closest encloser
 proof,
     //     construct the wildcard name based on the result, and get the
 NSEC3
     //     for it.
     //   Optimized in-memory version: similar to the NSEC3 + NXDOMAIN
 case.
     //     But the wildcard name should exist so it could even more
 optimize
     //     it by directly getting the wildcard node and its NSEC3.
 }}}

 And in this ticket we'll only need to do the "default version".  It
 should be essentially straightforward refactoring.

 When done, also update `auth::Query` so it uses this implementation.
 It's better to do it before trying to implement the in-memory
 optimization in case we miss something in the interface.

--

-- 
Ticket URL: <http://bind10.isc.org/ticket/2056#comment:3>
BIND 10 Development <http://bind10.isc.org>
BIND 10 Development