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