UNDF: UNDF-2026-000000104

UNDF: (pending)

helm-0001: ResourceList.Contains/Difference/Intersect — O(N²) linear scan

CWE-407 — Algorithmic Complexity

Field	Value
ID	helm-0001
Severity	MEDIUM
Ecosystem	helm
Package	pkg/kube
File	`pkg/kube/resource.go`
Lines	61–79
Complexity	O(N²) — Difference/Intersect each call Contains O(N) per element
Hot path	`helm upgrade` resource reconciliation — deletes resources not in new manifest

Defect

ResourceList.Contains() is a linear scan over all resources:

func (r ResourceList) Contains(info *resource.Info) bool {
    for _, i := range r {
        if isMatchingInfo(i, info) {
            return true
        }
    }
    return false
}

Difference and Intersect call Contains inside a Filter loop, which iterates over the full list:

func (r ResourceList) Difference(rs ResourceList) ResourceList {
    return r.Filter(func(info *resource.Info) bool {
        return !rs.Contains(info)   // O(|rs|) per element of r
    })
}

func (r ResourceList) Intersect(rs ResourceList) ResourceList {
    return r.Filter(rs.Contains)   // O(|rs|) per element of r
}

Filter iterates over r:

func (r ResourceList) Filter(fn func(*resource.Info) bool) ResourceList {
    var result ResourceList
    for _, v := range r {
        if fn(v) {
            result = append(result, v)
        }
    }
    return result
}

At helm upgrade time, client.go:648 calls originals.Difference(targets) to find resources to delete. With N=200 resources, this costs 200×200 = 40,000 equality checks instead of 200 map lookups.

isMatchingInfo compares Name+Namespace+Group+Kind — uniquely identifies a resource, making it suitable as a map key.

Fix

Build an index set from rs before filtering:

// resourceKey returns a unique string key for a resource.Info.
func resourceKey(info *resource.Info) string {
    return fmt.Sprintf("%s/%s/%s/%s",
        info.Mapping.GroupVersionKind.Group,
        info.Mapping.GroupVersionKind.Kind,
        info.Namespace,
        info.Name,
    )
}

func (r ResourceList) Contains(info *resource.Info) bool {
    for _, i := range r {
        if isMatchingInfo(i, info) {
            return true
        }
    }
    return false
}

// Difference returns resources in r not in rs. O(|r| + |rs|) with index.
func (r ResourceList) Difference(rs ResourceList) ResourceList {
    index := make(map[string]struct{}, len(rs))
    for _, i := range rs {
        index[resourceKey(i)] = struct{}{}
    }
    return r.Filter(func(info *resource.Info) bool {
        _, found := index[resourceKey(info)]
        return !found
    })
}

// Intersect returns resources in both r and rs. O(|r| + |rs|) with index.
func (r ResourceList) Intersect(rs ResourceList) ResourceList {
    index := make(map[string]struct{}, len(rs))
    for _, i := range rs {
        index[resourceKey(i)] = struct{}{}
    }
    return r.Filter(func(info *resource.Info) bool {
        _, found := index[resourceKey(info)]
        return found
    })
}

Speedup

N (resources)	Before (ops)	After (ops)	Speedup
50	2,500	100	25×
200	40,000	400	100×
500	250,000	1,000	250×

3.2 KiB Raw Permalink Blame History Unescape Escape