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

16 files changed, 609 insertions, 207 deletions

diff --git a/src/resolve/resolved-bus.c b/src/resolve/resolved-bus.c
index 537afc0d41..8885b83101 100644
--- a/src/resolve/resolved-bus.c
+++ b/src/resolve/resolved-bus.c
@@ -166,7 +166,7 @@ static void bus_method_resolve_hostname_complete(DnsQuery *q) {
                 int ifindex;
 
                 DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, 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)
                                 goto finish;
                         if (r == 0)
@@ -254,7 +254,7 @@ static int bus_method_resolve_hostname(sd_bus_message *message, void *userdata,
         if (r == 0)
                 return sd_bus_error_setf(error, SD_BUS_ERROR_INVALID_ARGS, "Invalid hostname '%s'", hostname);
 
-        r = check_ifindex_flags(ifindex, &flags, 0, error);
+        r = check_ifindex_flags(ifindex, &flags, SD_RESOLVED_NO_SEARCH, error);
         if (r < 0)
                 return r;
 
@@ -310,7 +310,7 @@ static void bus_method_resolve_address_complete(DnsQuery *q) {
 
         if (q->answer) {
                 DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, q->answer) {
-                        r = dns_question_matches_rr(q->question, rr);
+                        r = dns_question_matches_rr(q->question, rr, NULL);
                         if (r < 0)
                                 goto finish;
                         if (r == 0)
@@ -392,7 +392,7 @@ static int bus_method_resolve_address(sd_bus_message *message, void *userdata, s
         if (r < 0)
                 return r;
 
-        r = dns_query_new(m, &q, question, ifindex, flags);
+        r = dns_query_new(m, &q, question, ifindex, flags|SD_RESOLVED_NO_SEARCH);
         if (r < 0)
                 return r;
 
@@ -487,7 +487,7 @@ static void bus_method_resolve_record_complete(DnsQuery *q) {
                 int ifindex;
 
                 DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, q->answer) {
-                        r = dns_question_matches_rr(q->question, rr);
+                        r = dns_question_matches_rr(q->question, rr, NULL);
                         if (r < 0)
                                 goto finish;
                         if (r == 0)
@@ -566,7 +566,7 @@ static int bus_method_resolve_record(sd_bus_message *message, void *userdata, sd
         if (r < 0)
                 return r;
 
-        r = dns_query_new(m, &q, question, ifindex, flags);
+        r = dns_query_new(m, &q, question, ifindex, flags|SD_RESOLVED_NO_SEARCH);
         if (r < 0)
                 return r;
 
@@ -620,7 +620,7 @@ static int append_srv(DnsQuery *q, sd_bus_message *reply, DnsResourceRecord *rr)
 
                         DNS_ANSWER_FOREACH(zz, aux->answer) {
 
-                                r = dns_question_matches_rr(aux->question, zz);
+                                r = dns_question_matches_rr(aux->question, zz, NULL);
                                 if (r < 0)
                                         return r;
                                 if (r == 0)
@@ -672,7 +672,7 @@ static int append_srv(DnsQuery *q, sd_bus_message *reply, DnsResourceRecord *rr)
 
                         DNS_ANSWER_FOREACH_IFINDEX(zz, ifindex, aux->answer) {
 
-                                r = dns_question_matches_rr(aux->question, zz);
+                                r = dns_question_matches_rr(aux->question, zz, NULL);
                                 if (r < 0)
                                         return r;
                                 if (r == 0)
@@ -798,7 +798,7 @@ static void resolve_service_all_complete(DnsQuery *q) {
                 DnsResourceRecord *rr;
 
                 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)
                                 goto finish;
                         if (r == 0)
@@ -834,7 +834,7 @@ static void resolve_service_all_complete(DnsQuery *q) {
                 DnsResourceRecord *rr;
 
                 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)
                                 goto finish;
                         if (r == 0)
@@ -911,7 +911,7 @@ static int resolve_service_hostname(DnsQuery *q, DnsResourceRecord *rr, int ifin
         if (r < 0)
                 return r;
 
-        r = dns_query_new(q->manager, &aux, question, ifindex, q->flags);
+        r = dns_query_new(q->manager, &aux, question, ifindex, q->flags|SD_RESOLVED_NO_SEARCH);
         if (r < 0)
                 return r;
 
@@ -970,7 +970,7 @@ static void bus_method_resolve_service_complete(DnsQuery *q) {
                 int ifindex;
 
                 DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, q->answer) {
-                        r = dns_question_matches_rr(q->question, rr);
+                        r = dns_question_matches_rr(q->question, rr, NULL);
                         if (r < 0)
                                 goto finish;
                         if (r == 0)
@@ -1078,7 +1078,7 @@ static int bus_method_resolve_service(sd_bus_message *message, void *userdata, s
         if (r < 0)
                 return r;
 
-        r = dns_query_new(m, &q, question, ifindex, flags);
+        r = dns_query_new(m, &q, question, ifindex, flags|SD_RESOLVED_NO_SEARCH);
         if (r < 0)
                 return r;
 
diff --git a/src/resolve/resolved-def.h b/src/resolve/resolved-def.h
index 85af1923ff..33f8ddb1f2 100644
--- a/src/resolve/resolved-def.h
+++ b/src/resolve/resolved-def.h
@@ -27,6 +27,7 @@
 #define SD_RESOLVED_NO_CNAME      ((uint64_t) 8)
 #define SD_RESOLVED_NO_TXT        ((uint64_t) 16)
 #define SD_RESOLVED_NO_ADDRESS    ((uint64_t) 32)
+#define SD_RESOLVED_NO_SEARCH     ((uint64_t) 64)
 
 #define SD_RESOLVED_LLMNR         (SD_RESOLVED_LLMNR_IPV4|SD_RESOLVED_LLMNR_IPV6)
 #define SD_RESOLVED_PROTOCOLS_ALL (SD_RESOLVED_LLMNR|SD_RESOLVED_DNS)
diff --git a/src/resolve/resolved-dns-answer.c b/src/resolve/resolved-dns-answer.c
index 3cf9c68074..4db67f7278 100644
--- a/src/resolve/resolved-dns-answer.c
+++ b/src/resolve/resolved-dns-answer.c
@@ -141,7 +141,7 @@ int dns_answer_contains(DnsAnswer *a, DnsResourceKey *key) {
                 return 0;
 
         for (i = 0; i < a->n_rrs; i++) {
-                r = dns_resource_key_match_rr(key, a->items[i].rr);
+                r = dns_resource_key_match_rr(key, a->items[i].rr, NULL);
                 if (r < 0)
                         return r;
                 if (r > 0)
diff --git a/src/resolve/resolved-dns-answer.h b/src/resolve/resolved-dns-answer.h
index b5b1ad56ba..8814919deb 100644
--- a/src/resolve/resolved-dns-answer.h
+++ b/src/resolve/resolved-dns-answer.h
@@ -61,7 +61,7 @@ DEFINE_TRIVIAL_CLEANUP_FUNC(DnsAnswer*, dns_answer_unref);
 
 #define DNS_ANSWER_FOREACH(kk, a)                                       \
         for (unsigned _i = ({                                           \
-                                (kk) = ((a) && (a)->n_rrs > 0 ? (a)->items[0].rr : NULL); \
+                                (kk) = ((a) && (a)->n_rrs > 0) ? (a)->items[0].rr : NULL; \
                                 0;                                      \
                            });                                          \
              (a) && ((_i) < (a)->n_rrs);                                \
@@ -69,9 +69,9 @@ DEFINE_TRIVIAL_CLEANUP_FUNC(DnsAnswer*, dns_answer_unref);
 
 #define DNS_ANSWER_FOREACH_IFINDEX(kk, ifindex, a)                      \
         for (unsigned _i = ({                                           \
-                                (kk) = ((a) && (a)->n_rrs > 0 ? (a)->items[0].rr : NULL); \
-                                (ifindex) = ((a) && (a)->n_rrs > 0 ? (a)->items[0].ifindex : 0); \
+                                (kk) = ((a) && (a)->n_rrs > 0) ? (a)->items[0].rr : NULL; \
+                                (ifindex) = ((a) && (a)->n_rrs > 0) ? (a)->items[0].ifindex : 0; \
                                 0;                                      \
                            });                                          \
              (a) && ((_i) < (a)->n_rrs);                                \
-             _i++, (kk) = (_i < (a)->n_rrs ? (a)->items[_i].rr : NULL), (ifindex) = (_i < (a)->n_rrs ? (a)->items[_i].ifindex : 0))
+             _i++, (kk) = ((_i < (a)->n_rrs) ? (a)->items[_i].rr : NULL), (ifindex) = ((_i < (a)->n_rrs) ? (a)->items[_i].ifindex : 0))
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)
diff --git a/src/resolve/resolved-dns-query.h b/src/resolve/resolved-dns-query.h
index 256dddc00b..fb16747c55 100644
--- a/src/resolve/resolved-dns-query.h
+++ b/src/resolve/resolved-dns-query.h
@@ -26,11 +26,26 @@
 
 #include "set.h"
 
+typedef struct DnsQueryCandidate DnsQueryCandidate;
 typedef struct DnsQuery DnsQuery;
 
 #include "resolved-dns-answer.h"
 #include "resolved-dns-question.h"
 #include "resolved-dns-stream.h"
+#include "resolved-dns-search-domain.h"
+
+struct DnsQueryCandidate {
+        DnsQuery *query;
+        DnsScope *scope;
+
+        DnsSearchDomain *search_domain;
+
+        int error_code;
+        Set *transactions;
+
+        LIST_FIELDS(DnsQueryCandidate, candidates_by_query);
+        LIST_FIELDS(DnsQueryCandidate, candidates_by_scope);
+};
 
 struct DnsQuery {
         Manager *manager;
@@ -45,13 +60,13 @@ struct DnsQuery {
         int auxiliary_result;
 
         DnsQuestion *question;
-
         uint64_t flags;
         int ifindex;
 
         DnsTransactionState state;
         unsigned n_cname_redirects;
 
+        LIST_HEAD(DnsQueryCandidate, candidates);
         sd_event_source *timeout_event_source;
 
         /* Discovered data */
@@ -59,6 +74,7 @@ struct DnsQuery {
         int answer_family;
         DnsProtocol answer_protocol;
         int answer_rcode;
+        DnsSearchDomain *answer_search_domain;
 
         /* Bus client information */
         sd_bus_message *request;
@@ -71,14 +87,15 @@ struct DnsQuery {
         void (*complete)(DnsQuery* q);
         unsigned block_ready;
 
-        Set *transactions;
-
         sd_bus_track *bus_track;
 
         LIST_FIELDS(DnsQuery, queries);
         LIST_FIELDS(DnsQuery, auxiliary_queries);
 };
 
+DnsQueryCandidate* dns_query_candidate_free(DnsQueryCandidate *c);
+void dns_query_candidate_ready(DnsQueryCandidate *c);
+
 int dns_query_new(Manager *m, DnsQuery **q, DnsQuestion *question, int family, uint64_t flags);
 DnsQuery *dns_query_free(DnsQuery *q);
 
diff --git a/src/resolve/resolved-dns-question.c b/src/resolve/resolved-dns-question.c
index b1aa0175e0..3249448d3b 100644
--- a/src/resolve/resolved-dns-question.c
+++ b/src/resolve/resolved-dns-question.c
@@ -89,7 +89,7 @@ int dns_question_add(DnsQuestion *q, DnsResourceKey *key) {
         return 0;
 }
 
-int dns_question_matches_rr(DnsQuestion *q, DnsResourceRecord *rr) {
+int dns_question_matches_rr(DnsQuestion *q, DnsResourceRecord *rr, const char *search_domain) {
         unsigned i;
         int r;
 
@@ -99,7 +99,7 @@ int dns_question_matches_rr(DnsQuestion *q, DnsResourceRecord *rr) {
                 return 0;
 
         for (i = 0; i < q->n_keys; i++) {
-                r = dns_resource_key_match_rr(q->keys[i], rr);
+                r = dns_resource_key_match_rr(q->keys[i], rr, search_domain);
                 if (r != 0)
                         return r;
         }
@@ -107,7 +107,7 @@ int dns_question_matches_rr(DnsQuestion *q, DnsResourceRecord *rr) {
         return 0;
 }
 
-int dns_question_matches_cname(DnsQuestion *q, DnsResourceRecord *rr) {
+int dns_question_matches_cname(DnsQuestion *q, DnsResourceRecord *rr, const char *search_domain) {
         unsigned i;
         int r;
 
@@ -117,7 +117,7 @@ int dns_question_matches_cname(DnsQuestion *q, DnsResourceRecord *rr) {
                 return 0;
 
         for (i = 0; i < q->n_keys; i++) {
-                r = dns_resource_key_match_cname(q->keys[i], rr);
+                r = dns_resource_key_match_cname(q->keys[i], rr, search_domain);
                 if (r != 0)
                         return r;
         }
diff --git a/src/resolve/resolved-dns-question.h b/src/resolve/resolved-dns-question.h
index d728b9bed2..e77116c03a 100644
--- a/src/resolve/resolved-dns-question.h
+++ b/src/resolve/resolved-dns-question.h
@@ -43,8 +43,8 @@ int dns_question_new_service(DnsQuestion **ret, const char *name, bool with_txt)
 
 int dns_question_add(DnsQuestion *q, DnsResourceKey *key);
 
-int dns_question_matches_rr(DnsQuestion *q, DnsResourceRecord *rr);
-int dns_question_matches_cname(DnsQuestion *q, DnsResourceRecord *rr);
+int dns_question_matches_rr(DnsQuestion *q, DnsResourceRecord *rr, const char *search_domain);
+int dns_question_matches_cname(DnsQuestion *q, DnsResourceRecord *rr, const char* search_domain);
 int dns_question_is_valid_for_query(DnsQuestion *q);
 int dns_question_contains(DnsQuestion *a, DnsResourceKey *k);
 int dns_question_is_equal(DnsQuestion *a, DnsQuestion *b);
@@ -54,3 +54,11 @@ int dns_question_cname_redirect(DnsQuestion *q, const DnsResourceRecord *cname,
 const char *dns_question_first_name(DnsQuestion *q);
 
 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsQuestion*, dns_question_unref);
+
+#define DNS_QUESTION_FOREACH(key, q)                                    \
+        for (unsigned _i = ({                                           \
+                                (key) = ((q) && (q)->n_keys > 0) ? (q)->keys[0] : NULL; \
+                                0;                                      \
+                        });                                             \
+             (q) && ((_i) < (q)->n_keys);                               \
+             _i++, (key) = (_i < (q)->n_keys ? (q)->keys[_i] : NULL))
diff --git a/src/resolve/resolved-dns-rr.c b/src/resolve/resolved-dns-rr.c
index 9b264900fc..4f896b05af 100644
--- a/src/resolve/resolved-dns-rr.c
+++ b/src/resolve/resolved-dns-rr.c
@@ -86,6 +86,37 @@ DnsResourceKey* dns_resource_key_new_redirect(const DnsResourceKey *key, const D
         }
 }
 
+int dns_resource_key_new_append_suffix(DnsResourceKey **ret, DnsResourceKey *key, char *name) {
+        DnsResourceKey *new_key;
+        char *joined;
+        int r;
+
+        assert(ret);
+        assert(key);
+        assert(name);
+
+        r = dns_name_root(name);
+        if (r < 0)
+                return r;
+        if (r > 0) {
+                *ret = dns_resource_key_ref(key);
+                return 0;
+        }
+
+        r = dns_name_concat(DNS_RESOURCE_KEY_NAME(key), name, &joined);
+        if (r < 0)
+                return r;
+
+        new_key = dns_resource_key_new_consume(key->class, key->type, joined);
+        if (!new_key) {
+                free(joined);
+                return -ENOMEM;
+        }
+
+        *ret = new_key;
+        return 0;
+}
+
 DnsResourceKey* dns_resource_key_new_consume(uint16_t class, uint16_t type, char *name) {
         DnsResourceKey *k;
 
@@ -145,20 +176,42 @@ int dns_resource_key_equal(const DnsResourceKey *a, const DnsResourceKey *b) {
         return 1;
 }
 
-int dns_resource_key_match_rr(const DnsResourceKey *key, const DnsResourceRecord *rr) {
+int dns_resource_key_match_rr(const DnsResourceKey *key, const DnsResourceRecord *rr, const char *search_domain) {
+        int r;
+
         assert(key);
         assert(rr);
 
+        /* Checks if an rr matches the specified key. If a search
+         * domain is specified, it will also be checked if the key
+         * with the search domain suffixed might match the RR. */
+
         if (rr->key->class != key->class && key->class != DNS_CLASS_ANY)
                 return 0;
 
         if (rr->key->type != key->type && key->type != DNS_TYPE_ANY)
                 return 0;
 
-        return dns_name_equal(DNS_RESOURCE_KEY_NAME(rr->key), DNS_RESOURCE_KEY_NAME(key));
+        r = dns_name_equal(DNS_RESOURCE_KEY_NAME(rr->key), DNS_RESOURCE_KEY_NAME(key));
+        if (r != 0)
+                return r;
+
+        if (search_domain) {
+                _cleanup_free_ char *joined = NULL;
+
+                r = dns_name_concat(DNS_RESOURCE_KEY_NAME(key), search_domain, &joined);
+                if (r < 0)
+                        return r;
+
+                return dns_name_equal(DNS_RESOURCE_KEY_NAME(rr->key), joined);
+        }
+
+        return 0;
 }
 
-int dns_resource_key_match_cname(const DnsResourceKey *key, const DnsResourceRecord *rr) {
+int dns_resource_key_match_cname(const DnsResourceKey *key, const DnsResourceRecord *rr, const char *search_domain) {
+        int r;
+
         assert(key);
         assert(rr);
 
@@ -166,11 +219,30 @@ int dns_resource_key_match_cname(const DnsResourceKey *key, const DnsResourceRec
                 return 0;
 
         if (rr->key->type == DNS_TYPE_CNAME)
-                return dns_name_equal(DNS_RESOURCE_KEY_NAME(key), DNS_RESOURCE_KEY_NAME(rr->key));
+                r = dns_name_equal(DNS_RESOURCE_KEY_NAME(key), DNS_RESOURCE_KEY_NAME(rr->key));
         else if (rr->key->type == DNS_TYPE_DNAME)
-                return dns_name_endswith(DNS_RESOURCE_KEY_NAME(key), DNS_RESOURCE_KEY_NAME(rr->key));
+                r = dns_name_endswith(DNS_RESOURCE_KEY_NAME(key), DNS_RESOURCE_KEY_NAME(rr->key));
         else
                 return 0;
+
+        if (r != 0)
+                return r;
+
+        if (search_domain) {
+                _cleanup_free_ char *joined = NULL;
+
+                r = dns_name_concat(DNS_RESOURCE_KEY_NAME(key), search_domain, &joined);
+                if (r < 0)
+                        return r;
+
+                if (rr->key->type == DNS_TYPE_CNAME)
+                        return dns_name_equal(joined, DNS_RESOURCE_KEY_NAME(rr->key));
+                else if (rr->key->type == DNS_TYPE_DNAME)
+                        return dns_name_endswith(joined, DNS_RESOURCE_KEY_NAME(rr->key));
+        }
+
+        return 0;
+
 }
 
 static void dns_resource_key_hash_func(const void *i, struct siphash *state) {
diff --git a/src/resolve/resolved-dns-rr.h b/src/resolve/resolved-dns-rr.h
index c1601fb694..f8066c06a6 100644
--- a/src/resolve/resolved-dns-rr.h
+++ b/src/resolve/resolved-dns-rr.h
@@ -188,12 +188,13 @@ DnsResourceKey* dns_resource_key_new(uint16_t class, uint16_t type, const char *
 DnsResourceKey* dns_resource_key_new_cname(const DnsResourceKey *key);
 DnsResourceKey* dns_resource_key_new_dname(const DnsResourceKey *key);
 DnsResourceKey* dns_resource_key_new_redirect(const DnsResourceKey *key, const DnsResourceRecord *cname);
+int dns_resource_key_new_append_suffix(DnsResourceKey **ret, DnsResourceKey *key, char *name);
 DnsResourceKey* dns_resource_key_new_consume(uint16_t class, uint16_t type, char *name);
 DnsResourceKey* dns_resource_key_ref(DnsResourceKey *key);
 DnsResourceKey* dns_resource_key_unref(DnsResourceKey *key);
 int dns_resource_key_equal(const DnsResourceKey *a, const DnsResourceKey *b);
-int dns_resource_key_match_rr(const DnsResourceKey *key, const DnsResourceRecord *rr);
-int dns_resource_key_match_cname(const DnsResourceKey *key, const DnsResourceRecord *rr);
+int dns_resource_key_match_rr(const DnsResourceKey *key, const DnsResourceRecord *rr, const char *search_domain);
+int dns_resource_key_match_cname(const DnsResourceKey *key, const DnsResourceRecord *rr, const char *search_domain);
 int dns_resource_key_to_string(const DnsResourceKey *key, char **ret);
 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsResourceKey*, dns_resource_key_unref);
 
diff --git a/src/resolve/resolved-dns-scope.c b/src/resolve/resolved-dns-scope.c
index 2e47691c56..daeab9b9ee 100644
--- a/src/resolve/resolved-dns-scope.c
+++ b/src/resolve/resolved-dns-scope.c
@@ -69,18 +69,12 @@ int dns_scope_new(Manager *m, DnsScope **ret, Link *l, DnsProtocol protocol, int
         return 0;
 }
 
-DnsScope* dns_scope_free(DnsScope *s) {
+static void dns_scope_abort_transactions(DnsScope *s) {
         DnsTransaction *t;
-        DnsResourceRecord *rr;
-
-        if (!s)
-                return NULL;
-
-        log_debug("Removing scope on link %s, protocol %s, family %s", s->link ? s->link->name : "*", dns_protocol_to_string(s->protocol), s->family == AF_UNSPEC ? "*" : af_to_name(s->family));
 
-        dns_scope_llmnr_membership(s, false);
+        assert(s);
 
-        while ((t = hashmap_steal_first(s->transactions))) {
+        while ((t = hashmap_first(s->transactions))) {
                 /* Abort the transaction, but make sure it is not
                  * freed while we still look at it */
 
@@ -90,6 +84,21 @@ DnsScope* dns_scope_free(DnsScope *s) {
 
                 dns_transaction_free(t);
         }
+}
+
+DnsScope* dns_scope_free(DnsScope *s) {
+        DnsResourceRecord *rr;
+
+        if (!s)
+                return NULL;
+
+        log_debug("Removing scope on link %s, protocol %s, family %s", s->link ? s->link->name : "*", dns_protocol_to_string(s->protocol), s->family == AF_UNSPEC ? "*" : af_to_name(s->family));
+
+        dns_scope_llmnr_membership(s, false);
+        dns_scope_abort_transactions(s);
+
+        while (s->query_candidates)
+                dns_query_candidate_free(s->query_candidates);
 
         hashmap_free(s->transactions);
 
@@ -344,18 +353,28 @@ DnsScopeMatch dns_scope_good_domain(DnsScope *s, int ifindex, uint64_t flags, co
             dns_name_equal(domain, "1.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.ip6.arpa") > 0)
                 return DNS_SCOPE_NO;
 
+        /* Always honour search domains for routing queries. Note that
+         * we return DNS_SCOPE_YES here, rather than just
+         * DNS_SCOPE_MAYBE, which means wildcard scopes won't be
+         * considered anymore. */
         LIST_FOREACH(domains, d, dns_scope_get_search_domains(s))
                 if (dns_name_endswith(domain, d->name) > 0)
                         return DNS_SCOPE_YES;
 
         switch (s->protocol) {
-        case DNS_PROTOCOL_DNS:
-                if (dns_name_endswith(domain, "254.169.in-addr.arpa") == 0 &&
-                    dns_name_endswith(domain, "0.8.e.f.ip6.arpa") == 0 &&
-                    dns_name_single_label(domain) == 0)
+        case DNS_PROTOCOL_DNS: {
+                int is_single_label;
+
+                is_single_label = dns_name_single_label(domain);
+
+                if ((is_single_label == 0 ||
+                     (is_single_label > 0 && !(flags & SD_RESOLVED_NO_SEARCH) && dns_scope_has_search_domains(s))) &&
+                    dns_name_endswith(domain, "254.169.in-addr.arpa") == 0 &&
+                    dns_name_endswith(domain, "0.8.e.f.ip6.arpa") == 0)
                         return DNS_SCOPE_MAYBE;
 
                 return DNS_SCOPE_NO;
+        }
 
         case DNS_PROTOCOL_MDNS:
                 if ((s->family == AF_INET && dns_name_endswith(domain, "in-addr.arpa") > 0) ||
@@ -851,6 +870,10 @@ void dns_scope_dump(DnsScope *s, FILE *f) {
 }
 
 DnsSearchDomain *dns_scope_get_search_domains(DnsScope *s) {
+        assert(s);
+
+        /* Returns the list of *local* search domains -- not the
+         * global ones. */
 
         if (s->protocol != DNS_PROTOCOL_DNS)
                 return NULL;
@@ -860,3 +883,30 @@ DnsSearchDomain *dns_scope_get_search_domains(DnsScope *s) {
 
         return NULL;
 }
+
+bool dns_scope_has_search_domains(DnsScope *s) {
+        assert(s);
+
+        /* Tests if there are *any* search domains suitable for this
+         * scope. This means either local or global ones */
+
+        if (s->protocol != DNS_PROTOCOL_DNS)
+                return false;
+
+        if (s->manager->search_domains)
+                return true;
+
+        if (s->link && s->link->search_domains)
+                return true;
+
+        return false;
+}
+
+int dns_scope_name_needs_search_domain(DnsScope *s, const char *name) {
+        assert(s);
+
+        if (s->protocol != DNS_PROTOCOL_DNS)
+                return 0;
+
+        return dns_name_single_label(name);
+}
diff --git a/src/resolve/resolved-dns-scope.h b/src/resolve/resolved-dns-scope.h
index f69d51b203..244bb41314 100644
--- a/src/resolve/resolved-dns-scope.h
+++ b/src/resolve/resolved-dns-scope.h
@@ -59,6 +59,7 @@ struct DnsScope {
         usec_t max_rtt;
 
         Hashmap *transactions;
+        LIST_HEAD(DnsQueryCandidate, query_candidates);
 
         LIST_FIELDS(DnsScope, scopes);
 };
@@ -91,3 +92,6 @@ void dns_scope_check_conflicts(DnsScope *scope, DnsPacket *p);
 void dns_scope_dump(DnsScope *s, FILE *f);
 
 DnsSearchDomain *dns_scope_get_search_domains(DnsScope *s);
+bool dns_scope_has_search_domains(DnsScope *s);
+
+int dns_scope_name_needs_search_domain(DnsScope *s, const char *name);
diff --git a/src/resolve/resolved-dns-search-domain.h b/src/resolve/resolved-dns-search-domain.h
index 20b441206c..2e0af31dda 100644
--- a/src/resolve/resolved-dns-search-domain.h
+++ b/src/resolve/resolved-dns-search-domain.h
@@ -68,4 +68,8 @@ void dns_search_domain_mark_all(DnsSearchDomain *first);
 
 int dns_search_domain_find(DnsSearchDomain *first, const char *name, DnsSearchDomain **ret);
 
+static inline const char* DNS_SEARCH_DOMAIN_NAME(DnsSearchDomain *d) {
+        return d ? d->name : NULL;
+}
+
 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsSearchDomain*, dns_search_domain_unref);
diff --git a/src/resolve/resolved-dns-transaction.c b/src/resolve/resolved-dns-transaction.c
index 37f47c47c0..2fc84aec6f 100644
--- a/src/resolve/resolved-dns-transaction.c
+++ b/src/resolve/resolved-dns-transaction.c
@@ -29,7 +29,7 @@
 #include "string-table.h"
 
 DnsTransaction* dns_transaction_free(DnsTransaction *t) {
-        DnsQuery *q;
+        DnsQueryCandidate *c;
         DnsZoneItem *i;
 
         if (!t)
@@ -56,9 +56,10 @@ DnsTransaction* dns_transaction_free(DnsTransaction *t) {
 
         dns_resource_key_unref(t->key);
 
-        while ((q = set_steal_first(t->queries)))
-                set_remove(q->transactions, t);
-        set_free(t->queries);
+        while ((c = set_steal_first(t->query_candidates)))
+                set_remove(c->transactions, t);
+
+        set_free(t->query_candidates);
 
         while ((i = set_steal_first(t->zone_items)))
                 i->probe_transaction = NULL;
@@ -76,7 +77,7 @@ void dns_transaction_gc(DnsTransaction *t) {
         if (t->block_gc > 0)
                 return;
 
-        if (set_isempty(t->queries) && set_isempty(t->zone_items))
+        if (set_isempty(t->query_candidates) && set_isempty(t->zone_items))
                 dns_transaction_free(t);
 }
 
@@ -181,7 +182,7 @@ static void dns_transaction_tentative(DnsTransaction *t, DnsPacket *p) {
 }
 
 void dns_transaction_complete(DnsTransaction *t, DnsTransactionState state) {
-        DnsQuery *q;
+        DnsQueryCandidate *c;
         DnsZoneItem *z;
         Iterator i;
 
@@ -205,8 +206,8 @@ void dns_transaction_complete(DnsTransaction *t, DnsTransactionState state) {
         /* Notify all queries that are interested, but make sure the
          * transaction isn't freed while we are still looking at it */
         t->block_gc++;
-        SET_FOREACH(q, t->queries, i)
-                dns_query_ready(q);
+        SET_FOREACH(c, t->query_candidates, i)
+                dns_query_candidate_ready(c);
         SET_FOREACH(z, t->zone_items, i)
                 dns_zone_item_ready(z);
         t->block_gc--;
diff --git a/src/resolve/resolved-dns-transaction.h b/src/resolve/resolved-dns-transaction.h
index d0970bd695..a2aa73a524 100644
--- a/src/resolve/resolved-dns-transaction.h
+++ b/src/resolve/resolved-dns-transaction.h
@@ -71,9 +71,10 @@ struct DnsTransaction {
         /* TCP connection logic, if we need it */
         DnsStream *stream;
 
-        /* Queries this transaction is referenced by and that shall be
-         * notified about this specific transaction completing. */
-        Set *queries;
+        /* Query candidates this transaction is referenced by and that
+         * shall be notified about this specific transaction
+         * completing. */
+        Set *query_candidates;
 
         /* Zone items this transaction is referenced by and that shall
          * be notified about completion. */
diff --git a/src/resolve/resolved-dns-zone.c b/src/resolve/resolved-dns-zone.c
index a021ecb93d..493d11dd14 100644
--- a/src/resolve/resolved-dns-zone.c
+++ b/src/resolve/resolved-dns-zone.c
@@ -311,7 +311,7 @@ int dns_zone_lookup(DnsZone *z, DnsResourceKey *key, DnsAnswer **ret_answer, Dns
 
                         found = true;
 
-                        k = dns_resource_key_match_rr(key, j->rr);
+                        k = dns_resource_key_match_rr(key, j->rr, NULL);
                         if (k < 0)
                                 return k;
                         if (k > 0) {
@@ -381,7 +381,7 @@ int dns_zone_lookup(DnsZone *z, DnsResourceKey *key, DnsAnswer **ret_answer, Dns
                         if (j->state != DNS_ZONE_ITEM_PROBING)
                                 tentative = false;
 
-                        k = dns_resource_key_match_rr(key, j->rr);
+                        k = dns_resource_key_match_rr(key, j->rr, NULL);
                         if (k < 0)
                                 return k;
                         if (k > 0) {