74 lines
2.8 KiB
Markdown
74 lines
2.8 KiB
Markdown
# 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:
|
||
|
||
```c
|
||
// 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):
|
||
|
||
```c
|
||
/* 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× |
|