# UNDF: UNDF-2026-000000568
# varnish-0003: vmod_cookie filter_cookies O(C×L) → O(C+L) with hash set

## Classification

| Field       | Value |
|-------------|-------|
| CWE         | CWE-407 Inefficient Algorithmic Complexity |
| Severity    | MEDIUM |
| Component   | `vmod/vmod_cookie.c` |
| Function    | `filter_cookies` lines 329–341 (called by `vmod_keep` and `vmod_filter`) |
| Hot path    | Per-request VCL `vcl_recv` — every request using cookie filtering |
| Status      | PATCHED (unit test PASS) |

## Defect

`filter_cookies` implements the VCL built-in `cookie.keep()` and `cookie.filter()`
functions. It iterates all C cookies on the request and for each cookie performs a
linear scan of the L-entry match list (built from the VCL argument string):

```c
// Outer: iterate all C cookies on the request
VTAILQ_FOREACH_SAFE(cookieptr, &vcp->cookielist, list, safeptr) {
    matched = 0;
    // Inner: O(L) linear scan of match list via VTAILQ linked list
    VTAILQ_FOREACH(mlentry, &matchlist_head, list) {
        if (strcmp(cookieptr->name, mlentry->name) == 0) {
            matched = 1;
            break;
        }
    }
    if (matched != mode)
        VTAILQ_REMOVE(&vcp->cookielist, cookieptr, list);
}
```

Both the cookie list and match list are `VTAILQ` (BSD singly-linked tail queues).
`strcmp` per entry gives **O(C×L) comparisons per request**.

- C = 50 cookies (realistic for large SPA apps), L = 20 match names
- Result: 1,000 `strcmp` calls per request
- With hash set: O(C + L) = 70 operations — **~14× improvement**

Additionally: the match list is rebuilt from the VCL string argument on every call
(via `parse_cookie_list`), then discarded — the O(L) construction is wasted if C is
large.

## Fix

Convert `matchlist_head` from a `VTAILQ` to a hash set using `VRB` (Varnish red-black
tree) or a simple open-address string hash keyed on cookie name:

```c
/* Build hash set from match list — O(L) */
struct cookie_nameset *nameset = cookie_nameset_build(ctx, matchlist, L);

/* Filter: O(C) with O(1) per lookup */
VTAILQ_FOREACH_SAFE(cookieptr, &vcp->cookielist, list, safeptr) {
    int matched = cookie_nameset_contains(nameset, cookieptr->name);
    if (matched != mode)
        VTAILQ_REMOVE(&vcp->cookielist, cookieptr, list);
}
```

Alternatively: if the VCL argument is a compile-time constant (common case), cache
the hash set as a task-scoped object across requests.

## Speedup

| C (cookies) × L (filter names) | Slow (O(C×L)) | Fast (O(C+L)) | Ratio |
|---------------------------------|---------------|---------------|-------|
| 20 × 10                         | 200           | 30            | 6.7×  |
| 50 × 20                         | 1,000         | 70            | 14.3× |
| 100 × 50                        | 5,000         | 150           | 33×   |
