Merge pull request #7215 from vrothberg/flatten-the-curve

images: speed up lists

1 files changed, 222 insertions, 0 deletions

diff --git a/libpod/image/layer_tree.go b/libpod/image/layer_tree.go
new file mode 100644
index 000000000..3699655fd
--- /dev/null
+++ b/libpod/image/layer_tree.go
@@ -0,0 +1,222 @@
+package image
+
+import (
+	"context"
+
+	ociv1 "github.com/opencontainers/image-spec/specs-go/v1"
+	"github.com/pkg/errors"
+)
+
+// layerTree is an internal representation of local layers.
+type layerTree struct {
+	// nodes is the actual layer tree with layer IDs being keys.
+	nodes map[string]*layerNode
+	// ociCache is a cache for Image.ID -> OCI Image. Translations are done
+	// on-demand.
+	ociCache map[string]*ociv1.Image
+}
+
+// node returns a layerNode for the specified layerID.
+func (t *layerTree) node(layerID string) *layerNode {
+	node, exists := t.nodes[layerID]
+	if !exists {
+		node = &layerNode{}
+		t.nodes[layerID] = node
+	}
+	return node
+}
+
+// toOCI returns an OCI image for the specified image.
+func (t *layerTree) toOCI(ctx context.Context, i *Image) (*ociv1.Image, error) {
+	var err error
+	oci, exists := t.ociCache[i.ID()]
+	if !exists {
+		oci, err = i.ociv1Image(ctx)
+		t.ociCache[i.ID()] = oci
+	}
+	return oci, err
+}
+
+// layerNode is a node in a layerTree.  It's ID is the key in a layerTree.
+type layerNode struct {
+	children []*layerNode
+	images   []*Image
+	parent   *layerNode
+}
+
+// layerTree extracts a layerTree from the layers in the local storage and
+// relates them to the specified images.
+func (ir *Runtime) layerTree() (*layerTree, error) {
+	layers, err := ir.store.Layers()
+	if err != nil {
+		return nil, err
+	}
+
+	images, err := ir.GetImages()
+	if err != nil {
+		return nil, err
+	}
+
+	tree := layerTree{
+		nodes:    make(map[string]*layerNode),
+		ociCache: make(map[string]*ociv1.Image),
+	}
+
+	// First build a tree purely based on layer information.
+	for _, layer := range layers {
+		node := tree.node(layer.ID)
+		if layer.Parent == "" {
+			continue
+		}
+		parent := tree.node(layer.Parent)
+		node.parent = parent
+		parent.children = append(parent.children, node)
+	}
+
+	// Now assign the images to each (top) layer.
+	for i := range images {
+		img := images[i] // do not leak loop variable outside the scope
+		topLayer := img.TopLayer()
+		if topLayer == "" {
+			continue
+		}
+		node, exists := tree.nodes[topLayer]
+		if !exists {
+			return nil, errors.Errorf("top layer %s of image %s not found in layer tree", img.TopLayer(), img.ID())
+		}
+		node.images = append(node.images, img)
+	}
+
+	return &tree, nil
+}
+
+// children returns the image IDs of children . Child images are images
+// with either the same top layer as parent or parent being the true parent
+// layer.  Furthermore, the history of the parent and child images must match
+// with the parent having one history item less.
+// If all is true, all images are returned.  Otherwise, the first image is
+// returned.
+func (t *layerTree) children(ctx context.Context, parent *Image, all bool) ([]string, error) {
+	if parent.TopLayer() == "" {
+		return nil, nil
+	}
+
+	var children []string
+
+	parentNode, exists := t.nodes[parent.TopLayer()]
+	if !exists {
+		return nil, errors.Errorf("layer not found in layer tree: %q", parent.TopLayer())
+	}
+
+	parentID := parent.ID()
+	parentOCI, err := t.toOCI(ctx, parent)
+	if err != nil {
+		return nil, err
+	}
+
+	// checkParent returns true if child and parent are in such a relation.
+	checkParent := func(child *Image) (bool, error) {
+		if parentID == child.ID() {
+			return false, nil
+		}
+		childOCI, err := t.toOCI(ctx, child)
+		if err != nil {
+			return false, err
+		}
+		// History check.
+		return areParentAndChild(parentOCI, childOCI), nil
+	}
+
+	// addChildrenFrom adds child images of parent to children.  Returns
+	// true if any image is a child of parent.
+	addChildrenFromNode := func(node *layerNode) (bool, error) {
+		foundChildren := false
+		for _, childImage := range node.images {
+			isChild, err := checkParent(childImage)
+			if err != nil {
+				return foundChildren, err
+			}
+			if isChild {
+				foundChildren = true
+				children = append(children, childImage.ID())
+				if all {
+					return foundChildren, nil
+				}
+			}
+		}
+		return foundChildren, nil
+	}
+
+	// First check images where parent's top layer is also the parent
+	// layer.
+	for _, childNode := range parentNode.children {
+		found, err := addChildrenFromNode(childNode)
+		if err != nil {
+			return nil, err
+		}
+		if found && all {
+			return children, nil
+		}
+	}
+
+	// Now check images with the same top layer.
+	if _, err := addChildrenFromNode(parentNode); err != nil {
+		return nil, err
+	}
+
+	return children, nil
+}
+
+// parent returns the parent image or nil if no parent image could be found.
+func (t *layerTree) parent(ctx context.Context, child *Image) (*Image, error) {
+	if child.TopLayer() == "" {
+		return nil, nil
+	}
+
+	node, exists := t.nodes[child.TopLayer()]
+	if !exists {
+		return nil, errors.Errorf("layer not found in layer tree: %q", child.TopLayer())
+	}
+
+	childOCI, err := t.toOCI(ctx, child)
+	if err != nil {
+		return nil, err
+	}
+
+	// Check images from the parent node (i.e., parent layer) and images
+	// with the same layer (i.e., same top layer).
+	childID := child.ID()
+	images := node.images
+	if node.parent != nil {
+		images = append(images, node.parent.images...)
+	}
+	for _, parent := range images {
+		if parent.ID() == childID {
+			continue
+		}
+		parentOCI, err := t.toOCI(ctx, parent)
+		if err != nil {
+			return nil, err
+		}
+		// History check.
+		if areParentAndChild(parentOCI, childOCI) {
+			return parent, nil
+		}
+	}
+
+	return nil, nil
+}
+
+// hasChildrenAndParent returns true if the specified image has children and a
+// parent.
+func (t *layerTree) hasChildrenAndParent(ctx context.Context, i *Image) (bool, error) {
+	children, err := t.children(ctx, i, false)
+	if err != nil {
+		return false, err
+	}
+	if len(children) == 0 {
+		return false, nil
+	}
+	parent, err := t.parent(ctx, i)
+	return parent != nil, err
+}