// 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 import ( "context" "sync" ) // ResourceType represents type of resource at a node type ResourceType uint8 // Node presents a resource which has a type and key, // this node can be used to lookup other nodes. type Node struct { Type ResourceType Namespace string Key string } // Tricolor implements basic, single-thread tri-color GC. Given the roots, the // complete set and a refs function, this function returns a map of all // reachable 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 []Node, refs func(ref Node) ([]Node, error)) (map[Node]struct{}, error) { var ( grays []Node // maintain a gray "stack" seen = map[Node]struct{}{} // or not "white", basically "seen" reachable = map[Node]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 rs, err := refs(id) if err != nil { return nil, err } // mark all the referenced objects as gray for _, target := range rs { if _, ok := seen[target]; !ok { grays = append(grays, target) } } // mark as black when done reachable[id] = struct{}{} } return reachable, nil } // ConcurrentMark implements simple, concurrent GC. All the roots are scanned // and the complete set of references is formed by calling the refs function // for each seen object. This function returns a map of all object reachable // from a root. // // 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. func ConcurrentMark(ctx context.Context, root <-chan Node, refs func(context.Context, Node, func(Node)) error) (map[Node]struct{}, error) { ctx, cancel := context.WithCancel(ctx) defer cancel() var ( grays = make(chan Node) seen = map[Node]struct{}{} // or not "white", basically "seen" wg sync.WaitGroup errOnce sync.Once refErr error ) go func() { for gray := range grays { if _, ok := seen[gray]; ok { wg.Done() continue } seen[gray] = struct{}{} // post-mark this as non-white go func(gray Node) { defer wg.Done() send := func(n Node) { wg.Add(1) select { case grays <- n: case <-ctx.Done(): wg.Done() } } if err := refs(ctx, gray, send); err != nil { errOnce.Do(func() { refErr = err cancel() }) } }(gray) } }() for r := range root { wg.Add(1) select { case grays <- r: case <-ctx.Done(): wg.Done() } } // Wait for outstanding grays to be processed wg.Wait() close(grays) if refErr != nil { return nil, refErr } if cErr := ctx.Err(); cErr != nil { return nil, cErr } return seen, nil } // Sweep removes all nodes returned through the channel which are not in // the reachable set by calling the provided remove function. func Sweep(reachable map[Node]struct{}, all []Node, remove func(Node) error) error { // All black objects are now reachable, and all white objects are // unreachable. Free those that are white! for _, node := range all { if _, ok := reachable[node]; !ok { if err := remove(node); err != nil { return err } } } return nil }