[PATCH proxmox-ebpf 01/12] dhcp: add per-tap responder BPF program

[Hannes Laimer <h.laimer@proxmox.com>]

Attached on tap ingress, the responder rewrites a request from a MAC
with a record into the reply in place and redirects it back out the
tap, so the exchange never reaches the bridge. Everything else passes
untouched, so attaching is harmless on interfaces that end up
unmanaged, and a REQUEST for a stale address is NAKed so edited
records converge within one lease.

Signed-off-by: Hannes Laimer <h.laimer@proxmox.com>
---
 Cargo.toml              |   5 +
 debian/control          |   6 +-
 src/dhcp/bpf/dhcp.bpf.c | 324 +++++++++++++++++++
 src/dhcp/bpf/types.h    |  25 ++
 tests/dhcp.rs           | 668 ++++++++++++++++++++++++++++++++++++++++
 5 files changed, 1027 insertions(+), 1 deletion(-)
 create mode 100644 src/dhcp/bpf/dhcp.bpf.c
 create mode 100644 src/dhcp/bpf/types.h
 create mode 100644 tests/dhcp.rs

diff --git a/Cargo.toml b/Cargo.toml
index a87bb2e..a1171d9 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -11,6 +11,7 @@ homepage = "https://proxmox.com"
 exclude = ["build", "debian"]
 
 [features]
+dhcp = []
 # When enabled, BPF programs compile with -DBPF_DEBUG so their DBG() macros
 # expand to bpf_printk. Off by default
 bpf-debug = []
@@ -20,3 +21,7 @@ aya = "0.13"
 anyhow = "1"
 log = "0.4"
 nix = { version = "0.29", features = ["fs", "net"] }
+
+[[test]]
+name = "dhcp"
+required-features = ["dhcp"]
diff --git a/debian/control b/debian/control
index d1400c6..8830dbd 100644
--- a/debian/control
+++ b/debian/control
@@ -39,14 +39,18 @@ Depends:
 Provides:
  librust-proxmox-ebpf+bpf-debug-dev (= ${binary:Version}),
  librust-proxmox-ebpf+default-dev (= ${binary:Version}),
+ librust-proxmox-ebpf+dhcp-dev (= ${binary:Version}),
  librust-proxmox-ebpf-0-dev (= ${binary:Version}),
  librust-proxmox-ebpf-0+bpf-debug-dev (= ${binary:Version}),
  librust-proxmox-ebpf-0+default-dev (= ${binary:Version}),
+ librust-proxmox-ebpf-0+dhcp-dev (= ${binary:Version}),
  librust-proxmox-ebpf-0.1-dev (= ${binary:Version}),
  librust-proxmox-ebpf-0.1+bpf-debug-dev (= ${binary:Version}),
  librust-proxmox-ebpf-0.1+default-dev (= ${binary:Version}),
+ librust-proxmox-ebpf-0.1+dhcp-dev (= ${binary:Version}),
  librust-proxmox-ebpf-0.1.0-dev (= ${binary:Version}),
  librust-proxmox-ebpf-0.1.0+bpf-debug-dev (= ${binary:Version}),
- librust-proxmox-ebpf-0.1.0+default-dev (= ${binary:Version})
+ librust-proxmox-ebpf-0.1.0+default-dev (= ${binary:Version}),
+ librust-proxmox-ebpf-0.1.0+dhcp-dev (= ${binary:Version})
 Description: Proxmox VE eBPF - Rust source code
  Source code for Debianized Rust crate "proxmox-ebpf"
diff --git a/src/dhcp/bpf/dhcp.bpf.c b/src/dhcp/bpf/dhcp.bpf.c
new file mode 100644
index 0000000..8f9034e
--- /dev/null
+++ b/src/dhcp/bpf/dhcp.bpf.c
@@ -0,0 +1,324 @@
+// Per-tap DHCPv4 responder. Attached on tap ingress, it answers DISCOVER and
+// REQUEST for MACs with a record by rewriting the request into the reply in
+// place and redirecting it back out the same interface. The redirect consumes
+// the request, so nothing upstream on the bridge sees it. Everything else,
+// including requests from MACs without a record, passes untouched.
+
+#include "vmlinux.h"
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_endian.h>
+#include "types.h"
+#include "bpf_debug.h"
+
+char LICENSE[] SEC("license") = "GPL";
+
+#define TC_ACT_OK 0
+
+#define ETH_HLEN 14
+#define ETH_P_IP 0x0800
+#define IP_PROTO_UDP 17
+
+#define BOOTP_LEN 236
+// replies are padded up to the minimal BOOTP message size (RFC 1542), some old
+// client stacks drop anything shorter
+#define BOOTP_MIN_LEN 300
+#define DHCP_MAGIC 0x63825363
+#define BOOTP_FLAG_BCAST 0x8000
+
+#define BOOTREQUEST 1
+#define BOOTREPLY 2
+
+#define DHCP_DISCOVER 1
+#define DHCP_OFFER 2
+#define DHCP_REQUEST 3
+#define DHCP_ACK 5
+#define DHCP_NAK 6
+
+#define OPT_PAD 0
+#define OPT_NETMASK 1
+#define OPT_ROUTER 3
+#define OPT_DNS 6
+#define OPT_MTU 26
+#define OPT_REQUESTED_IP 50
+#define OPT_LEASE 51
+#define OPT_MSGTYPE 53
+#define OPT_SERVER_ID 54
+#define OPT_WPAD 252
+#define OPT_END 255
+
+struct {
+    __uint(type, BPF_MAP_TYPE_HASH);
+    __type(key, struct dhcp_mac_key);
+    __type(value, struct dhcp_record);
+    __uint(max_entries, 65536);
+    __uint(map_flags, BPF_F_NO_PREALLOC);
+    __uint(pinning, LIBBPF_PIN_BY_NAME);
+} dhcp_records SEC(".maps");
+
+struct bootp {
+    __u8 op;
+    __u8 htype;
+    __u8 hlen;
+    __u8 hops;
+    __u32 xid;
+    __u16 secs;
+    __u16 flags;
+    __u32 ciaddr;
+    __u32 yiaddr;
+    __u32 siaddr;
+    __u32 giaddr;
+    __u8 chaddr[16];
+    __u8 sname[64];
+    __u8 file[128];
+};
+
+struct reply_pkt {
+    struct iphdr ip;
+    struct udphdr udp;
+    struct bootp bp;
+    __u8 cookie[4];
+    __u8 opts[BOOTP_MIN_LEN - BOOTP_LEN - 4];
+} __attribute__((packed));
+
+// the responder has no address on the tap, replies carry a fixed locally
+// administered source MAC that nothing ever learns
+static const __u8 SRC_MAC[6] = { 0x02, 0x00, 0x00, 0x00, 0x00, 0x01 };
+static const __u8 BCAST_MAC[6] = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };
+
+static __always_inline __u16 ip_csum(struct iphdr *ip)
+{
+    __u32 sum = 0;
+    __u16 *p = (__u16 *)ip;
+#pragma unroll
+    for (int i = 0; i < 10; i++)
+        sum += p[i];
+    sum = (sum & 0xffff) + (sum >> 16);
+    sum = (sum & 0xffff) + (sum >> 16);
+    return ~sum;
+}
+
+SEC("classifier")
+int tc_dhcp_ingress(struct __sk_buff *skb)
+{
+    __u32 min_len = ETH_HLEN + sizeof(struct iphdr) + sizeof(struct udphdr) + BOOTP_LEN + 4;
+
+    void *data = (void *)(long)skb->data;
+    void *data_end = (void *)(long)skb->data_end;
+
+    if (data + min_len > data_end) {
+        // request may sit in a non-linear skb, everything shorter is
+        // not a DHCP request anyway
+        if (skb->len < min_len || bpf_skb_pull_data(skb, min_len))
+            return TC_ACT_OK;
+        data = (void *)(long)skb->data;
+        data_end = (void *)(long)skb->data_end;
+        if (data + min_len > data_end)
+            return TC_ACT_OK;
+    }
+
+    struct ethhdr *eth = data;
+    if (eth->h_proto != bpf_htons(ETH_P_IP))
+        return TC_ACT_OK;
+
+    struct iphdr *ip = data + ETH_HLEN;
+    if (ip->version != 4 || ip->ihl != 5 || ip->protocol != IP_PROTO_UDP)
+        return TC_ACT_OK;
+
+    // a fragment is never a whole request, and past the first one the bytes at
+    // the UDP header offset are arbitrary payload
+    if (ip->frag_off & bpf_htons(0x3fff))
+        return TC_ACT_OK;
+
+    struct udphdr *udp = data + ETH_HLEN + sizeof(struct iphdr);
+    if (udp->dest != bpf_htons(67))
+        return TC_ACT_OK;
+
+    struct bootp *req = data + ETH_HLEN + sizeof(struct iphdr) + sizeof(struct udphdr);
+    if (req->op != BOOTREQUEST || req->htype != 1 || req->hlen != 6)
+        return TC_ACT_OK;
+
+    // a reply to a relayed request must go unicast to the relay instead of the
+    // client, leave those to a server that speaks relay
+    if (req->giaddr) {
+        DBG("dhcp: request relayed via %pI4 passed", &req->giaddr);
+        return TC_ACT_OK;
+    }
+
+    __u32 *magic = (void *)req + BOOTP_LEN;
+    if (*magic != bpf_htonl(DHCP_MAGIC))
+        return TC_ACT_OK;
+
+    // clients are identified by chaddr alone, a client identifier option is
+    // deliberately not honored since the records are keyed by MAC (manual
+    // allocation in RFC 2131 terms)
+    struct dhcp_mac_key key = {};
+    __builtin_memcpy(key.addr, req->chaddr, 6);
+    struct dhcp_record *rec = bpf_map_lookup_elem(&dhcp_records, &key);
+    if (!rec) {
+        DBG("dhcp: no record for %02x:%02x:%02x:%02x:%02x:%02x", key.addr[0], key.addr[1],
+            key.addr[2], key.addr[3], key.addr[4], key.addr[5]);
+        return TC_ACT_OK;
+    }
+
+    __u8 msgtype = 0;
+    __u32 requested_ip = 0;
+    __u32 server_id = 0;
+    __u32 off = min_len;
+
+    for (int i = 0; i < 128; i++) {
+        __u8 code, len;
+        if (bpf_skb_load_bytes(skb, off, &code, 1))
+            break;
+        if (code == OPT_END)
+            break;
+        if (code == OPT_PAD) {
+            off += 1;
+            continue;
+        }
+        if (bpf_skb_load_bytes(skb, off + 1, &len, 1))
+            break;
+        if (code == OPT_MSGTYPE && len == 1)
+            bpf_skb_load_bytes(skb, off + 2, &msgtype, 1);
+        else if (code == OPT_REQUESTED_IP && len == 4)
+            bpf_skb_load_bytes(skb, off + 2, &requested_ip, 4);
+        else if (code == OPT_SERVER_ID && len == 4)
+            bpf_skb_load_bytes(skb, off + 2, &server_id, 4);
+        off += 2 + len;
+    }
+
+    __u8 reply;
+    if (msgtype == DHCP_DISCOVER) {
+        reply = DHCP_OFFER;
+    } else if (msgtype == DHCP_REQUEST) {
+        // a REQUEST naming another server declines our offer and is
+        // answered, if at all, by that server
+        if (server_id && server_id != rec->server_id) {
+            DBG("dhcp: request selected server %pI4, passed", &server_id);
+            return TC_ACT_OK;
+        }
+        // a NAK on a stale address makes the client re-DISCOVER, which
+        // is how an edited record converges within one lease
+        __u32 want = requested_ip ? requested_ip : req->ciaddr;
+        reply = want == rec->ip ? DHCP_ACK : DHCP_NAK;
+        if (reply == DHCP_NAK)
+            DBG("dhcp: request for %pI4 against record %pI4, nak", &want, &rec->ip);
+    } else {
+        DBG("dhcp: message type %d passed", msgtype);
+        return TC_ACT_OK;
+    }
+
+    __u32 xid = req->xid;
+    __u16 flags = req->flags;
+    __u32 ciaddr = req->ciaddr;
+
+    struct reply_pkt buf = {};
+
+    buf.bp.op = BOOTREPLY;
+    buf.bp.htype = 1;
+    buf.bp.hlen = 6;
+    buf.bp.xid = xid;
+    buf.bp.flags = flags;
+    __builtin_memcpy(buf.bp.chaddr, key.addr, 6);
+
+    buf.cookie[0] = 0x63;
+    buf.cookie[1] = 0x82;
+    buf.cookie[2] = 0x53;
+    buf.cookie[3] = 0x63;
+
+    __u32 o = 0;
+    buf.opts[o++] = OPT_MSGTYPE;
+    buf.opts[o++] = 1;
+    buf.opts[o++] = reply;
+    buf.opts[o++] = OPT_SERVER_ID;
+    buf.opts[o++] = 4;
+    __builtin_memcpy(&buf.opts[o], &rec->server_id, 4);
+    o += 4;
+
+    if (reply != DHCP_NAK) {
+        buf.bp.yiaddr = rec->ip;
+
+        buf.opts[o++] = OPT_LEASE;
+        buf.opts[o++] = 4;
+        __builtin_memcpy(&buf.opts[o], &rec->lease, 4);
+        o += 4;
+        buf.opts[o++] = OPT_NETMASK;
+        buf.opts[o++] = 4;
+        __builtin_memcpy(&buf.opts[o], &rec->netmask, 4);
+        o += 4;
+        if (rec->router) {
+            buf.opts[o++] = OPT_ROUTER;
+            buf.opts[o++] = 4;
+            __builtin_memcpy(&buf.opts[o], &rec->router, 4);
+            o += 4;
+        }
+        if (rec->dns) {
+            buf.opts[o++] = OPT_DNS;
+            buf.opts[o++] = 4;
+            __builtin_memcpy(&buf.opts[o], &rec->dns, 4);
+            o += 4;
+        }
+        if (rec->mtu) {
+            buf.opts[o++] = OPT_MTU;
+            buf.opts[o++] = 2;
+            __builtin_memcpy(&buf.opts[o], &rec->mtu, 2);
+            o += 2;
+        }
+        // an empty WPAD answer, without it some windows versions
+        // probe for a proxy config indefinitely
+        buf.opts[o++] = OPT_WPAD;
+        buf.opts[o++] = 1;
+        buf.opts[o++] = '\n';
+    }
+    buf.opts[o++] = OPT_END;
+
+    // the zeroed tail of opts pads short replies out to the minimum, on the
+    // wire those zeros read as pad options after the end option
+    __u32 bootp_out = BOOTP_LEN + 4 + o;
+    if (bootp_out < BOOTP_MIN_LEN)
+        bootp_out = BOOTP_MIN_LEN;
+
+    __u32 payload = sizeof(struct udphdr) + bootp_out;
+
+    buf.ip.version = 4;
+    buf.ip.ihl = 5;
+    buf.ip.ttl = 64;
+    buf.ip.protocol = IP_PROTO_UDP;
+    buf.ip.tot_len = bpf_htons(sizeof(struct iphdr) + payload);
+    buf.ip.saddr = rec->server_id;
+    // a renewing client has an address and gets a unicast answer,
+    // everything else cannot be addressed yet
+    buf.ip.daddr = (reply != DHCP_NAK && ciaddr) ? ciaddr : 0xffffffff;
+    buf.ip.check = ip_csum(&buf.ip);
+
+    buf.udp.source = bpf_htons(67);
+    buf.udp.dest = bpf_htons(68);
+    buf.udp.len = bpf_htons(payload);
+    buf.udp.check = 0; // optional for IPv4
+
+    __u32 wlen = sizeof(struct iphdr) + payload;
+    if (wlen > sizeof(buf))
+        return TC_ACT_OK;
+
+    if (bpf_skb_change_tail(skb, ETH_HLEN + wlen, 0))
+        return TC_ACT_OK;
+
+    // NAKs are always broadcast, and a client without an address that set the
+    // BROADCAST flag asked for a broadcast reply
+    __u8 eth_hdr[ETH_HLEN];
+    if (reply == DHCP_NAK || (!ciaddr && (flags & bpf_htons(BOOTP_FLAG_BCAST)))) {
+        __builtin_memcpy(eth_hdr, BCAST_MAC, 6);
+    } else {
+        __builtin_memcpy(eth_hdr, key.addr, 6);
+    }
+    __builtin_memcpy(eth_hdr + 6, SRC_MAC, 6);
+    eth_hdr[12] = 0x08;
+    eth_hdr[13] = 0x00;
+
+    if (bpf_skb_store_bytes(skb, 0, eth_hdr, ETH_HLEN, 0))
+        return TC_ACT_OK;
+    if (bpf_skb_store_bytes(skb, ETH_HLEN, &buf, wlen, 0))
+        return TC_ACT_OK;
+
+    DBG("dhcp: reply type %d with %pI4 to ifindex %d", reply, &buf.bp.yiaddr, skb->ifindex);
+    return bpf_redirect(skb->ifindex, 0);
+}
diff --git a/src/dhcp/bpf/types.h b/src/dhcp/bpf/types.h
new file mode 100644
index 0000000..84f1564
--- /dev/null
+++ b/src/dhcp/bpf/types.h
@@ -0,0 +1,25 @@
+#ifndef PROXMOX_EBPF_DHCP_TYPES_H
+#define PROXMOX_EBPF_DHCP_TYPES_H
+
+// Keep in sync with ../types.rs
+// __u8/__u16/__u32 come from vmlinux.h
+
+struct dhcp_mac_key {
+    __u8 addr[6];
+    __u8 _pad[2];
+};
+
+// addresses, lease and mtu are stored in network byte order, so a
+// reply copies them into the packet as-is
+struct dhcp_record {
+    __u32 ip;
+    __u32 netmask;
+    __u32 router; // 0 = not served
+    __u32 dns; // 0 = not served
+    __u32 server_id;
+    __u32 lease;
+    __u16 mtu; // 0 = not served
+    __u8 _pad[2];
+};
+
+#endif
diff --git a/tests/dhcp.rs b/tests/dhcp.rs
new file mode 100644
index 0000000..13a9ecd
--- /dev/null
+++ b/tests/dhcp.rs
@@ -0,0 +1,668 @@
+//! The dhcp responder program run natively: crafted requests in, the rewritten reply out.
+
+mod common;
+
+use std::ffi::{c_int, c_void};
+
+use common::*;
+
+unsafe extern "C" {
+    fn tc_dhcp_ingress(skb: *mut SkBuff) -> c_int;
+    static dhcp_records: u8;
+}
+
+const MAC: [u8; 6] = [0xda, 0x65, 0x8f, 0x18, 0x9b, 0x6f];
+const SRC_MAC: [u8; 6] = [0x02, 0x00, 0x00, 0x00, 0x00, 0x01];
+const BCAST: [u8; 6] = [0xff; 6];
+const IFINDEX: u32 = 42;
+
+const IP: [u8; 4] = [10, 0, 0, 100];
+const MASK: [u8; 4] = [255, 255, 255, 0];
+const GW: [u8; 4] = [10, 0, 0, 1];
+const DNS: [u8; 4] = [1, 1, 1, 1];
+const LEASE: u32 = 300;
+const MTU: u16 = 1500;
+
+const OPTS_OFF: usize = 14 + 20 + 8 + 236 + 4;
+
+const DISCOVER: &[u8] = &[53, 1, 1];
+const REQUEST: &[u8] = &[53, 1, 3];
+
+fn records_map() -> *const c_void {
+    (unsafe { &dhcp_records } as *const u8).cast()
+}
+
+fn key(mac: [u8; 6]) -> [u8; 8] {
+    let mut k = [0u8; 8];
+    k[..6].copy_from_slice(&mac);
+    k
+}
+
+fn record(
+    ip: [u8; 4],
+    mask: [u8; 4],
+    router: [u8; 4],
+    dns: [u8; 4],
+    server: [u8; 4],
+    lease: u32,
+    mtu: u16,
+) -> [u8; 28] {
+    let mut r = [0u8; 28];
+    r[0..4].copy_from_slice(&ip);
+    r[4..8].copy_from_slice(&mask);
+    r[8..12].copy_from_slice(&router);
+    r[12..16].copy_from_slice(&dns);
+    r[16..20].copy_from_slice(&server);
+    r[20..24].copy_from_slice(&lease.to_be_bytes());
+    r[24..26].copy_from_slice(&mtu.to_be_bytes());
+    r
+}
+
+fn setup_full_record() {
+    register_map(records_map(), 8);
+    map_insert(
+        records_map(),
+        &key(MAC),
+        &record(IP, MASK, GW, DNS, GW, LEASE, MTU),
+    );
+}
+
+struct Request {
+    mac: [u8; 6],
+    xid: [u8; 4],
+    flags: [u8; 2],
+    ciaddr: [u8; 4],
+    giaddr: [u8; 4],
+    options: Vec<u8>,
+    dport: u16,
+    ethertype: [u8; 2],
+    ipproto: u8,
+    frag_off: [u8; 2],
+    ip_options: Vec<u8>,
+    op: u8,
+    htype: u8,
+    hlen: u8,
+}
+
+impl Default for Request {
+    fn default() -> Self {
+        Request {
+            mac: MAC,
+            xid: [0xde, 0xad, 0xbe, 0xef],
+            flags: [0, 0],
+            ciaddr: [0; 4],
+            giaddr: [0; 4],
+            options: DISCOVER.to_vec(),
+            dport: 67,
+            ethertype: [0x08, 0x00],
+            ipproto: 17,
+            frag_off: [0, 0],
+            ip_options: Vec::new(),
+            op: 1,
+            htype: 1,
+            hlen: 6,
+        }
+    }
+}
+
+impl Request {
+    fn build(&self) -> Vec<u8> {
+        assert_eq!(self.ip_options.len() % 4, 0);
+        let ihl = 5 + self.ip_options.len() / 4;
+        let payload = 8 + 236 + 4 + self.options.len() + 1;
+        let mut p = Vec::new();
+        // ethernet
+        p.extend_from_slice(&BCAST);
+        p.extend_from_slice(&self.mac);
+        p.extend_from_slice(&self.ethertype);
+        // ipv4
+        p.extend_from_slice(&[0x40 | ihl as u8, 0]);
+        p.extend_from_slice(&((ihl * 4 + payload) as u16).to_be_bytes());
+        p.extend_from_slice(&[0, 0]); // id
+        p.extend_from_slice(&self.frag_off);
+        p.extend_from_slice(&[64, self.ipproto, 0, 0]);
+        p.extend_from_slice(&[0, 0, 0, 0]); // saddr
+        p.extend_from_slice(&[255, 255, 255, 255]); // daddr
+        p.extend_from_slice(&self.ip_options);
+        // udp
+        p.extend_from_slice(&68u16.to_be_bytes());
+        p.extend_from_slice(&self.dport.to_be_bytes());
+        p.extend_from_slice(&(payload as u16).to_be_bytes());
+        p.extend_from_slice(&[0, 0]);
+        // bootp
+        p.extend_from_slice(&[self.op, self.htype, self.hlen, 0]);
+        p.extend_from_slice(&self.xid);
+        p.extend_from_slice(&[0, 0]); // secs
+        p.extend_from_slice(&self.flags);
+        p.extend_from_slice(&self.ciaddr);
+        p.extend_from_slice(&[0; 8]); // yiaddr, siaddr
+        p.extend_from_slice(&self.giaddr);
+        p.extend_from_slice(&self.mac);
+        p.extend_from_slice(&[0; 10]); // chaddr padding
+        p.extend_from_slice(&[0; 192]); // sname, file
+        // cookie and options
+        p.extend_from_slice(&[0x63, 0x82, 0x53, 0x63]);
+        p.extend_from_slice(&self.options);
+        p.push(255);
+        p
+    }
+
+    fn run(&self) -> (c_int, TestSkb) {
+        let mut skb = TestSkb::new(&self.build(), IFINDEX);
+        let verdict = skb.run(tc_dhcp_ingress);
+        (verdict, skb)
+    }
+}
+
+fn parse_opts(pkt: &[u8]) -> Vec<(u8, Vec<u8>)> {
+    let mut opts = Vec::new();
+    let mut off = OPTS_OFF;
+    loop {
+        let code = pkt[off];
+        if code == 255 {
+            break;
+        }
+        if code == 0 {
+            off += 1;
+            continue;
+        }
+        let len = pkt[off + 1] as usize;
+        opts.push((code, pkt[off + 2..off + 2 + len].to_vec()));
+        off += 2 + len;
+    }
+    opts
+}
+
+fn ip_csum_ok(pkt: &[u8]) -> bool {
+    let mut sum = 0u32;
+    for w in pkt[14..34].chunks(2) {
+        sum += u32::from(u16::from_be_bytes([w[0], w[1]]));
+    }
+    while sum > 0xffff {
+        sum = (sum & 0xffff) + (sum >> 16);
+    }
+    sum == 0xffff
+}
+
+/// The offset just past the end option of a reply.
+fn opts_end(pkt: &[u8]) -> usize {
+    let mut off = OPTS_OFF;
+    loop {
+        match pkt[off] {
+            255 => return off + 1,
+            0 => off += 1,
+            _ => off += 2 + pkt[off + 1] as usize,
+        }
+    }
+}
+
+/// What every reply has to look like whatever the request was. The addressing and the answer
+/// itself are the caller's to check.
+fn assert_reply_invariants(pkt: &[u8]) {
+    assert_eq!(&pkt[6..12], &SRC_MAC, "eth src");
+    assert_eq!(&pkt[12..14], &[0x08, 0x00], "ethertype");
+
+    assert_eq!(pkt[14], 0x45, "ihl/version");
+    assert_eq!(pkt[22], 64, "ttl");
+    assert_eq!(pkt[23], 17, "protocol");
+    assert_eq!(&pkt[26..30], &GW, "ip src is the server id");
+    assert!(ip_csum_ok(pkt), "ip checksum");
+    let tot_len = u16::from_be_bytes([pkt[16], pkt[17]]) as usize;
+    assert_eq!(tot_len, pkt.len() - 14, "ip total length");
+
+    assert_eq!(&pkt[34..36], &67u16.to_be_bytes(), "udp sport");
+    assert_eq!(&pkt[36..38], &68u16.to_be_bytes(), "udp dport");
+    let udp_len = u16::from_be_bytes([pkt[38], pkt[39]]) as usize;
+    assert_eq!(udp_len, pkt.len() - 34, "udp length");
+    assert_eq!(&pkt[40..42], &[0, 0], "udp checksum left zero");
+    assert!(pkt.len() - 42 >= 300, "bootp minimum message size");
+
+    assert_eq!(&pkt[42..45], &[2, 1, 6], "bootp reply op, htype, hlen");
+    assert_eq!(&pkt[46..50], &[0xde, 0xad, 0xbe, 0xef], "xid preserved");
+    assert_eq!(&pkt[70..76], &MAC, "chaddr");
+    assert_eq!(&pkt[278..282], &[0x63, 0x82, 0x53, 0x63], "cookie");
+    assert!(
+        matches!(parse_opts(pkt).first(), Some((53, t)) if t.len() == 1 && [2, 5, 6].contains(&t[0])),
+        "message type leads the options"
+    );
+    let end = opts_end(pkt);
+    assert!(
+        pkt[end..].iter().all(|&b| b == 0),
+        "padding after the end option is zero"
+    );
+}
+
+fn assert_reply_headers(pkt: &[u8], eth_dst: [u8; 6], ip_dst: [u8; 4], yiaddr: [u8; 4]) {
+    assert_reply_invariants(pkt);
+    assert_eq!(&pkt[0..6], &eth_dst, "eth dst");
+    assert_eq!(&pkt[30..34], &ip_dst, "ip dst");
+    assert_eq!(&pkt[58..62], &yiaddr, "yiaddr");
+}
+
+#[test]
+fn discover_gets_full_offer() {
+    setup_full_record();
+    let (verdict, skb) = Request::default().run();
+
+    assert_eq!(verdict, TC_ACT_REDIRECT);
+    assert_eq!(redirected(), Some(IFINDEX));
+
+    let pkt = skb.packet();
+    assert_reply_headers(pkt, MAC, [255, 255, 255, 255], IP);
+    assert_eq!(
+        parse_opts(pkt),
+        vec![
+            (53, vec![2]),
+            (54, GW.to_vec()),
+            (51, LEASE.to_be_bytes().to_vec()),
+            (1, MASK.to_vec()),
+            (3, GW.to_vec()),
+            (6, DNS.to_vec()),
+            (26, MTU.to_be_bytes().to_vec()),
+            (252, vec![b'\n']),
+        ],
+    );
+}
+
+#[test]
+fn offer_skips_unset_options() {
+    register_map(records_map(), 8);
+    map_insert(
+        records_map(),
+        &key(MAC),
+        &record(IP, MASK, [0; 4], [0; 4], GW, LEASE, 0),
+    );
+    let (verdict, skb) = Request::default().run();
+
+    assert_eq!(verdict, TC_ACT_REDIRECT);
+    let codes: Vec<u8> = parse_opts(skb.packet()).iter().map(|(c, _)| *c).collect();
+    assert_eq!(codes, vec![53, 54, 51, 1, 252]);
+}
+
+#[test]
+fn matching_request_gets_ack() {
+    setup_full_record();
+    let mut options = REQUEST.to_vec();
+    options.extend_from_slice(&[50, 4]);
+    options.extend_from_slice(&IP);
+    let (verdict, skb) = Request {
+        options,
+        ..Request::default()
+    }
+    .run();
+
+    assert_eq!(verdict, TC_ACT_REDIRECT);
+    let pkt = skb.packet();
+    assert_reply_headers(pkt, MAC, [255, 255, 255, 255], IP);
+    assert_eq!(parse_opts(pkt)[0], (53, vec![5]));
+}
+
+#[test]
+fn stale_request_gets_nak() {
+    setup_full_record();
+    let mut options = REQUEST.to_vec();
+    options.extend_from_slice(&[50, 4, 10, 0, 0, 77]);
+    let (verdict, skb) = Request {
+        options,
+        ..Request::default()
+    }
+    .run();
+
+    assert_eq!(verdict, TC_ACT_REDIRECT);
+    let pkt = skb.packet();
+    assert_reply_headers(pkt, BCAST, [255, 255, 255, 255], [0; 4]);
+    assert_eq!(parse_opts(pkt), vec![(53, vec![6]), (54, GW.to_vec())]);
+}
+
+#[test]
+fn renewal_is_answered_unicast() {
+    setup_full_record();
+    let (verdict, skb) = Request {
+        options: REQUEST.to_vec(),
+        ciaddr: IP,
+        ..Request::default()
+    }
+    .run();
+
+    assert_eq!(verdict, TC_ACT_REDIRECT);
+    let pkt = skb.packet();
+    assert_reply_headers(pkt, MAC, IP, IP);
+    assert_eq!(parse_opts(pkt)[0], (53, vec![5]));
+}
+
+#[test]
+fn request_selecting_this_server_gets_ack() {
+    setup_full_record();
+    let mut options = REQUEST.to_vec();
+    options.extend_from_slice(&[54, 4]);
+    options.extend_from_slice(&GW);
+    options.extend_from_slice(&[50, 4]);
+    options.extend_from_slice(&IP);
+    let (verdict, skb) = Request {
+        options,
+        ..Request::default()
+    }
+    .run();
+
+    assert_eq!(verdict, TC_ACT_REDIRECT);
+    assert_eq!(parse_opts(skb.packet())[0], (53, vec![5]));
+}
+
+#[test]
+fn request_selecting_another_server_passes_untouched() {
+    setup_full_record();
+    let mut options = REQUEST.to_vec();
+    options.extend_from_slice(&[54, 4, 192, 168, 7, 7]);
+    options.extend_from_slice(&[50, 4, 10, 0, 0, 77]);
+    let req = Request {
+        options,
+        ..Request::default()
+    };
+    let (verdict, skb) = req.run();
+
+    assert_eq!(verdict, TC_ACT_OK);
+    assert_eq!(redirected(), None);
+    assert_eq!(skb.packet(), &req.build()[..]);
+}
+
+#[test]
+fn relayed_request_passes_untouched() {
+    setup_full_record();
+    let req = Request {
+        giaddr: [10, 0, 0, 254],
+        ..Request::default()
+    };
+    let (verdict, skb) = req.run();
+
+    assert_eq!(verdict, TC_ACT_OK);
+    assert_eq!(redirected(), None);
+    assert_eq!(skb.packet(), &req.build()[..]);
+}
+
+#[test]
+fn fragments_pass_untouched() {
+    setup_full_record();
+    for frag_off in [[0x20, 0x00], [0x00, 0x01]] {
+        let req = Request {
+            frag_off,
+            ..Request::default()
+        };
+        let (verdict, skb) = req.run();
+        assert_eq!(verdict, TC_ACT_OK);
+        assert_eq!(skb.packet(), &req.build()[..]);
+    }
+
+    let (verdict, _) = Request {
+        frag_off: [0x40, 0x00],
+        ..Request::default()
+    }
+    .run();
+    assert_eq!(verdict, TC_ACT_REDIRECT, "DF alone is not a fragment");
+}
+
+#[test]
+fn broadcast_flag_gets_l2_broadcast_reply() {
+    setup_full_record();
+    let (verdict, skb) = Request {
+        flags: [0x80, 0],
+        ..Request::default()
+    }
+    .run();
+
+    assert_eq!(verdict, TC_ACT_REDIRECT);
+    let pkt = skb.packet();
+    assert_reply_headers(pkt, BCAST, [255, 255, 255, 255], IP);
+    assert_eq!(&pkt[52..54], &[0x80, 0], "flags echoed");
+
+    // ciaddr wins over the flag, a renewing client is addressable
+    let (verdict, skb) = Request {
+        flags: [0x80, 0],
+        ciaddr: IP,
+        options: REQUEST.to_vec(),
+        ..Request::default()
+    }
+    .run();
+    assert_eq!(verdict, TC_ACT_REDIRECT);
+    assert_reply_headers(skb.packet(), MAC, IP, IP);
+}
+
+#[test]
+fn unknown_mac_passes_untouched() {
+    register_map(records_map(), 8);
+    let req = Request::default();
+    let (verdict, skb) = req.run();
+
+    assert_eq!(verdict, TC_ACT_OK);
+    assert_eq!(redirected(), None);
+    assert_eq!(skb.packet(), &req.build()[..]);
+}
+
+#[test]
+fn non_dhcp_traffic_passes_untouched() {
+    setup_full_record();
+    let variants = [
+        Request {
+            dport: 53,
+            ..Request::default()
+        },
+        Request {
+            ethertype: [0x86, 0xdd],
+            ..Request::default()
+        },
+        Request {
+            ipproto: 6,
+            ..Request::default()
+        },
+    ];
+    for req in variants {
+        let (verdict, skb) = req.run();
+        assert_eq!(verdict, TC_ACT_OK);
+        assert_eq!(skb.packet(), &req.build()[..]);
+    }
+
+    let frame = Request::default().build();
+    let mut skb = TestSkb::new(&frame[..100], IFINDEX);
+    assert_eq!(skb.run(tc_dhcp_ingress), TC_ACT_OK);
+
+    let mut corrupted = frame.clone();
+    corrupted[278] = 0;
+    let mut skb = TestSkb::new(&corrupted, IFINDEX);
+    assert_eq!(skb.run(tc_dhcp_ingress), TC_ACT_OK);
+}
+
+#[test]
+fn options_walk_handles_padding_and_early_end() {
+    setup_full_record();
+
+    let mut options = vec![0, 0, 0];
+    options.extend_from_slice(DISCOVER);
+    let (verdict, _) = Request {
+        options,
+        ..Request::default()
+    }
+    .run();
+    assert_eq!(verdict, TC_ACT_REDIRECT);
+
+    let mut options = vec![255];
+    options.extend_from_slice(DISCOVER);
+    let (verdict, skb) = Request {
+        options,
+        ..Request::default()
+    }
+    .run();
+    assert_eq!(verdict, TC_ACT_OK, "message type after end is not parsed");
+    assert_eq!(redirected(), None);
+    drop(skb);
+}
+
+#[test]
+fn stale_renewal_gets_broadcast_nak() {
+    setup_full_record();
+    let (verdict, skb) = Request {
+        options: REQUEST.to_vec(),
+        ciaddr: [10, 0, 0, 77],
+        ..Request::default()
+    }
+    .run();
+
+    assert_eq!(verdict, TC_ACT_REDIRECT);
+    let pkt = skb.packet();
+    assert_reply_headers(pkt, BCAST, [255, 255, 255, 255], [0; 4]);
+    assert_eq!(parse_opts(pkt), vec![(53, vec![6]), (54, GW.to_vec())]);
+}
+
+#[test]
+fn request_without_address_gets_nak() {
+    setup_full_record();
+    let (verdict, skb) = Request {
+        options: REQUEST.to_vec(),
+        ..Request::default()
+    }
+    .run();
+
+    assert_eq!(verdict, TC_ACT_REDIRECT);
+    let pkt = skb.packet();
+    assert_reply_headers(pkt, BCAST, [255, 255, 255, 255], [0; 4]);
+    assert_eq!(parse_opts(pkt)[0], (53, vec![6]));
+}
+
+#[test]
+fn realistic_request_is_answered_and_shrunk() {
+    setup_full_record();
+    let mut options = REQUEST.to_vec();
+    // a client identifier naming something else, records are keyed by chaddr alone
+    options.extend_from_slice(&[61, 7, 1, 0xde, 0xad, 0xbe, 0xef, 0x00, 0x01]);
+    options.extend_from_slice(&[50, 4]);
+    options.extend_from_slice(&IP);
+    options.extend_from_slice(&[54, 4]);
+    options.extend_from_slice(&GW);
+    options.extend_from_slice(&[12, 14]);
+    options.extend_from_slice(b"dhcp-client-01");
+    options.extend_from_slice(&[60, 32]);
+    options.extend_from_slice(b"PXEClient:Arch:00007:UNDI:003016");
+    options.extend_from_slice(&[55, 20]);
+    options.extend_from_slice(&[
+        1, 2, 3, 6, 12, 15, 17, 26, 28, 40, 41, 42, 51, 54, 58, 59, 66, 67, 119, 121,
+    ]);
+    options.extend_from_slice(&[57, 2, 0x05, 0xdc]);
+    options.extend_from_slice(&[93, 2, 0, 7]);
+    options.extend_from_slice(&[94, 3, 1, 3, 16]);
+    options.extend_from_slice(&[97, 17, 0]);
+    options.extend_from_slice(&[0x11; 16]);
+    let req = Request {
+        options,
+        ..Request::default()
+    };
+    let request_len = req.build().len();
+    let (verdict, skb) = req.run();
+
+    assert_eq!(verdict, TC_ACT_REDIRECT);
+    let pkt = skb.packet();
+    assert!(pkt.len() < request_len, "reply is shorter than the request");
+    assert_eq!(
+        pkt.len(),
+        14 + 20 + 8 + 300,
+        "trimmed to the padded minimum"
+    );
+    assert_reply_headers(pkt, MAC, [255, 255, 255, 255], IP);
+    assert_eq!(parse_opts(pkt)[0], (53, vec![5]));
+}
+
+#[test]
+fn other_message_types_pass_untouched() {
+    setup_full_record();
+    for msgtype in [4, 7, 8] {
+        let req = Request {
+            options: vec![53, 1, msgtype],
+            ..Request::default()
+        };
+        let (verdict, skb) = req.run();
+        assert_eq!(verdict, TC_ACT_OK, "message type {msgtype}");
+        assert_eq!(redirected(), None);
+        assert_eq!(skb.packet(), &req.build()[..]);
+    }
+}
+
+#[test]
+fn foreign_bootp_passes_untouched() {
+    setup_full_record();
+    let variants = [
+        // a reply coming in from the guest side, a guest running its own server
+        Request {
+            op: 2,
+            ..Request::default()
+        },
+        Request {
+            htype: 6,
+            ..Request::default()
+        },
+        Request {
+            hlen: 16,
+            ..Request::default()
+        },
+        Request {
+            ip_options: vec![1, 1, 1, 1],
+            ..Request::default()
+        },
+    ];
+    for req in variants {
+        let (verdict, skb) = req.run();
+        assert_eq!(verdict, TC_ACT_OK);
+        assert_eq!(redirected(), None);
+        assert_eq!(skb.packet(), &req.build()[..]);
+    }
+}
+
+#[test]
+fn truncated_option_ends_the_walk() {
+    setup_full_record();
+
+    // a length running past the packet before the message type leaves nothing to answer
+    let mut options = vec![12, 200];
+    options.extend_from_slice(DISCOVER);
+    let req = Request {
+        options,
+        ..Request::default()
+    };
+    let (verdict, skb) = req.run();
+    assert_eq!(verdict, TC_ACT_OK);
+    assert_eq!(redirected(), None);
+    assert_eq!(skb.packet(), &req.build()[..]);
+
+    // after the message type it only cuts the walk short, what was read still counts
+    let mut options = DISCOVER.to_vec();
+    options.extend_from_slice(&[12, 200]);
+    let (verdict, skb) = Request {
+        options,
+        ..Request::default()
+    }
+    .run();
+    assert_eq!(verdict, TC_ACT_REDIRECT);
+    assert_reply_headers(skb.packet(), MAC, [255, 255, 255, 255], IP);
+}
+
+#[test]
+fn arbitrary_option_bytes_never_break_the_reply() {
+    setup_full_record();
+    let mut lcg = 0x2545f4914f6cdd1du64;
+    let mut rand = move || {
+        lcg = lcg
+            .wrapping_mul(6364136223846793005)
+            .wrapping_add(1442695040888963407);
+        (lcg >> 33) as u8
+    };
+
+    for _ in 0..500 {
+        let len = (rand() % 60) as usize;
+        let options: Vec<u8> = (0..len).map(|_| rand()).collect();
+        let (verdict, skb) = Request {
+            options,
+            ..Request::default()
+        }
+        .run();
+        assert!(verdict == TC_ACT_OK || verdict == TC_ACT_REDIRECT);
+        if verdict == TC_ACT_REDIRECT {
+            assert_reply_invariants(skb.packet());
+        }
+    }
+}
-- 
2.47.3