gc

Documentation

Overview

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.

Index

• Constants
• func ConcurrentMark(ctx context.Context, root <-chan Node, ...) (map[Node]struct{}, error)
• func Sweep(reachable map[Node]struct{}, all []Node, remove func(Node) error) error
• func Tricolor(roots []Node, refs func(ref Node) ([]Node, error)) (map[Node]struct{}, error)
• type Node
• type ResourceType
• type Stats

Constants

const ResourceMax = ResourceType(0x1F)

ResourceMax represents the max resource. Upper bits are stripped out during the mark phase, allowing the upper 3 bits to be used by the caller reference function.

Functions

func ConcurrentMark

func ConcurrentMark(ctx context.Context, root <-chan Node, refs func(context.Context, Node, func(Node)) error) (map[Node]struct{}, error)

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 Sweep

func Sweep(reachable map[Node]struct{}, all []Node, remove func(Node) error) error

Sweep removes all nodes returned through the slice which are not in the reachable set by calling the provided remove function.

func Tricolor

func Tricolor(roots []Node, refs func(ref Node) ([]Node, error)) (map[Node]struct{}, error)

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.

https://en.wikipedia.org/wiki/Tracing_garbage_collection#Tri-color_marking

Types

type Node

type Node struct {
	Type      ResourceType
	Namespace string
	Key       string
}

Node presents a resource which has a type and key, this node can be used to lookup other nodes.

type ResourceType

type ResourceType uint8

ResourceType represents type of resource at a node

type Stats

type Stats interface {
	Elapsed() time.Duration
}

Stats about a garbage collection run