"Fossies" - the Fresh Open Source Software Archive

Member "bind-9.16.7/lib/dns/rbt.c" (4 Sep 2020, 94353 Bytes) of package /linux/misc/dns/bind9/9.16.7/bind-9.16.7.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "rbt.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 9.16.6_vs_9.16.7.

    1 /*
    2  * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
    3  *
    4  * This Source Code Form is subject to the terms of the Mozilla Public
    5  * License, v. 2.0. If a copy of the MPL was not distributed with this
    6  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
    7  *
    8  * See the COPYRIGHT file distributed with this work for additional
    9  * information regarding copyright ownership.
   10  */
   11 
   12 /*! \file */
   13 
   14 #include <inttypes.h>
   15 #include <stdbool.h>
   16 #include <sys/stat.h>
   17 
   18 #include <isc/crc64.h>
   19 #include <isc/file.h>
   20 #include <isc/hex.h>
   21 #include <isc/mem.h>
   22 #include <isc/once.h>
   23 #include <isc/platform.h>
   24 #include <isc/print.h>
   25 #include <isc/refcount.h>
   26 #include <isc/socket.h>
   27 #include <isc/stdio.h>
   28 #include <isc/string.h>
   29 #include <isc/util.h>
   30 
   31 /*%
   32  * This define is so dns/name.h (included by dns/fixedname.h) uses more
   33  * efficient macro calls instead of functions for a few operations.
   34  */
   35 #define DNS_NAME_USEINLINE 1
   36 
   37 #include <unistd.h>
   38 
   39 #include <dns/fixedname.h>
   40 #include <dns/log.h>
   41 #include <dns/rbt.h>
   42 #include <dns/result.h>
   43 #include <dns/version.h>
   44 
   45 #define CHECK(x)                             \
   46     do {                                 \
   47         result = (x);                \
   48         if (result != ISC_R_SUCCESS) \
   49             goto cleanup;        \
   50     } while (0)
   51 
   52 #define RBT_MAGIC      ISC_MAGIC('R', 'B', 'T', '+')
   53 #define VALID_RBT(rbt) ISC_MAGIC_VALID(rbt, RBT_MAGIC)
   54 
   55 /*
   56  * XXXDCL Since parent pointers were added in again, I could remove all of the
   57  * chain junk, and replace with dns_rbt_firstnode, _previousnode, _nextnode,
   58  * _lastnode.  This would involve pretty major change to the API.
   59  */
   60 #define CHAIN_MAGIC    ISC_MAGIC('0', '-', '0', '-')
   61 #define VALID_CHAIN(chain) ISC_MAGIC_VALID(chain, CHAIN_MAGIC)
   62 
   63 #define RBT_HASH_MIN_BITS   4
   64 #define RBT_HASH_MAX_BITS   32
   65 #define RBT_HASH_OVERCOMMIT 3
   66 #define RBT_HASH_BUCKETSIZE 4096 /* FIXME: What would be a good value here? */
   67 
   68 #ifdef RBT_MEM_TEST
   69 #undef RBT_HASH_SIZE
   70 #define RBT_HASH_SIZE 2 /*%< To give the reallocation code a workout. */
   71 #endif          /* ifdef RBT_MEM_TEST */
   72 
   73 #define GOLDEN_RATIO_32 0x61C88647
   74 
   75 #define HASHSIZE(bits) (UINT64_C(1) << (bits))
   76 
   77 static inline uint32_t
   78 hash_32(uint32_t val, unsigned int bits) {
   79     REQUIRE(bits <= RBT_HASH_MAX_BITS);
   80     /* High bits are more random. */
   81     return (val * GOLDEN_RATIO_32 >> (32 - bits));
   82 }
   83 
   84 struct dns_rbt {
   85     unsigned int magic;
   86     isc_mem_t *mctx;
   87     dns_rbtnode_t *root;
   88     void (*data_deleter)(void *, void *);
   89     void *deleter_arg;
   90     unsigned int nodecount;
   91     uint16_t hashbits;
   92     uint16_t maxhashbits;
   93     dns_rbtnode_t **hashtable;
   94     void *mmap_location;
   95 };
   96 
   97 #define RED   0
   98 #define BLACK 1
   99 
  100 /*
  101  * This is the header for map-format RBT images.  It is populated,
  102  * and then written, as the LAST thing done to the file before returning.
  103  * Writing this last (with zeros in the header area initially) will ensure
  104  * that the header is only valid when the RBT image is also valid.
  105  */
  106 typedef struct file_header file_header_t;
  107 
  108 /* Pad to 32 bytes */
  109 static char FILE_VERSION[32] = "\0";
  110 
  111 /* Header length, always the same size regardless of structure size */
  112 #define HEADER_LENGTH 1024
  113 
  114 struct file_header {
  115     char version1[32];
  116     uint64_t first_node_offset; /* usually 1024 */
  117     /*
  118      * information about the system on which the map file was generated
  119      * will be used to tell if we can load the map file or not
  120      */
  121     uint32_t ptrsize;
  122     unsigned int bigendian : 1;  /* big or little endian system */
  123     unsigned int rdataset_fixed : 1; /* compiled with
  124                       * --enable-rrset-fixed
  125                       */
  126     unsigned int nodecount;      /* shadow from rbt structure */
  127     uint64_t crc;
  128     char version2[32]; /* repeated; must match version1 */
  129 };
  130 
  131 /*
  132  * The following declarations are for the serialization of an RBT:
  133  *
  134  * step one: write out a zeroed header of 1024 bytes
  135  * step two: walk the tree in a depth-first, left-right-down order, writing
  136  * out the nodes, reserving space as we go, correcting addresses to point
  137  * at the proper offset in the file, and setting a flag for each pointer to
  138  * indicate that it is a reference to a location in the file, rather than in
  139  * memory.
  140  * step three: write out the header, adding the information that will be
  141  * needed to re-create the tree object itself.
  142  *
  143  * The RBTDB object will do this three times, once for each of the three
  144  * RBT objects it contains.
  145  *
  146  * Note: 'file' must point an actual open file that can be mmapped
  147  * and fseeked, not to a pipe or stream
  148  */
  149 
  150 static isc_result_t
  151 dns_rbt_zero_header(FILE *file);
  152 
  153 static isc_result_t
  154 write_header(FILE *file, dns_rbt_t *rbt, uint64_t first_node_offset,
  155          uint64_t crc);
  156 
  157 static bool
  158 match_header_version(file_header_t *header);
  159 
  160 static isc_result_t
  161 serialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left, uintptr_t right,
  162            uintptr_t down, uintptr_t parent, uintptr_t data, uint64_t *crc);
  163 
  164 static isc_result_t
  165 serialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
  166         dns_rbtdatawriter_t datawriter, void *writer_arg,
  167         uintptr_t *where, uint64_t *crc);
  168 
  169 /*
  170  * The following functions allow you to get the actual address of a pointer
  171  * without having to use an if statement to check to see if that address is
  172  * relative or not
  173  */
  174 static inline dns_rbtnode_t *
  175 getparent(dns_rbtnode_t *node, file_header_t *header) {
  176     char *adjusted_address = (char *)(node->parent);
  177     adjusted_address += node->parent_is_relative * (uintptr_t)header;
  178 
  179     return ((dns_rbtnode_t *)adjusted_address);
  180 }
  181 
  182 static inline dns_rbtnode_t *
  183 getleft(dns_rbtnode_t *node, file_header_t *header) {
  184     char *adjusted_address = (char *)(node->left);
  185     adjusted_address += node->left_is_relative * (uintptr_t)header;
  186 
  187     return ((dns_rbtnode_t *)adjusted_address);
  188 }
  189 
  190 static inline dns_rbtnode_t *
  191 getright(dns_rbtnode_t *node, file_header_t *header) {
  192     char *adjusted_address = (char *)(node->right);
  193     adjusted_address += node->right_is_relative * (uintptr_t)header;
  194 
  195     return ((dns_rbtnode_t *)adjusted_address);
  196 }
  197 
  198 static inline dns_rbtnode_t *
  199 getdown(dns_rbtnode_t *node, file_header_t *header) {
  200     char *adjusted_address = (char *)(node->down);
  201     adjusted_address += node->down_is_relative * (uintptr_t)header;
  202 
  203     return ((dns_rbtnode_t *)adjusted_address);
  204 }
  205 
  206 static inline dns_rbtnode_t *
  207 getdata(dns_rbtnode_t *node, file_header_t *header) {
  208     char *adjusted_address = (char *)(node->data);
  209     adjusted_address += node->data_is_relative * (uintptr_t)header;
  210 
  211     return ((dns_rbtnode_t *)adjusted_address);
  212 }
  213 
  214 /*%
  215  * Elements of the rbtnode structure.
  216  */
  217 #define PARENT(node)       ((node)->parent)
  218 #define LEFT(node)     ((node)->left)
  219 #define RIGHT(node)    ((node)->right)
  220 #define DOWN(node)     ((node)->down)
  221 #define UPPERNODE(node)    ((node)->uppernode)
  222 #define DATA(node)     ((node)->data)
  223 #define IS_EMPTY(node)     ((node)->data == NULL)
  224 #define HASHNEXT(node)     ((node)->hashnext)
  225 #define HASHVAL(node)      ((node)->hashval)
  226 #define COLOR(node)    ((node)->color)
  227 #define NAMELEN(node)      ((node)->namelen)
  228 #define OLDNAMELEN(node)   ((node)->oldnamelen)
  229 #define OFFSETLEN(node)    ((node)->offsetlen)
  230 #define ATTRS(node)    ((node)->attributes)
  231 #define IS_ROOT(node)      ((node)->is_root)
  232 #define FINDCALLBACK(node) ((node)->find_callback)
  233 
  234 /*%
  235  * Structure elements from the rbtdb.c, not
  236  * used as part of the rbt.c algorithms.
  237  */
  238 #define DIRTY(node)   ((node)->dirty)
  239 #define WILD(node)    ((node)->wild)
  240 #define LOCKNUM(node) ((node)->locknum)
  241 
  242 /*%
  243  * The variable length stuff stored after the node has the following
  244  * structure.
  245  *
  246  *  &lt;name_data&gt;{1..255}&lt;oldoffsetlen&gt;{1}&lt;offsets&gt;{1..128}
  247  *
  248  * &lt;name_data&gt; contains the name of the node when it was created.
  249  * &lt;oldoffsetlen&gt; contains the length of &lt;offsets&gt; when the node
  250  * was created.
  251  * &lt;offsets&gt; contains the offsets into name for each label when the node
  252  * was created.
  253  */
  254 
  255 #define NAME(node)     ((unsigned char *)((node) + 1))
  256 #define OFFSETS(node)      (NAME(node) + OLDNAMELEN(node) + 1)
  257 #define OLDOFFSETLEN(node) (OFFSETS(node)[-1])
  258 
  259 #define NODE_SIZE(node) \
  260     (sizeof(*node) + OLDNAMELEN(node) + OLDOFFSETLEN(node) + 1)
  261 
  262 /*%
  263  * Color management.
  264  */
  265 #define IS_RED(node)     ((node) != NULL && (node)->color == RED)
  266 #define IS_BLACK(node)   ((node) == NULL || (node)->color == BLACK)
  267 #define MAKE_RED(node)   ((node)->color = RED)
  268 #define MAKE_BLACK(node) ((node)->color = BLACK)
  269 
  270 /*%
  271  * Chain management.
  272  *
  273  * The "ancestors" member of chains were removed, with their job now
  274  * being wholly handled by parent pointers (which didn't exist, because
  275  * of memory concerns, when chains were first implemented).
  276  */
  277 #define ADD_LEVEL(chain, node)                                     \
  278     do {                                                       \
  279         INSIST((chain)->level_count < DNS_RBT_LEVELBLOCK); \
  280         (chain)->levels[(chain)->level_count++] = (node);  \
  281     } while (0)
  282 
  283 /*%
  284  * The following macros directly access normally private name variables.
  285  * These macros are used to avoid a lot of function calls in the critical
  286  * path of the tree traversal code.
  287  */
  288 
  289 static inline void
  290 NODENAME(dns_rbtnode_t *node, dns_name_t *name) {
  291     name->length = NAMELEN(node);
  292     name->labels = OFFSETLEN(node);
  293     name->ndata = NAME(node);
  294     name->offsets = OFFSETS(node);
  295     name->attributes = ATTRS(node);
  296     name->attributes |= DNS_NAMEATTR_READONLY;
  297 }
  298 
  299 #ifdef DEBUG
  300 #define inline
  301 /*
  302  * A little something to help out in GDB.
  303  */
  304 dns_name_t
  305 Name(dns_rbtnode_t *node);
  306 dns_name_t
  307 Name(dns_rbtnode_t *node) {
  308     dns_name_t name;
  309 
  310     dns_name_init(&name, NULL);
  311     if (node != NULL) {
  312         NODENAME(node, &name);
  313     }
  314 
  315     return (name);
  316 }
  317 
  318 static void
  319 hexdump(const char *desc, unsigned char *data, size_t size) {
  320     char hexdump[BUFSIZ * 2 + 1];
  321     isc_buffer_t b;
  322     isc_region_t r;
  323     isc_result_t result;
  324     size_t bytes;
  325 
  326     fprintf(stderr, "%s: ", desc);
  327     do {
  328         isc_buffer_init(&b, hexdump, sizeof(hexdump));
  329         r.base = data;
  330         r.length = bytes = (size > BUFSIZ) ? BUFSIZ : size;
  331         result = isc_hex_totext(&r, 0, "", &b);
  332         RUNTIME_CHECK(result == ISC_R_SUCCESS);
  333         isc_buffer_putuint8(&b, 0);
  334         fprintf(stderr, "%s", hexdump);
  335         data += bytes;
  336         size -= bytes;
  337     } while (size > 0);
  338     fprintf(stderr, "\n");
  339 }
  340 #endif /* DEBUG */
  341 
  342 /*
  343  * Upper node is the parent of the root of the passed node's
  344  * subtree. The passed node must not be NULL.
  345  */
  346 static inline dns_rbtnode_t *
  347 get_upper_node(dns_rbtnode_t *node) {
  348     return (UPPERNODE(node));
  349 }
  350 
  351 static void
  352 fixup_uppernodes_helper(dns_rbtnode_t *node, dns_rbtnode_t *uppernode) {
  353     if (node == NULL) {
  354         return;
  355     }
  356 
  357     UPPERNODE(node) = uppernode;
  358 
  359     fixup_uppernodes_helper(LEFT(node), uppernode);
  360     fixup_uppernodes_helper(RIGHT(node), uppernode);
  361     fixup_uppernodes_helper(DOWN(node), node);
  362 }
  363 
  364 /*
  365  * This function is used to fixup uppernode members of all dns_rbtnodes
  366  * after deserialization.
  367  */
  368 static void
  369 fixup_uppernodes(dns_rbt_t *rbt) {
  370     fixup_uppernodes_helper(rbt->root, NULL);
  371 }
  372 
  373 size_t
  374 dns__rbtnode_getdistance(dns_rbtnode_t *node) {
  375     size_t nodes = 1;
  376 
  377     while (node != NULL) {
  378         if (IS_ROOT(node)) {
  379             break;
  380         }
  381         nodes++;
  382         node = PARENT(node);
  383     }
  384 
  385     return (nodes);
  386 }
  387 
  388 /*
  389  * Forward declarations.
  390  */
  391 static isc_result_t
  392 create_node(isc_mem_t *mctx, const dns_name_t *name, dns_rbtnode_t **nodep);
  393 
  394 static isc_result_t
  395 inithash(dns_rbt_t *rbt);
  396 
  397 static inline void
  398 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, const dns_name_t *name);
  399 
  400 static inline void
  401 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
  402 
  403 static uint32_t
  404 rehash_bits(dns_rbt_t *rbt, size_t newcount);
  405 static void
  406 rehash(dns_rbt_t *rbt, uint32_t newbits);
  407 static void
  408 maybe_rehash(dns_rbt_t *rbt, size_t size);
  409 
  410 static inline void
  411 rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
  412 static inline void
  413 rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
  414 
  415 static void
  416 addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
  417        dns_rbtnode_t **rootp);
  418 
  419 static void
  420 deletefromlevel(dns_rbtnode_t *item, dns_rbtnode_t **rootp);
  421 
  422 static isc_result_t
  423 treefix(dns_rbt_t *rbt, void *base, size_t size, dns_rbtnode_t *n,
  424     const dns_name_t *name, dns_rbtdatafixer_t datafixer, void *fixer_arg,
  425     uint64_t *crc);
  426 
  427 static void
  428 deletetreeflat(dns_rbt_t *rbt, unsigned int quantum, bool unhash,
  429            dns_rbtnode_t **nodep);
  430 
  431 static void
  432 printnodename(dns_rbtnode_t *node, bool quoted, FILE *f);
  433 
  434 static void
  435 freenode(dns_rbt_t *rbt, dns_rbtnode_t **nodep);
  436 
  437 static isc_result_t
  438 dns_rbt_zero_header(FILE *file) {
  439     /*
  440      * Write out a zeroed header as a placeholder.  Doing this ensures
  441      * that the file will not read while it is partially written, should
  442      * writing fail or be interrupted.
  443      */
  444     char buffer[HEADER_LENGTH];
  445     isc_result_t result;
  446 
  447     memset(buffer, 0, HEADER_LENGTH);
  448     result = isc_stdio_write(buffer, 1, HEADER_LENGTH, file, NULL);
  449     if (result != ISC_R_SUCCESS) {
  450         return (result);
  451     }
  452 
  453     result = fflush(file);
  454     if (result != ISC_R_SUCCESS) {
  455         return (result);
  456     }
  457 
  458     return (ISC_R_SUCCESS);
  459 }
  460 
  461 static isc_once_t once = ISC_ONCE_INIT;
  462 
  463 static void
  464 init_file_version(void) {
  465     int n;
  466 
  467     memset(FILE_VERSION, 0, sizeof(FILE_VERSION));
  468     n = snprintf(FILE_VERSION, sizeof(FILE_VERSION), "RBT Image %s %s",
  469              dns_major, dns_mapapi);
  470     INSIST(n > 0 && (unsigned int)n < sizeof(FILE_VERSION));
  471 }
  472 
  473 /*
  474  * Write out the real header, including NodeDump version information
  475  * and the offset of the first node.
  476  *
  477  * Any information stored in the rbt object itself should be stored
  478  * here.
  479  */
  480 static isc_result_t
  481 write_header(FILE *file, dns_rbt_t *rbt, uint64_t first_node_offset,
  482          uint64_t crc) {
  483     file_header_t header;
  484     isc_result_t result;
  485     off_t location;
  486 
  487     RUNTIME_CHECK(isc_once_do(&once, init_file_version) == ISC_R_SUCCESS);
  488 
  489     memset(&header, 0, sizeof(file_header_t));
  490     memmove(header.version1, FILE_VERSION, sizeof(header.version1));
  491     memmove(header.version2, FILE_VERSION, sizeof(header.version2));
  492     header.first_node_offset = first_node_offset;
  493     header.ptrsize = (uint32_t)sizeof(void *);
  494     header.bigendian = (1 == htonl(1)) ? 1 : 0;
  495 
  496 #ifdef DNS_RDATASET_FIXED
  497     header.rdataset_fixed = 1;
  498 #else  /* ifdef DNS_RDATASET_FIXED */
  499     header.rdataset_fixed = 0;
  500 #endif /* ifdef DNS_RDATASET_FIXED */
  501 
  502     header.nodecount = rbt->nodecount;
  503 
  504     header.crc = crc;
  505 
  506     CHECK(isc_stdio_tell(file, &location));
  507     location = dns_rbt_serialize_align(location);
  508     CHECK(isc_stdio_seek(file, location, SEEK_SET));
  509     CHECK(isc_stdio_write(&header, 1, sizeof(file_header_t), file, NULL));
  510     CHECK(fflush(file));
  511 
  512     /* Ensure we are always at the end of the file. */
  513     CHECK(isc_stdio_seek(file, 0, SEEK_END));
  514 
  515 cleanup:
  516     return (result);
  517 }
  518 
  519 static bool
  520 match_header_version(file_header_t *header) {
  521     RUNTIME_CHECK(isc_once_do(&once, init_file_version) == ISC_R_SUCCESS);
  522 
  523     if (memcmp(header->version1, FILE_VERSION, sizeof(header->version1)) !=
  524             0 ||
  525         memcmp(header->version2, FILE_VERSION, sizeof(header->version1)) !=
  526             0)
  527     {
  528         return (false);
  529     }
  530 
  531     return (true);
  532 }
  533 
  534 unsigned int
  535 dns__rbtnode_namelen(dns_rbtnode_t *node) {
  536     dns_name_t current;
  537     unsigned int len = 0;
  538 
  539     REQUIRE(DNS_RBTNODE_VALID(node));
  540 
  541     dns_name_init(&current, NULL);
  542 
  543     do {
  544         if (node != NULL) {
  545             NODENAME(node, &current);
  546             len += current.length;
  547         } else {
  548             len += 1;
  549             break;
  550         }
  551 
  552         node = get_upper_node(node);
  553     } while (!dns_name_isabsolute(&current));
  554 
  555     return (len);
  556 }
  557 
  558 static isc_result_t
  559 serialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left, uintptr_t right,
  560            uintptr_t down, uintptr_t parent, uintptr_t data,
  561            uint64_t *crc) {
  562     isc_result_t result;
  563     dns_rbtnode_t temp_node;
  564     off_t file_position;
  565     unsigned char *node_data = NULL;
  566     size_t datasize;
  567 
  568     INSIST(node != NULL);
  569 
  570     CHECK(isc_stdio_tell(file, &file_position));
  571     file_position = dns_rbt_serialize_align(file_position);
  572     CHECK(isc_stdio_seek(file, file_position, SEEK_SET));
  573 
  574     temp_node = *node;
  575     temp_node.down_is_relative = 0;
  576     temp_node.left_is_relative = 0;
  577     temp_node.right_is_relative = 0;
  578     temp_node.parent_is_relative = 0;
  579     temp_node.data_is_relative = 0;
  580     temp_node.is_mmapped = 1;
  581 
  582     /*
  583      * If the next node is not NULL, calculate the next node's location
  584      * in the file.  Note that this will have to change when the data
  585      * structure changes, and it also assumes that we always write the
  586      * nodes out in list order (which we currently do.)
  587      */
  588     if (temp_node.parent != NULL) {
  589         temp_node.parent = (dns_rbtnode_t *)(parent);
  590         temp_node.parent_is_relative = 1;
  591     }
  592     if (temp_node.left != NULL) {
  593         temp_node.left = (dns_rbtnode_t *)(left);
  594         temp_node.left_is_relative = 1;
  595     }
  596     if (temp_node.right != NULL) {
  597         temp_node.right = (dns_rbtnode_t *)(right);
  598         temp_node.right_is_relative = 1;
  599     }
  600     if (temp_node.down != NULL) {
  601         temp_node.down = (dns_rbtnode_t *)(down);
  602         temp_node.down_is_relative = 1;
  603     }
  604     if (temp_node.data != NULL) {
  605         temp_node.data = (dns_rbtnode_t *)(data);
  606         temp_node.data_is_relative = 1;
  607     }
  608 
  609     temp_node.fullnamelen = dns__rbtnode_namelen(node);
  610 
  611     node_data = (unsigned char *)node + sizeof(dns_rbtnode_t);
  612     datasize = NODE_SIZE(node) - sizeof(dns_rbtnode_t);
  613 
  614     CHECK(isc_stdio_write(&temp_node, 1, sizeof(dns_rbtnode_t), file,
  615                   NULL));
  616     CHECK(isc_stdio_write(node_data, 1, datasize, file, NULL));
  617 
  618 #ifdef DEBUG
  619     fprintf(stderr, "serialize ");
  620     dns_name_print(name, stderr);
  621     fprintf(stderr, "\n");
  622     hexdump("node header", (unsigned char *)&temp_node,
  623         sizeof(dns_rbtnode_t));
  624     hexdump("node data", node_data, datasize);
  625 #endif /* ifdef DEBUG */
  626 
  627     isc_crc64_update(crc, (const uint8_t *)&temp_node,
  628              sizeof(dns_rbtnode_t));
  629     isc_crc64_update(crc, (const uint8_t *)node_data, datasize);
  630 
  631 cleanup:
  632     return (result);
  633 }
  634 
  635 static isc_result_t
  636 serialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
  637         dns_rbtdatawriter_t datawriter, void *writer_arg,
  638         uintptr_t *where, uint64_t *crc) {
  639     uintptr_t left = 0, right = 0, down = 0, data = 0;
  640     off_t location = 0, offset_adjust;
  641     isc_result_t result;
  642 
  643     if (node == NULL) {
  644         if (where != NULL) {
  645             *where = 0;
  646         }
  647         return (ISC_R_SUCCESS);
  648     }
  649 
  650     /* Reserve space for current node. */
  651     CHECK(isc_stdio_tell(file, &location));
  652     location = dns_rbt_serialize_align(location);
  653     CHECK(isc_stdio_seek(file, location, SEEK_SET));
  654 
  655     offset_adjust = dns_rbt_serialize_align(location + NODE_SIZE(node));
  656     CHECK(isc_stdio_seek(file, offset_adjust, SEEK_SET));
  657 
  658     /*
  659      * Serialize the rest of the tree.
  660      *
  661      * WARNING: A change in the order (from left, right, down)
  662      * will break the way the crc hash is computed.
  663      */
  664     CHECK(serialize_nodes(file, getleft(node, NULL), location, datawriter,
  665                   writer_arg, &left, crc));
  666     CHECK(serialize_nodes(file, getright(node, NULL), location, datawriter,
  667                   writer_arg, &right, crc));
  668     CHECK(serialize_nodes(file, getdown(node, NULL), location, datawriter,
  669                   writer_arg, &down, crc));
  670 
  671     if (node->data != NULL) {
  672         off_t ret;
  673 
  674         CHECK(isc_stdio_tell(file, &ret));
  675         ret = dns_rbt_serialize_align(ret);
  676         CHECK(isc_stdio_seek(file, ret, SEEK_SET));
  677         data = ret;
  678 
  679         datawriter(file, node->data, writer_arg, crc);
  680     }
  681 
  682     /* Seek back to reserved space. */
  683     CHECK(isc_stdio_seek(file, location, SEEK_SET));
  684 
  685     /* Serialize the current node. */
  686     CHECK(serialize_node(file, node, left, right, down, parent, data, crc));
  687 
  688     /* Ensure we are always at the end of the file. */
  689     CHECK(isc_stdio_seek(file, 0, SEEK_END));
  690 
  691     if (where != NULL) {
  692         *where = (uintptr_t)location;
  693     }
  694 
  695 cleanup:
  696     return (result);
  697 }
  698 
  699 off_t
  700 dns_rbt_serialize_align(off_t target) {
  701     off_t offset = target % 8;
  702 
  703     if (offset == 0) {
  704         return (target);
  705     } else {
  706         return (target + 8 - offset);
  707     }
  708 }
  709 
  710 isc_result_t
  711 dns_rbt_serialize_tree(FILE *file, dns_rbt_t *rbt,
  712                dns_rbtdatawriter_t datawriter, void *writer_arg,
  713                off_t *offset) {
  714     isc_result_t result;
  715     off_t header_position, node_position, end_position;
  716     uint64_t crc;
  717 
  718     REQUIRE(file != NULL);
  719 
  720     CHECK(isc_file_isplainfilefd(fileno(file)));
  721 
  722     isc_crc64_init(&crc);
  723 
  724     CHECK(isc_stdio_tell(file, &header_position));
  725 
  726     /* Write dummy header */
  727     CHECK(dns_rbt_zero_header(file));
  728 
  729     /* Serialize nodes */
  730     CHECK(isc_stdio_tell(file, &node_position));
  731     CHECK(serialize_nodes(file, rbt->root, 0, datawriter, writer_arg, NULL,
  732                   &crc));
  733 
  734     CHECK(isc_stdio_tell(file, &end_position));
  735     if (node_position == end_position) {
  736         CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
  737         *offset = 0;
  738         return (ISC_R_SUCCESS);
  739     }
  740 
  741     isc_crc64_final(&crc);
  742 #ifdef DEBUG
  743     hexdump("serializing CRC", (unsigned char *)&crc, sizeof(crc));
  744 #endif /* ifdef DEBUG */
  745 
  746     /* Serialize header */
  747     CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
  748     CHECK(write_header(file, rbt, HEADER_LENGTH, crc));
  749 
  750     /* Ensure we are always at the end of the file. */
  751     CHECK(isc_stdio_seek(file, 0, SEEK_END));
  752     *offset = dns_rbt_serialize_align(header_position);
  753 
  754 cleanup:
  755     return (result);
  756 }
  757 
  758 #define CONFIRM(a)                                  \
  759     do {                                        \
  760         if (!(a)) {                         \
  761             result = ISC_R_INVALIDFILE; \
  762             goto cleanup;               \
  763         }                                   \
  764     } while (0);
  765 
  766 static isc_result_t
  767 treefix(dns_rbt_t *rbt, void *base, size_t filesize, dns_rbtnode_t *n,
  768     const dns_name_t *name, dns_rbtdatafixer_t datafixer, void *fixer_arg,
  769     uint64_t *crc) {
  770     isc_result_t result = ISC_R_SUCCESS;
  771     dns_fixedname_t fixed;
  772     dns_name_t nodename, *fullname;
  773     unsigned char *node_data;
  774     dns_rbtnode_t header;
  775     size_t datasize, nodemax = filesize - sizeof(dns_rbtnode_t);
  776 
  777     if (n == NULL) {
  778         return (ISC_R_SUCCESS);
  779     }
  780 
  781     CONFIRM((void *)n >= base);
  782     CONFIRM((char *)n - (char *)base <= (int)nodemax);
  783     CONFIRM(DNS_RBTNODE_VALID(n));
  784 
  785     dns_name_init(&nodename, NULL);
  786     NODENAME(n, &nodename);
  787 
  788     fullname = &nodename;
  789     CONFIRM(dns_name_isvalid(fullname));
  790 
  791     if (!dns_name_isabsolute(&nodename)) {
  792         fullname = dns_fixedname_initname(&fixed);
  793         CHECK(dns_name_concatenate(&nodename, name, fullname, NULL));
  794     }
  795 
  796     /* memorize header contents prior to fixup */
  797     memmove(&header, n, sizeof(header));
  798 
  799     if (n->left_is_relative) {
  800         CONFIRM(n->left <= (dns_rbtnode_t *)nodemax);
  801         n->left = getleft(n, rbt->mmap_location);
  802         n->left_is_relative = 0;
  803         CONFIRM(DNS_RBTNODE_VALID(n->left));
  804     } else {
  805         CONFIRM(n->left == NULL);
  806     }
  807 
  808     if (n->right_is_relative) {
  809         CONFIRM(n->right <= (dns_rbtnode_t *)nodemax);
  810         n->right = getright(n, rbt->mmap_location);
  811         n->right_is_relative = 0;
  812         CONFIRM(DNS_RBTNODE_VALID(n->right));
  813     } else {
  814         CONFIRM(n->right == NULL);
  815     }
  816 
  817     if (n->down_is_relative) {
  818         CONFIRM(n->down <= (dns_rbtnode_t *)nodemax);
  819         n->down = getdown(n, rbt->mmap_location);
  820         n->down_is_relative = 0;
  821         CONFIRM(n->down > (dns_rbtnode_t *)n);
  822         CONFIRM(DNS_RBTNODE_VALID(n->down));
  823     } else {
  824         CONFIRM(n->down == NULL);
  825     }
  826 
  827     if (n->parent_is_relative) {
  828         CONFIRM(n->parent <= (dns_rbtnode_t *)nodemax);
  829         n->parent = getparent(n, rbt->mmap_location);
  830         n->parent_is_relative = 0;
  831         CONFIRM(n->parent < (dns_rbtnode_t *)n);
  832         CONFIRM(DNS_RBTNODE_VALID(n->parent));
  833     } else {
  834         CONFIRM(n->parent == NULL);
  835     }
  836 
  837     if (n->data_is_relative) {
  838         CONFIRM(n->data <= (void *)filesize);
  839         n->data = getdata(n, rbt->mmap_location);
  840         n->data_is_relative = 0;
  841         CONFIRM(n->data > (void *)n);
  842     } else {
  843         CONFIRM(n->data == NULL);
  844     }
  845 
  846     hash_node(rbt, n, fullname);
  847 
  848     /* a change in the order (from left, right, down) will break hashing*/
  849     if (n->left != NULL) {
  850         CHECK(treefix(rbt, base, filesize, n->left, name, datafixer,
  851                   fixer_arg, crc));
  852     }
  853     if (n->right != NULL) {
  854         CHECK(treefix(rbt, base, filesize, n->right, name, datafixer,
  855                   fixer_arg, crc));
  856     }
  857     if (n->down != NULL) {
  858         CHECK(treefix(rbt, base, filesize, n->down, fullname, datafixer,
  859                   fixer_arg, crc));
  860     }
  861 
  862     if (datafixer != NULL && n->data != NULL) {
  863         CHECK(datafixer(n, base, filesize, fixer_arg, crc));
  864     }
  865 
  866     rbt->nodecount++;
  867     node_data = (unsigned char *)n + sizeof(dns_rbtnode_t);
  868     datasize = NODE_SIZE(n) - sizeof(dns_rbtnode_t);
  869 
  870 #ifdef DEBUG
  871     fprintf(stderr, "deserialize ");
  872     dns_name_print(&nodename, stderr);
  873     fprintf(stderr, "\n");
  874     hexdump("node header", (unsigned char *)&header, sizeof(dns_rbtnode_t));
  875     hexdump("node data", node_data, datasize);
  876 #endif /* ifdef DEBUG */
  877     isc_crc64_update(crc, (const uint8_t *)&header, sizeof(dns_rbtnode_t));
  878     isc_crc64_update(crc, (const uint8_t *)node_data, datasize);
  879 
  880 cleanup:
  881     return (result);
  882 }
  883 
  884 isc_result_t
  885 dns_rbt_deserialize_tree(void *base_address, size_t filesize,
  886              off_t header_offset, isc_mem_t *mctx,
  887              dns_rbtdeleter_t deleter, void *deleter_arg,
  888              dns_rbtdatafixer_t datafixer, void *fixer_arg,
  889              dns_rbtnode_t **originp, dns_rbt_t **rbtp) {
  890     isc_result_t result = ISC_R_SUCCESS;
  891     file_header_t *header;
  892     dns_rbt_t *rbt = NULL;
  893     uint64_t crc;
  894     unsigned int host_big_endian;
  895 
  896     REQUIRE(originp == NULL || *originp == NULL);
  897     REQUIRE(rbtp != NULL && *rbtp == NULL);
  898 
  899     isc_crc64_init(&crc);
  900 
  901     CHECK(dns_rbt_create(mctx, deleter, deleter_arg, &rbt));
  902 
  903     rbt->mmap_location = base_address;
  904 
  905     header = (file_header_t *)((char *)base_address + header_offset);
  906     if (!match_header_version(header)) {
  907         result = ISC_R_INVALIDFILE;
  908         goto cleanup;
  909     }
  910 
  911 #ifdef DNS_RDATASET_FIXED
  912     if (header->rdataset_fixed != 1) {
  913         result = ISC_R_INVALIDFILE;
  914         goto cleanup;
  915     }
  916 
  917 #else  /* ifdef DNS_RDATASET_FIXED */
  918     if (header->rdataset_fixed != 0) {
  919         result = ISC_R_INVALIDFILE;
  920         goto cleanup;
  921     }
  922 #endif /* ifdef DNS_RDATASET_FIXED */
  923 
  924     if (header->ptrsize != (uint32_t)sizeof(void *)) {
  925         result = ISC_R_INVALIDFILE;
  926         goto cleanup;
  927     }
  928 
  929     host_big_endian = (1 == htonl(1));
  930     if (header->bigendian != host_big_endian) {
  931         result = ISC_R_INVALIDFILE;
  932         goto cleanup;
  933     }
  934 
  935     /* Copy other data items from the header into our rbt. */
  936     rbt->root = (dns_rbtnode_t *)((char *)base_address + header_offset +
  937                       header->first_node_offset);
  938 
  939     if ((header->nodecount * sizeof(dns_rbtnode_t)) > filesize) {
  940         result = ISC_R_INVALIDFILE;
  941         goto cleanup;
  942     }
  943     maybe_rehash(rbt, header->nodecount);
  944 
  945     CHECK(treefix(rbt, base_address, filesize, rbt->root, dns_rootname,
  946               datafixer, fixer_arg, &crc));
  947 
  948     isc_crc64_final(&crc);
  949 #ifdef DEBUG
  950     hexdump("deserializing CRC", (unsigned char *)&crc, sizeof(crc));
  951 #endif /* ifdef DEBUG */
  952 
  953     /* Check file hash */
  954     if (header->crc != crc) {
  955         result = ISC_R_INVALIDFILE;
  956         goto cleanup;
  957     }
  958 
  959     if (header->nodecount != rbt->nodecount) {
  960         result = ISC_R_INVALIDFILE;
  961         goto cleanup;
  962     }
  963 
  964     fixup_uppernodes(rbt);
  965 
  966     *rbtp = rbt;
  967     if (originp != NULL) {
  968         *originp = rbt->root;
  969     }
  970 
  971 cleanup:
  972     if (result != ISC_R_SUCCESS && rbt != NULL) {
  973         rbt->root = NULL;
  974         rbt->nodecount = 0;
  975         dns_rbt_destroy(&rbt);
  976     }
  977 
  978     return (result);
  979 }
  980 
  981 /*
  982  * Initialize a red/black tree of trees.
  983  */
  984 isc_result_t
  985 dns_rbt_create(isc_mem_t *mctx, dns_rbtdeleter_t deleter, void *deleter_arg,
  986            dns_rbt_t **rbtp) {
  987     isc_result_t result;
  988     dns_rbt_t *rbt;
  989 
  990     REQUIRE(mctx != NULL);
  991     REQUIRE(rbtp != NULL && *rbtp == NULL);
  992     REQUIRE(deleter == NULL ? deleter_arg == NULL : 1);
  993 
  994     rbt = isc_mem_get(mctx, sizeof(*rbt));
  995 
  996     rbt->mctx = NULL;
  997     isc_mem_attach(mctx, &rbt->mctx);
  998     rbt->data_deleter = deleter;
  999     rbt->deleter_arg = deleter_arg;
 1000     rbt->root = NULL;
 1001     rbt->nodecount = 0;
 1002     rbt->hashtable = NULL;
 1003     rbt->hashbits = 0;
 1004     rbt->maxhashbits = RBT_HASH_MAX_BITS;
 1005     rbt->mmap_location = NULL;
 1006 
 1007     result = inithash(rbt);
 1008     if (result != ISC_R_SUCCESS) {
 1009         isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
 1010         return (result);
 1011     }
 1012 
 1013     rbt->magic = RBT_MAGIC;
 1014 
 1015     *rbtp = rbt;
 1016 
 1017     return (ISC_R_SUCCESS);
 1018 }
 1019 
 1020 /*
 1021  * Deallocate a red/black tree of trees.
 1022  */
 1023 void
 1024 dns_rbt_destroy(dns_rbt_t **rbtp) {
 1025     RUNTIME_CHECK(dns_rbt_destroy2(rbtp, 0) == ISC_R_SUCCESS);
 1026 }
 1027 
 1028 isc_result_t
 1029 dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) {
 1030     dns_rbt_t *rbt;
 1031 
 1032     REQUIRE(rbtp != NULL && VALID_RBT(*rbtp));
 1033 
 1034     rbt = *rbtp;
 1035 
 1036     deletetreeflat(rbt, quantum, false, &rbt->root);
 1037     if (rbt->root != NULL) {
 1038         return (ISC_R_QUOTA);
 1039     }
 1040 
 1041     *rbtp = NULL;
 1042 
 1043     INSIST(rbt->nodecount == 0);
 1044 
 1045     rbt->mmap_location = NULL;
 1046 
 1047     if (rbt->hashtable != NULL) {
 1048         size_t size = HASHSIZE(rbt->hashbits) * sizeof(dns_rbtnode_t *);
 1049         isc_mem_put(rbt->mctx, rbt->hashtable, size);
 1050     }
 1051 
 1052     rbt->magic = 0;
 1053 
 1054     isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
 1055     return (ISC_R_SUCCESS);
 1056 }
 1057 
 1058 unsigned int
 1059 dns_rbt_nodecount(dns_rbt_t *rbt) {
 1060     REQUIRE(VALID_RBT(rbt));
 1061 
 1062     return (rbt->nodecount);
 1063 }
 1064 
 1065 size_t
 1066 dns_rbt_hashsize(dns_rbt_t *rbt) {
 1067     REQUIRE(VALID_RBT(rbt));
 1068 
 1069     return (1 << rbt->hashbits);
 1070 }
 1071 
 1072 isc_result_t
 1073 dns_rbt_adjusthashsize(dns_rbt_t *rbt, size_t size) {
 1074     REQUIRE(VALID_RBT(rbt));
 1075 
 1076     size_t newsize = size / RBT_HASH_BUCKETSIZE;
 1077 
 1078     rbt->maxhashbits = rehash_bits(rbt, newsize);
 1079 
 1080     maybe_rehash(rbt, newsize);
 1081 
 1082     return (ISC_R_SUCCESS);
 1083 }
 1084 
 1085 static inline isc_result_t
 1086 chain_name(dns_rbtnodechain_t *chain, dns_name_t *name,
 1087        bool include_chain_end) {
 1088     dns_name_t nodename;
 1089     isc_result_t result = ISC_R_SUCCESS;
 1090     int i;
 1091 
 1092     dns_name_init(&nodename, NULL);
 1093 
 1094     if (include_chain_end && chain->end != NULL) {
 1095         NODENAME(chain->end, &nodename);
 1096         dns_name_copynf(&nodename, name);
 1097     } else {
 1098         dns_name_reset(name);
 1099     }
 1100 
 1101     for (i = (int)chain->level_count - 1; i >= 0; i--) {
 1102         NODENAME(chain->levels[i], &nodename);
 1103         result = dns_name_concatenate(name, &nodename, name, NULL);
 1104 
 1105         if (result != ISC_R_SUCCESS) {
 1106             return (result);
 1107         }
 1108     }
 1109     return (result);
 1110 }
 1111 
 1112 static inline isc_result_t
 1113 move_chain_to_last(dns_rbtnodechain_t *chain, dns_rbtnode_t *node) {
 1114     do {
 1115         /*
 1116          * Go as far right and then down as much as possible,
 1117          * as long as the rightmost node has a down pointer.
 1118          */
 1119         while (RIGHT(node) != NULL) {
 1120             node = RIGHT(node);
 1121         }
 1122 
 1123         if (DOWN(node) == NULL) {
 1124             break;
 1125         }
 1126 
 1127         ADD_LEVEL(chain, node);
 1128         node = DOWN(node);
 1129     } while (1);
 1130 
 1131     chain->end = node;
 1132 
 1133     return (ISC_R_SUCCESS);
 1134 }
 1135 
 1136 /*
 1137  * Add 'name' to tree, initializing its data pointer with 'data'.
 1138  */
 1139 
 1140 isc_result_t
 1141 dns_rbt_addnode(dns_rbt_t *rbt, const dns_name_t *name, dns_rbtnode_t **nodep) {
 1142     /*
 1143      * Does this thing have too many variables or what?
 1144      */
 1145     dns_rbtnode_t **root, *parent, *child, *current, *new_current;
 1146     dns_name_t *add_name, *new_name, current_name, *prefix, *suffix;
 1147     dns_fixedname_t fixedcopy, fixedprefix, fixedsuffix, fnewname;
 1148     dns_offsets_t current_offsets;
 1149     dns_namereln_t compared;
 1150     isc_result_t result = ISC_R_SUCCESS;
 1151     unsigned int level_count;
 1152     unsigned int common_labels;
 1153     unsigned int nlabels, hlabels;
 1154     int order;
 1155 
 1156     REQUIRE(VALID_RBT(rbt));
 1157     REQUIRE(dns_name_isabsolute(name));
 1158     REQUIRE(nodep != NULL && *nodep == NULL);
 1159 
 1160     /*
 1161      * Dear future BIND developer,
 1162      *
 1163      * After you have tried attempting to optimize this routine by
 1164      * using the hashtable and have realized your folly, please
 1165      * append another cross ("X") below as a warning to the next
 1166      * future BIND developer:
 1167      *
 1168      * Number of victim developers: X
 1169      *
 1170      * I wish the past developer had included such a notice.
 1171      *
 1172      * Long form: Unlike dns_rbt_findnode(), this function does not
 1173      * lend itself to be optimized using the hashtable:
 1174      *
 1175      * 1. In the subtree where the insertion occurs, this function
 1176      * needs to have the insertion point and the order where the
 1177      * lookup terminated (i.e., at the insertion point where left or
 1178      * right child is NULL). This cannot be determined from the
 1179      * hashtable, so at least in that subtree, a BST O(log N) lookup
 1180      * is necessary.
 1181      *
 1182      * 2. Our RBT nodes contain not only single labels but label
 1183      * sequences to optimize space usage. So at every level, we have
 1184      * to look for a match in the hashtable for all superdomains in
 1185      * the rest of the name we're searching. This is an O(N)
 1186      * operation at least, here N being the label size of name, each
 1187      * of which is a hashtable lookup involving dns_name_equal()
 1188      * comparisons.
 1189      */
 1190 
 1191     /*
 1192      * Create a copy of the name so the original name structure is
 1193      * not modified.
 1194      */
 1195     add_name = dns_fixedname_initname(&fixedcopy);
 1196     INSIST(add_name != NULL);
 1197     dns_name_clone(name, add_name);
 1198 
 1199     if (ISC_UNLIKELY(rbt->root == NULL)) {
 1200         result = create_node(rbt->mctx, add_name, &new_current);
 1201         if (result == ISC_R_SUCCESS) {
 1202             rbt->nodecount++;
 1203             new_current->is_root = 1;
 1204 
 1205             UPPERNODE(new_current) = NULL;
 1206 
 1207             rbt->root = new_current;
 1208             *nodep = new_current;
 1209             hash_node(rbt, new_current, name);
 1210         }
 1211         return (result);
 1212     }
 1213 
 1214     level_count = 0;
 1215 
 1216     prefix = dns_fixedname_initname(&fixedprefix);
 1217     suffix = dns_fixedname_initname(&fixedsuffix);
 1218 
 1219     INSIST(prefix != NULL);
 1220     INSIST(suffix != NULL);
 1221 
 1222     root = &rbt->root;
 1223     INSIST(IS_ROOT(*root));
 1224     parent = NULL;
 1225     current = NULL;
 1226     child = *root;
 1227     dns_name_init(&current_name, current_offsets);
 1228     new_name = dns_fixedname_initname(&fnewname);
 1229     nlabels = dns_name_countlabels(name);
 1230     hlabels = 0;
 1231 
 1232     do {
 1233         current = child;
 1234 
 1235         NODENAME(current, &current_name);
 1236         compared = dns_name_fullcompare(add_name, &current_name, &order,
 1237                         &common_labels);
 1238 
 1239         if (compared == dns_namereln_equal) {
 1240             *nodep = current;
 1241             result = ISC_R_EXISTS;
 1242             break;
 1243         }
 1244 
 1245         if (compared == dns_namereln_none) {
 1246             if (order < 0) {
 1247                 parent = current;
 1248                 child = LEFT(current);
 1249             } else if (order > 0) {
 1250                 parent = current;
 1251                 child = RIGHT(current);
 1252             }
 1253         } else {
 1254             /*
 1255              * This name has some suffix in common with the
 1256              * name at the current node.  If the name at
 1257              * the current node is shorter, that means the
 1258              * new name should be in a subtree.  If the
 1259              * name at the current node is longer, that means
 1260              * the down pointer to this tree should point
 1261              * to a new tree that has the common suffix, and
 1262              * the non-common parts of these two names should
 1263              * start a new tree.
 1264              */
 1265             hlabels += common_labels;
 1266             if (compared == dns_namereln_subdomain) {
 1267                 /*
 1268                  * All of the existing labels are in common,
 1269                  * so the new name is in a subtree.
 1270                  * Whack off the common labels for the
 1271                  * not-in-common part to be searched for
 1272                  * in the next level.
 1273                  */
 1274                 dns_name_split(add_name, common_labels,
 1275                            add_name, NULL);
 1276 
 1277                 /*
 1278                  * Follow the down pointer (possibly NULL).
 1279                  */
 1280                 root = &DOWN(current);
 1281 
 1282                 INSIST(*root == NULL ||
 1283                        (IS_ROOT(*root) &&
 1284                     PARENT(*root) == current));
 1285 
 1286                 parent = NULL;
 1287                 child = DOWN(current);
 1288 
 1289                 INSIST(level_count < DNS_RBT_LEVELBLOCK);
 1290                 level_count++;
 1291             } else {
 1292                 /*
 1293                  * The number of labels in common is fewer
 1294                  * than the number of labels at the current
 1295                  * node, so the current node must be adjusted
 1296                  * to have just the common suffix, and a down
 1297                  * pointer made to a new tree.
 1298                  */
 1299 
 1300                 INSIST(compared ==
 1301                            dns_namereln_commonancestor ||
 1302                        compared == dns_namereln_contains);
 1303 
 1304                 /*
 1305                  * Ensure the number of levels in the tree
 1306                  * does not exceed the number of logical
 1307                  * levels allowed by DNSSEC.
 1308                  *
 1309                  * XXXDCL need a better error result?
 1310                  */
 1311                 if (level_count >= DNS_RBT_LEVELBLOCK) {
 1312                     result = ISC_R_NOSPACE;
 1313                     break;
 1314                 }
 1315 
 1316                 /*
 1317                  * Split the name into two parts, a prefix
 1318                  * which is the not-in-common parts of the
 1319                  * two names and a suffix that is the common
 1320                  * parts of them.
 1321                  */
 1322                 dns_name_split(&current_name, common_labels,
 1323                            prefix, suffix);
 1324                 result = create_node(rbt->mctx, suffix,
 1325                              &new_current);
 1326 
 1327                 if (result != ISC_R_SUCCESS) {
 1328                     break;
 1329                 }
 1330 
 1331                 /*
 1332                  * Reproduce the tree attributes of the
 1333                  * current node.
 1334                  */
 1335                 new_current->is_root = current->is_root;
 1336                 if (current->nsec == DNS_RBT_NSEC_HAS_NSEC) {
 1337                     new_current->nsec = DNS_RBT_NSEC_NORMAL;
 1338                 } else {
 1339                     new_current->nsec = current->nsec;
 1340                 }
 1341                 PARENT(new_current) = PARENT(current);
 1342                 LEFT(new_current) = LEFT(current);
 1343                 RIGHT(new_current) = RIGHT(current);
 1344                 COLOR(new_current) = COLOR(current);
 1345 
 1346                 /*
 1347                  * Fix pointers that were to the current node.
 1348                  */
 1349                 if (parent != NULL) {
 1350                     if (LEFT(parent) == current) {
 1351                         LEFT(parent) = new_current;
 1352                     } else {
 1353                         RIGHT(parent) = new_current;
 1354                     }
 1355                 }
 1356                 if (LEFT(new_current) != NULL) {
 1357                     PARENT(LEFT(new_current)) = new_current;
 1358                 }
 1359                 if (RIGHT(new_current) != NULL) {
 1360                     PARENT(RIGHT(new_current)) =
 1361                         new_current;
 1362                 }
 1363                 if (*root == current) {
 1364                     *root = new_current;
 1365                 }
 1366 
 1367                 NAMELEN(current) = prefix->length;
 1368                 OFFSETLEN(current) = prefix->labels;
 1369 
 1370                 /*
 1371                  * Set up the new root of the next level.
 1372                  * By definition it will not be the top
 1373                  * level tree, so clear DNS_NAMEATTR_ABSOLUTE.
 1374                  */
 1375                 current->is_root = 1;
 1376                 PARENT(current) = new_current;
 1377                 DOWN(new_current) = current;
 1378                 root = &DOWN(new_current);
 1379 
 1380                 UPPERNODE(new_current) = UPPERNODE(current);
 1381                 UPPERNODE(current) = new_current;
 1382 
 1383                 INSIST(level_count < DNS_RBT_LEVELBLOCK);
 1384                 level_count++;
 1385 
 1386                 LEFT(current) = NULL;
 1387                 RIGHT(current) = NULL;
 1388 
 1389                 MAKE_BLACK(current);
 1390                 ATTRS(current) &= ~DNS_NAMEATTR_ABSOLUTE;
 1391 
 1392                 rbt->nodecount++;
 1393                 dns_name_getlabelsequence(name,
 1394                               nlabels - hlabels,
 1395                               hlabels, new_name);
 1396                 hash_node(rbt, new_current, new_name);
 1397 
 1398                 if (common_labels ==
 1399                     dns_name_countlabels(add_name)) {
 1400                     /*
 1401                      * The name has been added by pushing
 1402                      * the not-in-common parts down to
 1403                      * a new level.
 1404                      */
 1405                     *nodep = new_current;
 1406                     return (ISC_R_SUCCESS);
 1407                 } else {
 1408                     /*
 1409                      * The current node has no data,
 1410                      * because it is just a placeholder.
 1411                      * Its data pointer is already NULL
 1412                      * from create_node()), so there's
 1413                      * nothing more to do to it.
 1414                      */
 1415 
 1416                     /*
 1417                      * The not-in-common parts of the new
 1418                      * name will be inserted into the new
 1419                      * level following this loop (unless
 1420                      * result != ISC_R_SUCCESS, which
 1421                      * is tested after the loop ends).
 1422                      */
 1423                     dns_name_split(add_name, common_labels,
 1424                                add_name, NULL);
 1425 
 1426                     break;
 1427                 }
 1428             }
 1429         }
 1430     } while (ISC_LIKELY(child != NULL));
 1431 
 1432     if (ISC_LIKELY(result == ISC_R_SUCCESS)) {
 1433         result = create_node(rbt->mctx, add_name, &new_current);
 1434     }
 1435 
 1436     if (ISC_LIKELY(result == ISC_R_SUCCESS)) {
 1437         if (*root == NULL) {
 1438             UPPERNODE(new_current) = current;
 1439         } else {
 1440             UPPERNODE(new_current) = PARENT(*root);
 1441         }
 1442 
 1443         addonlevel(new_current, current, order, root);
 1444         rbt->nodecount++;
 1445         *nodep = new_current;
 1446         hash_node(rbt, new_current, name);
 1447     }
 1448 
 1449     return (result);
 1450 }
 1451 
 1452 /*
 1453  * Add a name to the tree of trees, associating it with some data.
 1454  */
 1455 isc_result_t
 1456 dns_rbt_addname(dns_rbt_t *rbt, const dns_name_t *name, void *data) {
 1457     isc_result_t result;
 1458     dns_rbtnode_t *node;
 1459 
 1460     REQUIRE(VALID_RBT(rbt));
 1461     REQUIRE(dns_name_isabsolute(name));
 1462 
 1463     node = NULL;
 1464 
 1465     result = dns_rbt_addnode(rbt, name, &node);
 1466 
 1467     /*
 1468      * dns_rbt_addnode will report the node exists even when
 1469      * it does not have data associated with it, but the
 1470      * dns_rbt_*name functions all behave depending on whether
 1471      * there is data associated with a node.
 1472      */
 1473     if (result == ISC_R_SUCCESS ||
 1474         (result == ISC_R_EXISTS && DATA(node) == NULL)) {
 1475         DATA(node) = data;
 1476         result = ISC_R_SUCCESS;
 1477     }
 1478 
 1479     return (result);
 1480 }
 1481 
 1482 /*
 1483  * Find the node for "name" in the tree of trees.
 1484  */
 1485 isc_result_t
 1486 dns_rbt_findnode(dns_rbt_t *rbt, const dns_name_t *name, dns_name_t *foundname,
 1487          dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
 1488          unsigned int options, dns_rbtfindcallback_t callback,
 1489          void *callback_arg) {
 1490     dns_rbtnode_t *current, *last_compared;
 1491     dns_rbtnodechain_t localchain;
 1492     dns_name_t *search_name, current_name, *callback_name;
 1493     dns_fixedname_t fixedcallbackname, fixedsearchname;
 1494     dns_namereln_t compared;
 1495     isc_result_t result, saved_result;
 1496     unsigned int common_labels;
 1497     unsigned int hlabels = 0;
 1498     int order;
 1499 
 1500     REQUIRE(VALID_RBT(rbt));
 1501     REQUIRE(dns_name_isabsolute(name));
 1502     REQUIRE(node != NULL && *node == NULL);
 1503     REQUIRE((options & (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR)) !=
 1504         (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR));
 1505 
 1506     /*
 1507      * If there is a chain it needs to appear to be in a sane state,
 1508      * otherwise a chain is still needed to generate foundname and
 1509      * callback_name.
 1510      */
 1511     if (chain == NULL) {
 1512         options |= DNS_RBTFIND_NOPREDECESSOR;
 1513         chain = &localchain;
 1514         dns_rbtnodechain_init(chain);
 1515     } else {
 1516         dns_rbtnodechain_reset(chain);
 1517     }
 1518 
 1519     if (ISC_UNLIKELY(rbt->root == NULL)) {
 1520         return (ISC_R_NOTFOUND);
 1521     }
 1522 
 1523     /*
 1524      * Appease GCC about variables it incorrectly thinks are
 1525      * possibly used uninitialized.
 1526      */
 1527     compared = dns_namereln_none;
 1528     last_compared = NULL;
 1529     order = 0;
 1530 
 1531     callback_name = dns_fixedname_initname(&fixedcallbackname);
 1532 
 1533     /*
 1534      * search_name is the name segment being sought in each tree level.
 1535      * By using a fixedname, the search_name will definitely have offsets
 1536      * for use by any splitting.
 1537      * By using dns_name_clone, no name data should be copied thanks to
 1538      * the lack of bitstring labels.
 1539      */
 1540     search_name = dns_fixedname_initname(&fixedsearchname);
 1541     INSIST(search_name != NULL);
 1542     dns_name_clone(name, search_name);
 1543 
 1544     dns_name_init(&current_name, NULL);
 1545 
 1546     saved_result = ISC_R_SUCCESS;
 1547     current = rbt->root;
 1548 
 1549     while (ISC_LIKELY(current != NULL)) {
 1550         NODENAME(current, &current_name);
 1551         compared = dns_name_fullcompare(search_name, &current_name,
 1552                         &order, &common_labels);
 1553         /*
 1554          * last_compared is used as a shortcut to start (or
 1555          * continue rather) finding the stop-node of the search
 1556          * when hashing was used (see much below in this
 1557          * function).
 1558          */
 1559         last_compared = current;
 1560 
 1561         if (compared == dns_namereln_equal) {
 1562             break;
 1563         }
 1564 
 1565         if (compared == dns_namereln_none) {
 1566             /*
 1567              * Here, current is pointing at a subtree root
 1568              * node. We try to find a matching node using
 1569              * the hashtable. We can get one of 3 results
 1570              * here: (a) we locate the matching node, (b) we
 1571              * find a node to which the current node has a
 1572              * subdomain relation, (c) we fail to find (a)
 1573              * or (b).
 1574              */
 1575 
 1576             dns_name_t hash_name;
 1577             dns_rbtnode_t *hnode;
 1578             dns_rbtnode_t *up_current;
 1579             unsigned int nlabels;
 1580             unsigned int tlabels = 1;
 1581             uint32_t hash;
 1582 
 1583             /*
 1584              * The case of current not being a subtree root,
 1585              * that means a left or right pointer was
 1586              * followed, only happens when the algorithm
 1587              * fell through to the traditional binary search
 1588              * because of a bitstring label.  Since we
 1589              * dropped the bitstring support, this should
 1590              * not happen.
 1591              */
 1592             INSIST(IS_ROOT(current));
 1593 
 1594             nlabels = dns_name_countlabels(search_name);
 1595 
 1596             /*
 1597              * current is the root of the current level, so
 1598              * its parent is the same as its "up" pointer.
 1599              */
 1600             up_current = PARENT(current);
 1601             dns_name_init(&hash_name, NULL);
 1602 
 1603         hashagain:
 1604             /*
 1605              * Compute the hash over the full absolute
 1606              * name. Look for the smallest suffix match at
 1607              * this tree level (hlevel), and then at every
 1608              * iteration, look for the next smallest suffix
 1609              * match (add another subdomain label to the
 1610              * absolute name being hashed).
 1611              */
 1612             dns_name_getlabelsequence(name, nlabels - tlabels,
 1613                           hlabels + tlabels,
 1614                           &hash_name);
 1615             hash = dns_name_fullhash(&hash_name, false);
 1616             dns_name_getlabelsequence(search_name,
 1617                           nlabels - tlabels, tlabels,
 1618                           &hash_name);
 1619 
 1620             /*
 1621              * Walk all the nodes in the hash bucket pointed
 1622              * by the computed hash value.
 1623              */
 1624             for (hnode = rbt->hashtable[hash_32(hash,
 1625                                 rbt->hashbits)];
 1626                  hnode != NULL; hnode = hnode->hashnext)
 1627             {
 1628                 dns_name_t hnode_name;
 1629 
 1630                 if (ISC_LIKELY(hash != HASHVAL(hnode))) {
 1631                     continue;
 1632                 }
 1633                 /*
 1634                  * This checks that the hashed label
 1635                  * sequence being looked up is at the
 1636                  * same tree level, so that we don't
 1637                  * match a labelsequence from some other
 1638                  * subdomain.
 1639                  */
 1640                 if (ISC_LIKELY(get_upper_node(hnode) !=
 1641                            up_current)) {
 1642                     continue;
 1643                 }
 1644 
 1645                 dns_name_init(&hnode_name, NULL);
 1646                 NODENAME(hnode, &hnode_name);
 1647                 if (ISC_LIKELY(dns_name_equal(&hnode_name,
 1648                                   &hash_name))) {
 1649                     break;
 1650                 }
 1651             }
 1652 
 1653             if (hnode != NULL) {
 1654                 current = hnode;
 1655                 /*
 1656                  * This is an optimization.  If hashing found
 1657                  * the right node, the next call to
 1658                  * dns_name_fullcompare() would obviously
 1659                  * return _equal or _subdomain.  Determine
 1660                  * which of those would be the case by
 1661                  * checking if the full name was hashed.  Then
 1662                  * make it look like dns_name_fullcompare
 1663                  * was called and jump to the right place.
 1664                  */
 1665                 if (tlabels == nlabels) {
 1666                     compared = dns_namereln_equal;
 1667                     break;
 1668                 } else {
 1669                     common_labels = tlabels;
 1670                     compared = dns_namereln_subdomain;
 1671                     goto subdomain;
 1672                 }
 1673             }
 1674 
 1675             if (tlabels++ < nlabels) {
 1676                 goto hashagain;
 1677             }
 1678 
 1679             /*
 1680              * All of the labels have been tried against the hash
 1681              * table.  Since we dropped the support of bitstring
 1682              * labels, the name isn't in the table.
 1683              */
 1684             current = NULL;
 1685             continue;
 1686         } else {
 1687             /*
 1688              * The names have some common suffix labels.
 1689              *
 1690              * If the number in common are equal in length to
 1691              * the current node's name length, then follow the
 1692              * down pointer and search in the new tree.
 1693              */
 1694             if (compared == dns_namereln_subdomain) {
 1695             subdomain:
 1696                 /*
 1697                  * Whack off the current node's common parts
 1698                  * for the name to search in the next level.
 1699                  */
 1700                 dns_name_split(search_name, common_labels,
 1701                            search_name, NULL);
 1702                 hlabels += common_labels;
 1703                 /*
 1704                  * This might be the closest enclosing name.
 1705                  */
 1706                 if ((options & DNS_RBTFIND_EMPTYDATA) != 0 ||
 1707                     DATA(current) != NULL) {
 1708                     *node = current;
 1709                 }
 1710 
 1711                 /*
 1712                  * Point the chain to the next level.   This
 1713                  * needs to be done before 'current' is pointed
 1714                  * there because the callback in the next
 1715                  * block of code needs the current 'current',
 1716                  * but in the event the callback requests that
 1717                  * the search be stopped then the
 1718                  * DNS_R_PARTIALMATCH code at the end of this
 1719                  * function needs the chain pointed to the
 1720                  * next level.
 1721                  */
 1722                 ADD_LEVEL(chain, current);
 1723 
 1724                 /*
 1725                  * The caller may want to interrupt the
 1726                  * downward search when certain special nodes
 1727                  * are traversed.  If this is a special node,
 1728                  * the callback is used to learn what the
 1729                  * caller wants to do.
 1730                  */
 1731                 if (callback != NULL && FINDCALLBACK(current)) {
 1732                     result = chain_name(
 1733                         chain, callback_name, false);
 1734                     if (result != ISC_R_SUCCESS) {
 1735                         dns_rbtnodechain_reset(chain);
 1736                         return (result);
 1737                     }
 1738 
 1739                     result = (callback)(current,
 1740                                 callback_name,
 1741                                 callback_arg);
 1742                     if (result != DNS_R_CONTINUE) {
 1743                         saved_result = result;
 1744                         /*
 1745                          * Treat this node as if it
 1746                          * had no down pointer.
 1747                          */
 1748                         current = NULL;
 1749                         break;
 1750                     }
 1751                 }
 1752 
 1753                 /*
 1754                  * Finally, head to the next tree level.
 1755                  */
 1756                 current = DOWN(current);
 1757             } else {
 1758                 /*
 1759                  * Though there are labels in common, the
 1760                  * entire name at this node is not common
 1761                  * with the search name so the search
 1762                  * name does not exist in the tree.
 1763                  */
 1764                 INSIST(compared ==
 1765                            dns_namereln_commonancestor ||
 1766                        compared == dns_namereln_contains);
 1767 
 1768                 current = NULL;
 1769             }
 1770         }
 1771     }
 1772 
 1773     /*
 1774      * If current is not NULL, NOEXACT is not disallowing exact matches,
 1775      * and either the node has data or an empty node is ok, return
 1776      * ISC_R_SUCCESS to indicate an exact match.
 1777      */
 1778     if (current != NULL && (options & DNS_RBTFIND_NOEXACT) == 0 &&
 1779         ((options & DNS_RBTFIND_EMPTYDATA) != 0 || DATA(current) != NULL))
 1780     {
 1781         /*
 1782          * Found an exact match.
 1783          */
 1784         chain->end = current;
 1785         chain->level_matches = chain->level_count;
 1786 
 1787         if (foundname != NULL) {
 1788             result = chain_name(chain, foundname, true);
 1789         } else {
 1790             result = ISC_R_SUCCESS;
 1791         }
 1792 
 1793         if (result == ISC_R_SUCCESS) {
 1794             *node = current;
 1795             result = saved_result;
 1796         } else {
 1797             *node = NULL;
 1798         }
 1799     } else {
 1800         /*
 1801          * Did not find an exact match (or did not want one).
 1802          */
 1803         if (*node != NULL) {
 1804             /*
 1805              * ... but found a partially matching superdomain.
 1806              * Unwind the chain to the partial match node
 1807              * to set level_matches to the level above the node,
 1808              * and then to derive the name.
 1809              *
 1810              * chain->level_count is guaranteed to be at least 1
 1811              * here because by definition of finding a superdomain,
 1812              * the chain is pointed to at least the first subtree.
 1813              */
 1814             chain->level_matches = chain->level_count - 1;
 1815 
 1816             while (chain->levels[chain->level_matches] != *node) {
 1817                 INSIST(chain->level_matches > 0);
 1818                 chain->level_matches--;
 1819             }
 1820 
 1821             if (foundname != NULL) {
 1822                 unsigned int saved_count = chain->level_count;
 1823 
 1824                 chain->level_count = chain->level_matches + 1;
 1825 
 1826                 result = chain_name(chain, foundname, false);
 1827 
 1828                 chain->level_count = saved_count;
 1829             } else {
 1830                 result = ISC_R_SUCCESS;
 1831             }
 1832 
 1833             if (result == ISC_R_SUCCESS) {
 1834                 result = DNS_R_PARTIALMATCH;
 1835             }
 1836         } else {
 1837             result = ISC_R_NOTFOUND;
 1838         }
 1839 
 1840         if (current != NULL) {
 1841             /*
 1842              * There was an exact match but either
 1843              * DNS_RBTFIND_NOEXACT was set, or
 1844              * DNS_RBTFIND_EMPTYDATA was set and the node had no
 1845              * data.  A policy decision was made to set the
 1846              * chain to the exact match, but this is subject
 1847              * to change if it becomes apparent that something
 1848              * else would be more useful.  It is important that
 1849              * this case is handled here, because the predecessor
 1850              * setting code below assumes the match was not exact.
 1851              */
 1852             INSIST(((options & DNS_RBTFIND_NOEXACT) != 0) ||
 1853                    ((options & DNS_RBTFIND_EMPTYDATA) == 0 &&
 1854                 DATA(current) == NULL));
 1855             chain->end = current;
 1856         } else if ((options & DNS_RBTFIND_NOPREDECESSOR) != 0) {
 1857             /*
 1858              * Ensure the chain points nowhere.
 1859              */
 1860             chain->end = NULL;
 1861         } else {
 1862             /*
 1863              * Since there was no exact match, the chain argument
 1864              * needs to be pointed at the DNSSEC predecessor of
 1865              * the search name.
 1866              */
 1867             if (compared == dns_namereln_subdomain) {
 1868                 /*
 1869                  * Attempted to follow a down pointer that was
 1870                  * NULL, which means the searched for name was
 1871                  * a subdomain of a terminal name in the tree.
 1872                  * Since there are no existing subdomains to
 1873                  * order against, the terminal name is the
 1874                  * predecessor.
 1875                  */
 1876                 INSIST(chain->level_count > 0);
 1877                 INSIST(chain->level_matches <
 1878                        chain->level_count);
 1879                 chain->end =
 1880                     chain->levels[--chain->level_count];
 1881             } else {
 1882                 isc_result_t result2;
 1883 
 1884                 /*
 1885                  * Point current to the node that stopped
 1886                  * the search.
 1887                  *
 1888                  * With the hashing modification that has been
 1889                  * added to the algorithm, the stop node of a
 1890                  * standard binary search is not known.  So it
 1891                  * has to be found.  There is probably a more
 1892                  * clever way of doing this.
 1893                  *
 1894                  * The assignment of current to NULL when
 1895                  * the relationship is *not* dns_namereln_none,
 1896                  * even though it later gets set to the same
 1897                  * last_compared anyway, is simply to not push
 1898                  * the while loop in one more level of
 1899                  * indentation.
 1900                  */
 1901                 if (compared == dns_namereln_none) {
 1902                     current = last_compared;
 1903                 } else {
 1904                     current = NULL;
 1905                 }
 1906 
 1907                 while (current != NULL) {
 1908                     NODENAME(current, &current_name);
 1909                     compared = dns_name_fullcompare(
 1910                         search_name, &current_name,
 1911                         &order, &common_labels);
 1912                     POST(compared);
 1913 
 1914                     last_compared = current;
 1915 
 1916                     /*
 1917                      * Standard binary search movement.
 1918                      */
 1919                     if (order < 0) {
 1920                         current = LEFT(current);
 1921                     } else {
 1922                         current = RIGHT(current);
 1923                     }
 1924                 }
 1925 
 1926                 current = last_compared;
 1927 
 1928                 /*
 1929                  * Reached a point within a level tree that
 1930                  * positively indicates the name is not
 1931                  * present, but the stop node could be either
 1932                  * less than the desired name (order > 0) or
 1933                  * greater than the desired name (order < 0).
 1934                  *
 1935                  * If the stop node is less, it is not
 1936                  * necessarily the predecessor.  If the stop
 1937                  * node has a down pointer, then the real
 1938                  * predecessor is at the end of a level below
 1939                  * (not necessarily the next level).
 1940                  * Move down levels until the rightmost node
 1941                  * does not have a down pointer.
 1942                  *
 1943                  * When the stop node is greater, it is
 1944                  * the successor.  All the logic for finding
 1945                  * the predecessor is handily encapsulated
 1946                  * in dns_rbtnodechain_prev.  In the event
 1947                  * that the search name is less than anything
 1948                  * else in the tree, the chain is reset.
 1949                  * XXX DCL What is the best way for the caller
 1950                  *         to know that the search name has
 1951                  *         no predecessor?
 1952                  */
 1953 
 1954                 if (order > 0) {
 1955                     if (DOWN(current) != NULL) {
 1956                         ADD_LEVEL(chain, current);
 1957 
 1958                         result2 = move_chain_to_last(
 1959                             chain, DOWN(current));
 1960 
 1961                         if (result2 != ISC_R_SUCCESS) {
 1962                             result = result2;
 1963                         }
 1964                     } else {
 1965                         /*
 1966                          * Ah, the pure and simple
 1967                          * case.  The stop node is the
 1968                          * predecessor.
 1969                          */
 1970                         chain->end = current;
 1971                     }
 1972                 } else {
 1973                     INSIST(order < 0);
 1974 
 1975                     chain->end = current;
 1976 
 1977                     result2 = dns_rbtnodechain_prev(
 1978                         chain, NULL, NULL);
 1979                     if (result2 == ISC_R_SUCCESS ||
 1980                         result2 == DNS_R_NEWORIGIN) {
 1981                         /* Nothing. */
 1982                     } else if (result2 == ISC_R_NOMORE) {
 1983                         /*
 1984                          * There is no predecessor.
 1985                          */
 1986                         dns_rbtnodechain_reset(chain);
 1987                     } else {
 1988                         result = result2;
 1989                     }
 1990                 }
 1991             }
 1992         }
 1993     }
 1994 
 1995     ENSURE(*node == NULL || DNS_RBTNODE_VALID(*node));
 1996 
 1997     return (result);
 1998 }
 1999 
 2000 /*
 2001  * Get the data pointer associated with 'name'.
 2002  */
 2003 isc_result_t
 2004 dns_rbt_findname(dns_rbt_t *rbt, const dns_name_t *name, unsigned int options,
 2005          dns_name_t *foundname, void **data) {
 2006     dns_rbtnode_t *node = NULL;
 2007     isc_result_t result;
 2008 
 2009     REQUIRE(data != NULL && *data == NULL);
 2010 
 2011     result = dns_rbt_findnode(rbt, name, foundname, &node, NULL, options,
 2012                   NULL, NULL);
 2013 
 2014     if (node != NULL &&
 2015         (DATA(node) != NULL || (options & DNS_RBTFIND_EMPTYDATA) != 0))
 2016     {
 2017         *data = DATA(node);
 2018     } else {
 2019         result = ISC_R_NOTFOUND;
 2020     }
 2021 
 2022     return (result);
 2023 }
 2024 
 2025 /*
 2026  * Delete a name from the tree of trees.
 2027  */
 2028 isc_result_t
 2029 dns_rbt_deletename(dns_rbt_t *rbt, const dns_name_t *name, bool recurse) {
 2030     dns_rbtnode_t *node = NULL;
 2031     isc_result_t result;
 2032 
 2033     REQUIRE(VALID_RBT(rbt));
 2034     REQUIRE(dns_name_isabsolute(name));
 2035 
 2036     /*
 2037      * First, find the node.
 2038      *
 2039      * When searching, the name might not have an exact match:
 2040      * consider a.b.a.com, b.b.a.com and c.b.a.com as the only
 2041      * elements of a tree, which would make layer 1 a single
 2042      * node tree of "b.a.com" and layer 2 a three node tree of
 2043      * a, b, and c.  Deleting a.com would find only a partial depth
 2044      * match in the first layer.  Should it be a requirement that
 2045      * that the name to be deleted have data?  For now, it is.
 2046      *
 2047      * ->dirty, ->locknum and ->references are ignored; they are
 2048      * solely the province of rbtdb.c.
 2049      */
 2050     result = dns_rbt_findnode(rbt, name, NULL, &node, NULL,
 2051                   DNS_RBTFIND_NOOPTIONS, NULL, NULL);
 2052 
 2053     if (result == ISC_R_SUCCESS) {
 2054         if (DATA(node) != NULL) {
 2055             result = dns_rbt_deletenode(rbt, node, recurse);
 2056         } else {
 2057             result = ISC_R_NOTFOUND;
 2058         }
 2059     } else if (result == DNS_R_PARTIALMATCH) {
 2060         result = ISC_R_NOTFOUND;
 2061     }
 2062 
 2063     return (result);
 2064 }
 2065 
 2066 /*
 2067  * Remove a node from the tree of trees.
 2068  *
 2069  * NOTE WELL: deletion is *not* symmetric with addition; that is, reversing
 2070  * a sequence of additions to be deletions will not generally get the
 2071  * tree back to the state it started in.  For example, if the addition
 2072  * of "b.c" caused the node "a.b.c" to be split, pushing "a" to its own level,
 2073  * then the subsequent deletion of "b.c" will not cause "a" to be pulled up,
 2074  * restoring "a.b.c".  The RBT *used* to do this kind of rejoining, but it
 2075  * turned out to be a bad idea because it could corrupt an active nodechain
 2076  * that had "b.c" as one of its levels -- and the RBT has no idea what
 2077  * nodechains are in use by callers, so it can't even *try* to helpfully
 2078  * fix them up (which would probably be doomed to failure anyway).
 2079  *
 2080  * Similarly, it is possible to leave the tree in a state where a supposedly
 2081  * deleted node still exists.  The first case of this is obvious; take
 2082  * the tree which has "b.c" on one level, pointing to "a".  Now deleted "b.c".
 2083  * It was just established in the previous paragraph why we can't pull "a"
 2084  * back up to its parent level.  But what happens when "a" then gets deleted?
 2085  * "b.c" is left hanging around without data or children.  This condition
 2086  * is actually pretty easy to detect, but ... should it really be removed?
 2087  * Is a chain pointing to it?  An iterator?  Who knows!  (Note that the
 2088  * references structure member cannot be looked at because it is private to
 2089  * rbtdb.)  This is ugly and makes me unhappy, but after hours of trying to
 2090  * make it more aesthetically proper and getting nowhere, this is the way it
 2091  * is going to stay until such time as it proves to be a *real* problem.
 2092  *
 2093  * Finally, for reference, note that the original routine that did node
 2094  * joining was called join_nodes().  It has been excised, living now only
 2095  * in the CVS history, but comments have been left behind that point to it just
 2096  * in case someone wants to muck with this some more.
 2097  *
 2098  * The one positive aspect of all of this is that joining used to have a
 2099  * case where it might fail.  Without trying to join, now this function always
 2100  * succeeds. It still returns isc_result_t, though, so the API wouldn't change.
 2101  */
 2102 isc_result_t
 2103 dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, bool recurse) {
 2104     dns_rbtnode_t *parent;
 2105 
 2106     REQUIRE(VALID_RBT(rbt));
 2107     REQUIRE(DNS_RBTNODE_VALID(node));
 2108     INSIST(rbt->nodecount != 0);
 2109 
 2110     if (DOWN(node) != NULL) {
 2111         if (recurse) {
 2112             PARENT(DOWN(node)) = NULL;
 2113             deletetreeflat(rbt, 0, true, &DOWN(node));
 2114         } else {
 2115             if (DATA(node) != NULL && rbt->data_deleter != NULL) {
 2116                 rbt->data_deleter(DATA(node), rbt->deleter_arg);
 2117             }
 2118             DATA(node) = NULL;
 2119 
 2120             /*
 2121              * Since there is at least one node below this one and
 2122              * no recursion was requested, the deletion is
 2123              * complete.  The down node from this node might be all
 2124              * by itself on a single level, so join_nodes() could
 2125              * be used to collapse the tree (with all the caveats
 2126              * of the comment at the start of this function).
 2127              * But join_nodes() function has now been removed.
 2128              */
 2129             return (ISC_R_SUCCESS);
 2130         }
 2131     }
 2132 
 2133     /*
 2134      * Note the node that points to the level of the node
 2135      * that is being deleted.  If the deleted node is the
 2136      * top level, parent will be set to NULL.
 2137      */
 2138     parent = get_upper_node(node);
 2139 
 2140     /*
 2141      * This node now has no down pointer, so now it needs
 2142      * to be removed from this level.
 2143      */
 2144     deletefromlevel(node, parent == NULL ? &rbt->root : &DOWN(parent));
 2145 
 2146     if (DATA(node) != NULL && rbt->data_deleter != NULL) {
 2147         rbt->data_deleter(DATA(node), rbt->deleter_arg);
 2148     }
 2149 
 2150     unhash_node(rbt, node);
 2151 #if DNS_RBT_USEMAGIC
 2152     node->magic = 0;
 2153 #endif /* if DNS_RBT_USEMAGIC */
 2154     isc_refcount_destroy(&node->references);
 2155 
 2156     freenode(rbt, &node);
 2157 
 2158     /*
 2159      * This function never fails.
 2160      */
 2161     return (ISC_R_SUCCESS);
 2162 }
 2163 
 2164 void
 2165 dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name) {
 2166     REQUIRE(DNS_RBTNODE_VALID(node));
 2167     REQUIRE(name != NULL);
 2168     REQUIRE(name->offsets == NULL);
 2169 
 2170     NODENAME(node, name);
 2171 }
 2172 
 2173 isc_result_t
 2174 dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name) {
 2175     dns_name_t current;
 2176     isc_result_t result;
 2177 
 2178     REQUIRE(DNS_RBTNODE_VALID(node));
 2179     REQUIRE(name != NULL);
 2180     REQUIRE(name->buffer != NULL);
 2181 
 2182     dns_name_init(&current, NULL);
 2183     dns_name_reset(name);
 2184 
 2185     do {
 2186         INSIST(node != NULL);
 2187 
 2188         NODENAME(node, &current);
 2189 
 2190         result = dns_name_concatenate(name, &current, name, NULL);
 2191         if (result != ISC_R_SUCCESS) {
 2192             break;
 2193         }
 2194 
 2195         node = get_upper_node(node);
 2196     } while (!dns_name_isabsolute(name));
 2197 
 2198     return (result);
 2199 }
 2200 
 2201 char *
 2202 dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname,
 2203                unsigned int size) {
 2204     dns_fixedname_t fixedname;
 2205     dns_name_t *name;
 2206     isc_result_t result;
 2207 
 2208     REQUIRE(DNS_RBTNODE_VALID(node));
 2209     REQUIRE(printname != NULL);
 2210 
 2211     name = dns_fixedname_initname(&fixedname);
 2212     result = dns_rbt_fullnamefromnode(node, name);
 2213     if (result == ISC_R_SUCCESS) {
 2214         dns_name_format(name, printname, size);
 2215     } else {
 2216         snprintf(printname, size, "<error building name: %s>",
 2217              dns_result_totext(result));
 2218     }
 2219 
 2220     return (printname);
 2221 }
 2222 
 2223 static isc_result_t
 2224 create_node(isc_mem_t *mctx, const dns_name_t *name, dns_rbtnode_t **nodep) {
 2225     dns_rbtnode_t *node;
 2226     isc_region_t region;
 2227     unsigned int labels;
 2228     size_t nodelen;
 2229 
 2230     REQUIRE(name->offsets != NULL);
 2231 
 2232     dns_name_toregion(name, &region);
 2233     labels = dns_name_countlabels(name);
 2234     ENSURE(labels > 0);
 2235 
 2236     /*
 2237      * Allocate space for the node structure, the name, and the offsets.
 2238      */
 2239     nodelen = sizeof(dns_rbtnode_t) + region.length + labels + 1;
 2240     node = isc_mem_get(mctx, nodelen);
 2241     memset(node, 0, nodelen);
 2242 
 2243     node->is_root = 0;
 2244     PARENT(node) = NULL;
 2245     RIGHT(node) = NULL;
 2246     LEFT(node) = NULL;
 2247     DOWN(node) = NULL;
 2248     DATA(node) = NULL;
 2249     node->is_mmapped = 0;
 2250     node->down_is_relative = 0;
 2251     node->left_is_relative = 0;
 2252     node->right_is_relative = 0;
 2253     node->parent_is_relative = 0;
 2254     node->data_is_relative = 0;
 2255     node->rpz = 0;
 2256 
 2257     HASHNEXT(node) = NULL;
 2258     HASHVAL(node) = 0;
 2259 
 2260     ISC_LINK_INIT(node, deadlink);
 2261 
 2262     LOCKNUM(node) = 0;
 2263     WILD(node) = 0;
 2264     DIRTY(node) = 0;
 2265     isc_refcount_init(&node->references, 0);
 2266     node->find_callback = 0;
 2267     node->nsec = DNS_RBT_NSEC_NORMAL;
 2268 
 2269     MAKE_BLACK(node);
 2270 
 2271     /*
 2272      * The following is stored to make reconstructing a name from the
 2273      * stored value in the node easy:  the length of the name, the number
 2274      * of labels, whether the name is absolute or not, the name itself,
 2275      * and the name's offsets table.
 2276      *
 2277      * XXX RTH
 2278      *      The offsets table could be made smaller by eliminating the
 2279      *      first offset, which is always 0.  This requires changes to
 2280      *      lib/dns/name.c.
 2281      *
 2282      * Note: OLDOFFSETLEN *must* be assigned *after* OLDNAMELEN is assigned
 2283      *   as it uses OLDNAMELEN.
 2284      */
 2285     OLDNAMELEN(node) = NAMELEN(node) = region.length;
 2286     OLDOFFSETLEN(node) = OFFSETLEN(node) = labels;
 2287     ATTRS(node) = name->attributes;
 2288 
 2289     memmove(NAME(node), region.base, region.length);
 2290     memmove(OFFSETS(node), name->offsets, labels);
 2291 
 2292 #if DNS_RBT_USEMAGIC
 2293     node->magic = DNS_RBTNODE_MAGIC;
 2294 #endif /* if DNS_RBT_USEMAGIC */
 2295     *nodep = node;
 2296 
 2297     return (ISC_R_SUCCESS);
 2298 }
 2299 
 2300 /*
 2301  * Add a node to the hash table
 2302  */
 2303 static inline void
 2304 hash_add_node(dns_rbt_t *rbt, dns_rbtnode_t *node, const dns_name_t *name) {
 2305     uint32_t hash;
 2306 
 2307     REQUIRE(name != NULL);
 2308 
 2309     HASHVAL(node) = dns_name_fullhash(name, false);
 2310 
 2311     hash = hash_32(HASHVAL(node), rbt->hashbits);
 2312     HASHNEXT(node) = rbt->hashtable[hash];
 2313 
 2314     rbt->hashtable[hash] = node;
 2315 }
 2316 
 2317 /*
 2318  * Initialize hash table
 2319  */
 2320 static isc_result_t
 2321 inithash(dns_rbt_t *rbt) {
 2322     size_t size;
 2323 
 2324     rbt->hashbits = RBT_HASH_MIN_BITS;
 2325     size = HASHSIZE(rbt->hashbits) * sizeof(dns_rbtnode_t *);
 2326     rbt->hashtable = isc_mem_get(rbt->mctx, size);
 2327     memset(rbt->hashtable, 0, size);
 2328 
 2329     return (ISC_R_SUCCESS);
 2330 }
 2331 
 2332 static uint32_t
 2333 rehash_bits(dns_rbt_t *rbt, size_t newcount) {
 2334     uint32_t newbits = rbt->hashbits;
 2335 
 2336     while (newcount >= HASHSIZE(newbits) && newbits < rbt->maxhashbits) {
 2337         newbits += 1;
 2338     }
 2339 
 2340     return (newbits);
 2341 }
 2342 
 2343 /*
 2344  * Rebuild the hashtable to reduce the load factor
 2345  */
 2346 static void
 2347 rehash(dns_rbt_t *rbt, uint32_t newbits) {
 2348     uint32_t oldbits;
 2349     size_t oldsize;
 2350     dns_rbtnode_t **oldtable;
 2351     size_t newsize;
 2352 
 2353     REQUIRE(rbt->hashbits <= rbt->maxhashbits);
 2354     REQUIRE(newbits <= rbt->maxhashbits);
 2355 
 2356     oldbits = rbt->hashbits;
 2357     oldsize = HASHSIZE(oldbits);
 2358     oldtable = rbt->hashtable;
 2359 
 2360     rbt->hashbits = newbits;
 2361     newsize = HASHSIZE(rbt->hashbits);
 2362     rbt->hashtable = isc_mem_get(rbt->mctx,
 2363                      newsize * sizeof(dns_rbtnode_t *));
 2364     memset(rbt->hashtable, 0, newsize * sizeof(dns_rbtnode_t *));
 2365 
 2366     for (size_t i = 0; i < oldsize; i++) {
 2367         dns_rbtnode_t *node;
 2368         dns_rbtnode_t *nextnode;
 2369         for (node = oldtable[i]; node != NULL; node = nextnode) {
 2370             uint32_t hash = hash_32(HASHVAL(node), rbt->hashbits);
 2371             nextnode = HASHNEXT(node);
 2372             HASHNEXT(node) = rbt->hashtable[hash];
 2373             rbt->hashtable[hash] = node;
 2374         }
 2375     }
 2376 
 2377     isc_mem_put(rbt->mctx, oldtable, oldsize * sizeof(dns_rbtnode_t *));
 2378 }
 2379 
 2380 static void
 2381 maybe_rehash(dns_rbt_t *rbt, size_t newcount) {
 2382     uint32_t newbits = rehash_bits(rbt, newcount);
 2383     if (rbt->hashbits < newbits && newbits <= rbt->maxhashbits) {
 2384         rehash(rbt, newbits);
 2385     }
 2386 }
 2387 
 2388 /*
 2389  * Add a node to the hash table. Rehash the hashtable if the node count
 2390  * rises above a critical level.
 2391  */
 2392 static inline void
 2393 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, const dns_name_t *name) {
 2394     REQUIRE(DNS_RBTNODE_VALID(node));
 2395 
 2396     if (rbt->nodecount >= (HASHSIZE(rbt->hashbits) * RBT_HASH_OVERCOMMIT)) {
 2397         maybe_rehash(rbt, rbt->nodecount);
 2398     }
 2399 
 2400     hash_add_node(rbt, node, name);
 2401 }
 2402 
 2403 /*
 2404  * Remove a node from the hash table
 2405  */
 2406 static inline void
 2407 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node) {
 2408     uint32_t bucket;
 2409     dns_rbtnode_t *bucket_node;
 2410 
 2411     REQUIRE(DNS_RBTNODE_VALID(node));
 2412 
 2413     bucket = hash_32(HASHVAL(node), rbt->hashbits);
 2414     bucket_node = rbt->hashtable[bucket];
 2415 
 2416     if (bucket_node == node) {
 2417         rbt->hashtable[bucket] = HASHNEXT(node);
 2418     } else {
 2419         while (HASHNEXT(bucket_node) != node) {
 2420             INSIST(HASHNEXT(bucket_node) != NULL);
 2421             bucket_node = HASHNEXT(bucket_node);
 2422         }
 2423         HASHNEXT(bucket_node) = HASHNEXT(node);
 2424     }
 2425 }
 2426 
 2427 static inline void
 2428 rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
 2429     dns_rbtnode_t *child;
 2430 
 2431     REQUIRE(DNS_RBTNODE_VALID(node));
 2432     REQUIRE(rootp != NULL);
 2433 
 2434     child = RIGHT(node);
 2435     INSIST(child != NULL);
 2436 
 2437     RIGHT(node) = LEFT(child);
 2438     if (LEFT(child) != NULL) {
 2439         PARENT(LEFT(child)) = node;
 2440     }
 2441     LEFT(child) = node;
 2442 
 2443     PARENT(child) = PARENT(node);
 2444 
 2445     if (IS_ROOT(node)) {
 2446         *rootp = child;
 2447         child->is_root = 1;
 2448         node->is_root = 0;
 2449     } else {
 2450         if (LEFT(PARENT(node)) == node) {
 2451             LEFT(PARENT(node)) = child;
 2452         } else {
 2453             RIGHT(PARENT(node)) = child;
 2454         }
 2455     }
 2456 
 2457     PARENT(node) = child;
 2458 }
 2459 
 2460 static inline void
 2461 rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
 2462     dns_rbtnode_t *child;
 2463 
 2464     REQUIRE(DNS_RBTNODE_VALID(node));
 2465     REQUIRE(rootp != NULL);
 2466 
 2467     child = LEFT(node);
 2468     INSIST(child != NULL);
 2469 
 2470     LEFT(node) = RIGHT(child);
 2471     if (RIGHT(child) != NULL) {
 2472         PARENT(RIGHT(child)) = node;
 2473     }
 2474     RIGHT(child) = node;
 2475 
 2476     PARENT(child) = PARENT(node);
 2477 
 2478     if (IS_ROOT(node)) {
 2479         *rootp = child;
 2480         child->is_root = 1;
 2481         node->is_root = 0;
 2482     } else {
 2483         if (LEFT(PARENT(node)) == node) {
 2484             LEFT(PARENT(node)) = child;
 2485         } else {
 2486             RIGHT(PARENT(node)) = child;
 2487         }
 2488     }
 2489 
 2490     PARENT(node) = child;
 2491 }
 2492 
 2493 /*
 2494  * This is the real workhorse of the insertion code, because it does the
 2495  * true red/black tree on a single level.
 2496  */
 2497 static void
 2498 addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
 2499        dns_rbtnode_t **rootp) {
 2500     dns_rbtnode_t *child, *root, *parent, *grandparent;
 2501     dns_name_t add_name, current_name;
 2502     dns_offsets_t add_offsets, current_offsets;
 2503 
 2504     REQUIRE(rootp != NULL);
 2505     REQUIRE(DNS_RBTNODE_VALID(node) && LEFT(node) == NULL &&
 2506         RIGHT(node) == NULL);
 2507     REQUIRE(current != NULL);
 2508 
 2509     root = *rootp;
 2510     if (root == NULL) {
 2511         /*
 2512          * First node of a level.
 2513          */
 2514         MAKE_BLACK(node);
 2515         node->is_root = 1;
 2516         PARENT(node) = current;
 2517         *rootp = node;
 2518         return;
 2519     }
 2520 
 2521     child = root;
 2522     POST(child);
 2523 
 2524     dns_name_init(&add_name, add_offsets);
 2525     NODENAME(node, &add_name);
 2526 
 2527     dns_name_init(&current_name, current_offsets);
 2528     NODENAME(current, &current_name);
 2529 
 2530     if (order < 0) {
 2531         INSIST(LEFT(current) == NULL);
 2532         LEFT(current) = node;
 2533     } else {
 2534         INSIST(RIGHT(current) == NULL);
 2535         RIGHT(current) = node;
 2536     }
 2537 
 2538     INSIST(PARENT(node) == NULL);
 2539     PARENT(node) = current;
 2540 
 2541     MAKE_RED(node);
 2542 
 2543     while (node != root && IS_RED(PARENT(node))) {
 2544         /*
 2545          * XXXDCL could do away with separate parent and grandparent
 2546          * variables.  They are vestiges of the days before parent
 2547          * pointers.  However, they make the code a little clearer.
 2548          */
 2549 
 2550         parent = PARENT(node);
 2551         grandparent = PARENT(parent);
 2552 
 2553         if (parent == LEFT(grandparent)) {
 2554             child = RIGHT(grandparent);
 2555             if (child != NULL && IS_RED(child)) {
 2556                 MAKE_BLACK(parent);
 2557                 MAKE_BLACK(child);
 2558                 MAKE_RED(grandparent);
 2559                 node = grandparent;
 2560             } else {
 2561                 if (node == RIGHT(parent)) {
 2562                     rotate_left(parent, &root);
 2563                     node = parent;
 2564                     parent = PARENT(node);
 2565                     grandparent = PARENT(parent);
 2566                 }
 2567                 MAKE_BLACK(parent);
 2568                 MAKE_RED(grandparent);
 2569                 rotate_right(grandparent, &root);
 2570             }
 2571         } else {
 2572             child = LEFT(grandparent);
 2573             if (child != NULL && IS_RED(child)) {
 2574                 MAKE_BLACK(parent);
 2575                 MAKE_BLACK(child);
 2576                 MAKE_RED(grandparent);
 2577                 node = grandparent;
 2578             } else {
 2579                 if (node == LEFT(parent)) {
 2580                     rotate_right(parent, &root);
 2581                     node = parent;
 2582                     parent = PARENT(node);
 2583                     grandparent = PARENT(parent);
 2584                 }
 2585                 MAKE_BLACK(parent);
 2586                 MAKE_RED(grandparent);
 2587                 rotate_left(grandparent, &root);
 2588             }
 2589         }
 2590     }
 2591 
 2592     MAKE_BLACK(root);
 2593     ENSURE(IS_ROOT(root));
 2594     *rootp = root;
 2595 
 2596     return;
 2597 }
 2598 
 2599 /*
 2600  * This is the real workhorse of the deletion code, because it does the
 2601  * true red/black tree on a single level.
 2602  */
 2603 static void
 2604 deletefromlevel(dns_rbtnode_t *item, dns_rbtnode_t **rootp) {
 2605     dns_rbtnode_t *child, *sibling, *parent;
 2606     dns_rbtnode_t *successor;
 2607 
 2608     REQUIRE(item != NULL);
 2609 
 2610     /*
 2611      * Verify that the parent history is (apparently) correct.
 2612      */
 2613     INSIST((IS_ROOT(item) && *rootp == item) ||
 2614            (!IS_ROOT(item) &&
 2615         (LEFT(PARENT(item)) == item || RIGHT(PARENT(item)) == item)));
 2616 
 2617     child = NULL;
 2618 
 2619     if (LEFT(item) == NULL) {
 2620         if (RIGHT(item) == NULL) {
 2621             if (IS_ROOT(item)) {
 2622                 /*
 2623                  * This is the only item in the tree.
 2624                  */
 2625                 *rootp = NULL;
 2626                 return;
 2627             }
 2628         } else {
 2629             /*
 2630              * This node has one child, on the right.
 2631              */
 2632             child = RIGHT(item);
 2633         }
 2634     } else if (RIGHT(item) == NULL) {
 2635         /*
 2636          * This node has one child, on the left.
 2637          */
 2638         child = LEFT(item);
 2639     } else {
 2640         dns_rbtnode_t holder, *tmp = &holder;
 2641 
 2642         /*
 2643          * This node has two children, so it cannot be directly
 2644          * deleted.  Find its immediate in-order successor and
 2645          * move it to this location, then do the deletion at the
 2646          * old site of the successor.
 2647          */
 2648         successor = RIGHT(item);
 2649         while (LEFT(successor) != NULL) {
 2650             successor = LEFT(successor);
 2651         }
 2652 
 2653         /*
 2654          * The successor cannot possibly have a left child;
 2655          * if there is any child, it is on the right.
 2656          */
 2657         if (RIGHT(successor) != NULL) {
 2658             child = RIGHT(successor);
 2659         }
 2660 
 2661         /*
 2662          * Swap the two nodes; it would be simpler to just replace
 2663          * the value being deleted with that of the successor,
 2664          * but this rigamarole is done so the caller has complete
 2665          * control over the pointers (and memory allocation) of
 2666          * all of nodes.  If just the key value were removed from
 2667          * the tree, the pointer to the node would be unchanged.
 2668          */
 2669 
 2670         /*
 2671          * First, put the successor in the tree location of the
 2672          * node to be deleted.  Save its existing tree pointer
 2673          * information, which will be needed when linking up
 2674          * delete to the successor's old location.
 2675          */
 2676         memmove(tmp, successor, sizeof(dns_rbtnode_t));
 2677 
 2678         if (IS_ROOT(item)) {
 2679             *rootp = successor;
 2680             successor->is_root = true;
 2681             item->is_root = false;
 2682         } else if (LEFT(PARENT(item)) == item) {
 2683             LEFT(PARENT(item)) = successor;
 2684         } else {
 2685             RIGHT(PARENT(item)) = successor;
 2686         }
 2687 
 2688         PARENT(successor) = PARENT(item);
 2689         LEFT(successor) = LEFT(item);
 2690         RIGHT(successor) = RIGHT(item);
 2691         COLOR(successor) = COLOR(item);
 2692 
 2693         if (LEFT(successor) != NULL) {
 2694             PARENT(LEFT(successor)) = successor;
 2695         }
 2696         if (RIGHT(successor) != successor) {
 2697             PARENT(RIGHT(successor)) = successor;
 2698         }
 2699 
 2700         /*
 2701          * Now relink the node to be deleted into the
 2702          * successor's previous tree location.  PARENT(tmp)
 2703          * is the successor's original parent.
 2704          */
 2705         INSIST(!IS_ROOT(item));
 2706 
 2707         if (PARENT(tmp) == item) {
 2708             /*
 2709              * Node being deleted was successor's parent.
 2710              */
 2711             RIGHT(successor) = item;
 2712             PARENT(item) = successor;
 2713         } else {
 2714             LEFT(PARENT(tmp)) = item;
 2715             PARENT(item) = PARENT(tmp);
 2716         }
 2717 
 2718         /*
 2719          * Original location of successor node has no left.
 2720          */
 2721         LEFT(item) = NULL;
 2722         RIGHT(item) = RIGHT(tmp);
 2723         COLOR(item) = COLOR(tmp);
 2724     }
 2725 
 2726     /*
 2727      * Remove the node by removing the links from its parent.
 2728      */
 2729     if (!IS_ROOT(item)) {
 2730         if (LEFT(PARENT(item)) == item) {
 2731             LEFT(PARENT(item)) = child;
 2732         } else {
 2733             RIGHT(PARENT(item)) = child;
 2734         }
 2735 
 2736         if (child != NULL) {
 2737             PARENT(child) = PARENT(item);
 2738         }
 2739     } else {
 2740         /*
 2741          * This is the root being deleted, and at this point
 2742          * it is known to have just one child.
 2743          */
 2744         *rootp = child;
 2745         child->is_root = 1;
 2746         PARENT(child) = PARENT(item);
 2747     }
 2748 
 2749     /*
 2750      * Fix color violations.
 2751      */
 2752     if (IS_BLACK(item)) {
 2753         /* cppcheck-suppress nullPointerRedundantCheck symbolName=item
 2754          */
 2755         parent = PARENT(item);
 2756 
 2757         while (child != *rootp && IS_BLACK(child)) {
 2758             INSIST(child == NULL || !IS_ROOT(child));
 2759 
 2760             if (LEFT(parent) == child) {
 2761                 sibling = RIGHT(parent);
 2762 
 2763                 if (IS_RED(sibling)) {
 2764                     MAKE_BLACK(sibling);
 2765                     MAKE_RED(parent);
 2766                     rotate_left(parent, rootp);
 2767                     sibling = RIGHT(parent);
 2768                 }
 2769 
 2770                 INSIST(sibling != NULL);
 2771 
 2772                 /* cppcheck-suppress nullPointerRedundantCheck
 2773                  * symbolName=sibling */
 2774                 if (IS_BLACK(LEFT(sibling)) &&
 2775                     IS_BLACK(RIGHT(sibling))) {
 2776                     MAKE_RED(sibling);
 2777                     child = parent;
 2778                 } else {
 2779                     if (IS_BLACK(RIGHT(sibling))) {
 2780                         MAKE_BLACK(LEFT(sibling));
 2781                         MAKE_RED(sibling);
 2782                         rotate_right(sibling, rootp);
 2783                         sibling = RIGHT(parent);
 2784                     }
 2785 
 2786                     COLOR(sibling) = COLOR(parent);
 2787                     MAKE_BLACK(parent);
 2788                     INSIST(RIGHT(sibling) != NULL);
 2789                     MAKE_BLACK(RIGHT(sibling));
 2790                     rotate_left(parent, rootp);
 2791                     child = *rootp;
 2792                 }
 2793             } else {
 2794                 /*
 2795                  * Child is parent's right child.
 2796                  * Everything is done the same as above,
 2797                  * except mirrored.
 2798                  */
 2799                 sibling = LEFT(parent);
 2800 
 2801                 if (IS_RED(sibling)) {
 2802                     MAKE_BLACK(sibling);
 2803                     MAKE_RED(parent);
 2804                     rotate_right(parent, rootp);
 2805                     sibling = LEFT(parent);
 2806                 }
 2807 
 2808                 INSIST(sibling != NULL);
 2809 
 2810                 /* cppcheck-suppress nullPointerRedundantCheck
 2811                  * symbolName=sibling */
 2812                 if (IS_BLACK(LEFT(sibling)) &&
 2813                     IS_BLACK(RIGHT(sibling))) {
 2814                     MAKE_RED(sibling);
 2815                     child = parent;
 2816                 } else {
 2817                     if (IS_BLACK(LEFT(sibling))) {
 2818                         MAKE_BLACK(RIGHT(sibling));
 2819                         MAKE_RED(sibling);
 2820                         rotate_left(sibling, rootp);
 2821                         sibling = LEFT(parent);
 2822                     }
 2823 
 2824                     COLOR(sibling) = COLOR(parent);
 2825                     MAKE_BLACK(parent);
 2826                     INSIST(LEFT(sibling) != NULL);
 2827                     MAKE_BLACK(LEFT(sibling));
 2828                     rotate_right(parent, rootp);
 2829                     child = *rootp;
 2830                 }
 2831             }
 2832 
 2833             parent = PARENT(child);
 2834         }
 2835 
 2836         if (IS_RED(child)) {
 2837             MAKE_BLACK(child);
 2838         }
 2839     }
 2840 }
 2841 
 2842 static void
 2843 freenode(dns_rbt_t *rbt, dns_rbtnode_t **nodep) {
 2844     dns_rbtnode_t *node = *nodep;
 2845     *nodep = NULL;
 2846 
 2847     if (node->is_mmapped == 0) {
 2848         isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
 2849     }
 2850 
 2851     rbt->nodecount--;
 2852 }
 2853 
 2854 static void
 2855 deletetreeflat(dns_rbt_t *rbt, unsigned int quantum, bool unhash,
 2856            dns_rbtnode_t **nodep) {
 2857     dns_rbtnode_t *root = *nodep;
 2858 
 2859     while (root != NULL) {
 2860         /*
 2861          * If there is a left, right or down node, walk into it
 2862          * and iterate.
 2863          */
 2864         if (LEFT(root) != NULL) {
 2865             dns_rbtnode_t *node = root;
 2866             root = LEFT(root);
 2867             LEFT(node) = NULL;
 2868         } else if (RIGHT(root) != NULL) {
 2869             dns_rbtnode_t *node = root;
 2870             root = RIGHT(root);
 2871             RIGHT(node) = NULL;
 2872         } else if (DOWN(root) != NULL) {
 2873             dns_rbtnode_t *node = root;
 2874             root = DOWN(root);
 2875             DOWN(node) = NULL;
 2876         } else {
 2877             /*
 2878              * There are no left, right or down nodes, so we
 2879              * can free this one and go back to its parent.
 2880              */
 2881             dns_rbtnode_t *node = root;
 2882             root = PARENT(root);
 2883 
 2884             if (DATA(node) != NULL && rbt->data_deleter != NULL) {
 2885                 rbt->data_deleter(DATA(node), rbt->deleter_arg);
 2886             }
 2887             if (unhash) {
 2888                 unhash_node(rbt, node);
 2889             }
 2890             /*
 2891              * Note: we don't call unhash_node() here as we
 2892              * are destroying the complete RBT tree.
 2893              */
 2894 #if DNS_RBT_USEMAGIC
 2895             node->magic = 0;
 2896 #endif /* if DNS_RBT_USEMAGIC */
 2897             freenode(rbt, &node);
 2898             if (quantum != 0 && --quantum == 0) {
 2899                 break;
 2900             }
 2901         }
 2902     }
 2903 
 2904     *nodep = root;
 2905 }
 2906 
 2907 static size_t
 2908 getheight_helper(dns_rbtnode_t *node) {
 2909     size_t dl, dr;
 2910     size_t this_height, down_height;
 2911 
 2912     if (node == NULL) {
 2913         return (0);
 2914     }
 2915 
 2916     dl = getheight_helper(LEFT(node));
 2917     dr = getheight_helper(RIGHT(node));
 2918 
 2919     this_height = ISC_MAX(dl + 1, dr + 1);
 2920     down_height = getheight_helper(DOWN(node));
 2921 
 2922     return (ISC_MAX(this_height, down_height));
 2923 }
 2924 
 2925 size_t
 2926 dns__rbt_getheight(dns_rbt_t *rbt) {
 2927     return (getheight_helper(rbt->root));
 2928 }
 2929 
 2930 static bool
 2931 check_properties_helper(dns_rbtnode_t *node) {
 2932     if (node == NULL) {
 2933         return (true);
 2934     }
 2935 
 2936     if (IS_RED(node)) {
 2937         /* Root nodes must be BLACK. */
 2938         if (IS_ROOT(node)) {
 2939             return (false);
 2940         }
 2941 
 2942         /* Both children of RED nodes must be BLACK. */
 2943         if (IS_RED(LEFT(node)) || IS_RED(RIGHT(node))) {
 2944             return (false);
 2945         }
 2946     }
 2947 
 2948     /* cppcheck-suppress nullPointerRedundantCheck symbolName=node */
 2949     if ((DOWN(node) != NULL) && (!IS_ROOT(DOWN(node)))) {
 2950         return (false);
 2951     }
 2952 
 2953     if (IS_ROOT(node)) {
 2954         if ((PARENT(node) != NULL) && (DOWN(PARENT(node)) != node)) {
 2955             return (false);
 2956         }
 2957 
 2958         if (get_upper_node(node) != PARENT(node)) {
 2959             return (false);
 2960         }
 2961     }
 2962 
 2963     /* If node is assigned to the down_ pointer of its parent, it is
 2964      * a subtree root and must have the flag set.
 2965      */
 2966     if (((!PARENT(node)) || (DOWN(PARENT(node)) == node)) &&
 2967         (!IS_ROOT(node))) {
 2968         return (false);
 2969     }
 2970 
 2971     /* Repeat tests with this node's children. */
 2972     return (check_properties_helper(LEFT(node)) &&
 2973         check_properties_helper(RIGHT(node)) &&
 2974         check_properties_helper(DOWN(node)));
 2975 }
 2976 
 2977 static bool
 2978 check_black_distance_helper(dns_rbtnode_t *node, size_t *distance) {
 2979     size_t dl, dr, dd;
 2980 
 2981     if (node == NULL) {
 2982         *distance = 1;
 2983         return (true);
 2984     }
 2985 
 2986     /* cppcheck-suppress nullPointerRedundantCheck symbolName=node */
 2987     if (!check_black_distance_helper(LEFT(node), &dl)) {
 2988         return (false);
 2989     }
 2990 
 2991     /* cppcheck-suppress nullPointerRedundantCheck symbolName=node */
 2992     if (!check_black_distance_helper(RIGHT(node), &dr)) {
 2993         return (false);
 2994     }
 2995 
 2996     /* cppcheck-suppress nullPointerRedundantCheck symbolName=node */
 2997     if (!check_black_distance_helper(DOWN(node), &dd)) {
 2998         return (false);
 2999     }
 3000 
 3001     /* Left and right side black node counts must match. */
 3002     if (dl != dr) {
 3003         return (false);
 3004     }
 3005 
 3006     if (IS_BLACK(node)) {
 3007         dl++;
 3008     }
 3009 
 3010     *distance = dl;
 3011 
 3012     return (true);
 3013 }
 3014 
 3015 bool
 3016 dns__rbt_checkproperties(dns_rbt_t *rbt) {
 3017     size_t dd;
 3018 
 3019     if (!check_properties_helper(rbt->root)) {
 3020         return (false);
 3021     }
 3022 
 3023     /* Path from a given node to all its leaves must contain the
 3024      * same number of BLACK child nodes. This is done separately
 3025      * here instead of inside check_properties_helper() as
 3026      * it would take (n log n) complexity otherwise.
 3027      */
 3028     return (check_black_distance_helper(rbt->root, &dd));
 3029 }
 3030 
 3031 static void
 3032 dns_rbt_indent(FILE *f, int depth) {
 3033     int i;
 3034 
 3035     fprintf(f, "%4d ", depth);
 3036 
 3037     for (i = 0; i < depth; i++) {
 3038         fprintf(f, "- ");
 3039     }
 3040 }
 3041 
 3042 void
 3043 dns_rbt_printnodeinfo(dns_rbtnode_t *n, FILE *f) {
 3044     if (n == NULL) {
 3045         fprintf(f, "Null node\n");
 3046         return;
 3047     }
 3048 
 3049     fprintf(f, "Node info for nodename: ");
 3050     printnodename(n, true, f);
 3051     fprintf(f, "\n");
 3052 
 3053     fprintf(f, "n = %p\n", n);
 3054 
 3055     fprintf(f, "Relative pointers: %s%s%s%s%s\n",
 3056         (n->parent_is_relative == 1 ? " P" : ""),
 3057         (n->right_is_relative == 1 ? " R" : ""),
 3058         (n->left_is_relative == 1 ? " L" : ""),
 3059         (n->down_is_relative == 1 ? " D" : ""),
 3060         (n->data_is_relative == 1 ? " T" : ""));
 3061 
 3062     fprintf(f, "node lock address = %u\n", n->locknum);
 3063 
 3064     fprintf(f, "Parent: %p\n", n->parent);
 3065     fprintf(f, "Right: %p\n", n->right);
 3066     fprintf(f, "Left: %p\n", n->left);
 3067     fprintf(f, "Down: %p\n", n->down);
 3068     fprintf(f, "Data: %p\n", n->data);
 3069 }
 3070 
 3071 static void
 3072 printnodename(dns_rbtnode_t *node, bool quoted, FILE *f) {
 3073     isc_region_t r;
 3074     dns_name_t name;
 3075     char buffer[DNS_NAME_FORMATSIZE];
 3076     dns_offsets_t offsets;
 3077 
 3078     r.length = NAMELEN(node);
 3079     r.base = NAME(node);
 3080 
 3081     dns_name_init(&name, offsets);
 3082     dns_name_fromregion(&name, &r);
 3083 
 3084     dns_name_format(&name, buffer, sizeof(buffer));
 3085 
 3086     if (quoted) {
 3087         fprintf(f, "\"%s\"", buffer);
 3088     } else {
 3089         fprintf(f, "%s", buffer);
 3090     }
 3091 }
 3092 
 3093 static void
 3094 print_text_helper(dns_rbtnode_t *root, dns_rbtnode_t *parent, int depth,
 3095           const char *direction, void (*data_printer)(FILE *, void *),
 3096           FILE *f) {
 3097     dns_rbt_indent(f, depth);
 3098 
 3099     if (root != NULL) {
 3100         printnodename(root, true, f);
 3101         /*
 3102          * Don't use IS_RED(root) as it tests for 'root != NULL'
 3103          * and cppcheck produces false positives.
 3104          */
 3105         fprintf(f, " (%s, %s", direction,
 3106             COLOR(root) == RED ? "RED" : "BLACK");
 3107 
 3108         if ((!IS_ROOT(root) && PARENT(root) != parent) ||
 3109             (IS_ROOT(root) && depth > 0 && DOWN(PARENT(root)) != root))
 3110         {
 3111             fprintf(f, " (BAD parent pointer! -> ");
 3112             if (PARENT(root) != NULL) {
 3113                 printnodename(PARENT(root), true, f);
 3114             } else {
 3115                 fprintf(f, "NULL");
 3116             }
 3117             fprintf(f, ")");
 3118         }
 3119 
 3120         fprintf(f, ")");
 3121 
 3122         if (root->data != NULL && data_printer != NULL) {
 3123             fprintf(f, " data@%p: ", root->data);
 3124             data_printer(f, root->data);
 3125         }
 3126         fprintf(f, "\n");
 3127 
 3128         depth++;
 3129 
 3130         /*
 3131          * Don't use IS_RED(root) as it tests for 'root != NULL'
 3132          * and cppcheck produces false positives.
 3133          */
 3134         if (COLOR(root) == RED && IS_RED(LEFT(root))) {
 3135             fprintf(f, "** Red/Red color violation on left\n");
 3136         }
 3137         print_text_helper(LEFT(root), root, depth, "left", data_printer,
 3138                   f);
 3139 
 3140         /*
 3141          * Don't use IS_RED(root) as cppcheck produces false positives.
 3142          */
 3143         if (COLOR(root) == RED && IS_RED(RIGHT(root))) {
 3144             fprintf(f, "** Red/Red color violation on right\n");
 3145         }
 3146         print_text_helper(RIGHT(root), root, depth, "right",
 3147                   data_printer, f);
 3148 
 3149         print_text_helper(DOWN(root), NULL, depth, "down", data_printer,
 3150                   f);
 3151     } else {
 3152         fprintf(f, "NULL (%s)\n", direction);
 3153     }
 3154 }
 3155 
 3156 void
 3157 dns_rbt_printtext(dns_rbt_t *rbt, void (*data_printer)(FILE *, void *),
 3158           FILE *f) {
 3159     REQUIRE(VALID_RBT(rbt));
 3160 
 3161     print_text_helper(rbt->root, NULL, 0, "root", data_printer, f);
 3162 }
 3163 
 3164 static int
 3165 print_dot_helper(dns_rbtnode_t *node, unsigned int *nodecount,
 3166          bool show_pointers, FILE *f) {
 3167     unsigned int l, r, d;
 3168 
 3169     if (node == NULL) {
 3170         return (0);
 3171     }
 3172 
 3173     l = print_dot_helper(LEFT(node), nodecount, show_pointers, f);
 3174     r = print_dot_helper(RIGHT(node), nodecount, show_pointers, f);
 3175     d = print_dot_helper(DOWN(node), nodecount, show_pointers, f);
 3176 
 3177     *nodecount += 1;
 3178 
 3179     fprintf(f, "node%u[label = \"<f0> |<f1> ", *nodecount);
 3180     printnodename(node, false, f);
 3181     fprintf(f, "|<f2>");
 3182 
 3183     if (show_pointers) {
 3184         fprintf(f, "|<f3> n=%p|<f4> p=%p", node, PARENT(node));
 3185     }
 3186 
 3187     fprintf(f, "\"] [");
 3188 
 3189     if (IS_RED(node)) {
 3190         fprintf(f, "color=red");
 3191     } else {
 3192         fprintf(f, "color=black");
 3193     }
 3194 
 3195     /* XXXMUKS: verify that IS_ROOT() indicates subtree root and not
 3196      * forest root.
 3197      */
 3198     if (IS_ROOT(node)) {
 3199         fprintf(f, ",penwidth=3");
 3200     }
 3201 
 3202     if (IS_EMPTY(node)) {
 3203         fprintf(f, ",style=filled,fillcolor=lightgrey");
 3204     }
 3205 
 3206     fprintf(f, "];\n");
 3207 
 3208     if (LEFT(node) != NULL) {
 3209         fprintf(f, "\"node%u\":f0 -> \"node%u\":f1;\n", *nodecount, l);
 3210     }
 3211 
 3212     if (DOWN(node) != NULL) {
 3213         fprintf(f, "\"node%u\":f1 -> \"node%u\":f1 [penwidth=5];\n",
 3214             *nodecount, d);
 3215     }
 3216 
 3217     if (RIGHT(node) != NULL) {
 3218         fprintf(f, "\"node%u\":f2 -> \"node%u\":f1;\n", *nodecount, r);
 3219     }
 3220 
 3221     return (*nodecount);
 3222 }
 3223 
 3224 void
 3225 dns_rbt_printdot(dns_rbt_t *rbt, bool show_pointers, FILE *f) {
 3226     unsigned int nodecount = 0;
 3227 
 3228     REQUIRE(VALID_RBT(rbt));
 3229 
 3230     fprintf(f, "digraph g {\n");
 3231     fprintf(f, "node [shape = record,height=.1];\n");
 3232     print_dot_helper(rbt->root, &nodecount, show_pointers, f);
 3233     fprintf(f, "}\n");
 3234 }
 3235 
 3236 /*
 3237  * Chain Functions
 3238  */
 3239 
 3240 void
 3241 dns_rbtnodechain_init(dns_rbtnodechain_t *chain) {
 3242     REQUIRE(chain != NULL);
 3243 
 3244     /*
 3245      * Initialize 'chain'.
 3246      */
 3247     chain->end = NULL;
 3248     chain->level_count = 0;
 3249     chain->level_matches = 0;
 3250     memset(chain->levels, 0, sizeof(chain->levels));
 3251 
 3252     chain->magic = CHAIN_MAGIC;
 3253 }
 3254 
 3255 isc_result_t
 3256 dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name,
 3257              dns_name_t *origin, dns_rbtnode_t **node) {
 3258     isc_result_t result = ISC_R_SUCCESS;
 3259 
 3260     REQUIRE(VALID_CHAIN(chain));
 3261 
 3262     if (node != NULL) {
 3263         *node = chain->end;
 3264     }
 3265 
 3266     if (chain->end == NULL) {
 3267         return (ISC_R_NOTFOUND);
 3268     }
 3269 
 3270     if (name != NULL) {
 3271         NODENAME(chain->end, name);
 3272 
 3273         if (chain->level_count == 0) {
 3274             /*
 3275              * Names in the top level tree are all absolute.
 3276              * Always make 'name' relative.
 3277              */
 3278             INSIST(dns_name_isabsolute(name));
 3279 
 3280             /*
 3281              * This is cheaper than dns_name_getlabelsequence().
 3282              */
 3283             name->labels--;
 3284             name->length--;
 3285             name->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
 3286         }
 3287     }
 3288 
 3289     if (origin != NULL) {
 3290         if (chain->level_count > 0) {
 3291             result = chain_name(chain, origin, false);
 3292         } else {
 3293             dns_name_copynf(dns_rootname, origin);
 3294         }
 3295     }
 3296 
 3297     return (result);
 3298 }
 3299 
 3300 isc_result_t
 3301 dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
 3302               dns_name_t *origin) {
 3303     dns_rbtnode_t *current, *previous, *predecessor;
 3304     isc_result_t result = ISC_R_SUCCESS;
 3305     bool new_origin = false;
 3306 
 3307     REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
 3308 
 3309     predecessor = NULL;
 3310 
 3311     current = chain->end;
 3312 
 3313     if (LEFT(current) != NULL) {
 3314         /*
 3315          * Moving left one then right as far as possible is the
 3316          * previous node, at least for this level.
 3317          */
 3318         current = LEFT(current);
 3319 
 3320         while (RIGHT(current) != NULL) {
 3321             current = RIGHT(current);
 3322         }
 3323 
 3324         predecessor = current;
 3325     } else {
 3326         /*
 3327          * No left links, so move toward the root.  If at any point on
 3328          * the way there the link from parent to child is a right
 3329          * link, then the parent is the previous node, at least
 3330          * for this level.
 3331          */
 3332         while (!IS_ROOT(current)) {
 3333             previous = current;
 3334             current = PARENT(current);
 3335 
 3336             if (RIGHT(current) == previous) {
 3337                 predecessor = current;
 3338                 break;
 3339             }
 3340         }
 3341     }
 3342 
 3343     if (predecessor != NULL) {
 3344         /*
 3345          * Found a predecessor node in this level.  It might not
 3346          * really be the predecessor, however.
 3347          */
 3348         if (DOWN(predecessor) != NULL) {
 3349             /*
 3350              * The predecessor is really down at least one level.
 3351              * Go down and as far right as possible, and repeat
 3352              * as long as the rightmost node has a down pointer.
 3353              */
 3354             do {
 3355                 /*
 3356                  * XXX DCL Need to do something about origins
 3357                  * here. See whether to go down, and if so
 3358                  * whether it is truly what Bob calls a
 3359                  * new origin.
 3360                  */
 3361                 ADD_LEVEL(chain, predecessor);
 3362                 predecessor = DOWN(predecessor);
 3363 
 3364                 /* XXX DCL duplicated from above; clever
 3365                  * way to unduplicate? */
 3366 
 3367                 while (RIGHT(predecessor) != NULL) {
 3368                     predecessor = RIGHT(predecessor);
 3369                 }
 3370             } while (DOWN(predecessor) != NULL);
 3371 
 3372             /* XXX DCL probably needs work on the concept */
 3373             if (origin != NULL) {
 3374                 new_origin = true;
 3375             }
 3376         }
 3377     } else if (chain->level_count > 0) {
 3378         /*
 3379          * Dang, didn't find a predecessor in this level.
 3380          * Got to the root of this level without having traversed
 3381          * any right links.  Ascend the tree one level; the
 3382          * node that points to this tree is the predecessor.
 3383          */
 3384         INSIST(chain->level_count > 0 && IS_ROOT(current));
 3385         predecessor = chain->levels[--chain->level_count];
 3386 
 3387         /* XXX DCL probably needs work on the concept */
 3388         /*
 3389          * Don't declare an origin change when the new origin is "."
 3390          * at the top level tree, because "." is declared as the origin
 3391          * for the second level tree.
 3392          */
 3393         if (origin != NULL &&
 3394             (chain->level_count > 0 || OFFSETLEN(predecessor) > 1)) {
 3395             new_origin = true;
 3396         }
 3397     }
 3398 
 3399     if (predecessor != NULL) {
 3400         chain->end = predecessor;
 3401 
 3402         if (new_origin) {
 3403             result = dns_rbtnodechain_current(chain, name, origin,
 3404                               NULL);
 3405             if (result == ISC_R_SUCCESS) {
 3406                 result = DNS_R_NEWORIGIN;
 3407             }
 3408         } else {
 3409             result = dns_rbtnodechain_current(chain, name, NULL,
 3410                               NULL);
 3411         }
 3412     } else {
 3413         result = ISC_R_NOMORE;
 3414     }
 3415 
 3416     return (result);
 3417 }
 3418 
 3419 isc_result_t
 3420 dns_rbtnodechain_down(dns_rbtnodechain_t *chain, dns_name_t *name,
 3421               dns_name_t *origin) {
 3422     dns_rbtnode_t *current, *successor;
 3423     isc_result_t result = ISC_R_SUCCESS;
 3424     bool new_origin = false;
 3425 
 3426     REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
 3427 
 3428     successor = NULL;
 3429 
 3430     current = chain->end;
 3431 
 3432     if (DOWN(current) != NULL) {
 3433         /*
 3434          * Don't declare an origin change when the new origin is "."
 3435          * at the second level tree, because "." is already declared
 3436          * as the origin for the top level tree.
 3437          */
 3438         if (chain->level_count > 0 || OFFSETLEN(current) > 1) {
 3439             new_origin = true;
 3440         }
 3441 
 3442         ADD_LEVEL(chain, current);
 3443         current = DOWN(current);
 3444 
 3445         while (LEFT(current) != NULL) {
 3446             current = LEFT(current);
 3447         }
 3448 
 3449         successor = current;
 3450     }
 3451 
 3452     if (successor != NULL) {
 3453         chain->end = successor;
 3454 
 3455         /*
 3456          * It is not necessary to use dns_rbtnodechain_current like
 3457          * the other functions because this function will never
 3458          * find a node in the topmost level.  This is because the
 3459          * root level will never be more than one name, and everything
 3460          * in the megatree is a successor to that node, down at
 3461          * the second level or below.
 3462          */
 3463 
 3464         if (name != NULL) {
 3465             NODENAME(chain->end, name);
 3466         }
 3467 
 3468         if (new_origin) {
 3469             if (origin != NULL) {
 3470                 result = chain_name(chain, origin, false);
 3471             }
 3472 
 3473             if (result == ISC_R_SUCCESS) {
 3474                 result = DNS_R_NEWORIGIN;
 3475             }
 3476         } else {
 3477             result = ISC_R_SUCCESS;
 3478         }
 3479     } else {
 3480         result = ISC_R_NOMORE;
 3481     }
 3482 
 3483     return (result);
 3484 }
 3485 
 3486 isc_result_t
 3487 dns_rbtnodechain_nextflat(dns_rbtnodechain_t *chain, dns_name_t *name) {
 3488     dns_rbtnode_t *current, *previous, *successor;
 3489     isc_result_t result = ISC_R_SUCCESS;
 3490 
 3491     REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
 3492 
 3493     successor = NULL;
 3494 
 3495     current = chain->end;
 3496 
 3497     if (RIGHT(current) == NULL) {
 3498         while (!IS_ROOT(current)) {
 3499             previous = current;
 3500             current = PARENT(current);
 3501 
 3502             if (LEFT(current) == previous) {
 3503                 successor = current;
 3504                 break;
 3505             }
 3506         }
 3507     } else {
 3508         current = RIGHT(current);
 3509 
 3510         while (LEFT(current) != NULL) {
 3511             current = LEFT(current);
 3512         }
 3513 
 3514         successor = current;
 3515     }
 3516 
 3517     if (successor != NULL) {
 3518         chain->end = successor;
 3519 
 3520         if (name != NULL) {
 3521             NODENAME(chain->end, name);
 3522         }
 3523 
 3524         result = ISC_R_SUCCESS;
 3525     } else {
 3526         result = ISC_R_NOMORE;
 3527     }
 3528 
 3529     return (result);
 3530 }
 3531 
 3532 isc_result_t
 3533 dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name,
 3534               dns_name_t *origin) {
 3535     dns_rbtnode_t *current, *previous, *successor;
 3536     isc_result_t result = ISC_R_SUCCESS;
 3537     bool new_origin = false;
 3538 
 3539     REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
 3540 
 3541     successor = NULL;
 3542 
 3543     current = chain->end;
 3544 
 3545     /*
 3546      * If there is a level below this node, the next node is the leftmost
 3547      * node of the next level.
 3548      */
 3549     if (DOWN(current) != NULL) {
 3550         /*
 3551          * Don't declare an origin change when the new origin is "."
 3552          * at the second level tree, because "." is already declared
 3553          * as the origin for the top level tree.
 3554          */
 3555         if (chain->level_count > 0 || OFFSETLEN(current) > 1) {
 3556             new_origin = true;
 3557         }
 3558 
 3559         ADD_LEVEL(chain, current);
 3560         current = DOWN(current);
 3561 
 3562         while (LEFT(current) != NULL) {
 3563             current = LEFT(current);
 3564         }
 3565 
 3566         successor = current;
 3567     } else if (RIGHT(current) == NULL) {
 3568         /*
 3569          * The successor is up, either in this level or a previous one.
 3570          * Head back toward the root of the tree, looking for any path
 3571          * that was via a left link; the successor is the node that has
 3572          * that left link.  In the event the root of the level is
 3573          * reached without having traversed any left links, ascend one
 3574          * level and look for either a right link off the point of
 3575          * ascent, or search for a left link upward again, repeating
 3576          * ascends until either case is true.
 3577          */
 3578         do {
 3579             while (!IS_ROOT(current)) {
 3580                 previous = current;
 3581                 current = PARENT(current);
 3582 
 3583                 if (LEFT(current) == previous) {
 3584                     successor = current;
 3585                     break;
 3586                 }
 3587             }
 3588 
 3589             if (successor == NULL) {
 3590                 /*
 3591                  * Reached the root without having traversed
 3592                  * any left pointers, so this level is done.
 3593                  */
 3594                 if (chain->level_count == 0) {
 3595                     /*
 3596                      * If the tree we are iterating over
 3597                      * was modified since this chain was
 3598                      * initialized in a way that caused
 3599                      * node splits to occur, "current" may
 3600                      * now be pointing to a root node which
 3601                      * appears to be at level 0, but still
 3602                      * has a parent.  If that happens,
 3603                      * abort.  Otherwise, we are done
 3604                      * looking for a successor as we really
 3605                      * reached the root node on level 0.
 3606                      */
 3607                     INSIST(PARENT(current) == NULL);
 3608                     break;
 3609                 }
 3610 
 3611                 current = chain->levels[--chain->level_count];
 3612                 new_origin = true;
 3613 
 3614                 if (RIGHT(current) != NULL) {
 3615                     break;
 3616                 }
 3617             }
 3618         } while (successor == NULL);
 3619     }
 3620 
 3621     if (successor == NULL && RIGHT(current) != NULL) {
 3622         current = RIGHT(current);
 3623 
 3624         while (LEFT(current) != NULL) {
 3625             current = LEFT(current);
 3626         }
 3627 
 3628         successor = current;
 3629     }
 3630 
 3631     if (successor != NULL) {
 3632         /*
 3633          * If we determine that the current node is the successor to
 3634          * itself, we will run into an infinite loop, so abort instead.
 3635          */
 3636         INSIST(chain->end != successor);
 3637 
 3638         chain->end = successor;
 3639 
 3640         /*
 3641          * It is not necessary to use dns_rbtnodechain_current like
 3642          * the other functions because this function will never
 3643          * find a node in the topmost level.  This is because the
 3644          * root level will never be more than one name, and everything
 3645          * in the megatree is a successor to that node, down at
 3646          * the second level or below.
 3647          */
 3648 
 3649         if (name != NULL) {
 3650             NODENAME(chain->end, name);
 3651         }
 3652 
 3653         if (new_origin) {
 3654             if (origin != NULL) {
 3655                 result = chain_name(chain, origin, false);
 3656             }
 3657 
 3658             if (result == ISC_R_SUCCESS) {
 3659                 result = DNS_R_NEWORIGIN;
 3660             }
 3661         } else {
 3662             result = ISC_R_SUCCESS;
 3663         }
 3664     } else {
 3665         result = ISC_R_NOMORE;
 3666     }
 3667 
 3668     return (result);
 3669 }
 3670 
 3671 isc_result_t
 3672 dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
 3673                dns_name_t *name, dns_name_t *origin)
 3674 
 3675 {
 3676     isc_result_t result;
 3677 
 3678     REQUIRE(VALID_RBT(rbt));
 3679     REQUIRE(VALID_CHAIN(chain));
 3680 
 3681     dns_rbtnodechain_reset(chain);
 3682 
 3683     chain->end = rbt->root;
 3684 
 3685     result = dns_rbtnodechain_current(chain, name, origin, NULL);
 3686 
 3687     if (result == ISC_R_SUCCESS) {
 3688         result = DNS_R_NEWORIGIN;
 3689     }
 3690 
 3691     return (result);
 3692 }
 3693 
 3694 isc_result_t
 3695 dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
 3696               dns_name_t *name, dns_name_t *origin)
 3697 
 3698 {
 3699     isc_result_t result;
 3700 
 3701     REQUIRE(VALID_RBT(rbt));
 3702     REQUIRE(VALID_CHAIN(chain));
 3703 
 3704     dns_rbtnodechain_reset(chain);
 3705 
 3706     result = move_chain_to_last(chain, rbt->root);
 3707     if (result != ISC_R_SUCCESS) {
 3708         return (result);
 3709     }
 3710 
 3711     result = dns_rbtnodechain_current(chain, name, origin, NULL);
 3712 
 3713     if (result == ISC_R_SUCCESS) {
 3714         result = DNS_R_NEWORIGIN;
 3715     }
 3716 
 3717     return (result);
 3718 }
 3719 
 3720 void
 3721 dns_rbtnodechain_reset(dns_rbtnodechain_t *chain) {
 3722     REQUIRE(VALID_CHAIN(chain));
 3723 
 3724     /*
 3725      * Free any dynamic storage associated with 'chain', and then
 3726      * reinitialize 'chain'.
 3727      */
 3728     chain->end = NULL;
 3729     chain->level_count = 0;
 3730     chain->level_matches = 0;
 3731 }
 3732 
 3733 void
 3734 dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain) {
 3735     /*
 3736      * Free any dynamic storage associated with 'chain', and then
 3737      * invalidate 'chain'.
 3738      */
 3739 
 3740     dns_rbtnodechain_reset(chain);
 3741 
 3742     chain->magic = 0;
 3743 }
 3744 
 3745 /* XXXMUKS:
 3746  *
 3747  * - worth removing inline as static functions are inlined automatically
 3748  *   where suitable by modern compilers.
 3749  * - bump the size of dns_rbt.nodecount to size_t.
 3750  * - the dumpfile header also contains a nodecount that is unsigned
 3751  *   int. If large files (> 2^32 nodes) are to be supported, the
 3752  *   allocation for this field should be increased.
 3753  */