memory_datasrc.cc 15.9 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
    {}
Michal Vaner's avatar
Michal Vaner committed
40
41
42
43
44

    // Some type aliases
    /*
     * Each domain consists of some RRsets. They will be looked up by the
     * RRType.
45
46
47
48
49
50
51
     *
     * 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
52
     */
Michal Vaner's avatar
Michal Vaner committed
53
    typedef map<RRType, ConstRRsetPtr> Domain;
Michal Vaner's avatar
Michal Vaner committed
54
    typedef Domain::value_type DomainPair;
Michal Vaner's avatar
Michal Vaner committed
55
    typedef boost::shared_ptr<Domain> DomainPtr;
Michal Vaner's avatar
Michal Vaner committed
56
    // The tree stores domains
Michal Vaner's avatar
Michal Vaner committed
57
58
    typedef RBTree<Domain> DomainTree;
    typedef RBNode<Domain> DomainNode;
59
60
61
62
63
64
65

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

Michal Vaner's avatar
Michal Vaner committed
66
    // The actual zone data
Michal Vaner's avatar
Michal Vaner committed
67
    DomainTree domains_;
Michal Vaner's avatar
Michal Vaner committed
68

69
70
71
72
73
74
75
    /*
     * 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.
     */
76
77
    void contextCheck(const ConstRRsetPtr& rrset,
                      const DomainPtr& domain) const {
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
        // 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
111
112
113
114
    /*
     * 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
115
    // Implementation of MemoryZone::add
Michal Vaner's avatar
Michal Vaner committed
116
    result::Result add(const ConstRRsetPtr& rrset, DomainTree* domains) {
Michal Vaner's avatar
Michal Vaner committed
117
118
119
120
        // Sanitize input
        if (!rrset) {
            isc_throw(NullRRset, "The rrset provided is NULL");
        }
121
122
        // Check for singleton RRs. It should probably handled at a different
        // in future.
123
124
125
126
127
128
        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
129
130
131
132
133
            // separate task.
            isc_throw(AddError, "multiple RRs of singleton type for "
                      << rrset->getName());
        }

Michal Vaner's avatar
Michal Vaner committed
134
135
136
137
138
139
140
141
        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_);
        }
Michal Vaner's avatar
Michal Vaner committed
142
143
        // Get the node
        DomainNode* node;
144
        switch (domains->insert(name, &node)) {
Michal Vaner's avatar
Michal Vaner committed
145
            // Just check it returns reasonable results
Michal Vaner's avatar
Michal Vaner committed
146
147
            case DomainTree::SUCCESS:
            case DomainTree::ALREADYEXISTS:
Michal Vaner's avatar
Michal Vaner committed
148
149
150
                break;
            // Something odd got out
            default:
Michal Vaner's avatar
Michal Vaner committed
151
                assert(0);
Michal Vaner's avatar
Michal Vaner committed
152
        }
153
        assert(node != NULL);
Michal Vaner's avatar
Michal Vaner committed
154
155
156
157
158
159
160

        // Now get the domain
        DomainPtr domain;
        // It didn't exist yet, create it
        if (node->isEmpty()) {
            domain.reset(new Domain);
            node->setData(domain);
161
162
163
            if (origin_data_ == NULL && name == origin_) {
                origin_data_ = node;
            }
Michal Vaner's avatar
Michal Vaner committed
164
165
166
167
        } else { // Get existing one
            domain = node->getData();
        }

168
169
170
171
172
        // Checks related to the surrounding data.
        // 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.
173
        contextCheck(rrset, domain);
174

Michal Vaner's avatar
Michal Vaner committed
175
176
177
        // Try inserting the rrset there
        if (domain->insert(DomainPair(rrset->getType(), rrset)).second) {
            // Ok, we just put it in
178
179
180
181
182
183

            // 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();
184
185
186
            // If it is DNAME, we have a callback as well here
            } else if (rrset->getType() == RRType::DNAME()) {
                node->enableCallback();
187
188
            }

Michal Vaner's avatar
Michal Vaner committed
189
190
191
192
193
194
            return (result::SUCCESS);
        } else {
            // The RRSet of given type was already there
            return (result::EXIST);
        }
    }
Michal Vaner's avatar
Michal Vaner committed
195

196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
    /*
     * 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);
            }
    }

212
213
214
215
216
217
    // 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 {
218
219
220
221
        FindState(FindOptions options) :
            zonecut_node_(NULL),
            dname_node_(NULL),
            options_(options)
222
223
        {}
        const DomainNode* zonecut_node_;
224
        const DomainNode* dname_node_;
225
226
        ConstRRsetPtr rrset_;
        const FindOptions options_;
227
228
    };

229
230
231
    // 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) {
232
233
        // We perform callback check only for the highest zone cut in the
        // rare case of nested zone cuts.
234
        if (state->zonecut_node_ != NULL) {
235
236
237
            return (false);
        }

238
239
        // 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,
240
241
        // the NS is authoritative, not delegation (corner case explicitly
        // allowed by section 3 of 2672)
242
243
244
245
246
        const Domain::const_iterator foundDNAME(node.getData()->find(
            RRType::DNAME()));
        if (foundDNAME != node.getData()->end()) {
            state->dname_node_ = &node;
            state->rrset_ = foundDNAME->second;
247
248
249
250
251
252
            // 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.
253
            return (true);
254
255
256
257
258
259
        }

        // Look for NS
        const Domain::const_iterator foundNS(node.getData()->find(
            RRType::NS()));
        if (foundNS != node.getData()->end()) {
260
261
262
263
264
265
            // 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.
266
            state->zonecut_node_ = &node;
267
            state->rrset_ = foundNS->second;
268
269
270
271

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

JINMEI Tatuya's avatar
JINMEI Tatuya committed
274
275
276
        // This case should not happen because we enable callback only
        // when we add an RR searched for above.
        assert(0);
277
278
279
        // 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".
280
        return (false);
281
282
    }

chenzhengzhang's avatar
chenzhengzhang committed
283

Michal Vaner's avatar
Michal Vaner committed
284
    // Implementation of MemoryZone::find
285
    FindResult find(const Name& name, RRType type,
286
                    RRsetList* target, const FindOptions options) const
287
    {
Michal Vaner's avatar
Michal Vaner committed
288
        // Get the node
Michal Vaner's avatar
Michal Vaner committed
289
        DomainNode* node(NULL);
290
        FindState state(options);
291
        switch (domains_.find(name, &node, cutCallback, &state)) {
Michal Vaner's avatar
Michal Vaner committed
292
            case DomainTree::PARTIALMATCH:
293
294
295
296
297
                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_));
                }
298
299
                if (state.zonecut_node_ != NULL) {
                    return (FindResult(DELEGATION, state.rrset_));
300
301
302
303
304
                }
                // 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
305
306
307
308
309
310
            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
311
        }
Michal Vaner's avatar
Michal Vaner committed
312
313
314
        assert(node);
        assert(!node->isEmpty());

315
316
317
        Domain::const_iterator found;

        // If the node callback is enabled, this may be a zone cut.  If it
318
        // has a NS RR, we should return a delegation, but not in the apex.
319
        if (node->isCallbackEnabled() && node != origin_data_) {
320
321
322
323
324
325
            found = node->getData()->find(RRType::NS());
            if (found != node->getData()->end()) {
                return (FindResult(DELEGATION, found->second));
            }
        }

chenzhengzhang's avatar
chenzhengzhang committed
326
        // handle type any query
327
328
329
330
331
332
333
        if (target && !node->getData()->empty()) {
            // 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
334
            }
335
            return (FindResult(SUCCESS, ConstRRsetPtr()));
chenzhengzhang's avatar
chenzhengzhang committed
336
337
        }

338
        found = node->getData()->find(type);
Michal Vaner's avatar
Michal Vaner committed
339
340
341
342
        if (found != node->getData()->end()) {
            // Good, it is here
            return (FindResult(SUCCESS, found->second));
        } else {
343
            // Next, try CNAME.
344
345
346
347
            found = node->getData()->find(RRType::CNAME());
            if (found != node->getData()->end()) {
                return (FindResult(CNAME, found->second));
            }
Michal Vaner's avatar
Michal Vaner committed
348
        }
349
350
        // No exact match or CNAME.  Return NXRRSET.
        return (FindResult(NXRRSET, ConstRRsetPtr()));
Michal Vaner's avatar
Michal Vaner committed
351
    }
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
};

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
374
MemoryZone::find(const Name& name, const RRType& type,
375
                 RRsetList* target, const FindOptions options) const
chenzhengzhang's avatar
chenzhengzhang committed
376
{
377
    return (impl_->find(name, type, target, options));
chenzhengzhang's avatar
chenzhengzhang committed
378
379
}

Michal Vaner's avatar
Michal Vaner committed
380
381
result::Result
MemoryZone::add(const ConstRRsetPtr& rrset) {
382
    return (impl_->add(rrset, &impl_->domains_));
383
384
}

Michal Vaner's avatar
Michal Vaner committed
385
386
387

void
MemoryZone::load(const string& filename) {
388
389
390
391
392
    // 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
393
    impl_->file_name_ = filename;
394
395
    tmp.swap(impl_->domains_);
    // And let the old data die with tmp
396
397
}

398
399
400
401
402
403
404
405
406
407
void
MemoryZone::swap(MemoryZone& zone) {
    std::swap(impl_, zone.impl_);
}

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

408
409
410
411
412
413
/// 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.
414
415
416
417
class MemoryDataSrc::MemoryDataSrcImpl {
public:
    MemoryDataSrcImpl() : zone_count(0) {}
    unsigned int zone_count;
418
419
420
421
422
423
424
425
426
427
    ZoneTable zone_table;
};

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

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

428
429
430
431
432
unsigned int
MemoryDataSrc::getZoneCount() const {
    return (impl_->zone_count);
}

433
434
435
436
437
438
result::Result
MemoryDataSrc::addZone(ZonePtr zone) {
    if (!zone) {
        isc_throw(InvalidParameter,
                  "Null pointer is passed to MemoryDataSrc::addZone()");
    }
439
440
441
442
443
444

    const result::Result result = impl_->zone_table.addZone(zone);
    if (result == result::SUCCESS) {
        ++impl_->zone_count;
    }
    return (result);
445
446
447
448
449
450
451
452
453
}

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