# UNDF: UNDF-2026-000000414
# haproxy-0003 — flt_spoe.c spoe_check_config O(P×M), O(P×G), O(G×P×M) resolution loops

## Ecosystem
haproxy (C)

## Severity
LOW — config-finalization only, not hot path

## Location
`src/flt_spoe.c` function `spoe_check_config`:

- Line ~2407: `list_for_each_entry(ph, &curmphs)` × `list_for_each_entry(msg, &curmsgs)` — O(P×M)
- Line ~2508: `list_for_each_entry(ph, &curgphs)` × `list_for_each_entry_safe(grp, &curgrps)` — O(P×G)
- Line ~2526: `list_for_each_entry(grp)` × `list_for_each_entry(ph, &grp->phs)` × `list_for_each_entry(msg, &curmsgs)` — O(G×P×M)

## Description
`spoe_check_config` is called after the SPOE config file is parsed to resolve
placeholder references to their corresponding message/group objects. Three
separate nested list-walk patterns are present:

**Pattern 1 — placeholder-to-message resolution (lines ~2407–2504):**
```c
list_for_each_entry(ph, &curmphs, list) {           // outer: P placeholders
    list_for_each_entry(msg, &curmsgs, list) {       // inner: M messages
        if (strcmp(msg->id, ph->id) == 0) {          // O(1) strcmp
            // resolve
            goto next_mph;
        }
    }
    // error: undefined message
}
```
Complexity: O(P × M) where P = message placeholders, M = defined messages.

**Pattern 2 — group-placeholder resolution (lines ~2508–2522):**
```c
list_for_each_entry(ph, &curgphs, list) {                // outer: P group placeholders
    list_for_each_entry_safe(grp, grpback, &curgrps, list) { // inner: G groups
        if (strcmp(grp->id, ph->id) == 0) {                   // O(1) strcmp
            goto next_aph;
        }
    }
}
```
Complexity: O(P × G) where P = group placeholders, G = defined groups.

**Pattern 3 — group message assignment (lines ~2526–2553):**
```c
list_for_each_entry(grp, &curagent->groups, list) {         // outer: G groups
    list_for_each_entry_safe(ph, phback, &grp->phs, list) { // mid: P phs per group
        list_for_each_entry(msg, &curmsgs, list) {           // inner: M messages
            if (strcmp(msg->id, ph->id) == 0) {
                goto next_mph_grp;
            }
        }
        // error: undefined message
    }
}
```
Complexity: O(G × P × M) — cubic in terms of SPOE config size.

Note: `haproxy-0002` covers the duplicate-detection loops at lines ~1580/1604/1991
(while `*args[cur_arg]` + list scan). This defect covers the distinct
config-finalization resolution loops.

## Complexity Table

| Pattern | Complexity | Variables |
|---------|------------|-----------|
| msg placeholder resolution | O(P × M) | P=placeholders, M=messages |
| group placeholder resolution | O(P × G) | P=placeholders, G=groups |
| group-message assignment | O(G × P × M) | cubic |

Typical SPOE configs: M=10–50, G=5–20, P=10–50.
At M=50, G=20, P=50: pattern 3 = 50×50×50 = 125,000 iterations vs ~100 with maps.

## Fix
Build a `struct eb_root` keyed by `id` from `curmsgs` and `curgrps` before
the resolution loops, then replace each inner walk with an `ebst_lookup`:

```c
struct eb_root msgs_by_id = EB_ROOT;
list_for_each_entry(msg, &curmsgs, list) {
    ebst_insert(&msgs_by_id, &msg->by_id_node);  // O(log M)
}

list_for_each_entry(ph, &curmphs, list) {
    msg = ebst_entry(ebst_lookup(&msgs_by_id, ph->id), struct spoe_message, by_id_node);
    if (!msg) { /* error */ goto error; }
    // resolve
}
```

HAProxy already uses `ebst`/`ebmb` extensively throughout the codebase.

## CWE
CWE-407: Inefficient Algorithmic Complexity

## Speedup
Pattern 3 at M=50, G=20, P=50: 125,000 → ~120 lookups (O(log M) each) ≈ 1000x.

## Status
PATCHED (patch in this file)
