policy: Pre-parse cached selectors, index by namespace by jrajahalme · Pull Request #42008 · cilium/cilium

jrajahalme · 2025-10-03T13:43:10Z

Parse selector requirement keys into labels when inserting into selector cache. Previously the labels of each existing cached selector (and netip.Prefix for a CIDR selector) were re-parsed and re-allocated on each match operation, used when new selectors or identities are added to the selector cache. This was essentially an O(n^2) operation on policy ingestion and identity updates.

Index cached selectors and identities by namespace so that it is possible to avoid futile matches rather than making the match operation itself fail early for a non-matching namespace. This speeds up namespaced policy ingestion and identity updates.

These changes make CIDR policy resolution in the new BenchmarkResolveCIDRPolicyRules ~4x faster, using 90% less memory and 96% less allocations.

marseel · 2025-10-03T14:15:05Z

/scale-100

jrajahalme · 2025-10-03T14:21:49Z

/test

jrajahalme · 2025-10-07T12:46:54Z

/test

pkg/labels/array.go

pkg/policy/selectorcache_selector.go

pkg/policy/selectorcache.go

squeed · 2025-10-08T15:56:26Z

(note: I see at least one "wip" commit message)

jrajahalme · 2025-10-14T07:54:01Z

(note: I see at least one "wip" commit message)

Was a commit squash artefact, will fix :-)

jrajahalme · 2025-10-14T09:41:09Z

/test

pkg/policy/selectorcache.go

jrajahalme · 2025-10-14T12:08:16Z

/test

jrajahalme · 2025-10-15T06:45:30Z

/test

Use world label in CIDR selectors instead of a zero-length prefixes. Thus a CIDR "0.0.0.0/0" selector will translate to a "reserved:world" selector (in an IPv6 disabled configuration). This makes it possible to remove the addition of world selectors when wildcard selectors are added. Do not add extra selectors with "reserved:world" label requirement (or dual-stack equivalents) when a CIDR selecting all IPv4 or IPv6 addresses is ingested. Adding the extra world label selector will no longer expand the set of selected identities, since the world selector has already been used instead of a zero-length CIDR selector. The removed logic was also partially based on string matching on forms that would not match for selectors with a CIDR "1.1.1.1/0" for example, even though the resulting CIDR selector would be the same ("cidr.0.0.0.0/0"). This change allows CIDR selector parsing to internal representation to be simplified, as each CIDR selector will map to exactly one internal EndpointSelector. Signed-off-by: Jarno Rajahalme <[email protected]>

Add a new LabelMatcher interface with a sole LookupLabel function that uses a pre-parsed *Label as an argument. Implement it in Labels, LabelArray, and in a new K8sSet, that can be used to cast bare sting maps to a LabelMatcher. Use iteration index into LabelArray rather than using a temporary Label. This makes a diffence due to LookupLabel used in some inner loops in policy selector matching. Signed-off-by: Jarno Rajahalme <[email protected]>

Use the cached string and requirements with pre-parsed labels instead of api.EndpointSelector in labelIdentitySelector. labels.LabelArray is changed to add HasLabel(), GetLabel() and LookupLabel() functions that take a pre-parsed Label as an argument instead of a string. This makes CIDR policy resolution in BenchmarkResolveCIDRPolicyRules 70% faster, with 90% less memory used and 95% less allocations. Signed-off-by: Jarno Rajahalme <[email protected]>

Consider selector possibly selecting any namespace if the selector requirement has any operator than "In", "Equals", or "DoubleEquals". For example, if the requirement is "NotIn", then any namespace *not in* the values would be selected. In this kind of cases we skip namespace filtering and perform a full match. Signed-off-by: Jarno Rajahalme <[email protected]>

Store the fqdn identity label into `fqdnSelector` so that it does not need to be re-created on every match operation. Signed-off-by: Jarno Rajahalme <[email protected]>

Refactor scIdentityCache to a struct. Keep scIdentities in a map via a pointer so that it is possible to point to them via a secondary index to be added in the next commit. Signed-off-by: Jarno Rajahalme <[email protected]>

Add a namespace index to identities so that ones with non-matching identities can be trivially skipped when adding or removing selectors to/from the selector cache. Signed-off-by: Jarno Rajahalme <[email protected]>

Index cached selectors by namespace so that ones with non-matching namespaces can be trivially skipped when adding or deleting identities. Signed-off-by: Jarno Rajahalme <[email protected]>

Signed-off-by: Jarno Rajahalme <[email protected]>

jrajahalme · 2025-11-22T10:52:49Z

Removed part.Map change (last commit), as it triggered consistent ci-ingress failure. Will investigate and post as a separate PR.

jrajahalme · 2025-11-23T10:37:30Z

/test

sayboras

Looks good for cilium/proxy related files

joamaki

sig-k8s & sig-lb LGTM

pkg/policy/types/requirements.go

pkg/policy/types/selector.go

jrajahalme · 2025-12-01T18:44:58Z

/test

Keep pre-computed Requirements only in Selector implementations in pkg/policy/types. Use these in places where EndpointSelector was used for matching in production code previously. This simplifies policy/api code, and keeps the faster matching in one place (policy/types.Selector implementations). These same Selectors are now also used internally in SelectorCache for updating the cached selections. Note that the matching interface of api.EndpointSelector has been moved to unit test code. Due to dependency cycle avoidance the unit test matching logic in policy/api can not use the new matching logic in policy/types. For selector matching in production code, create a types.LabelSelector from api.EndpointSelector and use that for matching. Note that for this to work the api.EndpointSelector MUST HAVE the key prefixed with a label source (e.g., "k8s."), otherwise any dot separated prefix will be parsed as the label's source and removed from the label key! API selector types now all have a SelectorKey() method, used for getting a key string before a new Selectors are created from them. This method should be fast, and api.EndpointSelector keeps the internal cachedLabelSelectorString member for this purpose. This cached string is still updated after each modification to api.EndpointSelector. PeerSelector interface used to be a "marker" interface with IsPeerSelector() function that did nothing. Since we added another function (SelectorKey()) to the interface, it is not a pure marker anymore, and IsPeerSelector() function is no longer needed, so remove it. Since also subject selectors can be cached in selector cache, rename PeerSelector interface as APISelector, as it must be implemented by all policy.api types that can be used as types.Selectors. Stop hauling logger to selector matching functions, as they use validated inputs and should never fail. To help avoid breaking this invariant, use logging.DefaultSlogLogger as a "soft panic" to fail Cilium CI if these are hit during CI runs. Signed-off-by: Jarno Rajahalme <[email protected]>

jrajahalme · 2025-12-02T07:38:35Z

Squashed last three commits, added slogloggercheck with reason to use DefaultSlogLogger.

jrajahalme · 2025-12-02T08:32:15Z

/test

tklauser · 2025-12-03T15:07:07Z

pkg/policy/k8s/service.go

-		value = v.Value
-	}
-	return
+// Get implements labels.LabelMatcher; label source is ignored


nit:

Suggested change

// Get implements labels.LabelMatcher; label source is ignored

// GetLabel implements labels.LabelMatcher; label source is ignored

tklauser · 2025-12-03T15:07:16Z

pkg/policy/k8s/service.go

-// Has implements k8sLabels.Labels.
-func (l labelsMatcher) Has(label string) (exists bool) {
-	return labels.Labels(l).HasLabelWithKey(label)
+// Has implements labels.LabelMatcher.


Suggested change

// Has implements labels.LabelMatcher.

// HasLabel implements labels.LabelMatcher.

tklauser · 2025-12-03T15:07:26Z

pkg/policy/k8s/service.go

-// Lookup implements k8sLabels.Labels.
-func (l labelsMatcher) Lookup(label string) (value string, exists bool) {
-	v, ok := labels.Labels(l)[label]
+// Lookup implements labels.LabelMatcher


Suggested change

// Lookup implements labels.LabelMatcher

// LookupLabel implements labels.LabelMatcher

jrajahalme requested review from a team as code owners October 3, 2025 13:43

jrajahalme added the kind/performance There is a performance impact of this. label Oct 3, 2025

jrajahalme requested a review from squeed October 3, 2025 13:43

jrajahalme added sig/policy Impacts whether traffic is allowed or denied based on user-defined policies. release-note/misc This PR makes changes that have no direct user impact. labels Oct 3, 2025

jrajahalme force-pushed the cidr-label-perf branch from cbc5dd3 to cd19f69 Compare October 3, 2025 14:05

jrajahalme force-pushed the cidr-label-perf branch from cd19f69 to e4260a6 Compare October 7, 2025 12:26

jrajahalme changed the title ~~policy: Pre-parse labelIdentitySelector~~ policy: Pre-parse cached selectors, index by namespace Oct 7, 2025

jrajahalme force-pushed the cidr-label-perf branch from e4260a6 to 4d9ce46 Compare October 7, 2025 12:38

squeed reviewed Oct 8, 2025

View reviewed changes

pkg/labels/array.go Outdated Show resolved Hide resolved

squeed reviewed Oct 8, 2025

View reviewed changes

pkg/policy/selectorcache_selector.go Outdated Show resolved Hide resolved

squeed reviewed Oct 8, 2025

View reviewed changes

pkg/policy/selectorcache.go Outdated Show resolved Hide resolved

jrajahalme force-pushed the cidr-label-perf branch from 4d9ce46 to d18a7c0 Compare October 14, 2025 09:38

jrajahalme requested a review from a team as a code owner October 14, 2025 09:38

jrajahalme requested a review from squeed October 14, 2025 09:38

squeed reviewed Oct 14, 2025

View reviewed changes

pkg/policy/selectorcache.go Outdated Show resolved Hide resolved

squeed reviewed Oct 14, 2025

View reviewed changes

pkg/policy/selectorcache.go Outdated Show resolved Hide resolved

jrajahalme force-pushed the cidr-label-perf branch from ebfc4b8 to 91a39d8 Compare October 15, 2025 06:40

jrajahalme requested a review from squeed October 15, 2025 06:41

jrajahalme force-pushed the cidr-label-perf branch from 91a39d8 to c650f3a Compare October 15, 2025 06:42

jrajahalme force-pushed the cidr-label-perf branch from c650f3a to 6cca148 Compare October 28, 2025 07:15

jrajahalme added 9 commits November 22, 2025 11:50

policy: Pre-parse fqdnSelector

a180560

Store the fqdn identity label into `fqdnSelector` so that it does not need to be re-created on every match operation. Signed-off-by: Jarno Rajahalme <[email protected]>

policy: refactor scIdentityCache to a struct

548b86b

Refactor scIdentityCache to a struct. Keep scIdentities in a map via a pointer so that it is possible to point to them via a secondary index to be added in the next commit. Signed-off-by: Jarno Rajahalme <[email protected]>

policy: Index identities by namespace

422ae05

Add a namespace index to identities so that ones with non-matching identities can be trivially skipped when adding or removing selectors to/from the selector cache. Signed-off-by: Jarno Rajahalme <[email protected]>

policy: Index cached selectors by namespace

1683210

Index cached selectors by namespace so that ones with non-matching namespaces can be trivially skipped when adding or deleting identities. Signed-off-by: Jarno Rajahalme <[email protected]>

policy/api: Parse CIDRGroupSelector as an EndpointSelector

b36848f

Signed-off-by: Jarno Rajahalme <[email protected]>

jrajahalme force-pushed the cidr-label-perf branch from 898549e to fcacbe2 Compare November 22, 2025 10:50

jrajahalme changed the title ~~policy: Pre-parse cached selectors, index by namespace, use statedb/part.Map~~ policy: Pre-parse cached selectors, index by namespace Nov 22, 2025

jrajahalme removed request for a team, joamaki and marseel November 22, 2025 10:53

sayboras approved these changes Nov 26, 2025

View reviewed changes

jrajahalme mentioned this pull request Nov 26, 2025

policy: Replace versioned with part.Map #42992

Merged

rgo3 approved these changes Nov 27, 2025

View reviewed changes

joamaki approved these changes Dec 1, 2025

View reviewed changes

squeed reviewed Dec 1, 2025

View reviewed changes

pkg/policy/types/requirements.go Outdated Show resolved Hide resolved

squeed reviewed Dec 1, 2025

View reviewed changes

pkg/policy/types/selector.go Outdated Show resolved Hide resolved

squeed approved these changes Dec 1, 2025

View reviewed changes

tklauser approved these changes Dec 2, 2025

View reviewed changes

jrajahalme mentioned this pull request Dec 3, 2025

k8s: Delete unused subpackage "pkg/k8s/selector" #43104

Merged

tklauser reviewed Dec 3, 2025

View reviewed changes

	// Get implements labels.LabelMatcher; label source is ignored
	// GetLabel implements labels.LabelMatcher; label source is ignored

	// Has implements labels.LabelMatcher.
	// HasLabel implements labels.LabelMatcher.

	// Lookup implements labels.LabelMatcher
	// LookupLabel implements labels.LabelMatcher

Conversation

jrajahalme commented Oct 3, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

marseel commented Oct 3, 2025

Uh oh!

jrajahalme commented Oct 3, 2025

Uh oh!

jrajahalme commented Oct 7, 2025

Uh oh!

Uh oh!

Uh oh!

Uh oh!

squeed commented Oct 8, 2025

Uh oh!

jrajahalme commented Oct 14, 2025

Uh oh!

jrajahalme commented Oct 14, 2025

Uh oh!

Uh oh!

Uh oh!

jrajahalme commented Oct 14, 2025

Uh oh!

jrajahalme commented Oct 15, 2025

Uh oh!

jrajahalme commented Nov 22, 2025

Uh oh!

jrajahalme commented Nov 23, 2025

Uh oh!

sayboras left a comment

Choose a reason for hiding this comment

Uh oh!

joamaki left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

jrajahalme commented Dec 1, 2025

Uh oh!

jrajahalme commented Dec 2, 2025

Uh oh!

jrajahalme commented Dec 2, 2025

Uh oh!

tklauser Dec 3, 2025

Choose a reason for hiding this comment

Uh oh!

tklauser Dec 3, 2025

Choose a reason for hiding this comment

Uh oh!

tklauser Dec 3, 2025

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

13 participants

jrajahalme commented Oct 3, 2025 •

edited

Loading