memory_datasrc.cc 20.8 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Copyright (C) 2010  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.

Michal Vaner's avatar
Michal Vaner committed
15
#include <map>
Michal Vaner's avatar
Michal Vaner committed
16
#include <cassert>
Michal Vaner's avatar
Michal Vaner committed
17
#include <boost/shared_ptr.hpp>
Michal Vaner's avatar
Michal Vaner committed
18
#include <boost/bind.hpp>
Michal Vaner's avatar
Michal Vaner committed
19

20
#include <dns/name.h>
21
#include <dns/rrclass.h>
chenzhengzhang's avatar
chenzhengzhang committed
22
#include <dns/rrsetlist.h>
Michal Vaner's avatar
Michal Vaner committed
23
#include <dns/masterload.h>
24

25
#include <datasrc/memory_datasrc.h>
Michal Vaner's avatar
Michal Vaner committed
26
#include <datasrc/rbtree.h>
27
28
29
30
31
32
33

using namespace std;
using namespace isc::dns;

namespace isc {
namespace datasrc {

Michal Vaner's avatar
Michal Vaner committed
34
// Private data and hidden methods of MemoryZone
35
struct MemoryZone::MemoryZoneImpl {
Michal Vaner's avatar
Michal Vaner committed
36
    // Constructor
37
    MemoryZoneImpl(const RRClass& zone_class, const Name& origin) :
38
        zone_class_(zone_class), origin_(origin), origin_data_(NULL)
39
40
41
42
43
44
    {
        // We create the node for origin (it needs to exist anyway in future)
        domains_.insert(origin, &origin_data_);
        DomainPtr origin_domain(new Domain);
        origin_data_->setData(origin_domain);
    }
Michal Vaner's avatar
Michal Vaner committed
45
46
47
48
49

    // Some type aliases
    /*
     * Each domain consists of some RRsets. They will be looked up by the
     * RRType.
50
51
52
53
54
55
56
     *
     * The use of map is questionable with regard to performance - there'll
     * be usually only few RRsets in the domain, so the log n benefit isn't
     * much and a vector/array might be faster due to its simplicity and
     * continuous memory location. But this is unlikely to be a performance
     * critical place and map has better interface for the lookups, so we use
     * that.
Michal Vaner's avatar
Michal Vaner committed
57
     */
Michal Vaner's avatar
Michal Vaner committed
58
    typedef map<RRType, ConstRRsetPtr> Domain;
Michal Vaner's avatar
Michal Vaner committed
59
    typedef Domain::value_type DomainPair;
Michal Vaner's avatar
Michal Vaner committed
60
    typedef boost::shared_ptr<Domain> DomainPtr;
Michal Vaner's avatar
Michal Vaner committed
61
    // The tree stores domains
62
    typedef RBTree<Domain, true> DomainTree;
Michal Vaner's avatar
Michal Vaner committed
63
    typedef RBNode<Domain> DomainNode;
64
    static const DomainNode::Flags DOMAINFLAG_WILD = DomainNode::FLAG_USER1;
65
66
67
68
69
70
71

    // Information about the zone
    RRClass zone_class_;
    Name origin_;
    DomainNode* origin_data_;
    string file_name_;

Michal Vaner's avatar
Michal Vaner committed
72
    // The actual zone data
Michal Vaner's avatar
Michal Vaner committed
73
    DomainTree domains_;
Michal Vaner's avatar
Michal Vaner committed
74

75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
    // Add the necessary magic for any wildcard contained in 'name'
    // (including itself) to be found in the zone.
    //
    // In order for wildcard matching to work correctly in find(),
    // we must ensure that a node for the wildcarding level exists in the
    // backend RBTree.
    // E.g. if the wildcard name is "*.sub.example." then we must ensure
    // that "sub.example." exists and is marked as a wildcard level.
    // Note: the "wildcarding level" is for the parent name of the wildcard
    // name (such as "sub.example.").
    //
    // We also perform the same trick for empty wild card names possibly
    // contained in 'name' (e.g., '*.foo.example' in 'bar.*.foo.example').
    void addWildcards(DomainTree& domains, const Name& name) {
        Name wname(name);
        const unsigned int labels(wname.getLabelCount());
        const unsigned int origin_labels(origin_.getLabelCount());
        for (unsigned int l = labels;
             l > origin_labels;
             --l, wname = wname.split(1)) {
            if (wname.isWildcard()) {
                DomainNode* node;
                DomainTree::Result result;

                // Ensure a separate level exists for the wildcard name.
                // Note: for 'name' itself we do this later anyway, but the
                // overhead should be marginal because wildcard names should
                // be rare.
                result = domains.insert(wname.split(1), &node);
                assert(result == DomainTree::SUCCESS ||
                       result == DomainTree::ALREADYEXISTS);
106
                node->setFlag(DOMAINFLAG_WILD);
107

108
109
                // Ensure a separate level exists for the "wildcarding" name,
                // and mark the node as "wild".
110
111
112
113
114
115
116
                result = domains.insert(wname, &node);
                assert(result == DomainTree::SUCCESS ||
                       result == DomainTree::ALREADYEXISTS);
            }
        }
    }

117
118
119
120
121
122
123
    /*
     * Does some checks in context of the data that are already in the zone.
     * Currently checks for forbidden combinations of RRsets in the same
     * domain (CNAME+anything, DNAME+NS).
     *
     * If such condition is found, it throws AddError.
     */
124
125
    void contextCheck(const ConstRRsetPtr& rrset,
                      const DomainPtr& domain) const {
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
        // Ensure CNAME and other type of RR don't coexist for the same
        // owner name.
        if (rrset->getType() == RRType::CNAME()) {
            // XXX: this check will become incorrect when we support DNSSEC
            // (depending on how we support DNSSEC).  We should revisit it
            // at that point.
            if (!domain->empty()) {
                isc_throw(AddError, "CNAME can't be added with other data for "
                          << rrset->getName());
            }
        } else if (domain->find(RRType::CNAME()) != domain->end()) {
            isc_throw(AddError, "CNAME and " << rrset->getType() <<
                      " can't coexist for " << rrset->getName());
        }

        /*
         * Similar with DNAME, but it must not coexist only with NS and only in
         * non-apex domains.
         * RFC 2672 section 3 mentions that it is implied from it and RFC 2181
         */
        if (rrset->getName() != origin_ &&
            // Adding DNAME, NS already there
            ((rrset->getType() == RRType::DNAME() &&
            domain->find(RRType::NS()) != domain->end()) ||
            // Adding NS, DNAME already there
            (rrset->getType() == RRType::NS() &&
            domain->find(RRType::DNAME()) != domain->end())))
        {
            isc_throw(AddError, "DNAME can't coexist with NS in non-apex "
                "domain " << rrset->getName());
        }
    }

159
160
    // Validate rrset before adding it to the zone.  If something is wrong
    // it throws an exception.  It doesn't modify the zone, and provides
JINMEI Tatuya's avatar
JINMEI Tatuya committed
161
    // the strong exception guarantee.
162
    void addValidation(const ConstRRsetPtr rrset) {
Michal Vaner's avatar
Michal Vaner committed
163
164
165
        if (!rrset) {
            isc_throw(NullRRset, "The rrset provided is NULL");
        }
166
167
        // Check for singleton RRs. It should probably handled at a different
        // in future.
168
169
170
171
172
173
        if ((rrset->getType() == RRType::CNAME() ||
            rrset->getType() == RRType::DNAME()) &&
            rrset->getRdataCount() > 1)
        {
            // XXX: this is not only for CNAME or DNAME. We should generalize
            // this code for all other "singleton RR types" (such as SOA) in a
174
175
176
177
178
            // separate task.
            isc_throw(AddError, "multiple RRs of singleton type for "
                      << rrset->getName());
        }

179
        NameComparisonResult compare(origin_.compare(rrset->getName()));
Michal Vaner's avatar
Michal Vaner committed
180
181
182
        if (compare.getRelation() != NameComparisonResult::SUPERDOMAIN &&
            compare.getRelation() != NameComparisonResult::EQUAL)
        {
183
            isc_throw(OutOfZone, "The name " << rrset->getName() <<
Michal Vaner's avatar
Michal Vaner committed
184
185
                " is not contained in zone " << origin_);
        }
186
187
188
189
190
191
192
193
194

        // Some RR types do not really work well with a wildcard.
        // Even though the protocol specifically doesn't completely ban such
        // usage, we refuse to load a zone containing such RR in order to
        // keep the lookup logic simpler and more predictable.
        // See RFC4592 and (for DNAME) draft-ietf-dnsext-rfc2672bis-dname
        // for more technical background.  Note also that BIND 9 refuses
        // NS at a wildcard, so in that sense we simply provide compatible
        // behavior.
195
        if (rrset->getName().isWildcard()) {
196
197
            if (rrset->getType() == RRType::NS()) {
                isc_throw(AddError, "Invalid NS owner name (wildcard): " <<
198
                          rrset->getName());
199
200
201
            }
            if (rrset->getType() == RRType::DNAME()) {
                isc_throw(AddError, "Invalid DNAME owner name (wildcard): " <<
202
                          rrset->getName());
203
204
            }
        }
205
206
207
208
209
210
211
212
213
214
    }

    /*
     * Implementation of longer methods. We put them here, because the
     * access is without the impl_-> and it will get inlined anyway.
     */
    // Implementation of MemoryZone::add
    result::Result add(const ConstRRsetPtr& rrset, DomainTree* domains) {
        // Sanitize input
        addValidation(rrset);
215
216
217

        // Add wildcards possibly contained in the owner name to the domain
        // tree.
218
219
        // Note: this can throw an exception, breaking strong exception
        // guarantee.  (see also the note for contextCheck() below).
220
        addWildcards(*domains, rrset->getName());
221

Michal Vaner's avatar
Michal Vaner committed
222
223
        // Get the node
        DomainNode* node;
224
225
226
227
        DomainTree::Result result = domains->insert(rrset->getName(), &node);
        // Just check it returns reasonable results
        assert((result == DomainTree::SUCCESS ||
                result == DomainTree::ALREADYEXISTS) && node!= NULL);
Michal Vaner's avatar
Michal Vaner committed
228
229
230
231
232
233
234
235
236
237
238

        // Now get the domain
        DomainPtr domain;
        // It didn't exist yet, create it
        if (node->isEmpty()) {
            domain.reset(new Domain);
            node->setData(domain);
        } else { // Get existing one
            domain = node->getData();
        }

239
        // Checks related to the surrounding data.
240
241
242
243
        // Note: when the check fails and the exception is thrown, it may
        // break strong exception guarantee.  At the moment we prefer
        // code simplicity and don't bother to introduce complicated
        // recovery code.
244
        contextCheck(rrset, domain);
245

Michal Vaner's avatar
Michal Vaner committed
246
247
248
        // Try inserting the rrset there
        if (domain->insert(DomainPair(rrset->getType(), rrset)).second) {
            // Ok, we just put it in
249
250
251
252
253

            // If this RRset creates a zone cut at this node, mark the node
            // indicating the need for callback in find().
            if (rrset->getType() == RRType::NS() &&
                rrset->getName() != origin_) {
254
                node->setFlag(DomainNode::FLAG_CALLBACK);
255
256
            // If it is DNAME, we have a callback as well here
            } else if (rrset->getType() == RRType::DNAME()) {
257
                node->setFlag(DomainNode::FLAG_CALLBACK);
258
259
            }

Michal Vaner's avatar
Michal Vaner committed
260
261
262
263
264
265
            return (result::SUCCESS);
        } else {
            // The RRSet of given type was already there
            return (result::EXIST);
        }
    }
Michal Vaner's avatar
Michal Vaner committed
266

267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
    /*
     * Same as above, but it checks the return value and if it already exists,
     * it throws.
     */
    void addFromLoad(const ConstRRsetPtr& set, DomainTree* domains) {
            switch (add(set, domains)) {
                case result::EXIST:
                    isc_throw(dns::MasterLoadError, "Duplicate rrset: " <<
                        set->toText());
                case result::SUCCESS:
                    return;
                default:
                    assert(0);
            }
    }

283
284
285
286
287
288
    // Maintain intermediate data specific to the search context used in
    /// \c find().
    ///
    /// It will be passed to \c zonecutCallback() and record a possible
    /// zone cut node and related RRset (normally NS or DNAME).
    struct FindState {
289
290
291
292
        FindState(FindOptions options) :
            zonecut_node_(NULL),
            dname_node_(NULL),
            options_(options)
293
294
        {}
        const DomainNode* zonecut_node_;
295
        const DomainNode* dname_node_;
296
297
        ConstRRsetPtr rrset_;
        const FindOptions options_;
298
299
    };

300
301
302
303
304
    // A callback called from possible zone cut nodes and nodes with DNAME.
    // This will be passed from the \c find() method to \c RBTree::find().
    static bool cutCallback(const DomainNode& 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,
305
306
        // the NS is authoritative, not delegation (corner case explicitly
        // allowed by section 3 of 2672)
307
308
309
310
311
        const Domain::const_iterator foundDNAME(node.getData()->find(
            RRType::DNAME()));
        if (foundDNAME != node.getData()->end()) {
            state->dname_node_ = &node;
            state->rrset_ = foundDNAME->second;
312
313
314
315
316
317
            // No more processing below the DNAME (RFC 2672, section 3
            // forbids anything to exist below it, so there's no need
            // to actually search for it). This is strictly speaking
            // a different way than described in 4.1 of that RFC,
            // but because of the assumption in section 3, it has the
            // same behaviour.
318
            return (true);
319
320
        }

321
322
323
324
        // Look for NS
        const Domain::const_iterator foundNS(node.getData()->find(
            RRType::NS()));
        if (foundNS != node.getData()->end()) {
325
326
327
328
329
330
            // 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);
            }

331
332
333
334
335
336
            // 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.
337
            state->zonecut_node_ = &node;
338
            state->rrset_ = foundNS->second;
339
340
341
342

            // Unless glue is allowed the search stops here, so we return
            // false; otherwise return true to continue the search.
            return ((state->options_ & FIND_GLUE_OK) == 0);
343
344
        }

JINMEI Tatuya's avatar
JINMEI Tatuya committed
345
346
347
        // This case should not happen because we enable callback only
        // when we add an RR searched for above.
        assert(0);
348
349
350
        // 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".
351
        return (false);
352
353
    }

chenzhengzhang's avatar
chenzhengzhang committed
354

Michal Vaner's avatar
Michal Vaner committed
355
    // Implementation of MemoryZone::find
356
    FindResult find(const Name& name, RRType type,
357
                    RRsetList* target, const FindOptions options) const
358
    {
Michal Vaner's avatar
Michal Vaner committed
359
        // Get the node
Michal Vaner's avatar
Michal Vaner committed
360
        DomainNode* node(NULL);
361
        FindState state(options);
362
        switch (domains_.find(name, &node, cutCallback, &state)) {
Michal Vaner's avatar
Michal Vaner committed
363
            case DomainTree::PARTIALMATCH:
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
                /*
                 * In fact, we could use a single variable instead of
                 * dname_node_ and zonecut_node_. But then we would need
                 * to distinquish these two cases by something else and
                 * it seemed little more confusing to me when I wrote it.
                 *
                 * 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
379
                 * all other cases it doesn't matter, as at least one of them
380
381
                 * is NULL.
                 */
382
383
384
385
386
                if (state.dname_node_ != NULL) {
                    // We were traversing a DNAME node (and wanted to go
                    // lower below it), so return the DNAME
                    return (FindResult(DNAME, state.rrset_));
                }
387
388
                if (state.zonecut_node_ != NULL) {
                    return (FindResult(DELEGATION, state.rrset_));
389
390
391
392
393
                }
                // TODO: we should also cover empty non-terminal cases, which
                // will require non trivial code and is deferred for later
                // development.  For now, we regard any partial match that
                // didn't hit a zone cut as "not found".
Michal Vaner's avatar
Michal Vaner committed
394
395
396
397
398
399
            case DomainTree::NOTFOUND:
                return (FindResult(NXDOMAIN, ConstRRsetPtr()));
            case DomainTree::EXACTMATCH: // This one is OK, handle it
                break;
            default:
                assert(0);
Michal Vaner's avatar
Michal Vaner committed
400
        }
Michal Vaner's avatar
Michal Vaner committed
401
        assert(node);
402
403
404
405
406
407

        // If there is an exact match but the node is empty, it's equivalent
        // to NXRRSET.
        if (node->isEmpty()) {
            return (FindResult(NXRRSET, ConstRRsetPtr()));
        }
Michal Vaner's avatar
Michal Vaner committed
408

409
410
411
        Domain::const_iterator found;

        // If the node callback is enabled, this may be a zone cut.  If it
412
        // has a NS RR, we should return a delegation, but not in the apex.
413
        if (node->getFlag(DomainNode::FLAG_CALLBACK) && node != origin_data_) {
414
415
416
417
418
419
            found = node->getData()->find(RRType::NS());
            if (found != node->getData()->end()) {
                return (FindResult(DELEGATION, found->second));
            }
        }

chenzhengzhang's avatar
chenzhengzhang committed
420
        // handle type any query
421
        if (target != NULL && !node->getData()->empty()) {
422
423
424
425
426
427
            // Empty domain will be handled as NXRRSET by normal processing
            for (found = node->getData()->begin();
                 found != node->getData()->end(); found++)
            {
                target->addRRset(
                    boost::const_pointer_cast<RRset>(found->second));
chenzhengzhang's avatar
chenzhengzhang committed
428
            }
429
            return (FindResult(SUCCESS, ConstRRsetPtr()));
chenzhengzhang's avatar
chenzhengzhang committed
430
431
        }

432
        found = node->getData()->find(type);
Michal Vaner's avatar
Michal Vaner committed
433
434
435
436
        if (found != node->getData()->end()) {
            // Good, it is here
            return (FindResult(SUCCESS, found->second));
        } else {
437
            // Next, try CNAME.
438
439
440
441
            found = node->getData()->find(RRType::CNAME());
            if (found != node->getData()->end()) {
                return (FindResult(CNAME, found->second));
            }
Michal Vaner's avatar
Michal Vaner committed
442
        }
443
444
        // No exact match or CNAME.  Return NXRRSET.
        return (FindResult(NXRRSET, ConstRRsetPtr()));
Michal Vaner's avatar
Michal Vaner committed
445
    }
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
};

MemoryZone::MemoryZone(const RRClass& zone_class, const Name& origin) :
    impl_(new MemoryZoneImpl(zone_class, origin))
{
}

MemoryZone::~MemoryZone() {
    delete impl_;
}

const Name&
MemoryZone::getOrigin() const {
    return (impl_->origin_);
}

const RRClass&
MemoryZone::getClass() const {
    return (impl_->zone_class_);
}

Zone::FindResult
468
MemoryZone::find(const Name& name, const RRType& type,
469
                 RRsetList* target, const FindOptions options) const
chenzhengzhang's avatar
chenzhengzhang committed
470
{
471
    return (impl_->find(name, type, target, options));
chenzhengzhang's avatar
chenzhengzhang committed
472
473
}

Michal Vaner's avatar
Michal Vaner committed
474
475
result::Result
MemoryZone::add(const ConstRRsetPtr& rrset) {
476
    return (impl_->add(rrset, &impl_->domains_));
477
478
}

Michal Vaner's avatar
Michal Vaner committed
479
480
481

void
MemoryZone::load(const string& filename) {
482
483
484
485
486
    // Load it into a temporary tree
    MemoryZoneImpl::DomainTree tmp;
    masterLoad(filename.c_str(), getOrigin(), getClass(),
        boost::bind(&MemoryZoneImpl::addFromLoad, impl_, _1, &tmp));
    // If it went well, put it inside
487
    impl_->file_name_ = filename;
488
489
    tmp.swap(impl_->domains_);
    // And let the old data die with tmp
490
491
}

492
493
494
495
496
497
498
499
500
501
void
MemoryZone::swap(MemoryZone& zone) {
    std::swap(impl_, zone.impl_);
}

const string
MemoryZone::getFileName() const {
    return (impl_->file_name_);
}

502
503
504
505
506
507
/// Implementation details for \c MemoryDataSrc hidden from the public
/// interface.
///
/// For now, \c MemoryDataSrc only contains a \c ZoneTable object, which
/// consists of (pointers to) \c MemoryZone objects, we may add more
/// member variables later for new features.
508
509
510
511
class MemoryDataSrc::MemoryDataSrcImpl {
public:
    MemoryDataSrcImpl() : zone_count(0) {}
    unsigned int zone_count;
512
513
514
515
516
517
518
519
520
521
    ZoneTable zone_table;
};

MemoryDataSrc::MemoryDataSrc() : impl_(new MemoryDataSrcImpl)
{}

MemoryDataSrc::~MemoryDataSrc() {
    delete impl_;
}

522
523
524
525
526
unsigned int
MemoryDataSrc::getZoneCount() const {
    return (impl_->zone_count);
}

527
528
529
530
531
532
result::Result
MemoryDataSrc::addZone(ZonePtr zone) {
    if (!zone) {
        isc_throw(InvalidParameter,
                  "Null pointer is passed to MemoryDataSrc::addZone()");
    }
533
534
535
536
537
538

    const result::Result result = impl_->zone_table.addZone(zone);
    if (result == result::SUCCESS) {
        ++impl_->zone_count;
    }
    return (result);
539
540
541
542
543
544
545
546
547
}

MemoryDataSrc::FindResult
MemoryDataSrc::findZone(const isc::dns::Name& name) const {
    return (FindResult(impl_->zone_table.findZone(name).code,
                       impl_->zone_table.findZone(name).zone));
}
} // end of namespace datasrc
} // end of namespace dns