resolved: don't request the SOA for every dns label

When validating insecure delegations we don't actually need to request
the SOA for every single dns label. We need the DS records for the zone,
and we can seek them by querying for DS directly (in case we are at a
zone cut) and then following the SOA referrals or the parent name until
we have found a chain of trust.

Extra transactions and roundtrips, especially transactions for RRs that
aren't actually needed to validate and therefore aren't likely to be in
the recursive resolver's own cache are a big slowdown during validation.

Consequently, this change results in an enourmous speed up in validating
most names from our own cold-cache (10x or more), by eliminating a large
number of superfluous dnssec transactions.

1 files changed, 71 insertions, 86 deletions

diff --git a/src/resolve/resolved-dns-transaction.c b/src/resolve/resolved-dns-transaction.c
index 5af550bc59..c90be47dbe 100644
--- a/src/resolve/resolved-dns-transaction.c
+++ b/src/resolve/resolved-dns-transaction.c
@@ -2437,6 +2437,8 @@ static bool dns_transaction_dnssec_supported_full(DnsTransaction *t) {
 int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
         DnsResourceRecord *rr;
 
+        /* Have we already requested a record that would be sufficient to validate an insecure delegation? */
+        bool chased_insecure = false;
         int r;
 
         assert(t);
@@ -2449,11 +2451,11 @@ int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
          * - For RRSIG we get the matching DNSKEY
          * - For DNSKEY we get the matching DS
          * - For unsigned SOA/NS we get the matching DS
-         * - For unsigned CNAME/DNAME/DS we get the parent SOA RR
-         * - For other unsigned RRs we get the matching SOA RR
+         * - For unsigned CNAME/DNAME/DS we get the parent DS RR
+         * - For other unsigned RRs we get the matching DS RR
          * - For SOA/NS queries with no matching response RR, and no NSEC/NSEC3, the DS RR
-         * - For DS queries with no matching response RRs, and no NSEC/NSEC3, the parent's SOA RR
-         * - For other queries with no matching response RRs, and no NSEC/NSEC3, the SOA RR
+         * - For DS queries with no matching response RRs, and no NSEC/NSEC3, the parent's DS RR
+         * - For other queries with no matching response RRs, and no NSEC/NSEC3, the DS RR
          */
 
         if (FLAGS_SET(t->query_flags, SD_RESOLVED_NO_VALIDATE) || t->scope->dnssec_mode == DNSSEC_NO)
@@ -2593,6 +2595,7 @@ int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
                         if (r > 0)
                                 continue;
 
+                        chased_insecure = true;
                         ds = dns_resource_key_new(rr->key->class, DNS_TYPE_DS, dns_resource_key_name(rr->key));
                         if (!ds)
                                 return -ENOMEM;
@@ -2609,11 +2612,11 @@ int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
                 case DNS_TYPE_DS:
                 case DNS_TYPE_CNAME:
                 case DNS_TYPE_DNAME: {
-                        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *soa = NULL;
+                        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *ds = NULL;
                         const char *name;
 
                         /* CNAMEs and DNAMEs cannot be located at a
-                         * zone apex, hence ask for the parent SOA for
+                         * zone apex, hence ask for the parent DS for
                          * unsigned CNAME/DNAME RRs, maybe that's the
                          * apex. But do all that only if this is
                          * actually a response to our original
@@ -2647,13 +2650,13 @@ int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
                         if (r == 0)
                                 continue;
 
-                        soa = dns_resource_key_new(rr->key->class, DNS_TYPE_SOA, name);
-                        if (!soa)
+                        ds = dns_resource_key_new(rr->key->class, DNS_TYPE_DS, name);
+                        if (!ds)
                                 return -ENOMEM;
 
-                        log_debug("Requesting parent SOA to validate transaction %" PRIu16 " (%s, unsigned CNAME/DNAME/DS RRset).",
+                        log_debug("Requesting parent DS to validate transaction %" PRIu16 " (%s, unsigned CNAME/DNAME/DS RRset).",
                                   t->id, dns_resource_key_name(rr->key));
-                        r = dns_transaction_request_dnssec_rr(t, soa);
+                        r = dns_transaction_request_dnssec_rr(t, ds);
                         if (r < 0)
                                 return r;
 
@@ -2661,11 +2664,11 @@ int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
                 }
 
                 default: {
-                        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *soa = NULL;
+                        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *ds = NULL;
 
                         /* For other unsigned RRsets (including
                          * NSEC/NSEC3!), look for proof the zone is
-                         * unsigned, by requesting the SOA RR of the
+                         * unsigned, by requesting the DS RR of the
                          * zone. However, do so only if they are
                          * directly relevant to our original
                          * question. */
@@ -2682,13 +2685,13 @@ int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
                         if (r > 0)
                                 continue;
 
-                        soa = dns_resource_key_new(rr->key->class, DNS_TYPE_SOA, dns_resource_key_name(rr->key));
-                        if (!soa)
+                        ds = dns_resource_key_new(rr->key->class, DNS_TYPE_DS, dns_resource_key_name(rr->key));
+                        if (!ds)
                                 return -ENOMEM;
 
-                        log_debug("Requesting SOA to validate transaction %" PRIu16 " (%s, unsigned non-SOA/NS RRset <%s>).",
+                        log_debug("Requesting DS to validate transaction %" PRIu16 " (%s, unsigned non-SOA/NS RRset <%s>).",
                                   t->id, dns_resource_key_name(rr->key), dns_resource_record_to_string(rr));
-                        r = dns_transaction_request_dnssec_rr(t, soa);
+                        r = dns_transaction_request_dnssec_rr(t, ds);
                         if (r < 0)
                                 return r;
                         break;
@@ -2703,49 +2706,38 @@ int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
         if (r < 0)
                 return r;
         if (r > 0) {
-                const char *name, *signed_status;
-                uint16_t type = 0;
-
-                name = dns_resource_key_name(dns_transaction_key(t));
-                signed_status = dns_answer_contains_nsec_or_nsec3(t->answer) ? "signed" : "unsigned";
-
-                /* If this was a SOA or NS request, then check if there's a DS RR for the same domain. Note that this
-                 * could also be used as indication that we are not at a zone apex, but in real world setups there are
-                 * too many broken DNS servers (Hello, incapdns.net!) where non-terminal zones return NXDOMAIN even
-                 * though they have further children. If this was a DS request, then it's signed when the parent zone
-                 * is signed, hence ask the parent SOA in that case. If this was any other RR then ask for the SOA RR,
-                 * to see if that is signed. */
+                const char *name = dns_resource_key_name(dns_transaction_key(t));
+                bool was_signed = dns_answer_contains_nsec_or_nsec3(t->answer);
 
-                if (dns_transaction_key(t)->type == DNS_TYPE_DS) {
-                        r = dns_name_parent(&name);
-                        if (r > 0) {
-                                type = DNS_TYPE_SOA;
-                                log_debug("Requesting parent SOA (%s %s) to validate transaction %" PRIu16 " (%s, %s empty DS response).",
-                                          special_glyph(SPECIAL_GLYPH_ARROW_RIGHT), name, t->id,
-                                          dns_resource_key_name(dns_transaction_key(t)), signed_status);
-                        } else
+                /* If the response is empty, seek the DS for this name, just in case we're at a zone cut
+                 * already, unless we just requested the DS, in which case we have to ask the parent to make
+                 * progress.
+                 *
+                 * If this was an SOA or NS request, we could also skip to the parent, but in real world
+                 * setups there are too many broken DNS servers (Hello, incapdns.net!) where non-terminal
+                 * zones return NXDOMAIN even though they have further children. */
+
+                if (chased_insecure || was_signed)
+                        /* In this case we already reqeusted what we need above. */
+                        name = NULL;
+                else if (dns_transaction_key(t)->type == DNS_TYPE_DS)
+                        /* If the DS response is empty, we'll walk up the dns labels requesting DS until we
+                         * find a referral to the SOA or hit it anyway and get a positive DS response. */
+                        if (dns_name_parent(&name) <= 0)
                                 name = NULL;
 
-                } else if (IN_SET(dns_transaction_key(t)->type, DNS_TYPE_SOA, DNS_TYPE_NS)) {
-
-                        type = DNS_TYPE_DS;
-                        log_debug("Requesting DS (%s %s) to validate transaction %" PRIu16 " (%s, %s empty SOA/NS response).",
-                                  special_glyph(SPECIAL_GLYPH_ARROW_RIGHT), name, t->id, name, signed_status);
-
-                } else {
-                        type = DNS_TYPE_SOA;
-                        log_debug("Requesting SOA (%s %s) to validate transaction %" PRIu16 " (%s, %s empty non-SOA/NS/DS response).",
-                                  special_glyph(SPECIAL_GLYPH_ARROW_RIGHT), name, t->id, name, signed_status);
-                }
-
                 if (name) {
-                        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *soa = NULL;
+                        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *ds = NULL;
 
-                        soa = dns_resource_key_new(dns_transaction_key(t)->class, type, name);
-                        if (!soa)
+                        log_debug("Requesting DS (%s %s) to validate transaction %" PRIu16 " (%s empty response).",
+                                  special_glyph(SPECIAL_GLYPH_ARROW_RIGHT), name, t->id,
+                                  dns_resource_key_name(dns_transaction_key(t)));
+
+                        ds = dns_resource_key_new(dns_transaction_key(t)->class, DNS_TYPE_DS, name);
+                        if (!ds)
                                 return -ENOMEM;
 
-                        r = dns_transaction_request_dnssec_rr(t, soa);
+                        r = dns_transaction_request_dnssec_rr(t, ds);
                         if (r < 0)
                                 return r;
                 }
@@ -2825,7 +2817,6 @@ static int dns_transaction_requires_rrsig(DnsTransaction *t, DnsResourceRecord *
                 DnsTransaction *dt;
 
                 /* For SOA or NS RRs we look for a matching DS transaction */
-
                 SET_FOREACH(dt, t->dnssec_transactions) {
 
                         if (dns_transaction_key(dt)->class != rr->key->class)
@@ -2833,7 +2824,7 @@ static int dns_transaction_requires_rrsig(DnsTransaction *t, DnsResourceRecord *
                         if (dns_transaction_key(dt)->type != DNS_TYPE_DS)
                                 continue;
 
-                        r = dns_name_equal(dns_resource_key_name(dns_transaction_key(dt)), dns_resource_key_name(rr->key));
+                        r = dns_name_endswith(dns_resource_key_name(rr->key), dns_resource_key_name(dns_transaction_key(dt)));
                         if (r < 0)
                                 return r;
                         if (r == 0)
@@ -2862,16 +2853,16 @@ static int dns_transaction_requires_rrsig(DnsTransaction *t, DnsResourceRecord *
                 DnsTransaction *dt;
 
                 /*
-                 * CNAME/DNAME RRs cannot be located at a zone apex, hence look directly for the parent SOA.
+                 * CNAME/DNAME RRs cannot be located at a zone apex, hence look directly for the parent DS.
                  *
-                 * DS RRs are signed if the parent is signed, hence also look at the parent SOA
+                 * DS RRs are signed if the parent is signed, hence also look at the parent DS
                  */
 
                 SET_FOREACH(dt, t->dnssec_transactions) {
 
                         if (dns_transaction_key(dt)->class != rr->key->class)
                                 continue;
-                        if (dns_transaction_key(dt)->type != DNS_TYPE_SOA)
+                        if (dns_transaction_key(dt)->type != DNS_TYPE_DS)
                                 continue;
 
                         if (!parent) {
@@ -2889,7 +2880,7 @@ static int dns_transaction_requires_rrsig(DnsTransaction *t, DnsResourceRecord *
                                 }
                         }
 
-                        r = dns_name_equal(dns_resource_key_name(dns_transaction_key(dt)), parent);
+                        r = dns_name_endswith(parent, dns_resource_key_name(dns_transaction_key(dt)));
                         if (r < 0)
                                 return r;
                         if (r == 0)
@@ -2904,25 +2895,26 @@ static int dns_transaction_requires_rrsig(DnsTransaction *t, DnsResourceRecord *
         default: {
                 DnsTransaction *dt;
 
-                /* Any other kind of RR (including DNSKEY/NSEC/NSEC3). Let's see if our SOA lookup was authenticated */
+                /* Any other kind of RR (including DNSKEY/NSEC/NSEC3). Let's see if our DS lookup was authenticated */
 
                 SET_FOREACH(dt, t->dnssec_transactions) {
-
                         if (dns_transaction_key(dt)->class != rr->key->class)
                                 continue;
-                        if (dns_transaction_key(dt)->type != DNS_TYPE_SOA)
+                        if (dns_transaction_key(dt)->type != DNS_TYPE_DS)
                                 continue;
 
-                        r = dns_name_equal(dns_resource_key_name(dns_transaction_key(dt)), dns_resource_key_name(rr->key));
+                        r = dns_name_endswith(dns_resource_key_name(rr->key), dns_resource_key_name(dns_transaction_key(dt)));
                         if (r < 0)
                                 return r;
                         if (r == 0)
                                 continue;
 
-                        /* We found the transaction that was supposed to find the SOA RR for us. It was
-                         * successful, but found no RR for us. This means we are not at a zone cut. In this
-                         * case, we require authentication if the SOA lookup was authenticated too. */
-                        return FLAGS_SET(dt->answer_query_flags, SD_RESOLVED_AUTHENTICATED);
+                        if (!FLAGS_SET(dt->answer_query_flags, SD_RESOLVED_AUTHENTICATED))
+                                return false;
+
+                        /* We expect this to be signed when the DS record exists, and don't expect it to be
+                         * signed when the DS record is proven not to exist. */
+                        return dns_answer_match_key(dt->answer, dns_transaction_key(dt), NULL);
                 }
 
                 return true;
@@ -2992,7 +2984,6 @@ static int dns_transaction_requires_nsec(DnsTransaction *t) {
         char key_str[DNS_RESOURCE_KEY_STRING_MAX];
         DnsTransaction *dt;
         const char *name;
-        uint16_t type = 0;
         int r;
 
         assert(t);
@@ -3027,43 +3018,37 @@ static int dns_transaction_requires_nsec(DnsTransaction *t) {
 
         name = dns_resource_key_name(dns_transaction_key(t));
 
-        if (dns_transaction_key(t)->type == DNS_TYPE_DS) {
-
-                /* We got a negative reply for this DS lookup? DS RRs are signed when their parent zone is signed,
-                 * hence check the parent SOA in this case. */
-
+        if (IN_SET(dns_transaction_key(t)->type, DNS_TYPE_DS, DNS_TYPE_CNAME, DNS_TYPE_DNAME)) {
+                /* We got a negative reply for this DS/CNAME/DNAME lookup? Check the parent in this case to
+                 * see if this answer should have been signed. */
                 r = dns_name_parent(&name);
                 if (r < 0)
                         return r;
                 if (r == 0)
                         return true;
+        }
 
-                type = DNS_TYPE_SOA;
-
-        } else if (IN_SET(dns_transaction_key(t)->type, DNS_TYPE_SOA, DNS_TYPE_NS))
-                /* We got a negative reply for this SOA/NS lookup? If so, check if there's a DS RR for this */
-                type = DNS_TYPE_DS;
-        else
-                /* For all other negative replies, check for the SOA lookup */
-                type = DNS_TYPE_SOA;
-
-        /* For all other RRs we check the SOA on the same level to see
+        /* For all other RRs we check the DS on the same level to see
          * if it's signed. */
 
         SET_FOREACH(dt, t->dnssec_transactions) {
-
                 if (dns_transaction_key(dt)->class != dns_transaction_key(t)->class)
                         continue;
-                if (dns_transaction_key(dt)->type != type)
+                if (dns_transaction_key(dt)->type != DNS_TYPE_DS)
                         continue;
 
-                r = dns_name_equal(dns_resource_key_name(dns_transaction_key(dt)), name);
+                r = dns_name_endswith(name, dns_resource_key_name(dns_transaction_key(dt)));
                 if (r < 0)
                         return r;
                 if (r == 0)
                         continue;
 
-                return FLAGS_SET(dt->answer_query_flags, SD_RESOLVED_AUTHENTICATED);
+                if (!FLAGS_SET(dt->answer_query_flags, SD_RESOLVED_AUTHENTICATED))
+                        return false;
+
+                /* We expect this to be signed when the DS record exists, and don't expect it to be signed
+                 * when the DS record is proven not to exist. */
+                return dns_answer_match_key(dt->answer, dns_transaction_key(dt), NULL);
         }
 
         /* If in doubt, require NSEC/NSEC3 */