bpf: Policy map precedence by LPM prefix length #35150

jrajahalme · 2024-10-01T12:41:12Z

Policy map key can have nexthdr and destination port fields wildcarded. Cilium datapath typically performs two policy map lookups, one with the L3 identity mapped from the relevant IP address (destination or source IP for egress or ingress policy, respectively). Datapath chooses between the two policy entries based on two booleans in the policy entry: 'wildcarded_protocol' and 'wildcarded_dport'. The problem is that 'wildcarded_dport' is set only if the destination port is fully wildcarded, so partially wildcarded port is considered as "not wildcarded" for this logic.

Fix this for partially wildcarded ports by always choosing between L4-only and L3 policy matches by the key prefix length so that the most specific entry is always selected, selecting the entry with a specific identity if the prefix lengths are the same. That is, choose the policy with specific L3 if the prefixes are the same length, otherwise choose the policy with the longer prefix.

LPM map key already contains the prefix length, but unfortunately LPM map lookup does not return the map key. This is why we store an 8-bit version of the prefix length in the policy map entry, which is as follows:

0: both nexthdr and destination port fully wildcarded
8: nexthdr specified but port fully wildcarded
24: both nexthdr and destination port specified (no wildcarding)

Values between 8 and 24 represent the less or more wildcarded destination port.

Previously used wildcarded_protocol and wildcarded_dport flags are removed as redundant.

Before this change the precedence between the following two rules:

<ID>/TCP/80/15 -- L3 specified, TCP port 80 partially wildcarded (ports 80-81)
*/TCP/80/16 -- L3 wildcarded, TCP port 80 not wildcarded

would have resulted in selecting the policy with <ID> specified even when it's destination port is partially wildcarded, while the L4-only rule has no wildcarding in it's destination port.

If the entries above were allow (1) and deny (3), Cilium agent masked this behavior by adding an additional deny entry in this case:

<ID>/TCP/80/16 -- L3 <ID> specified, TCP port 80 not wildcarded

This masks the incorrect behavior for allow/deny case, since the non-wildcarded key (3) is given precedence by the datapath.

There is no such additional entry logic in the allow/allow case, so if the more specific L4-only policy entry has L7 policy, and the less specific L3 policy not, then matching traffic would not be sent to the L7 proxy for policy enforcement.

After this change the policy with less L4 wildcarding (the more specific L4) is given precedence, with L3 rule being selected when prefixes are of the same length. This allows for simplifying policy map computation by avoiding the need to add additional entries in cases where deny already has the longer prefix length.

This change makes no difference for keys which only have the destination port fully specified or fully wildcarded, so this only affects policies with port ranges as enabled in Cilium 1.16.

Removal of the additional deny entries enabled by this change make BenchmarkRegenerateCIDRDenyPolicyRules ~10% faster due to reduced allocations.

Fixes: #23885

Cilium datapath now gives precedence for the more specific allow rule with L7 rules when rules with port ranges are present.

jrajahalme · 2024-10-01T13:15:33Z

/test

jrajahalme · 2024-10-01T13:18:51Z

/test

gentoo-root · 2024-10-01T16:59:56Z

I don't feel like I fully get the idea, could you clarify please?

Before this change the precedence between the following two rules:

/TCP/80/15 -- L3 specified, TCP port 80 partially wildcarded (ports 80-81)

*/TCP/80/16 -- L3 wildcarded, TCP port 80 not wildcarded

would have resulted in selecting the policy with specified even when it's destination port is partially wildcarded, while the L4-only rule has no wildcarding in it's destination port.

Meaning that 1 is preferred over 2? Is that not expected according to the comment in the code?

* 2. ANY/proto/port (L4-only)
* 3. id/proto/ANY   (L3-proto)

After this change the policy with less L4 wildcarding (the more specific L4) is given precedence, with L3 rule being selected when prefixes are of the same length.

I.e. 2 will be preferred over 1? What's the motivation of this change?

jrajahalme · 2024-10-02T16:10:57Z

/test

jrajahalme · 2024-10-03T06:03:07Z

I don't feel like I fully get the idea, could you clarify please?

Before this change the precedence between the following two rules:

/TCP/80/15 -- L3 specified, TCP port 80 partially wildcarded (ports 80-81)

There is an unfortunate markdown rendering effect here, the source has "<ID>", which is rendered as an empty string. Note that the comment says "L3 specified".

*/TCP/80/16 -- L3 wildcarded, TCP port 80 not wildcarded

would have resulted in selecting the policy with specified even when it's destination port is partially wildcarded, while the L4-only rule has no wildcarding in it's destination port.

Meaning that 1 is preferred over 2? Is that not expected according to the comment in the code?
* 2. ANY/proto/port (L4-only)
* 3. id/proto/ANY   (L3-proto)

1 is preferred over 2 due to this:

 	 * 1. id/proto/port  (L3/L4)
 	 * 2. ANY/proto/port (L4-only)

This happens because the condition used for 1. evaluates true due to wildcarded_dport being true only if it is fully wildcarded:

   if (likely(policy && !policy->wildcard_dport)) {
		*match_type = POLICY_MATCH_L3_L4;		/* 1. id/proto/port */

After this change the policy with less L4 wildcarding (the more specific L4) is given precedence, with L3 rule being selected when prefixes are of the same length.

I.e. 2 will be preferred over 1? What's the motivation of this change?

Datapath only ever has to choose between two rules, one with full L3 identity match, other with L3 identity wildcarded (= 0). This change makes sure the policy with more specific proto/port is chosen out of these two. The lookup for these two cases is already doing that (among the matching L3 identity and wildcard L3 identity) due to the policy map being LPM.

jrajahalme · 2024-10-03T06:06:50Z

/test

nathanjsweet

LGTM

Consider following two policy map state entries: 1. Allow <ID>/TCP/80/15 -- L3 <ID> specified, TCP port 80 partially wildcarded (ports 80-81) 2. Deny */TCP/80/16 -- L3 wildcarded, TCP port 80 not wildcarded When the deny entry is added, Cilium adds an additional deny entry: 3. Deny <ID>/TCP/80/16 -- L3 <ID> specified, TCP port 80 not wildcarded This makes sure that the allow rule is not given precedence. This is currently needed due to the logic datapath uses to select between the L3-specific and L4-only entries when both are found. There is no such additional entry logic in the allow/allow case, so we rely on the datapath choosing the "right" entry. Eg., if the more specific L4-only policy entry has L7 policy, and the less specific L3 policy not, then the datapath should select the more specific entry and redirect the traffic to the L7 proxy for policy enforcement. Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>

Policy map key can have nexthdr and destination port fields wildcarded. Cilium datapath typically performs two policy map lookups, one with the L3 identity mapped from the relevant IP address (destination or source IP for egress or ingress policy, respectively). Datapath chooses between the two policy entries based on two booleans in the policy entry: 'wildcarded_protocol' and 'wildcarded_dport'. The problem is that 'wildcarded_dport' is set only if the destination port is fully wildcarded, so partially wildcarded port is considered as "not wildcarded" for this logic. Fix this for partially wildcarded ports by always choosing between L4-only and L3 policy matches by the key prefix length so that the most specific entry is always selected, selecting the entry with a precific identity if the prefix lengths are the same. That is, choose the policy with specific L3 if the prefixes are the same length, otherwise choose the policy with the longer prefix. LPM map key already contains the prefix length, but unfortunately LPM map lookup does not return the map key. This is why we store an 8-bit version of the prefix length in the policy map entry, which is as follows: 0: both nexthdr and destination port fully wildcarded 8: nexthdr specified but port fully wildcarded 24: both nexthdr and destination port specified (no wildcarding) Values between 8 and 24 represent the less or more wildcarded destination port. Previously used wildcarded_protocol and wildcarded_dport flags are removed as redundant. Before this change the precedence between the following two rules: 1. <ID>/TCP/80/15 -- L3 <ID> specified, TCP port 80 partially wildcarded (ports 80-81) 2. */TCP/80/16 -- L3 wildcarded, TCP port 80 not wildcarded would have resulted in selecting the policy with <ID> specified even when it's destination port is partially wildcarded, while the L4-only rule has no wildcarding in it's destination port. If the entries above were allow (1) and deny (3), Cilium agent masked this behavior by adding an additional deny entry in this case: 3. <ID>/TCP/80/16 -- L3 <ID> specified, TCP port 80 not wildcarded This masks the incorrect behavior for allow/deny case, since the non-wildcarded key (3) is given precedence by the datapath. There is no such additional entry logic in the allow/allow case, so if the more specific L4-only policy entry has L7 policy, and the less specific L3 policy not, then matching traffic would not be sent to the L7 proxy for policy enforcement. After this change the policy with less L4 wildcarding (the more specific L4) is given precedence, with L3 rule being selected when prefixes are of the same length. This allows for simplifying policy map computation by avoiding the need to add additional entries in cases where deny already has the longer prefix length. This change makes no difference for keys which only have the destination port fully specified or fully wildcarded, so this only affects policies with port ranges as enabled in Cilium 1.16. Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>

jrajahalme · 2024-10-08T19:55:40Z

/test

giorio94 · 2024-10-09T15:44:14Z

Marked backport/author due to significant differences between v1.16 and main (due to #33719 and #33313 apparently).

Move the prefix length field in the policy map value to the flags (same byte as 'deny') to a previously unused space. This cleans up padding space for future use. Skip map entries with inconsistent prefix length field in value vs. key so that the entry will be rewritten with the correct prefix length field in the value. This fixes a potential issue in upgrade where a policy map entry may remain with zero valued prefix length in value leading to incorrect policy enforcement. Fixes: cilium#35150 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>

Move the prefix length field in the policy map value to the flags (same byte as 'deny') to a previously unused space. This cleans up padding space for future use. Skip map entries with inconsistent prefix length field in value vs. key so that the entry will be rewritten with the correct prefix length field in the value. This fixes a potential issue in upgrade where a policy map entry may remain with zero valued prefix length in value leading to incorrect policy enforcement. Fixes: #35150 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>

[ upstream commit 60bc8fa ] Move the prefix length field in the policy map value to the flags (same byte as 'deny') to a previously unused space. This cleans up padding space for future use. Skip map entries with inconsistent prefix length field in value vs. key so that the entry will be rewritten with the correct prefix length field in the value. This fixes a potential issue in upgrade where a policy map entry may remain with zero valued prefix length in value leading to incorrect policy enforcement. Fixes: cilium#35150 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>

[ upstream commit 60bc8fa ] Move the prefix length field in the policy map value to the flags (same byte as 'deny') to a previously unused space. This cleans up padding space for future use. Skip map entries with inconsistent prefix length field in value vs. key so that the entry will be rewritten with the correct prefix length field in the value. This fixes a potential issue in upgrade where a policy map entry may remain with zero valued prefix length in value leading to incorrect policy enforcement. Fixes: #35150 Signed-off-by: Jarno Rajahalme <jarno@isovalent.com>

jrajahalme requested a review from a team as a code owner October 1, 2024 12:41

jrajahalme requested a review from gentoo-root October 1, 2024 12:41

jrajahalme marked this pull request as draft October 1, 2024 12:41

jrajahalme force-pushed the bpf-policy-map-precedence-fix branch from 28d4fb6 to 5c8007f Compare October 1, 2024 13:00

jrajahalme added the needs-backport/1.16 This PR / issue needs backporting to the v1.16 branch label Oct 1, 2024

jrajahalme force-pushed the bpf-policy-map-precedence-fix branch from 5c8007f to 7817265 Compare October 1, 2024 13:09

jrajahalme force-pushed the bpf-policy-map-precedence-fix branch from 7817265 to 4d46d86 Compare October 1, 2024 13:18

jrajahalme force-pushed the bpf-policy-map-precedence-fix branch from 4d46d86 to 5824824 Compare October 2, 2024 15:58

jrajahalme force-pushed the bpf-policy-map-precedence-fix branch from 5824824 to 6e60cfd Compare October 3, 2024 05:50

jrajahalme marked this pull request as ready for review October 3, 2024 05:51

jrajahalme requested a review from a team as a code owner October 3, 2024 05:51

jrajahalme requested a review from derailed October 3, 2024 05:51

jrajahalme added the kind/bug This is a bug in the Cilium logic. label Oct 4, 2024

jrajahalme requested review from nathanjsweet and removed request for derailed October 4, 2024 12:46

nathanjsweet approved these changes Oct 8, 2024

View reviewed changes

gentoo-root approved these changes Oct 8, 2024

View reviewed changes

maintainer-s-little-helper bot added the ready-to-merge This PR has passed all tests and received consensus from code owners to merge. label Oct 8, 2024

jrajahalme added 2 commits October 8, 2024 21:52

jrajahalme force-pushed the bpf-policy-map-precedence-fix branch from 6e60cfd to 6861644 Compare October 8, 2024 19:55

jrajahalme enabled auto-merge October 8, 2024 19:55

jrajahalme mentioned this pull request Oct 8, 2024

Policy mapstate cleanups #35233

Merged

jrajahalme added this pull request to the merge queue Oct 8, 2024

Merged via the queue into cilium:main with commit ebb4c47 Oct 8, 2024
63 checks passed

jrajahalme deleted the bpf-policy-map-precedence-fix branch October 8, 2024 21:19

giorio94 mentioned this pull request Oct 9, 2024

v1.16 Backports 2024-10-09 #35319

Merged

5 tasks

giorio94 added the backport/author The backport will be carried out by the author of the PR. label Oct 9, 2024

jrajahalme mentioned this pull request Oct 25, 2024

datapath: move policy map value prefix length to flags #35534

Merged

jrajahalme mentioned this pull request Oct 29, 2024

Pr/jrajahalme/bpf policy map precedence fix v1.16 #35603

Merged

2 tasks

jrajahalme added backport-pending/1.16 The backport for Cilium 1.16.x for this PR is in progress. and removed needs-backport/1.16 This PR / issue needs backporting to the v1.16 branch labels Oct 29, 2024

github-actions bot added backport-done/1.16 The backport for Cilium 1.16.x for this PR is done. and removed backport-pending/1.16 The backport for Cilium 1.16.x for this PR is in progress. labels Oct 30, 2024

cilium-release-bot bot mentioned this pull request Nov 13, 2024

Prepare for release v1.16.4 #35954

Merged

GoVulnBot mentioned this pull request Nov 25, 2024

x/vulndb: potential Go vuln in github.com/cilium/cilium: CVE-2024-52529 golang/vulndb#3290

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

bpf: Policy map precedence by LPM prefix length #35150

bpf: Policy map precedence by LPM prefix length #35150

Uh oh!

jrajahalme commented Oct 1, 2024 •

edited

Loading

Uh oh!

jrajahalme commented Oct 1, 2024

Uh oh!

jrajahalme commented Oct 1, 2024

Uh oh!

gentoo-root commented Oct 1, 2024

Uh oh!

jrajahalme commented Oct 2, 2024

Uh oh!

jrajahalme commented Oct 3, 2024

Uh oh!

jrajahalme commented Oct 3, 2024

Uh oh!

nathanjsweet left a comment

Uh oh!

jrajahalme commented Oct 8, 2024

Uh oh!

Uh oh!

giorio94 commented Oct 9, 2024

Uh oh!

Uh oh!

bpf: Policy map precedence by LPM prefix length #35150

bpf: Policy map precedence by LPM prefix length #35150

Uh oh!

Conversation

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

Uh oh!

Uh oh!

jrajahalme commented Oct 1, 2024

Uh oh!

jrajahalme commented Oct 1, 2024

Uh oh!

gentoo-root commented Oct 1, 2024

Uh oh!

jrajahalme commented Oct 2, 2024

Uh oh!

jrajahalme commented Oct 3, 2024

Uh oh!

jrajahalme commented Oct 3, 2024

Uh oh!

nathanjsweet left a comment

Choose a reason for hiding this comment

Uh oh!

jrajahalme commented Oct 8, 2024

Uh oh!

Uh oh!

giorio94 commented Oct 9, 2024

Uh oh!

Uh oh!

jrajahalme commented Oct 1, 2024 •

edited

Loading