ipcpd: Update DHT for unicast layer

This is a rewrite of the DHT for name-to-address resolution in the
unicast layer. It is now integrated as a proper directory policy. The
dir_wait_running function is removed, instead the a DHT peer is passed
on during IPCP enrolment.

Each DHT request/response gets a random 64-bit ID ('cookie'). DHT
messages to the same peer are deduped, except in the case when the DHT
is low on contacts. In that case, it will contact the per it received
at enrolment for more contacts. To combat packet loss, these messages
are not deduped by means of a 'magic cookie', chosen at random when
the DHT starts.

The DHT parameters (Kademlia) can be set using the configfile or the
IRM command line tools:

if DIRECTORY_POLICY == DHT
        [dht_alpha <search factor> (default: 3)]
        [dht_k <replication factor> (default: 8)]
        [dht_t_expire <expiration (s)> (default: 86400)]
        [dht_t_refresh <contact refresh (s)> (default: 900)]
        [dht_t_replicate <replication (s)> (default: 900)]

This commit also adds support for a protocol debug level (PP).
Protocol debugging for the DHT can be enabled using the
DEBUG_PROTO_DHT build flag.

The DHT has the following message types:

DHT_STORE, sent to k peers. Not acknowledged.

    DHT_STORE --> [2861814146dbf9b5|ed:d9:e2:c4].
      key: bcc236ab6ec69e65 [32 bytes]
      val: 00000000c4e2d9ed [8 bytes]
      exp: 2025-08-03 17:29:44 (UTC).

DHT_FIND_NODE_REQ, sent to 'alpha' peers, with a corresponding
response. This is used to update the peer routing table to iteratively
look for the nodes with IDs closest to the requested key.

    DHT_FIND_NODE_REQ --> [a62f92abffb451c4|ed:d9:e2:c4].
      cookie: 2d4b7acef8308210
      key:    a62f92abffb451c4 [32 bytes]

    DHT_FIND_NODE_RSP <-- [2861814146dbf9b5|ed:d9:e2:c4].
      cookie: 2d4b7acef8308210
      key:    a62f92abffb451c4 [32 bytes]
      contacts: [1]
        [a62f92abffb451c4|9f:0d:c1:fb]

DHT_FIND_VALUE_REQ, sent to 'k' peers, with a corresponding
response. Used to find a value for a key. Will also send its closest
known peers in the response.

    DHT_FIND_VALUE_REQ --> [2861814146dbf9b5|ed:d9:e2:c4].
      cookie: 80a1adcb09a2ff0a
      key:    42dee3b0415b4f69 [32 bytes]

    DHT_FIND_VALUE_RSP <-- [2861814146dbf9b5|ed:d9:e2:c4].
      cookie: 80a1adcb09a2ff0a
      key:    42dee3b0415b4f69 [32 bytes]
        values: [1]
          00000000c4e2d9ed [8 bytes]
        contacts: [1]
          [a62f92abffb451c4|9f:0d:c1:fb]

Also removes ubuntu 20 from appveyor config as it is not supported anymore.

Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks>
Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>

9 files changed, 177 insertions, 45 deletions

diff --git a/include/ouroboros/hash.h b/include/ouroboros/hash.h
index 3d5734f5..c44c2c8a 100644
--- a/include/ouroboros/hash.h
+++ b/include/ouroboros/hash.h
@@ -42,7 +42,8 @@ enum hash_algo {
 
 #define HASH_FMT32 "%02x%02x%02x%02x"
 #define HASH_VAL32(hash)                                  \
-        (hash)[0], (hash)[1], (hash)[2], (hash)[3]
+        ((uint8_t *) hash)[0], ((uint8_t *) hash)[1],     \
+        ((uint8_t *) hash)[2], ((uint8_t *) hash)[3]
 
 #define HASH_FMT64 HASH_FMT32 HASH_FMT32
 #define HASH_VAL64(hash64)                                \
diff --git a/include/ouroboros/ipcp.h b/include/ouroboros/ipcp.h
index 42c4dfa4..a77b700b 100644
--- a/include/ouroboros/ipcp.h
+++ b/include/ouroboros/ipcp.h
@@ -32,14 +32,15 @@
 #define LAYER_NAME_SIZE 255
 #define DEV_NAME_SIZE   255
 
+/* TODO: Move state to ipcpd/ipcp.h, requires small change to reg/ipcp.c */
 enum ipcp_state {
-        IPCP_INIT = 0,
+        IPCP_NULL = 0,
+        IPCP_INIT,
         IPCP_BOOT,
-        IPCP_OPERATIONAL,
         IPCP_BOOTSTRAPPED,
         IPCP_ENROLLED,
-        IPCP_SHUTDOWN,
-        IPCP_NULL
+        IPCP_OPERATIONAL,
+        IPCP_SHUTDOWN
 };
 
 enum ipcp_type { /* IRMd uses order to select an IPCP for flow allocation. */
@@ -56,7 +57,7 @@ struct ipcp_info {
         enum ipcp_type  type;
         pid_t           pid;
         char            name[IPCP_NAME_SIZE + 1];
-        enum ipcp_state state;
+        enum ipcp_state state; /* TODO: remove. */
 };
 
 /* Unicast IPCP components. */
@@ -89,13 +90,113 @@ struct dt_config {
         enum pol_routing routing_type;
 };
 
+static const struct dt_config default_dt_config = {
+        .addr_size    = 4,
+        .eid_size     = 8,
+        .max_ttl      = 60,
+        .routing_type = ROUTING_LINK_STATE
+};
+
+enum pol_dir {
+        DIR_DHT = 0,
+        DIR_INVALID
+};
+
+enum pol_dir_hash {
+        DIR_HASH_SHA3_224,
+        DIR_HASH_SHA3_256,
+        DIR_HASH_SHA3_384,
+        DIR_HASH_SHA3_512,
+        DIR_HASH_INVALID
+};
+
+enum dir_dht_config_limits {
+        DHT_ALPHA_MIN       = 1,
+        DHT_K_MIN           = 1,
+        DHT_T_EXPIRE_MIN    = 10,
+        DHT_T_REFRESH_MIN   = 3,
+        DHT_T_REPLICATE_MIN = 3,
+
+        DHT_ALPHA_MAX       = 10,
+        DHT_K_MAX           = 20,
+        DHT_T_EXPIRE_MAX    = 86400,
+        DHT_T_REFRESH_MAX   = 3600,
+        DHT_T_REPLICATE_MAX = 3600,
+};
+
+struct dir_dht_config {
+        struct {
+                uint32_t alpha;       /* Parallel search factor */
+                uint32_t k;           /* Replication factor     */
+                uint32_t t_expire;    /* Expire time (s)        */
+                uint32_t t_refresh;   /* Refresh time (s)       */
+                uint32_t t_replicate; /* Replication time (s)   */
+        } params;
+        uint64_t peer;                /* Initial peer address   */
+};
+
+static const struct dir_dht_config default_dht_config = {
+        .params = {
+                .alpha       = 3,     /* Proven optimal value   */
+                .k           = 8,     /* MDHT value             */
+                .t_expire    = 86400, /* Expire after 1 day     */
+                .t_refresh   = 900,   /* MDHT value.            */
+                .t_replicate = 900    /* MDHT value.            */
+        }
+};
+
+/* TODO: Move hash algorithm in directory config */
+struct dir_config {
+        enum pol_dir pol;
+        union {
+                struct dir_dht_config dht;
+        };
+};
+
+static const struct dir_config default_dir_config = {
+        .pol = DIR_DHT,
+        .dht = {
+                .params = {
+                        .alpha       = 3,
+                        .k           = 8,
+                        .t_expire    = 86400,
+                        .t_refresh   = 900,
+                        .t_replicate = 900
+                }
+        }
+};
+
 /* IPCP configuration */
 struct uni_config {
         struct dt_config    dt;
+        struct dir_config   dir;
         enum pol_addr_auth  addr_auth_type;
         enum pol_cong_avoid cong_avoid;
 };
 
+static const struct uni_config default_uni_config = {
+        .dt = {
+                .addr_size    = 4,
+                .eid_size     = 8,
+                .max_ttl      = 60,
+                .routing_type = ROUTING_LINK_STATE
+        },
+        .dir = {
+                .pol = DIR_DHT,
+                .dht = {
+                        .params = {
+                                .alpha       = 3,
+                                .k           = 8,
+                                .t_expire    = 86400,
+                                .t_refresh   = 900,
+                                .t_replicate = 900
+                        }
+                }
+        },
+        .addr_auth_type = ADDR_AUTH_FLAT_RANDOM,
+        .cong_avoid     = CA_MB_ECN
+};
+
 struct eth_config {
         char     dev[DEV_NAME_SIZE + 1];
         uint16_t ethertype; /* DIX only*/
@@ -108,16 +209,9 @@ struct udp_config {
 };
 
 /* Layers */
-enum pol_dir_hash {
-        DIR_HASH_SHA3_224,
-        DIR_HASH_SHA3_256,
-        DIR_HASH_SHA3_384,
-        DIR_HASH_SHA3_512,
-        DIR_HASH_INVALID
-};
-
 struct layer_info {
         char              name[LAYER_NAME_SIZE + 1];
+        /* TODO: Move this to directory info ? */
         enum pol_dir_hash dir_hash_algo;
 };
 
@@ -177,6 +271,18 @@ static const struct ipcp_config uni_default_conf = {
                         .max_ttl      = 60,
                         .routing_type = ROUTING_LINK_STATE
                 },
+                .dir = {
+                        .pol = DIR_DHT,
+                        .dht = {
+                                .params = {
+                                        .alpha       = 3,
+                                        .k           = 8,
+                                        .t_expire    = 86400,
+                                        .t_refresh   = 900,
+                                        .t_replicate = 900
+                                }
+                        }
+                },
                 .addr_auth_type = ADDR_AUTH_FLAT_RANDOM,
                 .cong_avoid     = CA_MB_ECN
         }
diff --git a/include/ouroboros/logs.h b/include/ouroboros/logs.h
index db49ae32..f1c401fa 100644
--- a/include/ouroboros/logs.h
+++ b/include/ouroboros/logs.h
@@ -37,12 +37,14 @@
 #define CLR_RED     "\x1b[31m"
 #define CLR_GREEN   "\x1b[32m"
 #define CLR_YELLOW  "\x1b[33m"
+#define CLR_BLUE    "\x1b[34m"
 #define CLR_RESET   "\x1b[0m"
 
 #define DEBUG_CODE "DB"
 #define ERROR_CODE "EE"
 #define WARN_CODE  "WW"
 #define INFO_CODE  "II"
+#define PROTO_CODE "PP"
 
 extern bool log_syslog;
 
@@ -98,9 +100,15 @@ void log_fini(void);
 #define log_dbg(...)  __olog("", DEBUG_CODE, LOG_DEBUG, __VA_ARGS__)
 #define log_dbg_id(id, fmt, ...)                                              \
         __olog_id("", DEBUG_CODE, LOG_DEBUG, id, fmt, ## __VA_ARGS__)
+#define log_proto(...) __olog(CLR_BLUE, PROTO_CODE, LOG_DEBUG, __VA_ARGS__)
+#define log_proto_id(id, fmt, ...)                                             \
+        __olog_id(CLR_BLUE, INFO_CODE, LOG_INFO, id, fmt, ## __VA_ARGS__)
+
 #else
 #define log_dbg(...)  do { } while (0)
 #define log_dbg_id(...)  do { } while (0)
+#define log_proto(...) do { } while (0)
+#define log_proto_id(...) do { } while (0)
 #endif
 
 #endif /* OUROBOROS_LIB_LOGS_H */
diff --git a/include/ouroboros/protobuf.h b/include/ouroboros/protobuf.h
index 9d38afb1..bf49261c 100644
--- a/include/ouroboros/protobuf.h
+++ b/include/ouroboros/protobuf.h
@@ -31,31 +31,33 @@
 #include <ouroboros/serdes-oep.h>
 
 #include "ipcp_config.pb-c.h"
-typedef IpcpConfigMsg ipcp_config_msg_t;
-typedef DtConfigMsg   dt_config_msg_t;
-typedef EthConfigMsg  eth_config_msg_t;
-typedef UdpConfigMsg  udp_config_msg_t;
-typedef UniConfigMsg  uni_config_msg_t;
+typedef IpcpConfigMsg   ipcp_config_msg_t;
+typedef DtConfigMsg     dt_config_msg_t;
+typedef DirConfigMsg    dir_config_msg_t;
+typedef DirDhtConfigMsg dir_dht_config_msg_t;
+typedef EthConfigMsg    eth_config_msg_t;
+typedef UdpConfigMsg    udp_config_msg_t;
+typedef UniConfigMsg    uni_config_msg_t;
 
 #include "ipcp.pb-c.h"
-typedef IpcpMsg       ipcp_msg_t;
+typedef IpcpMsg         ipcp_msg_t;
 
 #include "irm.pb-c.h"
-typedef IrmMsg        irm_msg_t;
-typedef TimespecMsg   timespec_msg_t;
-typedef IpcpInfoMsg   ipcp_info_msg_t;
-typedef IpcpListMsg   ipcp_list_msg_t;
+typedef IrmMsg          irm_msg_t;
+typedef TimespecMsg     timespec_msg_t;
+typedef IpcpInfoMsg     ipcp_info_msg_t;
+typedef IpcpListMsg     ipcp_list_msg_t;
 
 #include "model.pb-c.h"
-typedef FlowInfoMsg    flow_info_msg_t;
-typedef LayerInfoMsg   layer_info_msg_t;
-typedef NameInfoMsg    name_info_msg_t;
-typedef QosspecMsg     qosspec_msg_t;
+typedef FlowInfoMsg      flow_info_msg_t;
+typedef LayerInfoMsg     layer_info_msg_t;
+typedef NameInfoMsg      name_info_msg_t;
+typedef QosspecMsg       qosspec_msg_t;
 
 #include "enroll.pb-c.h"
-typedef EnrollReqMsg   enroll_req_msg_t;
-typedef EnrollRespMsg  enroll_resp_msg_t;
-typedef EnrollAckMsg   enroll_ack_msg_t;
+typedef EnrollReqMsg     enroll_req_msg_t;
+typedef EnrollRespMsg    enroll_resp_msg_t;
+typedef EnrollAckMsg     enroll_ack_msg_t;
 
 /* IPCP configuration */
 timespec_msg_t *    timespec_s_to_msg(const struct timespec * s);
diff --git a/include/ouroboros/rib.h b/include/ouroboros/rib.h
index 6aabe8f7..cdc5a9d5 100644
--- a/include/ouroboros/rib.h
+++ b/include/ouroboros/rib.h
@@ -25,6 +25,8 @@
 
 #define RIB_PATH_LEN  300
 #define RIB_SEPARATOR "/"
+#define RIB_TM_STRLEN 26
+#define RIB_TM_FORMAT "%F %T (UTC)"
 
 #include <sys/types.h>
 
diff --git a/include/ouroboros/serdes-oep.h b/include/ouroboros/serdes-oep.h
index 69ba71a4..af4446c1 100644
--- a/include/ouroboros/serdes-oep.h
+++ b/include/ouroboros/serdes-oep.h
@@ -33,7 +33,6 @@
 #define ENROLL_ID_LEN 8
 
 struct enroll_req {
-        /* TODO: Authentication */
         uint8_t id[ENROLL_ID_LEN];
 };
 
@@ -67,4 +66,12 @@ ssize_t enroll_ack_ser(const struct enroll_ack * ack,
 int     enroll_ack_des(struct enroll_ack * ack,
                        const buffer_t      buf);
 
+#ifdef DEBUG_PROTO_OEP
+void    debug_enroll_req(const struct enroll_req * req);
+
+void    debug_enroll_resp(const struct enroll_resp * resp);
+
+void    debug_enroll_ack(const struct enroll_ack * ack);
+#endif /* DEBUG_PROTO_OEP */
+
 #endif /* OUROBOROS_LIB_SERDES_OEP_H*/
diff --git a/include/ouroboros/test.h b/include/ouroboros/test.h
index 12214f15..bccf9ccd 100644
--- a/include/ouroboros/test.h
+++ b/include/ouroboros/test.h
@@ -23,8 +23,6 @@
 #ifndef OUROBOROS_LIB_TEST_H
 #define OUROBOROS_LIB_TEST_H
 
-#define OUROBOROS_TEST
-
 #include <errno.h>
 #include <stdio.h>
 #include <string.h>
@@ -32,7 +30,6 @@
 #include <sys/wait.h>
 #include <sys/types.h>
 
-
 #define TEST_RC_SUCCESS  0
 #define TEST_RC_SKIP     1
 #define TEST_RC_FAIL    -1
@@ -44,19 +41,19 @@
         } while (0)
 #define TEST_SUCCESS()                                                        \
         do {                                                                  \
-                printf("%s succeeded.\n", __func__);                          \
+                printf("\x1b[32m%s succeeded.\x1b[0m\n", __func__);            \
                 fflush(stdout);                                               \
         } while (0)
 
 #define TEST_SKIPPED()                                                        \
         do {                                                                  \
-                printf("%s skipped.\n", __func__);                            \
+                printf("\x1b[33m%s skipped.\x1b[0m\n", __func__);             \
                 fflush(stdout);                                               \
         } while (0)
 
 #define TEST_FAIL()                                                           \
         do {                                                                  \
-                printf("%s failed.\n", __func__);                             \
+                printf("\x1b[31m%s failed.\x1b[0m\n", __func__);              \
                 fflush(stdout);                                               \
         } while (0)
 
diff --git a/include/ouroboros/time.h b/include/ouroboros/time.h
index 470c99a0..3bd6a257 100644
--- a/include/ouroboros/time.h
+++ b/include/ouroboros/time.h
@@ -31,8 +31,8 @@
 #undef BILLION
 #endif
 
-#define MILLION  1000000L
-#define BILLION  1000000000L
+#define MILLION  1000000LL
+#define BILLION  1000000000LL
 
 #include <time.h>
 #include <sys/time.h>
diff --git a/include/ouroboros/utils.h b/include/ouroboros/utils.h
index e1f0ca0e..acd27a8f 100644
--- a/include/ouroboros/utils.h
+++ b/include/ouroboros/utils.h
@@ -40,6 +40,9 @@ typedef struct {
         uint8_t * data;
 } buffer_t;
 
+int bufcmp(const buffer_t * a,
+           const buffer_t * b);
+
 /*
  * Returns the number of characters a uint would
  * need when represented as a string
@@ -59,11 +62,17 @@ void    argvfree(char ** argv);
 /* destroy a ** */
 #define freepp(type, ptr, len)                          \
         do {                                            \
-                if (len == 0)                           \
-                        break;                          \
-                while (len > 0)                         \
-                        free(((type **) ptr)[--len]);   \
+                while (len-- > 0)                       \
+                        free(((type **) ptr)[len]);     \
+                free(ptr);                              \
+        } while (0)
+
+/* destroys an array of buffers */
+#define freebufs(ptr, len)                              \
+        do {                                            \
+                while ((len)-- > 0)                     \
+                        freebuf((ptr)[len]);            \
                 free(ptr);                              \
-        } while (0);
+        } while (0)
 
 #endif /* OUROBOROS_LIB_UTILS_H */