resolved: rework IDNA logic

Move IDNA logic out of the normal domain name processing, and into the bus frontend calls. Previously whenever
comparing two domain names we'd implicitly do IDNA conversion so that "pöttering.de" and "xn--pttering-n4a.de" would be
considered equal. This is problematic not only for DNSSEC, but actually also against he IDNA specs.

Moreover it creates problems when encoding DNS-SD services in classic DNS. There, the specification suggests using
UTF8 encoding for the actual service name, but apply IDNA encoding to the domain suffix.

With this change IDNA conversion is done only:

- When the user passes a non-ASCII hostname when resolving a host name using ResolveHostname()
- When the user passes a non-ASCII domain suffix when resolving a service using ResolveService()

No IDNA encoding is done anymore:

- When the user does raw ResolveRecord() RR resolving
- On the service part of a DNS-SD service name

Previously, IDNA encoding was done when serializing names into packets, at a point where information whether something
is a label that needs IDNA encoding or not was not available, but at a point whether it was known whether to generate a
classic DNS packet (where IDNA applies), or an mDNS/LLMNR packet (where IDNA does not apply, and UTF8 is used instead
for all host names). With this change each DnsQuery object will now maintain two copies of the DnsQuestion to ask: one
encoded in IDNA for use with classic DNS, and one encoded in UTF8 for use with LLMNR and MulticastDNS.

8 files changed, 400 insertions, 292 deletions

diff --git a/src/resolve/resolved-bus.c b/src/resolve/resolved-bus.c
index 41f90dedfd..4593bab5e8 100644
--- a/src/resolve/resolved-bus.c
+++ b/src/resolve/resolved-bus.c
@@ -27,18 +27,6 @@
 #include "resolved-def.h"
 
 static int reply_query_state(DnsQuery *q) {
-        _cleanup_free_ char *ip = NULL;
-        const char *name;
-        int r;
-
-        if (q->request_address_valid) {
-                r = in_addr_to_string(q->request_family, &q->request_address, &ip);
-                if (r < 0)
-                        return r;
-
-                name = ip;
-        } else
-                name = dns_question_first_name(q->question);
 
         switch (q->state) {
 
@@ -74,7 +62,7 @@ static int reply_query_state(DnsQuery *q) {
                 _cleanup_(sd_bus_error_free) sd_bus_error error = SD_BUS_ERROR_NULL;
 
                 if (q->answer_rcode == DNS_RCODE_NXDOMAIN)
-                        sd_bus_error_setf(&error, _BUS_ERROR_DNS "NXDOMAIN", "'%s' not found", name);
+                        sd_bus_error_setf(&error, _BUS_ERROR_DNS "NXDOMAIN", "'%s' not found", dns_query_string(q));
                 else {
                         const char *rc, *n;
                         char p[3]; /* the rcode is 4 bits long */
@@ -86,7 +74,7 @@ static int reply_query_state(DnsQuery *q) {
                         }
 
                         n = strjoina(_BUS_ERROR_DNS, rc);
-                        sd_bus_error_setf(&error, n, "Could not resolve '%s', server or network returned error %s", name, rc);
+                        sd_bus_error_setf(&error, n, "Could not resolve '%s', server or network returned error %s", dns_query_string(q), rc);
                 }
 
                 return sd_bus_reply_method_error(q->request, &error);
@@ -156,7 +144,7 @@ static void bus_method_resolve_hostname_complete(DnsQuery *q) {
 
         r = dns_query_process_cname(q);
         if (r == -ELOOP) {
-                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_CNAME_LOOP, "CNAME loop detected, or CNAME resolving disabled on '%s'", dns_question_first_name(q->question));
+                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_CNAME_LOOP, "CNAME loop detected, or CNAME resolving disabled on '%s'", dns_query_string(q));
                 goto finish;
         }
         if (r < 0)
@@ -177,7 +165,11 @@ 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, DNS_SEARCH_DOMAIN_NAME(q->answer_search_domain));
+                        DnsQuestion *question;
+
+                        question = dns_query_question_for_protocol(q, q->answer_protocol);
+
+                        r = dns_question_matches_rr(question, rr, DNS_SEARCH_DOMAIN_NAME(q->answer_search_domain));
                         if (r < 0)
                                 goto finish;
                         if (r == 0)
@@ -195,7 +187,7 @@ static void bus_method_resolve_hostname_complete(DnsQuery *q) {
         }
 
         if (added <= 0) {
-                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_SUCH_RR, "'%s' does not have any RR of the requested type", dns_question_first_name(q->question));
+                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_SUCH_RR, "'%s' does not have any RR of the requested type", dns_query_string(q));
                 goto finish;
         }
 
@@ -239,7 +231,7 @@ static int check_ifindex_flags(int ifindex, uint64_t *flags, uint64_t ok, sd_bus
 }
 
 static int bus_method_resolve_hostname(sd_bus_message *message, void *userdata, sd_bus_error *error) {
-        _cleanup_(dns_question_unrefp) DnsQuestion *question = NULL;
+        _cleanup_(dns_question_unrefp) DnsQuestion *question_idna = NULL, *question_utf8 = NULL;
         Manager *m = userdata;
         const char *hostname;
         int family, ifindex;
@@ -269,11 +261,15 @@ static int bus_method_resolve_hostname(sd_bus_message *message, void *userdata,
         if (r < 0)
                 return r;
 
-        r = dns_question_new_address(&question, family, hostname);
+        r = dns_question_new_address(&question_utf8, family, hostname, false);
+        if (r < 0)
+                return r;
+
+        r = dns_question_new_address(&question_idna, family, hostname, true);
         if (r < 0)
                 return r;
 
-        r = dns_query_new(m, &q, question, ifindex, flags);
+        r = dns_query_new(m, &q, question_utf8, question_idna, ifindex, flags);
         if (r < 0)
                 return r;
 
@@ -298,6 +294,7 @@ fail:
 
 static void bus_method_resolve_address_complete(DnsQuery *q) {
         _cleanup_(sd_bus_message_unrefp) sd_bus_message *reply = NULL;
+        DnsQuestion *question;
         DnsResourceRecord *rr;
         unsigned added = 0;
         int ifindex, r;
@@ -311,7 +308,7 @@ static void bus_method_resolve_address_complete(DnsQuery *q) {
 
         r = dns_query_process_cname(q);
         if (r == -ELOOP) {
-                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_CNAME_LOOP, "CNAME loop detected, or CNAME resolving disabled on '%s'", dns_question_first_name(q->question));
+                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_CNAME_LOOP, "CNAME loop detected, or CNAME resolving disabled on '%s'", dns_query_string(q));
                 goto finish;
         }
         if (r < 0)
@@ -327,20 +324,20 @@ static void bus_method_resolve_address_complete(DnsQuery *q) {
         if (r < 0)
                 goto finish;
 
-        if (q->answer) {
-                DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, q->answer) {
-                        r = dns_question_matches_rr(q->question, rr, NULL);
-                        if (r < 0)
-                                goto finish;
-                        if (r == 0)
-                                continue;
+        question = dns_query_question_for_protocol(q, q->answer_protocol);
 
-                        r = sd_bus_message_append(reply, "(is)", ifindex, rr->ptr.name);
-                        if (r < 0)
-                                goto finish;
+        DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, q->answer) {
+                r = dns_question_matches_rr(question, rr, NULL);
+                if (r < 0)
+                        goto finish;
+                if (r == 0)
+                        continue;
 
-                        added ++;
-                }
+                r = sd_bus_message_append(reply, "(is)", ifindex, rr->ptr.name);
+                if (r < 0)
+                        goto finish;
+
+                added ++;
         }
 
         if (added <= 0) {
@@ -411,7 +408,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|SD_RESOLVED_NO_SEARCH);
+        r = dns_query_new(m, &q, question, question, ifindex, flags|SD_RESOLVED_NO_SEARCH);
         if (r < 0)
                 return r;
 
@@ -465,7 +462,10 @@ static int bus_message_append_rr(sd_bus_message *m, DnsResourceRecord *rr, int i
 
 static void bus_method_resolve_record_complete(DnsQuery *q) {
         _cleanup_(sd_bus_message_unrefp) sd_bus_message *reply = NULL;
+        DnsResourceRecord *rr;
+        DnsQuestion *question;
         unsigned added = 0;
+        int ifindex;
         int r;
 
         assert(q);
@@ -477,7 +477,7 @@ static void bus_method_resolve_record_complete(DnsQuery *q) {
 
         r = dns_query_process_cname(q);
         if (r == -ELOOP) {
-                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_CNAME_LOOP, "CNAME loop detected, or CNAME resolving disabled on '%s'", dns_question_first_name(q->question));
+                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_CNAME_LOOP, "CNAME loop detected, or CNAME resolving disabled on '%s'", dns_query_string(q));
                 goto finish;
         }
         if (r < 0)
@@ -493,27 +493,24 @@ static void bus_method_resolve_record_complete(DnsQuery *q) {
         if (r < 0)
                 goto finish;
 
-        if (q->answer) {
-                DnsResourceRecord *rr;
-                int ifindex;
+        question = dns_query_question_for_protocol(q, q->answer_protocol);
 
-                DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, q->answer) {
-                        r = dns_question_matches_rr(q->question, rr, NULL);
-                        if (r < 0)
-                                goto finish;
-                        if (r == 0)
-                                continue;
+        DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, q->answer) {
+                r = dns_question_matches_rr(question, rr, NULL);
+                if (r < 0)
+                        goto finish;
+                if (r == 0)
+                        continue;
 
-                        r = bus_message_append_rr(reply, rr, ifindex);
-                        if (r < 0)
-                                goto finish;
+                r = bus_message_append_rr(reply, rr, ifindex);
+                if (r < 0)
+                        goto finish;
 
-                        added ++;
-                }
+                added ++;
         }
 
         if (added <= 0) {
-                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_SUCH_RR, "Name '%s' does not have any RR of the requested type", dns_question_first_name(q->question));
+                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_SUCH_RR, "Name '%s' does not have any RR of the requested type", dns_query_string(q));
                 goto finish;
         }
 
@@ -582,7 +579,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|SD_RESOLVED_NO_SEARCH);
+        r = dns_query_new(m, &q, question, question, ifindex, flags|SD_RESOLVED_NO_SEARCH);
         if (r < 0)
                 return r;
 
@@ -622,13 +619,16 @@ static int append_srv(DnsQuery *q, sd_bus_message *reply, DnsResourceRecord *rr)
                  * record for the SRV record */
                 LIST_FOREACH(auxiliary_queries, aux, q->auxiliary_queries) {
                         DnsResourceRecord *zz;
+                        DnsQuestion *question;
 
                         if (aux->state != DNS_TRANSACTION_SUCCESS)
                                 continue;
                         if (aux->auxiliary_result != 0)
                                 continue;
 
-                        r = dns_name_equal(dns_question_first_name(aux->question), rr->srv.name);
+                        question = dns_query_question_for_protocol(aux, aux->answer_protocol);
+
+                        r = dns_name_equal(dns_question_first_name(question), rr->srv.name);
                         if (r < 0)
                                 return r;
                         if (r == 0)
@@ -636,7 +636,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, NULL);
+                                r = dns_question_matches_rr(question, zz, NULL);
                                 if (r < 0)
                                         return r;
                                 if (r == 0)
@@ -673,6 +673,7 @@ static int append_srv(DnsQuery *q, sd_bus_message *reply, DnsResourceRecord *rr)
         if ((q->flags & SD_RESOLVED_NO_ADDRESS) == 0) {
                 LIST_FOREACH(auxiliary_queries, aux, q->auxiliary_queries) {
                         DnsResourceRecord *zz;
+                        DnsQuestion *question;
                         int ifindex;
 
                         if (aux->state != DNS_TRANSACTION_SUCCESS)
@@ -680,7 +681,9 @@ static int append_srv(DnsQuery *q, sd_bus_message *reply, DnsResourceRecord *rr)
                         if (aux->auxiliary_result != 0)
                                 continue;
 
-                        r = dns_name_equal(dns_question_first_name(aux->question), rr->srv.name);
+                        question = dns_query_question_for_protocol(aux, aux->answer_protocol);
+
+                        r = dns_name_equal(dns_question_first_name(question), rr->srv.name);
                         if (r < 0)
                                 return r;
                         if (r == 0)
@@ -688,7 +691,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, NULL);
+                                r = dns_question_matches_rr(question, zz, NULL);
                                 if (r < 0)
                                         return r;
                                 if (r == 0)
@@ -746,8 +749,10 @@ static void resolve_service_all_complete(DnsQuery *q) {
         _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *canonical = NULL;
         _cleanup_(sd_bus_message_unrefp) sd_bus_message *reply = NULL;
         _cleanup_free_ char *name = NULL, *type = NULL, *domain = NULL;
+        DnsQuestion *question;
+        DnsResourceRecord *rr;
+        unsigned added = 0;
         DnsQuery *aux;
-        unsigned added = false;
         int r;
 
         assert(q);
@@ -789,7 +794,7 @@ static void resolve_service_all_complete(DnsQuery *q) {
                                 assert(bad->auxiliary_result != 0);
 
                                 if (bad->auxiliary_result == -ELOOP) {
-                                        r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_CNAME_LOOP, "CNAME loop detected, or CNAME resolving disabled on '%s'", dns_question_first_name(bad->question));
+                                        r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_CNAME_LOOP, "CNAME loop detected, or CNAME resolving disabled on '%s'", dns_query_string(bad));
                                         goto finish;
                                 }
 
@@ -810,31 +815,28 @@ static void resolve_service_all_complete(DnsQuery *q) {
         if (r < 0)
                 goto finish;
 
-        if (q->answer) {
-                DnsResourceRecord *rr;
-
-                DNS_ANSWER_FOREACH(rr, q->answer) {
-                        r = dns_question_matches_rr(q->question, rr, NULL);
-                        if (r < 0)
-                                goto finish;
-                        if (r == 0)
-                                continue;
+        question = dns_query_question_for_protocol(q, q->answer_protocol);
+        DNS_ANSWER_FOREACH(rr, q->answer) {
+                r = dns_question_matches_rr(question, rr, NULL);
+                if (r < 0)
+                        goto finish;
+                if (r == 0)
+                        continue;
 
-                        r = append_srv(q, reply, rr);
-                        if (r < 0)
-                                goto finish;
-                        if (r == 0) /* not an SRV record */
-                                continue;
+                r = append_srv(q, reply, rr);
+                if (r < 0)
+                        goto finish;
+                if (r == 0) /* not an SRV record */
+                        continue;
 
-                        if (!canonical)
-                                canonical = dns_resource_record_ref(rr);
+                if (!canonical)
+                        canonical = dns_resource_record_ref(rr);
 
-                        added++;
-                }
+                added++;
         }
 
         if (added <= 0) {
-                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_SUCH_RR, "'%s' does not have any RR of the requested type", dns_question_first_name(q->question));
+                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_SUCH_RR, "'%s' does not have any RR of the requested type", dns_query_string(q));
                 goto finish;
         }
 
@@ -846,20 +848,16 @@ static void resolve_service_all_complete(DnsQuery *q) {
         if (r < 0)
                 goto finish;
 
-        if (q->answer) {
-                DnsResourceRecord *rr;
-
-                DNS_ANSWER_FOREACH(rr, q->answer) {
-                        r = dns_question_matches_rr(q->question, rr, NULL);
-                        if (r < 0)
-                                goto finish;
-                        if (r == 0)
-                                continue;
+        DNS_ANSWER_FOREACH(rr, q->answer) {
+                r = dns_question_matches_rr(question, rr, NULL);
+                if (r < 0)
+                        goto finish;
+                if (r == 0)
+                        continue;
 
-                        r = append_txt(reply, rr);
-                        if (r < 0)
-                                goto finish;
-                }
+                r = append_txt(reply, rr);
+                if (r < 0)
+                        goto finish;
         }
 
         r = sd_bus_message_close_container(reply);
@@ -923,11 +921,11 @@ static int resolve_service_hostname(DnsQuery *q, DnsResourceRecord *rr, int ifin
         /* OK, we found an SRV record for the service. Let's resolve
          * the hostname included in it */
 
-        r = dns_question_new_address(&question, q->request_family, rr->srv.name);
+        r = dns_question_new_address(&question, q->request_family, rr->srv.name, false);
         if (r < 0)
                 return r;
 
-        r = dns_query_new(q->manager, &aux, question, ifindex, q->flags|SD_RESOLVED_NO_SEARCH);
+        r = dns_query_new(q->manager, &aux, question, question, ifindex, q->flags|SD_RESOLVED_NO_SEARCH);
         if (r < 0)
                 return r;
 
@@ -961,8 +959,11 @@ fail:
 }
 
 static void bus_method_resolve_service_complete(DnsQuery *q) {
+        bool has_root_domain = false;
+        DnsResourceRecord *rr;
+        DnsQuestion *question;
         unsigned found = 0;
-        int r;
+        int ifindex, r;
 
         assert(q);
 
@@ -973,7 +974,7 @@ static void bus_method_resolve_service_complete(DnsQuery *q) {
 
         r = dns_query_process_cname(q);
         if (r == -ELOOP) {
-                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_CNAME_LOOP, "CNAME loop detected, or CNAME resolving disabled on '%s'", dns_question_first_name(q->question));
+                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_CNAME_LOOP, "CNAME loop detected, or CNAME resolving disabled on '%s'", dns_query_string(q));
                 goto finish;
         }
         if (r < 0)
@@ -981,53 +982,48 @@ static void bus_method_resolve_service_complete(DnsQuery *q) {
         if (r == DNS_QUERY_RESTARTED) /* This was a cname, and the query was restarted. */
                 return;
 
-        if (q->answer) {
-                bool has_root_domain = false;
-                DnsResourceRecord *rr;
-                int ifindex;
-
-                DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, q->answer) {
-                        r = dns_question_matches_rr(q->question, rr, NULL);
-                        if (r < 0)
-                                goto finish;
-                        if (r == 0)
-                                continue;
+        question = dns_query_question_for_protocol(q, q->answer_protocol);
 
-                        if (rr->key->type != DNS_TYPE_SRV)
-                                continue;
+        DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, q->answer) {
+                r = dns_question_matches_rr(question, rr, NULL);
+                if (r < 0)
+                        goto finish;
+                if (r == 0)
+                        continue;
 
-                        if (dns_name_is_root(rr->srv.name)) {
-                                has_root_domain = true;
-                                continue;
-                        }
+                if (rr->key->type != DNS_TYPE_SRV)
+                        continue;
 
-                        if ((q->flags & SD_RESOLVED_NO_ADDRESS) == 0) {
-                                q->block_all_complete ++;
-                                r = resolve_service_hostname(q, rr, ifindex);
-                                q->block_all_complete --;
+                if (dns_name_is_root(rr->srv.name)) {
+                        has_root_domain = true;
+                        continue;
+                }
 
-                                if (r < 0)
-                                        goto finish;
-                        }
+                if ((q->flags & SD_RESOLVED_NO_ADDRESS) == 0) {
+                        q->block_all_complete ++;
+                        r = resolve_service_hostname(q, rr, ifindex);
+                        q->block_all_complete --;
 
-                        found++;
+                        if (r < 0)
+                                goto finish;
                 }
 
-                if (has_root_domain && found == 0) {
-                        /* If there's exactly one SRV RR and it uses
-                         * the root domain as host name, then the
-                         * service is explicitly not offered on the
-                         * domain. Report this as a recognizable
-                         * error. See RFC 2782, Section "Usage
-                         * Rules". */
-                        r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_SUCH_SERVICE, "'%s' does not provide the requested service", dns_question_first_name(q->question));
-                        goto finish;
-                }
+                found++;
+        }
 
+        if (has_root_domain && found <= 0) {
+                /* If there's exactly one SRV RR and it uses
+                 * the root domain as host name, then the
+                 * service is explicitly not offered on the
+                 * domain. Report this as a recognizable
+                 * error. See RFC 2782, Section "Usage
+                 * Rules". */
+                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_SUCH_SERVICE, "'%s' does not provide the requested service", dns_query_string(q));
+                goto finish;
         }
 
         if (found <= 0) {
-                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_SUCH_RR, "'%s' does not have any RR of the requested type", dns_question_first_name(q->question));
+                r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_SUCH_RR, "'%s' does not have any RR of the requested type", dns_query_string(q));
                 goto finish;
         }
 
@@ -1045,8 +1041,8 @@ finish:
 }
 
 static int bus_method_resolve_service(sd_bus_message *message, void *userdata, sd_bus_error *error) {
-        _cleanup_(dns_question_unrefp) DnsQuestion *question = NULL;
-        const char *name, *type, *domain, *joined;
+        _cleanup_(dns_question_unrefp) DnsQuestion *question_idna = NULL, *question_utf8 = NULL;
+        const char *name, *type, *domain;
         _cleanup_free_ char *n = NULL;
         Manager *m = userdata;
         int family, ifindex;
@@ -1068,10 +1064,8 @@ static int bus_method_resolve_service(sd_bus_message *message, void *userdata, s
 
         if (isempty(name))
                 name = NULL;
-        else {
-                if (!dns_service_name_is_valid(name))
-                        return sd_bus_error_setf(error, SD_BUS_ERROR_INVALID_ARGS, "Invalid service name '%s'", name);
-        }
+        else if (!dns_service_name_is_valid(name))
+                return sd_bus_error_setf(error, SD_BUS_ERROR_INVALID_ARGS, "Invalid service name '%s'", name);
 
         if (isempty(type))
                 type = NULL;
@@ -1091,23 +1085,15 @@ static int bus_method_resolve_service(sd_bus_message *message, void *userdata, s
         if (r < 0)
                 return r;
 
-        if (type) {
-                /* If the type is specified, we generate the full domain name to look up ourselves */
-                r = dns_service_join(name, type, domain, &n);
-                if (r < 0)
-                        return r;
-
-                joined = n;
-        } else
-                /* If no type is specified, we assume the domain
-                 * contains the full domain name to lookup already */
-                joined = domain;
+        r = dns_question_new_service(&question_utf8, name, type, domain, !(flags & SD_RESOLVED_NO_TXT), false);
+        if (r < 0)
+                return r;
 
-        r = dns_question_new_service(&question, joined, !(flags & SD_RESOLVED_NO_TXT));
+        r = dns_question_new_service(&question_idna, name, type, domain, !(flags & SD_RESOLVED_NO_TXT), true);
         if (r < 0)
                 return r;
 
-        r = dns_query_new(m, &q, question, ifindex, flags|SD_RESOLVED_NO_SEARCH);
+        r = dns_query_new(m, &q, question_utf8, question_idna, ifindex, flags|SD_RESOLVED_NO_SEARCH);
         if (r < 0)
                 return r;
 
diff --git a/src/resolve/resolved-dns-dnssec.c b/src/resolve/resolved-dns-dnssec.c
index f999a8cc77..e5268b84ab 100644
--- a/src/resolve/resolved-dns-dnssec.c
+++ b/src/resolve/resolved-dns-dnssec.c
@@ -1005,16 +1005,6 @@ int dnssec_canonicalize(const char *n, char *buffer, size_t buffer_max) {
                         return r;
                 if (r == 0)
                         break;
-                if (r > 0) {
-                        int k;
-
-                        /* DNSSEC validation is always done on the ASCII version of the label */
-                        k = dns_label_apply_idna(buffer, r, buffer, buffer_max);
-                        if (k < 0)
-                                return k;
-                        if (k > 0)
-                                r = k;
-                }
 
                 if (buffer_max < (size_t) r + 2)
                         return -ENOBUFS;
diff --git a/src/resolve/resolved-dns-packet.c b/src/resolve/resolved-dns-packet.c
index 0acbcfe261..93867bedb7 100644
--- a/src/resolve/resolved-dns-packet.c
+++ b/src/resolve/resolved-dns-packet.c
@@ -499,7 +499,6 @@ int dns_packet_append_name(
                 const char *z = name;
                 char label[DNS_LABEL_MAX];
                 size_t n = 0;
-                int k;
 
                 if (allow_compression)
                         n = PTR_TO_SIZE(hashmap_get(p->names, name));
@@ -519,17 +518,6 @@ int dns_packet_append_name(
                 if (r < 0)
                         goto fail;
 
-                if (p->protocol == DNS_PROTOCOL_DNS)
-                        k = dns_label_apply_idna(label, r, label, sizeof(label));
-                else
-                        k = dns_label_undo_idna(label, r, label, sizeof(label));
-                if (k < 0) {
-                        r = k;
-                        goto fail;
-                }
-                if (k > 0)
-                        r = k;
-
                 r = dns_packet_append_label(p, label, r, canonical_candidate, &n);
                 if (r < 0)
                         goto fail;
diff --git a/src/resolve/resolved-dns-query.c b/src/resolve/resolved-dns-query.c
index c6da8d0a87..b01ac29591 100644
--- a/src/resolve/resolved-dns-query.c
+++ b/src/resolve/resolved-dns-query.c
@@ -24,6 +24,7 @@
 #include "hostname-util.h"
 #include "local-addresses.h"
 #include "resolved-dns-query.h"
+#include "string-util.h"
 
 /* How long to wait for the query in total */
 #define QUERY_TIMEOUT_USEC (30 * USEC_PER_SEC)
@@ -217,6 +218,7 @@ static DnsTransactionState dns_query_candidate_state(DnsQueryCandidate *c) {
 }
 
 static int dns_query_candidate_setup_transactions(DnsQueryCandidate *c) {
+        DnsQuestion *question;
         DnsResourceKey *key;
         int n = 0, r;
 
@@ -224,8 +226,10 @@ static int dns_query_candidate_setup_transactions(DnsQueryCandidate *c) {
 
         dns_query_candidate_stop(c);
 
+        question = dns_query_question_for_protocol(c->query, c->scope->protocol);
+
         /* Create one transaction per question key */
-        DNS_QUESTION_FOREACH(key, c->query->question) {
+        DNS_QUESTION_FOREACH(key, question) {
                 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *new_key = NULL;
 
                 if (c->search_domain) {
@@ -321,13 +325,16 @@ DnsQuery *dns_query_free(DnsQuery *q) {
         while (q->candidates)
                 dns_query_candidate_free(q->candidates);
 
-        dns_question_unref(q->question);
+        dns_question_unref(q->question_idna);
+        dns_question_unref(q->question_utf8);
         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);
 
+        free(q->request_address_string);
+
         if (q->manager) {
                 LIST_REMOVE(queries, q->manager->dns_queries, q);
                 q->manager->n_dns_queries--;
@@ -338,17 +345,50 @@ DnsQuery *dns_query_free(DnsQuery *q) {
         return NULL;
 }
 
-int dns_query_new(Manager *m, DnsQuery **ret, DnsQuestion *question, int ifindex, uint64_t flags) {
+int dns_query_new(
+                Manager *m,
+                DnsQuery **ret,
+                DnsQuestion *question_utf8,
+                DnsQuestion *question_idna,
+                int ifindex, uint64_t flags) {
+
         _cleanup_(dns_query_freep) DnsQuery *q = NULL;
-        unsigned i;
+        DnsResourceKey *key;
+        bool good = false;
         int r;
 
         assert(m);
-        assert(question);
 
-        r = dns_question_is_valid_for_query(question);
+        if (dns_question_size(question_utf8) > 0) {
+                r = dns_question_is_valid_for_query(question_utf8);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        return -EINVAL;
+
+                good = true;
+        }
+
+        /* If the IDNA and UTF8 questions are the same, merge their references */
+        r = dns_question_is_equal(question_idna, question_utf8);
         if (r < 0)
                 return r;
+        if (r > 0)
+                question_idna = question_utf8;
+        else {
+                if (dns_question_size(question_idna) > 0) {
+                        r = dns_question_is_valid_for_query(question_idna);
+                        if (r < 0)
+                                return r;
+                        if (r == 0)
+                                return -EINVAL;
+
+                        good = true;
+                }
+        }
+
+        if (!good) /* don't allow empty queries */
+                return -EINVAL;
 
         if (m->n_dns_queries >= QUERIES_MAX)
                 return -EBUSY;
@@ -357,20 +397,39 @@ int dns_query_new(Manager *m, DnsQuery **ret, DnsQuestion *question, int ifindex
         if (!q)
                 return -ENOMEM;
 
-        q->question = dns_question_ref(question);
+        q->question_utf8 = dns_question_ref(question_utf8);
+        q->question_idna = dns_question_ref(question_idna);
         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;
+        /* First dump UTF8  question */
+        DNS_QUESTION_FOREACH(key, question_utf8) {
+                _cleanup_free_ char *p = NULL;
 
-                r = dns_resource_key_to_string(question->keys[i], &p);
+                r = dns_resource_key_to_string(key, &p);
                 if (r < 0)
                         return r;
 
-                log_debug("Looking up RR for %s", p);
+                log_debug("Looking up RR for %s.", strstrip(p));
+        }
+
+        /* And then dump the IDNA question, but only what hasn't been dumped already through the UTF8 question. */
+        DNS_QUESTION_FOREACH(key, question_idna) {
+                _cleanup_free_ char *p = NULL;
+
+                r = dns_question_contains(question_utf8, key);
+                if (r < 0)
+                        return r;
+                if (r > 0)
+                        continue;
+
+                r = dns_resource_key_to_string(key, &p);
+                if (r < 0)
+                        return r;
+
+                log_debug("Looking up IDNA RR for %s.", strstrip(p));
         }
 
         LIST_PREPEND(queries, m->dns_queries, q);
@@ -446,7 +505,7 @@ static int dns_query_add_candidate(DnsQuery *q, DnsScope *s) {
 
         /* If this a single-label domain on DNS, we might append a suitable search domain first. */
         if ((q->flags & SD_RESOLVED_NO_SEARCH) == 0)  {
-                r = dns_scope_name_needs_search_domain(s, dns_question_first_name(q->question));
+                r = dns_scope_name_needs_search_domain(s, dns_question_first_name(q->question_idna));
                 if (r < 0)
                         goto fail;
                 if (r > 0) {
@@ -534,7 +593,7 @@ static int dns_type_to_af(uint16_t t) {
         }
 }
 
-static int synthesize_localhost_rr(DnsQuery *q, DnsResourceKey *key, DnsAnswer **answer) {
+static int synthesize_localhost_rr(DnsQuery *q, const DnsResourceKey *key, DnsAnswer **answer) {
         int r;
 
         assert(q);
@@ -590,7 +649,7 @@ static int answer_add_ptr(DnsAnswer **answer, const char *from, const char *to,
         return dns_answer_add(*answer, rr, ifindex, flags);
 }
 
-static int synthesize_localhost_ptr(DnsQuery *q, DnsResourceKey *key, DnsAnswer **answer) {
+static int synthesize_localhost_ptr(DnsQuery *q, const DnsResourceKey *key, DnsAnswer **answer) {
         int r;
 
         assert(q);
@@ -682,7 +741,7 @@ static int answer_add_addresses_ptr(
         return 0;
 }
 
-static int synthesize_system_hostname_rr(DnsQuery *q, DnsResourceKey *key, DnsAnswer **answer) {
+static int synthesize_system_hostname_rr(DnsQuery *q, const DnsResourceKey *key, DnsAnswer **answer) {
         _cleanup_free_ struct local_address *addresses = NULL;
         int n = 0, af;
 
@@ -766,7 +825,7 @@ static int synthesize_system_hostname_ptr(DnsQuery *q, int af, const union in_ad
         return answer_add_addresses_ptr(answer, q->manager->mdns_hostname, addresses, n, af, address);
 }
 
-static int synthesize_gateway_rr(DnsQuery *q, DnsResourceKey *key, DnsAnswer **answer) {
+static int synthesize_gateway_rr(DnsQuery *q, const DnsResourceKey *key, DnsAnswer **answer) {
         _cleanup_free_ struct local_address *addresses = NULL;
         int n = 0, af;
 
@@ -801,7 +860,7 @@ static int synthesize_gateway_ptr(DnsQuery *q, int af, const union in_addr_union
 
 static int dns_query_synthesize_reply(DnsQuery *q, DnsTransactionState *state) {
         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
-        unsigned i;
+        DnsResourceKey *key;
         int r;
 
         assert(q);
@@ -816,39 +875,39 @@ static int dns_query_synthesize_reply(DnsQuery *q, DnsTransactionState *state) {
                     DNS_TRANSACTION_ATTEMPTS_MAX_REACHED))
                 return 0;
 
-        for (i = 0; i < q->question->n_keys; i++) {
+        DNS_QUESTION_FOREACH(key, q->question_utf8) {
                 union in_addr_union address;
                 const char *name;
                 int af;
 
-                if (q->question->keys[i]->class != DNS_CLASS_IN &&
-                    q->question->keys[i]->class != DNS_CLASS_ANY)
+                if (key->class != DNS_CLASS_IN &&
+                    key->class != DNS_CLASS_ANY)
                         continue;
 
-                name = DNS_RESOURCE_KEY_NAME(q->question->keys[i]);
+                name = DNS_RESOURCE_KEY_NAME(key);
 
                 if (is_localhost(name)) {
 
-                        r = synthesize_localhost_rr(q, q->question->keys[i], &answer);
+                        r = synthesize_localhost_rr(q, key, &answer);
                         if (r < 0)
                                 return log_error_errno(r, "Failed to synthesize localhost RRs: %m");
 
                 } else if (manager_is_own_hostname(q->manager, name)) {
 
-                        r = synthesize_system_hostname_rr(q, q->question->keys[i], &answer);
+                        r = synthesize_system_hostname_rr(q, key, &answer);
                         if (r < 0)
                                 return log_error_errno(r, "Failed to synthesize system hostname RRs: %m");
 
                 } else if (is_gateway_hostname(name)) {
 
-                        r = synthesize_gateway_rr(q, q->question->keys[i], &answer);
+                        r = synthesize_gateway_rr(q, key, &answer);
                         if (r < 0)
                                 return log_error_errno(r, "Failed to synthesize gateway RRs: %m");
 
                 } else if ((dns_name_endswith(name, "127.in-addr.arpa") > 0 && dns_name_equal(name, "2.0.0.127.in-addr.arpa") == 0) ||
                            dns_name_equal(name, "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) {
 
-                        r = synthesize_localhost_ptr(q, q->question->keys[i], &answer);
+                        r = synthesize_localhost_ptr(q, key, &answer);
                         if (r < 0)
                                 return log_error_errno(r, "Failed to synthesize localhost PTR RRs: %m");
 
@@ -884,7 +943,6 @@ int dns_query_go(DnsQuery *q) {
         DnsScopeMatch found = DNS_SCOPE_NO;
         DnsScope *s, *first = NULL;
         DnsQueryCandidate *c;
-        const char *name;
         int r;
 
         assert(q);
@@ -892,13 +950,13 @@ int dns_query_go(DnsQuery *q) {
         if (q->state != DNS_TRANSACTION_NULL)
                 return 0;
 
-        assert(q->question);
-        assert(q->question->n_keys > 0);
-
-        name = dns_question_first_name(q->question);
-
         LIST_FOREACH(scopes, s, q->manager->dns_scopes) {
                 DnsScopeMatch match;
+                const char *name;
+
+                name = dns_question_first_name(dns_query_question_for_protocol(q, s->protocol));
+                if (!name)
+                        continue;
 
                 match = dns_scope_good_domain(s, q->ifindex, q->flags, name);
                 if (match < 0)
@@ -934,6 +992,11 @@ int dns_query_go(DnsQuery *q) {
 
         LIST_FOREACH(scopes, s, first->scopes_next) {
                 DnsScopeMatch match;
+                const char *name;
+
+                name = dns_question_first_name(dns_query_question_for_protocol(q, s->protocol));
+                if (!name)
+                        continue;
 
                 match = dns_scope_good_domain(s, q->ifindex, q->flags, name);
                 if (match < 0)
@@ -1115,8 +1178,8 @@ void dns_query_ready(DnsQuery *q) {
 }
 
 static int dns_query_cname_redirect(DnsQuery *q, const DnsResourceRecord *cname) {
-        _cleanup_(dns_question_unrefp) DnsQuestion *nq = NULL;
-        int r;
+        _cleanup_(dns_question_unrefp) DnsQuestion *nq_idna = NULL, *nq_utf8 = NULL;
+        int r, k;
 
         assert(q);
 
@@ -1124,15 +1187,37 @@ static int dns_query_cname_redirect(DnsQuery *q, const DnsResourceRecord *cname)
         if (q->n_cname_redirects > CNAME_MAX)
                 return -ELOOP;
 
-        r = dns_question_cname_redirect(q->question, cname, &nq);
+        r = dns_question_cname_redirect(q->question_idna, cname, &nq_idna);
         if (r < 0)
                 return r;
+        else if (r > 0)
+                log_debug("Following CNAME/DNAME %s → %s", dns_question_first_name(q->question_idna), dns_question_first_name(nq_idna));
+
+        k = dns_question_is_equal(q->question_idna, q->question_utf8);
+        if (k < 0)
+                return r;
+        if (k > 0) {
+                /* Same question? Shortcut new question generation */
+                nq_utf8 = dns_question_ref(nq_idna);
+                k = r;
+        } else {
+                k = dns_question_cname_redirect(q->question_utf8, cname, &nq_utf8);
+                if (k < 0)
+                        return k;
+                else if (k > 0)
+                        log_debug("Following UTF8 CNAME/DNAME %s → %s", dns_question_first_name(q->question_utf8), dns_question_first_name(nq_utf8));
+        }
 
-        log_debug("Following CNAME/DNAME %s → %s", dns_question_first_name(q->question), dns_question_first_name(nq));
+        if (r == 0 && k == 0) /* No actual cname happened? */
+                return -ELOOP;
+
+        dns_question_unref(q->question_idna);
+        q->question_idna = nq_idna;
+        nq_idna = NULL;
 
-        dns_question_unref(q->question);
-        q->question = nq;
-        nq = NULL;
+        dns_question_unref(q->question_utf8);
+        q->question_utf8 = nq_utf8;
+        nq_utf8 = NULL;
 
         dns_query_stop(q);
         q->state = DNS_TRANSACTION_NULL;
@@ -1142,6 +1227,7 @@ static int dns_query_cname_redirect(DnsQuery *q, const DnsResourceRecord *cname)
 
 int dns_query_process_cname(DnsQuery *q) {
         _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *cname = NULL;
+        DnsQuestion *question;
         DnsResourceRecord *rr;
         int r;
 
@@ -1150,15 +1236,16 @@ int dns_query_process_cname(DnsQuery *q) {
         if (!IN_SET(q->state, DNS_TRANSACTION_SUCCESS, DNS_TRANSACTION_NULL))
                 return DNS_QUERY_NOMATCH;
 
-        DNS_ANSWER_FOREACH(rr, q->answer) {
+        question = dns_query_question_for_protocol(q, q->answer_protocol);
 
-                r = dns_question_matches_rr(q->question, rr, DNS_SEARCH_DOMAIN_NAME(q->answer_search_domain));
+        DNS_ANSWER_FOREACH(rr, q->answer) {
+                r = dns_question_matches_rr(question, rr, DNS_SEARCH_DOMAIN_NAME(q->answer_search_domain));
                 if (r < 0)
                         return r;
                 if (r > 0)
                         return DNS_QUERY_MATCH; /* The answer matches directly, no need to follow cnames */
 
-                r = dns_question_matches_cname(q->question, rr, DNS_SEARCH_DOMAIN_NAME(q->answer_search_domain));
+                r = dns_question_matches_cname(question, rr, DNS_SEARCH_DOMAIN_NAME(q->answer_search_domain));
                 if (r < 0)
                         return r;
                 if (r > 0 && !cname)
@@ -1219,3 +1306,42 @@ int dns_query_bus_track(DnsQuery *q, sd_bus_message *m) {
 
         return 0;
 }
+
+DnsQuestion* dns_query_question_for_protocol(DnsQuery *q, DnsProtocol protocol) {
+        assert(q);
+
+        switch (protocol) {
+
+        case DNS_PROTOCOL_DNS:
+                return q->question_idna;
+
+        case DNS_PROTOCOL_MDNS:
+        case DNS_PROTOCOL_LLMNR:
+                return q->question_utf8;
+
+        default:
+                return NULL;
+        }
+}
+
+const char *dns_query_string(DnsQuery *q) {
+        const char *name;
+        int r;
+
+        /* Returns a somewhat useful human-readable lookup key string for this query */
+
+        if (q->request_address_string)
+                return q->request_address_string;
+
+        if (q->request_address_valid) {
+                r = in_addr_to_string(q->request_family, &q->request_address, &q->request_address_string);
+                if (r >= 0)
+                        return q->request_address_string;
+        }
+
+        name = dns_question_first_name(q->question_utf8);
+        if (name)
+                return name;
+
+        return dns_question_first_name(q->question_idna);
+}
diff --git a/src/resolve/resolved-dns-query.h b/src/resolve/resolved-dns-query.h
index 4a0d265a2d..9f618d6f6b 100644
--- a/src/resolve/resolved-dns-query.h
+++ b/src/resolve/resolved-dns-query.h
@@ -59,7 +59,13 @@ struct DnsQuery {
         unsigned n_auxiliary_queries;
         int auxiliary_result;
 
-        DnsQuestion *question;
+        /* The question, formatted in IDNA for use on classic DNS, and as UTF8 for use in LLMNR or mDNS. Note that even
+         * on classic DNS some labels might use UTF8 encoding. Specifically, DNS-SD service names (in contrast to their
+         * domain suffixes) use UTF-8 encoding even on DNS. Thus, the difference between these two fields is mostly
+         * relevant only for explicit *hostname* lookups as well as the domain suffixes of service lookups. */
+        DnsQuestion *question_idna;
+        DnsQuestion *question_utf8;
+
         uint64_t flags;
         int ifindex;
 
@@ -84,6 +90,7 @@ struct DnsQuery {
         bool request_address_valid;
         union in_addr_union request_address;
         unsigned block_all_complete;
+        char *request_address_string;
 
         /* Completion callback */
         void (*complete)(DnsQuery* q);
@@ -104,7 +111,7 @@ enum {
 DnsQueryCandidate* dns_query_candidate_free(DnsQueryCandidate *c);
 void dns_query_candidate_notify(DnsQueryCandidate *c);
 
-int dns_query_new(Manager *m, DnsQuery **q, DnsQuestion *question, int family, uint64_t flags);
+int dns_query_new(Manager *m, DnsQuery **q, DnsQuestion *question_utf8, DnsQuestion *question_idna, int family, uint64_t flags);
 DnsQuery *dns_query_free(DnsQuery *q);
 
 int dns_query_make_auxiliary(DnsQuery *q, DnsQuery *auxiliary_for);
@@ -116,4 +123,8 @@ int dns_query_process_cname(DnsQuery *q);
 
 int dns_query_bus_track(DnsQuery *q, sd_bus_message *m);
 
+DnsQuestion* dns_query_question_for_protocol(DnsQuery *q, DnsProtocol protocol);
+
+const char *dns_query_string(DnsQuery *q);
+
 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsQuery*, dns_query_free);
diff --git a/src/resolve/resolved-dns-question.c b/src/resolve/resolved-dns-question.c
index 938b43f225..fb5637779c 100644
--- a/src/resolve/resolved-dns-question.c
+++ b/src/resolve/resolved-dns-question.c
@@ -210,32 +210,27 @@ int dns_question_is_equal(DnsQuestion *a, DnsQuestion *b) {
 
 int dns_question_cname_redirect(DnsQuestion *q, const DnsResourceRecord *cname, DnsQuestion **ret) {
         _cleanup_(dns_question_unrefp) DnsQuestion *n = NULL;
+        DnsResourceKey *key;
         bool same = true;
-        unsigned i;
         int r;
 
         assert(cname);
         assert(ret);
         assert(IN_SET(cname->key->type, DNS_TYPE_CNAME, DNS_TYPE_DNAME));
 
-        if (!q) {
-                n = dns_question_new(0);
-                if (!n)
-                        return -ENOMEM;
-
-                *ret = n;
-                n = 0;
+        if (dns_question_size(q) <= 0) {
+                *ret = NULL;
                 return 0;
         }
 
-        for (i = 0; i < q->n_keys; i++) {
+        DNS_QUESTION_FOREACH(key, q) {
                 _cleanup_free_ char *destination = NULL;
                 const char *d;
 
                 if (cname->key->type == DNS_TYPE_CNAME)
                         d = cname->cname.name;
                 else {
-                        r = dns_name_change_suffix(DNS_RESOURCE_KEY_NAME(q->keys[i]), DNS_RESOURCE_KEY_NAME(cname->key), cname->dname.name, &destination);
+                        r = dns_name_change_suffix(DNS_RESOURCE_KEY_NAME(key), DNS_RESOURCE_KEY_NAME(cname->key), cname->dname.name, &destination);
                         if (r < 0)
                                 return r;
                         if (r == 0)
@@ -244,7 +239,7 @@ int dns_question_cname_redirect(DnsQuestion *q, const DnsResourceRecord *cname,
                         d = destination;
                 }
 
-                r = dns_name_equal(DNS_RESOURCE_KEY_NAME(q->keys[i]), d);
+                r = dns_name_equal(DNS_RESOURCE_KEY_NAME(key), d);
                 if (r < 0)
                         return r;
 
@@ -254,9 +249,9 @@ int dns_question_cname_redirect(DnsQuestion *q, const DnsResourceRecord *cname,
                 }
         }
 
+        /* Fully the same, indicate we didn't do a thing */
         if (same) {
-                /* Shortcut, the names are already right */
-                *ret = dns_question_ref(q);
+                *ret = NULL;
                 return 0;
         }
 
@@ -265,10 +260,10 @@ int dns_question_cname_redirect(DnsQuestion *q, const DnsResourceRecord *cname,
                 return -ENOMEM;
 
         /* Create a new question, and patch in the new name */
-        for (i = 0; i < q->n_keys; i++) {
+        DNS_QUESTION_FOREACH(key, q) {
                 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *k = NULL;
 
-                k = dns_resource_key_new_redirect(q->keys[i], cname);
+                k = dns_resource_key_new_redirect(key, cname);
                 if (!k)
                         return -ENOMEM;
 
@@ -294,8 +289,9 @@ const char *dns_question_first_name(DnsQuestion *q) {
         return DNS_RESOURCE_KEY_NAME(q->keys[0]);
 }
 
-int dns_question_new_address(DnsQuestion **ret, int family, const char *name) {
+int dns_question_new_address(DnsQuestion **ret, int family, const char *name, bool convert_idna) {
         _cleanup_(dns_question_unrefp) DnsQuestion *q = NULL;
+        _cleanup_free_ char *buf = NULL;
         int r;
 
         assert(ret);
@@ -304,6 +300,14 @@ int dns_question_new_address(DnsQuestion **ret, int family, const char *name) {
         if (!IN_SET(family, AF_INET, AF_INET6, AF_UNSPEC))
                 return -EAFNOSUPPORT;
 
+        if (convert_idna) {
+                r = dns_name_apply_idna(name, &buf);
+                if (r < 0)
+                        return r;
+
+                name = buf;
+        }
+
         q = dns_question_new(family == AF_UNSPEC ? 2 : 1);
         if (!q)
                 return -ENOMEM;
@@ -374,13 +378,60 @@ int dns_question_new_reverse(DnsQuestion **ret, int family, const union in_addr_
         return 0;
 }
 
-int dns_question_new_service(DnsQuestion **ret, const char *name, bool with_txt) {
+int dns_question_new_service(
+                DnsQuestion **ret,
+                const char *service,
+                const char *type,
+                const char *domain,
+                bool with_txt,
+                bool convert_idna) {
+
         _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
         _cleanup_(dns_question_unrefp) DnsQuestion *q = NULL;
+        _cleanup_free_ char *buf = NULL, *joined = NULL;
+        const char *name;
         int r;
 
         assert(ret);
-        assert(name);
+
+        /* We support three modes of invocation:
+         *
+         * 1. Only a domain is specified, in which case we assume a properly encoded SRV RR name, including service
+         *    type and possibly a service name. If specified in this way we assume it's already IDNA converted if
+         *    that's necessary.
+         *
+         * 2. Both service type and a domain specified, in which case a normal SRV RR is assumed, without a DNS-SD
+         *    style prefix. In this case we'll IDNA convert the domain, if that's requested.
+         *
+         * 3. All three of service name, type and domain are specified, in which case a DNS-SD service is put
+         *    together. The service name is never IDNA converted, and the domain is if requested.
+         *
+         * It's not supported to specify a service name without a type, or no domain name.
+         */
+
+        if (!domain)
+                return -EINVAL;
+
+        if (type) {
+                if (convert_idna) {
+                        r = dns_name_apply_idna(domain, &buf);
+                        if (r < 0)
+                                return r;
+
+                        domain = buf;
+                }
+
+                r = dns_service_join(service, type, domain, &joined);
+                if (r < 0)
+                        return r;
+
+                name = joined;
+        } else {
+                if (service)
+                        return -EINVAL;
+
+                name = domain;
+        }
 
         q = dns_question_new(1 + with_txt);
         if (!q)
diff --git a/src/resolve/resolved-dns-question.h b/src/resolve/resolved-dns-question.h
index 1be873f66d..7ca9224e6f 100644
--- a/src/resolve/resolved-dns-question.h
+++ b/src/resolve/resolved-dns-question.h
@@ -38,9 +38,9 @@ DnsQuestion *dns_question_new(unsigned n);
 DnsQuestion *dns_question_ref(DnsQuestion *q);
 DnsQuestion *dns_question_unref(DnsQuestion *q);
 
-int dns_question_new_address(DnsQuestion **ret, int family, const char *name);
+int dns_question_new_address(DnsQuestion **ret, int family, const char *name, bool convert_idna);
 int dns_question_new_reverse(DnsQuestion **ret, int family, const union in_addr_union *a);
-int dns_question_new_service(DnsQuestion **ret, const char *name, bool with_txt);
+int dns_question_new_service(DnsQuestion **ret, const char *service, const char *type, const char *domain, bool with_txt, bool convert_idna);
 
 int dns_question_add(DnsQuestion *q, DnsResourceKey *key);
 
@@ -54,6 +54,10 @@ int dns_question_cname_redirect(DnsQuestion *q, const DnsResourceRecord *cname,
 
 const char *dns_question_first_name(DnsQuestion *q);
 
+static inline unsigned dns_question_size(DnsQuestion *q) {
+        return q ? q->n_keys : 0;
+}
+
 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsQuestion*, dns_question_unref);
 
 #define _DNS_QUESTION_FOREACH(u, key, q)                                \
diff --git a/src/shared/dns-domain.c b/src/shared/dns-domain.c
index 33bc26ad7d..3ad409fc29 100644
--- a/src/shared/dns-domain.c
+++ b/src/shared/dns-domain.c
@@ -413,7 +413,6 @@ int dns_name_concat(const char *a, const char *b, char **_ret) {
 
         for (;;) {
                 char label[DNS_LABEL_MAX];
-                int k;
 
                 r = dns_label_unescape(&p, label, sizeof(label));
                 if (r < 0)
@@ -432,12 +431,6 @@ int dns_name_concat(const char *a, const char *b, char **_ret) {
                         break;
                 }
 
-                k = dns_label_undo_idna(label, r, label, sizeof(label));
-                if (k < 0)
-                        return k;
-                if (k > 0)
-                        r = k;
-
                 if (_ret) {
                         if (!GREEDY_REALLOC(ret, allocated, n + !first + DNS_LABEL_ESCAPED_MAX))
                                 return -ENOMEM;
@@ -487,7 +480,6 @@ void dns_name_hash_func(const void *s, struct siphash *state) {
 
         for (;;) {
                 char label[DNS_LABEL_MAX+1];
-                int k;
 
                 r = dns_label_unescape(&p, label, sizeof(label));
                 if (r < 0)
@@ -495,12 +487,6 @@ void dns_name_hash_func(const void *s, struct siphash *state) {
                 if (r == 0)
                         break;
 
-                k = dns_label_undo_idna(label, r, label, sizeof(label));
-                if (k < 0)
-                        break;
-                if (k > 0)
-                        r = k;
-
                 ascii_strlower_n(label, r);
                 siphash24_compress(label, r, state);
                 siphash24_compress_byte(0, state); /* make sure foobar and foo.bar result in different hashes */
@@ -512,7 +498,7 @@ void dns_name_hash_func(const void *s, struct siphash *state) {
 
 int dns_name_compare_func(const void *a, const void *b) {
         const char *x, *y;
-        int r, q, k, w;
+        int r, q;
 
         assert(a);
         assert(b);
@@ -531,22 +517,6 @@ int dns_name_compare_func(const void *a, const void *b) {
                 if (r < 0 || q < 0)
                         return r - q;
 
-                if (r > 0)
-                        k = dns_label_undo_idna(la, r, la, sizeof(la));
-                else
-                        k = 0;
-                if (q > 0)
-                        w = dns_label_undo_idna(lb, q, lb, sizeof(lb));
-                else
-                        w = 0;
-
-                if (k < 0 || w < 0)
-                        return k - w;
-                if (k > 0)
-                        r = k;
-                if (w > 0)
-                        q = w;
-
                 r = ascii_strcasecmp_nn(la, r, lb, q);
                 if (r != 0)
                         return r;
@@ -558,24 +528,6 @@ const struct hash_ops dns_name_hash_ops = {
         .compare = dns_name_compare_func
 };
 
-static int dns_label_unescape_undo_idna(const char **name, char *dest, size_t sz) {
-        int r, k;
-
-        /* Clobbers all arguments on failure... */
-
-        r = dns_label_unescape(name, dest, sz);
-        if (r <= 0)
-                return r;
-
-        k = dns_label_undo_idna(dest, r, dest, sz);
-        if (k < 0)
-                return k;
-        if (k == 0) /* not an IDNA name */
-                return r;
-
-        return k;
-}
-
 int dns_name_equal(const char *x, const char *y) {
         int r, q;
 
@@ -585,11 +537,11 @@ int dns_name_equal(const char *x, const char *y) {
         for (;;) {
                 char la[DNS_LABEL_MAX], lb[DNS_LABEL_MAX];
 
-                r = dns_label_unescape_undo_idna(&x, la, sizeof(la));
+                r = dns_label_unescape(&x, la, sizeof(la));
                 if (r < 0)
                         return r;
 
-                q = dns_label_unescape_undo_idna(&y, lb, sizeof(lb));
+                q = dns_label_unescape(&y, lb, sizeof(lb));
                 if (q < 0)
                         return q;
 
@@ -616,14 +568,14 @@ int dns_name_endswith(const char *name, const char *suffix) {
         for (;;) {
                 char ln[DNS_LABEL_MAX], ls[DNS_LABEL_MAX];
 
-                r = dns_label_unescape_undo_idna(&n, ln, sizeof(ln));
+                r = dns_label_unescape(&n, ln, sizeof(ln));
                 if (r < 0)
                         return r;
 
                 if (!saved_n)
                         saved_n = n;
 
-                q = dns_label_unescape_undo_idna(&s, ls, sizeof(ls));
+                q = dns_label_unescape(&s, ls, sizeof(ls));
                 if (q < 0)
                         return q;
 
@@ -655,13 +607,13 @@ int dns_name_startswith(const char *name, const char *prefix) {
         for (;;) {
                 char ln[DNS_LABEL_MAX], lp[DNS_LABEL_MAX];
 
-                r = dns_label_unescape_undo_idna(&p, lp, sizeof(lp));
+                r = dns_label_unescape(&p, lp, sizeof(lp));
                 if (r < 0)
                         return r;
                 if (r == 0)
                         return true;
 
-                q = dns_label_unescape_undo_idna(&n, ln, sizeof(ln));
+                q = dns_label_unescape(&n, ln, sizeof(ln));
                 if (q < 0)
                         return q;
 
@@ -690,14 +642,14 @@ int dns_name_change_suffix(const char *name, const char *old_suffix, const char
                 if (!saved_before)
                         saved_before = n;
 
-                r = dns_label_unescape_undo_idna(&n, ln, sizeof(ln));
+                r = dns_label_unescape(&n, ln, sizeof(ln));
                 if (r < 0)
                         return r;
 
                 if (!saved_after)
                         saved_after = n;
 
-                q = dns_label_unescape_undo_idna(&s, ls, sizeof(ls));
+                q = dns_label_unescape(&s, ls, sizeof(ls));
                 if (q < 0)
                         return q;
 
@@ -1286,12 +1238,12 @@ int dns_name_common_suffix(const char *a, const char *b, const char **ret) {
                 }
 
                 x = a_labels[n - 1 - k];
-                r = dns_label_unescape_undo_idna(&x, la, sizeof(la));
+                r = dns_label_unescape(&x, la, sizeof(la));
                 if (r < 0)
                         return r;
 
                 y = b_labels[m - 1 - k];
-                q = dns_label_unescape_undo_idna(&y, lb, sizeof(lb));
+                q = dns_label_unescape(&y, lb, sizeof(lb));
                 if (q < 0)
                         return q;