memory_datasrc.cc 20.6 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
65
66
67
68
69
70

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

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

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
106
107
108
109
110
111
112
113
    // 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);

                // Ensure a separate level exists for the "wildcarding" name
                result = domains.insert(wname, &node);
                assert(result == DomainTree::SUCCESS ||
                       result == DomainTree::ALREADYEXISTS);
            }
        }
    }

114
115
116
117
118
119
120
    /*
     * 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.
     */
121
122
    void contextCheck(const ConstRRsetPtr& rrset,
                      const DomainPtr& domain) const {
123
124
125
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
        // 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());
        }
    }

156
157
158
159
    // Validate rrset before adding it to the zone.  If something is wrong
    // it throws an exception.  It doesn't modify the zone, and provides
    // the strong exception guarantee. 
    void addValidation(const ConstRRsetPtr rrset) {
Michal Vaner's avatar
Michal Vaner committed
160
161
162
        if (!rrset) {
            isc_throw(NullRRset, "The rrset provided is NULL");
        }
163
164
        // Check for singleton RRs. It should probably handled at a different
        // in future.
165
166
167
168
169
170
        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
171
172
173
174
175
            // separate task.
            isc_throw(AddError, "multiple RRs of singleton type for "
                      << rrset->getName());
        }

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

        // 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.
192
        if (rrset->getName().isWildcard()) {
193
194
            if (rrset->getType() == RRType::NS()) {
                isc_throw(AddError, "Invalid NS owner name (wildcard): " <<
195
                          rrset->getName());
196
197
198
            }
            if (rrset->getType() == RRType::DNAME()) {
                isc_throw(AddError, "Invalid DNAME owner name (wildcard): " <<
199
                          rrset->getName());
200
201
            }
        }
202
203
204
205
206
207
208
209
210
211
    }

    /*
     * 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);
212
213
214

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

Michal Vaner's avatar
Michal Vaner committed
219
220
        // Get the node
        DomainNode* node;
221
222
223
224
        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
225
226
227
228
229
230
231
232
233
234
235

        // 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();
        }

236
        // Checks related to the surrounding data.
237
238
239
240
        // 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.
241
        contextCheck(rrset, domain);
242

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

            // 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_) {
251
                node->setFlag(DomainNode::FLAG_CALLBACK);
252
253
            // If it is DNAME, we have a callback as well here
            } else if (rrset->getType() == RRType::DNAME()) {
254
                node->setFlag(DomainNode::FLAG_CALLBACK);
255
256
            }

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

264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
    /*
     * 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);
            }
    }

280
281
282
283
284
285
    // 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 {
286
287
288
289
        FindState(FindOptions options) :
            zonecut_node_(NULL),
            dname_node_(NULL),
            options_(options)
290
291
        {}
        const DomainNode* zonecut_node_;
292
        const DomainNode* dname_node_;
293
294
        ConstRRsetPtr rrset_;
        const FindOptions options_;
295
296
    };

297
298
299
300
301
    // 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,
302
303
        // the NS is authoritative, not delegation (corner case explicitly
        // allowed by section 3 of 2672)
304
305
306
307
308
        const Domain::const_iterator foundDNAME(node.getData()->find(
            RRType::DNAME()));
        if (foundDNAME != node.getData()->end()) {
            state->dname_node_ = &node;
            state->rrset_ = foundDNAME->second;
309
310
311
312
313
314
            // 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.
315
            return (true);
316
317
        }

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

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

            // 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);
340
341
        }

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

chenzhengzhang's avatar
chenzhengzhang committed
351

Michal Vaner's avatar
Michal Vaner committed
352
    // Implementation of MemoryZone::find
353
    FindResult find(const Name& name, RRType type,
354
                    RRsetList* target, const FindOptions options) const
355
    {
Michal Vaner's avatar
Michal Vaner committed
356
        // Get the node
Michal Vaner's avatar
Michal Vaner committed
357
        DomainNode* node(NULL);
358
        FindState state(options);
359
        switch (domains_.find(name, &node, cutCallback, &state)) {
Michal Vaner's avatar
Michal Vaner committed
360
            case DomainTree::PARTIALMATCH:
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
                /*
                 * 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
376
                 * all other cases it doesn't matter, as at least one of them
377
378
                 * is NULL.
                 */
379
380
381
382
383
                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_));
                }
384
385
                if (state.zonecut_node_ != NULL) {
                    return (FindResult(DELEGATION, state.rrset_));
386
387
388
389
390
                }
                // 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
391
392
393
394
395
396
            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
397
        }
Michal Vaner's avatar
Michal Vaner committed
398
        assert(node);
399
400
401
402
403
404

        // 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
405

406
407
408
        Domain::const_iterator found;

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

chenzhengzhang's avatar
chenzhengzhang committed
417
        // handle type any query
418
        if (target != NULL && !node->getData()->empty()) {
419
420
421
422
423
424
            // 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
425
            }
426
            return (FindResult(SUCCESS, ConstRRsetPtr()));
chenzhengzhang's avatar
chenzhengzhang committed
427
428
        }

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

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
465
MemoryZone::find(const Name& name, const RRType& type,
466
                 RRsetList* target, const FindOptions options) const
chenzhengzhang's avatar
chenzhengzhang committed
467
{
468
    return (impl_->find(name, type, target, options));
chenzhengzhang's avatar
chenzhengzhang committed
469
470
}

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

Michal Vaner's avatar
Michal Vaner committed
476
477
478

void
MemoryZone::load(const string& filename) {
479
480
481
482
483
    // 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
484
    impl_->file_name_ = filename;
485
486
    tmp.swap(impl_->domains_);
    // And let the old data die with tmp
487
488
}

489
490
491
492
493
494
495
496
497
498
void
MemoryZone::swap(MemoryZone& zone) {
    std::swap(impl_, zone.impl_);
}

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

499
500
501
502
503
504
/// 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.
505
506
507
508
class MemoryDataSrc::MemoryDataSrcImpl {
public:
    MemoryDataSrcImpl() : zone_count(0) {}
    unsigned int zone_count;
509
510
511
512
513
514
515
516
517
518
    ZoneTable zone_table;
};

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

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

519
520
521
522
523
unsigned int
MemoryDataSrc::getZoneCount() const {
    return (impl_->zone_count);
}

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

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

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