labels/cidr: Memoize labels for already seen prefixes

[pippolo84]

GetCIDRLabels turns a CIDR into a set of labels representing the cidr itself and all broader CIDRS which include the specified CIDR in them.

In case of ToFQDNs policies matching many names that maps to many IPs with very short TTLs, this function can easily become a hot path.

To improve performance, the PR adds a LRU cache to memoize intermediate results.

See individual commit messages for further details.

[odinuge]

Hi!

It does seem like this introduces some strange behavior. My colleague @sjdot discovered that this change results in excessive numbers of false positive policy drops, for legit traffic that should not be dropped.

By adding this test

diff --git a/pkg/labels/cidr/cidr_test.go b/pkg/labels/cidr/cidr_test.go
index 8ee0dbd605..9a6dd722c4 100644
--- a/pkg/labels/cidr/cidr_test.go
+++ b/pkg/labels/cidr/cidr_test.go
@@ -4,6 +4,7 @@
 package cidr

 import (
+       "fmt"
        "net/netip"
        "testing"

@@ -309,6 +310,18 @@ func BenchmarkLabels_SortedListCIDRIDs(b *testing.B) {
        }
 }

+func TestThisThing(t *testing.T) {
+       for _, ip := range []string{
+               "10.0.0.0/1",
+               "10.0.0.0/3",
+       } {
+               t.Run(ip, func(b *testing.T) {
+                       lbls := GetCIDRLabels(netip.MustParsePrefix(ip))
+                       fmt.Printf("%q: %+v\n", netip.MustParsePrefix(ip), lbls.LabelArray())
+               })
+       }
+}
+
 func BenchmarkIPStringToLabel(b *testing.B) {
        for _, ip := range []string{
                "0.0.0.0/0",

, we get the following output;

=== RUN   TestThisThing
=== RUN   TestThisThing/10.0.0.0/1
"10.0.0.0/1": [cidr:0.0.0.0/0 cidr:0.0.0.0/1 reserved:world-ipv4]
=== RUN   TestThisThing/10.0.0.0/3
"10.0.0.0/3": [cidr:0.0.0.0/0 cidr:0.0.0.0/1 reserved:world-ipv4]
--- PASS: TestThisThing (0.00s)
  --- PASS: TestThisThing/10.0.0.0/1 (0.00s)
  --- PASS: TestThisThing/10.0.0.0/3 (0.00s)
PASS

When disabling the cache, we instead get this that make more sense.

=== RUN   TestThisThing
=== RUN   TestThisThing/10.0.0.0/1
"10.0.0.0/1": [cidr:0.0.0.0/0 cidr:0.0.0.0/1 reserved:world-ipv4]
=== RUN   TestThisThing/10.0.0.0/3
"10.0.0.0/3": [cidr:0.0.0.0/0 cidr:0.0.0.0/1 cidr:0.0.0.0/2 cidr:0.0.0.0/3 reserved:world-ipv4]
--- PASS: TestThisThing (0.00s)
    --- PASS: TestThisThing/10.0.0.0/1 (0.00s)
    --- PASS: TestThisThing/10.0.0.0/3 (0.00s)
PASS

So it overall seems like there is some issue in the way things are cached here, or is this expected..? @pippolo84 @joamaki

[pippolo84]

Hi @odinuge , thank you for bringing this up. 🙏
I confirm this was not expected. We are working on a fix, together with better unit testing.

[odinuge]

unless you were aware, you can also plumb this into the benchmark result to make it easier to use things like benchstat to compare it; https://github.com/cilium/cilium/pull/21895/files#diff-a5084c37ba77e5fe28cbc8d15ffe1e5c312e2daf79c8a363ec52df758818d26dR1091

[pippolo84]

Thanks for the heads up, but I think that in this case it is better to switch to a simple test instead of a benchmark. That's because we want to measure the memory usage when the cache is full and to do that with the benchmark we would need to either:

• pass benchtime=1x to complete only a single pass
• reset the cache at each pass as part of the code to benchmark (but this resulted in longer benchmark run, probably for the time needed to stabilize the time measure)