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