This repository has been archived by the owner on Mar 11, 2020. It is now read-only.
forked from containerd/containerd
-
Notifications
You must be signed in to change notification settings - Fork 41
/
gc.go
54 lines (47 loc) · 1.73 KB
/
gc.go
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
// Package gc experiments with providing central gc tooling to ensure
// deterministic resource removal within containerd.
//
// For now, we just have a single exported implementation that can be used
// under certain use cases.
package gc
// Tricolor implements basic, single-thread tri-color GC. Given the roots, the
// complete set and a refs function, this returns the unreachable objects.
//
// Correct usage requires that the caller not allow the arguments to change
// until the result is used to delete objects in the system.
//
// It will allocate memory proportional to the size of the reachable set.
//
// We can probably use this to inform a design for incremental GC by injecting
// callbacks to the set modification algorithms.
func Tricolor(roots []string, all []string, refs func(ref string) []string) []string {
var (
grays []string // maintain a gray "stack"
seen = map[string]struct{}{} // or not "white", basically "seen"
reachable = map[string]struct{}{} // or "block", in tri-color parlance
)
grays = append(grays, roots...)
for len(grays) > 0 {
// Pick any gray object
id := grays[len(grays)-1] // effectively "depth first" because first element
grays = grays[:len(grays)-1]
seen[id] = struct{}{} // post-mark this as not-white
// mark all the referenced objects as gray
for _, target := range refs(id) {
if _, ok := seen[target]; !ok {
grays = append(grays, target)
}
}
// mark as black when done
reachable[id] = struct{}{}
}
// All black objects are now reachable, and all white objects are
// unreachable. Free those that are white!
var whites []string
for _, obj := range all {
if _, ok := reachable[obj]; !ok {
whites = append(whites, obj)
}
}
return whites
}