# UNDF: UNDF-2026-000000445
# kubernetes-0006: tainteviction handleNodeUpdate — O(P×T×L) GetMatchingTolerations on every node taint change

**Severity:** HIGH
**CWE:** CWE-407 (Algorithmic Complexity — O(T×L) nested linear scan called once per pod per node-taint event)
**Speedup:** ~L× where L = average toleration count per pod
**Target:** Kubernetes (kubernetes/kubernetes)
**Files:**
- `pkg/controller/tainteviction/taint_eviction.go:533` — `handleNodeUpdate`: pod loop calling `processPodOnNode`
- `pkg/controller/tainteviction/taint_eviction.go:463` — `processPodOnNode`: calls `GetMatchingTolerations`
- `pkg/apis/core/v1/helper/helpers.go:280` — `GetMatchingTolerations`: O(T×L) nested loop

## Description

`handleNodeUpdate` is invoked whenever a node's taint set changes (node becomes
NotReady, Unreachable, or a custom NoExecute taint is added/removed). It fetches
all pods assigned to the node and for each pod calls `processPodOnNode`, which
calls `GetMatchingTolerations(taints, pod.Spec.Tolerations)`:

```go
// taint_eviction.go:533
func (tc *Controller) handleNodeUpdate(ctx context.Context, nodeUpdate nodeUpdateItem) {
    // ...
    pods, err := tc.getPodsAssignedToNode(node.Name)
    // ...
    for _, pod := range pods {                              // O(P) — pods on node
        tc.processPodOnNode(ctx, ..., pod.Spec.Tolerations, taints, now)
    }
}

// taint_eviction.go:463
func (tc *Controller) processPodOnNode(..., tolerations []v1.Toleration, taints []v1.Taint, ...) {
    allTolerated, usedTolerations := v1helper.GetMatchingTolerations(logger, taints, tolerations)
    // ...
}

// pkg/apis/core/v1/helper/helpers.go:280
func GetMatchingTolerations(logger klog.Logger, taints []v1.Taint, tolerations []v1.Toleration) (bool, []v1.Toleration) {
    // ...
    for i := range taints {                                 // O(T) — NoExecute taints
        tolerated := false
        for j := range tolerations {                        // O(L) — toleration scan per taint
            if tolerations[j].ToleratesTaint(logger, &taints[i], ...) {
                result = append(result, tolerations[j])
                tolerated = true
                break
            }
        }
        if !tolerated {
            return false, []v1.Toleration{}
        }
    }
    return true, result
}
```

For a node with P pods, T NoExecute taints, and L tolerations per pod:

- **Current**: O(P × T × L) per `handleNodeUpdate` call
- **Fixed**: O(T × L) with per-taint toleration index built once per node-taint-set, O(1) per pod per taint

## Root Cause

The node's taint set (`taints`) is fixed for the entire `handleNodeUpdate` call —
it does not change between pod iterations. However, `GetMatchingTolerations`
rebuilds the toleration-matching logic from scratch for every pod.

The taints are small (typically 1–3 NoExecute taints). For each taint, an O(1)
lookup into a per-pod toleration map would reduce the inner O(L) loop to O(1).

Better: build a `map[string]v1.Toleration` indexed by taint key+effect for each
pod once and then do O(T) lookups per pod. With T taints constant across all P
pods, this reduces from O(P×T×L) to O(P×(T+L)) = O(P×L) build + O(P×T) lookup.

## Complexity Before

Per `handleNodeUpdate`: **O(P × T × L)** — for a node with 110 pods (default
`--max-pods`), 2 NoExecute taints, and 10 tolerations per pod: 2,200 string
comparisons on every node health state change.

For a large cluster where a zone fails and 1,000 nodes go NotReady simultaneously,
the controller processes 110,000 pods × 20 comparisons = 2.2M comparisons in a
single control-plane event burst.

## Complexity After

**O(P × (T + L))** — toleration map built once per pod (O(L)), then O(T) map
lookups per pod for O(P×T) total matching work.

## Patch

In `processPodOnNode`, pre-index pod tolerations into a map before the taint loop:

```go
// Pre-index tolerations by (key, effect) and (key, "") for all-effect tolerations
func indexTolerations(tolerations []v1.Toleration) (map[string]v1.Toleration, bool) {
    m := make(map[string]v1.Toleration, len(tolerations))
    hasWildcard := false
    for _, t := range tolerations {
        if t.Key == "" {
            hasWildcard = true
            continue
        }
        effectKey := t.Key + "/" + string(t.Effect)
        if _, exists := m[effectKey]; !exists {
            m[effectKey] = t
        }
        emptyKey := t.Key + "/"
        if _, exists := m[emptyKey]; !exists {
            m[emptyKey] = t
        }
    }
    return m, hasWildcard
}
```

Then in `GetMatchingTolerations` or `processPodOnNode`, use the indexed map for
O(1) taint→toleration lookups instead of iterating all tolerations per taint.

## Reproduction

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