memory_datasrc.cc 42.4 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>
19
#include <boost/foreach.hpp>
Michal Vaner's avatar
Michal Vaner committed
20

21 22
#include <exceptions/exceptions.h>

23
#include <dns/name.h>
24
#include <dns/rdataclass.h>
25
#include <dns/rrclass.h>
chenzhengzhang's avatar
chenzhengzhang committed
26
#include <dns/rrsetlist.h>
Michal Vaner's avatar
Michal Vaner committed
27
#include <dns/masterload.h>
28

29
#include <datasrc/memory_datasrc.h>
Michal Vaner's avatar
Michal Vaner committed
30
#include <datasrc/rbtree.h>
31
#include <datasrc/logger.h>
32 33
#include <datasrc/iterator.h>
#include <datasrc/data_source.h>
34 35 36
#include <datasrc/factory.h>

#include <cc/data.h>
37 38 39

using namespace std;
using namespace isc::dns;
40
using namespace isc::dns::rdata;
41
using namespace isc::data;
42 43 44 45

namespace isc {
namespace datasrc {

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

67 68
// Private data and hidden methods of InMemoryZoneFinder
struct InMemoryZoneFinder::InMemoryZoneFinderImpl {
Michal Vaner's avatar
Michal Vaner committed
69
    // Constructor
70
    InMemoryZoneFinderImpl(const RRClass& zone_class, const Name& origin) :
71
        zone_class_(zone_class), origin_(origin), origin_data_(NULL),
72
        domains_(true)
73 74 75 76 77 78
    {
        // 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);
    }
79
    static const DomainNode::Flags DOMAINFLAG_WILD = DomainNode::FLAG_USER1;
80 81 82 83 84 85 86

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

Michal Vaner's avatar
Michal Vaner committed
87
    // The actual zone data
Michal Vaner's avatar
Michal Vaner committed
88
    DomainTree domains_;
Michal Vaner's avatar
Michal Vaner committed
89

90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
    // 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()) {
111
                LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_ADD_WILDCARD).
112
                    arg(name);
113 114
                // Ensure a separate level exists for the "wildcarding" name,
                // and mark the node as "wild".
115 116 117
                DomainNode* node;
                DomainTree::Result result(domains.insert(wname.split(1),
                                                         &node));
118 119
                assert(result == DomainTree::SUCCESS ||
                       result == DomainTree::ALREADYEXISTS);
120
                node->setFlag(DOMAINFLAG_WILD);
121

122 123 124 125
                // 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.
126 127 128 129 130 131 132
                result = domains.insert(wname, &node);
                assert(result == DomainTree::SUCCESS ||
                       result == DomainTree::ALREADYEXISTS);
            }
        }
    }

133 134 135 136 137 138 139
    /*
     * 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.
     */
140 141
    void contextCheck(const ConstRRsetPtr& rrset,
                      const DomainPtr& domain) const {
142 143 144
        // Ensure CNAME and other type of RR don't coexist for the same
        // owner name.
        if (rrset->getType() == RRType::CNAME()) {
145
            // TODO: this check will become incorrect when we support DNSSEC
146 147 148
            // (depending on how we support DNSSEC).  We should revisit it
            // at that point.
            if (!domain->empty()) {
149
                LOG_ERROR(logger, DATASRC_MEM_CNAME_TO_NONEMPTY).
150
                    arg(rrset->getName());
151 152 153 154
                isc_throw(AddError, "CNAME can't be added with other data for "
                          << rrset->getName());
            }
        } else if (domain->find(RRType::CNAME()) != domain->end()) {
155
            LOG_ERROR(logger, DATASRC_MEM_CNAME_COEXIST).arg(rrset->getName());
156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172
            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())))
        {
173
            LOG_ERROR(logger, DATASRC_MEM_DNAME_NS).arg(rrset->getName());
174 175 176 177 178
            isc_throw(AddError, "DNAME can't coexist with NS in non-apex "
                "domain " << rrset->getName());
        }
    }

179 180
    // 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
181
    // the strong exception guarantee.
182
    void addValidation(const ConstRRsetPtr rrset) {
Michal Vaner's avatar
Michal Vaner committed
183 184 185
        if (!rrset) {
            isc_throw(NullRRset, "The rrset provided is NULL");
        }
186 187 188 189
        if (rrset->getRdataCount() == 0) {
            isc_throw(AddError, "The rrset provided is empty: " <<
                      rrset->getName() << "/" << rrset->getType());
        }
190
        // Check for singleton RRs. It should probably handled at a different
191
        // layer in future.
192 193 194 195 196 197
        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
198
            // separate task.
199
            LOG_ERROR(logger, DATASRC_MEM_SINGLETON).arg(rrset->getName()).
200
                arg(rrset->getType());
201 202 203 204
            isc_throw(AddError, "multiple RRs of singleton type for "
                      << rrset->getName());
        }

205
        NameComparisonResult compare(origin_.compare(rrset->getName()));
Michal Vaner's avatar
Michal Vaner committed
206 207 208
        if (compare.getRelation() != NameComparisonResult::SUPERDOMAIN &&
            compare.getRelation() != NameComparisonResult::EQUAL)
        {
209
            LOG_ERROR(logger, DATASRC_MEM_OUT_OF_ZONE).arg(rrset->getName()).
210
                arg(origin_);
211
            isc_throw(OutOfZone, "The name " << rrset->getName() <<
Michal Vaner's avatar
Michal Vaner committed
212 213
                " is not contained in zone " << origin_);
        }
214 215 216 217 218 219 220 221 222

        // 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.
223
        if (rrset->getName().isWildcard()) {
224
            if (rrset->getType() == RRType::NS()) {
225 226
                LOG_ERROR(logger, DATASRC_MEM_WILDCARD_NS).
                    arg(rrset->getName());
227
                isc_throw(AddError, "Invalid NS owner name (wildcard): " <<
228
                          rrset->getName());
229 230
            }
            if (rrset->getType() == RRType::DNAME()) {
231 232
                LOG_ERROR(logger, DATASRC_MEM_WILDCARD_DNAME).
                    arg(rrset->getName());
233
                isc_throw(AddError, "Invalid DNAME owner name (wildcard): " <<
234
                          rrset->getName());
235 236
            }
        }
237 238
    }

239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288
    result::Result addRRsig(const ConstRRsetPtr sig_rrset,
                            DomainTree& domains)
    {
        DomainNode* node = NULL;
        if (domains.find(sig_rrset->getName(), &node) !=
            DomainTree::EXACTMATCH || node == NULL || !node->getData()) {
            isc_throw(AddError,
                      "RRSIG is being added, but no RR to be covered: "
                      << sig_rrset->getName());
        }

        // Check consistency of the type covered.
        // We know the RRset isn't empty, so the following check is safe.
        RdataIteratorPtr rit = sig_rrset->getRdataIterator();
        const RRType covered = dynamic_cast<const generic::RRSIG&>(
            rit->getCurrent()).typeCovered();
        for (rit->next(); !rit->isLast(); rit->next()) {
            if (dynamic_cast<const generic::RRSIG&>(
                    rit->getCurrent()).typeCovered() != covered) {
                isc_throw(AddError, "RRSIG contains mixed covered types: "
                          << sig_rrset->toText());
            }
        }

        // Find the RRset to be covered; if not found, treat it as an error
        // for now.
        const Domain::const_iterator it = node->getData()->find(covered);
        if (it == node->getData()->end()) {
            isc_throw(AddError,
                      "RRSIG is being added, but no RR of covered type found: "
                      << sig_rrset->toText());
        }

        // The current implementation doesn't allow an existing RRSIG to be
        // overridden (or updated with additional ones).
        if ((it->second)->getRRsig()) {
            isc_throw(AddError,
                      "RRSIG is being added to override an existing one: "
                      << sig_rrset->toText());
        }

        // All okay, setting the RRSIG.
        // XXX: we break const-ness of the covered RRsets.  In practice the
        // ownership of these RRsets would have been given to us so it should
        // be safe, but it's still a very bad practice.
        // We'll fix this problem anyway when we update the underlying
        // representation so that it's more space efficient.
        // Note: there's a slight chance of getting an exception.
        // As noted in add(), we give up strong exception guarantee in such
        // cases.
289
        boost::const_pointer_cast<AbstractRRset>(it->second)->addRRsig(sig_rrset);
290 291 292 293

        return (result::SUCCESS);
    }

294 295 296 297
    /*
     * Implementation of longer methods. We put them here, because the
     * access is without the impl_-> and it will get inlined anyway.
     */
298
    // Implementation of InMemoryZoneFinder::add
299
    result::Result add(const ConstRRsetPtr& rrset, DomainTree* domains) {
300 301 302 303 304
        // Sanitize input.  This will cause an exception to be thrown
        // if the input RRset is empty.
        addValidation(rrset);

        // OK, can add the RRset.
305 306
        LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_ADD_RRSET).
            arg(rrset->getName()).arg(rrset->getType()).arg(origin_);
307

308 309 310 311 312 313
        // RRSIGs are special in various points, so we handle it in a
        // separate dedicated method.
        if (rrset->getType() == RRType::RRSIG()) {
            return (addRRsig(rrset, *domains));
        }

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

Michal Vaner's avatar
Michal Vaner committed
320 321
        // Get the node
        DomainNode* node;
322 323 324 325
        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
326 327 328 329 330 331 332 333 334 335 336

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

337
        // Checks related to the surrounding data.
338 339 340 341
        // 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.
342
        contextCheck(rrset, domain);
343

Michal Vaner's avatar
Michal Vaner committed
344 345 346
        // Try inserting the rrset there
        if (domain->insert(DomainPair(rrset->getType(), rrset)).second) {
            // Ok, we just put it in
347 348 349 350 351

            // 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_) {
352
                node->setFlag(DomainNode::FLAG_CALLBACK);
353
                // If it is DNAME, we have a callback as well here
354
            } else if (rrset->getType() == RRType::DNAME()) {
355
                node->setFlag(DomainNode::FLAG_CALLBACK);
356 357
            }

Michal Vaner's avatar
Michal Vaner committed
358 359 360 361 362 363
            return (result::SUCCESS);
        } else {
            // The RRSet of given type was already there
            return (result::EXIST);
        }
    }
Michal Vaner's avatar
Michal Vaner committed
364

365 366 367 368 369 370 371
    /*
     * 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:
372 373
                    LOG_ERROR(logger, DATASRC_MEM_DUP_RRSET).
                        arg(set->getName()).arg(set->getType());
374 375 376 377 378 379 380 381 382
                    isc_throw(dns::MasterLoadError, "Duplicate rrset: " <<
                        set->toText());
                case result::SUCCESS:
                    return;
                default:
                    assert(0);
            }
    }

383 384 385 386 387 388
    // 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 {
389 390 391 392
        FindState(FindOptions options) :
            zonecut_node_(NULL),
            dname_node_(NULL),
            options_(options)
393 394
        {}
        const DomainNode* zonecut_node_;
395
        const DomainNode* dname_node_;
396 397
        ConstRRsetPtr rrset_;
        const FindOptions options_;
398 399
    };

400 401 402 403 404
    // 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,
405 406
        // the NS is authoritative, not delegation (corner case explicitly
        // allowed by section 3 of 2672)
407 408 409
        const Domain::const_iterator foundDNAME(node.getData()->find(
            RRType::DNAME()));
        if (foundDNAME != node.getData()->end()) {
410 411
            LOG_DEBUG(logger, DBG_TRACE_DETAILED,
                      DATASRC_MEM_DNAME_ENCOUNTERED);
412 413
            state->dname_node_ = &node;
            state->rrset_ = foundDNAME->second;
414 415 416 417 418 419
            // 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.
420
            return (true);
421 422
        }

423 424 425 426
        // Look for NS
        const Domain::const_iterator foundNS(node.getData()->find(
            RRType::NS()));
        if (foundNS != node.getData()->end()) {
427 428 429 430 431 432
            // 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);
            }

433
            LOG_DEBUG(logger, DBG_TRACE_DETAILED, DATASRC_MEM_NS_ENCOUNTERED);
434

435 436 437 438 439 440
            // 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.
441
            state->zonecut_node_ = &node;
442
            state->rrset_ = foundNS->second;
443 444 445 446

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

JINMEI Tatuya's avatar
JINMEI Tatuya committed
449 450 451
        // This case should not happen because we enable callback only
        // when we add an RR searched for above.
        assert(0);
452 453 454
        // 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".
455
        return (false);
456 457
    }

458 459 460 461 462 463 464 465 466 467 468 469
    /*
     * Prepares a rrset to be return as a result.
     *
     * If rename is false, it returns the one provided. If it is true, it
     * creates a new rrset with the same data but with provided name.
     * It is designed for wildcard case, where we create the rrsets
     * dynamically.
     */
    static ConstRRsetPtr prepareRRset(const Name& name, const ConstRRsetPtr&
        rrset, bool rename)
    {
        if (rename) {
470
            LOG_DEBUG(logger, DBG_TRACE_DETAILED, DATASRC_MEM_RENAME).
471
                arg(rrset->getName()).arg(name);
Michal 'vorner' Vaner's avatar
Michal 'vorner' Vaner committed
472 473 474 475 476 477
            /*
             * We lose a signature here. But it would be wrong anyway, because
             * the name changed. This might turn out to be unimportant in
             * future, because wildcards will probably be handled somehow
             * by DNSSEC.
             */
478 479 480 481 482 483 484 485 486 487 488
            RRsetPtr result(new RRset(name, rrset->getClass(),
                rrset->getType(), rrset->getTTL()));
            for (RdataIteratorPtr i(rrset->getRdataIterator()); !i->isLast();
                i->next()) {
                result->addRdata(i->getCurrent());
            }
            return (result);
        } else {
            return (rrset);
        }
    }
chenzhengzhang's avatar
chenzhengzhang committed
489

490
    // Implementation of InMemoryZoneFinder::find
491 492 493
    FindResult find(const Name& name, RRType type,
                    std::vector<ConstRRsetPtr> *target,
                    const FindOptions options) const
494
    {
495 496
        LOG_DEBUG(logger, DBG_TRACE_BASIC, DATASRC_MEM_FIND).arg(name).
            arg(type);
Michal Vaner's avatar
Michal Vaner committed
497
        // Get the node
Michal Vaner's avatar
Michal Vaner committed
498
        DomainNode* node(NULL);
499
        FindState state(options);
500
        RBTreeNodeChain<Domain> node_path;
501
        bool rename(false);
502
        switch (domains_.find(name, &node, node_path, cutCallback, &state)) {
Michal Vaner's avatar
Michal Vaner committed
503
            case DomainTree::PARTIALMATCH:
504 505 506 507 508 509 510 511 512 513 514 515 516 517 518
                /*
                 * 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
519
                 * all other cases it doesn't matter, as at least one of them
520 521
                 * is NULL.
                 */
522
                if (state.dname_node_ != NULL) {
523
                    LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_DNAME_FOUND).
524
                        arg(state.rrset_->getName());
525 526
                    // We were traversing a DNAME node (and wanted to go
                    // lower below it), so return the DNAME
527 528
                    return (FindResult(DNAME, prepareRRset(name, state.rrset_,
                        rename)));
529
                }
530
                if (state.zonecut_node_ != NULL) {
531
                    LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_DELEG_FOUND).
532
                        arg(state.rrset_->getName());
533 534
                    return (FindResult(DELEGATION, prepareRRset(name,
                        state.rrset_, rename)));
535
                }
536 537 538 539 540 541

                // 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) {
542 543
                    LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_SUPER_STOP).
                        arg(node_path.getAbsoluteName()).arg(name);
544 545 546
                    return (FindResult(NXRRSET, ConstRRsetPtr()));
                }

547 548
                /*
                 * No redirection anywhere. Let's try if it is a wildcard.
549 550 551 552 553
                 *
                 * The wildcard is checked after the empty non-terminal domain
                 * case above, because if that one triggers, it means we should
                 * not match according to 4.3.3 of RFC 1034 (the query name
                 * is known to exist).
554 555
                 */
                if (node->getFlag(DOMAINFLAG_WILD)) {
556 557 558 559 560 561 562 563 564 565 566 567 568 569 570
                    /* Should we cancel this match?
                     *
                     * If we compare with some node and get a common ancestor,
                     * it might mean we are comparing with a non-wildcard node.
                     * In that case, we check which part is common. If we have
                     * something in common that lives below the node we got
                     * (the one above *), then we should cancel the match
                     * according to section 4.3.3 of RFC 1034 (as the name
                     * between the wildcard domain and the query name is known
                     * to exist).
                     *
                     * Because the way the tree stores relative names, we will
                     * have exactly one common label (the ".") in case we have
                     * nothing common under the node we got and we will get
                     * more common labels otherwise (yes, this relies on the
571
                     * internal RBTree structure, which leaks out through this
572 573 574 575 576 577 578 579 580
                     * little bit).
                     *
                     * If the empty non-terminal node actually exists in the
                     * tree, then this cancellation is not needed, because we
                     * will not get here at all.
                     */
                    if (node_path.getLastComparisonResult().getRelation() ==
                        NameComparisonResult::COMMONANCESTOR && node_path.
                        getLastComparisonResult().getCommonLabels() > 1) {
581
                        LOG_DEBUG(logger, DBG_TRACE_DATA,
582
                                     DATASRC_MEM_WILDCARD_CANCEL).arg(name);
583 584
                        return (FindResult(NXDOMAIN, ConstRRsetPtr()));
                    }
585 586 587 588 589 590 591
                    Name wildcard(Name("*").concatenate(
                        node_path.getAbsoluteName()));
                    DomainTree::Result result(domains_.find(wildcard, &node));
                    /*
                     * Otherwise, why would the DOMAINFLAG_WILD be there if
                     * there was no wildcard under it?
                     */
592
                    assert(result == DomainTree::EXACTMATCH);
593 594 595 596
                    /*
                     * We have the wildcard node now. Jump below the switch,
                     * where handling of the common (exact-match) case is.
                     *
597
                     * However, rename it to the searched name.
598
                     */
599
                    rename = true;
600 601
                    break;
                }
602 603

                // fall through
Michal Vaner's avatar
Michal Vaner committed
604
            case DomainTree::NOTFOUND:
605
                LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_NOT_FOUND).
606
                    arg(name);
Michal Vaner's avatar
Michal Vaner committed
607 608 609 610 611
                return (FindResult(NXDOMAIN, ConstRRsetPtr()));
            case DomainTree::EXACTMATCH: // This one is OK, handle it
                break;
            default:
                assert(0);
Michal Vaner's avatar
Michal Vaner committed
612
        }
613
        assert(node != NULL);
614 615 616 617

        // If there is an exact match but the node is empty, it's equivalent
        // to NXRRSET.
        if (node->isEmpty()) {
618 619
            LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_DOMAIN_EMPTY).
                arg(name);
620 621
            return (FindResult(NXRRSET, ConstRRsetPtr()));
        }
Michal Vaner's avatar
Michal Vaner committed
622

623 624 625
        Domain::const_iterator found;

        // If the node callback is enabled, this may be a zone cut.  If it
626
        // has a NS RR, we should return a delegation, but not in the apex.
627 628 629 630
        // There is one exception: the case for DS query, which should always
        // be considered in-zone lookup.
        if (node->getFlag(DomainNode::FLAG_CALLBACK) && node != origin_data_ &&
            type != RRType::DS()) {
631 632
            found = node->getData()->find(RRType::NS());
            if (found != node->getData()->end()) {
633 634
                LOG_DEBUG(logger, DBG_TRACE_DATA,
                          DATASRC_MEM_EXACT_DELEGATION).arg(name);
635 636
                return (FindResult(DELEGATION, prepareRRset(name,
                    found->second, rename)));
637 638 639
            }
        }

chenzhengzhang's avatar
chenzhengzhang committed
640
        // handle type any query
641
        if (target != NULL && !node->getData()->empty()) {
642 643
            // Empty domain will be handled as NXRRSET by normal processing
            for (found = node->getData()->begin();
644
                 found != node->getData()->end(); ++found)
645
            {
646
                target->push_back(prepareRRset(name, found->second, rename));
chenzhengzhang's avatar
chenzhengzhang committed
647
            }
648 649
            LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_ANY_SUCCESS).
                arg(name);
650
            return (FindResult(SUCCESS, ConstRRsetPtr()));
chenzhengzhang's avatar
chenzhengzhang committed
651 652
        }

653
        found = node->getData()->find(type);
Michal Vaner's avatar
Michal Vaner committed
654 655
        if (found != node->getData()->end()) {
            // Good, it is here
656
            LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_SUCCESS).arg(name).
657
                arg(type);
658 659
            return (FindResult(SUCCESS, prepareRRset(name, found->second,
                rename)));
Michal Vaner's avatar
Michal Vaner committed
660
        } else {
661
            // Next, try CNAME.
662 663
            found = node->getData()->find(RRType::CNAME());
            if (found != node->getData()->end()) {
664
                LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_CNAME).arg(name);
665 666
                return (FindResult(CNAME, prepareRRset(name, found->second,
                    rename)));
667
            }
Michal Vaner's avatar
Michal Vaner committed
668
        }
669
        // No exact match or CNAME.  Return NXRRSET.
670 671
        LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_NXRRSET).arg(type).
            arg(name);
672
        return (FindResult(NXRRSET, ConstRRsetPtr()));
Michal Vaner's avatar
Michal Vaner committed
673
    }
674 675
};

676 677
InMemoryZoneFinder::InMemoryZoneFinder(const RRClass& zone_class, const Name& origin) :
    impl_(new InMemoryZoneFinderImpl(zone_class, origin))
678
{
679
    LOG_DEBUG(logger, DBG_TRACE_BASIC, DATASRC_MEM_CREATE).arg(origin).
680
        arg(zone_class);
681 682
}

683
InMemoryZoneFinder::~InMemoryZoneFinder() {
684
    LOG_DEBUG(logger, DBG_TRACE_BASIC, DATASRC_MEM_DESTROY).arg(getOrigin()).
685
        arg(getClass());
686 687 688
    delete impl_;
}

689
Name
690
InMemoryZoneFinder::getOrigin() const {
691 692 693
    return (impl_->origin_);
}

694
RRClass
695
InMemoryZoneFinder::getClass() const {
696 697 698
    return (impl_->zone_class_);
}

699
ZoneFinder::FindResult
700
InMemoryZoneFinder::find(const Name& name, const RRType& type,
701
                 const FindOptions options)
chenzhengzhang's avatar
chenzhengzhang committed
702
{
703 704 705 706 707 708 709 710 711
    return (impl_->find(name, type, NULL, options));
}

ZoneFinder::FindResult
InMemoryZoneFinder::findAll(const Name& name,
                            std::vector<ConstRRsetPtr>& target,
                            const FindOptions options)
{
    return (impl_->find(name, RRType::ANY(), &target, options));
chenzhengzhang's avatar
chenzhengzhang committed
712 713
}

714
ZoneFinder::FindNSEC3Result
715
InMemoryZoneFinder::findNSEC3(const Name&, bool) {
716 717 718 719
    isc_throw(NotImplemented, "findNSEC3 is not yet implemented for in memory "
              "data source");
}

Michal Vaner's avatar
Michal Vaner committed
720
result::Result
721
InMemoryZoneFinder::add(const ConstRRsetPtr& rrset) {
722
    return (impl_->add(rrset, &impl_->domains_));
723 724
}

Michal Vaner's avatar
Michal Vaner committed
725 726

void
727
InMemoryZoneFinder::load(const string& filename) {
728
    LOG_DEBUG(logger, DBG_TRACE_BASIC, DATASRC_MEM_LOAD).arg(getOrigin()).
729
        arg(filename);
730
    // Load it into a temporary tree
731
    DomainTree tmp;
732
    masterLoad(filename.c_str(), getOrigin(), getClass(),
733
        boost::bind(&InMemoryZoneFinderImpl::addFromLoad, impl_, _1, &tmp));
734
    // If it went well, put it inside
735
    impl_->file_name_ = filename;
736 737
    tmp.swap(impl_->domains_);
    // And let the old data die with tmp
738 739
}

740
void
741
InMemoryZoneFinder::swap(InMemoryZoneFinder& zone_finder) {
742
    LOG_DEBUG(logger, DBG_TRACE_BASIC, DATASRC_MEM_SWAP).arg(getOrigin()).
743 744
        arg(zone_finder.getOrigin());
    std::swap(impl_, zone_finder.impl_);
745 746 747
}

const string
748
InMemoryZoneFinder::getFileName() const {
749 750 751
    return (impl_->file_name_);
}

752 753 754 755 756 757
isc::dns::Name
InMemoryZoneFinder::findPreviousName(const isc::dns::Name&) const {
    isc_throw(NotImplemented, "InMemory data source doesn't support DNSSEC "
              "yet, can't find previous name");
}

758
/// Implementation details for \c InMemoryClient hidden from the public
759 760
/// interface.
///
761
/// For now, \c InMemoryClient only contains a \c ZoneTable object, which
762
/// consists of (pointers to) \c InMemoryZoneFinder objects, we may add more
763
/// member variables later for new features.
764
class InMemoryClient::InMemoryClientImpl {
765
public:
766
    InMemoryClientImpl() : zone_count(0) {}
767
    unsigned int zone_count;
768 769 770
    ZoneTable zone_table;
};

771
InMemoryClient::InMemoryClient() : impl_(new InMemoryClientImpl)
772 773
{}

774
InMemoryClient::~InMemoryClient() {
775 776 777
    delete impl_;
}

778
unsigned int
779
InMemoryClient::getZoneCount() const {
780 781 782
    return (impl_->zone_count);
}

783
result::Result
784 785
InMemoryClient::addZone(ZoneFinderPtr zone_finder) {
    if (!zone_finder) {
786
        isc_throw(InvalidParameter,
787
                  "Null pointer is passed to InMemoryClient::addZone()");
788
    }
789

790
    LOG_DEBUG(logger, DBG_TRACE_BASIC, DATASRC_MEM_ADD_ZONE).
791
        arg(zone_finder->getOrigin()).arg(zone_finder->getClass().toText());
792

793
    const result::Result result = impl_->zone_table.addZone(zone_finder);
794 795 796 797
    if (result == result::SUCCESS) {
        ++impl_->zone_count;
    }
    return (result);
798 799
}

800 801
InMemoryClient::FindResult
InMemoryClient::findZone(const isc::dns::Name& name) const {
802
    LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_FIND_ZONE).arg(name);
803 804
    ZoneTable::FindResult result(impl_->zone_table.findZone(name));
    return (FindResult(result.code, result.zone));
805
}
806 807 808 809 810 811 812 813 814

namespace {

class MemoryIterator : public ZoneIterator {
private:
    RBTreeNodeChain<Domain> chain_;
    Domain::const_iterator dom_iterator_;
    const DomainTree& tree_;
    const DomainNode* node_;
815 816 817
    // Only used when separate_rrs_ is true
    RdataIteratorPtr rdata_iterator_;
    bool separate_rrs_;
818 819
    bool ready_;
public:
820
    MemoryIterator(const DomainTree& tree, const Name& origin, bool separate_rrs) :
821
        tree_(tree),
822
        separate_rrs_(separate_rrs),
823 824 825 826 827 828 829 830 831 832 833 834 835 836
        ready_(true)
    {
        // Find the first node (origin) and preserve the node chain for future
        // searches
        DomainTree::Result result(tree_.find<void*>(origin, &node_, chain_,
                                                    NULL, NULL));
        // It can't happen that the origin is not in there
        if (result != DomainTree::EXACTMATCH) {
            isc_throw(Unexpected,
                      "In-memory zone corrupted, missing origin node");
        }
        // Initialize the iterator if there's somewhere to point to
        if (node_ != NULL && node_->getData() != DomainPtr()) {
            dom_iterator_ = node_->getData()->begin();
837 838
            if (separate_rrs_ && dom_iterator_ != node_->getData()->end()) {
                rdata_iterator_ = dom_iterator_->second->getRdataIterator();
839
            }
840 841
        }
    }
Jelte Jansen's avatar
Jelte Jansen committed
842

843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858
    virtual ConstRRsetPtr getNextRRset() {
        if (!ready_) {
            isc_throw(Unexpected, "Iterating past the zone end");
        }
        /*
         * This cycle finds the first nonempty node with yet unused RRset.
         * If it is NULL, we run out of nodes. If it is empty, it doesn't
         * contain any RRsets. If we are at the end, just get to next one.
         */
        while (node_ != NULL && (node_->getData() == DomainPtr() ||
                                 dom_iterator_ == node_->getData()->end())) {
            node_ = tree_.nextNode(chain_);
            // If there's a node, initialize the iterator and check next time
            // if the map is empty or not
            if (node_ != NULL && node_->getData() != NULL) {
                dom_iterator_ = node_->getData()->begin();
859 860 861 862
                // New RRset, so get a new rdata iterator
                if (separate_rrs_) {
                    rdata_iterator_ = dom_iterator_->second->getRdataIterator();
                }
863 864 865 866 867
            }
        }
        if (node_ == NULL) {
            // That's all, folks
            ready_ = false;
Jelte Jansen's avatar
Jelte Jansen committed
868
            return (ConstRRsetPtr());
869 870
        }

871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898
        if (separate_rrs_) {
            // For separate rrs, reconstruct a new RRset with just the
            // 'current' rdata
            RRsetPtr result(new RRset(dom_iterator_->second->getName(),
                                      dom_iterator_->second->getClass(),
                                      dom_iterator_->second->getType(),
                                      dom_iterator_->second->getTTL()));
            result->addRdata(rdata_iterator_->getCurrent());
            rdata_iterator_->next();
            if (rdata_iterator_->isLast()) {
                // all used up, next.
                ++dom_iterator_;
                // New RRset, so get a new rdata iterator, but only if this
                // was not the final RRset in the chain
                if (dom_iterator_ != node_->getData()->end()) {
                    rdata_iterator_ = dom_iterator_->second->getRdataIterator();
                }
            }
            return (result);
        } else {
            // The iterator points to the next yet unused RRset now
            ConstRRsetPtr result(dom_iterator_->second);

            // This one is used, move it to the next time for next call
            ++dom_iterator_;

            return (result);
        }
899
    }
900

901
    virtual ConstRRsetPtr getSOA() const {
902 903
        isc_throw(NotImplemented, "Not imelemented");
    }
904 905 906 907 908
};

} // End of anonymous namespace

ZoneIteratorPtr
909
InMemoryClient::getIterator(const Name& name, bool separate_rrs) const {
910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926
    ZoneTable::FindResult result(impl_->zone_table.findZone(name));
    if (result.code != result::SUCCESS) {
        isc_throw(DataSourceError, "No such zone: " + name.toText());
    }

    const InMemoryZoneFinder*
        zone(dynamic_cast<const InMemoryZoneFinder*>(result.zone.get()));
    if (zone == NULL) {
        /*
         * TODO: This can happen only during some of the tests and only as
         * a temporary solution. This should be fixed by #1159 and then
         * this cast and check shouldn't be necessary. We don't have
         * test for handling a "can not happen" condition.
         */
        isc_throw(Unexpected, "The zone at " + name.toText() +
                  " is not InMemoryZoneFinder");
    }
927 928
    return (ZoneIteratorPtr(new MemoryIterator(zone->impl_->domains_, name,
                                               separate_rrs)));
929 930
}

931
ZoneUpdaterPtr
932
InMemoryClient::getUpdater(const isc::dns::Name&, bool, bool) const {
933
    isc_throw(isc::NotImplemented, "Update attempt on in memory data source");
934
}
935

936
pair<ZoneJournalReader::Result, ZoneJournalReaderPtr>
937 938 939 940 941 942
InMemoryClient::getJournalReader(const isc::dns::Name&, uint32_t,
                                 uint32_t) const
{
    isc_throw(isc::NotImplemented, "Journaling isn't supported for "
              "in memory data source");
}
943 944 945 946 947 948 949 950 951 952 953 954

namespace {
// convencience function to add an error message to a list of those
// (TODO: move functions like these to some util lib?)
void
addError(ElementPtr errors, const std::string& error) {
    if (errors != ElementPtr() && errors->getType() == Element::list) {
        errors->add(Element::create(error));
    }
}

/// Check if the given element exists in the map, and if it is a string
955
bool
956 957 958 959 960 961
checkConfigElementString(ConstElementPtr config, const std::string& name,
                         ElementPtr errors)
{
    if (!config->contains(name)) {
        addError(errors,
                 "Config for memory backend does not contain a '"
962
                 +name+
963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056
                 "' value");
        return false;
    } else if (!config->get(name) ||
               config->get(name)->getType() != Element::string) {
        addError(errors, "value of " + name +
                 " in memory backend config is not a string");
        return false;
    } else {
        return true;
    }
}

bool
checkZoneConfig(ConstElementPtr config, ElementPtr errors) {
    bool result = true;
    if (!config || config->getType() != Element::map) {
        addError(errors, "Elements in memory backend's zone list must be maps");
        result = false;
    } else {
        if (!checkConfigElementString(config, "origin", errors)) {
            result = false;
        }
        if (!checkConfigElementString(config, "file", errors)) {
            result = false;
        }
        // we could add some existence/readabilty/parsability checks here
        // if we want
    }
    return result;
}

bool
checkConfig(ConstElementPtr config, ElementPtr errors) {
    /* Specific configuration is under discussion, right now this accepts
     * the 'old' configuration, see [TODO]
     * So for memory datasource, we get a structure like this:
     * { "type": string ("memory"),
     *   "class": string ("IN"/"CH"/etc),
     *   "zones": list
     * }
     * Zones list is a list of maps:
     * { "origin": string,
     *     "file": string
     * }
     *
     * At this moment we cannot be completely sure of the contents of the
     * structure, so we have to do some more extensive tests than should
     * strictly be necessary (e.g. existence and type of elements)
     */
    bool result = true;

    if (!config || config->getType() != Element::map) {
        addError(errors, "Base config for memory backend must be a map");
        result = false;
    } else {
        if (!checkConfigElementString(config, "type", errors)) {
            result = false;
        } else {
            if (config->get("type")->stringValue() != "memory") {
                addError(errors,
                         "Config for memory backend is not of type \"memory\"");
                result = false;
            }
        }
        if (!checkConfigElementString(config, "class", errors)) {
            result = false;
        } else {
            try {
                RRClass rrc(config->get("class")->stringValue());
            } catch (const isc::Exception& rrce) {
                addError(errors,
                         "Error parsing class config for memory backend: " +
                         std::string(rrce.what()));
                result = false;
            }
        }
        if (!config->contains("zones")) {
            addError(errors, "No 'zones' element in memory backend config");
            result = false;
        } else if (!config->get("zones") ||
                   config->get("zones")->getType() != Element::list) {
            addError(errors, "'zones' element in memory backend config is not a list");
            result = false;
        } else {
            BOOST_FOREACH(ConstElementPtr zone_config,
                          config->get("zones")->listValue()) {
                if (!checkZoneConfig(zone_config, errors)) {
                    result = false;
                }
            }
        }
    }

    return (result);
1057 1058 1059
    return true;
}

1060 1061
} // end anonymous namespace

1062
DataSourceClient *
1063
createInstance(isc::data::ConstElementPtr config, std::string& error) {
1064 1065
    ElementPtr errors(Element::createList());
    if (!checkConfig(config, errors)) {
1066 1067
        error = "Configuration error: " + errors->str();
        return (NULL);