resolved: add DNS cache

13 files changed, 857 insertions, 132 deletions

diff --git a/Makefile.am b/Makefile.am
index 0b9491ade0..88f468c9de 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -4658,7 +4658,9 @@ systemd_resolved_SOURCES = \
 	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-rr.c \
+	src/resolve/resolved-dns-cache.h \
+	src/resolve/resolved-dns-cache.c
 
 nodist_systemd_resolved_SOURCES = \
 	src/resolve/resolved-gperf.c
diff --git a/src/resolve/resolved-bus.c b/src/resolve/resolved-bus.c
index acdfd52403..642332790c 100644
--- a/src/resolve/resolved-bus.c
+++ b/src/resolve/resolved-bus.c
@@ -59,18 +59,21 @@ 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;
 
-                assert(q->received);
+                rcode = dns_query_get_rcode(q);
+                if (rcode < 0)
+                        return rcode;
 
-                if (DNS_PACKET_RCODE(q->received) == DNS_RCODE_NXDOMAIN)
+                if (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(DNS_PACKET_RCODE(q->received));
+                        rc = dns_rcode_to_string(rcode);
                         if (!rc) {
-                                sprintf(p, "%i", DNS_PACKET_RCODE(q->received));
+                                sprintf(p, "%i", rcode);
                                 rc = p;
                         }
 
@@ -129,9 +132,10 @@ 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;
-        unsigned i, n, added = 0;
-        size_t answer_rindex;
-        int r;
+        DnsResourceRecord **rrs;
+        unsigned added = 0;
+        int ifindex;
+        int r, n, i;
 
         assert(q);
 
@@ -140,13 +144,11 @@ static void bus_method_resolve_hostname_complete(DnsQuery *q) {
                 goto finish;
         }
 
-        assert(q->received);
-
-        r = dns_packet_skip_question(q->received);
-        if (r < 0)
+        n = dns_query_get_rrs(q, &rrs);
+        if (n < 0) {
+                r = n;
                 goto parse_fail;
-
-        answer_rindex = q->received->rindex;
+        }
 
         r = sd_bus_message_new_method_return(q->request, &reply);
         if (r < 0)
@@ -156,38 +158,32 @@ static void bus_method_resolve_hostname_complete(DnsQuery *q) {
         if (r < 0)
                 goto finish;
 
-        n = DNS_PACKET_ANCOUNT(q->received) +
-            DNS_PACKET_NSCOUNT(q->received) +
-            DNS_PACKET_ARCOUNT(q->received);
+        ifindex = dns_query_get_ifindex(q);
+        if (ifindex < 0)
+                ifindex = 0;
 
         for (i = 0; i < n; i++) {
-                _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *rr = NULL;
-
-                r = dns_packet_read_rr(q->received, &rr, NULL);
-                if (r < 0)
-                        goto parse_fail;
-
-                r = dns_query_matches_rr(q, rr);
+                r = dns_query_matches_rr(q, 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, rr);
+                        r = dns_query_matches_cname(q, rrs[i]);
                         if (r < 0)
                                 goto parse_fail;
                         if (r > 0)
-                                cname = dns_resource_record_ref(rr);
+                                cname = dns_resource_record_ref(rrs[i]);
 
                         continue;
                 }
 
-                r = append_address(reply, rr, q->received->ifindex);
+                r = append_address(reply, rrs[i], ifindex);
                 if (r < 0)
                         goto finish;
 
                 if (!canonical)
-                        canonical = dns_resource_record_ref(rr);
+                        canonical = dns_resource_record_ref(rrs[i]);
 
                 added ++;
         }
@@ -200,7 +196,7 @@ static void bus_method_resolve_hostname_complete(DnsQuery *q) {
 
                 /* This has a cname? Then update the query with the
                  * new cname. */
-                r = dns_query_follow_cname(q, cname->cname.name);
+                r = dns_query_cname_redirect(q, cname->cname.name);
                 if (r < 0) {
                         if (r == -ELOOP)
                                 r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_CNAME_LOOP, "CNAME loop on '%s'", q->request_hostname);
@@ -212,26 +208,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 */
-                dns_packet_rewind(q->received, answer_rindex);
                 for (i = 0; i < n; i++) {
-                        _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *rr = NULL;
-
-                        r = dns_packet_read_rr(q->received, &rr, NULL);
-                        if (r < 0)
-                                goto parse_fail;
-
-                        r = dns_query_matches_rr(q, rr);
+                        r = dns_query_matches_rr(q, rrs[i]);
                         if (r < 0)
                                 goto parse_fail;
                         if (r == 0)
                                 continue;
 
-                        r = append_address(reply, rr, q->received->ifindex);
+                        r = append_address(reply, rrs[i], ifindex);
                         if (r < 0)
                                 goto finish;
 
                         if (!canonical)
-                                canonical = dns_resource_record_ref(rr);
+                                canonical = dns_resource_record_ref(rrs[i]);
 
                         added++;
                 }
@@ -239,7 +228,7 @@ static void bus_method_resolve_hostname_complete(DnsQuery *q) {
                 /* If we didn't find anything, then let's restart the
                  * query, this time with the cname */
                 if (added <= 0) {
-                        r = dns_query_start(q);
+                        r = dns_query_go(q);
                         if (r == -ESRCH) {
                                 r = sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_NAME_SERVERS, "No appropriate name servers or networks for name found");
                                 goto finish;
@@ -321,7 +310,7 @@ static int bus_method_resolve_hostname(sd_bus *bus, sd_bus_message *message, voi
         q->request_hostname = hostname;
         q->complete = bus_method_resolve_hostname_complete;
 
-        r = dns_query_start(q);
+        r = dns_query_go(q);
         if (r < 0) {
                 dns_query_free(q);
 
@@ -336,8 +325,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;
-        unsigned i, n, added = 0;
-        int r;
+        DnsResourceRecord **rrs;
+        unsigned added = 0;
+        int r, n, i;
 
         assert(q);
 
@@ -346,11 +336,11 @@ static void bus_method_resolve_address_complete(DnsQuery *q) {
                 goto finish;
         }
 
-        assert(q->received);
-
-        r = dns_packet_skip_question(q->received);
-        if (r < 0)
+        n = dns_query_get_rrs(q, &rrs);
+        if (n < 0) {
+                r = n;
                 goto parse_fail;
+        }
 
         r = sd_bus_message_new_method_return(q->request, &reply);
         if (r < 0)
@@ -360,24 +350,14 @@ static void bus_method_resolve_address_complete(DnsQuery *q) {
         if (r < 0)
                 goto finish;
 
-        n = DNS_PACKET_ANCOUNT(q->received) +
-            DNS_PACKET_NSCOUNT(q->received) +
-            DNS_PACKET_ARCOUNT(q->received);
-
         for (i = 0; i < n; i++) {
-                _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *rr = NULL;
-
-                r = dns_packet_read_rr(q->received, &rr, NULL);
-                if (r < 0)
-                        goto parse_fail;
-
-                r = dns_query_matches_rr(q, rr);
+                r = dns_query_matches_rr(q, rrs[i]);
                 if (r < 0)
                         goto parse_fail;
                 if (r == 0)
                         continue;
 
-                r = sd_bus_message_append(reply, "s", rr->ptr.name);
+                r = sd_bus_message_append(reply, "s", rrs[i]->ptr.name);
                 if (r < 0)
                         goto finish;
 
@@ -412,6 +392,7 @@ 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_free_ char *ip = NULL;
         Manager *m = userdata;
         uint8_t family;
         const void *d;
@@ -460,7 +441,7 @@ static int bus_method_resolve_address(sd_bus *bus, sd_bus_message *message, void
         memcpy(&q->request_address, d, sz);
         q->complete = bus_method_resolve_address_complete;
 
-        r = dns_query_start(q);
+        r = dns_query_go(q);
         if (r < 0) {
                 dns_query_free(q);
                 return r;
diff --git a/src/resolve/resolved-dns-cache.c b/src/resolve/resolved-dns-cache.c
new file mode 100644
index 0000000000..7093b5a357
--- /dev/null
+++ b/src/resolve/resolved-dns-cache.c
@@ -0,0 +1,341 @@
+/*-*- 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-cache.h"
+
+#define CACHE_MAX 1024
+#define CACHE_TTL_MAX_USEC (10 * USEC_PER_MINUTE)
+
+static void dns_cache_item_free(DnsCacheItem *i) {
+        if (!i)
+                return;
+
+        dns_resource_record_unref(i->rr);
+        free(i);
+}
+
+DEFINE_TRIVIAL_CLEANUP_FUNC(DnsCacheItem*, dns_cache_item_free);
+
+static void dns_cache_item_remove_and_free(DnsCache *c, DnsCacheItem *i) {
+        DnsCacheItem *first;
+
+        assert(c);
+
+        if (!i)
+                return;
+
+        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);
+        else
+                hashmap_remove(c->rrsets, &i->rr->key);
+
+        prioq_remove(c->expire, i, &i->expire_prioq_idx);
+
+        dns_cache_item_free(i);
+}
+
+void dns_cache_flush(DnsCache *c) {
+        DnsCacheItem *i;
+
+        assert(c);
+
+        while ((i = hashmap_first(c->rrsets)))
+                dns_cache_item_remove_and_free(c, i);
+
+        assert(hashmap_size(c->rrsets) == 0);
+        assert(prioq_size(c->expire) == 0);
+
+        hashmap_free(c->rrsets);
+        c->rrsets = NULL;
+
+        prioq_free(c->expire);
+        c->expire = NULL;
+}
+
+void dns_cache_remove(DnsCache *c, DnsResourceKey *key) {
+        DnsCacheItem *i;
+
+        assert(c);
+        assert(key);
+
+        while ((i = hashmap_get(c->rrsets, &key)))
+                dns_cache_item_remove_and_free(c, i);
+}
+
+static void dns_cache_make_space(DnsCache *c, unsigned add) {
+        assert(c);
+
+        if (add <= 0)
+                return;
+
+        /* Makes space for n new entries. Note that we actually allow
+         * the cache to grow beyond CACHE_MAX, but only when we shall
+         * add more RRs to the cache than CACHE_MAX at once. In that
+         * case the cache will be emptied completely otherwise. */
+
+        for (;;) {
+                _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *rr = NULL;
+                DnsCacheItem *i;
+
+                if (prioq_size(c->expire) <= 0)
+                        break;
+
+                if (prioq_size(c->expire) + add < CACHE_MAX)
+                        break;
+
+                i = prioq_peek(c->expire);
+                rr = dns_resource_record_ref(i->rr);
+                dns_cache_remove(c, &rr->key);
+        }
+}
+
+void dns_cache_prune(DnsCache *c) {
+        usec_t t = 0;
+
+        assert(c);
+
+        /* Remove all entries that are past their TTL */
+
+        for (;;) {
+                DnsCacheItem *i;
+                usec_t ttl;
+
+                i = prioq_peek(c->expire);
+                if (!i)
+                        break;
+
+                ttl = i->rr->ttl * USEC_PER_SEC;
+                if (ttl > CACHE_TTL_MAX_USEC)
+                        ttl = CACHE_TTL_MAX_USEC;
+
+                if (t <= 0)
+                        t = now(CLOCK_MONOTONIC);
+
+                if (i->timestamp + ttl > t)
+                        break;
+
+                dns_cache_remove(c, &i->rr->key);
+        }
+}
+
+static int dns_cache_item_prioq_compare_func(const void *a, const void *b) {
+        usec_t t, z;
+        const DnsCacheItem *x = a, *y = b;
+
+        t = x->timestamp + x->rr->ttl * USEC_PER_SEC;
+        z = y->timestamp + y->rr->ttl * USEC_PER_SEC;
+
+        if (t < z)
+                return -1;
+        if (t > z)
+                return 1;
+        return 0;
+}
+
+static void dns_cache_item_update(DnsCache *c, DnsCacheItem *i, DnsResourceRecord *rr, usec_t timestamp) {
+        assert(c);
+        assert(i);
+        assert(rr);
+
+        if (!i->rrsets_prev) {
+                /* 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);
+        }
+
+        dns_resource_record_unref(i->rr);
+        i->rr = dns_resource_record_ref(rr);
+
+        i->timestamp = timestamp;
+
+        prioq_reshuffle(c->expire, i, &i->expire_prioq_idx);
+}
+
+int dns_cache_put(DnsCache *c, DnsResourceRecord *rr, usec_t timestamp) {
+        _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
+        DnsCacheItem *first = NULL, *existing;
+        int r;
+
+        assert(c);
+        assert(rr);
+
+        /* New TTL is 0? Delete the entry... */
+        if (rr->ttl <= 0) {
+                dns_cache_remove(c, &rr->key);
+                return 0;
+        }
+
+        /* Entry exists already? Update TTL and timestamp */
+        existing = dns_cache_get(c, rr);
+        if (existing) {
+                dns_cache_item_update(c, existing, rr, timestamp);
+                return 0;
+        }
+
+        /* Otherwise, add the new RR */
+        r = prioq_ensure_allocated(&c->expire, dns_cache_item_prioq_compare_func);
+        if (r < 0)
+                return r;
+
+        r = hashmap_ensure_allocated(&c->rrsets, dns_resource_key_hash_func, dns_resource_key_compare_func);
+        if (r < 0)
+                return r;
+
+        dns_cache_make_space(c, 1);
+
+        i = new0(DnsCacheItem, 1);
+        if (!i)
+                return -ENOMEM;
+
+        i->rr = dns_resource_record_ref(rr);
+        i->timestamp = timestamp;
+        i->expire_prioq_idx = PRIOQ_IDX_NULL;
+
+        r = prioq_put(c->expire, i, &i->expire_prioq_idx);
+        if (r < 0)
+                return r;
+
+        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);
+        } else {
+                r = hashmap_put(c->rrsets, &i->rr->key, i);
+                if (r < 0) {
+                        prioq_remove(c->expire, i, &i->expire_prioq_idx);
+                        return r;
+                }
+        }
+
+        i = NULL;
+
+        return 0;
+}
+
+int dns_cache_put_rrs(DnsCache *c, DnsResourceRecord **rrs, unsigned n_rrs, usec_t timestamp) {
+        unsigned i, added = 0;
+        int r;
+
+        assert(c);
+
+        if (n_rrs <= 0)
+                return 0;
+
+        assert(rrs);
+
+        /* 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);
+
+        dns_cache_make_space(c, n_rrs);
+
+        /* Second iteration, add in new RRs */
+        for (added = 0; added < n_rrs; added++) {
+                if (timestamp <= 0)
+                        timestamp = now(CLOCK_MONOTONIC);
+
+                r = dns_cache_put(c, rrs[added], timestamp);
+                if (r < 0)
+                        goto fail;
+
+        }
+
+        return 0;
+
+fail:
+        /* Adding all RRs failed. Let's clean up what we already
+         * added, just in case */
+
+        for (i = 0; i < added; i++)
+                dns_cache_remove(c, &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 r;
+
+        assert(c);
+        assert(rrs);
+
+        if (n_keys <= 0) {
+                *rrs = NULL;
+                return 0;
+        }
+
+        assert(keys);
+
+        for (i = 0; i < n_keys; i++) {
+                DnsCacheItem *j;
+
+                j = dns_cache_lookup(c, &keys[i]);
+                if (!j) {
+                        *rrs = NULL;
+                        r = 0;
+                        goto fail;
+                }
+
+                LIST_FOREACH(rrsets, j, j) {
+
+                        if (!GREEDY_REALLOC(p, allocated, used+1)) {
+                                r = -ENOMEM;
+                                goto fail;
+                        }
+
+                        p[used++] = dns_resource_record_ref(j->rr);
+                }
+        }
+
+        *rrs = p;
+        return (int) used;
+
+fail:
+        dns_resource_record_freev(p, used);
+        return r;
+}
diff --git a/src/resolve/resolved-dns-cache.h b/src/resolve/resolved-dns-cache.h
new file mode 100644
index 0000000000..8d1cf95342
--- /dev/null
+++ b/src/resolve/resolved-dns-cache.h
@@ -0,0 +1,57 @@
+/*-*- 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/>.
+***/
+
+#include <sys/types.h>
+
+#include "hashmap.h"
+#include "prioq.h"
+#include "time-util.h"
+#include "list.h"
+
+typedef struct DnsCacheItem DnsCacheItem;
+
+typedef struct DnsCache {
+        Hashmap *rrsets;
+        Prioq *expire;
+} DnsCache;
+
+#include "resolved-dns-rr.h"
+
+typedef struct DnsCacheItem {
+        DnsResourceRecord *rr;
+        usec_t timestamp;
+        unsigned expire_prioq_idx;
+        LIST_FIELDS(DnsCacheItem, rrsets);
+} DnsCacheItem;
+
+void dns_cache_flush(DnsCache *c);
+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);
+
+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);
diff --git a/src/resolve/resolved-dns-domain.c b/src/resolve/resolved-dns-domain.c
index a41052dde3..eea73f6d54 100644
--- a/src/resolve/resolved-dns-domain.c
+++ b/src/resolve/resolved-dns-domain.c
@@ -218,7 +218,7 @@ int dns_name_normalize(const char *s, char **_ret) {
 
 unsigned long dns_name_hash_func(const void *s, const uint8_t hash_key[HASH_KEY_SIZE]) {
         const char *p = s;
-        unsigned long ul = 0;
+        unsigned long ul = hash_key[0];
         int r;
 
         assert(p);
@@ -233,7 +233,7 @@ unsigned long dns_name_hash_func(const void *s, const uint8_t hash_key[HASH_KEY_
                 label[r] = 0;
                 ascii_strlower(label);
 
-                ul = hash_key[0] * ul + ul + string_hash_func(label, hash_key);
+                ul = ul * hash_key[1] + ul + string_hash_func(label, hash_key);
         }
 
         return ul;
diff --git a/src/resolve/resolved-dns-packet.c b/src/resolve/resolved-dns-packet.c
index 5597ffd969..499683ac1d 100644
--- a/src/resolve/resolved-dns-packet.c
+++ b/src/resolve/resolved-dns-packet.c
@@ -91,6 +91,9 @@ static void dns_packet_free(DnsPacket *p) {
 
         assert(p);
 
+        if (p->rrs)
+                dns_resource_record_freev(p->rrs, DNS_PACKET_RRCOUNT(p));
+
         while ((s = hashmap_steal_first_key(p->names)))
                 free(s);
         hashmap_free(p->names);
@@ -726,11 +729,13 @@ fail:
 }
 
 int dns_packet_skip_question(DnsPacket *p) {
+        unsigned i, n;
         int r;
 
-        unsigned i, n;
         assert(p);
 
+        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 = {};
@@ -743,6 +748,49 @@ int dns_packet_skip_question(DnsPacket *p) {
         return 0;
 }
 
+int dns_packet_extract_rrs(DnsPacket *p) {
+        DnsResourceRecord **rrs = NULL;
+        size_t saved_rindex;
+        unsigned n, added = 0;
+        int r;
+
+        if (p->rrs)
+                return (int) DNS_PACKET_RRCOUNT(p);
+
+        saved_rindex = p->rindex;
+
+        r = dns_packet_skip_question(p);
+        if (r < 0)
+                goto finish;
+
+        n = DNS_PACKET_RRCOUNT(p);
+        if (n <= 0) {
+                r = 0;
+                goto finish;
+        }
+
+        rrs = new0(DnsResourceRecord*, n);
+        if (!rrs) {
+                r = -ENOMEM;
+                goto finish;
+        }
+
+        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->rrs = rrs;
+        r = (int) n;
+
+finish:
+        p->rindex = saved_rindex;
+        return r;
+}
+
 static const char* const dns_rcode_table[_DNS_RCODE_MAX_DEFINED] = {
         [DNS_RCODE_SUCCESS] = "SUCCESS",
         [DNS_RCODE_FORMERR] = "FORMERR",
diff --git a/src/resolve/resolved-dns-packet.h b/src/resolve/resolved-dns-packet.h
index de3a789a78..67c7bc3dfc 100644
--- a/src/resolve/resolved-dns-packet.h
+++ b/src/resolve/resolved-dns-packet.h
@@ -57,6 +57,7 @@ struct DnsPacket {
         int ifindex;
         size_t size, allocated, rindex;
         Hashmap *names; /* For name compression */
+        DnsResourceRecord **rrs;
         void *data;
 };
 
@@ -92,6 +93,12 @@ static inline uint8_t* DNS_PACKET_DATA(DnsPacket *p) {
          ((uint16_t) !!cd << 4) | \
          ((uint16_t) (rcode & 15)))
 
+static inline unsigned DNS_PACKET_RRCOUNT(DnsPacket *p) {
+        return
+                (unsigned) DNS_PACKET_ANCOUNT(p) +
+                (unsigned) DNS_PACKET_NSCOUNT(p) +
+                (unsigned) DNS_PACKET_ARCOUNT(p);
+}
 
 int dns_packet_new(DnsPacket **p, size_t mtu);
 int dns_packet_new_query(DnsPacket **p, size_t mtu);
@@ -123,6 +130,7 @@ 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);
 
 enum {
         DNS_RCODE_SUCCESS = 0,
diff --git a/src/resolve/resolved-dns-query.c b/src/resolve/resolved-dns-query.c
index fcde03d0ea..3955bc2d7b 100644
--- a/src/resolve/resolved-dns-query.c
+++ b/src/resolve/resolved-dns-query.c
@@ -28,7 +28,7 @@
 #define CNAME_MAX 8
 #define QUERIES_MAX 2048
 
-static int dns_query_transaction_start(DnsQueryTransaction *t);
+static int dns_query_transaction_go(DnsQueryTransaction *t);
 
 DnsQueryTransaction* dns_query_transaction_free(DnsQueryTransaction *t) {
         if (!t)
@@ -39,6 +39,8 @@ DnsQueryTransaction* dns_query_transaction_free(DnsQueryTransaction *t) {
         dns_packet_unref(t->sent);
         dns_packet_unref(t->received);
 
+        dns_resource_record_freev(t->cached_rrs, t->n_cached_rrs);
+
         sd_event_source_unref(t->tcp_event_source);
         safe_close(t->tcp_fd);
 
@@ -106,18 +108,19 @@ static void dns_query_transaction_stop(DnsQueryTransaction *t) {
         t->tcp_fd = safe_close(t->tcp_fd);
 }
 
-static void dns_query_transaction_set_state(DnsQueryTransaction *t, DnsQueryState state) {
+static void dns_query_transaction_complete(DnsQueryTransaction *t, DnsQueryState state) {
         assert(t);
+        assert(!IN_SET(state, DNS_QUERY_NULL, DNS_QUERY_PENDING));
+        assert(IN_SET(t->state, DNS_QUERY_NULL, DNS_QUERY_PENDING));
 
-        if (t->state == state)
-                return;
+        /* Note that this call might invalidate the query. Callers
+         * should hence not attempt to access the query or transaction
+         * after calling this function. */
 
         t->state = state;
 
-        if (state != DNS_QUERY_PENDING) {
-                dns_query_transaction_stop(t);
-                dns_query_finish(t->query);
-        }
+        dns_query_transaction_stop(t);
+        dns_query_finish(t->query);
 }
 
 static int on_tcp_ready(sd_event_source *s, int fd, uint32_t revents, void *userdata) {
@@ -143,7 +146,7 @@ static int on_tcp_ready(sd_event_source *s, int fd, uint32_t revents, void *user
                 ss = writev(fd, iov, 2);
                 if (ss < 0) {
                         if (errno != EINTR && errno != EAGAIN) {
-                                dns_query_transaction_set_state(t, DNS_QUERY_RESOURCES);
+                                dns_query_transaction_complete(t, DNS_QUERY_RESOURCES);
                                 return -errno;
                         }
                 } else
@@ -153,7 +156,7 @@ static int on_tcp_ready(sd_event_source *s, int fd, uint32_t revents, void *user
                 if (t->tcp_written >= sizeof(sz) + t->sent->size) {
                         r = sd_event_source_set_io_events(s, EPOLLIN);
                         if (r < 0) {
-                                dns_query_transaction_set_state(t, DNS_QUERY_RESOURCES);
+                                dns_query_transaction_complete(t, DNS_QUERY_RESOURCES);
                                 return r;
                         }
                 }
@@ -167,11 +170,11 @@ static int on_tcp_ready(sd_event_source *s, int fd, uint32_t revents, void *user
                         ss = read(fd, (uint8_t*) &t->tcp_read_size + t->tcp_read, sizeof(t->tcp_read_size) - t->tcp_read);
                         if (ss < 0) {
                                 if (errno != EINTR && errno != EAGAIN) {
-                                        dns_query_transaction_set_state(t, DNS_QUERY_RESOURCES);
+                                        dns_query_transaction_complete(t, DNS_QUERY_RESOURCES);
                                         return -errno;
                                 }
                         } else if (ss == 0) {
-                                dns_query_transaction_set_state(t, DNS_QUERY_RESOURCES);
+                                dns_query_transaction_complete(t, DNS_QUERY_RESOURCES);
                                 return -EIO;
                         } else
                                 t->tcp_read += ss;
@@ -180,7 +183,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)) {
 
                         if (be16toh(t->tcp_read_size) < DNS_PACKET_HEADER_SIZE) {
-                                dns_query_transaction_set_state(t, DNS_QUERY_INVALID_REPLY);
+                                dns_query_transaction_complete(t, DNS_QUERY_INVALID_REPLY);
                                 return -EBADMSG;
                         }
 
@@ -190,7 +193,7 @@ static int on_tcp_ready(sd_event_source *s, int fd, uint32_t revents, void *user
                                 if (!t->received) {
                                         r = dns_packet_new(&t->received, be16toh(t->tcp_read_size));
                                         if (r < 0) {
-                                                dns_query_transaction_set_state(t, DNS_QUERY_RESOURCES);
+                                                dns_query_transaction_complete(t, DNS_QUERY_RESOURCES);
                                                 return r;
                                         }
                                 }
@@ -200,11 +203,11 @@ static int on_tcp_ready(sd_event_source *s, int fd, uint32_t revents, void *user
                                           sizeof(t->tcp_read_size) + be16toh(t->tcp_read_size) - t->tcp_read);
                                 if (ss < 0) {
                                         if (errno != EINTR && errno != EAGAIN) {
-                                                dns_query_transaction_set_state(t, DNS_QUERY_RESOURCES);
+                                                dns_query_transaction_complete(t, DNS_QUERY_RESOURCES);
                                                 return -errno;
                                         }
                                 } else if (ss == 0) {
-                                        dns_query_transaction_set_state(t, DNS_QUERY_RESOURCES);
+                                        dns_query_transaction_complete(t, DNS_QUERY_RESOURCES);
                                         return -EIO;
                                 }  else
                                         t->tcp_read += ss;
@@ -221,7 +224,7 @@ static int on_tcp_ready(sd_event_source *s, int fd, uint32_t revents, void *user
         return 0;
 }
 
-static int dns_query_transaction_start_tcp(DnsQueryTransaction *t) {
+static int dns_query_transaction_open_tcp(DnsQueryTransaction *t) {
         int r;
 
         assert(t);
@@ -251,9 +254,11 @@ void dns_query_transaction_reply(DnsQueryTransaction *t, DnsPacket *p) {
 
         assert(t);
         assert(p);
+        assert(t->state == DNS_QUERY_PENDING);
 
-        if (t->state != DNS_QUERY_PENDING)
-                return;
+        /* Note that this call might invalidate the query. Callers
+         * should hence not attempt to access the query or transaction
+         * after calling this function. */
 
         if (t->received != p) {
                 dns_packet_unref(t->received);
@@ -263,32 +268,32 @@ void dns_query_transaction_reply(DnsQueryTransaction *t, DnsPacket *p) {
         if (t->tcp_fd >= 0) {
                 if (DNS_PACKET_TC(p)) {
                         /* Truncated via TCP? Somebody must be fucking with us */
-                        dns_query_transaction_set_state(t, DNS_QUERY_INVALID_REPLY);
+                        dns_query_transaction_complete(t, DNS_QUERY_INVALID_REPLY);
                         return;
                 }
 
                 if (DNS_PACKET_ID(p) != t->id) {
                         /* Not the reply to our query? Somebody must be fucking with us */
-                        dns_query_transaction_set_state(t, DNS_QUERY_INVALID_REPLY);
+                        dns_query_transaction_complete(t, DNS_QUERY_INVALID_REPLY);
                         return;
                 }
         }
 
         if (DNS_PACKET_TC(p)) {
                 /* Response was truncated, let's try again with good old TCP */
-                r = dns_query_transaction_start_tcp(t);
+                r = dns_query_transaction_open_tcp(t);
                 if (r == -ESRCH) {
                         /* No servers found? Damn! */
-                        dns_query_transaction_set_state(t, DNS_QUERY_NO_SERVERS);
+                        dns_query_transaction_complete(t, DNS_QUERY_NO_SERVERS);
                         return;
                 }
                 if (r < 0) {
                         /* Couldn't send? Try immediately again, with a new server */
                         dns_scope_next_dns_server(t->scope);
 
-                        r = dns_query_transaction_start(t);
+                        r = dns_query_transaction_go(t);
                         if (r < 0) {
-                                dns_query_transaction_set_state(t, DNS_QUERY_RESOURCES);
+                                dns_query_transaction_complete(t, DNS_QUERY_RESOURCES);
                                 return;
                         }
 
@@ -296,10 +301,18 @@ void dns_query_transaction_reply(DnsQueryTransaction *t, DnsPacket *p) {
                 }
         }
 
+        /* Parse and update the cache */
+        r = dns_packet_extract_rrs(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);
+
         if (DNS_PACKET_RCODE(p) == DNS_RCODE_SUCCESS)
-                dns_query_transaction_set_state(t, DNS_QUERY_SUCCESS);
+                dns_query_transaction_complete(t, DNS_QUERY_SUCCESS);
         else
-                dns_query_transaction_set_state(t, DNS_QUERY_FAILURE);
+                dns_query_transaction_complete(t, DNS_QUERY_FAILURE);
 }
 
 static int on_transaction_timeout(sd_event_source *s, usec_t usec, void *userdata) {
@@ -312,9 +325,9 @@ static int on_transaction_timeout(sd_event_source *s, usec_t usec, void *userdat
         /* Timeout reached? Try again, with a new server */
         dns_scope_next_dns_server(t->scope);
 
-        r = dns_query_transaction_start(t);
+        r = dns_query_transaction_go(t);
         if (r < 0)
-                dns_query_transaction_set_state(t, DNS_QUERY_RESOURCES);
+                dns_query_transaction_complete(t, DNS_QUERY_RESOURCES);
 
         return 0;
 }
@@ -348,7 +361,7 @@ static int dns_query_make_packet(DnsQueryTransaction *t) {
         return 0;
 }
 
-static int dns_query_transaction_start(DnsQueryTransaction *t) {
+static int dns_query_transaction_go(DnsQueryTransaction *t) {
         int r;
 
         assert(t);
@@ -356,38 +369,51 @@ static int dns_query_transaction_start(DnsQueryTransaction *t) {
         dns_query_transaction_stop(t);
 
         if (t->n_attempts >= ATTEMPTS_MAX) {
-                dns_query_transaction_set_state(t, DNS_QUERY_ATTEMPTS_MAX);
+                dns_query_transaction_complete(t, DNS_QUERY_ATTEMPTS_MAX);
                 return 0;
         }
 
-        r = dns_query_make_packet(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;
+
+        /* 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);
         if (r < 0)
                 return r;
+        if (r > 0) {
+                t->n_cached_rrs = r;
+                dns_query_transaction_complete(t, DNS_QUERY_SUCCESS);
+                return 0;
+        }
 
-        t->n_attempts++;
-        t->received = dns_packet_unref(t->received);
+        /* Otherwise, we need to ask the network */
+        r = dns_query_make_packet(t);
+        if (r < 0)
+                return r;
 
         /* Try via UDP, and if that fails due to large size try via TCP */
         r = dns_scope_send(t->scope, t->sent);
         if (r == -EMSGSIZE)
-                r = dns_query_transaction_start_tcp(t);
-
+                r = dns_query_transaction_open_tcp(t);
         if (r == -ESRCH) {
-                dns_query_transaction_set_state(t, DNS_QUERY_NO_SERVERS);
+                dns_query_transaction_complete(t, DNS_QUERY_NO_SERVERS);
                 return 0;
         }
         if (r < 0) {
                 /* Couldn't send? Try immediately again, with a new server */
                 dns_scope_next_dns_server(t->scope);
 
-                return dns_query_transaction_start(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);
         if (r < 0)
                 return r;
 
-        dns_query_transaction_set_state(t, DNS_QUERY_PENDING);
+        t->state = DNS_QUERY_PENDING;
         return 1;
 }
 
@@ -399,6 +425,9 @@ DnsQuery *dns_query_free(DnsQuery *q) {
 
         sd_bus_message_unref(q->request);
         dns_packet_unref(q->received);
+
+        dns_resource_record_freev(q->cached_rrs, q->n_cached_rrs);
+
         sd_event_source_unref(q->timeout_event_source);
 
         while (q->transactions)
@@ -450,6 +479,11 @@ int dns_query_new(Manager *m, DnsQuery **ret, DnsResourceKey *keys, unsigned n_k
                         name = q->keys[q->n_keys].name;
                 else if (!dns_name_equal(name, q->keys[q->n_keys].name))
                         return -EINVAL;
+
+                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);
         }
 
         LIST_PREPEND(queries, m->dns_queries, q);
@@ -472,22 +506,20 @@ static void dns_query_stop(DnsQuery *q) {
                 dns_query_transaction_free(q->transactions);
 }
 
-static void dns_query_set_state(DnsQuery *q, DnsQueryState state) {
-        DnsQueryState old_state;
+static void dns_query_complete(DnsQuery *q, DnsQueryState state) {
         assert(q);
+        assert(!IN_SET(state, DNS_QUERY_NULL, DNS_QUERY_PENDING));
+        assert(IN_SET(q->state, DNS_QUERY_NULL, DNS_QUERY_PENDING));
 
-        if (q->state == state)
-                return;
+        /* Note that this call might invalidate the query. Callers
+         * should hence not attempt to access the query or transaction
+         * after calling this function. */
 
-        old_state = q->state;
         q->state = state;
 
-        if (!IN_SET(state, DNS_QUERY_NULL, DNS_QUERY_PENDING)) {
-                dns_query_stop(q);
-
-                if (old_state == DNS_QUERY_PENDING && q->complete)
-                        q->complete(q);
-        }
+        dns_query_stop(q);
+        if (q->complete)
+                q->complete(q);
 }
 
 static int on_query_timeout(sd_event_source *s, usec_t usec, void *userdata) {
@@ -496,11 +528,11 @@ static int on_query_timeout(sd_event_source *s, usec_t usec, void *userdata) {
         assert(s);
         assert(q);
 
-        dns_query_set_state(q, DNS_QUERY_TIMEOUT);
+        dns_query_complete(q, DNS_QUERY_TIMEOUT);
         return 0;
 }
 
-int dns_query_start(DnsQuery *q) {
+int dns_query_go(DnsQuery *q) {
         DnsScopeMatch found = DNS_SCOPE_NO;
         DnsScope *s, *first = NULL;
         DnsQueryTransaction *t;
@@ -564,18 +596,18 @@ int dns_query_start(DnsQuery *q) {
         if (r < 0)
                 goto fail;
 
-        dns_query_set_state(q, DNS_QUERY_PENDING);
+        q->state = DNS_QUERY_PENDING;
+        q->block_finish++;
 
         LIST_FOREACH(transactions_by_query, t, q->transactions) {
-
-                r = dns_query_transaction_start(t);
+                r = dns_query_transaction_go(t);
                 if (r < 0)
                         goto fail;
-
-                if (q->state != DNS_QUERY_PENDING)
-                        break;
         }
 
+        q->block_finish--;
+        dns_query_finish(q);
+
         return 1;
 
 fail:
@@ -589,8 +621,14 @@ void dns_query_finish(DnsQuery *q) {
         DnsPacket *received = NULL;
 
         assert(q);
+        assert(IN_SET(q->state, DNS_QUERY_NULL, DNS_QUERY_PENDING));
 
-        if (q->state != 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
+         * counter was explicitly bumped before doing so. */
+
+        if (q->block_finish > 0)
                 return;
 
         LIST_FOREACH(transactions_by_query, t, q->transactions) {
@@ -599,10 +637,18 @@ void dns_query_finish(DnsQuery *q) {
                 if (t->state == DNS_QUERY_PENDING || t->state == DNS_QUERY_NULL)
                         return;
 
-                /* One of the transactions is successful, let's use it */
+                /* 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);
-                        dns_query_set_state(q, DNS_QUERY_SUCCESS);
+
+                        /* 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;
+
+                        dns_query_complete(q, DNS_QUERY_SUCCESS);
                         return;
                 }
 
@@ -622,10 +668,10 @@ void dns_query_finish(DnsQuery *q) {
         if (state == DNS_QUERY_FAILURE)
                 q->received = dns_packet_ref(received);
 
-        dns_query_set_state(q, state);
+        dns_query_complete(q, state);
 }
 
-int dns_query_follow_cname(DnsQuery *q, const char *name) {
+int dns_query_cname_redirect(DnsQuery *q, const char *name) {
         DnsResourceKey *keys;
         unsigned i;
 
@@ -659,7 +705,9 @@ int dns_query_follow_cname(DnsQuery *q, const char *name) {
 
         q->n_cname++;
 
-        dns_query_set_state(q, DNS_QUERY_NULL);
+        dns_query_stop(q);
+        q->state = DNS_QUERY_NULL;
+
         return 0;
 }
 
@@ -709,3 +757,57 @@ int dns_query_matches_cname(DnsQuery *q, DnsResourceRecord *rr) {
 
         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 864036acc7..aa205033af 100644
--- a/src/resolve/resolved-dns-query.h
+++ b/src/resolve/resolved-dns-query.h
@@ -64,6 +64,10 @@ struct DnsQueryTransaction {
         size_t tcp_written, tcp_read;
         be16_t tcp_read_size;
 
+        /* Data from cache */
+        DnsResourceRecord **cached_rrs;
+        unsigned n_cached_rrs;
+
         LIST_FIELDS(DnsQueryTransaction, transactions_by_query);
         LIST_FIELDS(DnsQueryTransaction, transactions_by_scope);
 };
@@ -79,7 +83,10 @@ struct DnsQuery {
 
         sd_event_source *timeout_event_source;
 
+        /* Discovered data */
         DnsPacket *received;
+        DnsResourceRecord **cached_rrs;
+        unsigned n_cached_rrs;
 
         /* Bus client information */
         sd_bus_message *request;
@@ -87,21 +94,30 @@ struct DnsQuery {
         const char *request_hostname;
         union in_addr_union request_address;
 
+        /* Completion callback */
         void (*complete)(DnsQuery* q);
+        unsigned block_finish;
 
         LIST_HEAD(DnsQueryTransaction, transactions);
         LIST_FIELDS(DnsQuery, queries);
 };
 
+DnsQueryTransaction* dns_query_transaction_free(DnsQueryTransaction *t);
+void dns_query_transaction_reply(DnsQueryTransaction *t, DnsPacket *p);
+
 int dns_query_new(Manager *m, DnsQuery **q, DnsResourceKey *keys, unsigned n_keys);
 DnsQuery *dns_query_free(DnsQuery *q);
-int dns_query_start(DnsQuery *q);
-int dns_query_follow_cname(DnsQuery *q, const char *name);
+
+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);
 
-DnsQueryTransaction* dns_query_transaction_free(DnsQueryTransaction *t);
-void dns_query_transaction_reply(DnsQueryTransaction *t, DnsPacket *p);
-void dns_query_finish(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);
 
 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsQuery*, dns_query_free);
diff --git a/src/resolve/resolved-dns-rr.c b/src/resolve/resolved-dns-rr.c
index cb555cb4ef..c8f7cf4a4c 100644
--- a/src/resolve/resolved-dns-rr.c
+++ b/src/resolve/resolved-dns-rr.c
@@ -19,6 +19,7 @@
   along with systemd; If not, see <http://www.gnu.org/licenses/>.
 ***/
 
+#include "resolved-dns-domain.h"
 #include "resolved-dns-rr.h"
 
 void dns_resource_key_free(DnsResourceKey *key) {
@@ -29,6 +30,38 @@ void dns_resource_key_free(DnsResourceKey *key) {
         zero(*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 = ul * hash_key[0] + ul + k->class;
+        ul = ul * hash_key[1] + ul + k->type;
+
+        return ul;
+}
+
+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);
+        if (ret != 0)
+                return ret;
+
+        if (x->type < y->type)
+                return -1;
+        if (x->type > y->type)
+                return 1;
+
+        if (x->class < y->class)
+                return -1;
+        if (x->class > y->class)
+                return 1;
+
+        return 0;
+}
+
 DnsResourceRecord* dns_resource_record_new(void) {
         DnsResourceRecord *rr;
 
@@ -74,3 +107,121 @@ DnsResourceRecord* dns_resource_record_unref(DnsResourceRecord *rr) {
 
         return NULL;
 }
+
+DnsResourceRecord** dns_resource_record_freev(DnsResourceRecord **rrs, unsigned n) {
+        unsigned i;
+
+        assert(n == 0 || rrs);
+
+        for (i = 0; i < n; i++)
+                dns_resource_record_unref(rrs[i]);
+
+        free(rrs);
+        return NULL;
+}
+
+int dns_resource_record_equal(const DnsResourceRecord *a, const DnsResourceRecord *b) {
+        int r;
+
+        assert(a);
+        assert(b);
+
+        r = dns_name_equal(a->key.name, b->key.name);
+        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))
+                return dns_name_equal(a->ptr.name, b->ptr.name);
+        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)
+                return memcmp(&a->a.in_addr, &b->a.in_addr, sizeof(struct in_addr)) == 0;
+        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 &&
+                        memcmp(a->generic.data, b->generic.data, a->generic.size) == 0;
+}
+
+const char *dns_class_to_string(uint16_t class) {
+
+        switch (class) {
+
+        case DNS_CLASS_IN:
+                return "IN";
+
+        case DNS_CLASS_ANY:
+                return "ANY";
+        }
+
+        return NULL;
+}
+
+const char *dns_type_to_string(uint16_t type) {
+
+        switch (type) {
+
+        case DNS_TYPE_A:
+                return "A";
+
+        case DNS_TYPE_NS:
+                return "NS";
+
+        case DNS_TYPE_CNAME:
+                return "CNAME";
+
+        case DNS_TYPE_SOA:
+                return "SOA";
+
+        case DNS_TYPE_PTR:
+                return "PTR";
+
+        case DNS_TYPE_HINFO:
+                return "HINFO";
+
+        case DNS_TYPE_MX:
+                return "MX";
+
+        case DNS_TYPE_TXT:
+                return "TXT";
+
+        case DNS_TYPE_AAAA:
+                return "AAAA";
+
+        case DNS_TYPE_SRV:
+                return "SRV";
+
+        case DNS_TYPE_SSHFP:
+                return "SSHFP";
+
+        case DNS_TYPE_DNAME:
+                return "DNAME";
+
+        case DNS_TYPE_ANY:
+                return "ANY";
+
+        case DNS_TYPE_OPT:
+                return "OPT";
+
+        case DNS_TYPE_TKEY:
+                return "TKEY";
+
+        case DNS_TYPE_TSIG:
+                return "TSIG";
+
+        case DNS_TYPE_IXFR:
+                return "IXFR";
+
+        case DNS_TYPE_AXFR:
+                return "AXFR";
+        }
+
+        return NULL;
+}
diff --git a/src/resolve/resolved-dns-rr.h b/src/resolve/resolved-dns-rr.h
index 144fffa3e0..5d9f3e5a24 100644
--- a/src/resolve/resolved-dns-rr.h
+++ b/src/resolve/resolved-dns-rr.h
@@ -25,6 +25,7 @@
 #include <netinet/in.h>
 
 #include "util.h"
+#include "hashmap.h"
 
 typedef struct DnsResourceKey DnsResourceKey;
 typedef struct DnsResourceRecord DnsResourceRecord;
@@ -32,6 +33,7 @@ typedef struct DnsResourceRecord DnsResourceRecord;
 /* DNS record classes, see RFC 1035 */
 enum {
         DNS_CLASS_IN   = 0x01,
+        DNS_CLASS_ANY  = 0xFF,
 };
 
 /* DNS record types, see RFC 1035 */
@@ -47,6 +49,8 @@ enum {
         DNS_TYPE_TXT   = 0x10,
         DNS_TYPE_AAAA  = 0x1C,
         DNS_TYPE_SRV   = 0x21,
+        DNS_TYPE_SSHFP = 0x2C,
+        DNS_TYPE_DNAME = 0x27,
 
         /* Special records */
         DNS_TYPE_ANY   = 0xFF,
@@ -107,8 +111,18 @@ struct DnsResourceRecord {
 
 void dns_resource_key_free(DnsResourceKey *key);
 
+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);
+
 DnsResourceRecord* dns_resource_record_new(void);
 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);
+
+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 1fa8401ed5..b6884fd0aa 100644
--- a/src/resolve/resolved-dns-scope.c
+++ b/src/resolve/resolved-dns-scope.c
@@ -60,6 +60,8 @@ DnsScope* dns_scope_free(DnsScope *s) {
                 dns_query_finish(q);
         }
 
+        dns_cache_flush(&s->cache);
+
         LIST_REMOVE(scopes, s->manager->dns_scopes, s);
         strv_free(s->domains);
         free(s);
diff --git a/src/resolve/resolved-dns-scope.h b/src/resolve/resolved-dns-scope.h
index 97544f9e48..b5fae2d7a1 100644
--- a/src/resolve/resolved-dns-scope.h
+++ b/src/resolve/resolved-dns-scope.h
@@ -30,6 +30,7 @@ typedef struct DnsScope DnsScope;
 #include "resolved-dns-server.h"
 #include "resolved-dns-packet.h"
 #include "resolved-dns-query.h"
+#include "resolved-dns-cache.h"
 
 typedef enum DnsScopeType {
         DNS_SCOPE_DNS,
@@ -54,6 +55,8 @@ struct DnsScope {
 
         char **domains;
 
+        DnsCache cache;
+
         LIST_HEAD(DnsQueryTransaction, transactions);
 
         LIST_FIELDS(DnsScope, scopes);