1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
package libpod
import (
"github.com/pkg/errors"
"github.com/sirupsen/logrus"
)
type containerNode struct {
id string
container *Container
dependsOn []*containerNode
dependedOn []*containerNode
}
type containerGraph struct {
nodes map[string]*containerNode
noDepNodes []*containerNode
notDependedOnNodes map[string]*containerNode
}
func buildContainerGraph(ctrs []*Container) (*containerGraph, error) {
graph := new(containerGraph)
graph.nodes = make(map[string]*containerNode)
graph.notDependedOnNodes = make(map[string]*containerNode)
// Start by building all nodes, with no edges
for _, ctr := range ctrs {
ctrNode := new(containerNode)
ctrNode.id = ctr.ID()
ctrNode.container = ctr
graph.nodes[ctr.ID()] = ctrNode
graph.notDependedOnNodes[ctr.ID()] = ctrNode
}
// Now add edges based on dependencies
for _, node := range graph.nodes {
deps := node.container.Dependencies()
for _, dep := range deps {
// Get the dep's node
depNode, ok := graph.nodes[dep]
if !ok {
return nil, errors.Wrapf(ErrNoSuchCtr, "container %s depends on container %s not found in input list", node.id, dep)
}
// Add the dependent node to the node's dependencies
// And add the node to the dependent node's dependedOn
node.dependsOn = append(node.dependsOn, depNode)
depNode.dependedOn = append(depNode.dependedOn, node)
// The dependency now has something depending on it
delete(graph.notDependedOnNodes, dep)
}
// Maintain a list of nodes with no dependencies
// (no edges coming from them)
if len(deps) == 0 {
graph.noDepNodes = append(graph.noDepNodes, node)
}
}
// Need to do cycle detection
// We cannot start or stop if there are cyclic dependencies
cycle, err := detectCycles(graph)
if err != nil {
return nil, err
} else if cycle {
return nil, errors.Wrapf(ErrInternal, "cycle found in container dependency graph")
}
return graph, nil
}
// 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 {
index int
lowLink int
onStack bool
}
index := 0
nodes := make(map[string]*nodeInfo)
stack := make([]*containerNode, 0, len(graph.nodes))
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
index = index + 1
nodes[node.id] = info
stack = append(stack, node)
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
} else if cycle {
return true, nil
}
successorInfo := nodes[successor.id]
if successorInfo.lowLink < info.lowLink {
info.lowLink = successorInfo.lowLink
}
} else {
successorInfo := nodes[successor.id]
if successorInfo.index < info.lowLink && successorInfo.onStack {
info.lowLink = successorInfo.index
}
}
}
if info.lowLink == info.index {
l := len(stack)
if l == 0 {
return false, errors.Wrapf(ErrInternal, "empty stack in detectCycles")
}
// Pop off the stack
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 {
return true, nil
}
}
return false, nil
}
for id, node := range graph.nodes {
if _, ok := nodes[id]; !ok {
cycle, err := strongConnect(node)
if err != nil {
return false, err
} else if cycle {
return true, nil
}
}
}
return false, nil
}
|
