-
Notifications
You must be signed in to change notification settings - Fork 2.9k
/
mapstate.go
1456 lines (1332 loc) · 53.4 KB
/
mapstate.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// SPDX-License-Identifier: Apache-2.0
// Copyright Authors of Cilium
package policy
import (
"fmt"
"net"
"slices"
"strconv"
"testing"
"github.com/sirupsen/logrus"
"golang.org/x/exp/maps"
"github.com/cilium/cilium/pkg/identity"
"github.com/cilium/cilium/pkg/ip"
"github.com/cilium/cilium/pkg/labels"
"github.com/cilium/cilium/pkg/lock"
"github.com/cilium/cilium/pkg/logging/logfields"
"github.com/cilium/cilium/pkg/option"
"github.com/cilium/cilium/pkg/policy/trafficdirection"
)
var (
// localHostKey represents an ingress L3 allow from the local host.
localHostKey = Key{
Identity: identity.ReservedIdentityHost.Uint32(),
TrafficDirection: trafficdirection.Ingress.Uint8(),
}
// localRemoteNodeKey represents an ingress L3 allow from remote nodes.
localRemoteNodeKey = Key{
Identity: identity.ReservedIdentityRemoteNode.Uint32(),
TrafficDirection: trafficdirection.Ingress.Uint8(),
}
// allKey represents a key for unknown traffic, i.e., all traffic.
allKey = Key{
Identity: identity.IdentityUnknown.Uint32(),
}
)
const (
LabelKeyPolicyDerivedFrom = "io.cilium.policy.derived-from"
LabelAllowLocalHostIngress = "allow-localhost-ingress"
LabelAllowRemoteHostIngress = "allow-remotehost-ingress"
LabelAllowAnyIngress = "allow-any-ingress"
LabelAllowAnyEgress = "allow-any-egress"
LabelVisibilityAnnotation = "visibility-annotation"
)
// MapState is a map interface for policy maps
type MapState interface {
Get(Key) (MapStateEntry, bool)
Insert(Key, MapStateEntry)
Delete(Key)
// ForEach allows iteration over the MapStateEntries. It returns true iff
// the iteration was not stopped early by the callback.
ForEach(func(Key, MapStateEntry) (cont bool)) (complete bool)
// ForEachAllow behaves like ForEach, but only iterates MapStateEntries which are not denies.
ForEachAllow(func(Key, MapStateEntry) (cont bool)) (complete bool)
// ForEachDeny behaves like ForEach, but only iterates MapStateEntries which are denies.
ForEachDeny(func(Key, MapStateEntry) (cont bool)) (complete bool)
GetIdentities(*logrus.Logger) ([]int64, []int64)
GetDenyIdentities(*logrus.Logger) ([]int64, []int64)
RevertChanges(ChangeState)
AddVisibilityKeys(PolicyOwner, uint16, *VisibilityMetadata, ChangeState)
Len() int
Equals(MapState) bool
Diff(t *testing.T, expected MapState) string
allowAllIdentities(ingress, egress bool)
determineAllowLocalhostIngress()
deniesL4(policyOwner PolicyOwner, l4 *L4Filter) bool
denyPreferredInsertWithChanges(newKey Key, newEntry MapStateEntry, identities Identities, features policyFeatures, changes ChangeState)
deleteKeyWithChanges(key Key, owner MapStateOwner, changes ChangeState)
}
// mapState is a state of a policy map.
type mapState struct {
allows mapStateMap
denies mapStateMap
}
// mapStateMap is a convience type representing the actual structure mapping
// policymap keys to policymap entries.
type mapStateMap map[Key]MapStateEntry
func (m mapStateMap) insert(k Key, e MapStateEntry) {
if m == nil {
n := make(mapStateMap)
m = n
}
m[k] = e
}
type Identities interface {
GetNetsLocked(identity.NumericIdentity) []*net.IPNet
}
// Key is the userspace representation of a policy key in BPF. It is
// intentionally duplicated from pkg/maps/policymap to avoid pulling in the
// BPF dependency to this package.
type Key struct {
// Identity is the numeric identity to / from which traffic is allowed.
Identity uint32
// DestPort is the port at L4 to / from which traffic is allowed, in
// host-byte order.
DestPort uint16
// NextHdr is the protocol which is allowed.
Nexthdr uint8
// TrafficDirection indicates in which direction Identity is allowed
// communication (egress or ingress).
TrafficDirection uint8
}
// String returns a string representation of the Key
func (k Key) String() string {
return "Identity=" + strconv.FormatUint(uint64(k.Identity), 10) +
",DestPort=" + strconv.FormatUint(uint64(k.DestPort), 10) +
",Nexthdr=" + strconv.FormatUint(uint64(k.Nexthdr), 10) +
",TrafficDirection=" + strconv.FormatUint(uint64(k.TrafficDirection), 10)
}
// IsIngress returns true if the key refers to an ingress policy key
func (k Key) IsIngress() bool {
return k.TrafficDirection == trafficdirection.Ingress.Uint8()
}
// IsEgress returns true if the key refers to an egress policy key
func (k Key) IsEgress() bool {
return k.TrafficDirection == trafficdirection.Egress.Uint8()
}
// PortProtoIsBroader returns true if the receiver Key has broader
// port-protocol than the argument Key. That is a port-protocol
// that covers the argument Key's port-protocol and is larger.
// An equal port-protocol will return false.
func (k Key) PortProtoIsBroader(c Key) bool {
return k.DestPort == 0 && c.DestPort != 0 ||
k.Nexthdr == 0 && c.Nexthdr != 0
}
// PortProtoIsEqual returns true if the port-protocols of the
// two keys are exactly equal.
func (k Key) PortProtoIsEqual(c Key) bool {
return k.DestPort == c.DestPort && k.Nexthdr == c.Nexthdr
}
type Keys map[Key]struct{}
type MapStateOwner interface{}
// MapStateEntry is the configuration associated with a Key in a
// MapState. This is a minimized version of policymap.PolicyEntry.
type MapStateEntry struct {
// The proxy port, in host byte order.
// If 0 (default), there is no proxy redirection for the corresponding
// Key. Any other value signifies proxy redirection.
ProxyPort uint16
// IsDeny is true when the policy should be denied.
IsDeny bool
// hasAuthType is 'DefaultAuthType' when policy has no explicit AuthType set. In this case the
// value of AuthType is derived from more generic entries covering this entry.
hasAuthType HasAuthType
// AuthType is non-zero when authentication is required for the traffic to be allowed.
AuthType AuthType
// DerivedFromRules tracks the policy rules this entry derives from
// In sorted order.
DerivedFromRules labels.LabelArrayList
// Owners collects the keys in the map and selectors in the policy that require this key to be present.
// TODO: keep track which selector needed the entry to be deny, redirect, or just allow.
owners map[MapStateOwner]struct{}
// dependents contains the keys for entries create based on this entry. These entries
// will be deleted once all of the owners are deleted.
dependents Keys
}
// NewMapStateEntry creates a map state entry. If redirect is true, the
// caller is expected to replace the ProxyPort field before it is added to
// the actual BPF map.
// 'cs' is used to keep track of which policy selectors need this entry. If it is 'nil' this entry
// will become sticky and cannot be completely removed via incremental updates. Even in this case
// the entry may be overridden or removed by a deny entry.
func NewMapStateEntry(cs MapStateOwner, derivedFrom labels.LabelArrayList, redirect, deny bool, hasAuth HasAuthType, authType AuthType) MapStateEntry {
var proxyPort uint16
if redirect {
// Any non-zero value will do, as the callers replace this with the
// actual proxy listening port number before the entry is added to the
// actual bpf map.
proxyPort = 1
}
return MapStateEntry{
ProxyPort: proxyPort,
DerivedFromRules: derivedFrom,
IsDeny: deny,
hasAuthType: hasAuth,
AuthType: authType,
owners: map[MapStateOwner]struct{}{cs: {}},
}
}
// AddDependent adds 'key' to the set of dependent keys.
func (e *MapStateEntry) AddDependent(key Key) {
if e.dependents == nil {
e.dependents = make(Keys, 1)
}
e.dependents[key] = struct{}{}
}
// RemoveDependent removes 'key' from the set of dependent keys.
func (e *MapStateEntry) RemoveDependent(key Key) {
delete(e.dependents, key)
// Nil the map when empty. This is mainly to make unit testing easier.
if len(e.dependents) == 0 {
e.dependents = nil
}
}
// HasDependent returns true if the 'key' is contained
// within the set of dependent keys
func (e *MapStateEntry) HasDependent(key Key) bool {
if e.dependents == nil {
return false
}
_, ok := e.dependents[key]
return ok
}
var worldNets = map[identity.NumericIdentity][]*net.IPNet{
identity.ReservedIdentityWorld: {
{IP: net.IPv4zero, Mask: net.CIDRMask(0, net.IPv4len*8)},
{IP: net.IPv6zero, Mask: net.CIDRMask(0, net.IPv6len*8)},
},
identity.ReservedIdentityWorldIPv4: {
{IP: net.IPv4zero, Mask: net.CIDRMask(0, net.IPv4len*8)},
},
identity.ReservedIdentityWorldIPv6: {
{IP: net.IPv6zero, Mask: net.CIDRMask(0, net.IPv6len*8)},
},
}
// getNets returns the most specific CIDR for an identity. For the "World" identity
// it returns both IPv4 and IPv6.
func getNets(identities Identities, ident uint32) []*net.IPNet {
// World identities are handled explicitly for two reasons:
// 1. 'identities' may be nil, but world identities are still expected to be considered
// 2. SelectorCache is not be informed of reserved/world identities in all test cases
id := identity.NumericIdentity(ident)
if id <= identity.ReservedIdentityWorldIPv6 {
return worldNets[id]
}
// CIDR identities have a local scope, so we can skip the rest if id is not of local scope.
if !id.HasLocalScope() || identities == nil {
return nil
}
return identities.GetNetsLocked(id)
}
// NewMapState creates a new MapState interface
func NewMapState(initMap map[Key]MapStateEntry) MapState {
return newMapState(initMap)
}
func newMapState(initMap map[Key]MapStateEntry) *mapState {
m := &mapState{
allows: make(map[Key]MapStateEntry),
denies: make(map[Key]MapStateEntry),
}
for k, v := range initMap {
m.Insert(k, v)
}
return m
}
// Get the MapStateEntry that matches the Key.
func (ms *mapState) Get(k Key) (MapStateEntry, bool) {
v, ok := ms.denies[k]
if ok {
return v, ok
}
v, ok = ms.allows[k]
return v, ok
}
// Insert the Key and matcthing MapStateEntry into the
// MapState
func (ms *mapState) Insert(k Key, v MapStateEntry) {
if v.IsDeny {
delete(ms.allows, k)
ms.denies.insert(k, v)
} else {
delete(ms.denies, k)
ms.allows.insert(k, v)
}
}
// Delete removes the Key an related MapStateEntry.
func (ms *mapState) Delete(k Key) {
delete(ms.allows, k)
delete(ms.denies, k)
}
// ForEach iterates over every Key MapStateEntry and stops when the function
// argument returns false. It returns false iff the iteration was cut short.
func (ms *mapState) ForEach(f func(Key, MapStateEntry) (cont bool)) (complete bool) {
if complete := ms.ForEachAllow(f); !complete {
return complete
}
return ms.ForEachDeny(f)
}
// ForEachAllow iterates over every Key MapStateEntry that isn't a deny and
// stops when the function argument returns false
func (ms *mapState) ForEachAllow(f func(Key, MapStateEntry) (cont bool)) (complete bool) {
for k, v := range ms.allows {
if !f(k, v) {
return false
}
}
return true
}
// ForEachDeny iterates over every Key MapStateEntry that is a deny and
// stops when the function argument returns false
func (ms *mapState) ForEachDeny(f func(Key, MapStateEntry) (cont bool)) (complete bool) {
for k, v := range ms.denies {
if !f(k, v) {
return false
}
}
return true
}
// Len returns the length of the map
func (ms *mapState) Len() int {
return len(ms.allows) + len(ms.denies)
}
// Equals determines if this MapState is equal to the
// argument MapState
func (msA *mapState) Equals(msB MapState) bool {
if msA.Len() != msB.Len() {
return false
}
return msA.ForEach(func(kA Key, vA MapStateEntry) bool {
if vB, ok := msB.Get(kA); ok {
return (&vB).DatapathEqual(&vA)
}
return false
})
}
// Diff returns the string of differences between 'obtained' and 'expected' prefixed with
// '+ ' or '- ' for obtaining something unexpected, or not obtaining the expected, respectively.
// For use in debugging.
func (obtained *mapState) Diff(_ *testing.T, expected MapState) (res string) {
expected.ForEach(func(kE Key, vE MapStateEntry) bool {
if vO, ok := obtained.Get(kE); ok {
if !(&vO).DatapathEqual(&vE) {
res += "- " + kE.String() + ": " + vE.String() + "\n"
res += "+ " + kE.String() + ": " + vO.String() + "\n"
}
} else {
res += "- " + kE.String() + ": " + vE.String() + "\n"
}
return true
})
obtained.ForEach(func(kE Key, vE MapStateEntry) bool {
if vO, ok := expected.Get(kE); !ok {
res += "+ " + kE.String() + ": " + vO.String() + "\n"
}
return true
})
return res
}
// AddDependent adds 'key' to the set of dependent keys.
func (ms *mapState) AddDependent(owner Key, dependent Key, changes ChangeState) {
if e, exists := ms.allows[owner]; exists {
ms.addDependentOnEntry(owner, e, dependent, changes)
} else if e, exists := ms.denies[owner]; exists {
ms.addDependentOnEntry(owner, e, dependent, changes)
}
}
// addDependentOnEntry adds 'dependent' to the set of dependent keys of 'e'.
func (ms *mapState) addDependentOnEntry(owner Key, e MapStateEntry, dependent Key, changes ChangeState) {
if _, exists := e.dependents[dependent]; !exists {
if changes.Old != nil {
changes.Old[owner] = e
}
e.AddDependent(dependent)
ms.Insert(owner, e)
}
}
// RemoveDependent removes 'key' from the list of dependent keys.
// This is called when a dependent entry is being deleted.
// If 'old' is not nil, then old value is added there before any modifications.
func (ms *mapState) RemoveDependent(owner Key, dependent Key, changes ChangeState) {
if e, exists := ms.allows[owner]; exists {
changes.insertOldIfNotExists(owner, e)
e.RemoveDependent(dependent)
delete(ms.denies, owner)
ms.allows.insert(owner, e)
return
}
if e, exists := ms.denies[owner]; exists {
changes.insertOldIfNotExists(owner, e)
e.RemoveDependent(dependent)
delete(ms.allows, owner)
ms.denies.insert(owner, e)
}
}
// Merge adds owners, dependents, and DerivedFromRules from a new 'entry' to an existing
// entry 'e'. 'entry' is not modified.
// IsDeny, ProxyPort, and AuthType are merged by giving precedence to deny over non-deny, proxy
// redirection over no proxy redirection, and explicit auth type over default auth type.
func (e *MapStateEntry) Merge(entry *MapStateEntry) {
// Deny is sticky
if !e.IsDeny {
e.IsDeny = entry.IsDeny
}
// Deny entries have no proxy redirection nor auth requirement
if e.IsDeny {
e.ProxyPort = 0
e.hasAuthType = DefaultAuthType
e.AuthType = AuthTypeDisabled
} else {
// Proxy port takes precedence, but may be updated
if entry.ProxyPort != 0 {
e.ProxyPort = entry.ProxyPort
}
// Explicit auth takes precedence over defaulted one.
if entry.hasAuthType == ExplicitAuthType {
if e.hasAuthType == ExplicitAuthType {
// Numerically higher AuthType takes precedence when both are explicitly defined
if entry.AuthType > e.AuthType {
e.AuthType = entry.AuthType
}
} else {
e.hasAuthType = ExplicitAuthType
e.AuthType = entry.AuthType
}
} else if e.hasAuthType == DefaultAuthType {
e.AuthType = entry.AuthType // new default takes precedence
}
}
if e.owners == nil && len(entry.owners) > 0 {
e.owners = make(map[MapStateOwner]struct{}, len(entry.owners))
}
for k, v := range entry.owners {
e.owners[k] = v
}
// merge dependents
for k := range entry.dependents {
e.AddDependent(k)
}
// merge DerivedFromRules
if len(entry.DerivedFromRules) > 0 {
e.DerivedFromRules.MergeSorted(entry.DerivedFromRules)
}
}
// IsRedirectEntry returns true if e contains a redirect
func (e *MapStateEntry) IsRedirectEntry() bool {
return e.ProxyPort != 0
}
// DatapathEqual returns true of two entries are equal in the datapath's PoV,
// i.e., IsDeny, ProxyPort and AuthType are the same for both entries.
func (e *MapStateEntry) DatapathEqual(o *MapStateEntry) bool {
if e == nil || o == nil {
return e == o
}
return e.IsDeny == o.IsDeny && e.ProxyPort == o.ProxyPort && e.AuthType == o.AuthType
}
// DeepEqual is a manually generated deepequal function, deeply comparing the
// receiver with other. in must be non-nil.
// Defined manually due to deepequal-gen not supporting interface types.
// 'cachedNets' member is ignored in comparison, as it is a cached value and
// makes no functional difference.
func (e *MapStateEntry) DeepEqual(o *MapStateEntry) bool {
if !e.DatapathEqual(o) {
return false
}
if !e.DerivedFromRules.DeepEqual(&o.DerivedFromRules) {
return false
}
if len(e.owners) != len(o.owners) {
return false
}
for k := range o.owners {
if _, exists := e.owners[k]; !exists {
return false
}
}
if len(e.dependents) != len(o.dependents) {
return false
}
for k := range o.dependents {
if _, exists := e.dependents[k]; !exists {
return false
}
}
// ignoring cachedNets
return true
}
// String returns a string representation of the MapStateEntry
func (e MapStateEntry) String() string {
return "ProxyPort=" + strconv.FormatUint(uint64(e.ProxyPort), 10) +
",IsDeny=" + strconv.FormatBool(e.IsDeny) +
",AuthType=" + e.AuthType.String() +
",DerivedFromRules=" + fmt.Sprintf("%v", e.DerivedFromRules)
}
// denyPreferredInsert inserts a key and entry into the map by given preference
// to deny entries, and L3-only deny entries over L3-L4 allows.
// This form may be used when a full policy is computed and we are not yet interested
// in accumulating incremental changes.
// Caller may insert the same MapStateEntry multiple times for different Keys, but all from the same
// owner.
func (ms *mapState) denyPreferredInsert(newKey Key, newEntry MapStateEntry, identities Identities, features policyFeatures) {
// Enforce nil values from NewMapStateEntry
newEntry.dependents = nil
ms.denyPreferredInsertWithChanges(newKey, newEntry, identities, features, ChangeState{})
}
// addKeyWithChanges adds a 'key' with value 'entry' to 'keys' keeping track of incremental changes in 'adds' and 'deletes', and any changed or removed old values in 'old', if not nil.
func (ms *mapState) addKeyWithChanges(key Key, entry MapStateEntry, changes ChangeState) {
// Keep all owners that need this entry so that it is deleted only if all the owners delete their contribution
var datapathEqual bool
oldEntry, exists := ms.Get(key)
if exists {
// Deny entry can only be overridden by another deny entry
if oldEntry.IsDeny && !entry.IsDeny {
return
}
if entry.DeepEqual(&oldEntry) {
return // nothing to do
}
// Save old value before any changes, if desired
if changes.Old != nil {
changes.insertOldIfNotExists(key, oldEntry)
}
// Compare for datapath equalness before merging, as the old entry is updated in
// place!
datapathEqual = oldEntry.DatapathEqual(&entry)
oldEntry.Merge(&entry)
ms.Insert(key, oldEntry)
} else {
// Newly inserted entries must have their own containers, so that they
// remain separate when new owners/dependents are added to existing entries
entry.DerivedFromRules = slices.Clone(entry.DerivedFromRules)
entry.owners = maps.Clone(entry.owners)
entry.dependents = maps.Clone(entry.dependents)
ms.Insert(key, entry)
}
// Record an incremental Add if desired and entry is new or changed
if changes.Adds != nil && (!exists || !datapathEqual) {
changes.Adds[key] = struct{}{}
// Key add overrides any previous delete of the same key
if changes.Deletes != nil {
delete(changes.Deletes, key)
}
}
}
// deleteKeyWithChanges deletes a 'key' from 'keys' keeping track of incremental changes in 'adds' and 'deletes'.
// The key is unconditionally deleted if 'cs' is nil, otherwise only the contribution of this 'cs' is removed.
func (ms *mapState) deleteKeyWithChanges(key Key, owner MapStateOwner, changes ChangeState) {
if entry, exists := ms.Get(key); exists {
// Save old value before any changes, if desired
oldAdded := changes.insertOldIfNotExists(key, entry)
if owner != nil {
// remove the contribution of the given selector only
if _, exists = entry.owners[owner]; exists {
// Remove the contribution of this selector from the entry
delete(entry.owners, owner)
if ownerKey, ok := owner.(Key); ok {
ms.RemoveDependent(ownerKey, key, changes)
}
// key is not deleted if other owners still need it
if len(entry.owners) > 0 {
return
}
} else {
// 'owner' was not found, do not change anything
if oldAdded {
delete(changes.Old, key)
}
return
}
}
// Remove this key from all owners' dependents maps if no owner was given.
// Owner is nil when deleting more specific entries (e.g., L3/L4) when
// adding deny entries that cover them (e.g., L3-deny).
if owner == nil {
for owner := range entry.owners {
if owner != nil {
if ownerKey, ok := owner.(Key); ok {
ms.RemoveDependent(ownerKey, key, changes)
}
}
}
}
// Check if dependent entries need to be deleted as well
for k := range entry.dependents {
ms.deleteKeyWithChanges(k, key, changes)
}
if changes.Deletes != nil {
changes.Deletes[key] = struct{}{}
// Remove a potential previously added key
if changes.Adds != nil {
delete(changes.Adds, key)
}
}
delete(ms.allows, key)
delete(ms.denies, key)
}
}
// identityIsSupersetOf compares two entries and keys to see if the primary identity contains
// the compared identity. This means that either that primary identity is 0 (i.e. it is a superset
// of every other identity), or one of the subnets of the primary identity fully contains or is
// equal to one of the subnets in the compared identity (note:this covers cases like "reserved:world").
func identityIsSupersetOf(primaryIdentity, compareIdentity uint32, identities Identities) bool {
// If the identities are equal then neither is a superset (for the purposes of our business logic).
if primaryIdentity == compareIdentity {
return false
}
// Consider an identity that selects a broader CIDR as a superset of
// an identity that selects a narrower CIDR. For instance, an identity
// corresponding to 192.0.0.0/16 is a superset of the identity that
// corresponds to 192.0.2.3/32.
//
// The reasons we need to do this are surprisingly complex, taking into
// consideration design decisions around the handling of ToFQDNs policy
// and how L4PolicyMap/L4Filter structures cache the policies with
// respect to specific CIDRs. More specifically:
// - At the time of initial L4Filter creation, it is not known which
// specific CIDRs (or corresponding identities) are selected by a
// toFQDNs rule in the policy engine.
// - It is possible to have a CIDR deny rule that should deny peers
// that are allowed by a ToFQDNs statement. The precedence rules in
// the API for such policy conflicts define that the deny should take
// precedence.
// - Consider a case where there is a deny rule for 192.0.0.0/16 with
// an allow rule for cilium.io, and one of the IP addresses for
// cilium.io is 192.0.2.3.
// - If the IP for cilium.io was known at initial policy computation
// time, then we would calculate the MapState from the L4Filters and
// immediately determine that there is a conflict between the
// L4Filter that denies 192.0.0.0/16 vs. the allow for 192.0.2.3.
// From this we could immediately discard the "allow to 192.0.2.3"
// policymap entry during policy calculation. This would satisfy the
// API constraint that deny rules take precedence over allow rules.
// However, this is not the case for ToFQDNs -- the IPs are not known
// until DNS resolution time by the selected application / endpoint.
// - In order to make ToFQDNs policy implementation efficient, it uses
// a shorter incremental policy computation path that attempts to
// directly implement the ToFQDNs allow into a MapState entry without
// reaching back up to the L4Filter layer to iterate all selectors
// to determine traffic reachability for this newly learned IP.
// - As such, when the new ToFQDNs allow for the 192.0.2.3 IP address
// is implemented, we must iterate back through all existing MapState
// entries to determine whether any of the other map entries already
// denies this traffic by virtue of the IP prefix being a superset of
// this new allow. This allows us to ensure that the broader CIDR
// deny semantics are correctly applied when there is a combination
// of CIDR deny rules and ToFQDNs allow rules.
//
// An alternative to this approach might be to change the ToFQDNs
// policy calculation layer to reference back to the L4Filter layer,
// and perhaps introduce additional CIDR caching somewhere there so
// that this policy computation can be efficient while handling DNS
// responses. As of the writing of this message, such there is no
// active proposal to implement this proposal. As a result, any time
// there is an incremental policy update for a new map entry, we must
// iterate through all entries in the map and re-evaluate superset
// relationships for deny entries to ensure that policy precedence is
// correctly implemented between the new and old entries, taking into
// account whether the identities may represent CIDRs that have a
// superset relationship.
return primaryIdentity == 0 && compareIdentity != 0 ||
ip.NetsContainsAny(getNets(identities, primaryIdentity),
getNets(identities, compareIdentity))
}
// protocolsMatch checks to see if two given keys match on protocol.
// This means that either one of them covers all protocols or they
// are equal.
func protocolsMatch(a, b Key) bool {
return a.Nexthdr == 0 || b.Nexthdr == 0 || a.Nexthdr == b.Nexthdr
}
// RevertChanges undoes changes to 'keys' as indicated by 'changes.adds' and 'changes.old' collected via
// denyPreferredInsertWithChanges().
func (ms *mapState) RevertChanges(changes ChangeState) {
for k := range changes.Adds {
delete(ms.allows, k)
delete(ms.denies, k)
}
// 'old' contains all the original values of both modified and deleted entries
for k, v := range changes.Old {
ms.Insert(k, v)
}
}
// denyPreferredInsertWithChanges contains the most important business logic for policy insertions. It inserts
// a key and entry into the map by giving preference to deny entries, and L3-only deny entries over L3-L4 allows.
// Incremental changes performed are recorded in 'adds' and 'deletes', if not nil.
// See https://docs.google.com/spreadsheets/d/1WANIoZGB48nryylQjjOw6lKjI80eVgPShrdMTMalLEw#gid=2109052536 for details
func (ms *mapState) denyPreferredInsertWithChanges(newKey Key, newEntry MapStateEntry, identities Identities, features policyFeatures, changes ChangeState) {
// Skip deny rules processing if the policy in this direction has no deny rules
if !features.contains(denyRules) {
ms.authPreferredInsert(newKey, newEntry, features, changes)
return
}
allCpy := allKey
allCpy.TrafficDirection = newKey.TrafficDirection
// If we have a deny "all" we don't accept any kind of map entry.
if _, ok := ms.denies[allCpy]; ok {
return
}
if newEntry.IsDeny {
ms.ForEachAllow(func(k Key, v MapStateEntry) bool {
// Protocols and traffic directions that don't match ensure that the policies
// do not interact in anyway.
if newKey.TrafficDirection != k.TrafficDirection || !protocolsMatch(newKey, k) {
return true
}
if identityIsSupersetOf(k.Identity, newKey.Identity, identities) {
if newKey.PortProtoIsBroader(k) {
// If this iterated-allow-entry is a superset of the new-entry
// and it has a more specific port-protocol than the new-entry
// then an additional copy of the new-entry with the more
// specific port-protocol of the iterated-allow-entry must be inserted.
newKeyCpy := newKey
newKeyCpy.DestPort = k.DestPort
newKeyCpy.Nexthdr = k.Nexthdr
l3l4DenyEntry := NewMapStateEntry(newKey, newEntry.DerivedFromRules, false, true, DefaultAuthType, AuthTypeDisabled)
ms.addKeyWithChanges(newKeyCpy, l3l4DenyEntry, changes)
// L3-only entries can be deleted incrementally so we need to track their
// effects on other entries so that those effects can be reverted when the
// identity is removed.
newEntry.AddDependent(newKeyCpy)
}
} else if (newKey.Identity == k.Identity ||
identityIsSupersetOf(newKey.Identity, k.Identity, identities)) &&
(newKey.PortProtoIsBroader(k) || newKey.PortProtoIsEqual(k)) {
// If the new-entry is a superset (or equal) of the iterated-allow-entry and
// the new-entry has a broader (or equal) port-protocol then we
// should delete the iterated-allow-entry
ms.deleteKeyWithChanges(k, nil, changes)
}
return true
})
bailed := false
ms.ForEachDeny(func(k Key, v MapStateEntry) bool {
// Protocols and traffic directions that don't match ensure that the policies
// do not interact in anyway.
if newKey.TrafficDirection != k.TrafficDirection || !protocolsMatch(newKey, k) {
return true
}
if (newKey.Identity == k.Identity ||
identityIsSupersetOf(k.Identity, newKey.Identity, identities)) &&
k.DestPort == 0 && k.Nexthdr == 0 &&
!v.HasDependent(newKey) {
// If this iterated-deny-entry is a supserset (or equal) of the new-entry and
// the iterated-deny-entry is an L3-only policy then we
// should not insert the new entry (as long as it is not one
// of the special L4-only denies we created to cover the special
// case of a superset-allow with a more specific port-protocol).
//
// NOTE: This condition could be broader to reject more deny entries,
// but there *may* be performance tradeoffs.
bailed = true
return false
} else if (newKey.Identity == k.Identity ||
identityIsSupersetOf(newKey.Identity, k.Identity, identities)) &&
newKey.DestPort == 0 && newKey.Nexthdr == 0 &&
!newEntry.HasDependent(k) {
// If this iterated-deny-entry is a subset (or equal) of the new-entry and
// the new-entry is an L3-only policy then we
// should delete the iterated-deny-entry (as long as it is not one
// of the special L4-only denies we created to cover the special
// case of a superset-allow with a more specific port-protocol).
//
// NOTE: This condition could be broader to reject more deny entries,
// but there *may* be performance tradeoffs.
ms.deleteKeyWithChanges(k, nil, changes)
}
return true
})
if !bailed {
ms.addKeyWithChanges(newKey, newEntry, changes)
}
} else {
// NOTE: We do not delete redundant allow entries.
bailed := false
ms.ForEachDeny(func(k Key, v MapStateEntry) bool {
// Protocols and traffic directions that don't match ensure that the policies
// do not interact in anyway.
if newKey.TrafficDirection != k.TrafficDirection || !protocolsMatch(newKey, k) {
return true
}
if identityIsSupersetOf(newKey.Identity, k.Identity, identities) {
if k.PortProtoIsBroader(newKey) {
// If the new-entry is *only* superset of the iterated-deny-entry
// and the new-entry has a more specific port-protocol than the
// iterated-deny-entry then an additional copy of the iterated-deny-entry
// with the more specific port-porotocol of the new-entry must
// be added.
denyKeyCpy := k
denyKeyCpy.DestPort = newKey.DestPort
denyKeyCpy.Nexthdr = newKey.Nexthdr
l3l4DenyEntry := NewMapStateEntry(k, v.DerivedFromRules, false, true, DefaultAuthType, AuthTypeDisabled)
ms.addKeyWithChanges(denyKeyCpy, l3l4DenyEntry, changes)
// L3-only entries can be deleted incrementally so we need to track their
// effects on other entries so that those effects can be reverted when the
// identity is removed.
ms.addDependentOnEntry(k, v, denyKeyCpy, changes)
}
} else if (k.Identity == newKey.Identity ||
identityIsSupersetOf(k.Identity, newKey.Identity, identities)) &&
(k.PortProtoIsBroader(newKey) || k.PortProtoIsEqual(newKey)) &&
!v.HasDependent(newKey) {
// If the iterated-deny-entry is a superset (or equal) of the new-entry and has a
// broader (or equal) port-protocol than the new-entry then the new
// entry should not be inserted.
bailed = true
return false
}
return true
})
if !bailed {
ms.authPreferredInsert(newKey, newEntry, features, changes)
}
}
}
// IsSuperSetOf checks if the receiver Key is a superset of the argument Key, and returns a
// specificity score of the receiver key (higher score is more specific), if so. Being a superset
// means that the receiver key would match all the traffic of the argument key without being the
// same key. Hence, a L3-only key is not a superset of a L4-only key, as the L3-only key would match
// the traffic for the given L3 only, while the L4-only key matches traffic on the given port for
// all the L3's.
// Returns 0 if the receiver key is not a superset of the argument key.
//
// Specificity score for all possible superset wildcard patterns. Datapath requires proto to be specified if port is specified.
// x. L3/proto/port
// 1. */*/*
// 2. */proto/*
// 3. */proto/port
// 4. ID/*/*
// 5. ID/proto/*
// ( ID/proto/port can not be superset of anything )
func (k Key) IsSuperSetOf(other Key) int {
if k.TrafficDirection != other.TrafficDirection {
return 0 // TrafficDirection must match for 'k' to be a superset of 'other'
}
if k.Identity == 0 {
if other.Identity == 0 {
if k.Nexthdr == 0 { // k.DestPort == 0 is implied
if other.Nexthdr != 0 {
return 1 // */*/* is a superset of */proto/x
} // else both are */*/*
} else if k.Nexthdr == other.Nexthdr {
if k.DestPort == 0 && other.DestPort != 0 {
return 2 // */proto/* is a superset of */proto/port
} // else more specific or different ports
} // else more specific or different protocol
} else {
// Wildcard L3 is a superset of a specific L3 only if wildcard L3 is also wildcard L4, or the L4's match between the keys
if k.Nexthdr == 0 { // k.DestPort == 0 is implied
return 1 // */*/* is a superset of ID/x/x
} else if k.Nexthdr == other.Nexthdr {
if k.DestPort == 0 {
return 2 // */proto/* is a superset of ID/proto/x
} else if k.DestPort == other.DestPort {
return 3 // */proto/port is a superset of ID/proto/port
} // else more specific or different ports
} // else more specific or different protocol
}
} else if k.Identity == other.Identity {
if k.Nexthdr == 0 {
if other.Nexthdr != 0 {
return 4 // ID/*/* is a superset of ID/proto/x
} // else both are ID/*/*
} else if k.Nexthdr == other.Nexthdr {
if k.DestPort == 0 && other.DestPort != 0 {
return 5 // ID/proto/* is a superset of ID/proto/port
} // else more specific or different ports
} // else more specific or different protocol
} // else more specific or different identity
return 0
}
// authPreferredInsert applies AuthType of a more generic entry to more specific entries, if not
// explicitly specified.
//
// This function is expected to be called for a map insertion after deny
// entry evaluation. If there is a map entry that is a superset of 'newKey'
// which denies traffic matching 'newKey', then this function should not be called.
func (ms *mapState) authPreferredInsert(newKey Key, newEntry MapStateEntry, features policyFeatures, changes ChangeState) {
if features.contains(authRules) {
if newEntry.hasAuthType == DefaultAuthType {
// New entry has a default auth type.
// Fill in the AuthType from more generic entries with an explicit auth type
maxSpecificity := 0
l3l4State := newMapState(nil)
ms.ForEachAllow(func(k Key, v MapStateEntry) bool {
// Only consider the same Traffic direction
if newKey.TrafficDirection != k.TrafficDirection {
return true
}
// Nothing to be done if entry has default AuthType
if v.hasAuthType == DefaultAuthType {
return true
}
// Find out if 'k' is an identity-port-proto superset of 'newKey'
if specificity := k.IsSuperSetOf(newKey); specificity > 0 {
if specificity > maxSpecificity {
// AuthType from the most specific superset is
// applied to 'newEntry'
newEntry.AuthType = v.AuthType
maxSpecificity = specificity
}
} else {
// Check if a new L3L4 entry must be created due to L3-only
// 'k' specifying an explicit AuthType and an L4-only 'newKey' not
// having an explicit AuthType. In this case AuthType should
// only override the AuthType for the L3 & L4 combination,
// not L4 in general.
//
// These need to be collected and only added if there is a
// superset key of newKey with an explicit auth type. In
// this case AuthType of the new L4-only entry was
// overridden by a more generic entry and 'max_specificity >
// 0' after the loop.
if k.Identity != 0 && k.Nexthdr == 0 && newKey.Identity == 0 && newKey.Nexthdr != 0 {
newKeyCpy := k
newKeyCpy.DestPort = newKey.DestPort
newKeyCpy.Nexthdr = newKey.Nexthdr
l3l4AuthEntry := NewMapStateEntry(k, v.DerivedFromRules, false, false, DefaultAuthType, v.AuthType)
l3l4AuthEntry.DerivedFromRules.MergeSorted(newEntry.DerivedFromRules)
l3l4State.allows[newKeyCpy] = l3l4AuthEntry
}
}
return true
})
// Add collected L3/L4 entries if the auth type of the new entry was not
// overridden by a more generic entry. If it was overridden, the new L3L4
// entries are not needed as the L4-only entry with an overridden AuthType
// will be matched before the L3-only entries in the datapath.
if maxSpecificity == 0 {