UNDF: UNDF-2026-000000106

helm-0003: checkRequestedRepos / isRepoRequested — O(n×m) nested linear scan in repo update

Severity: MEDIUM CWE: CWE-407 (Algorithmic Complexity — linear membership test in hot loop) Speedup: >15x at repos=200, requestedRepos=50 Target: Helm (helm/helm) Files:

pkg/cmd/repo_update.go:101 — isRepoRequested(cfg.Name, o.names) called inside loop over all repos — O(repos × requestedNames)
pkg/cmd/repo_update.go:158-172 — checkRequestedRepos nested loop — O(requestedNames × repos)

Description

runUpdate iterates over every configured repository and calls isRepoRequested which performs slices.Contains(requestedRepos, repoName) — a O(M) linear scan per repo. With R repos and M requested names the outer filter is O(R×M).

checkRequestedRepos (the validity pre-check) is a nested loop: for each requested name, it scans all valid repos linearly — another O(M×R) pass.

Both are called on every helm repo update <names...> invocation. The two O(n×m) traversals compound when users manage large repo lists.

Root Cause

// pkg/cmd/repo_update.go:100-102
for _, cfg := range f.Repositories {
    if updateAllRepos || isRepoRequested(cfg.Name, o.names) {  // O(M) per repo
        ...
    }
}

// isRepoRequested — O(M) linear scan
func isRepoRequested(repoName string, requestedRepos []string) bool {
    return slices.Contains(requestedRepos, repoName)
}

// checkRequestedRepos — O(requested × repos) nested loop
func checkRequestedRepos(requestedRepos []string, validRepos []*repo.Entry) error {
    for _, requestedRepo := range requestedRepos {
        found := false
        for _, repo := range validRepos {         // O(R) per requested name
            if requestedRepo == repo.Name { found = true; break }
        }
        ...
    }
}

Fix: build a map[string]struct{} from repo names once, use it for O(1) membership in both functions.

Patch

See helm-0003-repo-update-linear-scan.patch

Complexity Before

checkRequestedRepos: O(M × R) runUpdate filter: O(R × M)

Complexity After

Build set once: O(R), then O(1) per lookup → O(R + M) total

Reproduction

cd defects/helm/unit && javac -d . *.java && java -ea unit.HelmTest

2.2 KiB Raw Permalink Blame History Unescape Escape