gc: add toy tri-color GC implementation

stevvooe · stevvooe · commit b542cc19ad45 · 2016-12-06T16:20:40.000-08:00
As a minimum, we would like to maintain generic garbage collection of
containerd resources. This includes images, bundles, containers and
arbitrary content.

The included implementation is just a textbook toy that we can use to
inform the requirements of gc. It implements a simple, stack-based
tricolor algorithm. Nothing special.

Mostly, this is to ensure we think about garbage collection from the
start, rather than as an afterthought or follow on feature.

Signed-off-by: Stephen J Day &lt;stephen.day@docker.com&gt;
diff --git a/gc/2 b/gc/2
@@ -0,0 +1,69 @@
+package gc
+
+type color uint8
+
+const (
+	white = iota
+	gray
+	black
+)
+
+func tricolor(roots []string, all []string, refs map[string][]string) []string {
+	// all objects white -> default value of color
+	state := make(map[string]color, len(all))
+	var (
+		grays     []string
+		reachable []string
+	)
+
+	grays = append(grays, roots...)
+	// root-set objects gray.
+	for _, ro := range roots {
+		state[ro] = gray
+	}
+
+	// (Repeat this as long as there are gray coloured objects) Pick a gray
+	// object. Colour all objects referenced to from that gray object gray too.
+	// (Except those who are black). And colour itself black.
+
+	// Pick any gray object
+	for id := findcolor(state, gray); id != ""; id = findcolor(state, gray) {
+		// mark all the referenced objects as gray
+		for _, target := range refs[id] {
+			if state[target] == white {
+				state[target] = gray
+			}
+		}
+		state[id] = black
+	}
+
+	// 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 state[obj] == white {
+			whites = append(whites, obj)
+		}
+	}
+
+	return whites
+}
+
+func findcolor(cs map[string]color, q color) string {
+	// TODO(stevvooe): Super-inefficient!
+	for id, c := range cs {
+		if c == q {
+			return id
+		}
+	}
+
+	return ""
+}
+
+// type colorset struct {
+// 	state map[string]color
+// }
+
+// func (cs *colorset) mark(id string, c color) {
+// 	cs.state[id] = c
+// }
diff --git a/gc/gc.go b/gc/gc.go
@@ -0,0 +1,54 @@
+// Package gc experiments with providing central gc tooling to ensure
+// deterministic resource removaol 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
+}
diff --git a/gc/gc_test.go b/gc/gc_test.go
@@ -0,0 +1,30 @@
+package gc
+
+import (
+	"reflect"
+	"testing"
+)
+
+func TestTricolorBasic(t *testing.T) {
+	roots := []string{"A", "C"}
+	all := []string{"A", "B", "C", "D", "E", "F", "G"}
+	refs := map[string][]string{
+		"A": {"B"},
+		"B": {"A"},
+		"C": {"D", "F", "B"},
+		"E": {"F", "G"},
+	}
+
+	unreachable := Tricolor(roots, all, lookup(refs))
+	expected := []string{"E", "G"}
+
+	if !reflect.DeepEqual(unreachable, expected) {
+		t.Fatalf("incorrect unreachable set: %v != %v", unreachable, expected)
+	}
+}
+
+func lookup(refs map[string][]string) func(id string) []string {
+	return func(ref string) []string {
+		return refs[ref]
+	}
+}
