Transactional selector cache #34205
Merged
Transactional selector cache #34205
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
b34ddb7 to
7ddb9f0
Compare
bimmlerd
reviewed
Aug 7, 2024
9bbc950 to
d87bf49
Compare
|
/test |
joamaki
reviewed
Aug 8, 2024
d87bf49 to
a99bf24
Compare
|
Dropped the last commit (changing how incremental updates are regenerated), which turned out to be a significant lift in itself. Added new commit refactoring |
joamaki
reviewed
Aug 8, 2024
a99bf24 to
74238fb
Compare
|
ci-runtime hit by #35055 |
Versioned values can be used for transactional updates where updates in multiple values become available at the same version number. Multiple versioned.Values are managed by a common versioned.Coordinator. Each versioned.Value keeps a linked list of nodes with the validity range for the value stored on that node. Nodes are traversed until a value that is valid for the version at the beginning of the transaction is found, or an empty value is returned otherwise. Old values are cleaned off when a read transaction is finished by calling the VersionHandle.Close() function. In steady-state only the head pointer needs to be dereferenced, which is the same cost as dereferencing a normal value stored via a pointer. With churn more nodes may need to be traversed, but that should be transitional, and on read heavy use cases the average number of traversed nodes should be close to 1, so the overhead of transactionality should be minimal. The list of values is accessed in lock-free manner, so no locks are needed when getting a value for a version of a valid handle. The entity updating the values must only allow one goroutine to update any value at any given time. This is inspired by earlier work at openvswitch/ovs@2b7b142 and as simplified at openvswitch/ovs@18721c4 and openvswitch/ovs@44e0c35 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
Use the new versioned.Value to make SelectorCache selections updates transactional. This allows changes to selections of different selectors to appear at once on a new version published by the selector cache after all the changes have been completed. This change allows SelectorCache users to rely on all the selectors to be in sync with each other, so that if a given identity is selected by two selectors, that identity appears in the result of the GetSelections(handle) call for both of the selectors. Previously it was possible that at the time of the respective GetSelections() call, either of them would have failed to include the new identity, due to the update of that selector still being in progress. With this change the visibility of new identities in the selections of any cached selector is delayed until all affected selectors have been updated. Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
Make incremental policy updates available for the endpoint only after all affected selectors have been updated. We do this by adding IdentitySelectionCommit() call to the CachedSelectionUser interface. This is called after calls to IdentitySelectionUpdated with all the affected selectors have been completed. IdentitySelectionCommit() gets a *versioned.Tx argument that is used when the incremental changes result in actual MapState changes to get the handle with which the Envoy policy update can be computed. We also synchronize the insertion of a new EndpointPolicy to a SelectorPolicy with the selector cache identity updates. This guarantees that all updates after the initial state are received. Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
Rename test variables in a separate commit first to highlight functional changes later. Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
Real CIDR (and WORLD) selectors select all covered identities, so that when we generate MapState for a CIDR or a WORLD rule, entries for all the covered identities are created. Mimic this in unit tests as well. Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
Deny entries with broader (i.e., less specific) port-protocols interact with superset allow entries only if the allow entry is an L3-wildcard. In the case of the L3-wildcard allow, the deny entry is by definition a non-L3-wildcard (its identity is a subset of the allow identity), and datapath does not relate two non-wildcard L3-entries in any way. Given this we need to add additional L3L4-deny entries only if the allow entry in this scenario has an L3-wildcard key. Tests are adjusted to not expect the unnecessary derivative deny entries. Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
Remove the CIDR index from MapState. Now that SelectorCache GetSelections() and incremental updates are both transactional, we can rely on a covering CIDR identity also select any covered new identities. For example, given a L3-only WORLD deny rule and an toFQDNs allow rule, and newly allocated FQDN identities are also selected by the deny WORLD selector, and we can rely on these new identities appearing on those selectors "at the same time", so that on any given round of DistillPolicy or ConsumeMapChanges, any new identities appear on all affected selectors, and conversely, and revoved identities are likewise removed from all affected selectors. Given the above, we do not need to go look for non-wildcard superset/subset identities, as keys with them will be added (or have already been added) or removed on the same round and the effect of them will be present in the computed mapstate. In the above example, even if on a given round we first add an allow rules the new FQDN-derived identity, we will later replace it with a deny entry based on the same ID being selected by the (deny) WORLD selector. Conversely, if on a given round we add the deny entry first, the allow entry will be naturally bailed due to the existing deny entry. This allows to get rid of the Identities interface as well as that was used to find a prefix for an ID in the selector cache. We also remove the validator interface, as maintaining it would be a burden at this point. Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
87072f4 to
e53f146
Compare
|
|
|
/test |
jrajahalme
added a commit
to jrajahalme/cilium
that referenced
this pull request
Oct 3, 2024
Call queueNotifiedUsersCommit() before starting go routing waiting on `wg`, as queueNotifiedUsersCommit() does `wg.Add(1)`. This makes it impossible to hit this bug: ``` 2024-10-03T08:45:07.562242086Z panic: sync: WaitGroup is reused before previous Wait has returned 2024-10-03T08:45:07.562251423Z 2024-10-03T08:45:07.562358242Z goroutine 11033 [running]: 2024-10-03T08:45:07.562532947Z sync.(*WaitGroup).Wait(0xc0041bfe90?) 2024-10-03T08:45:07.562538587Z /usr/local/go/src/sync/waitgroup.go:120 +0x74 2024-10-03T08:45:07.562541644Z github.com/cilium/cilium/pkg/policy.(*SelectorCache).UpdateIdentities.func1(0xc01829a4c0) 2024-10-03T08:45:07.562544629Z /go/src/github.com/cilium/cilium/pkg/policy/selectorcache.go:540 +0x3a 2024-10-03T08:45:07.562547444Z created by github.com/cilium/cilium/pkg/policy.(*SelectorCache).UpdateIdentities in goroutine 357 2024-10-03T08:45:07.562550470Z /go/src/github.com/cilium/cilium/pkg/policy/selectorcache.go:539 +0xd54 ``` Fixes: cilium#34205 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
jrajahalme
added a commit
to jrajahalme/cilium
that referenced
this pull request
Oct 4, 2024
Call queueNotifiedUsersCommit() before starting go routing waiting on `wg`, as queueNotifiedUsersCommit() does `wg.Add(1)`. This makes it impossible to hit this bug: ``` 2024-10-03T08:45:07.562242086Z panic: sync: WaitGroup is reused before previous Wait has returned 2024-10-03T08:45:07.562251423Z 2024-10-03T08:45:07.562358242Z goroutine 11033 [running]: 2024-10-03T08:45:07.562532947Z sync.(*WaitGroup).Wait(0xc0041bfe90?) 2024-10-03T08:45:07.562538587Z /usr/local/go/src/sync/waitgroup.go:120 +0x74 2024-10-03T08:45:07.562541644Z github.com/cilium/cilium/pkg/policy.(*SelectorCache).UpdateIdentities.func1(0xc01829a4c0) 2024-10-03T08:45:07.562544629Z /go/src/github.com/cilium/cilium/pkg/policy/selectorcache.go:540 +0x3a 2024-10-03T08:45:07.562547444Z created by github.com/cilium/cilium/pkg/policy.(*SelectorCache).UpdateIdentities in goroutine 357 2024-10-03T08:45:07.562550470Z /go/src/github.com/cilium/cilium/pkg/policy/selectorcache.go:539 +0xd54 ``` Fixes: cilium#34205 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
jrajahalme
added a commit
to jrajahalme/cilium
that referenced
this pull request
Oct 4, 2024
With transactional selector cache the action `insertBasDeny` is no longer needed, since the deny entry for the B's identities are already added as part of A, as in this case A is a deny entry and it includes all the IDs of B. Fixes: cilium#34205 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
jrajahalme
added a commit
to jrajahalme/cilium
that referenced
this pull request
Oct 4, 2024
With transactional selector cache the action `insertBasDeny` is no longer needed, since the deny entry for the B's identities are already added as part of A, as in this case A is a deny entry and it includes all the IDs of B. Fixes: cilium#34205 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
github-merge-queue bot
pushed a commit
that referenced
this pull request
Oct 4, 2024
Call queueNotifiedUsersCommit() before starting go routing waiting on `wg`, as queueNotifiedUsersCommit() does `wg.Add(1)`. This makes it impossible to hit this bug: ``` 2024-10-03T08:45:07.562242086Z panic: sync: WaitGroup is reused before previous Wait has returned 2024-10-03T08:45:07.562251423Z 2024-10-03T08:45:07.562358242Z goroutine 11033 [running]: 2024-10-03T08:45:07.562532947Z sync.(*WaitGroup).Wait(0xc0041bfe90?) 2024-10-03T08:45:07.562538587Z /usr/local/go/src/sync/waitgroup.go:120 +0x74 2024-10-03T08:45:07.562541644Z github.com/cilium/cilium/pkg/policy.(*SelectorCache).UpdateIdentities.func1(0xc01829a4c0) 2024-10-03T08:45:07.562544629Z /go/src/github.com/cilium/cilium/pkg/policy/selectorcache.go:540 +0x3a 2024-10-03T08:45:07.562547444Z created by github.com/cilium/cilium/pkg/policy.(*SelectorCache).UpdateIdentities in goroutine 357 2024-10-03T08:45:07.562550470Z /go/src/github.com/cilium/cilium/pkg/policy/selectorcache.go:539 +0xd54 ``` Fixes: #34205 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
jrajahalme
added a commit
to jrajahalme/cilium
that referenced
this pull request
Oct 4, 2024
With transactional selector cache the action `insertBasDeny` is no longer needed, since the deny entry for the B's identities are already added as part of A, as in this case A is a deny entry and it includes all the IDs of B. Fixes: cilium#34205 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
jrajahalme
added a commit
to jrajahalme/cilium
that referenced
this pull request
Oct 7, 2024
With transactional selector cache the action `insertBasDeny` is no longer needed, since the deny entry for the B's identities are already added as part of A, as in this case A is a deny entry and it includes all the IDs of B. Fixes: cilium#34205 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
jrajahalme
added a commit
to jrajahalme/cilium
that referenced
this pull request
Oct 8, 2024
With transactional selector cache the action `insertBasDeny` is no longer needed, since the deny entry for the B's identities are already added as part of A, as in this case A is a deny entry and it includes all the IDs of B. Fixes: cilium#34205 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
jrajahalme
added a commit
to jrajahalme/cilium
that referenced
this pull request
Oct 8, 2024
With transactional selector cache the action `insertBasDeny` is no longer needed, since the deny entry for the B's identities are already added as part of A, as in this case A is a deny entry and it includes all the IDs of B. Fixes: cilium#34205 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
jrajahalme
added a commit
to jrajahalme/cilium
that referenced
this pull request
Oct 8, 2024
With transactional selector cache the action `insertBasDeny` is no longer needed, since the deny entry for the B's identities are already added as part of A, as in this case A is a deny entry and it includes all the IDs of B. Fixes: cilium#34205 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
github-merge-queue bot
pushed a commit
that referenced
this pull request
Oct 9, 2024
With transactional selector cache the action `insertBasDeny` is no longer needed, since the deny entry for the B's identities are already added as part of A, as in this case A is a deny entry and it includes all the IDs of B. Fixes: #34205 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Make SelectorCache identity updates transactional. This allows changes to selections of different selectors to appear at once on a new version published by the selector cache after all the changes have been completed, which allows removal of the CIDR index within MapState, making computation of CIDR heavy policies ~45% faster, mainly due to reduction of allocations by ~37%.
This change allows SelectorCache users to rely on all the selectors to be in sync with each other, so that if a given identity is selected by multiple selectors, that identity appears in the result of the
GetSelections()call for all of them. Previously it was possible that at the time of the respective GetSelections() calls, some of them would have failed to include the new identity, due to the update of that selector still being in progress.With this change the visibility of new identities in the selections of any cached selector is delayed until all affected selectors have been updated.
Incremental updates are synchronized after each round of identity modifications in the selector cache so that the updates on all affected MapState entries appear during the same round of updates, essentially making incremental updates transactional as well. The consumer of incremental updates gets the version of the selector cache as of after the changes, so that a consistent NetworkPolicy can be computed for Envoy as well.
Now that SelectorCache GetSelections() and incremental updates are both transactional, we can rely on a covering CIDR selector to also select any covered new identities. For example, given a L3-only WORLD deny rule and an toFQDNs allow rule, and newly allocated FQDN identities are also selected by the deny WORLD selector, and we can rely on these new
identities appearing on those selectors "at the same time", so that on any given round of DistillPolicy or ConsumeMapChanges, any new identities appear on all affected selectors, and conversely, and removed identities are likewise removed from all affected selectors.
Given the above, we do not need to go look for non-wildcard superset/subset identities, as keys with them will be added (or have already been added) or removed on the same round and the effect of them will be present in the computed MapState. In the above example, even if on a given round we first add an allow rules the new FQDN-derived identity, we will later replace it with a deny entry based on the same ID being selected by the (deny) WORLD selector. Conversely, if on a given round we add the deny entry first, the allow entry will be naturally bailed due to the existing deny entry.
Following PR(s) have been carved out to merge separately: