# UNDF: UNDF-2026-000000444
# kubernetes-0005: Scheduler TaintToleration Score — O(N×T×L) quadratic toleration scan per scheduling cycle

**Severity:** HIGH
**CWE:** CWE-407 (Algorithmic Complexity — linear membership test inside a loop, called per node per pod)
**Speedup:** ~L× where L = toleration count per pod (scales with node count N and taint count T)
**Target:** Kubernetes (kubernetes/kubernetes)
**Files:**
- `pkg/scheduler/framework/plugins/tainttoleration/taint_toleration.go:180` — `countIntolerableTaintsPreferNoSchedule`
- `k8s.io/component-helpers/scheduling/corev1/helpers.go:78` — `TolerationsTolerateTaint` (inner linear scan)

## Description

The `TaintToleration` scheduler plugin's `Score` extension point calls
`countIntolerableTaintsPreferNoSchedule` for every candidate node in the
scheduling cycle. This function iterates over a node's taints and for each taint
calls `TolerationsTolerateTaint`, which linearly scans all pod tolerations:

```go
// taint_toleration.go:180
func (pl *TaintToleration) countIntolerableTaintsPreferNoSchedule(
    logger klog.Logger, taints []v1.Taint, tolerations []v1.Toleration) (intolerableTaints int) {
    for _, taint := range taints {                   // O(T) — taints on node
        if taint.Effect != v1.TaintEffectPreferNoSchedule {
            continue
        }
        if !v1helper.TolerationsTolerateTaint(logger, tolerations, &taint, ...) {
            intolerableTaints++
        }
    }
    return
}

// component-helpers/scheduling/corev1/helpers.go:78
func TolerationsTolerateTaint(logger klog.Logger, tolerations []v1.Toleration, taint *v1.Taint, ...) bool {
    for i := range tolerations {                     // O(L) — tolerations per pod
        if tolerations[i].ToleratesTaint(logger, taint, ...) {
            return true
        }
    }
    return false
}
```

Called from `Score`:
```go
// taint_toleration.go:205
score := int64(pl.countIntolerableTaintsPreferNoSchedule(logger, node.Spec.Taints, s.tolerationsPreferNoSchedule))
```

`Score` is invoked once per candidate node per pod scheduling cycle. With N nodes,
T taints per node, and L pod tolerations:

- **Current**: O(N × T × L) per scheduling cycle
- **Fixed**: O(L) once in PreScore to build a toleration key set; O(T) per node in Score for O(N × T) total

## Root Cause

`TolerationsTolerateTaint` performs a linear scan of all tolerations for each
taint lookup. The pod's `tolerationsPreferNoSchedule` is static throughout the
scoring phase (computed once in `PreScore`) but its effective set membership is
re-computed via linear scan for every taint on every node.

The fix is to build a map of `(key, effect)` toleration keys once in `PreScore`,
then do O(1) lookup per taint in `countIntolerableTaintsPreferNoSchedule`.
Wildcard tolerations (empty Key) require a flag indicating their presence.

## Complexity Before

`Score` per pod: **O(N × T × L)** — N nodes × T taints per node × L tolerations per pod.
For a 5,000-node cluster with T=5 taints and L=20 tolerations: 500,000 string comparisons per pod scheduling.

## Complexity After

**O(L + N × T)** — O(L) map build in PreScore + O(T) map lookup per node in Score.
For the same cluster: 25,000 operations per pod scheduling — 20× reduction.

## Patch

In `PreScore`, extend `preScoreState` to include a map of toleration keys built
from `tolerationsPreferNoSchedule`. In `countIntolerableTaintsPreferNoSchedule`,
use the map for O(1) toleration lookup instead of calling `TolerationsTolerateTaint`.

```go
// Extended preScoreState
type preScoreState struct {
    tolerationsPreferNoSchedule []v1.Toleration
    tolerationKeySet            map[string]v1.TolerationOperator // key → Exists/Equal, empty key = wildcard
    hasWildcardToleration       bool
}

// In PreScore:
func buildTolerationKeySet(tolerations []v1.Toleration) (map[string]v1.TolerationOperator, bool) {
    m := make(map[string]v1.TolerationOperator, len(tolerations))
    hasWildcard := false
    for _, t := range tolerations {
        if t.Key == "" {
            hasWildcard = true
        } else {
            m[t.Key+"/"+string(t.Effect)] = t.Operator
            m[t.Key+"/"] = t.Operator // effect-less toleration covers all effects
        }
    }
    return m, hasWildcard
}
```

## Reproduction

```
cd defects/kubernetes/unit && javac -d . *.java && java -ea unit.KubernetesTest
```
