image list: speed up

Listing images has shown increasing performance penalties with an
increasing number of images.  Unless `--all` is specified, Podman
will filter intermediate images.  Determining intermediate images
has been done by finding (and comparing!) parent images which is
expensive.  We had to query the storage many times which turned it
into a bottleneck.

Instead, create a layer tree and assign one or more images to nodes that
match the images' top layer.  Determining the children of an image is
now exponentially faster as we already know the child images from the
layer graph and the images using the same top layer, which may also be
considered child images based on their history.

On my system with 510 images, a rootful image list drops from 6 secs
down to 0.3 secs.

Also use the tree to compute parent nodes, and to filter intermediate
images for pruning.

Signed-off-by: Valentin Rothberg <rothberg@redhat.com>

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
+}