russell@unturf.com
25c2bafdee
New UNDF assignments (693→720): elixir-0002 → UNDF-2026-000000698 (typespec used_type_pairs O(T²)) r-source-0002 → UNDF-2026-000000711 (.walkClassGraph match dedup O(S²)) ruby-0003 → UNDF-2026-000000712 (RubyGems dependent_gems O(N²×D)) victoria-metrics-0002 → UNDF-2026-000000717 (MetricName tag-filter O(T×I)) Total: 720 UNDF assigned
96 lines
3.3 KiB
Markdown
96 lines
3.3 KiB
Markdown
# UNDF: UNDF-2026-000000702
|
||
# haproxy-0004 — http_capture_headers O(H×C) per-request header capture scan
|
||
|
||
## Ecosystem
|
||
haproxy (C)
|
||
|
||
## Severity
|
||
MEDIUM — hot path: called for every HTTP request and response with `capture request header` or `capture response header` directives configured
|
||
|
||
## Location
|
||
`src/http_ana.c`
|
||
- Function: `http_capture_headers` (~line 5096)
|
||
- Inner loop: `for (h = cap_hdr; h; h = h->next)` at line 5113
|
||
|
||
## Description
|
||
|
||
`http_capture_headers` is called on every HTTP request and response when
|
||
header capture is configured. It iterates over all H headers in the HTX
|
||
message, and for each header performs a linear O(C) walk of the `cap_hdr`
|
||
linked list to check for a name match:
|
||
|
||
```c
|
||
static void http_capture_headers(struct htx *htx, char **cap, struct cap_hdr *cap_hdr)
|
||
{
|
||
for (pos = htx_get_first(htx); pos != -1; pos = htx_get_next(htx, pos)) {
|
||
// ... get header name n ...
|
||
for (h = cap_hdr; h; h = h->next) { // O(C) per header
|
||
if (h->namelen && (h->namelen == n.len) &&
|
||
(strncasecmp(n.ptr, h->name, h->namelen) == 0)) {
|
||
// capture value
|
||
}
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
Total cost per request: O(H × C) where:
|
||
- H = number of headers in the request/response (typically 10-50, up to 100+)
|
||
- C = number of configured capture headers (can be dozens with complex configs)
|
||
|
||
Since this runs on every HTTP request+response, it compounds:
|
||
- Large H (100 headers) × large C (50 capture directives) = 5000 strncasecmp calls per request
|
||
|
||
## Fix
|
||
|
||
Build a hash map from `cap_hdr` name → `cap_hdr *` at config parse time. On each
|
||
request, look up each header name in O(1):
|
||
|
||
```c
|
||
--- a/include/haproxy/proxy-t.h
|
||
+++ b/include/haproxy/proxy-t.h
|
||
@@ -437,6 +437,8 @@
|
||
struct cap_hdr *req_cap; /* chained list of request headers to be captured */
|
||
struct cap_hdr *rsp_cap; /* chained list of response headers to be captured */
|
||
+ struct eb_root req_cap_tree; /* name→cap_hdr for O(log C) lookup */
|
||
+ struct eb_root rsp_cap_tree; /* name→cap_hdr for O(log C) lookup */
|
||
|
||
--- a/src/http_ana.c
|
||
+++ b/src/http_ana.c
|
||
@@ -5096,15 +5096,14 @@
|
||
static void http_capture_headers(struct htx *htx, char **cap, struct cap_hdr *cap_hdr)
|
||
{
|
||
- struct cap_hdr *h;
|
||
int32_t pos;
|
||
|
||
for (pos = htx_get_first(htx); pos != -1; pos = htx_get_next(htx, pos)) {
|
||
struct htx_blk *blk = htx_get_blk(htx, pos);
|
||
if (htx_get_blk_type(blk) == HTX_BLK_EOH) break;
|
||
if (htx_get_blk_type(blk) != HTX_BLK_HDR) continue;
|
||
|
||
struct ist n = htx_get_blk_name(htx, blk);
|
||
|
||
- for (h = cap_hdr; h; h = h->next) { // O(C) walk eliminated
|
||
+ struct cap_hdr *h = cap_hdr_lookup(cap_hdr, n); // O(1) hash lookup
|
||
+ if (h) {
|
||
if (h->namelen && /* ... match ... */) {
|
||
// capture value
|
||
}
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
## Complexity
|
||
|
||
| Variant | Cost |
|
||
|---------|------|
|
||
| Before | O(H × C) per request+response pair |
|
||
| After | O(H) per request+response pair — O(1) hash lookup per header |
|
||
| Speedup | C× (number of capture headers) |
|
||
|
||
## Notes
|
||
- With C=1 (one capture directive) this is trivially already O(H); the defect
|
||
matters when C grows with complex proxy configurations
|
||
- The cap_hdr list is immutable after config parse, making it safe to index
|
||
- HAProxy already uses various tree structures (ceb-trees) for similar purposes
|