zone_finder.cc 39.6 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Copyright (C) 2012  Internet Systems Consortium, Inc. ("ISC")
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted, provided that the above
// copyright notice and this permission notice appear in all copies.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
// AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.

#include <datasrc/memory/zone_finder.h>
#include <datasrc/memory/domaintree.h>
#include <datasrc/memory/treenode_rrset.h>
18
#include <datasrc/memory/rdata_serialization.h>
19
20
21
22
23
24
25

#include <datasrc/zone.h>
#include <datasrc/data_source.h>
#include <dns/labelsequence.h>
#include <dns/name.h>
#include <dns/rrset.h>
#include <dns/rrtype.h>
26
#include <dns/nsec3hash.h>
27

28
29
#include <datasrc/logger.h>

30
#include <boost/scoped_ptr.hpp>
31
32
33
34
35
#include <boost/bind.hpp>

#include <algorithm>
#include <vector>

36
37
#include <utility>

38
39
40
41
using namespace isc::dns;
using namespace isc::datasrc::memory;
using namespace isc::datasrc;

42
43
44
namespace isc {
namespace datasrc {
namespace memory {
45

46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
namespace internal {

// Specialized version of ZoneFinder::ResultContext, which  holds objects
// related to find() results using internal representations of the in-memory
// data source implementation.
class ZoneFinderResultContext {
public:
    /// \brief Constructor
    ///
    /// The first three parameters correspond to those of
    /// ZoneFinder::ResultContext.  If node is non NULL, it specifies the
    /// found ZoneNode in the search.
    ZoneFinderResultContext(ZoneFinder::Result code_param,
                            TreeNodeRRsetPtr rrset_param,
                            ZoneFinder::FindResultFlags flags_param,
                            const ZoneData& zone_data_param,
                            const ZoneNode* node, const RdataSet* rdset) :
JINMEI Tatuya's avatar
JINMEI Tatuya committed
63
        code(code_param), rrset(rrset_param), flags(flags_param),
64
65
66
67
68
69
70
71
72
73
74
75
76
        zone_data(&zone_data_param), found_node(node), found_rdset(rdset)
    {}

    const ZoneFinder::Result code;
    const TreeNodeRRsetPtr rrset;
    const ZoneFinder::FindResultFlags flags;
    const ZoneData* const zone_data;
    const ZoneNode* const found_node;
    const RdataSet* const found_rdset;
};
}
using internal::ZoneFinderResultContext;

77
namespace {
78
79
80
81
82
83
84
85
86
87
88
/// Conceptual RRset in the form of a pair of zone node and RdataSet.
///
/// In this implementation, the owner name of an RRset is derived from the
/// corresponding zone node, and the rest of the attributes come from
/// an RdataSet.  This shortcut type can be used when we want to refer to
/// the conceptual RRset without knowing these details.
///
/// This is a read-only version of the pair (and at the moment we don't need
/// a mutable version).
typedef std::pair<const ZoneNode*, const RdataSet*> ConstNodeRRset;

89
90
91
92
93
94
95
96
97
/// Creates a TreeNodeRRsetPtr for the given RdataSet at the given Node, for
/// the given RRClass
///
/// We should probably have some pool so these  do not need to be allocated
/// dynamically.
///
/// \param node The ZoneNode found by the find() calls
/// \param rdataset The RdataSet to create the RRsetPtr for
/// \param rrclass The RRClass as passed by the client
98
99
/// \param realname If given, the TreeNodeRRset is created with this name
///                 (e.g. for wildcard substitution)
100
///
101
/// Returns an empty TreeNodeRRsetPtr if node is NULL or if rdataset is NULL.
102
103
TreeNodeRRsetPtr
createTreeNodeRRset(const ZoneNode* node,
104
                    const RdataSet* rdataset,
105
                    const RRClass& rrclass,
106
                    ZoneFinder::FindOptions options,
107
                    const Name* realname = NULL)
108
{
109
    const bool dnssec = ((options & ZoneFinder::FIND_DNSSEC) != 0);
110
    if (node != NULL && rdataset != NULL) {
111
        if (realname != NULL) {
112
113
114
            return (TreeNodeRRsetPtr(new TreeNodeRRset(*realname, rrclass,
                                                       node, rdataset,
                                                       dnssec)));
115
        } else {
116
117
            return (TreeNodeRRsetPtr(new TreeNodeRRset(rrclass, node, rdataset,
                                                       dnssec)));
118
        }
119
    } else {
120
        return (TreeNodeRRsetPtr());
121
    }
122
123
}

124
125
126
127
128
/// Maintain intermediate data specific to the search context used in
/// \c find().
///
/// It will be passed to \c cutCallback() (see below) and record a possible
/// zone cut node and related RRset (normally NS or DNAME).
129
130
131
132
struct FindState {
    FindState(bool glue_ok) :
        zonecut_node_(NULL),
        dname_node_(NULL),
133
        rrset_(NULL),
134
135
136
137
138
139
140
141
142
143
144
        glue_ok_(glue_ok)
    {}

    // These will be set to a domain node of the highest delegation point,
    // if any.  In fact, we could use a single variable instead of both.
    // But then we would need to distinquish these two cases by something
    // else and it seemed little more confusing when this was written.
    const ZoneNode* zonecut_node_;
    const ZoneNode* dname_node_;

    // Delegation RRset (NS or DNAME), if found.
145
    const RdataSet* rrset_;
146
147
148
149
150
151
152

    // Whether to continue search below a delegation point.
    // Set at construction time.
    const bool glue_ok_;
};

// A callback called from possible zone cut nodes and nodes with DNAME.
153
// This will be passed from findNode() to \c ZoneTree::find().
154
155
156
157
158
bool cutCallback(const ZoneNode& node, FindState* state) {
    // We need to look for DNAME first, there's allowed case where
    // DNAME and NS coexist in the apex. DNAME is the one to notice,
    // the NS is authoritative, not delegation (corner case explicitly
    // allowed by section 3 of 2672)
159
160
    const RdataSet* found_dname = RdataSet::find(node.getData(),
                                                 RRType::DNAME());
161
162
163
164

    if (found_dname != NULL) {
        LOG_DEBUG(logger, DBG_TRACE_DETAILED, DATASRC_MEM_DNAME_ENCOUNTERED);
        state->dname_node_ = &node;
165
        state->rrset_ = found_dname;
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
        return (true);
    }

    // Look for NS
    const RdataSet* found_ns = RdataSet::find(node.getData(), RRType::NS());
    if (found_ns != NULL) {
        // We perform callback check only for the highest zone cut in the
        // rare case of nested zone cuts.
        if (state->zonecut_node_ != NULL) {
            return (false);
        }

        LOG_DEBUG(logger, DBG_TRACE_DETAILED, DATASRC_MEM_NS_ENCOUNTERED);

        // BIND 9 checks if this node is not the origin.  That's probably
        // because it can support multiple versions for dynamic updates
        // and IXFR, and it's possible that the callback is called at
        // the apex and the DNAME doesn't exist for a particular version.
        // It cannot happen for us (at least for now), so we don't do
        // that check.
        state->zonecut_node_ = &node;
187
        state->rrset_ = found_ns;
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202

        // Unless glue is allowed the search stops here, so we return
        // false; otherwise return true to continue the search.
        return (!state->glue_ok_);
    }

    // This case should not happen because we enable callback only
    // when we add an RR searched for above.
    assert(0);
    // This is here to avoid warning (therefore compilation error)
    // in case assert is turned off. Otherwise we could get "Control
    // reached end of non-void function".
    return (false);
}

203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
/// Creates a NSEC3 ConstRRsetPtr for the given ZoneNode inside the
/// NSEC3 tree, for the given RRClass.
///
/// It asserts that the node contains data (RdataSet) and is of type
/// NSEC3.
///
/// \param node The ZoneNode inside the NSEC3 tree
/// \param rrclass The RRClass as passed by the client
ConstRRsetPtr
createNSEC3RRset(const ZoneNode* node, const RRClass& rrclass) {
     const RdataSet* rdataset = node->getData();
     // Only NSEC3 ZoneNodes are allowed to be passed to this method. We
     // assert that these have data, and also are of type NSEC3.
     assert(rdataset != NULL);
     assert(rdataset->type == RRType::NSEC3());

219
220
221
    // Create the RRset.  Note the DNSSEC flag: NSEC3 implies DNSSEC.
    return (createTreeNodeRRset(node, rdataset, rrclass,
                                ZoneFinder::FIND_DNSSEC));
222
223
}

224
// convenience function to fill in the final details
225
226
227
228
229
230
231
232
233
//
// Set up ZoneFinderResultContext object as a return value of find(),
// taking into account wildcard matches and DNSSEC information.  We set
// the NSEC/NSEC3 flag when applicable regardless of the find option; the
// caller would simply ignore these when they didn't request DNSSEC
// related results.
//
// Also performs the conversion of node + RdataSet into a TreeNodeRRsetPtr
//
234
235
236
// if wild is true, the RESULT_WILDCARD flag will be set.
// If qname is not NULL, this is the query name, to be used in wildcard
// substitution instead of the Node's name).
237
ZoneFinderResultContext
238
239
240
createFindResult(const RRClass& rrclass,
                 const ZoneData& zone_data,
                 ZoneFinder::Result code,
241
                 const RdataSet* rdset,
242
                 const ZoneNode* node,
243
                 ZoneFinder::FindOptions options,
244
                 bool wild = false,
245
246
                 const Name* qname = NULL)
{
247
    ZoneFinder::FindResultFlags flags = ZoneFinder::RESULT_DEFAULT;
248
    const Name* rename = NULL;
249
250
251

    if (wild) {
        flags = flags | ZoneFinder::RESULT_WILDCARD;
252
253
        // only use the rename qname if wild is true
        rename = qname;
254
255
256
257
258
259
    }
    if (code == ZoneFinder::NXRRSET || code == ZoneFinder::NXDOMAIN || wild) {
        if (zone_data.isNSEC3Signed()) {
            flags = flags | ZoneFinder::RESULT_NSEC3_SIGNED;
        } else if (zone_data.isSigned()) {
            flags = flags | ZoneFinder::RESULT_NSEC_SIGNED;
260
261
262
        }
    }

263
264
265
    return (ZoneFinderResultContext(code, createTreeNodeRRset(node, rdset,
                                                              rrclass, options,
                                                              rename),
266
                                    flags, zone_data, node, rdset));
267
268
}

269
270
271
272
273
274
275
276
277
278
279
// A helper function for NSEC-signed zones.  It searches the zone for
// the "closest" NSEC corresponding to the search context stored in
// node_path (it should contain sufficient information to identify the
// previous name of the query name in the zone).  In some cases the
// immediate closest name may not have NSEC (when it's under a zone cut
// for glue records, or even when the zone is partly broken), so this
// method continues the search until it finds a name that has NSEC,
// and returns the one found first.  Due to the prerequisite (see below),
// it should always succeed.
//
// node_path must store valid search context (in practice, it's expected
280
// to be set by findNode()); otherwise the underlying ZoneTree implementation
281
282
283
284
285
286
287
// throws.
//
// If the zone is not considered NSEC-signed or DNSSEC records were not
// required in the original search context (specified in options), this
// method doesn't bother to find NSEC, and simply returns NULL.  So, by
// definition of "NSEC-signed", when it really tries to find an NSEC it
// should succeed; there should be one at least at the zone origin.
288
ConstNodeRRset
289
getClosestNSEC(const ZoneData& zone_data,
290
               ZoneChain& node_path,
291
292
               ZoneFinder::FindOptions options)
{
293
294
295
    if (!zone_data.isSigned() ||
        (options & ZoneFinder::FIND_DNSSEC) == 0 ||
        zone_data.isNSEC3Signed()) {
296
        return (ConstNodeRRset(NULL, NULL));
297
298
299
    }

    const ZoneNode* prev_node;
300
301
    while ((prev_node = zone_data.getZoneTree().previousNode(node_path))
           != NULL) {
302
        if (!prev_node->isEmpty()) {
303
304
            const RdataSet* found =
                RdataSet::find(prev_node->getData(), RRType::NSEC());
305
            if (found != NULL) {
306
                return (ConstNodeRRset(prev_node, found));
307
308
309
310
311
312
313
314
            }
        }
    }
    // This must be impossible and should be an internal bug.
    // See the description at the method declaration.
    assert(false);
    // Even though there is an assert here, strict compilers
    // will still need some return value.
315
    return (ConstNodeRRset(NULL, NULL));
316
317
318
319
320
321
}

// A helper function for the NXRRSET case in find().  If the zone is
// NSEC-signed and DNSSEC records are requested, try to find NSEC
// on the given node, and return it if found; return NULL for all other
// cases.
322
const RdataSet*
323
324
325
326
327
328
329
getNSECForNXRRSET(const ZoneData& zone_data,
                  ZoneFinder::FindOptions options,
                  const ZoneNode* node)
{
    if (zone_data.isSigned() &&
        !zone_data.isNSEC3Signed() &&
        (options & ZoneFinder::FIND_DNSSEC) != 0) {
330
331
        const RdataSet* found = RdataSet::find(node->getData(),
                                               RRType::NSEC());
332
        if (found != NULL) {
333
            return (found);
334
335
        }
    }
336
    return (NULL);
337
338
}

339
// Structure to hold result data of the findNode() call
340
341
342
343
344
345
346
347
348
349
350
class FindNodeResult {
public:
    // Bitwise flags to represent supplemental information of the
    // search result:
    // Search resulted in a wildcard match.
    static const unsigned int FIND_WILDCARD = 1;
    // Search encountered a zone cut due to NS but continued to look for
    // a glue.
    static const unsigned int FIND_ZONECUT = 2;

    FindNodeResult(ZoneFinder::Result code_param,
351
352
                   const ZoneNode* node_param,
                   const RdataSet* rrset_param,
353
354
355
356
357
358
359
360
                   unsigned int flags_param = 0) :
        code(code_param),
        node(node_param),
        rrset(rrset_param),
        flags(flags_param)
    {}
    const ZoneFinder::Result code;
    const ZoneNode* node;
361
    const RdataSet* rrset;
362
363
364
    const unsigned int flags;
};

365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
// Implementation notes: this method identifies an ZoneNode that best matches
// the give name in terms of DNS query handling.  In many cases,
// DomainTree::find() will result in EXACTMATCH or PARTIALMATCH (note that
// the given name is generally expected to be contained in the zone, so
// even if it doesn't exist, it should at least match the zone origin).
// If it finds an exact match, that's obviously the best one.  The partial
// match case is more complicated.
//
// We first need to consider the case where search hits a delegation point,
// either due to NS or DNAME.  They are indicated as either dname_node_ or
// zonecut_node_ being non NULL.  Usually at most one of them will be
// something else than NULL (it might happen both are NULL, in which case we
// consider it NOT FOUND). There's one corner case when both might be
// something else than NULL and it is in case there's a DNAME under a zone
// cut and we search in glue OK mode ‒ in that case we don't stop on the
// domain with NS and ignore it for the answer, but it gets set anyway. Then
// we find the DNAME and we need to act by it, therefore we first check for
// DNAME and then for NS. In all other cases it doesn't matter, as at least
// one of them is NULL.
//
// Next, we need to check if the ZoneTree search stopped at a node for a
// subdomain of the search name (so the comparison result that stopped the
// search is "SUPERDOMAIN"), it means the stopping node is an empty
// non-terminal node.  In this case the search name is considered to exist
// but no data should be found there.
//
// If none of above is the case, we then consider whether there's a matching
// wildcard.  DomainTree::find() records the node if it encounters a
// "wildcarding" node, i.e., the immediate ancestor of a wildcard name
// (e.g., wild.example.com for *.wild.example.com), and returns it if it
// doesn't find any node that better matches the query name.  In this case
// we'll check if there's indeed a wildcard below the wildcarding node.
//
// Note, first, that the wildcard is checked after the empty
// non-terminal domain case above, because if that one triggers, it
// means we should not match according to 4.3.3 of RFC 1034 (the query
// name is known to exist).
//
// Before we try to find a wildcard, we should check whether there's
// an existing node that would cancel the wildcard match.  If
// DomainTree::find() stopped at a node which has a common ancestor
// with the query name, it might mean we are comparing with a
// non-wildcard node. In that case, we check which part is common. If
// we have something in common that lives below the node we got (the
// one above *), then we should cancel the match according to section
// 4.3.3 of RFC 1034 (as the name between the wildcard domain and the
// query name is known to exist).
//
// If there's no node below the wildcarding node that shares a common ancestor
// of the query name, we can conclude the wildcard is the best match.
// We'll then identify the wildcard node via an incremental search.  Note that
// there's no possibility that the query name is at an empty non terminal
// node below the wildcarding node at this stage; that case should have been
// caught above.
//
// If none of the above succeeds, we conclude the name doesn't exist in
421
422
423
424
// the zone, and throw an OutOfZone exception by default.  If the optional
// out_of_zone_ok is true, it returns an NXDOMAIN result with NULL data so
// the caller can take an action to it (technically it's not "NXDOMAIN",
// but the caller is assumed not to rely on the difference.)
425
FindNodeResult findNode(const ZoneData& zone_data,
426
                        const LabelSequence& name_labels,
427
                        ZoneChain& node_path,
428
429
                        ZoneFinder::FindOptions options,
                        bool out_of_zone_ok = false)
430
431
432
433
434
{
    ZoneNode* node = NULL;
    FindState state((options & ZoneFinder::FIND_GLUE_OK) != 0);

    const ZoneTree& tree(zone_data.getZoneTree());
435
436
    const ZoneTree::Result result = tree.find(name_labels, &node, node_path,
                                              cutCallback, &state);
437
438
439
440
441
442
443
444
445
    const unsigned int zonecut_flag =
        (state.zonecut_node_ != NULL) ? FindNodeResult::FIND_ZONECUT : 0;
    if (result == ZoneTree::EXACTMATCH) {
        return (FindNodeResult(ZoneFinder::SUCCESS, node, state.rrset_,
                               zonecut_flag));
    } else if (result == ZoneTree::PARTIALMATCH) {
        assert(node != NULL);
        if (state.dname_node_ != NULL) { // DNAME
            LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_DNAME_FOUND).
446
                arg(state.dname_node_->getName());
447
448
            return (FindNodeResult(ZoneFinder::DNAME, state.dname_node_,
                                   state.rrset_));
449
450
451
        }
        if (state.zonecut_node_ != NULL) { // DELEGATION due to NS
            LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_DELEG_FOUND).
452
                arg(state.zonecut_node_->getName());
453
454
455
            return (FindNodeResult(ZoneFinder::DELEGATION,
                                   state.zonecut_node_,
                                   state.rrset_));
456
        }
457
        if (node_path.getLastComparisonResult().getRelation() ==
458
            NameComparisonResult::SUPERDOMAIN) { // empty node, so NXRRSET
459
            LOG_DEBUG(logger, DBG_TRACE_DATA,
460
                      DATASRC_MEM_SUPER_STOP).arg(name_labels);
461
462
463
464
            ConstNodeRRset nsec_rrset = getClosestNSEC(zone_data, node_path,
                                                       options);
            return (FindNodeResult(ZoneFinder::NXRRSET, nsec_rrset.first,
                                   nsec_rrset.second));
465
466
        }
        // Nothing really matched.
467
468
469
470
471
472
473
474
475
476
477

        // May be a wildcard, but check only if not disabled
        if (node->getFlag(ZoneData::WILDCARD_NODE) &&
            (options & ZoneFinder::NO_WILDCARD) == 0) {
            if (node_path.getLastComparisonResult().getRelation() ==
                NameComparisonResult::COMMONANCESTOR) {
                // This means, e.g., we have *.wild.example and
                // bar.foo.wild.example and are looking for
                // baz.foo.wild.example. The common ancestor, foo.wild.example,
                // should cancel wildcard.  Treat it as NXDOMAIN.
                LOG_DEBUG(logger, DBG_TRACE_DATA,
478
                          DATASRC_MEM_WILDCARD_CANCEL).arg(name_labels);
479
480
481
482
483
                ConstNodeRRset nsec_rrset = getClosestNSEC(zone_data,
                                                           node_path,
                                                           options);
                return (FindNodeResult(ZoneFinder::NXDOMAIN, nsec_rrset.first,
                                       nsec_rrset.second));
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
            }
            uint8_t ls_buf[LabelSequence::MAX_SERIALIZED_LENGTH];

            // Create the wildcard name (i.e. take "*" and extend it
            // with all node labels down to the wildcard node
            LabelSequence wildcard_ls(LabelSequence::WILDCARD(), ls_buf);
            const ZoneNode* extend_with = node;
            while (extend_with != NULL) {
                wildcard_ls.extend(extend_with->getLabels(), ls_buf);
                extend_with = extend_with->getUpperNode();
            }

            // Clear the node_path so that we don't keep incorrect (NSEC)
            // context
            node_path.clear();
499
500
            ZoneTree::Result result = tree.find(wildcard_ls, &node, node_path,
                                                cutCallback, &state);
501
502
503
504
505
506
507
            // Otherwise, why would the domain_flag::WILD be there if
            // there was no wildcard under it?
            assert(result == ZoneTree::EXACTMATCH);
            return (FindNodeResult(ZoneFinder::SUCCESS, node, state.rrset_,
                        FindNodeResult::FIND_WILDCARD | zonecut_flag));
        }

508
509
        LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_NOT_FOUND).
            arg(name_labels);
510
511
512
513
        ConstNodeRRset nsec_rrset = getClosestNSEC(zone_data, node_path,
                                                   options);
        return (FindNodeResult(ZoneFinder::NXDOMAIN, nsec_rrset.first,
                               nsec_rrset.second));
514
515
    } else {
        // If the name is neither an exact or partial match, it is
516
517
518
519
520
        // out of bailiwick, which is considered an error, unless the caller
        // is willing to accept it.
        if (out_of_zone_ok) {
            return (FindNodeResult(ZoneFinder::NXDOMAIN, NULL, NULL));
        }
521
        isc_throw(OutOfZone, name_labels << " not in " <<
522
523
524
525
526
527
                             zone_data.getOriginNode()->getName());
    }
}

} // end anonymous namespace

528

529
530
531
532
533
534
/// \brief Specialization of the ZoneFinder::Context for the in-memory finder.
///
/// Note that we don't have a specific constructor for the findAll() case.
/// For (successful) type ANY query, found_node points to the
/// corresponding zone node, which is recorded within this specialized
/// context.
535
536
537
class InMemoryZoneFinder::Context : public ZoneFinder::Context {
public:
    Context(ZoneFinder& finder, ZoneFinder::FindOptions options,
538
            const RRClass& rrclass, const ZoneFinderResultContext& result) :
539
540
541
        ZoneFinder::Context(finder, options,
                            ResultContext(result.code, result.rrset,
                                          result.flags)),
542
        rrclass_(rrclass), zone_data_(result.zone_data),
543
544
        found_node_(result.found_node),
        found_rdset_(result.found_rdset)
545
546
    {}

547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
protected:
    virtual void getAdditionalImpl(const std::vector<RRType>& requested_types,
                                   std::vector<ConstRRsetPtr>& result)
    {
        if (found_rdset_ != NULL) {
            // Normal query with successful result.
            getAdditionalForRdataset(found_rdset_, requested_types, result,
                                     options_);
        } else if (found_node_ != NULL) {
            // Successful type ANY query result.  Call
            // getAdditionalForRdataset for each RdataSet of the node.
            for (const RdataSet* rdset = found_node_->getData();
                 rdset != NULL;
                 rdset = rdset->getNext())
            {
                getAdditionalForRdataset(rdset, requested_types, result,
                                         options_);
            }
        }
    }

private:
    // Main subroutine of getAdditionalImpl, iterate over Rdata fields
    // find, create, and insert necessary additional RRsets.
    void
    getAdditionalForRdataset(const RdataSet* rdset,
                             const std::vector<RRType>& requested_types,
                             std::vector<ConstRRsetPtr>& result,
                             ZoneFinder::FindOptions orig_options) const
    {
        ZoneFinder::FindOptions options = ZoneFinder::FIND_DEFAULT;
        if ((orig_options & ZoneFinder::FIND_DNSSEC) != 0) {
            options = options | ZoneFinder::FIND_DNSSEC;
        }
        if (rdset->type == RRType::NS()) {
            options = options | ZoneFinder::FIND_GLUE_OK;
        }

        RdataReader(rrclass_, rdset->type, rdset->getDataBuf(),
                    rdset->getRdataCount(), rdset->getSigRdataCount(),
                    boost::bind(&Context::findAdditional, this,
                                &requested_types, &result, options, _1, _2),
                    &RdataReader::emptyDataAction).iterate();
    }

    // RdataReader callback for additional section processing.
    void
    findAdditional(const std::vector<RRType>* requested_types,
                   std::vector<ConstRRsetPtr>* result,
                   ZoneFinder::FindOptions options,
                   const LabelSequence& name_labels,
                   RdataNameAttributes attr) const;

    // Subroutine for findAdditional() to unify the normal and wildcard match
    // cases.
    void
    findAdditionalHelper(const std::vector<RRType>* requested_types,
                         std::vector<ConstRRsetPtr>* result,
                         const ZoneNode* node,
                         ZoneFinder::FindOptions options,
                         const Name* real_name) const
    {
        const std::vector<RRType>::const_iterator type_beg =
            requested_types->begin();
        const std::vector<RRType>::const_iterator type_end =
            requested_types->end();
        for (const RdataSet* rdset = node->getData();
             rdset != NULL;
             rdset = rdset->getNext())
        {
            // Checking all types for all RdataSets could be suboptimal.
            // This can be a bit more optimized, but unless we have many
            // requested types the effect is probably marginal.  For now we
            // keep it simple.
            if (std::find(type_beg, type_end, rdset->type) != type_end) {
                result->push_back(createTreeNodeRRset(node, rdset, rrclass_,
                                                      options, real_name));
            }
        }
    }

628
private:
629
    const RRClass rrclass_;
630
    const ZoneData* const zone_data_;
631
    const ZoneNode* const found_node_;
632
    const RdataSet* const found_rdset_;
633
634
};

635
636
637
638
639
640
641
642
643
644
645
646
647
void
InMemoryZoneFinder::Context::findAdditional(
    const std::vector<RRType>* requested_types,
    std::vector<ConstRRsetPtr>* result,
    ZoneFinder::FindOptions options,
    const LabelSequence& name_labels,
    RdataNameAttributes attr) const
{
    // Ignore name data that don't need additional processing.
    if ((attr & NAMEATTR_ADDITIONAL) == 0) {
        return;
    }

648
649
    // Find the zone node for the additional name.  By passing true as the
    // last parameter of findNode() we ignore out-of-zone names.
650
651
    ZoneChain node_path;
    const FindNodeResult node_result =
652
        findNode(*zone_data_, name_labels, node_path, options, true);
653
654
655
656
657
    // we only need non-empty exact match
    if (node_result.code != SUCCESS) {
        return;
    }

658
659
660
661
662
663
    // Ignore data at a zone cut (due to subdomain delegation) unless glue is
    // allowed.  Checking the node callback flag is a cheap way to detect
    // zone cuts, but it includes DNAME delegation, in which case we should
    // keep finding the additional records regardless of the 'GLUE_OK' flag.
    // The last two conditions limit the case to delegation NS, i.e, the node
    // has an NS and it's not the zone origin.
664
665
666
    const ZoneNode* node = node_result.node;
    if ((options & ZoneFinder::FIND_GLUE_OK) == 0 &&
        node->getFlag(ZoneNode::FLAG_CALLBACK) &&
667
668
        node != zone_data_->getOriginNode() &&
        RdataSet::find(node->getData(), RRType::NS()) != NULL) {
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
        return;
    }

    // Examine RdataSets of the node, and create and insert requested types
    // of RRsets as we find them.
    if ((node_result.flags & FindNodeResult::FIND_WILDCARD) == 0) {
        // normal case
        findAdditionalHelper(requested_types, result, node, options, NULL);
    } else {
        // if the additional name is subject to wildcard substitution, we need
        // to create a name object for the "real" (after substitution) name.
        // This is expensive, but in the additional processing this should be
        // very rare cases and acceptable.
        size_t data_len;
        const uint8_t* data;
        data = name_labels.getData(&data_len);
        util::InputBuffer buffer(data, data_len);
        const Name real_name(buffer);
        findAdditionalHelper(requested_types, result, node, options,
                             &real_name);
    }
}

692
693
694
695
696
boost::shared_ptr<ZoneFinder::Context>
InMemoryZoneFinder::find(const isc::dns::Name& name,
                const isc::dns::RRType& type,
                const FindOptions options)
{
697
    return (ZoneFinderContextPtr(new Context(*this, options, rrclass_,
698
699
                                             findInternal(name, type,
                                                          NULL, options))));
700
701
702
703
704
705
706
}

boost::shared_ptr<ZoneFinder::Context>
InMemoryZoneFinder::findAll(const isc::dns::Name& name,
        std::vector<isc::dns::ConstRRsetPtr>& target,
        const FindOptions options)
{
707
    return (ZoneFinderContextPtr(new Context(*this, options, rrclass_,
708
709
710
711
                                             findInternal(name,
                                                          RRType::ANY(),
                                                          &target,
                                                          options))));
712
713
}

714
ZoneFinderResultContext
715
716
717
718
InMemoryZoneFinder::findInternal(const isc::dns::Name& name,
                                 const isc::dns::RRType& type,
                                 std::vector<ConstRRsetPtr>* target,
                                 const FindOptions options)
719
720
721
{
    // Get the node.  All other cases than an exact match are handled
    // in findNode().  We simply construct a result structure and return.
722
    ZoneChain node_path;
723
    const FindNodeResult node_result =
724
        findNode(zone_data_, LabelSequence(name), node_path, options);
725
    if (node_result.code != SUCCESS) {
726
        return (createFindResult(rrclass_, zone_data_, node_result.code,
727
728
                                 node_result.rrset, node_result.node,
                                 options));
729
730
731
732
733
734
    }

    const ZoneNode* node = node_result.node;
    assert(node != NULL);

    // We've found an exact match, may or may not be a result of wildcard.
735
736
737
    const bool wild = ((node_result.flags &
                        FindNodeResult::FIND_WILDCARD) != 0);

738
739
740
741
742
    // If there is an exact match but the node is empty, it's equivalent
    // to NXRRSET.
    if (node->isEmpty()) {
        LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_DOMAIN_EMPTY).
            arg(name);
743
744
        ConstNodeRRset nsec_rrset = getClosestNSEC(zone_data_, node_path,
                                                   options);
745
        return (createFindResult(rrclass_, zone_data_, NXRRSET,
746
747
                                 nsec_rrset.second, nsec_rrset.first,
                                 options, wild));
748
749
750
751
752
753
    }

    const RdataSet* found;

    // If the node callback is enabled, this may be a zone cut.  If it
    // has a NS RR, we should return a delegation, but not in the apex.
754
755
756
757
    // There are two exceptions:
    // - the case for DS query, which should always be considered in-zone
    //   lookup.
    // - when we are looking for glue records (FIND_GLUE_OK)
758
    if (node->getFlag(ZoneNode::FLAG_CALLBACK) &&
759
760
        (options & FIND_GLUE_OK) == 0 &&
        node != zone_data_.getOriginNode() && type != RRType::DS()) {
761
762
763
764
        found = RdataSet::find(node->getData(), RRType::NS());
        if (found != NULL) {
            LOG_DEBUG(logger, DBG_TRACE_DATA,
                      DATASRC_MEM_EXACT_DELEGATION).arg(name);
765
            return (createFindResult(rrclass_, zone_data_, DELEGATION,
766
                                     found, node, options, wild, &name));
767
768
769
770
771
772
773
774
        }
    }

    // Handle type any query
    if (target != NULL && node->getData() != NULL) {
        // Empty domain will be handled as NXRRSET by normal processing
        const RdataSet* cur_rds = node->getData();
        while (cur_rds != NULL) {
775
            target->push_back(createTreeNodeRRset(node, cur_rds, rrclass_,
776
                                                  options, &name));
777
778
779
780
            cur_rds = cur_rds->getNext();
        }
        LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_ANY_SUCCESS).
            arg(name);
781
        return (createFindResult(rrclass_, zone_data_, SUCCESS, NULL, node,
782
                                 options, wild, &name));
783
784
785
786
787
788
789
    }

    found = RdataSet::find(node->getData(), type);
    if (found != NULL) {
        // Good, it is here
        LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_SUCCESS).arg(name).
            arg(type);
790
        return (createFindResult(rrclass_, zone_data_, SUCCESS, found, node,
791
                                 options, wild, &name));
792
793
794
795
    } else {
        // Next, try CNAME.
        found = RdataSet::find(node->getData(), RRType::CNAME());
        if (found != NULL) {
796

797
            LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_CNAME).arg(name);
798
            return (createFindResult(rrclass_, zone_data_, CNAME, found, node,
799
                                     options, wild, &name));
800
801
802
        }
    }
    // No exact match or CNAME.  Get NSEC if necessary and return NXRRSET.
803
804
    return (createFindResult(rrclass_, zone_data_, NXRRSET,
                             getNSECForNXRRSET(zone_data_, options, node),
805
                             node, options, wild, &name));
806
807
808
809
}

isc::datasrc::ZoneFinder::FindNSEC3Result
InMemoryZoneFinder::findNSEC3(const isc::dns::Name& name, bool recursive) {
810
811
812
    LOG_DEBUG(logger, DBG_TRACE_BASIC, DATASRC_MEM_FINDNSEC3).arg(name).
        arg(recursive ? "recursive" : "non-recursive");

813
814
815
    uint8_t labels_buf[LabelSequence::MAX_SERIALIZED_LENGTH];
    const LabelSequence origin_ls(zone_data_.getOriginNode()->
                                  getAbsoluteLabels(labels_buf));
816
817
    const LabelSequence name_ls(name);

818
819
820
    if (!zone_data_.isNSEC3Signed()) {
        isc_throw(DataSourceError,
                  "findNSEC3 attempt for non NSEC3 signed zone: " <<
821
                  origin_ls << "/" << getClass());
822
823
    }

824
    const NSEC3Data* nsec3_data = zone_data_.getNSEC3Data();
825
826
827
828
    // This would be a programming mistake, as ZoneData::isNSEC3Signed()
    // should check this.
    assert(nsec3_data != NULL);

829
830
831
    const ZoneTree& tree = nsec3_data->getNSEC3Tree();
    if (tree.getNodeCount() == 0) {
        isc_throw(DataSourceError,
832
                  "findNSEC3 attempt but zone has no NSEC3 RRs: " <<
833
                  origin_ls << "/" << getClass());
834
835
    }

836
    const NameComparisonResult cmp_result = name_ls.compare(origin_ls);
837
838
839
    if (cmp_result.getRelation() != NameComparisonResult::EQUAL &&
        cmp_result.getRelation() != NameComparisonResult::SUBDOMAIN) {
        isc_throw(OutOfZone, "findNSEC3 attempt for out-of-zone name: "
840
                  << name_ls << ", zone: " << origin_ls << "/"
841
842
843
844
                  << getClass());
    }

    // Convenient shortcuts
845
    const unsigned int olabels = origin_ls.getLabelCount();
846
    const unsigned int qlabels = name.getLabelCount();
847
848
    // placeholder of the next closer proof
    const ZoneNode* covering_node(NULL);
849
850
851
852

    // Now we'll first look up the origin node and initialize orig_chain
    // with it.
    ZoneChain orig_chain;
853
    const ZoneNode* node(NULL);
854
855
856
857
858
859
860
861
862
    ZoneTree::Result result =
         tree.find<void*>(origin_ls, &node, orig_chain, NULL, NULL);
    if (result != ZoneTree::EXACTMATCH) {
        // If the origin node doesn't exist, simply fail.
        isc_throw(DataSourceError,
                  "findNSEC3 attempt but zone has no NSEC3 RRs: " <<
                  origin_ls << "/" << getClass());
    }

863
864
865
866
867
    const boost::scoped_ptr<NSEC3Hash> hash
        (NSEC3Hash::create(nsec3_data->hashalg,
                           nsec3_data->iterations,
                           nsec3_data->getSaltData(),
                           nsec3_data->getSaltLen()));
868
869
870
871
872

    // Examine all names from the query name to the origin name, stripping
    // the deepest label one by one, until we find a name that has a matching
    // NSEC3 hash.
    for (unsigned int labels = qlabels; labels >= olabels; --labels) {
873
874
        const Name& hname = (labels == qlabels ?
                             name : name.split(qlabels - labels, labels));
875
        const std::string hlabel = hash->calculate(hname);
876
877
878
879

        LOG_DEBUG(logger, DBG_TRACE_BASIC, DATASRC_MEM_FINDNSEC3_TRYHASH).
            arg(name).arg(labels).arg(hlabel);

880
881
        node = NULL;
        ZoneChain chain(orig_chain);
882

883
884
885
        // Now, make a label sequence relative to the origin.
        const Name hlabel_name(hlabel);
        LabelSequence hlabel_ls(hlabel_name);
Mukund Sivaraman's avatar
Mukund Sivaraman committed
886
        // Remove trailing '.' making it relative
887
        hlabel_ls.stripRight(1);
888

889
890
        // Find hlabel relative to the orig_chain.
        result = tree.find<void*>(hlabel_ls, &node, chain, NULL, NULL);
891
892
        if (result == ZoneTree::EXACTMATCH) {
            // We found an exact match.
893
            ConstRRsetPtr closest = createNSEC3RRset(node, getClass());
894
895
            ConstRRsetPtr next;
            if (covering_node != NULL) {
896
                next = createNSEC3RRset(covering_node, getClass());
897
            }
898
899
900
901
902
903
904

            LOG_DEBUG(logger, DBG_TRACE_BASIC,
                      DATASRC_MEM_FINDNSEC3_MATCH).arg(name).arg(labels).
                arg(*closest);

            return (FindNSEC3Result(true, labels, closest, next));
        } else {
905
906
907
908
909
910
            while ((covering_node = tree.previousNode(chain)) != NULL &&
                   covering_node->isEmpty()) {
                ;
            }
            if (covering_node == NULL) {
                covering_node = tree.largestNode();
911
912
913
            }

            if (!recursive) {   // in non recursive mode, we are done.
914
915
                ConstRRsetPtr closest;
                if (covering_node != NULL) {
916
                    closest = createNSEC3RRset(covering_node, getClass());
917

918
919
920
921
                    LOG_DEBUG(logger, DBG_TRACE_BASIC,
                              DATASRC_MEM_FINDNSEC3_COVER).
                        arg(name).arg(*closest);
                }
922
923
924
925
926
927
928
929
930
931

                return (FindNSEC3Result(false, labels,
                                        closest, ConstRRsetPtr()));
            }
        }
    }

    isc_throw(DataSourceError, "recursive findNSEC3 mode didn't stop, likely "
              "a broken NSEC3 zone: " << getOrigin() << "/"
              << getClass());
932
933
}

934
935
Name
InMemoryZoneFinder::getOrigin() const {
936
937
938
939
940
941
942
943
944
945
    // In future we may allow adding out-of-zone names in the zone tree.
    // For example, to hold out-of-zone NS names so we can establish a
    // shortcut link to them as an optimization.  If and when that happens
    // the origin node may not have an absolute label (consider the zone
    // is example.org and we add ns.noexample.org).  Even in such cases,
    // DomainTreeNode::getAbsoluteLabels() returns the correct absolute
    // label sequence.
    uint8_t labels_buf[LabelSequence::MAX_SERIALIZED_LENGTH];
    const LabelSequence name_labels =
         zone_data_.getOriginNode()->getAbsoluteLabels(labels_buf);
946
    size_t data_len;
947
    const uint8_t* data = name_labels.getData(&data_len);
948
949
950

    util::InputBuffer buffer(data, data_len);
    return (Name(buffer));
951
952
}

953
954
955
} // namespace memory
} // namespace datasrc
} // namespace isc