New upstream version 1.16.0 upstream/1.16.0

8 files changed, 2064 insertions, 1013 deletions

diff --git a/shared/n-acd/src/n-acd-bpf-fallback.c b/shared/n-acd/src/n-acd-bpf-fallback.c
new file mode 100644
index 00000000..7270cfd9
--- /dev/null
+++ b/shared/n-acd/src/n-acd-bpf-fallback.c
@@ -0,0 +1,29 @@
+/*
+ * A noop implementation of eBPF filter for IPv4 Address Conflict Detection
+ *
+ * These are a collection of dummy functions that have no effect, but allows
+ * n-acd to compile without eBPF support.
+ *
+ * See n-acd-bpf.c for documentation.
+ */
+
+#include <stddef.h>
+#include "n-acd-private.h"
+
+int n_acd_bpf_map_create(int *mapfdp, size_t max_entries) {
+        *mapfdp = -1;
+        return 0;
+}
+
+int n_acd_bpf_map_add(int mapfd, struct in_addr *addrp) {
+        return 0;
+}
+
+int n_acd_bpf_map_remove(int mapfd, struct in_addr *addrp) {
+        return 0;
+}
+
+int n_acd_bpf_compile(int *progfdp, int mapfd, struct ether_addr *macp) {
+        *progfdp = -1;
+        return 0;
+}
diff --git a/shared/n-acd/src/n-acd-bpf.c b/shared/n-acd/src/n-acd-bpf.c
new file mode 100644
index 00000000..771a28ee
--- /dev/null
+++ b/shared/n-acd/src/n-acd-bpf.c
@@ -0,0 +1,316 @@
+/*
+ * eBPF filter for IPv4 Address Conflict Detection
+ *
+ * An eBPF map and an eBPF program are provided. The map contains all the
+ * addresses address conflict detection is performed on, and the program
+ * filters out all packets except exactly the packets relevant to the ACD
+ * protocol on the addresses currently in the map.
+ *
+ * Note that userspace still has to filter the incoming packets, as filter
+ * are applied when packets are queued on the socket, not when userspace
+ * receives them. It is therefore possible to receive packets about addresses
+ * that have already been removed.
+ */
+
+#include <errno.h>
+#include <inttypes.h>
+#include <linux/bpf.h>
+#include <netinet/if_ether.h>
+#include <netinet/in.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/resource.h>
+#include <sys/syscall.h>
+#include <unistd.h>
+#include "n-acd-private.h"
+
+#define BPF_LD_ABS(SIZE, IMM)                                                   \
+        ((struct bpf_insn) {                                                    \
+                .code           = BPF_LD | BPF_SIZE(SIZE) | BPF_ABS,            \
+                .dst_reg        = 0,                                            \
+                .src_reg        = 0,                                            \
+                .off            = 0,                                            \
+                .imm            = IMM,                                          \
+        })
+
+#define BPF_LDX_MEM(SIZE, DST, SRC, OFF)                                        \
+        ((struct bpf_insn) {                                                    \
+                .code           = BPF_LDX | BPF_SIZE(SIZE) | BPF_MEM,           \
+                .dst_reg        = DST,                                          \
+                .src_reg        = SRC,                                          \
+                .off            = OFF,                                          \
+                .imm            = 0,                                            \
+        })
+
+#define BPF_LD_MAP_FD(DST, MAP_FD)                                              \
+        ((struct bpf_insn) {                                                    \
+                .code           = BPF_LD | BPF_DW | BPF_IMM,                    \
+                .dst_reg        = DST,                                          \
+                .src_reg        = BPF_PSEUDO_MAP_FD,                            \
+                .off            = 0,                                            \
+                .imm            = (__u32) (MAP_FD),                             \
+        }),                                                                     \
+        ((struct bpf_insn) {                                                    \
+                .code           = 0, /* zero is reserved opcode */              \
+                .dst_reg        = 0,                                            \
+                .src_reg        = 0,                                            \
+                .off            = 0,                                            \
+                .imm            = ((__u64) (MAP_FD)) >> 32,                     \
+        })
+
+#define BPF_ALU_REG(OP, DST, SRC)                                               \
+        ((struct bpf_insn) {                                                    \
+                .code           = BPF_ALU64 | BPF_OP(OP) | BPF_X,               \
+                .dst_reg        = DST,                                          \
+                .src_reg        = SRC,                                          \
+                .off            = 0,                                            \
+                .imm            = 0,                                            \
+        })
+
+#define BPF_ALU_IMM(OP, DST, IMM)                                               \
+        ((struct bpf_insn) {                                                    \
+                .code           = BPF_ALU64 | BPF_OP(OP) | BPF_K,               \
+                .dst_reg        = DST,                                          \
+                .src_reg        = 0,                                            \
+                .off            = 0,                                            \
+                .imm            = IMM,                                          \
+        })
+
+#define BPF_MOV_REG(DST, SRC)                                                   \
+        ((struct bpf_insn) {                                                    \
+                .code           = BPF_ALU64 | BPF_MOV | BPF_X,                  \
+                .dst_reg        = DST,                                          \
+                .src_reg        = SRC,                                          \
+                .off            = 0,                                            \
+                .imm            = 0,                                            \
+        })
+
+#define BPF_MOV_IMM(DST, IMM)                                                   \
+        ((struct bpf_insn) {                                                    \
+                .code           = BPF_ALU64 | BPF_MOV | BPF_K,                  \
+                .dst_reg        = DST,                                          \
+                .src_reg        = 0,                                            \
+                .off            = 0,                                            \
+                .imm            = IMM,                                          \
+        })
+
+#define BPF_STX_MEM(SIZE, DST, SRC, OFF)                                        \
+        ((struct bpf_insn) {                                                    \
+                .code           = BPF_STX | BPF_SIZE(SIZE) | BPF_MEM,           \
+                .dst_reg        = DST,                                          \
+                .src_reg        = SRC,                                          \
+                .off            = OFF,                                          \
+                .imm            = 0,                                            \
+        })
+
+#define BPF_JMP_REG(OP, DST, SRC, OFF)                                          \
+        ((struct bpf_insn) {                                                    \
+                .code           = BPF_JMP | BPF_OP(OP) | BPF_X,                 \
+                .dst_reg        = DST,                                          \
+                .src_reg        = SRC,                                          \
+                .off            = OFF,                                          \
+                .imm            = 0,                                            \
+        })
+
+#define BPF_JMP_IMM(OP, DST, IMM, OFF)                                          \
+        ((struct bpf_insn) {                                                    \
+                .code           = BPF_JMP | BPF_OP(OP) | BPF_K,                 \
+                .dst_reg        = DST,                                          \
+                .src_reg        = 0,                                            \
+                .off            = OFF,                                          \
+                .imm            = IMM,                                          \
+        })
+
+#define BPF_EMIT_CALL(FUNC)                                                     \
+        ((struct bpf_insn) {                                                    \
+                .code           = BPF_JMP | BPF_CALL,                           \
+                .dst_reg        = 0,                                            \
+                .src_reg        = 0,                                            \
+                .off            = 0,                                            \
+                .imm            = FUNC,                                         \
+        })
+
+#define BPF_EXIT_INSN()                                                         \
+        ((struct bpf_insn) {                                                    \
+                .code           = BPF_JMP | BPF_EXIT,                           \
+                .dst_reg        = 0,                                            \
+                .src_reg        = 0,                                            \
+                .off            = 0,                                            \
+                .imm            = 0,                                            \
+        })
+
+static int n_acd_syscall_bpf(int cmd, union bpf_attr *attr, unsigned int size) {
+        return (int)syscall(__NR_bpf, cmd, attr, size);
+}
+
+int n_acd_bpf_map_create(int *mapfdp, size_t max_entries) {
+        union bpf_attr attr;
+        int mapfd;
+
+        memset(&attr, 0, sizeof(attr));
+        attr = (union bpf_attr){
+                .map_type    = BPF_MAP_TYPE_HASH,
+                .key_size    = sizeof(uint32_t),
+                .value_size  = sizeof(uint8_t), /* values are never used, but must be set */
+                .max_entries = max_entries,
+        };
+
+        mapfd = n_acd_syscall_bpf(BPF_MAP_CREATE, &attr, sizeof(attr));
+        if (mapfd < 0)
+                return -errno;
+
+        *mapfdp = mapfd;
+        return 0;
+}
+
+int n_acd_bpf_map_add(int mapfd, struct in_addr *addrp) {
+        union bpf_attr attr;
+        uint32_t addr = be32toh(addrp->s_addr);
+        uint8_t _dummy = 0;
+        int r;
+
+        memset(&attr, 0, sizeof(attr));
+        attr = (union bpf_attr){
+                .map_fd = mapfd,
+                .key    = (uint64_t)(unsigned long)&addr,
+                .value  = (uint64_t)(unsigned long)&_dummy,
+                .flags  = BPF_NOEXIST,
+        };
+
+        r = n_acd_syscall_bpf(BPF_MAP_UPDATE_ELEM, &attr, sizeof(attr));
+        if (r < 0)
+                return -errno;
+
+        return 0;
+}
+
+int n_acd_bpf_map_remove(int mapfd, struct in_addr *addrp) {
+        uint32_t addr = be32toh(addrp->s_addr);
+        union bpf_attr attr;
+        int r;
+
+        memset(&attr, 0, sizeof(attr));
+        attr = (union bpf_attr){
+                .map_fd = mapfd,
+                .key    = (uint64_t)(unsigned long)&addr,
+        };
+
+        r = n_acd_syscall_bpf(BPF_MAP_DELETE_ELEM, &attr, sizeof(attr));
+        if (r < 0)
+                return -errno;
+
+        return 0;
+}
+
+int n_acd_bpf_compile(int *progfdp, int mapfd, struct ether_addr *macp) {
+        const union {
+                uint8_t u8[6];
+                uint16_t u16[3];
+                uint32_t u32[1];
+        } mac = {
+                .u8 = {
+                        macp->ether_addr_octet[0],
+                        macp->ether_addr_octet[1],
+                        macp->ether_addr_octet[2],
+                        macp->ether_addr_octet[3],
+                        macp->ether_addr_octet[4],
+                        macp->ether_addr_octet[5],
+                },
+        };
+        struct bpf_insn prog[] = {
+                /* for using BPF_LD_ABS r6 must point to the skb, currently in r1 */
+                BPF_MOV_REG(6, 1),                                              /* r6 = r1 */
+
+                /* drop the packet if it is too short */
+                BPF_LDX_MEM(BPF_W, 0, 6, offsetof(struct __sk_buff, len)),      /* r0 = skb->len */
+                BPF_JMP_IMM(BPF_JGE, 0, sizeof(struct ether_arp), 2),           /* if (r0 >= sizeof(ether_arp)) skip 2 */
+                BPF_MOV_IMM(0, 0),                                              /* r0 = 0 */
+                BPF_EXIT_INSN(),                                                /* return */
+
+                /* drop the packet if the header is not as expected */
+                BPF_LD_ABS(BPF_H, offsetof(struct ether_arp, arp_hrd)),         /* r0 = header type */
+                BPF_JMP_IMM(BPF_JEQ, 0, ARPHRD_ETHER, 2),                       /* if (r0 == ethernet) skip 2 */
+                BPF_MOV_IMM(0, 0),                                              /* r0 = 0 */
+                BPF_EXIT_INSN(),                                                /* return */
+
+                BPF_LD_ABS(BPF_H, offsetof(struct ether_arp, arp_pro)),         /* r0 = protocol */
+                BPF_JMP_IMM(BPF_JEQ, 0, ETHERTYPE_IP, 2),                       /* if (r0 == IP) skip 2 */
+                BPF_MOV_IMM(0, 0),                                              /* r0 = 0 */
+                BPF_EXIT_INSN(),                                                /* return */
+
+                BPF_LD_ABS(BPF_B, offsetof(struct ether_arp, arp_hln)),         /* r0 = hw addr length */
+                BPF_JMP_IMM(BPF_JEQ, 0, sizeof(struct ether_addr), 2),          /* if (r0 == sizeof(ether_addr)) skip 2 */
+                BPF_MOV_IMM(0, 0),                                              /* r0 = 0 */
+                BPF_EXIT_INSN(),                                                /* return */
+
+                BPF_LD_ABS(BPF_B, offsetof(struct ether_arp, arp_pln)),         /* r0 = protocol addr length */
+                BPF_JMP_IMM(BPF_JEQ, 0, sizeof(struct in_addr), 2),             /* if (r0 == sizeof(in_addr)) skip 2 */
+                BPF_MOV_IMM(0, 0),                                              /* r0 = 0 */
+                BPF_EXIT_INSN(),                                                /* return */
+
+                /* drop packets from our own mac address */
+                BPF_LD_ABS(BPF_W, offsetof(struct ether_arp, arp_sha)),         /* r0 = first four bytes of packet mac address */
+                BPF_JMP_IMM(BPF_JNE, 0, be32toh(mac.u32[0]), 4),                /* if (r0 != first four bytes of our mac address) skip 4 */
+                BPF_LD_ABS(BPF_H, offsetof(struct ether_arp, arp_sha) + 4),     /* r0 = last two bytes of packet mac address */
+                BPF_JMP_IMM(BPF_JNE, 0, be16toh(mac.u16[2]), 2),                /* if (r0 != last two bytes of our mac address) skip 2 */
+                BPF_MOV_IMM(0, 0),                                              /* r0 = 0 */
+                BPF_EXIT_INSN(),                                                /* return */
+
+                /*
+                 * We listen for two kinds of packets:
+                 *  Conflicts)
+                 *    These are requests or replies with the sender address not set to INADDR_ANY. The
+                 *    conflicted address is the sender address, remember this in r7.
+                 *  Probes)
+                 *    These are requests with the sender address set to INADDR_ANY. The probed address
+                 *    is the target address, remember this in r7.
+                 *  Any other packets are dropped.
+                 */
+                BPF_LD_ABS(BPF_W, offsetof(struct ether_arp, arp_spa)),         /* r0 = sender ip address */
+                BPF_JMP_IMM(BPF_JEQ, 0, 0, 7),                                  /* if (r0 == 0) skip 7 */
+                BPF_MOV_REG(7, 0),                                              /* r7 = r0 */
+                BPF_LD_ABS(BPF_H, offsetof(struct ether_arp, arp_op)),          /* r0 = operation */
+                BPF_JMP_IMM(BPF_JEQ, 0, ARPOP_REQUEST, 3),                      /* if (r0 == request) skip 3 */
+                BPF_JMP_IMM(BPF_JEQ, 0, ARPOP_REPLY, 2),                        /* if (r0 == reply) skip 2 */
+                BPF_MOV_IMM(0, 0),                                              /* r0 = 0 */
+                BPF_EXIT_INSN(),                                                /* return */
+                BPF_JMP_IMM(BPF_JA, 0, 0, 6),                                   /* skip 6 */
+                BPF_LD_ABS(BPF_W, offsetof(struct ether_arp, arp_tpa)),         /* r0 = target ip address */
+                BPF_MOV_REG(7, 0),                                              /* r7 = r0 */
+                BPF_LD_ABS(BPF_H, offsetof(struct ether_arp, arp_op)),          /* r0 = operation */
+                BPF_JMP_IMM(BPF_JEQ, 0, ARPOP_REQUEST, 2),                      /* if (r0 == request) skip 2 */
+                BPF_MOV_IMM(0, 0),                                              /* r0 = 0 */
+                BPF_EXIT_INSN(),                                                /* return */
+
+                /* check if the probe or conflict is for an address we are monitoring */
+                BPF_STX_MEM(BPF_W, 10, 7, -4),                                  /* *(uint32_t*)fp - 4 = r7 */
+                BPF_MOV_REG(2, 10),                                             /* r2 = fp */
+                BPF_ALU_IMM(BPF_ADD, 2, -4),                                    /* r2 -= 4 */
+                BPF_LD_MAP_FD(1, mapfd),                                        /* r1 = mapfd */
+                BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),                        /* r0 = map_lookup_elem(r1, r2) */
+                BPF_JMP_IMM(BPF_JNE, 0, 0, 2),                                  /* if (r0 != NULL) skip 2 */
+                BPF_MOV_IMM(0, 0),                                              /* r0 = 0 */
+                BPF_EXIT_INSN(),                                                /* return */
+
+                /* return exactly the packet length*/
+                BPF_MOV_IMM(0, sizeof(struct ether_arp)),                       /* r0 = sizeof(struct ether_arp) */
+                BPF_EXIT_INSN(),                                                /* return */
+        };
+        union bpf_attr attr;
+        int progfd;
+
+        memset(&attr, 0, sizeof(attr));
+        attr = (union bpf_attr){
+                .prog_type = BPF_PROG_TYPE_SOCKET_FILTER,
+                .insns     = (uint64_t)(unsigned long)prog,
+                .insn_cnt  = sizeof(prog) / sizeof(*prog),
+                .license   = (uint64_t)(unsigned long)"ASL",
+        };
+
+        progfd = n_acd_syscall_bpf(BPF_PROG_LOAD, &attr, sizeof(attr));
+        if (progfd < 0)
+                return -errno;
+
+        *progfdp = progfd;
+        return 0;
+}
diff --git a/shared/n-acd/src/n-acd-private.h b/shared/n-acd/src/n-acd-private.h
new file mode 100644
index 00000000..3f207912
--- /dev/null
+++ b/shared/n-acd/src/n-acd-private.h
@@ -0,0 +1,172 @@
+#pragma once
+
+#include <c-list.h>
+#include <c-rbtree.h>
+#include <errno.h>
+#include <inttypes.h>
+#include <netinet/if_ether.h>
+#include <netinet/in.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include "util/timer.h"
+#include "n-acd.h"
+
+typedef struct NAcdEventNode NAcdEventNode;
+
+#define _cleanup_(_x) __attribute__((__cleanup__(_x)))
+#define _public_ __attribute__((__visibility__("default")))
+
+/* This augments the error-codes with internal ones that are never exposed. */
+enum {
+        _N_ACD_INTERNAL = _N_ACD_E_N,
+
+        N_ACD_E_DROPPED,
+};
+
+enum {
+        N_ACD_PROBE_STATE_PROBING,
+        N_ACD_PROBE_STATE_CONFIGURING,
+        N_ACD_PROBE_STATE_ANNOUNCING,
+        N_ACD_PROBE_STATE_FAILED,
+};
+
+struct NAcdConfig {
+        int ifindex;
+        unsigned int transport;
+        uint8_t mac[ETH_ALEN];
+        size_t n_mac;
+};
+
+#define N_ACD_CONFIG_NULL(_x) {                                                 \
+                .transport = _N_ACD_TRANSPORT_N,                                \
+        }
+
+struct NAcdProbeConfig {
+        struct in_addr ip;
+        uint64_t timeout_msecs;
+};
+
+#define N_ACD_PROBE_CONFIG_NULL(_x) {                                           \
+                .timeout_msecs = N_ACD_TIMEOUT_RFC5227,                         \
+        }
+
+struct NAcdEventNode {
+        CList acd_link;
+        CList probe_link;
+        NAcdEvent event;
+        uint8_t sender[ETH_ALEN];
+        bool is_public : 1;
+};
+
+#define N_ACD_EVENT_NODE_NULL(_x) {                                             \
+                .acd_link = C_LIST_INIT((_x).acd_link),                         \
+                .probe_link = C_LIST_INIT((_x).probe_link),                     \
+        }
+
+struct NAcd {
+        unsigned long n_refs;
+        unsigned int seed;
+        int fd_epoll;
+        int fd_socket;
+        CRBTree ip_tree;
+        CList event_list;
+        Timer timer;
+
+        /* BPF map */
+        int fd_bpf_map;
+        size_t n_bpf_map;
+        size_t max_bpf_map;
+
+        /* configuration */
+        int ifindex;
+        uint8_t mac[ETH_ALEN];
+
+        /* flags */
+        bool preempted : 1;
+};
+
+#define N_ACD_NULL(_x) {                                                        \
+                .n_refs = 1,                                                    \
+                .fd_epoll = -1,                                                 \
+                .fd_socket = -1,                                                \
+                .ip_tree = C_RBTREE_INIT,                                       \
+                .event_list = C_LIST_INIT((_x).event_list),                     \
+                .timer = TIMER_NULL((_x).timer),                                \
+                .fd_bpf_map = -1,                                               \
+        }
+
+struct NAcdProbe {
+        NAcd *acd;
+        CRBNode ip_node;
+        CList event_list;
+        Timeout timeout;
+
+        /* configuration */
+        struct in_addr ip;
+        uint64_t timeout_multiplier;
+        void *userdata;
+
+        /* state */
+        unsigned int state;
+        unsigned int n_iteration;
+        unsigned int defend;
+        uint64_t last_defend;
+};
+
+#define N_ACD_PROBE_NULL(_x) {                                                  \
+                .ip_node = C_RBNODE_INIT((_x).ip_node),                         \
+                .event_list = C_LIST_INIT((_x).event_list),                     \
+                .timeout = TIMEOUT_INIT((_x).timeout),                          \
+                .state = N_ACD_PROBE_STATE_PROBING,                             \
+                .defend = N_ACD_DEFEND_NEVER,                                   \
+        }
+
+/* events */
+
+int n_acd_event_node_new(NAcdEventNode **nodep);
+NAcdEventNode *n_acd_event_node_free(NAcdEventNode *node);
+
+/* contexts */
+
+void n_acd_remember(NAcd *acd, uint64_t now, bool success);
+int n_acd_raise(NAcd *acd, NAcdEventNode **nodep, unsigned int event);
+int n_acd_send(NAcd *acd, const struct in_addr *tpa, const struct in_addr *spa);
+int n_acd_ensure_bpf_map_space(NAcd *acd);
+
+/* probes */
+
+int n_acd_probe_new(NAcdProbe **probep, NAcd *acd, NAcdProbeConfig *config);
+int n_acd_probe_raise(NAcdProbe *probe, NAcdEventNode **nodep, unsigned int event);
+int n_acd_probe_handle_timeout(NAcdProbe *probe);
+int n_acd_probe_handle_packet(NAcdProbe *probe, struct ether_arp *packet, bool hard_conflict);
+
+/* eBPF */
+
+int n_acd_bpf_map_create(int *mapfdp, size_t max_elements);
+int n_acd_bpf_map_add(int mapfd, struct in_addr *addr);
+int n_acd_bpf_map_remove(int mapfd, struct in_addr *addr);
+
+int n_acd_bpf_compile(int *progfdp, int mapfd, struct ether_addr *mac);
+
+/* inline helpers */
+
+static inline int n_acd_errno(void) {
+        /*
+         * Compilers continuously warn about uninitialized variables since they
+         * cannot deduce that `return -errno;` will always be negative. This
+         * small wrapper makes sure compilers figure that out. Use it as
+         * replacement for `errno` read access. Yes, it generates worse code,
+         * but only marginally and only affects slow-paths.
+         */
+        return abs(errno) ? : EIO;
+}
+
+static inline void n_acd_event_node_freep(NAcdEventNode **node) {
+        if (*node)
+                n_acd_event_node_free(*node);
+}
+
+static inline void n_acd_closep(int *fdp) {
+        if (*fdp >= 0)
+                close(*fdp);
+}
diff --git a/shared/n-acd/src/n-acd-probe.c b/shared/n-acd/src/n-acd-probe.c
new file mode 100644
index 00000000..8c233b56
--- /dev/null
+++ b/shared/n-acd/src/n-acd-probe.c
@@ -0,0 +1,636 @@
+/*
+ * IPv4 Address Conflict Detection
+ */
+
+#include <assert.h>
+#include <c-rbtree.h>
+#include <endian.h>
+#include <errno.h>
+#include <inttypes.h>
+#include <limits.h>
+#include <netinet/if_ether.h>
+#include <netinet/in.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/types.h>
+#include <unistd.h>
+#include "n-acd.h"
+#include "n-acd-private.h"
+
+/*
+ * These parameters and timing intervals specified in RFC-5227. The original
+ * values are:
+ *
+ *     PROBE_NUM                                3
+ *     PROBE_WAIT                               1s
+ *     PROBE_MIN                                1s
+ *     PROBE_MAX                                3s
+ *     ANNOUNCE_NUM                             3
+ *     ANNOUNCE_WAIT                            2s
+ *     ANNOUNCE_INTERVAL                        2s
+ *     MAX_CONFLICTS                            10
+ *     RATE_LIMIT_INTERVAL                      60s
+ *     DEFEND_INTERVAL                          10s
+ *
+ * If we assume a best-case and worst-case scenario for non-conflicted runs, we
+ * end up with a runtime between 4s and 9s to finish the probe. Then it still
+ * takes a fixed 4s to finish the announcements.
+ *
+ * RFC 5227 section 1.1:
+ *     [...] (Note that the values listed here are fixed constants; they are
+ *     not intended to be modifiable by implementers, operators, or end users.
+ *     These constants are given symbolic names here to facilitate the writing
+ *     of future standards that may want to reference this document with
+ *     different values for these named constants; however, at the present time
+ *     no such future standards exist.) [...]
+ *
+ * Unfortunately, no-one ever stepped up to write a "future standard" to revise
+ * the timings. A 9s timeout for successful link setups is not acceptable today.
+ * Hence, we will just go forward and ignore the proposed values. On both
+ * wired and wireless local links round-trip latencies of below 3ms are common.
+ * We require the caller to set a timeout multiplier, where 1 corresponds to a
+ * total probe time between 0.5 ms and 1.0 ms. On modern networks a multiplier
+ * of about 100 should be a reasonable default. To comply with the RFC select a
+ * multiplier of 9000.
+ */
+#define N_ACD_RFC_PROBE_NUM                     (3)
+#define N_ACD_RFC_PROBE_WAIT_NSEC               (UINT64_C(111111)) /* 1/9 ms */
+#define N_ACD_RFC_PROBE_MIN_NSEC                (UINT64_C(111111)) /* 1/9 ms */
+#define N_ACD_RFC_PROBE_MAX_NSEC                (UINT64_C(333333)) /* 3/9 ms */
+#define N_ACD_RFC_ANNOUNCE_NUM                  (3)
+#define N_ACD_RFC_ANNOUNCE_WAIT_NSEC            (UINT64_C(222222)) /* 2/9 ms */
+#define N_ACD_RFC_ANNOUNCE_INTERVAL_NSEC        (UINT64_C(222222)) /* 2/9 ms */
+#define N_ACD_RFC_MAX_CONFLICTS                 (10)
+#define N_ACD_RFC_RATE_LIMIT_INTERVAL_NSEC      (UINT64_C(60000000000)) /* 60s */
+#define N_ACD_RFC_DEFEND_INTERVAL_NSEC          (UINT64_C(10000000000)) /* 10s */
+
+/**
+ * XXX
+ */
+_public_ int n_acd_probe_config_new(NAcdProbeConfig **configp) {
+        _cleanup_(n_acd_probe_config_freep) NAcdProbeConfig *config = NULL;
+
+        config = malloc(sizeof(*config));
+        if (!config)
+                return -ENOMEM;
+
+        *config = (NAcdProbeConfig)N_ACD_PROBE_CONFIG_NULL(*config);
+
+        *configp = config;
+        config = NULL;
+        return 0;
+}
+
+/**
+ * XXX
+ */
+_public_ NAcdProbeConfig *n_acd_probe_config_free(NAcdProbeConfig *config) {
+        if (!config)
+                return NULL;
+
+        free(config);
+
+        return NULL;
+}
+
+/**
+ * XXX
+ */
+_public_ void n_acd_probe_config_set_ip(NAcdProbeConfig *config, struct in_addr ip) {
+        config->ip = ip;
+}
+
+/**
+ * XXX
+ */
+_public_ void n_acd_probe_config_set_timeout(NAcdProbeConfig *config, uint64_t msecs) {
+        config->timeout_msecs = msecs;
+}
+
+static void n_acd_probe_schedule(NAcdProbe *probe, uint64_t n_timeout, unsigned int n_jitter) {
+        uint64_t n_time;
+
+        timer_now(&probe->acd->timer, &n_time);
+        n_time += n_timeout;
+
+        /*
+         * ACD specifies jitter values to reduce packet storms on the local
+         * link. This call accepts the maximum relative jitter value in
+         * nanoseconds as @n_jitter. We then use rand_r(3p) to get a
+         * pseudo-random jitter on top of the real timeout given as @n_timeout.
+         */
+        if (n_jitter) {
+                uint64_t random;
+
+                random = ((uint64_t)rand_r(&probe->acd->seed) << 32) | (uint64_t)rand_r(&probe->acd->seed);
+                n_time += random % n_jitter;
+        }
+
+        timeout_schedule(&probe->timeout, &probe->acd->timer, n_time);
+}
+
+static void n_acd_probe_unschedule(NAcdProbe *probe) {
+        timeout_unschedule(&probe->timeout);
+}
+
+static bool n_acd_probe_is_unique(NAcdProbe *probe) {
+        NAcdProbe *sibling;
+
+        if (!c_rbnode_is_linked(&probe->ip_node))
+                return false;
+
+        sibling = c_rbnode_entry(c_rbnode_next(&probe->ip_node), NAcdProbe, ip_node);
+        if (sibling && sibling->ip.s_addr == probe->ip.s_addr)
+                return false;
+
+        sibling = c_rbnode_entry(c_rbnode_prev(&probe->ip_node), NAcdProbe, ip_node);
+        if (sibling && sibling->ip.s_addr == probe->ip.s_addr)
+                return false;
+
+        return true;
+}
+
+static int n_acd_probe_link(NAcdProbe *probe) {
+        int r;
+
+        /*
+         * Make sure the kernel bpf map has space for at least one more
+         * entry.
+         */
+        r = n_acd_ensure_bpf_map_space(probe->acd);
+        if (r)
+                return r;
+
+        /*
+         * Link entry into context, indexed by its IP. Note that we allow
+         * duplicates just fine. It is up to you to decide whether to avoid
+         * duplicates, if you don't want them. Duplicates on the same context
+         * do not conflict with each other, though.
+         */
+        {
+                CRBNode **slot, *parent;
+                NAcdProbe *other;
+
+                slot = &probe->acd->ip_tree.root;
+                parent = NULL;
+                while (*slot) {
+                        other = c_rbnode_entry(*slot, NAcdProbe, ip_node);
+                        parent = *slot;
+                        if (probe->ip.s_addr < other->ip.s_addr)
+                                slot = &(*slot)->left;
+                        else
+                                slot = &(*slot)->right;
+                }
+
+                c_rbtree_add(&probe->acd->ip_tree, parent, slot, &probe->ip_node);
+        }
+
+        /*
+         * Add the ip address to the map, if it is not already there.
+         */
+        if (n_acd_probe_is_unique(probe)) {
+                r = n_acd_bpf_map_add(probe->acd->fd_bpf_map, &probe->ip);
+                if (r) {
+                        /*
+                         * Make sure the IP address is linked in userspace iff
+                         * it is linked in the kernel.
+                         */
+                        c_rbnode_unlink(&probe->ip_node);
+                        return r;
+                }
+                ++probe->acd->n_bpf_map;
+        }
+
+        return 0;
+}
+
+static void n_acd_probe_unlink(NAcdProbe *probe) {
+        int r;
+
+        /*
+         * If this is the only probe for a given IP, remove the IP from the
+         * kernel BPF map.
+         */
+        if (n_acd_probe_is_unique(probe)) {
+                r = n_acd_bpf_map_remove(probe->acd->fd_bpf_map, &probe->ip);
+                assert(r >= 0);
+                --probe->acd->n_bpf_map;
+        }
+        c_rbnode_unlink(&probe->ip_node);
+}
+
+int n_acd_probe_new(NAcdProbe **probep, NAcd *acd, NAcdProbeConfig *config) {
+        _cleanup_(n_acd_probe_freep) NAcdProbe *probe = NULL;
+        int r;
+
+        if (!config->ip.s_addr)
+                return N_ACD_E_INVALID_ARGUMENT;
+
+        probe = malloc(sizeof(*probe));
+        if (!probe)
+                return -ENOMEM;
+
+        *probe = (NAcdProbe)N_ACD_PROBE_NULL(*probe);
+        probe->acd = n_acd_ref(acd);
+        probe->ip = config->ip;
+
+        /*
+         * We use the provided timeout-length as multiplier for all our
+         * timeouts. The provided timeout defines the maximum length of an
+         * entire probe-interval until the first announcement. Given the
+         * spec-provided parameters, this ends up as:
+         *
+         *     PROBE_WAIT + PROBE_MAX + PROBE_MAX + ANNOUNCE_WAIT
+         *   =         1s +        3s +        3s +            2s
+         *   = 9s
+         *
+         * Hence, the default value for this timeout is 9000ms, which just
+         * ends up matching the spec-provided values.
+         *
+         * What we now semantically do is divide this timeout by 1ns/1000000.
+         * This first turns it into nanoseconds, then strips the unit by
+         * turning it into a multiplier. However, rather than performing the
+         * division here, we multiplier all our timeouts by 1000000 statically
+         * at compile time. Therefore, we can use the user-provided timeout as
+         * unmodified multiplier. No conversion necessary.
+         */
+        probe->timeout_multiplier = config->timeout_msecs;
+
+        r = n_acd_probe_link(probe);
+        if (r)
+                return r;
+
+        /*
+         * Now that everything is set up, we have to send the first probe. This
+         * is done after ~PROBE_WAIT seconds, hence we schedule our timer.
+         * In case no timeout-multiplier is set, we pretend we already sent all
+         * probes successfully and schedule the timer so we proceed with the
+         * announcements. We must schedule a fake timer there, since we are not
+         * allowed to advance the state machine outside of n_acd_dispatch().
+         */
+        if (probe->timeout_multiplier) {
+                probe->n_iteration = 0;
+                n_acd_probe_schedule(probe,
+                                     0,
+                                     probe->timeout_multiplier * N_ACD_RFC_PROBE_WAIT_NSEC);
+        } else {
+                probe->n_iteration = N_ACD_RFC_PROBE_NUM;
+                n_acd_probe_schedule(probe, 0, 0);
+        }
+
+        *probep = probe;
+        probe = NULL;
+        return 0;
+}
+
+/**
+ * XXX
+ */
+_public_ NAcdProbe *n_acd_probe_free(NAcdProbe *probe) {
+        NAcdEventNode *node, *t_node;
+
+        if (!probe)
+                return NULL;
+
+        c_list_for_each_entry_safe(node, t_node, &probe->event_list, probe_link)
+                n_acd_event_node_free(node);
+
+        n_acd_probe_unschedule(probe);
+        n_acd_probe_unlink(probe);
+        probe->acd = n_acd_unref(probe->acd);
+        free(probe);
+
+        return NULL;
+}
+
+int n_acd_probe_raise(NAcdProbe *probe, NAcdEventNode **nodep, unsigned int event) {
+        _cleanup_(n_acd_event_node_freep) NAcdEventNode *node = NULL;
+        int r;
+
+        r = n_acd_raise(probe->acd, &node, event);
+        if (r)
+                return r;
+
+        switch (event) {
+        case N_ACD_EVENT_READY:
+                node->event.ready.probe = probe;
+                break;
+        case N_ACD_EVENT_USED:
+                node->event.used.probe = probe;
+                break;
+        case N_ACD_EVENT_DEFENDED:
+                node->event.defended.probe = probe;
+                break;
+        case N_ACD_EVENT_CONFLICT:
+                node->event.conflict.probe = probe;
+                break;
+        default:
+                assert(0);
+                return -EIO;
+        }
+
+        c_list_link_tail(&probe->event_list, &node->probe_link);
+
+        if (nodep)
+                *nodep = node;
+        node = NULL;
+        return 0;
+}
+
+int n_acd_probe_handle_timeout(NAcdProbe *probe) {
+        int r;
+
+        switch (probe->state) {
+        case N_ACD_PROBE_STATE_PROBING:
+                /*
+                 * We are still PROBING. We send 3 probes with a random timeout
+                 * scheduled between each. If, after a fixed timeout, we did
+                 * not receive any conflict we consider the probing successful.
+                 */
+                if (probe->n_iteration < N_ACD_RFC_PROBE_NUM) {
+                        /*
+                         * We have not sent all 3 probes, yet. A timer fired,
+                         * so we are ready to send the next probe. If this is
+                         * the third probe, schedule a timer for ANNOUNCE_WAIT
+                         * to give other peers a chance to answer. If this is
+                         * not the third probe, wait between PROBE_MIN and
+                         * PROBE_MAX for the next probe.
+                         */
+
+                        r = n_acd_send(probe->acd, &probe->ip, NULL);
+                        if (r) {
+                                if (r != -N_ACD_E_DROPPED)
+                                        return r;
+
+                                /*
+                                 * Packet was dropped, and we know about it. It
+                                 * never reached the network. Reasons are
+                                 * manifold, and n_acd_send() raises events if
+                                 * necessary.
+                                 * From a probe-perspective, we simply pretend
+                                 * we never sent the probe and schedule a
+                                 * timeout for the next probe, effectively
+                                 * doubling a single probe-interval.
+                                 */
+                        } else {
+                                /* Successfully sent, so advance counter. */
+                                ++probe->n_iteration;
+                        }
+
+                        if (probe->n_iteration < N_ACD_RFC_PROBE_NUM)
+                                n_acd_probe_schedule(probe,
+                                                     probe->timeout_multiplier * N_ACD_RFC_PROBE_MIN_NSEC,
+                                                     probe->timeout_multiplier * (N_ACD_RFC_PROBE_MAX_NSEC - N_ACD_RFC_PROBE_MIN_NSEC));
+                        else
+                                n_acd_probe_schedule(probe,
+                                                     probe->timeout_multiplier * N_ACD_RFC_ANNOUNCE_WAIT_NSEC,
+                                                     0);
+                } else {
+                        /*
+                         * All 3 probes succeeded and we waited enough to
+                         * consider this address usable by now. Do not announce
+                         * the address, yet. We must first give the caller a
+                         * chance to configure the address (so they can answer
+                         * ARP requests), before announcing it.
+                         */
+                        r = n_acd_probe_raise(probe, NULL, N_ACD_EVENT_READY);
+                        if (r)
+                                return r;
+
+                        probe->state = N_ACD_PROBE_STATE_CONFIGURING;
+                }
+
+                break;
+
+        case N_ACD_PROBE_STATE_ANNOUNCING:
+                /*
+                 * We are ANNOUNCING, meaning the caller configured the address
+                 * on the interface and is actively using it. We send 3
+                 * announcements out, in a short interval, and then just
+                 * perform passive conflict detection.
+                 * Note that once all 3 announcements are sent, we no longer
+                 * schedule a timer, so this part should not trigger, anymore.
+                 */
+
+                r = n_acd_send(probe->acd, &probe->ip, &probe->ip);
+                if (r) {
+                        if (r != -N_ACD_E_DROPPED)
+                                return r;
+
+                        /*
+                         * See above in STATE_PROBING for details. We know the
+                         * packet was never sent, so we simply try again after
+                         * extending the timer.
+                         */
+                } else {
+                        /* Successfully sent, so advance counter. */
+                        ++probe->n_iteration;
+                }
+
+                if (probe->n_iteration < N_ACD_RFC_ANNOUNCE_NUM) {
+                        /*
+                         * Announcements are always scheduled according to the
+                         * time-intervals specified in the spec. We always use
+                         * the RFC5227-mandated multiplier.
+                         * If you reconsider this, note that timeout_multiplier
+                         * might be 0 here.
+                         */
+                        n_acd_probe_schedule(probe,
+                                             N_ACD_TIMEOUT_RFC5227 * N_ACD_RFC_ANNOUNCE_INTERVAL_NSEC,
+                                             0);
+                }
+
+                break;
+
+        case N_ACD_PROBE_STATE_CONFIGURING:
+        case N_ACD_PROBE_STATE_FAILED:
+        default:
+                /*
+                 * There are no timeouts in these states. If we trigger one,
+                 * something is fishy.
+                 */
+                assert(0);
+                return -EIO;
+        }
+
+        return 0;
+}
+
+int n_acd_probe_handle_packet(NAcdProbe *probe, struct ether_arp *packet, bool hard_conflict) {
+        NAcdEventNode *node;
+        uint64_t now;
+        int r;
+
+        timer_now(&probe->acd->timer, &now);
+
+        switch (probe->state) {
+        case N_ACD_PROBE_STATE_PROBING:
+                /*
+                 * Regardless whether this is a hard or soft conflict, we must
+                 * treat this as a probe failure. That is, notify the caller of
+                 * the conflict and wait for further instructions. We do not
+                 * react to this, until the caller tells us what to do, but we
+                 * do stop sending further probes.
+                 */
+                r = n_acd_probe_raise(probe, &node, N_ACD_EVENT_USED);
+                if (r)
+                        return r;
+
+                node->event.used.sender = node->sender;
+                node->event.used.n_sender = ETH_ALEN;
+                memcpy(node->sender, packet->arp_sha, ETH_ALEN);
+
+                n_acd_probe_unschedule(probe);
+                n_acd_probe_unlink(probe);
+                probe->state = N_ACD_PROBE_STATE_FAILED;
+
+                break;
+
+        case N_ACD_PROBE_STATE_CONFIGURING:
+                /*
+                 * We are waiting for the caller to configure the interface and
+                 * start ANNOUNCING. In this state, we cannot defend the
+                 * address as that would indicate that it is ready to be used,
+                 * and we cannot signal CONFLICT or USED as the caller may
+                 * already have started to use the address (and may have
+                 * configured the engine to always defend it, which means they
+                 * should be able to rely on never losing it after READY).
+                 * Simply drop the event, and rely on the anticipated ANNOUNCE
+                 * to trigger it again.
+                 */
+
+                break;
+
+        case N_ACD_PROBE_STATE_ANNOUNCING: {
+                /*
+                 * We were already instructed to announce the address, which
+                 * means the address is configured and in use. Hence, the
+                 * caller is responsible to serve regular ARP queries. Meaning,
+                 * we can ignore any soft conflicts (other peers doing ACD).
+                 *
+                 * But if we see a hard-conflict, we either defend the address
+                 * according to the caller's instructions, or we report the
+                 * conflict and bail out.
+                 */
+                bool conflict = false, rate_limited = false;
+
+                if (!hard_conflict)
+                        break;
+
+                rate_limited = now < probe->last_defend + N_ACD_RFC_DEFEND_INTERVAL_NSEC;
+
+                switch (probe->defend) {
+                case N_ACD_DEFEND_NEVER:
+                        conflict = true;
+                        break;
+                case N_ACD_DEFEND_ONCE:
+                        if (rate_limited) {
+                                conflict = true;
+                                break;
+                        }
+
+                        /* fallthrough */
+                case N_ACD_DEFEND_ALWAYS:
+                        if (!rate_limited) {
+                                r = n_acd_send(probe->acd, &probe->ip, &probe->ip);
+                                if (r) {
+                                        if (r != -N_ACD_E_DROPPED)
+                                                return r;
+
+                                        if (probe->defend == N_ACD_DEFEND_ONCE) {
+                                                conflict = true;
+                                                break;
+                                        }
+                                }
+
+                                if (r != -N_ACD_E_DROPPED)
+                                        probe->last_defend = now;
+                        }
+
+                        r = n_acd_probe_raise(probe, &node, N_ACD_EVENT_DEFENDED);
+                        if (r)
+                                return r;
+
+                        node->event.defended.sender = node->sender;
+                        node->event.defended.n_sender = ETH_ALEN;
+                        memcpy(node->sender, packet->arp_sha, ETH_ALEN);
+
+                        break;
+                }
+
+                if (conflict) {
+                        r = n_acd_probe_raise(probe, &node, N_ACD_EVENT_CONFLICT);
+                        if (r)
+                                return r;
+
+                        node->event.conflict.sender = node->sender;
+                        node->event.conflict.n_sender = ETH_ALEN;
+                        memcpy(node->sender, packet->arp_sha, ETH_ALEN);
+
+                        n_acd_probe_unschedule(probe);
+                        n_acd_probe_unlink(probe);
+                        probe->state = N_ACD_PROBE_STATE_FAILED;
+                }
+
+                break;
+        }
+
+        case N_ACD_PROBE_STATE_FAILED:
+        default:
+                /*
+                 * We are not listening for packets in these states. If we receive one,
+                 * something is fishy.
+                 */
+                assert(0);
+                return -EIO;
+        }
+
+        return 0;
+}
+
+/**
+ * n_acd_probe_set_userdata - XXX
+ */
+_public_ void n_acd_probe_set_userdata(NAcdProbe *probe, void *userdata) {
+        probe->userdata = userdata;
+}
+
+/**
+ * n_acd_probe_get_userdata - XXX
+ */
+_public_ void n_acd_probe_get_userdata(NAcdProbe *probe, void **userdatap) {
+        *userdatap = probe->userdata;
+}
+
+/**
+ * n_acd_probe_announce() - announce the configured IP address
+ * @probe:      probe object
+ * @defend:     defence policy
+ *
+ * Announce the IP address on the local link, and start defending it according
+ * to the given policy, which mut be one of N_ACD_DEFEND_ONCE,
+ * N_ACD_DEFEND_NEVER, or N_ACD_DEFEND_ALWAYS.
+ *
+ * This must be called in response to an N_ACD_EVENT_READY event, and only
+ * after the given address has been configured on the given network interface.
+ *
+ * Return: 0 on success, N_ACD_E_INVALID_ARGUMENT in case the defence policy
+ *         is invalid, negative error code on failure.
+ */
+_public_ int n_acd_probe_announce(NAcdProbe *probe, unsigned int defend) {
+        if (defend >= _N_ACD_DEFEND_N)
+                return N_ACD_E_INVALID_ARGUMENT;
+
+        probe->state = N_ACD_PROBE_STATE_ANNOUNCING;
+        probe->defend = defend;
+        probe->n_iteration = 0;
+
+        /*
+         * We must schedule a fake-timeout, since we are not allowed to
+         * advance the state-machine outside of n_acd_dispatch().
+         */
+        n_acd_probe_schedule(probe, 0, 0);
+
+        return 0;
+}
diff --git a/shared/n-acd/src/n-acd.c b/shared/n-acd/src/n-acd.c
index 9164f958..def56a21 100644
--- a/shared/n-acd/src/n-acd.c
+++ b/shared/n-acd/src/n-acd.c
@@ -1,188 +1,38 @@
 /*
  * IPv4 Address Conflict Detection
- *
- * This implements the main n-acd API. It is built around an epoll-fd to
- * encapsulate a timerfd+socket. The n-acd context has quite straightforward
- * lifetime rules. The parameters must be set when the engine is started, and
- * they can only be changed by stopping and restartding the engine. The engine
- * is started on demand and stopped when no longer needed.
- * During the entire lifetime the context can be dispatched. That is, the
- * dispatcher does not have to be aware of the context state. After each call
- * to dispatch(), the caller must pop all pending events until -EAGAIN is
- * returned.
- *
- * If a conflict is detected, the ACD engine reports to the caller and stops
- * the engine. The caller can now modify parameters and restart the engine, if
- * required.
  */
 
 #include <assert.h>
 #include <c-list.h>
+#include <c-rbtree.h>
 #include <c-siphash.h>
 #include <endian.h>
 #include <errno.h>
+#include <inttypes.h>
 #include <limits.h>
-#include <linux/filter.h>
-#include <linux/if_ether.h>
 #include <linux/if_packet.h>
-#include <net/ethernet.h>
 #include <netinet/if_ether.h>
 #include <netinet/in.h>
-#include <stddef.h>
-#include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <sys/auxv.h>
 #include <sys/epoll.h>
 #include <sys/socket.h>
-#include <sys/timerfd.h>
 #include <sys/types.h>
 #include <unistd.h>
 #include "n-acd.h"
-
-#define _public_ __attribute__((__visibility__("default")))
-
-/*
- * These parameters and timing intervals specified in RFC-5227. The original
- * values are:
- *
- *     PROBE_NUM                                3
- *     PROBE_WAIT                               1s
- *     PROBE_MIN                                1s
- *     PROBE_MAX                                3s
- *     ANNOUNCE_NUM                             3
- *     ANNOUNCE_WAIT                            2s
- *     ANNOUNCE_INTERVAL                        2s
- *     MAX_CONFLICTS                            10
- *     RATE_LIMIT_INTERVAL                      60s
- *     DEFEND_INTERVAL                          10s
- *
- * If we assume a best-case and worst-case scenario for non-conflicted runs, we
- * end up with a runtime between 4s and 9s to finish the probe. Then it still
- * takes a fixed 4s to finish the announcements.
- *
- * RFC 5227 section 1.1:
- *     [...] (Note that the values listed here are fixed constants; they are
- *     not intended to be modifiable by implementers, operators, or end users.
- *     These constants are given symbolic names here to facilitate the writing
- *     of future standards that may want to reference this document with
- *     different values for these named constants; however, at the present time
- *     no such future standards exist.) [...]
- *
- * Unfortunately, no-one ever stepped up to write a "future standard" to revise
- * the timings. A 9s timeout for successful link setups is not acceptable today.
- * Hence, we will just go forward and ignore the proposed values. On both
- * wired and wireless local links round-trip latencies of below 3ms are common,
- * while latencies above 10ms are rarely seen. We require the caller to set a
- * timeout multiplier, where 1 corresponds to a total probe time of 0.5 ms and
- * 1.0 ms. On modern networks a multiplier of about 100 should be a reasonable
- * default. To comply with the RFC select a multiplier of 9000.
- */
-#define N_ACD_RFC_PROBE_NUM                     (3)
-#define N_ACD_RFC_PROBE_WAIT_USEC               (UINT64_C(111)) /* 111us */
-#define N_ACD_RFC_PROBE_MIN_USEC                (UINT64_C(111)) /* 111us */
-#define N_ACD_RFC_PROBE_MAX_USEC                (UINT64_C(333)) /* 333us */
-#define N_ACD_RFC_ANNOUNCE_NUM                  (3)
-#define N_ACD_RFC_ANNOUNCE_WAIT_USEC            (UINT64_C(222)) /* 222us */
-#define N_ACD_RFC_ANNOUNCE_INTERVAL_USEC        (UINT64_C(222)) /* 222us */
-#define N_ACD_RFC_MAX_CONFLICTS                 (10)
-#define N_ACD_RFC_RATE_LIMIT_INTERVAL_USEC      (UINT64_C(60000000)) /* 60s */
-#define N_ACD_RFC_DEFEND_INTERVAL_USEC          (UINT64_C(10000000)) /* 10s */
-
-/*
- * Fake ENETDOWN error-code. We use this as replacement for known EFOOBAR error
- * codes. It is explicitly chosen to be outside the known error-code range.
- * Whenever we are deep down in a call-stack and notice a ENETDOWN error, we
- * return this instead. It is caught by the top-level dispatcher and then
- * properly handled.
- * This avoids gracefully handling ENETDOWN in call-stacks, but then continuing
- * with some work in the callers without noticing the soft failure.
- */
-#define N_ACD_E_DOWN (INT_MAX)
-
-#define TIME_INFINITY ((uint64_t) -1)
+#include "n-acd-private.h"
 
 enum {
         N_ACD_EPOLL_TIMER,
         N_ACD_EPOLL_SOCKET,
 };
 
-enum {
-        N_ACD_STATE_INIT,
-        N_ACD_STATE_PROBING,
-        N_ACD_STATE_CONFIGURING,
-        N_ACD_STATE_ANNOUNCING,
-};
-
-typedef struct NAcdEventNode {
-        NAcdEvent event;
-        uint8_t sender[ETH_ALEN];
-        CList link;
-} NAcdEventNode;
-
-struct NAcd {
-        /* context */
-        unsigned int seed;
-        int fd_epoll;
-        int fd_timer;
-
-        /* configuration */
-        NAcdConfig config;
-        uint8_t mac[ETH_ALEN];
-        uint64_t timeout_multiplier;
-
-        /* runtime */
-        int fd_socket;
-        unsigned int state;
-        unsigned int n_iteration;
-        unsigned int n_conflicts;
-        unsigned int defend;
-        uint64_t last_defend;
-        uint64_t last_conflict;
-
-        /* pending events */
-        CList events;
-        NAcdEventNode *current;
-};
-
-static int n_acd_errno(void) {
-        /*
-         * Compilers continuously warn about uninitialized variables since they
-         * cannot deduce that `return -errno;` will always be negative. This
-         * small wrapper makes sure compilers figure that out. Use it as
-         * replacement for `errno` read access. Yes, it generates worse code,
-         * but only marginally and only affects slow-paths.
-         */
-        return abs(errno) ? : EIO;
-}
-
-static int n_acd_event_node_new(NAcdEventNode **nodep, unsigned int event) {
-        NAcdEventNode *node;
-
-        node = calloc(1, sizeof(*node));
-        if (!node)
-                return -ENOMEM;
-
-        node->event.event = event;
-        node->link = (CList)C_LIST_INIT(node->link);
-
-        *nodep = node;
-
-        return 0;
-}
-
-static NAcdEventNode *n_acd_event_node_free(NAcdEventNode *node) {
-        if (!node)
-                return NULL;
-
-        c_list_unlink(&node->link);
-        free(node);
-
-        return NULL;
-}
-
 static int n_acd_get_random(unsigned int *random) {
-        uint8_t hash_seed[] = { 0x3a, 0x0c, 0xa6, 0xdd, 0x44, 0xef, 0x5f, 0x7a, 0x5e, 0xd7, 0x25, 0x37, 0xbf, 0x4e, 0x80, 0xa1 };
+        uint8_t hash_seed[] = {
+                0x3a, 0x0c, 0xa6, 0xdd, 0x44, 0xef, 0x5f, 0x7a,
+                0x5e, 0xd7, 0x25, 0x37, 0xbf, 0x4e, 0x80, 0xa1,
+        };
         CSipHash hash = C_SIPHASH_NULL;
         struct timespec ts;
         const uint8_t *p;
@@ -203,7 +53,7 @@ static int n_acd_get_random(unsigned int *random) {
         if (p)
                 c_siphash_append(&hash, p, 16);
 
-        r = clock_gettime(CLOCK_BOOTTIME, &ts);
+        r = clock_gettime(CLOCK_MONOTONIC, &ts);
         if (r < 0)
                 return -n_acd_errno();
 
@@ -214,114 +64,260 @@ static int n_acd_get_random(unsigned int *random) {
         return 0;
 }
 
-static void n_acd_reset(NAcd *acd) {
-        acd->state = N_ACD_STATE_INIT;
-        acd->defend = N_ACD_DEFEND_NEVER;
-        acd->n_iteration = 0;
-        acd->last_defend = 0;
-        timerfd_settime(acd->fd_timer, 0, &(struct itimerspec){}, NULL);
+static int n_acd_socket_new(int *fdp, int fd_bpf_prog, NAcdConfig *config) {
+        const struct sockaddr_ll address = {
+                .sll_family = AF_PACKET,
+                .sll_protocol = htobe16(ETH_P_ARP),
+                .sll_ifindex = config->ifindex,
+                .sll_halen = ETH_ALEN,
+                .sll_addr = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff },
+        };
+        int r, s = -1;
 
-        if (acd->fd_socket >= 0) {
-                assert(acd->fd_epoll >= 0);
-                epoll_ctl(acd->fd_epoll, EPOLL_CTL_DEL, acd->fd_socket, NULL);
-                close(acd->fd_socket);
-                acd->fd_socket = -1;
+        s = socket(PF_PACKET, SOCK_DGRAM | SOCK_CLOEXEC | SOCK_NONBLOCK, 0);
+        if (s < 0) {
+                r = -n_acd_errno();
+                goto error;
+        }
+
+        if (fd_bpf_prog >= 0) {
+                r = setsockopt(s, SOL_SOCKET, SO_ATTACH_BPF, &fd_bpf_prog, sizeof(fd_bpf_prog));
+                if (r < 0)
+                        return -n_acd_errno();
         }
+
+        r = bind(s, (struct sockaddr *)&address, sizeof(address));
+        if (r < 0) {
+                r = -n_acd_errno();
+                goto error;
+        }
+
+        *fdp = s;
+        s = -1;
+        return 0;
+
+error:
+        if (s >= 0)
+                close(s);
+        return r;
+}
+
+/**
+ * XXX
+ */
+_public_ int n_acd_config_new(NAcdConfig **configp) {
+        _cleanup_(n_acd_config_freep) NAcdConfig *config = NULL;
+
+        config = malloc(sizeof(*config));
+        if (!config)
+                return -ENOMEM;
+
+        *config = (NAcdConfig)N_ACD_CONFIG_NULL(*config);
+
+        *configp = config;
+        config = NULL;
+        return 0;
+}
+
+/**
+ * XXX
+ */
+_public_ NAcdConfig *n_acd_config_free(NAcdConfig *config) {
+        if (!config)
+                return NULL;
+
+        free(config);
+
+        return NULL;
+}
+
+/**
+ * XXX
+ */
+_public_ void n_acd_config_set_ifindex(NAcdConfig *config, int ifindex) {
+        config->ifindex = ifindex;
+}
+
+/**
+ * XXX
+ */
+_public_ void n_acd_config_set_transport(NAcdConfig *config, unsigned int transport) {
+        config->transport = transport;
+}
+
+/**
+ * XXX
+ */
+_public_ void n_acd_config_set_mac(NAcdConfig *config, const uint8_t *mac, size_t n_mac) {
+        config->n_mac = n_mac;
+        memcpy(config->mac, mac, n_mac > ETH_ALEN ? ETH_ALEN : n_mac);
+}
+
+int n_acd_event_node_new(NAcdEventNode **nodep) {
+        NAcdEventNode *node;
+
+        node = malloc(sizeof(*node));
+        if (!node)
+                return -ENOMEM;
+
+        *node = (NAcdEventNode)N_ACD_EVENT_NODE_NULL(*node);
+
+        *nodep = node;
+        return 0;
+}
+
+NAcdEventNode *n_acd_event_node_free(NAcdEventNode *node) {
+        if (!node)
+                return NULL;
+
+        c_list_unlink(&node->probe_link);
+        c_list_unlink(&node->acd_link);
+        free(node);
+
+        return NULL;
+}
+
+int n_acd_ensure_bpf_map_space(NAcd *acd) {
+        NAcdProbe *probe;
+        _cleanup_(n_acd_closep) int fd_map = -1, fd_prog = -1;
+        size_t  max_map;
+        int r;
+
+        if (acd->n_bpf_map < acd->max_bpf_map)
+                return 0;
+
+        max_map = 2 * acd->max_bpf_map;
+
+        r = n_acd_bpf_map_create(&fd_map, max_map);
+        if (r)
+                return r;
+
+        c_rbtree_for_each_entry(probe, &acd->ip_tree, ip_node) {
+                r = n_acd_bpf_map_add(fd_map, &probe->ip);
+                if (r)
+                        return r;
+        }
+
+        r = n_acd_bpf_compile(&fd_prog, fd_map, (struct ether_addr*) acd->mac);
+        if (r)
+                return r;
+
+        if (fd_prog >= 0) {
+                r = setsockopt(acd->fd_socket, SOL_SOCKET, SO_ATTACH_BPF, &fd_prog, sizeof(fd_prog));
+                if (r)
+                        return -n_acd_errno();
+        }
+
+        if (acd->fd_bpf_map >= 0)
+                close(acd->fd_bpf_map);
+        acd->fd_bpf_map = fd_map;
+        fd_map = -1;
+        acd->max_bpf_map = max_map;
+        return 0;
 }
 
 /**
  * n_acd_new() - create a new ACD context
  * @acdp:       output argument for context
+ * @config:     configuration parameters
  *
  * Create a new ACD context and return it in @acdp.
  *
  * Return: 0 on success, or a negative error code on failure.
  */
-_public_ int n_acd_new(NAcd **acdp) {
-        NAcd *acd;
+_public_ int n_acd_new(NAcd **acdp, NAcdConfig *config) {
+        _cleanup_(n_acd_unrefp) NAcd *acd = NULL;
+        _cleanup_(n_acd_closep) int fd_bpf_prog = -1;
         int r;
 
-        acd = calloc(1, sizeof(*acd));
+        if (config->ifindex <= 0 ||
+            config->transport != N_ACD_TRANSPORT_ETHERNET ||
+            config->n_mac != ETH_ALEN ||
+            !memcmp(config->mac, (uint8_t[ETH_ALEN]){ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff }, ETH_ALEN))
+                return N_ACD_E_INVALID_ARGUMENT;
+
+        acd = malloc(sizeof(*acd));
         if (!acd)
                 return -ENOMEM;
 
-        acd->fd_epoll = -1;
-        acd->fd_timer = -1;
-        acd->fd_socket = -1;
-        acd->state = N_ACD_STATE_INIT;
-        acd->defend = N_ACD_DEFEND_NEVER;
-        acd->events = (CList)C_LIST_INIT(acd->events);
-        acd->last_conflict = TIME_INFINITY;
+        *acd = (NAcd)N_ACD_NULL(*acd);
+        acd->ifindex = config->ifindex;
+        memcpy(acd->mac, config->mac, ETH_ALEN);
 
         r = n_acd_get_random(&acd->seed);
-        if (r < 0)
+        if (r)
                 return r;
 
         acd->fd_epoll = epoll_create1(EPOLL_CLOEXEC);
-        if (acd->fd_epoll < 0) {
-                r = -n_acd_errno();
-                goto error;
-        }
+        if (acd->fd_epoll < 0)
+                return -n_acd_errno();
 
-        acd->fd_timer = timerfd_create(CLOCK_BOOTTIME, TFD_CLOEXEC | TFD_NONBLOCK);
-        if (acd->fd_timer < 0 && errno == EINVAL) {
-                /*
-		 * Fall back to CLOCK_MONOTONIC when CLOCK_BOOTTIME is
-		 * not available (kernel < 3.15).
-                 */
-                acd->fd_timer = timerfd_create(CLOCK_MONOTONIC, TFD_CLOEXEC | TFD_NONBLOCK);
-        }
-        if (acd->fd_timer < 0) {
-                r = -n_acd_errno();
-                goto error;
-        }
+        r = timer_init(&acd->timer);
+        if (r < 0)
+                return r;
 
-        r = epoll_ctl(acd->fd_epoll, EPOLL_CTL_ADD, acd->fd_timer,
+        acd->max_bpf_map = 8;
+
+        r = n_acd_bpf_map_create(&acd->fd_bpf_map, acd->max_bpf_map);
+        if (r)
+                return r;
+
+        r = n_acd_bpf_compile(&fd_bpf_prog, acd->fd_bpf_map, (struct ether_addr*) acd->mac);
+        if (r)
+                return r;
+
+        r = n_acd_socket_new(&acd->fd_socket, fd_bpf_prog, config);
+        if (r)
+                return r;
+
+        r = epoll_ctl(acd->fd_epoll, EPOLL_CTL_ADD, acd->timer.fd,
                       &(struct epoll_event){
                               .events = EPOLLIN,
                               .data.u32 = N_ACD_EPOLL_TIMER,
                       });
-        if (r < 0) {
-                r = -n_acd_errno();
-                goto error;
-        }
+        if (r < 0)
+                return -n_acd_errno();
+
+        r = epoll_ctl(acd->fd_epoll, EPOLL_CTL_ADD, acd->fd_socket,
+                      &(struct epoll_event){
+                              .events = EPOLLIN,
+                              .data.u32 = N_ACD_EPOLL_SOCKET,
+                      });
+        if (r < 0)
+                return -n_acd_errno();
 
         *acdp = acd;
+        acd = NULL;
         return 0;
-
-error:
-        n_acd_free(acd);
-        return r;
 }
 
-/**
- * n_acd_free() - free an ACD context
- *
- * Frees all resources held by the context. This may be called at any time,
- * but doing so invalidates all data owned by the context.
- *
- * Return: NULL.
- */
-_public_ void n_acd_free(NAcd *acd) {
-        NAcdEventNode *node;
+static void n_acd_free(NAcd *acd) {
+        NAcdEventNode *node, *t_node;
 
         if (!acd)
                 return;
 
-        n_acd_reset(acd);
+        c_list_for_each_entry_safe(node, t_node, &acd->event_list, acd_link)
+                n_acd_event_node_free(node);
 
-        acd->current = n_acd_event_node_free(acd->current);
+        assert(c_rbtree_is_empty(&acd->ip_tree));
 
-        while ((node = c_list_first_entry(&acd->events, NAcdEventNode, link)))
-                n_acd_event_node_free(node);
+        if (acd->fd_socket >= 0) {
+                assert(acd->fd_epoll >= 0);
+                epoll_ctl(acd->fd_epoll, EPOLL_CTL_DEL, acd->fd_socket, NULL);
+                close(acd->fd_socket);
+                acd->fd_socket = -1;
+        }
 
-        assert(acd->fd_socket < 0);
+        if (acd->fd_bpf_map >= 0) {
+                close(acd->fd_bpf_map);
+                acd->fd_bpf_map = -1;
+        }
 
-        if (acd->fd_timer >= 0) {
+        if (acd->timer.fd >= 0) {
                 assert(acd->fd_epoll >= 0);
-                epoll_ctl(acd->fd_epoll, EPOLL_CTL_DEL, acd->fd_timer, NULL);
-                close(acd->fd_timer);
-                acd->fd_timer = -1;
+                epoll_ctl(acd->fd_epoll, EPOLL_CTL_DEL, acd->timer.fd, NULL);
+                timer_deinit(&acd->timer);
         }
 
         if (acd->fd_epoll >= 0) {
@@ -333,270 +329,163 @@ _public_ void n_acd_free(NAcd *acd) {
 }
 
 /**
- * n_acd_get_fd() - get pollable file descriptor
- * @acd:        ACD context
- * @fdp:        output argument for file descriptor
- *
- * Returns a file descriptor in @fdp. This filedescriptor can be polled by
- * the caller to indicate when the ACD context can be dispatched.
+ * XXX
  */
-_public_ void n_acd_get_fd(NAcd *acd, int *fdp) {
-        *fdp = acd->fd_epoll;
+_public_ NAcd *n_acd_ref(NAcd *acd) {
+        if (acd)
+                ++acd->n_refs;
+        return acd;
 }
 
-static int n_acd_push_event(NAcd *acd, unsigned int event, uint16_t *operation, uint8_t (*sender)[6], uint8_t (*target)[4]) {
-        NAcdEventNode *node;
-        int r;
-
-        r = n_acd_event_node_new(&node, event);
-        if (r < 0)
-                return r;
-
-        switch (event) {
-        case N_ACD_EVENT_USED:
-                node->event.used.operation = be16toh(*operation);
-                memcpy(node->sender, sender, sizeof(node->sender));
-                node->event.used.sender = node->sender;
-                node->event.used.n_sender = sizeof(node->sender);
-                memcpy(&node->event.used.target, target, sizeof(node->event.used.target));
-                break;
-        case N_ACD_EVENT_CONFLICT:
-                node->event.conflict.operation = be16toh(*operation);
-                memcpy(node->sender, sender, sizeof(node->sender));
-                node->event.used.sender = node->sender;
-                node->event.used.n_sender = sizeof(node->sender);
-                memcpy(&node->event.conflict.target, target, sizeof(node->event.conflict.target));
-                break;
-        case N_ACD_EVENT_DEFENDED:
-                node->event.defended.operation = be16toh(*operation);
-                memcpy(node->sender, sender, sizeof(node->sender));
-                node->event.used.sender = node->sender;
-                node->event.used.n_sender = sizeof(node->sender);
-                memcpy(&node->event.defended.target, target, sizeof(node->event.defended.target));
-                break;
-        case N_ACD_EVENT_READY:
-        case N_ACD_EVENT_DOWN:
-                break;
-        default:
-                assert(0);
-        }
-
-        c_list_link_tail(&acd->events, &node->link);
-
-        return 0;
-}
-
-static int n_acd_now(uint64_t *nowp) {
-        struct timespec ts;
-        int r;
-
-        r = clock_gettime(CLOCK_BOOTTIME, &ts);
-        if (r < 0)
-                return -n_acd_errno();
-
-        *nowp = ts.tv_sec * UINT64_C(1000000) + ts.tv_nsec / UINT64_C(1000);
-        return 0;
+/**
+ * XXX
+ */
+_public_ NAcd *n_acd_unref(NAcd *acd) {
+        if (acd && !--acd->n_refs)
+                n_acd_free(acd);
+        return NULL;
 }
 
-static int n_acd_schedule(NAcd *acd, uint64_t u_timeout, unsigned int u_jitter) {
-        uint64_t u_next = u_timeout;
+int n_acd_raise(NAcd *acd, NAcdEventNode **nodep, unsigned int event) {
+        NAcdEventNode *node;
         int r;
 
-        /*
-         * ACD specifies jitter values to reduce packet storms on the local
-         * link. This call accepts the maximum relative jitter value in
-         * microseconds as @u_jitter. We then use rand_r(3p) to get a
-         * pseudo-random jitter on top of the real timeout given as @u_timeout.
-         * Note that rand_r() is fine for this. Before you try to improve the
-         * RNG, you better spend some time securing ARP.
-         */
-        if (u_jitter)
-                u_next += rand_r(&acd->seed) % u_jitter;
+        r = n_acd_event_node_new(&node);
+        if (r)
+                return r;
 
-        /*
-         * Setting .it_value to 0 in timerfd_settime() disarms the timer. Avoid
-         * this and always schedule at least 1us. Otherwise, we'd have to
-         * recursively call into the time-out handler, which we really want to
-         * avoid. No reason to optimize performance here.
-         */
-        if (!u_next)
-                u_next = 1;
-
-        r = timerfd_settime(acd->fd_timer, 0,
-                            &(struct itimerspec){ .it_value = {
-                                    .tv_sec = u_next / UINT64_C(1000000),
-                                    .tv_nsec = u_next % UINT64_C(1000000) * UINT64_C(1000),
-                            } }, NULL);
-        if (r < 0)
-                return -n_acd_errno();
+        node->event.event = event;
+        c_list_link_tail(&acd->event_list, &node->acd_link);
 
+        if (nodep)
+                *nodep = node;
         return 0;
 }
 
-static int n_acd_send(NAcd *acd, const struct in_addr *spa) {
+int n_acd_send(NAcd *acd, const struct in_addr *tpa, const struct in_addr *spa) {
         struct sockaddr_ll address = {
                 .sll_family = AF_PACKET,
                 .sll_protocol = htobe16(ETH_P_ARP),
-                .sll_ifindex = acd->config.ifindex,
+                .sll_ifindex = acd->ifindex,
                 .sll_halen = ETH_ALEN,
                 .sll_addr = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff },
         };
         struct ether_arp arp = {
-                .ea_hdr.ar_hrd = htobe16(ARPHRD_ETHER),
-                .ea_hdr.ar_pro = htobe16(ETHERTYPE_IP),
-                .ea_hdr.ar_hln = sizeof(acd->mac),
-                .ea_hdr.ar_pln = sizeof(uint32_t),
-                .ea_hdr.ar_op = htobe16(ARPOP_REQUEST),
+                .ea_hdr = {
+                        .ar_hrd = htobe16(ARPHRD_ETHER),
+                        .ar_pro = htobe16(ETHERTYPE_IP),
+                        .ar_hln = sizeof(acd->mac),
+                        .ar_pln = sizeof(uint32_t),
+                        .ar_op = htobe16(ARPOP_REQUEST),
+                },
         };
         ssize_t l;
+        int r;
 
         memcpy(arp.arp_sha, acd->mac, sizeof(acd->mac));
-        memcpy(arp.arp_tpa, &acd->config.ip.s_addr, sizeof(uint32_t));
+        memcpy(arp.arp_tpa, &tpa->s_addr, sizeof(uint32_t));
 
         if (spa)
                 memcpy(arp.arp_spa, &spa->s_addr, sizeof(spa->s_addr));
 
-        l = sendto(acd->fd_socket, &arp, sizeof(arp), MSG_NOSIGNAL, (struct sockaddr *)&address, sizeof(address));
-        if (l == (ssize_t)sizeof(arp)) {
-                /* Packet was properly sent. */
-                return 0;
-        } else if (l >= 0) {
-                /*
-                 * Ugh. The packet was truncated. This should not happen, but
-                 * lets just pretend the packet was dropped.
-                 */
-                return 0;
-        } else if (errno == EAGAIN || errno == ENOBUFS) {
+        l = sendto(acd->fd_socket,
+                   &arp,
+                   sizeof(arp),
+                   MSG_NOSIGNAL,
+                   (struct sockaddr *)&address,
+                   sizeof(address));
+        if (l < 0) {
+                if (errno == EAGAIN || errno == ENOBUFS) {
+                        /*
+                         * We never maintain outgoing queues. We rely on the
+                         * network device to do that for us. In case the queues
+                         * are full, or the kernel refuses to queue the packet
+                         * for other reasons, we must tell our caller that the
+                         * packet was dropped.
+                         */
+                        return N_ACD_E_DROPPED;
+                } else if (errno == ENETDOWN || errno == ENXIO) {
+                        /*
+                         * These errors happen if the network device went down
+                         * or was actually removed. We always propagate this as
+                         * event, so the user can react accordingly (similarly
+                         * to the recvmmsg(2) handler). In case the user does
+                         * not immediately react, we also tell our caller that
+                         * the packet was dropped, so we don't erroneously
+                         * treat this as success.
+                         */
+
+                        r = n_acd_raise(acd, NULL, N_ACD_EVENT_DOWN);
+                        if (r)
+                                return r;
+
+                        return N_ACD_E_DROPPED;
+                }
+
                 /*
-                 * In case the output buffer is full, the packet is silently
-                 * dropped. This is just as if the physical layer happened to
-                 * drop the packet. We are not on a reliable medium, so no
-                 * reason to pretend we are.
+                 * Random network error. We treat this as fatal and propagate
+                 * the error, so it is noticed and can be investigated.
                  */
-                return 0;
-        } else if (errno == ENETDOWN || errno == ENXIO) {
+                return -n_acd_errno();
+        } else if (l != (ssize_t)sizeof(arp)) {
                 /*
-                 * We get ENETDOWN if the network-device goes down or is
-                 * removed. ENXIO might happen on async send-operations if the
-                 * network-device was unplugged and thus the kernel is no
-                 * longer aware of it.
-                 * In any case, we do not allow proceeding with this socket. We
-                 * stop the engine and notify the user gracefully.
+                 * Ugh, the kernel modified the packet. This is unexpected. We
+                 * consider the packet lost.
                  */
-                return -N_ACD_E_DOWN;
+                return N_ACD_E_DROPPED;
         }
 
-        return -n_acd_errno();
+        return 0;
 }
 
-static void n_acd_remember_conflict(NAcd *acd, uint64_t now) {
-        if (++acd->n_conflicts >= N_ACD_RFC_MAX_CONFLICTS) {
-                acd->n_conflicts = N_ACD_RFC_MAX_CONFLICTS;
-                acd->last_conflict = now;
-        }
+/**
+ * n_acd_get_fd() - get pollable file descriptor
+ * @acd:        ACD context
+ * @fdp:        output argument for file descriptor
+ *
+ * Returns a file descriptor in @fdp. This file descriptor can be polled by
+ * the caller to indicate when the ACD context can be dispatched.
+ */
+_public_ void n_acd_get_fd(NAcd *acd, int *fdp) {
+        *fdp = acd->fd_epoll;
 }
 
 static int n_acd_handle_timeout(NAcd *acd) {
+        NAcdProbe *probe;
+        uint64_t now;
         int r;
 
-        switch (acd->state) {
-        case N_ACD_STATE_PROBING:
-                /*
-                 * We are still PROBING. We send 3 probes with a random timeout
-                 * scheduled between each. If, after a fixed timeout, we did
-                 * not receive any conflict we consider the probing successful.
-                 */
-                if (acd->n_iteration >= N_ACD_RFC_PROBE_NUM) {
-                        /*
-                         * All 3 probes succeeded and we waited enough to
-                         * consider this address usable by now. Do not announce
-                         * the address, yet. We must first give the caller a
-                         * chance to configure the address (so they can answer
-                         * ARP requests), before announcing it. But our
-                         * callbacks are not necessarily synchronous (we want
-                         * to allow IPC there), so just notify the caller and
-                         * wait for further instructions, thus effectively
-                         * increasing the probe-wait.
-                         */
-                        r = n_acd_push_event(acd, N_ACD_EVENT_READY, NULL, NULL, NULL);
-                        if (r)
-                                return r;
-
-                        acd->state = N_ACD_STATE_CONFIGURING;
-                } else {
-                        /*
-                         * We have not sent all 3 probes, yet. A timer fired,
-                         * so we are ready to send the next probe. If this is
-                         * the third probe, schedule a timer for ANNOUNCE_WAIT
-                         * to give other peers a chance to answer. If this is
-                         * not the third probe, wait between PROBE_MIN and
-                         * PROBE_MAX for the next probe.
-                         */
-
-                        r = n_acd_send(acd, NULL);
-                        /*
-                         * During probe we must respect the total timeout and so
-                         * we ignore errors caused by a down interface.
-                         */
-                        if (r < 0 && r != -N_ACD_E_DOWN)
-                                return r;
-
-                        if (++acd->n_iteration >= N_ACD_RFC_PROBE_NUM)
-                                r = n_acd_schedule(acd, acd->timeout_multiplier * N_ACD_RFC_ANNOUNCE_WAIT_USEC, 0);
-                        else
-                                r = n_acd_schedule(acd, acd->timeout_multiplier * N_ACD_RFC_PROBE_MIN_USEC,
-                                                   acd->timeout_multiplier * (N_ACD_RFC_PROBE_MAX_USEC - N_ACD_RFC_PROBE_MIN_USEC));
-                        if (r < 0)
-                                return r;
-                }
-
-                break;
+        /*
+         * Read the current time once, and handle all timouts that triggered
+         * before the current time. Rereading the current time in each loop
+         * might risk creating a live-lock, and the fact that we read the
+         * time after reading the timer guarantees that the timeout which
+         * woke us up is hanlded.
+         *
+         * When there are no more timeouts to handle at the given time, we
+         * rearm the timer to potentially wake us up again in the future.
+         */
+        timer_now(&acd->timer, &now);
 
-        case N_ACD_STATE_ANNOUNCING:
-                /*
-                 * We are ANNOUNCING, meaning the caller configured the address
-                 * on the interface and is actively using it. We send 3
-                 * announcements out, in a short interval, and then just
-                 * perform passive conflict detection.
-                 * Note that once all 3 announcements are sent, we no longer
-                 * schedule a timer, so this part should not trigger, anymore.
-                 */
+        for (;;) {
+                Timeout *timeout;
 
-                r = n_acd_send(acd, &acd->config.ip);
+                r = timer_pop_timeout(&acd->timer, now, &timeout);
                 if (r < 0) {
-                        if (r != -N_ACD_E_DOWN)
-                                return r;
-                        /*
-                         * We want to send all the 3 announcements even if the
-                         * interface goes temporarily down. Therefore, if send()
-                         * fails, don't increment the iteration and try again.
-                         */
-                } else
-                        acd->n_iteration++;
-
-                if (acd->n_iteration < N_ACD_RFC_ANNOUNCE_NUM) {
+                        return r;
+                } else if (!timeout) {
                         /*
-                         * Announcements are always scheduled according to the
-                         * time-intervals specified in the spec. We always use
-                         * the RFC5227-mandated multiplier.
-                         * If you reconsider this, note that timeout_multiplier
-                         * might be 0 here.
+                         * There are no more timeouts pending before @now. Rearm
+                         * the timer to fire again at the next timeout.
                          */
-                        r = n_acd_schedule(acd, N_ACD_TIMEOUT_RFC5227 * N_ACD_RFC_ANNOUNCE_INTERVAL_USEC, 0);
-                        if (r < 0)
-                                return r;
+                        timer_rearm(&acd->timer);
+                        break;
                 }
 
-                break;
-
-        case N_ACD_STATE_INIT:
-        case N_ACD_STATE_CONFIGURING:
-        default:
-                /*
-                 * There are no timeouts in these states. If we trigger one,
-                 * something is fishy. Let the caller deal with this.
-                 */
-                return -EIO;
+                probe = (void *)timeout - offsetof(NAcdProbe, timeout);
+                r = n_acd_probe_handle_timeout(probe);
+                if (r)
+                        return r;
         }
 
         return 0;
@@ -604,136 +493,94 @@ static int n_acd_handle_timeout(NAcd *acd) {
 
 static int n_acd_handle_packet(NAcd *acd, struct ether_arp *packet) {
         bool hard_conflict;
-        uint64_t now;
+        NAcdProbe *probe;
+        uint32_t addr;
+        CRBNode *node;
         int r;
 
         /*
-         * Via BPF we discard any non-conflict packets. There are only 2 types
-         * that can pass: A conflict on the Sender Protocol Address, or a
-         * conflict on the Target Protocol Address.
+         * We are interested in 2 kinds of ARP messages:
+         *
+         *  1) Someone who is *NOT* us sends *ANY* ARP message with our IP
+         *     address as sender. This is never good, because it implies an
+         *     address conflict.
+         *     We call this a hard-conflict.
+         *
+         *  2) Someone who is *NOT* us sends an ARP REQUEST without any sender
+         *     IP, but our IP as target. This implies someone else performs an
+         *     ARP Probe with our address. This also implies a conflict, but
+         *     one that can be resolved by responding to the probe.
+         *     We call this a soft-conflict.
+         *
+         * We are never interested in any other ARP message. The kernel already
+         * deals with everything else, hence, we can silently ignore those.
          *
-         * The former we call a hard-conflict. It implies that the sender uses
-         * the address already. We must always catch this and in some way react
-         * to it. Any kind, REQUEST or REPLY must be caught (though it is
-         * unlikely that we ever catch REPLIES since they tend to be unicasts).
+         * Now, we simply check whether a sender-address is set. This allows us
+         * to distinguish both cases. We then check further conditions, so we
+         * can bail out early if neither is the case.
          *
-         * However, in case the Target Protocol Address matches, we just know
-         * that somebody is looking for the address. Hence, we must also check
-         * that the packet is an ARP-Probe (Sender Protocol Address is 0). If
-         * it is, it means someone else does ACD on our address. We call this a
-         * soft conflict.
+         * Lastly, we perform a lookup in our probe-set to check whether the
+         * address actually matches, so we can let these probes dispatch the
+         * message. Note that we allow duplicate probes, so we need to dispatch
+         * each matching probe, not just one.
          */
-        if (!memcmp(packet->arp_spa, (uint8_t[4]){ }, sizeof(packet->arp_spa)) &&
-            !memcmp(packet->arp_tpa, &acd->config.ip.s_addr, sizeof(packet->arp_tpa)) &&
-            packet->ea_hdr.ar_op == htobe16(ARPOP_REQUEST)) {
-                hard_conflict = false;
-        } else if (!memcmp(packet->arp_spa, &acd->config.ip.s_addr, sizeof(packet->arp_spa))) {
+
+        if (memcmp(packet->arp_spa, (uint8_t[4]){ }, sizeof(packet->arp_spa))) {
+                memcpy(&addr, packet->arp_spa, sizeof(addr));
                 hard_conflict = true;
+        } else if (packet->ea_hdr.ar_op == htobe16(ARPOP_REQUEST)) {
+                memcpy(&addr, packet->arp_tpa, sizeof(addr));
+                hard_conflict = false;
         } else {
                 /*
-                 * Ignore anything that is specific enough to match the BPF
-                 * filter, but is none of the conflicts described above.
+                 * The BPF filter will not let through any other packet.
                  */
-                return 0;
+                return -EIO;
         }
 
-        r = n_acd_now(&now);
-        if (r < 0)
-                return r;
-
-        switch (acd->state) {
-        case N_ACD_STATE_PROBING:
-                /*
-                 * Regardless whether this is a hard or soft conflict, we must
-                 * treat this as a probe failure. That is, notify the caller of
-                 * the conflict and wait for further instructions. We do not
-                 * react to this, until the caller tells us what to do. But we
-                 * immediately stop the engine, since there is no point in
-                 * continuing the probing.
-                 */
-                n_acd_remember_conflict(acd, now);
-                n_acd_reset(acd);
-                r = n_acd_push_event(acd, N_ACD_EVENT_USED, &packet->ea_hdr.ar_op, &packet->arp_sha, &packet->arp_tpa);
-                if (r)
-                        return r;
-
-                break;
-
-        case N_ACD_STATE_CONFIGURING:
-                /*
-                 * We are waiting for the caller to configure the interface and
-                 * start ANNOUNCING. In this state, we cannot defend the address
-                 * as that would indicate that it is ready to be used, and we
-                 * cannot signal CONFLICT or USED as the caller may already have
-                 * started to use the address (and may have configured the engine
-                 * to always defend it, which means they should be able to rely on
-                 * never losing it after READY). Simply drop the event, and rely
-                 * on the anticipated ANNOUNCE to trigger it again.
-                 */
+        /* Find top-most node that matches @addr. */
+        node = acd->ip_tree.root;
+        while (node) {
+                probe = c_rbnode_entry(node, NAcdProbe, ip_node);
+                if (addr < probe->ip.s_addr)
+                        node = node->left;
+                else if (addr > probe->ip.s_addr)
+                        node = node->right;
+                else
+                        break;
+        }
 
-                break;
+        /*
+         * If the address is unknown, we drop the package. This might happen if
+         * the kernel queued the packet and passed the BPF filter, but we
+         * modified the set before dequeuing the message.
+         */
+        if (!node)
+                return 0;
 
-        case N_ACD_STATE_ANNOUNCING:
-                /*
-                 * We were already instructed to announce the address, which
-                 * means the address is configured and in use. Hence, the
-                 * caller is responsible to serve regular ARP queries. Meaning,
-                 * we can ignore any soft conflicts (other peers doing ACD).
-                 *
-                 * But if we see a hard-conflict, we either defend the address
-                 * according to the caller's instructions, or we report the
-                 * conflict and bail out.
-                 */
+        /* Forward to left-most child that still matches @addr. */
+        while (node->left && addr == c_rbnode_entry(node->left,
+                                                    NAcdProbe,
+                                                    ip_node)->ip.s_addr)
+                node = node->left;
 
-                if (!hard_conflict)
-                        break;
+        /* Iterate all matching entries in-order. */
+        do {
+                probe = c_rbnode_entry(node, NAcdProbe, ip_node);
 
-                if (acd->defend == N_ACD_DEFEND_NEVER) {
-                        n_acd_remember_conflict(acd, now);
-                        n_acd_reset(acd);
-                        r = n_acd_push_event(acd, N_ACD_EVENT_CONFLICT, &packet->ea_hdr.ar_op, &packet->arp_sha, &packet->arp_tpa);
-                        if (r)
-                                return r;
-                } else {
-                        if (now > acd->last_defend + N_ACD_RFC_DEFEND_INTERVAL_USEC) {
-                                r = n_acd_send(acd, &acd->config.ip);
-                                if (r < 0)
-                                        return r;
-
-                                acd->last_defend = now;
-                                r = n_acd_push_event(acd, N_ACD_EVENT_DEFENDED, &packet->ea_hdr.ar_op, &packet->arp_sha, &packet->arp_tpa);
-                                if (r)
-                                        return r;
-                        } else if (acd->defend == N_ACD_DEFEND_ONCE) {
-                                n_acd_remember_conflict(acd, now);
-                                n_acd_reset(acd);
-                                r = n_acd_push_event(acd, N_ACD_EVENT_CONFLICT, &packet->ea_hdr.ar_op, &packet->arp_sha, &packet->arp_tpa);
-                                if (r)
-                                        return r;
-                        } else {
-                                r = n_acd_push_event(acd, N_ACD_EVENT_DEFENDED, &packet->ea_hdr.ar_op, &packet->arp_sha, &packet->arp_tpa);
-                                if (r)
-                                        return r;
-                        }
-                }
+                r = n_acd_probe_handle_packet(probe, packet, hard_conflict);
+                if (r)
+                        return r;
 
-                break;
-
-        case N_ACD_STATE_INIT:
-        default:
-                /*
-                 * The socket should not be dispatched in those states, since
-                 * it is neither allocated nor added to epoll. Fail hard if we
-                 * trigger this somehow.
-                 */
-                return -EIO;
-        }
+                node = c_rbnode_next(node);
+        } while (node && addr == c_rbnode_entry(node,
+                                                NAcdProbe,
+                                                ip_node)->ip.s_addr);
 
         return 0;
 }
 
 static int n_acd_dispatch_timer(NAcd *acd, struct epoll_event *event) {
-        uint64_t v;
         int r;
 
         if (event->events & (EPOLLHUP | EPOLLERR)) {
@@ -746,97 +593,113 @@ static int n_acd_dispatch_timer(NAcd *acd, struct epoll_event *event) {
         }
 
         if (event->events & EPOLLIN) {
-                for (unsigned int i = 0; i < 128; ++i) {
-                        r = read(acd->fd_timer, &v, sizeof(v));
-                        if (r == sizeof(v)) {
-                                /*
-                                 * We successfully read a timer-value. Handle it and
-                                 * return. We do NOT fall-through to EPOLLHUP handling,
-                                 * as we always must drain buffers first.
-                                 */
-                                return n_acd_handle_timeout(acd);
-                        } else if (r >= 0) {
-                                /*
-                                 * Kernel guarantees 8-byte reads; fail hard if it
-                                 * suddenly starts doing weird shit. No clue what to do
-                                 * with those values, anyway.
-                                 */
-                                return -EIO;
-                        } else if (errno == EAGAIN) {
-                                /*
-                                 * No more pending events.
-                                 */
-                                return 0;
-                        } else {
-                                /*
-                                 * Something failed. We use CLOCK_BOOTTIME, so
-                                 * ECANCELED cannot happen. Hence, there is no error
-                                 * that we could gracefully handle. Fail hard and let
-                                 * the caller deal with it.
-                                 */
-                                return -n_acd_errno();
-                        }
-                }
+                r = timer_read(&acd->timer);
+                if (r <= 0)
+                        return r;
 
-                return N_ACD_E_PREEMPTED;
+                assert(r == TIMER_E_TRIGGERED);
+
+                /*
+                 * A timer triggered, handle all pending timeouts at a given
+                 * point in time. There can only be a finite number of pending
+                 * timeouts, any new ones will be in the future, so not handled
+                 * now, but guaranteed to wake us up again when they do trigger.
+                 */
+                r = n_acd_handle_timeout(acd);
+                if (r)
+                        return r;
         }
 
         return 0;
 }
 
+static bool n_acd_packet_is_valid(NAcd *acd, void *packet, size_t n_packet) {
+        struct ether_arp *arp;
+
+        /*
+         * The eBPF filter will ensure that this function always returns true, however,
+         * this allows the eBPF filter to be an optional optimization which is necessary
+         * on older kernels.
+         *
+         * See comments in n-acd-bpf.c for details.
+         */
+
+        if (n_packet != sizeof(*arp))
+                return false;
+
+        arp = packet;
+
+        if (arp->arp_hrd != htobe16(ARPHRD_ETHER))
+                return false;
+
+        if (arp->arp_pro != htobe16(ETHERTYPE_IP))
+                return false;
+
+        if (arp->arp_hln != sizeof(struct ether_addr))
+                return false;
+
+        if (arp->arp_pln != sizeof(struct in_addr))
+                return false;
+
+        if (!memcmp(arp->arp_sha, acd->mac, sizeof(struct ether_addr)))
+                return false;
+
+        if (memcmp(arp->arp_spa, &((struct in_addr) { INADDR_ANY }), sizeof(struct in_addr))) {
+                if (arp->arp_op != htobe16(ARPOP_REQUEST) && arp->arp_op != htobe16(ARPOP_REPLY))
+                        return false;
+        } else if (arp->arp_op != htobe16(ARPOP_REQUEST)) {
+                return false;
+        }
+
+        return true;
+}
+
 static int n_acd_dispatch_socket(NAcd *acd, struct epoll_event *event) {
-        struct ether_arp packet;
-        ssize_t l;
+        const size_t n_batch = 8;
+        struct mmsghdr msgs[n_batch];
+        struct iovec iovecs[n_batch];
+        struct ether_arp data[n_batch];
+        size_t i;
+        int r, n;
+
+        for (i = 0; i < n_batch; ++i) {
+                iovecs[i].iov_base = data + i;
+                iovecs[i].iov_len = sizeof(data[i]);
+                msgs[i].msg_hdr = (struct msghdr){
+                        .msg_iov = iovecs + i,
+                        .msg_iovlen = 1,
+                };
+        }
 
-        for (unsigned int i = 0; i < 128; ++i) {
-                /*
-                 * Regardless whether EPOLLIN is set in @event->events, we always
-                 * invoke recv(2). This is a safety-net for sockets, which always fetch
-                 * queued errors on all syscalls. That means, if anything failed on the
-                 * socket, we will be notified via recv(2). This simplifies the code
-                 * and avoid magic EPOLLIN/ERR/HUP juggling.
-                 *
-                 * Note that we must use recv(2) over read(2), since the latter cannot
-                 * deal with empty packets properly.
-                 *
-                 * We explicitly skip passing MSG_TRUNC here. We *WANT*
-                 * overlong packets to be retrieved and truncated. Ethernet
-                 * frames might not have byte-granular lengths. Real hardware
-                 * does add trailing padding/garbage, so we must discard this
-                 * here.
-                 */
-                l = recv(acd->fd_socket, &packet, sizeof(packet), 0);
-                if (l == (ssize_t)sizeof(packet)) {
-                        /*
-                         * We read a full ARP packet. We never fall-through to EPOLLHUP
-                         * handling, as we always must drain buffers first.
-                         */
-                        return n_acd_handle_packet(acd, &packet);
-                } else if (l >= 0) {
-                        /*
-                         * The BPF filter discards short packets, so error out
-                         * if something slips through for any reason. Don't silently
-                         * ignore it, since we explicitly want to know if something
-                         * went fishy.
-                         */
-                        return -EIO;
-                } else if (errno == ENETDOWN || errno == ENXIO) {
+        /*
+         * We always directly call into recvmmsg(2), regardless which EPOLL*
+         * event is signalled. On sockets, the recv(2)-family of syscalls does
+         * a suitable job of handling all possible scenarios and telling us
+         * about it. Hence, lets take the easy route and always ask the kernel
+         * about the current state.
+         */
+        n = recvmmsg(acd->fd_socket, msgs, n_batch, 0, NULL);
+        if (n < 0) {
+                if (errno == ENETDOWN) {
                         /*
-                         * The network device went down or was removed. Ignore
-                         * such errors and let the pending probe time out.
-                         * Subsequent reads will simply return EAGAIN until the
-                         * device is up again and has data queued.
+                         * We get ENETDOWN if the network-device goes down or
+                         * is removed. This error is temporary and only queued
+                         * once. Subsequent reads will simply return EAGAIN
+                         * until the device is up again and has data queued.
+                         * Usually, the caller should tear down all probes when
+                         * an interface goes down, but we leave it up to the
+                         * caller to decide what to do. We propagate the code
+                         * and continue.
                          */
-                        return 0;
+                        return n_acd_raise(acd, NULL, N_ACD_EVENT_DOWN);
                 } else if (errno == EAGAIN) {
                         /*
-                         * We cannot read data from the socket (we got EAGAIN). As a safety net
-                         * check for EPOLLHUP/ERR. Those cannot be disabled with epoll, so we
-                         * must make sure to not busy-loop by ignoring them. Note that we know
-                         * recv(2) on sockets to return an error if either of these epoll-flags
-                         * is set. Hence, if we did not handle it above, we have no other way
-                         * but treating those flags as fatal errors and returning them to the
-                         * caller.
+                         * There is no more data queued and we did not get
+                         * preempted. Everything is good to go.
+                         * As a safety-net against busy-looping, we do check
+                         * for HUP/ERR. Neither should be set, since they imply
+                         * error-dequeue behavior on all socket calls. Lets
+                         * fail hard if we trigger it, so we can investigate.
                          */
                         if (event->events & (EPOLLHUP | EPOLLERR))
                                 return -EIO;
@@ -844,35 +707,63 @@ static int n_acd_dispatch_socket(NAcd *acd, struct epoll_event *event) {
                         return 0;
                 } else {
                         /*
-                         * Cannot dispatch the packet. This might be due to OOM, HUP,
-                         * or something else. We cannot handle it gracefully so forward
-                         * to the caller.
+                         * Something went wrong. Propagate the error-code, so
+                         * this can be investigated.
                          */
                         return -n_acd_errno();
                 }
+        } else if (n >= (ssize_t)n_batch) {
+                /*
+                 * If all buffers were filled with data, we cannot be sure that
+                 * there is nothing left to read. But to avoid starvation, we
+                 * cannot loop on this condition. Instead, we mark the context
+                 * as preempted so the caller can call us again.
+                 * Note that in level-triggered event-loops this condition can
+                 * be neglected, but in edge-triggered event-loops it is
+                 * crucial to forward this information.
+                 *
+                 * On the other hand, there are several conditions where the
+                 * kernel might return less batches than requested, but was
+                 * still preempted. However, all of those cases require the
+                 * preemption to have triggered a wakeup *after* we entered
+                 * recvmmsg(). Hence, even if we did not recognize the
+                 * preemption, an edge must have triggered and as such we will
+                 * handle the event on the next turn.
+                 */
+                acd->preempted = true;
+        }
+
+        for (i = 0; (ssize_t)i < n; ++i) {
+                if (!n_acd_packet_is_valid(acd, data + i, msgs[i].msg_len))
+                        continue;
+                /*
+                 * Handle the packet. Bail out if something went wrong. Note
+                 * that this must be fatal errors, since we discard all other
+                 * packets that follow.
+                 */
+                r = n_acd_handle_packet(acd, data + i);
+                if (r)
+                        return r;
         }
 
-        return N_ACD_E_PREEMPTED;
+        return 0;
 }
 
 /**
- * n_acd_dispatch() - dispatch ACD context
- * @acd:        ACD context
- *
- * Return: 0 on successful dispatch of all pending events, N_ACD_E_PREEMPT in
- *         case there are more still more events to be dispatched, or a
- *         negative error code on failure.
+ * XXX
  */
 _public_ int n_acd_dispatch(NAcd *acd) {
         struct epoll_event events[2];
         int n, i, r = 0;
-        bool preempted = false;
 
         n = epoll_wait(acd->fd_epoll, events, sizeof(events) / sizeof(*events), 0);
         if (n < 0) {
+                /* Linux never returns EINTR if `timeout == 0'. */
                 return -n_acd_errno();
         }
 
+        acd->preempted = false;
+
         for (i = 0; i < n; ++i) {
                 switch (events[i].data.u32) {
                 case N_ACD_EPOLL_TIMER:
@@ -882,35 +773,16 @@ _public_ int n_acd_dispatch(NAcd *acd) {
                         r = n_acd_dispatch_socket(acd, events + i);
                         break;
                 default:
+                        assert(0);
                         r = 0;
                         break;
                 }
 
-                if (r == N_ACD_E_PREEMPTED)
-                        preempted = true;
-                else if (r != 0)
-                        break;
-        }
-
-        if (r == -N_ACD_E_DOWN) {
-                /*
-                 * N_ACD_E_DOWN is synthesized whenever we notice
-                 * ENETDOWN-related errors on the network interface. This
-                 * allows bailing out of deep call-paths and then handling the
-                 * error gracefully here.
-                 */
-                n_acd_reset(acd);
-                r = n_acd_push_event(acd, N_ACD_EVENT_DOWN, NULL, NULL, NULL);
                 if (r)
                         return r;
-
-                return 0;
         }
 
-        if (preempted)
-                return N_ACD_E_PREEMPTED;
-        else
-                return r;
+        return acd->preempted ? N_ACD_E_PREEMPTED : 0;
 }
 
 /**
@@ -920,343 +792,75 @@ _public_ int n_acd_dispatch(NAcd *acd) {
  *
  * Returns a pointer to the next pending event. The event is still owend by
  * the context, and is only valid until the next call to n_acd_pop_event()
- * or until the context is freed.
+ * or until the owning object is freed (either the ACD context or the indicated
+ * probe object).
+ *
+ * An event either originates on the ACD context, or one of the configured
+ * probes. If the event-type has a 'probe' pointer, it originated on the
+ * indicated probe (which is *never* NULL), otherwise it originated on the
+ * context.
+ *
+ * Users must call this function repeatedly until either an error is returned,
+ * or the event-pointer is NULL. Wakeups on the epoll-fd are only guaranteed
+ * for each batch of events. Hence, it is the callers responsibility to drain
+ * the event-queue somehow after each call to n_acd_dispatch(). Note that
+ * events can only be added by n_acd_dispatch(), hence, you cannot live-lock
+ * when draining the event queue.
  *
  * The possible events are:
- *  * N_ACD_EVENT_READY:    The configured IP address was probed successfully
+ *  * N_ACD_EVENT_READY:    A configured IP address was probed successfully
  *                          and is ready to be used. Once configured on the
  *                          interface, the caller must call n_acd_announce()
  *                          to announce and start defending the address.
- *                          No further events may be received before
- *                          n_acd_announce() has been called.
  *  * N_ACD_EVENT_USED:     Someone is already using the IP address being
- *                          probed. The engine was stopped, and the caller
- *                          may restart it to try again.
- *  * N_ACD_EVENT_DEFENDED: A conflict was detected for the announced IP
+ *                          probed. The probe is put into stopped state and
+ *                          should be freed by the caller.
+ *  * N_ACD_EVENT_DEFENDED: A conflict was detected for an announced IP
  *                          address, and the engine attempted to defend it.
  *                          This is purely informational, and no action is
  *                          required by the caller.
- *  * N_ACD_EVENT_CONFLICT: A conflict was detected for the announced IP
- *                          address, and the engine was not able to defend
+ *  * N_ACD_EVENT_CONFLICT: A conflict was detected for an announced IP
+ *                          address, and the probe was not able to defend
  *                          it (according to the configured policy). The
- *                          engine has stoppde, the caller must stop using
- *                          the address immediately, and may restart the
- *                          engine to retry.
- *  * N_ACD_EVENT_DOWN:     A network error was detected. The engine was
- *                          stopped and it is the responsibility of the
- *                          caller to restart it once the network may be
- *                          functional again.
+ *                          probe halted, the caller must stop using
+ *                          the address immediately, and should free the probe.
+ *  * N_ACD_EVENT_DOWN:     The specified network interface was put down. The
+ *                          user is recommended to free *ALL* probes and
+ *                          recreate them as soon as the interface is up again.
+ *                          Note that this event is purely informational. The
+ *                          probes will continue running, but all packets will
+ *                          be blackholed, and no network packets are received,
+ *                          until the network is back up again. Hence, from an
+ *                          operational perspective, the legitimacy of the ACD
+ *                          probes is lost and the user better re-probes all
+ *                          addresses.
  *
- * Returns: 0 on success, N_ACD_E_STOPPED if there are no more events and
- *          the engine has been stopped, N_ACD_E_DONE if there are no more
- *          events, but the engine is still running, or a negative error
- *          code on failure.
+ * Returns: 0 on success, negative error code on failure. The popped event is
+ *          returned in @eventp. If no event is pending, NULL is placed in
+ *          @eventp and 0 is returned. If an error is returned, @eventp is left
+ *          untouched.
  */
 _public_ int n_acd_pop_event(NAcd *acd, NAcdEvent **eventp) {
-        acd->current = n_acd_event_node_free(acd->current);
-
-        if (c_list_is_empty(&acd->events)) {
-                if (acd->state == N_ACD_STATE_INIT)
-                        return N_ACD_E_STOPPED;
-                else
-                        return N_ACD_E_DONE;
-        }
-
-        acd->current = c_list_first_entry(&acd->events, NAcdEventNode, link);
-        c_list_unlink(&acd->current->link);
-
-        if (eventp)
-                *eventp = &acd->current->event;
-
-        return 0;
-}
-
-static int n_acd_bind_socket(NAcd *acd, int s) {
-        /*
-         * Due to strict aliasing, we cannot get uint32_t/uint16_t pointers to
-         * acd->config.mac, so provide a union accessor.
-         */
-        const union {
-                uint8_t u8[6];
-                uint16_t u16[3];
-                uint32_t u32[1];
-        } mac = {
-                .u8 = {
-                        acd->mac[0],
-                        acd->mac[1],
-                        acd->mac[2],
-                        acd->mac[3],
-                        acd->mac[4],
-                        acd->mac[5],
-                },
-        };
-        struct sock_filter filter[] = {
-                /*
-                 * Basic ARP header validation. Make sure the packet-length,
-                 * wire type, protocol type, and address lengths are correct.
-                 */
-                BPF_STMT(BPF_LD + BPF_W + BPF_LEN, 0),                                                          /* A <- packet length */
-                BPF_JUMP(BPF_JMP + BPF_JGE + BPF_K, sizeof(struct ether_arp), 1, 0),                            /* #packet >= #arp-packet ? */
-                BPF_STMT(BPF_RET + BPF_K, 0),                                                                   /* ignore */
-                BPF_STMT(BPF_LD + BPF_H + BPF_ABS, offsetof(struct ether_arp, ea_hdr.ar_hrd)),                  /* A <- header */
-                BPF_JUMP(BPF_JMP + BPF_JEQ + BPF_K, ARPHRD_ETHER, 1, 0),                                        /* header == ethernet ? */
-                BPF_STMT(BPF_RET + BPF_K, 0),                                                                   /* ignore */
-                BPF_STMT(BPF_LD + BPF_H + BPF_ABS, offsetof(struct ether_arp, ea_hdr.ar_pro)),                  /* A <- protocol */
-                BPF_JUMP(BPF_JMP + BPF_JEQ + BPF_K, ETHERTYPE_IP, 1, 0),                                        /* protocol == IP ? */
-                BPF_STMT(BPF_RET + BPF_K, 0),                                                                   /* ignore */
-                BPF_STMT(BPF_LD + BPF_B + BPF_ABS, offsetof(struct ether_arp, ea_hdr.ar_hln)),                  /* A <- hardware address length */
-                BPF_JUMP(BPF_JMP + BPF_JEQ + BPF_K, sizeof(struct ether_addr), 1, 0),                           /* length == sizeof(ether_addr)? */
-                BPF_STMT(BPF_RET + BPF_K, 0),                                                                   /* ignore */
-                BPF_STMT(BPF_LD + BPF_B + BPF_ABS, offsetof(struct ether_arp, ea_hdr.ar_pln)),                  /* A <- protocol address length */
-                BPF_JUMP(BPF_JMP + BPF_JEQ + BPF_K, sizeof(struct in_addr), 1, 0),                              /* length == sizeof(in_addr) ? */
-                BPF_STMT(BPF_RET + BPF_K, 0),                                                                   /* ignore */
-                BPF_STMT(BPF_LD + BPF_H + BPF_ABS, offsetof(struct ether_arp, ea_hdr.ar_op)),                   /* A <- operation */
-                BPF_JUMP(BPF_JMP + BPF_JEQ + BPF_K, ARPOP_REQUEST, 2, 0),                                       /* protocol == request ? */
-                BPF_JUMP(BPF_JMP + BPF_JEQ + BPF_K, ARPOP_REPLY, 1, 0),                                         /* protocol == reply ? */
-                BPF_STMT(BPF_RET + BPF_K, 0),                                                                   /* ignore */
-
-                /*
-                 * Sender hardware address must be different from ours. Note
-                 * that BPF runs in big-endian mode, but assumes immediates are
-                 * given in native-endian. This might look weird on 6-byte mac
-                 * addresses, but is needed to revert the BPF magic.
-                 */
-                BPF_STMT(BPF_LD + BPF_IMM, be32toh(mac.u32[0])),                                                /* A <- 4 bytes of client's MAC */
-                BPF_STMT(BPF_MISC + BPF_TAX, 0),                                                                /* X <- A */
-                BPF_STMT(BPF_LD + BPF_W + BPF_ABS, offsetof(struct ether_arp, arp_sha)),                        /* A <- 4 bytes of SHA */
-                BPF_STMT(BPF_ALU + BPF_XOR + BPF_X, 0),                                                         /* A xor X */
-                BPF_JUMP(BPF_JMP + BPF_JEQ + BPF_K, 0, 0, 6),                                                   /* A == 0 ? */
-                BPF_STMT(BPF_LD + BPF_IMM, be16toh(mac.u16[2])),                                                /* A <- remainder of client's MAC */
-                BPF_STMT(BPF_MISC + BPF_TAX, 0),                                                                /* X <- A */
-                BPF_STMT(BPF_LD + BPF_H + BPF_ABS, offsetof(struct ether_arp, arp_sha) + 4),                    /* A <- remainder of SHA */
-                BPF_STMT(BPF_ALU + BPF_XOR + BPF_X, 0),                                                         /* A xor X */
-                BPF_JUMP(BPF_JMP + BPF_JEQ + BPF_K, 0, 0, 1),                                                   /* A == 0 ? */
-                BPF_STMT(BPF_RET + BPF_K, 0),                                                                   /* ignore */
-
-                /*
-                 * Sender protocol address or target protocol address must be
-                 * equal to the one we care about. Again, immediates must be
-                 * given in native-endian.
-                 */
-                BPF_STMT(BPF_LD + BPF_IMM, be32toh(acd->config.ip.s_addr)),                                     /* A <- clients IP */
-                BPF_STMT(BPF_MISC + BPF_TAX, 0),                                                                /* X <- A */
-                BPF_STMT(BPF_LD + BPF_W + BPF_ABS, offsetof(struct ether_arp, arp_spa)),                        /* A <- SPA */
-                BPF_STMT(BPF_ALU + BPF_XOR + BPF_X, 0),                                                         /* X xor A */
-                BPF_JUMP(BPF_JMP + BPF_JEQ + BPF_K, 0, 0, 1),                                                   /* A == 0 ? */
-                BPF_STMT(BPF_RET + BPF_K, 65535),                                                               /* return all */
-                BPF_STMT(BPF_LD + BPF_IMM, be32toh(acd->config.ip.s_addr)),                                     /* A <- clients IP */
-                BPF_STMT(BPF_MISC + BPF_TAX, 0),                                                                /* X <- A */
-                BPF_STMT(BPF_LD + BPF_W + BPF_ABS, offsetof(struct ether_arp, arp_tpa)),                        /* A <- TPA */
-                BPF_STMT(BPF_ALU + BPF_XOR + BPF_X, 0),                                                         /* X xor A */
-                BPF_JUMP(BPF_JMP + BPF_JEQ + BPF_K, 0, 0, 1),                                                   /* A == 0 ? */
-                BPF_STMT(BPF_RET + BPF_K, 65535),                                                               /* return all */
-                BPF_STMT(BPF_RET + BPF_K, 0),                                                                   /* ignore */
-        };
-        const struct sock_fprog fprog = {
-                .len = sizeof(filter) / sizeof(*filter),
-                .filter = filter,
-        };
-        const struct sockaddr_ll address = {
-                .sll_family = AF_PACKET,
-                .sll_protocol = htobe16(ETH_P_ARP),
-                .sll_ifindex = acd->config.ifindex,
-                .sll_halen = ETH_ALEN,
-                .sll_addr = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff },
-        };
-        int r;
-
-        /*
-         * Install a packet filter that matches on the ARP header and
-         * addresses, to reduce the number of wake-ups to a minimum.
-         */
-        r = setsockopt(s, SOL_SOCKET, SO_ATTACH_FILTER, &fprog, sizeof(fprog));
-        if (r < 0)
-                return -n_acd_errno();
-
-        /*
-         * Bind the packet-socket to ETH_P_ARP and the specified network
-         * interface.
-         */
-        r = bind(s, (struct sockaddr *)&address, sizeof(address));
-        if (r < 0)
-                return -n_acd_errno();
-
-        return 0;
-}
-
-static int n_acd_setup_socket(NAcd *acd) {
-        int r, s;
-
-        s = socket(PF_PACKET, SOCK_DGRAM | SOCK_CLOEXEC | SOCK_NONBLOCK, 0);
-        if (s < 0)
-                return -n_acd_errno();
-
-        r = n_acd_bind_socket(acd, s);
-        if (r < 0)
-                goto error;
-
-        r = epoll_ctl(acd->fd_epoll, EPOLL_CTL_ADD, s,
-                      &(struct epoll_event){
-                              .events = EPOLLIN,
-                              .data.u32 = N_ACD_EPOLL_SOCKET,
-                      });
-        if (r < 0) {
-                r = -n_acd_errno();
-                goto error;
-        }
+        NAcdEventNode *node, *t_node;
 
-        acd->fd_socket = s;
-        return 0;
-
-error:
-        close(s);
-        return r;
-}
-
-/**
- * n_acd_start() - start the ACD engine
- * @acd:        ACD context
- * @config:     description of interface and desired IP address
- *
- * Start probing the given address on the given interface.
- *
- * The engine must not already be running, and there must not be
- * any pending events.
- *
- * Returns: 0 on success, N_ACD_E_INVALID_ARGUMENT in case the configuration
- *          was invalid, N_ACD_E_BUSY if the engine is running or there are
- *          pending events, or a negative error code on failure.
- */
-_public_ int n_acd_start(NAcd *acd, NAcdConfig *config) {
-        uint64_t now, delay;
-        int r;
-
-        if (config->ifindex <= 0 ||
-            config->transport != N_ACD_TRANSPORT_ETHERNET ||
-            config->n_mac != ETH_ALEN ||
-            !memcmp(config->mac, (uint8_t[ETH_ALEN]){ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff }, ETH_ALEN) ||
-            !config->ip.s_addr)
-                return N_ACD_E_INVALID_ARGUMENT;
-
-        if (acd->state != N_ACD_STATE_INIT || !c_list_is_empty(&acd->events))
-                return N_ACD_E_BUSY;
-
-        acd->config = *config;
-        memcpy(acd->mac, config->mac, config->n_mac);
-        acd->config.mac = acd->mac;
-        acd->timeout_multiplier = config->timeout_msec;
-
-        r = n_acd_setup_socket(acd);
-        if (r < 0)
-                goto error;
-
-        if (acd->timeout_multiplier) {
-                delay = 0;
-                acd->n_iteration = 0;
-
-                if (acd->last_conflict != TIME_INFINITY) {
-                        r = n_acd_now(&now);
-                        if (r < 0)
-                                goto error;
-
-                        if (now < acd->last_conflict + N_ACD_RFC_RATE_LIMIT_INTERVAL_USEC)
-                                delay = acd->last_conflict + N_ACD_RFC_RATE_LIMIT_INTERVAL_USEC - now;
+        c_list_for_each_entry_safe(node, t_node, &acd->event_list, acd_link) {
+                if (node->is_public) {
+                        n_acd_event_node_free(node);
+                        continue;
                 }
 
-                r = n_acd_schedule(acd, delay, acd->timeout_multiplier * N_ACD_RFC_PROBE_WAIT_USEC);
-                if (r < 0)
-                        goto error;
-        } else {
-                /*
-                 * A zero timeout means we drop the probing alltogether, and behave as if
-                 * the last probe succeeded immediately.
-                 */
-                acd->n_iteration = N_ACD_RFC_PROBE_NUM;
-
-                r = n_acd_schedule(acd, 0, 0);
-                if (r < 0)
-                        goto error;
+                node->is_public = true;
+                *eventp = &node->event;
+                return 0;
         }
 
-        acd->state = N_ACD_STATE_PROBING;
-        acd->defend = N_ACD_DEFEND_NEVER;
-        acd->last_defend = 0;
+        *eventp = NULL;
         return 0;
-
-error:
-        n_acd_reset(acd);
-        return r;
 }
 
 /**
- * n_acd_stop() - stop the ACD engine
- * @acd:        ACD context
- *
- * Stop the engine. No new events may be triggered, but pending events are not
- * flushed. Before calling n_acd_start() again all pending events must be popped.
- *
- * Return: 0 on success, negative error code on failure.
+ * XXX
  */
-_public_ int n_acd_stop(NAcd *acd) {
-        n_acd_reset(acd);
-        return 0;
-}
-
-/**
- * n_acd_announce() - announce the configured IP address
- * @acd:        ACD context
- * @defend:     defence policy
- *
- * Announce the IP address on the local link, and start defending it according
- * to the given policy, which mut be one of N_ACD_DEFEND_ONCE,
- * N_ACD_DEFEND_NEVER, or N_ACD_DEFEND_ALWAYS.
- *
- * This must be called after the engine in response to an N_ACD_EVENT_READY
- * event, and only after the given address has been configured on the given
- * interface.
- *
- * Return: 0 on success, N_ACD_E_INVALID_ARGUMENT in case the defence policy
- *         is invalid, N_ACD_E_BUSY if this is not in response to a
- *         N_ACD_EVENT_READY event, or a negative error code on failure.
- */
-_public_ int n_acd_announce(NAcd *acd, unsigned int defend) {
-        uint64_t now;
-        int r;
-
-        if (defend >= _N_ACD_DEFEND_N)
-                return N_ACD_E_INVALID_ARGUMENT;
-        if (acd->state != N_ACD_STATE_CONFIGURING)
-                return N_ACD_E_BUSY;
-
-        /*
-         * Sending announcements means we finished probing and use the address
-         * now. We therefore reset the conflict counter in case we adhered to
-         * the rate-limit. Since probing is properly delayed, a well-behaving
-         * client will always reset the conflict counter here. However, if you
-         * force-use an address regardless of conflicts, then this will not
-         * trigger and the conflict counter stays untouched.
-         */
-        if (acd->last_conflict != TIME_INFINITY) {
-                r = n_acd_now(&now);
-                if (r < 0)
-                        return r;
-
-                if (now >= acd->last_conflict + N_ACD_RFC_RATE_LIMIT_INTERVAL_USEC)
-                        acd->n_conflicts = 0;
-        }
-
-        /*
-         * Instead of sending the first announcement here, we schedule an idle
-         * timer. This avoids possibly recursing into the user callback. We
-         * should never trigger callbacks from arbitrary stacks, but always
-         * restrict them to the dispatcher.
-         */
-        r = n_acd_schedule(acd, 0, 0);
-        if (r < 0)
-                return r;
-
-        acd->state = N_ACD_STATE_ANNOUNCING;
-        acd->defend = defend;
-        acd->n_iteration = 0;
-        return 0;
+_public_ int n_acd_probe(NAcd *acd, NAcdProbe **probep, NAcdProbeConfig *config) {
+        return n_acd_probe_new(probep, acd, config);
 }
diff --git a/shared/n-acd/src/n-acd.h b/shared/n-acd/src/n-acd.h
index 75646243..74b0aacb 100644
--- a/shared/n-acd/src/n-acd.h
+++ b/shared/n-acd/src/n-acd.h
@@ -15,43 +15,22 @@ extern "C" {
 #include <netinet/in.h>
 #include <stdbool.h>
 
+typedef struct NAcd NAcd;
+typedef struct NAcdConfig NAcdConfig;
+typedef struct NAcdEvent NAcdEvent;
+typedef struct NAcdProbe NAcdProbe;
+typedef struct NAcdProbeConfig NAcdProbeConfig;
+
 #define N_ACD_TIMEOUT_RFC5227 (UINT64_C(9000))
 
 enum {
         _N_ACD_E_SUCCESS,
 
-        N_ACD_E_DONE,
-        N_ACD_E_STOPPED,
         N_ACD_E_PREEMPTED,
-
         N_ACD_E_INVALID_ARGUMENT,
-        N_ACD_E_BUSY,
-};
-
-typedef struct NAcd NAcd;
-
-typedef struct NAcdConfig {
-        int ifindex;
-        unsigned int transport;
-        const uint8_t *mac;
-        size_t n_mac;
-        struct in_addr ip;
-        uint64_t timeout_msec;
-} NAcdConfig;
 
-typedef struct NAcdEvent {
-        unsigned int event;
-        union {
-                struct {
-                } ready, down;
-                struct {
-                        uint16_t operation;
-                        uint8_t *sender;
-                        size_t n_sender;
-                        struct in_addr target;
-                } used, defended, conflict;
-        };
-} NAcdEvent;
+        _N_ACD_E_N,
+};
 
 enum {
         N_ACD_TRANSPORT_ETHERNET,
@@ -74,21 +53,94 @@ enum {
         _N_ACD_DEFEND_N,
 };
 
-int n_acd_new(NAcd **acdp);
-void n_acd_free(NAcd *acd);
+struct NAcdEvent {
+        unsigned int event;
+        union {
+                struct {
+                        NAcdProbe *probe;
+                } ready;
+                struct {
+                } down;
+                struct {
+                        NAcdProbe *probe;
+                        uint8_t *sender;
+                        size_t n_sender;
+                } used, defended, conflict;
+        };
+};
 
-void n_acd_get_fd(NAcd *acd, int *fdp);
+/* configs */
 
+int n_acd_config_new(NAcdConfig **configp);
+NAcdConfig *n_acd_config_free(NAcdConfig *config);
+
+void n_acd_config_set_ifindex(NAcdConfig *config, int ifindex);
+void n_acd_config_set_transport(NAcdConfig *config, unsigned int transport);
+void n_acd_config_set_mac(NAcdConfig *config, const uint8_t *mac, size_t n_mac);
+
+int n_acd_probe_config_new(NAcdProbeConfig **configp);
+NAcdProbeConfig *n_acd_probe_config_free(NAcdProbeConfig *config);
+
+void n_acd_probe_config_set_ip(NAcdProbeConfig *config, struct in_addr ip);
+void n_acd_probe_config_set_timeout(NAcdProbeConfig *config, uint64_t msecs);
+
+/* contexts */
+
+int n_acd_new(NAcd **acdp, NAcdConfig *config);
+NAcd *n_acd_ref(NAcd *acd);
+NAcd *n_acd_unref(NAcd *acd);
+
+void n_acd_get_fd(NAcd *acd, int *fdp);
 int n_acd_dispatch(NAcd *acd);
 int n_acd_pop_event(NAcd *acd, NAcdEvent **eventp);
-int n_acd_announce(NAcd *acd, unsigned int defend);
 
-int n_acd_start(NAcd *acd, NAcdConfig *config);
-int n_acd_stop(NAcd *acd);
+int n_acd_probe(NAcd *acd, NAcdProbe **probep, NAcdProbeConfig *config);
+
+/* probes */
+
+NAcdProbe *n_acd_probe_free(NAcdProbe *probe);
+
+void n_acd_probe_set_userdata(NAcdProbe *probe, void *userdata);
+void n_acd_probe_get_userdata(NAcdProbe *probe, void **userdatap);
+
+int n_acd_probe_announce(NAcdProbe *probe, unsigned int defend);
+
+/* inline helpers */
+
+static inline void n_acd_config_freep(NAcdConfig **config) {
+        if (*config)
+                n_acd_config_free(*config);
+}
+
+static inline void n_acd_config_freev(NAcdConfig *config) {
+        n_acd_config_free(config);
+}
+
+static inline void n_acd_probe_config_freep(NAcdProbeConfig **config) {
+        if (*config)
+                n_acd_probe_config_free(*config);
+}
+
+static inline void n_acd_probe_config_freev(NAcdProbeConfig *config) {
+        n_acd_probe_config_free(config);
+}
 
-static inline void n_acd_freep(NAcd **acd) {
+static inline void n_acd_unrefp(NAcd **acd) {
         if (*acd)
-                n_acd_free(*acd);
+                n_acd_unref(*acd);
+}
+
+static inline void n_acd_unrefv(NAcd *acd) {
+        n_acd_unref(acd);
+}
+
+static inline void n_acd_probe_freep(NAcdProbe **probe) {
+        if (*probe)
+                n_acd_probe_free(*probe);
+}
+
+static inline void n_acd_probe_freev(NAcdProbe *probe) {
+        n_acd_probe_free(probe);
 }
 
 #ifdef __cplusplus
diff --git a/shared/n-acd/src/util/timer.c b/shared/n-acd/src/util/timer.c
new file mode 100644
index 00000000..29627af7
--- /dev/null
+++ b/shared/n-acd/src/util/timer.c
@@ -0,0 +1,189 @@
+/*
+ * Timer Utility Library
+ */
+
+#include <assert.h>
+#include <c-rbtree.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <sys/timerfd.h>
+#include <time.h>
+#include "timer.h"
+
+int timer_init(Timer *timer) {
+        clockid_t clock = CLOCK_BOOTTIME;
+        int r;
+
+        r = timerfd_create(clock, TFD_CLOEXEC | TFD_NONBLOCK);
+        if (r < 0 && errno == EINVAL) {
+                clock = CLOCK_MONOTONIC;
+                r = timerfd_create(clock, TFD_CLOEXEC | TFD_NONBLOCK);
+        }
+        if (r < 0)
+                return -errno;
+
+        *timer = (Timer)TIMER_NULL(*timer);
+        timer->fd = r;
+        timer->clock = clock;
+
+        return 0;
+}
+
+void timer_deinit(Timer *timer) {
+        assert(c_rbtree_is_empty(&timer->tree));
+
+        if (timer->fd >= 0) {
+                close(timer->fd);
+                timer->fd = -1;
+        }
+}
+
+void timer_now(Timer *timer, uint64_t *nowp) {
+        struct timespec ts;
+        int r;
+
+        r = clock_gettime(timer->clock, &ts);
+        assert(r >= 0);
+
+        *nowp = ts.tv_sec * UINT64_C(1000000000) + ts.tv_nsec;
+}
+
+void timer_rearm(Timer *timer) {
+        uint64_t time;
+        Timeout *timeout;
+        int r;
+
+        /*
+         * A timeout value of 0 clears the timer, we sholud only set that if
+         * no timeout exists in the tree.
+         */
+
+        timeout = c_rbnode_entry(c_rbtree_first(&timer->tree), Timeout, node);
+        assert(!timeout || timeout->timeout);
+
+        time = timeout ? timeout->timeout : 0;
+
+        if (time != timer->scheduled_timeout) {
+                r = timerfd_settime(timer->fd,
+                                    TFD_TIMER_ABSTIME,
+                                    &(struct itimerspec){
+                                            .it_value = {
+                                                    .tv_sec = time / UINT64_C(1000000000),
+                                                    .tv_nsec = time % UINT64_C(1000000000),
+                                            },
+                                    },
+                                    NULL);
+                assert(r >= 0);
+
+                timer->scheduled_timeout = time;
+        }
+}
+
+int timer_read(Timer *timer) {
+        uint64_t v;
+        int r;
+
+        r = read(timer->fd, &v, sizeof(v));
+        if (r < 0) {
+                if (errno == EAGAIN) {
+                        /*
+                         * No more pending events.
+                         */
+                        return 0;
+                } else {
+                        /*
+                         * Something failed. We use CLOCK_BOOTTIME/MONOTONIC,
+                         * so ECANCELED cannot happen. Hence, there is no
+                         * error that we could gracefully handle. Fail hard
+                         * and let the caller deal with it.
+                         */
+                        return -errno;
+                }
+        } else if (r != sizeof(v) || v == 0) {
+                /*
+                 * Kernel guarantees 8-byte reads, and only to return
+                 * data if at least one timer triggered; fail hard if
+                 * it suddenly starts doing weird shit.
+                 */
+                return -EIO;
+        }
+
+        return TIMER_E_TRIGGERED;
+}
+
+
+int timer_pop_timeout(Timer *timer, uint64_t until, Timeout **timeoutp) {
+        Timeout *timeout;
+
+        /*
+         * If the first timeout is scheduled before @until, then unlink
+         * it and return it. Otherwise, return NULL.
+         */
+        timeout = c_rbnode_entry(c_rbtree_first(&timer->tree), Timeout, node);
+        if (timeout && timeout->timeout <= until) {
+                c_rbnode_unlink(&timeout->node);
+                timeout->timeout = 0;
+                *timeoutp = timeout;
+        } else {
+                *timeoutp = NULL;
+        }
+
+        return 0;
+}
+
+void timeout_schedule(Timeout *timeout, Timer *timer, uint64_t time) {
+
+        assert(time);
+
+        /*
+         * In case @timeout was already scheduled, remove it from the
+         * tree. If we are moving it to a new timer, rearm the old one.
+         */
+        if (timeout->timer) {
+                c_rbnode_unlink(&timeout->node);
+                if (timeout->timer != timer)
+                        timer_rearm(timeout->timer);
+        }
+        timeout->timer = timer;
+        timeout->timeout = time;
+
+        /*
+         * Now insert it back into the tree in the correct new position.
+         * We allow duplicates in the tree, so this insertion is open-coded.
+         */
+        {
+                Timeout *other;
+                CRBNode **slot, *parent;
+
+                slot = &timer->tree.root;
+                parent = NULL;
+                while (*slot) {
+                        other = c_rbnode_entry(*slot, Timeout, node);
+                        parent = *slot;
+                        if (timeout->timeout < other->timeout)
+                                slot = &(*slot)->left;
+                        else
+                                slot = &(*slot)->right;
+                }
+
+                c_rbtree_add(&timer->tree, parent, slot, &timeout->node);
+        }
+
+        /*
+         * Rearm the timer as we updated the timeout tree.
+         */
+        timer_rearm(timer);
+}
+
+void timeout_unschedule(Timeout *timeout) {
+        Timer *timer = timeout->timer;
+
+        if (!timer)
+                return;
+
+        c_rbnode_unlink(&timeout->node);
+        timeout->timeout = 0;
+        timeout->timer = NULL;
+
+        timer_rearm(timer);
+}
diff --git a/shared/n-acd/src/util/timer.h b/shared/n-acd/src/util/timer.h
new file mode 100644
index 00000000..2acc99e3
--- /dev/null
+++ b/shared/n-acd/src/util/timer.h
@@ -0,0 +1,53 @@
+#pragma once
+
+#include <c-rbtree.h>
+#include <inttypes.h>
+#include <stdlib.h>
+#include <time.h>
+#include <unistd.h>
+
+typedef struct Timer Timer;
+typedef struct Timeout Timeout;
+
+enum {
+        _TIMER_E_SUCCESS,
+
+        TIMER_E_TRIGGERED,
+
+        _TIMER_E_N,
+};
+
+struct Timer {
+        int fd;
+        clockid_t clock;
+        CRBTree tree;
+        uint64_t scheduled_timeout;
+};
+
+#define TIMER_NULL(_x) {                                                        \
+                .fd = -1,                                                       \
+                .tree = C_RBTREE_INIT,                                          \
+        }
+
+struct Timeout {
+        Timer *timer;
+        CRBNode node;
+        uint64_t timeout;
+};
+
+#define TIMEOUT_INIT(_x) {                                                      \
+                .node = C_RBNODE_INIT((_x).node),                               \
+        }
+
+int timer_init(Timer *timer);
+void timer_deinit(Timer *timer);
+
+void timer_now(Timer *timer, uint64_t *nowp);
+
+int timer_pop_timeout(Timer *timer, uint64_t now, Timeout **timerp);
+void timer_rearm(Timer *timer);
+int timer_read(Timer *timer);
+
+void timeout_schedule(Timeout *timeout, Timer *timer, uint64_t time);
+void timeout_unschedule(Timeout *timeout);
+