1 /* $NetBSD: qp.h,v 1.4 2026/01/29 18:37:50 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 /* 19 * A qp-trie is a kind of key -> value map, supporting lookups that are 20 * aware of the lexicographic order of keys. 21 * 22 * Keys are `dns_qpkey_t`, which is a string-like thing, usually created 23 * from a DNS name. You can use both relative and absolute DNS names as 24 * keys, even in the same trie, except for one caveat: if a trie contains 25 * names relative to the zone apex, the natural way to represent the apex 26 * itself (spelled `@` in zone files) is a zero-length name; but a 27 * zero-length name has the same qpkey representation as the root zone 28 * (apart from its length), so they collide. 29 * 30 * Leaf values are a pair of a `void *` pointer and a `uint32_t` 31 * (because that is what fits inside an internal qp-trie leaf node). 32 * 33 * The trie does not store keys; instead keys are derived from leaf values 34 * by calling a method provided by the user. 35 * 36 * There are a few flavours of qp-trie. 37 * 38 * The basic `dns_qp_t` supports single-threaded read/write access. 39 * 40 * A `dns_qpmulti_t` is a wrapper that supports multithreaded access. 41 * There can be many concurrent readers and a single writer. Writes are 42 * transactional, and support multi-version concurrency. 43 * 44 * The concurrency strategy uses copy-on-write. When making changes during 45 * a transaction, the caller must not modify leaf values in place, but 46 * instead delete the old leaf from the trie and insert a replacement. Leaf 47 * values have reference counts, which will indicate when the old leaf 48 * value can be freed after it is no longer needed by readers using an old 49 * version of the trie. 50 * 51 * For fast concurrent reads, call `dns_qpmulti_query()` to fill in a 52 * `dns_qpread_t`, which must be allocated on the stack. This gives 53 * the reader access to a single version of the trie. The reader's 54 * thread must be registered with `liburcu`, which is normally taken 55 * care of by `libisc`. Readers are not blocked by any write activity, 56 * and vice versa. 57 * 58 * For reads that need a stable view of the trie for multiple cycles 59 * of an isc_loop, or which can be used from any thread, call 60 * `dns_qpmulti_snapshot()` to get a `dns_qpsnap_t`. A snapshot is for 61 * relatively heavy long-running read-only operations such as zone 62 * transfers. 63 * 64 * You can start one read-write transaction at a time using 65 * `dns_qpmulti_write()` or `dns_qpmulti_update()`. Either way, you 66 * get a `dns_qp_t` that can be modified like a single-threaded trie, 67 * without affecting other read-only query or snapshot users of the 68 * `dns_qpmulti_t`. 69 * 70 * "Update" transactions are heavyweight. They allocate working memory to 71 * hold modifications to the trie, and compact the trie before committing. 72 * For extra space savings, a partially-used allocation chunk is shrunk to 73 * the smallest size possible. Unlike "write" transactions, an "update" 74 * transaction can be rolled back instead of committed. (Update 75 * transactions are intended for things like authoritative zones, where it 76 * is important to keep the per-trie memory overhead low because there can 77 * be a very large number of them.) 78 * 79 * "Write" transactions are more lightweight: they skip the allocation and 80 * compaction at the start and end of the transaction. (Write transactions 81 * are intended for frequent small changes, as in the DNS cache.) 82 */ 83 84 /*********************************************************************** 85 * 86 * types 87 */ 88 89 #include <isc/attributes.h> 90 91 #include <dns/name.h> 92 #include <dns/types.h> 93 94 /*% 95 * How many bytes a qp-trie might allocate as part of an insert. Needed for 96 * overmem checks. 97 */ 98 #define QP_SAFETY_MARGIN ((1ul << 12ul) * 12) 99 100 /*% 101 * A `dns_qp_t` supports single-threaded read/write access. 102 */ 103 typedef struct dns_qp dns_qp_t; 104 105 /*% 106 * A `dns_qpmulti_t` supports multi-version wait-free concurrent reads 107 * and one transactional modification at a time. 108 */ 109 typedef struct dns_qpmulti dns_qpmulti_t; 110 111 /*% 112 * Read-only parts of a qp-trie. 113 * 114 * A `dns_qpreader_t` is the common prefix of the `dns_qpreadable` 115 * types, containing just the fields neded for the hot path. The 116 * internals of a `dns_qpreader_t` are private; they are only exposed 117 * so that callers can allocate a `dns_qpread_t` on the stack. 118 * 119 * Ranty aside: annoyingly, C doesn't allow us to use a predeclared 120 * structure type as an anonymous struct member, so we have to use a 121 * macro. (GCC and Clang have the feature we want under -fms-extensions, 122 * but a non-standard extension won't make these declarations neater if 123 * we must also have a standard alternative.) 124 */ 125 #define DNS_QPREADER_FIELDS \ 126 uint32_t magic; \ 127 dns_qpref_t root_ref; \ 128 dns_qpbase_t *base; \ 129 void *uctx; \ 130 const struct dns_qpmethods *methods 131 132 typedef struct dns_qpbase dns_qpbase_t; /* private, declared in qp_p.h */ 133 134 /*% 135 * A unique twig reference; this can be converted to chunk and cell 136 * values to find a specific location. 137 */ 138 typedef uint32_t dns_qpref_t; 139 140 typedef struct dns_qpreader { 141 DNS_QPREADER_FIELDS; 142 } dns_qpreader_t; 143 144 /*% 145 * A `dns_qpread_t` is a read-only handle on a `dns_qpmulti_t`. 146 * The caller provides space for it on the stack; it can be 147 * used by only one thread. As well as the `DNS_QPREADER_FIELDS`, 148 * it contains a thread ID to check for incorrect usage. 149 * 150 * The internals of a `dns_qpread_t` are private; they are only 151 * exposed so that callers can allocate an instance on the stack. 152 */ 153 typedef struct dns_qpread { 154 DNS_QPREADER_FIELDS; 155 uint32_t tid; 156 } dns_qpread_t; 157 158 /*% 159 * A `dns_qpsnap_t` is a read-only snapshot of a `dns_qpmulti_t`. 160 * It requires allocation and taking the `dns_qpmulti_t` mutex to 161 * create; it can be used from any thread. 162 */ 163 typedef struct dns_qpsnap dns_qpsnap_t; 164 165 /*% 166 * The read-only qp-trie functions can work on either of the read-only 167 * qp-trie types dns_qpsnap_t or dns_qpread_t, or the general-purpose 168 * read-write `dns_qp_t`. They rely on the fact that all the 169 * `dns_qpreadable_t` structures start with a `dns_qpreader_t` 170 */ 171 typedef union dns_qpreadable { 172 dns_qpreader_t *qp; 173 dns_qpread_t *qpr; 174 dns_qpsnap_t *qps; 175 dns_qp_t *qpt; 176 } dns_qpreadable_t __attribute__((__transparent_union__)); 177 178 #define dns_qpreader(qpr) ((qpr).qp) 179 180 /*% 181 * The maximum size of a key is also the maximum depth of a trie. 182 * 183 * A domain name can be up to 255 bytes. When converted to a key, each 184 * character in the name corresponds to one byte in the key if it is a 185 * common hostname character; otherwise unusual characters are escaped, 186 * using two bytes in the key. So we allow keys to be up to 512 bytes. 187 * (The actual max is (255 - 5) * 2 + 6 == 506) 188 */ 189 #define DNS_QP_MAXKEY 512 190 191 /* 192 * C is not strict enough with its integer types for the following typedefs 193 * to improve type safety, but it helps to have annotations saying what 194 * particular kind of number we are dealing with. 195 */ 196 197 /*% 198 * The bit number, or position of a bit inside a word. (Valid values 0..63) 199 * A dns_qpkey_t (below) is an array of these; each element within dns_qpkey 200 * must satisfy: 201 * 202 * SHIFT_NOBYTE <= key[off] && key[off] < SHIFT_OFFSET 203 */ 204 typedef uint8_t dns_qpshift_t; 205 206 /*% 207 * The number of bits set in a word (i.e, Hamming weight or popcount). 208 * This is used to determine the position of a node in the packed sparse 209 * vector of twigs. Valid values are 0..47 (because our bitmap does not 210 * fill the entire word). 211 */ 212 typedef uint8_t dns_qpweight_t; 213 214 /* 215 * Chunk and cell numbers, used to identify a specific location in 216 * one of the chunks stored in the QP base pointer array. Each cell 217 * within a chunk can contain a node. 218 */ 219 typedef uint32_t dns_qpchunk_t; 220 typedef uint32_t dns_qpcell_t; 221 222 /*% 223 * A trie lookup key is a small array, allocated on the stack during trie 224 * searches. Keys are usually created on demand from DNS names using 225 * `dns_qpkey_fromname()`, but in principle you can define your own 226 * functions to convert other types to trie lookup keys. 227 */ 228 typedef dns_qpshift_t dns_qpkey_t[DNS_QP_MAXKEY]; 229 230 /*% 231 * A QP iterator traverses a trie starting with the root and passing 232 * though each leaf node in lexicographic order; it is used by 233 * `dns_qpiter_init()` and `dns_qpiter_next()`. It is also used 234 * internally by `dns_qp_findname_iterator()` to locate the predecessor 235 * of a searched-for name. 236 */ 237 typedef struct dns_qpiter { 238 unsigned int magic; 239 dns_qpreader_t *qp; 240 uint16_t sp; 241 dns_qpnode_t *stack[DNS_QP_MAXKEY]; 242 } dns_qpiter_t; 243 244 /*% 245 * A QP chain holds references to each populated node between the root and 246 * a given leaf. It is used internally by `dns_qp_lookup()` to return a 247 * partial match if the specific name requested is not found; optionally it 248 * can be passed back to the caller so that individual nodes can be 249 * accessed. 250 */ 251 typedef struct dns_qpchain { 252 unsigned int magic; 253 dns_qpreader_t *qp; 254 uint8_t len; 255 struct { 256 dns_qpnode_t *node; 257 size_t offset; 258 } chain[DNS_NAME_MAXLABELS]; 259 } dns_qpchain_t; 260 261 /*% 262 * These leaf methods allow the qp-trie code to call back to the code 263 * responsible for the leaf values that are stored in the trie. The 264 * methods are provided for a whole trie when the trie is created. 265 * 266 * When you create a qp-trie, you provide a context pointer that is 267 * passed to the methods. The context pointer can tell the methods 268 * something about the trie as a whole, in addition to a particular 269 * leaf's values. 270 * 271 * The `attach` and `detach` methods adjust reference counts on value 272 * objects. They support copy-on-write and safe memory reclamation 273 * needed for multi-version concurrency. The methods are only called 274 * when the `dns_qpmulti_t` mutex is held. 275 * 276 * Note: When a value object reference count is greater than one, the 277 * object is in use by concurrent readers so it must not be modified. A 278 * refcount equal to one does not indicate whether or not the object is 279 * mutable: its refcount can be 1 while it is only in use by readers (and 280 * must be left unchanged), or newly created by a writer (and therefore 281 * mutable). 282 * 283 * The `makekey` method fills in a `dns_qpkey_t` corresponding to a 284 * value object stored in the qp-trie. It returns the length of the 285 * key, which must be less than `sizeof(dns_qpkey_t)`. This method 286 * will typically call dns_qpkey_fromname() with a name stored in the 287 * value object. 288 * 289 * For logging and tracing, the `triename` method copies a human- 290 * readable identifier into `buf` which has max length `size`. 291 */ 292 typedef struct dns_qpmethods { 293 void (*attach)(void *uctx, void *pval, uint32_t ival); 294 void (*detach)(void *uctx, void *pval, uint32_t ival); 295 size_t (*makekey)(dns_qpkey_t key, void *uctx, void *pval, 296 uint32_t ival); 297 void (*triename)(void *uctx, char *buf, size_t size); 298 } dns_qpmethods_t; 299 300 /*% 301 * Buffers for use by the `triename()` method need to be large enough 302 * to hold a zone name and a few descriptive words. 303 */ 304 #define DNS_QP_TRIENAME_MAX 300 305 306 /*% 307 * A container for the counters returned by `dns_qp_memusage()` 308 */ 309 typedef struct dns_qp_memusage { 310 void *uctx; /*%< qp-trie method context */ 311 size_t leaves; /*%< values in the trie */ 312 size_t live; /*%< nodes in use */ 313 size_t used; /*%< allocated nodes */ 314 size_t hold; /*%< nodes retained for readers */ 315 size_t free; /*%< nodes to be reclaimed */ 316 size_t node_size; /*%< in bytes */ 317 size_t chunk_count; /*%< allocated chunks */ 318 size_t bytes; /*%< total memory in chunks and metadata */ 319 bool fragmented; /*%< trie needs compaction */ 320 } dns_qp_memusage_t; 321 322 /*% 323 * Choice of mode for `dns_qp_compact()` 324 */ 325 typedef enum dns_qpgc { 326 DNS_QPGC_MAYBE, 327 DNS_QPGC_NOW, 328 DNS_QPGC_ALL, 329 } dns_qpgc_t; 330 331 /*********************************************************************** 332 * 333 * functions - create, destory, enquire 334 */ 335 336 void 337 dns_qp_create(isc_mem_t *mctx, const dns_qpmethods_t *methods, void *uctx, 338 dns_qp_t **qptp); 339 /*%< 340 * Create a single-threaded qp-trie. 341 * 342 * Requires: 343 * \li `mctx` is a pointer to a valid memory context. 344 * \li all the methods are non-NULL 345 * \li `qptp != NULL && *qptp == NULL` 346 * 347 * Ensures: 348 * \li `*qptp` is a pointer to a valid single-threaded qp-trie 349 */ 350 351 void 352 dns_qp_destroy(dns_qp_t **qptp); 353 /*%< 354 * Destroy a single-threaded qp-trie. 355 * 356 * Requires: 357 * \li `qptp != NULL` 358 * \li `*qptp` is a pointer to a valid single-threaded qp-trie 359 * 360 * Ensures: 361 * \li all memory allocated by the qp-trie has been released 362 * \li `*qptp` is NULL 363 */ 364 365 void 366 dns_qpmulti_create(isc_mem_t *mctx, const dns_qpmethods_t *methods, void *uctx, 367 dns_qpmulti_t **qpmp); 368 /*%< 369 * Create a multi-threaded qp-trie. 370 * 371 * Requires: 372 * \li `mctx` is a pointer to a valid memory context. 373 * \li all the methods are non-NULL 374 * \li `qpmp != NULL && *qpmp == NULL` 375 * 376 * Ensures: 377 * \li `*qpmp` is a pointer to a valid multi-threaded qp-trie 378 */ 379 380 void 381 dns_qpmulti_destroy(dns_qpmulti_t **qpmp); 382 /*%< 383 * Destroy a multi-threaded qp-trie. 384 * 385 * Requires: 386 * \li `qptp != NULL` 387 * \li `*qptp` is a pointer to a valid multi-threaded qp-trie 388 * \li there are no write or update transactions in progress 389 * \li no snapshots exist 390 * 391 * Ensures: 392 * \li all memory allocated by the qp-trie has been released 393 * \li `*qpmp` is NULL 394 */ 395 396 void 397 dns_qp_compact(dns_qp_t *qp, dns_qpgc_t mode); 398 /*%< 399 * Defragment the qp-trie and release unused memory. 400 * 401 * When modifications make a trie too fragmented, it is automatically 402 * compacted. However, automatic compaction is limited when a 403 * multithreaded trie has lots of immutable memory from past 404 * transactions, and lightweight write transactions do not compact on 405 * commit like heavyweight update transactions. 406 * 407 * This function can be used with a single-threaded qp-trie and during a 408 * transaction on a multi-threaded trie. 409 * 410 * \li If `mode == DNS_QPGC_MAYBE`, the trie is cleaned if it is fragmented 411 * 412 * \li If `mode == DNS_QPGC_NOW`, the trie is cleaned while avoiding 413 * unnecessary work 414 * 415 * \li If `mode == DNS_QPGC_ALL`, the entire trie is compacted 416 * 417 * Requires: 418 * \li `qp` is a pointer to a valid qp-trie 419 */ 420 421 void 422 dns_qp_gctime(uint64_t *compact_us, uint64_t *recover_us, 423 uint64_t *rollback_us); 424 /*%< 425 * Get the total times spent on garbage collection in microseconds. 426 * 427 * These counters are global, covering every qp-trie in the program. 428 * 429 * XXXFANF This is a placeholder until we can record times in histograms. 430 */ 431 432 dns_qp_memusage_t 433 dns_qp_memusage(dns_qp_t *qp); 434 /*%< 435 * Get the memory counters from a qp-trie 436 * 437 * Requires: 438 * \li `qp` is a pointer to a valid qp-trie 439 * 440 * Returns: 441 * \li a `dns_qp_memusage_t` structure described above 442 */ 443 444 dns_qp_memusage_t 445 dns_qpmulti_memusage(dns_qpmulti_t *multi); 446 /*%< 447 * Get the memory counters from multi-threaded qp-trie outside the 448 * context of a transaction. 449 * 450 * Requires: 451 * \li `multi` is a pointer to a valid dns_qpmulti_t 452 * 453 * Returns: 454 * \li a `dns_qp_memusage_t` structure described above 455 */ 456 457 /*********************************************************************** 458 * 459 * functions - search, modify 460 */ 461 462 /* 463 * XXXFANF todo, based on what we discover BIND needs 464 * 465 * more fancy searches: lexicographic predecessor (for NSEC), 466 * successor (for modification-safe iteration), etc. 467 * 468 * do we need specific lookup functions to find out if the 469 * returned value is readonly or mutable? 470 * 471 * richer modification such as dns_qp_replace{key,name} 472 */ 473 474 size_t 475 dns_qpkey_fromname(dns_qpkey_t key, const dns_name_t *name); 476 /*%< 477 * Convert a DNS name into a trie lookup key. 478 * 479 * Requires: 480 * \li `name` is a pointer to a valid `dns_name_t` 481 * 482 * Ensures: 483 * \li returned length is less than `sizeof(dns_qpkey_t)` 484 * 485 * Returns: 486 * \li the length of the key 487 */ 488 489 void 490 dns_qpkey_toname(const dns_qpkey_t key, size_t keylen, dns_name_t *name); 491 /*%< 492 * Convert a trie lookup key back into a DNS name. 493 * 494 * Requires: 495 * \li `name` is a pointer to a valid `dns_name_t` 496 * \li `name->buffer` is not NULL 497 * \li `name->offsets` is not NULL 498 */ 499 500 isc_result_t 501 dns_qp_getkey(dns_qpreadable_t qpr, const dns_qpkey_t search_key, 502 size_t search_keylen, void **pval_r, uint32_t *ival_r); 503 /*%< 504 * Find a leaf in a qp-trie that matches the given search key 505 * 506 * The leaf values are assigned to whichever of `*pval_r` and `*ival_r` 507 * are not null, unless the return value is ISC_R_NOTFOUND. 508 * 509 * Requires: 510 * \li `qpr` is a pointer to a readable qp-trie 511 * \li `search_keylen < sizeof(dns_qpkey_t)` 512 * 513 * Returns: 514 * \li ISC_R_NOTFOUND if the trie has no leaf with a matching key 515 * \li ISC_R_SUCCESS if the leaf was found 516 */ 517 518 isc_result_t 519 dns_qp_getname(dns_qpreadable_t qpr, const dns_name_t *name, void **pval_r, 520 uint32_t *ival_r); 521 /*%< 522 * Find a leaf in a qp-trie that matches the given DNS name 523 * 524 * The leaf values are assigned to whichever of `*pval_r` and `*ival_r` 525 * are not null, unless the return value is ISC_R_NOTFOUND. 526 * 527 * Requires: 528 * \li `qpr` is a pointer to a readable qp-trie 529 * \li `name` is a pointer to a valid `dns_name_t` 530 * 531 * Returns: 532 * \li ISC_R_NOTFOUND if the trie has no leaf with a matching key 533 * \li ISC_R_SUCCESS if the leaf was found 534 */ 535 536 isc_result_t 537 dns_qp_lookup(dns_qpreadable_t qpr, const dns_name_t *name, 538 dns_name_t *foundname, dns_qpiter_t *iter, dns_qpchain_t *chain, 539 void **pval_r, uint32_t *ival_r); 540 /*%< 541 * Look up a leaf in a qp-trie that is equal to, or an ancestor domain of, 542 * 'name'. 543 * 544 * If 'foundname' is not NULL, it will be updated to contain the name 545 * that was found (if any). The return code, ISC_R_SUCCESS or 546 * DNS_R_PARTIALMATCH, indicates whether the name found is the name 547 * that was requested, or an ancestor. If the result is ISC_R_NOTFOUND, 548 * 'foundname' will not be updated. (NOTE: the name will be constructed 549 * from the QP key of the found node, and this can be time-consuming. 550 * In performance-critical code, it is faster to store a copy of the 551 * name in the node data and use that instead of passing 'foundname'.) 552 * 553 * If 'chain' is not NULL, it is updated to contain a QP chain with 554 * references to the populated nodes in the tree between the root and 555 * the name that was found. If the return code is DNS_R_PARTIALMATCH 556 * then the chain terminates at the closest ancestor found; if it is 557 * ISC_R_SUCCESS then it terminates at the name that was requested. 558 * If the result is ISC_R_NOTFOUND, 'chain' will not be updated. 559 * 560 * If 'iter' is not NULL, it will be updated to point to a QP iterator 561 * which is pointed at the searched-for name if it exists in the trie, 562 * or the closest predecessor if it doesn't. 563 * 564 * The leaf data for the node that was found will be assigned to 565 * whichever of `*pval_r` and `*ival_r` are not NULL, unless the 566 * return value is ISC_R_NOTFOUND. 567 * 568 * Requires: 569 * \li `qpr` is a pointer to a readable qp-trie 570 * \li `name` is a pointer to a valid `dns_name_t` 571 * \li `foundname` is a pointer to a valid `dns_name_t` with 572 * buffer and offset space available, or is NULL 573 * 574 * Returns: 575 * \li ISC_R_SUCCESS if an exact match was found 576 * \li ISC_R_PARTIALMATCH if an ancestor domain was found 577 * \li ISC_R_NOTFOUND if no match was found 578 */ 579 580 isc_result_t 581 dns_qp_insert(dns_qp_t *qp, void *pval, uint32_t ival); 582 /*%< 583 * Insert a leaf into a qp-trie 584 * 585 * Requires: 586 * \li `qp` is a pointer to a valid qp-trie 587 * \li `pval != NULL` 588 * \li `alignof(pval) >= 4` 589 * 590 * Returns: 591 * \li ISC_R_EXISTS if the trie already has a leaf with the same key 592 * \li ISC_R_SUCCESS if the leaf was added to the trie 593 */ 594 595 isc_result_t 596 dns_qp_deletekey(dns_qp_t *qp, const dns_qpkey_t key, size_t keylen, 597 void **pval_r, uint32_t *ival_r); 598 /*%< 599 * Delete a leaf from a qp-trie that matches the given key 600 * 601 * The leaf values are assigned to whichever of `*pval_r` and `*ival_r` 602 * are not null, unless the return value is ISC_R_NOTFOUND. 603 * 604 * Requires: 605 * \li `qp` is a pointer to a valid qp-trie 606 * \li `keylen < sizeof(dns_qpkey_t)` 607 * 608 * Returns: 609 * \li ISC_R_NOTFOUND if the trie has no leaf with a matching key 610 * \li ISC_R_SUCCESS if the leaf was deleted from the trie 611 */ 612 613 isc_result_t 614 dns_qp_deletename(dns_qp_t *qp, const dns_name_t *name, void **pval_r, 615 uint32_t *ival_r); 616 /*%< 617 * Delete a leaf from a qp-trie that matches the given DNS name 618 * 619 * The leaf values are assigned to whichever of `*pval_r` and `*ival_r` 620 * are not null, unless the return value is ISC_R_NOTFOUND. 621 * 622 * Requires: 623 * \li `qp` is a pointer to a valid qp-trie 624 * \li `name` is a pointer to a valid qp-trie 625 * 626 * Returns: 627 * \li ISC_R_NOTFOUND if the trie has no leaf with a matching name 628 * \li ISC_R_SUCCESS if the leaf was deleted from the trie 629 */ 630 631 void 632 dns_qpiter_init(dns_qpreadable_t qpr, dns_qpiter_t *qpi); 633 /*%< 634 * Initialize an iterator 635 * 636 * SAFETY NOTE: If `qpr` is a `dns_qp_t`, it is not safe to modify the 637 * trie during iteration. If `qpr` is a `dns_qpread_t` or `dns_qpsnap_t` 638 * then (like any other read-only access) modifications will not affect 639 * iteration. 640 * 641 * Requires: 642 * \li `qp` is a pointer to a valid qp-trie 643 * \li `qpi` is a pointer to a qp iterator 644 */ 645 646 isc_result_t 647 dns_qpiter_next(dns_qpiter_t *qpi, dns_name_t *name, void **pval_r, 648 uint32_t *ival_r); 649 isc_result_t 650 dns_qpiter_prev(dns_qpiter_t *qpi, dns_name_t *name, void **pval_r, 651 uint32_t *ival_r); 652 /*%< 653 * Iterate forward/backward through a QP trie in lexicographic order. 654 * 655 * The leaf values are assigned to whichever of `*pval_r` and `*ival_r` 656 * are not null, unless the return value is ISC_R_NOMORE. Similarly, 657 * if `name` is not null, it is updated to contain the node name. 658 * 659 * NOTE: see the safety note under `dns_qpiter_init()`. 660 * 661 * For example, 662 * 663 * dns_qpiter_t qpi; 664 * void *pval; 665 * uint32_t ival; 666 * dns_qpiter_init(qp, &qpi); 667 * while (dns_qpiter_next(&qpi, &pval, &ival) == ISC_R_SUCCESS) { 668 * // do something with pval and ival 669 * } 670 * 671 * Requires: 672 * \li `qpi` is a pointer to a valid qp iterator 673 * 674 * Returns: 675 * \li ISC_R_SUCCESS if a leaf was found and pval_r and ival_r were set 676 * \li ISC_R_NOMORE otherwise 677 */ 678 679 isc_result_t 680 dns_qpiter_current(dns_qpiter_t *qpi, dns_name_t *name, void **pval_r, 681 uint32_t *ival_r); 682 /*%< 683 * Sets the values of `name`, `pval_r` and `ival_r` to those at the 684 * node currently pointed to by `qpi`, but without moving the iterator 685 * in either direction. If the iterator is not currently pointed at a 686 * leaf node, ISC_R_FAILURE is returned. 687 * Requires: 688 * 689 * \li `qpi` is a pointer to a valid qp iterator 690 * 691 * Returns: 692 * \li ISC_R_SUCCESS if a leaf was found and pval_r and ival_r were set 693 * \li ISC_R_FAILURE if the iterator is not initialized or not pointing 694 * at a leaf node 695 */ 696 697 void 698 dns_qpchain_init(dns_qpreadable_t qpr, dns_qpchain_t *chain); 699 /*%< 700 * Initialize a QP chain. 701 * 702 * Requires: 703 * \li `qpr` is a pointer to a valid qp-trie 704 * \li `chain` is not NULL 705 */ 706 707 unsigned int 708 dns_qpchain_length(dns_qpchain_t *chain); 709 /*%< 710 * Returns the length of a QP chain. 711 * 712 * Requires: 713 * \li `chain` is a pointer to an initialized QP chain object 714 */ 715 716 void 717 dns_qpchain_node(dns_qpchain_t *chain, unsigned int level, dns_name_t *name, 718 void **pval_r, uint32_t *ival_r); 719 /*%< 720 * Sets 'name' to the name of the leaf referenced at `chain->stack[level]`. 721 * 722 * The leaf values are assigned to whichever of `*pval_r` and `*ival_r` 723 * are not null. 724 * 725 * Requires: 726 * \li `chain` is a pointer to an initialized QP chain object 727 * \li `level` is less than `chain->len` 728 */ 729 730 /*********************************************************************** 731 * 732 * functions - transactions 733 */ 734 735 void 736 dns_qpmulti_query(dns_qpmulti_t *multi, dns_qpread_t *qpr); 737 /*%< 738 * Start a lightweight (brief) read-only transaction 739 * 740 * The `dns_qpmulti_query()` function must be called from an isc_loop 741 * thread and its 'qpr' argument must be allocated on the stack. 742 * 743 * Requires: 744 * \li `multi` is a pointer to a valid multi-threaded qp-trie 745 * \li `qpr != NULL` 746 * 747 * Returns: 748 * \li `qpr` is a valid read-only qp-trie handle 749 */ 750 751 void 752 dns_qpread_destroy(dns_qpmulti_t *multi, dns_qpread_t *qpr); 753 /*%< 754 * End a lightweight query or read transaction. 755 * 756 * Requires: 757 * \li `multi` is a pointer to a valid multi-threaded qp-trie 758 * \li `qpr` is a read-only qp-trie handle obtained from `multi` 759 * 760 * Returns: 761 * \li `qpr` is invalidated 762 */ 763 764 void 765 dns_qpmulti_snapshot(dns_qpmulti_t *multi, dns_qpsnap_t **qpsp); 766 /*%< 767 * Start a heavyweight (long) read-only transaction 768 * 769 * This function briefly takes and releases the modification mutex 770 * while allocating a copy of the trie's metadata. While the snapshot 771 * exists it does not interfere with other read-only or read-write 772 * transactions on the trie. 773 * 774 * Requires: 775 * \li `multi` is a pointer to a valid multi-threaded qp-trie 776 * \li `qpsp != NULL` 777 * \li `*qpsp == NULL` 778 * 779 * Returns: 780 * \li `*qpsp` is a pointer to a snapshot obtained from `multi` 781 */ 782 783 void 784 dns_qpsnap_destroy(dns_qpmulti_t *multi, dns_qpsnap_t **qpsp); 785 /*%< 786 * End a heavyweight read transaction 787 * 788 * Requires: 789 * \li `multi` is a pointer to a valid multi-threaded qp-trie 790 * \li `qpsp != NULL` 791 * \li `*qpsp` is a pointer to a snapshot obtained from `multi` 792 * 793 * Returns: 794 * \li `*qpsp == NULL` 795 */ 796 797 void 798 dns_qpmulti_update(dns_qpmulti_t *multi, dns_qp_t **qptp); 799 /*%< 800 * Start a heavyweight write transaction 801 * 802 * This style of transaction allocates a copy of the trie's metadata to 803 * support rollback, and it aims to minimize the memory usage of the 804 * trie between transactions. The trie is compacted when the transaction 805 * commits, and any partly-used chunk is shrunk to fit. 806 * 807 * During the transaction, the modification mutex is held. 808 * 809 * Requires: 810 * \li `multi` is a pointer to a valid multi-threaded qp-trie 811 * \li `qptp != NULL` 812 * \li `*qptp == NULL` 813 * 814 * Returns: 815 * \li `*qptp` is a pointer to the modifiable qp-trie inside `multi` 816 */ 817 818 void 819 dns_qpmulti_write(dns_qpmulti_t *multi, dns_qp_t **qptp); 820 /*%< 821 * Start a lightweight write transaction 822 * 823 * This style of transaction does not need extra allocations in addition 824 * to the ones required by insert and delete operations. It is intended 825 * for a large trie that gets frequent small writes, such as a DNS 826 * cache. 827 * 828 * A sequence of lightweight write transactions can accumulate 829 * garbage that the automatic compact/recycle cannot reclaim. 830 * To reclaim this space, you can use the `dns_qp_memusage 831 * fragmented` flag to trigger a call to dns_qp_compact(), or you 832 * can use occasional update transactions to compact the trie. 833 * 834 * During the transaction, the modification mutex is held. 835 * 836 * Requires: 837 * \li `multi` is a pointer to a valid multi-threaded qp-trie 838 * \li `qptp != NULL` 839 * \li `*qptp == NULL` 840 * 841 * Returns: 842 * \li `*qptp` is a pointer to the modifiable qp-trie inside `multi` 843 */ 844 845 void 846 dns_qpmulti_commit(dns_qpmulti_t *multi, dns_qp_t **qptp); 847 /*%< 848 * Complete a modification transaction 849 * 850 * Apart from memory management logistics, the commit itself only 851 * requires flipping the read pointer inside `multi` from the old 852 * version of the trie to the new version. Readers are not blocked. 853 * 854 * This function releases the modification mutex after the post-commit 855 * memory reclamation is completed. 856 * 857 * Requires: 858 * \li `multi` is a pointer to a valid multi-threaded qp-trie 859 * \li `qptp != NULL` 860 * \li `*qptp` is a pointer to the modifiable qp-trie inside `multi` 861 * 862 * Returns: 863 * \li `*qptp == NULL` 864 */ 865 866 void 867 dns_qpmulti_rollback(dns_qpmulti_t *multi, dns_qp_t **qptp); 868 /*%< 869 * Abandon an update transaction 870 * 871 * This function reclaims the memory allocated during the transaction 872 * and releases the modification mutex. 873 * 874 * Requires: 875 * \li `multi` is a pointer to a valid multi-threaded qp-trie 876 * \li `qptp != NULL` 877 * \li `*qptp` is a pointer to the modifiable qp-trie inside `multi` 878 * \li `*qptp` was obtained from `dns_qpmulti_update()` 879 * 880 * Returns: 881 * \li `*qptp == NULL` 882 */ 883 884 /**********************************************************************/ 885
Indexes created Fri Jun 12 00:25:51 UTC 2026