resolved: implement LLMNR uniqueness verification

15 files changed, 1202 insertions, 759 deletions

diff --git a/src/resolve/resolved-bus.c b/src/resolve/resolved-bus.c
index 0b8ecf1b82..bfb060d86b 100644
--- a/src/resolve/resolved-bus.c
+++ b/src/resolve/resolved-bus.c
@@ -42,22 +42,22 @@ static int reply_query_state(DnsQuery *q) {
 
         switch (q->state) {
 
-        case DNS_QUERY_NO_SERVERS:
+        case DNS_TRANSACTION_NO_SERVERS:
                 return sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_NAME_SERVERS, "No appropriate name servers or networks for name found");
 
-        case DNS_QUERY_TIMEOUT:
+        case DNS_TRANSACTION_TIMEOUT:
                 return sd_bus_reply_method_errorf(q->request, SD_BUS_ERROR_TIMEOUT, "Query timed out");
 
-        case DNS_QUERY_ATTEMPTS_MAX:
+        case DNS_TRANSACTION_ATTEMPTS_MAX_REACHED:
                 return sd_bus_reply_method_errorf(q->request, SD_BUS_ERROR_TIMEOUT, "All attempts to contact name servers or networks failed");
 
-        case DNS_QUERY_RESOURCES:
+        case DNS_TRANSACTION_RESOURCES:
                 return sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_RESOURCES, "Not enough resources");
 
-        case DNS_QUERY_INVALID_REPLY:
+        case DNS_TRANSACTION_INVALID_REPLY:
                 return sd_bus_reply_method_errorf(q->request, BUS_ERROR_INVALID_REPLY, "Received invalid reply");
 
-        case DNS_QUERY_FAILURE: {
+        case DNS_TRANSACTION_FAILURE: {
                 _cleanup_bus_error_free_ sd_bus_error error = SD_BUS_ERROR_NULL;
 
                 if (q->answer_rcode == DNS_RCODE_NXDOMAIN)
@@ -79,9 +79,9 @@ static int reply_query_state(DnsQuery *q) {
                 return sd_bus_reply_method_error(q->request, &error);
         }
 
-        case DNS_QUERY_NULL:
-        case DNS_QUERY_PENDING:
-        case DNS_QUERY_SUCCESS:
+        case DNS_TRANSACTION_NULL:
+        case DNS_TRANSACTION_PENDING:
+        case DNS_TRANSACTION_SUCCESS:
         default:
                 assert_not_reached("Impossible state");
         }
@@ -136,7 +136,7 @@ static void bus_method_resolve_hostname_complete(DnsQuery *q) {
 
         assert(q);
 
-        if (q->state != DNS_QUERY_SUCCESS) {
+        if (q->state != DNS_TRANSACTION_SUCCESS) {
                 r = reply_query_state(q);
                 goto finish;
         }
@@ -336,7 +336,7 @@ static void bus_method_resolve_address_complete(DnsQuery *q) {
 
         assert(q);
 
-        if (q->state != DNS_QUERY_SUCCESS) {
+        if (q->state != DNS_TRANSACTION_SUCCESS) {
                 r = reply_query_state(q);
                 goto finish;
         }
@@ -474,7 +474,7 @@ static void bus_method_resolve_record_complete(DnsQuery *q) {
 
         assert(q);
 
-        if (q->state != DNS_QUERY_SUCCESS) {
+        if (q->state != DNS_TRANSACTION_SUCCESS) {
                 r = reply_query_state(q);
                 goto finish;
         }
diff --git a/src/resolve/resolved-dns-query.c b/src/resolve/resolved-dns-query.c
index 2277002304..57f7467667 100644
--- a/src/resolve/resolved-dns-query.c
+++ b/src/resolve/resolved-dns-query.c
@@ -24,516 +24,36 @@
 #include "resolved-dns-query.h"
 #include "resolved-dns-domain.h"
 
-/* After how much time to repeat classic DNS requests */
-#define DNS_TRANSACTION_TIMEOUT_USEC (5 * USEC_PER_SEC)
-
-/* After how much time to repeat LLMNR requests, see RFC 4795 Section 7 */
-#define LLMNR_TRANSACTION_TIMEOUT_USEC (1 * USEC_PER_SEC)
-
 /* How long to wait for the query in total */
 #define QUERY_TIMEOUT_USEC (30 * USEC_PER_SEC)
 
-/* Maximum attempts to send DNS requests, across all DNS servers */
-#define DNS_TRANSACTION_ATTEMPTS_MAX 8
-
-/* Maximum attempts to send LLMNR requests, see RFC 4795 Section 2.7 */
-#define LLMNR_TRANSACTION_ATTEMPTS_MAX 3
-
 #define CNAME_MAX 8
 #define QUERIES_MAX 2048
 
-#define TRANSACTION_TIMEOUT_USEC(p) ((t)->scope->protocol == DNS_PROTOCOL_LLMNR ? LLMNR_TRANSACTION_TIMEOUT_USEC : DNS_TRANSACTION_TIMEOUT_USEC)
-#define TRANSACTION_ATTEMPTS_MAX(p) ((t)->scope->protocol == DNS_PROTOCOL_LLMNR ? LLMNR_TRANSACTION_ATTEMPTS_MAX : DNS_TRANSACTION_ATTEMPTS_MAX)
-
-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_answer_unref(t->cached);
-
-        dns_stream_free(t->stream);
-
-        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));
-        }
-
-        while ((q = set_steal_first(t->queries)))
-                set_remove(q->transactions, t);
-
-        set_free(t->queries);
-
-        free(t);
-        return NULL;
-}
-
-DEFINE_TRIVIAL_CLEANUP_FUNC(DnsQueryTransaction*, dns_query_transaction_free);
-
-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;
+static void dns_query_stop(DnsQuery *q) {
+        DnsTransaction *t;
 
-        assert(ret);
-        assert(s);
         assert(q);
 
-        r = hashmap_ensure_allocated(&s->manager->dns_query_transactions, NULL, NULL);
-        if (r < 0)
-                return r;
-
-        t = new0(DnsQueryTransaction, 1);
-        if (!t)
-                return -ENOMEM;
-
-        t->question = dns_question_ref(q);
-
-        do
-                random_bytes(&t->id, sizeof(t->id));
-        while (t->id == 0 ||
-               hashmap_get(s->manager->dns_query_transactions, UINT_TO_PTR(t->id)));
-
-        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_scope, s->transactions, t);
-        t->scope = s;
-
-        if (ret)
-                *ret = t;
-
-        t = NULL;
-
-        return 0;
-}
-
-static void dns_query_transaction_stop(DnsQueryTransaction *t) {
-        assert(t);
-
-        t->timeout_event_source = sd_event_source_unref(t->timeout_event_source);
-        t->stream = dns_stream_free(t->stream);
-}
-
-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));
-
-        /* Note that this call might invalidate the query. Callers
-         * should hence not attempt to access the query or transaction
-         * after calling this function. */
-
-        log_debug("Transaction on scope %s on %s/%s now complete with %s",
-                  dns_protocol_to_string(t->scope->protocol),
-                  t->scope->link ? t->scope->link->name : "*",
-                  t->scope->family == AF_UNSPEC ? "*" : af_to_name(t->scope->family),
-                  dns_query_state_to_string(state));
-
-        t->state = state;
-
-        dns_query_transaction_stop(t);
-
-        /* 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_stream_complete(DnsStream *s, int error) {
-        _cleanup_(dns_packet_unrefp) DnsPacket *p = NULL;
-        DnsQueryTransaction *t;
-
-        assert(s);
-        assert(s->transaction);
-
-        /* Copy the data we care about out of the stream before we
-         * destroy it. */
-        t = s->transaction;
-        p = dns_packet_ref(s->read_packet);
-
-        t->stream = dns_stream_free(t->stream);
-
-        if (error != 0) {
-                dns_query_transaction_complete(t, DNS_QUERY_RESOURCES);
-                return 0;
-        }
-
-        t->block_gc++;
-        dns_query_transaction_process_reply(t, p);
-        t->block_gc--;
-
-        /* If the response wasn't useful, then complete the transition now */
-        if (t->state == DNS_QUERY_PENDING)
-                dns_query_transaction_complete(t, DNS_QUERY_INVALID_REPLY);
-
-        return 0;
-}
-
-static int dns_query_transaction_open_tcp(DnsQueryTransaction *t) {
-        _cleanup_close_ int fd = -1;
-        int r;
-
-        assert(t);
-
-        if (t->stream)
-                return 0;
-
-        if (t->scope->protocol == DNS_PROTOCOL_DNS)
-                fd = dns_scope_tcp_socket(t->scope, AF_UNSPEC, NULL, 53);
-        else if (t->scope->protocol == DNS_PROTOCOL_LLMNR) {
-
-                /* When we already received a query to this (but it was truncated), send to its sender address */
-                if (t->received)
-                        fd = dns_scope_tcp_socket(t->scope, t->received->family, &t->received->sender, t->received->sender_port);
-                else {
-                        union in_addr_union address;
-                        int family;
-
-                        /* Otherwise, try to talk to the owner of a
-                         * the IP address, in case this is a reverse
-                         * PTR lookup */
-                        r = dns_question_extract_reverse_address(t->question, &family, &address);
-                        if (r < 0)
-                                return r;
-                        if (r == 0)
-                                return -EINVAL;
-
-                        fd = dns_scope_tcp_socket(t->scope, family, &address, 5355);
-                }
-        } else
-                return -EAFNOSUPPORT;
-
-        if (fd < 0)
-                return fd;
-
-        r = dns_stream_new(t->scope->manager, &t->stream, t->scope->protocol, fd);
-        if (r < 0)
-                return r;
-
-        fd = -1;
-
-        r = dns_stream_write_packet(t->stream, t->sent);
-        if (r < 0) {
-                t->stream = dns_stream_free(t->stream);
-                return r;
-        }
-
-        t->received = dns_packet_unref(t->received);
-        t->stream->complete = on_stream_complete;
-        t->stream->transaction = t;
-
-        /* The interface index is difficult to determine if we are
-         * connecting to the local host, hence fill this in right away
-         * instead of determining it from the socket */
-        if (t->scope->link)
-                t->stream->ifindex = t->scope->link->ifindex;
-
-        return 0;
-}
-
-void dns_query_transaction_process_reply(DnsQueryTransaction *t, DnsPacket *p) {
-        int r;
-
-        assert(t);
-        assert(p);
-        assert(t->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. */
-
-        if (t->scope->protocol == DNS_PROTOCOL_LLMNR) {
-                assert(t->scope->link);
-
-                /* For LLMNR we will not accept any packets from other
-                 * interfaces */
-
-                if (p->ifindex != t->scope->link->ifindex)
-                        return;
-
-                if (p->family != t->scope->family)
-                        return;
-
-                /* Tentative replies shall be discarded, see RFC 4795,
-                 * 2.1.1 */
-
-                if (DNS_PACKET_T(p))
-                        return;
-        }
-
-        if (t->scope->protocol == DNS_PROTOCOL_DNS) {
-
-                /* For DNS we are fine with accepting packets on any
-                 * interface, but the source IP address must be one of
-                 * a valid DNS server */
-
-                if (!dns_scope_good_dns_server(t->scope, p->family, &p->sender))
-                        return;
-
-                if (p->sender_port != 53)
-                        return;
-        }
-
-        if (t->received != p) {
-                dns_packet_unref(t->received);
-                t->received = dns_packet_ref(p);
-        }
-
-        if (p->ipproto == IPPROTO_TCP) {
-                if (DNS_PACKET_TC(p)) {
-                        /* Truncated via TCP? Somebody must be fucking with us */
-                        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_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_open_tcp(t);
-                if (r == -ESRCH) {
-                        /* No servers found? Damn! */
-                        dns_query_transaction_complete(t, DNS_QUERY_NO_SERVERS);
-                        return;
-                }
-                if (r < 0) {
-                        /* On LLMNR, if we cannot connect to the host,
-                         * we immediately give up */
-                        if (t->scope->protocol == DNS_PROTOCOL_LLMNR) {
-                                dns_query_transaction_complete(t, DNS_QUERY_RESOURCES);
-                                return;
-                        }
-
-                        /* On DNS, couldn't send? Try immediately again, with a new server */
-                        dns_scope_next_dns_server(t->scope);
-
-                        r = dns_query_transaction_go(t);
-                        if (r < 0) {
-                                dns_query_transaction_complete(t, DNS_QUERY_RESOURCES);
-                                return;
-                        }
-
-                        return;
-                }
-        }
-
-        /* Parse and update the cache */
-        r = dns_packet_extract(p);
-        if (r < 0) {
-                dns_query_transaction_complete(t, DNS_QUERY_INVALID_REPLY);
-                return;
-        }
-
-        /* According to RFC 4795, section 2.9. only the RRs from the answer section shall be cached */
-        dns_cache_put(&t->scope->cache, p->question, DNS_PACKET_RCODE(p), p->answer, DNS_PACKET_ANCOUNT(p), 0);
-
-        if (DNS_PACKET_RCODE(p) == DNS_RCODE_SUCCESS)
-                dns_query_transaction_complete(t, DNS_QUERY_SUCCESS);
-        else
-                dns_query_transaction_complete(t, DNS_QUERY_FAILURE);
-}
-
-static int on_transaction_timeout(sd_event_source *s, usec_t usec, void *userdata) {
-        DnsQueryTransaction *t = userdata;
-        int r;
-
-        assert(s);
-        assert(t);
-
-        /* Timeout reached? Try again, with a new server */
-        dns_scope_next_dns_server(t->scope);
-
-        r = dns_query_transaction_go(t);
-        if (r < 0)
-                dns_query_transaction_complete(t, DNS_QUERY_RESOURCES);
-
-        return 0;
-}
-
-static int dns_query_make_packet(DnsQueryTransaction *t) {
-        _cleanup_(dns_packet_unrefp) DnsPacket *p = NULL;
-        unsigned n, added = 0;
-        int r;
-
-        assert(t);
-
-        if (t->sent)
-                return 0;
-
-        r = dns_packet_new_query(&p, t->scope->protocol, 0);
-        if (r < 0)
-                return r;
-
-        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->question->keys[n], NULL);
-                if (r < 0)
-                        return r;
-
-                added++;
-        }
-
-        if (added <= 0)
-                return -EDOM;
-
-        DNS_PACKET_HEADER(p)->qdcount = htobe16(added);
-        DNS_PACKET_HEADER(p)->id = t->id;
-
-        t->sent = p;
-        p = NULL;
-
-        return 0;
-}
-
-static int dns_query_transaction_go(DnsQueryTransaction *t) {
-        bool had_stream;
-        int r;
-
-        assert(t);
-
-        had_stream = !!t->stream;
-
-        dns_query_transaction_stop(t);
-
-        log_debug("Beginning transaction on scope %s on %s/%s",
-                  dns_protocol_to_string(t->scope->protocol),
-                  t->scope->link ? t->scope->link->name : "*",
-                  t->scope->family == AF_UNSPEC ? "*" : af_to_name(t->scope->family));
-
-        if (t->n_attempts >= TRANSACTION_ATTEMPTS_MAX(t)) {
-                dns_query_transaction_complete(t, DNS_QUERY_ATTEMPTS_MAX);
-                return 0;
-        }
-
-        if (t->scope->protocol == DNS_PROTOCOL_LLMNR && had_stream) {
-                /* If we already tried via a stream, then we don't
-                 * retry on LLMNR. See RFC 4795, Section 2.7. */
-                dns_query_transaction_complete(t, DNS_QUERY_ATTEMPTS_MAX);
-                return 0;
-        }
-
-        t->n_attempts++;
-        t->received = dns_packet_unref(t->received);
-        t->cached = dns_answer_unref(t->cached);
-        t->cached_rcode = 0;
-
-        /* First, let's try the cache */
-        dns_cache_prune(&t->scope->cache);
-        r = dns_cache_lookup(&t->scope->cache, t->question, &t->cached_rcode, &t->cached);
-        if (r < 0)
-                return r;
-        if (r > 0) {
-                if (t->cached_rcode == DNS_RCODE_SUCCESS)
-                        dns_query_transaction_complete(t, DNS_QUERY_SUCCESS);
-                else
-                        dns_query_transaction_complete(t, DNS_QUERY_FAILURE);
-                return 0;
-        }
-
-        /* Otherwise, we need to ask the network */
-        r = dns_query_make_packet(t);
-        if (r == -EDOM) {
-                /* Not the right request to make on this network?
-                 * (i.e. an A request made on IPv6 or an AAAA request
-                 * made on IPv4, on LLMNR or mDNS.) */
-                dns_query_transaction_complete(t, DNS_QUERY_NO_SERVERS);
-                return 0;
-        }
-        if (r < 0)
-                return r;
-
-        if (t->scope->protocol == DNS_PROTOCOL_LLMNR &&
-            (dns_question_endswith(t->question, "in-addr.arpa") > 0 ||
-             dns_question_endswith(t->question, "ip6.arpa") > 0)) {
-
-                /* RFC 4795, Section 2.4. says reverse lookups shall
-                 * always be made via TCP on LLMNR */
-                r = dns_query_transaction_open_tcp(t);
-        } else {
-                /* 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_open_tcp(t);
-        }
-        if (r == -ESRCH) {
-                /* No servers to send this to? */
-                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);
+        q->timeout_event_source = sd_event_source_unref(q->timeout_event_source);
 
-                return dns_query_transaction_go(t);
+        while ((t = set_steal_first(q->transactions))) {
+                set_remove(t->queries, q);
+                dns_transaction_gc(t);
         }
-
-        r = sd_event_add_time(t->scope->manager->event, &t->timeout_event_source, CLOCK_MONOTONIC, now(CLOCK_MONOTONIC) + TRANSACTION_TIMEOUT_USEC(t), 0, on_transaction_timeout, t);
-        if (r < 0)
-                return r;
-
-        t->state = DNS_QUERY_PENDING;
-        return 1;
 }
 
 DnsQuery *dns_query_free(DnsQuery *q) {
-        DnsQueryTransaction *t;
-
         if (!q)
                 return NULL;
 
-        sd_bus_message_unref(q->request);
+        dns_query_stop(q);
+        set_free(q->transactions);
 
         dns_question_unref(q->question);
         dns_answer_unref(q->answer);
 
-        sd_event_source_unref(q->timeout_event_source);
-
-        while ((t = set_steal_first(q->transactions))) {
-                set_remove(t->queries, q);
-                dns_query_transaction_gc(t);
-        }
-
-        set_free(q->transactions);
+        sd_bus_message_unref(q->request);
 
         if (q->manager) {
                 LIST_REMOVE(queries, q->manager->dns_queries, q);
@@ -587,23 +107,10 @@ int dns_query_new(Manager *m, DnsQuery **ret, DnsQuestion *question) {
         return 0;
 }
 
-static void dns_query_stop(DnsQuery *q) {
-        DnsQueryTransaction *t;
-
-        assert(q);
-
-        q->timeout_event_source = sd_event_source_unref(q->timeout_event_source);
-
-        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) {
+static void dns_query_complete(DnsQuery *q, DnsTransactionState state) {
         assert(q);
-        assert(!IN_SET(state, DNS_QUERY_NULL, DNS_QUERY_PENDING));
-        assert(IN_SET(q->state, DNS_QUERY_NULL, DNS_QUERY_PENDING));
+        assert(!IN_SET(state, DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING));
+        assert(IN_SET(q->state, DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING));
 
         /* Note that this call might invalidate the query. Callers
          * should hence not attempt to access the query or transaction
@@ -622,16 +129,17 @@ static int on_query_timeout(sd_event_source *s, usec_t usec, void *userdata) {
         assert(s);
         assert(q);
 
-        dns_query_complete(q, DNS_QUERY_TIMEOUT);
+        dns_query_complete(q, DNS_TRANSACTION_TIMEOUT);
         return 0;
 }
 
 static int dns_query_add_transaction(DnsQuery *q, DnsScope *s, DnsResourceKey *key) {
         _cleanup_(dns_question_unrefp) DnsQuestion *question = NULL;
-        DnsQueryTransaction *t;
+        DnsTransaction *t;
         int r;
 
         assert(q);
+        assert(s);
 
         r = set_ensure_allocated(&q->transactions, NULL, NULL);
         if (r < 0)
@@ -648,34 +156,31 @@ static int dns_query_add_transaction(DnsQuery *q, DnsScope *s, DnsResourceKey *k
         } else
                 question = dns_question_ref(q->question);
 
-        LIST_FOREACH(transactions_by_scope, t, s->transactions)
-                if (dns_question_is_superset(t->question, question))
-                        break;
-
+        t = dns_scope_find_transaction(s, question);
         if (!t) {
-                r = dns_query_transaction_new(&t, s, question);
+                r = dns_transaction_new(&t, s, question);
                 if (r < 0)
                         return r;
         }
 
         r = set_ensure_allocated(&t->queries, NULL, NULL);
         if (r < 0)
-                goto fail;
+                goto gc;
 
         r = set_put(t->queries, q);
         if (r < 0)
-                goto fail;
+                goto gc;
 
         r = set_put(q->transactions, t);
         if (r < 0) {
                 set_remove(t->queries, q);
-                goto fail;
+                goto gc;
         }
 
         return 0;
 
-fail:
-        dns_query_transaction_gc(t);
+gc:
+        dns_transaction_gc(t);
         return r;
 }
 
@@ -709,14 +214,14 @@ static int dns_query_add_transaction_split(DnsQuery *q, DnsScope *s) {
 int dns_query_go(DnsQuery *q) {
         DnsScopeMatch found = DNS_SCOPE_NO;
         DnsScope *s, *first = NULL;
-        DnsQueryTransaction *t;
+        DnsTransaction *t;
         const char *name;
         Iterator i;
         int r;
 
         assert(q);
 
-        if (q->state != DNS_QUERY_NULL)
+        if (q->state != DNS_TRANSACTION_NULL)
                 return 0;
 
         assert(q->question);
@@ -752,21 +257,21 @@ int dns_query_go(DnsQuery *q) {
 
         r = dns_query_add_transaction_split(q, first);
         if (r < 0)
-                return r;
+                goto fail;
 
         LIST_FOREACH(scopes, s, first->scopes_next) {
                 DnsScopeMatch match;
 
                 match = dns_scope_good_domain(s, name);
                 if (match < 0)
-                        return match;
+                        goto fail;
 
                 if (match != found)
                         continue;
 
                 r = dns_query_add_transaction_split(q, s);
                 if (r < 0)
-                        return r;
+                        goto fail;
         }
 
         q->answer = dns_answer_unref(q->answer);
@@ -777,15 +282,17 @@ int dns_query_go(DnsQuery *q) {
         if (r < 0)
                 goto fail;
 
-        q->state = DNS_QUERY_PENDING;
+        q->state = DNS_TRANSACTION_PENDING;
         q->block_ready++;
 
+        /* Start the transactions that are not started yet */
         SET_FOREACH(t, q->transactions, i) {
-                if (t->state == DNS_QUERY_NULL) {
-                        r = dns_query_transaction_go(t);
-                        if (r < 0)
-                                goto fail;
-                }
+                if (t->state != DNS_TRANSACTION_NULL)
+                        continue;
+
+                r = dns_transaction_go(t);
+                if (r < 0)
+                        goto fail;
         }
 
         q->block_ready--;
@@ -799,8 +306,8 @@ fail:
 }
 
 void dns_query_ready(DnsQuery *q) {
-        DnsQueryTransaction *t;
-        DnsQueryState state = DNS_QUERY_NO_SERVERS;
+        DnsTransaction *t;
+        DnsTransactionState state = DNS_TRANSACTION_NO_SERVERS;
         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
         int rcode = 0;
         DnsScope *scope = NULL;
@@ -808,7 +315,7 @@ void dns_query_ready(DnsQuery *q) {
         Iterator i;
 
         assert(q);
-        assert(IN_SET(q->state, DNS_QUERY_NULL, DNS_QUERY_PENDING));
+        assert(IN_SET(q->state, DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING));
 
         /* Note that this call might invalidate the query. Callers
          * should hence not attempt to access the query or transaction
@@ -821,18 +328,18 @@ void dns_query_ready(DnsQuery *q) {
         SET_FOREACH(t, q->transactions, i) {
 
                 /* If we found a successful answer, ignore all answers from other scopes */
-                if (state == DNS_QUERY_SUCCESS && t->scope != scope)
+                if (state == DNS_TRANSACTION_SUCCESS && t->scope != scope)
                         continue;
 
                 /* One of the transactions is still going on, let's maybe wait for it */
-                if (IN_SET(t->state, DNS_QUERY_PENDING, DNS_QUERY_NULL)) {
+                if (IN_SET(t->state, DNS_TRANSACTION_PENDING, DNS_TRANSACTION_NULL)) {
                         pending = true;
                         continue;
                 }
 
                 /* One of the transactions is successful, let's use
                  * it, and copy its data out */
-                if (t->state == DNS_QUERY_SUCCESS) {
+                if (t->state == DNS_TRANSACTION_SUCCESS) {
                         DnsAnswer *a;
 
                         if (t->received) {
@@ -843,12 +350,12 @@ void dns_query_ready(DnsQuery *q) {
                                 a = t->cached;
                         }
 
-                        if (state == DNS_QUERY_SUCCESS) {
+                        if (state == DNS_TRANSACTION_SUCCESS) {
                                 DnsAnswer *merged;
 
                                 merged = dns_answer_merge(answer, a);
                                 if (!merged) {
-                                        dns_query_complete(q, DNS_QUERY_RESOURCES);
+                                        dns_query_complete(q, DNS_TRANSACTION_RESOURCES);
                                         return;
                                 }
 
@@ -860,14 +367,14 @@ void dns_query_ready(DnsQuery *q) {
                         }
 
                         scope = t->scope;
-                        state = DNS_QUERY_SUCCESS;
+                        state = DNS_TRANSACTION_SUCCESS;
                         continue;
                 }
 
                 /* One of the transactions has failed, let's see
                  * whether we find anything better, but if not, return
                  * its response data */
-                if (state != DNS_QUERY_SUCCESS && t->state == DNS_QUERY_FAILURE) {
+                if (state != DNS_TRANSACTION_SUCCESS && t->state == DNS_TRANSACTION_FAILURE) {
                         DnsAnswer *a;
 
                         if (t->received) {
@@ -882,11 +389,11 @@ void dns_query_ready(DnsQuery *q) {
                         answer = dns_answer_ref(a);
 
                         scope = t->scope;
-                        state = DNS_QUERY_FAILURE;
+                        state = DNS_TRANSACTION_FAILURE;
                         continue;
                 }
 
-                if (state == DNS_QUERY_NO_SERVERS && t->state != DNS_QUERY_NO_SERVERS)
+                if (state == DNS_TRANSACTION_NO_SERVERS && t->state != DNS_TRANSACTION_NO_SERVERS)
                         state = t->state;
         }
 
@@ -894,18 +401,18 @@ void dns_query_ready(DnsQuery *q) {
 
                 /* If so far we weren't successful, and there's
                  * something still pending, then wait for it */
-                if (state != DNS_QUERY_SUCCESS)
+                if (state != DNS_TRANSACTION_SUCCESS)
                         return;
 
                 /* If we already were successful, then only wait for
                  * other transactions on the same scope to finish. */
                 SET_FOREACH(t, q->transactions, i) {
-                        if (t->scope == scope && IN_SET(t->state, DNS_QUERY_PENDING, DNS_QUERY_NULL))
+                        if (t->scope == scope && IN_SET(t->state, DNS_TRANSACTION_PENDING, DNS_TRANSACTION_NULL))
                                 return;
                 }
         }
 
-        if (IN_SET(state, DNS_QUERY_SUCCESS, DNS_QUERY_FAILURE)) {
+        if (IN_SET(state, DNS_TRANSACTION_SUCCESS, DNS_TRANSACTION_FAILURE)) {
                 q->answer = dns_answer_ref(answer);
                 q->answer_rcode = rcode;
                 q->answer_ifindex = (scope && scope->link) ? scope->link->ifindex : 0;
@@ -934,21 +441,7 @@ int dns_query_cname_redirect(DnsQuery *q, const char *name) {
         q->n_cname_redirects++;
 
         dns_query_stop(q);
-        q->state = DNS_QUERY_NULL;
+        q->state = DNS_TRANSACTION_NULL;
 
         return 0;
 }
-
-static const char* const dns_query_state_table[_DNS_QUERY_STATE_MAX] = {
-        [DNS_QUERY_NULL] = "null",
-        [DNS_QUERY_PENDING] = "pending",
-        [DNS_QUERY_FAILURE] = "failure",
-        [DNS_QUERY_SUCCESS] = "success",
-        [DNS_QUERY_NO_SERVERS] = "no-servers",
-        [DNS_QUERY_TIMEOUT] = "timeout",
-        [DNS_QUERY_ATTEMPTS_MAX] = "attempts-max",
-        [DNS_QUERY_INVALID_REPLY] = "invalid-reply",
-        [DNS_QUERY_RESOURCES] = "resources",
-        [DNS_QUERY_ABORTED] = "aborted",
-};
-DEFINE_STRING_TABLE_LOOKUP(dns_query_state, DnsQueryState);
diff --git a/src/resolve/resolved-dns-query.h b/src/resolve/resolved-dns-query.h
index 67fe7f6e8f..7fc11dfbf4 100644
--- a/src/resolve/resolved-dns-query.h
+++ b/src/resolve/resolved-dns-query.h
@@ -28,63 +28,20 @@
 #include "set.h"
 
 typedef struct DnsQuery DnsQuery;
-typedef struct DnsQueryTransaction DnsQueryTransaction;
 
 #include "resolved.h"
 #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"
 #include "resolved-dns-stream.h"
-
-typedef enum DnsQueryState {
-        DNS_QUERY_NULL,
-        DNS_QUERY_PENDING,
-        DNS_QUERY_FAILURE,
-        DNS_QUERY_SUCCESS,
-        DNS_QUERY_NO_SERVERS,
-        DNS_QUERY_TIMEOUT,
-        DNS_QUERY_ATTEMPTS_MAX,
-        DNS_QUERY_INVALID_REPLY,
-        DNS_QUERY_RESOURCES,
-        DNS_QUERY_ABORTED,
-        _DNS_QUERY_STATE_MAX,
-        _DNS_QUERY_STATE_INVALID = -1
-} DnsQueryState;
-
-struct DnsQueryTransaction {
-        DnsScope *scope;
-
-        DnsQuestion *question;
-
-        DnsQueryState state;
-        uint16_t id;
-
-        DnsPacket *sent, *received;
-        DnsAnswer *cached;
-        int cached_rcode;
-
-        sd_event_source *timeout_event_source;
-        unsigned n_attempts;
-
-        /* TCP connection logic, if we need it */
-        DnsStream *stream;
-
-        /* 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_scope);
-};
+#include "resolved-dns-transaction.h"
 
 struct DnsQuery {
         Manager *manager;
         DnsQuestion *question;
 
-        DnsQueryState state;
+        DnsTransactionState state;
         unsigned n_cname_redirects;
 
         sd_event_source *timeout_event_source;
@@ -109,11 +66,6 @@ struct DnsQuery {
         LIST_FIELDS(DnsQuery, queries);
 };
 
-DnsQueryTransaction* dns_query_transaction_free(DnsQueryTransaction *t);
-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, DnsQuestion *question);
 DnsQuery *dns_query_free(DnsQuery *q);
 
@@ -122,7 +74,4 @@ void dns_query_ready(DnsQuery *q);
 
 int dns_query_cname_redirect(DnsQuery *q, const char *name);
 
-const char* dns_query_state_to_string(DnsQueryState p) _const_;
-DnsQueryState dns_query_state_from_string(const char *s) _pure_;
-
 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsQuery*, dns_query_free);
diff --git a/src/resolve/resolved-dns-scope.c b/src/resolve/resolved-dns-scope.c
index 4c53edb5a0..6061761723 100644
--- a/src/resolve/resolved-dns-scope.c
+++ b/src/resolve/resolved-dns-scope.c
@@ -28,8 +28,6 @@
 #include "resolved-dns-domain.h"
 #include "resolved-dns-scope.h"
 
-#define SEND_TIMEOUT_USEC (2*USEC_PER_SEC)
-
 int dns_scope_new(Manager *m, DnsScope **ret, Link *l, DnsProtocol protocol, int family) {
         DnsScope *s;
 
@@ -56,7 +54,7 @@ int dns_scope_new(Manager *m, DnsScope **ret, Link *l, DnsProtocol protocol, int
 }
 
 DnsScope* dns_scope_free(DnsScope *s) {
-        DnsQueryTransaction *t;
+        DnsTransaction *t;
 
         if (!s)
                 return NULL;
@@ -71,10 +69,10 @@ DnsScope* dns_scope_free(DnsScope *s) {
                  * freed while we still look at it */
 
                 t->block_gc++;
-                dns_query_transaction_complete(t, DNS_QUERY_ABORTED);
+                dns_transaction_complete(t, DNS_TRANSACTION_ABORTED);
                 t->block_gc--;
 
-                dns_query_transaction_free(t);
+                dns_transaction_free(t);
         }
 
         dns_cache_flush(&s->cache);
@@ -389,7 +387,16 @@ int dns_scope_good_dns_server(DnsScope *s, int family, const union in_addr_union
                 return !!manager_find_dns_server(s->manager, family, address);
 }
 
-static int dns_scope_make_reply_packet(DnsScope *s, uint16_t id, int rcode, DnsQuestion *q, DnsAnswer *answer, DnsAnswer *soa, DnsPacket **ret) {
+static int dns_scope_make_reply_packet(
+                DnsScope *s,
+                uint16_t id,
+                int rcode,
+                DnsQuestion *q,
+                DnsAnswer *answer,
+                DnsAnswer *soa,
+                bool tentative,
+                DnsPacket **ret) {
+
         _cleanup_(dns_packet_unrefp) DnsPacket *p = NULL;
         unsigned i;
         int r;
@@ -409,7 +416,7 @@ static int dns_scope_make_reply_packet(DnsScope *s, uint16_t id, int rcode, DnsQ
                                                               0 /* opcode */,
                                                               0 /* c */,
                                                               0 /* tc */,
-                                                              0 /* t */,
+                                                              tentative,
                                                               0 /* (ra) */,
                                                               0 /* (ad) */,
                                                               0 /* (cd) */,
@@ -454,6 +461,7 @@ static int dns_scope_make_reply_packet(DnsScope *s, uint16_t id, int rcode, DnsQ
 void dns_scope_process_query(DnsScope *s, DnsStream *stream, DnsPacket *p) {
         _cleanup_(dns_packet_unrefp) DnsPacket *reply = NULL;
         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL, *soa = NULL;
+        bool tentative = false;
         int r, fd;
 
         assert(s);
@@ -485,7 +493,7 @@ void dns_scope_process_query(DnsScope *s, DnsStream *stream, DnsPacket *p) {
                 return;
         }
 
-        r = dns_zone_lookup(&s->zone, p->question, &answer, &soa);
+        r = dns_zone_lookup(&s->zone, p->question, &answer, &soa, &tentative);
         if (r < 0) {
                 log_debug("Failed to lookup key: %s", strerror(-r));
                 return;
@@ -496,7 +504,7 @@ void dns_scope_process_query(DnsScope *s, DnsStream *stream, DnsPacket *p) {
         if (answer)
                 dns_answer_order_by_scope(answer, in_addr_is_link_local(p->family, &p->sender) > 0);
 
-        r = dns_scope_make_reply_packet(s, DNS_PACKET_ID(p), DNS_RCODE_SUCCESS, p->question, answer, soa, &reply);
+        r = dns_scope_make_reply_packet(s, DNS_PACKET_ID(p), DNS_RCODE_SUCCESS, p->question, answer, soa, tentative, &reply);
         if (r < 0) {
                 log_debug("Failed to build reply packet: %s", strerror(-r));
                 return;
@@ -526,3 +534,19 @@ void dns_scope_process_query(DnsScope *s, DnsStream *stream, DnsPacket *p) {
                 return;
         }
 }
+
+DnsTransaction *dns_scope_find_transaction(DnsScope *scope, DnsQuestion *question) {
+        DnsTransaction *t;
+
+        assert(scope);
+        assert(question);
+
+        /* Try to find an ongoing transaction that is a equal or a
+         * superset of the specified question */
+
+        LIST_FOREACH(transactions_by_scope, t, scope->transactions)
+                if (dns_question_is_superset(t->question, question) > 0)
+                        return t;
+
+        return NULL;
+}
diff --git a/src/resolve/resolved-dns-scope.h b/src/resolve/resolved-dns-scope.h
index 639c4b4e86..67a6ba2901 100644
--- a/src/resolve/resolved-dns-scope.h
+++ b/src/resolve/resolved-dns-scope.h
@@ -55,7 +55,7 @@ struct DnsScope {
         DnsCache cache;
         DnsZone zone;
 
-        LIST_HEAD(DnsQueryTransaction, transactions);
+        LIST_HEAD(DnsTransaction, transactions);
 
         LIST_FIELDS(DnsScope, scopes);
 };
@@ -76,3 +76,5 @@ void dns_scope_next_dns_server(DnsScope *s);
 int dns_scope_llmnr_membership(DnsScope *s, bool b);
 
 void dns_scope_process_query(DnsScope *s, DnsStream *stream, DnsPacket *p);
+
+DnsTransaction *dns_scope_find_transaction(DnsScope *scope, DnsQuestion *question);
diff --git a/src/resolve/resolved-dns-stream.h b/src/resolve/resolved-dns-stream.h
index 5509f7528b..fc24bb670e 100644
--- a/src/resolve/resolved-dns-stream.h
+++ b/src/resolve/resolved-dns-stream.h
@@ -26,6 +26,8 @@
 typedef struct DnsStream DnsStream;
 
 #include "resolved.h"
+#include "resolved-dns-packet.h"
+#include "resolved-dns-transaction.h"
 
 struct DnsStream {
         Manager *manager;
@@ -51,7 +53,7 @@ struct DnsStream {
         int (*on_packet)(DnsStream *s);
         int (*complete)(DnsStream *s, int error);
 
-        DnsQueryTransaction *transaction;
+        DnsTransaction *transaction;
 
         LIST_FIELDS(DnsStream, streams);
 };
diff --git a/src/resolve/resolved-dns-transaction.c b/src/resolve/resolved-dns-transaction.c
new file mode 100644
index 0000000000..92f7e4c5b1
--- /dev/null
+++ b/src/resolve/resolved-dns-transaction.c
@@ -0,0 +1,538 @@
+/*-*- 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 "af-list.h"
+
+#include "resolved-dns-transaction.h"
+
+DnsTransaction* dns_transaction_free(DnsTransaction *t) {
+        DnsQuery *q;
+        DnsZoneItem *i;
+
+        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_answer_unref(t->cached);
+
+        dns_stream_free(t->stream);
+
+        if (t->scope) {
+                LIST_REMOVE(transactions_by_scope, t->scope->transactions, t);
+
+                if (t->id != 0)
+                        hashmap_remove(t->scope->manager->dns_transactions, UINT_TO_PTR(t->id));
+        }
+
+        while ((q = set_steal_first(t->queries)))
+                set_remove(q->transactions, t);
+        set_free(t->queries);
+
+        while ((i = set_steal_first(t->zone_items)))
+                i->probe_transaction = NULL;
+        set_free(t->zone_items);
+
+        free(t);
+        return NULL;
+}
+
+DEFINE_TRIVIAL_CLEANUP_FUNC(DnsTransaction*, dns_transaction_free);
+
+void dns_transaction_gc(DnsTransaction *t) {
+        assert(t);
+
+        if (t->block_gc > 0)
+                return;
+
+        if (set_isempty(t->queries) && set_isempty(t->zone_items))
+                dns_transaction_free(t);
+}
+
+int dns_transaction_new(DnsTransaction **ret, DnsScope *s, DnsQuestion *q) {
+        _cleanup_(dns_transaction_freep) DnsTransaction *t = NULL;
+        int r;
+
+        assert(ret);
+        assert(s);
+        assert(q);
+
+        r = hashmap_ensure_allocated(&s->manager->dns_transactions, NULL, NULL);
+        if (r < 0)
+                return r;
+
+        t = new0(DnsTransaction, 1);
+        if (!t)
+                return -ENOMEM;
+
+        t->question = dns_question_ref(q);
+
+        do
+                random_bytes(&t->id, sizeof(t->id));
+        while (t->id == 0 ||
+               hashmap_get(s->manager->dns_transactions, UINT_TO_PTR(t->id)));
+
+        r = hashmap_put(s->manager->dns_transactions, UINT_TO_PTR(t->id), t);
+        if (r < 0) {
+                t->id = 0;
+                return r;
+        }
+
+        LIST_PREPEND(transactions_by_scope, s->transactions, t);
+        t->scope = s;
+
+        if (ret)
+                *ret = t;
+
+        t = NULL;
+
+        return 0;
+}
+
+static void dns_transaction_stop(DnsTransaction *t) {
+        assert(t);
+
+        t->timeout_event_source = sd_event_source_unref(t->timeout_event_source);
+        t->stream = dns_stream_free(t->stream);
+}
+
+static void dns_transaction_tentative(DnsTransaction *t, DnsPacket *p) {
+        DnsZoneItem *z;
+        Iterator i;
+
+        assert(t);
+        assert(p);
+
+        if (manager_our_packet(t->scope->manager, p) != 0)
+                return;
+
+        log_debug("Transaction on scope %s on %s/%s got tentative packet",
+                  dns_protocol_to_string(t->scope->protocol),
+                  t->scope->link ? t->scope->link->name : "*",
+                  t->scope->family == AF_UNSPEC ? "*" : af_to_name(t->scope->family));
+
+        t->block_gc++;
+        SET_FOREACH(z, t->zone_items, i)
+                dns_zone_item_conflict(z);
+        t->block_gc--;
+
+        dns_transaction_gc(t);
+}
+
+void dns_transaction_complete(DnsTransaction *t, DnsTransactionState state) {
+        DnsQuery *q;
+        DnsZoneItem *z;
+        Iterator i;
+
+        assert(t);
+        assert(!IN_SET(state, DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING));
+        assert(IN_SET(t->state, DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING));
+
+        /* Note that this call might invalidate the query. Callers
+         * should hence not attempt to access the query or transaction
+         * after calling this function. */
+
+        log_debug("Transaction on scope %s on %s/%s now complete with <%s>",
+                  dns_protocol_to_string(t->scope->protocol),
+                  t->scope->link ? t->scope->link->name : "*",
+                  t->scope->family == AF_UNSPEC ? "*" : af_to_name(t->scope->family),
+                  dns_transaction_state_to_string(state));
+
+        t->state = state;
+
+        dns_transaction_stop(t);
+
+        /* Notify all queries that are interested, but make sure the
+         * transaction isn't freed while we are still looking at it */
+        t->block_gc++;
+        SET_FOREACH(q, t->queries, i)
+                dns_query_ready(q);
+        SET_FOREACH(z, t->zone_items, i)
+                dns_zone_item_ready(z);
+        t->block_gc--;
+
+        dns_transaction_gc(t);
+}
+
+static int on_stream_complete(DnsStream *s, int error) {
+        _cleanup_(dns_packet_unrefp) DnsPacket *p = NULL;
+        DnsTransaction *t;
+
+        assert(s);
+        assert(s->transaction);
+
+        /* Copy the data we care about out of the stream before we
+         * destroy it. */
+        t = s->transaction;
+        p = dns_packet_ref(s->read_packet);
+
+        t->stream = dns_stream_free(t->stream);
+
+        if (error != 0) {
+                dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
+                return 0;
+        }
+
+        t->block_gc++;
+        dns_transaction_process_reply(t, p);
+        t->block_gc--;
+
+        /* If the response wasn't useful, then complete the transition now */
+        if (t->state == DNS_TRANSACTION_PENDING)
+                dns_transaction_complete(t, DNS_TRANSACTION_INVALID_REPLY);
+
+        return 0;
+}
+
+static int dns_transaction_open_tcp(DnsTransaction *t) {
+        _cleanup_close_ int fd = -1;
+        int r;
+
+        assert(t);
+
+        if (t->stream)
+                return 0;
+
+        if (t->scope->protocol == DNS_PROTOCOL_DNS)
+                fd = dns_scope_tcp_socket(t->scope, AF_UNSPEC, NULL, 53);
+        else if (t->scope->protocol == DNS_PROTOCOL_LLMNR) {
+
+                /* When we already received a query to this (but it was truncated), send to its sender address */
+                if (t->received)
+                        fd = dns_scope_tcp_socket(t->scope, t->received->family, &t->received->sender, t->received->sender_port);
+                else {
+                        union in_addr_union address;
+                        int family;
+
+                        /* Otherwise, try to talk to the owner of a
+                         * the IP address, in case this is a reverse
+                         * PTR lookup */
+                        r = dns_question_extract_reverse_address(t->question, &family, &address);
+                        if (r < 0)
+                                return r;
+                        if (r == 0)
+                                return -EINVAL;
+
+                        fd = dns_scope_tcp_socket(t->scope, family, &address, 5355);
+                }
+        } else
+                return -EAFNOSUPPORT;
+
+        if (fd < 0)
+                return fd;
+
+        r = dns_stream_new(t->scope->manager, &t->stream, t->scope->protocol, fd);
+        if (r < 0)
+                return r;
+
+        fd = -1;
+
+        r = dns_stream_write_packet(t->stream, t->sent);
+        if (r < 0) {
+                t->stream = dns_stream_free(t->stream);
+                return r;
+        }
+
+        t->received = dns_packet_unref(t->received);
+        t->stream->complete = on_stream_complete;
+        t->stream->transaction = t;
+
+        /* The interface index is difficult to determine if we are
+         * connecting to the local host, hence fill this in right away
+         * instead of determining it from the socket */
+        if (t->scope->link)
+                t->stream->ifindex = t->scope->link->ifindex;
+
+        return 0;
+}
+
+void dns_transaction_process_reply(DnsTransaction *t, DnsPacket *p) {
+        int r;
+
+        assert(t);
+        assert(p);
+        assert(t->state == DNS_TRANSACTION_PENDING);
+
+        /* Note that this call might invalidate the query. Callers
+         * should hence not attempt to access the query or transaction
+         * after calling this function. */
+
+        if (t->scope->protocol == DNS_PROTOCOL_LLMNR) {
+                assert(t->scope->link);
+
+                /* For LLMNR we will not accept any packets from other
+                 * interfaces */
+
+                if (p->ifindex != t->scope->link->ifindex)
+                        return;
+
+                if (p->family != t->scope->family)
+                        return;
+
+                /* Tentative packets are not full responses but still
+                 * useful for identifying uniqueness conflicts during
+                 * probing. */
+                if (DNS_PACKET_T(p)) {
+                        dns_transaction_tentative(t, p);
+                        return;
+                }
+        }
+
+        if (t->scope->protocol == DNS_PROTOCOL_DNS) {
+
+                /* For DNS we are fine with accepting packets on any
+                 * interface, but the source IP address must be one of
+                 * a valid DNS server */
+
+                if (!dns_scope_good_dns_server(t->scope, p->family, &p->sender))
+                        return;
+
+                if (p->sender_port != 53)
+                        return;
+        }
+
+        if (t->received != p) {
+                dns_packet_unref(t->received);
+                t->received = dns_packet_ref(p);
+        }
+
+        if (p->ipproto == IPPROTO_TCP) {
+                if (DNS_PACKET_TC(p)) {
+                        /* Truncated via TCP? Somebody must be fucking with us */
+                        dns_transaction_complete(t, DNS_TRANSACTION_INVALID_REPLY);
+                        return;
+                }
+
+                if (DNS_PACKET_ID(p) != t->id) {
+                        /* Not the reply to our query? Somebody must be fucking with us */
+                        dns_transaction_complete(t, DNS_TRANSACTION_INVALID_REPLY);
+                        return;
+                }
+        }
+
+        if (DNS_PACKET_TC(p)) {
+                /* Response was truncated, let's try again with good old TCP */
+                r = dns_transaction_open_tcp(t);
+                if (r == -ESRCH) {
+                        /* No servers found? Damn! */
+                        dns_transaction_complete(t, DNS_TRANSACTION_NO_SERVERS);
+                        return;
+                }
+                if (r < 0) {
+                        /* On LLMNR, if we cannot connect to the host,
+                         * we immediately give up */
+                        if (t->scope->protocol == DNS_PROTOCOL_LLMNR) {
+                                dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
+                                return;
+                        }
+
+                        /* On DNS, couldn't send? Try immediately again, with a new server */
+                        dns_scope_next_dns_server(t->scope);
+
+                        r = dns_transaction_go(t);
+                        if (r < 0) {
+                                dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
+                                return;
+                        }
+
+                        return;
+                }
+        }
+
+        /* Parse and update the cache */
+        r = dns_packet_extract(p);
+        if (r < 0) {
+                dns_transaction_complete(t, DNS_TRANSACTION_INVALID_REPLY);
+                return;
+        }
+
+        /* According to RFC 4795, section 2.9. only the RRs from the answer section shall be cached */
+        dns_cache_put(&t->scope->cache, p->question, DNS_PACKET_RCODE(p), p->answer, DNS_PACKET_ANCOUNT(p), 0);
+
+        if (DNS_PACKET_RCODE(p) == DNS_RCODE_SUCCESS)
+                dns_transaction_complete(t, DNS_TRANSACTION_SUCCESS);
+        else
+                dns_transaction_complete(t, DNS_TRANSACTION_FAILURE);
+}
+
+static int on_transaction_timeout(sd_event_source *s, usec_t usec, void *userdata) {
+        DnsTransaction *t = userdata;
+        int r;
+
+        assert(s);
+        assert(t);
+
+        /* Timeout reached? Try again, with a new server */
+        dns_scope_next_dns_server(t->scope);
+
+        r = dns_transaction_go(t);
+        if (r < 0)
+                dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
+
+        return 0;
+}
+
+static int dns_transaction_make_packet(DnsTransaction *t) {
+        _cleanup_(dns_packet_unrefp) DnsPacket *p = NULL;
+        unsigned n, added = 0;
+        int r;
+
+        assert(t);
+
+        if (t->sent)
+                return 0;
+
+        r = dns_packet_new_query(&p, t->scope->protocol, 0);
+        if (r < 0)
+                return r;
+
+        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->question->keys[n], NULL);
+                if (r < 0)
+                        return r;
+
+                added++;
+        }
+
+        if (added <= 0)
+                return -EDOM;
+
+        DNS_PACKET_HEADER(p)->qdcount = htobe16(added);
+        DNS_PACKET_HEADER(p)->id = t->id;
+
+        t->sent = p;
+        p = NULL;
+
+        return 0;
+}
+
+int dns_transaction_go(DnsTransaction *t) {
+        bool had_stream;
+        int r;
+
+        assert(t);
+
+        had_stream = !!t->stream;
+
+        dns_transaction_stop(t);
+
+        log_debug("Beginning transaction on scope %s on %s/%s",
+                  dns_protocol_to_string(t->scope->protocol),
+                  t->scope->link ? t->scope->link->name : "*",
+                  t->scope->family == AF_UNSPEC ? "*" : af_to_name(t->scope->family));
+
+        if (t->n_attempts >= TRANSACTION_ATTEMPTS_MAX(t->scope->protocol)) {
+                dns_transaction_complete(t, DNS_TRANSACTION_ATTEMPTS_MAX_REACHED);
+                return 0;
+        }
+
+        if (t->scope->protocol == DNS_PROTOCOL_LLMNR && had_stream) {
+                /* If we already tried via a stream, then we don't
+                 * retry on LLMNR. See RFC 4795, Section 2.7. */
+                dns_transaction_complete(t, DNS_TRANSACTION_ATTEMPTS_MAX_REACHED);
+                return 0;
+        }
+
+        t->n_attempts++;
+        t->received = dns_packet_unref(t->received);
+        t->cached = dns_answer_unref(t->cached);
+        t->cached_rcode = 0;
+
+        /* First, let's try the cache */
+        dns_cache_prune(&t->scope->cache);
+        r = dns_cache_lookup(&t->scope->cache, t->question, &t->cached_rcode, &t->cached);
+        if (r < 0)
+                return r;
+        if (r > 0) {
+                if (t->cached_rcode == DNS_RCODE_SUCCESS)
+                        dns_transaction_complete(t, DNS_TRANSACTION_SUCCESS);
+                else
+                        dns_transaction_complete(t, DNS_TRANSACTION_FAILURE);
+                return 0;
+        }
+
+        /* Otherwise, we need to ask the network */
+        r = dns_transaction_make_packet(t);
+        if (r == -EDOM) {
+                /* Not the right request to make on this network?
+                 * (i.e. an A request made on IPv6 or an AAAA request
+                 * made on IPv4, on LLMNR or mDNS.) */
+                dns_transaction_complete(t, DNS_TRANSACTION_NO_SERVERS);
+                return 0;
+        }
+        if (r < 0)
+                return r;
+
+        if (t->scope->protocol == DNS_PROTOCOL_LLMNR &&
+            (dns_question_endswith(t->question, "in-addr.arpa") > 0 ||
+             dns_question_endswith(t->question, "ip6.arpa") > 0)) {
+
+                /* RFC 4795, Section 2.4. says reverse lookups shall
+                 * always be made via TCP on LLMNR */
+                r = dns_transaction_open_tcp(t);
+        } else {
+                /* 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_transaction_open_tcp(t);
+        }
+        if (r == -ESRCH) {
+                /* No servers to send this to? */
+                dns_transaction_complete(t, DNS_TRANSACTION_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_transaction_go(t);
+        }
+
+        r = sd_event_add_time(t->scope->manager->event, &t->timeout_event_source, CLOCK_MONOTONIC, now(CLOCK_MONOTONIC) + TRANSACTION_TIMEOUT_USEC(t->scope->protocol), 0, on_transaction_timeout, t);
+        if (r < 0)
+                return r;
+
+        t->state = DNS_TRANSACTION_PENDING;
+        return 1;
+}
+
+static const char* const dns_transaction_state_table[_DNS_TRANSACTION_STATE_MAX] = {
+        [DNS_TRANSACTION_NULL] = "null",
+        [DNS_TRANSACTION_PENDING] = "pending",
+        [DNS_TRANSACTION_FAILURE] = "failure",
+        [DNS_TRANSACTION_SUCCESS] = "success",
+        [DNS_TRANSACTION_NO_SERVERS] = "no-servers",
+        [DNS_TRANSACTION_TIMEOUT] = "timeout",
+        [DNS_TRANSACTION_ATTEMPTS_MAX_REACHED] = "attempts-max-reached",
+        [DNS_TRANSACTION_INVALID_REPLY] = "invalid-reply",
+        [DNS_TRANSACTION_RESOURCES] = "resources",
+        [DNS_TRANSACTION_ABORTED] = "aborted",
+};
+DEFINE_STRING_TABLE_LOOKUP(dns_transaction_state, DnsTransactionState);
diff --git a/src/resolve/resolved-dns-transaction.h b/src/resolve/resolved-dns-transaction.h
new file mode 100644
index 0000000000..d825b3ec85
--- /dev/null
+++ b/src/resolve/resolved-dns-transaction.h
@@ -0,0 +1,108 @@
+/*-*- 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 DnsTransaction DnsTransaction;
+typedef enum DnsTransactionState DnsTransactionState;
+
+enum DnsTransactionState {
+        DNS_TRANSACTION_NULL,
+        DNS_TRANSACTION_PENDING,
+        DNS_TRANSACTION_FAILURE,
+        DNS_TRANSACTION_SUCCESS,
+        DNS_TRANSACTION_NO_SERVERS,
+        DNS_TRANSACTION_TIMEOUT,
+        DNS_TRANSACTION_ATTEMPTS_MAX_REACHED,
+        DNS_TRANSACTION_INVALID_REPLY,
+        DNS_TRANSACTION_RESOURCES,
+        DNS_TRANSACTION_ABORTED,
+        _DNS_TRANSACTION_STATE_MAX,
+        _DNS_TRANSACTION_STATE_INVALID = -1
+};
+
+#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"
+#include "resolved-dns-stream.h"
+
+struct DnsTransaction {
+        DnsScope *scope;
+
+        DnsQuestion *question;
+
+        DnsTransactionState state;
+        uint16_t id;
+
+        DnsPacket *sent, *received;
+        DnsAnswer *cached;
+        int cached_rcode;
+
+        sd_event_source *timeout_event_source;
+        unsigned n_attempts;
+
+        /* TCP connection logic, if we need it */
+        DnsStream *stream;
+
+        /* Queries this transaction is referenced by and that shall be
+         * notified about this specific transaction completing. */
+        Set *queries;
+
+        /* Zone items this transaction is referenced by and that shall
+         * be notified about completion. */
+        Set *zone_items;
+
+        unsigned block_gc;
+
+        LIST_FIELDS(DnsTransaction, transactions_by_scope);
+};
+
+int dns_transaction_new(DnsTransaction **ret, DnsScope *s, DnsQuestion *q);
+DnsTransaction* dns_transaction_free(DnsTransaction *t);
+
+void dns_transaction_gc(DnsTransaction *t);
+int dns_transaction_go(DnsTransaction *t);
+
+void dns_transaction_process_reply(DnsTransaction *t, DnsPacket *p);
+void dns_transaction_complete(DnsTransaction *t, DnsTransactionState state);
+
+const char* dns_transaction_state_to_string(DnsTransactionState p) _const_;
+DnsTransactionState dns_transaction_state_from_string(const char *s) _pure_;
+
+/* After how much time to repeat classic DNS requests */
+#define DNS_TRANSACTION_TIMEOUT_USEC (5 * USEC_PER_SEC)
+
+/* After how much time to repeat LLMNR requests, see RFC 4795 Section 7 */
+#define LLMNR_TRANSACTION_TIMEOUT_USEC (1 * USEC_PER_SEC)
+
+/* LLMNR Jitter interval, see RFC 4795 Section 7 */
+#define LLMNR_TRANSACTION_JITTER_INTERVAL_USEC (100 * USEC_PER_MSEC)
+
+/* Maximum attempts to send DNS requests, across all DNS servers */
+#define DNS_TRANSACTION_ATTEMPTS_MAX 8
+
+/* Maximum attempts to send LLMNR requests, see RFC 4795 Section 2.7 */
+#define LLMNR_TRANSACTION_ATTEMPTS_MAX 3
+
+#define TRANSACTION_TIMEOUT_USEC(p) (p == DNS_PROTOCOL_LLMNR ? LLMNR_TRANSACTION_TIMEOUT_USEC : DNS_TRANSACTION_TIMEOUT_USEC)
+#define TRANSACTION_ATTEMPTS_MAX(p) (p == DNS_PROTOCOL_LLMNR ? LLMNR_TRANSACTION_ATTEMPTS_MAX : DNS_TRANSACTION_ATTEMPTS_MAX)
diff --git a/src/resolve/resolved-dns-zone.c b/src/resolve/resolved-dns-zone.c
index 99ea420ff4..b577fd6cc6 100644
--- a/src/resolve/resolved-dns-zone.c
+++ b/src/resolve/resolved-dns-zone.c
@@ -28,20 +28,27 @@
 /* Never allow more than 1K entries */
 #define ZONE_MAX 1024
 
-typedef struct DnsZoneItem DnsZoneItem;
+static void dns_zone_item_probe_stop(DnsZoneItem *i) {
+        DnsTransaction *t;
+        assert(i);
 
-struct DnsZoneItem {
-        DnsResourceRecord *rr;
-        bool verified;
-        LIST_FIELDS(DnsZoneItem, by_key);
-        LIST_FIELDS(DnsZoneItem, by_name);
-};
+        if (!i->probe_transaction)
+                return;
+
+        t = i->probe_transaction;
+        i->probe_transaction = NULL;
+
+        set_remove(t->zone_items, i);
+        dns_transaction_gc(t);
+}
 
 static void dns_zone_item_free(DnsZoneItem *i) {
         if (!i)
                 return;
 
+        dns_zone_item_probe_stop(i);
         dns_resource_record_unref(i->rr);
+
         free(i);
 }
 
@@ -157,12 +164,74 @@ static int dns_zone_link_item(DnsZone *z, DnsZoneItem *i) {
         return 0;
 }
 
-int dns_zone_put(DnsZone *z, DnsResourceRecord *rr) {
+static int dns_zone_item_probe_start(DnsZoneItem *i)  {
+        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
+        _cleanup_(dns_question_unrefp) DnsQuestion *question = NULL;
+        DnsTransaction *t;
+        int r;
+
+        assert(i);
+
+        if (i->probe_transaction)
+                return 0;
+
+        key = dns_resource_key_new(i->rr->key->class, DNS_TYPE_ANY, DNS_RESOURCE_KEY_NAME(i->rr->key));
+        if (!key)
+                return -ENOMEM;
+
+        question = dns_question_new(1);
+        if (!question)
+                return -ENOMEM;
+
+        r = dns_question_add(question, key);
+        if (r < 0)
+                return r;
+
+        t = dns_scope_find_transaction(i->scope, question);
+        if (!t) {
+                r = dns_transaction_new(&t, i->scope, question);
+                if (r < 0)
+                        return r;
+        }
+
+        r = set_ensure_allocated(&t->zone_items, NULL, NULL);
+        if (r < 0)
+                goto gc;
+
+        r = set_put(t->zone_items, i);
+        if (r < 0)
+                goto gc;
+
+        i->probe_transaction = t;
+
+        if (t->state == DNS_TRANSACTION_NULL) {
+
+                i->block_ready++;
+                r = dns_transaction_go(t);
+                i->block_ready--;
+
+                if (r < 0) {
+                        dns_zone_item_probe_stop(i);
+                        return r;
+                }
+        }
+
+        dns_zone_item_ready(i);
+
+        return 0;
+
+gc:
+        dns_transaction_gc(t);
+        return r;
+}
+
+int dns_zone_put(DnsZone *z, DnsScope *s, DnsResourceRecord *rr, bool probe) {
         _cleanup_(dns_zone_item_freep) DnsZoneItem *i = NULL;
         DnsZoneItem *existing;
         int r;
 
         assert(z);
+        assert(s);
         assert(rr);
 
         if (rr->key->class == DNS_CLASS_ANY)
@@ -182,19 +251,34 @@ int dns_zone_put(DnsZone *z, DnsResourceRecord *rr) {
         if (!i)
                 return -ENOMEM;
 
+        i->scope = s;
         i->rr = dns_resource_record_ref(rr);
+        i->probing_enabled = probe;
 
         r = dns_zone_link_item(z, i);
         if (r < 0)
                 return r;
 
+        if (probe) {
+                r = dns_zone_item_probe_start(i);
+                if (r < 0) {
+                        dns_zone_item_remove_and_free(z, i);
+                        i = NULL;
+                        return r;
+                }
+
+                i->state = DNS_ZONE_ITEM_PROBING;
+        } else
+                i->state = DNS_ZONE_ITEM_ESTABLISHED;
+
         i = NULL;
         return 0;
 }
 
-int dns_zone_lookup(DnsZone *z, DnsQuestion *q, DnsAnswer **ret_answer, DnsAnswer **ret_soa) {
+int dns_zone_lookup(DnsZone *z, DnsQuestion *q, DnsAnswer **ret_answer, DnsAnswer **ret_soa, bool *ret_tentative) {
         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL, *soa = NULL;
         unsigned i, n_answer = 0, n_soa = 0;
+        bool tentative = true;
         int r;
 
         assert(z);
@@ -205,40 +289,70 @@ int dns_zone_lookup(DnsZone *z, DnsQuestion *q, DnsAnswer **ret_answer, DnsAnswe
         if (q->n_keys <= 0) {
                 *ret_answer = NULL;
                 *ret_soa = NULL;
+
+                if (ret_tentative)
+                        *ret_tentative = false;
+
                 return 0;
         }
 
         /* First iteration, count what we have */
         for (i = 0; i < q->n_keys; i++) {
-                DnsZoneItem *j;
+                DnsZoneItem *j, *first;
 
                 if (q->keys[i]->type == DNS_TYPE_ANY ||
                     q->keys[i]->class == DNS_CLASS_ANY) {
+                        bool found = false, added = false;
                         int k;
 
                         /* If this is a generic match, then we have to
                          * go through the list by the name and look
                          * for everything manually */
 
-                        j = hashmap_get(z->by_name, DNS_RESOURCE_KEY_NAME(q->keys[i]));
-                        LIST_FOREACH(by_name, j, j) {
+                        first = hashmap_get(z->by_name, DNS_RESOURCE_KEY_NAME(q->keys[i]));
+                        LIST_FOREACH(by_name, j, first) {
+                                if (!IN_SET(j->state, DNS_ZONE_ITEM_PROBING, DNS_ZONE_ITEM_ESTABLISHED, DNS_ZONE_ITEM_VERIFYING))
+                                        continue;
+
+                                found = true;
+
                                 k = dns_resource_key_match_rr(q->keys[i], j->rr);
                                 if (k < 0)
                                         return k;
-                                if (k == 0)
-                                        n_soa++;
-                                else
+                                if (k > 0) {
                                         n_answer++;
+                                        added = true;
+                                }
+
                         }
 
+                        if (found && !added)
+                                n_soa++;
+
                 } else {
-                        j = hashmap_get(z->by_key, q->keys[i]);
-                        if (j) {
-                                LIST_FOREACH(by_key, j, j)
-                                        n_answer++;
-                        } else {
-                                if (hashmap_get(z->by_name, DNS_RESOURCE_KEY_NAME(q->keys[i])))
-                                        n_soa ++;
+                        bool found = false;
+
+                        /* If this is a specific match, then look for
+                         * the right key immediately */
+
+                        first = hashmap_get(z->by_key, q->keys[i]);
+                        LIST_FOREACH(by_key, j, first) {
+                                if (!IN_SET(j->state, DNS_ZONE_ITEM_PROBING, DNS_ZONE_ITEM_ESTABLISHED, DNS_ZONE_ITEM_VERIFYING))
+                                        continue;
+
+                                found = true;
+                                n_answer++;
+                        }
+
+                        if (!found) {
+                                first = hashmap_get(z->by_name, DNS_RESOURCE_KEY_NAME(q->keys[i]));
+                                LIST_FOREACH(by_name, j, first) {
+                                        if (!IN_SET(j->state, DNS_ZONE_ITEM_PROBING, DNS_ZONE_ITEM_ESTABLISHED, DNS_ZONE_ITEM_VERIFYING))
+                                                continue;
+
+                                        n_soa++;
+                                        break;
+                                }
                         }
                 }
         }
@@ -246,6 +360,10 @@ int dns_zone_lookup(DnsZone *z, DnsQuestion *q, DnsAnswer **ret_answer, DnsAnswe
         if (n_answer <= 0 && n_soa <= 0) {
                 *ret_answer = NULL;
                 *ret_soa = NULL;
+
+                if (ret_tentative)
+                        *ret_tentative = false;
+
                 return 0;
         }
 
@@ -263,35 +381,73 @@ int dns_zone_lookup(DnsZone *z, DnsQuestion *q, DnsAnswer **ret_answer, DnsAnswe
 
         /* Second iteration, actually add the RRs to the answers */
         for (i = 0; i < q->n_keys; i++) {
-                DnsZoneItem *j;
+                DnsZoneItem *j, *first;
 
                 if (q->keys[i]->type == DNS_TYPE_ANY ||
                     q->keys[i]->class == DNS_CLASS_ANY) {
+                        bool found = false, added = false;
                         int k;
 
-                        j = hashmap_get(z->by_name, DNS_RESOURCE_KEY_NAME(q->keys[i]));
-                        LIST_FOREACH(by_name, j, j) {
+                        first = hashmap_get(z->by_name, DNS_RESOURCE_KEY_NAME(q->keys[i]));
+                        LIST_FOREACH(by_name, j, first) {
+                                if (!IN_SET(j->state, DNS_ZONE_ITEM_PROBING, DNS_ZONE_ITEM_ESTABLISHED, DNS_ZONE_ITEM_VERIFYING))
+                                        continue;
+
+                                found = true;
+
+                                if (j->state != DNS_ZONE_ITEM_PROBING)
+                                        tentative = false;
+
                                 k = dns_resource_key_match_rr(q->keys[i], j->rr);
                                 if (k < 0)
                                         return k;
-                                if (k == 0)
-                                        r = dns_answer_add_soa(soa, DNS_RESOURCE_KEY_NAME(q->keys[i]), LLMNR_DEFAULT_TTL);
-                                else
+                                if (k > 0) {
                                         r = dns_answer_add(answer, j->rr);
+                                        if (r < 0)
+                                                return r;
+
+                                        added = true;
+                                }
+                        }
+
+                        if (found && !added) {
+                                r = dns_answer_add_soa(soa, DNS_RESOURCE_KEY_NAME(q->keys[i]), LLMNR_DEFAULT_TTL);
                                 if (r < 0)
                                         return r;
                         }
                 } else {
+                        bool found = false;
 
-                        j = hashmap_get(z->by_key, q->keys[i]);
-                        if (j) {
-                                LIST_FOREACH(by_key, j, j) {
-                                        r = dns_answer_add(answer, j->rr);
-                                        if (r < 0)
-                                                return r;
+                        first = hashmap_get(z->by_key, q->keys[i]);
+                        LIST_FOREACH(by_key, j, first) {
+                                if (!IN_SET(j->state, DNS_ZONE_ITEM_PROBING, DNS_ZONE_ITEM_ESTABLISHED, DNS_ZONE_ITEM_VERIFYING))
+                                        continue;
+
+                                found = true;
+
+                                if (j->state != DNS_ZONE_ITEM_PROBING)
+                                        tentative = false;
+
+                                r = dns_answer_add(answer, j->rr);
+                                if (r < 0)
+                                        return r;
+                        }
+
+                        if (!found) {
+                                bool add_soa = false;
+
+                                first = hashmap_get(z->by_name, DNS_RESOURCE_KEY_NAME(q->keys[i]));
+                                LIST_FOREACH(by_name, j, first) {
+                                        if (!IN_SET(j->state, DNS_ZONE_ITEM_PROBING, DNS_ZONE_ITEM_ESTABLISHED, DNS_ZONE_ITEM_VERIFYING))
+                                                continue;
+
+                                        if (j->state != DNS_ZONE_ITEM_PROBING)
+                                                tentative = false;
+
+                                        add_soa = true;
                                 }
-                        } else {
-                                if (hashmap_get(z->by_name, DNS_RESOURCE_KEY_NAME(q->keys[i]))) {
+
+                                if (add_soa) {
                                         r = dns_answer_add_soa(soa, DNS_RESOURCE_KEY_NAME(q->keys[i]), LLMNR_DEFAULT_TTL);
                                         if (r < 0)
                                                 return r;
@@ -306,5 +462,47 @@ int dns_zone_lookup(DnsZone *z, DnsQuestion *q, DnsAnswer **ret_answer, DnsAnswe
         *ret_soa = soa;
         soa = NULL;
 
+        if (ret_tentative)
+                *ret_tentative = tentative;
+
         return 1;
 }
+
+void dns_zone_item_conflict(DnsZoneItem *i) {
+        _cleanup_free_ char *pretty = NULL;
+
+        assert(i);
+
+        dns_resource_record_to_string(i->rr, &pretty);
+        log_info("Detected conflict on %s", strna(pretty));
+
+        /* Withdraw the conflict item */
+        i->state = DNS_ZONE_ITEM_WITHDRAWN;
+
+        /* Maybe change the hostname */
+        if (dns_name_equal(i->scope->manager->hostname, DNS_RESOURCE_KEY_NAME(i->rr->key)) > 0)
+                manager_next_hostname(i->scope->manager);
+}
+
+void dns_zone_item_ready(DnsZoneItem *i) {
+        assert(i);
+        assert(i->probe_transaction);
+
+        if (i->block_ready > 0)
+                return;
+
+        if (IN_SET(i->probe_transaction->state, DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING))
+                return;
+
+        if (i->probe_transaction->state != DNS_TRANSACTION_SUCCESS) {
+                _cleanup_free_ char *pretty = NULL;
+
+                dns_resource_record_to_string(i->rr, &pretty);
+                log_debug("Record %s successfully probed.", strna(pretty));
+
+                dns_zone_item_probe_stop(i);
+                i->state = DNS_ZONE_ITEM_ESTABLISHED;
+
+        } else
+                dns_zone_item_conflict(i);
+}
diff --git a/src/resolve/resolved-dns-zone.h b/src/resolve/resolved-dns-zone.h
index b2af028cfc..bf93ab43fb 100644
--- a/src/resolve/resolved-dns-zone.h
+++ b/src/resolve/resolved-dns-zone.h
@@ -28,16 +28,46 @@ typedef struct DnsZone {
         Hashmap *by_name;
 } DnsZone;
 
+typedef struct DnsZoneItem DnsZoneItem;
+typedef enum DnsZoneItemState DnsZoneItemState;
+
 #include "resolved-dns-rr.h"
 #include "resolved-dns-question.h"
 #include "resolved-dns-answer.h"
+#include "resolved-dns-transaction.h"
+
+/* RFC 4795 Section 2.8. suggests a TTL of 30s by default */
+#define LLMNR_DEFAULT_TTL (30)
+
+enum DnsZoneItemState {
+        DNS_ZONE_ITEM_PROBING,
+        DNS_ZONE_ITEM_ESTABLISHED,
+        DNS_ZONE_ITEM_VERIFYING,
+        DNS_ZONE_ITEM_WITHDRAWN,
+};
+
+struct DnsZoneItem {
+        DnsScope *scope;
+        DnsResourceRecord *rr;
+
+        DnsZoneItemState state;
+
+        unsigned block_ready;
+
+        bool probing_enabled;
+
+        LIST_FIELDS(DnsZoneItem, by_key);
+        LIST_FIELDS(DnsZoneItem, by_name);
+
+        DnsTransaction *probe_transaction;
+};
 
 void dns_zone_flush(DnsZone *z);
 
-int dns_zone_put(DnsZone *z, DnsResourceRecord *rr);
+int dns_zone_put(DnsZone *z, DnsScope *s, DnsResourceRecord *rr, bool probe);
 void dns_zone_remove_rr(DnsZone *z, DnsResourceRecord *rr);
 
-int dns_zone_lookup(DnsZone *z, DnsQuestion *q, DnsAnswer **answer, DnsAnswer **soa);
+int dns_zone_lookup(DnsZone *z, DnsQuestion *q, DnsAnswer **answer, DnsAnswer **soa, bool *tentative);
 
-/* RFC 4795 Section 2.8. suggests a TTL of 30s by default */
-#define LLMNR_DEFAULT_TTL (30)
+void dns_zone_item_conflict(DnsZoneItem *i);
+void dns_zone_item_ready(DnsZoneItem *i);
diff --git a/src/resolve/resolved-link.c b/src/resolve/resolved-link.c
index a4c23bab06..5355eab042 100644
--- a/src/resolve/resolved-link.c
+++ b/src/resolve/resolved-link.c
@@ -23,10 +23,9 @@
 
 #include "sd-network.h"
 #include "strv.h"
+#include "missing.h"
 #include "resolved-link.h"
 
-static void link_address_add_rrs(LinkAddress *a);
-
 int link_new(Manager *m, Link **ret, int ifindex) {
         _cleanup_(link_freep) Link *l = NULL;
         int r;
@@ -93,7 +92,7 @@ static void link_allocate_scopes(Link *l) {
         } else
                 l->unicast_scope = dns_scope_free(l->unicast_scope);
 
-        if (link_relevant(l, AF_INET) && (l->flags & IFF_MULTICAST) && l->manager->use_llmnr) {
+        if (link_relevant(l, AF_INET) && l->manager->use_llmnr) {
                 if (!l->llmnr_ipv4_scope) {
                         r = dns_scope_new(l->manager, &l->llmnr_ipv4_scope, l, DNS_PROTOCOL_LLMNR, AF_INET);
                         if (r < 0)
@@ -102,7 +101,7 @@ static void link_allocate_scopes(Link *l) {
         } else
                 l->llmnr_ipv4_scope = dns_scope_free(l->llmnr_ipv4_scope);
 
-        if (link_relevant(l, AF_INET6) && (l->flags & IFF_MULTICAST) && l->manager->use_llmnr) {
+        if (link_relevant(l, AF_INET6) && l->manager->use_llmnr) {
                 if (!l->llmnr_ipv6_scope) {
                         r = dns_scope_new(l->manager, &l->llmnr_ipv6_scope, l, DNS_PROTOCOL_LLMNR, AF_INET6);
                         if (r < 0)
@@ -112,11 +111,11 @@ static void link_allocate_scopes(Link *l) {
                 l->llmnr_ipv6_scope = dns_scope_free(l->llmnr_ipv6_scope);
 }
 
-static void link_add_rrs(Link *l) {
+void link_add_rrs(Link *l, bool force_remove) {
         LinkAddress *a;
 
         LIST_FOREACH(addresses, a, l->addresses)
-                link_address_add_rrs(a);
+                link_address_add_rrs(a, force_remove);
 }
 
 int link_update_rtnl(Link *l, sd_rtnl_message *m) {
@@ -138,7 +137,7 @@ int link_update_rtnl(Link *l, sd_rtnl_message *m) {
         }
 
         link_allocate_scopes(l);
-        link_add_rrs(l);
+        link_add_rrs(l, false);
 
         return 0;
 }
@@ -194,7 +193,7 @@ int link_update_monitor(Link *l) {
 
         link_update_dns_servers(l);
         link_allocate_scopes(l);
-        link_add_rrs(l);
+        link_add_rrs(l, false);
 
         return 0;
 }
@@ -205,10 +204,14 @@ bool link_relevant(Link *l, int family) {
 
         assert(l);
 
-        /* A link is relevant if it isn't a loopback device and has at
-         * least one relevant IP address */
+        /* A link is relevant if it isn't a loopback or pointopoint
+         * device, has a link beat, can do multicast and has at least
+         * one relevant IP address */
+
+        if (l->flags & (IFF_LOOPBACK|IFF_POINTOPOINT|IFF_DORMANT))
+                return false;
 
-        if (l->flags & IFF_LOOPBACK)
+        if ((l->flags & (IFF_UP|IFF_LOWER_UP|IFF_MULTICAST)) != (IFF_UP|IFF_LOWER_UP|IFF_MULTICAST))
                 return false;
 
         sd_network_get_link_operational_state(l->ifindex, &state);
@@ -306,13 +309,10 @@ LinkAddress *link_address_free(LinkAddress *a) {
                 LIST_REMOVE(addresses, a->link->addresses, a);
 
                 if (a->llmnr_address_rr) {
-
                         if (a->family == AF_INET && a->link->llmnr_ipv4_scope)
                                 dns_zone_remove_rr(&a->link->llmnr_ipv4_scope->zone, a->llmnr_address_rr);
                         else if (a->family == AF_INET6 && a->link->llmnr_ipv6_scope)
                                 dns_zone_remove_rr(&a->link->llmnr_ipv6_scope->zone, a->llmnr_address_rr);
-
-                        dns_resource_record_unref(a->llmnr_address_rr);
                 }
 
                 if (a->llmnr_ptr_rr) {
@@ -320,103 +320,122 @@ LinkAddress *link_address_free(LinkAddress *a) {
                                 dns_zone_remove_rr(&a->link->llmnr_ipv4_scope->zone, a->llmnr_ptr_rr);
                         else if (a->family == AF_INET6 && a->link->llmnr_ipv6_scope)
                                 dns_zone_remove_rr(&a->link->llmnr_ipv6_scope->zone, a->llmnr_ptr_rr);
-
-                        dns_resource_record_unref(a->llmnr_ptr_rr);
                 }
         }
 
+        dns_resource_record_unref(a->llmnr_address_rr);
+        dns_resource_record_unref(a->llmnr_ptr_rr);
+
         free(a);
         return NULL;
 }
 
-static void link_address_add_rrs(LinkAddress *a) {
+void link_address_add_rrs(LinkAddress *a, bool force_remove) {
         int r;
 
         assert(a);
 
-        if (a->family == AF_INET && a->link->llmnr_ipv4_scope) {
+        if (a->family == AF_INET) {
 
-                if (!a->link->manager->host_ipv4_key) {
-                        a->link->manager->host_ipv4_key = dns_resource_key_new(DNS_CLASS_IN, DNS_TYPE_A, a->link->manager->hostname);
+                if (!force_remove && link_address_relevant(a) && a->link->llmnr_ipv4_scope) {
                         if (!a->link->manager->host_ipv4_key) {
-                                r = -ENOMEM;
-                                goto fail;
+                                a->link->manager->host_ipv4_key = dns_resource_key_new(DNS_CLASS_IN, DNS_TYPE_A, a->link->manager->hostname);
+                                if (!a->link->manager->host_ipv4_key) {
+                                        r = -ENOMEM;
+                                        goto fail;
+                                }
                         }
-                }
 
-                if (!a->llmnr_address_rr) {
-                        a->llmnr_address_rr = dns_resource_record_new(a->link->manager->host_ipv4_key);
                         if (!a->llmnr_address_rr) {
-                                r = -ENOMEM;
-                                goto fail;
+                                a->llmnr_address_rr = dns_resource_record_new(a->link->manager->host_ipv4_key);
+                                if (!a->llmnr_address_rr) {
+                                        r = -ENOMEM;
+                                        goto fail;
+                                }
+
+                                a->llmnr_address_rr->a.in_addr = a->in_addr.in;
+                                a->llmnr_address_rr->ttl = LLMNR_DEFAULT_TTL;
                         }
 
-                        a->llmnr_address_rr->a.in_addr = a->in_addr.in;
-                        a->llmnr_address_rr->ttl = LLMNR_DEFAULT_TTL;
-                }
-
-                if (!a->llmnr_ptr_rr) {
-                        r = dns_resource_record_new_reverse(&a->llmnr_ptr_rr, a->family, &a->in_addr, a->link->manager->hostname);
-                        if (r < 0)
-                                goto fail;
+                        if (!a->llmnr_ptr_rr) {
+                                r = dns_resource_record_new_reverse(&a->llmnr_ptr_rr, a->family, &a->in_addr, a->link->manager->hostname);
+                                if (r < 0)
+                                        goto fail;
 
-                        a->llmnr_ptr_rr->ttl = LLMNR_DEFAULT_TTL;
-                }
+                                a->llmnr_ptr_rr->ttl = LLMNR_DEFAULT_TTL;
+                        }
 
-                if (link_address_relevant(a)) {
-                        r = dns_zone_put(&a->link->llmnr_ipv4_scope->zone, a->llmnr_address_rr);
+                        r = dns_zone_put(&a->link->llmnr_ipv4_scope->zone, a->link->llmnr_ipv4_scope, a->llmnr_address_rr, true);
                         if (r < 0)
-                                goto fail;
+                                log_warning("Failed tp add A record to LLMNR zone: %s", strerror(-r));
 
-                        r = dns_zone_put(&a->link->llmnr_ipv4_scope->zone, a->llmnr_ptr_rr);
+                        r = dns_zone_put(&a->link->llmnr_ipv4_scope->zone, a->link->llmnr_ipv4_scope, a->llmnr_ptr_rr, false);
                         if (r < 0)
-                                goto fail;
+                                log_warning("Failed tp add IPv6 PTR record to LLMNR zone: %s", strerror(-r));
                 } else {
-                        dns_zone_remove_rr(&a->link->llmnr_ipv4_scope->zone, a->llmnr_address_rr);
-                        dns_zone_remove_rr(&a->link->llmnr_ipv4_scope->zone, a->llmnr_ptr_rr);
+                        if (a->llmnr_address_rr) {
+                                if (a->link->llmnr_ipv4_scope)
+                                        dns_zone_remove_rr(&a->link->llmnr_ipv4_scope->zone, a->llmnr_address_rr);
+                                a->llmnr_address_rr = dns_resource_record_unref(a->llmnr_address_rr);
+                        }
+
+                        if (a->llmnr_ptr_rr) {
+                                if (a->link->llmnr_ipv4_scope)
+                                        dns_zone_remove_rr(&a->link->llmnr_ipv4_scope->zone, a->llmnr_ptr_rr);
+                                a->llmnr_ptr_rr = dns_resource_record_unref(a->llmnr_ptr_rr);
+                        }
                 }
         }
 
-        if (a->family == AF_INET6 && a->link->llmnr_ipv6_scope) {
+        if (a->family == AF_INET6) {
 
-                if (!a->link->manager->host_ipv6_key) {
-                        a->link->manager->host_ipv6_key = dns_resource_key_new(DNS_CLASS_IN, DNS_TYPE_AAAA, a->link->manager->hostname);
+                if (!force_remove && link_address_relevant(a) && a->link->llmnr_ipv6_scope) {
                         if (!a->link->manager->host_ipv6_key) {
-                                r = -ENOMEM;
-                                goto fail;
+                                a->link->manager->host_ipv6_key = dns_resource_key_new(DNS_CLASS_IN, DNS_TYPE_AAAA, a->link->manager->hostname);
+                                if (!a->link->manager->host_ipv6_key) {
+                                        r = -ENOMEM;
+                                        goto fail;
+                                }
                         }
-                }
 
-                if (!a->llmnr_address_rr) {
-                        a->llmnr_address_rr = dns_resource_record_new(a->link->manager->host_ipv6_key);
                         if (!a->llmnr_address_rr) {
-                                r = -ENOMEM;
-                                goto fail;
+                                a->llmnr_address_rr = dns_resource_record_new(a->link->manager->host_ipv6_key);
+                                if (!a->llmnr_address_rr) {
+                                        r = -ENOMEM;
+                                        goto fail;
+                                }
+
+                                a->llmnr_address_rr->aaaa.in6_addr = a->in_addr.in6;
+                                a->llmnr_address_rr->ttl = LLMNR_DEFAULT_TTL;
                         }
 
-                        a->llmnr_address_rr->aaaa.in6_addr = a->in_addr.in6;
-                        a->llmnr_address_rr->ttl = LLMNR_DEFAULT_TTL;
-                }
-
-                if (!a->llmnr_ptr_rr) {
-                        r = dns_resource_record_new_reverse(&a->llmnr_ptr_rr, a->family, &a->in_addr, a->link->manager->hostname);
-                        if (r < 0)
-                                goto fail;
+                        if (!a->llmnr_ptr_rr) {
+                                r = dns_resource_record_new_reverse(&a->llmnr_ptr_rr, a->family, &a->in_addr, a->link->manager->hostname);
+                                if (r < 0)
+                                        goto fail;
 
-                        a->llmnr_ptr_rr->ttl = LLMNR_DEFAULT_TTL;
-                }
+                                a->llmnr_ptr_rr->ttl = LLMNR_DEFAULT_TTL;
+                        }
 
-                if (link_address_relevant(a)) {
-                        r = dns_zone_put(&a->link->llmnr_ipv6_scope->zone, a->llmnr_address_rr);
+                        r = dns_zone_put(&a->link->llmnr_ipv6_scope->zone, a->link->llmnr_ipv6_scope, a->llmnr_address_rr, true);
                         if (r < 0)
-                                goto fail;
+                                log_warning("Failed to add AAAA record to LLMNR zone: %s", strerror(-r));
 
-                        r = dns_zone_put(&a->link->llmnr_ipv6_scope->zone, a->llmnr_ptr_rr);
+                        r = dns_zone_put(&a->link->llmnr_ipv6_scope->zone, a->link->llmnr_ipv6_scope, a->llmnr_ptr_rr, false);
                         if (r < 0)
-                                goto fail;
+                                log_warning("Failed to add IPv6 PTR record to LLMNR zone: %s", strerror(-r));
                 } else {
-                        dns_zone_remove_rr(&a->link->llmnr_ipv6_scope->zone, a->llmnr_address_rr);
-                        dns_zone_remove_rr(&a->link->llmnr_ipv6_scope->zone, a->llmnr_ptr_rr);
+                        if (a->llmnr_address_rr) {
+                                if (a->link->llmnr_ipv6_scope)
+                                        dns_zone_remove_rr(&a->link->llmnr_ipv6_scope->zone, a->llmnr_address_rr);
+                                a->llmnr_address_rr = dns_resource_record_unref(a->llmnr_address_rr);
+                        }
+
+                        if (a->llmnr_ptr_rr) {
+                                if (a->link->llmnr_ipv6_scope)
+                                        dns_zone_remove_rr(&a->link->llmnr_ipv6_scope->zone, a->llmnr_ptr_rr);
+                                a->llmnr_ptr_rr = dns_resource_record_unref(a->llmnr_ptr_rr);
+                        }
                 }
         }
 
@@ -438,7 +457,7 @@ int link_address_update_rtnl(LinkAddress *a, sd_rtnl_message *m) {
         sd_rtnl_message_addr_get_scope(m, &a->scope);
 
         link_allocate_scopes(a->link);
-        link_add_rrs(a->link);
+        link_add_rrs(a->link, false);
 
         return 0;
 }
diff --git a/src/resolve/resolved-link.h b/src/resolve/resolved-link.h
index f58bd54203..3cafaab26c 100644
--- a/src/resolve/resolved-link.h
+++ b/src/resolve/resolved-link.h
@@ -76,7 +76,7 @@ int link_update_rtnl(Link *l, sd_rtnl_message *m);
 int link_update_monitor(Link *l);
 bool link_relevant(Link *l, int family);
 LinkAddress* link_find_address(Link *l, int family, const union in_addr_union *in_addr);
-
+void link_add_rrs(Link *l, bool force_remove);
 DnsServer* link_find_dns_server(Link *l, int family, const union in_addr_union *in_addr);
 DnsServer* link_get_dns_server(Link *l);
 void link_next_dns_server(Link *l);
@@ -85,5 +85,6 @@ int link_address_new(Link *l, LinkAddress **ret, int family, const union in_addr
 LinkAddress *link_address_free(LinkAddress *a);
 int link_address_update_rtnl(LinkAddress *a, sd_rtnl_message *m);
 bool link_address_relevant(LinkAddress *l);
+void link_address_add_rrs(LinkAddress *a, bool force_remove);
 
 DEFINE_TRIVIAL_CLEANUP_FUNC(Link*, link_free);
diff --git a/src/resolve/resolved-manager.c b/src/resolve/resolved-manager.c
index fecd7ea0c6..72034c1f48 100644
--- a/src/resolve/resolved-manager.c
+++ b/src/resolve/resolved-manager.c
@@ -461,7 +461,7 @@ Manager *manager_free(Manager *m) {
         while (m->dns_queries)
                 dns_query_free(m->dns_queries);
 
-        hashmap_free(m->dns_query_transactions);
+        hashmap_free(m->dns_transactions);
 
         while ((l = hashmap_first(m->links)))
                link_free(l);
@@ -703,7 +703,7 @@ int manager_recv(Manager *m, int fd, DnsProtocol protocol, DnsPacket **ret) {
 
 static int on_dns_packet(sd_event_source *s, int fd, uint32_t revents, void *userdata) {
         _cleanup_(dns_packet_unrefp) DnsPacket *p = NULL;
-        DnsQueryTransaction *t = NULL;
+        DnsTransaction *t = NULL;
         Manager *m = userdata;
         int r;
 
@@ -712,11 +712,11 @@ static int on_dns_packet(sd_event_source *s, int fd, uint32_t revents, void *use
                 return r;
 
         if (dns_packet_validate_reply(p) > 0) {
-                t = hashmap_get(m->dns_query_transactions, UINT_TO_PTR(DNS_PACKET_ID(p)));
+                t = hashmap_get(m->dns_transactions, UINT_TO_PTR(DNS_PACKET_ID(p)));
                 if (!t)
                         return 0;
 
-                dns_query_transaction_process_reply(t, p);
+                dns_transaction_process_reply(t, p);
 
         } else
                 log_debug("Invalid DNS packet.");
@@ -990,7 +990,7 @@ uint32_t manager_find_mtu(Manager *m) {
 
 static int on_llmnr_packet(sd_event_source *s, int fd, uint32_t revents, void *userdata) {
         _cleanup_(dns_packet_unrefp) DnsPacket *p = NULL;
-        DnsQueryTransaction *t = NULL;
+        DnsTransaction *t = NULL;
         Manager *m = userdata;
         int r;
 
@@ -1001,11 +1001,11 @@ static int on_llmnr_packet(sd_event_source *s, int fd, uint32_t revents, void *u
         if (dns_packet_validate_reply(p) > 0) {
                 log_debug("Got reply packet for id %u", DNS_PACKET_ID(p));
 
-                t = hashmap_get(m->dns_query_transactions, UINT_TO_PTR(DNS_PACKET_ID(p)));
+                t = hashmap_get(m->dns_transactions, UINT_TO_PTR(DNS_PACKET_ID(p)));
                 if (!t)
                         return 0;
 
-                dns_query_transaction_process_reply(t, p);
+                dns_transaction_process_reply(t, p);
 
         } else if (dns_packet_validate_query(p) > 0) {
                 Link *l;
@@ -1397,14 +1397,80 @@ int manager_ifindex_is_loopback(Manager *m, int ifindex) {
 }
 
 int manager_find_ifindex(Manager *m, int family, const union in_addr_union *in_addr) {
-        Link *l;
+        LinkAddress *a;
+
+        assert(m);
+
+        a = manager_find_address(m, family, in_addr);
+        if (a)
+                return a->link->ifindex;
+
+        return 0;
+}
+
+int manager_next_hostname(Manager *m) {
+        const char *p;
         Iterator i;
+        uint64_t u;
+        char *h;
+        Link *l;
 
         assert(m);
 
-        HASHMAP_FOREACH(l, m->links, i)
-                if (link_find_address(l, family, in_addr))
-                        return l->ifindex;
+        p = strchr(m->hostname, 0);
+        assert(p);
+
+        while (p > m->hostname) {
+                if (!strchr("0123456789", p[-1]))
+                        break;
+
+                p--;
+        }
+
+        if (*p == 0 || safe_atou64(p, &u) < 0 || u <= 0)
+                u = 1;
+
+        u++;
+
+        if (asprintf(&h, "%.*s%" PRIu64, (int) (p - m->hostname), m->hostname, u) < 0)
+                return -ENOMEM;
+
+        log_info("Hostname conflict, changing local hostname from '%s' to '%s'.", m->hostname, h);
+
+        free(m->hostname);
+        m->hostname = h;
+
+        m->host_ipv4_key = dns_resource_key_unref(m->host_ipv4_key);
+        m->host_ipv6_key = dns_resource_key_unref(m->host_ipv6_key);
+
+        HASHMAP_FOREACH(l, m->links, i) {
+                link_add_rrs(l, true);
+                link_add_rrs(l, false);
+        }
 
         return 0;
 }
+
+LinkAddress* manager_find_address(Manager *m, int family, const union in_addr_union *in_addr) {
+        Iterator i;
+        Link *l;
+
+        assert(m);
+
+        HASHMAP_FOREACH(l, m->links, i) {
+                LinkAddress *a;
+
+                a = link_find_address(l, family, in_addr);
+                if (a)
+                        return a;
+        }
+
+        return NULL;
+}
+
+int manager_our_packet(Manager *m, DnsPacket *p) {
+        assert(m);
+        assert(p);
+
+        return !!manager_find_address(m, p->family, &p->sender);
+}
diff --git a/src/resolve/resolved.h b/src/resolve/resolved.h
index 6aa0fc9e56..07560553b9 100644
--- a/src/resolve/resolved.h
+++ b/src/resolve/resolved.h
@@ -51,7 +51,7 @@ struct Manager {
         sd_event_source *network_event_source;
 
         /* DNS query management */
-        Hashmap *dns_query_transactions;
+        Hashmap *dns_transactions;
         LIST_HEAD(DnsQuery, dns_queries);
         unsigned n_dns_queries;
 
@@ -103,6 +103,7 @@ int manager_write_resolv_conf(Manager *m);
 DnsServer* manager_find_dns_server(Manager *m, int family, const union in_addr_union *in_addr);
 DnsServer *manager_get_dns_server(Manager *m);
 void manager_next_dns_server(Manager *m);
+
 uint32_t manager_find_mtu(Manager *m);
 
 int manager_send(Manager *m, int fd, int ifindex, int family, const union in_addr_union *addr, uint16_t port, DnsPacket *p);
@@ -117,7 +118,11 @@ int manager_llmnr_ipv6_tcp_fd(Manager *m);
 
 int manager_ifindex_is_loopback(Manager *m, int ifindex);
 int manager_find_ifindex(Manager *m, int family, const union in_addr_union *in_addr);
+LinkAddress* manager_find_address(Manager *m, int family, const union in_addr_union *in_addr);
+
+int manager_next_hostname(Manager *m);
 
+int manager_our_packet(Manager *m, DnsPacket *p);
 int manager_connect_bus(Manager *m);
 
 DEFINE_TRIVIAL_CLEANUP_FUNC(Manager*, manager_free);
diff --git a/src/shared/missing.h b/src/shared/missing.h
index f4378a36b1..083b85a26c 100644
--- a/src/shared/missing.h
+++ b/src/shared/missing.h
@@ -503,3 +503,11 @@ static inline int setns(int fd, int nstype) {
 #ifndef IPV6_UNICAST_IF
 #define IPV6_UNICAST_IF 76
 #endif
+
+#ifndef IFF_LOWER_UP
+#define IFF_LOWER_UP 0x10000
+#endif
+
+#ifndef IFF_DORMANT
+#define IFF_DORMANT 0x20000
+#endif