Created
May 12, 2022 17:48
-
-
Save stevenctl/74476bcf93e46189d020a93f614e1924 to your computer and use it in GitHub Desktop.
Unified Matcher REpair
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package match | |
import ( | |
xds "github.com/cncf/xds/go/xds/core/v3" | |
matcher "github.com/cncf/xds/go/xds/type/matcher/v3" | |
network "github.com/envoyproxy/go-control-plane/envoy/extensions/matching/common_inputs/network/v3" | |
"github.com/golang/protobuf/ptypes/wrappers" | |
"istio.io/istio/pilot/pkg/networking/util" | |
"istio.io/pkg/log" | |
) | |
var ( | |
DestinationPort = &xds.TypedExtensionConfig{ | |
Name: "port", | |
TypedConfig: util.MessageToAny(&network.DestinationPortInput{}), | |
} | |
DestinationIP = &xds.TypedExtensionConfig{ | |
Name: "ip", | |
TypedConfig: util.MessageToAny(&network.DestinationIPInput{}), | |
} | |
SourceIP = &xds.TypedExtensionConfig{ | |
Name: "source-ip", | |
TypedConfig: util.MessageToAny(&network.SourceIPInput{}), | |
} | |
SNI = &xds.TypedExtensionConfig{ | |
Name: "sni", | |
TypedConfig: util.MessageToAny(&network.ServerNameInput{}), | |
} | |
ApplicationProtocolInput = &xds.TypedExtensionConfig{ | |
Name: "application-protocol", | |
TypedConfig: util.MessageToAny(&network.ApplicationProtocolInput{}), | |
} | |
TransportProtocolInput = &xds.TypedExtensionConfig{ | |
Name: "transport-protocol", | |
TypedConfig: util.MessageToAny(&network.TransportProtocolInput{}), | |
} | |
) | |
type Mapper struct { | |
*matcher.Matcher | |
Map map[string]*matcher.Matcher_OnMatch | |
} | |
func newMapper(input *xds.TypedExtensionConfig) Mapper { | |
m := map[string]*matcher.Matcher_OnMatch{} | |
match := &matcher.Matcher{ | |
MatcherType: &matcher.Matcher_MatcherTree_{ | |
MatcherTree: &matcher.Matcher_MatcherTree{ | |
Input: input, | |
TreeType: &matcher.Matcher_MatcherTree_ExactMatchMap{ | |
ExactMatchMap: &matcher.Matcher_MatcherTree_MatchMap{ | |
Map: m, | |
}, | |
}, | |
}, | |
}, | |
OnNoMatch: nil, | |
} | |
return Mapper{Matcher: match, Map: m} | |
} | |
func NewDestinationIP() Mapper { | |
return newMapper(DestinationIP) | |
} | |
func NewSourceIP() Mapper { | |
return newMapper(SourceIP) | |
} | |
func NewDestinationPort() Mapper { | |
return newMapper(DestinationPort) | |
} | |
func ToChain(name string) *matcher.Matcher_OnMatch { | |
return &matcher.Matcher_OnMatch{ | |
OnMatch: &matcher.Matcher_OnMatch_Action{ | |
Action: &xds.TypedExtensionConfig{ | |
Name: name, | |
TypedConfig: util.MessageToAny(&wrappers.StringValue{Value: name}), | |
}, | |
}, | |
} | |
} | |
func ToMatcher(match *matcher.Matcher) *matcher.Matcher_OnMatch { | |
return &matcher.Matcher_OnMatch{ | |
OnMatch: &matcher.Matcher_OnMatch_Matcher{ | |
Matcher: match, | |
}, | |
} | |
} | |
// BuildMatcher cleans the entire match tree to avoid empty maps and returns a viable top-level matcher. | |
// Note: this mutates the internal mappers/matchers that make up the tree. | |
func (m Mapper) BuildMatcher() *matcher.Matcher { | |
root := m | |
for len(root.Map) == 0 { | |
// the top level matcher is empty; if its fallback goes to a matcher, return that | |
// TODO is there a way we can just say "always go to action"? | |
if fallback := root.GetOnNoMatch(); fallback != nil { | |
if replacement, ok := mapperFromMatch(fallback.GetMatcher()); ok { | |
root = replacement | |
continue | |
} | |
} | |
// no fallback or fallback isn't a mapper | |
log.Warnf("could not repair invalid matcher; empty map at root matcher does not have a map fallback") | |
return nil | |
} | |
q := []*matcher.Matcher_OnMatch{m.OnNoMatch} | |
for _, onMatch := range root.Map { | |
q = append(q, onMatch) | |
} | |
// fix the matchers, add child mappers OnMatch to the queue | |
for len(q) > 0 { | |
head := q[0] | |
q = q[1:] | |
q = append(q, fixEmptyOnMatchMap(head)...) | |
} | |
return root.Matcher | |
} | |
// if the onMatch sends to an empty mapper, make the onMatch send directly to the onNoMatch of that empty mapper | |
// returns mapper if it doesn't need to be fixed, or can't be fixed | |
func fixEmptyOnMatchMap(onMatch *matcher.Matcher_OnMatch) []*matcher.Matcher_OnMatch { | |
if onMatch == nil { | |
return nil | |
} | |
innerMatcher := onMatch.GetMatcher() | |
if innerMatcher == nil { | |
// this already just performs an Action | |
return nil | |
} | |
innerMapper, ok := mapperFromMatch(innerMatcher) | |
if !ok { | |
// this isn't a mapper or action, not supported by this func | |
return nil | |
} | |
if len(innerMapper.Map) > 0 { | |
return innerMapper.allOnMatches() | |
} | |
if fallback := innerMapper.GetOnNoMatch(); fallback != nil { | |
// change from: onMatch -> map (empty with fallback) to onMatch -> fallback | |
// that fallback may be an empty map, so we re-queue onMatch in case it still needs fixing | |
onMatch.OnMatch = fallback.OnMatch | |
return []*matcher.Matcher_OnMatch{onMatch} // the inner mapper is gone | |
} | |
// envoy will nack this eventually | |
log.Warnf("empty mapper %v with no fallback", innerMapper.Matcher) | |
return innerMapper.allOnMatches() | |
} | |
func (m Mapper) allOnMatches() []*matcher.Matcher_OnMatch { | |
var out []*matcher.Matcher_OnMatch | |
out = append(out, m.OnNoMatch) | |
if m.Map == nil { | |
return out | |
} | |
for _, match := range m.Map { | |
out = append(out, match) | |
} | |
return out | |
} | |
func mapperFromMatch(mmatcher *matcher.Matcher) (Mapper, bool) { | |
if mmatcher == nil { | |
return Mapper{}, false | |
} | |
switch m := mmatcher.MatcherType.(type) { | |
case *matcher.Matcher_MatcherTree_: | |
var mmap *matcher.Matcher_MatcherTree_MatchMap | |
switch t := m.MatcherTree.TreeType.(type) { | |
case *matcher.Matcher_MatcherTree_PrefixMatchMap: | |
mmap = t.PrefixMatchMap | |
case *matcher.Matcher_MatcherTree_ExactMatchMap: | |
mmap = t.ExactMatchMap | |
default: | |
return Mapper{}, false | |
} | |
return Mapper{Matcher: mmatcher, Map: mmap.Map}, true | |
} | |
return Mapper{}, false | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package match | |
import ( | |
matcher "github.com/cncf/xds/go/xds/type/matcher/v3" | |
"github.com/google/go-cmp/cmp" | |
"istio.io/istio/pkg/util/protomarshal" | |
"testing" | |
) | |
func TestCleanupEmptyMaps(t *testing.T) { | |
tc := []struct { | |
name string | |
given func() Mapper | |
want func() *matcher.Matcher | |
}{ | |
{ | |
name: "empty map at depth = 0", | |
given: func() Mapper { | |
// root (dest port): | |
// <no matches> | |
// fallback (dest ip): | |
// 1.2.3.4: chain | |
fallback := NewDestinationIP() | |
fallback.Map["1.2.3.4"] = ToChain("chain") | |
root := NewDestinationPort() | |
root.OnNoMatch = ToMatcher(fallback.Matcher) | |
return root | |
}, | |
want: func() *matcher.Matcher { | |
// root (dest ip): | |
// 1.2.3.4: chain | |
// fallback becomes root | |
want := NewDestinationIP() | |
want.Map["1.2.3.4"] = ToChain("chain") | |
return want.Matcher | |
}, | |
}, | |
{ | |
name: "empty map at depth = 1", | |
given: func() Mapper { | |
// root (dest port) | |
// 15001: | |
// inner (dest ip): | |
// <no matches> | |
// fallback: chain | |
inner := NewDestinationIP() | |
inner.OnNoMatch = ToChain("chain") | |
root := NewDestinationPort() | |
root.Map["15001"] = ToMatcher(inner.Matcher) | |
return root | |
}, | |
want: func() *matcher.Matcher { | |
// dest port | |
// 15001: chain | |
want := NewDestinationPort() | |
want.Map["15001"] = ToChain("chain") | |
return want.Matcher | |
}, | |
}, | |
{ | |
name: "empty map at depth = 0 and 1", | |
given: func() Mapper { | |
// root (dest port) | |
// fallback: | |
// inner (dest ip): | |
// <no matches> | |
// fallback (src ip): | |
// 1.2.3.4: chain | |
inner := NewSourceIP() | |
inner.Map["1.2.3.4"] = ToChain("chain") | |
middle := NewDestinationIP() | |
middle.OnNoMatch = ToMatcher(inner.Matcher) | |
root := NewDestinationPort() | |
root.OnNoMatch = ToMatcher(middle.Matcher) | |
return root | |
}, | |
want: func() *matcher.Matcher { | |
// src ip | |
// 1.2.3.4: chain | |
want := NewSourceIP() | |
want.Map["1.2.3.4"] = ToChain("chain") | |
return want.Matcher | |
}, | |
}, | |
{ | |
name: "empty map at depths = 1 and 2", | |
given: func() Mapper { | |
// root (dest port) | |
// 15001: | |
// depth1 (SNI): | |
// fallback: | |
// depth2 (src ip): | |
// fallback: chain | |
depth2 := NewDestinationIP() | |
depth2.OnNoMatch = ToChain("chain") | |
depth1 := newMapper(SNI) | |
depth1.OnNoMatch = ToMatcher(depth2.Matcher) | |
root := NewDestinationPort() | |
root.Map["15001"] = ToMatcher(depth1.Matcher) | |
return root | |
}, | |
want: func() *matcher.Matcher { | |
// dest port | |
// 15001: chain | |
want := NewDestinationPort() | |
want.Map["15001"] = ToChain("chain") | |
return want.Matcher | |
}, | |
}, | |
} | |
for _, tt := range tc { | |
t.Run(tt.name, func(t *testing.T) { | |
got := tt.given().BuildMatcher() | |
haveJSON, _ := protomarshal.ToJSONWithIndent(got, " ") | |
wantJSON, _ := protomarshal.ToJSONWithIndent(tt.want(), " ") | |
if diff := cmp.Diff(haveJSON, wantJSON, cmp.AllowUnexported()); diff != "" { | |
t.Error(haveJSON) | |
t.Error(wantJSON) | |
t.Error(diff) | |
} | |
}) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment