resolved: fully support DNS search domains

This adds support for searching single-label hostnames in a set of
configured search domains.

A new object DnsQueryCandidate is added that links queries to scopes.
It keeps track of the search domain last used for a query on a specific
link. Whenever a host name was unsuccessfuly resolved on a scope all its
transactions are flushed out and replaced by a new set, with the next
search domain appended.

This also adds a new flag SD_RESOLVED_NO_SEARCH to disable search domain
behaviour. The "systemd-resolve-host" tool is updated to make this
configurable via --search=.

Fixes #1697

1 files changed, 390 insertions, 147 deletions

diff --git a/src/resolve/resolved-dns-query.c b/src/resolve/resolved-dns-query.c
index 0970f3ead7..b84f5bf0f3 100644
--- a/src/resolve/resolved-dns-query.c
+++ b/src/resolve/resolved-dns-query.c
@@ -32,19 +32,277 @@
 #define QUERIES_MAX 2048
 #define AUXILIARY_QUERIES_MAX 64
 
-static void dns_query_stop(DnsQuery *q) {
-        DnsTransaction *t;
+static int dns_query_candidate_new(DnsQueryCandidate **ret, DnsQuery *q, DnsScope *s) {
+        DnsQueryCandidate *c;
 
+        assert(ret);
         assert(q);
+        assert(s);
 
-        q->timeout_event_source = sd_event_source_unref(q->timeout_event_source);
+        c = new0(DnsQueryCandidate, 1);
+        if (!c)
+                return -ENOMEM;
+
+        c->query = q;
+        c->scope = s;
+
+        LIST_PREPEND(candidates_by_query, q->candidates, c);
+        LIST_PREPEND(candidates_by_scope, s->query_candidates, c);
+
+        *ret = c;
+        return 0;
+}
+
+static void dns_query_candidate_stop(DnsQueryCandidate *c) {
+        DnsTransaction *t;
 
-        while ((t = set_steal_first(q->transactions))) {
-                set_remove(t->queries, q);
+        assert(c);
+
+        while ((t = set_steal_first(c->transactions))) {
+                set_remove(t->query_candidates, c);
                 dns_transaction_gc(t);
         }
 }
 
+DnsQueryCandidate* dns_query_candidate_free(DnsQueryCandidate *c) {
+
+        if (!c)
+                return NULL;
+
+        dns_query_candidate_stop(c);
+
+        set_free(c->transactions);
+        dns_search_domain_unref(c->search_domain);
+
+        if (c->query)
+                LIST_REMOVE(candidates_by_query, c->query->candidates, c);
+
+        if (c->scope)
+                LIST_REMOVE(candidates_by_scope, c->scope->query_candidates, c);
+
+        free(c);
+
+        return NULL;
+}
+
+static int dns_query_candidate_next_search_domain(DnsQueryCandidate *c) {
+        _cleanup_(dns_search_domain_unrefp) DnsSearchDomain *previous = NULL;
+        DnsSearchDomain *next = NULL;
+
+        assert(c);
+
+        if (c->search_domain && c->search_domain->linked) {
+                next = c->search_domain->domains_next;
+
+                if (!next) {
+                        /* We hit the last entry. Let's see if this
+                         * was the per-link search domain list. If so,
+                         * let's continue with the global one. */
+
+                        if (c->search_domain->type == DNS_SEARCH_DOMAIN_LINK)
+                                next = c->query->manager->search_domains;
+
+                        if (!next) /* Still no item? Then we really hit the end of the list. */
+                                return 0;
+                }
+
+        } else {
+                /* If we have, start with the per-link domains */
+                next = dns_scope_get_search_domains(c->scope);
+
+                if (!next) /* Fall back to the global search domains */
+                        next = c->scope->manager->search_domains;
+
+                if (!next) /* OK, there's really nothing. */
+                        return 0;
+        }
+
+        dns_search_domain_unref(c->search_domain);
+        c->search_domain = dns_search_domain_ref(next);
+        return 1;
+}
+
+static int dns_query_candidate_add_transaction(DnsQueryCandidate *c, DnsResourceKey *key) {
+        DnsTransaction *t;
+        int r;
+
+        assert(c);
+        assert(key);
+
+        r = set_ensure_allocated(&c->transactions, NULL);
+        if (r < 0)
+                return r;
+
+        t = dns_scope_find_transaction(c->scope, key, true);
+        if (!t) {
+                r = dns_transaction_new(&t, c->scope, key);
+                if (r < 0)
+                        return r;
+        }
+
+        r = set_ensure_allocated(&t->query_candidates, NULL);
+        if (r < 0)
+                goto gc;
+
+        r = set_put(t->query_candidates, c);
+        if (r < 0)
+                goto gc;
+
+        r = set_put(c->transactions, t);
+        if (r < 0) {
+                set_remove(t->query_candidates, c);
+                goto gc;
+        }
+
+        return 0;
+
+gc:
+        dns_transaction_gc(t);
+        return r;
+}
+
+static int dns_query_candidate_go(DnsQueryCandidate *c) {
+        DnsTransaction *t;
+        Iterator i;
+        int r;
+
+        assert(c);
+
+        /* Start the transactions that are not started yet */
+        SET_FOREACH(t, c->transactions, i) {
+                if (t->state != DNS_TRANSACTION_NULL)
+                        continue;
+
+                r = dns_transaction_go(t);
+                if (r < 0)
+                        return r;
+        }
+
+        return 0;
+}
+
+static DnsTransactionState dns_query_candidate_state(DnsQueryCandidate *c) {
+        DnsTransactionState state = DNS_TRANSACTION_NO_SERVERS;
+        DnsTransaction *t;
+        Iterator i;
+
+        assert(c);
+
+        if (c->error_code != 0)
+                return DNS_TRANSACTION_RESOURCES;
+
+        SET_FOREACH(t, c->transactions, i) {
+
+                switch (t->state) {
+
+                case DNS_TRANSACTION_PENDING:
+                case DNS_TRANSACTION_NULL:
+                        return t->state;
+
+                case DNS_TRANSACTION_SUCCESS:
+                        state = t->state;
+                        break;
+
+                default:
+                        if (state != DNS_TRANSACTION_SUCCESS)
+                                state = t->state;
+
+                        break;
+                }
+        }
+
+        return state;
+}
+
+static int dns_query_candidate_setup_transactions(DnsQueryCandidate *c) {
+        DnsResourceKey *key;
+        int n = 0, r;
+
+        assert(c);
+
+        dns_query_candidate_stop(c);
+
+        /* Create one transaction per question key */
+        DNS_QUESTION_FOREACH(key, c->query->question) {
+                _cleanup_(dns_resource_key_unrefp) DnsResourceKey *new_key = NULL;
+
+                if (c->search_domain) {
+                        r = dns_resource_key_new_append_suffix(&new_key, key, c->search_domain->name);
+                        if (r < 0)
+                                goto fail;
+                }
+
+                r = dns_query_candidate_add_transaction(c, new_key ?: key);
+                if (r < 0)
+                        goto fail;
+
+                n++;
+        }
+
+        return n;
+
+fail:
+        dns_query_candidate_stop(c);
+        return r;
+}
+
+void dns_query_candidate_ready(DnsQueryCandidate *c) {
+        DnsTransactionState state;
+        int r;
+
+        assert(c);
+
+        state = dns_query_candidate_state(c);
+
+        if (IN_SET(state, DNS_TRANSACTION_PENDING, DNS_TRANSACTION_NULL))
+                return;
+
+        if (state != DNS_TRANSACTION_SUCCESS && c->search_domain) {
+
+                r = dns_query_candidate_next_search_domain(c);
+                if (r < 0)
+                        goto fail;
+
+                if (r > 0) {
+                        /* OK, there's another search domain to try, let's do so. */
+
+                        r = dns_query_candidate_setup_transactions(c);
+                        if (r < 0)
+                                goto fail;
+
+                        if (r > 0) {
+                                /* New transactions where queued. Start them and wait */
+
+                                r = dns_query_candidate_go(c);
+                                if (r < 0)
+                                        goto fail;
+
+                                return;
+                        }
+                }
+
+        }
+
+        dns_query_ready(c->query);
+        return;
+
+fail:
+        log_warning_errno(r, "Failed to follow search domains: %m");
+        c->error_code = r;
+        dns_query_ready(c->query);
+}
+
+static void dns_query_stop(DnsQuery *q) {
+        DnsQueryCandidate *c;
+
+        assert(q);
+
+        q->timeout_event_source = sd_event_source_unref(q->timeout_event_source);
+
+        LIST_FOREACH(candidates_by_query, c, q->candidates)
+                dns_query_candidate_stop(c);
+}
+
 DnsQuery *dns_query_free(DnsQuery *q) {
         if (!q)
                 return NULL;
@@ -58,11 +316,12 @@ DnsQuery *dns_query_free(DnsQuery *q) {
                 LIST_REMOVE(auxiliary_queries, q->auxiliary_for->auxiliary_queries, q);
         }
 
-        dns_query_stop(q);
-        set_free(q->transactions);
+        while (q->candidates)
+                dns_query_candidate_free(q->candidates);
 
         dns_question_unref(q->question);
         dns_answer_unref(q->answer);
+        dns_search_domain_unref(q->answer_search_domain);
 
         sd_bus_message_unref(q->request);
         sd_bus_track_unref(q->bus_track);
@@ -99,6 +358,8 @@ int dns_query_new(Manager *m, DnsQuery **ret, DnsQuestion *question, int ifindex
         q->question = dns_question_ref(question);
         q->ifindex = ifindex;
         q->flags = flags;
+        q->answer_family = AF_UNSPEC;
+        q->answer_protocol = _DNS_PROTOCOL_INVALID;
 
         for (i = 0; i < question->n_keys; i++) {
                 _cleanup_free_ char *p;
@@ -170,64 +431,40 @@ static int on_query_timeout(sd_event_source *s, usec_t usec, void *userdata) {
         return 0;
 }
 
-static int dns_query_add_transaction(DnsQuery *q, DnsScope *s, DnsResourceKey *key) {
-        DnsTransaction *t;
+static int dns_query_add_candidate(DnsQuery *q, DnsScope *s) {
+        DnsQueryCandidate *c;
         int r;
 
         assert(q);
         assert(s);
-        assert(key);
 
-        r = set_ensure_allocated(&q->transactions, NULL);
+        r = dns_query_candidate_new(&c, q, s);
         if (r < 0)
                 return r;
 
-        t = dns_scope_find_transaction(s, key, true);
-        if (!t) {
-                r = dns_transaction_new(&t, s, key);
-                if (r < 0)
-                        return r;
-        }
-
-        r = set_ensure_allocated(&t->queries, NULL);
-        if (r < 0)
-                goto gc;
-
-        r = set_put(t->queries, q);
+        /* If this a single-label domain on DNS, we might append a suitable search domain first. */
+        r = dns_scope_name_needs_search_domain(s, dns_question_first_name(q->question));
         if (r < 0)
-                goto gc;
+                goto fail;
+        if (r > 0) {
+                /* OK, we need a search domain now. Let's find one for this scope */
 
-        r = set_put(q->transactions, t);
-        if (r < 0) {
-                set_remove(t->queries, q);
-                goto gc;
+                r = dns_query_candidate_next_search_domain(c);
+                if (r <= 0) /* if there's no search domain, then we won't add any transaction. */
+                        goto fail;
         }
 
+        r = dns_query_candidate_setup_transactions(c);
+        if (r < 0)
+                goto fail;
+
         return 0;
 
-gc:
-        dns_transaction_gc(t);
+fail:
+        dns_query_candidate_free(c);
         return r;
 }
 
-static int dns_query_add_transaction_split(DnsQuery *q, DnsScope *s) {
-        unsigned i;
-        int r;
-
-        assert(q);
-        assert(s);
-
-        /* Create one transaction per question key */
-
-        for (i = 0; i < q->question->n_keys; i++) {
-                r = dns_query_add_transaction(q, s, q->question->keys[i]);
-                if (r < 0)
-                        return r;
-        }
-
-        return 0;
-}
-
 static int SYNTHESIZE_IFINDEX(int ifindex) {
 
         /* When the caller asked for resolving on a specific
@@ -630,9 +867,9 @@ static int dns_query_synthesize_reply(DnsQuery *q, DnsTransactionState *state) {
         q->answer = answer;
         answer = NULL;
 
-        q->answer_family = SYNTHESIZE_FAMILY(q->flags);
-        q->answer_protocol = SYNTHESIZE_PROTOCOL(q->flags);
         q->answer_rcode = DNS_RCODE_SUCCESS;
+        q->answer_protocol = SYNTHESIZE_PROTOCOL(q->flags);
+        q->answer_family = SYNTHESIZE_FAMILY(q->flags);
 
         *state = DNS_TRANSACTION_SUCCESS;
 
@@ -642,9 +879,8 @@ static int dns_query_synthesize_reply(DnsQuery *q, DnsTransactionState *state) {
 int dns_query_go(DnsQuery *q) {
         DnsScopeMatch found = DNS_SCOPE_NO;
         DnsScope *s, *first = NULL;
-        DnsTransaction *t;
+        DnsQueryCandidate *c;
         const char *name;
-        Iterator i;
         int r;
 
         assert(q);
@@ -688,7 +924,7 @@ int dns_query_go(DnsQuery *q) {
                 return 1;
         }
 
-        r = dns_query_add_transaction_split(q, first);
+        r = dns_query_add_candidate(q, first);
         if (r < 0)
                 goto fail;
 
@@ -702,7 +938,7 @@ int dns_query_go(DnsQuery *q) {
                 if (match != found)
                         continue;
 
-                r = dns_query_add_transaction_split(q, s);
+                r = dns_query_add_candidate(q, s);
                 if (r < 0)
                         goto fail;
         }
@@ -724,14 +960,13 @@ int dns_query_go(DnsQuery *q) {
         q->state = DNS_TRANSACTION_PENDING;
         q->block_ready++;
 
-        /* Start the transactions that are not started yet */
-        SET_FOREACH(t, q->transactions, i) {
-                if (t->state != DNS_TRANSACTION_NULL)
-                        continue;
-
-                r = dns_transaction_go(t);
-                if (r < 0)
+        /* Start the transactions */
+        LIST_FOREACH(candidates_by_query, c, q->candidates) {
+                r = dns_query_candidate_go(c);
+                if (r < 0) {
+                        q->block_ready--;
                         goto fail;
+                }
         }
 
         q->block_ready--;
@@ -744,124 +979,132 @@ fail:
         return r;
 }
 
-void dns_query_ready(DnsQuery *q) {
-        DnsTransaction *t;
+static void dns_query_accept(DnsQuery *q, DnsQueryCandidate *c) {
         DnsTransactionState state = DNS_TRANSACTION_NO_SERVERS;
-        _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
-        int rcode = 0;
-        DnsScope *scope = NULL;
-        bool pending = false;
+        DnsTransaction *t;
         Iterator i;
 
         assert(q);
-        assert(IN_SET(q->state, DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING));
 
-        /* Note that this call might invalidate the query. Callers
-         * should hence not attempt to access the query or transaction
-         * after calling this function, unless the block_ready
-         * counter was explicitly bumped before doing so. */
-
-        if (q->block_ready > 0)
+        if (!c) {
+                dns_query_synthesize_reply(q, &state);
+                dns_query_complete(q, state);
                 return;
+        }
 
-        SET_FOREACH(t, q->transactions, i) {
+        SET_FOREACH(t, c->transactions, i) {
 
-                /* If we found a successful answer, ignore all answers from other scopes */
-                if (state == DNS_TRANSACTION_SUCCESS && t->scope != scope)
-                        continue;
+                switch (t->state) {
 
-                /* One of the transactions is still going on, let's maybe wait for it */
-                if (IN_SET(t->state, DNS_TRANSACTION_PENDING, DNS_TRANSACTION_NULL)) {
-                        pending = true;
-                        continue;
-                }
-
-                /* One of the transactions is successful, let's use
-                 * it, and copy its data out */
-                if (t->state == DNS_TRANSACTION_SUCCESS) {
-                        DnsAnswer *a;
+                case DNS_TRANSACTION_SUCCESS: {
+                        /* We found a successfuly reply, merge it into the answer */
+                        DnsAnswer *merged, *a;
 
                         if (t->received) {
-                                rcode = DNS_PACKET_RCODE(t->received);
+                                q->answer_rcode = DNS_PACKET_RCODE(t->received);
                                 a = t->received->answer;
                         } else {
-                                rcode = t->cached_rcode;
+                                q->answer_rcode = t->cached_rcode;
                                 a = t->cached;
                         }
 
-                        if (state == DNS_TRANSACTION_SUCCESS) {
-                                DnsAnswer *merged;
+                        merged = dns_answer_merge(q->answer, a);
+                        if (!merged) {
+                                dns_query_complete(q, DNS_TRANSACTION_RESOURCES);
+                                return;
+                        }
+
+                        dns_answer_unref(q->answer);
+                        q->answer = merged;
+
+                        state = DNS_TRANSACTION_SUCCESS;
+                        break;
+                }
+
+                case DNS_TRANSACTION_PENDING:
+                case DNS_TRANSACTION_NULL:
+                case DNS_TRANSACTION_ABORTED:
+                        /* Ignore transactions that didn't complete */
+                        continue;
+
+                default:
+                        /* Any kind of failure? Store the data away,
+                         * if there's nothing stored yet. */
 
-                                merged = dns_answer_merge(answer, a);
-                                if (!merged) {
-                                        dns_query_complete(q, DNS_TRANSACTION_RESOURCES);
-                                        return;
+                        if (state != DNS_TRANSACTION_SUCCESS) {
+
+                                dns_answer_unref(q->answer);
+
+                                if (t->received) {
+                                        q->answer = dns_answer_ref(t->received->answer);
+                                        q->answer_rcode = DNS_PACKET_RCODE(t->received);
+                                } else {
+                                        q->answer = dns_answer_ref(t->cached);
+                                        q->answer_rcode = t->cached_rcode;
                                 }
 
-                                dns_answer_unref(answer);
-                                answer = merged;
-                        } else {
-                                dns_answer_unref(answer);
-                                answer = dns_answer_ref(a);
+                                state = t->state;
                         }
 
-                        scope = t->scope;
-                        state = DNS_TRANSACTION_SUCCESS;
-                        continue;
+                        break;
                 }
+        }
 
-                /* One of the transactions has failed, let's see
-                 * whether we find anything better, but if not, return
-                 * its response data */
-                if (state != DNS_TRANSACTION_SUCCESS && t->state == DNS_TRANSACTION_FAILURE) {
-                        DnsAnswer *a;
+        q->answer_protocol = c->scope->protocol;
+        q->answer_family = c->scope->family;
 
-                        if (t->received) {
-                                rcode = DNS_PACKET_RCODE(t->received);
-                                a = t->received->answer;
-                        } else {
-                                rcode = t->cached_rcode;
-                                a = t->cached;
-                        }
+        dns_search_domain_unref(q->answer_search_domain);
+        q->answer_search_domain = dns_search_domain_ref(c->search_domain);
 
-                        dns_answer_unref(answer);
-                        answer = dns_answer_ref(a);
+        dns_query_synthesize_reply(q, &state);
+        dns_query_complete(q, state);
+}
 
-                        scope = t->scope;
-                        state = DNS_TRANSACTION_FAILURE;
-                        continue;
-                }
+void dns_query_ready(DnsQuery *q) {
 
-                if (state == DNS_TRANSACTION_NO_SERVERS && t->state != DNS_TRANSACTION_NO_SERVERS)
-                        state = t->state;
-        }
+        DnsQueryCandidate *bad = NULL, *c;
+        bool pending = false;
 
-        if (pending) {
+        assert(q);
+        assert(IN_SET(q->state, DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING));
 
-                /* If so far we weren't successful, and there's
-                 * something still pending, then wait for it */
-                if (state != DNS_TRANSACTION_SUCCESS)
+        /* Note that this call might invalidate the query. Callers
+         * should hence not attempt to access the query or transaction
+         * after calling this function, unless the block_ready
+         * counter was explicitly bumped before doing so. */
+
+        if (q->block_ready > 0)
+                return;
+
+        LIST_FOREACH(candidates_by_query, c, q->candidates) {
+                DnsTransactionState state;
+
+                state = dns_query_candidate_state(c);
+                switch (state) {
+
+                case DNS_TRANSACTION_SUCCESS:
+                        /* One of the transactions is successful,
+                         * let's use it, and copy its data out */
+                        dns_query_accept(q, c);
                         return;
 
-                /* If we already were successful, then only wait for
-                 * other transactions on the same scope to finish. */
-                SET_FOREACH(t, q->transactions, i) {
-                        if (t->scope == scope && IN_SET(t->state, DNS_TRANSACTION_PENDING, DNS_TRANSACTION_NULL))
-                                return;
-                }
-        }
+                case DNS_TRANSACTION_PENDING:
+                case DNS_TRANSACTION_NULL:
+                        /* One of the transactions is still going on, let's maybe wait for it */
+                        pending = true;
+                        break;
 
-        if (IN_SET(state, DNS_TRANSACTION_SUCCESS, DNS_TRANSACTION_FAILURE)) {
-                q->answer = dns_answer_ref(answer);
-                q->answer_rcode = rcode;
-                q->answer_protocol = scope ? scope->protocol : _DNS_PROTOCOL_INVALID;
-                q->answer_family = scope ? scope->family : AF_UNSPEC;
+                default:
+                        /* Any kind of failure */
+                        bad = c;
+                        break;
+                }
         }
 
-        /* Try to synthesize a reply if we couldn't resolve something. */
-        dns_query_synthesize_reply(q, &state);
+        if (pending)
+                return;
 
-        dns_query_complete(q, state);
+        dns_query_accept(q, bad);
 }
 
 static int dns_query_cname_redirect(DnsQuery *q, const DnsResourceRecord *cname) {
@@ -900,13 +1143,13 @@ int dns_query_process_cname(DnsQuery *q) {
 
         DNS_ANSWER_FOREACH(rr, q->answer) {
 
-                r = dns_question_matches_rr(q->question, rr);
+                r = dns_question_matches_rr(q->question, rr, DNS_SEARCH_DOMAIN_NAME(q->answer_search_domain));
                 if (r < 0)
                         return r;
                 if (r > 0)
                         return 0; /* The answer matches directly, no need to follow cnames */
 
-                r = dns_question_matches_cname(q->question, rr);
+                r = dns_question_matches_cname(q->question, rr, DNS_SEARCH_DOMAIN_NAME(q->answer_search_domain));
                 if (r < 0)
                         return r;
                 if (r > 0 && !cname)
@@ -927,7 +1170,7 @@ int dns_query_process_cname(DnsQuery *q) {
         /* Let's see if the answer can already answer the new
          * redirected question */
         DNS_ANSWER_FOREACH(rr, q->answer) {
-                r = dns_question_matches_rr(q->question, rr);
+                r = dns_question_matches_rr(q->question, rr, NULL);
                 if (r < 0)
                         return r;
                 if (r > 0)