syz-cluster: consider multiple trees during triage

Even if the target tree is specified in the patch title, there happen to
be cases when it's actually only applicable to some other trees.

So instead of choosing one particular tree and sticking to it, obtain an
ordered list of candidates and pick the first to which the series
actually applies.

3 files changed, 89 insertions, 63 deletions

diff --git a/syz-cluster/pkg/triage/tree.go b/syz-cluster/pkg/triage/tree.go
index 34bcb0d02..4d0faeeaf 100644
--- a/syz-cluster/pkg/triage/tree.go
+++ b/syz-cluster/pkg/triage/tree.go
@@ -4,12 +4,14 @@
 package triage
 
 import (
+	"sort"
 	"strings"
 
 	"github.com/google/syzkaller/syz-cluster/pkg/api"
 )
 
-func SelectTree(series *api.Series, trees []*api.Tree) *api.Tree {
+// SelectTrees returns an ordered list of git trees to apply the series to.
+func SelectTrees(series *api.Series, trees []*api.Tree) []*api.Tree {
 	seriesCc := map[string]bool{}
 	for _, cc := range series.Cc {
 		seriesCc[strings.ToLower(cc)] = true
@@ -18,11 +20,12 @@ func SelectTree(series *api.Series, trees []*api.Tree) *api.Tree {
 	for _, tag := range series.SubjectTags {
 		tagsMap[tag] = true
 	}
-	var best *api.Tree
+	var result []*api.Tree
 	for _, tree := range trees {
 		if tagsMap[tree.Name] {
-			// If the tree was directly mentioned in the patch subject, just return it.
-			return tree
+			// If the tree was directly mentioned in the patch subject, always take it.
+			result = append(result, tree)
+			continue
 		}
 		intersects := false
 		for _, cc := range tree.EmailLists {
@@ -34,9 +37,14 @@ func SelectTree(series *api.Series, trees []*api.Tree) *api.Tree {
 		if len(tree.EmailLists) > 0 && !intersects {
 			continue
 		}
-		if best == nil || tree.Priority > best.Priority {
-			best = tree
-		}
+		result = append(result, tree)
 	}
-	return best
+	sort.SliceStable(result, func(i, j int) bool {
+		a, b := result[i], result[j]
+		if tagsMap[a.Name] != tagsMap[b.Name] {
+			return tagsMap[a.Name]
+		}
+		return a.Priority > b.Priority
+	})
+	return result
 }
diff --git a/syz-cluster/pkg/triage/tree_test.go b/syz-cluster/pkg/triage/tree_test.go
index 2a5dfd721..81352700b 100644
--- a/syz-cluster/pkg/triage/tree_test.go
+++ b/syz-cluster/pkg/triage/tree_test.go
@@ -10,7 +10,7 @@ import (
 	"github.com/stretchr/testify/assert"
 )
 
-func TestSelectTree(t *testing.T) {
+func TestSelectTrees(t *testing.T) {
 	trees := []*api.Tree{
 		{
 			Name:       "mainline",
@@ -28,33 +28,39 @@ func TestSelectTree(t *testing.T) {
 			Priority:   2,
 		},
 		{
-			Name:     "test",
-			Priority: api.TreePriorityNever,
+			Name:       "bpf",
+			EmailLists: []string{"bpf@list"},
+			Priority:   3,
+		},
+		{
+			Name:       "test",
+			Priority:   api.TreePriorityNever,
+			EmailLists: []string{"test@list"},
 		},
 	}
 	tests := []struct {
 		testName string
-		result   string
+		result   []string
 		series   *api.Series
 	}{
 		{
 			testName: "only-net",
-			result:   "net",
+			result:   []string{"net", "mainline"},
 			series:   &api.Series{Cc: []string{"net@list"}},
 		},
 		{
 			testName: "prefer-wireless",
-			result:   "wireless",
+			result:   []string{"wireless", "net", "mainline"},
 			series:   &api.Series{Cc: []string{"net@list", "wireless@list"}},
 		},
 		{
 			testName: "fallback",
-			result:   "mainline",
+			result:   []string{"mainline"},
 			series:   &api.Series{Cc: []string{"unknown@list"}},
 		},
 		{
 			testName: "prefer-direct-match",
-			result:   "test",
+			result:   []string{"test", "wireless", "net", "mainline"},
 			series: &api.Series{
 				Cc:          []string{"net@list", "wireless@list"},
 				SubjectTags: []string{"test"},
@@ -64,9 +70,12 @@ func TestSelectTree(t *testing.T) {
 
 	for _, test := range tests {
 		t.Run(test.testName, func(t *testing.T) {
-			ret := SelectTree(test.series, trees)
-			assert.NotNil(t, ret)
-			assert.Equal(t, test.result, ret.Name)
+			ret := SelectTrees(test.series, trees)
+			var retNames []string
+			for _, tree := range ret {
+				retNames = append(retNames, tree.Name)
+			}
+			assert.Equal(t, test.result, retNames)
 		})
 	}
 }
diff --git a/syz-cluster/workflow/triage-step/main.go b/syz-cluster/workflow/triage-step/main.go
index 9fa7a50bd..6aaeab84a 100644
--- a/syz-cluster/workflow/triage-step/main.go
+++ b/syz-cluster/workflow/triage-step/main.go
@@ -63,55 +63,64 @@ func getVerdict(ctx context.Context, tracer debugtracer.DebugTracer, client *api
 		// TODO: the workflow step must be retried.
 		return nil, fmt.Errorf("failed to query series: %w", err)
 	}
-	trees, err := client.GetTrees(ctx)
+	treesResp, err := client.GetTrees(ctx)
 	if err != nil {
 		return nil, fmt.Errorf("failed to query trees: %w", err)
 	}
-	tree := triage.SelectTree(series, trees.Trees)
-	if tree == nil {
+	selectedTrees := triage.SelectTrees(series, treesResp.Trees)
+	if len(selectedTrees) == 0 {
 		return &api.TriageResult{
-			SkipReason: "no suitable base kernel tree found",
+			SkipReason: "no suitable base kernel trees found",
 		}, nil
 	}
-	tracer.Log("selected tree %q", tree.Name)
-	arch := "amd64"
-	lastBuild, err := client.LastBuild(ctx, &api.LastBuildReq{
-		Arch:       arch,
-		ConfigName: tree.KernelConfig,
-		TreeName:   tree.Name,
-		Status:     api.BuildSuccess,
-	})
-	if err != nil {
-		// TODO: the workflow step must be retried.
-		return nil, fmt.Errorf("failed to query the last build: %w", err)
-	}
-	tracer.Log("last build: %q", lastBuild)
-	selector := triage.NewCommitSelector(ops, tracer)
-	result, err := selector.Select(series, tree, lastBuild)
-	if err != nil {
-		// TODO: the workflow step must be retried.
-		return nil, fmt.Errorf("failed to run the commit selector: %w", err)
-	} else if result.Commit == "" {
-		return &api.TriageResult{
-			SkipReason: "failed to find the base commit: " + result.Reason,
-		}, nil
-	}
-	tracer.Log("selected base commit: %s", result.Commit)
-	base := api.BuildRequest{
-		TreeName:   tree.Name,
-		TreeURL:    tree.URL,
-		ConfigName: tree.KernelConfig,
-		CommitHash: result.Commit,
-		Arch:       arch,
-	}
-	ret := &api.TriageResult{
-		Fuzz: &api.FuzzConfig{
-			Base:      base,
-			Patched:   base,
-			Config:    tree.FuzzConfig,
-			CorpusURL: tree.CorpusURL(),
-		},
+	var triageResult *api.TriageResult
+	for _, tree := range selectedTrees {
+		tracer.Log("considering tree %q", tree.Name)
+		arch := "amd64"
+		lastBuild, err := client.LastBuild(ctx, &api.LastBuildReq{
+			Arch:       arch,
+			ConfigName: tree.KernelConfig,
+			TreeName:   tree.Name,
+			Status:     api.BuildSuccess,
+		})
+		if err != nil {
+			// TODO: the workflow step must be retried.
+			return nil, fmt.Errorf("failed to query the last build for %q: %w", tree.Name, err)
+		}
+		tracer.Log("%q's last build: %q", tree.Name, lastBuild)
+		selector := triage.NewCommitSelector(ops, tracer)
+		result, err := selector.Select(series, tree, lastBuild)
+		if err != nil {
+			// TODO: the workflow step must be retried.
+			return nil, fmt.Errorf("failed to run the commit selector for %q: %w", tree.Name, err)
+		} else if result.Commit == "" {
+			// If we fail to find a suitable commit for all the trees, return an error just about the first one.
+			if triageResult == nil {
+				triageResult = &api.TriageResult{
+					SkipReason: "failed to find a base commit: " + result.Reason,
+				}
+			}
+			tracer.Log("failed to find a base commit for %q", tree.Name)
+			continue
+		}
+		tracer.Log("selected base commit: %s", result.Commit)
+		base := api.BuildRequest{
+			TreeName:   tree.Name,
+			TreeURL:    tree.URL,
+			ConfigName: tree.KernelConfig,
+			CommitHash: result.Commit,
+			Arch:       arch,
+		}
+		triageResult = &api.TriageResult{
+			Fuzz: &api.FuzzConfig{
+				Base:      base,
+				Patched:   base,
+				Config:    tree.FuzzConfig,
+				CorpusURL: tree.CorpusURL(),
+			},
+		}
+		triageResult.Fuzz.Patched.SeriesID = series.ID
+		break
 	}
-	ret.Fuzz.Patched.SeriesID = series.ID
-	return ret, nil
+	return triageResult, nil
 }