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