red-black revision bf668d00172e2308da0e01048284d7efa85495b1
d6fa26d0adaec6c910115be34fe7a5a5f402c14fMark Andrews Red-Black Tree Implementation Notes
5347c0fcb04eaea19d9f39795646239f487c6207Tinderbox UserBIND9's basic name storage mechanism is to use a modified form of
5347c0fcb04eaea19d9f39795646239f487c6207Tinderbox Userbalanced binary tree known as a red-black tree. Red-black trees
5347c0fcb04eaea19d9f39795646239f487c6207Tinderbox Userprovide for relatively efficient storage, retrieval and removal of
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userdata while maintaining the lexical order of all stored keys, a
d6fa26d0adaec6c910115be34fe7a5a5f402c14fMark Andrewsnecessary function for DNS security.
fd2597f75693a2279fdf588bd40dfe2407c42028Tinderbox UserA red-black tree is a balanced binary tree named for the coloring that
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Huntis done in the tree, identifying each node as either red or black.
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserThere are two simple rules for maintaining the color of nodes:
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Hunt (1) A red node has only black children.
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Hunt (2) The path from the root to any leaf node always includes the
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User same number of black nodes.
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserWhenever a key is added or removed, adjustments are made to adhere to
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userthose two rules. These adjustments are relatively cheap to make but
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Usermaintain the balance of the tree, thus making for efficient addition,
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userlookup and deletion operations, all of which are O(log N). The color
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userof a node is not relevant to external users of the tree; it is needed
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Huntonly to maintain the balance of the tree.
14a656f94b1fd0ababd84a772228dfa52276ba15Evan HuntFor more information on basic red-black trees, see _Introduction to
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserAlgorithms_, Cormen, Leiserson, and Rivest, MIT Press / McGraw Hill,
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User1990, ISBN 0-262-03141-8, chapter 14.
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserIn BIND9, the red-black tree implementation uses DNS names as keys,
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userand can store arbitrary data with each key value. "name" and "key"
fd2597f75693a2279fdf588bd40dfe2407c42028Tinderbox Userare used interchangably in this document.
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserThe basic red-black tree algorithm is further adapted for use in BIND9
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userto incorporate the notion of hierarchy, creating a tree of red-black
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Usertrees. Where there is more than one name with a common suffix, all
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Usernames with that suffix are stored in their own red-black tree, with a
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userdown pointer from the suffix locating the subtree.
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserFor example, consider storing the following names:
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserNo matter which order the keys were added, this would result in a tree
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userthat can be visualized as:
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserThis tree shows that when there is no key for a particular label, and
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userwhen there is only one known label for its immediate subordinate, then
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Usermultiple labels can appear in a single node, such as at d.e.f and g.h.
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserIt also demonstrates that there can be more nodes in the tree of trees
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userthan there are actual keys (which degrades the O(log N) performance
9700e6d72c3ba0d0c567969ab97d9eff202656d4Tinderbox Usermarginally); the nodes at d.e.f and w.y do not represent keys.
9700e6d72c3ba0d0c567969ab97d9eff202656d4Tinderbox UserAs an aside, remember that when ordering DNS names, labels are
9700e6d72c3ba0d0c567969ab97d9eff202656d4Tinderbox Userexamined from the right, therefore w.y sorts after x and before z.
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserWhen bitfields are fully supported (they aren't yet) then a split can
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Useroccur not only on a regular label boundary, but also between any two
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userbits. The common-suffix rules will be applied to keep as many bits
7e71f05d8643aca84914437c900cb716444507e4Tinderbox Usertogether as possible.
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserIn the current implementation of the tree of trees, a node is
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userconsidered to "formally" exist only if it has data associated with
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userit. So if the above tree then had the key d.e.f added to it, the
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Useroperation would succeed rather than getting an "already exists"
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserAlong the same lines, if a key is added with a name which is a proper
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Usersuperdomain of the name stored in an existing node, the operation will
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Usersucceed by splitting the existing node into one node that is the key
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userand another node that is the remaining parts of the name. Adding e.f
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userto the above tree results in the top level red-black tree having a
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Usernode named e.f where the current d.e.f is, and a down pointer from
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Huntd.e.f to a "tree" of a single node named d. The down pointer from d
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userwould be kept to the level which has x, w.y, and z.
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserA similar split of d.e.f would occur if the name k.e.f were added.
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserThe top level tree would have the node e.f with a down pointer to a
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userlevel that had both d and k, and d would continue to have its down
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userpointer to the x, w.y and z level.
14a656f94b1fd0ababd84a772228dfa52276ba15Evan HuntIt is guaranteed when splitting that external references to the node
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userthat is split will remain valid --- in the previous examples, anything
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userthat was pointing to the node that was d.e.f will still point to the
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Usernode that is now just d.
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserWhen deleting keys, nodes can be rejoined. If both of p.w.y.d.e.f and
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Huntq.w.y.d.e.f were removed from the example tree, the node named w.y
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userwould become o.w.y. Unlike splitting, it is _not_ guaranteed that
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userexternal references remain consistent; sometimes they will, sometimes
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userthey won't. Also, note that deletion is not perfectly symmetric with
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Huntaddition. If you "undo" the last addition with a deletion of the same
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userkey then the tree of trees is not guaranteed to have exactly the same
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userstructure as it had prior to the addition. Sometimes, but not always.
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserRejoining does not happen if it would violate any of the rules that
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Usercause a split. o would not be rejoined with w.y if w.y had data
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userassociated with the key; o would remain as a single node on its own
7e71f05d8643aca84914437c900cb716444507e4Tinderbox Userlevel. This emphasizes the rule that a node is considered to formally
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userexist only if data is associated with it, because even if w.y.d.e.f
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userhad been explicitly added as a key but with no data, then o would
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userstill be merged with the w.y node when p and q were deleted.
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserSearching for a node generally returns one of three possible results:
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Usereither the key is found, a superdomain (partial match) of the key is
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userfound, or no part of the key is found. The first and last are rather
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userobvious, and the second result basically means that a hierarchically
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userenclosing name is found; e.g, searching for bb.rc.vix.com turned up
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userrc.vix.com, but not the full name.
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserNo locking is done within the RBT library. @@@
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserEXTERNAL PROGRAMMATIC DETAILS
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserThis section details the functions used to interact with the BIND9
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userred-black tree library, or RBT for short.
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserA source file that will be using RBT will usually need to include
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User<dns/rbt.h>. This header file automatically includes <isc/result.h),
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserThe rbt.h file has more complete descriptions of each of the functions
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Usernamed here, including what is required for each argument, what each
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userfunction ensures (and might not ensure) will occur, and the full range
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userof possible results for each call. Note well: if a function returns a
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userdns_result_t rather than void, it definitely means there is something
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userthat can go possibly wrong in the function and it should be checked by
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserA new tree of trees must be initialized using:
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User dns_result_t dns_rbt_create(isc_mem_t *mctx, void (*deleter)(void *, void *),
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User void *deleter_arg, dns_rbt_t **rbtp);
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserThe memory context, mctx, must be a non-null pointer that was
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userinitialized with isc_mem_create(). The deleter argument, if non-null,
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Usershould point to a function that is responsible for cleaning up any
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Usermemory associated with the data pointer of a node when the node is
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userdeleted. It is passed the deleted node's data pointer as its first
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userargument and deleter_arg as its second argument.
14a656f94b1fd0ababd84a772228dfa52276ba15Evan HuntAfter initializing an RBT manager, to add keys to the tree, use:
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox User dns_result_t dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data);
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserThe name _must_ be an absolute name. It is not required that the data
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userpointer be non-null, but it is recommended that it point to something,
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Usereven just invalid memory, because of the various searching and
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userdeletion issues described in the previous section. The RBT code will
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Usernot attempt to dereference the pointer.
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserTo find a key in the tree, use:
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox User dns_result_t dns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, void **data);
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserThe data parameter must not be NULL, but *data must be NULL. The
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userresult will be either DNS_R_SUCCESS, DNS_R_PARTIALMATCH or
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserDNS_R_NOTFOUND. In the first case, an exact match was found for the
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Username and there was an associate data pointer, which is returned via
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userthe data parameter. A partial match results when the name has not
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userbeen found but a superdomain name, with data, does exist; then the
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userdata for that name is returned in the data parameter. If no data is
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userfound for the name or a superdomain, *data will remain NULL.
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserINTERNAL PROGRAMMATIC DETAILS
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserThis section is mainly relevant to the RBT DB implementation. It is
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userhighly recommended that programmers using the RBT library stick to the
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userfunctions named in the previous section.
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserThe dns_rbt_addname and dns_rbt_findname functions named in the
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userprevious section are wrappers around dns_rbt_addnode and
9d557856c2a19ec95ee73245f60a92f8675cf5baTinderbox Userdns_rbt_findnode. The *node functions for the most part do not
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Userparticularly care whether a node has an associated data pointer or
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Usernot, whereas the *name functions do. The one exception to this is
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userthat when a PARTIALMATCH is returned for a search, the indicated node
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Useris the deepest match that has data, rather than just the deepest
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox Usermatch. This inconsistency could be addressed by adding another
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userparameter to dns_rbt_findnode.
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox UserEach node in the tree of trees is represented by the following structure:
14a656f94b1fd0ababd84a772228dfa52276ba15Evan Hunt typedef struct dns_rbtnode {
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User struct dns_rbtnode *left;
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User struct dns_rbtnode *right;
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User struct dns_rbtnode *down;
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox User * The following bitfields add up to a total bitwidth of 32.
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User * The range of values necessary for each item is indicated,
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox User * but in the case of "attributes" the field is wider to accomodate
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox User * possible future expansion. "offsetlen" could be one bit
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User * narrower by always adjusting its value by 1 to find the real
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User * offsetlen, but doing so does not gain anything (except perhaps
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User * another bit for "attributes", which doesn't yet need any more).
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox User unsigned int color:1; /* range is 0..1 */
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User unsigned int attributes:6; /* range is 0..2 */
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox User unsigned int namelen:8; /* range is 1..255 */
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox User unsigned int offsetlen:8; /* range is 1..128 */
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User unsigned int padbytes:9; /* range is 0..380 */
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User * These values are used in the RBT DB implementation. The
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User * appropriate node lock must be held before accessing them.
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox User unsigned int dirty:1;
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User unsigned int locknum:DNS_RBT_LOCKLENGTH;
9a5087bf58f651bfff841192aba5afd06760d6ceTinderbox User unsigned int references:DNS_RBT_REFLENGTH;
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox User } dns_rbtnode_t;