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>

2 files changed, 133 insertions, 90 deletions

diff --git a/src/tools/irm/CMakeLists.txt b/src/tools/irm/CMakeLists.txt
index e5e5c466..7acd5396 100644
--- a/src/tools/irm/CMakeLists.txt
+++ b/src/tools/irm/CMakeLists.txt
@@ -4,7 +4,7 @@ include_directories(${CMAKE_CURRENT_BINARY_DIR})
 include_directories(${CMAKE_SOURCE_DIR}/include)
 include_directories(${CMAKE_BINARY_DIR}/include)
 
-set(SOURCE_FILES
+set(TOOLS_IRM_SOURCE_FILES
   # Add source files here
   irm.c
   irm_bind_program.c
@@ -32,8 +32,11 @@ set(SOURCE_FILES
   irm_utils.c
   )
 
-add_executable(irm ${SOURCE_FILES})
+add_executable(irm ${TOOLS_IRM_SOURCE_FILES})
 
 target_link_libraries(irm LINK_PUBLIC ouroboros-irm)
 
 install(TARGETS irm RUNTIME DESTINATION ${CMAKE_INSTALL_SBINDIR})
+
+# enable when we have tests
+# add_subdirectory(tests)
diff --git a/src/tools/irm/irm_ipcp_bootstrap.c b/src/tools/irm/irm_ipcp_bootstrap.c
index b8e5c54d..1032e09d 100644
--- a/src/tools/irm/irm_ipcp_bootstrap.c
+++ b/src/tools/irm/irm_ipcp_bootstrap.c
@@ -50,86 +50,109 @@
 #include <sys/socket.h>
 #endif
 
-#define UNICAST                "unicast"
-#define BROADCAST              "broadcast"
-#define UDP                    "udp"
-#define ETH_LLC                "eth-llc"
-#define ETH_DIX                "eth-dix"
-#define LOCAL                  "local"
+#define UNICAST        "unicast"
+#define BROADCAST      "broadcast"
+#define IP_UDP         "udp"
+#define ETH_LLC        "eth-llc"
+#define ETH_DIX        "eth-dix"
+#define LOCAL          "local"
 
-#define MD5                    "MD5"
-#define SHA3_224               "SHA3_224"
-#define SHA3_256               "SHA3_256"
-#define SHA3_384               "SHA3_384"
-#define SHA3_512               "SHA3_512"
+#define MD5            "MD5"
+#define SHA3_224       "SHA3_224"
+#define SHA3_256       "SHA3_256"
+#define SHA3_384       "SHA3_384"
+#define SHA3_512       "SHA3_512"
 
-#define DEFAULT_ADDR_SIZE      4
-#define DEFAULT_EID_SIZE       8
-#define DEFAULT_DDNS           0
-#define DEFAULT_TTL            60
-#define DEFAULT_ADDR_AUTH      ADDR_AUTH_FLAT_RANDOM
-#define DEFAULT_ROUTING        ROUTING_LINK_STATE
-#define DEFAULT_CONG_AVOID     CA_MB_ECN
-#define DEFAULT_HASH_ALGO      DIR_HASH_SHA3_256
-#define DEFAULT_ETHERTYPE      0xA000
-#define DEFAULT_UDP_PORT       0x0D6B /* 3435 */
+#define FLAT_RANDOM    "flat"
+#define DHT_DIR        "DHT"
+#define LINK_STATE     "link_state"
+#define LINK_STATE_LFA "lfa"
+#define LINK_STATE_ECM "ecmp"
+#define NONE_CA        "none"
+#define MB_ECN_CA      "mb-ecn"
 
-#define FLAT_RANDOM_ADDR_AUTH  "flat"
-#define LINK_STATE_ROUTING     "link_state"
-#define LINK_STATE_LFA_ROUTING "lfa"
-#define LINK_STATE_ECM_ROUTING "ecmp"
-#define NONE_CA                "none"
-#define MB_ECN_CA              "mb-ecn"
+#define DT(x)  default_dt_config.x
+#define DHT(x) default_dht_config.params.x
+#define UNI(x) default_uni_config.x
+#define DIX(x) eth_dix_default_conf.eth.x
+#define LLC(x) eth_llc_default_conf.eth.x
+#define UDP(x) udp_default_conf.udp.x
+
+static char * usage_str = \
+        "Usage: irm ipcp bootstrap\n"
+        "           name <ipcp name>\n"
+        "           layer <layer name>\n"
+        "           [type [TYPE]]\n"
+        "where TYPE in {" UNICAST " " BROADCAST " " LOCAL " "
+        IP_UDP " " ETH_LLC " " ETH_DIX "},\n\n"
+        "if TYPE == " UNICAST "\n"
+        "        [addr_auth <ADDRESS_POLICY> (default: %s)]\n"
+        "        [directory <DIRECTORY_POLICY> (default: %s)]\n"
+        "        [hash [ALGORITHM] (default: %s)]\n"
+        "        [routing <ROUTING_POLICY> (default: %s)]\n"
+        "        [congestion <CONG_POLICY> (default: %s)]\n"
+        "        [autobind]\n"
+        "where ADDRESS_POLICY in {" FLAT_RANDOM "}\n"
+        "    DIRECTORY_POLICY in {" DHT_DIR "}\n"
+        "    ALGORITHM in {" SHA3_224 " " SHA3_256 " "
+        SHA3_384 " " SHA3_512 "}\n\n"
+        "    ROUTING_POLICY in {" LINK_STATE " "
+        LINK_STATE_LFA " " LINK_STATE_ECM "}\n"
+        "    CONG_POLICY in {" NONE_CA " " MB_ECN_CA "}\n"
+        "    [Data Transfer Constants]\n"
+        "        [addr <address size> (default: %d)]\n"
+        "        [eid <eid size> (default: %d)]\n"
+        "        [ttl <max time-to-live>, default: %d)]\n"
+        "if DIRECTORY_POLICY == " DHT_DIR "\n"
+        "        [dht_alpha <search factor> (default: %u)]\n"
+        "        [dht_k <replication factor> (default: %u)]\n"
+        "        [dht_t_expire <expiration (s)> (default: %u)]\n"
+        "        [dht_t_refresh <contact refresh (s)> (default: %u)]\n"
+        "        [dht_t_replicate <replication (s)> (default: %u)]\n"
+        "if TYPE == " IP_UDP "\n"
+        "        ip <IP address in dotted notation>\n"
+        "        [port <UDP port> (default: %d)]\n"
+        "        [dns <DDNS IP address in dotted notation>"
+        " (default: none)]\n\n"
+        "if TYPE == " ETH_LLC "\n"
+        "        dev <interface name>\n"
+        "        [hash [ALGORITHM] (default: %s)]\n"
+        "where ALGORITHM in {" SHA3_224 " " SHA3_256 " "
+        SHA3_384 " " SHA3_512 "}\n\n"
+        "if TYPE == " ETH_DIX "\n"
+        "        dev <interface name>\n"
+        "        [ethertype <ethertype> (default: 0x%4X)]\n"
+        "        [hash [ALGORITHM] (default: %s)]\n"
+        "where ALGORITHM in {" SHA3_224 " " SHA3_256 " "
+        SHA3_384 " " SHA3_512 "}\n\n"
+        "if TYPE == " LOCAL "\n"
+        "        [hash [ALGORITHM] (default: %s)]\n"
+        "where ALGORITHM in {" SHA3_224 " " SHA3_256 " "
+        SHA3_384 " " SHA3_512 "}\n\n"
+        "if TYPE == " BROADCAST "\n"
+        "        [autobind]\n\n";
 
 static void usage(void)
 {
         /* FIXME: Add ipcp_config stuff. */
-        printf("Usage: irm ipcp bootstrap\n"
-               "                name <ipcp name>\n"
-               "                layer <layer name>\n"
-               "                [type [TYPE]]\n"
-               "where TYPE in {" UNICAST " " BROADCAST " " LOCAL " "
-               UDP " " ETH_LLC " " ETH_DIX "},\n\n"
-               "if TYPE == " UNICAST "\n"
-               "                [addr <address size> (default: %d)]\n"
-               "                [eid <eid size> (default: %d)]\n"
-               "                [ttl (max time-to-live value, default: %d)]\n"
-               "                [addr_auth <ADDRESS_POLICY> (default: %s)]\n"
-               "                [routing <ROUTING_POLICY> (default: %s)]\n"
-               "                [congestion <CONG_POLICY> (default: %s)]\n"
-               "                [hash [ALGORITHM] (default: %s)]\n"
-               "                [autobind]\n"
-               "where ADDRESS_POLICY in {" FLAT_RANDOM_ADDR_AUTH "}\n"
-               "      ROUTING_POLICY in {" LINK_STATE_ROUTING " "
-               LINK_STATE_LFA_ROUTING " " LINK_STATE_ECM_ROUTING "}\n"
-               "      CONG_POLICY in {" NONE_CA " " MB_ECN_CA "}\n"
-               "      ALGORITHM in {" SHA3_224 " " SHA3_256 " "
-               SHA3_384 " " SHA3_512 "}\n\n"
-               "if TYPE == " UDP "\n"
-               "                ip <IP address in dotted notation>\n"
-               "                [port <UDP port> (default: %d)]\n"
-               "                [dns <DDNS IP address in dotted notation>"
-               " (default: none)]\n\n"
-               "if TYPE == " ETH_LLC "\n"
-               "                dev <interface name>\n"
-               "                [hash [ALGORITHM] (default: %s)]\n"
-               "where ALGORITHM in {" SHA3_224 " " SHA3_256 " "
-               SHA3_384 " " SHA3_512 "}\n\n"
-               "if TYPE == " ETH_DIX "\n"
-               "                dev <interface name>\n"
-               "                [ethertype <ethertype> (default: 0x%4X)]\n"
-               "                [hash [ALGORITHM] (default: %s)]\n"
-               "where ALGORITHM in {" SHA3_224 " " SHA3_256 " "
-               SHA3_384 " " SHA3_512 "}\n\n"
-               "if TYPE == " LOCAL "\n"
-               "                [hash [ALGORITHM] (default: %s)]\n"
-               "where ALGORITHM in {" SHA3_224 " " SHA3_256 " "
-               SHA3_384 " " SHA3_512 "}\n\n"
-               "if TYPE == " BROADCAST "\n"
-               "                [autobind]\n\n",
-               DEFAULT_ADDR_SIZE, DEFAULT_EID_SIZE, DEFAULT_TTL,
-               FLAT_RANDOM_ADDR_AUTH, LINK_STATE_ROUTING, MB_ECN_CA,
-               SHA3_256, DEFAULT_UDP_PORT, SHA3_256, 0xA000, SHA3_256,
+        printf(usage_str,
+               /* unicast */
+               FLAT_RANDOM, DHT_DIR, SHA3_256, LINK_STATE, MB_ECN_CA,
+               /* dt */
+               DT(addr_size), DT(eid_size), DT(max_ttl),
+               /* dht */
+               DHT(alpha), DHT(k), DHT(t_expire),
+               DHT(t_refresh), DHT(t_replicate),
+               /* udp */
+               UDP(port),
+               /* eth_llc */
+               SHA3_256,
+               /* eth_dix */
+               DIX(ethertype),
+               SHA3_256,
+               /* local */
+               SHA3_256,
+               /* broadcast */
                SHA3_256);
 }
 
@@ -139,26 +162,27 @@ int do_bootstrap_ipcp(int     argc,
         char *                  ipcp           = NULL;
         pid_t                   pid            = -1;
         struct ipcp_config      conf;
-        uint8_t                 addr_size      = DEFAULT_ADDR_SIZE;
-        uint8_t                 eid_size       = DEFAULT_EID_SIZE;
-        uint8_t                 max_ttl        = DEFAULT_TTL;
-        enum pol_addr_auth      addr_auth_type = DEFAULT_ADDR_AUTH;
-        enum pol_routing        routing_type   = DEFAULT_ROUTING;
-        enum pol_dir_hash       hash_algo      = DEFAULT_HASH_ALGO;
-        enum pol_cong_avoid     cong_avoid     = DEFAULT_CONG_AVOID;
+        struct dir_config       dir_config     = default_dir_config;
+        uint8_t                 addr_size      = DT(addr_size);
+        uint8_t                 eid_size       = DT(eid_size);
+        uint8_t                 max_ttl        = DT(max_ttl);
+        enum pol_routing        routing_type   = DT(routing_type);
+        enum pol_addr_auth      addr_auth_type = UNI(addr_auth_type);
+        enum pol_cong_avoid     cong_avoid     = UNI(cong_avoid);
+        enum pol_dir_hash       hash_algo      = DIR_HASH_SHA3_256;
         uint32_t                ip_addr        = 0;
-        uint32_t                dns_addr       = DEFAULT_DDNS;
+        uint32_t                dns_addr       = UDP(dns_addr);
+        int                     port           = UDP(port);
         char *                  ipcp_type      = NULL;
         enum ipcp_type          type           = IPCP_INVALID;
         char *                  layer          = NULL;
         char *                  dev            = NULL;
-        uint16_t                ethertype      = DEFAULT_ETHERTYPE;
+        uint16_t                ethertype      = DIX(ethertype);
         struct ipcp_list_info * ipcps;
         ssize_t                 len            = 0;
         int                     i              = 0;
         bool                    autobind       = false;
         int                     cargs;
-        int                     port           = DEFAULT_UDP_PORT;
 
         while (argc > 0) {
                 cargs = 2;
@@ -211,17 +235,32 @@ int do_bootstrap_ipcp(int     argc,
                         autobind = true;
                         cargs = 1;
                 } else if (matches(*argv, "addr_auth") == 0) {
-                        if (strcmp(FLAT_RANDOM_ADDR_AUTH, *(argv + 1)) == 0)
+                        if (strcmp(FLAT_RANDOM, *(argv + 1)) == 0)
                                 addr_auth_type = ADDR_AUTH_FLAT_RANDOM;
                         else
                                 goto unknown_param;
+                } else if (matches(*argv, "directory") == 0) {
+                        if (strcmp(DHT_DIR, *(argv + 1)) == 0)
+                                dir_config.pol = DIR_DHT;
+                        else
+                                goto unknown_param;
+                } else if (matches(*argv, "dht_alpha") == 0) {
+                        dir_config.dht.params.alpha = atoi(*(argv + 1));
+                } else if (matches(*argv, "dht_k") == 0) {
+                        dir_config.dht.params.k = atoi(*(argv + 1));
+                } else if (matches(*argv, "dht_t_expire") == 0) {
+                        dir_config.dht.params.t_expire = atoi(*(argv + 1));
+                } else if (matches(*argv, "dht_t_refresh") == 0) {
+                        dir_config.dht.params.t_refresh = atoi(*(argv + 1));
+                } else if (matches(*argv, "dht_t_replicate") == 0) {
+                        dir_config.dht.params.t_replicate = atoi(*(argv + 1));
                 } else if (matches(*argv, "routing") == 0) {
-                        if (strcmp(LINK_STATE_ROUTING, *(argv + 1)) == 0)
+                        if (strcmp(LINK_STATE, *(argv + 1)) == 0)
                                 routing_type = ROUTING_LINK_STATE;
-                        else if (strcmp(LINK_STATE_LFA_ROUTING,
+                        else if (strcmp(LINK_STATE_LFA,
                                         *(argv + 1)) == 0)
                                 routing_type = ROUTING_LINK_STATE_LFA;
-                        else if (strcmp(LINK_STATE_ECM_ROUTING,
+                        else if (strcmp(LINK_STATE_ECM,
                                         *(argv + 1)) == 0)
                                 routing_type = ROUTING_LINK_STATE_ECMP;
                         else
@@ -261,7 +300,7 @@ int do_bootstrap_ipcp(int     argc,
                         type = IPCP_UNICAST;
                 else if (strcmp(ipcp_type, BROADCAST) == 0)
                         type = IPCP_BROADCAST;
-                else if (strcmp(ipcp_type, UDP) == 0)
+                else if (strcmp(ipcp_type, IP_UDP) == 0)
                         type = IPCP_UDP;
                 else if (strcmp(ipcp_type, ETH_LLC) == 0)
                         type = IPCP_ETH_LLC;
@@ -318,6 +357,7 @@ int do_bootstrap_ipcp(int     argc,
                                 conf.unicast.dt.routing_type = routing_type;
                                 conf.unicast.addr_auth_type  = addr_auth_type;
                                 conf.unicast.cong_avoid      = cong_avoid;
+                                conf.unicast.dir             = dir_config;
                                 break;
                         case IPCP_UDP:
                                 if (ip_addr == 0)