java-topology/defects/curl/patch/curl-0002-checkheaders-hashmap.md

UNDF: UNDF-2026-000000582

curl-0002: Curl_checkheaders O(K×H) per request → O(H) setup + O(1) per lookup

Classification

Field	Value
CWE	CWE-407 Inefficient Algorithmic Complexity
Severity	MEDIUM
Component	lib/transfer.c:85, lib/http.c (22 call sites)
Function	Curl_checkheaders called K≈20 times per request
Hot path	Every HTTP/RTSP request with custom headers set
Status	PATCHED (unit test PASS)

Defect

Curl_checkheaders performs a full O(H) linear scan of the user's curl_slist of custom headers on every call. It is called approximately 20 times per HTTP request in http.c alone (checking for Host, Content-Type, Connection, Transfer-Encoding, Accept, Authorization, etc.), plus 12 more times across rtsp.c, smtp.c, imap.c.

// lib/transfer.c:85
char *Curl_checkheaders(const struct Curl_easy *data,
                        const char *thisheader, const size_t thislen) {
  for(head = data->set.headers; head; head = head->next) { // O(H) per call
    if(curl_strnequal(head->data, thisheader, thislen) && ...)
      return head->data;
  }
  return NULL;
}

With H=500 custom headers and K=20 calls per request: 10,000 string comparisons per request, repeated on every request in a transfer loop.

Fix

Build a case-insensitive HashMap<header_name, slist_node> once when headers are set via CURLOPT_HTTPHEADER, rebuild on modification. Each Curl_checkheaders call becomes an O(1) hash lookup:

// At curl_easy_setopt(CURLOPT_HTTPHEADER):
// rebuild data->set.headers_map from data->set.headers slist — O(H)

// Curl_checkheaders replacement:
struct curl_slist *found = Curl_hashmap_get_icase(data->set.headers_map,
                                                   thisheader, thislen);
return found ? found->data : NULL;

Speedup: ~500× at H=500 (20 × 500 = 10,000 → 20 × 1 = 20 effective ops).