# UNDF: UNDF-2026-000000695
# curl-0004 — curl_mime multipart header search O(P×H) per request build

## Ecosystem
curl (C)

## Severity
LOW-MEDIUM — affects multipart POST requests; `mime_add_headers` is called
once per MIME part during request construction; scales with P (parts) × H
(user headers per part)

## Location
`lib/mime.c`
- `search_header(struct curl_slist *hdrlist, ...)` (~line 252): O(H) linear scan
- `mime_add_headers` / `Curl_mime_add_header` (~line 1696, 1730, 1777):
  calls `search_header` 3 times per part during request construction

## Description

When building a multipart POST request, `mime_add_headers` checks whether the
user has already provided `Content-Type`, `Content-Disposition`, and
`Content-Transfer-Encoding` headers by calling `search_header` on the user's
header list `part->userheaders`:

```c
// mime.c:252
static char *search_header(struct curl_slist *hdrlist,
                            const char *hdr, size_t len)
{
  char *value = NULL;
  for(; !value && hdrlist; hdrlist = hdrlist->next)   // O(H) scan
    value = match_header(hdrlist, hdr, len);
  return value;
}
```

Called during request construction:
```c
// mime.c:1696 — check Content-Type
customct = search_header(part->userheaders, STRCONST("Content-Type"));

// mime.c:1730 — check Content-Disposition
if(!search_header(part->userheaders, STRCONST("Content-Disposition"))) { ... }

// mime.c:1777 — check Content-Transfer-Encoding
if(!search_header(part->userheaders, ...)) { ... }
```

For a multipart request with P parts each having H user headers, the cost
per request construction is O(P × H × 3) = O(P × H).

With P=100 parts × H=20 custom headers per part = 6000 header comparisons
per request build. The `curl_slist` is a singly-linked list so there is no
O(1) name lookup.

## Fix

Pre-index per-part user headers into an `unordered_set` or `unordered_map`
keyed by header name (case-insensitive). Built once when the part's header
list is finalized, looked up O(1):

```c
--- a/lib/mime.h
+++ b/lib/mime.h
@@ struct curl_mimepart {
    struct curl_slist *userheaders;      /* list of user-set headers */
+   /* O(1) header name presence check, built lazily in mime_add_headers */
+   /* For C, use a small sorted array or hash table of header names */

--- a/lib/mime.c
+++ b/lib/mime.c
-  customct = search_header(part->userheaders, STRCONST("Content-Type"));
-  if(!search_header(part->userheaders, STRCONST("Content-Disposition"))) ...
-  if(!search_header(part->userheaders, STRCONST("Content-Transfer-Encoding"))) ...

+  /* Build set once if not already cached */
+  struct header_set *hset = build_header_set(part->userheaders);
+  customct = header_set_find(hset, "Content-Type");
+  if(!header_set_contains(hset, "Content-Disposition")) ...
+  if(!header_set_contains(hset, "Content-Transfer-Encoding")) ...
```

## Complexity

| Variant | Cost per part | Total for P parts, H headers |
|---------|--------------|------------------------------|
| Before  | O(H × 3)    | O(P × H)                     |
| After   | O(1 × 3)    | O(P + H) for set build       |
| Speedup | H× per part  |                              |

## Notes
- The defect is only measurable for large multipart uploads with many
  user-supplied headers per part (e.g., upload pipelines, multipart forms
  with per-field metadata)
- For typical use (1-5 headers per part), H is small and the impact is minimal
- `part->userheaders` is set once via `curl_mime_headers()` before the first
  request; the cache can be built on first use and invalidated on modification
- curl-0002 covers the similar `Curl_checkheaders` pattern for request-level
  headers; this defect is the MIME-part-level equivalent
