| 1 |
/* |
| 2 |
Copyright 2019 The Kubernetes Authors. |
| 3 |
|
| 4 |
Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 |
you may not use this file except in compliance with the License. |
| 6 |
You may obtain a copy of the License at |
| 7 |
|
| 8 |
http://www.apache.org/licenses/LICENSE-2.0 |
| 9 |
|
| 10 |
Unless required by applicable law or agreed to in writing, software |
| 11 |
distributed under the License is distributed on an "AS IS" BASIS, |
| 12 |
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 |
See the License for the specific language governing permissions and |
| 14 |
limitations under the License. |
| 15 |
*/ |
| 16 |
|
| 17 |
package flowcontrol |
| 18 |
|
| 19 |
import ( |
| 20 |
"fmt" |
| 21 |
"math/rand" |
| 22 |
"sync/atomic" |
| 23 |
"testing" |
| 24 |
|
| 25 |
"k8s.io/utils/clock" |
| 26 |
"k8s.io/utils/ptr" |
| 27 |
|
| 28 |
flowcontrol "k8s.io/api/flowcontrol/v1" |
| 29 |
metav1 "k8s.io/apimachinery/pkg/apis/meta/v1" |
| 30 |
"k8s.io/apimachinery/pkg/util/sets" |
| 31 |
fcboot "k8s.io/apiserver/pkg/apis/flowcontrol/bootstrap" |
| 32 |
"k8s.io/apiserver/pkg/authentication/user" |
| 33 |
"k8s.io/apiserver/pkg/endpoints/request" |
| 34 |
fq "k8s.io/apiserver/pkg/util/flowcontrol/fairqueuing" |
| 35 |
fqtesting "k8s.io/apiserver/pkg/util/flowcontrol/fairqueuing/testing" |
| 36 |
fcfmt "k8s.io/apiserver/pkg/util/flowcontrol/format" |
| 37 |
"k8s.io/apiserver/pkg/util/flowcontrol/metrics" |
| 38 |
) |
| 39 |
|
| 40 |
var noRestraintQSF = fqtesting.NewNoRestraintFactory() |
| 41 |
|
| 42 |
// genPL creates a valid PriorityLevelConfiguration with the given |
| 43 |
// name and randomly generated spec. The given name must not be one |
| 44 |
// of the mandatory ones. |
| 45 |
func genPL(rng *rand.Rand, name string) *flowcontrol.PriorityLevelConfiguration { |
| 46 |
plc := &flowcontrol.PriorityLevelConfiguration{ |
| 47 |
ObjectMeta: metav1.ObjectMeta{Name: name}, |
| 48 |
Spec: flowcontrol.PriorityLevelConfigurationSpec{ |
| 49 |
Type: flowcontrol.PriorityLevelEnablementLimited, |
| 50 |
Limited: &flowcontrol.LimitedPriorityLevelConfiguration{ |
| 51 |
NominalConcurrencyShares: ptr.To(int32(rng.Int31n(100) + 1)), |
| 52 |
LimitResponse: flowcontrol.LimitResponse{ |
| 53 |
Type: flowcontrol.LimitResponseTypeReject}}}} |
| 54 |
if rng.Float32() < 0.95 { |
| 55 |
plc.Spec.Limited.LimitResponse.Type = flowcontrol.LimitResponseTypeQueue |
| 56 |
hs := rng.Int31n(5) + 1 |
| 57 |
plc.Spec.Limited.LimitResponse.Queuing = &flowcontrol.QueuingConfiguration{ |
| 58 |
Queues: hs + rng.Int31n(20), |
| 59 |
HandSize: hs, |
| 60 |
QueueLengthLimit: 5} |
| 61 |
} |
| 62 |
labelVals := []string{"test"} |
| 63 |
_, err := queueSetCompleterForPL(noRestraintQSF, nil, plc, metrics.RatioedGaugeVecPhasedElementPair(metrics.PriorityLevelConcurrencyGaugeVec, 1, 1, labelVals), metrics.PriorityLevelExecutionSeatsGaugeVec.NewForLabelValuesSafe(0, 1, labelVals), fq.NewNamedIntegrator(clock.RealClock{}, name)) |
| 64 |
if err != nil { |
| 65 |
panic(err) |
| 66 |
} |
| 67 |
return plc |
| 68 |
} |
| 69 |
|
| 70 |
// A FlowSchema together with characteristics relevant to testing |
| 71 |
type fsTestingRecord struct { |
| 72 |
fs *flowcontrol.FlowSchema |
| 73 |
// Does this reference an existing priority level? |
| 74 |
wellFormed bool |
| 75 |
matchesAllResourceRequests bool |
| 76 |
matchesAllNonResourceRequests bool |
| 77 |
// maps `matches bool` to `isResourceRequest bool` to digests |
| 78 |
digests map[bool]map[bool][]RequestDigest |
| 79 |
} |
| 80 |
|
| 81 |
func (ftr *fsTestingRecord) addDigest(digest RequestDigest, matches bool) { |
| 82 |
ftr.digests[matches][digest.RequestInfo.IsResourceRequest] = append(ftr.digests[matches][digest.RequestInfo.IsResourceRequest], digest) |
| 83 |
} |
| 84 |
|
| 85 |
func (ftr *fsTestingRecord) addDigests(digests []RequestDigest, matches bool) { |
| 86 |
for _, digest := range digests { |
| 87 |
ftr.addDigest(digest, matches) |
| 88 |
} |
| 89 |
} |
| 90 |
|
| 91 |
var flowDistinguisherMethodTypes = sets.NewString( |
| 92 |
string(flowcontrol.FlowDistinguisherMethodByUserType), |
| 93 |
string(flowcontrol.FlowDistinguisherMethodByNamespaceType), |
| 94 |
) |
| 95 |
|
| 96 |
var mandFTRExempt = &fsTestingRecord{ |
| 97 |
fs: fcboot.MandatoryFlowSchemaExempt, |
| 98 |
wellFormed: true, |
| 99 |
digests: map[bool]map[bool][]RequestDigest{ |
| 100 |
false: { |
| 101 |
false: {{ |
| 102 |
RequestInfo: &request.RequestInfo{ |
| 103 |
IsResourceRequest: false, |
| 104 |
Path: "/foo/bar", |
| 105 |
Verb: "frobulate"}, |
| 106 |
User: &user.DefaultInfo{ |
| 107 |
Name: "nobody", |
| 108 |
Groups: []string{user.AllAuthenticated, "nogroup"}, |
| 109 |
}, |
| 110 |
}}, |
| 111 |
true: {{ |
| 112 |
RequestInfo: &request.RequestInfo{ |
| 113 |
IsResourceRequest: true, |
| 114 |
Verb: "mandate", |
| 115 |
APIGroup: "nogroup", |
| 116 |
Namespace: "nospace", |
| 117 |
Resource: "nons", |
| 118 |
}, |
| 119 |
User: &user.DefaultInfo{ |
| 120 |
Name: "nobody", |
| 121 |
Groups: []string{user.AllAuthenticated, "nogroup"}, |
| 122 |
}, |
| 123 |
}}, |
| 124 |
}, |
| 125 |
true: { |
| 126 |
false: {{ |
| 127 |
RequestInfo: &request.RequestInfo{ |
| 128 |
IsResourceRequest: false, |
| 129 |
Path: "/foo/bar", |
| 130 |
Verb: "frobulate"}, |
| 131 |
User: &user.DefaultInfo{ |
| 132 |
Name: "nobody", |
| 133 |
Groups: []string{user.AllAuthenticated, user.SystemPrivilegedGroup}, |
| 134 |
}, |
| 135 |
}}, |
| 136 |
true: {{ |
| 137 |
RequestInfo: &request.RequestInfo{ |
| 138 |
IsResourceRequest: true, |
| 139 |
Verb: "mandate", |
| 140 |
APIGroup: "nogroup", |
| 141 |
Namespace: "nospace", |
| 142 |
Resource: "nons", |
| 143 |
}, |
| 144 |
User: &user.DefaultInfo{ |
| 145 |
Name: "nobody", |
| 146 |
Groups: []string{user.AllAuthenticated, user.SystemPrivilegedGroup}, |
| 147 |
}, |
| 148 |
}}, |
| 149 |
}, |
| 150 |
}, |
| 151 |
} |
| 152 |
|
| 153 |
var mandFTRCatchAll = &fsTestingRecord{ |
| 154 |
fs: fcboot.MandatoryFlowSchemaCatchAll, |
| 155 |
wellFormed: true, |
| 156 |
digests: map[bool]map[bool][]RequestDigest{ |
| 157 |
false: {}, |
| 158 |
true: { |
| 159 |
false: {{ |
| 160 |
RequestInfo: &request.RequestInfo{ |
| 161 |
IsResourceRequest: false, |
| 162 |
Path: "/foo/bar", |
| 163 |
Verb: "frobulate"}, |
| 164 |
User: &user.DefaultInfo{ |
| 165 |
Name: "nobody", |
| 166 |
Groups: []string{user.AllAuthenticated, "nogroup"}, |
| 167 |
}, |
| 168 |
}}, |
| 169 |
true: {{ |
| 170 |
RequestInfo: &request.RequestInfo{ |
| 171 |
IsResourceRequest: true, |
| 172 |
Verb: "mandate", |
| 173 |
APIGroup: "nogroup", |
| 174 |
Namespace: "nospace", |
| 175 |
Resource: "nons", |
| 176 |
}, |
| 177 |
User: &user.DefaultInfo{ |
| 178 |
Name: "nobody", |
| 179 |
Groups: []string{user.AllAuthenticated, "nogroup"}, |
| 180 |
}, |
| 181 |
}}, |
| 182 |
}, |
| 183 |
}, |
| 184 |
} |
| 185 |
|
| 186 |
// genFS creates a valid FlowSchema with the given name and randomly |
| 187 |
// generated spec, along with characteristics relevant to testing. |
| 188 |
// When all the FlowSchemas in a collection are generated with |
| 189 |
// different names: (a) the matching digests match only the schema for |
| 190 |
// which they were generated, and (b) the non-matching digests do not |
| 191 |
// match any schema in the collection. The generated spec is |
| 192 |
// relatively likely to be well formed but might not be. An ill |
| 193 |
// formed spec references a priority level drawn from badPLNames. |
| 194 |
// goodPLNames may be empty, but badPLNames may not. |
| 195 |
func genFS(t *testing.T, rng *rand.Rand, name string, mayMatchClusterScope bool, goodPLNames, badPLNames sets.String) *fsTestingRecord { |
| 196 |
fs := &flowcontrol.FlowSchema{ |
| 197 |
ObjectMeta: metav1.ObjectMeta{Name: name}, |
| 198 |
Spec: flowcontrol.FlowSchemaSpec{}} |
| 199 |
// 5% chance of zero rules, otherwise draw from 1--6 biased low |
| 200 |
nRules := (1 + rng.Intn(3)) * (1 + rng.Intn(2)) * ((19 + rng.Intn(20)) / 20) |
| 201 |
ftr := &fsTestingRecord{fs: fs, |
| 202 |
wellFormed: true, |
| 203 |
matchesAllResourceRequests: nRules > 0 && rng.Float32() < 0.1, |
| 204 |
matchesAllNonResourceRequests: nRules > 0 && rng.Float32() < 0.1, |
| 205 |
digests: map[bool]map[bool][]RequestDigest{ |
| 206 |
false: {false: {}, true: {}}, |
| 207 |
true: {false: {}, true: {}}}, |
| 208 |
} |
| 209 |
dangleStatus := flowcontrol.ConditionFalse |
| 210 |
if rng.Float32() < 0.9 && len(goodPLNames) > 0 { |
| 211 |
fs.Spec.PriorityLevelConfiguration = flowcontrol.PriorityLevelConfigurationReference{Name: pickSetString(rng, goodPLNames)} |
| 212 |
} else { |
| 213 |
fs.Spec.PriorityLevelConfiguration = flowcontrol.PriorityLevelConfigurationReference{Name: pickSetString(rng, badPLNames)} |
| 214 |
ftr.wellFormed = false |
| 215 |
dangleStatus = flowcontrol.ConditionTrue |
| 216 |
} |
| 217 |
fs.Status.Conditions = []flowcontrol.FlowSchemaCondition{{ |
| 218 |
Type: flowcontrol.FlowSchemaConditionDangling, |
| 219 |
Status: dangleStatus}} |
| 220 |
fs.Spec.MatchingPrecedence = rng.Int31n(9997) + 2 |
| 221 |
if rng.Float32() < 0.8 { |
| 222 |
fdmt := flowcontrol.FlowDistinguisherMethodType(pickSetString(rng, flowDistinguisherMethodTypes)) |
| 223 |
fs.Spec.DistinguisherMethod = &flowcontrol.FlowDistinguisherMethod{Type: fdmt} |
| 224 |
} |
| 225 |
fs.Spec.Rules = []flowcontrol.PolicyRulesWithSubjects{} |
| 226 |
everyResourceMatcher := -1 |
| 227 |
if ftr.matchesAllResourceRequests { |
| 228 |
if mayMatchClusterScope { |
| 229 |
everyResourceMatcher = 0 |
| 230 |
} else { |
| 231 |
everyResourceMatcher = rng.Intn(nRules) |
| 232 |
} |
| 233 |
} |
| 234 |
everyNonResourceMatcher := -1 |
| 235 |
if ftr.matchesAllNonResourceRequests { |
| 236 |
if mayMatchClusterScope { |
| 237 |
everyNonResourceMatcher = 0 |
| 238 |
} else { |
| 239 |
everyNonResourceMatcher = rng.Intn(nRules) |
| 240 |
} |
| 241 |
} |
| 242 |
// Allow only one rule if mayMatchClusterScope because that breaks |
| 243 |
// cross-rule exclusion. |
| 244 |
for i := 0; i < nRules && (i == 0 || !mayMatchClusterScope); i++ { |
| 245 |
rule, ruleMatchingRDigests, ruleMatchingNDigests, ruleSkippingRDigests, ruleSkippingNDigests := genPolicyRuleWithSubjects(t, rng, fmt.Sprintf("%s-%d", name, i+1), mayMatchClusterScope, ftr.matchesAllResourceRequests, ftr.matchesAllNonResourceRequests, i == everyResourceMatcher, i == everyNonResourceMatcher) |
| 246 |
fs.Spec.Rules = append(fs.Spec.Rules, rule) |
| 247 |
ftr.addDigests(ruleMatchingRDigests, true) |
| 248 |
ftr.addDigests(ruleMatchingNDigests, true) |
| 249 |
ftr.addDigests(ruleSkippingRDigests, false) |
| 250 |
ftr.addDigests(ruleSkippingNDigests, false) |
| 251 |
} |
| 252 |
if nRules == 0 { |
| 253 |
var skippingRDigests, skippingNDigests []RequestDigest |
| 254 |
_, _, _, skippingRDigests, skippingNDigests = genPolicyRuleWithSubjects(t, rng, name+"-1", false, false, false, false, false) |
| 255 |
ftr.addDigests(skippingRDigests, false) |
| 256 |
ftr.addDigests(skippingNDigests, false) |
| 257 |
} |
| 258 |
if testDebugLogs { |
| 259 |
t.Logf("Returning name=%s, plRef=%q, wellFormed=%v, matchesAllResourceRequests=%v, matchesAllNonResourceRequests=%v for mayMatchClusterScope=%v", fs.Name, fs.Spec.PriorityLevelConfiguration.Name, ftr.wellFormed, ftr.matchesAllResourceRequests, ftr.matchesAllNonResourceRequests, mayMatchClusterScope) |
| 260 |
} |
| 261 |
return ftr |
| 262 |
} |
| 263 |
|
| 264 |
var noextra = make(map[string][]string) |
| 265 |
|
| 266 |
// Generate one valid PolicyRulesWithSubjects. Also returns: matching |
| 267 |
// resource-style digests, matching non-resource-style digests, |
| 268 |
// skipping (i.e., not matching the generated rule) resource-style |
| 269 |
// digests, skipping non-resource-style digests. When a collection of |
| 270 |
// rules is generated with unique prefixes, the skipping digests for |
| 271 |
// each rule match no rules in the collection. The |
| 272 |
// someMatchesAllResourceRequests and |
| 273 |
// someMatchesAllNonResourceRequests parameters indicate whether any |
| 274 |
// rule in the collection matches all of the relevant sort of request; |
| 275 |
// these imply the respective returned slice of counterexamples will |
| 276 |
// be empty. The matchAllResourceRequests and |
| 277 |
// matchAllNonResourceRequests parameters indicate whether the |
| 278 |
// generated rule should match all of the relevant sort. The |
| 279 |
// cross-rule exclusion is based on using names that start with the |
| 280 |
// given prefix --- which can not be done for the namespace of a |
| 281 |
// cluster-scoped request. Thus, these are normally excluded. When |
| 282 |
// mayMatchClusterScope==true the generated rule may be cluster-scoped |
| 283 |
// and there is no promise of cross-rule exclusion. |
| 284 |
func genPolicyRuleWithSubjects(t *testing.T, rng *rand.Rand, pfx string, mayMatchClusterScope, someMatchesAllResourceRequests, someMatchesAllNonResourceRequests, matchAllResourceRequests, matchAllNonResourceRequests bool) (flowcontrol.PolicyRulesWithSubjects, []RequestDigest, []RequestDigest, []RequestDigest, []RequestDigest) { |
| 285 |
subjects := []flowcontrol.Subject{} |
| 286 |
matchingUIs := []user.Info{} |
| 287 |
skippingUIs := []user.Info{} |
| 288 |
resourceRules := []flowcontrol.ResourcePolicyRule{} |
| 289 |
nonResourceRules := []flowcontrol.NonResourcePolicyRule{} |
| 290 |
matchingRRIs := []*request.RequestInfo{} |
| 291 |
skippingRRIs := []*request.RequestInfo{} |
| 292 |
matchingNRIs := []*request.RequestInfo{} |
| 293 |
skippingNRIs := []*request.RequestInfo{} |
| 294 |
nSubj := rng.Intn(4) |
| 295 |
for i := 0; i < nSubj; i++ { |
| 296 |
subject, smus, ssus := genSubject(rng, fmt.Sprintf("%s-%d", pfx, i+1)) |
| 297 |
subjects = append(subjects, subject) |
| 298 |
matchingUIs = append(matchingUIs, smus...) |
| 299 |
skippingUIs = append(skippingUIs, ssus...) |
| 300 |
} |
| 301 |
if matchAllResourceRequests || matchAllNonResourceRequests { |
| 302 |
switch rng.Intn(3) { |
| 303 |
case 0: |
| 304 |
subjects = append(subjects, mkUserSubject("*")) |
| 305 |
case 1: |
| 306 |
subjects = append(subjects, mkGroupSubject("*")) |
| 307 |
default: |
| 308 |
subjects = append(subjects, mkGroupSubject("system:authenticated"), mkGroupSubject("system:unauthenticated")) |
| 309 |
} |
| 310 |
matchingUIs = append(matchingUIs, skippingUIs...) |
| 311 |
} |
| 312 |
if someMatchesAllResourceRequests || someMatchesAllNonResourceRequests { |
| 313 |
skippingUIs = []user.Info{} |
| 314 |
} else if nSubj == 0 { |
| 315 |
_, _, skippingUIs = genSubject(rng, pfx+"-o") |
| 316 |
} |
| 317 |
var nRR, nNRR int |
| 318 |
for nRR+nNRR == 0 || matchAllResourceRequests && nRR == 0 || matchAllNonResourceRequests && nNRR == 0 { |
| 319 |
nRR = rng.Intn(4) |
| 320 |
nNRR = rng.Intn(4) |
| 321 |
} |
| 322 |
allResourceMatcher := -1 |
| 323 |
if matchAllResourceRequests { |
| 324 |
allResourceMatcher = rng.Intn(nRR) |
| 325 |
} |
| 326 |
// Allow only one resource rule if mayMatchClusterScope because |
| 327 |
// that breaks cross-rule exclusion. |
| 328 |
for i := 0; i < nRR && (i == 0 || !mayMatchClusterScope); i++ { |
| 329 |
rr, rmrs, rsrs := genResourceRule(rng, fmt.Sprintf("%s-%d", pfx, i+1), mayMatchClusterScope, i == allResourceMatcher, someMatchesAllResourceRequests) |
| 330 |
resourceRules = append(resourceRules, rr) |
| 331 |
matchingRRIs = append(matchingRRIs, rmrs...) |
| 332 |
skippingRRIs = append(skippingRRIs, rsrs...) |
| 333 |
} |
| 334 |
if nRR == 0 { |
| 335 |
_, _, skippingRRIs = genResourceRule(rng, pfx+"-o", mayMatchClusterScope, false, someMatchesAllResourceRequests) |
| 336 |
} |
| 337 |
allNonResourceMatcher := -1 |
| 338 |
if matchAllNonResourceRequests { |
| 339 |
allNonResourceMatcher = rng.Intn(nNRR) |
| 340 |
} |
| 341 |
for i := 0; i < nNRR; i++ { |
| 342 |
nrr, nmrs, nsrs := genNonResourceRule(rng, fmt.Sprintf("%s-%d", pfx, i+1), i == allNonResourceMatcher, someMatchesAllNonResourceRequests) |
| 343 |
nonResourceRules = append(nonResourceRules, nrr) |
| 344 |
matchingNRIs = append(matchingNRIs, nmrs...) |
| 345 |
skippingNRIs = append(skippingNRIs, nsrs...) |
| 346 |
} |
| 347 |
if nRR == 0 { |
| 348 |
_, _, skippingNRIs = genNonResourceRule(rng, pfx+"-o", false, someMatchesAllNonResourceRequests) |
| 349 |
} |
| 350 |
rule := flowcontrol.PolicyRulesWithSubjects{Subjects: subjects, ResourceRules: resourceRules, NonResourceRules: nonResourceRules} |
| 351 |
if testDebugLogs { |
| 352 |
t.Logf("For pfx=%s, mayMatchClusterScope=%v, someMatchesAllResourceRequests=%v, someMatchesAllNonResourceRequests=%v, marr=%v, manrr=%v: generated prws=%s, mu=%s, su=%s, mrr=%s, mnr=%s, srr=%s, snr=%s", pfx, mayMatchClusterScope, someMatchesAllResourceRequests, someMatchesAllNonResourceRequests, matchAllResourceRequests, matchAllNonResourceRequests, fcfmt.Fmt(rule), fcfmt.Fmt(matchingUIs), fcfmt.Fmt(skippingUIs), fcfmt.Fmt(matchingRRIs), fcfmt.Fmt(matchingNRIs), fcfmt.Fmt(skippingRRIs), fcfmt.Fmt(skippingNRIs)) |
| 353 |
} |
| 354 |
matchingRDigests := cross(matchingUIs, matchingRRIs) |
| 355 |
skippingRDigests := append(append(cross(matchingUIs, skippingRRIs), |
| 356 |
cross(skippingUIs, matchingRRIs)...), |
| 357 |
cross(skippingUIs, skippingRRIs)...) |
| 358 |
matchingNDigests := cross(matchingUIs, matchingNRIs) |
| 359 |
skippingNDigests := append(append(cross(matchingUIs, skippingNRIs), |
| 360 |
cross(skippingUIs, matchingNRIs)...), |
| 361 |
cross(skippingUIs, skippingNRIs)...) |
| 362 |
matchingRDigests = shuffleAndTakeDigests(t, rng, &rule, true, matchingRDigests, (1+rng.Intn(2))*(1+rng.Intn(2))) |
| 363 |
skippingRDigests = shuffleAndTakeDigests(t, rng, &rule, false, skippingRDigests, (1+rng.Intn(2))*(1+rng.Intn(2))) |
| 364 |
matchingNDigests = shuffleAndTakeDigests(t, rng, &rule, true, matchingNDigests, (1+rng.Intn(2))*(1+rng.Intn(2))) |
| 365 |
skippingNDigests = shuffleAndTakeDigests(t, rng, &rule, false, skippingNDigests, (1+rng.Intn(2))*(1+rng.Intn(2))) |
| 366 |
return rule, matchingRDigests, matchingNDigests, skippingRDigests, skippingNDigests |
| 367 |
} |
| 368 |
|
| 369 |
func cross(uis []user.Info, ris []*request.RequestInfo) []RequestDigest { |
| 370 |
ans := make([]RequestDigest, 0, len(uis)*len(ris)) |
| 371 |
for _, ui := range uis { |
| 372 |
for _, ri := range ris { |
| 373 |
ans = append(ans, RequestDigest{RequestInfo: ri, User: ui}) |
| 374 |
} |
| 375 |
} |
| 376 |
return ans |
| 377 |
} |
| 378 |
|
| 379 |
func shuffleAndTakeDigests(t *testing.T, rng *rand.Rand, rule *flowcontrol.PolicyRulesWithSubjects, toMatch bool, digests []RequestDigest, n int) []RequestDigest { |
| 380 |
ans := make([]RequestDigest, 0, n) |
| 381 |
for len(ans) < n && len(digests) > 0 { |
| 382 |
i := rng.Intn(len(digests)) |
| 383 |
digest := digests[i] |
| 384 |
ans = append(ans, digest) |
| 385 |
digests[i] = digests[len(digests)-1] |
| 386 |
digests = digests[:len(digests)-1] |
| 387 |
if rule != nil { |
| 388 |
thisMatches := matchesPolicyRule(digest, rule) |
| 389 |
if toMatch { |
| 390 |
if testDebugLogs { |
| 391 |
t.Logf("Added matching digest %#+v", digest) |
| 392 |
} |
| 393 |
if !thisMatches { |
| 394 |
t.Errorf("Fail in check: rule %s does not match digest %#+v", fcfmt.Fmt(rule), digest) |
| 395 |
} |
| 396 |
} else { |
| 397 |
if testDebugLogs { |
| 398 |
t.Logf("Added skipping digest %#+v", digest) |
| 399 |
} |
| 400 |
if thisMatches { |
| 401 |
t.Errorf("Fail in check: rule %s matches digest %#+v", fcfmt.Fmt(rule), digest) |
| 402 |
} |
| 403 |
} |
| 404 |
} |
| 405 |
} |
| 406 |
return ans |
| 407 |
} |
| 408 |
|
| 409 |
var uCounter uint32 = 1 |
| 410 |
|
| 411 |
func uniqify(in RequestDigest) RequestDigest { |
| 412 |
u1 := in.User.(*user.DefaultInfo) |
| 413 |
u2 := *u1 |
| 414 |
u2.Extra = map[string][]string{"u": {fmt.Sprintf("z%d", atomic.AddUint32(&uCounter, 1))}} |
| 415 |
return RequestDigest{User: &u2, RequestInfo: in.RequestInfo} |
| 416 |
} |
| 417 |
|
| 418 |
// genSubject returns a randomly generated valid Subject that matches |
| 419 |
// on some name(s) starting with the given prefix. The first returned |
| 420 |
// list contains members that match the generated Subject and involve |
| 421 |
// names that begin with the given prefix. The second returned list |
| 422 |
// contains members that mismatch the generated Subject and involve |
| 423 |
// names that begin with the given prefix. |
| 424 |
func genSubject(rng *rand.Rand, pfx string) (flowcontrol.Subject, []user.Info, []user.Info) { |
| 425 |
subject := flowcontrol.Subject{} |
| 426 |
var matchingUIs, skippingUIs []user.Info |
| 427 |
x := rng.Float32() |
| 428 |
switch { |
| 429 |
case x < 0.33: |
| 430 |
subject.Kind = flowcontrol.SubjectKindUser |
| 431 |
subject.User, matchingUIs, skippingUIs = genUser(rng, pfx) |
| 432 |
case x < 0.67: |
| 433 |
subject.Kind = flowcontrol.SubjectKindGroup |
| 434 |
subject.Group, matchingUIs, skippingUIs = genGroup(rng, pfx) |
| 435 |
default: |
| 436 |
subject.Kind = flowcontrol.SubjectKindServiceAccount |
| 437 |
subject.ServiceAccount, matchingUIs, skippingUIs = genServiceAccount(rng, pfx) |
| 438 |
} |
| 439 |
return subject, matchingUIs, skippingUIs |
| 440 |
} |
| 441 |
|
| 442 |
func genUser(rng *rand.Rand, pfx string) (*flowcontrol.UserSubject, []user.Info, []user.Info) { |
| 443 |
mui := &user.DefaultInfo{ |
| 444 |
Name: pfx + "-u", |
| 445 |
UID: "good-id", |
| 446 |
Groups: []string{pfx + "-g1", mg(rng), pfx + "-g2"}, |
| 447 |
Extra: noextra} |
| 448 |
skips := []user.Info{&user.DefaultInfo{ |
| 449 |
Name: mui.Name + "x", |
| 450 |
UID: mui.UID, |
| 451 |
Groups: mui.Groups, |
| 452 |
Extra: mui.Extra}} |
| 453 |
return &flowcontrol.UserSubject{Name: mui.Name}, []user.Info{mui}, skips |
| 454 |
} |
| 455 |
|
| 456 |
var groupCover = []string{"system:authenticated", "system:unauthenticated"} |
| 457 |
|
| 458 |
func mg(rng *rand.Rand) string { |
| 459 |
return groupCover[rng.Intn(len(groupCover))] |
| 460 |
} |
| 461 |
|
| 462 |
func mkUserSubject(username string) flowcontrol.Subject { |
| 463 |
return flowcontrol.Subject{ |
| 464 |
Kind: flowcontrol.SubjectKindUser, |
| 465 |
User: &flowcontrol.UserSubject{Name: username}, |
| 466 |
} |
| 467 |
} |
| 468 |
|
| 469 |
func mkGroupSubject(group string) flowcontrol.Subject { |
| 470 |
return flowcontrol.Subject{ |
| 471 |
Kind: flowcontrol.SubjectKindGroup, |
| 472 |
Group: &flowcontrol.GroupSubject{Name: group}, |
| 473 |
} |
| 474 |
} |
| 475 |
|
| 476 |
func genGroup(rng *rand.Rand, pfx string) (*flowcontrol.GroupSubject, []user.Info, []user.Info) { |
| 477 |
name := pfx + "-g" |
| 478 |
ui := &user.DefaultInfo{ |
| 479 |
Name: pfx + "-u", |
| 480 |
UID: "good-id", |
| 481 |
Groups: []string{name}, |
| 482 |
Extra: noextra} |
| 483 |
if rng.Intn(2) == 0 { |
| 484 |
ui.Groups = append([]string{mg(rng)}, ui.Groups...) |
| 485 |
} else { |
| 486 |
ui.Groups = append(ui.Groups, mg(rng)) |
| 487 |
} |
| 488 |
if rng.Intn(3) == 0 { |
| 489 |
ui.Groups = append([]string{pfx + "-h"}, ui.Groups...) |
| 490 |
} |
| 491 |
if rng.Intn(3) == 0 { |
| 492 |
ui.Groups = append(ui.Groups, pfx+"-i") |
| 493 |
} |
| 494 |
skipper := &user.DefaultInfo{ |
| 495 |
Name: pfx + "-u", |
| 496 |
UID: "bad-id", |
| 497 |
Groups: []string{pfx + "-j", mg(rng)}, |
| 498 |
Extra: noextra} |
| 499 |
if rng.Intn(2) == 0 { |
| 500 |
skipper.Groups = append(skipper.Groups, pfx+"-k") |
| 501 |
} |
| 502 |
return &flowcontrol.GroupSubject{Name: name}, []user.Info{ui}, []user.Info{skipper} |
| 503 |
} |
| 504 |
|
| 505 |
func genServiceAccount(rng *rand.Rand, pfx string) (*flowcontrol.ServiceAccountSubject, []user.Info, []user.Info) { |
| 506 |
ns := pfx + "-ns" |
| 507 |
name := pfx + "-n" |
| 508 |
mname := name |
| 509 |
if rng.Float32() < 0.05 { |
| 510 |
mname = "*" |
| 511 |
} |
| 512 |
mui := &user.DefaultInfo{ |
| 513 |
Name: fmt.Sprintf("system:serviceaccount:%s:%s", ns, name), |
| 514 |
UID: "good-id", |
| 515 |
Groups: []string{pfx + "-g1", mg(rng), pfx + "-g2"}, |
| 516 |
Extra: noextra} |
| 517 |
var skips []user.Info |
| 518 |
if mname == "*" || rng.Intn(2) == 0 { |
| 519 |
skips = []user.Info{&user.DefaultInfo{ |
| 520 |
Name: fmt.Sprintf("system:serviceaccount:%sx:%s", ns, name), |
| 521 |
UID: "bad-id", |
| 522 |
Groups: mui.Groups, |
| 523 |
Extra: mui.Extra}} |
| 524 |
} else { |
| 525 |
skips = []user.Info{&user.DefaultInfo{ |
| 526 |
Name: fmt.Sprintf("system:serviceaccount:%s:%sx", ns, name), |
| 527 |
UID: "bad-id", |
| 528 |
Groups: mui.Groups, |
| 529 |
Extra: mui.Extra}} |
| 530 |
} |
| 531 |
return &flowcontrol.ServiceAccountSubject{Namespace: ns, Name: mname}, []user.Info{mui}, skips |
| 532 |
} |
| 533 |
|
| 534 |
// genResourceRule randomly generates a valid ResourcePolicyRule and lists |
| 535 |
// of matching and non-matching `*request.RequestInfo`. |
| 536 |
func genResourceRule(rng *rand.Rand, pfx string, mayMatchClusterScope, matchAllResources, someMatchesAllResources bool) (flowcontrol.ResourcePolicyRule, []*request.RequestInfo, []*request.RequestInfo) { |
| 537 |
namespaces := []string{pfx + "-n1", pfx + "-n2", pfx + "-n3"} |
| 538 |
rnamespaces := namespaces |
| 539 |
if mayMatchClusterScope && rng.Float32() < 0.1 { |
| 540 |
namespaces[0] = "" |
| 541 |
rnamespaces = namespaces[1:] |
| 542 |
} |
| 543 |
rr := flowcontrol.ResourcePolicyRule{ |
| 544 |
Verbs: []string{pfx + "-v1", pfx + "-v2", pfx + "-v3"}, |
| 545 |
APIGroups: []string{pfx + ".g1", pfx + ".g2", pfx + ".g3"}, |
| 546 |
Resources: []string{pfx + "-r1s", pfx + "-r2s", pfx + "-r3s"}, |
| 547 |
ClusterScope: namespaces[0] == "", |
| 548 |
Namespaces: rnamespaces} |
| 549 |
matchingRIs := genRRIs(rng, 3, rr.Verbs, rr.APIGroups, rr.Resources, namespaces) |
| 550 |
var skippingRIs []*request.RequestInfo |
| 551 |
if !someMatchesAllResources { |
| 552 |
skipNSs := []string{pfx + "-n4", pfx + "-n5", pfx + "-n6"} |
| 553 |
if mayMatchClusterScope && rr.Namespaces[0] != "" && rng.Float32() < 0.1 { |
| 554 |
skipNSs[0] = "" |
| 555 |
} |
| 556 |
skippingRIs = genRRIs(rng, 3, |
| 557 |
[]string{pfx + "-v4", pfx + "-v5", pfx + "-v6"}, |
| 558 |
[]string{pfx + ".g4", pfx + ".g5", pfx + ".g6"}, |
| 559 |
[]string{pfx + "-r4s", pfx + "-r5s", pfx + "-r6s"}, |
| 560 |
skipNSs) |
| 561 |
} |
| 562 |
// choose a proper subset of fields to wildcard; only matters if not matching all |
| 563 |
starMask := rng.Intn(15) |
| 564 |
if matchAllResources || starMask&1 == 1 && rng.Float32() < 0.1 { |
| 565 |
rr.Verbs = []string{flowcontrol.VerbAll} |
| 566 |
} |
| 567 |
if matchAllResources || starMask&2 == 2 && rng.Float32() < 0.1 { |
| 568 |
rr.APIGroups = []string{flowcontrol.APIGroupAll} |
| 569 |
} |
| 570 |
if matchAllResources || starMask&4 == 4 && rng.Float32() < 0.1 { |
| 571 |
rr.Resources = []string{flowcontrol.ResourceAll} |
| 572 |
} |
| 573 |
if matchAllResources || starMask&8 == 8 && rng.Float32() < 0.1 { |
| 574 |
rr.ClusterScope = true |
| 575 |
rr.Namespaces = []string{flowcontrol.NamespaceEvery} |
| 576 |
} |
| 577 |
return rr, matchingRIs, skippingRIs |
| 578 |
} |
| 579 |
|
| 580 |
func genRRIs(rng *rand.Rand, m int, verbs, apiGroups, resources, namespaces []string) []*request.RequestInfo { |
| 581 |
nv := len(verbs) |
| 582 |
ng := len(apiGroups) |
| 583 |
nr := len(resources) |
| 584 |
nn := len(namespaces) |
| 585 |
coords := chooseInts(rng, nv*ng*nr*nn, m) |
| 586 |
ans := make([]*request.RequestInfo, 0, m) |
| 587 |
for _, coord := range coords { |
| 588 |
ans = append(ans, &request.RequestInfo{ |
| 589 |
IsResourceRequest: true, |
| 590 |
Verb: verbs[coord%nv], |
| 591 |
APIGroup: apiGroups[coord/nv%ng], |
| 592 |
Resource: resources[coord/nv/ng%nr], |
| 593 |
Namespace: namespaces[coord/nv/ng/nr]}) |
| 594 |
} |
| 595 |
return ans |
| 596 |
} |
| 597 |
|
| 598 |
func genNRRIs(rng *rand.Rand, m int, verbs, urls []string) []*request.RequestInfo { |
| 599 |
nv := len(verbs) |
| 600 |
nu := len(urls) |
| 601 |
coords := chooseInts(rng, nv*nu, m) |
| 602 |
ans := make([]*request.RequestInfo, 0, m) |
| 603 |
for _, coord := range coords { |
| 604 |
ri := &request.RequestInfo{ |
| 605 |
IsResourceRequest: false, |
| 606 |
Verb: verbs[coord%nv], |
| 607 |
Path: urls[coord/nv]} |
| 608 |
if rng.Intn(2) == 1 { |
| 609 |
ri.Path = ri.Path + "/more" |
| 610 |
} |
| 611 |
ans = append(ans, ri) |
| 612 |
} |
| 613 |
return ans |
| 614 |
} |
| 615 |
|
| 616 |
func chooseInts(rng *rand.Rand, n, m int) []int { |
| 617 |
ans := sets.NewInt() |
| 618 |
for len(ans) < m { |
| 619 |
i := rng.Intn(n) |
| 620 |
if ans.Has(i) { |
| 621 |
continue |
| 622 |
} |
| 623 |
ans.Insert(i) |
| 624 |
} |
| 625 |
return ans.List() |
| 626 |
} |
| 627 |
|
| 628 |
// genNonResourceRule returns a randomly generated valid |
| 629 |
// NonResourcePolicyRule and lists of matching and non-matching |
| 630 |
// `*request.RequestInfo`. |
| 631 |
func genNonResourceRule(rng *rand.Rand, pfx string, matchAllNonResources, someMatchesAllNonResources bool) (flowcontrol.NonResourcePolicyRule, []*request.RequestInfo, []*request.RequestInfo) { |
| 632 |
nrr := flowcontrol.NonResourcePolicyRule{ |
| 633 |
Verbs: []string{pfx + "-v1", pfx + "-v2", pfx + "-v3"}, |
| 634 |
NonResourceURLs: []string{"/" + pfx + "/g/p1", "/" + pfx + "/g/p2", "/" + pfx + "/g/p3"}, |
| 635 |
} |
| 636 |
matchingRIs := genNRRIs(rng, 3, nrr.Verbs, nrr.NonResourceURLs) |
| 637 |
var skippingRIs []*request.RequestInfo |
| 638 |
if !someMatchesAllNonResources { |
| 639 |
skippingRIs = genNRRIs(rng, 3, |
| 640 |
[]string{pfx + "-v4", pfx + "-v5", pfx + "-v6"}, |
| 641 |
[]string{"/" + pfx + "/b/p1", "/" + pfx + "/b/p2", "/" + pfx + "/b/p3"}) |
| 642 |
} |
| 643 |
// choose a proper subset of fields to consider wildcarding; only matters if not matching all |
| 644 |
starMask := rng.Intn(3) |
| 645 |
if matchAllNonResources || starMask&1 == 1 && rng.Float32() < 0.1 { |
| 646 |
nrr.Verbs = []string{flowcontrol.VerbAll} |
| 647 |
} |
| 648 |
if matchAllNonResources || starMask&2 == 2 && rng.Float32() < 0.1 { |
| 649 |
nrr.NonResourceURLs = []string{"*"} |
| 650 |
} else { |
| 651 |
nrr.NonResourceURLs[rng.Intn(3)] = "/" + pfx + "/g/*" |
| 652 |
nrr.NonResourceURLs[rng.Intn(3)] = "/" + pfx + "/g" |
| 653 |
} |
| 654 |
return nrr, matchingRIs, skippingRIs |
| 655 |
} |
| 656 |
|
| 657 |
func pickSetString(rng *rand.Rand, set sets.String) string { |
| 658 |
i, n := 0, rng.Intn(len(set)) |
| 659 |
for s := range set { |
| 660 |
if i == n { |
| 661 |
return s |
| 662 |
} |
| 663 |
i++ |
| 664 |
} |
| 665 |
panic("empty set") |
| 666 |
} |