1// +build go1.10 2 3/* 4 * 5 * Copyright 2020 gRPC authors. 6 * 7 * Licensed under the Apache License, Version 2.0 (the "License"); 8 * you may not use this file except in compliance with the License. 9 * You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, software 14 * distributed under the License is distributed on an "AS IS" BASIS, 15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16 * See the License for the specific language governing permissions and 17 * limitations under the License. 18 * 19 */ 20 21// Package keys provides functionality required to build RLS request keys. 22package keys 23 24import ( 25 "errors" 26 "fmt" 27 "sort" 28 "strings" 29 30 rlspb "google.golang.org/grpc/balancer/rls/internal/proto/grpc_lookup_v1" 31 "google.golang.org/grpc/metadata" 32) 33 34// BuilderMap provides a mapping from a request path to the key builder to be 35// used for that path. 36// The BuilderMap is constructed by parsing the RouteLookupConfig received by 37// the RLS balancer as part of its ServiceConfig, and is used by the picker in 38// the data path to build the RLS keys to be used for a given request. 39type BuilderMap map[string]builder 40 41// MakeBuilderMap parses the provided RouteLookupConfig proto and returns a map 42// from paths to key builders. 43// 44// The following conditions are validated, and an error is returned if any of 45// them is not met: 46// grpc_keybuilders field 47// * must have at least one entry 48// * must not have two entries with the same Name 49// * must not have any entry with a Name with the service field unset or empty 50// * must not have any entries without a Name 51// * must not have a headers entry that has required_match set 52// * must not have two headers entries with the same key within one entry 53func MakeBuilderMap(cfg *rlspb.RouteLookupConfig) (BuilderMap, error) { 54 kbs := cfg.GetGrpcKeybuilders() 55 if len(kbs) == 0 { 56 return nil, errors.New("rls: RouteLookupConfig does not contain any GrpcKeyBuilder") 57 } 58 59 bm := make(map[string]builder) 60 for _, kb := range kbs { 61 var matchers []matcher 62 seenKeys := make(map[string]bool) 63 for _, h := range kb.GetHeaders() { 64 if h.GetRequiredMatch() { 65 return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig has required_match field set {%+v}", kbs) 66 } 67 key := h.GetKey() 68 if seenKeys[key] { 69 return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig contains repeated Key field in headers {%+v}", kbs) 70 } 71 seenKeys[key] = true 72 matchers = append(matchers, matcher{key: h.GetKey(), names: h.GetNames()}) 73 } 74 b := builder{matchers: matchers} 75 76 names := kb.GetNames() 77 if len(names) == 0 { 78 return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig does not contain any Name {%+v}", kbs) 79 } 80 for _, name := range names { 81 if name.GetService() == "" { 82 return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig contains a Name field with no Service {%+v}", kbs) 83 } 84 if strings.Contains(name.GetMethod(), `/`) { 85 return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig contains a method with a slash {%+v}", kbs) 86 } 87 path := "/" + name.GetService() + "/" + name.GetMethod() 88 if _, ok := bm[path]; ok { 89 return nil, fmt.Errorf("rls: GrpcKeyBuilder in RouteLookupConfig contains repeated Name field {%+v}", kbs) 90 } 91 bm[path] = b 92 } 93 } 94 return bm, nil 95} 96 97// KeyMap represents the RLS keys to be used for a request. 98type KeyMap struct { 99 // Map is the representation of an RLS key as a Go map. This is used when 100 // an actual RLS request is to be sent out on the wire, since the 101 // RouteLookupRequest proto expects a Go map. 102 Map map[string]string 103 // Str is the representation of an RLS key as a string, sorted by keys. 104 // Since the RLS keys are part of the cache key in the request cache 105 // maintained by the RLS balancer, and Go maps cannot be used as keys for 106 // Go maps (the cache is implemented as a map), we need a stringified 107 // version of it. 108 Str string 109} 110 111// RLSKey builds the RLS keys to be used for the given request, identified by 112// the request path and the request headers stored in metadata. 113func (bm BuilderMap) RLSKey(md metadata.MD, path string) KeyMap { 114 b, ok := bm[path] 115 if !ok { 116 i := strings.LastIndex(path, "/") 117 b, ok = bm[path[:i+1]] 118 if !ok { 119 return KeyMap{} 120 } 121 } 122 return b.keys(md) 123} 124 125// Equal reports whether bm and am represent equivalent BuilderMaps. 126func (bm BuilderMap) Equal(am BuilderMap) bool { 127 if (bm == nil) != (am == nil) { 128 return false 129 } 130 if len(bm) != len(am) { 131 return false 132 } 133 134 for key, bBuilder := range bm { 135 aBuilder, ok := am[key] 136 if !ok { 137 return false 138 } 139 if !bBuilder.Equal(aBuilder) { 140 return false 141 } 142 } 143 return true 144} 145 146// builder provides the actual functionality of building RLS keys. These are 147// stored in the BuilderMap. 148// While processing a pick, the picker looks in the BuilderMap for the 149// appropriate builder to be used for the given RPC. For each of the matchers 150// in the found builder, we iterate over the list of request headers (available 151// as metadata in the context). Once a header matches one of the names in the 152// matcher, we set the value of the header in the keyMap (with the key being 153// the one found in the matcher) and move on to the next matcher. If no 154// KeyBuilder was found in the map, or no header match was found, an empty 155// keyMap is returned. 156type builder struct { 157 matchers []matcher 158} 159 160// Equal reports whether b and a represent equivalent key builders. 161func (b builder) Equal(a builder) bool { 162 if (b.matchers == nil) != (a.matchers == nil) { 163 return false 164 } 165 if len(b.matchers) != len(a.matchers) { 166 return false 167 } 168 // Protobuf serialization maintains the order of repeated fields. Matchers 169 // are specified as a repeated field inside the KeyBuilder proto. If the 170 // order changes, it means that the order in the protobuf changed. We report 171 // this case as not being equal even though the builders could possible be 172 // functionally equal. 173 for i, bMatcher := range b.matchers { 174 aMatcher := a.matchers[i] 175 if !bMatcher.Equal(aMatcher) { 176 return false 177 } 178 } 179 return true 180} 181 182// matcher helps extract a key from request headers based on a given name. 183type matcher struct { 184 // The key used in the keyMap sent as part of the RLS request. 185 key string 186 // List of header names which can supply the value for this key. 187 names []string 188} 189 190// Equal reports if m and are are equivalent matchers. 191func (m matcher) Equal(a matcher) bool { 192 if m.key != a.key { 193 return false 194 } 195 if (m.names == nil) != (a.names == nil) { 196 return false 197 } 198 if len(m.names) != len(a.names) { 199 return false 200 } 201 for i := 0; i < len(m.names); i++ { 202 if m.names[i] != a.names[i] { 203 return false 204 } 205 } 206 return true 207} 208 209func (b builder) keys(md metadata.MD) KeyMap { 210 kvMap := make(map[string]string) 211 for _, m := range b.matchers { 212 for _, name := range m.names { 213 if vals := md.Get(name); vals != nil { 214 kvMap[m.key] = strings.Join(vals, ",") 215 break 216 } 217 } 218 } 219 return KeyMap{Map: kvMap, Str: mapToString(kvMap)} 220} 221 222func mapToString(kv map[string]string) string { 223 var keys []string 224 for k := range kv { 225 keys = append(keys, k) 226 } 227 sort.Strings(keys) 228 var sb strings.Builder 229 for i, k := range keys { 230 if i != 0 { 231 fmt.Fprint(&sb, ",") 232 } 233 fmt.Fprintf(&sb, "%s=%s", k, kv[k]) 234 } 235 return sb.String() 236} 237