diff options
Diffstat (limited to '')
| -rw-r--r-- | lib/dns/include/dns/rbt.h | 1144 |
1 files changed, 1144 insertions, 0 deletions
diff --git a/lib/dns/include/dns/rbt.h b/lib/dns/include/dns/rbt.h new file mode 100644 index 0000000..67ac3e4 --- /dev/null +++ b/lib/dns/include/dns/rbt.h @@ -0,0 +1,1144 @@ +/* + * Copyright (C) Internet Systems Consortium, Inc. ("ISC") + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * See the COPYRIGHT file distributed with this work for additional + * information regarding copyright ownership. + */ + + +#ifndef DNS_RBT_H +#define DNS_RBT_H 1 + +/*! \file dns/rbt.h */ + +#include <inttypes.h> +#include <stdbool.h> + +#include <isc/assertions.h> +#include <isc/crc64.h> +#include <isc/lang.h> +#include <isc/magic.h> +#include <isc/refcount.h> + +#include <dns/types.h> + +ISC_LANG_BEGINDECLS + +#define DNS_RBT_USEHASH 1 + +/*@{*/ +/*% + * Option values for dns_rbt_findnode() and dns_rbt_findname(). + * These are used to form a bitmask. + */ +#define DNS_RBTFIND_NOOPTIONS 0x00 +#define DNS_RBTFIND_EMPTYDATA 0x01 +#define DNS_RBTFIND_NOEXACT 0x02 +#define DNS_RBTFIND_NOPREDECESSOR 0x04 +/*@}*/ + +#ifndef DNS_RBT_USEISCREFCOUNT +#ifdef ISC_REFCOUNT_HAVEATOMIC +#define DNS_RBT_USEISCREFCOUNT 1 +#endif +#endif + +#define DNS_RBT_USEMAGIC 1 + +/* + * These should add up to 30. + */ +#define DNS_RBT_LOCKLENGTH 10 +#define DNS_RBT_REFLENGTH 20 + +#define DNS_RBTNODE_MAGIC ISC_MAGIC('R','B','N','O') +#if DNS_RBT_USEMAGIC +#define DNS_RBTNODE_VALID(n) ISC_MAGIC_VALID(n, DNS_RBTNODE_MAGIC) +#else +#define DNS_RBTNODE_VALID(n) true +#endif + +/*% + * This is the structure that is used for each node in the red/black + * tree of trees. NOTE WELL: the implementation manages this as a variable + * length structure, with the actual wire-format name and other data + * appended to this structure. Allocating a contiguous block of memory for + * multiple dns_rbtnode structures will not work. + */ +typedef struct dns_rbtnode dns_rbtnode_t; +enum { + DNS_RBT_NSEC_NORMAL=0, /* in main tree */ + DNS_RBT_NSEC_HAS_NSEC=1, /* also has node in nsec tree */ + DNS_RBT_NSEC_NSEC=2, /* in nsec tree */ + DNS_RBT_NSEC_NSEC3=3 /* in nsec3 tree */ +}; +struct dns_rbtnode { +#if DNS_RBT_USEMAGIC + unsigned int magic; +#endif + /*@{*/ + /*! + * The following bitfields add up to a total bitwidth of 32. + * The range of values necessary for each item is indicated, + * but in the case of "attributes" the field is wider to accommodate + * possible future expansion. + * + * In each case below the "range" indicated is what's _necessary_ for + * the bitfield to hold, not what it actually _can_ hold. + * + * Note: Tree lock must be held before modifying these + * bit-fields. + * + * Note: The two "unsigned int :0;" unnamed bitfields on either + * side of the bitfields below are scaffolding that border the + * set of bitfields which are accessed after acquiring the tree + * lock. Please don't insert any other bitfield members between + * the unnamed bitfields unless they should also be accessed + * after acquiring the tree lock. + */ + unsigned int :0; /* start of bitfields c/o tree lock */ + unsigned int is_root : 1; /*%< range is 0..1 */ + unsigned int color : 1; /*%< range is 0..1 */ + unsigned int find_callback : 1; /*%< range is 0..1 */ + unsigned int attributes : 3; /*%< range is 0..2 */ + unsigned int nsec : 2; /*%< range is 0..3 */ + unsigned int namelen : 8; /*%< range is 1..255 */ + unsigned int offsetlen : 8; /*%< range is 1..128 */ + unsigned int oldnamelen : 8; /*%< range is 1..255 */ + /*@}*/ + + /* flags needed for serialization to file*/ + unsigned int is_mmapped : 1; + unsigned int parent_is_relative : 1; + unsigned int left_is_relative : 1; + unsigned int right_is_relative : 1; + unsigned int down_is_relative : 1; + unsigned int data_is_relative : 1; + + /* node needs to be cleaned from rpz */ + unsigned int rpz : 1; + unsigned int :0; /* end of bitfields c/o tree lock */ + +#ifdef DNS_RBT_USEHASH + unsigned int hashval; + dns_rbtnode_t *uppernode; + dns_rbtnode_t *hashnext; +#endif + dns_rbtnode_t *parent; + dns_rbtnode_t *left; + dns_rbtnode_t *right; + dns_rbtnode_t *down; + + /*% + * Used for LRU cache. This linked list is used to mark nodes which + * have no data any longer, but we cannot unlink at that exact moment + * because we did not or could not obtain a write lock on the tree. + */ + ISC_LINK(dns_rbtnode_t) deadlink; + + /*@{*/ + /*! + * These values are used in the RBT DB implementation. The appropriate + * node lock must be held before accessing them. + * + * Note: The two "unsigned int :0;" unnamed bitfields on either + * side of the bitfields below are scaffolding that border the + * set of bitfields which are accessed after acquiring the node + * lock. Please don't insert any other bitfield members between + * the unnamed bitfields unless they should also be accessed + * after acquiring the node lock. + * + * NOTE: Do not merge these fields into bitfields above, as + * they'll all be put in the same qword that could be accessed + * without the node lock as it shares the qword with other + * members. Leave these members here so that they occupy a + * separate region of memory. + */ + void *data; + unsigned int :0; /* start of bitfields c/o node lock */ + unsigned int dirty:1; + unsigned int wild:1; + unsigned int locknum:DNS_RBT_LOCKLENGTH; +#ifndef DNS_RBT_USEISCREFCOUNT + unsigned int references:DNS_RBT_REFLENGTH; +#endif + unsigned int :0; /* end of bitfields c/o node lock */ +#ifdef DNS_RBT_USEISCREFCOUNT + isc_refcount_t references; /* note that this is not in the bitfield */ +#endif + /*@}*/ +}; + +typedef isc_result_t (*dns_rbtfindcallback_t)(dns_rbtnode_t *node, + dns_name_t *name, + void *callback_arg); + +typedef isc_result_t (*dns_rbtdatawriter_t)(FILE *file, + unsigned char *data, + void *arg, + uint64_t *crc); + +typedef isc_result_t (*dns_rbtdatafixer_t)(dns_rbtnode_t *rbtnode, + void *base, size_t offset, + void *arg, uint64_t *crc); + +typedef void (*dns_rbtdeleter_t)(void *, void *); + +/***** + ***** Chain Info + *****/ + +/*! + * A chain is used to keep track of the sequence of nodes to reach any given + * node from the root of the tree. Originally nodes did not have parent + * pointers in them (for memory usage reasons) so there was no way to find + * the path back to the root from any given node. Now that nodes have parent + * pointers, chains might be going away in a future release, though the + * movement functionality would remain. + * + * Chains may be used to iterate over a tree of trees. After setting up the + * chain's structure using dns_rbtnodechain_init(), it needs to be initialized + * to point to the lexically first or lexically last node in the tree of trees + * using dns_rbtnodechain_first() or dns_rbtnodechain_last(), respectively. + * Calling dns_rbtnodechain_next() or dns_rbtnodechain_prev() then moves the + * chain over to the next or previous node, respectively. + * + * In any event, parent information, whether via parent pointers or chains, is + * necessary information for iterating through the tree or for basic internal + * tree maintenance issues (ie, the rotations that are done to rebalance the + * tree when a node is added). The obvious implication of this is that for a + * chain to remain valid, the tree has to be locked down against writes for the + * duration of the useful life of the chain, because additions or removals can + * change the path from the root to the node the chain has targeted. + * + * The dns_rbtnodechain_ functions _first, _last, _prev and _next all take + * dns_name_t parameters for the name and the origin, which can be NULL. If + * non-NULL, 'name' will end up pointing to the name data and offsets that are + * stored at the node (and thus it will be read-only), so it should be a + * regular dns_name_t that has been initialized with dns_name_init. When + * 'origin' is non-NULL, it will get the name of the origin stored in it, so it + * needs to have its own buffer space and offsets, which is most easily + * accomplished with a dns_fixedname_t. It is _not_ necessary to reinitialize + * either 'name' or 'origin' between calls to the chain functions. + * + * NOTE WELL: even though the name data at the root of the tree of trees will + * be absolute (typically just "."), it will will be made into a relative name + * with an origin of "." -- an empty name when the node is ".". This is + * because a common on operation on 'name' and 'origin' is to use + * dns_name_concatenate() on them to generate the complete name. An empty name + * can be detected when dns_name_countlabels == 0, and is printed by + * dns_name_totext()/dns_name_format() as "@", consistent with RFC1035's + * definition of "@" as the current origin. + * + * dns_rbtnodechain_current is similar to the _first, _last, _prev and _next + * functions but additionally can provide the node to which the chain points. + */ + +/*% + * The number of level blocks to allocate at a time. Currently the maximum + * number of levels is allocated directly in the structure, but future + * revisions of this code might have a static initial block with dynamic + * growth. Allocating space for 256 levels when the tree is almost never that + * deep is wasteful, but it's not clear that it matters, since the waste is + * only 2MB for 1000 concurrently active chains on a system with 64-bit + * pointers. + */ +#define DNS_RBT_LEVELBLOCK 254 + +typedef struct dns_rbtnodechain { + unsigned int magic; + isc_mem_t * mctx; + /*% + * The terminal node of the chain. It is not in levels[]. + * This is ostensibly private ... but in a pinch it could be + * used tell that the chain points nowhere without needing to + * call dns_rbtnodechain_current(). + */ + dns_rbtnode_t * end; + /*% + * The maximum number of labels in a name is 128; bitstrings mean + * a conceptually very large number (which I have not bothered to + * compute) of logical levels because splitting can potentially occur + * at each bit. However, DNSSEC restricts the number of "logical" + * labels in a name to 255, meaning only 254 pointers are needed + * in the worst case. + */ + dns_rbtnode_t * levels[DNS_RBT_LEVELBLOCK]; + /*% + * level_count indicates how deep the chain points into the + * tree of trees, and is the index into the levels[] array. + * Thus, levels[level_count - 1] is the last level node stored. + * A chain that points to the top level of the tree of trees has + * a level_count of 0, the first level has a level_count of 1, and + * so on. + */ + unsigned int level_count; + /*% + * level_matches tells how many levels matched above the node + * returned by dns_rbt_findnode(). A match (partial or exact) found + * in the first level thus results in level_matches being set to 1. + * This is used by the rbtdb to set the start point for a recursive + * search of superdomains until the RR it is looking for is found. + */ + unsigned int level_matches; +} dns_rbtnodechain_t; + +/***** + ***** Public interfaces. + *****/ +isc_result_t +dns_rbt_create(isc_mem_t *mctx, dns_rbtdeleter_t deleter, + void *deleter_arg, dns_rbt_t **rbtp); +/*%< + * Initialize a red-black tree of trees. + * + * Notes: + *\li The deleter argument, if non-null, points to a function that is + * responsible for cleaning up any memory associated with the data + * pointer of a node when the node is deleted. It is passed the + * deleted node's data pointer as its first argument and deleter_arg + * as its second argument. + * + * Requires: + * \li mctx is a pointer to a valid memory context. + *\li rbtp != NULL && *rbtp == NULL + *\li arg == NULL iff deleter == NULL + * + * Ensures: + *\li If result is ISC_R_SUCCESS: + * *rbtp points to a valid red-black tree manager + * + *\li If result is failure: + * *rbtp does not point to a valid red-black tree manager. + * + * Returns: + *\li #ISC_R_SUCCESS Success + *\li #ISC_R_NOMEMORY Resource limit: Out of Memory + */ + +isc_result_t +dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data); +/*%< + * Add 'name' to the tree of trees, associated with 'data'. + * + * Notes: + *\li 'data' is never required to be non-NULL, but specifying it + * when the name is added is faster than searching for 'name' + * again and then setting the data pointer. The lack of a data pointer + * for a node also has other ramifications regarding whether + * dns_rbt_findname considers a node to exist, or dns_rbt_deletename + * joins nodes. + * + * Requires: + *\li rbt is a valid rbt manager. + *\li dns_name_isabsolute(name) == TRUE + * + * Ensures: + *\li 'name' is not altered in any way. + * + *\li Any external references to nodes in the tree are unaffected by + * node splits that are necessary to insert the new name. + * + *\li If result is #ISC_R_SUCCESS: + * 'name' is findable in the red/black tree of trees in O(log N). + * The data pointer of the node for 'name' is set to 'data'. + * + *\li If result is #ISC_R_EXISTS or #ISC_R_NOSPACE: + * The tree of trees is unaltered. + * + *\li If result is #ISC_R_NOMEMORY: + * No guarantees. + * + * Returns: + *\li #ISC_R_SUCCESS Success + *\li #ISC_R_EXISTS The name already exists with associated data. + *\li #ISC_R_NOSPACE The name had more logical labels than are allowed. + *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory + */ + +isc_result_t +dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep); + +/*%< + * Just like dns_rbt_addname, but returns the address of the node. + * + * Requires: + *\li rbt is a valid rbt structure. + *\li dns_name_isabsolute(name) == TRUE + *\li nodep != NULL && *nodep == NULL + * + * Ensures: + *\li 'name' is not altered in any way. + * + *\li Any external references to nodes in the tree are unaffected by + * node splits that are necessary to insert the new name. + * + *\li If result is ISC_R_SUCCESS: + * 'name' is findable in the red/black tree of trees in O(log N). + * *nodep is the node that was added for 'name'. + * + *\li If result is ISC_R_EXISTS: + * The tree of trees is unaltered. + * *nodep is the existing node for 'name'. + * + *\li If result is ISC_R_NOMEMORY: + * No guarantees. + * + * Returns: + *\li #ISC_R_SUCCESS Success + *\li #ISC_R_EXISTS The name already exists, possibly without data. + *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory + */ + +isc_result_t +dns_rbt_findname(dns_rbt_t *rbt, const dns_name_t *name, unsigned int options, + dns_name_t *foundname, void **data); +/*%< + * Get the data pointer associated with 'name'. + * + * Notes: + *\li When #DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is + * returned (also subject to #DNS_RBTFIND_EMPTYDATA), even when there is + * an exact match in the tree. + * + *\li A node that has no data is considered not to exist for this function, + * unless the #DNS_RBTFIND_EMPTYDATA option is set. + * + * Requires: + *\li rbt is a valid rbt manager. + *\li dns_name_isabsolute(name) == TRUE + *\li data != NULL && *data == NULL + * + * Ensures: + *\li 'name' and the tree are not altered in any way. + * + *\li If result is ISC_R_SUCCESS: + * *data is the data associated with 'name'. + * + *\li If result is DNS_R_PARTIALMATCH: + * *data is the data associated with the deepest superdomain + * of 'name' which has data. + * + *\li If result is ISC_R_NOTFOUND: + * Neither the name nor a superdomain was found with data. + * + * Returns: + *\li #ISC_R_SUCCESS Success + *\li #DNS_R_PARTIALMATCH Superdomain found with data + *\li #ISC_R_NOTFOUND No match + *\li #ISC_R_NOSPACE Concatenating nodes to form foundname failed + */ + +isc_result_t +dns_rbt_findnode(dns_rbt_t *rbt, const dns_name_t *name, dns_name_t *foundname, + dns_rbtnode_t **node, dns_rbtnodechain_t *chain, + unsigned int options, dns_rbtfindcallback_t callback, + void *callback_arg); +/*%< + * Find the node for 'name'. + * + * Notes: + *\li A node that has no data is considered not to exist for this function, + * unless the DNS_RBTFIND_EMPTYDATA option is set. This applies to both + * exact matches and partial matches. + * + *\li If the chain parameter is non-NULL, then the path through the tree + * to the DNSSEC predecessor of the searched for name is maintained, + * unless the DNS_RBTFIND_NOPREDECESSOR or DNS_RBTFIND_NOEXACT option + * is used. (For more details on those options, see below.) + * + *\li If there is no predecessor, then the chain will point to nowhere, as + * indicated by chain->end being NULL or dns_rbtnodechain_current + * returning ISC_R_NOTFOUND. Note that in a normal Internet DNS RBT + * there will always be a predecessor for all names except the root + * name, because '.' will exist and '.' is the predecessor of + * everything. But you can certainly construct a trivial tree and a + * search for it that has no predecessor. + * + *\li Within the chain structure, the 'levels' member of the structure holds + * the root node of each level except the first. + * + *\li The 'level_count' of the chain indicates how deep the chain to the + * predecessor name is, as an index into the 'levels[]' array. It does + * not count name elements, per se, but only levels of the tree of trees, + * the distinction arising because multiple labels from a name can be + * stored on only one level. It is also does not include the level + * that has the node, since that level is not stored in levels[]. + * + *\li The chain's 'level_matches' is not directly related to the predecessor. + * It is the number of levels above the level of the found 'node', + * regardless of whether it was a partial match or exact match. When + * the node is found in the top level tree, or no node is found at all, + * level_matches is 0. + * + *\li When DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is + * returned (also subject to DNS_RBTFIND_EMPTYDATA), even when + * there is an exact match in the tree. In this case, the chain + * will not point to the DNSSEC predecessor, but will instead point + * to the exact match, if there was any. Thus the preceding paragraphs + * should have "exact match" substituted for "predecessor" to describe + * how the various elements of the chain are set. This was done to + * ensure that the chain's state was sane, and to prevent problems that + * occurred when running the predecessor location code under conditions + * it was not designed for. It is not clear *where* the chain should + * point when DNS_RBTFIND_NOEXACT is set, so if you end up using a chain + * with this option because you want a particular node, let us know + * where you want the chain pointed, so this can be made more firm. + * + * Requires: + *\li rbt is a valid rbt manager. + *\li dns_name_isabsolute(name) == TRUE. + *\li node != NULL && *node == NULL. + *\li #DNS_RBTFIND_NOEXACT and DNS_RBTFIND_NOPREDECESSOR are mutually + * exclusive. + * + * Ensures: + *\li 'name' and the tree are not altered in any way. + * + *\li If result is ISC_R_SUCCESS: + *\verbatim + * *node is the terminal node for 'name'. + + * 'foundname' and 'name' represent the same name (though not + * the same memory). + + * 'chain' points to the DNSSEC predecessor, if any, of 'name'. + * + * chain->level_matches and chain->level_count are equal. + *\endverbatim + * + * If result is DNS_R_PARTIALMATCH: + *\verbatim + * *node is the data associated with the deepest superdomain + * of 'name' which has data. + * + * 'foundname' is the name of deepest superdomain (which has + * data, unless the DNS_RBTFIND_EMPTYDATA option is set). + * + * 'chain' points to the DNSSEC predecessor, if any, of 'name'. + *\endverbatim + * + *\li If result is ISC_R_NOTFOUND: + *\verbatim + * Neither the name nor a superdomain was found. *node is NULL. + * + * 'chain' points to the DNSSEC predecessor, if any, of 'name'. + * + * chain->level_matches is 0. + *\endverbatim + * + * Returns: + *\li #ISC_R_SUCCESS Success + *\li #DNS_R_PARTIALMATCH Superdomain found with data + *\li #ISC_R_NOTFOUND No match, or superdomain with no data + *\li #ISC_R_NOSPACE Concatenating nodes to form foundname failed + */ + +isc_result_t +dns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, bool recurse); +/*%< + * Delete 'name' from the tree of trees. + * + * Notes: + *\li When 'name' is removed, if recurse is true then all of its + * subnames are removed too. + * + * Requires: + *\li rbt is a valid rbt manager. + *\li dns_name_isabsolute(name) == TRUE + * + * Ensures: + *\li 'name' is not altered in any way. + * + *\li Does NOT ensure that any external references to nodes in the tree + * are unaffected by node joins. + * + *\li If result is ISC_R_SUCCESS: + * 'name' does not appear in the tree with data; however, + * the node for the name might still exist which can be + * found with dns_rbt_findnode (but not dns_rbt_findname). + * + *\li If result is ISC_R_NOTFOUND: + * 'name' does not appear in the tree with data, because + * it did not appear in the tree before the function was called. + * + *\li If result is something else: + * See result codes for dns_rbt_findnode (if it fails, the + * node is not deleted) or dns_rbt_deletenode (if it fails, + * the node is deleted, but the tree is not optimized when + * it could have been). + * + * Returns: + *\li #ISC_R_SUCCESS Success + *\li #ISC_R_NOTFOUND No match + *\li something_else Any return code from dns_rbt_findnode except + * DNS_R_PARTIALMATCH (which causes ISC_R_NOTFOUND + * to be returned instead), and any code from + * dns_rbt_deletenode. + */ + +isc_result_t +dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, bool recurse); +/*%< + * Delete 'node' from the tree of trees. + * + * Notes: + *\li When 'node' is removed, if recurse is true then all nodes + * in levels down from it are removed too. + * + * Requires: + *\li rbt is a valid rbt manager. + *\li node != NULL. + * + * Ensures: + *\li Does NOT ensure that any external references to nodes in the tree + * are unaffected by node joins. + * + *\li If result is ISC_R_SUCCESS: + * 'node' does not appear in the tree with data; however, + * the node might still exist if it serves as a pointer to + * a lower tree level as long as 'recurse' was false, hence + * the node could can be found with dns_rbt_findnode when + * that function's empty_data_ok parameter is true. + * + *\li If result is ISC_R_NOMEMORY or ISC_R_NOSPACE: + * The node was deleted, but the tree structure was not + * optimized. + * + * Returns: + *\li #ISC_R_SUCCESS Success + *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory when joining nodes. + *\li #ISC_R_NOSPACE dns_name_concatenate failed when joining nodes. + */ + +void +dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name); +/*%< + * Convert the sequence of labels stored at 'node' into a 'name'. + * + * Notes: + *\li This function does not return the full name, from the root, but + * just the labels at the indicated node. + * + *\li The name data pointed to by 'name' is the information stored + * in the node, not a copy. Altering the data at this pointer + * will likely cause grief. + * + * Requires: + * \li name->offsets == NULL + * + * Ensures: + * \li 'name' is DNS_NAMEATTR_READONLY. + * + * \li 'name' will point directly to the labels stored after the + * dns_rbtnode_t struct. + * + * \li 'name' will have offsets that also point to the information stored + * as part of the node. + */ + +isc_result_t +dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name); +/*%< + * Like dns_rbt_namefromnode, but returns the full name from the root. + * + * Notes: + * \li Unlike dns_rbt_namefromnode, the name will not point directly + * to node data. Rather, dns_name_concatenate will be used to copy + * the name data from each node into the 'name' argument. + * + * Requires: + * \li name != NULL + * \li name has a dedicated buffer. + * + * Returns: + * \li ISC_R_SUCCESS + * \li ISC_R_NOSPACE (possible via dns_name_concatenate) + * \li DNS_R_NAMETOOLONG (possible via dns_name_concatenate) + */ + +char * +dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname, + unsigned int size); +/*%< + * Format the full name of a node for printing, using dns_name_format(). + * + * Notes: + * \li 'size' is the length of the printname buffer. This should be + * DNS_NAME_FORMATSIZE or larger. + * + * Requires: + * \li node and printname are not NULL. + * + * Returns: + * \li The 'printname' pointer. + */ + +unsigned int +dns_rbt_nodecount(dns_rbt_t *rbt); +/*%< + * Obtain the number of nodes in the tree of trees. + * + * Requires: + * \li rbt is a valid rbt manager. + */ + +size_t +dns_rbt_hashsize(dns_rbt_t *rbt); +/*%< + * Obtain the current number of buckets in the 'rbt' hash table. + * + * Requires: + * \li rbt is a valid rbt manager. + */ + +void +dns_rbt_destroy(dns_rbt_t **rbtp); +isc_result_t +dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum); +/*%< + * Stop working with a red-black tree of trees. + * If 'quantum' is zero then the entire tree will be destroyed. + * If 'quantum' is non zero then up to 'quantum' nodes will be destroyed + * allowing the rbt to be incrementally destroyed by repeated calls to + * dns_rbt_destroy2(). Once dns_rbt_destroy2() has been called no other + * operations than dns_rbt_destroy()/dns_rbt_destroy2() should be + * performed on the tree of trees. + * + * Requires: + * \li *rbt is a valid rbt manager. + * + * Ensures on ISC_R_SUCCESS: + * \li All space allocated by the RBT library has been returned. + * + * \li *rbt is invalidated as an rbt manager. + * + * Returns: + * \li ISC_R_SUCCESS + * \li ISC_R_QUOTA if 'quantum' nodes have been destroyed. + */ + +off_t +dns_rbt_serialize_align(off_t target); +/*%< + * Align the provided integer to a pointer-size boundary. + * This should be used if, during serialization of data to a will-be + * mmap()ed file, a pointer alignment is needed for some data. + */ + +isc_result_t +dns_rbt_serialize_tree(FILE *file, dns_rbt_t *rbt, + dns_rbtdatawriter_t datawriter, + void *writer_arg, off_t *offset); +/*%< + * Write out the RBT structure and its data to a file. + * + * Notes: + * \li The file must be an actual file which allows seek() calls, so it cannot + * be a stream. Returns ISC_R_INVALIDFILE if not. + */ + +isc_result_t +dns_rbt_deserialize_tree(void *base_address, size_t filesize, + off_t header_offset, isc_mem_t *mctx, + dns_rbtdeleter_t deleter, void *deleter_arg, + dns_rbtdatafixer_t datafixer, void *fixer_arg, + dns_rbtnode_t **originp, dns_rbt_t **rbtp); +/*%< + * Read a RBT structure and its data from a file. + * + * If 'originp' is not NULL, then it is pointed to the root node of the RBT. + * + * Notes: + * \li The file must be an actual file which allows seek() calls, so it cannot + * be a stream. This condition is not checked in the code. + */ + +void +dns_rbt_printtext(dns_rbt_t *rbt, + void (*data_printer)(FILE *, void *), FILE *f); +/*%< + * Print an ASCII representation of the internal structure of the red-black + * tree of trees to the passed stream. + * + * data_printer is a callback function that is called to print the data + * in a node. It should print it to the passed FILE stream. + * + * Notes: + * \li The name stored at each node, along with the node's color, is printed. + * Then the down pointer, left and right pointers are displayed + * recursively in turn. NULL down pointers are silently omitted; + * NULL left and right pointers are printed. + */ + +void +dns_rbt_printdot(dns_rbt_t *rbt, bool show_pointers, FILE *f); +/*%< + * Print a GraphViz dot representation of the internal structure of the + * red-black tree of trees to the passed stream. + * + * If show_pointers is TRUE, pointers are also included in the generated + * graph. + * + * Notes: + * \li The name stored at each node, along with the node's color is displayed. + * Then the down pointer, left and right pointers are displayed + * recursively in turn. NULL left, right and down pointers are + * silently omitted. + */ + +void +dns_rbt_printnodeinfo(dns_rbtnode_t *n, FILE *f); +/*%< + * Print out various information about a node + * + * Requires: + *\li 'n' is a valid pointer. + * + *\li 'f' points to a valid open FILE structure that allows writing. + */ + + +size_t +dns__rbt_getheight(dns_rbt_t *rbt); +/*%< + * Return the maximum height of sub-root nodes found in the red-black + * forest. + * + * The height of a node is defined as the number of nodes in the longest + * path from the node to a leaf. For each subtree in the forest, this + * function determines the height of its root node. Then it returns the + * maximum such height in the forest. + * + * Note: This function exists for testing purposes. Non-test code must + * not use it. + * + * Requires: + * \li rbt is a valid rbt manager. + */ + +bool +dns__rbt_checkproperties(dns_rbt_t *rbt); +/*%< + * Check red-black properties of the forest. + * + * Note: This function exists for testing purposes. Non-test code must + * not use it. + * + * Requires: + * \li rbt is a valid rbt manager. + */ + +size_t +dns__rbtnode_getdistance(dns_rbtnode_t *node); +/*%< + * Return the distance (in nodes) from the node to its upper node of its + * subtree. The root node has a distance of 1. A child of the root node + * has a distance of 2. + */ + +/***** + ***** Chain Functions + *****/ + +void +dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx); +/*%< + * Initialize 'chain'. + * + * Requires: + *\li 'chain' is a valid pointer. + * + *\li 'mctx' is a valid memory context. + * + * Ensures: + *\li 'chain' is suitable for use. + */ + +void +dns_rbtnodechain_reset(dns_rbtnodechain_t *chain); +/*%< + * Free any dynamic storage associated with 'chain', and then reinitialize + * 'chain'. + * + * Requires: + *\li 'chain' is a valid pointer. + * + * Ensures: + *\li 'chain' is suitable for use, and uses no dynamic storage. + */ + +void +dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain); +/*%< + * Free any dynamic storage associated with 'chain', and then invalidates it. + * + * Notes: + *\li Future calls to any dns_rbtnodechain_ function will need to call + * dns_rbtnodechain_init on the chain first (except, of course, + * dns_rbtnodechain_init itself). + * + * Requires: + *\li 'chain' is a valid chain. + * + * Ensures: + *\li 'chain' is no longer suitable for use, and uses no dynamic storage. + */ + +isc_result_t +dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name, + dns_name_t *origin, dns_rbtnode_t **node); +/*%< + * Provide the name, origin and node to which the chain is currently pointed. + * + * Notes: + *\li The tree need not have be locked against additions for the chain + * to remain valid, however there are no guarantees if any deletion + * has been made since the chain was established. + * + * Requires: + *\li 'chain' is a valid chain. + * + * Ensures: + *\li 'node', if non-NULL, is the node to which the chain was pointed + * by dns_rbt_findnode, dns_rbtnodechain_first or dns_rbtnodechain_last. + * If none were called for the chain since it was initialized or reset, + * or if the was no predecessor to the name searched for with + * dns_rbt_findnode, then '*node' is NULL and ISC_R_NOTFOUND is returned. + * + *\li 'name', if non-NULL, is the name stored at the terminal level of + * the chain. This is typically a single label, like the "www" of + * "www.isc.org", but need not be so. At the root of the tree of trees, + * if the node is "." then 'name' is ".", otherwise it is relative to ".". + * (Minimalist and atypical case: if the tree has just the name + * "isc.org." then the root node's stored name is "isc.org." but 'name' + * will be "isc.org".) + * + *\li 'origin', if non-NULL, is the sequence of labels in the levels + * above the terminal level, such as "isc.org." in the above example. + * 'origin' is always "." for the root node. + * + * + * Returns: + *\li #ISC_R_SUCCESS name, origin & node were successfully set. + *\li #ISC_R_NOTFOUND The chain does not point to any node. + *\li <something_else> Any error return from dns_name_concatenate. + */ + +isc_result_t +dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt, + dns_name_t *name, dns_name_t *origin); +/*%< + * Set the chain to the lexically first node in the tree of trees. + * + * Notes: + *\li By the definition of ordering for DNS names, the root of the tree of + * trees is the very first node, since everything else in the megatree + * uses it as a common suffix. + * + * Requires: + *\li 'chain' is a valid chain. + *\li 'rbt' is a valid rbt manager. + * + * Ensures: + *\li The chain points to the very first node of the tree. + * + *\li 'name' and 'origin', if non-NULL, are set as described for + * dns_rbtnodechain_current. Thus 'origin' will always be ".". + * + * Returns: + *\li #DNS_R_NEWORIGIN The name & origin were successfully set. + *\li <something_else> Any error result from dns_rbtnodechain_current. + */ + +isc_result_t +dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt, + dns_name_t *name, dns_name_t *origin); +/*%< + * Set the chain to the lexically last node in the tree of trees. + * + * Requires: + *\li 'chain' is a valid chain. + *\li 'rbt' is a valid rbt manager. + * + * Ensures: + *\li The chain points to the very last node of the tree. + * + *\li 'name' and 'origin', if non-NULL, are set as described for + * dns_rbtnodechain_current. + * + * Returns: + *\li #DNS_R_NEWORIGIN The name & origin were successfully set. + *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory building chain. + *\li <something_else> Any error result from dns_name_concatenate. + */ + +isc_result_t +dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name, + dns_name_t *origin); +/*%< + * Adjusts chain to point the DNSSEC predecessor of the name to which it + * is currently pointed. + * + * Requires: + *\li 'chain' is a valid chain. + *\li 'chain' has been pointed somewhere in the tree with dns_rbt_findnode, + * dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that + * dns_rbt_findnode is not guaranteed to point the chain somewhere, + * since there may have been no predecessor to the searched for name. + * + * Ensures: + *\li The chain is pointed to the predecessor of its current target. + * + *\li 'name' and 'origin', if non-NULL, are set as described for + * dns_rbtnodechain_current. + * + *\li 'origin' is only if a new origin was found. + * + * Returns: + *\li #ISC_R_SUCCESS The predecessor was found and 'name' was set. + *\li #DNS_R_NEWORIGIN The predecessor was found with a different + * origin and 'name' and 'origin' were set. + *\li #ISC_R_NOMORE There was no predecessor. + *\li <something_else> Any error result from dns_rbtnodechain_current. + */ + +isc_result_t +dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name, + dns_name_t *origin); +/*%< + * Adjusts chain to point the DNSSEC successor of the name to which it + * is currently pointed. + * + * Requires: + *\li 'chain' is a valid chain. + *\li 'chain' has been pointed somewhere in the tree with dns_rbt_findnode, + * dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that + * dns_rbt_findnode is not guaranteed to point the chain somewhere, + * since there may have been no predecessor to the searched for name. + * + * Ensures: + *\li The chain is pointed to the successor of its current target. + * + *\li 'name' and 'origin', if non-NULL, are set as described for + * dns_rbtnodechain_current. + * + *\li 'origin' is only if a new origin was found. + * + * Returns: + *\li #ISC_R_SUCCESS The successor was found and 'name' was set. + *\li #DNS_R_NEWORIGIN The successor was found with a different + * origin and 'name' and 'origin' were set. + *\li #ISC_R_NOMORE There was no successor. + *\li <something_else> Any error result from dns_name_concatenate. + */ + +isc_result_t +dns_rbtnodechain_down(dns_rbtnodechain_t *chain, dns_name_t *name, + dns_name_t *origin); +/*%< + * Descend down if possible. + */ + +isc_result_t +dns_rbtnodechain_nextflat(dns_rbtnodechain_t *chain, dns_name_t *name); +/*%< + * Find the next node at the current depth in DNSSEC order. + */ + +/* + * Wrapper macros for manipulating the rbtnode reference counter: + * Since we selectively use isc_refcount_t for the reference counter of + * a rbtnode, operations on the counter depend on the actual type of it. + * The following macros provide a common interface to these operations, + * hiding the back-end. The usage is the same as that of isc_refcount_xxx(). + */ +#ifdef DNS_RBT_USEISCREFCOUNT +#define dns_rbtnode_refinit(node, n) \ + do { \ + isc_refcount_init(&(node)->references, (n)); \ + } while (0) +#define dns_rbtnode_refdestroy(node) \ + do { \ + isc_refcount_destroy(&(node)->references); \ + } while (0) +#define dns_rbtnode_refcurrent(node) \ + isc_refcount_current(&(node)->references) +#define dns_rbtnode_refincrement0(node, refs) \ + do { \ + isc_refcount_increment0(&(node)->references, (refs)); \ + } while (0) +#define dns_rbtnode_refincrement(node, refs) \ + do { \ + isc_refcount_increment(&(node)->references, (refs)); \ + } while (0) +#define dns_rbtnode_refdecrement(node, refs) \ + do { \ + isc_refcount_decrement(&(node)->references, (refs)); \ + } while (0) +#else /* DNS_RBT_USEISCREFCOUNT */ +#define dns_rbtnode_refinit(node, n) ((node)->references = (n)) +#define dns_rbtnode_refdestroy(node) ISC_REQUIRE((node)->references == 0) +#define dns_rbtnode_refcurrent(node) ((node)->references) + +#if (__STDC_VERSION__ + 0) >= 199901L || defined __GNUC__ +static inline void +dns_rbtnode_refincrement0(dns_rbtnode_t *node, unsigned int *refs) { + node->references++; + if (refs != NULL) + *refs = node->references; +} + +static inline void +dns_rbtnode_refincrement(dns_rbtnode_t *node, unsigned int *refs) { + ISC_REQUIRE(node->references > 0); + node->references++; + if (refs != NULL) + *refs = node->references; +} + +static inline void +dns_rbtnode_refdecrement(dns_rbtnode_t *node, unsigned int *refs) { + ISC_REQUIRE(node->references > 0); + node->references--; + if (refs != NULL) + *refs = node->references; +} +#else +#define dns_rbtnode_refincrement0(node, refs) \ + do { \ + unsigned int *_tmp = (unsigned int *)(refs); \ + (node)->references++; \ + if ((_tmp) != NULL) \ + (*_tmp) = (node)->references; \ + } while (0) +#define dns_rbtnode_refincrement(node, refs) \ + do { \ + ISC_REQUIRE((node)->references > 0); \ + (node)->references++; \ + if ((refs) != NULL) \ + (*refs) = (node)->references; \ + } while (0) +#define dns_rbtnode_refdecrement(node, refs) \ + do { \ + ISC_REQUIRE((node)->references > 0); \ + (node)->references--; \ + if ((refs) != NULL) \ + (*refs) = (node)->references; \ + } while (0) +#endif +#endif /* DNS_RBT_USEISCREFCOUNT */ + +void +dns_rbtnode_nodename(dns_rbtnode_t *node, dns_name_t *name); + +dns_rbtnode_t * +dns_rbt_root(dns_rbt_t *rbt); + +ISC_LANG_ENDDECLS + +#endif /* DNS_RBT_H */ |