From 50b2f41ed948a2a47420d8edc9abca2d477eccfb Mon Sep 17 00:00:00 2001
From: Aleksandr Nogikh <nogikh@google.com>
Date: Fri, 10 Feb 2023 11:38:05 +0100
Subject: pkg/subsystem: detect loops on the go

This lets us reduce the amount of code in parents.go.
---
 pkg/subsystem/entity/entities.go    |  3 +++
 pkg/subsystem/linux/parents.go      | 46 +------------------------------------
 pkg/subsystem/linux/parents_test.go | 15 ------------
 3 files changed, 4 insertions(+), 60 deletions(-)

(limited to 'pkg')

diff --git a/pkg/subsystem/entity/entities.go b/pkg/subsystem/entity/entities.go
index 9d1d8e5a5..e2b29a7f3 100644
--- a/pkg/subsystem/entity/entities.go
+++ b/pkg/subsystem/entity/entities.go
@@ -21,6 +21,9 @@ func (subsystem *Subsystem) ReachableParents() map[*Subsystem]struct{} {
 			return
 		}
 		for _, p := range node.Parents {
+			if p == subsystem {
+				panic("loop in the parents relation")
+			}
 			ret[p] = struct{}{}
 			dfs(p)
 		}
diff --git a/pkg/subsystem/linux/parents.go b/pkg/subsystem/linux/parents.go
index 6d27565bf..fdea4a62f 100644
--- a/pkg/subsystem/linux/parents.go
+++ b/pkg/subsystem/linux/parents.go
@@ -4,8 +4,6 @@
 package linux
 
 import (
-	"fmt"
-
 	"github.com/google/syzkaller/pkg/subsystem/entity"
 	"github.com/google/syzkaller/pkg/subsystem/match"
 )
@@ -39,12 +37,9 @@ func setParents(matrix *match.CoincidenceMatrix, list []*entity.Subsystem) error
 		// Demand that >= 50% paths are related.
 		if 2*count/matrix.Count(a) >= 1 && matrix.Count(a) < matrix.Count(b) {
 			a.Parents = append(a.Parents, b)
+			a.ReachableParents() // make sure we haven't created a loop
 		}
 	})
-	// Just in case.
-	if loopsExist(list) {
-		return fmt.Errorf("there are loops in the parents relation")
-	}
 	transitiveReduction(list)
 	return nil
 }
@@ -124,42 +119,3 @@ func transitiveReduction(list []*entity.Subsystem) {
 		s.Parents = newParents
 	}
 }
-
-// loopsExist is a helper method that verifies that the resulting graph has no loops.
-func loopsExist(list []*entity.Subsystem) bool {
-	type graphNode struct {
-		obj     *entity.Subsystem
-		entered bool
-		left    bool
-	}
-	nodes := []*graphNode{}
-	objToNode := map[*entity.Subsystem]*graphNode{}
-	for _, obj := range list {
-		node := &graphNode{obj: obj}
-		nodes = append(nodes, node)
-		objToNode[obj] = node
-	}
-	var dfs func(*graphNode) bool
-	dfs = func(node *graphNode) bool {
-		if node.left {
-			return false
-		}
-		if node.entered {
-			// We've found a cycle.
-			return true
-		}
-		node.entered = true
-		anyLoop := false
-		for _, parent := range node.obj.Parents {
-			anyLoop = anyLoop || dfs(objToNode[parent])
-		}
-		node.left = true
-		return anyLoop
-	}
-	for _, node := range nodes {
-		if dfs(node) {
-			return true
-		}
-	}
-	return false
-}
diff --git a/pkg/subsystem/linux/parents_test.go b/pkg/subsystem/linux/parents_test.go
index f1942671d..dde13177d 100644
--- a/pkg/subsystem/linux/parents_test.go
+++ b/pkg/subsystem/linux/parents_test.go
@@ -69,21 +69,6 @@ func TestDropDuplicateSubsystems(t *testing.T) {
 	assert.ElementsMatch(t, ret, expected)
 }
 
-func TestLoopsDoExist(t *testing.T) {
-	a := &entity.Subsystem{}
-	b := &entity.Subsystem{Parents: []*entity.Subsystem{a}}
-	c := &entity.Subsystem{Parents: []*entity.Subsystem{b}}
-	a.Parents = []*entity.Subsystem{c}
-	assert.True(t, loopsExist([]*entity.Subsystem{a, b, c}))
-}
-
-func TestLoopsDoNotExist(t *testing.T) {
-	a := &entity.Subsystem{}
-	b := &entity.Subsystem{Parents: []*entity.Subsystem{a}}
-	c := &entity.Subsystem{Parents: []*entity.Subsystem{b}}
-	assert.False(t, loopsExist([]*entity.Subsystem{a, b, c}))
-}
-
 func TestTransitiveReduction(t *testing.T) {
 	// (d, c), (c, b), (b, a)
 	// (d, a)
-- 
cgit mrf-deployment