memory_datasrc.cc 21 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
        domains_(true)
40 41 42 43 44 45
    {
        // 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
46 47 48 49 50

    // Some type aliases
    /*
     * Each domain consists of some RRsets. They will be looked up by the
     * RRType.
51 52 53 54 55 56 57
     *
     * 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
58
     */
Michal Vaner's avatar
Michal Vaner committed
59
    typedef map<RRType, ConstRRsetPtr> Domain;
Michal Vaner's avatar
Michal Vaner committed
60
    typedef Domain::value_type DomainPair;
Michal Vaner's avatar
Michal Vaner committed
61
    typedef boost::shared_ptr<Domain> DomainPtr;
Michal Vaner's avatar
Michal Vaner committed
62
    // The tree stores domains
Michal Vaner's avatar
Michal Vaner committed
63 64
    typedef RBTree<Domain> DomainTree;
    typedef RBNode<Domain> DomainNode;
65
    static const DomainNode::Flags DOMAINFLAG_WILD = DomainNode::FLAG_USER1;
66 67 68 69 70 71 72

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

Michal Vaner's avatar
Michal Vaner committed
73
    // The actual zone data
Michal Vaner's avatar
Michal Vaner committed
74
    DomainTree domains_;
Michal Vaner's avatar
Michal Vaner committed
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
    // 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()) {
                // 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.
101 102 103
                DomainNode* node;
                DomainTree::Result result(domains.insert(wname.split(1),
                                                         &node));
104 105 106
                assert(result == DomainTree::SUCCESS ||
                       result == DomainTree::ALREADYEXISTS);

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

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
        RBTreeNodeChain<Domain> node_path;
363
        switch (domains_.find(name, &node, node_path, cutCallback, &state)) {
Michal Vaner's avatar
Michal Vaner committed
364
            case DomainTree::PARTIALMATCH:
365 366 367 368 369 370 371 372 373 374 375 376 377 378 379
                /*
                 * 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
380
                 * all other cases it doesn't matter, as at least one of them
381 382
                 * is NULL.
                 */
383 384 385 386 387
                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_));
                }
388 389
                if (state.zonecut_node_ != NULL) {
                    return (FindResult(DELEGATION, state.rrset_));
390
                }
391 392 393 394 395 396 397 398 399 400

                // If the RBTree search stopped at a node for a super domain
                // of the search name, it means the search name exists in
                // the zone but is empty.  Treat it as NXRRSET.
                if (node_path.getLastComparisonResult().getRelation() ==
                    NameComparisonResult::SUPERDOMAIN) {
                    return (FindResult(NXRRSET, ConstRRsetPtr()));
                }

                // fall through
Michal Vaner's avatar
Michal Vaner committed
401 402 403 404 405 406
            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
407
        }
408
        assert(node != NULL);
409 410 411 412 413 414

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

416 417 418
        Domain::const_iterator found;

        // If the node callback is enabled, this may be a zone cut.  If it
419
        // has a NS RR, we should return a delegation, but not in the apex.
420
        if (node->getFlag(DomainNode::FLAG_CALLBACK) && node != origin_data_) {
421 422 423 424 425 426
            found = node->getData()->find(RRType::NS());
            if (found != node->getData()->end()) {
                return (FindResult(DELEGATION, found->second));
            }
        }

chenzhengzhang's avatar
chenzhengzhang committed
427
        // handle type any query
428
        if (target != NULL && !node->getData()->empty()) {
429 430 431 432 433 434
            // 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
435
            }
436
            return (FindResult(SUCCESS, ConstRRsetPtr()));
chenzhengzhang's avatar
chenzhengzhang committed
437 438
        }

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

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
475
MemoryZone::find(const Name& name, const RRType& type,
476
                 RRsetList* target, const FindOptions options) const
chenzhengzhang's avatar
chenzhengzhang committed
477
{
478
    return (impl_->find(name, type, target, options));
chenzhengzhang's avatar
chenzhengzhang committed
479 480
}

Michal Vaner's avatar
Michal Vaner committed
481 482
result::Result
MemoryZone::add(const ConstRRsetPtr& rrset) {
483
    return (impl_->add(rrset, &impl_->domains_));
484 485
}

Michal Vaner's avatar
Michal Vaner committed
486 487 488

void
MemoryZone::load(const string& filename) {
489 490 491 492 493
    // 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
494
    impl_->file_name_ = filename;
495 496
    tmp.swap(impl_->domains_);
    // And let the old data die with tmp
497 498
}

499 500 501 502 503 504 505 506 507 508
void
MemoryZone::swap(MemoryZone& zone) {
    std::swap(impl_, zone.impl_);
}

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

509 510 511 512 513 514
/// 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.
515 516 517 518
class MemoryDataSrc::MemoryDataSrcImpl {
public:
    MemoryDataSrcImpl() : zone_count(0) {}
    unsigned int zone_count;
519 520 521 522 523 524 525 526 527 528
    ZoneTable zone_table;
};

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

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

529 530 531 532 533
unsigned int
MemoryDataSrc::getZoneCount() const {
    return (impl_->zone_count);
}

534 535 536 537 538 539
result::Result
MemoryDataSrc::addZone(ZonePtr zone) {
    if (!zone) {
        isc_throw(InvalidParameter,
                  "Null pointer is passed to MemoryDataSrc::addZone()");
    }
540 541 542 543 544 545

    const result::Result result = impl_->zone_table.addZone(zone);
    if (result == result::SUCCESS) {
        ++impl_->zone_count;
    }
    return (result);
546 547 548 549 550 551 552 553 554
}

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