summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMatthew Heon <matthew.heon@gmail.com>2018-03-27 13:23:23 -0400
committerAtomic Bot <atomic-devel@projectatomic.io>2018-03-29 02:18:45 +0000
commitb1dfee50e826bb3e4a699c89fabdb3bfcdaae86b (patch)
tree4258f39aa67bbcbc220d3533cf3bc2ec86df7fd1
parent120520af349bd6f23133fcf2e7f3b6efa0f7a7ad (diff)
downloadpodman-b1dfee50e826bb3e4a699c89fabdb3bfcdaae86b.tar.gz
podman-b1dfee50e826bb3e4a699c89fabdb3bfcdaae86b.tar.bz2
podman-b1dfee50e826bb3e4a699c89fabdb3bfcdaae86b.zip
Add tests for container graphs
Signed-off-by: Matthew Heon <matthew.heon@gmail.com> Closes: #557 Approved by: rhatdan
-rw-r--r--libpod/common_test.go (renamed from libpod/test_common.go)28
-rw-r--r--libpod/container_graph.go19
-rw-r--r--libpod/container_graph_test.go293
-rw-r--r--libpod/state_test.go24
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)