# UNDF: UNDF-2026-000000200
# openbsd-0002 — `if.c`: O(I×A) nested scan in `ifa_ifwithaddr`

## Status
PATCHED

## Severity
HIGH (called per-packet in ip_input.c, icmp6.c, in_pcb.c, ip_output.c; O(I×A) per
lookup where I=interface count, A=addresses per interface)

## Location
`sys/net/if.c`, function `ifa_ifwithaddr()` (~line 1619)

## Description
`ifa_ifwithaddr` locates an interface address matching a given `sockaddr` by
performing a nested iteration over all interfaces × all addresses per interface:

```c
struct ifaddr *
ifa_ifwithaddr(const struct sockaddr *addr, u_int rtableid)
{
    struct ifnet *ifp;
    struct ifaddr *ifa;
    u_int rdomain = rtable_l2(rtableid);

    TAILQ_FOREACH(ifp, &ifnetlist, if_list) {          // O(I)
        if (ifp->if_rdomain != rdomain)
            continue;
        TAILQ_FOREACH(ifa, &ifp->if_addrlist, ifa_list) {  // O(A)
            if (ifa->ifa_addr->sa_family != addr->sa_family)
                continue;
            if (equal(addr, ifa->ifa_addr))
                return (ifa);
        }
    }
    return (NULL);
}
```

This is O(I×A) per call. The function is called in **packet-reception hot paths**:
- `sys/netinet/ip_input.c` — raw IP input (line 1265, 1399)
- `sys/netinet6/in6_pcb.c` — IPv6 PCB bind (line 191)
- `sys/netinet/in_pcb.c` — IPv4 PCB bind (line 402)
- `sys/netinet/ip_output.c` — IP output multicast (line 1485)
- `sys/netinet/ip_icmp.c` — ICMP error path (line 756)
- `sys/netinet6/icmp6.c` — ICMPv6 path (line 1150)
- `sys/net/route.c` — route add/check (line 709)

On a system with 50 interfaces (each with 3 addresses), each call scans up to 150
entries. Under high packet rates (100k pps), this results in 15M comparisons/sec.

## Complexity
- Slow: O(I × A) per address lookup
- Fast: O(1) amortized with a hash table keyed by `(af, addr)` per rdomain
- At I=50, A=3: 150 comparisons → ~1 with hash
- At I=100, A=10: 1000 comparisons → ~1 with hash

## Root Cause
`ifa_ifwithaddr` predates the routing table infrastructure. Modern OpenBSD routing
uses an RB_TREE (`rtable_lookup`) for route lookups, but local address resolution
still uses the flat `ifnetlist` scan.

## Fix
Add a `struct ifaddr_hash` — a per-rdomain hash table mapping `(af, sa_data[N])`
→ `struct ifaddr *`. Maintain this hash on `if_addra`/`if_deladdr` events.
`ifa_ifwithaddr` becomes a single hash lookup.

Alternatively: use the existing `rtable` infrastructure —
`rtable_lookup(rtableid, addr, NULL, NULL, RTV_PROTO_LOCAL)` already performs
O(log N) or O(1) lookup for local addresses if the local host route is installed.

## Patch (conceptual — C)

```c
/* Add to sys/net/if.h: */
void	 ifa_hash_insert(struct ifaddr *);
void	 ifa_hash_remove(struct ifaddr *);
struct ifaddr *ifa_ifwithaddr(const struct sockaddr *, u_int);

/* In sys/net/if.c: */
#define IFA_HASH_SIZE	256
#define IFA_HASH(sa)	/* hash sa_family + first 4 bytes of sa_data */

static struct ifaddr_list ifa_hashtbl[IFA_HASH_SIZE];

struct ifaddr *
ifa_ifwithaddr(const struct sockaddr *addr, u_int rtableid)
{
    unsigned int h = IFA_HASH(addr);
    struct ifaddr *ifa;

    NET_ASSERT_LOCKED();

    LIST_FOREACH(ifa, &ifa_hashtbl[h], ifa_hash) {
        if (ifa->ifa_ifp->if_rdomain != rtable_l2(rtableid))
            continue;
        if (ifa->ifa_addr->sa_family == addr->sa_family &&
            equal(addr, ifa->ifa_addr))
            return (ifa);
    }
    return (NULL);
}
```

## Patch file
See `openbsd-0002-ifa-ifwithaddr-nested-scan.patch`
