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