matcher.go

Documentation: google.golang.org/grpc/xds/internal/xdsclient/xdsresource

     1  /*
     2   *
     3   * Copyright 2020 gRPC authors.
     4   *
     5   * Licensed under the Apache License, Version 2.0 (the "License");
     6   * you may not use this file except in compliance with the License.
     7   * You may obtain a copy of the License at
     8   *
     9   *     http://www.apache.org/licenses/LICENSE-2.0
    10   *
    11   * Unless required by applicable law or agreed to in writing, software
    12   * distributed under the License is distributed on an "AS IS" BASIS,
    13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    14   * See the License for the specific language governing permissions and
    15   * limitations under the License.
    16   */
    17  
    18  package xdsresource
    19  
    20  import (
    21  	"fmt"
    22  	"strings"
    23  
    24  	"google.golang.org/grpc/internal/grpcrand"
    25  	"google.golang.org/grpc/internal/grpcutil"
    26  	iresolver "google.golang.org/grpc/internal/resolver"
    27  	"google.golang.org/grpc/internal/xds/matcher"
    28  	"google.golang.org/grpc/metadata"
    29  )
    30  
    31  // RouteToMatcher converts a route to a Matcher to match incoming RPC's against.
    32  func RouteToMatcher(r *Route) (*CompositeMatcher, error) {
    33  	var pm pathMatcher
    34  	switch {
    35  	case r.Regex != nil:
    36  		pm = newPathRegexMatcher(r.Regex)
    37  	case r.Path != nil:
    38  		pm = newPathExactMatcher(*r.Path, r.CaseInsensitive)
    39  	case r.Prefix != nil:
    40  		pm = newPathPrefixMatcher(*r.Prefix, r.CaseInsensitive)
    41  	default:
    42  		return nil, fmt.Errorf("illegal route: missing path_matcher")
    43  	}
    44  
    45  	headerMatchers := make([]matcher.HeaderMatcher, 0, len(r.Headers))
    46  	for _, h := range r.Headers {
    47  		var matcherT matcher.HeaderMatcher
    48  		invert := h.InvertMatch != nil && *h.InvertMatch
    49  		switch {
    50  		case h.ExactMatch != nil && *h.ExactMatch != "":
    51  			matcherT = matcher.NewHeaderExactMatcher(h.Name, *h.ExactMatch, invert)
    52  		case h.RegexMatch != nil:
    53  			matcherT = matcher.NewHeaderRegexMatcher(h.Name, h.RegexMatch, invert)
    54  		case h.PrefixMatch != nil && *h.PrefixMatch != "":
    55  			matcherT = matcher.NewHeaderPrefixMatcher(h.Name, *h.PrefixMatch, invert)
    56  		case h.SuffixMatch != nil && *h.SuffixMatch != "":
    57  			matcherT = matcher.NewHeaderSuffixMatcher(h.Name, *h.SuffixMatch, invert)
    58  		case h.RangeMatch != nil:
    59  			matcherT = matcher.NewHeaderRangeMatcher(h.Name, h.RangeMatch.Start, h.RangeMatch.End, invert)
    60  		case h.PresentMatch != nil:
    61  			matcherT = matcher.NewHeaderPresentMatcher(h.Name, *h.PresentMatch, invert)
    62  		case h.StringMatch != nil:
    63  			matcherT = matcher.NewHeaderStringMatcher(h.Name, *h.StringMatch, invert)
    64  		default:
    65  			return nil, fmt.Errorf("illegal route: missing header_match_specifier")
    66  		}
    67  		headerMatchers = append(headerMatchers, matcherT)
    68  	}
    69  
    70  	var fractionMatcher *fractionMatcher
    71  	if r.Fraction != nil {
    72  		fractionMatcher = newFractionMatcher(*r.Fraction)
    73  	}
    74  	return newCompositeMatcher(pm, headerMatchers, fractionMatcher), nil
    75  }
    76  
    77  // CompositeMatcher is a matcher that holds onto many matchers and aggregates
    78  // the matching results.
    79  type CompositeMatcher struct {
    80  	pm  pathMatcher
    81  	hms []matcher.HeaderMatcher
    82  	fm  *fractionMatcher
    83  }
    84  
    85  func newCompositeMatcher(pm pathMatcher, hms []matcher.HeaderMatcher, fm *fractionMatcher) *CompositeMatcher {
    86  	return &CompositeMatcher{pm: pm, hms: hms, fm: fm}
    87  }
    88  
    89  // Match returns true if all matchers return true.
    90  func (a *CompositeMatcher) Match(info iresolver.RPCInfo) bool {
    91  	if a.pm != nil && !a.pm.match(info.Method) {
    92  		return false
    93  	}
    94  
    95  	// Call headerMatchers even if md is nil, because routes may match
    96  	// non-presence of some headers.
    97  	var md metadata.MD
    98  	if info.Context != nil {
    99  		md, _ = metadata.FromOutgoingContext(info.Context)
   100  		if extraMD, ok := grpcutil.ExtraMetadata(info.Context); ok {
   101  			md = metadata.Join(md, extraMD)
   102  			// Remove all binary headers. They are hard to match with. May need
   103  			// to add back if asked by users.
   104  			for k := range md {
   105  				if strings.HasSuffix(k, "-bin") {
   106  					delete(md, k)
   107  				}
   108  			}
   109  		}
   110  	}
   111  	for _, m := range a.hms {
   112  		if !m.Match(md) {
   113  			return false
   114  		}
   115  	}
   116  
   117  	if a.fm != nil && !a.fm.match() {
   118  		return false
   119  	}
   120  	return true
   121  }
   122  
   123  func (a *CompositeMatcher) String() string {
   124  	var ret string
   125  	if a.pm != nil {
   126  		ret += a.pm.String()
   127  	}
   128  	for _, m := range a.hms {
   129  		ret += m.String()
   130  	}
   131  	if a.fm != nil {
   132  		ret += a.fm.String()
   133  	}
   134  	return ret
   135  }
   136  
   137  type fractionMatcher struct {
   138  	fraction int64 // real fraction is fraction/1,000,000.
   139  }
   140  
   141  func newFractionMatcher(fraction uint32) *fractionMatcher {
   142  	return &fractionMatcher{fraction: int64(fraction)}
   143  }
   144  
   145  // RandInt63n overwrites grpcrand for control in tests.
   146  var RandInt63n = grpcrand.Int63n
   147  
   148  func (fm *fractionMatcher) match() bool {
   149  	t := RandInt63n(1000000)
   150  	return t <= fm.fraction
   151  }
   152  
   153  func (fm *fractionMatcher) String() string {
   154  	return fmt.Sprintf("fraction:%v", fm.fraction)
   155  }
   156  
   157  type domainMatchType int
   158  
   159  const (
   160  	domainMatchTypeInvalid domainMatchType = iota
   161  	domainMatchTypeUniversal
   162  	domainMatchTypePrefix
   163  	domainMatchTypeSuffix
   164  	domainMatchTypeExact
   165  )
   166  
   167  // Exact > Suffix > Prefix > Universal > Invalid.
   168  func (t domainMatchType) betterThan(b domainMatchType) bool {
   169  	return t > b
   170  }
   171  
   172  func matchTypeForDomain(d string) domainMatchType {
   173  	if d == "" {
   174  		return domainMatchTypeInvalid
   175  	}
   176  	if d == "*" {
   177  		return domainMatchTypeUniversal
   178  	}
   179  	if strings.HasPrefix(d, "*") {
   180  		return domainMatchTypeSuffix
   181  	}
   182  	if strings.HasSuffix(d, "*") {
   183  		return domainMatchTypePrefix
   184  	}
   185  	if strings.Contains(d, "*") {
   186  		return domainMatchTypeInvalid
   187  	}
   188  	return domainMatchTypeExact
   189  }
   190  
   191  func match(domain, host string) (domainMatchType, bool) {
   192  	switch typ := matchTypeForDomain(domain); typ {
   193  	case domainMatchTypeInvalid:
   194  		return typ, false
   195  	case domainMatchTypeUniversal:
   196  		return typ, true
   197  	case domainMatchTypePrefix:
   198  		// abc.*
   199  		return typ, strings.HasPrefix(host, strings.TrimSuffix(domain, "*"))
   200  	case domainMatchTypeSuffix:
   201  		// *.123
   202  		return typ, strings.HasSuffix(host, strings.TrimPrefix(domain, "*"))
   203  	case domainMatchTypeExact:
   204  		return typ, domain == host
   205  	default:
   206  		return domainMatchTypeInvalid, false
   207  	}
   208  }
   209  
   210  // FindBestMatchingVirtualHost returns the virtual host whose domains field best
   211  // matches host
   212  //
   213  //	The domains field support 4 different matching pattern types:
   214  //
   215  //	- Exact match
   216  //	- Suffix match (e.g. “*ABC”)
   217  //	- Prefix match (e.g. “ABC*)
   218  //	- Universal match (e.g. “*”)
   219  //
   220  //	The best match is defined as:
   221  //	- A match is better if it’s matching pattern type is better.
   222  //	  * Exact match > suffix match > prefix match > universal match.
   223  //
   224  //	- If two matches are of the same pattern type, the longer match is
   225  //	  better.
   226  //	  * This is to compare the length of the matching pattern, e.g. “*ABCDE” >
   227  //	    “*ABC”
   228  func FindBestMatchingVirtualHost(host string, vHosts []*VirtualHost) *VirtualHost { // Maybe move this crap to client
   229  	var (
   230  		matchVh   *VirtualHost
   231  		matchType = domainMatchTypeInvalid
   232  		matchLen  int
   233  	)
   234  	for _, vh := range vHosts {
   235  		for _, domain := range vh.Domains {
   236  			typ, matched := match(domain, host)
   237  			if typ == domainMatchTypeInvalid {
   238  				// The rds response is invalid.
   239  				return nil
   240  			}
   241  			if matchType.betterThan(typ) || matchType == typ && matchLen >= len(domain) || !matched {
   242  				// The previous match has better type, or the previous match has
   243  				// better length, or this domain isn't a match.
   244  				continue
   245  			}
   246  			matchVh = vh
   247  			matchType = typ
   248  			matchLen = len(domain)
   249  		}
   250  	}
   251  	return matchVh
   252  }
   253  
   254  // FindBestMatchingVirtualHostServer returns the virtual host whose domains field best
   255  // matches authority.
   256  func FindBestMatchingVirtualHostServer(authority string, vHosts []VirtualHostWithInterceptors) *VirtualHostWithInterceptors {
   257  	var (
   258  		matchVh   *VirtualHostWithInterceptors
   259  		matchType = domainMatchTypeInvalid
   260  		matchLen  int
   261  	)
   262  	for _, vh := range vHosts {
   263  		for _, domain := range vh.Domains {
   264  			typ, matched := match(domain, authority)
   265  			if typ == domainMatchTypeInvalid {
   266  				// The rds response is invalid.
   267  				return nil
   268  			}
   269  			if matchType.betterThan(typ) || matchType == typ && matchLen >= len(domain) || !matched {
   270  				// The previous match has better type, or the previous match has
   271  				// better length, or this domain isn't a match.
   272  				continue
   273  			}
   274  			matchVh = &vh
   275  			matchType = typ
   276  			matchLen = len(domain)
   277  		}
   278  	}
   279  	return matchVh
   280  }
   281
View as plain text