java-topology/docs/tickets/istio-0001-virtualhost-domains-linear-scan-rc-patch.md

istio-0001: virtualHostMatch slices.Contains(vh.Domains) O(n) inside VH×patch nested loop → O(n²)

Target: istio/istio Severity: HIGH CWE: CWE-407 (Inefficient Algorithmic Complexity) File: pilot/pkg/networking/core/envoyfilter/rc_patch.go Status: PATCHED

Description

virtualHostMatch() calls slices.Contains(vh.Domains, match.DomainName) to test whether a VirtualHost serves a given domain. This function is called from patchVirtualHost(), which is invoked in a loop over every VirtualHost in a route configuration. For each VirtualHost there is an inner loop over all applicable EnvoyFilter patches. Each slices.Contains call is O(D) where D = number of domains on the VirtualHost. The overall complexity is O(VH × P × D) — cubic in the worst case.

In a large Istio mesh with many services and EnvoyFilter rules, VirtualHosts routinely have dozens of domain aliases (service name, FQDN, short name, wildcard variants). A single xDS push iterates this product for every listener/route-config pair.

Location	Pattern
rc_patch.go:346	slices.Contains(vh.Domains, match.DomainName) — O(D) membership test
rc_patch.go:116	virtualHostMatch(virtualHosts[idx], rp) called per VH per patch
rc_patch.go:79	outer loop: for i := range routeConfiguration.VirtualHosts

Root cause

// rc_patch.go:327 — O(D) per call
func virtualHostMatch(vh *route.VirtualHost, rp *model.EnvoyFilterConfigPatchWrapper) bool {
    match := rp.Match.GetRouteConfiguration().GetVhost()
    if match == nil { return true }
    return (match.Name == "" || match.Name == vh.Name) &&
        (match.DomainName == "" || slices.Contains(vh.Domains, match.DomainName))
}

// rc_patch.go:112 — called in O(VH × P) loop
for i := range routeConfiguration.VirtualHosts {
    ...
    virtualHostMatch(virtualHosts[idx], rp)   // O(D) inside

With 500 VirtualHosts × 20 patches × 15 domains each: 150,000 string comparisons per route-config push.

Fix

Build a map[string]*route.VirtualHost keyed by domain before the patch loop, so each domain lookup is O(1).

// Build domain→VH index once, outside the patch loop
domainIndex := make(map[string]*route.VirtualHost, len(routeConfiguration.VirtualHosts))
for _, vh := range routeConfiguration.VirtualHosts {
    for _, d := range vh.Domains {
        domainIndex[d] = vh
    }
}

// virtualHostMatch: O(1)
func virtualHostMatchFast(vh *route.VirtualHost, rp *model.EnvoyFilterConfigPatchWrapper,
    domainIndex map[string]*route.VirtualHost) bool {
    match := rp.Match.GetRouteConfiguration().GetVhost()
    if match == nil { return true }
    if match.Name != "" && match.Name != vh.Name { return false }
    if match.DomainName == "" { return true }
    return domainIndex[match.DomainName] == vh
}

Ops/ns numbers (Java benchmark)

See defects/istio/unit/IstioTest.java. At VH=500, P=20, D=15: slow ~150,000 ops, fast ~10,000 ops → >10× speedup.