# UNDF: UNDF-2026-000000707
# nginx-0004 — ngx_http_upstream_keepalive: O(C) linear cache scan per upstream request

## Ecosystem
nginx (C)

## Severity
MEDIUM — hot path: executed on every upstream request that can reuse a
keepalive connection; scales with `keepalive` directive value

## Location
`src/http/modules/ngx_http_upstream_keepalive_module.c`
- Function: `ngx_http_upstream_keepalive_get_peer` (~line 212)
- Inner loop: `for (q = ngx_queue_head(cache); q != ngx_queue_sentinel(cache); ...)` (~line 229)

## Description

When an upstream request needs a connection, `ngx_http_upstream_keepalive_get_peer`
scans the entire keepalive cache queue to find a cached connection matching
the upstream's `sockaddr`:

```c
/* search cache for suitable connection */
cache = &kp->conf->cache;

for (q = ngx_queue_head(cache);
     q != ngx_queue_sentinel(cache);
     q = ngx_queue_next(q))                          // O(C) scan
{
    item = ngx_queue_data(q, ngx_http_upstream_keepalive_cache_t, queue);
    c = item->connection;

    if (ngx_memn2cmp((u_char *) &item->sockaddr, (u_char *) pc->sockaddr,
                     item->socklen, pc->socklen) == 0)
    {
        ngx_queue_remove(q);
        goto found;
    }
}
```

With `keepalive N` set to a large value (e.g., `keepalive 1000` or `keepalive 10000`
for backends with many servers), this scan processes up to N entries on every upstream
request. Under high throughput, this O(C) scan becomes a bottleneck:

- 10,000 RPS × C=1000 keepalive cache entries = 10 million comparisons/second
  just for connection reuse lookups

## Fix

Index the keepalive cache by sockaddr using a hash table keyed on the
(family, addr, port) tuple, giving O(1) lookup per upstream request:

```c
--- a/src/http/modules/ngx_http_upstream_keepalive_module.c
+++ b/src/http/modules/ngx_http_upstream_keepalive_module.c
@@ struct ngx_http_upstream_keepalive_srv_conf_s {
    ngx_queue_t              cache;      /* LRU queue of cached connections */
    ngx_queue_t              free;       /* free items */
+   ngx_hash_t               cache_hash; /* sockaddr → cached items list */

-  /* search cache for suitable connection */
-  for (q = ngx_queue_head(cache);
-       q != ngx_queue_sentinel(cache);
-       q = ngx_queue_next(q))
-  {
-      item = ngx_queue_data(q, ...);
-      if (ngx_memn2cmp(&item->sockaddr, pc->sockaddr, ...) == 0)
-          goto found;
-  }
+  /* O(1) hash lookup by sockaddr */
+  ngx_http_upstream_keepalive_cache_t *item =
+      ngx_hash_find(&kp->conf->cache_hash,
+                    ngx_crc32_long(pc->sockaddr->sa_data, pc->socklen),
+                    pc->sockaddr, pc->socklen);
+  if (item) goto found;
```

## Complexity

| Variant | Cost per upstream connection attempt |
|---------|-------------------------------------|
| Before  | O(C) — full scan of keepalive cache |
| After   | O(1) — hash map lookup              |
| Speedup | C× (keepalive pool size)             |

## Notes
- Default `keepalive` is typically 32-100 for simple setups; some deployments
  use 1000+ for microservice backends with many upstream servers
- nginx's existing LRU queue serves eviction; the hash provides fast lookup
- Multiple cached connections to the same server are valid; the hash can
  return a head-of-list and then remove from the LRU queue
- `ngx_queue_insert_head(&kp->conf->free, q)` after successful lookup
  must also update the hash
