Michał Kępień [Tue, 28 Feb 2023 11:54:02 +0000 (12:54 +0100)]
(Mostly) fix building bin/tests/system/rpz/dnsrps
Building the bin/tests/system/rpz/dnsrps helper binary is currently not
possible at all as the necessary compiler and linker flag definitions
are missing from bin/tests/system/Makefile.am. Add these as a basis for
addressing the problem.
Unfortunately, this is where the "mostly" bit mentioned in this commit's
subject line comes into play. The dlopen() parts of DNSRPS code have
not yet been reworked to use libuv's dlopen() API (uv_dlopen() etc.)
(See commit 37b9511ce1dd9ba66a6620c5ff617016eb81188f for prior work in
this area.) While it is certainly possible to do that, implementing
such a change without testing it in practice against a usable librpz.so
(i.e. a DNSRPS provider library) is bound to cause more trouble and
confusion than keeping the code the way it is right now. However,
making that code buildable as-is requires linking against a C standard
library that exports the dlopen(), dlsym(), and dlclose() symbols used
by the DNSRPS dynamic loading code. glibc 2.34+ satisfies that
requirement, but older glibc versions do not (these come with a separate
libdl shared library that would need to be linked in as well). (Other
C standard library implementations have not been examined.) Since the
long-term plan is to rely on libuv's dlopen() API exclusively and
detecting the shared object containing dlopen() & friends would only
pull in build system complexity for no good reason, assume for now that
the target system provides the dlopen() API in its C standard library.
This change enables the system test suite to be run for a BIND 9 build
prepared using --enable-dnsrps --enable-dnsrps-dl (on systems satisfying
the requirement explained above). However, it is important to note that
this change by itself does NOT enable actual testing of the DNSRPS
feature as doing that requires a DNSRPS provider library to be present
on the test host.
Ondřej Surý [Thu, 5 Jan 2023 08:12:35 +0000 (09:12 +0100)]
Implement dns_db node tracing
This implements node reference tracing that passes all the internal
layers from dns_db API (and friends) to increment_reference() and
decrement_reference().
It can be enabled by #defining DNS_DB_NODETRACE in <dns/trace.h> header.
Matthijs Mekking [Tue, 21 Feb 2023 07:50:04 +0000 (08:50 +0100)]
dnssec-signzone can now create multiple CDS RRs
Change the commandline option -G to take a string that determines what
sync records should be published. It is a comma-separated string with
each element being either "cdnskey", or "cds:<algorithm>", where
<algorithm> is a valid digest type. Duplicates are suppressed.
Matthijs Mekking [Tue, 31 Jan 2023 09:25:48 +0000 (10:25 +0100)]
Update code to publish CDS with other digest type
Now that we can configure a different digest type, update the code
to honor the configuration. Update 'dns_dnssec_syncupdate' so that
the correct CDS record is published, and also when deleting CDS records,
ensure that all possible CDS records are removed from the zone.
Matthijs Mekking [Tue, 31 Jan 2023 09:20:00 +0000 (10:20 +0100)]
Add test case for different digest type
Change one of the test cases to use a different digest type (4). The
system tests and kasp script need to be updated to take into account
the new algorithm (instead of the hard coded 2).
Mark Andrews [Tue, 28 Feb 2023 03:10:56 +0000 (14:10 +1100)]
Fix 'lame server clients are dropped below the hard limit' test
The test was setting a minimum count for recursive clients which
was not always being met (e.g. 91 instead of 100) producing a false
positive. Lower the lower bound on recursive clients for this
test to 1.
Tony Finch [Thu, 16 Feb 2023 21:42:04 +0000 (21:42 +0000)]
Improve qp-trie compaction in write transactions
In general, it's better to do one thorough compaction when a batch of
work is complete, which is the way that `update` transactions work.
Conversely, `write` transactions are designed so that lots of little
transactions are not too inefficient, but they need explicit
compaction. This changes `dns_qp_compact()` so that it is easier to
compact any time that makes sense, if there isn't a better way to
schedule compaction. And `dns_qpmulti_commit()` only recycles garbage
when there is enough to make it worthwhile.
Tony Finch [Fri, 17 Feb 2023 18:28:24 +0000 (18:28 +0000)]
Improve qp-trie refcount debugging
Add some qp-trie tracing macros which can be enabled by a
developer. These print a message when a leaf is attached or
detached, indicating which part of the qp-trie implementation
did so. The refcount methods must now return the refcount value
so it can be printed by the trace macros.
Tony Finch [Thu, 22 Dec 2022 14:55:14 +0000 (14:55 +0000)]
Refactor qp-trie to use QSBR
The first working multi-threaded qp-trie was stuck with an unpleasant
trade-off:
* Use `isc_rwlock`, which has acceptable write performance, but
terrible read scalability because the qp-trie made all accesses
through a single lock.
* Use `liburcu`, which has great read scalability, but terrible
write performance, because I was relying on `rcu_synchronize()`
which is rather slow. And `liburcu` is LGPL.
To get the best of both worlds, we need our own scalable read side,
which we now have with `isc_qsbr`. And we need to modify the write
side so that it is not blocked by readers.
Better write performance requires an async cleanup function like
`call_rcu()`, instead of the blocking `rcu_synchronize()`. (There
is no blocking cleanup in `isc_qsbr`, because I have concluded
that it would be an attractive nuisance.)
Until now, all my multithreading qp-trie designs have been based
around two versions, read-only and mutable. This is too few to
work with asynchronous cleanup. The bare minimum (as in epoch
based reclamation) is three, but it makes more sense to support an
arbitrary number. Doing multi-version support "properly" makes
fewer assumptions about how safe memory reclamation works, and it
makes snapshots and rollbacks simpler.
To avoid making the memory management even more complicated, I
have introduced a new kind of "packed reader node" to anchor the
root of a version of the trie. This is simpler because it re-uses
the existing chunk lifetime logic - see the discussion under
"packed reader nodes" in `qp_p.h`.
I have also made the chunk lifetime logic simpler. The idea of a
"generation" is gone; instead, chunks are either mutable or
immutable. And the QSBR phase number is used to indicate when a
chunk can be reclaimed.
Instead of the `shared_base` flag (which was basically a one-bit
reference count, with a two version limit) the base array now has a
refcount, which replaces the confusing ad-hoc lifetime logic with
something more familiar and systematic.
Tony Finch [Wed, 28 Sep 2022 15:56:46 +0000 (16:56 +0100)]
Benchmarks for the qp-trie
The main benchmark is `qpmulti`, which exercizes the qp-trie
transactional API with differing numbers of threads and differing data
sizes, to get some idea of how its performance scales.
The `load-names` benchmark compares the times to populate and query
and the memory used by various BIND data structures: qp-trie, hash
table (chained), hash map (closed), and red-black tree.
The `qp-dump` program is a test utility rather than a benchmark. It
populates a qp-trie and prints it out, either in an ad-hoc text
format, or as input to the graphviz `dot` program.
Tony Finch [Sun, 12 Jun 2022 14:52:35 +0000 (15:52 +0100)]
Fuzz testing the qp-trie
Ensure dns_qpkey_fromname() and dns_qpkey_toname() are inverses.
Excercise a single-threaded dns_qp_t with a fixed set of random keys
and a small chunk size. Use the table of names to ensure that the trie
is behaving as expected. This is (in effect) randomized testing like
the `qpmulti` unit test, but making use of coverage-guided fuzzing
and (in principle) test case minimization.
Tony Finch [Thu, 6 Oct 2022 14:59:14 +0000 (15:59 +0100)]
Test the qp-trie transactional API
Randomized testing with intensive consistency and correctness checks
make it much easier to get good coverage and to shake out bugs than
hand-written unit tests for specific cases.
These tests only run in a single thread, but each test transaction
uses both a write/update and a query/snapshot, to ensure that
modifications are not visible to concurrent readers.
Tony Finch [Tue, 14 Jun 2022 15:20:28 +0000 (16:20 +0100)]
Test infrastructure for the qp-trie
This change adds a number of support routines for the unit tests, and
for benchmarks and fuzz tests to be added later. It isn't necessary to
include the support routines in libdns, since they are not needed by
BIND's installed programs. So `libtest` seems like the best place for
them.
The tests themselves verify that dns_qpkey_fromname() behaves as
expected.
Tony Finch [Wed, 22 Feb 2023 18:08:26 +0000 (18:08 +0000)]
Fix qp-trie refcounting mistake
The error occurred when:
* The bump chunk was re-used across multiple write transactions.
In this situation the bump chunk is marked immutable, but the
immutable flag is disregarded for cells after the fender, which
were allocated in the current transaction.
* The bump chunk fills up during an insert operation, so that the
enlarged twigs vector is allocated from a new bump chunk.
* Before this happened, we should have (but didn't) made the twigs
vector mutable. This would have adjusted its refcounts as necessary.
* However, moving to a new bump chunk has a side effect: twigs that
were previously considered mutable because they are after the
fender become immutable.
* Because of this, the old twigs vector was not destroyed as expected.
* So leaves were duplicated without their refcounts being increased.
The effect is that the refcounts were lower than they should have
been, and underflowed. The tests failed to check for refcount
underflow, so this mistake was detected much later than it ideally
could have been.
After the fix, it is now correct not to ensure the twigs are mutable,
because they are about to be copied to a larger vector. Instead, we
need to find out whether `squash_twigs()` destroyed the old twigs, and
adjust the refcounts accordingly.
Tony Finch [Mon, 9 May 2022 13:31:35 +0000 (14:31 +0100)]
Add a qp-trie data structure
A qp-trie is a kind of radix tree that is particularly well-suited to
DNS servers. I invented the qp-trie in 2015, based on Dan Bernstein's
crit-bit trees and Phil Bagwell's HAMT. https://dotat.at/prog/qp/
This code incorporates some new ideas that I prototyped using
NLnet Labs NSD in 2020 (optimizations for DNS names as keys)
and 2021 (custom allocator and garbage collector).
https://dotat.at/cgi/git/nsd.git
The BIND version of my qp-trie code has a number of improvements
compared to the prototype developed for NSD.
* The main omission in the prototype was the very sketchy outline of
how locking might work. Now the locking has been implemented,
using a reader/writer lock and a mutex. However, it is designed to
benefit from liburcu if that is available.
* The prototype was designed for two-version concurrency, one
version for readers and one for the writer. The new code supports
multiversion concurrency, to provide a basis for BIND's dbversion
machinery, so that updates are not blocked by long-running zone
transfers.
* There are now two kinds of transaction that modify the trie: an
`update` aims to support many very small zones without wasting
memory; a `write` avoids unnecessary allocation to help the
performance of many small changes to the cache.
* There is also a single-threaded interface for situations where
concurrent access is not necessary.
* The API makes better use of types to make it more clear which
operations are permitted when.
* The lookup table used to convert a DNS name to a qp-trie key is
now initialized by a run-time constructor instead of a programmer
using copy-and-paste. Key conversion is more flexible, so the
qp-trie can be used with keys other than DNS names.
* There has been much refactoring and re-arranging things to improve
the terminology and order of presentation in the code, and the
internal documentation has been moved from a comment into a file
of its own.
Some of the required functionality has been stripped out, to be
brought back later after the basics are known to work.
* Garbage collector performance statistics are missing.
* Fancy searches are missing, such as longest match and
nearest match.
* Iteration is missing.
* Search for update is missing, for cases where the caller needs to
know if the value object is mutable or not.
Aram Sargsyan [Fri, 27 Jan 2023 08:47:52 +0000 (08:47 +0000)]
catz: unregister the db update-notify callback before detaching from db
When detaching from the previous version of the database, make sure
that the update-notify callback is unregistered, otherwise there is
an INSIST check which can generate an assertion failure in free_rbtdb(),
which checks that there are no outstanding update listeners in the list.
Aram Sargsyan [Thu, 26 Jan 2023 19:08:19 +0000 (19:08 +0000)]
Process db callbacks in zone_loaddone() after zone_postload()
The zone_postload() function can fail and unregister the callbacks.
Call dns_db_endload() only after calling zone_postload() to make
sure that the registered update-notify callbacks are not called
when the zone loading has failed during zone_postload().
Also, don't ignore the return value of zone_postload().
Aram Sargsyan [Fri, 27 Jan 2023 09:22:11 +0000 (09:22 +0000)]
Add a system test for [GL #3777]
Add the 'ixfr-from-differences yes;' option to trigger a failed
zone postload operation when a zone is updated but the serial
number is not updated, then issue two successive 'rndc reload'
commands to trigger the bug, which causes an assertion failure.
Ondřej Surý [Thu, 23 Feb 2023 10:10:39 +0000 (11:10 +0100)]
Pause the catz dbiterator while processing the zone
The dbiterator read-locks the whole zone and it stayed locked during
whole processing time when catz is being read. Pause the iterator, so
the updates to catz zone are not being blocked while processing the catz
update.
Ondřej Surý [Fri, 24 Feb 2023 09:46:00 +0000 (09:46 +0000)]
Unlock catzs during dns__catz_update_cb()
Instead of holding the catzs->lock the whole time we process the catz
update, only hold it for hash table lookup and then release it. This
should unblock any other threads that might be processing updates to
catzs triggered by extra incoming transfer.
Aram Sargsyan [Tue, 21 Feb 2023 14:23:38 +0000 (14:23 +0000)]
Offload catalog zone updates
Offload catalog zone processing so that the network manager threads
are not interrupted by a large catalog zone update.
Introduce a new 'updaterunning' state alongside with 'updatepending',
like it is done in the RPZ module.
Note that the dns__catz_update_cb() function currently holds the
catzs->lock during the whole process, which is far from being optimal,
but the issue is going to be addressed separately.
Aram Sargsyan [Tue, 21 Feb 2023 21:14:44 +0000 (21:14 +0000)]
Add shutdown signaling for catalog zones
This change should make sure that catalog zone update processing
doesn't happen when the catalog zone is being shut down. This
should help avoid races when offloading the catalog zone updates
in the follow-up commit.
Aram Sargsyan [Thu, 23 Feb 2023 14:43:41 +0000 (14:43 +0000)]
Call dns_catz_new_zones() only when it is needed
The configure_catz() function creates the catalog zones structure
for the view even when it is not needed, in which case it then
discards it (by detaching) later.
Instead, call dns_catz_new_zones() only when it is needed, i.e. when
there is no existing "previous" view with an existing 'catzs', that
is going to be reused.
Aram Sargsyan [Thu, 9 Feb 2023 10:32:33 +0000 (10:32 +0000)]
Light refactoring of catz.c
* Change 'dns_catz_new_zones()' function's prototype (the order of the
arguments) to synchronize it with the similar function in rpz.c.
* Rename 'refs' to 'references' in preparation of ISC_REFCOUNT_*
macros usage for reference tracking.
* Unify dns_catz_zone_t naming to catz, and dns_catz_zones_t naming to
catzs, following the logic of similar changes in rpz.c.
* Use C compound literals for structure initialization.
* Synchronize the "new zone version came too soon" log message with the
one in rpz.c.
* Use more of 'sizeof(*ptr)' style instead of the 'sizeof(type_t)' style
expressions when allocating or freeing memory for 'ptr'.
Tony Finch [Fri, 16 Dec 2022 12:19:08 +0000 (12:19 +0000)]
Move irs_resconf into libdns and remove libirs
`libirs` used to be a reference implementation of `getaddrinfo` and
related modern resolver APIs. It was stripped down in BIND 9.18
leaving only the `irs_resconf` module, which parses
`/etc/resolv.conf`. I have kept its include path and namespace prefix,
so it remains a little fragment of libirs now embedded in libdns.
Ondřej Surý [Fri, 24 Feb 2023 07:41:51 +0000 (08:41 +0100)]
Add SonarCloud GitHub Action
Add new SonarCloud GitHub Action and configuration; something (maybe
the way the builds were submitted) has apparently changed and the
project got deleted and the analysis wasn't working.
Evan Hunt [Wed, 22 Feb 2023 19:04:12 +0000 (11:04 -0800)]
fix a bug in dns_dispatch_getnext()
when a message arrives over a TCP connection matching an expected
QID, the dispatch is updated so it no longer expects that QID,
but continues reading. subsequent messages with the same QID are
ignored, unless the dispatch entry has called dns_dispatch_getnext()
or dns_dispatch_resume().
however, a coding error caused those functions to have no effect
when the dispatch was reading, so streams of messages with the same
QID could not be received over a single TCP connection, breaking *XFR.
this has been corrected by changing the order of operations in
tcp_dispatch_getnext() so that disp->reading isn't checked until
after the dispatch entry has been reactivated.
Evan Hunt [Wed, 22 Feb 2023 04:14:30 +0000 (20:14 -0800)]
refactor dns_xfrin to use dns_dispatch
the dns_xfrin module was still using the network manager directly to
manage TCP connections and send and receive messages. this commit
changes it to use the dispatch manager instead.
Evan Hunt [Thu, 23 Feb 2023 18:29:33 +0000 (10:29 -0800)]
implement refcount tracing in xfrin.c
use ISC_REFCOUNT_IMPL for dns_xfrin_ctx_t (which has been renamed
to dns_xfrin_t to keep the function names dns_xfrin_attach() and
dns_xfrin_detach() unchanged).
Evan Hunt [Wed, 22 Feb 2023 00:34:41 +0000 (16:34 -0800)]
move dispatchmgr from resolver to view
the 'dispatchmgr' member of the resolver object is used by both
the dns_resolver and dns_request modules, and may in the future
be used by others such as dns_xfrin. it doesn't make sense for it
to live in the resolver object; this commit moves it into dns_view.
Tony Finch [Thu, 29 Dec 2022 19:18:00 +0000 (19:18 +0000)]
QSBR: safe memory reclamation for lock-free data structures
This "quiescent state based reclamation" module provides support for
the qp-trie module in dns/qp. It is a replacement for liburcu, written
without reference to the urcu source code, and in fact it works in a
significantly different way.
A few specifics of BIND make this variant of QSBR somewhat simpler:
* We can require that wait-free access to a qp-trie only happens in
an isc_loop callback. The loop provides a natural quiescent state,
after the callbacks are done, when no qp-trie access occurs.
* We can dispense with any API like rcu_synchronize(). In practice,
it takes far too long to wait for a grace period to elapse for each
write to a data structure.
* We use the idea of "phases" (aka epochs or eras) from EBR to
reduce the amount of bookkeeping needed to track memory that is no
longer needed, knowing that the qp-trie does most of that work
already.
I considered hazard pointers for safe memory reclamation. They have
more read-side overhead (updating the hazard pointers) and it wasn't
clear to me how to nicely schedule the cleanup work. Another
alternative, epoch-based reclamation, is designed for fine-grained
lock-free updates, so it needs some rethinking to work well with the
heavily read-biased design of the qp-trie. QSBR has the fastest read
side of the basic SMR algorithms (with no barriers), and fits well
into a libuv loop. More recent hybrid SMR algorithms do not appear to
have enough benefits to justify the extra complexity.
Evan Hunt [Tue, 21 Feb 2023 22:39:43 +0000 (14:39 -0800)]
remove isc_glob
the isc_glob module was originally needed to support posix-style glob
processing on Windows, but is now just an unnecessary wrapper around
glob(3). this commit removes it.
Evan Hunt [Tue, 21 Feb 2023 22:31:58 +0000 (14:31 -0800)]
fix a crash from using an empty string for "include"
the parser could crash when "include" specified an empty string in place
of the filename. this has been fixed by returning ISC_R_FILENOTFOUND
when the string length is 0.