BIND 10 #2218: update InMemoryZoneFinder::findNSEC3 using memory-efficient version

[BIND 10 Development]

#2218: update InMemoryZoneFinder::findNSEC3 using memory-efficient version
-------------------------------------+-------------------------------------
                   Reporter:         |                 Owner:  jinmei
  jinmei                             |                Status:  reviewing
                       Type:  task   |             Milestone:
                   Priority:         |  Sprint-20121009
  medium                             |            Resolution:
                  Component:  data   |             Sensitive:  0
  source                             |           Sub-Project:  DNS
                   Keywords:         |  Estimated Difficulty:  5
            Defect Severity:  N/A    |           Total Hours:  10.75
Feature Depending on Ticket:         |
  scalable inmemory                  |
        Add Hours to Ticket:  0      |
                  Internal?:  0      |
-------------------------------------+-------------------------------------
Changes (by muks):

 * owner:  muks => jinmei


Comment:

 Hi Jinmei

 Replying to [comment:18 jinmei]:
 > It rather suggests the concept of signed-or-non-signed is independent
 > from the existence of NSEC/NSEC3. (but maybe the second paragraph gave
 > you your impression?).

 Yes it was that paragraph.

 >
 > The relationship and clear definition of "signed" were left open
 > partially on purpose - I expected when we support incremental
 > signing or migration between NSEC and NSEC3, it will be possible that
 > the zone wouldn't be considered "signed" but still have NSEC or NSEC3
 > records.  That's the basic rationale of separating the concept of
 > "NSEC signed" and "zone is signed".  In that sense, it doesn't really
 > match the original vague intent if we mark the zone "signed" just
 > because the zone has NSEC3 (or NSEC3PARAM).
 >
 > But, anyway, at the moment this won't cause any difference in
 > observable server behavior as we only support complete, full loading
 > of zones.
 >
 > So, for the purpose of this ticket I'm okay with the current code.
 > We'll need a separate cleanup ticket though.

 Let's clean it up when we support incremental signing. We will notice it
 anyway then.

 >
 > > > '''zone_finder_unittest.cc'''
 > > >
 > > > - does addZoneData() need everything for the NSEC3 case?  It seems
 to
 > > >   be almost a duplicate of the main code, which is not generally
 good.
 > > >   For example, if the test data aren't expected to contain
 > > >   inconsistent NSEC3 param, it's probably better just to skip the
 > > >   check.
 > >
 > > Let's keep this for now as the worst thing it does is check more. :) I
 want to finish up the other loose ends and merge this.
 >
 > Okay, can you open a ticket for that?

 I've fixed it in branch trac2218_3. Please review it and I'll close this
 bug after that.

 >
 > > > '''zone_finder.cc'''
 > > >
 > > > I have a few more suggestions
 > > > - InMemoryZoneFinder::getOrigin() is expensive and should better be
 > > >   avoided whenever possible.  It looks like possible to use the
 label
 > > >   sequence of the origin node and use LabelSequence based interfaces
 > > >   in both cases.
 > >
 > > Done. I've also made it use the previous-chain relative `find()` which
 was added in a recent bug to search relative to the origin node.
 >
 > Okay.  In the case of the NSEC3 tree I'm not sure how much it buys or
 > whether it's even really faster (I'm assuming you did it as a kind of
 > performance optimization), but I don't oppose to the change itself.
 >
 > Looking into the code further, I noticed another possibility of
 > optimization:
 > {{{#!cpp
 >     for (unsigned int labels = qlabels; labels >= olabels; --labels) {
 >         const Name& hname = (labels == qlabels ?
 >                              name : name.split(qlabels - labels,
 labels));
 >         const std::string hlabel = hash->calculate(hname);
 > }}}
 > if we extend `NSEC3Hash()` so it can take a `LabelSequence` (must be
 > absolute), we should be able to avoid the expensive `Name::split()`.
 > But that's definitely beyond the scope of this ticket.  And,
 > calculate() is probably the most significant bottleneck in this
 > context anyway, so other optimizations may be marginal.
 >

 This would need additional methods in `LabelSequence` (that are in `Name`
 such as `downcase()`) to work on a copy of the passed label sequence
 inside `calculate()`. LabelSequence is also written to assume that its
 internal data is const, so we may have to create a `Name` copy instead
 (there's no inexpensive way to do this from `LabelSequence`).

 > > > '''nsec3hash.h,cc'''
 > > >
 > > > - A minor, and possibly controversial point: for the new signature
 of
 > > >   factory, it might be better to take `const uint8_t*` and `size_t`
 > > >   instead of `vector<uint8_t>`, considering this is a relatively
 lower
 > > >   level primitive when performance is important.  If we require a
 > > >   vector, the caller needs to prepare for it, which might be
 expensive
 > > >   depending on the context (see above).
 > >
 > > It's been changed now. `NSEC3Hash` was internally refactored for it.
 >
 > I'd keep the internal vector and copy the given data + size into it,
 > but I don't oppose to your version.

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