contrib/bind-9.3/lib/dns/rbtdb.c

   1 /*
   2  * Copyright (C) 2004-2006  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1999-2003  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  10  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  11  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  12  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  13  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  14  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  15  * PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /* $Id: rbtdb.c,v 1.168.2.11.2.26 2006/03/02 23:18:20 marka Exp $ */
  19
  20 /*
  21  * Principal Author: Bob Halley
  22  */
  23
  24 #include <config.h>
  25
  26 #include <isc/event.h>
  27 #include <isc/mem.h>
  28 #include <isc/print.h>
  29 #include <isc/mutex.h>
  30 #include <isc/random.h>
  31 #include <isc/refcount.h>
  32 #include <isc/rwlock.h>
  33 #include <isc/string.h>
  34 #include <isc/task.h>
  35 #include <isc/util.h>
  36
  37 #include <dns/db.h>
  38 #include <dns/dbiterator.h>
  39 #include <dns/events.h>
  40 #include <dns/fixedname.h>
  41 #include <dns/log.h>
  42 #include <dns/masterdump.h>
  43 #include <dns/rbt.h>
  44 #include <dns/rdata.h>
  45 #include <dns/rdataset.h>
  46 #include <dns/rdatasetiter.h>
  47 #include <dns/rdataslab.h>
  48 #include <dns/result.h>
  49 #include <dns/zonekey.h>
  50
  51 #ifdef DNS_RBTDB_VERSION64
  52 #include "rbtdb64.h"
  53 #else
  54 #include "rbtdb.h"
  55 #endif
  56
  57 #ifdef DNS_RBTDB_VERSION64
  58 #define RBTDB_MAGIC                     ISC_MAGIC('R', 'B', 'D', '8')
  59 #else
  60 #define RBTDB_MAGIC                     ISC_MAGIC('R', 'B', 'D', '4')
  61 #endif
  62
  63 /*
  64  * Note that "impmagic" is not the first four bytes of the struct, so
  65  * ISC_MAGIC_VALID cannot be used.
  66  */
  67 #define VALID_RBTDB(rbtdb)      ((rbtdb) != NULL && \
  68                                  (rbtdb)->common.impmagic == RBTDB_MAGIC)
  69
  70 #ifdef DNS_RBTDB_VERSION64
  71 typedef isc_uint64_t                    rbtdb_serial_t;
  72 /*
  73  * Make casting easier in symbolic debuggers by using different names
  74  * for the 64 bit version.
  75  */
  76 #define dns_rbtdb_t dns_rbtdb64_t
  77 #define rdatasetheader_t rdatasetheader64_t
  78 #define rbtdb_version_t rbtdb_version64_t
  79 #else
  80 typedef isc_uint32_t                    rbtdb_serial_t;
  81 #endif
  82
  83 typedef isc_uint32_t                    rbtdb_rdatatype_t;
  84
  85 #define RBTDB_RDATATYPE_BASE(type)      ((dns_rdatatype_t)((type) & 0xFFFF))
  86 #define RBTDB_RDATATYPE_EXT(type)       ((dns_rdatatype_t)((type) >> 16))
  87 #define RBTDB_RDATATYPE_VALUE(b, e)     (((e) << 16) | (b))
  88
  89 #define RBTDB_RDATATYPE_SIGNSEC \
  90                 RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, dns_rdatatype_nsec)
  91 #define RBTDB_RDATATYPE_SIGNS \
  92                 RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, dns_rdatatype_ns)
  93 #define RBTDB_RDATATYPE_SIGCNAME \
  94                 RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, dns_rdatatype_cname)
  95 #define RBTDB_RDATATYPE_SIGDNAME \
  96                 RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, dns_rdatatype_dname)
  97 #define RBTDB_RDATATYPE_NCACHEANY \
  98                 RBTDB_RDATATYPE_VALUE(0, dns_rdatatype_any)
  99
 100 /*
 101  * Allow clients with a virtual time of upto 5 minutes in the past to see
 102  * records that would have otherwise have expired.
 103  */
 104 #define RBTDB_VIRTUAL 300
 105
 106 struct noqname {
 107         dns_name_t name;
 108         void *     nsec;
 109         void *     nsecsig;
 110 };
 111
 112 typedef struct rdatasetheader {
 113         /*
 114          * Locked by the owning node's lock.
 115          */
 116         rbtdb_serial_t                  serial;
 117         dns_ttl_t                       ttl;
 118         rbtdb_rdatatype_t               type;
 119         isc_uint16_t                    attributes;
 120         dns_trust_t                     trust;
 121         struct noqname                  *noqname;
 122         /*
 123          * We don't use the LIST macros, because the LIST structure has
 124          * both head and tail pointers, and is doubly linked.
 125          */
 126
 127         struct rdatasetheader           *next;
 128         /*
 129          * If this is the top header for an rdataset, 'next' points
 130          * to the top header for the next rdataset (i.e., the next type).
 131          * Otherwise, it points up to the header whose down pointer points
 132          * at this header.
 133          */
 134
 135         struct rdatasetheader           *down;
 136         /*
 137          * Points to the header for the next older version of
 138          * this rdataset.
 139          */
 140
 141         isc_uint32_t                    count;
 142         /*
 143          * Monotonously increased every time this rdataset is bound so that
 144          * it is used as the base of the starting point in DNS responses
 145          * when the "cyclic" rrset-order is required.  Since the ordering
 146          * should not be so crucial, no lock is set for the counter for
 147          * performance reasons.
 148          */
 149 } rdatasetheader_t;
 150
 151 #define RDATASET_ATTR_NONEXISTENT       0x0001
 152 #define RDATASET_ATTR_STALE             0x0002
 153 #define RDATASET_ATTR_IGNORE            0x0004
 154 #define RDATASET_ATTR_RETAIN            0x0008
 155 #define RDATASET_ATTR_NXDOMAIN          0x0010
 156
 157 /*
 158  * XXX
 159  * When the cache will pre-expire data (due to memory low or other
 160  * situations) before the rdataset's TTL has expired, it MUST
 161  * respect the RETAIN bit and not expire the data until its TTL is
 162  * expired.
 163  */
 164
 165 #undef IGNORE                   /* WIN32 winbase.h defines this. */
 166
 167 #define EXISTS(header) \
 168         (((header)->attributes & RDATASET_ATTR_NONEXISTENT) == 0)
 169 #define NONEXISTENT(header) \
 170         (((header)->attributes & RDATASET_ATTR_NONEXISTENT) != 0)
 171 #define IGNORE(header) \
 172         (((header)->attributes & RDATASET_ATTR_IGNORE) != 0)
 173 #define RETAIN(header) \
 174         (((header)->attributes & RDATASET_ATTR_RETAIN) != 0)
 175 #define NXDOMAIN(header) \
 176         (((header)->attributes & RDATASET_ATTR_NXDOMAIN) != 0)
 177
 178 #define DEFAULT_NODE_LOCK_COUNT         7               /* Should be prime. */
 179
 180 typedef struct {
 181         isc_mutex_t                     lock;
 182         /* Locked by lock. */
 183         unsigned int                    references;
 184         isc_boolean_t                   exiting;
 185 } rbtdb_nodelock_t;
 186
 187 typedef struct rbtdb_changed {
 188         dns_rbtnode_t *                 node;
 189         isc_boolean_t                   dirty;
 190         ISC_LINK(struct rbtdb_changed)  link;
 191 } rbtdb_changed_t;
 192
 193 typedef ISC_LIST(rbtdb_changed_t)       rbtdb_changedlist_t;
 194
 195 typedef struct rbtdb_version {
 196         /* Not locked */
 197         rbtdb_serial_t                  serial;
 198         /* Locked by database lock. */
 199         isc_boolean_t                   writer;
 200         unsigned int                    references;
 201         isc_boolean_t                   commit_ok;
 202         rbtdb_changedlist_t             changed_list;
 203         ISC_LINK(struct rbtdb_version)  link;
 204 } rbtdb_version_t;
 205
 206 typedef ISC_LIST(rbtdb_version_t)       rbtdb_versionlist_t;
 207
 208 typedef struct {
 209         /* Unlocked. */
 210         dns_db_t                        common;
 211         isc_mutex_t                     lock;
 212         isc_rwlock_t                    tree_lock;
 213         unsigned int                    node_lock_count;
 214         rbtdb_nodelock_t *              node_locks;
 215         dns_rbtnode_t *                 origin_node;
 216         /* Locked by lock. */
 217         unsigned int                    active;
 218         isc_refcount_t                  references;
 219         unsigned int                    attributes;
 220         rbtdb_serial_t                  current_serial;
 221         rbtdb_serial_t                  least_serial;
 222         rbtdb_serial_t                  next_serial;
 223         rbtdb_version_t *               current_version;
 224         rbtdb_version_t *               future_version;
 225         rbtdb_versionlist_t             open_versions;
 226         isc_boolean_t                   overmem;
 227         isc_task_t *                    task;
 228         /* Locked by tree_lock. */
 229         dns_rbt_t *                     tree;
 230         isc_boolean_t                   secure;
 231 } dns_rbtdb_t;
 232
 233 #define RBTDB_ATTR_LOADED               0x01
 234 #define RBTDB_ATTR_LOADING              0x02
 235
 236 /*
 237  * Search Context
 238  */
 239 typedef struct {
 240         dns_rbtdb_t *           rbtdb;
 241         rbtdb_version_t *       rbtversion;
 242         rbtdb_serial_t          serial;
 243         unsigned int            options;
 244         dns_rbtnodechain_t      chain;
 245         isc_boolean_t           copy_name;
 246         isc_boolean_t           need_cleanup;
 247         isc_boolean_t           wild;
 248         dns_rbtnode_t *         zonecut;
 249         rdatasetheader_t *      zonecut_rdataset;
 250         rdatasetheader_t *      zonecut_sigrdataset;
 251         dns_fixedname_t         zonecut_name;
 252         isc_stdtime_t           now;
 253 } rbtdb_search_t;
 254
 255 /*
 256  * Load Context
 257  */
 258 typedef struct {
 259         dns_rbtdb_t *           rbtdb;
 260         isc_stdtime_t           now;
 261 } rbtdb_load_t;
 262
 263 static void rdataset_disassociate(dns_rdataset_t *rdataset);
 264 static isc_result_t rdataset_first(dns_rdataset_t *rdataset);
 265 static isc_result_t rdataset_next(dns_rdataset_t *rdataset);
 266 static void rdataset_current(dns_rdataset_t *rdataset, dns_rdata_t *rdata);
 267 static void rdataset_clone(dns_rdataset_t *source, dns_rdataset_t *target);
 268 static unsigned int rdataset_count(dns_rdataset_t *rdataset);
 269 static isc_result_t rdataset_getnoqname(dns_rdataset_t *rdataset,
 270                                         dns_name_t *name,
 271                                         dns_rdataset_t *nsec,
 272                                         dns_rdataset_t *nsecsig);
 273
 274 static dns_rdatasetmethods_t rdataset_methods = {
 275         rdataset_disassociate,
 276         rdataset_first,
 277         rdataset_next,
 278         rdataset_current,
 279         rdataset_clone,
 280         rdataset_count,
 281         NULL,
 282         rdataset_getnoqname
 283 };
 284
 285 static void rdatasetiter_destroy(dns_rdatasetiter_t **iteratorp);
 286 static isc_result_t rdatasetiter_first(dns_rdatasetiter_t *iterator);
 287 static isc_result_t rdatasetiter_next(dns_rdatasetiter_t *iterator);
 288 static void rdatasetiter_current(dns_rdatasetiter_t *iterator,
 289                                  dns_rdataset_t *rdataset);
 290
 291 static dns_rdatasetitermethods_t rdatasetiter_methods = {
 292         rdatasetiter_destroy,
 293         rdatasetiter_first,
 294         rdatasetiter_next,
 295         rdatasetiter_current
 296 };
 297
 298 typedef struct rbtdb_rdatasetiter {
 299         dns_rdatasetiter_t              common;
 300         rdatasetheader_t *              current;
 301 } rbtdb_rdatasetiter_t;
 302
 303 static void             dbiterator_destroy(dns_dbiterator_t **iteratorp);
 304 static isc_result_t     dbiterator_first(dns_dbiterator_t *iterator);
 305 static isc_result_t     dbiterator_last(dns_dbiterator_t *iterator);
 306 static isc_result_t     dbiterator_seek(dns_dbiterator_t *iterator,
 307                                         dns_name_t *name);
 308 static isc_result_t     dbiterator_prev(dns_dbiterator_t *iterator);
 309 static isc_result_t     dbiterator_next(dns_dbiterator_t *iterator);
 310 static isc_result_t     dbiterator_current(dns_dbiterator_t *iterator,
 311                                            dns_dbnode_t **nodep,
 312                                            dns_name_t *name);
 313 static isc_result_t     dbiterator_pause(dns_dbiterator_t *iterator);
 314 static isc_result_t     dbiterator_origin(dns_dbiterator_t *iterator,
 315                                           dns_name_t *name);
 316
 317 static dns_dbiteratormethods_t dbiterator_methods = {
 318         dbiterator_destroy,
 319         dbiterator_first,
 320         dbiterator_last,
 321         dbiterator_seek,
 322         dbiterator_prev,
 323         dbiterator_next,
 324         dbiterator_current,
 325         dbiterator_pause,
 326         dbiterator_origin
 327 };
 328
 329 #define DELETION_BATCH_MAX 64
 330
 331 /*
 332  * If 'paused' is ISC_TRUE, then the tree lock is not being held.
 333  */
 334 typedef struct rbtdb_dbiterator {
 335         dns_dbiterator_t                common;
 336         isc_boolean_t                   paused;
 337         isc_boolean_t                   new_origin;
 338         isc_rwlocktype_t                tree_locked;
 339         isc_result_t                    result;
 340         dns_fixedname_t                 name;
 341         dns_fixedname_t                 origin;
 342         dns_rbtnodechain_t              chain;
 343         dns_rbtnode_t                   *node;
 344         dns_rbtnode_t                   *deletions[DELETION_BATCH_MAX];
 345         int                             delete;
 346 } rbtdb_dbiterator_t;
 347
 348
 349 #define IS_STUB(rbtdb)  (((rbtdb)->common.attributes & DNS_DBATTR_STUB)  != 0)
 350 #define IS_CACHE(rbtdb) (((rbtdb)->common.attributes & DNS_DBATTR_CACHE) != 0)
 351
 352 static void free_rbtdb(dns_rbtdb_t *rbtdb, isc_boolean_t log,
 353                        isc_event_t *event);
 354
 355 /*
 356  * Locking
 357  *
 358  * If a routine is going to lock more than one lock in this module, then
 359  * the locking must be done in the following order:
 360  *
 361  *      Tree Lock
 362  *
 363  *      Node Lock       (Only one from the set may be locked at one time by
 364  *                       any caller)
 365  *
 366  *      Database Lock
 367  *
 368  * Failure to follow this hierarchy can result in deadlock.
 369  */
 370
 371 /*
 372  * Deleting Nodes
 373  *
 374  * Currently there is no deletion of nodes from the database, except when
 375  * the database is being destroyed.
 376  *
 377  * If node deletion is added in the future, then for zone databases the node
 378  * for the origin of the zone MUST NOT be deleted.
 379  */
 380
 381
 382 /*
 383  * DB Routines
 384  */
 385
 386 static void
 387 attach(dns_db_t *source, dns_db_t **targetp) {
 388         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)source;
 389
 390         REQUIRE(VALID_RBTDB(rbtdb));
 391
 392         isc_refcount_increment(&rbtdb->references, NULL);
 393
 394         *targetp = source;
 395 }
 396
 397 static void
 398 free_rbtdb_callback(isc_task_t *task, isc_event_t *event) {
 399         dns_rbtdb_t *rbtdb = event->ev_arg;
 400
 401         UNUSED(task);
 402
 403         free_rbtdb(rbtdb, ISC_TRUE, event);
 404 }
 405
 406 static void
 407 free_rbtdb(dns_rbtdb_t *rbtdb, isc_boolean_t log, isc_event_t *event) {
 408         unsigned int i;
 409         isc_ondestroy_t ondest;
 410         isc_result_t result;
 411         char buf[DNS_NAME_FORMATSIZE];
 412
 413         REQUIRE(EMPTY(rbtdb->open_versions));
 414         REQUIRE(rbtdb->future_version == NULL);
 415
 416         if (rbtdb->current_version != NULL)
 417                 isc_mem_put(rbtdb->common.mctx, rbtdb->current_version,
 418                             sizeof(rbtdb_version_t));
 419  again:
 420         if (rbtdb->tree != NULL) {
 421                 result = dns_rbt_destroy2(&rbtdb->tree,
 422                                           (rbtdb->task != NULL) ? 1000 : 0);
 423                 if (result == ISC_R_QUOTA) {
 424                         INSIST(rbtdb->task != NULL);
 425                         if (event == NULL)
 426                                 event = isc_event_allocate(rbtdb->common.mctx,
 427                                                            NULL,
 428                                                          DNS_EVENT_FREESTORAGE,
 429                                                            free_rbtdb_callback,
 430                                                            rbtdb,
 431                                                            sizeof(isc_event_t));
 432                         if (event == NULL)
 433                                 goto again;
 434                         isc_task_send(rbtdb->task, &event);
 435                         return;
 436                 }
 437                 INSIST(result == ISC_R_SUCCESS && rbtdb->tree == NULL);
 438         }
 439         if (event != NULL)
 440                 isc_event_free(&event);
 441         if (log) {
 442                 if (dns_name_dynamic(&rbtdb->common.origin))
 443                         dns_name_format(&rbtdb->common.origin, buf,
 444                                         sizeof(buf));
 445                 else
 446                         strcpy(buf, "<UNKNOWN>");
 447                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
 448                               DNS_LOGMODULE_CACHE, ISC_LOG_DEBUG(1),
 449                               "done free_rbtdb(%s)", buf);
 450         }
 451         if (dns_name_dynamic(&rbtdb->common.origin))
 452                 dns_name_free(&rbtdb->common.origin, rbtdb->common.mctx);
 453         for (i = 0; i < rbtdb->node_lock_count; i++)
 454                 DESTROYLOCK(&rbtdb->node_locks[i].lock);
 455         isc_mem_put(rbtdb->common.mctx, rbtdb->node_locks,
 456                     rbtdb->node_lock_count * sizeof(rbtdb_nodelock_t));
 457         isc_rwlock_destroy(&rbtdb->tree_lock);
 458         isc_refcount_destroy(&rbtdb->references);
 459         if (rbtdb->task != NULL)
 460                 isc_task_detach(&rbtdb->task);
 461         DESTROYLOCK(&rbtdb->lock);
 462         rbtdb->common.magic = 0;
 463         rbtdb->common.impmagic = 0;
 464         ondest = rbtdb->common.ondest;
 465         isc_mem_putanddetach(&rbtdb->common.mctx, rbtdb, sizeof(*rbtdb));
 466         isc_ondestroy_notify(&ondest, rbtdb);
 467 }
 468
 469 static inline void
 470 maybe_free_rbtdb(dns_rbtdb_t *rbtdb) {
 471         isc_boolean_t want_free = ISC_FALSE;
 472         unsigned int i;
 473         unsigned int inactive = 0;
 474
 475         /* XXX check for open versions here */
 476
 477         /*
 478          * Even though there are no external direct references, there still
 479          * may be nodes in use.
 480          */
 481         for (i = 0; i < rbtdb->node_lock_count; i++) {
 482                 LOCK(&rbtdb->node_locks[i].lock);
 483                 rbtdb->node_locks[i].exiting = ISC_TRUE;
 484                 if (rbtdb->node_locks[i].references == 0)
 485                         inactive++;
 486                 UNLOCK(&rbtdb->node_locks[i].lock);
 487         }
 488
 489         if (inactive != 0) {
 490                 LOCK(&rbtdb->lock);
 491                 rbtdb->active -= inactive;
 492                 if (rbtdb->active == 0)
 493                         want_free = ISC_TRUE;
 494                 UNLOCK(&rbtdb->lock);
 495                 if (want_free) {
 496                         char buf[DNS_NAME_FORMATSIZE];
 497                         if (dns_name_dynamic(&rbtdb->common.origin))
 498                                 dns_name_format(&rbtdb->common.origin, buf,
 499                                                 sizeof(buf));
 500                         else
 501                                 strcpy(buf, "<UNKNOWN>");
 502                         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
 503                                       DNS_LOGMODULE_CACHE, ISC_LOG_DEBUG(1),
 504                                       "calling free_rbtdb(%s)", buf);
 505                         free_rbtdb(rbtdb, ISC_TRUE, NULL);
 506                 }
 507         }
 508 }
 509
 510 static void
 511 detach(dns_db_t **dbp) {
 512         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)(*dbp);
 513         unsigned int refs;
 514
 515         REQUIRE(VALID_RBTDB(rbtdb));
 516
 517         isc_refcount_decrement(&rbtdb->references, &refs);
 518
 519         if (refs == 0)
 520                 maybe_free_rbtdb(rbtdb);
 521
 522         *dbp = NULL;
 523 }
 524
 525 static void
 526 currentversion(dns_db_t *db, dns_dbversion_t **versionp) {
 527         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
 528         rbtdb_version_t *version;
 529
 530         REQUIRE(VALID_RBTDB(rbtdb));
 531
 532         LOCK(&rbtdb->lock);
 533         version = rbtdb->current_version;
 534         if (version->references == 0)
 535                 PREPEND(rbtdb->open_versions, version, link);
 536         version->references++;
 537         UNLOCK(&rbtdb->lock);
 538
 539         *versionp = (dns_dbversion_t *)version;
 540 }
 541
 542 static inline rbtdb_version_t *
 543 allocate_version(isc_mem_t *mctx, rbtdb_serial_t serial,
 544                  unsigned int references, isc_boolean_t writer)
 545 {
 546         rbtdb_version_t *version;
 547
 548         version = isc_mem_get(mctx, sizeof(*version));
 549         if (version == NULL)
 550                 return (NULL);
 551         version->serial = serial;
 552         version->references = references;
 553         version->writer = writer;
 554         version->commit_ok = ISC_FALSE;
 555         ISC_LIST_INIT(version->changed_list);
 556         ISC_LINK_INIT(version, link);
 557
 558         return (version);
 559 }
 560
 561 static isc_result_t
 562 newversion(dns_db_t *db, dns_dbversion_t **versionp) {
 563         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
 564         rbtdb_version_t *version;
 565
 566         REQUIRE(VALID_RBTDB(rbtdb));
 567         REQUIRE(versionp != NULL && *versionp == NULL);
 568         REQUIRE(rbtdb->future_version == NULL);
 569
 570         LOCK(&rbtdb->lock);
 571         RUNTIME_CHECK(rbtdb->next_serial != 0);         /* XXX Error? */
 572         version = allocate_version(rbtdb->common.mctx, rbtdb->next_serial, 1,
 573                                    ISC_TRUE);
 574         if (version != NULL) {
 575                 version->commit_ok = ISC_TRUE;
 576                 rbtdb->next_serial++;
 577                 rbtdb->future_version = version;
 578         }
 579         UNLOCK(&rbtdb->lock);
 580
 581         if (version == NULL)
 582                 return (ISC_R_NOMEMORY);
 583
 584         *versionp = version;
 585
 586         return (ISC_R_SUCCESS);
 587 }
 588
 589 static void
 590 attachversion(dns_db_t *db, dns_dbversion_t *source,
 591               dns_dbversion_t **targetp)
 592 {
 593         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
 594         rbtdb_version_t *rbtversion = source;
 595
 596         REQUIRE(VALID_RBTDB(rbtdb));
 597
 598         LOCK(&rbtdb->lock);
 599
 600         INSIST(rbtversion->references > 0);
 601         rbtversion->references++;
 602         INSIST(rbtversion->references != 0);
 603
 604         UNLOCK(&rbtdb->lock);
 605
 606         *targetp = rbtversion;
 607 }
 608
 609 static rbtdb_changed_t *
 610 add_changed(dns_rbtdb_t *rbtdb, rbtdb_version_t *version,
 611             dns_rbtnode_t *node)
 612 {
 613         rbtdb_changed_t *changed;
 614
 615         /*
 616          * Caller must be holding the node lock.
 617          */
 618
 619         changed = isc_mem_get(rbtdb->common.mctx, sizeof(*changed));
 620
 621         LOCK(&rbtdb->lock);
 622
 623         REQUIRE(version->writer);
 624
 625         if (changed != NULL) {
 626                 INSIST(node->references > 0);
 627                 node->references++;
 628                 INSIST(node->references != 0);
 629                 changed->node = node;
 630                 changed->dirty = ISC_FALSE;
 631                 ISC_LIST_INITANDAPPEND(version->changed_list, changed, link);
 632         } else
 633                 version->commit_ok = ISC_FALSE;
 634
 635         UNLOCK(&rbtdb->lock);
 636
 637         return (changed);
 638 }
 639
 640 static inline void
 641 free_noqname(isc_mem_t *mctx, struct noqname **noqname) {
 642
 643         if (dns_name_dynamic(&(*noqname)->name))
 644                 dns_name_free(&(*noqname)->name, mctx);
 645         if ((*noqname)->nsec != NULL)
 646                 isc_mem_put(mctx, (*noqname)->nsec,
 647                             dns_rdataslab_size((*noqname)->nsec, 0));
 648         if ((*noqname)->nsec != NULL)
 649                 isc_mem_put(mctx, (*noqname)->nsecsig,
 650                             dns_rdataslab_size((*noqname)->nsecsig, 0));
 651         isc_mem_put(mctx, *noqname, sizeof(**noqname));
 652         *noqname = NULL;
 653 }
 654
 655 static inline void
 656 free_rdataset(isc_mem_t *mctx, rdatasetheader_t *rdataset) {
 657         unsigned int size;
 658
 659         if (rdataset->noqname != NULL)
 660                 free_noqname(mctx, &rdataset->noqname);
 661
 662         if ((rdataset->attributes & RDATASET_ATTR_NONEXISTENT) != 0)
 663                 size = sizeof(*rdataset);
 664         else
 665                 size = dns_rdataslab_size((unsigned char *)rdataset,
 666                                           sizeof(*rdataset));
 667         isc_mem_put(mctx, rdataset, size);
 668 }
 669
 670 static inline void
 671 rollback_node(dns_rbtnode_t *node, rbtdb_serial_t serial) {
 672         rdatasetheader_t *header, *dcurrent;
 673         isc_boolean_t make_dirty = ISC_FALSE;
 674
 675         /*
 676          * Caller must hold the node lock.
 677          */
 678
 679         /*
 680          * We set the IGNORE attribute on rdatasets with serial number
 681          * 'serial'.  When the reference count goes to zero, these rdatasets
 682          * will be cleaned up; until that time, they will be ignored.
 683          */
 684         for (header = node->data; header != NULL; header = header->next) {
 685                 if (header->serial == serial) {
 686                         header->attributes |= RDATASET_ATTR_IGNORE;
 687                         make_dirty = ISC_TRUE;
 688                 }
 689                 for (dcurrent = header->down;
 690                      dcurrent != NULL;
 691                      dcurrent = dcurrent->down) {
 692                         if (dcurrent->serial == serial) {
 693                                 dcurrent->attributes |= RDATASET_ATTR_IGNORE;
 694                                 make_dirty = ISC_TRUE;
 695                         }
 696                 }
 697         }
 698         if (make_dirty)
 699                 node->dirty = 1;
 700 }
 701
 702 static inline void
 703 clean_cache_node(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node) {
 704         rdatasetheader_t *current, *dcurrent, *top_prev, *top_next, *down_next;
 705         isc_mem_t *mctx = rbtdb->common.mctx;
 706
 707         /*
 708          * Caller must be holding the node lock.
 709          */
 710
 711         top_prev = NULL;
 712         for (current = node->data; current != NULL; current = top_next) {
 713                 top_next = current->next;
 714                 dcurrent = current->down;
 715                 if (dcurrent != NULL) {
 716                         do {
 717                                 down_next = dcurrent->down;
 718                                 free_rdataset(mctx, dcurrent);
 719                                 dcurrent = down_next;
 720                         } while (dcurrent != NULL);
 721                         current->down = NULL;
 722                 }
 723                 /*
 724                  * If current is nonexistent or stale, we can clean it up.
 725                  */
 726                 if ((current->attributes &
 727                      (RDATASET_ATTR_NONEXISTENT|RDATASET_ATTR_STALE)) != 0) {
 728                         if (top_prev != NULL)
 729                                 top_prev->next = current->next;
 730                         else
 731                                 node->data = current->next;
 732                         free_rdataset(mctx, current);
 733                 } else
 734                         top_prev = current;
 735         }
 736         node->dirty = 0;
 737 }
 738
 739 static inline void
 740 clean_zone_node(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node,
 741                 rbtdb_serial_t least_serial)
 742 {
 743         rdatasetheader_t *current, *dcurrent, *down_next, *dparent;
 744         rdatasetheader_t *top_prev, *top_next;
 745         isc_mem_t *mctx = rbtdb->common.mctx;
 746         isc_boolean_t still_dirty = ISC_FALSE;
 747
 748         /*
 749          * Caller must be holding the node lock.
 750          */
 751         REQUIRE(least_serial != 0);
 752
 753         top_prev = NULL;
 754         for (current = node->data; current != NULL; current = top_next) {
 755                 top_next = current->next;
 756
 757                 /*
 758                  * First, we clean up any instances of multiple rdatasets
 759                  * with the same serial number, or that have the IGNORE
 760                  * attribute.
 761                  */
 762                 dparent = current;
 763                 for (dcurrent = current->down;
 764                      dcurrent != NULL;
 765                      dcurrent = down_next) {
 766                         down_next = dcurrent->down;
 767                         INSIST(dcurrent->serial <= dparent->serial);
 768                         if (dcurrent->serial == dparent->serial ||
 769                             IGNORE(dcurrent)) {
 770                                 if (down_next != NULL)
 771                                         down_next->next = dparent;
 772                                 dparent->down = down_next;
 773                                 free_rdataset(mctx, dcurrent);
 774                         } else
 775                                 dparent = dcurrent;
 776                 }
 777
 778                 /*
 779                  * We've now eliminated all IGNORE datasets with the possible
 780                  * exception of current, which we now check.
 781                  */
 782                 if (IGNORE(current)) {
 783                         down_next = current->down;
 784                         if (down_next == NULL) {
 785                                 if (top_prev != NULL)
 786                                         top_prev->next = current->next;
 787                                 else
 788                                         node->data = current->next;
 789                                 free_rdataset(mctx, current);
 790                                 /*
 791                                  * current no longer exists, so we can
 792                                  * just continue with the loop.
 793                                  */
 794                                 continue;
 795                         } else {
 796                                 /*
 797                                  * Pull up current->down, making it the new
 798                                  * current.
 799                                  */
 800                                 if (top_prev != NULL)
 801                                         top_prev->next = down_next;
 802                                 else
 803                                         node->data = down_next;
 804                                 down_next->next = top_next;
 805                                 free_rdataset(mctx, current);
 806                                 current = down_next;
 807                         }
 808                 }
 809
 810                 /*
 811                  * We now try to find the first down node less than the
 812                  * least serial.
 813                  */
 814                 dparent = current;
 815                 for (dcurrent = current->down;
 816                      dcurrent != NULL;
 817                      dcurrent = down_next) {
 818                         down_next = dcurrent->down;
 819                         if (dcurrent->serial < least_serial)
 820                                 break;
 821                         dparent = dcurrent;
 822                 }
 823
 824                 /*
 825                  * If there is a such an rdataset, delete it and any older
 826                  * versions.
 827                  */
 828                 if (dcurrent != NULL) {
 829                         do {
 830                                 down_next = dcurrent->down;
 831                                 INSIST(dcurrent->serial <= least_serial);
 832                                 free_rdataset(mctx, dcurrent);
 833                                 dcurrent = down_next;
 834                         } while (dcurrent != NULL);
 835                         dparent->down = NULL;
 836                 }
 837
 838                 /*
 839                  * Note.  The serial number of 'current' might be less than
 840                  * least_serial too, but we cannot delete it because it is
 841                  * the most recent version, unless it is a NONEXISTENT
 842                  * rdataset.
 843                  */
 844                 if (current->down != NULL) {
 845                         still_dirty = ISC_TRUE;
 846                         top_prev = current;
 847                 } else {
 848                         /*
 849                          * If this is a NONEXISTENT rdataset, we can delete it.
 850                          */
 851                         if (NONEXISTENT(current)) {
 852                                 if (top_prev != NULL)
 853                                         top_prev->next = current->next;
 854                                 else
 855                                         node->data = current->next;
 856                                 free_rdataset(mctx, current);
 857                         } else
 858                                 top_prev = current;
 859                 }
 860         }
 861         if (!still_dirty)
 862                 node->dirty = 0;
 863 }
 864
 865 static inline void
 866 new_reference(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node) {
 867         if (node->references == 0) {
 868                 rbtdb->node_locks[node->locknum].references++;
 869                 INSIST(rbtdb->node_locks[node->locknum].references != 0);
 870         }
 871         node->references++;
 872         INSIST(node->references != 0);
 873 }
 874
 875 static void
 876 no_references(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node,
 877               rbtdb_serial_t least_serial, isc_rwlocktype_t lock)
 878 {
 879         isc_result_t result;
 880         isc_boolean_t write_locked;
 881         unsigned int locknum;
 882
 883         /*
 884          * Caller must be holding the node lock.
 885          */
 886
 887         REQUIRE(node->references == 0);
 888
 889         if (node->dirty) {
 890                 if (IS_CACHE(rbtdb))
 891                         clean_cache_node(rbtdb, node);
 892                 else {
 893                         if (least_serial == 0) {
 894                                 /*
 895                                  * Caller doesn't know the least serial.
 896                                  * Get it.
 897                                  */
 898                                 LOCK(&rbtdb->lock);
 899                                 least_serial = rbtdb->least_serial;
 900                                 UNLOCK(&rbtdb->lock);
 901                         }
 902                         clean_zone_node(rbtdb, node, least_serial);
 903                 }
 904         }
 905
 906         locknum = node->locknum;
 907
 908         INSIST(rbtdb->node_locks[locknum].references > 0);
 909         rbtdb->node_locks[locknum].references--;
 910
 911         /*
 912          * XXXDCL should this only be done for cache zones?
 913          */
 914         if (node->data != NULL || node->down != NULL)
 915                 return;
 916
 917         /*
 918          * XXXDCL need to add a deferred delete method for ISC_R_LOCKBUSY.
 919          */
 920         if (lock != isc_rwlocktype_write) {
 921                 /*
 922                  * Locking hierarchy notwithstanding, we don't need to free
 923                  * the node lock before acquiring the tree write lock because
 924                  * we only do a trylock.
 925                  */
 926                 if (lock == isc_rwlocktype_read)
 927                         result = isc_rwlock_tryupgrade(&rbtdb->tree_lock);
 928                 else
 929                         result = isc_rwlock_trylock(&rbtdb->tree_lock,
 930                                                     isc_rwlocktype_write);
 931                 RUNTIME_CHECK(result == ISC_R_SUCCESS ||
 932                               result == ISC_R_LOCKBUSY);
 933
 934                 write_locked = ISC_TF(result == ISC_R_SUCCESS);
 935         } else
 936                 write_locked = ISC_TRUE;
 937
 938         if (write_locked) {
 939                 if (isc_log_wouldlog(dns_lctx, ISC_LOG_DEBUG(1))) {
 940                         char printname[DNS_NAME_FORMATSIZE];
 941
 942                         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
 943                                       DNS_LOGMODULE_CACHE, ISC_LOG_DEBUG(1),
 944                                       "no_references: delete from rbt: %p %s",
 945                                       node,
 946                                       dns_rbt_formatnodename(node, printname,
 947                                                            sizeof(printname)));
 948                 }
 949
 950                 result = dns_rbt_deletenode(rbtdb->tree, node, ISC_FALSE);
 951                 if (result != ISC_R_SUCCESS)
 952                         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
 953                                       DNS_LOGMODULE_CACHE, ISC_LOG_WARNING,
 954                                       "no_references: dns_rbt_deletenode: %s",
 955                                       isc_result_totext(result));
 956         }
 957
 958         /*
 959          * Relock a read lock, or unlock the write lock if no lock was held.
 960          */
 961         if (lock == isc_rwlocktype_none)
 962                 if (write_locked)
 963                         RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_write);
 964
 965         if (lock == isc_rwlocktype_read)
 966                 if (write_locked)
 967                         isc_rwlock_downgrade(&rbtdb->tree_lock);
 968 }
 969
 970 static inline void
 971 make_least_version(dns_rbtdb_t *rbtdb, rbtdb_version_t *version,
 972                    rbtdb_changedlist_t *cleanup_list)
 973 {
 974         /*
 975          * Caller must be holding the database lock.
 976          */
 977
 978         rbtdb->least_serial = version->serial;
 979         *cleanup_list = version->changed_list;
 980         ISC_LIST_INIT(version->changed_list);
 981 }
 982
 983 static inline void
 984 cleanup_nondirty(rbtdb_version_t *version, rbtdb_changedlist_t *cleanup_list) {
 985         rbtdb_changed_t *changed, *next_changed;
 986
 987         /*
 988          * If the changed record is dirty, then
 989          * an update created multiple versions of
 990          * a given rdataset.  We keep this list
 991          * until we're the least open version, at
 992          * which point it's safe to get rid of any
 993          * older versions.
 994          *
 995          * If the changed record isn't dirty, then
 996          * we don't need it anymore since we're
 997          * committing and not rolling back.
 998          *
 999          * The caller must be holding the database lock.
1000          */
1001         for (changed = HEAD(version->changed_list);
1002              changed != NULL;
1003              changed = next_changed) {
1004                 next_changed = NEXT(changed, link);
1005                 if (!changed->dirty) {
1006                         UNLINK(version->changed_list,
1007                                changed, link);
1008                         APPEND(*cleanup_list,
1009                                changed, link);
1010                 }
1011         }
1012 }
1013
1014 static isc_boolean_t
1015 iszonesecure(dns_db_t *db, dns_dbnode_t *origin) {
1016         dns_rdataset_t keyset;
1017         dns_rdataset_t nsecset, signsecset;
1018         isc_boolean_t haszonekey = ISC_FALSE;
1019         isc_boolean_t hasnsec = ISC_FALSE;
1020         isc_result_t result;
1021
1022         dns_rdataset_init(&keyset);
1023         result = dns_db_findrdataset(db, origin, NULL, dns_rdatatype_dnskey, 0,
1024                                      0, &keyset, NULL);
1025         if (result == ISC_R_SUCCESS) {
1026                 dns_rdata_t keyrdata = DNS_RDATA_INIT;
1027                 result = dns_rdataset_first(&keyset);
1028                 while (result == ISC_R_SUCCESS) {
1029                         dns_rdataset_current(&keyset, &keyrdata);
1030                         if (dns_zonekey_iszonekey(&keyrdata)) {
1031                                 haszonekey = ISC_TRUE;
1032                                 break;
1033                         }
1034                         result = dns_rdataset_next(&keyset);
1035                 }
1036                 dns_rdataset_disassociate(&keyset);
1037         }
1038         if (!haszonekey)
1039                 return (ISC_FALSE);
1040
1041         dns_rdataset_init(&nsecset);
1042         dns_rdataset_init(&signsecset);
1043         result = dns_db_findrdataset(db, origin, NULL, dns_rdatatype_nsec, 0,
1044                                      0, &nsecset, &signsecset);
1045         if (result == ISC_R_SUCCESS) {
1046                 if (dns_rdataset_isassociated(&signsecset)) {
1047                         hasnsec = ISC_TRUE;
1048                         dns_rdataset_disassociate(&signsecset);
1049                 }
1050                 dns_rdataset_disassociate(&nsecset);
1051         }
1052         return (hasnsec);
1053 }
1054
1055 static void
1056 closeversion(dns_db_t *db, dns_dbversion_t **versionp, isc_boolean_t commit) {
1057         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
1058         rbtdb_version_t *version, *cleanup_version, *least_greater;
1059         isc_boolean_t rollback = ISC_FALSE;
1060         rbtdb_changedlist_t cleanup_list;
1061         rbtdb_changed_t *changed, *next_changed;
1062         rbtdb_serial_t serial, least_serial;
1063         dns_rbtnode_t *rbtnode;
1064         isc_mutex_t *lock;
1065
1066         REQUIRE(VALID_RBTDB(rbtdb));
1067         version = (rbtdb_version_t *)*versionp;
1068
1069         cleanup_version = NULL;
1070         ISC_LIST_INIT(cleanup_list);
1071
1072         LOCK(&rbtdb->lock);
1073         INSIST(version->references > 0);
1074         INSIST(!version->writer || !(commit && version->references > 1));
1075         version->references--;
1076         serial = version->serial;
1077         if (version->references == 0) {
1078                 if (version->writer) {
1079                         if (commit) {
1080                                 INSIST(version->commit_ok);
1081                                 INSIST(version == rbtdb->future_version);
1082                                 if (EMPTY(rbtdb->open_versions)) {
1083                                         /*
1084                                          * We're going to become the least open
1085                                          * version.
1086                                          */
1087                                         make_least_version(rbtdb, version,
1088                                                            &cleanup_list);
1089                                 } else {
1090                                         /*
1091                                          * Some other open version is the
1092                                          * least version.  We can't cleanup
1093                                          * records that were changed in this
1094                                          * version because the older versions
1095                                          * may still be in use by an open
1096                                          * version.
1097                                          *
1098                                          * We can, however, discard the
1099                                          * changed records for things that
1100                                          * we've added that didn't exist in
1101                                          * prior versions.
1102                                          */
1103                                         cleanup_nondirty(version,
1104                                                          &cleanup_list);
1105                                 }
1106                                 /*
1107                                  * If the (soon to be former) current version
1108                                  * isn't being used by anyone, we can clean
1109                                  * it up.
1110                                  */
1111                                 if (rbtdb->current_version->references == 0) {
1112                                         cleanup_version =
1113                                                 rbtdb->current_version;
1114                                         APPENDLIST(version->changed_list,
1115                                                  cleanup_version->changed_list,
1116                                                    link);
1117                                 }
1118                                 /*
1119                                  * Become the current version.
1120                                  */
1121                                 version->writer = ISC_FALSE;
1122                                 rbtdb->current_version = version;
1123                                 rbtdb->current_serial = version->serial;
1124                                 rbtdb->future_version = NULL;
1125                         } else {
1126                                 /*
1127                                  * We're rolling back this transaction.
1128                                  */
1129                                 cleanup_list = version->changed_list;
1130                                 ISC_LIST_INIT(version->changed_list);
1131                                 rollback = ISC_TRUE;
1132                                 cleanup_version = version;
1133                                 rbtdb->future_version = NULL;
1134                         }
1135                 } else {
1136                         if (version != rbtdb->current_version) {
1137                                 /*
1138                                  * There are no external or internal references
1139                                  * to this version and it can be cleaned up.
1140                                  */
1141                                 cleanup_version = version;
1142
1143                                 /*
1144                                  * Find the version with the least serial
1145                                  * number greater than ours.
1146                                  */
1147                                 least_greater = PREV(version, link);
1148                                 if (least_greater == NULL)
1149                                         least_greater = rbtdb->current_version;
1150
1151                                 INSIST(version->serial < least_greater->serial);
1152                                 /*
1153                                  * Is this the least open version?
1154                                  */
1155                                 if (version->serial == rbtdb->least_serial) {
1156                                         /*
1157                                          * Yes.  Install the new least open
1158                                          * version.
1159                                          */
1160                                         make_least_version(rbtdb,
1161                                                            least_greater,
1162                                                            &cleanup_list);
1163                                 } else {
1164                                         /*
1165                                          * Add any unexecuted cleanups to
1166                                          * those of the least greater version.
1167                                          */
1168                                         APPENDLIST(least_greater->changed_list,
1169                                                    version->changed_list,
1170                                                    link);
1171                                 }
1172                         } else if (version->serial == rbtdb->least_serial)
1173                                 INSIST(EMPTY(version->changed_list));
1174                         UNLINK(rbtdb->open_versions, version, link);
1175                 }
1176         }
1177         least_serial = rbtdb->least_serial;
1178         UNLOCK(&rbtdb->lock);
1179
1180         /*
1181          * Update the zone's secure status.
1182          */
1183         if (version->writer && commit && !IS_CACHE(rbtdb))
1184                 rbtdb->secure = iszonesecure(db, rbtdb->origin_node);
1185
1186         if (cleanup_version != NULL) {
1187                 INSIST(EMPTY(cleanup_version->changed_list));
1188                 isc_mem_put(rbtdb->common.mctx, cleanup_version,
1189                             sizeof(*cleanup_version));
1190         }
1191
1192         if (!EMPTY(cleanup_list)) {
1193                 for (changed = HEAD(cleanup_list);
1194                      changed != NULL;
1195                      changed = next_changed) {
1196                         next_changed = NEXT(changed, link);
1197                         rbtnode = changed->node;
1198                         lock = &rbtdb->node_locks[rbtnode->locknum].lock;
1199
1200                         LOCK(lock);
1201
1202                         INSIST(rbtnode->references > 0);
1203                         rbtnode->references--;
1204                         if (rollback)
1205                                 rollback_node(rbtnode, serial);
1206
1207                         if (rbtnode->references == 0)
1208                                 no_references(rbtdb, rbtnode, least_serial,
1209                                               isc_rwlocktype_none);
1210
1211                         UNLOCK(lock);
1212
1213                         isc_mem_put(rbtdb->common.mctx, changed,
1214                                     sizeof(*changed));
1215                 }
1216         }
1217
1218         *versionp = NULL;
1219 }
1220
1221 /*
1222  * Add the necessary magic for the wildcard name 'name'
1223  * to be found in 'rbtdb'.
1224  *
1225  * In order for wildcard matching to work correctly in
1226  * zone_find(), we must ensure that a node for the wildcarding
1227  * level exists in the database, and has its 'find_callback'
1228  * and 'wild' bits set.
1229  *
1230  * E.g. if the wildcard name is "*.sub.example." then we
1231  * must ensure that "sub.example." exists and is marked as
1232  * a wildcard level.
1233  */
1234 static isc_result_t
1235 add_wildcard_magic(dns_rbtdb_t *rbtdb, dns_name_t *name) {
1236         isc_result_t result;
1237         dns_name_t foundname;
1238         dns_offsets_t offsets;
1239         unsigned int n;
1240         dns_rbtnode_t *node = NULL;
1241
1242         dns_name_init(&foundname, offsets);
1243         n = dns_name_countlabels(name);
1244         INSIST(n >= 2);
1245         n--;
1246         dns_name_getlabelsequence(name, 1, n, &foundname);
1247         result = dns_rbt_addnode(rbtdb->tree, &foundname, &node);
1248         if (result != ISC_R_SUCCESS && result != ISC_R_EXISTS)
1249                 return (result);
1250         node->find_callback = 1;
1251         node->wild = 1;
1252         return (ISC_R_SUCCESS);
1253 }
1254
1255 static isc_result_t
1256 add_empty_wildcards(dns_rbtdb_t *rbtdb, dns_name_t *name) {
1257         isc_result_t result;
1258         dns_name_t foundname;
1259         dns_offsets_t offsets;
1260         unsigned int n, l, i;
1261
1262         dns_name_init(&foundname, offsets);
1263         n = dns_name_countlabels(name);
1264         l = dns_name_countlabels(&rbtdb->common.origin);
1265         i = l + 1;
1266         while (i < n) {
1267                 dns_rbtnode_t *node = NULL;     /* dummy */
1268                 dns_name_getlabelsequence(name, n - i, i, &foundname);
1269                 if (dns_name_iswildcard(&foundname)) {
1270                         result = add_wildcard_magic(rbtdb, &foundname);
1271                         if (result != ISC_R_SUCCESS)
1272                                 return (result);
1273                         result = dns_rbt_addnode(rbtdb->tree, &foundname,
1274                                                  &node);
1275                         if (result != ISC_R_SUCCESS && result != ISC_R_EXISTS)
1276                                 return (result);
1277                 }
1278                 i++;
1279         }
1280         return (ISC_R_SUCCESS);
1281 }
1282
1283 static isc_result_t
1284 findnode(dns_db_t *db, dns_name_t *name, isc_boolean_t create,
1285          dns_dbnode_t **nodep)
1286 {
1287         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
1288         dns_rbtnode_t *node = NULL;
1289         dns_name_t nodename;
1290         unsigned int locknum;
1291         isc_result_t result;
1292         isc_rwlocktype_t locktype = isc_rwlocktype_read;
1293
1294         REQUIRE(VALID_RBTDB(rbtdb));
1295
1296         dns_name_init(&nodename, NULL);
1297         RWLOCK(&rbtdb->tree_lock, locktype);
1298         result = dns_rbt_findnode(rbtdb->tree, name, NULL, &node, NULL,
1299                                   DNS_RBTFIND_EMPTYDATA, NULL, NULL);
1300         if (result != ISC_R_SUCCESS) {
1301                 RWUNLOCK(&rbtdb->tree_lock, locktype);
1302                 if (!create) {
1303                         if (result == DNS_R_PARTIALMATCH)
1304                                 result = ISC_R_NOTFOUND;
1305                         return (result);
1306                 }
1307                 /*
1308                  * It would be nice to try to upgrade the lock instead of
1309                  * unlocking then relocking.
1310                  */
1311                 locktype = isc_rwlocktype_write;
1312                 RWLOCK(&rbtdb->tree_lock, locktype);
1313                 node = NULL;
1314                 result = dns_rbt_addnode(rbtdb->tree, name, &node);
1315                 if (result == ISC_R_SUCCESS) {
1316                         dns_rbt_namefromnode(node, &nodename);
1317 #ifdef DNS_RBT_USEHASH
1318                         node->locknum = node->hashval % rbtdb->node_lock_count;
1319 #else
1320                         node->locknum = dns_name_hash(&nodename, ISC_TRUE) %
1321                                 rbtdb->node_lock_count;
1322 #endif
1323                         add_empty_wildcards(rbtdb, name);
1324
1325                         if (dns_name_iswildcard(name)) {
1326                                 result = add_wildcard_magic(rbtdb, name);
1327                                 if (result != ISC_R_SUCCESS) {
1328                                         RWUNLOCK(&rbtdb->tree_lock, locktype);
1329                                         return (result);
1330                                 }
1331                         }
1332                 } else if (result != ISC_R_EXISTS) {
1333                         RWUNLOCK(&rbtdb->tree_lock, locktype);
1334                         return (result);
1335                 }
1336         }
1337         locknum = node->locknum;
1338         LOCK(&rbtdb->node_locks[locknum].lock);
1339         new_reference(rbtdb, node);
1340         UNLOCK(&rbtdb->node_locks[locknum].lock);
1341         RWUNLOCK(&rbtdb->tree_lock, locktype);
1342
1343         *nodep = (dns_dbnode_t *)node;
1344
1345         return (ISC_R_SUCCESS);
1346 }
1347
1348 static isc_result_t
1349 zone_zonecut_callback(dns_rbtnode_t *node, dns_name_t *name, void *arg) {
1350         rbtdb_search_t *search = arg;
1351         rdatasetheader_t *header, *header_next;
1352         rdatasetheader_t *dname_header, *sigdname_header, *ns_header;
1353         rdatasetheader_t *found;
1354         isc_result_t result;
1355         dns_rbtnode_t *onode;
1356
1357         /*
1358          * We only want to remember the topmost zone cut, since it's the one
1359          * that counts, so we'll just continue if we've already found a
1360          * zonecut.
1361          */
1362         if (search->zonecut != NULL)
1363                 return (DNS_R_CONTINUE);
1364
1365         found = NULL;
1366         result = DNS_R_CONTINUE;
1367         onode = search->rbtdb->origin_node;
1368
1369         LOCK(&(search->rbtdb->node_locks[node->locknum].lock));
1370
1371         /*
1372          * Look for an NS or DNAME rdataset active in our version.
1373          */
1374         ns_header = NULL;
1375         dname_header = NULL;
1376         sigdname_header = NULL;
1377         for (header = node->data; header != NULL; header = header_next) {
1378                 header_next = header->next;
1379                 if (header->type == dns_rdatatype_ns ||
1380                     header->type == dns_rdatatype_dname ||
1381                     header->type == RBTDB_RDATATYPE_SIGDNAME) {
1382                         do {
1383                                 if (header->serial <= search->serial &&
1384                                     !IGNORE(header)) {
1385                                         /*
1386                                          * Is this a "this rdataset doesn't
1387                                          * exist" record?
1388                                          */
1389                                         if (NONEXISTENT(header))
1390                                                 header = NULL;
1391                                         break;
1392                                 } else
1393                                         header = header->down;
1394                         } while (header != NULL);
1395                         if (header != NULL) {
1396                                 if (header->type == dns_rdatatype_dname)
1397                                         dname_header = header;
1398                                 else if (header->type ==
1399                                            RBTDB_RDATATYPE_SIGDNAME)
1400                                         sigdname_header = header;
1401                                 else if (node != onode ||
1402                                          IS_STUB(search->rbtdb)) {
1403                                         /*
1404                                          * We've found an NS rdataset that
1405                                          * isn't at the origin node.  We check
1406                                          * that they're not at the origin node,
1407                                          * because otherwise we'd erroneously
1408                                          * treat the zone top as if it were
1409                                          * a delegation.
1410                                          */
1411                                         ns_header = header;
1412                                 }
1413                         }
1414                 }
1415         }
1416
1417         /*
1418          * Did we find anything?
1419          */
1420         if (dname_header != NULL) {
1421                 /*
1422                  * Note that DNAME has precedence over NS if both exist.
1423                  */
1424                 found = dname_header;
1425                 search->zonecut_sigrdataset = sigdname_header;
1426         } else if (ns_header != NULL) {
1427                 found = ns_header;
1428                 search->zonecut_sigrdataset = NULL;
1429         }
1430
1431         if (found != NULL) {
1432                 /*
1433                  * We increment the reference count on node to ensure that
1434                  * search->zonecut_rdataset will still be valid later.
1435                  */
1436                 new_reference(search->rbtdb, node);
1437                 search->zonecut = node;
1438                 search->zonecut_rdataset = found;
1439                 search->need_cleanup = ISC_TRUE;
1440                 /*
1441                  * Since we've found a zonecut, anything beneath it is
1442                  * glue and is not subject to wildcard matching, so we
1443                  * may clear search->wild.
1444                  */
1445                 search->wild = ISC_FALSE;
1446                 if ((search->options & DNS_DBFIND_GLUEOK) == 0) {
1447                         /*
1448                          * If the caller does not want to find glue, then
1449                          * this is the best answer and the search should
1450                          * stop now.
1451                          */
1452                         result = DNS_R_PARTIALMATCH;
1453                 } else {
1454                         dns_name_t *zcname;
1455
1456                         /*
1457                          * The search will continue beneath the zone cut.
1458                          * This may or may not be the best match.  In case it
1459                          * is, we need to remember the node name.
1460                          */
1461                         zcname = dns_fixedname_name(&search->zonecut_name);
1462                         RUNTIME_CHECK(dns_name_copy(name, zcname, NULL) ==
1463                                       ISC_R_SUCCESS);
1464                         search->copy_name = ISC_TRUE;
1465                 }
1466         } else {
1467                 /*
1468                  * There is no zonecut at this node which is active in this
1469                  * version.
1470                  *
1471                  * If this is a "wild" node and the caller hasn't disabled
1472                  * wildcard matching, remember that we've seen a wild node
1473                  * in case we need to go searching for wildcard matches
1474                  * later on.
1475                  */
1476                 if (node->wild && (search->options & DNS_DBFIND_NOWILD) == 0)
1477                         search->wild = ISC_TRUE;
1478         }
1479
1480         UNLOCK(&(search->rbtdb->node_locks[node->locknum].lock));
1481
1482         return (result);
1483 }
1484
1485 static inline void
1486 bind_rdataset(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node,
1487               rdatasetheader_t *header, isc_stdtime_t now,
1488               dns_rdataset_t *rdataset)
1489 {
1490         unsigned char *raw;
1491
1492         /*
1493          * Caller must be holding the node lock.
1494          */
1495
1496         if (rdataset == NULL)
1497                 return;
1498
1499         new_reference(rbtdb, node);
1500
1501         INSIST(rdataset->methods == NULL);      /* We must be disassociated. */
1502
1503         rdataset->methods = &rdataset_methods;
1504         rdataset->rdclass = rbtdb->common.rdclass;
1505         rdataset->type = RBTDB_RDATATYPE_BASE(header->type);
1506         rdataset->covers = RBTDB_RDATATYPE_EXT(header->type);
1507         rdataset->ttl = header->ttl - now;
1508         rdataset->trust = header->trust;
1509         if (NXDOMAIN(header))
1510                 rdataset->attributes |= DNS_RDATASETATTR_NXDOMAIN;
1511         rdataset->private1 = rbtdb;
1512         rdataset->private2 = node;
1513         raw = (unsigned char *)header + sizeof(*header);
1514         rdataset->private3 = raw;
1515         rdataset->count = header->count++;
1516         if (header->count == ISC_UINT32_MAX)
1517                 header->count = 0;
1518
1519         /*
1520          * Reset iterator state.
1521          */
1522         rdataset->privateuint4 = 0;
1523         rdataset->private5 = NULL;
1524
1525         /*
1526          * Add noqname proof.
1527          */
1528         rdataset->private6 = header->noqname;
1529         if (rdataset->private6 != NULL)
1530                 rdataset->attributes |=  DNS_RDATASETATTR_NOQNAME;
1531 }
1532
1533 static inline isc_result_t
1534 setup_delegation(rbtdb_search_t *search, dns_dbnode_t **nodep,
1535                  dns_name_t *foundname, dns_rdataset_t *rdataset,
1536                  dns_rdataset_t *sigrdataset)
1537 {
1538         isc_result_t result;
1539         dns_name_t *zcname;
1540         rbtdb_rdatatype_t type;
1541         dns_rbtnode_t *node;
1542
1543         /*
1544          * The caller MUST NOT be holding any node locks.
1545          */
1546
1547         node = search->zonecut;
1548         type = search->zonecut_rdataset->type;
1549
1550         /*
1551          * If we have to set foundname, we do it before anything else.
1552          * If we were to set foundname after we had set nodep or bound the
1553          * rdataset, then we'd have to undo that work if dns_name_copy()
1554          * failed.  By setting foundname first, there's nothing to undo if
1555          * we have trouble.
1556          */
1557         if (foundname != NULL && search->copy_name) {
1558                 zcname = dns_fixedname_name(&search->zonecut_name);
1559                 result = dns_name_copy(zcname, foundname, NULL);
1560                 if (result != ISC_R_SUCCESS)
1561                         return (result);
1562         }
1563         if (nodep != NULL) {
1564                 /*
1565                  * Note that we don't have to increment the node's reference
1566                  * count here because we're going to use the reference we
1567                  * already have in the search block.
1568                  */
1569                 *nodep = node;
1570                 search->need_cleanup = ISC_FALSE;
1571         }
1572         if (rdataset != NULL) {
1573                 LOCK(&(search->rbtdb->node_locks[node->locknum].lock));
1574                 bind_rdataset(search->rbtdb, node, search->zonecut_rdataset,
1575                               search->now, rdataset);
1576                 if (sigrdataset != NULL && search->zonecut_sigrdataset != NULL)
1577                         bind_rdataset(search->rbtdb, node,
1578                                       search->zonecut_sigrdataset,
1579                                       search->now, sigrdataset);
1580                 UNLOCK(&(search->rbtdb->node_locks[node->locknum].lock));
1581         }
1582
1583         if (type == dns_rdatatype_dname)
1584                 return (DNS_R_DNAME);
1585         return (DNS_R_DELEGATION);
1586 }
1587
1588 static inline isc_boolean_t
1589 valid_glue(rbtdb_search_t *search, dns_name_t *name, rbtdb_rdatatype_t type,
1590            dns_rbtnode_t *node)
1591 {
1592         unsigned char *raw;
1593         unsigned int count, size;
1594         dns_name_t ns_name;
1595         isc_boolean_t valid = ISC_FALSE;
1596         dns_offsets_t offsets;
1597         isc_region_t region;
1598         rdatasetheader_t *header;
1599
1600         /*
1601          * No additional locking is required.
1602          */
1603
1604         /*
1605          * Valid glue types are A, AAAA, A6.  NS is also a valid glue type
1606          * if it occurs at a zone cut, but is not valid below it.
1607          */
1608         if (type == dns_rdatatype_ns) {
1609                 if (node != search->zonecut) {
1610                         return (ISC_FALSE);
1611                 }
1612         } else if (type != dns_rdatatype_a &&
1613                    type != dns_rdatatype_aaaa &&
1614                    type != dns_rdatatype_a6) {
1615                 return (ISC_FALSE);
1616         }
1617
1618         header = search->zonecut_rdataset;
1619         raw = (unsigned char *)header + sizeof(*header);
1620         count = raw[0] * 256 + raw[1];
1621         raw += 2;
1622
1623         while (count > 0) {
1624                 count--;
1625                 size = raw[0] * 256 + raw[1];
1626                 raw += 2;
1627                 region.base = raw;
1628                 region.length = size;
1629                 raw += size;
1630                 /*
1631                  * XXX Until we have rdata structures, we have no choice but
1632                  * to directly access the rdata format.
1633                  */
1634                 dns_name_init(&ns_name, offsets);
1635                 dns_name_fromregion(&ns_name, &region);
1636                 if (dns_name_compare(&ns_name, name) == 0) {
1637                         valid = ISC_TRUE;
1638                         break;
1639                 }
1640         }
1641
1642         return (valid);
1643 }
1644
1645 static inline isc_boolean_t
1646 activeempty(rbtdb_search_t *search, dns_rbtnodechain_t *chain,
1647             dns_name_t *name)
1648 {
1649         dns_fixedname_t fnext;
1650         dns_fixedname_t forigin;
1651         dns_name_t *next;
1652         dns_name_t *origin;
1653         dns_name_t prefix;
1654         dns_rbtdb_t *rbtdb;
1655         dns_rbtnode_t *node;
1656         isc_result_t result;
1657         isc_boolean_t answer = ISC_FALSE;
1658         rdatasetheader_t *header;
1659
1660         rbtdb = search->rbtdb;
1661
1662         dns_name_init(&prefix, NULL);
1663         dns_fixedname_init(&fnext);
1664         next = dns_fixedname_name(&fnext);
1665         dns_fixedname_init(&forigin);
1666         origin = dns_fixedname_name(&forigin);
1667
1668         result = dns_rbtnodechain_next(chain, NULL, NULL);
1669         while (result == ISC_R_SUCCESS || result == DNS_R_NEWORIGIN) {
1670                 node = NULL;
1671                 result = dns_rbtnodechain_current(chain, &prefix,
1672                                                   origin, &node);
1673                 if (result != ISC_R_SUCCESS)
1674                         break;
1675                 LOCK(&(rbtdb->node_locks[node->locknum].lock));
1676                 for (header = node->data;
1677                      header != NULL;
1678                      header = header->next) {
1679                         if (header->serial <= search->serial &&
1680                             !IGNORE(header) && EXISTS(header))
1681                                 break;
1682                 }
1683                 UNLOCK(&(rbtdb->node_locks[node->locknum].lock));
1684                 if (header != NULL)
1685                         break;
1686                 result = dns_rbtnodechain_next(chain, NULL, NULL);
1687         }
1688         if (result == ISC_R_SUCCESS)
1689                 result = dns_name_concatenate(&prefix, origin, next, NULL);
1690         if (result == ISC_R_SUCCESS && dns_name_issubdomain(next, name))
1691                 answer = ISC_TRUE;
1692         return (answer);
1693 }
1694
1695 static inline isc_boolean_t
1696 activeemtpynode(rbtdb_search_t *search, dns_name_t *qname, dns_name_t *wname) {
1697         dns_fixedname_t fnext;
1698         dns_fixedname_t forigin;
1699         dns_fixedname_t fprev;
1700         dns_name_t *next;
1701         dns_name_t *origin;
1702         dns_name_t *prev;
1703         dns_name_t name;
1704         dns_name_t rname;
1705         dns_name_t tname;
1706         dns_rbtdb_t *rbtdb;
1707         dns_rbtnode_t *node;
1708         dns_rbtnodechain_t chain;
1709         isc_boolean_t check_next = ISC_TRUE;
1710         isc_boolean_t check_prev = ISC_TRUE;
1711         isc_boolean_t answer = ISC_FALSE;
1712         isc_result_t result;
1713         rdatasetheader_t *header;
1714         unsigned int n;
1715
1716         rbtdb = search->rbtdb;
1717
1718         dns_name_init(&name, NULL);
1719         dns_name_init(&tname, NULL);
1720         dns_name_init(&rname, NULL);
1721         dns_fixedname_init(&fnext);
1722         next = dns_fixedname_name(&fnext);
1723         dns_fixedname_init(&fprev);
1724         prev = dns_fixedname_name(&fprev);
1725         dns_fixedname_init(&forigin);
1726         origin = dns_fixedname_name(&forigin);
1727
1728         /*
1729          * Find if qname is at or below a empty node.
1730          * Use our own copy of the chain.
1731          */
1732
1733         chain = search->chain;
1734         do {
1735                 node = NULL;
1736                 result = dns_rbtnodechain_current(&chain, &name,
1737                                                   origin, &node);
1738                 if (result != ISC_R_SUCCESS)
1739                         break;
1740                 LOCK(&(rbtdb->node_locks[node->locknum].lock));
1741                 for (header = node->data;
1742                      header != NULL;
1743                      header = header->next) {
1744                         if (header->serial <= search->serial &&
1745                             !IGNORE(header) && EXISTS(header))
1746                                 break;
1747                 }
1748                 UNLOCK(&(rbtdb->node_locks[node->locknum].lock));
1749                 if (header != NULL)
1750                         break;
1751                 result = dns_rbtnodechain_prev(&chain, NULL, NULL);
1752         } while (result == ISC_R_SUCCESS || result == DNS_R_NEWORIGIN);
1753         if (result == ISC_R_SUCCESS)
1754                 result = dns_name_concatenate(&name, origin, prev, NULL);
1755         if (result != ISC_R_SUCCESS)
1756                 check_prev = ISC_FALSE;
1757
1758         result = dns_rbtnodechain_next(&chain, NULL, NULL);
1759         while (result == ISC_R_SUCCESS || result == DNS_R_NEWORIGIN) {
1760                 node = NULL;
1761                 result = dns_rbtnodechain_current(&chain, &name,
1762                                                   origin, &node);
1763                 if (result != ISC_R_SUCCESS)
1764                         break;
1765                 LOCK(&(rbtdb->node_locks[node->locknum].lock));
1766                 for (header = node->data;
1767                      header != NULL;
1768                      header = header->next) {
1769                         if (header->serial <= search->serial &&
1770                             !IGNORE(header) && EXISTS(header))
1771                                 break;
1772                 }
1773                 UNLOCK(&(rbtdb->node_locks[node->locknum].lock));
1774                 if (header != NULL)
1775                         break;
1776                 result = dns_rbtnodechain_next(&chain, NULL, NULL);
1777         }
1778         if (result == ISC_R_SUCCESS)
1779                 result = dns_name_concatenate(&name, origin, next, NULL);
1780         if (result != ISC_R_SUCCESS)
1781                 check_next = ISC_FALSE;
1782
1783         dns_name_clone(qname, &rname);
1784
1785         /*
1786          * Remove the wildcard label to find the terminal name.
1787          */
1788         n = dns_name_countlabels(wname);
1789         dns_name_getlabelsequence(wname, 1, n - 1, &tname);
1790
1791         do {
1792                 if ((check_prev && dns_name_issubdomain(prev, &rname)) ||
1793                     (check_next && dns_name_issubdomain(next, &rname))) {
1794                         answer = ISC_TRUE;
1795                         break;
1796                 }
1797                 /*
1798                  * Remove the left hand label.
1799                  */
1800                 n = dns_name_countlabels(&rname);
1801                 dns_name_getlabelsequence(&rname, 1, n - 1, &rname);
1802         } while (!dns_name_equal(&rname, &tname));
1803         return (answer);
1804 }
1805
1806 static inline isc_result_t
1807 find_wildcard(rbtdb_search_t *search, dns_rbtnode_t **nodep,
1808               dns_name_t *qname)
1809 {
1810         unsigned int i, j;
1811         dns_rbtnode_t *node, *level_node, *wnode;
1812         rdatasetheader_t *header;
1813         isc_result_t result = ISC_R_NOTFOUND;
1814         dns_name_t name;
1815         dns_name_t *wname;
1816         dns_fixedname_t fwname;
1817         dns_rbtdb_t *rbtdb;
1818         isc_boolean_t done, wild, active;
1819         dns_rbtnodechain_t wchain;
1820
1821         /*
1822          * Caller must be holding the tree lock and MUST NOT be holding
1823          * any node locks.
1824          */
1825
1826         /*
1827          * Examine each ancestor level.  If the level's wild bit
1828          * is set, then construct the corresponding wildcard name and
1829          * search for it.  If the wildcard node exists, and is active in
1830          * this version, we're done.  If not, then we next check to see
1831          * if the ancestor is active in this version.  If so, then there
1832          * can be no possible wildcard match and again we're done.  If not,
1833          * continue the search.
1834          */
1835
1836         rbtdb = search->rbtdb;
1837         i = search->chain.level_matches;
1838         done = ISC_FALSE;
1839         node = *nodep;
1840         do {
1841                 LOCK(&(rbtdb->node_locks[node->locknum].lock));
1842
1843                 /*
1844                  * First we try to figure out if this node is active in
1845                  * the search's version.  We do this now, even though we
1846                  * may not need the information, because it simplifies the
1847                  * locking and code flow.
1848                  */
1849                 for (header = node->data;
1850                      header != NULL;
1851                      header = header->next) {
1852                         if (header->serial <= search->serial &&
1853                             !IGNORE(header) && EXISTS(header))
1854                                 break;
1855                 }
1856                 if (header != NULL)
1857                         active = ISC_TRUE;
1858                 else
1859                         active = ISC_FALSE;
1860
1861                 if (node->wild)
1862                         wild = ISC_TRUE;
1863                 else
1864                         wild = ISC_FALSE;
1865
1866                 UNLOCK(&(rbtdb->node_locks[node->locknum].lock));
1867
1868                 if (wild) {
1869                         /*
1870                          * Construct the wildcard name for this level.
1871                          */
1872                         dns_name_init(&name, NULL);
1873                         dns_rbt_namefromnode(node, &name);
1874                         dns_fixedname_init(&fwname);
1875                         wname = dns_fixedname_name(&fwname);
1876                         result = dns_name_concatenate(dns_wildcardname, &name,
1877                                                       wname, NULL);
1878                         j = i;
1879                         while (result == ISC_R_SUCCESS && j != 0) {
1880                                 j--;
1881                                 level_node = search->chain.levels[j];
1882                                 dns_name_init(&name, NULL);
1883                                 dns_rbt_namefromnode(level_node, &name);
1884                                 result = dns_name_concatenate(wname,
1885                                                               &name,
1886                                                               wname,
1887                                                               NULL);
1888                         }
1889                         if (result != ISC_R_SUCCESS)
1890                                 break;
1891
1892                         wnode = NULL;
1893                         dns_rbtnodechain_init(&wchain, NULL);
1894                         result = dns_rbt_findnode(rbtdb->tree, wname,
1895                                                   NULL, &wnode, &wchain,
1896                                                   DNS_RBTFIND_EMPTYDATA,
1897                                                   NULL, NULL);
1898                         if (result == ISC_R_SUCCESS) {
1899                             /*
1900                              * We have found the wildcard node.  If it
1901                              * is active in the search's version, we're
1902                              * done.
1903                              */
1904                             LOCK(&(rbtdb->node_locks[wnode->locknum].lock));
1905                             for (header = wnode->data;
1906                                  header != NULL;
1907                                  header = header->next) {
1908                                     if (header->serial <= search->serial &&
1909                                         !IGNORE(header) && EXISTS(header))
1910                                             break;
1911                             }
1912                             UNLOCK(&(rbtdb->node_locks[wnode->locknum].lock));
1913                             if (header != NULL ||
1914                                 activeempty(search, &wchain, wname)) {
1915                                     if (activeemtpynode(search, qname, wname))
1916                                                 return (ISC_R_NOTFOUND);
1917                                     /*
1918                                      * The wildcard node is active!
1919                                      *
1920                                      * Note: result is still ISC_R_SUCCESS
1921                                      * so we don't have to set it.
1922                                      */
1923                                     *nodep = wnode;
1924                                     break;
1925                             }
1926                         } else if (result != ISC_R_NOTFOUND &&
1927                                    result != DNS_R_PARTIALMATCH) {
1928                                 /*
1929                                  * An error has occurred.  Bail out.
1930                                  */
1931                                 break;
1932                         }
1933                 }
1934
1935                 if (active) {
1936                         /*
1937                          * The level node is active.  Any wildcarding
1938                          * present at higher levels has no
1939                          * effect and we're done.
1940                          */
1941                         result = ISC_R_NOTFOUND;
1942                         break;
1943                 }
1944
1945                 if (i > 0) {
1946                         i--;
1947                         node = search->chain.levels[i];
1948                 } else
1949                         done = ISC_TRUE;
1950         } while (!done);
1951
1952         return (result);
1953 }
1954
1955 static inline isc_result_t
1956 find_closest_nsec(rbtdb_search_t *search, dns_dbnode_t **nodep,
1957                   dns_name_t *foundname, dns_rdataset_t *rdataset,
1958                   dns_rdataset_t *sigrdataset, isc_boolean_t need_sig)
1959 {
1960         dns_rbtnode_t *node;
1961         rdatasetheader_t *header, *header_next, *found, *foundsig;
1962         isc_boolean_t empty_node;
1963         isc_result_t result;
1964         dns_fixedname_t fname, forigin;
1965         dns_name_t *name, *origin;
1966
1967         do {
1968                 node = NULL;
1969                 dns_fixedname_init(&fname);
1970                 name = dns_fixedname_name(&fname);
1971                 dns_fixedname_init(&forigin);
1972                 origin = dns_fixedname_name(&forigin);
1973                 result = dns_rbtnodechain_current(&search->chain, name,
1974                                                   origin, &node);
1975                 if (result != ISC_R_SUCCESS)
1976                         return (result);
1977                 LOCK(&(search->rbtdb->node_locks[node->locknum].lock));
1978                 found = NULL;
1979                 foundsig = NULL;
1980                 empty_node = ISC_TRUE;
1981                 for (header = node->data;
1982                      header != NULL;
1983                      header = header_next) {
1984                         header_next = header->next;
1985                         /*
1986                          * Look for an active, extant NSEC or RRSIG NSEC.
1987                          */
1988                         do {
1989                                 if (header->serial <= search->serial &&
1990                                     !IGNORE(header)) {
1991                                         /*
1992                                          * Is this a "this rdataset doesn't
1993                                          * exist" record?
1994                                          */
1995                                         if (NONEXISTENT(header))
1996                                                 header = NULL;
1997                                         break;
1998                                 } else
1999                                         header = header->down;
2000                         } while (header != NULL);
2001                         if (header != NULL) {
2002                                 /*
2003                                  * We now know that there is at least one
2004                                  * active rdataset at this node.
2005                                  */
2006                                 empty_node = ISC_FALSE;
2007                                 if (header->type == dns_rdatatype_nsec) {
2008                                         found = header;
2009                                         if (foundsig != NULL)
2010                                                 break;
2011                                 } else if (header->type ==
2012                                            RBTDB_RDATATYPE_SIGNSEC) {
2013                                         foundsig = header;
2014                                         if (found != NULL)
2015                                                 break;
2016                                 }
2017                         }
2018                 }
2019                 if (!empty_node) {
2020                         if (found != NULL &&
2021                             (foundsig != NULL || !need_sig))
2022                         {
2023                                 /*
2024                                  * We've found the right NSEC record.
2025                                  *
2026                                  * Note: for this to really be the right
2027                                  * NSEC record, it's essential that the NSEC
2028                                  * records of any nodes obscured by a zone
2029                                  * cut have been removed; we assume this is
2030                                  * the case.
2031                                  */
2032                                 result = dns_name_concatenate(name, origin,
2033                                                               foundname, NULL);
2034                                 if (result == ISC_R_SUCCESS) {
2035                                         if (nodep != NULL) {
2036                                                 new_reference(search->rbtdb,
2037                                                               node);
2038                                                 *nodep = node;
2039                                         }
2040                                         bind_rdataset(search->rbtdb, node,
2041                                                       found, search->now,
2042                                                       rdataset);
2043                                         if (foundsig != NULL)
2044                                                 bind_rdataset(search->rbtdb,
2045                                                               node,
2046                                                               foundsig,
2047                                                               search->now,
2048                                                               sigrdataset);
2049                                 }
2050                         } else if (found == NULL && foundsig == NULL) {
2051                                 /*
2052                                  * This node is active, but has no NSEC or
2053                                  * RRSIG NSEC.  That means it's glue or
2054                                  * other obscured zone data that isn't
2055                                  * relevant for our search.  Treat the
2056                                  * node as if it were empty and keep looking.
2057                                  */
2058                                 empty_node = ISC_TRUE;
2059                                 result = dns_rbtnodechain_prev(&search->chain,
2060                                                                NULL, NULL);
2061                         } else {
2062                                 /*
2063                                  * We found an active node, but either the
2064                                  * NSEC or the RRSIG NSEC is missing.  This
2065                                  * shouldn't happen.
2066                                  */
2067                                 result = DNS_R_BADDB;
2068                         }
2069                 } else {
2070                         /*
2071                          * This node isn't active.  We've got to keep
2072                          * looking.
2073                          */
2074                         result = dns_rbtnodechain_prev(&search->chain, NULL,
2075                                                        NULL);
2076                 }
2077                 UNLOCK(&(search->rbtdb->node_locks[node->locknum].lock));
2078         } while (empty_node && result == ISC_R_SUCCESS);
2079
2080         /*
2081          * If the result is ISC_R_NOMORE, then we got to the beginning of
2082          * the database and didn't find a NSEC record.  This shouldn't
2083          * happen.
2084          */
2085         if (result == ISC_R_NOMORE)
2086                 result = DNS_R_BADDB;
2087
2088         return (result);
2089 }
2090
2091 static isc_result_t
2092 zone_find(dns_db_t *db, dns_name_t *name, dns_dbversion_t *version,
2093           dns_rdatatype_t type, unsigned int options, isc_stdtime_t now,
2094           dns_dbnode_t **nodep, dns_name_t *foundname,
2095           dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset)
2096 {
2097         dns_rbtnode_t *node = NULL;
2098         isc_result_t result;
2099         rbtdb_search_t search;
2100         isc_boolean_t cname_ok = ISC_TRUE;
2101         isc_boolean_t close_version = ISC_FALSE;
2102         isc_boolean_t maybe_zonecut = ISC_FALSE;
2103         isc_boolean_t at_zonecut = ISC_FALSE;
2104         isc_boolean_t wild;
2105         isc_boolean_t empty_node;
2106         isc_mutex_t *lock;
2107         rdatasetheader_t *header, *header_next, *found, *nsecheader;
2108         rdatasetheader_t *foundsig, *cnamesig, *nsecsig;
2109         rbtdb_rdatatype_t sigtype;
2110         isc_boolean_t active;
2111         dns_rbtnodechain_t chain;
2112
2113
2114         search.rbtdb = (dns_rbtdb_t *)db;
2115
2116         REQUIRE(VALID_RBTDB(search.rbtdb));
2117
2118         /*
2119          * We don't care about 'now'.
2120          */
2121         UNUSED(now);
2122
2123         /*
2124          * If the caller didn't supply a version, attach to the current
2125          * version.
2126          */
2127         if (version == NULL) {
2128                 currentversion(db, &version);
2129                 close_version = ISC_TRUE;
2130         }
2131
2132         search.rbtversion = version;
2133         search.serial = search.rbtversion->serial;
2134         search.options = options;
2135         search.copy_name = ISC_FALSE;
2136         search.need_cleanup = ISC_FALSE;
2137         search.wild = ISC_FALSE;
2138         search.zonecut = NULL;
2139         dns_fixedname_init(&search.zonecut_name);
2140         dns_rbtnodechain_init(&search.chain, search.rbtdb->common.mctx);
2141         search.now = 0;
2142
2143         /*
2144          * 'wild' will be true iff. we've matched a wildcard.
2145          */
2146         wild = ISC_FALSE;
2147
2148         RWLOCK(&search.rbtdb->tree_lock, isc_rwlocktype_read);
2149
2150         /*
2151          * Search down from the root of the tree.  If, while going down, we
2152          * encounter a callback node, zone_zonecut_callback() will search the
2153          * rdatasets at the zone cut for active DNAME or NS rdatasets.
2154          */
2155         result = dns_rbt_findnode(search.rbtdb->tree, name, foundname, &node,
2156                                   &search.chain, DNS_RBTFIND_EMPTYDATA,
2157                                   zone_zonecut_callback, &search);
2158
2159         if (result == DNS_R_PARTIALMATCH) {
2160         partial_match:
2161                 if (search.zonecut != NULL) {
2162                     result = setup_delegation(&search, nodep, foundname,
2163                                               rdataset, sigrdataset);
2164                     goto tree_exit;
2165                 }
2166
2167                 if (search.wild) {
2168                         /*
2169                          * At least one of the levels in the search chain
2170                          * potentially has a wildcard.  For each such level,
2171                          * we must see if there's a matching wildcard active
2172                          * in the current version.
2173                          */
2174                         result = find_wildcard(&search, &node, name);
2175                         if (result == ISC_R_SUCCESS) {
2176                                 result = dns_name_copy(name, foundname, NULL);
2177                                 if (result != ISC_R_SUCCESS)
2178                                         goto tree_exit;
2179                                 wild = ISC_TRUE;
2180                                 goto found;
2181                         }
2182                         else if (result != ISC_R_NOTFOUND)
2183                                 goto tree_exit;
2184                 }
2185
2186                 chain = search.chain;
2187                 active = activeempty(&search, &chain, name);
2188
2189                 /*
2190                  * If we're here, then the name does not exist, is not
2191                  * beneath a zonecut, and there's no matching wildcard.
2192                  */
2193                 if (search.rbtdb->secure ||
2194                     (search.options & DNS_DBFIND_FORCENSEC) != 0)
2195                 {
2196                         result = find_closest_nsec(&search, nodep, foundname,
2197                                                   rdataset, sigrdataset,
2198                                                   search.rbtdb->secure);
2199                         if (result == ISC_R_SUCCESS)
2200                                 result = active ? DNS_R_EMPTYNAME :
2201                                                   DNS_R_NXDOMAIN;
2202                 } else
2203                         result = active ? DNS_R_EMPTYNAME : DNS_R_NXDOMAIN;
2204                 goto tree_exit;
2205         } else if (result != ISC_R_SUCCESS)
2206                 goto tree_exit;
2207
2208  found:
2209         /*
2210          * We have found a node whose name is the desired name, or we
2211          * have matched a wildcard.
2212          */
2213
2214         if (search.zonecut != NULL) {
2215                 /*
2216                  * If we're beneath a zone cut, we don't want to look for
2217                  * CNAMEs because they're not legitimate zone glue.
2218                  */
2219                 cname_ok = ISC_FALSE;
2220         } else {
2221                 /*
2222                  * The node may be a zone cut itself.  If it might be one,
2223                  * make sure we check for it later.
2224                  */
2225                 if (node->find_callback &&
2226                     (node != search.rbtdb->origin_node ||
2227                      IS_STUB(search.rbtdb)) &&
2228                     !dns_rdatatype_atparent(type))
2229                         maybe_zonecut = ISC_TRUE;
2230         }
2231
2232         /*
2233          * Certain DNSSEC types are not subject to CNAME matching
2234          * (RFC4035, section 2.5 and RFC3007).
2235          *
2236          * We don't check for RRSIG, because we don't store RRSIG records
2237          * directly.
2238          */
2239         if (type == dns_rdatatype_key || type == dns_rdatatype_nsec)
2240                 cname_ok = ISC_FALSE;
2241
2242         /*
2243          * We now go looking for rdata...
2244          */
2245
2246         LOCK(&(search.rbtdb->node_locks[node->locknum].lock));
2247
2248         found = NULL;
2249         foundsig = NULL;
2250         sigtype = RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, type);
2251         nsecheader = NULL;
2252         nsecsig = NULL;
2253         cnamesig = NULL;
2254         empty_node = ISC_TRUE;
2255         for (header = node->data; header != NULL; header = header_next) {
2256                 header_next = header->next;
2257                 /*
2258                  * Look for an active, extant rdataset.
2259                  */
2260                 do {
2261                         if (header->serial <= search.serial &&
2262                             !IGNORE(header)) {
2263                                 /*
2264                                  * Is this a "this rdataset doesn't
2265                                  * exist" record?
2266                                  */
2267                                 if (NONEXISTENT(header))
2268                                         header = NULL;
2269                                 break;
2270                         } else
2271                                 header = header->down;
2272                 } while (header != NULL);
2273                 if (header != NULL) {
2274                         /*
2275                          * We now know that there is at least one active
2276                          * rdataset at this node.
2277                          */
2278                         empty_node = ISC_FALSE;
2279
2280                         /*
2281                          * Do special zone cut handling, if requested.
2282                          */
2283                         if (maybe_zonecut &&
2284                             header->type == dns_rdatatype_ns) {
2285                                 /*
2286                                  * We increment the reference count on node to
2287                                  * ensure that search->zonecut_rdataset will
2288                                  * still be valid later.
2289                                  */
2290                                 new_reference(search.rbtdb, node);
2291                                 search.zonecut = node;
2292                                 search.zonecut_rdataset = header;
2293                                 search.zonecut_sigrdataset = NULL;
2294                                 search.need_cleanup = ISC_TRUE;
2295                                 maybe_zonecut = ISC_FALSE;
2296                                 at_zonecut = ISC_TRUE;
2297                                 /*
2298                                  * It is not clear if KEY should still be
2299                                  * allowed at the parent side of the zone
2300                                  * cut or not.  It is needed for RFC3007
2301                                  * validated updates.
2302                                  */
2303                                 if ((search.options & DNS_DBFIND_GLUEOK) == 0
2304                                     && type != dns_rdatatype_nsec
2305                                     && type != dns_rdatatype_key) {
2306                                         /*
2307                                          * Glue is not OK, but any answer we
2308                                          * could return would be glue.  Return
2309                                          * the delegation.
2310                                          */
2311                                         found = NULL;
2312                                         break;
2313                                 }
2314                                 if (found != NULL && foundsig != NULL)
2315                                         break;
2316                         }
2317
2318                         /*
2319                          * If we found a type we were looking for,
2320                          * remember it.
2321                          */
2322                         if (header->type == type ||
2323                             type == dns_rdatatype_any ||
2324                             (header->type == dns_rdatatype_cname &&
2325                              cname_ok)) {
2326                                 /*
2327                                  * We've found the answer!
2328                                  */
2329                                 found = header;
2330                                 if (header->type == dns_rdatatype_cname &&
2331                                     cname_ok) {
2332                                         /*
2333                                          * We may be finding a CNAME instead
2334                                          * of the desired type.
2335                                          *
2336                                          * If we've already got the CNAME RRSIG,
2337                                          * use it, otherwise change sigtype
2338                                          * so that we find it.
2339                                          */
2340                                         if (cnamesig != NULL)
2341                                                 foundsig = cnamesig;
2342                                         else
2343                                                 sigtype =
2344                                                     RBTDB_RDATATYPE_SIGCNAME;
2345                                 }
2346                                 /*
2347                                  * If we've got all we need, end the search.
2348                                  */
2349                                 if (!maybe_zonecut && foundsig != NULL)
2350                                         break;
2351                         } else if (header->type == sigtype) {
2352                                 /*
2353                                  * We've found the RRSIG rdataset for our
2354                                  * target type.  Remember it.
2355                                  */
2356                                 foundsig = header;
2357                                 /*
2358                                  * If we've got all we need, end the search.
2359                                  */
2360                                 if (!maybe_zonecut && found != NULL)
2361                                         break;
2362                         } else if (header->type == dns_rdatatype_nsec) {
2363                                 /*
2364                                  * Remember a NSEC rdataset even if we're
2365                                  * not specifically looking for it, because
2366                                  * we might need it later.
2367                                  */
2368                                 nsecheader = header;
2369                         } else if (header->type == RBTDB_RDATATYPE_SIGNSEC) {
2370                                 /*
2371                                  * If we need the NSEC rdataset, we'll also
2372                                  * need its signature.
2373                                  */
2374                                 nsecsig = header;
2375                         } else if (cname_ok &&
2376                                    header->type == RBTDB_RDATATYPE_SIGCNAME) {
2377                                 /*
2378                                  * If we get a CNAME match, we'll also need
2379                                  * its signature.
2380                                  */
2381                                 cnamesig = header;
2382                         }
2383                 }
2384         }
2385
2386         if (empty_node) {
2387                 /*
2388                  * We have an exact match for the name, but there are no
2389                  * active rdatasets in the desired version.  That means that
2390                  * this node doesn't exist in the desired version, and that
2391                  * we really have a partial match.
2392                  */
2393                 if (!wild) {
2394                         UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
2395                         goto partial_match;
2396                 }
2397         }
2398
2399         /*
2400          * If we didn't find what we were looking for...
2401          */
2402         if (found == NULL) {
2403                 if (search.zonecut != NULL) {
2404                     /*
2405                      * We were trying to find glue at a node beneath a
2406                      * zone cut, but didn't.
2407                      *
2408                      * Return the delegation.
2409                      */
2410                     UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
2411                     result = setup_delegation(&search, nodep, foundname,
2412                                               rdataset, sigrdataset);
2413                     goto tree_exit;
2414                 }
2415                 /*
2416                  * The desired type doesn't exist.
2417                  */
2418                 result = DNS_R_NXRRSET;
2419                 if (search.rbtdb->secure &&
2420                     (nsecheader == NULL || nsecsig == NULL)) {
2421                         /*
2422                          * The zone is secure but there's no NSEC,
2423                          * or the NSEC has no signature!
2424                          */
2425                         if (!wild) {
2426                                 result = DNS_R_BADDB;
2427                                 goto node_exit;
2428                         }
2429
2430                         UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
2431                         result = find_closest_nsec(&search, nodep, foundname,
2432                                                   rdataset, sigrdataset,
2433                                                   search.rbtdb->secure);
2434                         if (result == ISC_R_SUCCESS)
2435                                 result = DNS_R_EMPTYWILD;
2436                         goto tree_exit;
2437                 }
2438                 if ((search.options & DNS_DBFIND_FORCENSEC) != 0 &&
2439                     nsecheader == NULL)
2440                 {
2441                         /*
2442                          * There's no NSEC record, and we were told
2443                          * to find one.
2444                          */
2445                         result = DNS_R_BADDB;
2446                         goto node_exit;
2447                 }
2448                 if (nodep != NULL) {
2449                         new_reference(search.rbtdb, node);
2450                         *nodep = node;
2451                 }
2452                 if (search.rbtdb->secure ||
2453                     (search.options & DNS_DBFIND_FORCENSEC) != 0)
2454                 {
2455                         bind_rdataset(search.rbtdb, node, nsecheader,
2456                                       0, rdataset);
2457                         if (nsecsig != NULL)
2458                                 bind_rdataset(search.rbtdb, node,
2459                                               nsecsig, 0, sigrdataset);
2460                 }
2461                 if (wild)
2462                         foundname->attributes |= DNS_NAMEATTR_WILDCARD;
2463                 goto node_exit;
2464         }
2465
2466         /*
2467          * We found what we were looking for, or we found a CNAME.
2468          */
2469
2470         if (type != found->type &&
2471             type != dns_rdatatype_any &&
2472             found->type == dns_rdatatype_cname) {
2473                 /*
2474                  * We weren't doing an ANY query and we found a CNAME instead
2475                  * of the type we were looking for, so we need to indicate
2476                  * that result to the caller.
2477                  */
2478                 result = DNS_R_CNAME;
2479         } else if (search.zonecut != NULL) {
2480                 /*
2481                  * If we're beneath a zone cut, we must indicate that the
2482                  * result is glue, unless we're actually at the zone cut
2483                  * and the type is NSEC or KEY.
2484                  */
2485                 if (search.zonecut == node) {
2486                         /*
2487                          * It is not clear if KEY should still be
2488                          * allowed at the parent side of the zone
2489                          * cut or not.  It is needed for RFC3007
2490                          * validated updates.
2491                          */
2492                         if (type == dns_rdatatype_nsec ||
2493                             type == dns_rdatatype_key)
2494                                 result = ISC_R_SUCCESS;
2495                         else if (type == dns_rdatatype_any)
2496                                 result = DNS_R_ZONECUT;
2497                         else
2498                                 result = DNS_R_GLUE;
2499                 } else
2500                         result = DNS_R_GLUE;
2501                 /*
2502                  * We might have found data that isn't glue, but was occluded
2503                  * by a dynamic update.  If the caller cares about this, they
2504                  * will have told us to validate glue.
2505                  *
2506                  * XXX We should cache the glue validity state!
2507                  */
2508                 if (result == DNS_R_GLUE &&
2509                     (search.options & DNS_DBFIND_VALIDATEGLUE) != 0 &&
2510                     !valid_glue(&search, foundname, type, node)) {
2511                     UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
2512                     result = setup_delegation(&search, nodep, foundname,
2513                                               rdataset, sigrdataset);
2514                     goto tree_exit;
2515                 }
2516         } else {
2517                 /*
2518                  * An ordinary successful query!
2519                  */
2520                 result = ISC_R_SUCCESS;
2521         }
2522
2523         if (nodep != NULL) {
2524                 if (!at_zonecut)
2525                         new_reference(search.rbtdb, node);
2526                 else
2527                         search.need_cleanup = ISC_FALSE;
2528                 *nodep = node;
2529         }
2530
2531         if (type != dns_rdatatype_any) {
2532                 bind_rdataset(search.rbtdb, node, found, 0, rdataset);
2533                 if (foundsig != NULL)
2534                         bind_rdataset(search.rbtdb, node, foundsig, 0,
2535                                       sigrdataset);
2536         }
2537
2538         if (wild)
2539                 foundname->attributes |= DNS_NAMEATTR_WILDCARD;
2540
2541  node_exit:
2542         UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
2543
2544  tree_exit:
2545         RWUNLOCK(&search.rbtdb->tree_lock, isc_rwlocktype_read);
2546
2547         /*
2548          * If we found a zonecut but aren't going to use it, we have to
2549          * let go of it.
2550          */
2551         if (search.need_cleanup) {
2552                 node = search.zonecut;
2553                 lock = &(search.rbtdb->node_locks[node->locknum].lock);
2554
2555                 LOCK(lock);
2556                 INSIST(node->references > 0);
2557                 node->references--;
2558                 if (node->references == 0)
2559                         no_references(search.rbtdb, node, 0,
2560                                       isc_rwlocktype_none);
2561
2562                 UNLOCK(lock);
2563         }
2564
2565         if (close_version)
2566                 closeversion(db, &version, ISC_FALSE);
2567
2568         dns_rbtnodechain_reset(&search.chain);
2569
2570         return (result);
2571 }
2572
2573 static isc_result_t
2574 zone_findzonecut(dns_db_t *db, dns_name_t *name, unsigned int options,
2575                  isc_stdtime_t now, dns_dbnode_t **nodep,
2576                  dns_name_t *foundname,
2577                  dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset)
2578 {
2579         UNUSED(db);
2580         UNUSED(name);
2581         UNUSED(options);
2582         UNUSED(now);
2583         UNUSED(nodep);
2584         UNUSED(foundname);
2585         UNUSED(rdataset);
2586         UNUSED(sigrdataset);
2587
2588         FATAL_ERROR(__FILE__, __LINE__, "zone_findzonecut() called!");
2589
2590         return (ISC_R_NOTIMPLEMENTED);
2591 }
2592
2593 static isc_result_t
2594 cache_zonecut_callback(dns_rbtnode_t *node, dns_name_t *name, void *arg) {
2595         rbtdb_search_t *search = arg;
2596         rdatasetheader_t *header, *header_prev, *header_next;
2597         rdatasetheader_t *dname_header, *sigdname_header;
2598         isc_result_t result;
2599
2600         /* XXX comment */
2601
2602         REQUIRE(search->zonecut == NULL);
2603
2604         /*
2605          * Keep compiler silent.
2606          */
2607         UNUSED(name);
2608
2609         LOCK(&(search->rbtdb->node_locks[node->locknum].lock));
2610
2611         /*
2612          * Look for a DNAME or RRSIG DNAME rdataset.
2613          */
2614         dname_header = NULL;
2615         sigdname_header = NULL;
2616         header_prev = NULL;
2617         for (header = node->data; header != NULL; header = header_next) {
2618                 header_next = header->next;
2619                 if (header->ttl <= search->now) {
2620                         /*
2621                          * This rdataset is stale.  If no one else is
2622                          * using the node, we can clean it up right
2623                          * now, otherwise we mark it as stale, and
2624                          * the node as dirty, so it will get cleaned
2625                          * up later.
2626                          */
2627                         if (node->references == 0) {
2628                                 INSIST(header->down == NULL);
2629                                 if (header_prev != NULL)
2630                                         header_prev->next =
2631                                                 header->next;
2632                                 else
2633                                         node->data = header->next;
2634                                 free_rdataset(search->rbtdb->common.mctx,
2635                                               header);
2636                         } else {
2637                                 header->attributes |=
2638                                         RDATASET_ATTR_STALE;
2639                                 node->dirty = 1;
2640                                 header_prev = header;
2641                         }
2642                 } else if (header->type == dns_rdatatype_dname &&
2643                            EXISTS(header)) {
2644                         dname_header = header;
2645                         header_prev = header;
2646                 } else if (header->type == RBTDB_RDATATYPE_SIGDNAME &&
2647                          EXISTS(header)) {
2648                         sigdname_header = header;
2649                         header_prev = header;
2650                 } else
2651                         header_prev = header;
2652         }
2653
2654         if (dname_header != NULL &&
2655             (dname_header->trust != dns_trust_pending ||
2656              (search->options & DNS_DBFIND_PENDINGOK) != 0)) {
2657                 /*
2658                  * We increment the reference count on node to ensure that
2659                  * search->zonecut_rdataset will still be valid later.
2660                  */
2661                 new_reference(search->rbtdb, node);
2662                 search->zonecut = node;
2663                 search->zonecut_rdataset = dname_header;
2664                 search->zonecut_sigrdataset = sigdname_header;
2665                 search->need_cleanup = ISC_TRUE;
2666                 result = DNS_R_PARTIALMATCH;
2667         } else
2668                 result = DNS_R_CONTINUE;
2669
2670         UNLOCK(&(search->rbtdb->node_locks[node->locknum].lock));
2671
2672         return (result);
2673 }
2674
2675 static inline isc_result_t
2676 find_deepest_zonecut(rbtdb_search_t *search, dns_rbtnode_t *node,
2677                      dns_dbnode_t **nodep, dns_name_t *foundname,
2678                      dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset)
2679 {
2680         unsigned int i;
2681         dns_rbtnode_t *level_node;
2682         rdatasetheader_t *header, *header_prev, *header_next;
2683         rdatasetheader_t *found, *foundsig;
2684         isc_result_t result = ISC_R_NOTFOUND;
2685         dns_name_t name;
2686         dns_rbtdb_t *rbtdb;
2687         isc_boolean_t done;
2688
2689         /*
2690          * Caller must be holding the tree lock.
2691          */
2692
2693         rbtdb = search->rbtdb;
2694         i = search->chain.level_matches;
2695         done = ISC_FALSE;
2696         do {
2697                 LOCK(&(rbtdb->node_locks[node->locknum].lock));
2698
2699                 /*
2700                  * Look for NS and RRSIG NS rdatasets.
2701                  */
2702                 found = NULL;
2703                 foundsig = NULL;
2704                 header_prev = NULL;
2705                 for (header = node->data;
2706                      header != NULL;
2707                      header = header_next) {
2708                         header_next = header->next;
2709                         if (header->ttl <= search->now) {
2710                                 /*
2711                                  * This rdataset is stale.  If no one else is
2712                                  * using the node, we can clean it up right
2713                                  * now, otherwise we mark it as stale, and
2714                                  * the node as dirty, so it will get cleaned
2715                                  * up later.
2716                                  */
2717                                 if (node->references == 0) {
2718                                         INSIST(header->down == NULL);
2719                                         if (header_prev != NULL)
2720                                                 header_prev->next =
2721                                                         header->next;
2722                                         else
2723                                                 node->data = header->next;
2724                                         free_rdataset(rbtdb->common.mctx,
2725                                                       header);
2726                                 } else {
2727                                         header->attributes |=
2728                                                 RDATASET_ATTR_STALE;
2729                                         node->dirty = 1;
2730                                         header_prev = header;
2731                                 }
2732                         } else if (EXISTS(header)) {
2733                                 /*
2734                                  * We've found an extant rdataset.  See if
2735                                  * we're interested in it.
2736                                  */
2737                                 if (header->type == dns_rdatatype_ns) {
2738                                         found = header;
2739                                         if (foundsig != NULL)
2740                                                 break;
2741                                 } else if (header->type ==
2742                                            RBTDB_RDATATYPE_SIGNS) {
2743                                         foundsig = header;
2744                                         if (found != NULL)
2745                                                 break;
2746                                 }
2747                                 header_prev = header;
2748                         } else
2749                                 header_prev = header;
2750                 }
2751
2752                 if (found != NULL) {
2753                         /*
2754                          * If we have to set foundname, we do it before
2755                          * anything else.  If we were to set foundname after
2756                          * we had set nodep or bound the rdataset, then we'd
2757                          * have to undo that work if dns_name_concatenate()
2758                          * failed.  By setting foundname first, there's
2759                          * nothing to undo if we have trouble.
2760                          */
2761                         if (foundname != NULL) {
2762                                 dns_name_init(&name, NULL);
2763                                 dns_rbt_namefromnode(node, &name);
2764                                 result = dns_name_copy(&name, foundname, NULL);
2765                                 while (result == ISC_R_SUCCESS && i > 0) {
2766                                         i--;
2767                                         level_node = search->chain.levels[i];
2768                                         dns_name_init(&name, NULL);
2769                                         dns_rbt_namefromnode(level_node,
2770                                                              &name);
2771                                         result =
2772                                                 dns_name_concatenate(foundname,
2773                                                                      &name,
2774                                                                      foundname,
2775                                                                      NULL);
2776                                 }
2777                                 if (result != ISC_R_SUCCESS) {
2778                                         *nodep = NULL;
2779                                         goto node_exit;
2780                                 }
2781                         }
2782                         result = DNS_R_DELEGATION;
2783                         if (nodep != NULL) {
2784                                 new_reference(search->rbtdb, node);
2785                                 *nodep = node;
2786                         }
2787                         bind_rdataset(search->rbtdb, node, found, search->now,
2788                                       rdataset);
2789                         if (foundsig != NULL)
2790                                 bind_rdataset(search->rbtdb, node, foundsig,
2791                                               search->now, sigrdataset);
2792                 }
2793
2794         node_exit:
2795                 UNLOCK(&(search->rbtdb->node_locks[node->locknum].lock));
2796
2797                 if (found == NULL && i > 0) {
2798                         i--;
2799                         node = search->chain.levels[i];
2800                 } else
2801                         done = ISC_TRUE;
2802
2803         } while (!done);
2804
2805         return (result);
2806 }
2807
2808 static isc_result_t
2809 find_coveringnsec(rbtdb_search_t *search, dns_dbnode_t **nodep,
2810                   isc_stdtime_t now, dns_name_t *foundname,
2811                   dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset)
2812 {
2813         dns_rbtnode_t *node;
2814         rdatasetheader_t *header, *header_next, *header_prev;
2815         rdatasetheader_t *found, *foundsig;
2816         isc_boolean_t empty_node;
2817         isc_result_t result;
2818         dns_fixedname_t fname, forigin;
2819         dns_name_t *name, *origin;
2820         rbtdb_rdatatype_t matchtype, sigmatchtype;
2821
2822         matchtype = RBTDB_RDATATYPE_VALUE(dns_rdatatype_nsec, 0);
2823         sigmatchtype = RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig,
2824                                              dns_rdatatype_nsec);
2825
2826         do {
2827                 node = NULL;
2828                 dns_fixedname_init(&fname);
2829                 name = dns_fixedname_name(&fname);
2830                 dns_fixedname_init(&forigin);
2831                 origin = dns_fixedname_name(&forigin);
2832                 result = dns_rbtnodechain_current(&search->chain, name,
2833                                                   origin, &node);
2834                 if (result != ISC_R_SUCCESS)
2835                         return (result);
2836                 LOCK(&(search->rbtdb->node_locks[node->locknum].lock));
2837                 found = NULL;
2838                 foundsig = NULL;
2839                 empty_node = ISC_TRUE;
2840                 header_prev = NULL;
2841                 for (header = node->data;
2842                      header != NULL;
2843                      header = header_next) {
2844                         header_next = header->next;
2845                         if (header->ttl <= now) {
2846                                 /*
2847                                  * This rdataset is stale.  If no one else is
2848                                  * using the node, we can clean it up right
2849                                  * now, otherwise we mark it as stale, and the
2850                                  * node as dirty, so it will get cleaned up
2851                                  * later.
2852                                  */
2853                                 if (header->ttl > search->now - RBTDB_VIRTUAL)
2854                                         header_prev = header;
2855                                 else if (node->references == 0) {
2856                                         INSIST(header->down == NULL);
2857                                         if (header_prev != NULL)
2858                                                 header_prev->next =
2859                                                         header->next;
2860                                         else
2861                                                 node->data = header->next;
2862                                         free_rdataset(search->rbtdb->common.mctx,
2863                                                       header);
2864                                 } else {
2865                                         header->attributes |=
2866                                                  RDATASET_ATTR_STALE;
2867                                         node->dirty = 1;
2868                                         header_prev = header;
2869                                 }
2870                                 continue;
2871                         }
2872                         if (NONEXISTENT(header) || NXDOMAIN(header)) {
2873                                 header_prev = header;
2874                                 continue;
2875                         }
2876                         empty_node = ISC_FALSE;
2877                         if (header->type == matchtype)
2878                                 found = header;
2879                         else if (header->type == sigmatchtype)
2880                                 foundsig = header;
2881                         header_prev = header;
2882                 }
2883                 if (found != NULL) {
2884                         result = dns_name_concatenate(name, origin,
2885                                                       foundname, NULL);
2886                         if (result != ISC_R_SUCCESS)
2887                                 goto unlock_node;
2888                         bind_rdataset(search->rbtdb, node, found,
2889                                       now, rdataset);
2890                         if (foundsig != NULL)
2891                                 bind_rdataset(search->rbtdb, node, foundsig,
2892                                               now, sigrdataset);
2893                         new_reference(search->rbtdb, node);
2894                         *nodep = node;
2895                         result = DNS_R_COVERINGNSEC;
2896                 } else if (!empty_node) {
2897                         result = ISC_R_NOTFOUND;
2898                 }else
2899                         result = dns_rbtnodechain_prev(&search->chain, NULL,
2900                                                        NULL);
2901  unlock_node:
2902                 UNLOCK(&(search->rbtdb->node_locks[node->locknum].lock));
2903         } while (empty_node && result == ISC_R_SUCCESS);
2904         return (result);
2905 }
2906
2907 static isc_result_t
2908 cache_find(dns_db_t *db, dns_name_t *name, dns_dbversion_t *version,
2909            dns_rdatatype_t type, unsigned int options, isc_stdtime_t now,
2910            dns_dbnode_t **nodep, dns_name_t *foundname,
2911            dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset)
2912 {
2913         dns_rbtnode_t *node = NULL;
2914         isc_result_t result;
2915         rbtdb_search_t search;
2916         isc_boolean_t cname_ok = ISC_TRUE;
2917         isc_boolean_t empty_node;
2918         isc_mutex_t *lock;
2919         rdatasetheader_t *header, *header_prev, *header_next;
2920         rdatasetheader_t *found, *nsheader;
2921         rdatasetheader_t *foundsig, *nssig, *cnamesig;
2922         rbtdb_rdatatype_t sigtype, negtype;
2923
2924         UNUSED(version);
2925
2926         search.rbtdb = (dns_rbtdb_t *)db;
2927
2928         REQUIRE(VALID_RBTDB(search.rbtdb));
2929         REQUIRE(version == NULL);
2930
2931         if (now == 0)
2932                 isc_stdtime_get(&now);
2933
2934         search.rbtversion = NULL;
2935         search.serial = 1;
2936         search.options = options;
2937         search.copy_name = ISC_FALSE;
2938         search.need_cleanup = ISC_FALSE;
2939         search.wild = ISC_FALSE;
2940         search.zonecut = NULL;
2941         dns_fixedname_init(&search.zonecut_name);
2942         dns_rbtnodechain_init(&search.chain, search.rbtdb->common.mctx);
2943         search.now = now;
2944
2945         RWLOCK(&search.rbtdb->tree_lock, isc_rwlocktype_read);
2946
2947         /*
2948          * Search down from the root of the tree.  If, while going down, we
2949          * encounter a callback node, cache_zonecut_callback() will search the
2950          * rdatasets at the zone cut for a DNAME rdataset.
2951          */
2952         result = dns_rbt_findnode(search.rbtdb->tree, name, foundname, &node,
2953                                   &search.chain, DNS_RBTFIND_EMPTYDATA,
2954                                   cache_zonecut_callback, &search);
2955
2956         if (result == DNS_R_PARTIALMATCH) {
2957                 if ((search.options & DNS_DBFIND_COVERINGNSEC) != 0) {
2958                         result = find_coveringnsec(&search, nodep, now,
2959                                                    foundname, rdataset,
2960                                                    sigrdataset);
2961                         if (result == DNS_R_COVERINGNSEC)
2962                                 goto tree_exit;
2963                 }
2964                 if (search.zonecut != NULL) {
2965                     result = setup_delegation(&search, nodep, foundname,
2966                                               rdataset, sigrdataset);
2967                     goto tree_exit;
2968                 } else {
2969                 find_ns:
2970                         result = find_deepest_zonecut(&search, node, nodep,
2971                                                       foundname, rdataset,
2972                                                       sigrdataset);
2973                         goto tree_exit;
2974                 }
2975         } else if (result != ISC_R_SUCCESS)
2976                 goto tree_exit;
2977
2978         /*
2979          * Certain DNSSEC types are not subject to CNAME matching
2980          * (RFC4035, section 2.5 and RFC3007).
2981          *
2982          * We don't check for RRSIG, because we don't store RRSIG records
2983          * directly.
2984          */
2985         if (type == dns_rdatatype_key || type == dns_rdatatype_nsec)
2986                 cname_ok = ISC_FALSE;
2987
2988         /*
2989          * We now go looking for rdata...
2990          */
2991
2992         LOCK(&(search.rbtdb->node_locks[node->locknum].lock));
2993
2994         found = NULL;
2995         foundsig = NULL;
2996         sigtype = RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, type);
2997         negtype = RBTDB_RDATATYPE_VALUE(0, type);
2998         nsheader = NULL;
2999         nssig = NULL;
3000         cnamesig = NULL;
3001         empty_node = ISC_TRUE;
3002         header_prev = NULL;
3003         for (header = node->data; header != NULL; header = header_next) {
3004                 header_next = header->next;
3005                 if (header->ttl <= now) {
3006                         /*
3007                          * This rdataset is stale.  If no one else is using the
3008                          * node, we can clean it up right now, otherwise we
3009                          * mark it as stale, and the node as dirty, so it will
3010                          * get cleaned up later.
3011                          */
3012                         if (header->ttl > now - RBTDB_VIRTUAL)
3013                                 header_prev = header;
3014                         else if (node->references == 0) {
3015                                 INSIST(header->down == NULL);
3016                                 if (header_prev != NULL)
3017                                         header_prev->next = header->next;
3018                                 else
3019                                         node->data = header->next;
3020                                 free_rdataset(search.rbtdb->common.mctx,
3021                                               header);
3022                         } else {
3023                                 header->attributes |= RDATASET_ATTR_STALE;
3024                                 node->dirty = 1;
3025                                 header_prev = header;
3026                         }
3027                 } else if (EXISTS(header)) {
3028                         /*
3029                          * We now know that there is at least one active
3030                          * non-stale rdataset at this node.
3031                          */
3032                         empty_node = ISC_FALSE;
3033
3034                         /*
3035                          * If we found a type we were looking for, remember
3036                          * it.
3037                          */
3038                         if (header->type == type ||
3039                             (type == dns_rdatatype_any &&
3040                              RBTDB_RDATATYPE_BASE(header->type) != 0) ||
3041                             (cname_ok && header->type ==
3042                              dns_rdatatype_cname)) {
3043                                 /*
3044                                  * We've found the answer.
3045                                  */
3046                                 found = header;
3047                                 if (header->type == dns_rdatatype_cname &&
3048                                     cname_ok &&
3049                                     cnamesig != NULL) {
3050                                         /*
3051                                          * If we've already got the CNAME RRSIG,
3052                                          * use it, otherwise change sigtype
3053                                          * so that we find it.
3054                                          */
3055                                         if (cnamesig != NULL)
3056                                                 foundsig = cnamesig;
3057                                         else
3058                                                 sigtype =
3059                                                     RBTDB_RDATATYPE_SIGCNAME;
3060                                         foundsig = cnamesig;
3061                                 }
3062                         } else if (header->type == sigtype) {
3063                                 /*
3064                                  * We've found the RRSIG rdataset for our
3065                                  * target type.  Remember it.
3066                                  */
3067                                 foundsig = header;
3068                         } else if (header->type == RBTDB_RDATATYPE_NCACHEANY ||
3069                                    header->type == negtype) {
3070                                 /*
3071                                  * We've found a negative cache entry.
3072                                  */
3073                                 found = header;
3074                         } else if (header->type == dns_rdatatype_ns) {
3075                                 /*
3076                                  * Remember a NS rdataset even if we're
3077                                  * not specifically looking for it, because
3078                                  * we might need it later.
3079                                  */
3080                                 nsheader = header;
3081                         } else if (header->type == RBTDB_RDATATYPE_SIGNS) {
3082                                 /*
3083                                  * If we need the NS rdataset, we'll also
3084                                  * need its signature.
3085                                  */
3086                                 nssig = header;
3087                         } else if (cname_ok &&
3088                                    header->type == RBTDB_RDATATYPE_SIGCNAME) {
3089                                 /*
3090                                  * If we get a CNAME match, we'll also need
3091                                  * its signature.
3092                                  */
3093                                 cnamesig = header;
3094                         }
3095                         header_prev = header;
3096                 } else
3097                         header_prev = header;
3098         }
3099
3100         if (empty_node) {
3101                 /*
3102                  * We have an exact match for the name, but there are no
3103                  * extant rdatasets.  That means that this node doesn't
3104                  * meaningfully exist, and that we really have a partial match.
3105                  */
3106                 UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
3107                 goto find_ns;
3108         }
3109
3110         /*
3111          * If we didn't find what we were looking for...
3112          */
3113         if (found == NULL ||
3114             (found->trust == dns_trust_glue &&
3115              ((options & DNS_DBFIND_GLUEOK) == 0)) ||
3116             (found->trust == dns_trust_pending &&
3117              ((options & DNS_DBFIND_PENDINGOK) == 0))) {
3118                 /*
3119                  * If there is an NS rdataset at this node, then this is the
3120                  * deepest zone cut.
3121                  */
3122                 if (nsheader != NULL) {
3123                         if (nodep != NULL) {
3124                                 new_reference(search.rbtdb, node);
3125                                 *nodep = node;
3126                         }
3127                         bind_rdataset(search.rbtdb, node, nsheader, search.now,
3128                                       rdataset);
3129                         if (nssig != NULL)
3130                                 bind_rdataset(search.rbtdb, node, nssig,
3131                                               search.now, sigrdataset);
3132                         result = DNS_R_DELEGATION;
3133                         goto node_exit;
3134                 }
3135
3136                 /*
3137                  * Go find the deepest zone cut.
3138                  */
3139                 UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
3140                 goto find_ns;
3141         }
3142
3143         /*
3144          * We found what we were looking for, or we found a CNAME.
3145          */
3146
3147         if (nodep != NULL) {
3148                 new_reference(search.rbtdb, node);
3149                 *nodep = node;
3150         }
3151
3152         if (RBTDB_RDATATYPE_BASE(found->type) == 0) {
3153                 /*
3154                  * We found a negative cache entry.
3155                  */
3156                 if (NXDOMAIN(found))
3157                         result = DNS_R_NCACHENXDOMAIN;
3158                 else
3159                         result = DNS_R_NCACHENXRRSET;
3160         } else if (type != found->type &&
3161                    type != dns_rdatatype_any &&
3162                    found->type == dns_rdatatype_cname) {
3163                 /*
3164                  * We weren't doing an ANY query and we found a CNAME instead
3165                  * of the type we were looking for, so we need to indicate
3166                  * that result to the caller.
3167                  */
3168                 result = DNS_R_CNAME;
3169         } else {
3170                 /*
3171                  * An ordinary successful query!
3172                  */
3173                 result = ISC_R_SUCCESS;
3174         }
3175
3176         if (type != dns_rdatatype_any || result == DNS_R_NCACHENXDOMAIN ||
3177             result == DNS_R_NCACHENXRRSET) {
3178                 bind_rdataset(search.rbtdb, node, found, search.now,
3179                               rdataset);
3180                 if (foundsig != NULL)
3181                         bind_rdataset(search.rbtdb, node, foundsig, search.now,
3182                                       sigrdataset);
3183         }
3184
3185  node_exit:
3186         UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
3187
3188  tree_exit:
3189         RWUNLOCK(&search.rbtdb->tree_lock, isc_rwlocktype_read);
3190
3191         /*
3192          * If we found a zonecut but aren't going to use it, we have to
3193          * let go of it.
3194          */
3195         if (search.need_cleanup) {
3196                 node = search.zonecut;
3197                 lock = &(search.rbtdb->node_locks[node->locknum].lock);
3198
3199                 LOCK(lock);
3200                 INSIST(node->references > 0);
3201                 node->references--;
3202                 if (node->references == 0)
3203                         no_references(search.rbtdb, node, 0,
3204                                       isc_rwlocktype_none);
3205                 UNLOCK(lock);
3206         }
3207
3208         dns_rbtnodechain_reset(&search.chain);
3209
3210         return (result);
3211 }
3212
3213 static isc_result_t
3214 cache_findzonecut(dns_db_t *db, dns_name_t *name, unsigned int options,
3215                   isc_stdtime_t now, dns_dbnode_t **nodep,
3216                   dns_name_t *foundname,
3217                   dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset)
3218 {
3219         dns_rbtnode_t *node = NULL;
3220         isc_result_t result;
3221         rbtdb_search_t search;
3222         rdatasetheader_t *header, *header_prev, *header_next;
3223         rdatasetheader_t *found, *foundsig;
3224         unsigned int rbtoptions = DNS_RBTFIND_EMPTYDATA;
3225
3226         search.rbtdb = (dns_rbtdb_t *)db;
3227
3228         REQUIRE(VALID_RBTDB(search.rbtdb));
3229
3230         if (now == 0)
3231                 isc_stdtime_get(&now);
3232
3233         search.rbtversion = NULL;
3234         search.serial = 1;
3235         search.options = options;
3236         search.copy_name = ISC_FALSE;
3237         search.need_cleanup = ISC_FALSE;
3238         search.wild = ISC_FALSE;
3239         search.zonecut = NULL;
3240         dns_fixedname_init(&search.zonecut_name);
3241         dns_rbtnodechain_init(&search.chain, search.rbtdb->common.mctx);
3242         search.now = now;
3243
3244         if ((options & DNS_DBFIND_NOEXACT) != 0)
3245                 rbtoptions |= DNS_RBTFIND_NOEXACT;
3246
3247         RWLOCK(&search.rbtdb->tree_lock, isc_rwlocktype_read);
3248
3249         /*
3250          * Search down from the root of the tree.
3251          */
3252         result = dns_rbt_findnode(search.rbtdb->tree, name, foundname, &node,
3253                                   &search.chain, rbtoptions, NULL, &search);
3254
3255         if (result == DNS_R_PARTIALMATCH) {
3256         find_ns:
3257                 result = find_deepest_zonecut(&search, node, nodep, foundname,
3258                                               rdataset, sigrdataset);
3259                 goto tree_exit;
3260         } else if (result != ISC_R_SUCCESS)
3261                 goto tree_exit;
3262
3263         /*
3264          * We now go looking for an NS rdataset at the node.
3265          */
3266
3267         LOCK(&(search.rbtdb->node_locks[node->locknum].lock));
3268
3269         found = NULL;
3270         foundsig = NULL;
3271         header_prev = NULL;
3272         for (header = node->data; header != NULL; header = header_next) {
3273                 header_next = header->next;
3274                 if (header->ttl <= now) {
3275                         /*
3276                          * This rdataset is stale.  If no one else is using the
3277                          * node, we can clean it up right now, otherwise we
3278                          * mark it as stale, and the node as dirty, so it will
3279                          * get cleaned up later.
3280                          */
3281                         if (header->ttl > now - RBTDB_VIRTUAL)
3282                                 header_prev = header;
3283                         else if (node->references == 0) {
3284                                 INSIST(header->down == NULL);
3285                                 if (header_prev != NULL)
3286                                         header_prev->next = header->next;
3287                                 else
3288                                         node->data = header->next;
3289                                 free_rdataset(search.rbtdb->common.mctx,
3290                                               header);
3291                         } else {
3292                                 header->attributes |= RDATASET_ATTR_STALE;
3293                                 node->dirty = 1;
3294                                 header_prev = header;
3295                         }
3296                 } else if (EXISTS(header)) {
3297                         /*
3298                          * If we found a type we were looking for, remember
3299                          * it.
3300                          */
3301                         if (header->type == dns_rdatatype_ns) {
3302                                 /*
3303                                  * Remember a NS rdataset even if we're
3304                                  * not specifically looking for it, because
3305                                  * we might need it later.
3306                                  */
3307                                 found = header;
3308                         } else if (header->type == RBTDB_RDATATYPE_SIGNS) {
3309                                 /*
3310                                  * If we need the NS rdataset, we'll also
3311                                  * need its signature.
3312                                  */
3313                                 foundsig = header;
3314                         }
3315                         header_prev = header;
3316                 } else
3317                         header_prev = header;
3318         }
3319
3320         if (found == NULL) {
3321                 /*
3322                  * No NS records here.
3323                  */
3324                 UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
3325                 goto find_ns;
3326         }
3327
3328         if (nodep != NULL) {
3329                 new_reference(search.rbtdb, node);
3330                 *nodep = node;
3331         }
3332
3333         bind_rdataset(search.rbtdb, node, found, search.now, rdataset);
3334         if (foundsig != NULL)
3335                 bind_rdataset(search.rbtdb, node, foundsig, search.now,
3336                               sigrdataset);
3337
3338         UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
3339
3340  tree_exit:
3341         RWUNLOCK(&search.rbtdb->tree_lock, isc_rwlocktype_read);
3342
3343         INSIST(!search.need_cleanup);
3344
3345         dns_rbtnodechain_reset(&search.chain);
3346
3347         if (result == DNS_R_DELEGATION)
3348                 result = ISC_R_SUCCESS;
3349
3350         return (result);
3351 }
3352
3353 static void
3354 attachnode(dns_db_t *db, dns_dbnode_t *source, dns_dbnode_t **targetp) {
3355         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3356         dns_rbtnode_t *node = (dns_rbtnode_t *)source;
3357
3358         REQUIRE(VALID_RBTDB(rbtdb));
3359         REQUIRE(targetp != NULL && *targetp == NULL);
3360
3361         LOCK(&rbtdb->node_locks[node->locknum].lock);
3362         INSIST(node->references > 0);
3363         node->references++;
3364         INSIST(node->references != 0);                  /* Catch overflow. */
3365         UNLOCK(&rbtdb->node_locks[node->locknum].lock);
3366
3367         *targetp = source;
3368 }
3369
3370 static void
3371 detachnode(dns_db_t *db, dns_dbnode_t **targetp) {
3372         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3373         dns_rbtnode_t *node;
3374         isc_boolean_t want_free = ISC_FALSE;
3375         isc_boolean_t inactive = ISC_FALSE;
3376         unsigned int locknum;
3377
3378         REQUIRE(VALID_RBTDB(rbtdb));
3379         REQUIRE(targetp != NULL && *targetp != NULL);
3380
3381         node = (dns_rbtnode_t *)(*targetp);
3382         locknum = node->locknum;
3383
3384         LOCK(&rbtdb->node_locks[locknum].lock);
3385
3386         INSIST(node->references > 0);
3387         node->references--;
3388         if (node->references == 0) {
3389                 no_references(rbtdb, node, 0, isc_rwlocktype_none);
3390                 if (rbtdb->node_locks[locknum].references == 0 &&
3391                     rbtdb->node_locks[locknum].exiting)
3392                         inactive = ISC_TRUE;
3393         }
3394
3395         UNLOCK(&rbtdb->node_locks[locknum].lock);
3396
3397         *targetp = NULL;
3398
3399         if (inactive) {
3400                 LOCK(&rbtdb->lock);
3401                 rbtdb->active--;
3402                 if (rbtdb->active == 0)
3403                         want_free = ISC_TRUE;
3404                 UNLOCK(&rbtdb->lock);
3405                 if (want_free) {
3406                         char buf[DNS_NAME_FORMATSIZE];
3407                         if (dns_name_dynamic(&rbtdb->common.origin))
3408                                 dns_name_format(&rbtdb->common.origin, buf,
3409                                                 sizeof(buf));
3410                         else
3411                                 strcpy(buf, "<UNKNOWN>");
3412                         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
3413                                       DNS_LOGMODULE_CACHE, ISC_LOG_DEBUG(1),
3414                                       "calling free_rbtdb(%s)", buf);
3415                         free_rbtdb(rbtdb, ISC_TRUE, NULL);
3416                 }
3417         }
3418 }
3419
3420 static isc_result_t
3421 expirenode(dns_db_t *db, dns_dbnode_t *node, isc_stdtime_t now) {
3422         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3423         dns_rbtnode_t *rbtnode = node;
3424         rdatasetheader_t *header;
3425         isc_boolean_t force_expire = ISC_FALSE;
3426         /*
3427          * These are the category and module used by the cache cleaner.
3428          */
3429         isc_boolean_t log = ISC_FALSE;
3430         isc_logcategory_t *category = DNS_LOGCATEGORY_DATABASE;
3431         isc_logmodule_t *module = DNS_LOGMODULE_CACHE;
3432         int level = ISC_LOG_DEBUG(2);
3433         char printname[DNS_NAME_FORMATSIZE];
3434
3435         REQUIRE(VALID_RBTDB(rbtdb));
3436
3437         /*
3438          * Caller must hold a tree lock.
3439          */
3440
3441         if (now == 0)
3442                 isc_stdtime_get(&now);
3443
3444         if (rbtdb->overmem) {
3445                 isc_uint32_t val;
3446
3447                 isc_random_get(&val);
3448                 /*
3449                  * XXXDCL Could stand to have a better policy, like LRU.
3450                  */
3451                 force_expire = ISC_TF(rbtnode->down == NULL && val % 4 == 0);
3452
3453                 /*
3454                  * Note that 'log' can be true IFF rbtdb->overmem is also true.
3455                  * rbtdb->ovemem can currently only be true for cache databases
3456                  * -- hence all of the "overmem cache" log strings.
3457                  */
3458                 log = ISC_TF(isc_log_wouldlog(dns_lctx, level));
3459                 if (log)
3460                         isc_log_write(dns_lctx, category, module, level,
3461                                       "overmem cache: %s %s",
3462                                       force_expire ? "FORCE" : "check",
3463                                       dns_rbt_formatnodename(rbtnode,
3464                                                            printname,
3465                                                            sizeof(printname)));
3466         }
3467
3468         LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3469
3470         for (header = rbtnode->data; header != NULL; header = header->next)
3471                 if (header->ttl <= now - RBTDB_VIRTUAL) {
3472                         /*
3473                          * We don't check if rbtnode->references == 0 and try
3474                          * to free like we do in cache_find(), because
3475                          * rbtnode->references must be non-zero.  This is so
3476                          * because 'node' is an argument to the function.
3477                          */
3478                         header->attributes |= RDATASET_ATTR_STALE;
3479                         rbtnode->dirty = 1;
3480                         if (log)
3481                                 isc_log_write(dns_lctx, category, module,
3482                                               level, "overmem cache: stale %s",
3483                                               printname);
3484                 } else if (force_expire) {
3485                         if (! RETAIN(header)) {
3486                                 header->ttl = 0;
3487                                 header->attributes |= RDATASET_ATTR_STALE;
3488                                 rbtnode->dirty = 1;
3489                         } else if (log) {
3490                                 isc_log_write(dns_lctx, category, module,
3491                                               level, "overmem cache: "
3492                                               "reprieve by RETAIN() %s",
3493                                               printname);
3494                         }
3495                 } else if (rbtdb->overmem && log)
3496                         isc_log_write(dns_lctx, category, module, level,
3497                                       "overmem cache: saved %s", printname);
3498
3499         UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3500
3501         return (ISC_R_SUCCESS);
3502 }
3503
3504 static void
3505 overmem(dns_db_t *db, isc_boolean_t overmem) {
3506         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3507
3508         if (IS_CACHE(rbtdb)) {
3509                 rbtdb->overmem = overmem;
3510         }
3511 }
3512
3513 static void
3514 printnode(dns_db_t *db, dns_dbnode_t *node, FILE *out) {
3515         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3516         dns_rbtnode_t *rbtnode = node;
3517         isc_boolean_t first;
3518
3519         REQUIRE(VALID_RBTDB(rbtdb));
3520
3521         LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3522
3523         fprintf(out, "node %p, %u references, locknum = %u\n",
3524                 rbtnode, rbtnode->references, rbtnode->locknum);
3525         if (rbtnode->data != NULL) {
3526                 rdatasetheader_t *current, *top_next;
3527
3528                 for (current = rbtnode->data; current != NULL;
3529                      current = top_next) {
3530                         top_next = current->next;
3531                         first = ISC_TRUE;
3532                         fprintf(out, "\ttype %u", current->type);
3533                         do {
3534                                 if (!first)
3535                                         fprintf(out, "\t");
3536                                 first = ISC_FALSE;
3537                                 fprintf(out,
3538                                         "\tserial = %lu, ttl = %u, "
3539                                         "trust = %u, attributes = %u\n",
3540                                         (unsigned long)current->serial,
3541                                         current->ttl,
3542                                         current->trust,
3543                                         current->attributes);
3544                                 current = current->down;
3545                         } while (current != NULL);
3546                 }
3547         } else
3548                 fprintf(out, "(empty)\n");
3549
3550         UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3551 }
3552
3553 static isc_result_t
3554 createiterator(dns_db_t *db, isc_boolean_t relative_names,
3555                dns_dbiterator_t **iteratorp)
3556 {
3557         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3558         rbtdb_dbiterator_t *rbtdbiter;
3559
3560         REQUIRE(VALID_RBTDB(rbtdb));
3561
3562         rbtdbiter = isc_mem_get(rbtdb->common.mctx, sizeof(*rbtdbiter));
3563         if (rbtdbiter == NULL)
3564                 return (ISC_R_NOMEMORY);
3565
3566         rbtdbiter->common.methods = &dbiterator_methods;
3567         rbtdbiter->common.db = NULL;
3568         dns_db_attach(db, &rbtdbiter->common.db);
3569         rbtdbiter->common.relative_names = relative_names;
3570         rbtdbiter->common.magic = DNS_DBITERATOR_MAGIC;
3571         rbtdbiter->common.cleaning = ISC_FALSE;
3572         rbtdbiter->paused = ISC_TRUE;
3573         rbtdbiter->tree_locked = isc_rwlocktype_none;
3574         rbtdbiter->result = ISC_R_SUCCESS;
3575         dns_fixedname_init(&rbtdbiter->name);
3576         dns_fixedname_init(&rbtdbiter->origin);
3577         rbtdbiter->node = NULL;
3578         rbtdbiter->delete = 0;
3579         memset(rbtdbiter->deletions, 0, sizeof(rbtdbiter->deletions));
3580         dns_rbtnodechain_init(&rbtdbiter->chain, db->mctx);
3581
3582         *iteratorp = (dns_dbiterator_t *)rbtdbiter;
3583
3584         return (ISC_R_SUCCESS);
3585 }
3586
3587 static isc_result_t
3588 zone_findrdataset(dns_db_t *db, dns_dbnode_t *node, dns_dbversion_t *version,
3589                   dns_rdatatype_t type, dns_rdatatype_t covers,
3590                   isc_stdtime_t now, dns_rdataset_t *rdataset,
3591                   dns_rdataset_t *sigrdataset)
3592 {
3593         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3594         dns_rbtnode_t *rbtnode = (dns_rbtnode_t *)node;
3595         rdatasetheader_t *header, *header_next, *found, *foundsig;
3596         rbtdb_serial_t serial;
3597         rbtdb_version_t *rbtversion = version;
3598         isc_boolean_t close_version = ISC_FALSE;
3599         rbtdb_rdatatype_t matchtype, sigmatchtype;
3600
3601         REQUIRE(VALID_RBTDB(rbtdb));
3602         REQUIRE(type != dns_rdatatype_any);
3603
3604         if (rbtversion == NULL) {
3605                 currentversion(db, (dns_dbversion_t **) (void *)(&rbtversion));
3606                 close_version = ISC_TRUE;
3607         }
3608         serial = rbtversion->serial;
3609         now = 0;
3610
3611         LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3612
3613         found = NULL;
3614         foundsig = NULL;
3615         matchtype = RBTDB_RDATATYPE_VALUE(type, covers);
3616         if (covers == 0)
3617                 sigmatchtype = RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, type);
3618         else
3619                 sigmatchtype = 0;
3620
3621         for (header = rbtnode->data; header != NULL; header = header_next) {
3622                 header_next = header->next;
3623                 do {
3624                         if (header->serial <= serial &&
3625                             !IGNORE(header)) {
3626                                 /*
3627                                  * Is this a "this rdataset doesn't
3628                                  * exist" record?
3629                                  */
3630                                 if (NONEXISTENT(header))
3631                                         header = NULL;
3632                                 break;
3633                         } else
3634                                 header = header->down;
3635                 } while (header != NULL);
3636                 if (header != NULL) {
3637                         /*
3638                          * We have an active, extant rdataset.  If it's a
3639                          * type we're looking for, remember it.
3640                          */
3641                         if (header->type == matchtype) {
3642                                 found = header;
3643                                 if (foundsig != NULL)
3644                                         break;
3645                         } else if (header->type == sigmatchtype) {
3646                                 foundsig = header;
3647                                 if (found != NULL)
3648                                         break;
3649                         }
3650                 }
3651         }
3652         if (found != NULL) {
3653                 bind_rdataset(rbtdb, rbtnode, found, now, rdataset);
3654                 if (foundsig != NULL)
3655                         bind_rdataset(rbtdb, rbtnode, foundsig, now,
3656                                       sigrdataset);
3657         }
3658
3659         UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3660
3661         if (close_version)
3662                 closeversion(db, (dns_dbversion_t **) (void *)(&rbtversion),
3663                              ISC_FALSE);
3664
3665         if (found == NULL)
3666                 return (ISC_R_NOTFOUND);
3667
3668         return (ISC_R_SUCCESS);
3669 }
3670
3671 static isc_result_t
3672 cache_findrdataset(dns_db_t *db, dns_dbnode_t *node, dns_dbversion_t *version,
3673                    dns_rdatatype_t type, dns_rdatatype_t covers,
3674                    isc_stdtime_t now, dns_rdataset_t *rdataset,
3675                    dns_rdataset_t *sigrdataset)
3676 {
3677         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3678         dns_rbtnode_t *rbtnode = (dns_rbtnode_t *)node;
3679         rdatasetheader_t *header, *header_next, *found, *foundsig;
3680         rbtdb_rdatatype_t matchtype, sigmatchtype, negtype;
3681         isc_result_t result;
3682
3683         REQUIRE(VALID_RBTDB(rbtdb));
3684         REQUIRE(type != dns_rdatatype_any);
3685
3686         UNUSED(version);
3687
3688         result = ISC_R_SUCCESS;
3689
3690         if (now == 0)
3691                 isc_stdtime_get(&now);
3692
3693         LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3694
3695         found = NULL;
3696         foundsig = NULL;
3697         matchtype = RBTDB_RDATATYPE_VALUE(type, covers);
3698         negtype = RBTDB_RDATATYPE_VALUE(0, type);
3699         if (covers == 0)
3700                 sigmatchtype = RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, type);
3701         else
3702                 sigmatchtype = 0;
3703
3704         for (header = rbtnode->data; header != NULL; header = header_next) {
3705                 header_next = header->next;
3706                 if (header->ttl <= now) {
3707                         /*
3708                          * We don't check if rbtnode->references == 0 and try
3709                          * to free like we do in cache_find(), because
3710                          * rbtnode->references must be non-zero.  This is so
3711                          * because 'node' is an argument to the function.
3712                          */
3713                         if (header->ttl <= now - RBTDB_VIRTUAL) {
3714                                 header->attributes |= RDATASET_ATTR_STALE;
3715                                 rbtnode->dirty = 1;
3716                         }
3717                 } else if (EXISTS(header)) {
3718                         if (header->type == matchtype)
3719                                 found = header;
3720                         else if (header->type == RBTDB_RDATATYPE_NCACHEANY ||
3721                                  header->type == negtype)
3722                                 found = header;
3723                         else if (header->type == sigmatchtype)
3724                                 foundsig = header;
3725                 }
3726         }
3727         if (found != NULL) {
3728                 bind_rdataset(rbtdb, rbtnode, found, now, rdataset);
3729                 if (foundsig != NULL)
3730                         bind_rdataset(rbtdb, rbtnode, foundsig, now,
3731                                       sigrdataset);
3732         }
3733
3734         UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3735
3736         if (found == NULL)
3737                 return (ISC_R_NOTFOUND);
3738
3739         if (RBTDB_RDATATYPE_BASE(found->type) == 0) {
3740                 /*
3741                  * We found a negative cache entry.
3742                  */
3743                 if (NXDOMAIN(found))
3744                         result = DNS_R_NCACHENXDOMAIN;
3745                 else
3746                         result = DNS_R_NCACHENXRRSET;
3747         }
3748
3749         return (result);
3750 }
3751
3752 static isc_result_t
3753 allrdatasets(dns_db_t *db, dns_dbnode_t *node, dns_dbversion_t *version,
3754              isc_stdtime_t now, dns_rdatasetiter_t **iteratorp)
3755 {
3756         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3757         dns_rbtnode_t *rbtnode = (dns_rbtnode_t *)node;
3758         rbtdb_version_t *rbtversion = version;
3759         rbtdb_rdatasetiter_t *iterator;
3760
3761         REQUIRE(VALID_RBTDB(rbtdb));
3762
3763         iterator = isc_mem_get(rbtdb->common.mctx, sizeof(*iterator));
3764         if (iterator == NULL)
3765                 return (ISC_R_NOMEMORY);
3766
3767         if ((db->attributes & DNS_DBATTR_CACHE) == 0) {
3768                 now = 0;
3769                 if (rbtversion == NULL)
3770                         currentversion(db,
3771                                  (dns_dbversion_t **) (void *)(&rbtversion));
3772                 else {
3773                         LOCK(&rbtdb->lock);
3774                         INSIST(rbtversion->references > 0);
3775                         rbtversion->references++;
3776                         INSIST(rbtversion->references != 0);
3777                         UNLOCK(&rbtdb->lock);
3778                 }
3779         } else {
3780                 if (now == 0)
3781                         isc_stdtime_get(&now);
3782                 rbtversion = NULL;
3783         }
3784
3785         iterator->common.magic = DNS_RDATASETITER_MAGIC;
3786         iterator->common.methods = &rdatasetiter_methods;
3787         iterator->common.db = db;
3788         iterator->common.node = node;
3789         iterator->common.version = (dns_dbversion_t *)rbtversion;
3790         iterator->common.now = now;
3791
3792         LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3793
3794         INSIST(rbtnode->references > 0);
3795         rbtnode->references++;
3796         INSIST(rbtnode->references != 0);
3797         iterator->current = NULL;
3798
3799         UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3800
3801         *iteratorp = (dns_rdatasetiter_t *)iterator;
3802
3803         return (ISC_R_SUCCESS);
3804 }
3805
3806 static isc_boolean_t
3807 cname_and_other_data(dns_rbtnode_t *node, rbtdb_serial_t serial) {
3808         rdatasetheader_t *header, *header_next;
3809         isc_boolean_t cname, other_data;
3810         dns_rdatatype_t rdtype;
3811
3812         /*
3813          * The caller must hold the node lock.
3814          */
3815
3816         /*
3817          * Look for CNAME and "other data" rdatasets active in our version.
3818          */
3819         cname = ISC_FALSE;
3820         other_data = ISC_FALSE;
3821         for (header = node->data; header != NULL; header = header_next) {
3822                 header_next = header->next;
3823                 if (header->type == dns_rdatatype_cname) {
3824                         /*
3825                          * Look for an active extant CNAME.
3826                          */
3827                         do {
3828                                 if (header->serial <= serial &&
3829                                     !IGNORE(header)) {
3830                                         /*
3831                                          * Is this a "this rdataset doesn't
3832                                          * exist" record?
3833                                          */
3834                                         if (NONEXISTENT(header))
3835                                                 header = NULL;
3836                                         break;
3837                                 } else
3838                                         header = header->down;
3839                         } while (header != NULL);
3840                         if (header != NULL)
3841                                 cname = ISC_TRUE;
3842                 } else {
3843                         /*
3844                          * Look for active extant "other data".
3845                          *
3846                          * "Other data" is any rdataset whose type is not
3847                          * KEY, RRSIG KEY, NSEC, RRSIG NSEC or RRSIG CNAME.
3848                          */
3849                         rdtype = RBTDB_RDATATYPE_BASE(header->type);
3850                         if (rdtype == dns_rdatatype_rrsig ||
3851                             rdtype == dns_rdatatype_sig)
3852                                 rdtype = RBTDB_RDATATYPE_EXT(header->type);
3853                         if (rdtype != dns_rdatatype_nsec &&
3854                             rdtype != dns_rdatatype_key &&
3855                             rdtype != dns_rdatatype_cname) {
3856                                 /*
3857                                  * We've found a type that isn't
3858                                  * NSEC, KEY, CNAME, or one of their
3859                                  * signatures.  Is it active and extant?
3860                                  */
3861                                 do {
3862                                         if (header->serial <= serial &&
3863                                             !IGNORE(header)) {
3864                                                 /*
3865                                                  * Is this a "this rdataset
3866                                                  * doesn't exist" record?
3867                                                  */
3868                                                 if (NONEXISTENT(header))
3869                                                         header = NULL;
3870                                                 break;
3871                                         } else
3872                                                 header = header->down;
3873                                 } while (header != NULL);
3874                                 if (header != NULL)
3875                                         other_data = ISC_TRUE;
3876                         }
3877                 }
3878         }
3879
3880         if (cname && other_data)
3881                 return (ISC_TRUE);
3882
3883         return (ISC_FALSE);
3884 }
3885
3886 static isc_result_t
3887 add(dns_rbtdb_t *rbtdb, dns_rbtnode_t *rbtnode, rbtdb_version_t *rbtversion,
3888     rdatasetheader_t *newheader, unsigned int options, isc_boolean_t loading,
3889     dns_rdataset_t *addedrdataset, isc_stdtime_t now)
3890 {
3891         rbtdb_changed_t *changed = NULL;
3892         rdatasetheader_t *topheader, *topheader_prev, *header;
3893         unsigned char *merged;
3894         isc_result_t result;
3895         isc_boolean_t header_nx;
3896         isc_boolean_t newheader_nx;
3897         isc_boolean_t merge;
3898         dns_rdatatype_t rdtype, covers;
3899         rbtdb_rdatatype_t negtype;
3900         dns_trust_t trust;
3901
3902         /*
3903          * Add an rdatasetheader_t to a node.
3904          */
3905
3906         /*
3907          * Caller must be holding the node lock.
3908          */
3909
3910         if ((options & DNS_DBADD_MERGE) != 0) {
3911                 REQUIRE(rbtversion != NULL);
3912                 merge = ISC_TRUE;
3913         } else
3914                 merge = ISC_FALSE;
3915
3916         if ((options & DNS_DBADD_FORCE) != 0)
3917                 trust = dns_trust_ultimate;
3918         else
3919                 trust = newheader->trust;
3920
3921         if (rbtversion != NULL && !loading) {
3922                 /*
3923                  * We always add a changed record, even if no changes end up
3924                  * being made to this node, because it's harmless and
3925                  * simplifies the code.
3926                  */
3927                 changed = add_changed(rbtdb, rbtversion, rbtnode);
3928                 if (changed == NULL) {
3929                         free_rdataset(rbtdb->common.mctx, newheader);
3930                         return (ISC_R_NOMEMORY);
3931                 }
3932         }
3933
3934         newheader_nx = NONEXISTENT(newheader) ? ISC_TRUE : ISC_FALSE;
3935         topheader_prev = NULL;
3936
3937         negtype = 0;
3938         if (rbtversion == NULL && !newheader_nx) {
3939                 rdtype = RBTDB_RDATATYPE_BASE(newheader->type);
3940                 if (rdtype == 0) {
3941                         /*
3942                          * We're adding a negative cache entry.
3943                          */
3944                         covers = RBTDB_RDATATYPE_EXT(newheader->type);
3945                         if (covers == dns_rdatatype_any) {
3946                                 /*
3947                                  * We're adding an negative cache entry
3948                                  * which covers all types (NXDOMAIN,
3949                                  * NODATA(QTYPE=ANY)).
3950                                  *
3951                                  * We make all other data stale so that the
3952                                  * only rdataset that can be found at this
3953                                  * node is the negative cache entry.
3954                                  */
3955                                 for (topheader = rbtnode->data;
3956                                      topheader != NULL;
3957                                      topheader = topheader->next) {
3958                                         topheader->ttl = 0;
3959                                         topheader->attributes |=
3960                                                 RDATASET_ATTR_STALE;
3961                                 }
3962                                 rbtnode->dirty = 1;
3963                                 goto find_header;
3964                         }
3965                         negtype = RBTDB_RDATATYPE_VALUE(covers, 0);
3966                 } else {
3967                         /*
3968                          * We're adding something that isn't a
3969                          * negative cache entry.  Look for an extant
3970                          * non-stale NXDOMAIN/NODATA(QTYPE=ANY) negative
3971                          * cache entry.
3972                          */
3973                         for (topheader = rbtnode->data;
3974                              topheader != NULL;
3975                              topheader = topheader->next) {
3976                                 if (topheader->type ==
3977                                     RBTDB_RDATATYPE_NCACHEANY)
3978                                         break;
3979                         }
3980                         if (topheader != NULL && EXISTS(topheader) &&
3981                             topheader->ttl > now) {
3982                                 /*
3983                                  * Found one.
3984                                  */
3985                                 if (trust < topheader->trust) {
3986                                         /*
3987                                          * The NXDOMAIN/NODATA(QTYPE=ANY)
3988                                          * is more trusted.
3989                                          */
3990                                         free_rdataset(rbtdb->common.mctx,
3991                                                       newheader);
3992                                         if (addedrdataset != NULL)
3993                                                 bind_rdataset(rbtdb, rbtnode,
3994                                                               topheader, now,
3995                                                               addedrdataset);
3996                                         return (DNS_R_UNCHANGED);
3997                                 }
3998                                 /*
3999                                  * The new rdataset is better.  Expire the
4000                                  * NXDOMAIN/NODATA(QTYPE=ANY).
4001                                  */
4002                                 topheader->ttl = 0;
4003                                 topheader->attributes |= RDATASET_ATTR_STALE;
4004                                 rbtnode->dirty = 1;
4005                                 topheader = NULL;
4006                                 goto find_header;
4007                         }
4008                         negtype = RBTDB_RDATATYPE_VALUE(0, rdtype);
4009                 }
4010         }
4011
4012         for (topheader = rbtnode->data;
4013              topheader != NULL;
4014              topheader = topheader->next) {
4015                 if (topheader->type == newheader->type ||
4016                     topheader->type == negtype)
4017                         break;
4018                 topheader_prev = topheader;
4019         }
4020
4021  find_header:
4022         /*
4023          * If header isn't NULL, we've found the right type.  There may be
4024          * IGNORE rdatasets between the top of the chain and the first real
4025          * data.  We skip over them.
4026          */
4027         header = topheader;
4028         while (header != NULL && IGNORE(header))
4029                 header = header->down;
4030         if (header != NULL) {
4031                 header_nx = NONEXISTENT(header) ? ISC_TRUE : ISC_FALSE;
4032
4033                 /*
4034                  * Deleting an already non-existent rdataset has no effect.
4035                  */
4036                 if (header_nx && newheader_nx) {
4037                         free_rdataset(rbtdb->common.mctx, newheader);
4038                         return (DNS_R_UNCHANGED);
4039                 }
4040
4041                 /*
4042                  * Trying to add an rdataset with lower trust to a cache DB
4043                  * has no effect, provided that the cache data isn't stale.
4044                  */
4045                 if (rbtversion == NULL && trust < header->trust &&
4046                     (header->ttl > now || header_nx)) {
4047                         free_rdataset(rbtdb->common.mctx, newheader);
4048                         if (addedrdataset != NULL)
4049                                 bind_rdataset(rbtdb, rbtnode, header, now,
4050                                               addedrdataset);
4051                         return (DNS_R_UNCHANGED);
4052                 }
4053
4054                 /*
4055                  * Don't merge if a nonexistent rdataset is involved.
4056                  */
4057                 if (merge && (header_nx || newheader_nx))
4058                         merge = ISC_FALSE;
4059
4060                 /*
4061                  * If 'merge' is ISC_TRUE, we'll try to create a new rdataset
4062                  * that is the union of 'newheader' and 'header'.
4063                  */
4064                 if (merge) {
4065                         unsigned int flags = 0;
4066                         INSIST(rbtversion->serial >= header->serial);
4067                         merged = NULL;
4068                         result = ISC_R_SUCCESS;
4069
4070                         if ((options & DNS_DBADD_EXACT) != 0)
4071                                 flags |= DNS_RDATASLAB_EXACT;
4072                         if ((options & DNS_DBADD_EXACTTTL) != 0 &&
4073                              newheader->ttl != header->ttl)
4074                                         result = DNS_R_NOTEXACT;
4075                         else if (newheader->ttl != header->ttl)
4076                                 flags |= DNS_RDATASLAB_FORCE;
4077                         if (result == ISC_R_SUCCESS)
4078                                 result = dns_rdataslab_merge(
4079                                              (unsigned char *)header,
4080                                              (unsigned char *)newheader,
4081                                              (unsigned int)(sizeof(*newheader)),
4082                                              rbtdb->common.mctx,
4083                                              rbtdb->common.rdclass,
4084                                              (dns_rdatatype_t)header->type,
4085                                              flags, &merged);
4086                         if (result == ISC_R_SUCCESS) {
4087                                 /*
4088                                  * If 'header' has the same serial number as
4089                                  * we do, we could clean it up now if we knew
4090                                  * that our caller had no references to it.
4091                                  * We don't know this, however, so we leave it
4092                                  * alone.  It will get cleaned up when
4093                                  * clean_zone_node() runs.
4094                                  */
4095                                 free_rdataset(rbtdb->common.mctx, newheader);
4096                                 newheader = (rdatasetheader_t *)merged;
4097                         } else {
4098                                 free_rdataset(rbtdb->common.mctx, newheader);
4099                                 return (result);
4100                         }
4101                 }
4102                 /*
4103                  * Don't replace existing NS, A and AAAA RRsets
4104                  * in the cache if they are already exist.  This
4105                  * prevents named being locked to old servers.
4106                  * Don't lower trust of existing record if the
4107                  * update is forced.
4108                  */
4109                 if (IS_CACHE(rbtdb) && header->ttl > now &&
4110                     header->type == dns_rdatatype_ns &&
4111                     !header_nx && !newheader_nx &&
4112                     header->trust >= newheader->trust &&
4113                     dns_rdataslab_equalx((unsigned char *)header,
4114                                          (unsigned char *)newheader,
4115                                          (unsigned int)(sizeof(*newheader)),
4116                                          rbtdb->common.rdclass,
4117                                          (dns_rdatatype_t)header->type)) {
4118                         /*
4119                          * Honour the new ttl if it is less than the
4120                          * older one.
4121                          */
4122                         if (header->ttl > newheader->ttl)
4123                                 header->ttl = newheader->ttl;
4124                         if (header->noqname == NULL &&
4125                             newheader->noqname != NULL) {
4126                                 header->noqname = newheader->noqname;
4127                                 newheader->noqname = NULL;
4128                         }
4129                         free_rdataset(rbtdb->common.mctx, newheader);
4130                         if (addedrdataset != NULL)
4131                                 bind_rdataset(rbtdb, rbtnode, header, now,
4132                                               addedrdataset);
4133                         return (ISC_R_SUCCESS);
4134                 }
4135                 if (IS_CACHE(rbtdb) && header->ttl > now &&
4136                     (header->type == dns_rdatatype_a ||
4137                      header->type == dns_rdatatype_aaaa) &&
4138                     !header_nx && !newheader_nx &&
4139                     header->trust >= newheader->trust &&
4140                     dns_rdataslab_equal((unsigned char *)header,
4141                                         (unsigned char *)newheader,
4142                                         (unsigned int)(sizeof(*newheader)))) {
4143                         /*
4144                          * Honour the new ttl if it is less than the
4145                          * older one.
4146                          */
4147                         if (header->ttl > newheader->ttl)
4148                                 header->ttl = newheader->ttl;
4149                         if (header->noqname == NULL &&
4150                             newheader->noqname != NULL) {
4151                                 header->noqname = newheader->noqname;
4152                                 newheader->noqname = NULL;
4153                         }
4154                         free_rdataset(rbtdb->common.mctx, newheader);
4155                         if (addedrdataset != NULL)
4156                                 bind_rdataset(rbtdb, rbtnode, header, now,
4157                                               addedrdataset);
4158                         return (ISC_R_SUCCESS);
4159                 }
4160                 INSIST(rbtversion == NULL ||
4161                        rbtversion->serial >= topheader->serial);
4162                 if (topheader_prev != NULL)
4163                         topheader_prev->next = newheader;
4164                 else
4165                         rbtnode->data = newheader;
4166                 newheader->next = topheader->next;
4167                 if (loading) {
4168                         /*
4169                          * There are no other references to 'header' when
4170                          * loading, so we MAY clean up 'header' now.
4171                          * Since we don't generate changed records when
4172                          * loading, we MUST clean up 'header' now.
4173                          */
4174                         newheader->down = NULL;
4175                         free_rdataset(rbtdb->common.mctx, header);
4176                 } else {
4177                         newheader->down = topheader;
4178                         topheader->next = newheader;
4179                         rbtnode->dirty = 1;
4180                         if (changed != NULL)
4181                                 changed->dirty = ISC_TRUE;
4182                         if (rbtversion == NULL) {
4183                                 header->ttl = 0;
4184                                 header->attributes |= RDATASET_ATTR_STALE;
4185                         }
4186                 }
4187         } else {
4188                 /*
4189                  * No non-IGNORED rdatasets of the given type exist at
4190                  * this node.
4191                  */
4192
4193                 /*
4194                  * If we're trying to delete the type, don't bother.
4195                  */
4196                 if (newheader_nx) {
4197                         free_rdataset(rbtdb->common.mctx, newheader);
4198                         return (DNS_R_UNCHANGED);
4199                 }
4200
4201                 if (topheader != NULL) {
4202                         /*
4203                          * We have an list of rdatasets of the given type,
4204                          * but they're all marked IGNORE.  We simply insert
4205                          * the new rdataset at the head of the list.
4206                          *
4207                          * Ignored rdatasets cannot occur during loading, so
4208                          * we INSIST on it.
4209                          */
4210                         INSIST(!loading);
4211                         INSIST(rbtversion == NULL ||
4212                                rbtversion->serial >= topheader->serial);
4213                         if (topheader_prev != NULL)
4214                                 topheader_prev->next = newheader;
4215                         else
4216                                 rbtnode->data = newheader;
4217                         newheader->next = topheader->next;
4218                         newheader->down = topheader;
4219                         topheader->next = newheader;
4220                         rbtnode->dirty = 1;
4221                         if (changed != NULL)
4222                                 changed->dirty = ISC_TRUE;
4223                 } else {
4224                         /*
4225                          * No rdatasets of the given type exist at the node.
4226                          */
4227                         newheader->next = rbtnode->data;
4228                         newheader->down = NULL;
4229                         rbtnode->data = newheader;
4230                 }
4231         }
4232
4233         /*
4234          * Check if the node now contains CNAME and other data.
4235          */
4236         if (rbtversion != NULL &&
4237             cname_and_other_data(rbtnode, rbtversion->serial))
4238                 return (DNS_R_CNAMEANDOTHER);
4239
4240         if (addedrdataset != NULL)
4241                 bind_rdataset(rbtdb, rbtnode, newheader, now, addedrdataset);
4242
4243         return (ISC_R_SUCCESS);
4244 }
4245
4246 static inline isc_boolean_t
4247 delegating_type(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node,
4248                 rbtdb_rdatatype_t type)
4249 {
4250         if (IS_CACHE(rbtdb)) {
4251                 if (type == dns_rdatatype_dname)
4252                         return (ISC_TRUE);
4253                 else
4254                         return (ISC_FALSE);
4255         } else if (type == dns_rdatatype_dname ||
4256                    (type == dns_rdatatype_ns &&
4257                     (node != rbtdb->origin_node || IS_STUB(rbtdb))))
4258                 return (ISC_TRUE);
4259         return (ISC_FALSE);
4260 }
4261
4262 static inline isc_result_t
4263 addnoqname(dns_rbtdb_t *rbtdb, rdatasetheader_t *newheader,
4264            dns_rdataset_t *rdataset)
4265 {
4266         struct noqname *noqname;
4267         isc_mem_t *mctx = rbtdb->common.mctx;
4268         dns_name_t name;
4269         dns_rdataset_t nsec, nsecsig;
4270         isc_result_t result;
4271         isc_region_t r;
4272
4273         dns_name_init(&name, NULL);
4274         dns_rdataset_init(&nsec);
4275         dns_rdataset_init(&nsecsig);
4276
4277         result = dns_rdataset_getnoqname(rdataset, &name, &nsec, &nsecsig);
4278         RUNTIME_CHECK(result == ISC_R_SUCCESS);
4279
4280         noqname = isc_mem_get(mctx, sizeof(*noqname));
4281         if (noqname == NULL) {
4282                 result = ISC_R_NOMEMORY;
4283                 goto cleanup;
4284         }
4285         dns_name_init(&noqname->name, NULL);
4286         noqname->nsec = NULL;
4287         noqname->nsecsig = NULL;
4288         result = dns_name_dup(&name, mctx, &noqname->name);
4289         if (result != ISC_R_SUCCESS)
4290                 goto cleanup;
4291         result = dns_rdataslab_fromrdataset(&nsec, mctx, &r, 0);
4292         if (result != ISC_R_SUCCESS)
4293                 goto cleanup;
4294         noqname->nsec = r.base;
4295         result = dns_rdataslab_fromrdataset(&nsecsig, mctx, &r, 0);
4296         if (result != ISC_R_SUCCESS)
4297                 goto cleanup;
4298         noqname->nsecsig = r.base;
4299         dns_rdataset_disassociate(&nsec);
4300         dns_rdataset_disassociate(&nsecsig);
4301         newheader->noqname = noqname;
4302         return (ISC_R_SUCCESS);
4303
4304 cleanup:
4305         dns_rdataset_disassociate(&nsec);
4306         dns_rdataset_disassociate(&nsecsig);
4307         free_noqname(mctx, &noqname);
4308         return(result);
4309 }
4310
4311 static isc_result_t
4312 addrdataset(dns_db_t *db, dns_dbnode_t *node, dns_dbversion_t *version,
4313             isc_stdtime_t now, dns_rdataset_t *rdataset, unsigned int options,
4314             dns_rdataset_t *addedrdataset)
4315 {
4316         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
4317         dns_rbtnode_t *rbtnode = (dns_rbtnode_t *)node;
4318         rbtdb_version_t *rbtversion = version;
4319         isc_region_t region;
4320         rdatasetheader_t *newheader;
4321         isc_result_t result;
4322         isc_boolean_t delegating;
4323
4324         REQUIRE(VALID_RBTDB(rbtdb));
4325
4326         if (rbtversion == NULL) {
4327                 if (now == 0)
4328                         isc_stdtime_get(&now);
4329         } else
4330                 now = 0;
4331
4332         result = dns_rdataslab_fromrdataset(rdataset, rbtdb->common.mctx,
4333                                             &region,
4334                                             sizeof(rdatasetheader_t));
4335         if (result != ISC_R_SUCCESS)
4336                 return (result);
4337
4338         newheader = (rdatasetheader_t *)region.base;
4339         newheader->ttl = rdataset->ttl + now;
4340         newheader->type = RBTDB_RDATATYPE_VALUE(rdataset->type,
4341                                                 rdataset->covers);
4342         newheader->attributes = 0;
4343         newheader->noqname = NULL;
4344         newheader->count = 0;
4345         newheader->trust = rdataset->trust;
4346         if (rbtversion != NULL) {
4347                 newheader->serial = rbtversion->serial;
4348                 now = 0;
4349         } else {
4350                 newheader->serial = 1;
4351                 if ((rdataset->attributes & DNS_RDATASETATTR_NXDOMAIN) != 0)
4352                         newheader->attributes |= RDATASET_ATTR_NXDOMAIN;
4353                 if ((rdataset->attributes & DNS_RDATASETATTR_NOQNAME) != 0) {
4354                         result = addnoqname(rbtdb, newheader, rdataset);
4355                         if (result != ISC_R_SUCCESS) {
4356                                 free_rdataset(rbtdb->common.mctx, newheader);
4357                                 return (result);
4358                         }
4359                 }
4360         }
4361
4362         /*
4363          * If we're adding a delegation type (e.g. NS or DNAME for a zone,
4364          * just DNAME for the cache), then we need to set the callback bit
4365          * on the node, and to do that we must be holding an exclusive lock
4366          * on the tree.
4367          */
4368         if (delegating_type(rbtdb, rbtnode, rdataset->type)) {
4369                 delegating = ISC_TRUE;
4370                 RWLOCK(&rbtdb->tree_lock, isc_rwlocktype_write);
4371         } else
4372                 delegating = ISC_FALSE;
4373
4374         LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
4375
4376         result = add(rbtdb, rbtnode, rbtversion, newheader, options, ISC_FALSE,
4377                      addedrdataset, now);
4378         if (result == ISC_R_SUCCESS && delegating)
4379                 rbtnode->find_callback = 1;
4380
4381         UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
4382
4383         if (delegating)
4384                 RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_write);
4385
4386         /*
4387          * Update the zone's secure status.  If version is non-NULL
4388          * this is defered until closeversion() is called.
4389          */
4390         if (result == ISC_R_SUCCESS && version == NULL && !IS_CACHE(rbtdb))
4391                 rbtdb->secure = iszonesecure(db, rbtdb->origin_node);
4392
4393         return (result);
4394 }
4395
4396 static isc_result_t
4397 subtractrdataset(dns_db_t *db, dns_dbnode_t *node, dns_dbversion_t *version,
4398                  dns_rdataset_t *rdataset, unsigned int options,
4399                  dns_rdataset_t *newrdataset)
4400 {
4401         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
4402         dns_rbtnode_t *rbtnode = (dns_rbtnode_t *)node;
4403         rbtdb_version_t *rbtversion = version;
4404         rdatasetheader_t *topheader, *topheader_prev, *header, *newheader;
4405         unsigned char *subresult;
4406         isc_region_t region;
4407         isc_result_t result;
4408         rbtdb_changed_t *changed;
4409
4410         REQUIRE(VALID_RBTDB(rbtdb));
4411
4412         result = dns_rdataslab_fromrdataset(rdataset, rbtdb->common.mctx,
4413                                             &region,
4414                                             sizeof(rdatasetheader_t));
4415         if (result != ISC_R_SUCCESS)
4416                 return (result);
4417         newheader = (rdatasetheader_t *)region.base;
4418         newheader->ttl = rdataset->ttl;
4419         newheader->type = RBTDB_RDATATYPE_VALUE(rdataset->type,
4420                                                 rdataset->covers);
4421         newheader->attributes = 0;
4422         newheader->serial = rbtversion->serial;
4423         newheader->trust = 0;
4424         newheader->noqname = NULL;
4425         newheader->count = 0;
4426
4427         LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
4428
4429         changed = add_changed(rbtdb, rbtversion, rbtnode);
4430         if (changed == NULL) {
4431                 free_rdataset(rbtdb->common.mctx, newheader);
4432                 UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
4433                 return (ISC_R_NOMEMORY);
4434         }
4435
4436         topheader_prev = NULL;
4437         for (topheader = rbtnode->data;
4438              topheader != NULL;
4439              topheader = topheader->next) {
4440                 if (topheader->type == newheader->type)
4441                         break;
4442                 topheader_prev = topheader;
4443         }
4444         /*
4445          * If header isn't NULL, we've found the right type.  There may be
4446          * IGNORE rdatasets between the top of the chain and the first real
4447          * data.  We skip over them.
4448          */
4449         header = topheader;
4450         while (header != NULL && IGNORE(header))
4451                 header = header->down;
4452         if (header != NULL && EXISTS(header)) {
4453                 unsigned int flags = 0;
4454                 subresult = NULL;
4455                 result = ISC_R_SUCCESS;
4456                 if ((options & DNS_DBSUB_EXACT) != 0) {
4457                         flags |= DNS_RDATASLAB_EXACT;
4458                         if (newheader->ttl != header->ttl)
4459                                 result = DNS_R_NOTEXACT;
4460                 }
4461                 if (result == ISC_R_SUCCESS)
4462                         result = dns_rdataslab_subtract(
4463                                         (unsigned char *)header,
4464                                         (unsigned char *)newheader,
4465                                         (unsigned int)(sizeof(*newheader)),
4466                                         rbtdb->common.mctx,
4467                                         rbtdb->common.rdclass,
4468                                         (dns_rdatatype_t)header->type,
4469                                         flags, &subresult);
4470                 if (result == ISC_R_SUCCESS) {
4471                         free_rdataset(rbtdb->common.mctx, newheader);
4472                         newheader = (rdatasetheader_t *)subresult;
4473                         /*
4474                          * We have to set the serial since the rdataslab
4475                          * subtraction routine copies the reserved portion of
4476                          * header, not newheader.
4477                          */
4478                         newheader->serial = rbtversion->serial;
4479                 } else if (result == DNS_R_NXRRSET) {
4480                         /*
4481                          * This subtraction would remove all of the rdata;
4482                          * add a nonexistent header instead.
4483                          */
4484                         free_rdataset(rbtdb->common.mctx, newheader);
4485                         newheader = isc_mem_get(rbtdb->common.mctx,
4486                                                 sizeof(*newheader));
4487                         if (newheader == NULL) {
4488                                 result = ISC_R_NOMEMORY;
4489                                 goto unlock;
4490                         }
4491                         newheader->ttl = 0;
4492                         newheader->type = topheader->type;
4493                         newheader->attributes = RDATASET_ATTR_NONEXISTENT;
4494                         newheader->trust = 0;
4495                         newheader->serial = rbtversion->serial;
4496                         newheader->noqname = NULL;
4497                         newheader->count = 0;
4498                 } else {
4499                         free_rdataset(rbtdb->common.mctx, newheader);
4500                         goto unlock;
4501                 }
4502
4503                 /*
4504                  * If we're here, we want to link newheader in front of
4505                  * topheader.
4506                  */
4507                 INSIST(rbtversion->serial >= topheader->serial);
4508                 if (topheader_prev != NULL)
4509                         topheader_prev->next = newheader;
4510                 else
4511                         rbtnode->data = newheader;
4512                 newheader->next = topheader->next;
4513                 newheader->down = topheader;
4514                 topheader->next = newheader;
4515                 rbtnode->dirty = 1;
4516                 changed->dirty = ISC_TRUE;
4517         } else {
4518                 /*
4519                  * The rdataset doesn't exist, so we don't need to do anything
4520                  * to satisfy the deletion request.
4521                  */
4522                 free_rdataset(rbtdb->common.mctx, newheader);
4523                 if ((options & DNS_DBSUB_EXACT) != 0)
4524                         result = DNS_R_NOTEXACT;
4525                 else
4526                         result = DNS_R_UNCHANGED;
4527         }
4528
4529         if (result == ISC_R_SUCCESS && newrdataset != NULL)
4530                 bind_rdataset(rbtdb, rbtnode, newheader, 0, newrdataset);
4531
4532  unlock:
4533         UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
4534
4535         /*
4536          * Update the zone's secure status.  If version is non-NULL
4537          * this is defered until closeversion() is called.
4538          */
4539         if (result == ISC_R_SUCCESS && version == NULL && !IS_CACHE(rbtdb))
4540                 rbtdb->secure = iszonesecure(db, rbtdb->origin_node);
4541
4542         return (result);
4543 }
4544
4545 static isc_result_t
4546 deleterdataset(dns_db_t *db, dns_dbnode_t *node, dns_dbversion_t *version,
4547                dns_rdatatype_t type, dns_rdatatype_t covers)
4548 {
4549         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
4550         dns_rbtnode_t *rbtnode = (dns_rbtnode_t *)node;
4551         rbtdb_version_t *rbtversion = version;
4552         isc_result_t result;
4553         rdatasetheader_t *newheader;
4554
4555         REQUIRE(VALID_RBTDB(rbtdb));
4556
4557         if (type == dns_rdatatype_any)
4558                 return (ISC_R_NOTIMPLEMENTED);
4559         if (type == dns_rdatatype_rrsig && covers == 0)
4560                 return (ISC_R_NOTIMPLEMENTED);
4561
4562         newheader = isc_mem_get(rbtdb->common.mctx, sizeof(*newheader));
4563         if (newheader == NULL)
4564                 return (ISC_R_NOMEMORY);
4565         newheader->ttl = 0;
4566         newheader->type = RBTDB_RDATATYPE_VALUE(type, covers);
4567         newheader->attributes = RDATASET_ATTR_NONEXISTENT;
4568         newheader->trust = 0;
4569         newheader->noqname = NULL;
4570         if (rbtversion != NULL)
4571                 newheader->serial = rbtversion->serial;
4572         else
4573                 newheader->serial = 0;
4574         newheader->count = 0;
4575
4576         LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
4577
4578         result = add(rbtdb, rbtnode, rbtversion, newheader, DNS_DBADD_FORCE,
4579                      ISC_FALSE, NULL, 0);
4580
4581         UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
4582
4583         /*
4584          * Update the zone's secure status.  If version is non-NULL
4585          * this is defered until closeversion() is called.
4586          */
4587         if (result == ISC_R_SUCCESS && version == NULL && !IS_CACHE(rbtdb))
4588                 rbtdb->secure = iszonesecure(db, rbtdb->origin_node);
4589
4590         return (result);
4591 }
4592
4593 static isc_result_t
4594 loading_addrdataset(void *arg, dns_name_t *name, dns_rdataset_t *rdataset) {
4595         rbtdb_load_t *loadctx = arg;
4596         dns_rbtdb_t *rbtdb = loadctx->rbtdb;
4597         dns_rbtnode_t *node;
4598         isc_result_t result;
4599         isc_region_t region;
4600         rdatasetheader_t *newheader;
4601
4602         /*
4603          * This routine does no node locking.  See comments in
4604          * 'load' below for more information on loading and
4605          * locking.
4606          */
4607
4608
4609         /*
4610          * SOA records are only allowed at top of zone.
4611          */
4612         if (rdataset->type == dns_rdatatype_soa &&
4613             !IS_CACHE(rbtdb) && !dns_name_equal(name, &rbtdb->common.origin))
4614                 return (DNS_R_NOTZONETOP);
4615
4616         add_empty_wildcards(rbtdb, name);
4617
4618         if (dns_name_iswildcard(name)) {
4619                 /*
4620                  * NS record owners cannot legally be wild cards.
4621                  */
4622                 if (rdataset->type == dns_rdatatype_ns)
4623                         return (DNS_R_INVALIDNS);
4624                 result = add_wildcard_magic(rbtdb, name);
4625                 if (result != ISC_R_SUCCESS)
4626                         return (result);
4627         }
4628
4629         node = NULL;
4630         result = dns_rbt_addnode(rbtdb->tree, name, &node);
4631         if (result != ISC_R_SUCCESS && result != ISC_R_EXISTS)
4632                 return (result);
4633         if (result != ISC_R_EXISTS) {
4634                 dns_name_t foundname;
4635                 dns_name_init(&foundname, NULL);
4636                 dns_rbt_namefromnode(node, &foundname);
4637 #ifdef DNS_RBT_USEHASH
4638                 node->locknum = node->hashval % rbtdb->node_lock_count;
4639 #else
4640                 node->locknum = dns_name_hash(&foundname, ISC_TRUE) %
4641                         rbtdb->node_lock_count;
4642 #endif
4643         }
4644
4645         result = dns_rdataslab_fromrdataset(rdataset, rbtdb->common.mctx,
4646                                             &region,
4647                                             sizeof(rdatasetheader_t));
4648         if (result != ISC_R_SUCCESS)
4649                 return (result);
4650         newheader = (rdatasetheader_t *)region.base;
4651         newheader->ttl = rdataset->ttl + loadctx->now; /* XXX overflow check */
4652         newheader->type = RBTDB_RDATATYPE_VALUE(rdataset->type,
4653                                                 rdataset->covers);
4654         newheader->attributes = 0;
4655         newheader->trust = rdataset->trust;
4656         newheader->serial = 1;
4657         newheader->noqname = NULL;
4658         newheader->count = 0;
4659
4660         result = add(rbtdb, node, rbtdb->current_version, newheader,
4661                      DNS_DBADD_MERGE, ISC_TRUE, NULL, 0);
4662         if (result == ISC_R_SUCCESS &&
4663             delegating_type(rbtdb, node, rdataset->type))
4664                 node->find_callback = 1;
4665         else if (result == DNS_R_UNCHANGED)
4666                 result = ISC_R_SUCCESS;
4667
4668         return (result);
4669 }
4670
4671 static isc_result_t
4672 beginload(dns_db_t *db, dns_addrdatasetfunc_t *addp, dns_dbload_t **dbloadp) {
4673         rbtdb_load_t *loadctx;
4674         dns_rbtdb_t *rbtdb;
4675
4676         rbtdb = (dns_rbtdb_t *)db;
4677
4678         REQUIRE(VALID_RBTDB(rbtdb));
4679
4680         loadctx = isc_mem_get(rbtdb->common.mctx, sizeof(*loadctx));
4681         if (loadctx == NULL)
4682                 return (ISC_R_NOMEMORY);
4683
4684         loadctx->rbtdb = rbtdb;
4685         if (IS_CACHE(rbtdb))
4686                 isc_stdtime_get(&loadctx->now);
4687         else
4688                 loadctx->now = 0;
4689
4690         LOCK(&rbtdb->lock);
4691
4692         REQUIRE((rbtdb->attributes & (RBTDB_ATTR_LOADED|RBTDB_ATTR_LOADING))
4693                 == 0);
4694         rbtdb->attributes |= RBTDB_ATTR_LOADING;
4695
4696         UNLOCK(&rbtdb->lock);
4697
4698         *addp = loading_addrdataset;
4699         *dbloadp = loadctx;
4700
4701         return (ISC_R_SUCCESS);
4702 }
4703
4704 static isc_result_t
4705 endload(dns_db_t *db, dns_dbload_t **dbloadp) {
4706         rbtdb_load_t *loadctx;
4707         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
4708
4709         REQUIRE(VALID_RBTDB(rbtdb));
4710         REQUIRE(dbloadp != NULL);
4711         loadctx = *dbloadp;
4712         REQUIRE(loadctx->rbtdb == rbtdb);
4713
4714         LOCK(&rbtdb->lock);
4715
4716         REQUIRE((rbtdb->attributes & RBTDB_ATTR_LOADING) != 0);
4717         REQUIRE((rbtdb->attributes & RBTDB_ATTR_LOADED) == 0);
4718
4719         rbtdb->attributes &= ~RBTDB_ATTR_LOADING;
4720         rbtdb->attributes |= RBTDB_ATTR_LOADED;
4721
4722         UNLOCK(&rbtdb->lock);
4723
4724         /*
4725          * If there's a KEY rdataset at the zone origin containing a
4726          * zone key, we consider the zone secure.
4727          */
4728         if (! IS_CACHE(rbtdb))
4729                 rbtdb->secure = iszonesecure(db, rbtdb->origin_node);
4730
4731         *dbloadp = NULL;
4732
4733         isc_mem_put(rbtdb->common.mctx, loadctx, sizeof(*loadctx));
4734
4735         return (ISC_R_SUCCESS);
4736 }
4737
4738 static isc_result_t
4739 dump(dns_db_t *db, dns_dbversion_t *version, const char *filename) {
4740         dns_rbtdb_t *rbtdb;
4741
4742         rbtdb = (dns_rbtdb_t *)db;
4743
4744         REQUIRE(VALID_RBTDB(rbtdb));
4745
4746         return (dns_master_dump(rbtdb->common.mctx, db, version,
4747                                 &dns_master_style_default,
4748                                 filename));
4749 }
4750
4751 static void
4752 delete_callback(void *data, void *arg) {
4753         dns_rbtdb_t *rbtdb = arg;
4754         rdatasetheader_t *current, *next;
4755
4756         for (current = data; current != NULL; current = next) {
4757                 next = current->next;
4758                 free_rdataset(rbtdb->common.mctx, current);
4759         }
4760 }
4761
4762 static isc_boolean_t
4763 issecure(dns_db_t *db) {
4764         dns_rbtdb_t *rbtdb;
4765         isc_boolean_t secure;
4766
4767         rbtdb = (dns_rbtdb_t *)db;
4768
4769         REQUIRE(VALID_RBTDB(rbtdb));
4770
4771         RWLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
4772         secure = rbtdb->secure;
4773         RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
4774
4775         return (secure);
4776 }
4777
4778 static unsigned int
4779 nodecount(dns_db_t *db) {
4780         dns_rbtdb_t *rbtdb;
4781         unsigned int count;
4782
4783         rbtdb = (dns_rbtdb_t *)db;
4784
4785         REQUIRE(VALID_RBTDB(rbtdb));
4786
4787         RWLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
4788         count = dns_rbt_nodecount(rbtdb->tree);
4789         RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
4790
4791         return (count);
4792 }
4793
4794 static void
4795 settask(dns_db_t *db, isc_task_t *task) {
4796         dns_rbtdb_t *rbtdb;
4797
4798         rbtdb = (dns_rbtdb_t *)db;
4799
4800         REQUIRE(VALID_RBTDB(rbtdb));
4801
4802         LOCK(&rbtdb->lock);
4803         if (rbtdb->task != NULL)
4804                 isc_task_detach(&rbtdb->task);
4805         if (task != NULL)
4806                 isc_task_attach(task, &rbtdb->task);
4807         UNLOCK(&rbtdb->lock);
4808 }
4809
4810 static isc_boolean_t
4811 ispersistent(dns_db_t *db) {
4812         UNUSED(db);
4813         return (ISC_FALSE);
4814 }
4815
4816 static dns_dbmethods_t zone_methods = {
4817         attach,
4818         detach,
4819         beginload,
4820         endload,
4821         dump,
4822         currentversion,
4823         newversion,
4824         attachversion,
4825         closeversion,
4826         findnode,
4827         zone_find,
4828         zone_findzonecut,
4829         attachnode,
4830         detachnode,
4831         expirenode,
4832         printnode,
4833         createiterator,
4834         zone_findrdataset,
4835         allrdatasets,
4836         addrdataset,
4837         subtractrdataset,
4838         deleterdataset,
4839         issecure,
4840         nodecount,
4841         ispersistent,
4842         overmem,
4843         settask
4844 };
4845
4846 static dns_dbmethods_t cache_methods = {
4847         attach,
4848         detach,
4849         beginload,
4850         endload,
4851         dump,
4852         currentversion,
4853         newversion,
4854         attachversion,
4855         closeversion,
4856         findnode,
4857         cache_find,
4858         cache_findzonecut,
4859         attachnode,
4860         detachnode,
4861         expirenode,
4862         printnode,
4863         createiterator,
4864         cache_findrdataset,
4865         allrdatasets,
4866         addrdataset,
4867         subtractrdataset,
4868         deleterdataset,
4869         issecure,
4870         nodecount,
4871         ispersistent,
4872         overmem,
4873         settask
4874 };
4875
4876 isc_result_t
4877 #ifdef DNS_RBTDB_VERSION64
4878 dns_rbtdb64_create
4879 #else
4880 dns_rbtdb_create
4881 #endif
4882                 (isc_mem_t *mctx, dns_name_t *origin, dns_dbtype_t type,
4883                  dns_rdataclass_t rdclass, unsigned int argc, char *argv[],
4884                  void *driverarg, dns_db_t **dbp)
4885 {
4886         dns_rbtdb_t *rbtdb;
4887         isc_result_t result;
4888         int i;
4889         dns_name_t name;
4890
4891         /* Keep the compiler happy. */
4892         UNUSED(argc);
4893         UNUSED(argv);
4894         UNUSED(driverarg);
4895
4896         rbtdb = isc_mem_get(mctx, sizeof(*rbtdb));
4897         if (rbtdb == NULL)
4898                 return (ISC_R_NOMEMORY);
4899         memset(rbtdb, '\0', sizeof(*rbtdb));
4900         dns_name_init(&rbtdb->common.origin, NULL);
4901         rbtdb->common.attributes = 0;
4902         if (type == dns_dbtype_cache) {
4903                 rbtdb->common.methods = &cache_methods;
4904                 rbtdb->common.attributes |= DNS_DBATTR_CACHE;
4905         } else if (type == dns_dbtype_stub) {
4906                 rbtdb->common.methods = &zone_methods;
4907                 rbtdb->common.attributes |= DNS_DBATTR_STUB;
4908         } else
4909                 rbtdb->common.methods = &zone_methods;
4910         rbtdb->common.rdclass = rdclass;
4911         rbtdb->common.mctx = NULL;
4912
4913         result = isc_mutex_init(&rbtdb->lock);
4914         if (result != ISC_R_SUCCESS) {
4915                 isc_mem_put(mctx, rbtdb, sizeof(*rbtdb));
4916                 UNEXPECTED_ERROR(__FILE__, __LINE__,
4917                                  "isc_mutex_init() failed: %s",
4918                                  isc_result_totext(result));
4919                 return (ISC_R_UNEXPECTED);
4920         }
4921
4922         result = isc_rwlock_init(&rbtdb->tree_lock, 0, 0);
4923         if (result != ISC_R_SUCCESS) {
4924                 DESTROYLOCK(&rbtdb->lock);
4925                 isc_mem_put(mctx, rbtdb, sizeof(*rbtdb));
4926                 UNEXPECTED_ERROR(__FILE__, __LINE__,
4927                                  "isc_rwlock_init() failed: %s",
4928                                  isc_result_totext(result));
4929                 return (ISC_R_UNEXPECTED);
4930         }
4931
4932         INSIST(rbtdb->node_lock_count < (1 << DNS_RBT_LOCKLENGTH));
4933
4934         if (rbtdb->node_lock_count == 0)
4935                 rbtdb->node_lock_count = DEFAULT_NODE_LOCK_COUNT;
4936         rbtdb->node_locks = isc_mem_get(mctx, rbtdb->node_lock_count *
4937                                         sizeof(rbtdb_nodelock_t));
4938         rbtdb->active = rbtdb->node_lock_count;
4939         for (i = 0; i < (int)(rbtdb->node_lock_count); i++) {
4940                 result = isc_mutex_init(&rbtdb->node_locks[i].lock);
4941                 if (result != ISC_R_SUCCESS) {
4942                         i--;
4943                         while (i >= 0) {
4944                                 DESTROYLOCK(&rbtdb->node_locks[i].lock);
4945                                 i--;
4946                         }
4947                         isc_mem_put(mctx, rbtdb->node_locks,
4948                                     rbtdb->node_lock_count *
4949                                     sizeof(rbtdb_nodelock_t));
4950                         isc_rwlock_destroy(&rbtdb->tree_lock);
4951                         DESTROYLOCK(&rbtdb->lock);
4952                         isc_mem_put(mctx, rbtdb, sizeof(*rbtdb));
4953                         UNEXPECTED_ERROR(__FILE__, __LINE__,
4954                                          "isc_mutex_init() failed: %s",
4955                                          isc_result_totext(result));
4956                         return (ISC_R_UNEXPECTED);
4957                 }
4958                 rbtdb->node_locks[i].references = 0;
4959                 rbtdb->node_locks[i].exiting = ISC_FALSE;
4960         }
4961
4962         /*
4963          * Attach to the mctx.  The database will persist so long as there
4964          * are references to it, and attaching to the mctx ensures that our
4965          * mctx won't disappear out from under us.
4966          */
4967         isc_mem_attach(mctx, &rbtdb->common.mctx);
4968
4969         /*
4970          * Must be initalized before free_rbtdb() is called.
4971          */
4972         isc_ondestroy_init(&rbtdb->common.ondest);
4973
4974         /*
4975          * Make a copy of the origin name.
4976          */
4977         result = dns_name_dupwithoffsets(origin, mctx, &rbtdb->common.origin);
4978         if (result != ISC_R_SUCCESS) {
4979                 free_rbtdb(rbtdb, ISC_FALSE, NULL);
4980                 return (result);
4981         }
4982
4983         /*
4984          * Make the Red-Black Tree.
4985          */
4986         result = dns_rbt_create(mctx, delete_callback, rbtdb, &rbtdb->tree);
4987         if (result != ISC_R_SUCCESS) {
4988                 free_rbtdb(rbtdb, ISC_FALSE, NULL);
4989                 return (result);
4990         }
4991         /*
4992          * In order to set the node callback bit correctly in zone databases,
4993          * we need to know if the node has the origin name of the zone.
4994          * In loading_addrdataset() we could simply compare the new name
4995          * to the origin name, but this is expensive.  Also, we don't know the
4996          * node name in addrdataset(), so we need another way of knowing the
4997          * zone's top.
4998          *
4999          * We now explicitly create a node for the zone's origin, and then
5000          * we simply remember the node's address.  This is safe, because
5001          * the top-of-zone node can never be deleted, nor can its address
5002          * change.
5003          */
5004         if (! IS_CACHE(rbtdb)) {
5005                 rbtdb->origin_node = NULL;
5006                 result = dns_rbt_addnode(rbtdb->tree, &rbtdb->common.origin,
5007                                          &rbtdb->origin_node);
5008                 if (result != ISC_R_SUCCESS) {
5009                         INSIST(result != ISC_R_EXISTS);
5010                         free_rbtdb(rbtdb, ISC_FALSE, NULL);
5011                         return (result);
5012                 }
5013                 /*
5014                  * We need to give the origin node the right locknum.
5015                  */
5016                 dns_name_init(&name, NULL);
5017                 dns_rbt_namefromnode(rbtdb->origin_node, &name);
5018 #ifdef DNS_RBT_USEHASH
5019                 rbtdb->origin_node->locknum =
5020                         rbtdb->origin_node->hashval %
5021                         rbtdb->node_lock_count;
5022 #else
5023                 rbtdb->origin_node->locknum =
5024                         dns_name_hash(&name, ISC_TRUE) %
5025                         rbtdb->node_lock_count;
5026 #endif
5027         }
5028
5029         /*
5030          * Misc. Initialization.
5031          */
5032         isc_refcount_init(&rbtdb->references, 1);
5033         rbtdb->attributes = 0;
5034         rbtdb->secure = ISC_FALSE;
5035         rbtdb->overmem = ISC_FALSE;
5036         rbtdb->task = NULL;
5037
5038         /*
5039          * Version Initialization.
5040          */
5041         rbtdb->current_serial = 1;
5042         rbtdb->least_serial = 1;
5043         rbtdb->next_serial = 2;
5044         rbtdb->current_version = allocate_version(mctx, 1, 0, ISC_FALSE);
5045         if (rbtdb->current_version == NULL) {
5046                 free_rbtdb(rbtdb, ISC_FALSE, NULL);
5047                 return (ISC_R_NOMEMORY);
5048         }
5049         rbtdb->future_version = NULL;
5050         ISC_LIST_INIT(rbtdb->open_versions);
5051
5052         rbtdb->common.magic = DNS_DB_MAGIC;
5053         rbtdb->common.impmagic = RBTDB_MAGIC;
5054
5055         *dbp = (dns_db_t *)rbtdb;
5056
5057         return (ISC_R_SUCCESS);
5058 }
5059
5060
5061 /*
5062  * Slabbed Rdataset Methods
5063  */
5064
5065 static void
5066 rdataset_disassociate(dns_rdataset_t *rdataset) {
5067         dns_db_t *db = rdataset->private1;
5068         dns_dbnode_t *node = rdataset->private2;
5069
5070         detachnode(db, &node);
5071 }
5072
5073 static isc_result_t
5074 rdataset_first(dns_rdataset_t *rdataset) {
5075         unsigned char *raw = rdataset->private3;
5076         unsigned int count;
5077
5078         count = raw[0] * 256 + raw[1];
5079         if (count == 0) {
5080                 rdataset->private5 = NULL;
5081                 return (ISC_R_NOMORE);
5082         }
5083         raw += 2;
5084         /*
5085          * The privateuint4 field is the number of rdata beyond the cursor
5086          * position, so we decrement the total count by one before storing
5087          * it.
5088          */
5089         count--;
5090         rdataset->privateuint4 = count;
5091         rdataset->private5 = raw;
5092
5093         return (ISC_R_SUCCESS);
5094 }
5095
5096 static isc_result_t
5097 rdataset_next(dns_rdataset_t *rdataset) {
5098         unsigned int count;
5099         unsigned int length;
5100         unsigned char *raw;
5101
5102         count = rdataset->privateuint4;
5103         if (count == 0)
5104                 return (ISC_R_NOMORE);
5105         count--;
5106         rdataset->privateuint4 = count;
5107         raw = rdataset->private5;
5108         length = raw[0] * 256 + raw[1];
5109         raw += length + 2;
5110         rdataset->private5 = raw;
5111
5112         return (ISC_R_SUCCESS);
5113 }
5114
5115 static void
5116 rdataset_current(dns_rdataset_t *rdataset, dns_rdata_t *rdata) {
5117         unsigned char *raw = rdataset->private5;
5118         isc_region_t r;
5119
5120         REQUIRE(raw != NULL);
5121
5122         r.length = raw[0] * 256 + raw[1];
5123         raw += 2;
5124         r.base = raw;
5125         dns_rdata_fromregion(rdata, rdataset->rdclass, rdataset->type, &r);
5126 }
5127
5128 static void
5129 rdataset_clone(dns_rdataset_t *source, dns_rdataset_t *target) {
5130         dns_db_t *db = source->private1;
5131         dns_dbnode_t *node = source->private2;
5132         dns_dbnode_t *cloned_node = NULL;
5133
5134         attachnode(db, node, &cloned_node);
5135         *target = *source;
5136
5137         /*
5138          * Reset iterator state.
5139          */
5140         target->privateuint4 = 0;
5141         target->private5 = NULL;
5142 }
5143
5144 static unsigned int
5145 rdataset_count(dns_rdataset_t *rdataset) {
5146         unsigned char *raw = rdataset->private3;
5147         unsigned int count;
5148
5149         count = raw[0] * 256 + raw[1];
5150
5151         return (count);
5152 }
5153
5154 static isc_result_t
5155 rdataset_getnoqname(dns_rdataset_t *rdataset, dns_name_t *name,
5156                     dns_rdataset_t *nsec, dns_rdataset_t *nsecsig)
5157 {
5158         dns_db_t *db = rdataset->private1;
5159         dns_dbnode_t *node = rdataset->private2;
5160         dns_dbnode_t *cloned_node;
5161         struct noqname *noqname = rdataset->private6;
5162
5163         cloned_node = NULL;
5164         attachnode(db, node, &cloned_node);
5165         nsec->methods = &rdataset_methods;
5166         nsec->rdclass = db->rdclass;
5167         nsec->type = dns_rdatatype_nsec;
5168         nsec->covers = 0;
5169         nsec->ttl = rdataset->ttl;
5170         nsec->trust = rdataset->trust;
5171         nsec->private1 = rdataset->private1;
5172         nsec->private2 = rdataset->private2;
5173         nsec->private3 = noqname->nsec;
5174         nsec->privateuint4 = 0;
5175         nsec->private5 = NULL;
5176         nsec->private6 = NULL;
5177
5178         cloned_node = NULL;
5179         attachnode(db, node, &cloned_node);
5180         nsecsig->methods = &rdataset_methods;
5181         nsecsig->rdclass = db->rdclass;
5182         nsecsig->type = dns_rdatatype_rrsig;
5183         nsecsig->covers = dns_rdatatype_nsec;
5184         nsecsig->ttl = rdataset->ttl;
5185         nsecsig->trust = rdataset->trust;
5186         nsecsig->private1 = rdataset->private1;
5187         nsecsig->private2 = rdataset->private2;
5188         nsecsig->private3 = noqname->nsecsig;
5189         nsecsig->privateuint4 = 0;
5190         nsecsig->private5 = NULL;
5191         nsec->private6 = NULL;
5192
5193         dns_name_clone(&noqname->name, name);
5194
5195         return (ISC_R_SUCCESS);
5196 }
5197
5198 /*
5199  * Rdataset Iterator Methods
5200  */
5201
5202 static void
5203 rdatasetiter_destroy(dns_rdatasetiter_t **iteratorp) {
5204         rbtdb_rdatasetiter_t *rbtiterator;
5205
5206         rbtiterator = (rbtdb_rdatasetiter_t *)(*iteratorp);
5207
5208         if (rbtiterator->common.version != NULL)
5209                 closeversion(rbtiterator->common.db,
5210                              &rbtiterator->common.version, ISC_FALSE);
5211         detachnode(rbtiterator->common.db, &rbtiterator->common.node);
5212         isc_mem_put(rbtiterator->common.db->mctx, rbtiterator,
5213                     sizeof(*rbtiterator));
5214
5215         *iteratorp = NULL;
5216 }
5217
5218 static isc_result_t
5219 rdatasetiter_first(dns_rdatasetiter_t *iterator) {
5220         rbtdb_rdatasetiter_t *rbtiterator = (rbtdb_rdatasetiter_t *)iterator;
5221         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)(rbtiterator->common.db);
5222         dns_rbtnode_t *rbtnode = rbtiterator->common.node;
5223         rbtdb_version_t *rbtversion = rbtiterator->common.version;
5224         rdatasetheader_t *header, *top_next;
5225         rbtdb_serial_t serial;
5226         isc_stdtime_t now;
5227
5228         if (IS_CACHE(rbtdb)) {
5229                 serial = 1;
5230                 now = rbtiterator->common.now;
5231         } else {
5232                 serial = rbtversion->serial;
5233                 now = 0;
5234         }
5235
5236         LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
5237
5238         for (header = rbtnode->data; header != NULL; header = top_next) {
5239                 top_next = header->next;
5240                 do {
5241                         if (header->serial <= serial && !IGNORE(header)) {
5242                                 /*
5243                                  * Is this a "this rdataset doesn't exist"
5244                                  * record?  Or is it too old in the cache?
5245                                  *
5246                                  * Note: unlike everywhere else, we
5247                                  * check for now > header->ttl instead
5248                                  * of now >= header->ttl.  This allows
5249                                  * ANY and RRSIG queries for 0 TTL
5250                                  * rdatasets to work.
5251                                  */
5252                                 if (NONEXISTENT(header) ||
5253                                     (now != 0 && now > header->ttl))
5254                                         header = NULL;
5255                                 break;
5256                         } else
5257                                 header = header->down;
5258                 } while (header != NULL);
5259                 if (header != NULL)
5260                         break;
5261         }
5262
5263         UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
5264
5265         rbtiterator->current = header;
5266
5267         if (header == NULL)
5268                 return (ISC_R_NOMORE);
5269
5270         return (ISC_R_SUCCESS);
5271 }
5272
5273 static isc_result_t
5274 rdatasetiter_next(dns_rdatasetiter_t *iterator) {
5275         rbtdb_rdatasetiter_t *rbtiterator = (rbtdb_rdatasetiter_t *)iterator;
5276         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)(rbtiterator->common.db);
5277         dns_rbtnode_t *rbtnode = rbtiterator->common.node;
5278         rbtdb_version_t *rbtversion = rbtiterator->common.version;
5279         rdatasetheader_t *header, *top_next;
5280         rbtdb_serial_t serial;
5281         isc_stdtime_t now;
5282         rbtdb_rdatatype_t type, negtype;
5283         dns_rdatatype_t rdtype, covers;
5284
5285         header = rbtiterator->current;
5286         if (header == NULL)
5287                 return (ISC_R_NOMORE);
5288
5289         if (IS_CACHE(rbtdb)) {
5290                 serial = 1;
5291                 now = rbtiterator->common.now;
5292         } else {
5293                 serial = rbtversion->serial;
5294                 now = 0;
5295         }
5296
5297         LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
5298
5299         type = header->type;
5300         rdtype = RBTDB_RDATATYPE_BASE(header->type);
5301         if (rdtype == 0) {
5302                 covers = RBTDB_RDATATYPE_EXT(header->type);
5303                 negtype = RBTDB_RDATATYPE_VALUE(covers, 0);
5304         } else
5305                 negtype = RBTDB_RDATATYPE_VALUE(0, rdtype);
5306         for (header = header->next; header != NULL; header = top_next) {
5307                 top_next = header->next;
5308                 /*
5309                  * If not walking back up the down list.
5310                  */
5311                 if (header->type != type && header->type != negtype) {
5312                         do {
5313                                 if (header->serial <= serial &&
5314                                     !IGNORE(header)) {
5315                                         /*
5316                                          * Is this a "this rdataset doesn't
5317                                          * exist" record?
5318                                          *
5319                                          * Note: unlike everywhere else, we
5320                                          * check for now > header->ttl instead
5321                                          * of now >= header->ttl.  This allows
5322                                          * ANY and RRSIG queries for 0 TTL
5323                                          * rdatasets to work.
5324                                          */
5325                                         if ((header->attributes &
5326                                              RDATASET_ATTR_NONEXISTENT) != 0 ||
5327                                             (now != 0 && now > header->ttl))
5328                                                 header = NULL;
5329                                         break;
5330                                 } else
5331                                         header = header->down;
5332                         } while (header != NULL);
5333                         if (header != NULL)
5334                                 break;
5335                 }
5336         }
5337
5338         UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
5339
5340         rbtiterator->current = header;
5341
5342         if (header == NULL)
5343                 return (ISC_R_NOMORE);
5344
5345         return (ISC_R_SUCCESS);
5346 }
5347
5348 static void
5349 rdatasetiter_current(dns_rdatasetiter_t *iterator, dns_rdataset_t *rdataset) {
5350         rbtdb_rdatasetiter_t *rbtiterator = (rbtdb_rdatasetiter_t *)iterator;
5351         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)(rbtiterator->common.db);
5352         dns_rbtnode_t *rbtnode = rbtiterator->common.node;
5353         rdatasetheader_t *header;
5354
5355         header = rbtiterator->current;
5356         REQUIRE(header != NULL);
5357
5358         LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
5359
5360         bind_rdataset(rbtdb, rbtnode, header, rbtiterator->common.now,
5361                       rdataset);
5362
5363         UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
5364 }
5365
5366
5367 /*
5368  * Database Iterator Methods
5369  */
5370
5371 static inline void
5372 reference_iter_node(rbtdb_dbiterator_t *rbtdbiter) {
5373         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)rbtdbiter->common.db;
5374         dns_rbtnode_t *node = rbtdbiter->node;
5375
5376         if (node == NULL)
5377                 return;
5378
5379         INSIST(rbtdbiter->tree_locked != isc_rwlocktype_none);
5380         LOCK(&rbtdb->node_locks[node->locknum].lock);
5381         new_reference(rbtdb, node);
5382         UNLOCK(&rbtdb->node_locks[node->locknum].lock);
5383 }
5384
5385 static inline void
5386 dereference_iter_node(rbtdb_dbiterator_t *rbtdbiter) {
5387         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)rbtdbiter->common.db;
5388         dns_rbtnode_t *node = rbtdbiter->node;
5389         isc_mutex_t *lock;
5390
5391         if (node == NULL)
5392                 return;
5393
5394         lock = &rbtdb->node_locks[node->locknum].lock;
5395         LOCK(lock);
5396         INSIST(rbtdbiter->node->references > 0);
5397         if (--node->references == 0)
5398                 no_references(rbtdb, node, 0, rbtdbiter->tree_locked);
5399         UNLOCK(lock);
5400
5401         rbtdbiter->node = NULL;
5402 }
5403
5404 static void
5405 flush_deletions(rbtdb_dbiterator_t *rbtdbiter) {
5406         dns_rbtnode_t *node;
5407         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)rbtdbiter->common.db;
5408         isc_boolean_t was_read_locked = ISC_FALSE;
5409         isc_mutex_t *lock;
5410         int i;
5411
5412         if (rbtdbiter->delete != 0) {
5413                 /*
5414                  * Note that "%d node of %d in tree" can report things like
5415                  * "flush_deletions: 59 nodes of 41 in tree".  This means
5416                  * That some nodes appear on the deletions list more than
5417                  * once.  Only the last occurence will actually be deleted.
5418                  */
5419                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
5420                               DNS_LOGMODULE_CACHE, ISC_LOG_DEBUG(1),
5421                               "flush_deletions: %d nodes of %d in tree",
5422                               rbtdbiter->delete,
5423                               dns_rbt_nodecount(rbtdb->tree));
5424
5425                 if (rbtdbiter->tree_locked == isc_rwlocktype_read) {
5426                         RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
5427                         was_read_locked = ISC_TRUE;
5428                 }
5429                 RWLOCK(&rbtdb->tree_lock, isc_rwlocktype_write);
5430                 rbtdbiter->tree_locked = isc_rwlocktype_write;
5431
5432                 for (i = 0; i < rbtdbiter->delete; i++) {
5433                         node = rbtdbiter->deletions[i];
5434                         lock = &rbtdb->node_locks[node->locknum].lock;
5435
5436                         LOCK(lock);
5437                         INSIST(node->references > 0);
5438                         node->references--;
5439                         if (node->references == 0)
5440                                 no_references(rbtdb, node, 0,
5441                                               rbtdbiter->tree_locked);
5442                         UNLOCK(lock);
5443                 }
5444
5445                 rbtdbiter->delete = 0;
5446
5447                 RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_write);
5448                 if (was_read_locked) {
5449                         RWLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
5450                         rbtdbiter->tree_locked = isc_rwlocktype_read;
5451
5452                 } else {
5453                         rbtdbiter->tree_locked = isc_rwlocktype_none;
5454                 }
5455         }
5456 }
5457
5458 static inline void
5459 resume_iteration(rbtdb_dbiterator_t *rbtdbiter) {
5460         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)rbtdbiter->common.db;
5461
5462         REQUIRE(rbtdbiter->paused);
5463         REQUIRE(rbtdbiter->tree_locked == isc_rwlocktype_none);
5464
5465         RWLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
5466         rbtdbiter->tree_locked = isc_rwlocktype_read;
5467
5468         rbtdbiter->paused = ISC_FALSE;
5469 }
5470
5471 static void
5472 dbiterator_destroy(dns_dbiterator_t **iteratorp) {
5473         rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)(*iteratorp);
5474         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)rbtdbiter->common.db;
5475         dns_db_t *db = NULL;
5476
5477         if (rbtdbiter->tree_locked == isc_rwlocktype_read) {
5478                 RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
5479                 rbtdbiter->tree_locked = isc_rwlocktype_none;
5480         } else
5481                 INSIST(rbtdbiter->tree_locked == isc_rwlocktype_none);
5482
5483         dereference_iter_node(rbtdbiter);
5484
5485         flush_deletions(rbtdbiter);
5486
5487         dns_db_attach(rbtdbiter->common.db, &db);
5488         dns_db_detach(&rbtdbiter->common.db);
5489
5490         dns_rbtnodechain_reset(&rbtdbiter->chain);
5491         isc_mem_put(db->mctx, rbtdbiter, sizeof(*rbtdbiter));
5492         dns_db_detach(&db);
5493
5494         *iteratorp = NULL;
5495 }
5496
5497 static isc_result_t
5498 dbiterator_first(dns_dbiterator_t *iterator) {
5499         isc_result_t result;
5500         rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5501         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)iterator->db;
5502         dns_name_t *name, *origin;
5503
5504         if (rbtdbiter->result != ISC_R_SUCCESS &&
5505             rbtdbiter->result != ISC_R_NOMORE)
5506                 return (rbtdbiter->result);
5507
5508         if (rbtdbiter->paused)
5509                 resume_iteration(rbtdbiter);
5510
5511         dereference_iter_node(rbtdbiter);
5512
5513         name = dns_fixedname_name(&rbtdbiter->name);
5514         origin = dns_fixedname_name(&rbtdbiter->origin);
5515         dns_rbtnodechain_reset(&rbtdbiter->chain);
5516
5517         result = dns_rbtnodechain_first(&rbtdbiter->chain, rbtdb->tree, name,
5518                                         origin);
5519
5520         if (result == ISC_R_SUCCESS || result == DNS_R_NEWORIGIN) {
5521                 result = dns_rbtnodechain_current(&rbtdbiter->chain, NULL,
5522                                                   NULL, &rbtdbiter->node);
5523                 if (result == ISC_R_SUCCESS) {
5524                         rbtdbiter->new_origin = ISC_TRUE;
5525                         reference_iter_node(rbtdbiter);
5526                 }
5527         } else {
5528                 INSIST(result == ISC_R_NOTFOUND);
5529                 result = ISC_R_NOMORE; /* The tree is empty. */
5530         }
5531
5532         rbtdbiter->result = result;
5533
5534         return (result);
5535 }
5536
5537 static isc_result_t
5538 dbiterator_last(dns_dbiterator_t *iterator) {
5539         isc_result_t result;
5540         rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5541         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)iterator->db;
5542         dns_name_t *name, *origin;
5543
5544         if (rbtdbiter->result != ISC_R_SUCCESS &&
5545             rbtdbiter->result != ISC_R_NOMORE)
5546                 return (rbtdbiter->result);
5547
5548         if (rbtdbiter->paused)
5549                 resume_iteration(rbtdbiter);
5550
5551         dereference_iter_node(rbtdbiter);
5552
5553         name = dns_fixedname_name(&rbtdbiter->name);
5554         origin = dns_fixedname_name(&rbtdbiter->origin);
5555         dns_rbtnodechain_reset(&rbtdbiter->chain);
5556
5557         result = dns_rbtnodechain_last(&rbtdbiter->chain, rbtdb->tree, name,
5558                                        origin);
5559         if (result == ISC_R_SUCCESS || result == DNS_R_NEWORIGIN) {
5560                 result = dns_rbtnodechain_current(&rbtdbiter->chain, NULL,
5561                                                   NULL, &rbtdbiter->node);
5562                 if (result == ISC_R_SUCCESS) {
5563                         rbtdbiter->new_origin = ISC_TRUE;
5564                         reference_iter_node(rbtdbiter);
5565                 }
5566         } else {
5567                 INSIST(result == ISC_R_NOTFOUND);
5568                 result = ISC_R_NOMORE; /* The tree is empty. */
5569         }
5570
5571         rbtdbiter->result = result;
5572
5573         return (result);
5574 }
5575
5576 static isc_result_t
5577 dbiterator_seek(dns_dbiterator_t *iterator, dns_name_t *name) {
5578         isc_result_t result;
5579         rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5580         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)iterator->db;
5581         dns_name_t *iname, *origin;
5582
5583         if (rbtdbiter->result != ISC_R_SUCCESS &&
5584             rbtdbiter->result != ISC_R_NOMORE)
5585                 return (rbtdbiter->result);
5586
5587         if (rbtdbiter->paused)
5588                 resume_iteration(rbtdbiter);
5589
5590         dereference_iter_node(rbtdbiter);
5591
5592         iname = dns_fixedname_name(&rbtdbiter->name);
5593         origin = dns_fixedname_name(&rbtdbiter->origin);
5594         dns_rbtnodechain_reset(&rbtdbiter->chain);
5595
5596         result = dns_rbt_findnode(rbtdb->tree, name, NULL, &rbtdbiter->node,
5597                                   &rbtdbiter->chain, DNS_RBTFIND_EMPTYDATA,
5598                                   NULL, NULL);
5599         if (result == ISC_R_SUCCESS) {
5600                 result = dns_rbtnodechain_current(&rbtdbiter->chain, iname,
5601                                                   origin, NULL);
5602                 if (result == ISC_R_SUCCESS) {
5603                         rbtdbiter->new_origin = ISC_TRUE;
5604                         reference_iter_node(rbtdbiter);
5605                 }
5606
5607         } else if (result == DNS_R_PARTIALMATCH)
5608                 result = ISC_R_NOTFOUND;
5609
5610         rbtdbiter->result = result;
5611
5612         return (result);
5613 }
5614
5615 static isc_result_t
5616 dbiterator_prev(dns_dbiterator_t *iterator) {
5617         isc_result_t result;
5618         rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5619         dns_name_t *name, *origin;
5620
5621         REQUIRE(rbtdbiter->node != NULL);
5622
5623         if (rbtdbiter->result != ISC_R_SUCCESS)
5624                 return (rbtdbiter->result);
5625
5626         if (rbtdbiter->paused)
5627                 resume_iteration(rbtdbiter);
5628
5629         name = dns_fixedname_name(&rbtdbiter->name);
5630         origin = dns_fixedname_name(&rbtdbiter->origin);
5631         result = dns_rbtnodechain_prev(&rbtdbiter->chain, name, origin);
5632
5633         dereference_iter_node(rbtdbiter);
5634
5635         if (result == DNS_R_NEWORIGIN || result == ISC_R_SUCCESS) {
5636                 rbtdbiter->new_origin = ISC_TF(result == DNS_R_NEWORIGIN);
5637                 result = dns_rbtnodechain_current(&rbtdbiter->chain, NULL,
5638                                                   NULL, &rbtdbiter->node);
5639         }
5640
5641         if (result == ISC_R_SUCCESS)
5642                 reference_iter_node(rbtdbiter);
5643
5644         rbtdbiter->result = result;
5645
5646         return (result);
5647 }
5648
5649 static isc_result_t
5650 dbiterator_next(dns_dbiterator_t *iterator) {
5651         isc_result_t result;
5652         rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5653         dns_name_t *name, *origin;
5654
5655         REQUIRE(rbtdbiter->node != NULL);
5656
5657         if (rbtdbiter->result != ISC_R_SUCCESS)
5658                 return (rbtdbiter->result);
5659
5660         if (rbtdbiter->paused)
5661                 resume_iteration(rbtdbiter);
5662
5663         name = dns_fixedname_name(&rbtdbiter->name);
5664         origin = dns_fixedname_name(&rbtdbiter->origin);
5665         result = dns_rbtnodechain_next(&rbtdbiter->chain, name, origin);
5666
5667         dereference_iter_node(rbtdbiter);
5668
5669         if (result == DNS_R_NEWORIGIN || result == ISC_R_SUCCESS) {
5670                 rbtdbiter->new_origin = ISC_TF(result == DNS_R_NEWORIGIN);
5671                 result = dns_rbtnodechain_current(&rbtdbiter->chain, NULL,
5672                                                   NULL, &rbtdbiter->node);
5673         }
5674         if (result == ISC_R_SUCCESS)
5675                 reference_iter_node(rbtdbiter);
5676
5677         rbtdbiter->result = result;
5678
5679         return (result);
5680 }
5681
5682 static isc_result_t
5683 dbiterator_current(dns_dbiterator_t *iterator, dns_dbnode_t **nodep,
5684                    dns_name_t *name)
5685 {
5686         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)iterator->db;
5687         rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5688         dns_rbtnode_t *node = rbtdbiter->node;
5689         isc_result_t result;
5690         dns_name_t *nodename = dns_fixedname_name(&rbtdbiter->name);
5691         dns_name_t *origin = dns_fixedname_name(&rbtdbiter->origin);
5692
5693         REQUIRE(rbtdbiter->result == ISC_R_SUCCESS);
5694         REQUIRE(rbtdbiter->node != NULL);
5695
5696         if (rbtdbiter->paused)
5697                 resume_iteration(rbtdbiter);
5698
5699         if (name != NULL) {
5700                 if (rbtdbiter->common.relative_names)
5701                         origin = NULL;
5702                 result = dns_name_concatenate(nodename, origin, name, NULL);
5703                 if (result != ISC_R_SUCCESS)
5704                         return (result);
5705                 if (rbtdbiter->common.relative_names && rbtdbiter->new_origin)
5706                         result = DNS_R_NEWORIGIN;
5707         } else
5708                 result = ISC_R_SUCCESS;
5709
5710         LOCK(&rbtdb->node_locks[node->locknum].lock);
5711         new_reference(rbtdb, node);
5712         UNLOCK(&rbtdb->node_locks[node->locknum].lock);
5713
5714         *nodep = rbtdbiter->node;
5715
5716         if (iterator->cleaning && result == ISC_R_SUCCESS) {
5717                 isc_result_t expire_result;
5718
5719                 /*
5720                  * If the deletion array is full, flush it before trying
5721                  * to expire the current node.  The current node can't
5722                  * fully deleted while the iteration cursor is still on it.
5723                  */
5724                 if (rbtdbiter->delete == DELETION_BATCH_MAX)
5725                         flush_deletions(rbtdbiter);
5726
5727                 expire_result = expirenode(iterator->db, *nodep, 0);
5728
5729                 /*
5730                  * expirenode() currently always returns success.
5731                  */
5732                 if (expire_result == ISC_R_SUCCESS && node->down == NULL) {
5733                         rbtdbiter->deletions[rbtdbiter->delete++] = node;
5734                         LOCK(&rbtdb->node_locks[node->locknum].lock);
5735                         node->references++;
5736                         UNLOCK(&rbtdb->node_locks[node->locknum].lock);
5737                 }
5738         }
5739
5740         return (result);
5741 }
5742
5743 static isc_result_t
5744 dbiterator_pause(dns_dbiterator_t *iterator) {
5745         dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)iterator->db;
5746         rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5747
5748         if (rbtdbiter->result != ISC_R_SUCCESS &&
5749             rbtdbiter->result != ISC_R_NOMORE)
5750                 return (rbtdbiter->result);
5751
5752         if (rbtdbiter->paused)
5753                 return (ISC_R_SUCCESS);
5754
5755         rbtdbiter->paused = ISC_TRUE;
5756
5757         if (rbtdbiter->tree_locked != isc_rwlocktype_none) {
5758                 INSIST(rbtdbiter->tree_locked == isc_rwlocktype_read);
5759                 RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
5760                 rbtdbiter->tree_locked = isc_rwlocktype_none;
5761         }
5762
5763         flush_deletions(rbtdbiter);
5764
5765         return (ISC_R_SUCCESS);
5766 }
5767
5768 static isc_result_t
5769 dbiterator_origin(dns_dbiterator_t *iterator, dns_name_t *name) {
5770         rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5771         dns_name_t *origin = dns_fixedname_name(&rbtdbiter->origin);
5772
5773         if (rbtdbiter->result != ISC_R_SUCCESS)
5774                 return (rbtdbiter->result);
5775
5776         return (dns_name_copy(origin, name, NULL));
5777 }