testplan: Allow multiple board values in CTPv1 compatibility mode.
- The current test plans allow for rules that specify a list of
boards to choose one of, e.g. `only_keep_one_suite_from_each_group`
(https://source.chromium.org/chromium/chromiumos/infra/proto/+/HEAD:src/testplans/source_tree_test_config.proto;l=33;drc=212ee2d69622a9e9026548f7d789ee4e108c4893).
The choice is based off which boards produced a critical build
(i.e. choose a board that had a successful build, using criticality
to break ties). If there are multiple choices which produced a
critical build, choose randomly with probability proportional to
the priorties configured in a static priority list
(http://cs/chromeos_internal/infra/config/testingconfig/generated/board_priority.cfg).
- This is needed in the chromite example, see
http://cs/chromeos_internal/infra/config/testingconfig/source_tree_test_config_main.star;l=507;rcl=0c479a9332f94eac32c76dd16aeb924fbcac571e.
BUG=b:218319842
TEST=CQ
Change-Id: Ia83516ddeaa3961110f2078e448f20a2fd8a17d1
Reviewed-on: https://chromium-review.googlesource.com/c/chromiumos/platform/dev-util/+/3511380
Reviewed-by: Tim Bain <tbain@google.com>
Commit-Queue: Andrew Lamb <andrewlamb@chromium.org>
Tested-by: Andrew Lamb <andrewlamb@chromium.org>
diff --git a/src/chromiumos/test/plan/cmd/testplan.go b/src/chromiumos/test/plan/cmd/testplan.go
index c121c3b..951cb80 100644
--- a/src/chromiumos/test/plan/cmd/testplan.go
+++ b/src/chromiumos/test/plan/cmd/testplan.go
@@ -13,9 +13,11 @@
"flag"
"fmt"
"io/ioutil"
+ "math/rand"
"os"
"regexp"
"strings"
+ "time"
"github.com/golang/glog"
"github.com/golang/protobuf/jsonpb"
@@ -150,6 +152,13 @@
"JSON or binary proto. Should be set iff ctpv1 is set.",
)
r.Flags.StringVar(
+ &r.boardPriorityListPath,
+ "boardprioritylist",
+ "",
+ "Path to a proto file containing a BoardPriorityList. Can be JSON"+
+ "or binary proto. Should be set iff ctpv1 is set.",
+ )
+ r.Flags.StringVar(
&r.out,
"out",
"",
@@ -177,6 +186,7 @@
flatConfigListPath string
ctpV1 bool
generateTestPlanReqPath string
+ boardPriorityListPath string
out string
textSummaryOut string
}
@@ -331,6 +341,10 @@
return errors.New("-generatetestplanreq must be set iff -out is set.")
}
+ if r.ctpV1 != (r.boardPriorityListPath != "") {
+ return errors.New("-boardprioritylist must be set iff -out is set.")
+ }
+
return nil
}
@@ -391,7 +405,15 @@
return err
}
- resp, err := compatibility.ToCTP1(hwTestPlans, generateTestPlanReq, dutAttributeList)
+ boardPriorityList := &testplans.BoardPriorityList{}
+ if err := readBinaryOrJSONPb(r.boardPriorityListPath, boardPriorityList); err != nil {
+ return err
+ }
+
+ resp, err := compatibility.ToCTP1(
+ rand.New(rand.NewSource(time.Now().Unix())),
+ hwTestPlans, generateTestPlanReq, dutAttributeList, boardPriorityList,
+ )
if err != nil {
return err
}
diff --git a/src/chromiumos/test/plan/internal/compatibility/convertv1.go b/src/chromiumos/test/plan/internal/compatibility/convertv1.go
index 8746123..102a7df 100644
--- a/src/chromiumos/test/plan/internal/compatibility/convertv1.go
+++ b/src/chromiumos/test/plan/internal/compatibility/convertv1.go
@@ -8,6 +8,9 @@
import (
"fmt"
+ "math/rand"
+
+ "chromiumos/test/plan/internal/compatibility/priority"
"github.com/golang/glog"
testpb "go.chromium.org/chromiumos/config/go/test/api"
@@ -22,9 +25,8 @@
)
// getAttrFromCriteria finds the DutCriterion with attribute id attr in
-// criteria. If the DutCriterion is not found or has more than one value, an
-// error is returned.
-func getAttrFromCriteria(criteria []*testpb.DutCriterion, attr *testpb.DutAttribute) (string, error) {
+// criteria. If the DutCriterion is not found an error is returned.
+func getAttrFromCriteria(criteria []*testpb.DutCriterion, attr *testpb.DutAttribute) ([]string, error) {
for _, criterion := range criteria {
isAttr := false
if criterion.GetAttributeId().GetValue() == attr.GetId().GetValue() {
@@ -39,15 +41,54 @@
}
if isAttr {
- if len(criterion.GetValues()) != 1 {
- return "", fmt.Errorf("only DutCriterion with exactly one value supported, got %q", criterion)
+ if len(criterion.GetValues()) == 0 {
+ return nil, fmt.Errorf("only DutCriterion with at least one value supported, got %q", criterion)
}
- return criterion.GetValues()[0], nil
+ return criterion.GetValues(), nil
}
}
- return "", fmt.Errorf("attribute %q not found in DutCriterion %q", attr.GetId().GetValue(), criteria)
+ return nil, fmt.Errorf("attribute %q not found in DutCriterion %q", attr.GetId().GetValue(), criteria)
+}
+
+// Chooses a program from the options in programs to test. The choice is
+// determined by:
+// 1. Choose a program with a critial completed build. If there are multiple
+// programs, choose with prioritySelector.
+// 2. Choose a program with a non-critial completed build. If there are multiple
+// programs, choose with prioritySelector.
+// 3. Choose a program with prioritySelector.
+func chooseProgramToTest(
+ pool string,
+ programs []string,
+ buildInfos map[string]*buildInfo,
+ prioritySelector *priority.RandomWeightedSelector,
+) (string, error) {
+ var criticalPrograms, completedPrograms []string
+ for _, program := range programs {
+ buildInfo, found := buildInfos[program]
+ if found {
+ completedPrograms = append(completedPrograms, program)
+
+ if buildInfo.criticality == bbpb.Trinary_YES {
+ criticalPrograms = append(criticalPrograms, program)
+ }
+ }
+ }
+
+ if len(criticalPrograms) > 0 {
+ glog.V(2).Infof("Choosing between critical programs: %q", criticalPrograms)
+ return prioritySelector.Select(pool, criticalPrograms)
+ }
+
+ if len(completedPrograms) > 0 {
+ glog.V(2).Infof("Choosing between completed programs: %q", completedPrograms)
+ return prioritySelector.Select(pool, completedPrograms)
+ }
+
+ glog.V(2).Info("No completed programs found.")
+ return prioritySelector.Select(pool, programs)
}
// extractFromProtoStruct returns the path pointed to by fields. For example,
@@ -100,6 +141,7 @@
type buildInfo struct {
buildTarget string
builderName string
+ criticality bbpb.Trinary
payload *testplans.BuildPayload
}
@@ -184,6 +226,7 @@
buildInfos = append(buildInfos, &buildInfo{
buildTarget: buildTarget,
builderName: build.GetBuilder().GetBuilder(),
+ criticality: build.GetCritical(),
payload: &testplans.BuildPayload{
ArtifactsGsBucket: artifacts_gs_bucket,
ArtifactsGsPath: artifacts_gs_path,
@@ -205,8 +248,11 @@
// extractSuiteInfos returns a map from program name to suiteInfos for the
// program. There is one suiteInfo per CoverageRule in hwTestPlans.
func extractSuiteInfos(
+ rnd *rand.Rand,
hwTestPlans []*test_api_v1.HWTestPlan,
dutAttributeList *testpb.DutAttributeList,
+ boardPriorityList *testplans.BoardPriorityList,
+ boardToBuildInfo map[string]*buildInfo,
) (map[string][]*suiteInfo, error) {
// Find the program and pool attributes in the DutAttributeList.
var programAttr, poolAttr *testpb.DutAttribute
@@ -227,6 +273,10 @@
}
programToSuiteInfos := map[string][]*suiteInfo{}
+ prioritySelector := priority.NewRandomWeightedSelector(
+ rnd,
+ boardPriorityList,
+ )
for _, hwTestPlan := range hwTestPlans {
for _, rule := range hwTestPlan.GetCoverageRules() {
@@ -236,20 +286,34 @@
dutTarget := rule.GetDutTargets()[0]
- program, err := getAttrFromCriteria(dutTarget.GetCriteria(), programAttr)
+ pools, err := getAttrFromCriteria(dutTarget.GetCriteria(), poolAttr)
if err != nil {
return nil, err
}
- if _, ok := programToSuiteInfos[program]; !ok {
- programToSuiteInfos[program] = []*suiteInfo{}
+ if len(pools) != 1 {
+ return nil, fmt.Errorf("only DutCriteria with exactly one \"pool\" argument are supported, got %q", pools)
}
- pool, err := getAttrFromCriteria(dutTarget.GetCriteria(), poolAttr)
+ pool := pools[0]
+
+ programs, err := getAttrFromCriteria(dutTarget.GetCriteria(), programAttr)
if err != nil {
return nil, err
}
+ chosenProgram, err := chooseProgramToTest(
+ pool, programs, boardToBuildInfo, prioritySelector,
+ )
+ if err != nil {
+ return nil, err
+ }
+ glog.V(2).Infof("chose program %q from possible programs %q", chosenProgram, programs)
+
+ if _, ok := programToSuiteInfos[chosenProgram]; !ok {
+ programToSuiteInfos[chosenProgram] = []*suiteInfo{}
+ }
+
if len(dutTarget.GetCriteria()) != 2 {
return nil, fmt.Errorf(
"expected DutTarget to use exactly criteria %q and %q, got %q",
@@ -264,10 +328,10 @@
}
for _, id := range testCaseIds.GetTestCaseIds() {
- programToSuiteInfos[program] = append(
- programToSuiteInfos[program],
+ programToSuiteInfos[chosenProgram] = append(
+ programToSuiteInfos[chosenProgram],
&suiteInfo{
- program: program,
+ program: chosenProgram,
pool: pool,
suite: id.Value,
})
@@ -288,24 +352,37 @@
// - Both the "attr-program" and "swarming-pool" DutAttributes must be used in
// each DutTarget, and only these DutAttributes are allowed, i.e. each
// DutTarget must use exactly these attributes.
-// - Only one value per DutCriterion is allowed, e.g. a rule that specifies a
-// test should run on either "programA" or "programB" is not allowed.
+// - Multiple values for "attr-program" are allowed, a program will be chosen
+// randomly proportional to the board's priority in boardPriorityList
+// (lowest priority is most likely to get chosen, negative priorities are
+// allowed, programs without a priority get priority 0).
// - Only TestCaseIds are supported (no tag-based testing).
//
// generateTestPlanReq is needed to provide Build protos for the builds being
// tested. dutAttributeList must contain the "attr-program" and "swarming-pool"
// DutAttributes.
func ToCTP1(
+ rnd *rand.Rand,
hwTestPlans []*test_api_v1.HWTestPlan,
generateTestPlanReq *testplans.GenerateTestPlanRequest,
dutAttributeList *testpb.DutAttributeList,
+ boardPriorityList *testplans.BoardPriorityList,
) (*testplans.GenerateTestPlanResponse, error) {
buildInfos, err := parseBuildProtos(generateTestPlanReq.GetBuildbucketProtos())
if err != nil {
return nil, err
}
- programToSuiteInfos, err := extractSuiteInfos(hwTestPlans, dutAttributeList)
+ // Form maps from board to buildInfo, which will be needed by calls to
+ // extractSuiteInfos.
+ boardToBuildInfo := map[string]*buildInfo{}
+ for _, buildInfo := range buildInfos {
+ boardToBuildInfo[buildInfo.buildTarget] = buildInfo
+ }
+
+ programToSuiteInfos, err := extractSuiteInfos(
+ rnd, hwTestPlans, dutAttributeList, boardPriorityList, boardToBuildInfo,
+ )
if err != nil {
return nil, err
}
@@ -336,6 +413,8 @@
},
},
})
+
+ glog.V(2).Infof("added HwTest %q", hwTests[len(hwTests)-1])
}
hwTestUnit := &testplans.HwTestUnit{
diff --git a/src/chromiumos/test/plan/internal/compatibility/convertv1_test.go b/src/chromiumos/test/plan/internal/compatibility/convertv1_test.go
index 6751db2..ae892a8 100644
--- a/src/chromiumos/test/plan/internal/compatibility/convertv1_test.go
+++ b/src/chromiumos/test/plan/internal/compatibility/convertv1_test.go
@@ -4,10 +4,12 @@
package compatibility_test
import (
- "chromiumos/test/plan/internal/compatibility"
+ "math/rand"
"strings"
"testing"
+ "chromiumos/test/plan/internal/compatibility"
+
"github.com/golang/protobuf/proto"
"github.com/google/go-cmp/cmp"
testpb "go.chromium.org/chromiumos/config/go/test/api"
@@ -71,13 +73,14 @@
AttributeId: &testpb.DutAttribute_Id{
Value: "attr-design",
},
- Values: []string{"boardA"},
+ // "boardA" will be chosen, since it is critical and has the lowest priority.
+ Values: []string{"boardC", "boardA", "boardB", "non-critical-board"},
},
{
AttributeId: &testpb.DutAttribute_Id{
Value: "swarming-pool",
},
- Values: []string{"testpool"},
+ Values: []string{"DUT_POOL_QUOTA"},
},
},
},
@@ -119,6 +122,7 @@
},
}),
},
+ Critical: bbpb.Trinary_YES,
}
build2 := &bbpb.Build{
@@ -143,10 +147,60 @@
},
}),
},
+ Critical: bbpb.Trinary_YES,
}
build3 := &bbpb.Build{
Builder: &bbpb.BuilderID{
+ Builder: "cq-builderC",
+ },
+ Input: &bbpb.Build_Input{
+ Properties: newStruct(t, map[string]interface{}{
+ "build_target": map[string]interface{}{
+ "name": "boardC",
+ },
+ }),
+ },
+ Output: &bbpb.Build_Output{
+ Properties: newStruct(t, map[string]interface{}{
+ "artifacts": map[string]interface{}{
+ "gs_bucket": "testgsbucket",
+ "gs_path": "testgspathC",
+ "files_by_artifact": map[string]interface{}{
+ "AUTOTEST_FILES": []interface{}{"file1", "file2"},
+ },
+ },
+ }),
+ },
+ }
+
+ build4 := &bbpb.Build{
+ Builder: &bbpb.BuilderID{
+ Builder: "non-critical-builder",
+ },
+ Input: &bbpb.Build_Input{
+ Properties: newStruct(t, map[string]interface{}{
+ "build_target": map[string]interface{}{
+ "name": "non-critical-board",
+ },
+ }),
+ },
+ Output: &bbpb.Build_Output{
+ Properties: newStruct(t, map[string]interface{}{
+ "artifacts": map[string]interface{}{
+ "gs_bucket": "testgsbucket",
+ "gs_path": "testgspath",
+ "files_by_artifact": map[string]interface{}{
+ "AUTOTEST_FILES": []interface{}{"file1", "file2"},
+ },
+ },
+ }),
+ },
+ Critical: bbpb.Trinary_NO,
+ }
+
+ build5 := &bbpb.Build{
+ Builder: &bbpb.BuilderID{
Builder: "pointless-build",
},
Output: &bbpb.Build_Output{
@@ -156,7 +210,7 @@
},
}
- build4 := &bbpb.Build{
+ build6 := &bbpb.Build{
Builder: &bbpb.BuilderID{
Builder: "no-build-target-build",
},
@@ -183,6 +237,8 @@
serializeOrFatal(t, build2),
serializeOrFatal(t, build3),
serializeOrFatal(t, build4),
+ serializeOrFatal(t, build5),
+ serializeOrFatal(t, build6),
}
}
@@ -202,12 +258,26 @@
},
}
+var boardPriorityList = &testplans.BoardPriorityList{
+ BoardPriorities: []*testplans.BoardPriority{
+ {
+ SkylabBoard: "boardA", Priority: -100,
+ },
+ {
+ SkylabBoard: "boardB", Priority: 100,
+ },
+ },
+}
+
func TestToCTP1(t *testing.T) {
req := &testplans.GenerateTestPlanRequest{
BuildbucketProtos: getSerializedBuilds(t),
}
- resp, err := compatibility.ToCTP1(hwTestPlans, req, dutAttributeList)
+ resp, err := compatibility.ToCTP1(
+ rand.New(rand.NewSource(7)),
+ hwTestPlans, req, dutAttributeList, boardPriorityList,
+ )
if err != nil {
t.Fatal(err)
}
@@ -237,7 +307,7 @@
},
Suite: "suite1",
SkylabBoard: "boardA",
- Pool: "testpool",
+ Pool: "DUT_POOL_QUOTA",
},
{
Common: &testplans.TestSuiteCommon{
@@ -246,7 +316,7 @@
},
Suite: "suite2",
SkylabBoard: "boardA",
- Pool: "testpool",
+ Pool: "DUT_POOL_QUOTA",
},
},
},
@@ -278,7 +348,7 @@
AttributeId: &testpb.DutAttribute_Id{
Value: "swarming-pool",
},
- Values: []string{"testpool"},
+ Values: []string{"DUT_POOL_QUOTA"},
},
},
},
@@ -316,6 +386,56 @@
err: "attribute \"swarming-pool\" not found in DutCriterion",
},
{
+
+ name: "missing pool DUT attribute",
+ hwTestPlans: []*test_api_v1.HWTestPlan{
+ {
+ CoverageRules: []*testpb.CoverageRule{
+ {
+ DutTargets: []*testpb.DutTarget{
+ {
+ Criteria: []*testpb.DutCriterion{
+ {
+ AttributeId: &testpb.DutAttribute_Id{
+ Value: "attr-program",
+ },
+ Values: []string{"programA"},
+ },
+ },
+ },
+ },
+ },
+ },
+ },
+ },
+ dutAttributeList: dutAttributeList,
+ },
+ {
+ name: "criteria with no values",
+ hwTestPlans: []*test_api_v1.HWTestPlan{
+ {
+ CoverageRules: []*testpb.CoverageRule{
+ {
+ DutTargets: []*testpb.DutTarget{
+ {
+ Criteria: []*testpb.DutCriterion{
+ {
+ AttributeId: &testpb.DutAttribute_Id{
+ Value: "swarming-pool",
+ },
+ Values: []string{},
+ },
+ },
+ },
+ },
+ },
+ },
+ },
+ },
+ dutAttributeList: dutAttributeList,
+ err: "only DutCriterion with at least one value supported",
+ },
+ {
name: "invalid DUT attribute",
hwTestPlans: []*test_api_v1.HWTestPlan{
{
@@ -334,7 +454,7 @@
AttributeId: &testpb.DutAttribute_Id{
Value: "swarming-pool",
},
- Values: []string{"testpool"},
+ Values: []string{"DUT_POOL_QUOTA"},
},
{
AttributeId: &testpb.DutAttribute_Id{
@@ -353,7 +473,7 @@
err: "expected DutTarget to use exactly criteria \"attr-program\" and \"swarming-pool\"",
},
{
- name: "multiple program values",
+ name: "multiple pool values",
hwTestPlans: []*test_api_v1.HWTestPlan{
{
CoverageRules: []*testpb.CoverageRule{
@@ -363,9 +483,15 @@
Criteria: []*testpb.DutCriterion{
{
AttributeId: &testpb.DutAttribute_Id{
+ Value: "swarming-pool",
+ },
+ Values: []string{"testpoolA", "testpoolB"},
+ },
+ {
+ AttributeId: &testpb.DutAttribute_Id{
Value: "attr-program",
},
- Values: []string{"programA", "programB"},
+ Values: []string{"boardA", "boardB"},
},
},
},
@@ -375,7 +501,7 @@
},
},
dutAttributeList: dutAttributeList,
- err: "only DutCriterion with exactly one value supported",
+ err: "only DutCriteria with exactly one \"pool\" argument are supported",
},
{
name: "test tags used",
@@ -396,7 +522,7 @@
AttributeId: &testpb.DutAttribute_Id{
Value: "swarming-pool",
},
- Values: []string{"testpool"},
+ Values: []string{"DUT_POOL_QUOTA"},
},
},
},
@@ -473,7 +599,10 @@
for _, tc := range testCases {
t.Run(tc.name, func(t *testing.T) {
- _, err := compatibility.ToCTP1(tc.hwTestPlans, req, tc.dutAttributeList)
+ _, err := compatibility.ToCTP1(
+ rand.New(rand.NewSource(7)),
+ tc.hwTestPlans, req, tc.dutAttributeList, boardPriorityList,
+ )
if err == nil {
t.Error("Expected error from ToCTP1")
}
diff --git a/src/chromiumos/test/plan/internal/compatibility/priority/randomweighted.go b/src/chromiumos/test/plan/internal/compatibility/priority/randomweighted.go
new file mode 100644
index 0000000..abebc1f
--- /dev/null
+++ b/src/chromiumos/test/plan/internal/compatibility/priority/randomweighted.go
@@ -0,0 +1,138 @@
+// Copyright 2022 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+package priority
+
+import (
+ "errors"
+ "fmt"
+ "math/rand"
+ "sort"
+
+ "github.com/golang/glog"
+ "go.chromium.org/chromiumos/infra/proto/go/testplans"
+)
+
+// RandomWeightedSelector selects from a list of boards, with a random choice
+// weighted by BoardPriorities. The algorithm is as follows:
+//
+// 1. The sign of priorities is flipped, so that the board with the most
+// negative configured priority now has the most positive priority.
+// 2. If a priority is not defined for a board, it is implicitly 0, as defined
+// in the BoardPriority proto comment.
+// 3. Priorities are shifted so that the minimum priority is 1.
+// 4. Priorities are divided by the sum of the shifted priorities. At this
+// point, the priorities form a probability distribution (each is in the
+// range (0, 1], and they sum to 1). Each board's probability is proportional
+// to its original configured priority, i.e. the board with the most negative
+// configured priority has the highest probability.
+// 5. Sample a board from the probability distribution.
+type RandomWeightedSelector struct {
+ rand *rand.Rand
+ boardToPriority map[string]*testplans.BoardPriority
+}
+
+// NewRandomWeightedSelector returns a RandomWeightedSelector based on
+// boardPriorityList.
+func NewRandomWeightedSelector(rand *rand.Rand, boardPriorityList *testplans.BoardPriorityList) *RandomWeightedSelector {
+ boardToPriority := make(map[string]*testplans.BoardPriority)
+ for _, boardPriority := range boardPriorityList.GetBoardPriorities() {
+ boardToPriority[boardPriority.GetSkylabBoard()] = boardPriority
+ }
+
+ return &RandomWeightedSelector{rand: rand, boardToPriority: boardToPriority}
+}
+
+// floatPriority is similar to the BoardPriority proto, but supports float
+// priorities for internal computations.
+type floatPriority struct {
+ board string
+ priority float64
+}
+
+// getPriority looks up the configured priority for a given (board, pool)
+// combination. The bool return value indicates whether a configured priority
+// was found for the combination (similar to a map's return values).
+//
+// Currently only DUT_POOL_QUOTA has priorities configured.
+// TODO(b/224916762): Modify this to look up by pool once the configuration is
+// available.
+func (rw *RandomWeightedSelector) getPriority(board, pool string) (*testplans.BoardPriority, bool) {
+ if pool != "DUT_POOL_QUOTA" {
+ glog.Warningf("no priority data configured for pool %q", pool)
+ return nil, false
+ }
+
+ pri, found := rw.boardToPriority[board]
+ return pri, found
+}
+
+// RandomWeightedSelector makes assertions that computed values fall within
+// expected ranges, e.g. probabilities are <= 1.0. Add some tolerance to avoid
+// panics due to possible small floating point imprecisions.
+const floatErrorTolerance = 0.001
+
+// Select randomly chooses a board from boards, with the probability a board is
+// chosen proportional to its configured probability.
+func (rw *RandomWeightedSelector) Select(pool string, boards []string) (string, error) {
+ if len(boards) == 0 {
+ return "", errors.New("boards must be non-empty")
+ }
+
+ var normalizedPriorities []floatPriority
+ // For each board in boards, look up its priority and store a floatPriority
+ // with the sign flipped from the configured priority. If a board is not
+ // found in the configured priorities, it gets priority 0.
+ for _, board := range boards {
+ if priority, found := rw.getPriority(board, pool); found {
+ normalizedPriorities = append(normalizedPriorities, floatPriority{
+ board: board, priority: float64(-priority.GetPriority()),
+ })
+ } else {
+ normalizedPriorities = append(normalizedPriorities, floatPriority{
+ board: board, priority: 0,
+ })
+ }
+ }
+
+ sort.SliceStable(normalizedPriorities, func(i, j int) bool {
+ return normalizedPriorities[i].priority < normalizedPriorities[j].priority
+ })
+
+ // Shift the priorities so the minimum is 1, and compute the sum of the
+ // shifted priorities.
+ minPriority := normalizedPriorities[0].priority
+ sumPriorities := 0.0
+ for i := range normalizedPriorities {
+ normalizedPriorities[i].priority -= (minPriority - 1)
+ sumPriorities += normalizedPriorities[i].priority
+ }
+
+ // Divide each priority by the sum, each priority must be in the range
+ // (0, 1] after.
+ for i := range normalizedPriorities {
+ normalizedPriorities[i].priority /= sumPriorities
+
+ if normalizedPriorities[i].priority <= 0-floatErrorTolerance || normalizedPriorities[i].priority > 1+floatErrorTolerance {
+ panic(fmt.Sprintf("normalized priorities must be in range (0, 1], got %f", normalizedPriorities[i].priority))
+ }
+ }
+
+ // randFloat is in the range [0.0, 1.0). Compute the cumulative probabilites
+ // and find the first value for which randFloat < cdf(priority).
+ randFloat := rw.rand.Float64()
+ cumulativePriority := 0.0
+ for _, priority := range normalizedPriorities {
+ cumulativePriority += priority.priority
+
+ if cumulativePriority > 1+floatErrorTolerance {
+ panic(fmt.Sprintf("cumulative priority must be <= 1, got %f", cumulativePriority))
+ }
+
+ if randFloat < cumulativePriority {
+ return priority.board, nil
+ }
+ }
+
+ panic(fmt.Sprintf("rand.Float64() is > cumulativePriority (%f > %f)", randFloat, cumulativePriority))
+}
diff --git a/src/chromiumos/test/plan/internal/compatibility/priority/randomweighted_test.go b/src/chromiumos/test/plan/internal/compatibility/priority/randomweighted_test.go
new file mode 100644
index 0000000..e6b736e
--- /dev/null
+++ b/src/chromiumos/test/plan/internal/compatibility/priority/randomweighted_test.go
@@ -0,0 +1,308 @@
+// Copyright 2022 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+package priority_test
+
+import (
+ "math"
+ "math/rand"
+ "testing"
+
+ "chromiumos/test/plan/internal/compatibility/priority"
+
+ "github.com/google/go-cmp/cmp"
+ "go.chromium.org/chromiumos/infra/proto/go/testplans"
+)
+
+func TestRandomWeighted_MixedPriorities(t *testing.T) {
+ boardPriorityList := &testplans.BoardPriorityList{
+ BoardPriorities: []*testplans.BoardPriority{
+ {
+ SkylabBoard: "boardA",
+ Priority: -100,
+ },
+ {
+ SkylabBoard: "boardB",
+ Priority: -99,
+ },
+ {
+ SkylabBoard: "boardC",
+ Priority: -50,
+ },
+ {
+ SkylabBoard: "boardD",
+ Priority: 100,
+ },
+ },
+ }
+
+ selector := priority.NewRandomWeightedSelector(
+ rand.New(rand.NewSource(7)), boardPriorityList,
+ )
+
+ counts := make(map[string]int)
+ for i := 0; i < 1000; i++ {
+ selected, err := selector.Select("DUT_POOL_QUOTA", []string{"boardA", "boardB", "boardC", "boardD", "undefinedBoard"})
+ if err != nil {
+ t.Fatal(err)
+ }
+ counts[selected] += 1
+ }
+
+ // The probabilities are computed from configured priorities as follows:
+ // 1. Flip signs: 100, 99, 50, -100.
+ // 2. Shift so minimum is 1 (and add default probability for the undefined
+ // board): 201, 200, 151, 1, 101
+ // 3. Divide by the sum (654): 0.3073, 0.3058, 0.2309, 0.0015, 0.1544
+ expected := map[string]int{
+ "boardA": 322,
+ "boardB": 303,
+ "boardC": 221,
+ "boardD": 5,
+ "undefinedBoard": 149,
+ }
+ if diff := cmp.Diff(expected, counts); diff != "" {
+ t.Errorf("Unexpected counts of chosen boards (-want +got): %s", diff)
+ }
+}
+
+func TestRandomWeighted_AllPositivePriorities(t *testing.T) {
+ boardPriorityList := &testplans.BoardPriorityList{
+ BoardPriorities: []*testplans.BoardPriority{
+ {
+ SkylabBoard: "boardA",
+ Priority: 100,
+ },
+ {
+ SkylabBoard: "boardB",
+ Priority: 50,
+ },
+ {
+ SkylabBoard: "boardC",
+ Priority: 10,
+ },
+ },
+ }
+
+ selector := priority.NewRandomWeightedSelector(
+ rand.New(rand.NewSource(7)), boardPriorityList,
+ )
+
+ counts := make(map[string]int)
+ for i := 0; i < 1000; i++ {
+ selected, err := selector.Select("DUT_POOL_QUOTA", []string{"boardA", "boardB", "boardC", "undefinedBoard"})
+ if err != nil {
+ t.Fatal(err)
+ }
+ counts[selected] += 1
+ }
+
+ // The probabilities are computed from configured priorities as follows:
+ // 1. Flip signs: -100, -50, -10
+ // 2. Shift so minimum is 1 (and add default probability for the undefined
+ // board): 1, 51, 91, 101
+ // 3. Divide by the sum (244): 0.0041, 0.2090, 0.3730, 0.4139
+ expected := map[string]int{
+ "boardA": 9,
+ "boardB": 202,
+ "boardC": 377,
+ "undefinedBoard": 412,
+ }
+ if diff := cmp.Diff(expected, counts); diff != "" {
+ t.Errorf("Unexpected counts of chosen boards (-want +got): %s", diff)
+ }
+}
+
+func TestRandomWeighted_AllNegativePriorities(t *testing.T) {
+ boardPriorityList := &testplans.BoardPriorityList{
+ BoardPriorities: []*testplans.BoardPriority{
+ {
+ SkylabBoard: "boardA",
+ Priority: -100,
+ },
+ {
+ SkylabBoard: "boardB",
+ Priority: -50,
+ },
+ {
+ SkylabBoard: "boardC",
+ Priority: -10,
+ },
+ },
+ }
+
+ selector := priority.NewRandomWeightedSelector(
+ rand.New(rand.NewSource(7)), boardPriorityList,
+ )
+
+ counts := make(map[string]int)
+ for i := 0; i < 1000; i++ {
+ selected, err := selector.Select("DUT_POOL_QUOTA", []string{"boardA", "boardB", "boardC", "undefinedBoard"})
+ if err != nil {
+ t.Fatal(err)
+ }
+ counts[selected] += 1
+ }
+
+ // The probabilities are computed from configured priorities as follows:
+ // 1. Flip signs: 100, 50, 10
+ // 2. Shift so minimum is 1 (and add default probability for the undefined
+ // board): 101, 51, 11, 1
+ // 3. Divide by the sum (164): 0.6159, 0.3110, 0.0671, 0.0061
+ expected := map[string]int{
+ "boardA": 629,
+ "boardB": 292,
+ "boardC": 68,
+ "undefinedBoard": 11,
+ }
+ if diff := cmp.Diff(expected, counts); diff != "" {
+ t.Errorf("Unexpected counts of chosen boards (-want +got): %s", diff)
+ }
+}
+
+func TestRandomWeighted_SingleBoard(t *testing.T) {
+ boardPriorityList := &testplans.BoardPriorityList{
+ BoardPriorities: []*testplans.BoardPriority{
+ {
+ SkylabBoard: "boardA",
+ Priority: -100,
+ },
+ {
+ SkylabBoard: "boardB",
+ Priority: -50,
+ },
+ {
+ SkylabBoard: "boardC",
+ Priority: -10,
+ },
+ },
+ }
+
+ selector := priority.NewRandomWeightedSelector(
+ rand.New(rand.NewSource(7)), boardPriorityList,
+ )
+
+ selected, err := selector.Select("DUT_POOL_QUOTA", []string{"boardA"})
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ if selected != "boardA" {
+ t.Errorf("expected \"boardA\" to be selected, got %q", selected)
+ }
+}
+
+func TestRandomWeighted_NoBoards(t *testing.T) {
+ boardPriorityList := &testplans.BoardPriorityList{
+ BoardPriorities: []*testplans.BoardPriority{
+ {
+ SkylabBoard: "boardA",
+ Priority: -100,
+ },
+ {
+ SkylabBoard: "boardB",
+ Priority: -50,
+ },
+ {
+ SkylabBoard: "boardC",
+ Priority: -10,
+ },
+ },
+ }
+
+ selector := priority.NewRandomWeightedSelector(
+ rand.New(rand.NewSource(7)), boardPriorityList,
+ )
+
+ _, err := selector.Select("DUT_POOL_QUOTA", []string{})
+ if err == nil {
+ t.Error("expected error from calling Select with no boards.")
+ }
+}
+
+func TestRandomWeighted_LargePriorities(t *testing.T) {
+ boardPriorityList := &testplans.BoardPriorityList{
+ BoardPriorities: []*testplans.BoardPriority{
+ {
+ SkylabBoard: "boardA",
+ Priority: -int32(math.Pow(2, 30)),
+ },
+ {
+ SkylabBoard: "boardB",
+ Priority: -int32(math.Pow(2, 29)),
+ },
+ {
+ SkylabBoard: "boardC",
+ Priority: int32(math.Pow(2, 21)),
+ },
+ },
+ }
+
+ selector := priority.NewRandomWeightedSelector(
+ rand.New(rand.NewSource(7)), boardPriorityList,
+ )
+
+ counts := make(map[string]int)
+ for i := 0; i < 1000; i++ {
+ selected, err := selector.Select("DUT_POOL_QUOTA", []string{"boardA", "boardB", "boardC", "undefinedBoard"})
+ if err != nil {
+ t.Fatal(err)
+ }
+ counts[selected] += 1
+ }
+
+ // boardA should be chosen approximately twice as much as boardB. boardC
+ // should be chosen approximately 1 / 512 choices.
+ expected := map[string]int{
+ "boardA": 679,
+ "boardB": 318,
+ "undefinedBoard": 3,
+ }
+ if diff := cmp.Diff(expected, counts); diff != "" {
+ t.Errorf("Unexpected counts of chosen boards (-want +got): %s", diff)
+ }
+}
+
+func TestRandomWeighted_UnconfiguredPool(t *testing.T) {
+ boardPriorityList := &testplans.BoardPriorityList{
+ BoardPriorities: []*testplans.BoardPriority{
+ {
+ SkylabBoard: "boardA",
+ Priority: -500,
+ },
+ {
+ SkylabBoard: "boardB",
+ Priority: -100,
+ },
+ {
+ SkylabBoard: "boardC",
+ Priority: 1000,
+ },
+ },
+ }
+
+ selector := priority.NewRandomWeightedSelector(
+ rand.New(rand.NewSource(7)), boardPriorityList,
+ )
+
+ counts := make(map[string]int)
+ for i := 0; i < 1000; i++ {
+ selected, err := selector.Select("unconfiguredpool", []string{"boardA", "boardB", "boardC", "undefinedBoard"})
+ if err != nil {
+ t.Fatal(err)
+ }
+ counts[selected] += 1
+ }
+
+ // Since there is no configuration for the pool, every board gets default
+ // priority, and should be chosen equally.
+ expected := map[string]int{
+ "boardA": 247,
+ "boardB": 258,
+ "boardC": 239,
+ "undefinedBoard": 256,
+ }
+ if diff := cmp.Diff(expected, counts); diff != "" {
+ t.Errorf("Unexpected counts of chosen boards (-want +got): %s", diff)
+ }
+}
