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 #ifndef DNS_RBT_H 13 #define DNS_RBT_H 1 14 15 /*! \file dns/rbt.h */ 16 17 #include <inttypes.h> 18 #include <stdbool.h> 19 20 #include <isc/assertions.h> 21 #include <isc/crc64.h> 22 #include <isc/lang.h> 23 #include <isc/magic.h> 24 #include <isc/refcount.h> 25 26 #include <dns/types.h> 27 28 ISC_LANG_BEGINDECLS 29 30 /*@{*/ 31 /*% 32 * Option values for dns_rbt_findnode() and dns_rbt_findname(). 33 * These are used to form a bitmask. 34 */ 35 #define DNS_RBTFIND_NOOPTIONS 0x00 36 #define DNS_RBTFIND_EMPTYDATA 0x01 37 #define DNS_RBTFIND_NOEXACT 0x02 38 #define DNS_RBTFIND_NOPREDECESSOR 0x04 39 /*@}*/ 40 41 #define DNS_RBT_USEMAGIC 1 42 43 #define DNS_RBT_LOCKLENGTH (sizeof(((dns_rbtnode_t *)0)->locknum) * 8) 44 45 #define DNS_RBTNODE_MAGIC ISC_MAGIC('R', 'B', 'N', 'O') 46 #if DNS_RBT_USEMAGIC 47 #define DNS_RBTNODE_VALID(n) ISC_MAGIC_VALID(n, DNS_RBTNODE_MAGIC) 48 #else /* if DNS_RBT_USEMAGIC */ 49 #define DNS_RBTNODE_VALID(n) true 50 #endif /* if DNS_RBT_USEMAGIC */ 51 52 /*% 53 * This is the structure that is used for each node in the red/black 54 * tree of trees. NOTE WELL: the implementation manages this as a variable 55 * length structure, with the actual wire-format name and other data 56 * appended to this structure. Allocating a contiguous block of memory for 57 * multiple dns_rbtnode structures will not work. 58 */ 59 typedef struct dns_rbtnode dns_rbtnode_t; 60 enum { DNS_RBT_NSEC_NORMAL = 0, /* in main tree */ 61 DNS_RBT_NSEC_HAS_NSEC = 1, /* also has node in nsec tree */ 62 DNS_RBT_NSEC_NSEC = 2, /* in nsec tree */ 63 DNS_RBT_NSEC_NSEC3 = 3 /* in nsec3 tree */ 64 }; 65 struct dns_rbtnode { 66 #if DNS_RBT_USEMAGIC 67 unsigned int magic; 68 #endif /* if DNS_RBT_USEMAGIC */ 69 /*@{*/ 70 /*! 71 * The following bitfields add up to a total bitwidth of 32. 72 * The range of values necessary for each item is indicated, 73 * but in the case of "attributes" the field is wider to accommodate 74 * possible future expansion. 75 * 76 * In each case below the "range" indicated is what's _necessary_ for 77 * the bitfield to hold, not what it actually _can_ hold. 78 * 79 * Note: Tree lock must be held before modifying these 80 * bit-fields. 81 * 82 * Note: The two "unsigned int :0;" unnamed bitfields on either 83 * side of the bitfields below are scaffolding that border the 84 * set of bitfields which are accessed after acquiring the tree 85 * lock. Please don't insert any other bitfield members between 86 * the unnamed bitfields unless they should also be accessed 87 * after acquiring the tree lock. 88 */ 89 unsigned int : 0; /* start of bitfields c/o tree lock */ 90 unsigned int is_root : 1; /*%< range is 0..1 */ 91 unsigned int color : 1; /*%< range is 0..1 */ 92 unsigned int find_callback : 1; /*%< range is 0..1 */ 93 unsigned int attributes : 3; /*%< range is 0..2 */ 94 unsigned int nsec : 2; /*%< range is 0..3 */ 95 unsigned int namelen : 8; /*%< range is 1..255 */ 96 unsigned int offsetlen : 8; /*%< range is 1..128 */ 97 unsigned int oldnamelen : 8; /*%< range is 1..255 */ 98 /*@}*/ 99 100 /* flags needed for serialization to file */ 101 unsigned int is_mmapped : 1; 102 unsigned int parent_is_relative : 1; 103 unsigned int left_is_relative : 1; 104 unsigned int right_is_relative : 1; 105 unsigned int down_is_relative : 1; 106 unsigned int data_is_relative : 1; 107 108 /* 109 * full name length; set during serialization, and used 110 * during deserialization to calculate database size. 111 * should be cleared after use. 112 */ 113 unsigned int fullnamelen : 8; /*%< range is 1..255 */ 114 115 /* node needs to be cleaned from rpz */ 116 unsigned int rpz : 1; 117 unsigned int : 0; /* end of bitfields c/o tree lock */ 118 119 /*% 120 * These are needed for hashing. The 'uppernode' points to the 121 * node's superdomain node in the parent subtree, so that it can 122 * be reached from a child that was found by a hash lookup. 123 */ 124 unsigned int hashval; 125 dns_rbtnode_t *uppernode; 126 dns_rbtnode_t *hashnext; 127 128 dns_rbtnode_t *parent; 129 dns_rbtnode_t *left; 130 dns_rbtnode_t *right; 131 dns_rbtnode_t *down; 132 133 /*% 134 * Used for LRU cache. This linked list is used to mark nodes which 135 * have no data any longer, but we cannot unlink at that exact moment 136 * because we did not or could not obtain a write lock on the tree. 137 */ 138 ISC_LINK(dns_rbtnode_t) deadlink; 139 140 /*@{*/ 141 /*! 142 * These values are used in the RBT DB implementation. The appropriate 143 * node lock must be held before accessing them. 144 * 145 * Note: The two "unsigned int :0;" unnamed bitfields on either 146 * side of the bitfields below are scaffolding that border the 147 * set of bitfields which are accessed after acquiring the node 148 * lock. Please don't insert any other bitfield members between 149 * the unnamed bitfields unless they should also be accessed 150 * after acquiring the node lock. 151 * 152 * NOTE: Do not merge these fields into bitfields above, as 153 * they'll all be put in the same qword that could be accessed 154 * without the node lock as it shares the qword with other 155 * members. Leave these members here so that they occupy a 156 * separate region of memory. 157 */ 158 void *data; 159 uint8_t : 0; /* start of bitfields c/o node lock */ 160 uint8_t dirty : 1; 161 uint8_t wild : 1; 162 uint8_t : 0; /* end of bitfields c/o node lock */ 163 uint16_t locknum; /* note that this is not in the bitfield */ 164 isc_refcount_t references; 165 /*@}*/ 166 }; 167 168 typedef isc_result_t (*dns_rbtfindcallback_t)(dns_rbtnode_t *node, 169 dns_name_t * name, 170 void * callback_arg); 171 172 typedef isc_result_t (*dns_rbtdatawriter_t)(FILE *file, unsigned char *data, 173 void *arg, uint64_t *crc); 174 175 typedef isc_result_t (*dns_rbtdatafixer_t)(dns_rbtnode_t *rbtnode, void *base, 176 size_t offset, void *arg, 177 uint64_t *crc); 178 179 typedef void (*dns_rbtdeleter_t)(void *, void *); 180 181 /***** 182 ***** Chain Info 183 *****/ 184 185 /*! 186 * A chain is used to keep track of the sequence of nodes to reach any given 187 * node from the root of the tree. Originally nodes did not have parent 188 * pointers in them (for memory usage reasons) so there was no way to find 189 * the path back to the root from any given node. Now that nodes have parent 190 * pointers, chains might be going away in a future release, though the 191 * movement functionality would remain. 192 * 193 * Chains may be used to iterate over a tree of trees. After setting up the 194 * chain's structure using dns_rbtnodechain_init(), it needs to be initialized 195 * to point to the lexically first or lexically last node in the tree of trees 196 * using dns_rbtnodechain_first() or dns_rbtnodechain_last(), respectively. 197 * Calling dns_rbtnodechain_next() or dns_rbtnodechain_prev() then moves the 198 * chain over to the next or previous node, respectively. 199 * 200 * In any event, parent information, whether via parent pointers or chains, is 201 * necessary information for iterating through the tree or for basic internal 202 * tree maintenance issues (ie, the rotations that are done to rebalance the 203 * tree when a node is added). The obvious implication of this is that for a 204 * chain to remain valid, the tree has to be locked down against writes for the 205 * duration of the useful life of the chain, because additions or removals can 206 * change the path from the root to the node the chain has targeted. 207 * 208 * The dns_rbtnodechain_ functions _first, _last, _prev and _next all take 209 * dns_name_t parameters for the name and the origin, which can be NULL. If 210 * non-NULL, 'name' will end up pointing to the name data and offsets that are 211 * stored at the node (and thus it will be read-only), so it should be a 212 * regular dns_name_t that has been initialized with dns_name_init. When 213 * 'origin' is non-NULL, it will get the name of the origin stored in it, so it 214 * needs to have its own buffer space and offsets, which is most easily 215 * accomplished with a dns_fixedname_t. It is _not_ necessary to reinitialize 216 * either 'name' or 'origin' between calls to the chain functions. 217 * 218 * NOTE WELL: even though the name data at the root of the tree of trees will 219 * be absolute (typically just "."), it will will be made into a relative name 220 * with an origin of "." -- an empty name when the node is ".". This is 221 * because a common on operation on 'name' and 'origin' is to use 222 * dns_name_concatenate() on them to generate the complete name. An empty name 223 * can be detected when dns_name_countlabels == 0, and is printed by 224 * dns_name_totext()/dns_name_format() as "@", consistent with RFC1035's 225 * definition of "@" as the current origin. 226 * 227 * dns_rbtnodechain_current is similar to the _first, _last, _prev and _next 228 * functions but additionally can provide the node to which the chain points. 229 */ 230 231 /*% 232 * The number of level blocks to allocate at a time. Currently the maximum 233 * number of levels is allocated directly in the structure, but future 234 * revisions of this code might have a static initial block with dynamic 235 * growth. Allocating space for 256 levels when the tree is almost never that 236 * deep is wasteful, but it's not clear that it matters, since the waste is 237 * only 2MB for 1000 concurrently active chains on a system with 64-bit 238 * pointers. 239 */ 240 #define DNS_RBT_LEVELBLOCK 254 241 242 typedef struct dns_rbtnodechain { 243 unsigned int magic; 244 /*% 245 * The terminal node of the chain. It is not in levels[]. 246 * This is ostensibly private ... but in a pinch it could be 247 * used tell that the chain points nowhere without needing to 248 * call dns_rbtnodechain_current(). 249 */ 250 dns_rbtnode_t *end; 251 /*% 252 * The maximum number of labels in a name is 128; bitstrings mean 253 * a conceptually very large number (which I have not bothered to 254 * compute) of logical levels because splitting can potentially occur 255 * at each bit. However, DNSSEC restricts the number of "logical" 256 * labels in a name to 255, meaning only 254 pointers are needed 257 * in the worst case. 258 */ 259 dns_rbtnode_t *levels[DNS_RBT_LEVELBLOCK]; 260 /*% 261 * level_count indicates how deep the chain points into the 262 * tree of trees, and is the index into the levels[] array. 263 * Thus, levels[level_count - 1] is the last level node stored. 264 * A chain that points to the top level of the tree of trees has 265 * a level_count of 0, the first level has a level_count of 1, and 266 * so on. 267 */ 268 unsigned int level_count; 269 /*% 270 * level_matches tells how many levels matched above the node 271 * returned by dns_rbt_findnode(). A match (partial or exact) found 272 * in the first level thus results in level_matches being set to 1. 273 * This is used by the rbtdb to set the start point for a recursive 274 * search of superdomains until the RR it is looking for is found. 275 */ 276 unsigned int level_matches; 277 } dns_rbtnodechain_t; 278 279 /***** 280 ***** Public interfaces. 281 *****/ 282 isc_result_t 283 dns_rbt_create(isc_mem_t *mctx, dns_rbtdeleter_t deleter, void *deleter_arg, 284 dns_rbt_t **rbtp); 285 /*%< 286 * Initialize a red-black tree of trees. 287 * 288 * Notes: 289 *\li The deleter argument, if non-null, points to a function that is 290 * responsible for cleaning up any memory associated with the data 291 * pointer of a node when the node is deleted. It is passed the 292 * deleted node's data pointer as its first argument and deleter_arg 293 * as its second argument. 294 * 295 * Requires: 296 * \li mctx is a pointer to a valid memory context. 297 *\li rbtp != NULL && *rbtp == NULL 298 *\li arg == NULL iff deleter == NULL 299 * 300 * Ensures: 301 *\li If result is ISC_R_SUCCESS: 302 * *rbtp points to a valid red-black tree manager 303 * 304 *\li If result is failure: 305 * *rbtp does not point to a valid red-black tree manager. 306 * 307 * Returns: 308 *\li #ISC_R_SUCCESS Success 309 *\li #ISC_R_NOMEMORY Resource limit: Out of Memory 310 */ 311 312 isc_result_t 313 dns_rbt_addname(dns_rbt_t *rbt, const dns_name_t *name, void *data); 314 /*%< 315 * Add 'name' to the tree of trees, associated with 'data'. 316 * 317 * Notes: 318 *\li 'data' is never required to be non-NULL, but specifying it 319 * when the name is added is faster than searching for 'name' 320 * again and then setting the data pointer. The lack of a data pointer 321 * for a node also has other ramifications regarding whether 322 * dns_rbt_findname considers a node to exist, or dns_rbt_deletename 323 * joins nodes. 324 * 325 * Requires: 326 *\li rbt is a valid rbt manager. 327 *\li dns_name_isabsolute(name) == TRUE 328 * 329 * Ensures: 330 *\li 'name' is not altered in any way. 331 * 332 *\li Any external references to nodes in the tree are unaffected by 333 * node splits that are necessary to insert the new name. 334 * 335 *\li If result is #ISC_R_SUCCESS: 336 * 'name' is findable in the red/black tree of trees in O(log N). 337 * The data pointer of the node for 'name' is set to 'data'. 338 * 339 *\li If result is #ISC_R_EXISTS or #ISC_R_NOSPACE: 340 * The tree of trees is unaltered. 341 * 342 *\li If result is #ISC_R_NOMEMORY: 343 * No guarantees. 344 * 345 * Returns: 346 *\li #ISC_R_SUCCESS Success 347 *\li #ISC_R_EXISTS The name already exists with associated data. 348 *\li #ISC_R_NOSPACE The name had more logical labels than are allowed. 349 *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory 350 */ 351 352 isc_result_t 353 dns_rbt_addnode(dns_rbt_t *rbt, const dns_name_t *name, dns_rbtnode_t **nodep); 354 355 /*%< 356 * Just like dns_rbt_addname, but returns the address of the node. 357 * 358 * Requires: 359 *\li rbt is a valid rbt structure. 360 *\li dns_name_isabsolute(name) == TRUE 361 *\li nodep != NULL && *nodep == NULL 362 * 363 * Ensures: 364 *\li 'name' is not altered in any way. 365 * 366 *\li Any external references to nodes in the tree are unaffected by 367 * node splits that are necessary to insert the new name. 368 * 369 *\li If result is ISC_R_SUCCESS: 370 * 'name' is findable in the red/black tree of trees in O(log N). 371 * *nodep is the node that was added for 'name'. 372 * 373 *\li If result is ISC_R_EXISTS: 374 * The tree of trees is unaltered. 375 * *nodep is the existing node for 'name'. 376 * 377 *\li If result is ISC_R_NOMEMORY: 378 * No guarantees. 379 * 380 * Returns: 381 *\li #ISC_R_SUCCESS Success 382 *\li #ISC_R_EXISTS The name already exists, possibly without data. 383 *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory 384 */ 385 386 isc_result_t 387 dns_rbt_findname(dns_rbt_t *rbt, const dns_name_t *name, unsigned int options, 388 dns_name_t *foundname, void **data); 389 /*%< 390 * Get the data pointer associated with 'name'. 391 * 392 * Notes: 393 *\li When #DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is 394 * returned (also subject to #DNS_RBTFIND_EMPTYDATA), even when there is 395 * an exact match in the tree. 396 * 397 *\li A node that has no data is considered not to exist for this function, 398 * unless the #DNS_RBTFIND_EMPTYDATA option is set. 399 * 400 * Requires: 401 *\li rbt is a valid rbt manager. 402 *\li dns_name_isabsolute(name) == TRUE 403 *\li data != NULL && *data == NULL 404 * 405 * Ensures: 406 *\li 'name' and the tree are not altered in any way. 407 * 408 *\li If result is ISC_R_SUCCESS: 409 * *data is the data associated with 'name'. 410 * 411 *\li If result is DNS_R_PARTIALMATCH: 412 * *data is the data associated with the deepest superdomain 413 * of 'name' which has data. 414 * 415 *\li If result is ISC_R_NOTFOUND: 416 * Neither the name nor a superdomain was found with data. 417 * 418 * Returns: 419 *\li #ISC_R_SUCCESS Success 420 *\li #DNS_R_PARTIALMATCH Superdomain found with data 421 *\li #ISC_R_NOTFOUND No match 422 *\li #ISC_R_NOSPACE Concatenating nodes to form foundname failed 423 */ 424 425 isc_result_t 426 dns_rbt_findnode(dns_rbt_t *rbt, const dns_name_t *name, dns_name_t *foundname, 427 dns_rbtnode_t **node, dns_rbtnodechain_t *chain, 428 unsigned int options, dns_rbtfindcallback_t callback, 429 void *callback_arg); 430 /*%< 431 * Find the node for 'name'. 432 * 433 * Notes: 434 *\li A node that has no data is considered not to exist for this function, 435 * unless the DNS_RBTFIND_EMPTYDATA option is set. This applies to both 436 * exact matches and partial matches. 437 * 438 *\li If the chain parameter is non-NULL, then the path through the tree 439 * to the DNSSEC predecessor of the searched for name is maintained, 440 * unless the DNS_RBTFIND_NOPREDECESSOR or DNS_RBTFIND_NOEXACT option 441 * is used. (For more details on those options, see below.) 442 * 443 *\li If there is no predecessor, then the chain will point to nowhere, as 444 * indicated by chain->end being NULL or dns_rbtnodechain_current 445 * returning ISC_R_NOTFOUND. Note that in a normal Internet DNS RBT 446 * there will always be a predecessor for all names except the root 447 * name, because '.' will exist and '.' is the predecessor of 448 * everything. But you can certainly construct a trivial tree and a 449 * search for it that has no predecessor. 450 * 451 *\li Within the chain structure, the 'levels' member of the structure holds 452 * the root node of each level except the first. 453 * 454 *\li The 'level_count' of the chain indicates how deep the chain to the 455 * predecessor name is, as an index into the 'levels[]' array. It does 456 * not count name elements, per se, but only levels of the tree of trees, 457 * the distinction arising because multiple labels from a name can be 458 * stored on only one level. It is also does not include the level 459 * that has the node, since that level is not stored in levels[]. 460 * 461 *\li The chain's 'level_matches' is not directly related to the predecessor. 462 * It is the number of levels above the level of the found 'node', 463 * regardless of whether it was a partial match or exact match. When 464 * the node is found in the top level tree, or no node is found at all, 465 * level_matches is 0. 466 * 467 *\li When DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is 468 * returned (also subject to DNS_RBTFIND_EMPTYDATA), even when 469 * there is an exact match in the tree. In this case, the chain 470 * will not point to the DNSSEC predecessor, but will instead point 471 * to the exact match, if there was any. Thus the preceding paragraphs 472 * should have "exact match" substituted for "predecessor" to describe 473 * how the various elements of the chain are set. This was done to 474 * ensure that the chain's state was sane, and to prevent problems that 475 * occurred when running the predecessor location code under conditions 476 * it was not designed for. It is not clear *where* the chain should 477 * point when DNS_RBTFIND_NOEXACT is set, so if you end up using a chain 478 * with this option because you want a particular node, let us know 479 * where you want the chain pointed, so this can be made more firm. 480 * 481 * Requires: 482 *\li rbt is a valid rbt manager. 483 *\li dns_name_isabsolute(name) == TRUE. 484 *\li node != NULL && *node == NULL. 485 *\li #DNS_RBTFIND_NOEXACT and DNS_RBTFIND_NOPREDECESSOR are mutually 486 * exclusive. 487 * 488 * Ensures: 489 *\li 'name' and the tree are not altered in any way. 490 * 491 *\li If result is ISC_R_SUCCESS: 492 *\verbatim 493 * *node is the terminal node for 'name'. 494 * 495 * 'foundname' and 'name' represent the same name (though not 496 * the same memory). 497 * 498 * 'chain' points to the DNSSEC predecessor, if any, of 'name'. 499 * 500 * chain->level_matches and chain->level_count are equal. 501 *\endverbatim 502 * 503 * If result is DNS_R_PARTIALMATCH: 504 *\verbatim 505 * *node is the data associated with the deepest superdomain 506 * of 'name' which has data. 507 * 508 * 'foundname' is the name of deepest superdomain (which has 509 * data, unless the DNS_RBTFIND_EMPTYDATA option is set). 510 * 511 * 'chain' points to the DNSSEC predecessor, if any, of 'name'. 512 *\endverbatim 513 * 514 *\li If result is ISC_R_NOTFOUND: 515 *\verbatim 516 * Neither the name nor a superdomain was found. *node is NULL. 517 * 518 * 'chain' points to the DNSSEC predecessor, if any, of 'name'. 519 * 520 * chain->level_matches is 0. 521 *\endverbatim 522 * 523 * Returns: 524 *\li #ISC_R_SUCCESS Success 525 *\li #DNS_R_PARTIALMATCH Superdomain found with data 526 *\li #ISC_R_NOTFOUND No match, or superdomain with no data 527 *\li #ISC_R_NOSPACE Concatenating nodes to form foundname failed 528 */ 529 530 isc_result_t 531 dns_rbt_deletename(dns_rbt_t *rbt, const dns_name_t *name, bool recurse); 532 /*%< 533 * Delete 'name' from the tree of trees. 534 * 535 * Notes: 536 *\li When 'name' is removed, if recurse is true then all of its 537 * subnames are removed too. 538 * 539 * Requires: 540 *\li rbt is a valid rbt manager. 541 *\li dns_name_isabsolute(name) == TRUE 542 * 543 * Ensures: 544 *\li 'name' is not altered in any way. 545 * 546 *\li Does NOT ensure that any external references to nodes in the tree 547 * are unaffected by node joins. 548 * 549 *\li If result is ISC_R_SUCCESS: 550 * 'name' does not appear in the tree with data; however, 551 * the node for the name might still exist which can be 552 * found with dns_rbt_findnode (but not dns_rbt_findname). 553 * 554 *\li If result is ISC_R_NOTFOUND: 555 * 'name' does not appear in the tree with data, because 556 * it did not appear in the tree before the function was called. 557 * 558 *\li If result is something else: 559 * See result codes for dns_rbt_findnode (if it fails, the 560 * node is not deleted) or dns_rbt_deletenode (if it fails, 561 * the node is deleted, but the tree is not optimized when 562 * it could have been). 563 * 564 * Returns: 565 *\li #ISC_R_SUCCESS Success 566 *\li #ISC_R_NOTFOUND No match 567 *\li something_else Any return code from dns_rbt_findnode except 568 * DNS_R_PARTIALMATCH (which causes ISC_R_NOTFOUND 569 * to be returned instead), and any code from 570 * dns_rbt_deletenode. 571 */ 572 573 isc_result_t 574 dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, bool recurse); 575 /*%< 576 * Delete 'node' from the tree of trees. 577 * 578 * Notes: 579 *\li When 'node' is removed, if recurse is true then all nodes 580 * in levels down from it are removed too. 581 * 582 * Requires: 583 *\li rbt is a valid rbt manager. 584 *\li node != NULL. 585 * 586 * Ensures: 587 *\li Does NOT ensure that any external references to nodes in the tree 588 * are unaffected by node joins. 589 * 590 *\li If result is ISC_R_SUCCESS: 591 * 'node' does not appear in the tree with data; however, 592 * the node might still exist if it serves as a pointer to 593 * a lower tree level as long as 'recurse' was false, hence 594 * the node could can be found with dns_rbt_findnode when 595 * that function's empty_data_ok parameter is true. 596 * 597 *\li If result is ISC_R_NOMEMORY or ISC_R_NOSPACE: 598 * The node was deleted, but the tree structure was not 599 * optimized. 600 * 601 * Returns: 602 *\li #ISC_R_SUCCESS Success 603 *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory when joining nodes. 604 *\li #ISC_R_NOSPACE dns_name_concatenate failed when joining nodes. 605 */ 606 607 void 608 dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name); 609 /*%< 610 * Convert the sequence of labels stored at 'node' into a 'name'. 611 * 612 * Notes: 613 *\li This function does not return the full name, from the root, but 614 * just the labels at the indicated node. 615 * 616 *\li The name data pointed to by 'name' is the information stored 617 * in the node, not a copy. Altering the data at this pointer 618 * will likely cause grief. 619 * 620 * Requires: 621 * \li name->offsets == NULL 622 * 623 * Ensures: 624 * \li 'name' is DNS_NAMEATTR_READONLY. 625 * 626 * \li 'name' will point directly to the labels stored after the 627 * dns_rbtnode_t struct. 628 * 629 * \li 'name' will have offsets that also point to the information stored 630 * as part of the node. 631 */ 632 633 isc_result_t 634 dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name); 635 /*%< 636 * Like dns_rbt_namefromnode, but returns the full name from the root. 637 * 638 * Notes: 639 * \li Unlike dns_rbt_namefromnode, the name will not point directly 640 * to node data. Rather, dns_name_concatenate will be used to copy 641 * the name data from each node into the 'name' argument. 642 * 643 * Requires: 644 * \li name != NULL 645 * \li name has a dedicated buffer. 646 * 647 * Returns: 648 * \li ISC_R_SUCCESS 649 * \li ISC_R_NOSPACE (possible via dns_name_concatenate) 650 * \li DNS_R_NAMETOOLONG (possible via dns_name_concatenate) 651 */ 652 653 char * 654 dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname, unsigned int size); 655 /*%< 656 * Format the full name of a node for printing, using dns_name_format(). 657 * 658 * Notes: 659 * \li 'size' is the length of the printname buffer. This should be 660 * DNS_NAME_FORMATSIZE or larger. 661 * 662 * Requires: 663 * \li node and printname are not NULL. 664 * 665 * Returns: 666 * \li The 'printname' pointer. 667 */ 668 669 unsigned int 670 dns_rbt_nodecount(dns_rbt_t *rbt); 671 /*%< 672 * Obtain the number of nodes in the tree of trees. 673 * 674 * Requires: 675 * \li rbt is a valid rbt manager. 676 */ 677 678 size_t 679 dns_rbt_hashsize(dns_rbt_t *rbt); 680 /*%< 681 * Obtain the current number of buckets in the 'rbt' hash table. 682 * 683 * Requires: 684 * \li rbt is a valid rbt manager. 685 */ 686 687 void 688 dns_rbt_destroy(dns_rbt_t **rbtp); 689 isc_result_t 690 dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum); 691 /*%< 692 * Stop working with a red-black tree of trees. 693 * If 'quantum' is zero then the entire tree will be destroyed. 694 * If 'quantum' is non zero then up to 'quantum' nodes will be destroyed 695 * allowing the rbt to be incrementally destroyed by repeated calls to 696 * dns_rbt_destroy2(). Once dns_rbt_destroy2() has been called no other 697 * operations than dns_rbt_destroy()/dns_rbt_destroy2() should be 698 * performed on the tree of trees. 699 * 700 * Requires: 701 * \li *rbt is a valid rbt manager. 702 * 703 * Ensures on ISC_R_SUCCESS: 704 * \li All space allocated by the RBT library has been returned. 705 * 706 * \li *rbt is invalidated as an rbt manager. 707 * 708 * Returns: 709 * \li ISC_R_SUCCESS 710 * \li ISC_R_QUOTA if 'quantum' nodes have been destroyed. 711 */ 712 713 off_t 714 dns_rbt_serialize_align(off_t target); 715 /*%< 716 * Align the provided integer to a pointer-size boundary. 717 * This should be used if, during serialization of data to a will-be 718 * mmap()ed file, a pointer alignment is needed for some data. 719 */ 720 721 isc_result_t 722 dns_rbt_serialize_tree(FILE *file, dns_rbt_t *rbt, 723 dns_rbtdatawriter_t datawriter, void *writer_arg, 724 off_t *offset); 725 /*%< 726 * Write out the RBT structure and its data to a file. 727 * 728 * Notes: 729 * \li The file must be an actual file which allows seek() calls, so it cannot 730 * be a stream. Returns ISC_R_INVALIDFILE if not. 731 */ 732 733 isc_result_t 734 dns_rbt_deserialize_tree(void *base_address, size_t filesize, 735 off_t header_offset, isc_mem_t *mctx, 736 dns_rbtdeleter_t deleter, void *deleter_arg, 737 dns_rbtdatafixer_t datafixer, void *fixer_arg, 738 dns_rbtnode_t **originp, dns_rbt_t **rbtp); 739 /*%< 740 * Read a RBT structure and its data from a file. 741 * 742 * If 'originp' is not NULL, then it is pointed to the root node of the RBT. 743 * 744 * Notes: 745 * \li The file must be an actual file which allows seek() calls, so it cannot 746 * be a stream. This condition is not checked in the code. 747 */ 748 749 void 750 dns_rbt_printtext(dns_rbt_t *rbt, void (*data_printer)(FILE *, void *), 751 FILE * f); 752 /*%< 753 * Print an ASCII representation of the internal structure of the red-black 754 * tree of trees to the passed stream. 755 * 756 * data_printer is a callback function that is called to print the data 757 * in a node. It should print it to the passed FILE stream. 758 * 759 * Notes: 760 * \li The name stored at each node, along with the node's color, is printed. 761 * Then the down pointer, left and right pointers are displayed 762 * recursively in turn. NULL down pointers are silently omitted; 763 * NULL left and right pointers are printed. 764 */ 765 766 void 767 dns_rbt_printdot(dns_rbt_t *rbt, bool show_pointers, FILE *f); 768 /*%< 769 * Print a GraphViz dot representation of the internal structure of the 770 * red-black tree of trees to the passed stream. 771 * 772 * If show_pointers is TRUE, pointers are also included in the generated 773 * graph. 774 * 775 * Notes: 776 * \li The name stored at each node, along with the node's color is displayed. 777 * Then the down pointer, left and right pointers are displayed 778 * recursively in turn. NULL left, right and down pointers are 779 * silently omitted. 780 */ 781 782 void 783 dns_rbt_printnodeinfo(dns_rbtnode_t *n, FILE *f); 784 /*%< 785 * Print out various information about a node 786 * 787 * Requires: 788 *\li 'n' is a valid pointer. 789 * 790 *\li 'f' points to a valid open FILE structure that allows writing. 791 */ 792 793 size_t 794 dns__rbt_getheight(dns_rbt_t *rbt); 795 /*%< 796 * Return the maximum height of sub-root nodes found in the red-black 797 * forest. 798 * 799 * The height of a node is defined as the number of nodes in the longest 800 * path from the node to a leaf. For each subtree in the forest, this 801 * function determines the height of its root node. Then it returns the 802 * maximum such height in the forest. 803 * 804 * Note: This function exists for testing purposes. Non-test code must 805 * not use it. 806 * 807 * Requires: 808 * \li rbt is a valid rbt manager. 809 */ 810 811 bool 812 dns__rbt_checkproperties(dns_rbt_t *rbt); 813 /*%< 814 * Check red-black properties of the forest. 815 * 816 * Note: This function exists for testing purposes. Non-test code must 817 * not use it. 818 * 819 * Requires: 820 * \li rbt is a valid rbt manager. 821 */ 822 823 size_t 824 dns__rbtnode_getdistance(dns_rbtnode_t *node); 825 /*%< 826 * Return the distance (in nodes) from the node to its upper node of its 827 * subtree. The root node has a distance of 1. A child of the root node 828 * has a distance of 2. 829 */ 830 831 /***** 832 ***** Chain Functions 833 *****/ 834 835 void 836 dns_rbtnodechain_init(dns_rbtnodechain_t *chain); 837 /*%< 838 * Initialize 'chain'. 839 * 840 * Requires: 841 *\li 'chain' is a valid pointer. 842 * 843 * Ensures: 844 *\li 'chain' is suitable for use. 845 */ 846 847 void 848 dns_rbtnodechain_reset(dns_rbtnodechain_t *chain); 849 /*%< 850 * Free any dynamic storage associated with 'chain', and then reinitialize 851 * 'chain'. 852 * 853 * Requires: 854 *\li 'chain' is a valid pointer. 855 * 856 * Ensures: 857 *\li 'chain' is suitable for use, and uses no dynamic storage. 858 */ 859 860 void 861 dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain); 862 /*%< 863 * Free any dynamic storage associated with 'chain', and then invalidates it. 864 * 865 * Notes: 866 *\li Future calls to any dns_rbtnodechain_ function will need to call 867 * dns_rbtnodechain_init on the chain first (except, of course, 868 * dns_rbtnodechain_init itself). 869 * 870 * Requires: 871 *\li 'chain' is a valid chain. 872 * 873 * Ensures: 874 *\li 'chain' is no longer suitable for use, and uses no dynamic storage. 875 */ 876 877 isc_result_t 878 dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name, 879 dns_name_t *origin, dns_rbtnode_t **node); 880 /*%< 881 * Provide the name, origin and node to which the chain is currently pointed. 882 * 883 * Notes: 884 *\li The tree need not have be locked against additions for the chain 885 * to remain valid, however there are no guarantees if any deletion 886 * has been made since the chain was established. 887 * 888 * Requires: 889 *\li 'chain' is a valid chain. 890 * 891 * Ensures: 892 *\li 'node', if non-NULL, is the node to which the chain was pointed 893 * by dns_rbt_findnode, dns_rbtnodechain_first or dns_rbtnodechain_last. 894 * If none were called for the chain since it was initialized or reset, 895 * or if the was no predecessor to the name searched for with 896 * dns_rbt_findnode, then '*node' is NULL and ISC_R_NOTFOUND is returned. 897 * 898 *\li 'name', if non-NULL, is the name stored at the terminal level of 899 * the chain. This is typically a single label, like the "www" of 900 * "www.isc.org", but need not be so. At the root of the tree of trees, 901 * if the node is "." then 'name' is ".", otherwise it is relative to ".". 902 * (Minimalist and atypical case: if the tree has just the name 903 * "isc.org." then the root node's stored name is "isc.org." but 'name' 904 * will be "isc.org".) 905 * 906 *\li 'origin', if non-NULL, is the sequence of labels in the levels 907 * above the terminal level, such as "isc.org." in the above example. 908 * 'origin' is always "." for the root node. 909 * 910 * 911 * Returns: 912 *\li #ISC_R_SUCCESS name, origin & node were successfully set. 913 *\li #ISC_R_NOTFOUND The chain does not point to any node. 914 *\li <something_else> Any error return from dns_name_concatenate. 915 */ 916 917 isc_result_t 918 dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt, 919 dns_name_t *name, dns_name_t *origin); 920 /*%< 921 * Set the chain to the lexically first node in the tree of trees. 922 * 923 * Notes: 924 *\li By the definition of ordering for DNS names, the root of the tree of 925 * trees is the very first node, since everything else in the megatree 926 * uses it as a common suffix. 927 * 928 * Requires: 929 *\li 'chain' is a valid chain. 930 *\li 'rbt' is a valid rbt manager. 931 * 932 * Ensures: 933 *\li The chain points to the very first node of the tree. 934 * 935 *\li 'name' and 'origin', if non-NULL, are set as described for 936 * dns_rbtnodechain_current. Thus 'origin' will always be ".". 937 * 938 * Returns: 939 *\li #DNS_R_NEWORIGIN The name & origin were successfully set. 940 *\li <something_else> Any error result from dns_rbtnodechain_current. 941 */ 942 943 isc_result_t 944 dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt, 945 dns_name_t *name, dns_name_t *origin); 946 /*%< 947 * Set the chain to the lexically last node in the tree of trees. 948 * 949 * Requires: 950 *\li 'chain' is a valid chain. 951 *\li 'rbt' is a valid rbt manager. 952 * 953 * Ensures: 954 *\li The chain points to the very last node of the tree. 955 * 956 *\li 'name' and 'origin', if non-NULL, are set as described for 957 * dns_rbtnodechain_current. 958 * 959 * Returns: 960 *\li #DNS_R_NEWORIGIN The name & origin were successfully set. 961 *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory building chain. 962 *\li <something_else> Any error result from dns_name_concatenate. 963 */ 964 965 isc_result_t 966 dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name, 967 dns_name_t *origin); 968 /*%< 969 * Adjusts chain to point the DNSSEC predecessor of the name to which it 970 * is currently pointed. 971 * 972 * Requires: 973 *\li 'chain' is a valid chain. 974 *\li 'chain' has been pointed somewhere in the tree with dns_rbt_findnode, 975 * dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that 976 * dns_rbt_findnode is not guaranteed to point the chain somewhere, 977 * since there may have been no predecessor to the searched for name. 978 * 979 * Ensures: 980 *\li The chain is pointed to the predecessor of its current target. 981 * 982 *\li 'name' and 'origin', if non-NULL, are set as described for 983 * dns_rbtnodechain_current. 984 * 985 *\li 'origin' is only if a new origin was found. 986 * 987 * Returns: 988 *\li #ISC_R_SUCCESS The predecessor was found and 'name' was set. 989 *\li #DNS_R_NEWORIGIN The predecessor was found with a 990 * different origin and 'name' and 'origin' were set. \li #ISC_R_NOMORE There 991 * was no predecessor. \li <something_else> Any error result from 992 * dns_rbtnodechain_current. 993 */ 994 995 isc_result_t 996 dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name, 997 dns_name_t *origin); 998 /*%< 999 * Adjusts chain to point the DNSSEC successor of the name to which it 1000 * is currently pointed. 1001 * 1002 * Requires: 1003 *\li 'chain' is a valid chain. 1004 *\li 'chain' has been pointed somewhere in the tree with dns_rbt_findnode, 1005 * dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that 1006 * dns_rbt_findnode is not guaranteed to point the chain somewhere, 1007 * since there may have been no predecessor to the searched for name. 1008 * 1009 * Ensures: 1010 *\li The chain is pointed to the successor of its current target. 1011 * 1012 *\li 'name' and 'origin', if non-NULL, are set as described for 1013 * dns_rbtnodechain_current. 1014 * 1015 *\li 'origin' is only if a new origin was found. 1016 * 1017 * Returns: 1018 *\li #ISC_R_SUCCESS The successor was found and 'name' was set. 1019 *\li #DNS_R_NEWORIGIN The successor was found with a different 1020 * origin and 'name' and 'origin' were set. 1021 *\li #ISC_R_NOMORE There was no successor. 1022 *\li <something_else> Any error result from dns_name_concatenate. 1023 */ 1024 1025 isc_result_t 1026 dns_rbtnodechain_down(dns_rbtnodechain_t *chain, dns_name_t *name, 1027 dns_name_t *origin); 1028 /*%< 1029 * Descend down if possible. 1030 */ 1031 1032 isc_result_t 1033 dns_rbtnodechain_nextflat(dns_rbtnodechain_t *chain, dns_name_t *name); 1034 /*%< 1035 * Find the next node at the current depth in DNSSEC order. 1036 */ 1037 1038 unsigned int 1039 dns__rbtnode_namelen(dns_rbtnode_t *node); 1040 /*%< 1041 * Returns the length of the full name of the node. Used only internally 1042 * and in unit tests. 1043 */ 1044 ISC_LANG_ENDDECLS 1045 1046 #endif /* DNS_RBT_H */ 1047