java-topology/defects/httpd/patch/httpd-0004-proxy-route-worker-hashmap.md

UNDF: UNDF-2026-000000420

httpd-0004: find_route_worker redirect chain O(N²) → O(N) with route hash map

Classification

Field	Value
CWE	CWE-407 Inefficient Algorithmic Complexity
Severity	LOW-MEDIUM
Component	modules/proxy/mod_proxy_balancer.c
Function	find_route_worker lines 210–266
Hot path	Per-sticky-session request failover when workers are in error state with redirect
Status	PATCHED (unit test PASS)

Defect

find_route_worker locates a backend worker by route name for sticky-session routing. When a worker is down but has a redirect configured, it recursively calls itself to find the redirect target — scanning all N workers at each recursion level:

// Per request: scan all N workers for route match
for (i = 0; i < balancer->workers->nelts; i++, workers++) {
    if (strcmp(worker->s->route, route) == 0) {
        if (!PROXY_WORKER_IS_USABLE(worker)) {
            if (worker->s->redirect) {
                // Recursive: re-scans all N workers for redirect route
                rworker = find_route_worker(balancer, worker->s->redirect,
                                            r, recursion + 1);
            }
        }
    }
}

Recursion depth is bounded at balancer->workers->nelts (N), but each level re-scans all N workers → O(N²) worst case during worker failover.

At N=100 workers with a full redirect chain: 10,000 worker scans per request vs O(N)=100.

Fix

Build a route → worker* hash table at balancer configuration time (workers are added/removed infrequently, not per-request). Route lookup becomes O(1):

/* At balancer init: apr_hash_t *route_map built once */
for (i = 0; i < balancer->workers->nelts; i++) {
    proxy_worker *w = ...;
    if (w->s->route[0])
        apr_hash_set(route_map, w->s->route, APR_HASH_KEY_STRING, w);
}

/* find_route_worker replacement: O(1) per lookup, O(depth) for chain */
static proxy_worker *find_route_worker(proxy_balancer *balancer,
                                        const char *route, request_rec *r,
                                        int recursion) {
    proxy_worker *worker = apr_hash_get(balancer->route_map,
                                        route, APR_HASH_KEY_STRING);
    if (!worker) return NULL;
    if (PROXY_WORKER_IS_USABLE(worker)) return worker;
    if (worker->s->redirect && recursion < balancer->workers->nelts)
        return find_route_worker(balancer, worker->s->redirect, r, recursion+1);
    return NULL;
}

Speedup

N (workers)	Slow (O(N²))	Fast (O(N))	Ratio
10	100	10	10×
50	2,500	50	50×
100	10,000	100	100×