sock_dns: implement DNS cache

RIOT-OS · benpicco · Jul 15, 2022 · Feb 19, 2022 · Apr 3, 2022 · Jul 13, 2022
commit 077a41a719f60aee6e3ccf126d0318f1f1b2b219
diff --git a/makefiles/pseudomodules.inc.mk b/makefiles/pseudomodules.inc.mk
@@ -215,6 +215,7 @@ PSEUDOMODULES += sock_async
 PSEUDOMODULES += sock_aux_local
 PSEUDOMODULES += sock_aux_rssi
 PSEUDOMODULES += sock_aux_timestamp
+PSEUDOMODULES += sock_dns_cache
 PSEUDOMODULES += sock_dtls
 PSEUDOMODULES += sock_ip
 PSEUDOMODULES += sock_tcp

diff --git a/sys/Makefile.dep b/sys/Makefile.dep
@@ -602,6 +602,12 @@ ifneq (,$(filter sock_dns,$(USEMODULE)))
   USEMODULE += posix_headers
 endif
 
+ifneq (,$(filter sock_dns_cache,$(USEMODULE)))
+  USEMODULE += sock_dns
+  USEMODULE += ztimer_msec
+  USEMODULE += checksum
+endif
+
 ifneq (,$(filter sock_util,$(USEMODULE)))
   USEMODULE += posix_inet
   USEMODULE += fmt

diff --git a/sys/include/net/dns/msg.h b/sys/include/net/dns/msg.h
@@ -104,13 +104,14 @@ size_t dns_msg_compose_query(void *dns_buf, const char *domain_name,
  * @param[in] family        The address family used to compose the query for
  *                          this response (see @ref dns_msg_compose_query())
  * @param[out] addr_out     The IP address returned by the response.
+ * @param[out] ttl          The live time of the entry in seconds
  *
  * @return  Length of the @p addr_out on success.
  * @return  -EBADMSG, when an address corresponding to @p family can not be found
  *          in @p buf.
  */
 int dns_msg_parse_reply(const uint8_t *buf, size_t len, int family,
-                        void *addr_out);
+                        void *addr_out, uint32_t *ttl);
 
 #ifdef __cplusplus
 }

@@ -131,7 +131,7 @@ size_t dns_msg_compose_query(void *dns_buf, const char *domain_name,
 }
 
 int dns_msg_parse_reply(const uint8_t *buf, size_t len, int family,
-                        void *addr_out)
+                        void *addr_out, uint32_t *ttl)
 {
     const uint8_t *buflim = buf + len;
     const dns_hdr_t *hdr = (dns_hdr_t *)buf;
@@ -162,7 +162,10 @@ int dns_msg_parse_reply(const uint8_t *buf, size_t len, int family,
         bufpos += RR_TYPE_LENGTH;
         uint16_t class = ntohs(_get_short(bufpos));
         bufpos += RR_CLASS_LENGTH;
-        bufpos += RR_TTL_LENGTH; /* skip ttl */
+        if (ttl) {
+            *ttl = byteorder_bebuftohl(bufpos);
+        }
+        bufpos += RR_TTL_LENGTH;
 
         unsigned addrlen = ntohs(_get_short(bufpos));
         /* skip unwanted answers */

@@ -712,7 +712,7 @@ static void _resp_handler(const gcoap_request_memo_t *memo, coap_pkt_t *pdu,
         case COAP_FORMAT_DNS_MESSAGE:
         case COAP_FORMAT_NONE:
             context->res = dns_msg_parse_reply(data, data_len, family,
-                                               context->addr_out);
+                                               context->addr_out, NULL);
             if ((ENABLE_DEBUG) && (context->res < 0)) {
                 DEBUG("gcoap_dns: Unable to parse DNS reply: %d\n",
                       context->res);

@@ -1 +1,7 @@
+SRC += dns.c
+
+ifneq (,$(filter sock_dns_cache, $(USEMODULE)))
+  SRC += dns_cache.c
+endif
+
 include $(RIOTBASE)/Makefile.base
@@ -25,6 +25,7 @@
 #include "net/dns/msg.h"
 #include "net/sock/udp.h"
 #include "net/sock/dns.h"
+#include "dns_cache.h"
 
 /* min domain name length is 1, so minimum record length is 7 */
 #define DNS_MIN_REPLY_LEN   (unsigned)(sizeof(dns_hdr_t) + 7)
@@ -67,6 +68,8 @@ void auto_init_sock_dns(void)
 
 int sock_dns_query(const char *domain_name, void *addr_out, int family)
 {
+    ssize_t res;
+    sock_udp_t sock_dns;
     static uint8_t dns_buf[CONFIG_DNS_MSG_LEN];
 
     if (sock_dns_server.port == 0) {
@@ -77,9 +80,12 @@ int sock_dns_query(const char *domain_name, void *addr_out, int family)
         return -ENOSPC;
     }
 
-    sock_udp_t sock_dns;
+    res = sock_dns_cache_query(domain_name, addr_out, family);
+    if (res) {
+        return res;
+    }
 
-    ssize_t res = sock_udp_create(&sock_dns, NULL, &sock_dns_server, 0);
+    res = sock_udp_create(&sock_dns, NULL, &sock_dns_server, 0);
     if (res) {
         goto out;
     }
@@ -95,8 +101,10 @@ int sock_dns_query(const char *domain_name, void *addr_out, int family)
         res = sock_udp_recv(&sock_dns, dns_buf, sizeof(dns_buf), 1000000LU, NULL);
         if (res > 0) {
             if (res > (int)DNS_MIN_REPLY_LEN) {
+                uint32_t ttl;
                 if ((res = dns_msg_parse_reply(dns_buf, res, family,
-                                               addr_out)) > 0) {
+                                               addr_out, &ttl)) > 0) {
+                    sock_dns_cache_add(domain_name, addr_out, res, ttl);
                     goto out;
                 }
             }

@@ -0,0 +1,188 @@
+/*
+ * Copyright (C) 2022 ML!PA Consulting GmbH
+ *
+ * This file is subject to the terms and conditions of the GNU Lesser
+ * General Public License v2.1. See the file LICENSE in the top level
+ * directory for more details.
+ */
+
+/**
+ * @ingroup net_sock_dns
+ * @{
+ * @file
+ * @brief   DNS cache implementation
+ * @author  Benjamin Valentin <benjamin.valentin@ml-pa.com>
+ * @}
+ */
+
+#include "bitfield.h"
+#include "checksum/fletcher32.h"
+#include "net/sock/dns.h"
+#include "time_units.h"
+#include "dns_cache.h"
+#include "ztimer.h"
+
+#define ENABLE_DEBUG 0
+#include "debug.h"
+
+static struct dns_cache_entry {
+    uint32_t hash;
+    uint32_t expires;
+    union {
+#if IS_ACTIVE(SOCK_HAS_IPV4)
+        ipv4_addr_t v4;
+#endif
+#if IS_ACTIVE(SOCK_HAS_IPV6)
+        ipv6_addr_t v6;
+#endif
+    } addr;
+} cache[CONFIG_DNS_CACHE_SIZE];
+
+#if IS_ACTIVE(SOCK_HAS_IPV4) && IS_ACTIVE(SOCK_HAS_IPV6)
+BITFIELD(cache_is_v6, CONFIG_DNS_CACHE_SIZE);
+
+static inline uint8_t _get_len(unsigned idx)
+{
+    return bf_isset(cache_is_v6, idx) ? 16 : 4;
+}
+#elif IS_ACTIVE(SOCK_HAS_IPV4)
+static inline uint8_t _get_len(unsigned idx)
+{
+    (void)idx;
+    return 4;
+}
+#elif IS_ACTIVE(SOCK_HAS_IPV6)
+static inline uint8_t _get_len(unsigned idx)
+{
+    (void)idx;
+    return 16;
+}
+#endif
+
+static void _set_len(unsigned idx, uint8_t len)
+{
+#if IS_ACTIVE(SOCK_HAS_IPV4) && IS_ACTIVE(SOCK_HAS_IPV6)
+    if (len == 16) {
+        bf_set(cache_is_v6, idx);
+    } else {
+        bf_unset(cache_is_v6, idx);
+    }
+#else
+    (void)idx;
+    (void)len;
+#endif
+}
+
+static bool _is_empty(unsigned idx)
+{
+    const uint8_t len = _get_len(idx);
+    const uint8_t *addr = (void *)&cache[idx].addr;
+    for (unsigned i = 0; i < len; ++i) {
+        if (addr[i]) {
+            return false;
+        }
+    }
+
+    return true;
+}
+
+static void _set_empty(unsigned idx)
+{
+    memset(&cache[idx].addr, 0, _get_len(idx));
+}
+
+static uint8_t _addr_len(int family)
+{
+    switch (family) {
+#if IS_ACTIVE(SOCK_HAS_IPV4)
+    case AF_INET:
+        return sizeof(ipv4_addr_t);
+#endif
+#if IS_ACTIVE(SOCK_HAS_IPV6)
+   case AF_INET6:
+        return sizeof(ipv6_addr_t);
+#endif
+    case AF_UNSPEC:
+        return 0;
+    default:
+        return 255;
+    }
+}
+
+static uint32_t _hash(const void *data, size_t len)
+{
+    return fletcher32(data, (len + 1) / 2);
+}
+
+int sock_dns_cache_query(const char *domain_name, void *addr_out, int family)
+{
+    uint32_t now = ztimer_now(ZTIMER_MSEC) / MS_PER_SEC;
+    uint32_t hash = _hash(domain_name, strlen(domain_name));
+    uint8_t addr_len = _addr_len(family);
+
+    for (unsigned i = 0; i < CONFIG_DNS_CACHE_SIZE; ++i) {
+        /* empty slot */
+        if (_is_empty(i)) {
+            continue;
+        }
+        /* TTL expired - invalidate slot */
+        if (now > cache[i].expires) {
+            DEBUG("dns_cache[%u] expired\n", i);
+            _set_empty(i);
+            continue;
+        }
+        /* check if hash and length match */
+        if (cache[i].hash == hash && (!addr_len || addr_len == _get_len(i))) {
+            DEBUG("dns_cache[%u] hit\n", i);
+            memcpy(addr_out, &cache[i].addr, _get_len(i));
+            return _get_len(i);
+        }
+    }
+    DEBUG("dns_cache miss\n");
+
+    return 0;
+}
+
+static void _add_entry(uint8_t i, uint32_t hash, const void *addr_out,
+                       int addr_len, uint32_t expires)
+{
+    DEBUG("dns_cache[%u] add cache entry\n", i);
+    cache[i].hash = hash;
+    cache[i].expires = expires;
+    memcpy(&cache[i].addr, addr_out, addr_len);
+    _set_len(i, addr_len);
+}
+
+void sock_dns_cache_add(const char *domain_name, const void *addr_out,
+                        int addr_len, uint32_t ttl)
+{
+    uint32_t now = ztimer_now(ZTIMER_MSEC) / MS_PER_SEC;
+    uint32_t hash = _hash(domain_name, strlen(domain_name));
+    uint32_t oldest = ttl;
+    int idx = -1;
+
+    assert(addr_len == 4 || addr_len == 16);
+    DEBUG("dns_cache: lifetime of %s is %"PRIu32" s\n", domain_name, ttl);
+
+    for (unsigned i = 0; i < CONFIG_DNS_CACHE_SIZE; ++i) {
+        if (now > cache[i].expires || _is_empty(i)) {
+            _add_entry(i, hash, addr_out, addr_len, now + ttl);
+            return;
+        }
+        if (cache[i].hash == hash && _get_len(i) == addr_len) {
+            DEBUG("dns_cache[%u] update ttl\n", i);
+            cache[i].expires = now + ttl;
+            return;
+        }
+        uint32_t _ttl = cache[i].expires - now;
+        if (_ttl < oldest) {
+            oldest = _ttl;
+            idx = i;
+        }
+    }
+
+    if (idx >= 0) {
+        DEBUG("dns_cache: evict first entry to expire\n");
+        _add_entry(idx, hash, addr_out, addr_len, now + ttl);
+    }
+}