0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark AndrewsCopyright (C) 1999-2001, 2004, 2016 Internet Systems Consortium, Inc. ("ISC")
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark AndrewsThis Source Code Form is subject to the terms of the Mozilla Public
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark AndrewsLicense, v. 2.0. If a copy of the MPL was not distributed with this
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark Andrewsfile, You can obtain one at http://mozilla.org/MPL/2.0/.
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews$Id: red-black,v 1.9 2004/03/05 05:04:46 marka Exp $
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence Red-Black Tree Implementation Notes
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceBIND9's basic name storage mechanism is to use a modified form of
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencebalanced binary tree known as a red-black tree. Red-black trees
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceprovide for relatively efficient storage, retrieval and removal of
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencedata while maintaining the lexical order of all stored keys, a
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencenecessary function for DNS security.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceA red-black tree is a balanced binary tree named for the coloring that
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceis done in the tree, identifying each node as either red or black.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceThere are two simple rules for maintaining the color of nodes:
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence (1) A red node has only black children.
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence (2) The path from the root to any leaf node always includes the
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence same number of black nodes.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceWhenever a key is added or removed, adjustments are made to adhere to
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencethose two rules. These adjustments are relatively cheap to make but
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencemaintain the balance of the tree, thus making for efficient addition,
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencelookup and deletion operations, all of which are O(log N). The color
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceof a node is not relevant to external users of the tree; it is needed
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceonly to maintain the balance of the tree.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceFor more information on basic red-black trees, see _Introduction to
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceAlgorithms_, Cormen, Leiserson, and Rivest, MIT Press / McGraw Hill,
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence1990, ISBN 0-262-03141-8, chapter 14.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceIn BIND9, the red-black tree implementation uses DNS names as keys,
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceand can store arbitrary data with each key value. "name" and "key"
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceare used interchangably in this document.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceThe basic red-black tree algorithm is further adapted for use in BIND9
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceto incorporate the notion of hierarchy, creating a tree of red-black
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencetrees. Where there is more than one name with a common suffix, all
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencenames with that suffix are stored in their own red-black tree, with a
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencedown pointer from the suffix locating the subtree.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceFor example, consider storing the following names:
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceNo matter which order the keys were added, this would result in a tree
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencethat can be visualized as:
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceThis tree shows that when there is no key for a particular label, and
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencewhen there is only one known label for its immediate subordinate, then
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencemultiple labels can appear in a single node, such as at d.e.f and g.h.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceIt also demonstrates that there can be more nodes in the tree of trees
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencethan there are actual keys (which degrades the O(log N) performance
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencemarginally); the nodes at d.e.f and w.y do not represent keys.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceAs an aside, remember that when ordering DNS names, labels are
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceexamined from the right, therefore w.y sorts after x and before z.
1641377cbaa7aac054bfa6b5c6172ed64044e020David LawrenceA split can occur not only on a regular label boundary, but also
1641377cbaa7aac054bfa6b5c6172ed64044e020David Lawrencebetween any two bits in an EDNS bitstring label. The common-suffix
1641377cbaa7aac054bfa6b5c6172ed64044e020David Lawrencerules will be applied to keep as many bits together as possible.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceIn the current implementation of the tree of trees, a node is
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceconsidered to "formally" exist only if it has data associated with
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceit. So if the above tree then had the key d.e.f added to it, the
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceoperation would succeed rather than getting an "already exists"
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceAlong the same lines, if a key is added with a name which is a proper
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencesuperdomain of the name stored in an existing node, the operation will
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencesucceed by splitting the existing node into one node that is the key
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceand another node that is the remaining parts of the name. Adding e.f
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceto the above tree results in the top level red-black tree having a
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencenode named e.f where the current d.e.f is, and a down pointer from
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenced.e.f to a "tree" of a single node named d. The down pointer from d
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencewould be kept to the level which has x, w.y, and z.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceA similar split of d.e.f would occur if the name k.e.f were added.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceThe top level tree would have the node e.f with a down pointer to a
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencelevel that had both d and k, and d would continue to have its down
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencepointer to the x, w.y and z level.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceIt is guaranteed when splitting that external references to the node
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencethat is split will remain valid --- in the previous examples, anything
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencethat was pointing to the node that was d.e.f will still point to the
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencenode that is now just d.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceWhen deleting keys, nodes can be rejoined. If both of p.w.y.d.e.f and
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceq.w.y.d.e.f were removed from the example tree, the node named w.y
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencewould become o.w.y. Unlike splitting, it is _not_ guaranteed that
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceexternal references remain consistent; sometimes they will, sometimes
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencethey won't. Also, note that deletion is not perfectly symmetric with
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceaddition. If you "undo" the last addition with a deletion of the same
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencekey then the tree of trees is not guaranteed to have exactly the same
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencestructure as it had prior to the addition. Sometimes, but not always.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceRejoining does not happen if it would violate any of the rules that
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencecause a split. o would not be rejoined with w.y if w.y had data
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceassociated with the key; o would remain as a single node on its own
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencelevel. This emphasizes the rule that a node is considered to formally
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceexist only if data is associated with it, because even if w.y.d.e.f
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencehad been explicitly added as a key but with no data, then o would
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencestill be merged with the w.y node when p and q were deleted.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceSearching for a node generally returns one of three possible results:
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceeither the key is found, a superdomain (partial match) of the key is
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencefound, or no part of the key is found. The first and last are rather
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceobvious, and the second result basically means that a hierarchically
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceenclosing name is found; e.g, searching for bb.rc.vix.com turned up
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencerc.vix.com, but not the full name.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceNo locking is done within the RBT library. @@@
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid LawrenceWhen a partial match is made, level_matches is set while the chain
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid Lawrencepoints to the partial match node that was found. Then the chain is
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid Lawrenceadjusted to point to the DNSSEC predecessor node, which might not even
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid Lawrencebe under the same top level domain as the name that was searched for.
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid LawrenceFor example, consider a database that had only the names vix.com and
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid Lawrenceisc.org. A search for uu.net would leave the chain pointed to
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid Lawrencevix.com, the DNSSEC predecessor. Though this might first appear to
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid Lawrencecause level_matches to be bogus because the chain has been unwound and
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid Lawrencesent down another path, note that the partial match node will always
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid Lawrencebe in the chain of the predecessor, too --- and often the partial
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid Lawrencematch node will be the predecessor itself. In the vix.com/isc.org
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid Lawrenceexample, the search for uu.net finds a partial match at ".", which is
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid Lawrenceof course also in the path to the vix.com predecessor. A search for
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid Lawrencewww.isc.org would find that isc.org is both the partial match and the
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceEXTERNAL PROGRAMMATIC DETAILS
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceThis section details the functions used to interact with the BIND9
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencered-black tree library, or RBT for short.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceA source file that will be using RBT will usually need to include
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence<dns/rbt.h>. This header file automatically includes <isc/result.h),
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceThe rbt.h file has more complete descriptions of each of the functions
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencenamed here, including what is required for each argument, what each
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencefunction ensures (and might not ensure) will occur, and the full range
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceof possible results for each call. Note well: if a function returns a
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencedns_result_t rather than void, it definitely means there is something
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencethat can go possibly wrong in the function and it should be checked by
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceA new tree of trees must be initialized using:
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence dns_result_t dns_rbt_create(isc_mem_t *mctx, void (*deleter)(void *, void *),
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence void *deleter_arg, dns_rbt_t **rbtp);
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceThe memory context, mctx, must be a non-null pointer that was
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceinitialized with isc_mem_create(). The deleter argument, if non-null,
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceshould point to a function that is responsible for cleaning up any
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencememory associated with the data pointer of a node when the node is
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencedeleted. It is passed the deleted node's data pointer as its first
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceargument and deleter_arg as its second argument.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceAfter initializing an RBT manager, to add keys to the tree, use:
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence dns_result_t dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data);
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceThe name _must_ be an absolute name. It is not required that the data
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencepointer be non-null, but it is recommended that it point to something,
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceeven just invalid memory, because of the various searching and
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencedeletion issues described in the previous section. The RBT code will
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencenot attempt to dereference the pointer.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceTo find a key in the tree, use:
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence dns_result_t dns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, void **data);
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceThe data parameter must not be NULL, but *data must be NULL. The
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceresult will be either DNS_R_SUCCESS, DNS_R_PARTIALMATCH or
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceDNS_R_NOTFOUND. In the first case, an exact match was found for the
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencename and there was an associate data pointer, which is returned via
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencethe data parameter. A partial match results when the name has not
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencebeen found but a superdomain name, with data, does exist; then the
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencedata for that name is returned in the data parameter. If no data is
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencefound for the name or a superdomain, *data will remain NULL.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceINTERNAL PROGRAMMATIC DETAILS
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceThis section is mainly relevant to the RBT DB implementation. It is
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencehighly recommended that programmers using the RBT library stick to the
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencefunctions named in the previous section.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceThe dns_rbt_addname and dns_rbt_findname functions named in the
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceprevious section are wrappers around dns_rbt_addnode and
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencedns_rbt_findnode. The *node functions for the most part do not
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceparticularly care whether a node has an associated data pointer or
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencenot, whereas the *name functions do. The one exception to this is
bf668d00172e2308da0e01048284d7efa85495b1David Lawrencethat when a PARTIALMATCH is returned for a search, the indicated node
bf668d00172e2308da0e01048284d7efa85495b1David Lawrenceis the deepest match that has data, rather than just the deepest
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid Lawrencematch. Even that behavior is selectable, however, using the boolean
29e23c0b3eec2a7c4b0f6bfa3f9ff9e17e72e48dDavid Lawrenceempty_data_ok argument to dns_rbt_findnode.
bf668d00172e2308da0e01048284d7efa85495b1David LawrenceEach node in the tree of trees is represented by the following structure:
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence typedef struct dns_rbtnode {
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence struct dns_rbtnode *left;
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence struct dns_rbtnode *right;
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence struct dns_rbtnode *down;
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence * The following bitfields add up to a total bitwidth of 32.
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence * The range of values necessary for each item is indicated,
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence * but in the case of "attributes" the field is wider to accomodate
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence * possible future expansion. "offsetlen" could be one bit
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence * narrower by always adjusting its value by 1 to find the real
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence * offsetlen, but doing so does not gain anything (except perhaps
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence * another bit for "attributes", which doesn't yet need any more).
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence unsigned int color:1; /* range is 0..1 */
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence unsigned int attributes:6; /* range is 0..2 */
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence unsigned int namelen:8; /* range is 1..255 */
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence unsigned int offsetlen:8; /* range is 1..128 */
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence unsigned int padbytes:9; /* range is 0..380 */
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence * These values are used in the RBT DB implementation. The
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence * appropriate node lock must be held before accessing them.
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence unsigned int dirty:1;
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence unsigned int locknum:DNS_RBT_LOCKLENGTH;
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence unsigned int references:DNS_RBT_REFLENGTH;
bf668d00172e2308da0e01048284d7efa85495b1David Lawrence } dns_rbtnode_t;