/* * Copyright (C) Internet Systems Consortium, Inc. ("ISC") * * SPDX-License-Identifier: MPL-2.0 * * This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, you can obtain one at https://mozilla.org/MPL/2.0/. * * See the COPYRIGHT file distributed with this work for additional * information regarding copyright ownership. */ #pragma once /* * A qp-trie is a kind of key -> value map, supporting lookups that are * aware of the lexicographic order of keys. * * Keys are `dns_qpkey_t`, which is a string-like thing, usually created * from a DNS name. You can use both relative and absolute DNS names as * keys, even in the same trie, except for one caveat: if a trie contains * names relative to the zone apex, the natural way to represent the apex * itself (spelled `@` in zone files) is a zero-length name; but a * zero-length name has the same qpkey representation as the root zone * (apart from its length), so they collide. * * Leaf values are a pair of a `void *` pointer and a `uint32_t` * (because that is what fits inside an internal qp-trie leaf node). * * The trie does not store keys; instead keys are derived from leaf values * by calling a method provided by the user. * * There are a few flavours of qp-trie. * * The basic `dns_qp_t` supports single-threaded read/write access. * * A `dns_qpmulti_t` is a wrapper that supports multithreaded access. * There can be many concurrent readers and a single writer. Writes are * transactional, and support multi-version concurrency. * * The concurrency strategy uses copy-on-write. When making changes during * a transaction, the caller must not modify leaf values in place, but * instead delete the old leaf from the trie and insert a replacement. Leaf * values have reference counts, which will indicate when the old leaf * value can be freed after it is no longer needed by readers using an old * version of the trie. * * For fast concurrent reads, call `dns_qpmulti_query()` to fill in a * `dns_qpread_t`, which must be allocated on the stack. This gives * the reader access to a single version of the trie. The reader's * thread must be registered with `liburcu`, which is normally taken * care of by `libisc`. Readers are not blocked by any write activity, * and vice versa. * * For reads that need a stable view of the trie for multiple cycles * of an isc_loop, or which can be used from any thread, call * `dns_qpmulti_snapshot()` to get a `dns_qpsnap_t`. A snapshot is for * relatively heavy long-running read-only operations such as zone * transfers. * * You can start one read-write transaction at a time using * `dns_qpmulti_write()` or `dns_qpmulti_update()`. Either way, you * get a `dns_qp_t` that can be modified like a single-threaded trie, * without affecting other read-only query or snapshot users of the * `dns_qpmulti_t`. * * "Update" transactions are heavyweight. They allocate working memory to * hold modifications to the trie, and compact the trie before committing. * For extra space savings, a partially-used allocation chunk is shrunk to * the smallest size possible. Unlike "write" transactions, an "update" * transaction can be rolled back instead of committed. (Update * transactions are intended for things like authoritative zones, where it * is important to keep the per-trie memory overhead low because there can * be a very large number of them.) * * "Write" transactions are more lightweight: they skip the allocation and * compaction at the start and end of the transaction. (Write transactions * are intended for frequent small changes, as in the DNS cache.) */ /*********************************************************************** * * types */ #include #include #include /*% * How many bytes a qp-trie might allocate as part of an insert. Needed for * overmem checks. */ #define QP_SAFETY_MARGIN ((1ul << 12ul) * 12) /*% * A `dns_qp_t` supports single-threaded read/write access. */ typedef struct dns_qp dns_qp_t; /*% * A `dns_qpmulti_t` supports multi-version wait-free concurrent reads * and one transactional modification at a time. */ typedef struct dns_qpmulti dns_qpmulti_t; /*% * Read-only parts of a qp-trie. * * A `dns_qpreader_t` is the common prefix of the `dns_qpreadable` * types, containing just the fields neded for the hot path. The * internals of a `dns_qpreader_t` are private; they are only exposed * so that callers can allocate a `dns_qpread_t` on the stack. * * Ranty aside: annoyingly, C doesn't allow us to use a predeclared * structure type as an anonymous struct member, so we have to use a * macro. (GCC and Clang have the feature we want under -fms-extensions, * but a non-standard extension won't make these declarations neater if * we must also have a standard alternative.) */ #define DNS_QPREADER_FIELDS \ uint32_t magic; \ dns_qpref_t root_ref; \ dns_qpbase_t *base; \ void *uctx; \ const struct dns_qpmethods *methods typedef struct dns_qpbase dns_qpbase_t; /* private, declared in qp_p.h */ /*% * A unique twig reference; this can be converted to chunk and cell * values to find a specific location. */ typedef uint32_t dns_qpref_t; typedef struct dns_qpreader { DNS_QPREADER_FIELDS; } dns_qpreader_t; /*% * A `dns_qpread_t` is a read-only handle on a `dns_qpmulti_t`. * The caller provides space for it on the stack; it can be * used by only one thread. As well as the `DNS_QPREADER_FIELDS`, * it contains a thread ID to check for incorrect usage. * * The internals of a `dns_qpread_t` are private; they are only * exposed so that callers can allocate an instance on the stack. */ typedef struct dns_qpread { DNS_QPREADER_FIELDS; uint32_t tid; } dns_qpread_t; /*% * A `dns_qpsnap_t` is a read-only snapshot of a `dns_qpmulti_t`. * It requires allocation and taking the `dns_qpmulti_t` mutex to * create; it can be used from any thread. */ typedef struct dns_qpsnap dns_qpsnap_t; /*% * The read-only qp-trie functions can work on either of the read-only * qp-trie types dns_qpsnap_t or dns_qpread_t, or the general-purpose * read-write `dns_qp_t`. They rely on the fact that all the * `dns_qpreadable_t` structures start with a `dns_qpreader_t` */ typedef union dns_qpreadable { dns_qpreader_t *qp; dns_qpread_t *qpr; dns_qpsnap_t *qps; dns_qp_t *qpt; } dns_qpreadable_t __attribute__((__transparent_union__)); #define dns_qpreader(qpr) ((qpr).qp) /*% * The maximum size of a key is also the maximum depth of a trie. * * A domain name can be up to 255 bytes. When converted to a key, each * character in the name corresponds to one byte in the key if it is a * common hostname character; otherwise unusual characters are escaped, * using two bytes in the key. So we allow keys to be up to 512 bytes. * (The actual max is (255 - 5) * 2 + 6 == 506) */ #define DNS_QP_MAXKEY 512 /* * C is not strict enough with its integer types for the following typedefs * to improve type safety, but it helps to have annotations saying what * particular kind of number we are dealing with. */ /*% * The bit number, or position of a bit inside a word. (Valid values 0..63) * A dns_qpkey_t (below) is an array of these; each element within dns_qpkey * must satisfy: * * SHIFT_NOBYTE <= key[off] && key[off] < SHIFT_OFFSET */ typedef uint8_t dns_qpshift_t; /*% * The number of bits set in a word (i.e, Hamming weight or popcount). * This is used to determine the position of a node in the packed sparse * vector of twigs. Valid values are 0..47 (because our bitmap does not * fill the entire word). */ typedef uint8_t dns_qpweight_t; /* * Chunk and cell numbers, used to identify a specific location in * one of the chunks stored in the QP base pointer array. Each cell * within a chunk can contain a node. */ typedef uint32_t dns_qpchunk_t; typedef uint32_t dns_qpcell_t; /*% * A trie lookup key is a small array, allocated on the stack during trie * searches. Keys are usually created on demand from DNS names using * `dns_qpkey_fromname()`, but in principle you can define your own * functions to convert other types to trie lookup keys. */ typedef dns_qpshift_t dns_qpkey_t[DNS_QP_MAXKEY]; /*% * A QP iterator traverses a trie starting with the root and passing * though each leaf node in lexicographic order; it is used by * `dns_qpiter_init()` and `dns_qpiter_next()`. It is also used * internally by `dns_qp_findname_iterator()` to locate the predecessor * of a searched-for name. */ typedef struct dns_qpiter { unsigned int magic; dns_qpreader_t *qp; uint16_t sp; dns_qpnode_t *stack[DNS_QP_MAXKEY]; } dns_qpiter_t; /*% * A QP chain holds references to each populated node between the root and * a given leaf. It is used internally by `dns_qp_lookup()` to return a * partial match if the specific name requested is not found; optionally it * can be passed back to the caller so that individual nodes can be * accessed. */ typedef struct dns_qpchain { unsigned int magic; dns_qpreader_t *qp; uint8_t len; struct { dns_qpnode_t *node; size_t offset; } chain[DNS_NAME_MAXLABELS]; } dns_qpchain_t; /*% * These leaf methods allow the qp-trie code to call back to the code * responsible for the leaf values that are stored in the trie. The * methods are provided for a whole trie when the trie is created. * * When you create a qp-trie, you provide a context pointer that is * passed to the methods. The context pointer can tell the methods * something about the trie as a whole, in addition to a particular * leaf's values. * * The `attach` and `detach` methods adjust reference counts on value * objects. They support copy-on-write and safe memory reclamation * needed for multi-version concurrency. The methods are only called * when the `dns_qpmulti_t` mutex is held. * * Note: When a value object reference count is greater than one, the * object is in use by concurrent readers so it must not be modified. A * refcount equal to one does not indicate whether or not the object is * mutable: its refcount can be 1 while it is only in use by readers (and * must be left unchanged), or newly created by a writer (and therefore * mutable). * * The `makekey` method fills in a `dns_qpkey_t` corresponding to a * value object stored in the qp-trie. It returns the length of the * key, which must be less than `sizeof(dns_qpkey_t)`. This method * will typically call dns_qpkey_fromname() with a name stored in the * value object. * * For logging and tracing, the `triename` method copies a human- * readable identifier into `buf` which has max length `size`. */ typedef struct dns_qpmethods { void (*attach)(void *uctx, void *pval, uint32_t ival); void (*detach)(void *uctx, void *pval, uint32_t ival); size_t (*makekey)(dns_qpkey_t key, void *uctx, void *pval, uint32_t ival); void (*triename)(void *uctx, char *buf, size_t size); } dns_qpmethods_t; /*% * Buffers for use by the `triename()` method need to be large enough * to hold a zone name and a few descriptive words. */ #define DNS_QP_TRIENAME_MAX 300 /*% * A container for the counters returned by `dns_qp_memusage()` */ typedef struct dns_qp_memusage { void *uctx; /*%< qp-trie method context */ size_t leaves; /*%< values in the trie */ size_t live; /*%< nodes in use */ size_t used; /*%< allocated nodes */ size_t hold; /*%< nodes retained for readers */ size_t free; /*%< nodes to be reclaimed */ size_t node_size; /*%< in bytes */ size_t chunk_count; /*%< allocated chunks */ size_t bytes; /*%< total memory in chunks and metadata */ bool fragmented; /*%< trie needs compaction */ } dns_qp_memusage_t; /*% * Choice of mode for `dns_qp_compact()` */ typedef enum dns_qpgc { DNS_QPGC_MAYBE, DNS_QPGC_NOW, DNS_QPGC_ALL, } dns_qpgc_t; /*********************************************************************** * * functions - create, destory, enquire */ void dns_qp_create(isc_mem_t *mctx, const dns_qpmethods_t *methods, void *uctx, dns_qp_t **qptp); /*%< * Create a single-threaded qp-trie. * * Requires: * \li `mctx` is a pointer to a valid memory context. * \li all the methods are non-NULL * \li `qptp != NULL && *qptp == NULL` * * Ensures: * \li `*qptp` is a pointer to a valid single-threaded qp-trie */ void dns_qp_destroy(dns_qp_t **qptp); /*%< * Destroy a single-threaded qp-trie. * * Requires: * \li `qptp != NULL` * \li `*qptp` is a pointer to a valid single-threaded qp-trie * * Ensures: * \li all memory allocated by the qp-trie has been released * \li `*qptp` is NULL */ void dns_qpmulti_create(isc_mem_t *mctx, const dns_qpmethods_t *methods, void *uctx, dns_qpmulti_t **qpmp); /*%< * Create a multi-threaded qp-trie. * * Requires: * \li `mctx` is a pointer to a valid memory context. * \li all the methods are non-NULL * \li `qpmp != NULL && *qpmp == NULL` * * Ensures: * \li `*qpmp` is a pointer to a valid multi-threaded qp-trie */ void dns_qpmulti_destroy(dns_qpmulti_t **qpmp); /*%< * Destroy a multi-threaded qp-trie. * * Requires: * \li `qptp != NULL` * \li `*qptp` is a pointer to a valid multi-threaded qp-trie * \li there are no write or update transactions in progress * \li no snapshots exist * * Ensures: * \li all memory allocated by the qp-trie has been released * \li `*qpmp` is NULL */ void dns_qp_compact(dns_qp_t *qp, dns_qpgc_t mode); /*%< * Defragment the qp-trie and release unused memory. * * When modifications make a trie too fragmented, it is automatically * compacted. However, automatic compaction is limited when a * multithreaded trie has lots of immutable memory from past * transactions, and lightweight write transactions do not compact on * commit like heavyweight update transactions. * * This function can be used with a single-threaded qp-trie and during a * transaction on a multi-threaded trie. * * \li If `mode == DNS_QPGC_MAYBE`, the trie is cleaned if it is fragmented * * \li If `mode == DNS_QPGC_NOW`, the trie is cleaned while avoiding * unnecessary work * * \li If `mode == DNS_QPGC_ALL`, the entire trie is compacted * * Requires: * \li `qp` is a pointer to a valid qp-trie */ void dns_qp_gctime(uint64_t *compact_us, uint64_t *recover_us, uint64_t *rollback_us); /*%< * Get the total times spent on garbage collection in microseconds. * * These counters are global, covering every qp-trie in the program. * * XXXFANF This is a placeholder until we can record times in histograms. */ dns_qp_memusage_t dns_qp_memusage(dns_qp_t *qp); /*%< * Get the memory counters from a qp-trie * * Requires: * \li `qp` is a pointer to a valid qp-trie * * Returns: * \li a `dns_qp_memusage_t` structure described above */ dns_qp_memusage_t dns_qpmulti_memusage(dns_qpmulti_t *multi); /*%< * Get the memory counters from multi-threaded qp-trie outside the * context of a transaction. * * Requires: * \li `multi` is a pointer to a valid dns_qpmulti_t * * Returns: * \li a `dns_qp_memusage_t` structure described above */ /*********************************************************************** * * functions - search, modify */ /* * XXXFANF todo, based on what we discover BIND needs * * more fancy searches: lexicographic predecessor (for NSEC), * successor (for modification-safe iteration), etc. * * do we need specific lookup functions to find out if the * returned value is readonly or mutable? * * richer modification such as dns_qp_replace{key,name} */ size_t dns_qpkey_fromname(dns_qpkey_t key, const dns_name_t *name); /*%< * Convert a DNS name into a trie lookup key. * * Requires: * \li `name` is a pointer to a valid `dns_name_t` * * Ensures: * \li returned length is less than `sizeof(dns_qpkey_t)` * * Returns: * \li the length of the key */ void dns_qpkey_toname(const dns_qpkey_t key, size_t keylen, dns_name_t *name); /*%< * Convert a trie lookup key back into a DNS name. * * Requires: * \li `name` is a pointer to a valid `dns_name_t` * \li `name->buffer` is not NULL * \li `name->offsets` is not NULL */ isc_result_t dns_qp_getkey(dns_qpreadable_t qpr, const dns_qpkey_t search_key, size_t search_keylen, void **pval_r, uint32_t *ival_r); /*%< * Find a leaf in a qp-trie that matches the given search key * * The leaf values are assigned to whichever of `*pval_r` and `*ival_r` * are not null, unless the return value is ISC_R_NOTFOUND. * * Requires: * \li `qpr` is a pointer to a readable qp-trie * \li `search_keylen < sizeof(dns_qpkey_t)` * * Returns: * \li ISC_R_NOTFOUND if the trie has no leaf with a matching key * \li ISC_R_SUCCESS if the leaf was found */ isc_result_t dns_qp_getname(dns_qpreadable_t qpr, const dns_name_t *name, void **pval_r, uint32_t *ival_r); /*%< * Find a leaf in a qp-trie that matches the given DNS name * * The leaf values are assigned to whichever of `*pval_r` and `*ival_r` * are not null, unless the return value is ISC_R_NOTFOUND. * * Requires: * \li `qpr` is a pointer to a readable qp-trie * \li `name` is a pointer to a valid `dns_name_t` * * Returns: * \li ISC_R_NOTFOUND if the trie has no leaf with a matching key * \li ISC_R_SUCCESS if the leaf was found */ isc_result_t dns_qp_lookup(dns_qpreadable_t qpr, const dns_name_t *name, dns_name_t *foundname, dns_qpiter_t *iter, dns_qpchain_t *chain, void **pval_r, uint32_t *ival_r); /*%< * Look up a leaf in a qp-trie that is equal to, or an ancestor domain of, * 'name'. * * If 'foundname' is not NULL, it will be updated to contain the name * that was found (if any). The return code, ISC_R_SUCCESS or * DNS_R_PARTIALMATCH, indicates whether the name found is the name * that was requested, or an ancestor. If the result is ISC_R_NOTFOUND, * 'foundname' will not be updated. (NOTE: the name will be constructed * from the QP key of the found node, and this can be time-consuming. * In performance-critical code, it is faster to store a copy of the * name in the node data and use that instead of passing 'foundname'.) * * If 'chain' is not NULL, it is updated to contain a QP chain with * references to the populated nodes in the tree between the root and * the name that was found. If the return code is DNS_R_PARTIALMATCH * then the chain terminates at the closest ancestor found; if it is * ISC_R_SUCCESS then it terminates at the name that was requested. * If the result is ISC_R_NOTFOUND, 'chain' will not be updated. * * If 'iter' is not NULL, it will be updated to point to a QP iterator * which is pointed at the searched-for name if it exists in the trie, * or the closest predecessor if it doesn't. * * The leaf data for the node that was found will be assigned to * whichever of `*pval_r` and `*ival_r` are not NULL, unless the * return value is ISC_R_NOTFOUND. * * Requires: * \li `qpr` is a pointer to a readable qp-trie * \li `name` is a pointer to a valid `dns_name_t` * \li `foundname` is a pointer to a valid `dns_name_t` with * buffer and offset space available, or is NULL * * Returns: * \li ISC_R_SUCCESS if an exact match was found * \li ISC_R_PARTIALMATCH if an ancestor domain was found * \li ISC_R_NOTFOUND if no match was found */ isc_result_t dns_qp_insert(dns_qp_t *qp, void *pval, uint32_t ival); /*%< * Insert a leaf into a qp-trie * * Requires: * \li `qp` is a pointer to a valid qp-trie * \li `pval != NULL` * \li `alignof(pval) >= 4` * * Returns: * \li ISC_R_EXISTS if the trie already has a leaf with the same key * \li ISC_R_SUCCESS if the leaf was added to the trie */ isc_result_t dns_qp_deletekey(dns_qp_t *qp, const dns_qpkey_t key, size_t keylen, void **pval_r, uint32_t *ival_r); /*%< * Delete a leaf from a qp-trie that matches the given key * * The leaf values are assigned to whichever of `*pval_r` and `*ival_r` * are not null, unless the return value is ISC_R_NOTFOUND. * * Requires: * \li `qp` is a pointer to a valid qp-trie * \li `keylen < sizeof(dns_qpkey_t)` * * Returns: * \li ISC_R_NOTFOUND if the trie has no leaf with a matching key * \li ISC_R_SUCCESS if the leaf was deleted from the trie */ isc_result_t dns_qp_deletename(dns_qp_t *qp, const dns_name_t *name, void **pval_r, uint32_t *ival_r); /*%< * Delete a leaf from a qp-trie that matches the given DNS name * * The leaf values are assigned to whichever of `*pval_r` and `*ival_r` * are not null, unless the return value is ISC_R_NOTFOUND. * * Requires: * \li `qp` is a pointer to a valid qp-trie * \li `name` is a pointer to a valid qp-trie * * Returns: * \li ISC_R_NOTFOUND if the trie has no leaf with a matching name * \li ISC_R_SUCCESS if the leaf was deleted from the trie */ void dns_qpiter_init(dns_qpreadable_t qpr, dns_qpiter_t *qpi); /*%< * Initialize an iterator * * SAFETY NOTE: If `qpr` is a `dns_qp_t`, it is not safe to modify the * trie during iteration. If `qpr` is a `dns_qpread_t` or `dns_qpsnap_t` * then (like any other read-only access) modifications will not affect * iteration. * * Requires: * \li `qp` is a pointer to a valid qp-trie * \li `qpi` is a pointer to a qp iterator */ isc_result_t dns_qpiter_next(dns_qpiter_t *qpi, dns_name_t *name, void **pval_r, uint32_t *ival_r); isc_result_t dns_qpiter_prev(dns_qpiter_t *qpi, dns_name_t *name, void **pval_r, uint32_t *ival_r); /*%< * Iterate forward/backward through a QP trie in lexicographic order. * * The leaf values are assigned to whichever of `*pval_r` and `*ival_r` * are not null, unless the return value is ISC_R_NOMORE. Similarly, * if `name` is not null, it is updated to contain the node name. * * NOTE: see the safety note under `dns_qpiter_init()`. * * For example, * * dns_qpiter_t qpi; * void *pval; * uint32_t ival; * dns_qpiter_init(qp, &qpi); * while (dns_qpiter_next(&qpi, &pval, &ival) == ISC_R_SUCCESS) { * // do something with pval and ival * } * * Requires: * \li `qpi` is a pointer to a valid qp iterator * * Returns: * \li ISC_R_SUCCESS if a leaf was found and pval_r and ival_r were set * \li ISC_R_NOMORE otherwise */ isc_result_t dns_qpiter_current(dns_qpiter_t *qpi, dns_name_t *name, void **pval_r, uint32_t *ival_r); /*%< * Sets the values of `name`, `pval_r` and `ival_r` to those at the * node currently pointed to by `qpi`, but without moving the iterator * in either direction. If the iterator is not currently pointed at a * leaf node, ISC_R_FAILURE is returned. * Requires: * * \li `qpi` is a pointer to a valid qp iterator * * Returns: * \li ISC_R_SUCCESS if a leaf was found and pval_r and ival_r were set * \li ISC_R_FAILURE if the iterator is not initialized or not pointing * at a leaf node */ void dns_qpchain_init(dns_qpreadable_t qpr, dns_qpchain_t *chain); /*%< * Initialize a QP chain. * * Requires: * \li `qpr` is a pointer to a valid qp-trie * \li `chain` is not NULL */ unsigned int dns_qpchain_length(dns_qpchain_t *chain); /*%< * Returns the length of a QP chain. * * Requires: * \li `chain` is a pointer to an initialized QP chain object */ void dns_qpchain_node(dns_qpchain_t *chain, unsigned int level, dns_name_t *name, void **pval_r, uint32_t *ival_r); /*%< * Sets 'name' to the name of the leaf referenced at `chain->stack[level]`. * * The leaf values are assigned to whichever of `*pval_r` and `*ival_r` * are not null. * * Requires: * \li `chain` is a pointer to an initialized QP chain object * \li `level` is less than `chain->len` */ /*********************************************************************** * * functions - transactions */ void dns_qpmulti_query(dns_qpmulti_t *multi, dns_qpread_t *qpr); /*%< * Start a lightweight (brief) read-only transaction * * The `dns_qpmulti_query()` function must be called from an isc_loop * thread and its 'qpr' argument must be allocated on the stack. * * Requires: * \li `multi` is a pointer to a valid multi-threaded qp-trie * \li `qpr != NULL` * * Returns: * \li `qpr` is a valid read-only qp-trie handle */ void dns_qpread_destroy(dns_qpmulti_t *multi, dns_qpread_t *qpr); /*%< * End a lightweight query or read transaction. * * Requires: * \li `multi` is a pointer to a valid multi-threaded qp-trie * \li `qpr` is a read-only qp-trie handle obtained from `multi` * * Returns: * \li `qpr` is invalidated */ void dns_qpmulti_snapshot(dns_qpmulti_t *multi, dns_qpsnap_t **qpsp); /*%< * Start a heavyweight (long) read-only transaction * * This function briefly takes and releases the modification mutex * while allocating a copy of the trie's metadata. While the snapshot * exists it does not interfere with other read-only or read-write * transactions on the trie. * * Requires: * \li `multi` is a pointer to a valid multi-threaded qp-trie * \li `qpsp != NULL` * \li `*qpsp == NULL` * * Returns: * \li `*qpsp` is a pointer to a snapshot obtained from `multi` */ void dns_qpsnap_destroy(dns_qpmulti_t *multi, dns_qpsnap_t **qpsp); /*%< * End a heavyweight read transaction * * Requires: * \li `multi` is a pointer to a valid multi-threaded qp-trie * \li `qpsp != NULL` * \li `*qpsp` is a pointer to a snapshot obtained from `multi` * * Returns: * \li `*qpsp == NULL` */ void dns_qpmulti_update(dns_qpmulti_t *multi, dns_qp_t **qptp); /*%< * Start a heavyweight write transaction * * This style of transaction allocates a copy of the trie's metadata to * support rollback, and it aims to minimize the memory usage of the * trie between transactions. The trie is compacted when the transaction * commits, and any partly-used chunk is shrunk to fit. * * During the transaction, the modification mutex is held. * * Requires: * \li `multi` is a pointer to a valid multi-threaded qp-trie * \li `qptp != NULL` * \li `*qptp == NULL` * * Returns: * \li `*qptp` is a pointer to the modifiable qp-trie inside `multi` */ void dns_qpmulti_write(dns_qpmulti_t *multi, dns_qp_t **qptp); /*%< * Start a lightweight write transaction * * This style of transaction does not need extra allocations in addition * to the ones required by insert and delete operations. It is intended * for a large trie that gets frequent small writes, such as a DNS * cache. * * A sequence of lightweight write transactions can accumulate * garbage that the automatic compact/recycle cannot reclaim. * To reclaim this space, you can use the `dns_qp_memusage * fragmented` flag to trigger a call to dns_qp_compact(), or you * can use occasional update transactions to compact the trie. * * During the transaction, the modification mutex is held. * * Requires: * \li `multi` is a pointer to a valid multi-threaded qp-trie * \li `qptp != NULL` * \li `*qptp == NULL` * * Returns: * \li `*qptp` is a pointer to the modifiable qp-trie inside `multi` */ void dns_qpmulti_commit(dns_qpmulti_t *multi, dns_qp_t **qptp); /*%< * Complete a modification transaction * * Apart from memory management logistics, the commit itself only * requires flipping the read pointer inside `multi` from the old * version of the trie to the new version. Readers are not blocked. * * This function releases the modification mutex after the post-commit * memory reclamation is completed. * * Requires: * \li `multi` is a pointer to a valid multi-threaded qp-trie * \li `qptp != NULL` * \li `*qptp` is a pointer to the modifiable qp-trie inside `multi` * * Returns: * \li `*qptp == NULL` */ void dns_qpmulti_rollback(dns_qpmulti_t *multi, dns_qp_t **qptp); /*%< * Abandon an update transaction * * This function reclaims the memory allocated during the transaction * and releases the modification mutex. * * Requires: * \li `multi` is a pointer to a valid multi-threaded qp-trie * \li `qptp != NULL` * \li `*qptp` is a pointer to the modifiable qp-trie inside `multi` * \li `*qptp` was obtained from `dns_qpmulti_update()` * * Returns: * \li `*qptp == NULL` */ /**********************************************************************/