podman

1
//go:build !remote
2

3
package libpod
4

5
import (
6
	"context"
7
	"fmt"
8
	"strings"
9

10
	"github.com/containers/podman/v5/libpod/define"
11
	"github.com/sirupsen/logrus"
12
)
13

14
type containerNode struct {
15
	id         string
16
	container  *Container
17
	dependsOn  []*containerNode
18
	dependedOn []*containerNode
19
}
20

21
// ContainerGraph is a dependency graph based on a set of containers.
22
type ContainerGraph struct {
23
	nodes              map[string]*containerNode
24
	noDepNodes         []*containerNode
25
	notDependedOnNodes map[string]*containerNode
26
}
27

28
// DependencyMap returns the dependency graph as map with the key being a
29
// container and the value being the containers the key depends on.
30
func (cg *ContainerGraph) DependencyMap() (dependencies map[*Container][]*Container) {
31
	dependencies = make(map[*Container][]*Container)
32
	for _, node := range cg.nodes {
33
		dependsOn := make([]*Container, len(node.dependsOn))
34
		for i, d := range node.dependsOn {
35
			dependsOn[i] = d.container
36
		}
37
		dependencies[node.container] = dependsOn
38
	}
39
	return dependencies
40
}
41

42
// BuildContainerGraph builds a dependency graph based on the container slice.
43
func BuildContainerGraph(ctrs []*Container) (*ContainerGraph, error) {
44
	graph := new(ContainerGraph)
45
	graph.nodes = make(map[string]*containerNode)
46
	graph.notDependedOnNodes = make(map[string]*containerNode)
47

48
	// Start by building all nodes, with no edges
49
	for _, ctr := range ctrs {
50
		ctrNode := new(containerNode)
51
		ctrNode.id = ctr.ID()
52
		ctrNode.container = ctr
53

54
		graph.nodes[ctr.ID()] = ctrNode
55
		graph.notDependedOnNodes[ctr.ID()] = ctrNode
56
	}
57

58
	// Now add edges based on dependencies
59
	for _, node := range graph.nodes {
60
		deps := node.container.Dependencies()
61
		for _, dep := range deps {
62
			// Get the dep's node
63
			depNode, ok := graph.nodes[dep]
64
			if !ok {
65
				return nil, fmt.Errorf("container %s depends on container %s not found in input list: %w", node.id, dep, define.ErrNoSuchCtr)
66
			}
67

68
			// Add the dependent node to the node's dependencies
69
			// And add the node to the dependent node's dependedOn
70
			node.dependsOn = append(node.dependsOn, depNode)
71
			depNode.dependedOn = append(depNode.dependedOn, node)
72

73
			// The dependency now has something depending on it
74
			delete(graph.notDependedOnNodes, dep)
75
		}
76

77
		// Maintain a list of nodes with no dependencies
78
		// (no edges coming from them)
79
		if len(deps) == 0 {
80
			graph.noDepNodes = append(graph.noDepNodes, node)
81
		}
82
	}
83

84
	// Need to do cycle detection
85
	// We cannot start or stop if there are cyclic dependencies
86
	cycle, err := detectCycles(graph)
87
	if err != nil {
88
		return nil, err
89
	} else if cycle {
90
		return nil, fmt.Errorf("cycle found in container dependency graph: %w", define.ErrInternal)
91
	}
92

93
	return graph, nil
94
}
95

96
// Detect cycles in a container graph using Tarjan's strongly connected
97
// components algorithm
98
// Return true if a cycle is found, false otherwise
99
func detectCycles(graph *ContainerGraph) (bool, error) {
100
	type nodeInfo struct {
101
		index   int
102
		lowLink int
103
		onStack bool
104
	}
105

106
	index := 0
107

108
	nodes := make(map[string]*nodeInfo)
109
	stack := make([]*containerNode, 0, len(graph.nodes))
110

111
	var strongConnect func(*containerNode) (bool, error)
112
	strongConnect = func(node *containerNode) (bool, error) {
113
		logrus.Debugf("Strongconnecting node %s", node.id)
114

115
		info := new(nodeInfo)
116
		info.index = index
117
		info.lowLink = index
118
		index++
119

120
		nodes[node.id] = info
121

122
		stack = append(stack, node)
123

124
		info.onStack = true
125

126
		logrus.Debugf("Pushed %s onto stack", node.id)
127

128
		// Work through all nodes we point to
129
		for _, successor := range node.dependsOn {
130
			if _, ok := nodes[successor.id]; !ok {
131
				logrus.Debugf("Recursing to successor node %s", successor.id)
132

133
				cycle, err := strongConnect(successor)
134
				if err != nil {
135
					return false, err
136
				} else if cycle {
137
					return true, nil
138
				}
139

140
				successorInfo := nodes[successor.id]
141
				if successorInfo.lowLink < info.lowLink {
142
					info.lowLink = successorInfo.lowLink
143
				}
144
			} else {
145
				successorInfo := nodes[successor.id]
146
				if successorInfo.index < info.lowLink && successorInfo.onStack {
147
					info.lowLink = successorInfo.index
148
				}
149
			}
150
		}
151

152
		if info.lowLink == info.index {
153
			l := len(stack)
154
			if l == 0 {
155
				return false, fmt.Errorf("empty stack in detectCycles: %w", define.ErrInternal)
156
			}
157

158
			// Pop off the stack
159
			topOfStack := stack[l-1]
160
			stack = stack[:l-1]
161

162
			// Popped item is no longer on the stack, mark as such
163
			topInfo, ok := nodes[topOfStack.id]
164
			if !ok {
165
				return false, fmt.Errorf("finding node info for %s: %w", topOfStack.id, define.ErrInternal)
166
			}
167
			topInfo.onStack = false
168

169
			logrus.Debugf("Finishing node %s. Popped %s off stack", node.id, topOfStack.id)
170

171
			// If the top of the stack is not us, we have found a
172
			// cycle
173
			if topOfStack.id != node.id {
174
				return true, nil
175
			}
176
		}
177

178
		return false, nil
179
	}
180

181
	for id, node := range graph.nodes {
182
		if _, ok := nodes[id]; !ok {
183
			cycle, err := strongConnect(node)
184
			if err != nil {
185
				return false, err
186
			} else if cycle {
187
				return true, nil
188
			}
189
		}
190
	}
191

192
	return false, nil
193
}
194

195
// Visit a node on a container graph and start the container, or set an error if
196
// a dependency failed to start. if restart is true, startNode will restart the node instead of starting it.
197
func startNode(ctx context.Context, node *containerNode, setError bool, ctrErrors map[string]error, ctrsVisited map[string]bool, restart bool) {
198
	// First, check if we have already visited the node
199
	if ctrsVisited[node.id] {
200
		return
201
	}
202

203
	// If setError is true, a dependency of us failed
204
	// Mark us as failed and recurse
205
	if setError {
206
		// Mark us as visited, and set an error
207
		ctrsVisited[node.id] = true
208
		ctrErrors[node.id] = fmt.Errorf("a dependency of container %s failed to start: %w", node.id, define.ErrCtrStateInvalid)
209

210
		// Hit anyone who depends on us, and set errors on them too
211
		for _, successor := range node.dependedOn {
212
			startNode(ctx, successor, true, ctrErrors, ctrsVisited, restart)
213
		}
214

215
		return
216
	}
217

218
	// Have all our dependencies started?
219
	// If not, don't visit the node yet
220
	depsVisited := true
221
	for _, dep := range node.dependsOn {
222
		depsVisited = depsVisited && ctrsVisited[dep.id]
223
	}
224
	if !depsVisited {
225
		// Don't visit us yet, all dependencies are not up
226
		// We'll hit the dependencies eventually, and when we do it will
227
		// recurse here
228
		return
229
	}
230

231
	// Going to try to start the container, mark us as visited
232
	ctrsVisited[node.id] = true
233

234
	ctrErrored := false
235

236
	// Check if dependencies are running
237
	// Graph traversal means we should have started them
238
	// But they could have died before we got here
239
	// Does not require that the container be locked, we only need to lock
240
	// the dependencies
241
	depsStopped, err := node.container.checkDependenciesRunning()
242
	if err != nil {
243
		ctrErrors[node.id] = err
244
		ctrErrored = true
245
	} else if len(depsStopped) > 0 {
246
		// Our dependencies are not running
247
		depsList := strings.Join(depsStopped, ",")
248
		ctrErrors[node.id] = fmt.Errorf("the following dependencies of container %s are not running: %s: %w", node.id, depsList, define.ErrCtrStateInvalid)
249
		ctrErrored = true
250
	}
251

252
	// Lock before we start
253
	node.container.lock.Lock()
254

255
	// Sync the container to pick up current state
256
	if !ctrErrored {
257
		if err := node.container.syncContainer(); err != nil {
258
			ctrErrored = true
259
			ctrErrors[node.id] = err
260
		}
261
	}
262

263
	// Start the container (only if it is not running)
264
	if !ctrErrored && len(node.container.config.InitContainerType) < 1 {
265
		if !restart && node.container.state.State != define.ContainerStateRunning {
266
			if err := node.container.initAndStart(ctx); err != nil {
267
				ctrErrored = true
268
				ctrErrors[node.id] = err
269
			}
270
		}
271
		if restart && node.container.state.State != define.ContainerStatePaused && node.container.state.State != define.ContainerStateUnknown {
272
			if err := node.container.restartWithTimeout(ctx, node.container.config.StopTimeout); err != nil {
273
				ctrErrored = true
274
				ctrErrors[node.id] = err
275
			}
276
		}
277
	}
278

279
	node.container.lock.Unlock()
280

281
	// Recurse to anyone who depends on us and start them
282
	for _, successor := range node.dependedOn {
283
		startNode(ctx, successor, ctrErrored, ctrErrors, ctrsVisited, restart)
284
	}
285
}
286

287
// Visit a node on the container graph and remove it, or set an error if it
288
// failed to remove. Only intended for use in pod removal; do *not* use when
289
// removing individual containers.
290
// All containers are assumed to be *UNLOCKED* on running this function.
291
// Container locks will be acquired as necessary.
292
// Pod and infraID are optional. If a pod is given it must be *LOCKED*.
293
func removeNode(ctx context.Context, node *containerNode, pod *Pod, force bool, timeout *uint, setError bool, ctrErrors map[string]error, ctrsVisited map[string]bool, ctrNamedVolumes map[string]*ContainerNamedVolume) {
294
	// If we already visited this node, we're done.
295
	if ctrsVisited[node.id] {
296
		return
297
	}
298

299
	// Someone who depends on us failed.
300
	// Mark us as failed and recurse.
301
	if setError {
302
		ctrsVisited[node.id] = true
303
		ctrErrors[node.id] = fmt.Errorf("a container that depends on container %s could not be removed: %w", node.id, define.ErrCtrStateInvalid)
304

305
		// Hit anyone who depends on us, set errors there as well.
306
		for _, successor := range node.dependsOn {
307
			removeNode(ctx, successor, pod, force, timeout, true, ctrErrors, ctrsVisited, ctrNamedVolumes)
308
		}
309
	}
310

311
	// Does anyone still depend on us?
312
	// Cannot remove if true. Once all our dependencies have been removed,
313
	// we will be removed.
314
	for _, dep := range node.dependedOn {
315
		// The container that depends on us hasn't been removed yet.
316
		// OK to continue on
317
		if ok := ctrsVisited[dep.id]; !ok {
318
			return
319
		}
320
	}
321

322
	// Going to try to remove the node, mark us as visited
323
	ctrsVisited[node.id] = true
324

325
	ctrErrored := false
326

327
	// Verify that all that depend on us are gone.
328
	// Graph traversal should guarantee this is true, but this isn't that
329
	// expensive, and it's better to be safe.
330
	for _, dep := range node.dependedOn {
331
		if _, err := node.container.runtime.GetContainer(dep.id); err == nil {
332
			ctrErrored = true
333
			ctrErrors[node.id] = fmt.Errorf("a container that depends on container %s still exists: %w", node.id, define.ErrDepExists)
334
		}
335
	}
336

337
	// Lock the container
338
	node.container.lock.Lock()
339

340
	// Gate all subsequent bits behind a ctrErrored check - we don't want to
341
	// proceed if a previous step failed.
342
	if !ctrErrored {
343
		if err := node.container.syncContainer(); err != nil {
344
			ctrErrored = true
345
			ctrErrors[node.id] = err
346
		}
347
	}
348

349
	if !ctrErrored {
350
		for _, vol := range node.container.config.NamedVolumes {
351
			ctrNamedVolumes[vol.Name] = vol
352
		}
353

354
		if pod != nil && pod.state.InfraContainerID == node.id {
355
			pod.state.InfraContainerID = ""
356
			if err := pod.save(); err != nil {
357
				ctrErrored = true
358
				ctrErrors[node.id] = fmt.Errorf("error removing infra container %s from pod %s: %w", node.id, pod.ID(), err)
359
			}
360
		}
361
	}
362

363
	if !ctrErrored {
364
		opts := ctrRmOpts{
365
			Force:     force,
366
			RemovePod: true,
367
			Timeout:   timeout,
368
		}
369

370
		if _, _, err := node.container.runtime.removeContainer(ctx, node.container, opts); err != nil {
371
			ctrErrored = true
372
			ctrErrors[node.id] = err
373
		}
374
	}
375

376
	node.container.lock.Unlock()
377

378
	// Recurse to anyone who we depend on and remove them
379
	for _, successor := range node.dependsOn {
380
		removeNode(ctx, successor, pod, force, timeout, ctrErrored, ctrErrors, ctrsVisited, ctrNamedVolumes)
381
	}
382
}
383