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.
Ondřej Surý [Mon, 20 Feb 2023 15:16:07 +0000 (16:16 +0100)]
Use atomic stack for async job queue
Previously, the async job queue would use a locked-list (ISC_LIST).
With introduction of atomic stack (that has to be drained at once), we
could use it to remove some contention between the threads and simplify
the async queue.
Fortunately, the reverse order still works for us - instead of append
and tail/prev operation on the list, we are now using prepend and
head/next operation on the atomic stack.
Tony Finch [Mon, 2 Jan 2023 14:49:52 +0000 (14:49 +0000)]
Simple lock-free stack in <isc/stack.h>
Add a singly-linked stack that supports lock-free prepend and drain (to
empty the list and clean up its elements). Intended for use with QSBR
to collect objects that need safe memory reclamation, or any other user
that works with adding objects to the stack and then draining them in
one go like various work queues.
In <isc/atomic.h>, add an `atomic_ptr()` macro to make type
declarations a little less abominable, and clean up a duplicate
definition of `atomic_compare_exchange_strong_acq_rel()`
Aram Sargsyan [Fri, 11 Nov 2022 14:44:26 +0000 (14:44 +0000)]
Add tests for CVE-2022-3924
Reproduce the assertion by configuring a 'named' resolver with
'recursive-clients 10;' configuration option and running 20
queries is parallel.
Also tweak the 'ans2/ans.pl' to simulate a 50ms network latency
when qname starts with "latency". This makes sure that queries
running in parallel don't get served immediately, thus allowing
the configured recursive clients quota limitation to be activated.
Evan Hunt [Tue, 21 Feb 2023 20:21:32 +0000 (12:21 -0800)]
remove references to obsolete isc_task/timer functions
removed references in code comments, doc/dev documentation, etc, to
isc_task, isc_timer_reset(), and isc_timertype_inactive. also removed a
coccinelle patch related to isc_timer_reset() that was no longer needed.
Evan Hunt [Fri, 10 Feb 2023 07:21:57 +0000 (23:21 -0800)]
make builtin a standalone dns_db implementation
instead of using the SDB API as a wrapper to register and
unregister and provide a call framework for the builtin databases,
this commit flattens things so that the builtin databases implement
dns_db directly.
Evan Hunt [Fri, 17 Feb 2023 21:04:12 +0000 (13:04 -0800)]
enable detailed db tracing
move database attach/detach functions to db.c, instead of
requiring them to be implemented for every database type.
instead, they must implement a 'destroy' function that is
called when references go to zero.
this enables us to use ISC_REFCOUNT_IMPL for databases,
with detailed tracing enabled by setting DNS_DB_TRACE to 1.
Evan Hunt [Fri, 17 Feb 2023 20:04:32 +0000 (12:04 -0800)]
simplify dns_sdb API
SDB is currently (and foreseeably) only used by the named
builtin databases, so it only needs as much of its API as
those databases use.
- removed three flags defined for the SDB API that were always
set the same by builtin databases.
- there were two different types of lookup functions defined for
SDB, using slightly different function signatures. since backward
compatibility is no longer a concern, we can eliminate the 'lookup'
entry point and rename 'lookup2' to 'lookup'.
- removed the 'allnodes' entry point and all database iterator
implementation code
- removed dns_sdb_putnamedrr() and dns_sdb_putnamedrdata() since
they were never used.
Evan Hunt [Fri, 17 Feb 2023 19:46:58 +0000 (11:46 -0800)]
use member name initialization for methods
initialize dns_dbmethods, dns_sdbmethods and dns_rdatasetmethods
using explicit struct member names, so we don't have to keep track
of NULLs for unimplemented functions any longer.
Evan Hunt [Fri, 17 Feb 2023 20:05:25 +0000 (12:05 -0800)]
make fewer dns_db functions mandatory-to-implement
some dns_db functions would have crashed if the DB implementation failed
to implement them, requiring the implementations to add functions that
did nothing but return ISC_R_NOTIMPLEMENTED or some obvious default
value. we can just have the dns_db wrapper functions themselves return
those values, and clean up the implementations accordingly.
Evan Hunt [Fri, 17 Feb 2023 19:57:05 +0000 (11:57 -0800)]
remove rdatalist_p.h
make the private isc__rdatalist_* functions public dns_rdatalist
functions so that all the rdatalist primitives can be used by
callers to libdns. (this will be needed later for moving SDB and
SDLZ out of libdns.)
Mark Andrews [Tue, 21 Feb 2023 02:37:24 +0000 (13:37 +1100)]
Cleanup left over 'fctx != NULL' test following refactoring
This was causing 'CID 436299: Null pointer dereferences (REVERSE_INULL)'
in Coverity. Also removed an 'INSIST(fctx != NULL);' that should
no longer be needed.
Aram Sargsyan [Fri, 17 Feb 2023 12:41:29 +0000 (12:41 +0000)]
Detach rpzs and catzs from the previous view
When switching to a new view during a reconfiguration (or reverting
to the old view), detach the 'rpzs' and 'catzs' from the previuos view.
The 'catzs' case was earlier solved slightly differently, by detaching
from the new view when reverting to the old view, but we can not solve
this the same way for 'rpzs', because now in BIND 9.19 and BIND 9.18
a dns_rpz_shutdown_rpzs() call was added in view's destroy() function
before detaching the 'rpzs', so we can not leave the 'rpzs' attached to
the previous view and let it be shut down when we intend to continue
using it with the new view.
Instead, "re-fix" the issue for the 'catzs' pointer the same way as
for 'rpzs' for consistency, and also because a similar shutdown call
is likely to be implemented for 'catzs' in the near future.