1 /* $NetBSD: rbtdb_p.h,v 1.2 2025/01/26 16:25:24 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 #pragma once 17 18 #include <isc/heap.h> 19 #include <isc/lang.h> 20 #include <isc/rwlock.h> 21 #include <isc/urcu.h> 22 23 #include <dns/nsec3.h> 24 #include <dns/rbt.h> 25 #include <dns/types.h> 26 27 #include "db_p.h" /* for db_nodelock_t */ 28 29 /*% 30 * Note that "impmagic" is not the first four bytes of the struct, so 31 * ISC_MAGIC_VALID cannot be used. 32 */ 33 #define RBTDB_MAGIC ISC_MAGIC('R', 'B', 'D', '4') 34 #define VALID_RBTDB(rbtdb) \ 35 ((rbtdb) != NULL && (rbtdb)->common.impmagic == RBTDB_MAGIC) 36 37 #define RBTDB_HEADERNODE(h) ((dns_rbtnode_t *)((h)->node)) 38 39 /* 40 * Allow clients with a virtual time of up to 5 minutes in the past to see 41 * records that would have otherwise have expired. 42 */ 43 #define RBTDB_VIRTUAL 300 44 45 /***** 46 ***** Module Info 47 *****/ 48 49 /*! \file 50 * \brief 51 * DNS Red-Black Tree DB Implementation 52 */ 53 54 ISC_LANG_BEGINDECLS 55 56 typedef struct rbtdb_changed { 57 dns_rbtnode_t *node; 58 bool dirty; 59 ISC_LINK(struct rbtdb_changed) link; 60 } rbtdb_changed_t; 61 62 typedef ISC_LIST(rbtdb_changed_t) rbtdb_changedlist_t; 63 64 struct dns_rbtdb_version { 65 /* Not locked */ 66 uint32_t serial; 67 dns_rbtdb_t *rbtdb; 68 /* 69 * Protected in the refcount routines. 70 * XXXJT: should we change the lock policy based on the refcount 71 * performance? 72 */ 73 isc_refcount_t references; 74 /* Locked by database lock. */ 75 bool writer; 76 bool commit_ok; 77 rbtdb_changedlist_t changed_list; 78 dns_slabheaderlist_t resigned_list; 79 ISC_LINK(dns_rbtdb_version_t) link; 80 bool secure; 81 bool havensec3; 82 /* NSEC3 parameters */ 83 dns_hash_t hash; 84 uint8_t flags; 85 uint16_t iterations; 86 uint8_t salt_length; 87 unsigned char salt[DNS_NSEC3_SALTSIZE]; 88 89 /* 90 * records and xfrsize are covered by rwlock. 91 */ 92 isc_rwlock_t rwlock; 93 uint64_t records; 94 uint64_t xfrsize; 95 96 struct cds_lfht *glue_table; 97 }; 98 99 typedef ISC_LIST(dns_rbtdb_version_t) rbtdb_versionlist_t; 100 101 struct dns_rbtdb { 102 /* Unlocked. */ 103 dns_db_t common; 104 /* Locks the data in this struct */ 105 isc_rwlock_t lock; 106 /* Locks the tree structure (prevents nodes appearing/disappearing) */ 107 isc_rwlock_t tree_lock; 108 /* Locks for individual tree nodes */ 109 unsigned int node_lock_count; 110 db_nodelock_t *node_locks; 111 dns_rbtnode_t *origin_node; 112 dns_rbtnode_t *nsec3_origin_node; 113 dns_stats_t *rrsetstats; /* cache DB only */ 114 isc_stats_t *cachestats; /* cache DB only */ 115 isc_stats_t *gluecachestats; /* zone DB only */ 116 /* Locked by lock. */ 117 unsigned int active; 118 unsigned int attributes; 119 uint32_t current_serial; 120 uint32_t least_serial; 121 uint32_t next_serial; 122 uint32_t maxrrperset; 123 uint32_t maxtypepername; 124 dns_rbtdb_version_t *current_version; 125 dns_rbtdb_version_t *future_version; 126 rbtdb_versionlist_t open_versions; 127 isc_loop_t *loop; 128 dns_dbnode_t *soanode; 129 dns_dbnode_t *nsnode; 130 131 /* 132 * The time after a failed lookup, where stale answers from cache 133 * may be used directly in a DNS response without attempting a 134 * new iterative lookup. 135 */ 136 uint32_t serve_stale_refresh; 137 138 /* 139 * This is an array of linked lists used to implement the LRU cache. 140 * There will be node_lock_count linked lists here. Nodes in bucket 1 141 * will be placed on the linked list lru[1]. 142 */ 143 dns_slabheaderlist_t *lru; 144 145 /* 146 * Start point % node_lock_count for next LRU cleanup. 147 */ 148 atomic_uint lru_sweep; 149 150 /* 151 * When performing LRU cleaning limit cleaning to headers that were 152 * last used at or before this. 153 */ 154 _Atomic(isc_stdtime_t) last_used; 155 156 /*% 157 * Temporary storage for stale cache nodes and dynamically deleted 158 * nodes that await being cleaned up. 159 */ 160 dns_rbtnodelist_t *deadnodes; 161 162 /* 163 * Heaps. These are used for TTL based expiry in a cache, 164 * or for zone resigning in a zone DB. hmctx is the memory 165 * context to use for the heap (which differs from the main 166 * database memory context in the case of a cache). 167 */ 168 isc_mem_t *hmctx; 169 isc_heap_t **heaps; 170 isc_heapcompare_t sooner; 171 172 /* Locked by tree_lock. */ 173 dns_rbt_t *tree; 174 dns_rbt_t *nsec; 175 dns_rbt_t *nsec3; 176 177 /* Unlocked */ 178 unsigned int quantum; 179 }; 180 181 /*% 182 * Search Context 183 */ 184 typedef struct { 185 dns_rbtdb_t *rbtdb; 186 dns_rbtdb_version_t *rbtversion; 187 uint32_t serial; 188 unsigned int options; 189 dns_rbtnodechain_t chain; 190 bool copy_name; 191 bool need_cleanup; 192 bool wild; 193 dns_rbtnode_t *zonecut; 194 dns_slabheader_t *zonecut_header; 195 dns_slabheader_t *zonecut_sigheader; 196 dns_fixedname_t zonecut_name; 197 isc_stdtime_t now; 198 } rbtdb_search_t; 199 200 /*% 201 * Load Context 202 */ 203 typedef struct { 204 dns_db_t *db; 205 isc_stdtime_t now; 206 } rbtdb_load_t; 207 208 /*% 209 * Prune context 210 */ 211 typedef struct { 212 dns_db_t *db; 213 dns_rbtnode_t *node; 214 } rbtdb_prune_t; 215 216 extern dns_dbmethods_t dns__rbtdb_zonemethods; 217 extern dns_dbmethods_t dns__rbtdb_cachemethods; 218 219 typedef struct dns_gluenode_t { 220 isc_mem_t *mctx; 221 222 struct dns_glue *glue; 223 224 dns_db_t *db; 225 dns_rbtnode_t *node; 226 227 struct cds_lfht_node ht_node; 228 struct rcu_head rcu_head; 229 } dns_gluenode_t; 230 231 /* 232 * Common DB implementation methods shared by both cache and zone RBT 233 * databases: 234 */ 235 236 isc_result_t 237 dns__rbtdb_create(isc_mem_t *mctx, const dns_name_t *base, dns_dbtype_t type, 238 dns_rdataclass_t rdclass, unsigned int argc, char *argv[], 239 void *driverarg, dns_db_t **dbp); 240 /*%< 241 * Create a new database of type "rbt". Called via dns_db_create(); 242 * see documentation for that function for more details. 243 * 244 * If argv[0] is set, it points to a valid memory context to be used for 245 * allocation of heap memory. Generally this is used for cache databases 246 * only. 247 * 248 * Requires: 249 * 250 * \li argc == 0 or argv[0] is a valid memory context. 251 */ 252 253 void 254 dns__rbtdb_destroy(dns_db_t *arg); 255 /*%< 256 * Implement dns_db_destroy() for RBT databases, see documentation 257 * for that function for more details. 258 */ 259 260 void 261 dns__rbtdb_currentversion(dns_db_t *db, dns_dbversion_t **versionp); 262 isc_result_t 263 dns__rbtdb_newversion(dns_db_t *db, dns_dbversion_t **versionp); 264 void 265 dns__rbtdb_attachversion(dns_db_t *db, dns_dbversion_t *source, 266 dns_dbversion_t **targetp); 267 void 268 dns__rbtdb_closeversion(dns_db_t *db, dns_dbversion_t **versionp, 269 bool commit DNS__DB_FLARG); 270 /*%< 271 * Implement the dns_db_currentversion(), _newversion(), 272 * _attachversion() and _closeversion() methods for RBT databases; 273 * see documentation of those functions for more details. 274 */ 275 276 isc_result_t 277 dns__rbtdb_findnode(dns_db_t *db, const dns_name_t *name, bool create, 278 dns_dbnode_t **nodep DNS__DB_FLARG); 279 isc_result_t 280 dns__rbtdb_findnodeintree(dns_rbtdb_t *rbtdb, dns_rbt_t *tree, 281 const dns_name_t *name, bool create, 282 dns_dbnode_t **nodep DNS__DB_FLARG); 283 /*%< 284 * Implement the dns_db_findnode() and _findnodeintree() methods for 285 * RBT databases; see documentation of those functions for more details. 286 */ 287 288 void 289 dns__rbtdb_attachnode(dns_db_t *db, dns_dbnode_t *source, 290 dns_dbnode_t **targetp DNS__DB_FLARG); 291 void 292 dns__rbtdb_detachnode(dns_db_t *db, dns_dbnode_t **targetp DNS__DB_FLARG); 293 /*%< 294 * Implement the dns_db_attachnode() and _detachnode() methods for 295 * RBT databases; see documentation of those functions for more details. 296 */ 297 298 isc_result_t 299 dns__rbtdb_createiterator(dns_db_t *db, unsigned int options, 300 dns_dbiterator_t **iteratorp); 301 /*%< 302 * Implement dns_db_createiterator() for RBT databases; see documentation of 303 * that function for more details. 304 */ 305 306 isc_result_t 307 dns__rbtdb_allrdatasets(dns_db_t *db, dns_dbnode_t *node, 308 dns_dbversion_t *version, unsigned int options, 309 isc_stdtime_t now, 310 dns_rdatasetiter_t **iteratorp DNS__DB_FLARG); 311 /*%< 312 * Implement dns_db_allrdatasets() for RBT databases; see documentation of 313 * that function for more details. 314 */ 315 isc_result_t 316 dns__rbtdb_addrdataset(dns_db_t *db, dns_dbnode_t *node, 317 dns_dbversion_t *version, isc_stdtime_t now, 318 dns_rdataset_t *rdataset, unsigned int options, 319 dns_rdataset_t *addedrdataset DNS__DB_FLARG); 320 isc_result_t 321 dns__rbtdb_subtractrdataset(dns_db_t *db, dns_dbnode_t *node, 322 dns_dbversion_t *version, dns_rdataset_t *rdataset, 323 unsigned int options, 324 dns_rdataset_t *newrdataset DNS__DB_FLARG); 325 isc_result_t 326 dns__rbtdb_deleterdataset(dns_db_t *db, dns_dbnode_t *node, 327 dns_dbversion_t *version, dns_rdatatype_t type, 328 dns_rdatatype_t covers DNS__DB_FLARG); 329 /*%< 330 * Implement the dns_db_addrdataset(), _subtractrdataset() and 331 * _deleterdataset() methods for RBT databases; see documentation of 332 * those functions for more details. 333 */ 334 335 unsigned int 336 dns__rbtdb_nodecount(dns_db_t *db, dns_dbtree_t tree); 337 /*%< 338 * Implement dns_db_nodecount() for RBT databases; see documentation of 339 * that function for more details. 340 */ 341 342 void 343 dns__rbtdb_setloop(dns_db_t *db, isc_loop_t *loop); 344 /*%< 345 * Implement dns_db_setloop() for RBT databases; see documentation of 346 * that function for more details. 347 */ 348 349 isc_result_t 350 dns__rbtdb_getoriginnode(dns_db_t *db, dns_dbnode_t **nodep DNS__DB_FLARG); 351 /*%< 352 * Implement dns_db_getoriginnode() for RBT databases; see documentation of 353 * that function for more details. 354 */ 355 356 void 357 dns__rbtdb_deletedata(dns_db_t *db ISC_ATTR_UNUSED, 358 dns_dbnode_t *node ISC_ATTR_UNUSED, void *data); 359 /*%< 360 * Implement dns_db_deletedata() for RBT databases; see documentation of 361 * that function for more details. 362 */ 363 364 void 365 dns__rbtdb_locknode(dns_db_t *db, dns_dbnode_t *node, isc_rwlocktype_t type); 366 void 367 dns__rbtdb_unlocknode(dns_db_t *db, dns_dbnode_t *node, isc_rwlocktype_t type); 368 /*%< 369 * Implement the dns_db_locknode() and _unlocknode() methods for 370 * RBT databases; see documentation of those functions for more details. 371 */ 372 373 /*% 374 * Functions used for the RBT implementation which are defined and 375 * used in rbtdb.c but may also be called from rbt-zonedb.c or 376 * rbt-cachedb.c: 377 */ 378 void 379 dns__rbtdb_bindrdataset(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node, 380 dns_slabheader_t *header, isc_stdtime_t now, 381 isc_rwlocktype_t locktype, 382 dns_rdataset_t *rdataset DNS__DB_FLARG); 383 384 isc_result_t 385 dns__rbtdb_nodefullname(dns_db_t *db, dns_dbnode_t *node, dns_name_t *name); 386 387 void 388 dns__rbtdb_free_gluenode_rcu(struct rcu_head *rcu_head); 389 void 390 dns__rbtdb_free_gluenode(dns_gluenode_t *gluenode); 391 392 void 393 dns__rbtdb_newref(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node, 394 isc_rwlocktype_t locktype DNS__DB_FLARG); 395 /*%< 396 * Increment the reference counter to a node in an RBT database. 397 * If the caller holds a node lock then its lock type is specified 398 * as 'locktype'. If the node is write-locked, then the node can 399 * be removed from the dead nodes list. If not, the list can be 400 * cleaned up later. 401 */ 402 403 bool 404 dns__rbtdb_decref(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node, 405 uint32_t least_serial, isc_rwlocktype_t *nlocktypep, 406 isc_rwlocktype_t *tlocktypep, bool tryupgrade, 407 bool pruning DNS__DB_FLARG); 408 /*%< 409 * Decrement the reference counter to a node in an RBT database. 410 * 'nlocktypep' and 'tlocktypep' are pointers to the current status 411 * of the node lock and tree lock. 412 * 413 * If references go to 0, the node will be cleaned up, which may 414 * necessitate upgrading the locks. 415 */ 416 417 isc_result_t 418 dns__rbtdb_add(dns_rbtdb_t *rbtdb, dns_rbtnode_t *rbtnode, 419 const dns_name_t *nodename, dns_rbtdb_version_t *rbtversion, 420 dns_slabheader_t *newheader, unsigned int options, bool loading, 421 dns_rdataset_t *addedrdataset, isc_stdtime_t now DNS__DB_FLARG); 422 /*%< 423 * Add a slab header 'newheader' to a node in an RBT database. 424 * The caller must have the node write-locked. 425 */ 426 427 void 428 dns__rbtdb_setsecure(dns_db_t *db, dns_rbtdb_version_t *version, 429 dns_dbnode_t *origin); 430 /*%< 431 * Update the secure status for an RBT database version 'version'. 432 * The version will be marked secure if it is fully signed and 433 * and contains a complete NSEC/NSEC3 chain. 434 */ 435 436 void 437 dns__rbtdb_mark(dns_slabheader_t *header, uint_least16_t flag); 438 /*%< 439 * Set attribute 'flag' in a slab header 'header' - for example, 440 * DNS_SLABHEADERATTR_STALE or DNS_SLABHEADERATTR_ANCIENT - and, 441 * in a cache database, update the rrset stats accordingly. 442 */ 443 444 void 445 dns__rbtdb_setttl(dns_slabheader_t *header, dns_ttl_t newttl); 446 /*%< 447 * Set the TTL in a slab header 'header'. In a cache database, 448 * also update the TTL heap accordingly. 449 */ 450 451 void 452 dns__rbtdb_setmaxrrperset(dns_db_t *db, uint32_t maxrrperset); 453 /*%< 454 * Set the max RRs per RRset limit. 455 */ 456 457 void 458 dns__rbtdb_setmaxtypepername(dns_db_t *db, uint32_t maxtypepername); 459 /*%< 460 * Set the max RRs per RRset limit. 461 */ 462 463 /* 464 * Functions specific to zone databases that are also called from rbtdb.c. 465 */ 466 void 467 dns__zonerbt_resigninsert(dns_rbtdb_t *rbtdb, int idx, 468 dns_slabheader_t *newheader); 469 void 470 dns__zonerbt_resigndelete(dns_rbtdb_t *rbtdb, dns_rbtdb_version_t *version, 471 dns_slabheader_t *header DNS__DB_FLARG); 472 /*%< 473 * Insert/delete a node from the zone database's resigning heap. 474 */ 475 476 isc_result_t 477 dns__zonerbt_wildcardmagic(dns_rbtdb_t *rbtdb, const dns_name_t *name, 478 bool lock); 479 /*%< 480 * Add the necessary magic for the wildcard name 'name' 481 * to be found in 'rbtdb'. 482 * 483 * In order for wildcard matching to work correctly in 484 * zone_find(), we must ensure that a node for the wildcarding 485 * level exists in the database, and has its 'find_callback' 486 * and 'wild' bits set. 487 * 488 * E.g. if the wildcard name is "*.sub.example." then we 489 * must ensure that "sub.example." exists and is marked as 490 * a wildcard level. 491 * 492 * The tree must be write-locked. 493 */ 494 isc_result_t 495 dns__zonerbt_addwildcards(dns_rbtdb_t *rbtdb, const dns_name_t *name, 496 bool lock); 497 /*%< 498 * If 'name' is or contains a wildcard name, create a node for it in the 499 * database. The tree must be write-locked. 500 */ 501 502 /* 503 * Cache-specific functions that are called from rbtdb.c 504 */ 505 void 506 dns__cacherbt_expireheader(dns_slabheader_t *header, 507 isc_rwlocktype_t *tlocktypep, 508 dns_expire_t reason DNS__DB_FLARG); 509 void 510 dns__cacherbt_overmem(dns_rbtdb_t *rbtdb, dns_slabheader_t *newheader, 511 isc_rwlocktype_t *tlocktypep DNS__DB_FLARG); 512 513 ISC_LANG_ENDDECLS 514