"Fossies" - the Fresh Open Source Software Archive

Member "bind-9.17.5/lib/dns/rbt.c" (4 Sep 2020, 94336 Bytes) of package /linux/misc/dns/bind9/9.17.5/bind-9.17.5.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.17.4_vs_9.17.5.

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