resolved: use a temporary Set to speed up dns question parsing

keszybz · keszybz · commit 2d34cf0c16dd · 2019-03-04T15:53:37.000+01:00
This doesn't necessarily make things faster, because we still spend more time
in dns_answer_add(), but it improves the compuational complexity of this part.
If we even make dns_resource_key_equal_faster, this will become worthwhile.
diff --git a/src/resolve/resolved-dns-packet.c b/src/resolve/resolved-dns-packet.c
@@ -7,6 +7,7 @@
 #include "alloc-util.h"
 #include "dns-domain.h"
 #include "resolved-dns-packet.h"
+#include "set.h"
 #include "string-table.h"
 #include "strv.h"
 #include "unaligned.h"
@@ -2133,6 +2134,17 @@ static int dns_packet_extract_question(DnsPacket *p, DnsQuestion **ret_question)
                 if (!question)
                         return -ENOMEM;
 
+                _cleanup_set_free_ Set *keys = NULL; /* references to keys are kept by Question */
+
+                keys = set_new(&dns_resource_key_hash_ops);
+                if (!keys)
+                        return log_oom();
+
+                r = set_reserve(keys, n * 2); /* Higher multipliers give slightly higher efficiency through
+                                               * hash collisions, but the gains quickly drop of after 2. */
+                if (r < 0)
+                        return r;
+
                 for (i = 0; i < n; i++) {
                         _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
                         bool cache_flush;
@@ -2147,7 +2159,14 @@ static int dns_packet_extract_question(DnsPacket *p, DnsQuestion **ret_question)
                         if (!dns_type_is_valid_query(key->type))
                                 return -EBADMSG;
 
-                        r = dns_question_add(question, key);
+                        r = set_put(keys, key);
+                        if (r < 0)
+                                return r;
+                        if (r == 0)
+                                /* Already in the Question, let's skip */
+                                continue;
+
+                        r = dns_question_add_raw(question, key);
                         if (r < 0)
                                 return r;
                 }
diff --git a/src/resolve/resolved-dns-question.c b/src/resolve/resolved-dns-question.c
@@ -32,28 +32,36 @@ static DnsQuestion *dns_question_free(DnsQuestion *q) {
 
 DEFINE_TRIVIAL_REF_UNREF_FUNC(DnsQuestion, dns_question, dns_question_free);
 
+int dns_question_add_raw(DnsQuestion *q, DnsResourceKey *key) {
+        /* Insert without checking for duplicates. */
+
+        assert(key);
+        assert(q);
+
+        if (q->n_keys >= q->n_allocated)
+                return -ENOSPC;
+
+        q->keys[q->n_keys++] = dns_resource_key_ref(key);
+        return 0;
+}
+
 int dns_question_add(DnsQuestion *q, DnsResourceKey *key) {
-        size_t i;
         int r;
 
         assert(key);
 
         if (!q)
                 return -ENOSPC;
 
-        for (i = 0; i < q->n_keys; i++) {
+        for (size_t i = 0; i < q->n_keys; i++) {
                 r = dns_resource_key_equal(q->keys[i], key);
                 if (r < 0)
                         return r;
                 if (r > 0)
                         return 0;
         }
 
-        if (q->n_keys >= q->n_allocated)
-                return -ENOSPC;
-
-        q->keys[q->n_keys++] = dns_resource_key_ref(key);
-        return 0;
+        return dns_question_add_raw(q, key);
 }
 
 int dns_question_matches_rr(DnsQuestion *q, DnsResourceRecord *rr, const char *search_domain) {
diff --git a/src/resolve/resolved-dns-question.h b/src/resolve/resolved-dns-question.h
@@ -22,6 +22,7 @@ int dns_question_new_address(DnsQuestion **ret, int family, const char *name, bo
 int dns_question_new_reverse(DnsQuestion **ret, int family, const union in_addr_union *a);
 int dns_question_new_service(DnsQuestion **ret, const char *service, const char *type, const char *domain, bool with_txt, bool convert_idna);
 
+int dns_question_add_raw(DnsQuestion *q, DnsResourceKey *key);
 int dns_question_add(DnsQuestion *q, DnsResourceKey *key);
 
 int dns_question_matches_rr(DnsQuestion *q, DnsResourceRecord *rr, const char *search_domain);
