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