memory_datasrc.cc 20.2 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());
        }
    }

Michal Vaner's avatar
Michal Vaner committed
156
157
158
159
    /*
     * Implementation of longer methods. We put them here, because the
     * access is without the impl_-> and it will get inlined anyway.
     */
Michal Vaner's avatar
Michal Vaner committed
160
    // Implementation of MemoryZone::add
Michal Vaner's avatar
Michal Vaner committed
161
    result::Result add(const ConstRRsetPtr& rrset, DomainTree* domains) {
Michal Vaner's avatar
Michal Vaner committed
162
163
164
165
        // Sanitize input
        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());
        }

Michal Vaner's avatar
Michal Vaner committed
179
180
181
182
183
184
185
186
        Name name(rrset->getName());
        NameComparisonResult compare(origin_.compare(name));
        if (compare.getRelation() != NameComparisonResult::SUPERDOMAIN &&
            compare.getRelation() != NameComparisonResult::EQUAL)
        {
            isc_throw(OutOfZone, "The name " << name <<
                " is not contained in zone " << origin_);
        }
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210

        // 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.
        if (name.isWildcard()) {
            if (rrset->getType() == RRType::NS()) {
                isc_throw(AddError, "Invalid NS owner name (wildcard): " <<
                          name);
            }
            if (rrset->getType() == RRType::DNAME()) {
                isc_throw(AddError, "Invalid DNAME owner name (wildcard): " <<
                          name);
            }
        }

        // Add wildcards possibly contained in the owner name to the domain
        // tree.
        addWildcards(*domains, name);

Michal Vaner's avatar
Michal Vaner committed
211
212
        // Get the node
        DomainNode* node;
213
        switch (domains->insert(name, &node)) {
Michal Vaner's avatar
Michal Vaner committed
214
            // Just check it returns reasonable results
Michal Vaner's avatar
Michal Vaner committed
215
216
            case DomainTree::SUCCESS:
            case DomainTree::ALREADYEXISTS:
Michal Vaner's avatar
Michal Vaner committed
217
218
219
                break;
            // Something odd got out
            default:
Michal Vaner's avatar
Michal Vaner committed
220
                assert(0);
Michal Vaner's avatar
Michal Vaner committed
221
        }
222
        assert(node != NULL);
Michal Vaner's avatar
Michal Vaner committed
223
224
225
226
227
228
229
230
231
232
233

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

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

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

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

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

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

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

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

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

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

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

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

chenzhengzhang's avatar
chenzhengzhang committed
349

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

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

404
405
406
        Domain::const_iterator found;

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

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

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

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

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

Michal Vaner's avatar
Michal Vaner committed
474
475
476

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

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

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

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

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

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

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

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

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

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