java-topology/docs/tickets/dragonflybsd-0001.md

dragonflybsd-0001 — CWE-407: ifa_ifwithaddr / ifa_ifwithnet / ifa_ifwithdstaddr — O(I×A) per-packet scan

Severity: HIGH File: sys/net/if.c Functions: ifa_ifwithaddr, ifa_ifwithnet, ifa_ifwithdstaddr CWE: CWE-407 Algorithmic Complexity

Defect

Two-level nested loop — outer for loop over ifnet_array (I interfaces), inner TAILQ_FOREACH over if_addrheads[mycpuid] (A addresses per interface). O(I×A) per call.

Called from ip_dooptions() inside ip_input() — per-packet on source-routed traffic. At I=50, A=20: 1,000 comparisons per packet.

for (i = 0; i < ifnet_array_count; i++) {
    ifp = ifnet_array[i];
    TAILQ_FOREACH(ifa, &ifp->if_addrheads[mycpuid], ifa_link) {
        if (ifa->ifa_addr->sa_family != af)
            continue;
        if (address_match(ifa->ifa_addr, addr))  // O(1) compare
            return ifa;
    }
}

Complexity: O(I×A) per call, called per source-routed packet in ip_input().

Scale

I=50 interfaces, A=20 addresses per interface: 1,000 comparisons per packet. On a busy router with high source-routed traffic volume, this dominates ip_input() cost.

Fix

Per-CPU hash table keyed on (AF, address bytes) → ifaddr*. O(1) lookup replaces the nested scan. Hash table is updated on ifa_ifadd/ifa_ifdel which are already serialized.