policy: Fix concurrent access of SelectorCache

[joestringer]

Marco Iorio reports that with previous code, Cilium could crash at
runtime after importing a network policy, with the following error
printed to the logs:

fatal error: concurrent map read and map write

The path for this issue is printed also in the logs, with the following
call stack:

pkg/policy.(*SelectorCache).GetLabels(...)
pkg/policy.(*MapStateEntry).getNets(...)
pkg/policy.entryIdentityIsSupersetOf(...)
pkg/policy.MapState.denyPreferredInsertWithChanges(...)
pkg/policy.MapState.DenyPreferredInsert(...)
pkg/policy.(*EndpointPolicy).computeDirectionL4PolicyMapEntries(...)
pkg/policy.(*EndpointPolicy).computeDesiredL4PolicyMapEntries(...)
pkg/policy.(*selectorPolicy).DistillPolicy(...)
pkg/policy.(*cachedSelectorPolicy).Consume(...)
pkg/endpoint.(*Endpoint).regeneratePolicy(...)
...

Upon further inspection, this call path is not grabbing the
SelectorCache lock at any point. If we check all of the incoming calls
to this function, we can see multiple higher level functions calling
into this function. The following tree starts from the deepest level of
the call stack and increasing indentation represents one level higher in
the call stack.

INCOMING CALLS

• f GetLabels github.com/cilium/cilium/pkg/policy • selectorcache.go
  • f getNets github.com/cilium/cilium/pkg/policy • mapstate.go
    • f entryIdentityIsSupersetOf github.com/cilium/cilium/pkg/policy • mapstate.go
      • f denyPreferredInsertWithChanges github.com/cilium/cilium/pkg/policy • mapstate.go
        • f DenyPreferredInsert github.com/cilium/cilium/pkg/policy • mapstate.go
          • f computeDirectionL4PolicyMapEntries github.com/cilium/cilium/pkg/policy • resolve.go
            • f computeDesiredL4PolicyMapEntries github.com/cilium/cilium/pkg/policy • resolve.go
              • f DistillPolicy github.com/cilium/cilium/pkg/policy • resolve.go <--- No SelectorCache lock
          • f DetermineAllowLocalhostIngress github.com/cilium/cilium/pkg/policy • mapstate.go
            • f DistillPolicy github.com/cilium/cilium/pkg/policy • resolve.go <--- No SelectorCache lock
        • f consumeMapChanges github.com/cilium/cilium/pkg/policy • mapstate.go
          • f ConsumeMapChanges github.com/cilium/cilium/pkg/policy • resolve.go <--- Already locks the SelectorCache

Read the above tree as "GetLabels() is called by getNets()",
"getNets() is called by entryIdentityIsSupersetOf()", and so on.
Siblings at the same level of indent represent alternate callers of the
function that is one level of indentation less in the tree, ie
DenyPreferredInsert() and consumeMapChanges() both call
denyPreferredInsertWithChanges().

As annotated above, we see that calls through DistillPolicy() do not
grab the SelectorCache lock. Given that ConsumeMapChanges() grabs the
SelectorCache lock, we cannot introduce a new lock acquisition in any
descendent function, otherwise it would introduce a deadlock in
goroutines that follow that call path. This provides us the option to
lock at some point from the sibling of consumeMapChanges() or higher in
the call stack.

Given that the ancestors of DenyPreferredInsert() are all from
DistillPolicy(), we can amortize the cost of grabbing the SelectorCache
lock by grabbing it once for the policy distillation phase rather than
putting the lock into DenyPreferredInsert() where the SelectorCache
could be locked and unlocked for each map state entry.

Future work could investigate whether these call paths could make use of
the IdentityAllocator's cache of local identities for the GetLabels()
call rather than relying on the SelectorCache, but for now this patch
should address the immediate locking issue that triggers agent crashes.

Fixes: #24021
Supersedes: #24032
Supersedes: #24283

Fix Cilium crash during network policy computation

[joestringer]

/test

[christarazi]

Fix makes sense to me.

1. Should we go a step further in this PR as an additional commit to rename GetLabels here to GetLabelsLocked to document the assumption that the SelectorCache is intended to be locked?

2. What do you think of clarifying the locking expectations for the functions in common between the write-locked SelectorCache (ConsumeMapChanges) and the read-locked SelectorCache (DistillPolicy)?

Also, as an FYI the call graph in the commit msg omits ToMapState as a potential caller; it's a sibling of DenyPreferredInsert, btw. Not sure if its omission was intended or not, however I don't think it fundamentally impacts the conclusions drawn from the call graph. It was more that my expectation of the call graph was that it was exhaustive, so when I double-checked locally, I noticed this gap.

[joestringer]

Yeah, sounds like (1) and (2) above would be good follow-ups.

As it turns out, if you start the callgraph from SelectorCache.GetLabels(), it does not highlight ToMapState() as another caller, because ToMapState doesn't use the SelectorCache to grab the labels for an identity. Rather, it calls into the CachingIdentityAllocator which has its own local cache of this information. I took one stab at better-documenting this in #24321 , and hint at some future explanation in the final paragraph of the commit message.

[joestringer]

/test

[joestringer]

This was backported in #25427, #25491.

[lefterisALEX]

We are running cilium 1.12.15 and are experiencing that issue. This pull request should is backported to our version if i am looking correctly.

We are getting same error as mentioned in #24021

evel=info msg="Policy imported via API, recalculating..." policyAddRequest=e1602b41-ce7e-4404-8465-ed96eaf95513 policyRevision=1646 subsys=daemon
level=info msg="Imported CiliumNetworkPolicy" ciliumNetworkPolicyName=testing k8sApiVersion= k8sNamespace=demo-01 subsys=k8s-watcher
level=info msg="CEP deleted, calling endpointDeleted" CEPName=dc-develop/dc-registration-service-develop-75b6ddd889-mhjz9 CESName=ces-tqnvnq6ks-ppxl2 subsys=k8s-watcher
level=info msg="regenerating all endpoints" reason="one or more identities created or deleted" subsys=endpoint-manager
fatal error: concurrent map read and map write

goroutine 13404 [running]:
github.com/cilium/cilium/pkg/policy.(*SelectorCache).GetNetsLocked(0x4fcd9e?, 0x4fd13f?)
	/go/src/github.com/cilium/cilium/pkg/policy/selectorcache.go:1119 +0x68
github.com/cilium/cilium/pkg/policy.getNets({0x358a4a0?, 0xc000119490?}, 0x1e4?)
	/go/src/github.com/cilium/cilium/pkg/policy/mapstate.go:194 +0x58
github.com/cilium/cilium/pkg/policy.identityIsSupersetOf(0x53fa7a8?, 0x7e13, {0x358a4a0, 0xc000119490})
	/go/src/github.com/cilium/cilium/pkg/policy/mapstate.go:399 +0x52