Repository: cilium/cilium
Pull request #14321 (2020-12-09 08:26:05)

policy: Track selectors that contribute to MapStateEntries
Note to backporters: This will be backported by the author, as merge
conflicts are expected.

Track which selectors in policy require a specific bpf policy map key to
be present, and keep policy entries in the map as long as any selector
requires it's presence. Without this it is possible for a timed-out
DNS cache entry to clear a policy cache key that is still required by
another selector (FQDN or CIDR).

To implement this, each MapStateEntry is now equipped with a set of
(cached) selectors through which the policy map key/value was
added. 'nil' has the special significance that it is used as the
CachedSelector in cases where the policy map entry is added due to
some administrative or configuration reason. Currently incremental
updates will never remove such entries.

Incremental policy updates now simply collect the requested map
changes. When the endpoint then pulls the changes they are first
applied the desired policy map (MapState), while tallying which
selectors still need the map entries to be present. The actual bpf map
diffs are recorded based on the total count of selectors on each map
entry.

Signed-off-by: Jarno Rajahalme <jarno@covalent.io>

```release-note
Bug where a timed out DNS cache entry caused access to an IP via another name being denied is fixed.
```


jrajahalme: test-me-please
jrajahalme: test-me-please
jrajahalme: test-me-please
jrajahalme: test-me-please
jrajahalme: test-me-please
jrajahalme: retest-netnext
jrajahalme: retest-net-next
jrajahalme: retest-runtime
jrajahalme: Known flake (#13275) on netnext run.

Patch:
diff --git a/pkg/endpoint/bpf.go b/pkg/endpoint/bpf.go
index 7982fdd146..9619dc7307 100644
--- a/pkg/endpoint/bpf.go
+++ b/pkg/endpoint/bpf.go
@@ -421,7 +421,7 @@ func (e *Endpoint) addVisibilityRedirects(ingress bool, desiredRedirects map[str
 				labels.NewLabel(policy.LabelKeyPolicyDerivedFrom, policy.LabelVisibilityAnnotation, labels.LabelSourceReserved),
 			},
 		}
-		entry := policy.NewMapStateEntry(derivedFrom, true, false)
+		entry := policy.NewMapStateEntry(nil, derivedFrom, true, false)
 		entry.ProxyPort = redirectPort
 
 		e.desiredPolicy.PolicyMapState[newKey] = entry
@@ -1106,11 +1106,6 @@ func (e *Endpoint) deletePolicyKey(keyToDelete policy.Key, incremental bool, had
 	// Operation was successful, remove from realized state.
 	delete(e.realizedPolicy.PolicyMapState, keyToDelete)
 
-	// Incremental updates need to update the desired state as well.
-	if incremental && e.desiredPolicy != e.realizedPolicy {
-		delete(e.desiredPolicy.PolicyMapState, keyToDelete)
-	}
-
 	e.policyDebug(logrus.Fields{
 		logfields.BPFMapKey:   keyToDelete,
 		logfields.BPFMapValue: entry,
@@ -1146,11 +1141,6 @@ func (e *Endpoint) addPolicyKey(keyToAdd policy.Key, entry policy.MapStateEntry,
 	// Operation was successful, add to realized state.
 	e.realizedPolicy.PolicyMapState[keyToAdd] = entry
 
-	// Incremental updates need to update the desired state as well.
-	if incremental && e.desiredPolicy != e.realizedPolicy {
-		e.desiredPolicy.PolicyMapState[keyToAdd] = entry
-	}
-
 	e.policyDebug(logrus.Fields{
 		logfields.BPFMapKey:   keyToAdd,
 		logfields.BPFMapValue: entry,
@@ -1200,6 +1190,9 @@ func (e *Endpoint) applyPolicyMapChanges() (proxyChanges bool, err error) {
 	//  collected on the newly computed desired policy, which is
 	//  not fully realized yet. This is why we get the map changes
 	//  from the desired policy here.
+	//  ConsumeMapChanges() applies the incremental updates to the
+	//  desired policy and only returns changes that need to be
+	//  applied to the Endpoint's bpf policy map.
 	adds, deletes := e.desiredPolicy.ConsumeMapChanges()
 
 	// Add policy map entries before deleting to avoid transient drops
@@ -1314,10 +1307,6 @@ func (e *Endpoint) syncPolicyMapWithDump() error {
 		e.realizedPolicy.PolicyMapState = make(policy.MapState)
 	}
 
-	if e.desiredPolicy.PolicyMapState == nil {
-		e.desiredPolicy.PolicyMapState = make(policy.MapState)
-	}
-
 	if e.policyMap == nil {
 		return fmt.Errorf("not syncing PolicyMap state for endpoint because PolicyMap is nil")
 	}
diff --git a/pkg/policy/l4.go b/pkg/policy/l4.go
index 2605a8210d..87b3ecdedf 100644
--- a/pkg/policy/l4.go
+++ b/pkg/policy/l4.go
@@ -387,7 +387,7 @@ func (l4Filter *L4Filter) ToMapState(policyOwner PolicyOwner, direction trafficd
 			}
 		}
 
-		entry := NewMapStateEntry(l4Filter.DerivedFromRules, currentRule.IsRedirect(), isDenyRule)
+		entry := NewMapStateEntry(cs, l4Filter.DerivedFromRules, currentRule.IsRedirect(), isDenyRule)
 		if cs.IsWildcard() {
 			keyToAdd.Identity = 0
 			keysToAdd.DenyPreferredInsert(keyToAdd, entry)
@@ -447,8 +447,8 @@ func (l4 *L4Filter) IdentitySelectionUpdated(selector CachedSelector, added, del
 
 	// Push endpoint policy changes.
 	//
-	// `l4.policy` is set to nil when the filter is detached so
-	// that we could not push updates on a stale policy.
+	// `l4.policy` is nil when the filter is detached so
+	// that we could not push updates on an unstable policy.
 	l4Policy := (*L4Policy)(atomic.LoadPointer(&l4.policy))
 	if l4Policy != nil {
 		direction := trafficdirection.Egress
@@ -458,7 +458,7 @@ func (l4 *L4Filter) IdentitySelectionUpdated(selector CachedSelector, added, del
 		l7Rules := l4.L7RulesPerSelector[selector]
 		isRedirect := l7Rules.IsRedirect()
 		isDeny := l7Rules != nil && l7Rules.IsDeny
-		l4Policy.AccumulateMapChanges(added, deleted, l4, direction, isRedirect, isDeny)
+		l4Policy.AccumulateMapChanges(selector, added, deleted, l4, direction, isRedirect, isDeny)
 	}
 }
 
@@ -637,11 +637,15 @@ func (l4 *L4Filter) removeSelectors(selectorCache *SelectorCache) {
 
 // detach releases the references held in the L4Filter and must be called before
 // the filter is left to be garbage collected.
+// L4Filter may still be accessed concurrently after it has been detached.
 func (l4 *L4Filter) detach(selectorCache *SelectorCache) {
 	l4.removeSelectors(selectorCache)
 	l4.attach(nil, nil)
 }
 
+// attach signifies that the L4Filter is ready and reacheable for updates
+// from SelectorCache. L4Filter is read-only after this is called,
+// multiple goroutines will be reading the fields from that point on.
 func (l4 *L4Filter) attach(ctx PolicyContext, l4Policy *L4Policy) {
 	// All rules have been added to the L4Filter at this point.
 	// Sort the rules label array list for more efficient equality comparison.
@@ -775,6 +779,7 @@ func (l4 L4PolicyMap) Detach(selectorCache *SelectorCache) {
 }
 
 // Attach makes all the L4Filters to point back to the L4Policy that contains them.
+// This is done before the L4PolicyMap is exposed to concurrent access.
 func (l4 L4PolicyMap) Attach(ctx PolicyContext, l4Policy *L4Policy) {
 	for _, f := range l4 {
 		f.attach(ctx, l4Policy)
@@ -932,7 +937,7 @@ func (l4 *L4Policy) insertUser(user *EndpointPolicy) {
 //
 // The caller is responsible for making sure the same identity is not
 // present in both 'adds' and 'deletes'.
-func (l4 *L4Policy) AccumulateMapChanges(adds, deletes []identity.NumericIdentity, l4Filter *L4Filter,
+func (l4 *L4Policy) AccumulateMapChanges(cs CachedSelector, adds, deletes []identity.NumericIdentity, l4Filter *L4Filter,
 	direction trafficdirection.TrafficDirection, redirect, isDeny bool) {
 	port := uint16(l4Filter.Port)
 	proto := uint8(l4Filter.U8Proto)
@@ -955,7 +960,7 @@ func (l4 *L4Policy) AccumulateMapChanges(adds, deletes []identity.NumericIdentit
 				continue
 			}
 		}
-		epPolicy.policyMapChanges.AccumulateMapChanges(adds, deletes, port, proto, direction, redirect, isDeny, derivedFrom)
+		epPolicy.policyMapChanges.AccumulateMapChanges(cs, adds, deletes, port, proto, direction, redirect, isDeny, derivedFrom)
 	}
 }
 
diff --git a/pkg/policy/mapstate.go b/pkg/policy/mapstate.go
index c0c3d53aeb..88f6550b2a 100644
--- a/pkg/policy/mapstate.go
+++ b/pkg/policy/mapstate.go
@@ -94,17 +94,24 @@ type MapStateEntry struct {
 	// Key. Any other value signifies proxy redirection.
 	ProxyPort uint16
 
+	// IsDeny is true when the policy should be denied.
+	IsDeny bool
+
 	// DerivedFromRules tracks the policy rules this entry derives from
 	DerivedFromRules labels.LabelArrayList
 
-	// IsDeny is true when the policy should be denied.
-	IsDeny bool
+	// Selectors collects the 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.
+	selectors map[CachedSelector]struct{}
 }
 
 // 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.
-func NewMapStateEntry(derivedFrom labels.LabelArrayList, redirect, deny bool) MapStateEntry {
+// '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 CachedSelector, derivedFrom labels.LabelArrayList, redirect, deny bool) MapStateEntry {
 	var proxyPort uint16
 	if redirect {
 		// Any non-zero value will do, as the callers replace this with the
@@ -117,6 +124,14 @@ func NewMapStateEntry(derivedFrom labels.LabelArrayList, redirect, deny bool) Ma
 		ProxyPort:        proxyPort,
 		DerivedFromRules: derivedFrom,
 		IsDeny:           deny,
+		selectors:        map[CachedSelector]struct{}{cs: {}},
+	}
+}
+
+// MergeSelectors adds selectors from entry 'b' to 'e'. 'b' is not modified.
+func (e *MapStateEntry) MergeSelectors(b *MapStateEntry) {
+	for cs, v := range b.selectors {
+		e.selectors[cs] = v
 	}
 }
 
@@ -142,7 +157,77 @@ func (e MapStateEntry) String() string {
 
 // 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.
 func (keys MapState) DenyPreferredInsert(newKey Key, newEntry MapStateEntry) {
+	keys.denyPreferredInsertWithChanges(newKey, newEntry, nil, nil)
+}
+
+// addKeyWithChanges adds a 'key' with value 'entry' to 'keys' keeping track of incremental changes in 'adds' and 'deletes'
+func (keys MapState) addKeyWithChanges(key Key, entry MapStateEntry, adds, deletes MapState) {
+	// Keep all selectors that need this entry so that it is deleted only if all the selectors delete their contribution
+	updatedEntry := entry
+	oldEntry, exists := keys[key]
+	if exists {
+		// keep the existing selectors map of the old entry
+		updatedEntry.selectors = oldEntry.selectors
+	} else if len(entry.selectors) > 0 {
+		// create a new selectors map
+		updatedEntry.selectors = make(map[CachedSelector]struct{}, len(entry.selectors))
+	} else {
+		// Keep the map as nil when empty. This makes a difference for unit testing only.
+		// MergeSelectors below becomes a no-op as 'entry' is empty.
+		updatedEntry.selectors = nil
+	}
+
+	// TODO: Do we need to merge labels as well?
+	// Merge new selectors to the updated entry without modifying 'entry' as it is being reused by the caller
+	updatedEntry.MergeSelectors(&entry)
+	// Update (or insert) the entry
+	keys[key] = updatedEntry
+
+	// Record an incremental Add if desired and entry is new or changed
+	if adds != nil && (!exists || !oldEntry.DatapathEqual(&entry)) {
+		updatedEntry.selectors = nil
+		adds[key] = updatedEntry // copy w/o selectors
+		// Key add overrides any previous delete of the same key
+		if deletes != nil {
+			delete(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 (keys MapState) deleteKeyWithChanges(key Key, cs CachedSelector, adds, deletes MapState) {
+	if entry, exists := keys[key]; exists {
+		if cs != nil {
+			// remove the contribution of the given selector only
+			if _, exists = entry.selectors[cs]; exists {
+				// Remove the contribution of this selector from the entry
+				delete(entry.selectors, cs)
+				// key is not deleted if other selectors still need it
+				if len(entry.selectors) > 0 {
+					return
+				}
+			}
+		}
+		if deletes != nil {
+			entry.selectors = nil
+			deletes[key] = entry // copy w/o selectors
+			// Remove a potential previously added key
+			if adds != nil {
+				delete(adds, key)
+			}
+		}
+		delete(keys, key)
+	}
+}
+
+// denyPreferredInsertWithChanges 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.
+func (keys MapState) denyPreferredInsertWithChanges(newKey Key, newEntry MapStateEntry, adds, deletes MapState) {
 	allCpy := allKey
 	allCpy.TrafficDirection = newKey.TrafficDirection
 	// If we have a deny "all" we don't accept any kind of map entry
@@ -163,7 +248,7 @@ func (keys MapState) DenyPreferredInsert(newKey Key, newEntry MapStateEntry) {
 					newKeyCpy := newKey
 					newKeyCpy.DestPort = k.DestPort
 					newKeyCpy.Nexthdr = k.Nexthdr
-					keys[newKeyCpy] = newEntry
+					keys.addKeyWithChanges(newKeyCpy, newEntry, adds, deletes)
 
 					l4OnlyAllows[k] = v
 				}
@@ -178,7 +263,7 @@ func (keys MapState) DenyPreferredInsert(newKey Key, newEntry MapStateEntry) {
 					kCpy := k
 					kCpy.Identity = 0
 					if _, ok := l4OnlyAllows[kCpy]; !ok {
-						delete(keys, k)
+						keys.deleteKeyWithChanges(k, nil, adds, deletes)
 					}
 				}
 			}
@@ -187,7 +272,7 @@ func (keys MapState) DenyPreferredInsert(newKey Key, newEntry MapStateEntry) {
 			// from the map state for that direction.
 			for k := range keys {
 				if k.TrafficDirection == allCpy.TrafficDirection {
-					delete(keys, k)
+					keys.deleteKeyWithChanges(k, nil, adds, deletes)
 				}
 			}
 		default:
@@ -203,7 +288,7 @@ func (keys MapState) DenyPreferredInsert(newKey Key, newEntry MapStateEntry) {
 			}
 		}
 
-		keys[newKey] = newEntry
+		keys.addKeyWithChanges(newKey, newEntry, adds, deletes)
 		return
 	} else if newKey.Identity == 0 && newKey.DestPort != 0 {
 		// case for an existing deny L3-only and we are inserting allow L4
@@ -213,11 +298,11 @@ func (keys MapState) DenyPreferredInsert(newKey Key, newEntry MapStateEntry) {
 					// create a deny L3-L4 with the same deny L3
 					newKeyCpy := newKey
 					newKeyCpy.Identity = k.Identity
-					keys[newKeyCpy] = v
+					keys.addKeyWithChanges(newKeyCpy, v, adds, deletes)
 				}
 			}
 		}
-		keys[newKey] = newEntry
+		keys.addKeyWithChanges(newKey, newEntry, adds, deletes)
 		return
 	}
 	// branch for adding a new allow L3-L4
@@ -231,21 +316,30 @@ func (keys MapState) DenyPreferredInsert(newKey Key, newEntry MapStateEntry) {
 		return
 	}
 
-	keys.RedirectPreferredInsert(newKey, newEntry)
+	keys.RedirectPreferredInsert(newKey, newEntry, adds, deletes)
 }
 
 // RedirectPreferredInsert inserts a new entry giving priority to L7-redirects by
 // not overwriting a L7-redirect entry with a non-redirect entry.
-func (keys MapState) RedirectPreferredInsert(key Key, entry MapStateEntry) {
-	if !entry.IsRedirectEntry() {
-		if _, ok := keys[key]; ok {
-			// Key already exist, keep the existing entry so that
-			// a redirect entry is never overwritten by a non-redirect
-			// entry
-			return
+func (keys MapState) RedirectPreferredInsert(key Key, entry MapStateEntry, adds, deletes MapState) {
+	// Do not overwrite the entry, but only merge selectors if the old entry is a deny or redirect.
+	// This prevents an existing deny or redirect being overridden by a non-deny or a non-redirect.
+	if oldEntry, exists := keys[key]; exists && (oldEntry.IsRedirectEntry() || oldEntry.IsDeny) {
+		oldEntry.MergeSelectors(&entry)
+		keys[key] = oldEntry
+		// For compatibility with old redirect management code we'll have to pass on
+		// redirect entry if the oldEntry is also a redirect, even if they are equal.
+		// We store the new entry here, the proxy port of it will be fixed up before
+		// insertion to the bpf map.
+		// TODO: Remove this hack when not needed any more.
+		if adds != nil && entry.IsRedirectEntry() && oldEntry.IsRedirectEntry() {
+			entry.selectors = nil
+			adds[key] = entry // copy w/o selectors
 		}
+		return
 	}
-	keys[key] = entry
+	// Otherwise write the entry to the map
+	keys.addKeyWithChanges(key, entry, adds, deletes)
 }
 
 // DetermineAllowLocalhostIngress determines whether communication should be allowed
@@ -259,13 +353,13 @@ func (keys MapState) DetermineAllowLocalhostIngress() {
 				labels.NewLabel(LabelKeyPolicyDerivedFrom, LabelAllowLocalHostIngress, labels.LabelSourceReserved),
 			},
 		}
-		es := NewMapStateEntry(derivedFrom, false, false)
+		es := NewMapStateEntry(nil, derivedFrom, false, false)
 		keys.DenyPreferredInsert(localHostKey, es)
 		if !option.Config.EnableRemoteNodeIdentity {
 			var isHostDenied bool
 			v, ok := keys[localHostKey]
 			isHostDenied = ok && v.IsDeny
-			es := NewMapStateEntry(derivedFrom, false, isHostDenied)
+			es := NewMapStateEntry(nil, derivedFrom, false, isHostDenied)
 			keys.DenyPreferredInsert(localRemoteNodeKey, es)
 		}
 	}
@@ -287,7 +381,7 @@ func (keys MapState) AllowAllIdentities(ingress, egress bool) {
 				labels.NewLabel(LabelKeyPolicyDerivedFrom, LabelAllowLocalHostIngress, labels.LabelSourceReserved),
 			},
 		}
-		keys[keyToAdd] = NewMapStateEntry(derivedFrom, false, false)
+		keys[keyToAdd] = NewMapStateEntry(nil, derivedFrom, false, false)
 	}
 	if egress {
 		keyToAdd := Key{
@@ -301,7 +395,7 @@ func (keys MapState) AllowAllIdentities(ingress, egress bool) {
 				labels.NewLabel(LabelKeyPolicyDerivedFrom, LabelAllowAnyEgress, labels.LabelSourceReserved),
 			},
 		}
-		keys[keyToAdd] = NewMapStateEntry(derivedFrom, false, false)
+		keys[keyToAdd] = NewMapStateEntry(nil, derivedFrom, false, false)
 	}
 }
 
@@ -388,20 +482,21 @@ func (pms MapState) getIdentities(log *logrus.Logger, denied bool) (ingIdentitie
 // and deletes. 'mutex' must be held for any access.
 type MapChanges struct {
 	mutex   lock.Mutex
-	adds    MapState
-	deletes MapState
+	changes []MapChange
+}
+
+type MapChange struct {
+	add   bool // false deletes
+	key   Key
+	value MapStateEntry
 }
 
 // AccumulateMapChanges accumulates the given changes to the
-// MapChanges, updating both maps for each add and delete, as
-// applicable.
+// MapChanges.
 //
 // The caller is responsible for making sure the same identity is not
-// present in both 'adds' and 'deletes'.  Across multiple calls we
-// maintain the adds and deletes within the MapChanges are disjoint in
-// cases where an identity is first added and then deleted, or first
-// deleted and then added.
-func (mc *MapChanges) AccumulateMapChanges(adds, deletes []identity.NumericIdentity,
+// present in both 'adds' and 'deletes'.
+func (mc *MapChanges) AccumulateMapChanges(cs CachedSelector, adds, deletes []identity.NumericIdentity,
 	port uint16, proto uint8, direction trafficdirection.TrafficDirection,
 	redirect, isDeny bool, derivedFrom labels.LabelArrayList) {
 	key := Key{
@@ -413,10 +508,11 @@ func (mc *MapChanges) AccumulateMapChanges(adds, deletes []identity.NumericIdent
 		TrafficDirection: direction.Uint8(),
 	}
 
-	value := NewMapStateEntry(derivedFrom, redirect, isDeny)
+	value := NewMapStateEntry(cs, derivedFrom, redirect, isDeny)
 
 	if option.Config.Debug {
 		log.WithFields(logrus.Fields{
+			logfields.EndpointSelector: cs,
 			logfields.AddedPolicyID:    adds,
 			logfields.DeletedPolicyID:  deletes,
 			logfields.Port:             port,
@@ -427,45 +523,38 @@ func (mc *MapChanges) AccumulateMapChanges(adds, deletes []identity.NumericIdent
 	}
 
 	mc.mutex.Lock()
-	if len(adds) > 0 {
-		if mc.adds == nil {
-			mc.adds = make(MapState)
-		}
-		for _, id := range adds {
-			key.Identity = id.Uint32()
-			// insert but do not allow non-redirect entries to overwrite a redirect entry
-			mc.adds.DenyPreferredInsert(key, value)
-
-			// Remove a potential previously deleted key
-			if mc.deletes != nil {
-				delete(mc.deletes, key)
-			}
-		}
+	for _, id := range adds {
+		key.Identity = id.Uint32()
+		mc.changes = append(mc.changes, MapChange{true, key, value})
 	}
-	if len(deletes) > 0 {
-		if mc.deletes == nil {
-			mc.deletes = make(MapState)
-		}
-		for _, id := range deletes {
-			key.Identity = id.Uint32()
-			mc.deletes[key] = value
-			// Remove a potential previously added key
-			if mc.adds != nil {
-				delete(mc.adds, key)
-			}
-		}
+	for _, id := range deletes {
+		key.Identity = id.Uint32()
+		mc.changes = append(mc.changes, MapChange{false, key, value})
 	}
 	mc.mutex.Unlock()
 }
 
-// consumeMapChanges transfers the changes from MapChanges to the caller.
-// May return nil maps.
-func (mc *MapChanges) consumeMapChanges() (adds, deletes MapState) {
+// consumeMapChanges transfers the incremental changes from MapChanges to the caller,
+// while applying the changes to PolicyMapState.
+func (mc *MapChanges) consumeMapChanges(policyMapState MapState) (adds, deletes MapState) {
 	mc.mutex.Lock()
-	adds = mc.adds
-	mc.adds = nil
-	deletes = mc.deletes
-	mc.deletes = nil
+	adds = make(MapState, len(mc.changes))
+	deletes = make(MapState, len(mc.changes))
+
+	for i := range mc.changes {
+		if mc.changes[i].add {
+			// insert but do not allow non-redirect entries to overwrite a redirect entry,
+			// nor allow non-deny entries to overwrite deny entries.
+			// Collect the incremental changes to the overall state in 'mc.adds' and 'mc.deletes'.
+			policyMapState.denyPreferredInsertWithChanges(mc.changes[i].key, mc.changes[i].value, adds, deletes)
+		} else {
+			// Delete the contribution of this cs to the key and collect incremental changes
+			for cs := range mc.changes[i].value.selectors { // get the sole selector
+				policyMapState.deleteKeyWithChanges(mc.changes[i].key, cs, adds, deletes)
+			}
+		}
+	}
+	mc.changes = nil
 	mc.mutex.Unlock()
 	return adds, deletes
 }
diff --git a/pkg/policy/resolve.go b/pkg/policy/resolve.go
index d2075b3f67..c650622171 100644
--- a/pkg/policy/resolve.go
+++ b/pkg/policy/resolve.go
@@ -65,6 +65,7 @@ type EndpointPolicy struct {
 	// It maps each Key to the proxy port if proxy redirection is needed.
 	// Proxy port 0 indicates no proxy redirection.
 	// All fields within the Key and the proxy port must be in host byte-order.
+	// Must only be accessed with PolicyOwner (aka Endpoint) lock taken.
 	PolicyMapState MapState
 
 	// policyMapChanges collects pending changes to the PolicyMapState
@@ -191,10 +192,11 @@ func (p *EndpointPolicy) computeDirectionL4PolicyMapEntries(policyMapState MapSt
 // ConsumeMapChanges transfers the changes from MapChanges to the caller,
 // locking the selector cache to make sure concurrent identity updates
 // have completed.
+// PolicyOwner (aka Endpoint) is also locked during this call.
 func (p *EndpointPolicy) ConsumeMapChanges() (adds, deletes MapState) {
 	p.selectorPolicy.SelectorCache.mutex.Lock()
 	defer p.selectorPolicy.SelectorCache.mutex.Unlock()
-	return p.policyMapChanges.consumeMapChanges()
+	return p.policyMapChanges.consumeMapChanges(p.PolicyMapState)
 }
 
 // AllowsIdentity returns whether the specified policy allows


Test patch:
diff --git a/pkg/policy/distillery_test.go b/pkg/policy/distillery_test.go
index 46395ca4c2..ade82d7ec3 100644
--- a/pkg/policy/distillery_test.go
+++ b/pkg/policy/distillery_test.go
@@ -326,13 +326,13 @@ var (
 	mapKeyAllowAll__ = Key{0, 0, 0, dirIngress}
 	// Desired map entries for no L7 redirect / redirect to Proxy
 	mapEntryL7None_ = func(lbls ...labels.LabelArray) MapStateEntry {
-		return NewMapStateEntry(labels.LabelArrayList(lbls).Sort(), false, false)
+		return NewMapStateEntry(nil, labels.LabelArrayList(lbls).Sort(), false, false).WithoutSelectors()
 	}
 	mapEntryL7Deny_ = func(lbls ...labels.LabelArray) MapStateEntry {
-		return NewMapStateEntry(labels.LabelArrayList(lbls).Sort(), false, true)
+		return NewMapStateEntry(nil, labels.LabelArrayList(lbls).Sort(), false, true).WithoutSelectors()
 	}
 	mapEntryL7Proxy = func(lbls ...labels.LabelArray) MapStateEntry {
-		return NewMapStateEntry(labels.LabelArrayList(lbls).Sort(), true, false)
+		return NewMapStateEntry(nil, labels.LabelArrayList(lbls).Sort(), true, false).WithoutSelectors()
 	}
 )
 
@@ -382,6 +382,7 @@ func (d *policyDistillery) distillPolicy(owner PolicyOwner, epLabels labels.Labe
 		allowAllIngress := true
 		allowAllEgress := false // Skip egress
 		result.AllowAllIdentities(allowAllIngress, allowAllEgress)
+		result.clearCachedSelectors()
 		return result, nil
 	}
 
@@ -413,9 +414,22 @@ func (d *policyDistillery) distillPolicy(owner PolicyOwner, epLabels labels.Labe
 		}
 	}
 	l4IngressPolicy.Detach(d.Repository.GetSelectorCache())
+	result.clearCachedSelectors()
 	return result, nil
 }
 
+// clearCachedSelectors removes CachedSelectors from MapStateEntries
+// for testing purposes.  Table-driven testing pattern used for these
+// tests does not allow expected MapStateEntries to contain actual
+// CachedSelectors as those have not been inserted to the selector
+// cache at the time when the expectations are created.
+func (m MapState) clearCachedSelectors() {
+	for k, v := range m {
+		v.selectors = nil
+		m[k] = v
+	}
+}
+
 func Test_MergeL3(t *testing.T) {
 	identityCache := cache.IdentityCache{
 		identity.NumericIdentity(identityFoo): labelsFoo,
diff --git a/pkg/policy/mapstate_test.go b/pkg/policy/mapstate_test.go
index a84beb4e4e..50691b69f4 100644
--- a/pkg/policy/mapstate_test.go
+++ b/pkg/policy/mapstate_test.go
@@ -23,6 +23,27 @@ import (
 	"gopkg.in/check.v1"
 )
 
+// WithSelectors returns a copy of 'e', but selectors replaced with 'selectors'. 'e' is not modified.
+// No selectors is represented with a 'nil' map.
+func (e MapStateEntry) WithSelectors(selectors ...CachedSelector) MapStateEntry {
+	mse := e
+	if len(selectors) > 0 {
+		mse.selectors = make(map[CachedSelector]struct{}, len(selectors))
+		for _, cs := range selectors {
+			mse.selectors[cs] = struct{}{}
+		}
+	} else {
+		mse.selectors = nil
+	}
+	return mse
+}
+
+// WithoutSelectors returns a copy of 'e', but selectors replaced with 'nil'. 'e' is not modified.
+// Note: This is used only in unit tests and helps test readability.
+func (e MapStateEntry) WithoutSelectors() MapStateEntry {
+	return e.WithSelectors()
+}
+
 func (ds *PolicyTestSuite) TestPolicyKeyTrafficDirection(c *check.C) {
 	k := Key{TrafficDirection: trafficdirection.Ingress.Uint8()}
 	c.Assert(k.IsIngress(), check.Equals, true)
@@ -709,3 +730,249 @@ func (ds *PolicyTestSuite) TestMapState_DenyPreferredInsert(c *check.C) {
 		c.Assert(tt.keys, checker.DeepEquals, tt.want, check.Commentf(tt.name))
 	}
 }
+
+func (ds *PolicyTestSuite) TestMapState_AccumulateMapChanges(c *check.C) {
+	csFoo := newTestCachedSelector("Foo", false)
+	csBar := newTestCachedSelector("Bar", false)
+
+	TestKey := func(id int, port uint16, proto uint8, direction trafficdirection.TrafficDirection) Key {
+		return Key{
+			Identity:         uint32(id),
+			DestPort:         port,
+			Nexthdr:          proto,
+			TrafficDirection: direction.Uint8(),
+		}
+	}
+	TestIngressKey := func(id int, port uint16, proto uint8) Key {
+		return TestKey(id, port, proto, trafficdirection.Ingress)
+	}
+	TestEgressKey := func(id int, port uint16, proto uint8) Key {
+		return TestKey(id, port, proto, trafficdirection.Egress)
+	}
+	DNSUDPEgressKey := func(id int) Key {
+		return TestEgressKey(id, 53, 17)
+	}
+	DNSTCPEgressKey := func(id int) Key {
+		return TestEgressKey(id, 53, 6)
+	}
+	HostIngressKey := func() Key {
+		return TestIngressKey(1, 0, 0)
+	}
+	AnyIngressKey := func() Key {
+		return TestIngressKey(0, 0, 0)
+	}
+	//AnyEgressKey := func() Key {
+	//	return TestEgressKey(0, 0, 0)
+	//}
+	HttpIngressKey := func(id int) Key {
+		return TestIngressKey(id, 80, 6)
+	}
+	HttpEgressKey := func(id int) Key {
+		return TestEgressKey(id, 80, 6)
+	}
+
+	TestEntry := func(proxyPort uint16, deny bool, selectors ...CachedSelector) MapStateEntry {
+		entry := MapStateEntry{
+			ProxyPort: proxyPort,
+			IsDeny:    deny,
+		}
+		if len(selectors) > 0 {
+			entry.selectors = make(map[CachedSelector]struct{}, len(selectors))
+			for _, cs := range selectors {
+				entry.selectors[cs] = struct{}{}
+			}
+		}
+		return entry
+	}
+
+	type args struct {
+		cs       *testCachedSelector
+		adds     []int
+		deletes  []int
+		port     uint16
+		proto    uint8
+		ingress  bool
+		redirect bool
+		deny     bool
+	}
+	tests := []struct {
+		continued bool // Start from the end state of the previous test
+		name      string
+		args      []args // changes applied, in order
+		state     MapState
+		adds      MapState
+		deletes   MapState
+	}{{
+		name: "test-1 - Adding identity to an empty state",
+		args: []args{
+			{cs: csFoo, adds: []int{42}, deletes: []int{}, port: 80, proto: 6, ingress: true, redirect: false, deny: false},
+		},
+		state: MapState{
+			HttpIngressKey(42): TestEntry(0, false, csFoo),
+		},
+		adds: MapState{
+			HttpIngressKey(42): TestEntry(0, false),
+		},
+		deletes: MapState{},
+	}, {
+		continued: true,
+		name:      "test-2 - Removing the sole key",
+		args: []args{
+			{cs: csFoo, adds: nil, deletes: []int{42}, port: 80, proto: 6, ingress: true, redirect: false, deny: false},
+		},
+		state: MapState{},
+		adds:  MapState{},
+		deletes: MapState{
+			HttpIngressKey(42): TestEntry(0, false),
+		},
+	}, {
+		name: "test-3 - Adding 2 identities, and deleting a nonexisting key on an empty state",
+		args: []args{
+			{cs: csFoo, adds: []int{42, 43}, deletes: []int{50}, port: 80, proto: 6, ingress: true, redirect: false, deny: false},
+		},
+		state: MapState{
+			HttpIngressKey(42): TestEntry(0, false, csFoo),
+			HttpIngressKey(43): TestEntry(0, false, csFoo),
+		},
+		adds: MapState{
+			HttpIngressKey(42): TestEntry(0, false),
+			HttpIngressKey(43): TestEntry(0, false),
+		},
+		deletes: MapState{},
+	}, {
+		continued: true,
+		name:      "test-4 - Adding Bar also selecting 42",
+		args: []args{
+			{cs: csBar, adds: []int{42, 44}, deletes: []int{50}, port: 80, proto: 6, ingress: true, redirect: false, deny: false},
+		},
+		state: MapState{
+			HttpIngressKey(42): TestEntry(0, false, csFoo, csBar),
+			HttpIngressKey(43): TestEntry(0, false, csFoo),
+			HttpIngressKey(44): TestEntry(0, false, csBar),
+		},
+		adds: MapState{
+			HttpIngressKey(44): TestEntry(0, false),
+		},
+		deletes: MapState{},
+	}, {
+		continued: true,
+		name:      "test-5 - Deleting 42 from Foo, remains on Bar and no deletes",
+		args: []args{
+			{cs: csFoo, adds: []int{}, deletes: []int{42}, port: 80, proto: 6, ingress: true, redirect: false, deny: false},
+		},
+		state: MapState{
+			HttpIngressKey(42): TestEntry(0, false, csBar),
+			HttpIngressKey(43): TestEntry(0, false, csFoo),
+			HttpIngressKey(44): TestEntry(0, false, csBar),
+		},
+		adds:    MapState{},
+		deletes: MapState{},
+	}, {
+		continued: true,
+		name:      "test-6 - Deleting 42 from Bar, deleted",
+		args: []args{
+			{cs: csFoo, adds: []int{}, deletes: []int{42}, port: 80, proto: 6, ingress: true, redirect: false, deny: false},
+		},
+		state: MapState{
+			HttpIngressKey(43): TestEntry(0, false, csFoo),
+			HttpIngressKey(44): TestEntry(0, false, csBar),
+		},
+		adds: MapState{},
+		deletes: MapState{
+			HttpIngressKey(42): TestEntry(0, false),
+		},
+	}, {
+		continued: true,
+		name:      "test-6b - Adding an entry that already exists, no adds",
+		args: []args{
+			{cs: csBar, adds: []int{44}, deletes: []int{}, port: 80, proto: 6, ingress: true, redirect: false, deny: false},
+		},
+		state: MapState{
+			HttpIngressKey(43): TestEntry(0, false, csFoo),
+			HttpIngressKey(44): TestEntry(0, false, csBar),
+		},
+		adds:    MapState{},
+		deletes: MapState{},
+	}, {
+		continued: false,
+		name:      "test-7a - egress HTTP proxy (setup)",
+		args: []args{
+			{cs: nil, adds: []int{0}, deletes: []int{}, port: 0, proto: 0, ingress: true, redirect: false, deny: false},
+			{cs: nil, adds: []int{1}, deletes: []int{}, port: 0, proto: 0, ingress: true, redirect: false, deny: false},
+			{cs: csBar, adds: []int{42}, deletes: []int{}, port: 53, proto: 17, ingress: false, redirect: false, deny: false},
+			{cs: csBar, adds: []int{42}, deletes: []int{}, port: 53, proto: 6, ingress: false, redirect: false, deny: false},
+		},
+		state: MapState{
+			AnyIngressKey():     TestEntry(0, false, nil),
+			HostIngressKey():    TestEntry(0, false, nil),
+			DNSUDPEgressKey(42): TestEntry(0, false, csBar),
+			DNSTCPEgressKey(42): TestEntry(0, false, csBar),
+		},
+		adds: MapState{
+			AnyIngressKey():     TestEntry(0, false),
+			HostIngressKey():    TestEntry(0, false),
+			DNSUDPEgressKey(42): TestEntry(0, false),
+			DNSTCPEgressKey(42): TestEntry(0, false),
+		},
+		deletes: MapState{},
+	}, {
+		continued: true,
+		name:      "test-7b - egress HTTP proxy (incremental update)",
+		args: []args{
+			{cs: csFoo, adds: []int{43}, deletes: []int{}, port: 80, proto: 6, ingress: false, redirect: true, deny: false},
+		},
+		state: MapState{
+			AnyIngressKey():     TestEntry(0, false, nil),
+			HostIngressKey():    TestEntry(0, false, nil),
+			DNSUDPEgressKey(42): TestEntry(0, false, csBar),
+			DNSTCPEgressKey(42): TestEntry(0, false, csBar),
+			HttpEgressKey(43):   TestEntry(1, false, csFoo),
+		},
+		adds: MapState{
+			HttpEgressKey(43): TestEntry(1, false),
+		},
+		deletes: MapState{},
+	}, {
+		continued: false,
+		name:      "test-n - title",
+		args:      []args{
+			//{cs: csFoo, adds: []int{42, 43}, deletes: []int{50}, port: 80, proto: 6, ingress: true, redirect: false, deny: false},
+		},
+		state: MapState{
+			//HttpIngressKey(42): TestEntry(0, false, csFoo),
+		},
+		adds: MapState{
+			//HttpIngressKey(42): TestEntry(0, false),
+		},
+		deletes: MapState{
+			//HttpIngressKey(43): TestEntry(0, false),
+		},
+	},
+	}
+
+	policyMapState := MapState{}
+
+	for _, tt := range tests {
+		policyMaps := MapChanges{}
+		if !tt.continued {
+			policyMapState = MapState{}
+		}
+		for _, x := range tt.args {
+			dir := trafficdirection.Egress
+			if x.ingress {
+				dir = trafficdirection.Ingress
+			}
+			adds := x.cs.addSelections(x.adds...)
+			deletes := x.cs.deleteSelections(x.deletes...)
+			var cs CachedSelector
+			if x.cs != nil {
+				cs = x.cs
+			}
+			policyMaps.AccumulateMapChanges(cs, adds, deletes, x.port, x.proto, dir, x.redirect, x.deny, nil)
+		}
+		adds, deletes := policyMaps.consumeMapChanges(policyMapState)
+		c.Assert(policyMapState, checker.DeepEquals, tt.state, check.Commentf(tt.name+" (MapState)"))
+		c.Assert(adds, checker.DeepEquals, tt.adds, check.Commentf(tt.name+" (adds)"))
+		c.Assert(deletes, checker.DeepEquals, tt.deletes, check.Commentf(tt.name+" (deletes)"))
+	}
+}
diff --git a/pkg/policy/resolve_deny_test.go b/pkg/policy/resolve_deny_test.go
index 55340bd377..db8c6dde7f 100644
--- a/pkg/policy/resolve_deny_test.go
+++ b/pkg/policy/resolve_deny_test.go
@@ -314,8 +314,8 @@ func (ds *PolicyTestSuite) TestMapStateWithIngressDenyWildcard(c *C) {
 	c.Assert(err, IsNil)
 	policy := selPolicy.DistillPolicy(DummyOwner{}, false)
 
-	rule1MapStateEntry := NewMapStateEntry(labels.LabelArrayList{ruleLabel}, false, true)
-	allowEgressMapStateEntry := NewMapStateEntry(labels.LabelArrayList{ruleLabelAllowAnyEgress}, false, false)
+	rule1MapStateEntry := NewMapStateEntry(wildcardCachedSelector, labels.LabelArrayList{ruleLabel}, false, true)
+	allowEgressMapStateEntry := NewMapStateEntry(nil, labels.LabelArrayList{ruleLabelAllowAnyEgress}, false, false)
 
 	expectedEndpointPolicy := EndpointPolicy{
 		selectorPolicy: &selectorPolicy{
@@ -351,13 +351,12 @@ func (ds *PolicyTestSuite) TestMapStateWithIngressDenyWildcard(c *C) {
 		},
 	}
 
-	// Add new identity to test accumulation of PolicyMapChanges
+	// Add new identity to test accumulation of MapChanges
 	added1 := cache.IdentityCache{
 		identity.NumericIdentity(192): labels.ParseSelectLabelArray("id=resolve_test_1"),
 	}
 	testSelectorCache.UpdateIdentities(added1, nil)
-	c.Assert(policy.policyMapChanges.adds, HasLen, 0)
-	c.Assert(policy.policyMapChanges.deletes, HasLen, 0)
+	c.Assert(policy.policyMapChanges.changes, HasLen, 0)
 
 	// Have to remove circular reference before testing to avoid an infinite loop
 	policy.selectorPolicy.Detach()
@@ -425,7 +424,7 @@ func (ds *PolicyTestSuite) TestMapStateWithIngressDeny(c *C) {
 	c.Assert(err, IsNil)
 	policy := selPolicy.DistillPolicy(DummyOwner{}, false)
 
-	// Add new identity to test accumulation of PolicyMapChanges
+	// Add new identity to test accumulation of MapChanges
 	added1 := cache.IdentityCache{
 		identity.NumericIdentity(192): labels.ParseSelectLabelArray("id=resolve_test_1", "num=1"),
 		identity.NumericIdentity(193): labels.ParseSelectLabelArray("id=resolve_test_1", "num=2"),
@@ -434,15 +433,13 @@ func (ds *PolicyTestSuite) TestMapStateWithIngressDeny(c *C) {
 	testSelectorCache.UpdateIdentities(added1, nil)
 	// Cleanup the identities from the testSelectorCache
 	defer testSelectorCache.UpdateIdentities(nil, added1)
-	c.Assert(policy.policyMapChanges.adds, HasLen, 3)
-	c.Assert(policy.policyMapChanges.deletes, HasLen, 0)
+	c.Assert(policy.policyMapChanges.changes, HasLen, 3)
 
 	deleted1 := cache.IdentityCache{
 		identity.NumericIdentity(193): labels.ParseSelectLabelArray("id=resolve_test_1", "num=2"),
 	}
 	testSelectorCache.UpdateIdentities(nil, deleted1)
-	c.Assert(policy.policyMapChanges.adds, HasLen, 2)
-	c.Assert(policy.policyMapChanges.deletes, HasLen, 1)
+	c.Assert(policy.policyMapChanges.changes, HasLen, 4)
 
 	cachedSelectorWorld := testSelectorCache.FindCachedIdentitySelector(api.ReservedEndpointSelectors[labels.IDNameWorld])
 	c.Assert(cachedSelectorWorld, Not(IsNil))
@@ -450,8 +447,8 @@ func (ds *PolicyTestSuite) TestMapStateWithIngressDeny(c *C) {
 	cachedSelectorTest := testSelectorCache.FindCachedIdentitySelector(api.NewESFromLabels(lblTest))
 	c.Assert(cachedSelectorTest, Not(IsNil))
 
-	rule1MapStateEntry := NewMapStateEntry(labels.LabelArrayList{ruleLabel, ruleLabel}, false, true)
-	allowEgressMapStateEntry := NewMapStateEntry(labels.LabelArrayList{ruleLabelDenyAnyEgress}, false, false)
+	rule1MapStateEntry := NewMapStateEntry(cachedSelectorTest, labels.LabelArrayList{ruleLabel, ruleLabel}, false, true)
+	allowEgressMapStateEntry := NewMapStateEntry(nil, labels.LabelArrayList{ruleLabelDenyAnyEgress}, false, false)
 
 	expectedEndpointPolicy := EndpointPolicy{
 		selectorPolicy: &selectorPolicy{
@@ -483,18 +480,23 @@ func (ds *PolicyTestSuite) TestMapStateWithIngressDeny(c *C) {
 			// Although we have calculated deny policies, the overall policy
 			// will still allow egress to world.
 			{TrafficDirection: trafficdirection.Egress.Uint8()}:                          allowEgressMapStateEntry,
-			{Identity: uint32(identity.ReservedIdentityWorld), DestPort: 80, Nexthdr: 6}: rule1MapStateEntry,
+			{Identity: uint32(identity.ReservedIdentityWorld), DestPort: 80, Nexthdr: 6}: rule1MapStateEntry.WithSelectors(cachedSelectorWorld),
+			{Identity: 192, DestPort: 80, Nexthdr: 6}:                                    rule1MapStateEntry,
+			{Identity: 194, DestPort: 80, Nexthdr: 6}:                                    rule1MapStateEntry,
 		},
-		policyMapChanges: MapChanges{
-			adds: MapState{
-				{Identity: 192, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry,
-				{Identity: 194, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry,
-			},
-			deletes: MapState{
-				{Identity: 193, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry,
-			}},
 	}
 
+	adds, deletes := policy.ConsumeMapChanges()
+	// maps on the policy got cleared
+
+	c.Assert(adds, checker.Equals, MapState{
+		{Identity: 192, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry.WithoutSelectors(),
+		{Identity: 194, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry.WithoutSelectors(),
+	})
+	c.Assert(deletes, checker.Equals, MapState{
+		{Identity: 193, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry.WithoutSelectors(),
+	})
+
 	// Have to remove circular reference before testing for Equality to avoid an infinite loop
 	policy.selectorPolicy.Detach()
 	// Verify that cached selector is not found after Detach().
@@ -507,15 +509,4 @@ func (ds *PolicyTestSuite) TestMapStateWithIngressDeny(c *C) {
 	policy.selectorPolicy.L4Policy.mutex = lock.RWMutex{}
 	policy.policyMapChanges.mutex = lock.Mutex{}
 	c.Assert(policy, checker.Equals, &expectedEndpointPolicy)
-
-	allows, deletes := policy.ConsumeMapChanges()
-	// maps on the policy got cleared
-
-	c.Assert(allows, checker.Equals, MapState{
-		{Identity: 192, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry,
-		{Identity: 194, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry,
-	})
-	c.Assert(deletes, checker.Equals, MapState{
-		{Identity: 193, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry,
-	})
 }
diff --git a/pkg/policy/resolve_test.go b/pkg/policy/resolve_test.go
index 88c70e6447..27b1590f40 100644
--- a/pkg/policy/resolve_test.go
+++ b/pkg/policy/resolve_test.go
@@ -480,8 +480,8 @@ func (ds *PolicyTestSuite) TestMapStateWithIngressWildcard(c *C) {
 	c.Assert(err, IsNil)
 	policy := selPolicy.DistillPolicy(DummyOwner{}, false)
 
-	rule1MapStateEntry := NewMapStateEntry(labels.LabelArrayList{ruleLabel}, false, false)
-	allowEgressMapStateEntry := NewMapStateEntry(labels.LabelArrayList{ruleLabelAllowAnyEgress}, false, false)
+	rule1MapStateEntry := NewMapStateEntry(wildcardCachedSelector, labels.LabelArrayList{ruleLabel}, false, false)
+	allowEgressMapStateEntry := NewMapStateEntry(nil, labels.LabelArrayList{ruleLabelAllowAnyEgress}, false, false)
 
 	expectedEndpointPolicy := EndpointPolicy{
 		selectorPolicy: &selectorPolicy{
@@ -516,13 +516,12 @@ func (ds *PolicyTestSuite) TestMapStateWithIngressWildcard(c *C) {
 		},
 	}
 
-	// Add new identity to test accumulation of PolicyMapChanges
+	// Add new identity to test accumulation of MapChanges
 	added1 := cache.IdentityCache{
 		identity.NumericIdentity(192): labels.ParseSelectLabelArray("id=resolve_test_1"),
 	}
 	testSelectorCache.UpdateIdentities(added1, nil)
-	c.Assert(policy.policyMapChanges.adds, HasLen, 0)
-	c.Assert(policy.policyMapChanges.deletes, HasLen, 0)
+	c.Assert(policy.policyMapChanges.changes, HasLen, 0)
 
 	// Have to remove circular reference before testing to avoid an infinite loop
 	policy.selectorPolicy.Detach()
@@ -592,7 +591,7 @@ func (ds *PolicyTestSuite) TestMapStateWithIngress(c *C) {
 	c.Assert(err, IsNil)
 	policy := selPolicy.DistillPolicy(DummyOwner{}, false)
 
-	// Add new identity to test accumulation of PolicyMapChanges
+	// Add new identity to test accumulation of MapChanges
 	added1 := cache.IdentityCache{
 		identity.NumericIdentity(192): labels.ParseSelectLabelArray("id=resolve_test_1", "num=1"),
 		identity.NumericIdentity(193): labels.ParseSelectLabelArray("id=resolve_test_1", "num=2"),
@@ -601,15 +600,13 @@ func (ds *PolicyTestSuite) TestMapStateWithIngress(c *C) {
 	testSelectorCache.UpdateIdentities(added1, nil)
 	// Cleanup the identities from the testSelectorCache
 	defer testSelectorCache.UpdateIdentities(nil, added1)
-	c.Assert(policy.policyMapChanges.adds, HasLen, 3)
-	c.Assert(policy.policyMapChanges.deletes, HasLen, 0)
+	c.Assert(policy.policyMapChanges.changes, HasLen, 3)
 
 	deleted1 := cache.IdentityCache{
 		identity.NumericIdentity(193): labels.ParseSelectLabelArray("id=resolve_test_1", "num=2"),
 	}
 	testSelectorCache.UpdateIdentities(nil, deleted1)
-	c.Assert(policy.policyMapChanges.adds, HasLen, 2)
-	c.Assert(policy.policyMapChanges.deletes, HasLen, 1)
+	c.Assert(policy.policyMapChanges.changes, HasLen, 4)
 
 	cachedSelectorWorld := testSelectorCache.FindCachedIdentitySelector(api.ReservedEndpointSelectors[labels.IDNameWorld])
 	c.Assert(cachedSelectorWorld, Not(IsNil))
@@ -617,8 +614,8 @@ func (ds *PolicyTestSuite) TestMapStateWithIngress(c *C) {
 	cachedSelectorTest := testSelectorCache.FindCachedIdentitySelector(api.NewESFromLabels(lblTest))
 	c.Assert(cachedSelectorTest, Not(IsNil))
 
-	rule1MapStateEntry := NewMapStateEntry(labels.LabelArrayList{ruleLabel, ruleLabel}, false, false)
-	allowEgressMapStateEntry := NewMapStateEntry(labels.LabelArrayList{ruleLabelAllowAnyEgress}, false, false)
+	rule1MapStateEntry := NewMapStateEntry(cachedSelectorTest, labels.LabelArrayList{ruleLabel, ruleLabel}, false, false)
+	allowEgressMapStateEntry := NewMapStateEntry(nil, labels.LabelArrayList{ruleLabelAllowAnyEgress}, false, false)
 
 	expectedEndpointPolicy := EndpointPolicy{
 		selectorPolicy: &selectorPolicy{
@@ -649,16 +646,9 @@ func (ds *PolicyTestSuite) TestMapStateWithIngress(c *C) {
 		PolicyOwner: DummyOwner{},
 		PolicyMapState: MapState{
 			{TrafficDirection: trafficdirection.Egress.Uint8()}:                          allowEgressMapStateEntry,
-			{Identity: uint32(identity.ReservedIdentityWorld), DestPort: 80, Nexthdr: 6}: rule1MapStateEntry,
-		},
-		policyMapChanges: MapChanges{
-			adds: MapState{
-				{Identity: 192, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry,
-				{Identity: 194, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry,
-			},
-			deletes: MapState{
-				{Identity: 193, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry,
-			},
+			{Identity: uint32(identity.ReservedIdentityWorld), DestPort: 80, Nexthdr: 6}: rule1MapStateEntry.WithSelectors(cachedSelectorWorld),
+			{Identity: 192, DestPort: 80, Nexthdr: 6}:                                    rule1MapStateEntry,
+			{Identity: 194, DestPort: 80, Nexthdr: 6}:                                    rule1MapStateEntry,
 		},
 	}
 
@@ -669,24 +659,23 @@ func (ds *PolicyTestSuite) TestMapStateWithIngress(c *C) {
 	cachedSelectorTest = testSelectorCache.FindCachedIdentitySelector(api.NewESFromLabels(lblTest))
 	c.Assert(cachedSelectorTest, IsNil)
 
-	// Assign an empty mutex so that checker.Equal does not complain about the
-	// difference of the internal time.Time from the lock_debug.go.
-	policy.selectorPolicy.L4Policy.mutex = lock.RWMutex{}
-	policy.policyMapChanges.mutex = lock.Mutex{}
-	c.Assert(policy, checker.Equals, &expectedEndpointPolicy)
-
 	adds, deletes := policy.ConsumeMapChanges()
 	// maps on the policy got cleared
-	c.Assert(policy.policyMapChanges.adds, IsNil)
-	c.Assert(policy.policyMapChanges.deletes, IsNil)
+	c.Assert(policy.policyMapChanges.changes, IsNil)
 
 	c.Assert(adds, checker.Equals, MapState{
-		{Identity: 192, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry,
-		{Identity: 194, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry,
+		{Identity: 192, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry.WithoutSelectors(),
+		{Identity: 194, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry.WithoutSelectors(),
 	})
 	c.Assert(deletes, checker.Equals, MapState{
-		{Identity: 193, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry,
+		{Identity: 193, DestPort: 80, Nexthdr: 6}: rule1MapStateEntry.WithoutSelectors(),
 	})
+
+	// Assign an empty mutex so that checker.Equal does not complain about the
+	// difference of the internal time.Time from the lock_debug.go.
+	policy.selectorPolicy.L4Policy.mutex = lock.RWMutex{}
+	policy.policyMapChanges.mutex = lock.Mutex{}
+	c.Assert(policy, checker.Equals, &expectedEndpointPolicy)
 }
 
 func TestEndpointPolicy_AllowsIdentity(t *testing.T) {
diff --git a/pkg/policy/selectorcache_test.go b/pkg/policy/selectorcache_test.go
index 6ab3be9dc5..94f61ebe39 100644
--- a/pkg/policy/selectorcache_test.go
+++ b/pkg/policy/selectorcache_test.go
@@ -125,6 +125,83 @@ func (csu *cachedSelectionUser) IdentitySelectionUpdated(selector CachedSelector
 	csu.selections[selector] = selections
 }
 
+// Mock CachedSelector for unit testing.
+
+type testCachedSelector struct {
+	name       string
+	wildcard   bool
+	selections []identity.NumericIdentity
+}
+
+func newTestCachedSelector(name string, wildcard bool, selections ...int) *testCachedSelector {
+	cs := &testCachedSelector{
+		name:       name,
+		wildcard:   wildcard,
+		selections: make([]identity.NumericIdentity, 0, len(selections)),
+	}
+	cs.addSelections(selections...)
+	return cs
+}
+
+// returns selections as []identity.NumericIdentity
+func (cs *testCachedSelector) addSelections(selections ...int) (adds []identity.NumericIdentity) {
+	for _, id := range selections {
+		nid := identity.NumericIdentity(id)
+		adds = append(adds, nid)
+		if cs == nil {
+			continue
+		}
+		if !cs.Selects(nid) {
+			cs.selections = append(cs.selections, nid)
+		}
+	}
+	return adds
+}
+
+// returns selections as []identity.NumericIdentity
+func (cs *testCachedSelector) deleteSelections(selections ...int) (deletes []identity.NumericIdentity) {
+	for _, id := range selections {
+		nid := identity.NumericIdentity(id)
+		deletes = append(deletes, nid)
+		if cs == nil {
+			continue
+		}
+		for i := 0; i < len(cs.selections); i++ {
+			if nid == cs.selections[i] {
+				cs.selections = append(cs.selections[:i], cs.selections[i+1:]...)
+				i--
+			}
+		}
+	}
+	return deletes
+}
+
+// CachedSelector interface
+
+func (cs *testCachedSelector) GetSelections() []identity.NumericIdentity {
+	return cs.selections
+}
+func (cs *testCachedSelector) Selects(nid identity.NumericIdentity) bool {
+	for _, id := range cs.selections {
+		if id == nid {
+			return true
+		}
+	}
+	return false
+}
+
+func (cs *testCachedSelector) IsWildcard() bool {
+	return cs.wildcard
+}
+
+func (cs *testCachedSelector) IsNone() bool {
+	return false
+}
+
+func (cs *testCachedSelector) String() string {
+	return cs.name
+}
+
 func (ds *SelectorCacheTestSuite) SetUpTest(c *C) {
 }