16 files changed, 1018 insertions, 529 deletions

diff --git a/Makefile.am b/Makefile.am
index 55ed54d941..3fb3703c46 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -4710,6 +4710,12 @@ systemd_resolved_SOURCES = \
 	src/resolve/resolved-link.c \
 	src/resolve/resolved-dns-domain.h \
 	src/resolve/resolved-dns-domain.c \
+	src/resolve/resolved-dns-rr.h \
+	src/resolve/resolved-dns-rr.c \
+	src/resolve/resolved-dns-question.h \
+	src/resolve/resolved-dns-question.c \
+	src/resolve/resolved-dns-answer.h \
+	src/resolve/resolved-dns-answer.c \
 	src/resolve/resolved-dns-packet.h \
 	src/resolve/resolved-dns-packet.c \
 	src/resolve/resolved-dns-query.h \
@@ -4718,8 +4724,6 @@ systemd_resolved_SOURCES = \
 	src/resolve/resolved-dns-scope.c \
 	src/resolve/resolved-dns-server.h \
 	src/resolve/resolved-dns-server.c \
-	src/resolve/resolved-dns-rr.h \
-	src/resolve/resolved-dns-rr.c \
 	src/resolve/resolved-dns-cache.h \
 	src/resolve/resolved-dns-cache.c
 
diff --git a/src/resolve/resolved-bus.c b/src/resolve/resolved-bus.c
index 5222cc81f1..1244b6dd07 100644
--- a/src/resolve/resolved-bus.c
+++ b/src/resolve/resolved-bus.c
@@ -59,21 +59,16 @@ static int reply_query_state(DnsQuery *q) {
 
         case DNS_QUERY_FAILURE: {
                 _cleanup_bus_error_free_ sd_bus_error error = SD_BUS_ERROR_NULL;
-                int rcode;
 
-                rcode = dns_query_get_rcode(q);
-                if (rcode < 0)
-                        return rcode;
-
-                if (rcode == DNS_RCODE_NXDOMAIN)
+                if (q->answer_rcode == DNS_RCODE_NXDOMAIN)
                         sd_bus_error_setf(&error, _BUS_ERROR_DNS "NXDOMAIN", "'%s' not found", name);
                 else {
                         const char *rc, *n;
                         char p[3]; /* the rcode is 4 bits long */
 
-                        rc = dns_rcode_to_string(rcode);
+                        rc = dns_rcode_to_string(q->answer_rcode);
                         if (!rc) {
-                                sprintf(p, "%i", rcode);
+                                sprintf(p, "%i", q->answer_rcode);
                                 rc = p;
                         }
 
@@ -102,19 +97,22 @@ static int append_address(sd_bus_message *reply, DnsResourceRecord *rr, int ifin
         if (r < 0)
                 return r;
 
-        if (rr->key.type == DNS_TYPE_A) {
+        if (rr->key->type == DNS_TYPE_A) {
                 r = sd_bus_message_append(reply, "i", AF_INET);
                 if (r < 0)
                         return r;
 
                 r = sd_bus_message_append_array(reply, 'y', &rr->a.in_addr, sizeof(struct in_addr));
-        } else {
+
+        } else if (rr->key->type == DNS_TYPE_AAAA) {
                 r = sd_bus_message_append(reply, "i", AF_INET6);
                 if (r < 0)
                         return r;
 
                 r = sd_bus_message_append_array(reply, 'y', &rr->aaaa.in6_addr, sizeof(struct in6_addr));
-        }
+        } else
+                return -EAFNOSUPPORT;
+
         if (r < 0)
                 return r;
 
@@ -132,10 +130,9 @@ static int append_address(sd_bus_message *reply, DnsResourceRecord *rr, int ifin
 static void bus_method_resolve_hostname_complete(DnsQuery *q) {
         _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *cname = NULL, *canonical = NULL;
         _cleanup_bus_message_unref_ sd_bus_message *reply = NULL;
-        DnsResourceRecord **rrs;
-        unsigned added = 0;
-        int ifindex;
-        int r, n, i;
+        _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
+        unsigned added = 0, i;
+        int r, ifindex;
 
         assert(q);
 
@@ -144,10 +141,6 @@ static void bus_method_resolve_hostname_complete(DnsQuery *q) {
                 goto finish;
         }
 
-        n = dns_query_get_rrs(q, &rrs);
-        if (n < 0)
-                goto parse_fail;
-
         r = sd_bus_message_new_method_return(q->request, &reply);
         if (r < 0)
                 goto finish;
@@ -156,32 +149,31 @@ static void bus_method_resolve_hostname_complete(DnsQuery *q) {
         if (r < 0)
                 goto finish;
 
-        ifindex = dns_query_get_ifindex(q);
-        if (ifindex < 0)
-                ifindex = 0;
+        answer = dns_answer_ref(q->answer);
+        ifindex = q->answer_ifindex;
 
-        for (i = 0; i < n; i++) {
-                r = dns_query_matches_rr(q, rrs[i]);
+        for (i = 0; i < answer->n_rrs; i++) {
+                r = dns_question_matches_rr(q->question, answer->rrs[i]);
                 if (r < 0)
                         goto parse_fail;
                 if (r == 0) {
                         /* Hmm, if this is not an address record,
                            maybe it's a cname? If so, remember this */
-                        r = dns_query_matches_cname(q, rrs[i]);
+                        r = dns_question_matches_cname(q->question, answer->rrs[i]);
                         if (r < 0)
                                 goto parse_fail;
                         if (r > 0)
-                                cname = dns_resource_record_ref(rrs[i]);
+                                cname = dns_resource_record_ref(answer->rrs[i]);
 
                         continue;
                 }
 
-                r = append_address(reply, rrs[i], ifindex);
+                r = append_address(reply, answer->rrs[i], ifindex);
                 if (r < 0)
                         goto finish;
 
                 if (!canonical)
-                        canonical = dns_resource_record_ref(rrs[i]);
+                        canonical = dns_resource_record_ref(answer->rrs[i]);
 
                 added ++;
         }
@@ -206,19 +198,19 @@ static void bus_method_resolve_hostname_complete(DnsQuery *q) {
 
                 /* Before we restart the query, let's see if any of
                  * the RRs we already got already answers our query */
-                for (i = 0; i < n; i++) {
-                        r = dns_query_matches_rr(q, rrs[i]);
+                for (i = 0; i < answer->n_rrs; i++) {
+                        r = dns_question_matches_rr(q->question, answer->rrs[i]);
                         if (r < 0)
                                 goto parse_fail;
                         if (r == 0)
                                 continue;
 
-                        r = append_address(reply, rrs[i], ifindex);
+                        r = append_address(reply, answer->rrs[i], ifindex);
                         if (r < 0)
                                 goto finish;
 
                         if (!canonical)
-                                canonical = dns_resource_record_ref(rrs[i]);
+                                canonical = dns_resource_record_ref(answer->rrs[i]);
 
                         added++;
                 }
@@ -245,7 +237,7 @@ static void bus_method_resolve_hostname_complete(DnsQuery *q) {
 
         /* Return the precise spelling and uppercasing reported by the server */
         assert(canonical);
-        r = sd_bus_message_append(reply, "s", canonical->key.name);
+        r = sd_bus_message_append(reply, "s", DNS_RESOURCE_KEY_NAME(canonical->key));
         if (r < 0)
                 goto finish;
 
@@ -263,12 +255,11 @@ finish:
 }
 
 static int bus_method_resolve_hostname(sd_bus *bus, sd_bus_message *message, void *userdata, sd_bus_error *error) {
+        _cleanup_(dns_question_unrefp) DnsQuestion *question = NULL;
         Manager *m = userdata;
         const char *hostname;
         int family;
-        DnsResourceKey keys[2];
         DnsQuery *q;
-        unsigned n = 0;
         int r;
 
         assert(bus);
@@ -285,21 +276,35 @@ static int bus_method_resolve_hostname(sd_bus *bus, sd_bus_message *message, voi
         if (!hostname_is_valid(hostname))
                 return sd_bus_error_setf(error, SD_BUS_ERROR_INVALID_ARGS, "Invalid hostname '%s'", hostname);
 
+        question = dns_question_new(family == AF_UNSPEC ? 2 : 1);
+        if (!question)
+                return -ENOMEM;
+
         if (family != AF_INET6) {
-                keys[n].class = DNS_CLASS_IN;
-                keys[n].type = DNS_TYPE_A;
-                keys[n].name = (char*) hostname;
-                n++;
+                _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
+
+                key = dns_resource_key_new(DNS_CLASS_IN, DNS_TYPE_A, hostname);
+                if (!key)
+                        return -ENOMEM;
+
+                r = dns_question_add(question, key);
+                if (r < 0)
+                        return r;
         }
 
         if (family != AF_INET) {
-                keys[n].class = DNS_CLASS_IN;
-                keys[n].type = DNS_TYPE_AAAA;
-                keys[n].name = (char*) hostname;
-                n++;
+                _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
+
+                key = dns_resource_key_new(DNS_CLASS_IN, DNS_TYPE_AAAA, hostname);
+                if (!key)
+                        return -ENOMEM;
+
+                r = dns_question_add(question, key);
+                if (r < 0)
+                        return r;
         }
 
-        r = dns_query_new(m, &q, keys, n);
+        r = dns_query_new(m, &q, question);
         if (r < 0)
                 return r;
 
@@ -323,9 +328,9 @@ static int bus_method_resolve_hostname(sd_bus *bus, sd_bus_message *message, voi
 
 static void bus_method_resolve_address_complete(DnsQuery *q) {
         _cleanup_bus_message_unref_ sd_bus_message *reply = NULL;
-        DnsResourceRecord **rrs;
-        unsigned added = 0;
-        int r, n, i;
+        _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
+        unsigned added = 0, i;
+        int r;
 
         assert(q);
 
@@ -334,10 +339,6 @@ static void bus_method_resolve_address_complete(DnsQuery *q) {
                 goto finish;
         }
 
-        n = dns_query_get_rrs(q, &rrs);
-        if (n < 0)
-                goto parse_fail;
-
         r = sd_bus_message_new_method_return(q->request, &reply);
         if (r < 0)
                 goto finish;
@@ -346,14 +347,16 @@ static void bus_method_resolve_address_complete(DnsQuery *q) {
         if (r < 0)
                 goto finish;
 
-        for (i = 0; i < n; i++) {
-                r = dns_query_matches_rr(q, rrs[i]);
+        answer = dns_answer_ref(q->answer);
+
+        for (i = 0; i < answer->n_rrs; i++) {
+                r = dns_question_matches_rr(q->question, answer->rrs[i]);
                 if (r < 0)
                         goto parse_fail;
                 if (r == 0)
                         continue;
 
-                r = sd_bus_message_append(reply, "s", rrs[i]->ptr.name);
+                r = sd_bus_message_append(reply, "s", answer->rrs[i]->ptr.name);
                 if (r < 0)
                         goto finish;
 
@@ -387,11 +390,12 @@ finish:
 }
 
 static int bus_method_resolve_address(sd_bus *bus, sd_bus_message *message, void *userdata, sd_bus_error *error) {
-        _cleanup_(dns_resource_key_free) DnsResourceKey key = {};
+        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
+        _cleanup_(dns_question_unrefp) DnsQuestion *question = NULL;
+        _cleanup_free_ char *reverse = NULL;
         Manager *m = userdata;
-        int family;
+        int family, ifindex;
         const void *d;
-        int ifindex;
         DnsQuery *q;
         size_t sz;
         int r;
@@ -420,13 +424,25 @@ static int bus_method_resolve_address(sd_bus *bus, sd_bus_message *message, void
         if (ifindex < 0)
                 return sd_bus_error_setf(error, SD_BUS_ERROR_INVALID_ARGS, "Invalid interface index");
 
-        key.class = DNS_CLASS_IN;
-        key.type = DNS_TYPE_PTR;
-        r = dns_name_reverse(family, d, &key.name);
+        r = dns_name_reverse(family, d, &reverse);
+        if (r < 0)
+                return r;
+
+        question = dns_question_new(1);
+        if (!question)
+                return -ENOMEM;
+
+        key = dns_resource_key_new_consume(DNS_CLASS_IN, DNS_TYPE_PTR, reverse);
+        if (!key)
+                return -ENOMEM;
+
+        reverse = NULL;
+
+        r = dns_question_add(question, key);
         if (r < 0)
                 return r;
 
-        r = dns_query_new(m, &q, &key, 1);
+        r = dns_query_new(m, &q, question);
         if (r < 0)
                 return r;
 
@@ -438,6 +454,10 @@ static int bus_method_resolve_address(sd_bus *bus, sd_bus_message *message, void
         r = dns_query_go(q);
         if (r < 0) {
                 dns_query_free(q);
+
+                if (r == -ESRCH)
+                        sd_bus_error_setf(error, BUS_ERROR_NO_NAME_SERVERS, "No appropriate name servers or networks for name found");
+
                 return r;
         }
 
diff --git a/src/resolve/resolved-dns-answer.c b/src/resolve/resolved-dns-answer.c
new file mode 100644
index 0000000000..fbc282550e
--- /dev/null
+++ b/src/resolve/resolved-dns-answer.c
@@ -0,0 +1,76 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+/***
+  This file is part of systemd.
+
+  Copyright 2014 Lennart Poettering
+
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd is distributed in the hope that it will be useful, but
+  WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include "resolved-dns-answer.h"
+
+DnsAnswer *dns_answer_new(unsigned n) {
+        DnsAnswer *a;
+
+        assert(n > 0);
+
+        a = malloc0(offsetof(DnsAnswer, rrs) + sizeof(DnsResourceRecord*) * n);
+        if (!a)
+                return NULL;
+
+        a->n_ref = 1;
+        a->n_allocated = n;
+
+        return a;
+}
+
+DnsAnswer *dns_answer_ref(DnsAnswer *a) {
+        if (!a)
+                return NULL;
+
+        assert(a->n_ref > 0);
+        a->n_ref++;
+        return a;
+}
+
+DnsAnswer *dns_answer_unref(DnsAnswer *a) {
+        if (!a)
+                return NULL;
+
+        assert(a->n_ref > 0);
+
+        if (a->n_ref == 1) {
+                unsigned i;
+
+                for (i = 0; i < a->n_rrs; i++)
+                        dns_resource_record_unref(a->rrs[i]);
+
+                free(a);
+        } else
+                a->n_ref--;
+
+        return NULL;
+}
+
+int dns_answer_add(DnsAnswer *a, DnsResourceRecord *rr) {
+        assert(a);
+        assert(rr);
+
+        if (a->n_rrs >= a->n_allocated)
+                return -ENOSPC;
+
+        a->rrs[a->n_rrs++] = dns_resource_record_ref(rr);
+        return 0;
+}
diff --git a/src/resolve/resolved-dns-answer.h b/src/resolve/resolved-dns-answer.h
new file mode 100644
index 0000000000..dc2ec3a461
--- /dev/null
+++ b/src/resolve/resolved-dns-answer.h
@@ -0,0 +1,42 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+#pragma once
+
+/***
+  This file is part of systemd.
+
+  Copyright 2014 Lennart Poettering
+
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd is distributed in the hope that it will be useful, but
+  WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+typedef struct DnsAnswer DnsAnswer;
+
+#include "resolved-dns-rr.h"
+
+/* A simple array of resource records */
+
+struct DnsAnswer {
+        unsigned n_ref;
+        unsigned n_rrs, n_allocated;
+        DnsResourceRecord* rrs[0];
+};
+
+DnsAnswer *dns_answer_new(unsigned n);
+DnsAnswer *dns_answer_ref(DnsAnswer *a);
+DnsAnswer *dns_answer_unref(DnsAnswer *a);
+
+int dns_answer_add(DnsAnswer *a, DnsResourceRecord *rr);
+
+DEFINE_TRIVIAL_CLEANUP_FUNC(DnsAnswer*, dns_answer_unref);
diff --git a/src/resolve/resolved-dns-cache.c b/src/resolve/resolved-dns-cache.c
index ce74a81f6a..e42af41c78 100644
--- a/src/resolve/resolved-dns-cache.c
+++ b/src/resolve/resolved-dns-cache.c
@@ -45,13 +45,13 @@ static void dns_cache_item_remove_and_free(DnsCache *c, DnsCacheItem *i) {
         if (!i)
                 return;
 
-        first = hashmap_get(c->rrsets, &i->rr->key);
+        first = hashmap_get(c->rrsets, i->rr->key);
         LIST_REMOVE(rrsets, first, i);
 
         if (first)
-                assert_se(hashmap_replace(c->rrsets, &first->rr->key, first) >= 0);
+                assert_se(hashmap_replace(c->rrsets, first->rr->key, first) >= 0);
         else
-                hashmap_remove(c->rrsets, &i->rr->key);
+                hashmap_remove(c->rrsets, i->rr->key);
 
         prioq_remove(c->expire, i, &i->expire_prioq_idx);
 
@@ -98,7 +98,7 @@ static void dns_cache_make_space(DnsCache *c, unsigned add) {
          * case the cache will be emptied completely otherwise. */
 
         for (;;) {
-                _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *rr = NULL;
+                _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
                 DnsCacheItem *i;
 
                 if (prioq_size(c->expire) <= 0)
@@ -110,10 +110,10 @@ static void dns_cache_make_space(DnsCache *c, unsigned add) {
                 i = prioq_peek(c->expire);
                 assert(i);
 
-                /* Take an extra reference to the RR so that the key
+                /* Take an extra reference to the key so that it
                  * doesn't go away in the middle of the remove call */
-                rr = dns_resource_record_ref(i->rr);
-                dns_cache_remove(c, &rr->key);
+                key = dns_resource_key_ref(i->rr->key);
+                dns_cache_remove(c, key);
         }
 }
 
@@ -125,7 +125,7 @@ void dns_cache_prune(DnsCache *c) {
         /* Remove all entries that are past their TTL */
 
         for (;;) {
-                _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *rr = NULL;
+                _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
                 DnsCacheItem *i;
                 usec_t ttl;
 
@@ -143,10 +143,10 @@ void dns_cache_prune(DnsCache *c) {
                 if (i->timestamp + ttl > t)
                         break;
 
-                /* Take an extra reference to the RR so that the key
+                /* Take an extra reference to the key so that it
                  * doesn't go away in the middle of the remove call */
-                rr = dns_resource_record_ref(i->rr);
-                dns_cache_remove(c, &rr->key);
+                key = dns_resource_key_ref(i->rr->key);
+                dns_cache_remove(c, key);
         }
 }
 
@@ -173,7 +173,7 @@ static void dns_cache_item_update(DnsCache *c, DnsCacheItem *i, DnsResourceRecor
                 /* We are the first item in the list, we need to
                  * update the key used in the hashmap */
 
-                assert_se(hashmap_replace(c->rrsets, &rr->key, i) >= 0);
+                assert_se(hashmap_replace(c->rrsets, rr->key, i) >= 0);
         }
 
         dns_resource_record_ref(rr);
@@ -184,6 +184,19 @@ static void dns_cache_item_update(DnsCache *c, DnsCacheItem *i, DnsResourceRecor
         prioq_reshuffle(c->expire, i, &i->expire_prioq_idx);
 }
 
+static DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr) {
+        DnsCacheItem *i;
+
+        assert(c);
+        assert(rr);
+
+        LIST_FOREACH(rrsets, i, hashmap_get(c->rrsets, rr->key))
+                if (dns_resource_record_equal(i->rr, rr))
+                        return i;
+
+        return NULL;
+}
+
 int dns_cache_put(DnsCache *c, DnsResourceRecord *rr, usec_t timestamp) {
         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
         DnsCacheItem *first = NULL, *existing;
@@ -194,7 +207,7 @@ int dns_cache_put(DnsCache *c, DnsResourceRecord *rr, usec_t timestamp) {
 
         /* New TTL is 0? Delete the entry... */
         if (rr->ttl <= 0) {
-                dns_cache_remove(c, &rr->key);
+                dns_cache_remove(c, rr->key);
                 return 0;
         }
 
@@ -228,12 +241,12 @@ int dns_cache_put(DnsCache *c, DnsResourceRecord *rr, usec_t timestamp) {
         if (r < 0)
                 return r;
 
-        first = hashmap_get(c->rrsets, &i->rr->key);
+        first = hashmap_get(c->rrsets, i->rr->key);
         if (first) {
                 LIST_PREPEND(rrsets, first, i);
-                assert_se(hashmap_replace(c->rrsets, &first->rr->key, first) >= 0);
+                assert_se(hashmap_replace(c->rrsets, first->rr->key, first) >= 0);
         } else {
-                r = hashmap_put(c->rrsets, &i->rr->key, i);
+                r = hashmap_put(c->rrsets, i->rr->key, i);
                 if (r < 0) {
                         prioq_remove(c->expire, i, &i->expire_prioq_idx);
                         return r;
@@ -245,33 +258,28 @@ int dns_cache_put(DnsCache *c, DnsResourceRecord *rr, usec_t timestamp) {
         return 0;
 }
 
-int dns_cache_put_rrs(DnsCache *c, DnsResourceRecord **rrs, unsigned n_rrs, usec_t timestamp) {
+int dns_cache_put_answer(DnsCache *c, DnsAnswer *answer, usec_t timestamp) {
         unsigned i, added = 0;
         int r;
 
         assert(c);
-
-        if (n_rrs <= 0)
-                return 0;
-
-        assert(rrs);
+        assert(answer);
 
         /* First iteration, delete all matching old RRs, so that we
          * only keep complete rrsets in place. */
-        for (i = 0; i < n_rrs; i++)
-                dns_cache_remove(c, &rrs[i]->key);
+        for (i = 0; i < answer->n_rrs; i++)
+                dns_cache_remove(c, answer->rrs[i]->key);
 
-        dns_cache_make_space(c, n_rrs);
+        dns_cache_make_space(c, answer->n_rrs);
 
         /* Second iteration, add in new RRs */
-        for (added = 0; added < n_rrs; added++) {
+        for (added = 0; added < answer->n_rrs; added++) {
                 if (timestamp <= 0)
                         timestamp = now(CLOCK_MONOTONIC);
 
-                r = dns_cache_put(c, rrs[added], timestamp);
+                r = dns_cache_put(c, answer->rrs[added], timestamp);
                 if (r < 0)
                         goto fail;
-
         }
 
         return 0;
@@ -281,72 +289,60 @@ fail:
          * added, just in case */
 
         for (i = 0; i < added; i++)
-                dns_cache_remove(c, &rrs[i]->key);
+                dns_cache_remove(c, answer->rrs[i]->key);
 
         return r;
 }
 
-DnsCacheItem* dns_cache_lookup(DnsCache *c, DnsResourceKey *key) {
-        assert(c);
-        assert(key);
-
-        return hashmap_get(c->rrsets, key);
-}
-
-DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr) {
-        DnsCacheItem *i;
-
-        assert(c);
-        assert(rr);
-
-        LIST_FOREACH(rrsets, i, hashmap_get(c->rrsets, &rr->key))
-                if (dns_resource_record_equal(i->rr, rr))
-                        return i;
-
-        return NULL;
-}
-
-int dns_cache_lookup_many(DnsCache *c, DnsResourceKey *keys, unsigned n_keys, DnsResourceRecord ***rrs) {
-        DnsResourceRecord **p = NULL;
-        size_t allocated = 0, used = 0;
-        unsigned i;
+int dns_cache_lookup(DnsCache *c, DnsQuestion *q, DnsAnswer **ret) {
+        _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
+        unsigned i, n = 0;
         int r;
 
         assert(c);
-        assert(rrs);
+        assert(q);
+        assert(ret);
 
-        if (n_keys <= 0) {
-                *rrs = NULL;
+        if (q->n_keys <= 0) {
+                *ret = NULL;
                 return 0;
         }
 
-        assert(keys);
-
-        for (i = 0; i < n_keys; i++) {
+        for (i = 0; i < q->n_keys; i++) {
                 DnsCacheItem *j;
 
-                j = dns_cache_lookup(c, &keys[i]);
+                j = hashmap_get(c->rrsets, q->keys[i]);
                 if (!j) {
-                        *rrs = NULL;
-                        r = 0;
-                        goto fail;
+                        /* If one question cannot be answered we need to refresh */
+                        *ret = NULL;
+                        return 0;
                 }
 
-                LIST_FOREACH(rrsets, j, j) {
+                LIST_FOREACH(rrsets, j, j)
+                        n++;
+        }
+
+        assert(n > 0);
+
+        answer = dns_answer_new(n);
+        if (!answer)
+                return -ENOMEM;
 
-                        if (!GREEDY_REALLOC(p, allocated, used+1)) {
-                                r = -ENOMEM;
-                                goto fail;
-                        }
+        for (i = 0; i < q->n_keys; i++) {
+                DnsCacheItem *j;
 
-                        p[used++] = dns_resource_record_ref(j->rr);
+                j = hashmap_get(c->rrsets, q->keys[i]);
+                LIST_FOREACH(rrsets, j, j) {
+                        r = dns_answer_add(answer, j->rr);
+                        if (r < 0)
+                                return r;
                 }
         }
 
-        *rrs = p;
-        return (int) used;
+        assert(n >= answer->n_rrs);
 
-fail:
-        dns_resource_record_freev(p, used);
-        return r;
+        *ret = answer;
+        answer = NULL;
+
+        return n;
 }
diff --git a/src/resolve/resolved-dns-cache.h b/src/resolve/resolved-dns-cache.h
index 8d1cf95342..1ede5bfd81 100644
--- a/src/resolve/resolved-dns-cache.h
+++ b/src/resolve/resolved-dns-cache.h
@@ -36,6 +36,8 @@ typedef struct DnsCache {
 } DnsCache;
 
 #include "resolved-dns-rr.h"
+#include "resolved-dns-question.h"
+#include "resolved-dns-answer.h"
 
 typedef struct DnsCacheItem {
         DnsResourceRecord *rr;
@@ -50,8 +52,6 @@ void dns_cache_prune(DnsCache *c);
 void dns_cache_remove(DnsCache *c, DnsResourceKey *key);
 
 int dns_cache_put(DnsCache *c, DnsResourceRecord *rr, usec_t timestamp);
-int dns_cache_put_rrs(DnsCache *c, DnsResourceRecord **rrs, unsigned n_rrs, usec_t timestamp);
+int dns_cache_put_answer(DnsCache *c, DnsAnswer *answer, usec_t timestamp);
 
-DnsCacheItem* dns_cache_lookup(DnsCache *c, DnsResourceKey *key);
-DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr);
-int dns_cache_lookup_many(DnsCache *c, DnsResourceKey *keys, unsigned n_keys, DnsResourceRecord ***rrs);
+int dns_cache_lookup(DnsCache *c, DnsQuestion *q, DnsAnswer **ret);
diff --git a/src/resolve/resolved-dns-packet.c b/src/resolve/resolved-dns-packet.c
index 02532dc721..527102943a 100644
--- a/src/resolve/resolved-dns-packet.c
+++ b/src/resolve/resolved-dns-packet.c
@@ -96,14 +96,14 @@ static void dns_packet_free(DnsPacket *p) {
 
         assert(p);
 
-        if (p->rrs)
-                dns_resource_record_freev(p->rrs, DNS_PACKET_RRCOUNT(p));
+        dns_question_unref(p->question);
+        dns_answer_unref(p->answer);
 
         while ((s = hashmap_steal_first_key(p->names)))
                 free(s);
         hashmap_free(p->names);
 
-        free(p->data);
+        free(p->_data);
         free(p);
 }
 
@@ -164,21 +164,21 @@ static int dns_packet_extend(DnsPacket *p, size_t add, void **ret, size_t *start
                 if (p->size + add > a)
                         return -EMSGSIZE;
 
-                if (p->data) {
+                if (p->_data) {
                         void *d;
 
-                        d = realloc(p->data, a);
+                        d = realloc(p->_data, a);
                         if (!d)
                                 return -ENOMEM;
 
-                        p->data = d;
+                        p->_data = d;
                 } else {
-                        p->data = malloc(a);
-                        if (!p->data)
+                        p->_data = malloc(a);
+                        if (!p->_data)
                                 return -ENOMEM;
 
-                        memcpy(p->data, (uint8_t*) p + ALIGN(sizeof(DnsPacket)), p->size);
-                        memzero((uint8_t*) p->data + p->size, a - p->size);
+                        memcpy(p->_data, (uint8_t*) p + ALIGN(sizeof(DnsPacket)), p->size);
+                        memzero((uint8_t*) p->_data + p->size, a - p->size);
                 }
 
                 p->allocated = a;
@@ -365,7 +365,7 @@ int dns_packet_append_key(DnsPacket *p, const DnsResourceKey *k, size_t *start)
 
         saved_size = p->size;
 
-        r = dns_packet_append_name(p, k->name, NULL);
+        r = dns_packet_append_name(p, DNS_RESOURCE_KEY_NAME(k), NULL);
         if (r < 0)
                 goto fail;
 
@@ -599,8 +599,10 @@ fail:
         return r;
 }
 
-int dns_packet_read_key(DnsPacket *p, DnsResourceKey *ret, size_t *start) {
-        _cleanup_(dns_resource_key_free) DnsResourceKey k = {};
+int dns_packet_read_key(DnsPacket *p, DnsResourceKey **ret, size_t *start) {
+        _cleanup_free_ char *name = NULL;
+        uint16_t class, type;
+        DnsResourceKey *key;
         size_t saved_rindex;
         int r;
 
@@ -609,20 +611,26 @@ int dns_packet_read_key(DnsPacket *p, DnsResourceKey *ret, size_t *start) {
 
         saved_rindex = p->rindex;
 
-        r = dns_packet_read_name(p, &k.name, NULL);
+        r = dns_packet_read_name(p, &name, NULL);
         if (r < 0)
                 goto fail;
 
-        r = dns_packet_read_uint16(p, &k.type, NULL);
+        r = dns_packet_read_uint16(p, &type, NULL);
         if (r < 0)
                 goto fail;
 
-        r = dns_packet_read_uint16(p, &k.class, NULL);
+        r = dns_packet_read_uint16(p, &class, NULL);
         if (r < 0)
                 goto fail;
 
-        *ret = k;
-        zero(k);
+        key = dns_resource_key_new_consume(class, type, name);
+        if (!key) {
+                r = -ENOMEM;
+                goto fail;
+        }
+
+        name = NULL;
+        *ret = key;
 
         if (start)
                 *start = saved_rindex;
@@ -634,7 +642,8 @@ fail:
 }
 
 int dns_packet_read_rr(DnsPacket *p, DnsResourceRecord **ret, size_t *start) {
-        _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *rr;
+        _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *rr = NULL;
+        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
         size_t saved_rindex, offset;
         uint16_t rdlength;
         const void *d;
@@ -643,16 +652,18 @@ int dns_packet_read_rr(DnsPacket *p, DnsResourceRecord **ret, size_t *start) {
         assert(p);
         assert(ret);
 
-        rr = dns_resource_record_new();
-        if (!rr)
-                return -ENOMEM;
-
         saved_rindex = p->rindex;
 
-        r = dns_packet_read_key(p, &rr->key, NULL);
+        r = dns_packet_read_key(p, &key, NULL);
         if (r < 0)
                 goto fail;
 
+        rr = dns_resource_record_new(key);
+        if (!rr) {
+                r = -ENOMEM;
+                goto fail;
+        }
+
         r = dns_packet_read_uint32(p, &rr->ttl, NULL);
         if (r < 0)
                 goto fail;
@@ -668,7 +679,7 @@ int dns_packet_read_rr(DnsPacket *p, DnsResourceRecord **ret, size_t *start) {
 
         offset = p->rindex;
 
-        switch (rr->key.type) {
+        switch (rr->key->type) {
 
         case DNS_TYPE_PTR:
         case DNS_TYPE_NS:
@@ -733,63 +744,65 @@ fail:
         return r;
 }
 
-int dns_packet_skip_question(DnsPacket *p) {
-        unsigned i, n;
+int dns_packet_extract(DnsPacket *p) {
+        _cleanup_(dns_question_unrefp) DnsQuestion *question = NULL;
+        _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
+        size_t saved_rindex;
+        unsigned n, i;
         int r;
 
-        assert(p);
-
+        saved_rindex = p->rindex;
         dns_packet_rewind(p, DNS_PACKET_HEADER_SIZE);
 
         n = DNS_PACKET_QDCOUNT(p);
-        for (i = 0; i < n; i++) {
-                _cleanup_(dns_resource_key_free) DnsResourceKey key = {};
+        if (n > 0) {
+                question = dns_question_new(n);
+                if (!question) {
+                        r = -ENOMEM;
+                        goto finish;
+                }
 
-                r = dns_packet_read_key(p, &key, NULL);
-                if (r < 0)
-                        return r;
-        }
+                for (i = 0; i < n; i++) {
+                        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
 
-        return 0;
-}
+                        r = dns_packet_read_key(p, &key, NULL);
+                        if (r < 0)
+                                goto finish;
 
-int dns_packet_extract_rrs(DnsPacket *p) {
-        DnsResourceRecord **rrs = NULL;
-        size_t saved_rindex;
-        unsigned n, added = 0;
-        int r;
+                        r = dns_question_add(question, key);
+                        if (r < 0)
+                                goto finish;
+                }
+        }
 
-        if (p->rrs)
-                return (int) DNS_PACKET_RRCOUNT(p);
+        n = DNS_PACKET_RRCOUNT(p);
+        if (n > 0) {
+                answer = dns_answer_new(n);
+                if (!answer) {
+                        r = -ENOMEM;
+                        goto finish;
+                }
 
-        saved_rindex = p->rindex;
+                for (i = 0; i < n; i++) {
+                        _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *rr = NULL;
 
-        r = dns_packet_skip_question(p);
-        if (r < 0)
-                goto finish;
+                        r = dns_packet_read_rr(p, &rr, NULL);
+                        if (r < 0)
+                                goto finish;
 
-        n = DNS_PACKET_RRCOUNT(p);
-        if (n <= 0) {
-                r = 0;
-                goto finish;
+                        r = dns_answer_add(answer, rr);
+                        if (r < 0)
+                                goto finish;
+                }
         }
 
-        rrs = new0(DnsResourceRecord*, n);
-        if (!rrs) {
-                r = -ENOMEM;
-                goto finish;
-        }
+        p->question = question;
+        question = NULL;
 
-        for (added = 0; added < n; added++) {
-                r = dns_packet_read_rr(p, &rrs[added], NULL);
-                if (r < 0) {
-                        dns_resource_record_freev(rrs, added);
-                        goto finish;
-                }
-        }
+        p->answer = answer;
+        answer = NULL;
 
-        p->rrs = rrs;
-        r = (int) n;
+        r = 0;
 
 finish:
         p->rindex = saved_rindex;
diff --git a/src/resolve/resolved-dns-packet.h b/src/resolve/resolved-dns-packet.h
index 4fd2d408ce..ab46b33c48 100644
--- a/src/resolve/resolved-dns-packet.h
+++ b/src/resolve/resolved-dns-packet.h
@@ -30,6 +30,8 @@ typedef struct DnsPacket DnsPacket;
 #include "sparse-endian.h"
 #include "hashmap.h"
 #include "resolved-dns-rr.h"
+#include "resolved-dns-question.h"
+#include "resolved-dns-answer.h"
 
 typedef enum DnsProtocol {
         DNS_PROTOCOL_DNS,
@@ -64,9 +66,12 @@ struct DnsPacket {
         int n_ref;
         DnsProtocol protocol;
         size_t size, allocated, rindex;
-        void *data;
+        void *_data; /* don't access directly, use DNS_PACKET_DATA()! */
         Hashmap *names; /* For name compression */
-        DnsResourceRecord **rrs;
+
+        /* Parsed data */
+        DnsQuestion *question;
+        DnsAnswer *answer;
 
         /* Packet reception meta data */
         int ifindex;
@@ -79,8 +84,8 @@ static inline uint8_t* DNS_PACKET_DATA(DnsPacket *p) {
         if (_unlikely_(!p))
                 return NULL;
 
-        if (p->data)
-                return p->data;
+        if (p->_data)
+                return p->_data;
 
         return ((uint8_t*) p) + ALIGN(sizeof(DnsPacket));
 }
@@ -138,13 +143,13 @@ int dns_packet_read_uint16(DnsPacket *p, uint16_t *ret, size_t *start);
 int dns_packet_read_uint32(DnsPacket *p, uint32_t *ret, size_t *start);
 int dns_packet_read_string(DnsPacket *p, char **ret, size_t *start);
 int dns_packet_read_name(DnsPacket *p, char **ret, size_t *start);
-int dns_packet_read_key(DnsPacket *p, DnsResourceKey *ret, size_t *start);
+int dns_packet_read_key(DnsPacket *p, DnsResourceKey **ret, size_t *start);
 int dns_packet_read_rr(DnsPacket *p, DnsResourceRecord **ret, size_t *start);
 
 void dns_packet_rewind(DnsPacket *p, size_t idx);
 
 int dns_packet_skip_question(DnsPacket *p);
-int dns_packet_extract_rrs(DnsPacket *p);
+int dns_packet_extract(DnsPacket *p);
 
 enum {
         DNS_RCODE_SUCCESS = 0,
diff --git a/src/resolve/resolved-dns-query.c b/src/resolve/resolved-dns-query.c
index ace768b824..80526bbc28 100644
--- a/src/resolve/resolved-dns-query.c
+++ b/src/resolve/resolved-dns-query.c
@@ -31,26 +31,32 @@
 static int dns_query_transaction_go(DnsQueryTransaction *t);
 
 DnsQueryTransaction* dns_query_transaction_free(DnsQueryTransaction *t) {
+        DnsQuery *q;
+
         if (!t)
                 return NULL;
 
         sd_event_source_unref(t->timeout_event_source);
 
+        dns_question_unref(t->question);
         dns_packet_unref(t->sent);
         dns_packet_unref(t->received);
-
-        dns_resource_record_freev(t->cached_rrs, t->n_cached_rrs);
+        dns_answer_unref(t->cached);
 
         sd_event_source_unref(t->tcp_event_source);
         safe_close(t->tcp_fd);
 
-        if (t->query) {
-                LIST_REMOVE(transactions_by_query, t->query->transactions, t);
-                hashmap_remove(t->query->manager->dns_query_transactions, UINT_TO_PTR(t->id));
+        if (t->scope) {
+                LIST_REMOVE(transactions_by_scope, t->scope->transactions, t);
+
+                if (t->id != 0)
+                        hashmap_remove(t->scope->manager->dns_query_transactions, UINT_TO_PTR(t->id));
         }
 
-        if (t->scope)
-                LIST_REMOVE(transactions_by_scope, t->scope->transactions, t);
+        while ((q = set_steal_first(t->queries)))
+                set_remove(q->transactions, t);
+
+        set_free(t->queries);
 
         free(t);
         return NULL;
@@ -58,14 +64,25 @@ DnsQueryTransaction* dns_query_transaction_free(DnsQueryTransaction *t) {
 
 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsQueryTransaction*, dns_query_transaction_free);
 
-static int dns_query_transaction_new(DnsQuery *q, DnsQueryTransaction **ret, DnsScope *s) {
+static void dns_query_transaction_gc(DnsQueryTransaction *t) {
+        assert(t);
+
+        if (t->block_gc > 0)
+                return;
+
+        if (set_isempty(t->queries))
+                dns_query_transaction_free(t);
+}
+
+static int dns_query_transaction_new(DnsQueryTransaction **ret, DnsScope *s, DnsQuestion *q) {
         _cleanup_(dns_query_transaction_freep) DnsQueryTransaction *t = NULL;
         int r;
 
-        assert(q);
+        assert(ret);
         assert(s);
+        assert(q);
 
-        r = hashmap_ensure_allocated(&q->manager->dns_query_transactions, NULL, NULL);
+        r = hashmap_ensure_allocated(&s->manager->dns_query_transactions, NULL, NULL);
         if (r < 0)
                 return r;
 
@@ -74,21 +91,19 @@ static int dns_query_transaction_new(DnsQuery *q, DnsQueryTransaction **ret, Dns
                 return -ENOMEM;
 
         t->tcp_fd = -1;
+        t->question = dns_question_ref(q);
 
         do
                 random_bytes(&t->id, sizeof(t->id));
         while (t->id == 0 ||
-               hashmap_get(q->manager->dns_query_transactions, UINT_TO_PTR(t->id)));
+               hashmap_get(s->manager->dns_query_transactions, UINT_TO_PTR(t->id)));
 
-        r = hashmap_put(q->manager->dns_query_transactions, UINT_TO_PTR(t->id), t);
+        r = hashmap_put(s->manager->dns_query_transactions, UINT_TO_PTR(t->id), t);
         if (r < 0) {
                 t->id = 0;
                 return r;
         }
 
-        LIST_PREPEND(transactions_by_query, q->transactions, t);
-        t->query = q;
-
         LIST_PREPEND(transactions_by_scope, s->transactions, t);
         t->scope = s;
 
@@ -108,7 +123,10 @@ static void dns_query_transaction_stop(DnsQueryTransaction *t) {
         t->tcp_fd = safe_close(t->tcp_fd);
 }
 
-static void dns_query_transaction_complete(DnsQueryTransaction *t, DnsQueryState state) {
+void dns_query_transaction_complete(DnsQueryTransaction *t, DnsQueryState state) {
+        DnsQuery *q;
+        Iterator i;
+
         assert(t);
         assert(!IN_SET(state, DNS_QUERY_NULL, DNS_QUERY_PENDING));
         assert(IN_SET(t->state, DNS_QUERY_NULL, DNS_QUERY_PENDING));
@@ -120,7 +138,15 @@ static void dns_query_transaction_complete(DnsQueryTransaction *t, DnsQueryState
         t->state = state;
 
         dns_query_transaction_stop(t);
-        dns_query_finish(t->query);
+
+        /* 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);
+        t->block_gc--;
+
+        dns_query_transaction_gc(t);
 }
 
 static int on_tcp_ready(sd_event_source *s, int fd, uint32_t revents, void *userdata) {
@@ -215,7 +241,7 @@ static int on_tcp_ready(sd_event_source *s, int fd, uint32_t revents, void *user
 
                         if (t->tcp_read >= sizeof(t->tcp_read_size) + be16toh(t->tcp_read_size)) {
                                 t->received->size = be16toh(t->tcp_read_size);
-                                dns_query_transaction_reply(t, t->received);
+                                dns_query_transaction_process_reply(t, t->received);
                                 return 0;
                         }
                 }
@@ -243,7 +269,7 @@ static int dns_query_transaction_open_tcp(DnsQueryTransaction *t) {
         if (t->tcp_fd < 0)
                 return t->tcp_fd;
 
-        r = sd_event_add_io(t->query->manager->event, &t->tcp_event_source, t->tcp_fd, EPOLLIN|EPOLLOUT, on_tcp_ready, t);
+        r = sd_event_add_io(t->scope->manager->event, &t->tcp_event_source, t->tcp_fd, EPOLLIN|EPOLLOUT, on_tcp_ready, t);
         if (r < 0) {
                 t->tcp_fd = safe_close(t->tcp_fd);
                 return r;
@@ -252,7 +278,7 @@ static int dns_query_transaction_open_tcp(DnsQueryTransaction *t) {
         return 0;
 }
 
-void dns_query_transaction_reply(DnsQueryTransaction *t, DnsPacket *p) {
+void dns_query_transaction_process_reply(DnsQueryTransaction *t, DnsPacket *p) {
         int r;
 
         assert(t);
@@ -305,12 +331,12 @@ void dns_query_transaction_reply(DnsQueryTransaction *t, DnsPacket *p) {
         }
 
         /* Parse and update the cache */
-        r = dns_packet_extract_rrs(p);
+        r = dns_packet_extract(p);
         if (r < 0) {
                 dns_query_transaction_complete(t, DNS_QUERY_INVALID_REPLY);
                 return;
         } else if (r > 0)
-                dns_cache_put_rrs(&t->scope->cache, p->rrs, r, 0);
+                dns_cache_put_answer(&t->scope->cache, p->answer, 0);
 
         if (DNS_PACKET_RCODE(p) == DNS_RCODE_SUCCESS)
                 dns_query_transaction_complete(t, DNS_QUERY_SUCCESS);
@@ -349,14 +375,14 @@ static int dns_query_make_packet(DnsQueryTransaction *t) {
         if (r < 0)
                 return r;
 
-        for (n = 0; n < t->query->n_keys; n++) {
-                r = dns_scope_good_key(t->scope, &t->query->keys[n]);
+        for (n = 0; n < t->question->n_keys; n++) {
+                r = dns_scope_good_key(t->scope, t->question->keys[n]);
                 if (r < 0)
                         return r;
                 if (r == 0)
                         continue;
 
-                r = dns_packet_append_key(p, &t->query->keys[n], NULL);
+                r = dns_packet_append_key(p, t->question->keys[n], NULL);
                 if (r < 0)
                         return r;
 
@@ -389,16 +415,14 @@ static int dns_query_transaction_go(DnsQueryTransaction *t) {
 
         t->n_attempts++;
         t->received = dns_packet_unref(t->received);
-        t->cached_rrs = dns_resource_record_freev(t->cached_rrs, t->n_cached_rrs);
-        t->n_cached_rrs = 0;
+        t->cached = dns_answer_unref(t->cached);
 
         /* First, let's try the cache */
         dns_cache_prune(&t->scope->cache);
-        r = dns_cache_lookup_many(&t->scope->cache, t->query->keys, t->query->n_keys, &t->cached_rrs);
+        r = dns_cache_lookup(&t->scope->cache, t->question, &t->cached);
         if (r < 0)
                 return r;
         if (r > 0) {
-                t->n_cached_rrs = r;
                 dns_query_transaction_complete(t, DNS_QUERY_SUCCESS);
                 return 0;
         }
@@ -431,7 +455,7 @@ static int dns_query_transaction_go(DnsQueryTransaction *t) {
                 return dns_query_transaction_go(t);
         }
 
-        r = sd_event_add_time(t->query->manager->event, &t->timeout_event_source, CLOCK_MONOTONIC, now(CLOCK_MONOTONIC) + TRANSACTION_TIMEOUT_USEC, 0, on_transaction_timeout, t);
+        r = sd_event_add_time(t->scope->manager->event, &t->timeout_event_source, CLOCK_MONOTONIC, now(CLOCK_MONOTONIC) + TRANSACTION_TIMEOUT_USEC, 0, on_transaction_timeout, t);
         if (r < 0)
                 return r;
 
@@ -440,72 +464,61 @@ static int dns_query_transaction_go(DnsQueryTransaction *t) {
 }
 
 DnsQuery *dns_query_free(DnsQuery *q) {
-        unsigned n;
+        DnsQueryTransaction *t;
 
         if (!q)
                 return NULL;
 
         sd_bus_message_unref(q->request);
-        dns_packet_unref(q->received);
 
-        dns_resource_record_freev(q->cached_rrs, q->n_cached_rrs);
+        dns_question_unref(q->question);
+        dns_answer_unref(q->answer);
 
         sd_event_source_unref(q->timeout_event_source);
 
-        while (q->transactions)
-                dns_query_transaction_free(q->transactions);
+        while ((t = set_steal_first(q->transactions))) {
+                set_remove(t->queries, q);
+                dns_query_transaction_gc(t);
+        }
+
+        set_free(q->transactions);
 
         if (q->manager) {
                 LIST_REMOVE(queries, q->manager->dns_queries, q);
                 q->manager->n_dns_queries--;
         }
 
-        for (n = 0; n < q->n_keys; n++)
-                free(q->keys[n].name);
-        free(q->keys);
         free(q);
 
         return NULL;
 }
 
-int dns_query_new(Manager *m, DnsQuery **ret, DnsResourceKey *keys, unsigned n_keys) {
+int dns_query_new(Manager *m, DnsQuery **ret, DnsQuestion *question) {
         _cleanup_(dns_query_freep) DnsQuery *q = NULL;
-        const char *name = NULL;
+        unsigned i;
+        int r;
 
         assert(m);
+        assert(question);
 
-        if (n_keys <= 0 || n_keys >= 65535)
-                return -EINVAL;
+        r = dns_question_is_valid(question);
+        if (r < 0)
+                return r;
 
         if (m->n_dns_queries >= QUERIES_MAX)
                 return -EBUSY;
 
-        assert(keys);
-
         q = new0(DnsQuery, 1);
         if (!q)
                 return -ENOMEM;
 
-        q->keys = new(DnsResourceKey, n_keys);
-        if (!q->keys)
-                return -ENOMEM;
-
-        for (q->n_keys = 0; q->n_keys < n_keys; q->n_keys++) {
-                q->keys[q->n_keys].class = keys[q->n_keys].class;
-                q->keys[q->n_keys].type = keys[q->n_keys].type;
-                q->keys[q->n_keys].name = strdup(keys[q->n_keys].name);
-                if (!q->keys[q->n_keys].name)
-                        return -ENOMEM;
-
-                if (!name)
-                        name = q->keys[q->n_keys].name;
-                else if (!dns_name_equal(name, q->keys[q->n_keys].name))
-                        return -EINVAL;
+        q->question = dns_question_ref(question);
 
+        for (i = 0; i < question->n_keys; i++) {
                 log_debug("Looking up RR for %s %s %s",
-                          strna(dns_class_to_string(keys[q->n_keys].class)),
-                          strna(dns_type_to_string(keys[q->n_keys].type)),
-                          keys[q->n_keys].name);
+                          strna(dns_class_to_string(question->keys[i]->class)),
+                          strna(dns_type_to_string(question->keys[i]->type)),
+                          DNS_RESOURCE_KEY_NAME(question->keys[i]));
         }
 
         LIST_PREPEND(queries, m->dns_queries, q);
@@ -520,12 +533,16 @@ int dns_query_new(Manager *m, DnsQuery **ret, DnsResourceKey *keys, unsigned n_k
 }
 
 static void dns_query_stop(DnsQuery *q) {
+        DnsQueryTransaction *t;
+
         assert(q);
 
         q->timeout_event_source = sd_event_source_unref(q->timeout_event_source);
 
-        while (q->transactions)
-                dns_query_transaction_free(q->transactions);
+        while ((t = set_steal_first(q->transactions))) {
+                set_remove(t->queries, q);
+                dns_query_transaction_gc(t);
+        }
 }
 
 static void dns_query_complete(DnsQuery *q, DnsQueryState state) {
@@ -554,10 +571,53 @@ 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) {
+        DnsQueryTransaction *t;
+        int r;
+
+        assert(q);
+
+        r = set_ensure_allocated(&q->transactions, NULL, NULL);
+        if (r < 0)
+                return r;
+
+        LIST_FOREACH(transactions_by_scope, t, s->transactions)
+                if (dns_question_is_superset(t->question, q->question))
+                        break;
+
+        if (!t) {
+                r = dns_query_transaction_new(&t, s, q->question);
+                if (r < 0)
+                        return r;
+        }
+
+        r = set_ensure_allocated(&t->queries, NULL, NULL);
+        if (r < 0)
+                goto fail;
+
+        r = set_put(t->queries, q);
+        if (r < 0)
+                goto fail;
+
+        r = set_put(q->transactions, t);
+        if (r < 0) {
+                set_remove(t->queries, q);
+                goto fail;
+        }
+
+        return 0;
+
+fail:
+        dns_query_transaction_gc(t);
+        return r;
+}
+
 int dns_query_go(DnsQuery *q) {
         DnsScopeMatch found = DNS_SCOPE_NO;
         DnsScope *s, *first = NULL;
         DnsQueryTransaction *t;
+        const char *name;
+        Iterator i;
         int r;
 
         assert(q);
@@ -565,12 +625,15 @@ int dns_query_go(DnsQuery *q) {
         if (q->state != DNS_QUERY_NULL)
                 return 0;
 
-        assert(q->n_keys > 0);
+        assert(q->question);
+        assert(q->question->n_keys > 0);
+
+        name = DNS_RESOURCE_KEY_NAME(q->question->keys[0]);
 
         LIST_FOREACH(scopes, s, q->manager->dns_scopes) {
                 DnsScopeMatch match;
 
-                match = dns_scope_good_domain(s, q->keys[0].name);
+                match = dns_scope_good_domain(s, name);
                 if (match < 0)
                         return match;
 
@@ -593,42 +656,46 @@ int dns_query_go(DnsQuery *q) {
         if (found == DNS_SCOPE_NO)
                 return -ESRCH;
 
-        r = dns_query_transaction_new(q, NULL, first);
+        r = dns_query_add_transaction(q, first);
         if (r < 0)
                 return r;
 
         LIST_FOREACH(scopes, s, first->scopes_next) {
                 DnsScopeMatch match;
 
-                match = dns_scope_good_domain(s, q->keys[0].name);
+                match = dns_scope_good_domain(s, name);
                 if (match < 0)
                         return match;
 
                 if (match != found)
                         continue;
 
-                r = dns_query_transaction_new(q, NULL, s);
+                r = dns_query_add_transaction(q, s);
                 if (r < 0)
                         return r;
         }
 
-        q->received = dns_packet_unref(q->received);
+        q->answer = dns_answer_unref(q->answer);
+        q->answer_ifindex = 0;
+        q->answer_rcode = 0;
 
         r = sd_event_add_time(q->manager->event, &q->timeout_event_source, CLOCK_MONOTONIC, now(CLOCK_MONOTONIC) + QUERY_TIMEOUT_USEC, 0, on_query_timeout, q);
         if (r < 0)
                 goto fail;
 
         q->state = DNS_QUERY_PENDING;
-        q->block_finish++;
+        q->block_ready++;
 
-        LIST_FOREACH(transactions_by_query, t, q->transactions) {
-                r = dns_query_transaction_go(t);
-                if (r < 0)
-                        goto fail;
+        SET_FOREACH(t, q->transactions, i) {
+                if (t->state == DNS_QUERY_NULL) {
+                        r = dns_query_transaction_go(t);
+                        if (r < 0)
+                                goto fail;
+                }
         }
 
-        q->block_finish--;
-        dns_query_finish(q);
+        q->block_ready--;
+        dns_query_ready(q);
 
         return 1;
 
@@ -637,23 +704,24 @@ fail:
         return r;
 }
 
-void dns_query_finish(DnsQuery *q) {
+void dns_query_ready(DnsQuery *q) {
         DnsQueryTransaction *t;
         DnsQueryState state = DNS_QUERY_NO_SERVERS;
         DnsPacket *received = NULL;
+        Iterator i;
 
         assert(q);
         assert(IN_SET(q->state, DNS_QUERY_NULL, DNS_QUERY_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_finish
+         * after calling this function, unless the block_ready
          * counter was explicitly bumped before doing so. */
 
-        if (q->block_finish > 0)
+        if (q->block_ready > 0)
                 return;
 
-        LIST_FOREACH(transactions_by_query, t, q->transactions) {
+        SET_FOREACH(t, q->transactions, i) {
 
                 /* One of the transactions is still going on, let's wait for it */
                 if (t->state == DNS_QUERY_PENDING || t->state == DNS_QUERY_NULL)
@@ -662,13 +730,15 @@ void dns_query_finish(DnsQuery *q) {
                 /* One of the transactions is successful, let's use
                  * it, and copy its data out */
                 if (t->state == DNS_QUERY_SUCCESS) {
-                        q->received = dns_packet_ref(t->received);
-
-                        /* We simply steal the cached RRs array */
-                        q->cached_rrs = t->cached_rrs;
-                        q->n_cached_rrs = t->n_cached_rrs;
-                        t->cached_rrs = NULL;
-                        t->n_cached_rrs = 0;
+                        if (t->received) {
+                                q->answer = dns_answer_ref(t->received->answer);
+                                q->answer_ifindex = t->received->ifindex;
+                                q->answer_rcode = DNS_PACKET_RCODE(t->received);
+                        } else {
+                                q->answer = dns_answer_ref(t->cached);
+                                q->answer_ifindex = t->scope->link ? t->scope->link->ifindex : 0;
+                                q->answer_rcode = 0;
+                        }
 
                         dns_query_complete(q, DNS_QUERY_SUCCESS);
                         return;
@@ -687,149 +757,36 @@ void dns_query_finish(DnsQuery *q) {
                         state = t->state;
         }
 
-        if (state == DNS_QUERY_FAILURE)
-                q->received = dns_packet_ref(received);
+        if (state == DNS_QUERY_FAILURE) {
+                q->answer = dns_answer_ref(received->answer);
+                q->answer_ifindex = received->ifindex;
+                q->answer_rcode = DNS_PACKET_RCODE(received);
+        }
 
         dns_query_complete(q, state);
 }
 
 int dns_query_cname_redirect(DnsQuery *q, const char *name) {
-        DnsResourceKey *keys;
-        unsigned i;
+        _cleanup_(dns_question_unrefp) DnsQuestion *nq = NULL;
+        int r;
 
         assert(q);
 
-        if (q->n_cname > CNAME_MAX)
+        if (q->n_cname_redirects > CNAME_MAX)
                 return -ELOOP;
 
-        keys = new(DnsResourceKey, q->n_keys);
-        if (!keys)
-                return -ENOMEM;
-
-        for (i = 0; i < q->n_keys; i++) {
-                keys[i].class = q->keys[i].class;
-                keys[i].type = q->keys[i].type;
-                keys[i].name = strdup(name);
-                if (!keys[i].name) {
-
-                        for (; i > 0; i--)
-                                free(keys[i-1].name);
-                        free(keys);
-                        return -ENOMEM;
-                }
-        }
-
-        for (i = 0; i < q->n_keys; i++)
-                free(q->keys[i].name);
-        free(q->keys);
+        r = dns_question_cname_redirect(q->question, name, &nq);
+        if (r < 0)
+                return r;
 
-        q->keys = keys;
+        dns_question_unref(q->question);
+        q->question = nq;
+        nq = NULL;
 
-        q->n_cname++;
+        q->n_cname_redirects++;
 
         dns_query_stop(q);
         q->state = DNS_QUERY_NULL;
 
         return 0;
 }
-
-int dns_query_matches_rr(DnsQuery *q, DnsResourceRecord *rr) {
-        unsigned i;
-        int r;
-
-        assert(q);
-        assert(rr);
-
-        for (i = 0; i < q->n_keys; i++) {
-
-                if (rr->key.class != q->keys[i].class)
-                        continue;
-
-                if (rr->key.type != q->keys[i].type &&
-                    q->keys[i].type != DNS_TYPE_ANY)
-                        continue;
-
-                r = dns_name_equal(rr->key.name, q->keys[i].name);
-                if (r != 0)
-                        return r;
-        }
-
-        return 0;
-}
-
-int dns_query_matches_cname(DnsQuery *q, DnsResourceRecord *rr) {
-        unsigned i;
-        int r;
-
-        assert(q);
-        assert(rr);
-
-        for (i = 0; i < q->n_keys; i++) {
-
-                if (rr->key.class != q->keys[i].class)
-                        continue;
-
-                if (rr->key.type != DNS_TYPE_CNAME)
-                        continue;
-
-                r = dns_name_equal(rr->key.name, q->keys[i].name);
-                if (r != 0)
-                        return r;
-        }
-
-        return 0;
-}
-
-int dns_query_get_rrs(DnsQuery *q, DnsResourceRecord ***rrs) {
-        int r;
-
-        assert(q);
-        assert(rrs);
-
-        if (IN_SET(q->state, DNS_QUERY_NULL, DNS_QUERY_PENDING))
-                return -EBUSY;
-
-        if (q->received) {
-                r = dns_packet_extract_rrs(q->received);
-                if (r < 0)
-                        return r;
-                if (r == 0) {
-                        *rrs = NULL;
-                        return r;
-                }
-
-                *rrs = q->received->rrs;
-                return r;
-        }
-
-        if (q->cached_rrs) {
-                *rrs = q->cached_rrs;
-                return q->n_cached_rrs;
-        }
-
-        return -ESRCH;
-}
-
-int dns_query_get_rcode(DnsQuery *q) {
-        assert(q);
-
-        if (IN_SET(q->state, DNS_QUERY_NULL, DNS_QUERY_PENDING))
-                return -EBUSY;
-
-        if (!q->received)
-                return -ESRCH;
-
-        return DNS_PACKET_RCODE(q->received);
-}
-
-int dns_query_get_ifindex(DnsQuery *q) {
-        assert(q);
-
-        if (IN_SET(q->state, DNS_QUERY_NULL, DNS_QUERY_PENDING))
-                return -EBUSY;
-
-        if (!q->received)
-                return -ESRCH;
-
-        return q->received->ifindex;
-}
diff --git a/src/resolve/resolved-dns-query.h b/src/resolve/resolved-dns-query.h
index 2b814cca42..2756048be5 100644
--- a/src/resolve/resolved-dns-query.h
+++ b/src/resolve/resolved-dns-query.h
@@ -25,6 +25,7 @@
 
 #include "sd-bus.h"
 #include "util.h"
+#include "set.h"
 
 typedef struct DnsQuery DnsQuery;
 typedef struct DnsQueryTransaction DnsQueryTransaction;
@@ -33,6 +34,8 @@ typedef struct DnsQueryTransaction DnsQueryTransaction;
 #include "resolved-dns-scope.h"
 #include "resolved-dns-rr.h"
 #include "resolved-dns-packet.h"
+#include "resolved-dns-question.h"
+#include "resolved-dns-answer.h"
 
 typedef enum DnsQueryState {
         DNS_QUERY_NULL,
@@ -43,50 +46,53 @@ typedef enum DnsQueryState {
         DNS_QUERY_TIMEOUT,
         DNS_QUERY_ATTEMPTS_MAX,
         DNS_QUERY_INVALID_REPLY,
-        DNS_QUERY_RESOURCES
+        DNS_QUERY_RESOURCES,
+        DNS_QUERY_ABORTED,
 } DnsQueryState;
 
 struct DnsQueryTransaction {
-        DnsQuery *query;
         DnsScope *scope;
 
+        DnsQuestion *question;
+
         DnsQueryState state;
         uint16_t id;
 
+        DnsPacket *sent, *received;
+        DnsAnswer *cached;
+
         sd_event_source *timeout_event_source;
         unsigned n_attempts;
 
-        DnsPacket *sent, *received;
-
         /* TCP connection logic */
         int tcp_fd;
         sd_event_source *tcp_event_source;
         size_t tcp_written, tcp_read;
         be16_t tcp_read_size;
 
-        /* Data from cache */
-        DnsResourceRecord **cached_rrs;
-        unsigned n_cached_rrs;
+        /* Queries this transaction is referenced by and that shall by
+         * notified about this specific transaction completing. */
+        Set *queries;
+
+        unsigned block_gc;
 
-        LIST_FIELDS(DnsQueryTransaction, transactions_by_query);
         LIST_FIELDS(DnsQueryTransaction, transactions_by_scope);
 };
 
 struct DnsQuery {
         Manager *manager;
-
-        DnsResourceKey *keys;
-        unsigned n_keys;
+        DnsQuestion *question;
 
         DnsQueryState state;
-        unsigned n_cname;
+        unsigned n_cname_redirects;
 
         sd_event_source *timeout_event_source;
 
         /* Discovered data */
         DnsPacket *received;
-        DnsResourceRecord **cached_rrs;
-        unsigned n_cached_rrs;
+        DnsAnswer *answer;
+        int answer_ifindex;
+        int answer_rcode;
 
         /* Bus client information */
         sd_bus_message *request;
@@ -96,28 +102,24 @@ struct DnsQuery {
 
         /* Completion callback */
         void (*complete)(DnsQuery* q);
-        unsigned block_finish;
+        unsigned block_ready;
+
+        Set *transactions;
 
-        LIST_HEAD(DnsQueryTransaction, transactions);
         LIST_FIELDS(DnsQuery, queries);
 };
 
 DnsQueryTransaction* dns_query_transaction_free(DnsQueryTransaction *t);
-void dns_query_transaction_reply(DnsQueryTransaction *t, DnsPacket *p);
+void dns_query_transaction_complete(DnsQueryTransaction *t, DnsQueryState state);
+
+void dns_query_transaction_process_reply(DnsQueryTransaction *t, DnsPacket *p);
 
-int dns_query_new(Manager *m, DnsQuery **q, DnsResourceKey *keys, unsigned n_keys);
+int dns_query_new(Manager *m, DnsQuery **q, DnsQuestion *question);
 DnsQuery *dns_query_free(DnsQuery *q);
 
 int dns_query_go(DnsQuery *q);
-int dns_query_cname_redirect(DnsQuery *q, const char *name);
-void dns_query_finish(DnsQuery *q);
-
-int dns_query_matches_rr(DnsQuery *q, DnsResourceRecord *rr);
-int dns_query_matches_cname(DnsQuery *q, DnsResourceRecord *rr);
+void dns_query_ready(DnsQuery *q);
 
-/* What we found */
-int dns_query_get_rrs(DnsQuery *q, DnsResourceRecord *** rrs);
-int dns_query_get_rcode(DnsQuery *q);
-int dns_query_get_ifindex(DnsQuery *q);
+int dns_query_cname_redirect(DnsQuery *q, const char *name);
 
 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsQuery*, dns_query_free);
diff --git a/src/resolve/resolved-dns-question.c b/src/resolve/resolved-dns-question.c
new file mode 100644
index 0000000000..026a67d7b3
--- /dev/null
+++ b/src/resolve/resolved-dns-question.c
@@ -0,0 +1,226 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+/***
+  This file is part of systemd.
+
+  Copyright 2014 Lennart Poettering
+
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd is distributed in the hope that it will be useful, but
+  WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include "resolved-dns-question.h"
+#include "resolved-dns-domain.h"
+
+DnsQuestion *dns_question_new(unsigned n) {
+        DnsQuestion *q;
+
+        assert(n > 0);
+
+        q = malloc0(offsetof(DnsQuestion, keys) + sizeof(DnsResourceKey*) * n);
+        if (!q)
+                return NULL;
+
+        q->n_ref = 1;
+        q->n_allocated = n;
+
+        return q;
+}
+
+DnsQuestion *dns_question_ref(DnsQuestion *q) {
+        if (!q)
+                return NULL;
+
+        assert(q->n_ref > 0);
+        q->n_ref++;
+        return q;
+}
+
+DnsQuestion *dns_question_unref(DnsQuestion *q) {
+        if (!q)
+                return NULL;
+
+        assert(q->n_ref > 0);
+
+        if (q->n_ref == 1) {
+                unsigned i;
+
+                for (i = 0; i < q->n_keys; i++)
+                        dns_resource_key_unref(q->keys[i]);
+                free(q);
+        } else
+                q->n_ref--;
+
+        return  NULL;
+}
+
+int dns_question_add(DnsQuestion *q, DnsResourceKey *key) {
+        assert(q);
+        assert(key);
+
+        if (q->n_keys >= q->n_allocated)
+                return -ENOSPC;
+
+        q->keys[q->n_keys++] = dns_resource_key_ref(key);
+        return 0;
+}
+
+int dns_question_matches_rr(DnsQuestion *q, DnsResourceRecord *rr) {
+        unsigned i;
+        int r;
+
+        assert(q);
+        assert(rr);
+
+        for (i = 0; i < q->n_keys; i++) {
+                r = dns_resource_key_match_rr(q->keys[i], rr);
+                if (r != 0)
+                        return r;
+        }
+
+        return 0;
+}
+
+int dns_question_matches_cname(DnsQuestion *q, DnsResourceRecord *rr) {
+        unsigned i;
+        int r;
+
+        assert(q);
+        assert(rr);
+
+        for (i = 0; i < q->n_keys; i++) {
+                r = dns_resource_key_match_cname(q->keys[i], rr);
+                if (r != 0)
+                        return r;
+        }
+
+        return 1;
+}
+
+int dns_question_is_valid(DnsQuestion *q) {
+        const char *name;
+        unsigned i;
+        int r;
+
+        assert(q);
+
+        if (q->n_keys <= 0)
+                return 0;
+
+        if (q->n_keys > 65535)
+                return 0;
+
+        name = DNS_RESOURCE_KEY_NAME(q->keys[0]);
+        if (!name)
+                return 0;
+
+        /* Check that all keys in this question bear the same name */
+        for (i = 1; i < q->n_keys; i++) {
+                r = dns_name_equal(DNS_RESOURCE_KEY_NAME(q->keys[i]), name);
+                if (r <= 0)
+                        return r;
+        }
+
+        return 1;
+}
+
+int dns_question_is_superset(DnsQuestion *q, DnsQuestion *other) {
+        unsigned j;
+        int r;
+
+        assert(q);
+        assert(other);
+
+        /* Checks if all keys in "other" are also contained in "q" */
+
+        for (j = 0; j < other->n_keys; j++) {
+                DnsResourceKey *b = other->keys[j];
+                bool found = false;
+                unsigned i;
+
+                for (i = 0; i < q->n_keys; i++) {
+                        DnsResourceKey *a = q->keys[i];
+
+                        r = dns_name_equal(DNS_RESOURCE_KEY_NAME(a), DNS_RESOURCE_KEY_NAME(b));
+                        if (r < 0)
+                                return r;
+
+                        if (r == 0)
+                                continue;
+
+                        if (a->class != b->class && a->class != DNS_CLASS_ANY)
+                                continue;
+
+                        if (a->type != b->type && a->type != DNS_TYPE_ANY)
+                                continue;
+
+                        found = true;
+                        break;
+                }
+
+                if (!found)
+                        return 0;
+        }
+
+        return 1;
+}
+
+int dns_question_cname_redirect(DnsQuestion *q, const char *name, DnsQuestion **ret) {
+        _cleanup_(dns_question_unrefp) DnsQuestion *n = NULL;
+        bool same = true;
+        unsigned i;
+        int r;
+
+        assert(q);
+        assert(name);
+        assert(ret);
+
+        for (i = 0; i < q->n_keys; i++) {
+                r = dns_name_equal(DNS_RESOURCE_KEY_NAME(q->keys[i]), name);
+                if (r < 0)
+                        return r;
+
+                if (r == 0) {
+                        same = false;
+                        break;
+                }
+        }
+
+        if (same) {
+                /* Shortcut, the names are already right */
+                *ret = dns_question_ref(q);
+                return 0;
+        }
+
+        n = dns_question_new(q->n_keys);
+        if (!n)
+                return -ENOMEM;
+
+        /* Create a new question, and patch in the new name */
+        for (n->n_keys = 0; n->n_keys < q->n_keys; n->n_keys++) {
+                _cleanup_(dns_resource_key_unrefp) DnsResourceKey *k = NULL;
+
+                k = dns_resource_key_new(q->keys[i]->class, q->keys[i]->type, name);
+                if (!k)
+                        return -ENOMEM;
+
+                r = dns_question_add(n, k);
+                if (r < 0)
+                        return r;
+        }
+
+        *ret = n;
+        n = NULL;
+
+        return 1;
+}
diff --git a/src/resolve/resolved-dns-question.h b/src/resolve/resolved-dns-question.h
new file mode 100644
index 0000000000..7da627fdca
--- /dev/null
+++ b/src/resolve/resolved-dns-question.h
@@ -0,0 +1,49 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+#pragma once
+
+/***
+  This file is part of systemd.
+
+  Copyright 2014 Lennart Poettering
+
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd is distributed in the hope that it will be useful, but
+  WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+typedef struct DnsQuestion DnsQuestion;
+
+#include "resolved-dns-rr.h"
+
+/* A simple array of resources keys */
+
+struct DnsQuestion {
+        unsigned n_ref;
+        unsigned n_keys, n_allocated;
+        DnsResourceKey* keys[0];
+};
+
+DnsQuestion *dns_question_new(unsigned n);
+DnsQuestion *dns_question_ref(DnsQuestion *q);
+DnsQuestion *dns_question_unref(DnsQuestion *q);
+
+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_is_valid(DnsQuestion *q);
+int dns_question_is_superset(DnsQuestion *q, DnsQuestion *other);
+
+int dns_question_cname_redirect(DnsQuestion *q, const char *name, DnsQuestion **ret);
+
+DEFINE_TRIVIAL_CLEANUP_FUNC(DnsQuestion*, dns_question_unref);
diff --git a/src/resolve/resolved-dns-rr.c b/src/resolve/resolved-dns-rr.c
index c8f7cf4a4c..c9b564b544 100644
--- a/src/resolve/resolved-dns-rr.c
+++ b/src/resolve/resolved-dns-rr.c
@@ -22,19 +22,116 @@
 #include "resolved-dns-domain.h"
 #include "resolved-dns-rr.h"
 
-void dns_resource_key_free(DnsResourceKey *key) {
-        if (!key)
-                return;
+DnsResourceKey* dns_resource_key_new(uint16_t class, uint16_t type, const char *name) {
+        DnsResourceKey *k;
+        size_t l;
 
-        free(key->name);
-        zero(*key);
+        assert(name);
+
+        l = strlen(name);
+        k = malloc0(sizeof(DnsResourceKey) + l + 1);
+        if (!k)
+                return NULL;
+
+        k->n_ref = 1;
+        k->class = class;
+        k->type = type;
+
+        strcpy((char*) k + sizeof(DnsResourceKey), name);
+
+        return k;
+}
+
+DnsResourceKey* dns_resource_key_new_consume(uint16_t class, uint16_t type, char *name) {
+        DnsResourceKey *k;
+
+        assert(name);
+
+        k = new0(DnsResourceKey, 1);
+        if (!k)
+                return NULL;
+
+        k->n_ref = 1;
+        k->class = class;
+        k->type = type;
+        k->_name = name;
+
+        return k;
+}
+
+DnsResourceKey* dns_resource_key_ref(DnsResourceKey *k) {
+
+        if (!k)
+                return NULL;
+
+        assert(k->n_ref > 0);
+        k->n_ref++;
+
+        return k;
+}
+
+DnsResourceKey* dns_resource_key_unref(DnsResourceKey *k) {
+        if (!k)
+                return NULL;
+
+        assert(k->n_ref > 0);
+
+        if (k->n_ref == 1) {
+                free(k->_name);
+                free(k);
+        } else
+                k->n_ref--;
+
+        return NULL;
+}
+
+int dns_resource_key_equal(const DnsResourceKey *a, const DnsResourceKey *b) {
+        int r;
+
+        r = dns_name_equal(DNS_RESOURCE_KEY_NAME(a), DNS_RESOURCE_KEY_NAME(b));
+        if (r <= 0)
+                return r;
+
+        if (a->class != b->class)
+                return 0;
+
+        if (a->type != b->type)
+                return 0;
+
+        return 1;
+}
+
+int dns_resource_key_match_rr(const DnsResourceKey *key, const DnsResourceRecord *rr) {
+        assert(key);
+        assert(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));
+}
+
+int dns_resource_key_match_cname(const DnsResourceKey *key, const DnsResourceRecord *rr) {
+        assert(key);
+        assert(rr);
+
+        if (rr->key->class != key->class && key->class != DNS_CLASS_ANY)
+                return 0;
+
+        if (rr->key->type != DNS_TYPE_CNAME)
+                return 0;
+
+        return dns_name_equal(DNS_RESOURCE_KEY_NAME(rr->key), DNS_RESOURCE_KEY_NAME(key));
 }
 
 unsigned long dns_resource_key_hash_func(const void *i, const uint8_t hash_key[HASH_KEY_SIZE]) {
         const DnsResourceKey *k = i;
         unsigned long ul;
 
-        ul = dns_name_hash_func(k->name, hash_key);
+        ul = dns_name_hash_func(DNS_RESOURCE_KEY_NAME(k), hash_key);
         ul = ul * hash_key[0] + ul + k->class;
         ul = ul * hash_key[1] + ul + k->type;
 
@@ -45,7 +142,7 @@ int dns_resource_key_compare_func(const void *a, const void *b) {
         const DnsResourceKey *x = a, *y = b;
         int ret;
 
-        ret = dns_name_compare_func(x->name, y->name);
+        ret = dns_name_compare_func(DNS_RESOURCE_KEY_NAME(x), DNS_RESOURCE_KEY_NAME(y));
         if (ret != 0)
                 return ret;
 
@@ -62,7 +159,7 @@ int dns_resource_key_compare_func(const void *a, const void *b) {
         return 0;
 }
 
-DnsResourceRecord* dns_resource_record_new(void) {
+DnsResourceRecord* dns_resource_record_new(DnsResourceKey *key) {
         DnsResourceRecord *rr;
 
         rr = new0(DnsResourceRecord, 1);
@@ -70,6 +167,8 @@ DnsResourceRecord* dns_resource_record_new(void) {
                 return NULL;
 
         rr->n_ref = 1;
+        rr->key = dns_resource_key_ref(key);
+
         return rr;
 }
 
@@ -94,29 +193,20 @@ DnsResourceRecord* dns_resource_record_unref(DnsResourceRecord *rr) {
                 return NULL;
         }
 
-        if (IN_SET(rr->key.type, DNS_TYPE_PTR, DNS_TYPE_NS, DNS_TYPE_CNAME))
-                free(rr->ptr.name);
-        else if (rr->key.type == DNS_TYPE_HINFO) {
-                free(rr->hinfo.cpu);
-                free(rr->hinfo.os);
-        } else if (!IN_SET(rr->key.type, DNS_TYPE_A, DNS_TYPE_AAAA))
-                free(rr->generic.data);
-
-        dns_resource_key_free(&rr->key);
-        free(rr);
-
-        return NULL;
-}
+        if (rr->key) {
+                if (IN_SET(rr->key->type, DNS_TYPE_PTR, DNS_TYPE_NS, DNS_TYPE_CNAME))
+                        free(rr->ptr.name);
+                else if (rr->key->type == DNS_TYPE_HINFO) {
+                        free(rr->hinfo.cpu);
+                        free(rr->hinfo.os);
+                } else if (!IN_SET(rr->key->type, DNS_TYPE_A, DNS_TYPE_AAAA))
+                        free(rr->generic.data);
 
-DnsResourceRecord** dns_resource_record_freev(DnsResourceRecord **rrs, unsigned n) {
-        unsigned i;
-
-        assert(n == 0 || rrs);
+                dns_resource_key_unref(rr->key);
+        }
 
-        for (i = 0; i < n; i++)
-                dns_resource_record_unref(rrs[i]);
+        free(rr);
 
-        free(rrs);
         return NULL;
 }
 
@@ -126,24 +216,18 @@ int dns_resource_record_equal(const DnsResourceRecord *a, const DnsResourceRecor
         assert(a);
         assert(b);
 
-        r = dns_name_equal(a->key.name, b->key.name);
+        r = dns_resource_key_equal(a->key, b->key);
         if (r <= 0)
                 return r;
 
-        if (a->key.class != b->key.class)
-                return 0;
-
-        if (a->key.type != b->key.type)
-                return 0;
-
-        if (IN_SET(a->key.type, DNS_TYPE_PTR, DNS_TYPE_NS, DNS_TYPE_CNAME))
+        if (IN_SET(a->key->type, DNS_TYPE_PTR, DNS_TYPE_NS, DNS_TYPE_CNAME))
                 return dns_name_equal(a->ptr.name, b->ptr.name);
-        else if (a->key.type == DNS_TYPE_HINFO)
+        else if (a->key->type == DNS_TYPE_HINFO)
                 return strcasecmp(a->hinfo.cpu, b->hinfo.cpu) == 0 &&
                        strcasecmp(a->hinfo.os, b->hinfo.os) == 0;
-        else if (a->key.type == DNS_TYPE_A)
+        else if (a->key->type == DNS_TYPE_A)
                 return memcmp(&a->a.in_addr, &b->a.in_addr, sizeof(struct in_addr)) == 0;
-        else if (a->key.type == DNS_TYPE_AAAA)
+        else if (a->key->type == DNS_TYPE_AAAA)
                 return memcmp(&a->aaaa.in6_addr, &b->aaaa.in6_addr, sizeof(struct in6_addr)) == 0;
         else
                 return a->generic.size == b->generic.size &&
diff --git a/src/resolve/resolved-dns-rr.h b/src/resolve/resolved-dns-rr.h
index 5d9f3e5a24..3ab01fac8d 100644
--- a/src/resolve/resolved-dns-rr.h
+++ b/src/resolve/resolved-dns-rr.h
@@ -62,17 +62,15 @@ enum {
 };
 
 struct DnsResourceKey {
-        uint16_t class;
-        uint16_t type;
-        char *name;
+        unsigned n_ref;
+        uint16_t class, type;
+        char *_name; /* don't access directy, use DNS_RESOURCE_KEY_NAME()! */
 };
 
 struct DnsResourceRecord {
         unsigned n_ref;
-
-        DnsResourceKey key;
+        DnsResourceKey *key;
         uint32_t ttl;
-
         union {
                 struct {
                         void *data;
@@ -109,20 +107,32 @@ struct DnsResourceRecord {
         };
 };
 
-void dns_resource_key_free(DnsResourceKey *key);
+static inline const char* DNS_RESOURCE_KEY_NAME(const DnsResourceKey *key) {
+        if (_unlikely_(!key))
+                return NULL;
+
+        if (key->_name)
+                return key->_name;
+
+        return (char*) key + sizeof(DnsResourceKey);
+}
 
+DnsResourceKey* dns_resource_key_new(uint16_t class, uint16_t type, const 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);
 unsigned long dns_resource_key_hash_func(const void *i, const uint8_t hash_key[HASH_KEY_SIZE]);
 int dns_resource_key_compare_func(const void *a, const void *b);
+DEFINE_TRIVIAL_CLEANUP_FUNC(DnsResourceKey*, dns_resource_key_unref);
 
-DnsResourceRecord* dns_resource_record_new(void);
+DnsResourceRecord* dns_resource_record_new(DnsResourceKey *key);
 DnsResourceRecord* dns_resource_record_ref(DnsResourceRecord *rr);
 DnsResourceRecord* dns_resource_record_unref(DnsResourceRecord *rr);
-
-DnsResourceRecord** dns_resource_record_freev(DnsResourceRecord **rrs, unsigned n);
-
 int dns_resource_record_equal(const DnsResourceRecord *a, const DnsResourceRecord *b);
+DEFINE_TRIVIAL_CLEANUP_FUNC(DnsResourceRecord*, dns_resource_record_unref);
 
 const char *dns_type_to_string(uint16_t type);
 const char *dns_class_to_string(uint16_t type);
-
-DEFINE_TRIVIAL_CLEANUP_FUNC(DnsResourceRecord*, dns_resource_record_unref);
diff --git a/src/resolve/resolved-dns-scope.c b/src/resolve/resolved-dns-scope.c
index 190c5f41af..96a2ff7fae 100644
--- a/src/resolve/resolved-dns-scope.c
+++ b/src/resolve/resolved-dns-scope.c
@@ -55,6 +55,8 @@ int dns_scope_new(Manager *m, DnsScope **ret, Link *l, DnsProtocol protocol, int
 }
 
 DnsScope* dns_scope_free(DnsScope *s) {
+        DnsQueryTransaction *t;
+
         if (!s)
                 return NULL;
 
@@ -62,13 +64,16 @@ DnsScope* dns_scope_free(DnsScope *s) {
 
         dns_scope_llmnr_membership(s, false);
 
-        while (s->transactions) {
-                DnsQuery *q;
+        while ((t = s->transactions)) {
+
+                /* Abort the transaction, but make sure it is not
+                 * freed while we still look at it */
 
-                q = s->transactions->query;
-                dns_query_transaction_free(s->transactions);
+                t->block_gc++;
+                dns_query_transaction_complete(t, DNS_QUERY_ABORTED);
+                t->block_gc--;
 
-                dns_query_finish(q);
+                dns_query_transaction_free(t);
         }
 
         dns_cache_flush(&s->cache);
@@ -228,37 +233,37 @@ DnsScopeMatch dns_scope_good_domain(DnsScope *s, const char *domain) {
         assert(domain);
 
         STRV_FOREACH(i, s->domains)
-                if (dns_name_endswith(domain, *i))
+                if (dns_name_endswith(domain, *i) > 0)
                         return DNS_SCOPE_YES;
 
-        if (dns_name_root(domain))
+        if (dns_name_root(domain) != 0)
                 return DNS_SCOPE_NO;
 
         if (is_localhost(domain))
                 return DNS_SCOPE_NO;
 
         if (s->protocol == DNS_PROTOCOL_DNS) {
-                if (dns_name_endswith(domain, "254.169.in-addr.arpa") ||
-                    dns_name_endswith(domain, "0.8.e.f.ip6.arpa") ||
-                    dns_name_single_label(domain))
-                        return DNS_SCOPE_NO;
+                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)
+                        return DNS_SCOPE_MAYBE;
 
-                return DNS_SCOPE_MAYBE;
+                return DNS_SCOPE_NO;
         }
 
         if (s->protocol == DNS_PROTOCOL_MDNS) {
-                if (dns_name_endswith(domain, "254.169.in-addr.arpa") ||
-                    dns_name_endswith(domain, "0.8.e.f.ip6.arpa") ||
-                    dns_name_endswith(domain, "local"))
+                if (dns_name_endswith(domain, "254.169.in-addr.arpa") > 0 ||
+                    dns_name_endswith(domain, "0.8.e.f.ip6.arpa") > 0 ||
+                    (dns_name_endswith(domain, "local") > 0 && dns_name_equal(domain, "local") == 0))
                         return DNS_SCOPE_MAYBE;
 
                 return DNS_SCOPE_NO;
         }
 
         if (s->protocol == DNS_PROTOCOL_LLMNR) {
-                if (dns_name_endswith(domain, "254.169.in-addr.arpa") ||
-                    dns_name_endswith(domain, "0.8.e.f.ip6.arpa") ||
-                    dns_name_single_label(domain))
+                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)
                         return DNS_SCOPE_MAYBE;
 
                 return DNS_SCOPE_NO;
diff --git a/src/resolve/resolved-manager.c b/src/resolve/resolved-manager.c
index 96728433b3..19ea678de0 100644
--- a/src/resolve/resolved-manager.c
+++ b/src/resolve/resolved-manager.c
@@ -395,7 +395,7 @@ int manager_new(Manager **ret) {
 
         m->use_llmnr = true;
 
-        r = parse_dns_server_string(m, /* "172.31.0.125 2001:4860:4860::8888 2001:4860:4860::8889" */ DNS_SERVERS);
+        r = parse_dns_server_string(m, DNS_SERVERS);
         if (r < 0)
                 return r;
 
@@ -669,7 +669,7 @@ static int on_dns_packet(sd_event_source *s, int fd, uint32_t revents, void *use
                 if (!t)
                         return 0;
 
-                dns_query_transaction_reply(t, p);
+                dns_query_transaction_process_reply(t, p);
         } else
                 log_debug("Invalid reply packet.");
 
@@ -954,7 +954,7 @@ static int on_llmnr_packet(sd_event_source *s, int fd, uint32_t revents, void *u
                 if (!t)
                         return 0;
 
-                dns_query_transaction_reply(t, p);
+                dns_query_transaction_process_reply(t, p);
         }
 
         return 0;