Add tests for container graphs

Signed-off-by: Matthew Heon <matthew.heon@gmail.com>

Closes: #557
Approved by: rhatdan

4 files changed, 336 insertions, 28 deletions

diff --git a/libpod/test_common.go b/libpod/common_test.go
index 69dcf70ac..01dca7acb 100644
--- a/libpod/test_common.go
+++ b/libpod/common_test.go
@@ -4,6 +4,7 @@ import (
 	"encoding/json"
 	"net"
 	"path/filepath"
+	"strings"
 	"testing"
 	"time"
 
@@ -13,7 +14,6 @@ import (
 	"github.com/stretchr/testify/assert"
 )
 
-// nolint
 func getTestContainer(id, name, locksDir string) (*Container, error) {
 	ctr := &Container{
 		config: &ContainerConfig{
@@ -91,7 +91,6 @@ func getTestContainer(id, name, locksDir string) (*Container, error) {
 	return ctr, nil
 }
 
-// nolint
 func getTestPod(id, name, locksDir string) (*Pod, error) {
 	pod := &Pod{
 		config: &PodConfig{
@@ -112,9 +111,32 @@ func getTestPod(id, name, locksDir string) (*Pod, error) {
 	return pod, nil
 }
 
+func getTestCtrN(n, lockPath string) (*Container, error) {
+	return getTestContainer(strings.Repeat(n, 32), "test"+n, lockPath)
+}
+
+func getTestCtr1(lockPath string) (*Container, error) {
+	return getTestCtrN("1", lockPath)
+}
+
+func getTestCtr2(lockPath string) (*Container, error) {
+	return getTestCtrN("2", lockPath)
+}
+
+func getTestPodN(n, lockPath string) (*Pod, error) {
+	return getTestPod(strings.Repeat(n, 32), "test"+n, lockPath)
+}
+
+func getTestPod1(lockPath string) (*Pod, error) {
+	return getTestPodN("1", lockPath)
+}
+
+func getTestPod2(lockPath string) (*Pod, error) {
+	return getTestPodN("2", lockPath)
+}
+
 // This horrible hack tests if containers are equal in a way that should handle
 // empty arrays being dropped to nil pointers in the spec JSON
-// nolint
 func testContainersEqual(t *testing.T, a, b *Container) {
 	if a == nil && b == nil {
 		return
diff --git a/libpod/container_graph.go b/libpod/container_graph.go
index 67b0e3ac2..214f1b245 100644
--- a/libpod/container_graph.go
+++ b/libpod/container_graph.go
@@ -2,6 +2,7 @@ package libpod
 
 import (
 	"github.com/pkg/errors"
+	"github.com/sirupsen/logrus"
 )
 
 type containerNode struct {
@@ -73,7 +74,8 @@ func buildContainerGraph(ctrs []*Container) (*containerGraph, error) {
 	return graph, nil
 }
 
-// Detect cycles in a container graph
+// Detect cycles in a container graph using Tarjan's strongly connected
+// components algorithm
 // Return true if a cycle is found, false otherwise
 func detectCycles(graph *containerGraph) (bool, error) {
 	type nodeInfo struct {
@@ -89,6 +91,8 @@ func detectCycles(graph *containerGraph) (bool, error) {
 
 	var strongConnect func(*containerNode) (bool, error)
 	strongConnect = func(node *containerNode) (bool, error) {
+		logrus.Debugf("Strongconnecting node %s", node.id)
+
 		info := new(nodeInfo)
 		info.index = index
 		info.lowLink = index
@@ -100,9 +104,13 @@ func detectCycles(graph *containerGraph) (bool, error) {
 
 		info.onStack = true
 
+		logrus.Debugf("Pushed %s onto stack", node.id)
+
 		// Work through all nodes we point to
 		for _, successor := range node.dependsOn {
 			if _, ok := nodes[successor.id]; !ok {
+				logrus.Debugf("Recursing to successor node %s", successor.id)
+
 				cycle, err := strongConnect(successor)
 				if err != nil {
 					return false, err
@@ -132,6 +140,15 @@ func detectCycles(graph *containerGraph) (bool, error) {
 			topOfStack := stack[l-1]
 			stack = stack[:l-1]
 
+			// Popped item is no longer on the stack, mark as such
+			topInfo, ok := nodes[topOfStack.id]
+			if !ok {
+				return false, errors.Wrapf(ErrInternal, "error finding node info for %s", topOfStack.id)
+			}
+			topInfo.onStack = false
+
+			logrus.Debugf("Finishing node %s. Popped %s off stack", node.id, topOfStack.id)
+
 			// If the top of the stack is not us, we have found a
 			// cycle
 			if topOfStack.id != node.id {
diff --git a/libpod/container_graph_test.go b/libpod/container_graph_test.go
new file mode 100644
index 000000000..2303a05dd
--- /dev/null
+++ b/libpod/container_graph_test.go
@@ -0,0 +1,293 @@
+package libpod
+
+import (
+	"io/ioutil"
+	"os"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func TestBuildContainerGraphNoCtrsIsEmpty(t *testing.T) {
+	graph, err := buildContainerGraph([]*Container{})
+	assert.NoError(t, err)
+	assert.Equal(t, 0, len(graph.nodes))
+	assert.Equal(t, 0, len(graph.noDepNodes))
+	assert.Equal(t, 0, len(graph.notDependedOnNodes))
+}
+
+func TestBuildContainerGraphOneCtr(t *testing.T) {
+	tmpDir, err := ioutil.TempDir("", tmpDirPrefix)
+	assert.NoError(t, err)
+	defer os.RemoveAll(tmpDir)
+
+	ctr1, err := getTestCtr1(tmpDir)
+	assert.NoError(t, err)
+
+	graph, err := buildContainerGraph([]*Container{ctr1})
+	assert.NoError(t, err)
+	assert.Equal(t, 1, len(graph.nodes))
+	assert.Equal(t, 1, len(graph.noDepNodes))
+	assert.Equal(t, 1, len(graph.notDependedOnNodes))
+
+	node, ok := graph.nodes[ctr1.ID()]
+	assert.True(t, ok)
+	assert.Equal(t, ctr1.ID(), node.id)
+
+	assert.Equal(t, ctr1.ID(), graph.noDepNodes[0].id)
+	assert.Equal(t, ctr1.ID(), graph.notDependedOnNodes[0].id)
+}
+
+func TestBuildContainerGraphTwoCtrNoEdge(t *testing.T) {
+	tmpDir, err := ioutil.TempDir("", tmpDirPrefix)
+	assert.NoError(t, err)
+	defer os.RemoveAll(tmpDir)
+
+	ctr1, err := getTestCtr1(tmpDir)
+	assert.NoError(t, err)
+	ctr2, err := getTestCtr2(tmpDir)
+	assert.NoError(t, err)
+
+	graph, err := buildContainerGraph([]*Container{ctr1, ctr2})
+	assert.NoError(t, err)
+	assert.Equal(t, 2, len(graph.nodes))
+	assert.Equal(t, 2, len(graph.noDepNodes))
+	assert.Equal(t, 2, len(graph.notDependedOnNodes))
+
+	node1, ok := graph.nodes[ctr1.ID()]
+	assert.True(t, ok)
+	assert.Equal(t, ctr1.ID(), node1.id)
+
+	node2, ok := graph.nodes[ctr2.ID()]
+	assert.True(t, ok)
+	assert.Equal(t, ctr2.ID(), node2.id)
+}
+
+func TestBuildContainerGraphTwoCtrOneEdge(t *testing.T) {
+	tmpDir, err := ioutil.TempDir("", tmpDirPrefix)
+	assert.NoError(t, err)
+	defer os.RemoveAll(tmpDir)
+
+	ctr1, err := getTestCtr1(tmpDir)
+	assert.NoError(t, err)
+	ctr2, err := getTestCtr2(tmpDir)
+	assert.NoError(t, err)
+	ctr2.config.UserNsCtr = ctr1.config.ID
+
+	graph, err := buildContainerGraph([]*Container{ctr1, ctr2})
+	assert.NoError(t, err)
+	assert.Equal(t, 2, len(graph.nodes))
+	assert.Equal(t, 1, len(graph.noDepNodes))
+	assert.Equal(t, 1, len(graph.notDependedOnNodes))
+
+	assert.Equal(t, ctr1.ID(), graph.noDepNodes[0].id)
+	assert.Equal(t, ctr2.ID(), graph.notDependedOnNodes[0].id)
+}
+
+func TestBuildContainerGraphTwoCtrCycle(t *testing.T) {
+	tmpDir, err := ioutil.TempDir("", tmpDirPrefix)
+	assert.NoError(t, err)
+	defer os.RemoveAll(tmpDir)
+
+	ctr1, err := getTestCtr1(tmpDir)
+	assert.NoError(t, err)
+	ctr2, err := getTestCtr2(tmpDir)
+	assert.NoError(t, err)
+	ctr2.config.UserNsCtr = ctr1.config.ID
+	ctr1.config.NetNsCtr = ctr2.config.ID
+
+	_, err = buildContainerGraph([]*Container{ctr1, ctr2})
+	assert.Error(t, err)
+}
+
+func TestBuildContainerGraphThreeCtrNoEdges(t *testing.T) {
+	tmpDir, err := ioutil.TempDir("", tmpDirPrefix)
+	assert.NoError(t, err)
+	defer os.RemoveAll(tmpDir)
+
+	ctr1, err := getTestCtr1(tmpDir)
+	assert.NoError(t, err)
+	ctr2, err := getTestCtr2(tmpDir)
+	assert.NoError(t, err)
+	ctr3, err := getTestCtrN("3", tmpDir)
+	assert.NoError(t, err)
+
+	graph, err := buildContainerGraph([]*Container{ctr1, ctr2, ctr3})
+	assert.NoError(t, err)
+	assert.Equal(t, 3, len(graph.nodes))
+	assert.Equal(t, 3, len(graph.noDepNodes))
+	assert.Equal(t, 3, len(graph.notDependedOnNodes))
+
+	node1, ok := graph.nodes[ctr1.ID()]
+	assert.True(t, ok)
+	assert.Equal(t, ctr1.ID(), node1.id)
+
+	node2, ok := graph.nodes[ctr2.ID()]
+	assert.True(t, ok)
+	assert.Equal(t, ctr2.ID(), node2.id)
+
+	node3, ok := graph.nodes[ctr3.ID()]
+	assert.True(t, ok)
+	assert.Equal(t, ctr3.ID(), node3.id)
+}
+
+func TestBuildContainerGraphThreeContainersTwoInCycle(t *testing.T) {
+	tmpDir, err := ioutil.TempDir("", tmpDirPrefix)
+	assert.NoError(t, err)
+	defer os.RemoveAll(tmpDir)
+
+	ctr1, err := getTestCtr1(tmpDir)
+	assert.NoError(t, err)
+	ctr2, err := getTestCtr2(tmpDir)
+	assert.NoError(t, err)
+	ctr3, err := getTestCtrN("3", tmpDir)
+	assert.NoError(t, err)
+	ctr1.config.UserNsCtr = ctr2.config.ID
+	ctr2.config.IPCNsCtr = ctr1.config.ID
+
+	_, err = buildContainerGraph([]*Container{ctr1, ctr2, ctr3})
+	assert.Error(t, err)
+}
+
+func TestBuildContainerGraphThreeContainersCycle(t *testing.T) {
+	tmpDir, err := ioutil.TempDir("", tmpDirPrefix)
+	assert.NoError(t, err)
+	defer os.RemoveAll(tmpDir)
+
+	ctr1, err := getTestCtr1(tmpDir)
+	assert.NoError(t, err)
+	ctr2, err := getTestCtr2(tmpDir)
+	assert.NoError(t, err)
+	ctr3, err := getTestCtrN("3", tmpDir)
+	assert.NoError(t, err)
+	ctr1.config.UserNsCtr = ctr2.config.ID
+	ctr2.config.IPCNsCtr = ctr3.config.ID
+	ctr3.config.NetNsCtr = ctr1.config.ID
+
+	_, err = buildContainerGraph([]*Container{ctr1, ctr2, ctr3})
+	assert.Error(t, err)
+}
+
+func TestBuildContainerGraphThreeContainersNoCycle(t *testing.T) {
+	tmpDir, err := ioutil.TempDir("", tmpDirPrefix)
+	assert.NoError(t, err)
+	defer os.RemoveAll(tmpDir)
+
+	ctr1, err := getTestCtr1(tmpDir)
+	assert.NoError(t, err)
+	ctr2, err := getTestCtr2(tmpDir)
+	assert.NoError(t, err)
+	ctr3, err := getTestCtrN("3", tmpDir)
+	assert.NoError(t, err)
+	ctr1.config.UserNsCtr = ctr2.config.ID
+	ctr1.config.NetNsCtr = ctr3.config.ID
+	ctr2.config.IPCNsCtr = ctr3.config.ID
+
+	graph, err := buildContainerGraph([]*Container{ctr1, ctr2, ctr3})
+	assert.NoError(t, err)
+	assert.Equal(t, 3, len(graph.nodes))
+	assert.Equal(t, 1, len(graph.noDepNodes))
+	assert.Equal(t, 1, len(graph.notDependedOnNodes))
+
+	assert.Equal(t, ctr3.ID(), graph.noDepNodes[0].id)
+	assert.Equal(t, ctr1.ID(), graph.notDependedOnNodes[0].id)
+}
+
+func TestBuildContainerGraphFourContainersNoEdges(t *testing.T) {
+	tmpDir, err := ioutil.TempDir("", tmpDirPrefix)
+	assert.NoError(t, err)
+	defer os.RemoveAll(tmpDir)
+
+	ctr1, err := getTestCtr1(tmpDir)
+	assert.NoError(t, err)
+	ctr2, err := getTestCtr2(tmpDir)
+	assert.NoError(t, err)
+	ctr3, err := getTestCtrN("3", tmpDir)
+	assert.NoError(t, err)
+	ctr4, err := getTestCtrN("4", tmpDir)
+
+	graph, err := buildContainerGraph([]*Container{ctr1, ctr2, ctr3, ctr4})
+	assert.NoError(t, err)
+	assert.Equal(t, 4, len(graph.nodes))
+	assert.Equal(t, 4, len(graph.noDepNodes))
+	assert.Equal(t, 4, len(graph.notDependedOnNodes))
+
+	node1, ok := graph.nodes[ctr1.ID()]
+	assert.True(t, ok)
+	assert.Equal(t, ctr1.ID(), node1.id)
+
+	node2, ok := graph.nodes[ctr2.ID()]
+	assert.True(t, ok)
+	assert.Equal(t, ctr2.ID(), node2.id)
+
+	node3, ok := graph.nodes[ctr3.ID()]
+	assert.True(t, ok)
+	assert.Equal(t, ctr3.ID(), node3.id)
+
+	node4, ok := graph.nodes[ctr4.ID()]
+	assert.True(t, ok)
+	assert.Equal(t, ctr4.ID(), node4.id)
+}
+
+func TestBuildContainerGraphFourContainersTwoInCycle(t *testing.T) {
+	tmpDir, err := ioutil.TempDir("", tmpDirPrefix)
+	assert.NoError(t, err)
+	defer os.RemoveAll(tmpDir)
+
+	ctr1, err := getTestCtr1(tmpDir)
+	assert.NoError(t, err)
+	ctr2, err := getTestCtr2(tmpDir)
+	assert.NoError(t, err)
+	ctr3, err := getTestCtrN("3", tmpDir)
+	assert.NoError(t, err)
+	ctr4, err := getTestCtrN("4", tmpDir)
+	ctr1.config.IPCNsCtr = ctr2.config.ID
+	ctr2.config.UserNsCtr = ctr1.config.ID
+
+	_, err = buildContainerGraph([]*Container{ctr1, ctr2, ctr3, ctr4})
+	assert.Error(t, err)
+}
+
+func TestBuildContainerGraphFourContainersAllInCycle(t *testing.T) {
+	tmpDir, err := ioutil.TempDir("", tmpDirPrefix)
+	assert.NoError(t, err)
+	defer os.RemoveAll(tmpDir)
+
+	ctr1, err := getTestCtr1(tmpDir)
+	assert.NoError(t, err)
+	ctr2, err := getTestCtr2(tmpDir)
+	assert.NoError(t, err)
+	ctr3, err := getTestCtrN("3", tmpDir)
+	assert.NoError(t, err)
+	ctr4, err := getTestCtrN("4", tmpDir)
+	ctr1.config.IPCNsCtr = ctr2.config.ID
+	ctr2.config.UserNsCtr = ctr3.config.ID
+	ctr3.config.NetNsCtr = ctr4.config.ID
+	ctr4.config.UTSNsCtr = ctr1.config.ID
+
+	_, err = buildContainerGraph([]*Container{ctr1, ctr2, ctr3, ctr4})
+	assert.Error(t, err)
+}
+
+func TestBuildContainerGraphFourContainersNoneInCycle(t *testing.T) {
+	tmpDir, err := ioutil.TempDir("", tmpDirPrefix)
+	assert.NoError(t, err)
+	defer os.RemoveAll(tmpDir)
+
+	ctr1, err := getTestCtr1(tmpDir)
+	assert.NoError(t, err)
+	ctr2, err := getTestCtr2(tmpDir)
+	assert.NoError(t, err)
+	ctr3, err := getTestCtrN("3", tmpDir)
+	assert.NoError(t, err)
+	ctr4, err := getTestCtrN("4", tmpDir)
+	ctr1.config.IPCNsCtr = ctr2.config.ID
+	ctr1.config.NetNsCtr = ctr3.config.ID
+	ctr2.config.UserNsCtr = ctr3.config.ID
+
+	graph, err := buildContainerGraph([]*Container{ctr1, ctr2, ctr3, ctr4})
+	assert.NoError(t, err)
+	assert.Equal(t, 4, len(graph.nodes))
+	assert.Equal(t, 2, len(graph.noDepNodes))
+	assert.Equal(t, 2, len(graph.notDependedOnNodes))
+}
diff --git a/libpod/state_test.go b/libpod/state_test.go
index 8b6abdb8d..f989dfefd 100644
--- a/libpod/state_test.go
+++ b/libpod/state_test.go
@@ -96,30 +96,6 @@ func runForAllStates(t *testing.T, testFunc func(*testing.T, State, string)) {
 	}
 }
 
-func getTestCtrN(n, lockPath string) (*Container, error) {
-	return getTestContainer(strings.Repeat(n, 32), "test"+n, lockPath)
-}
-
-func getTestCtr1(lockPath string) (*Container, error) {
-	return getTestCtrN("1", lockPath)
-}
-
-func getTestCtr2(lockPath string) (*Container, error) {
-	return getTestCtrN("2", lockPath)
-}
-
-func getTestPodN(n, lockPath string) (*Pod, error) {
-	return getTestPod(strings.Repeat(n, 32), "test"+n, lockPath)
-}
-
-func getTestPod1(lockPath string) (*Pod, error) {
-	return getTestPodN("1", lockPath)
-}
-
-func getTestPod2(lockPath string) (*Pod, error) {
-	return getTestPodN("2", lockPath)
-}
-
 func TestAddAndGetContainer(t *testing.T) {
 	runForAllStates(t, func(t *testing.T, state State, lockPath string) {
 		testCtr, err := getTestCtr1(lockPath)