Merge pull request #2990 from nalind/image-parent-child

image: rework parent/child/history matching

12 files changed, 228 insertions, 62 deletions

diff --git a/cmd/podman/images.go b/cmd/podman/images.go
index f584c1131..41aa213a8 100644
--- a/cmd/podman/images.go
+++ b/cmd/podman/images.go
@@ -243,7 +243,7 @@ func getImagesTemplateOutput(ctx context.Context, images []*adapter.ContainerIma
 		// If all is false and the image doesn't have a name, check to see if the top layer of the image is a parent
 		// to another image's top layer. If it is, then it is an intermediate image so don't print out if the --all flag
 		// is not set.
-		isParent, err := img.IsParent()
+		isParent, err := img.IsParent(ctx)
 		if err != nil {
 			logrus.Errorf("error checking if image is a parent %q: %v", img.ID(), err)
 		}
diff --git a/cmd/podman/images_prune.go b/cmd/podman/images_prune.go
index 84181d0a2..c522c8b15 100644
--- a/cmd/podman/images_prune.go
+++ b/cmd/podman/images_prune.go
@@ -45,7 +45,7 @@ func pruneImagesCmd(c *cliconfig.PruneImagesValues) error {
 
 	// Call prune; if any cids are returned, print them and then
 	// return err in case an error also came up
-	pruneCids, err := runtime.PruneImages(c.All)
+	pruneCids, err := runtime.PruneImages(getContext(), c.All)
 	if len(pruneCids) > 0 {
 		for _, cid := range pruneCids {
 			fmt.Println(cid)
diff --git a/cmd/podman/rmi.go b/cmd/podman/rmi.go
index 7ec875d5b..be7c81dab 100644
--- a/cmd/podman/rmi.go
+++ b/cmd/podman/rmi.go
@@ -97,7 +97,7 @@ func rmiCmd(c *cliconfig.RmiValues) error {
 				return errors.New("unable to delete all images; re-run the rmi command again.")
 			}
 			for _, i := range imagesToDelete {
-				isParent, err := i.IsParent()
+				isParent, err := i.IsParent(ctx)
 				if err != nil {
 					return err
 				}
diff --git a/cmd/podman/system_df.go b/cmd/podman/system_df.go
index 16a8ad120..aa0ead022 100644
--- a/cmd/podman/system_df.go
+++ b/cmd/podman/system_df.go
@@ -201,7 +201,7 @@ func imageUniqueSize(ctx context.Context, images []*image.Image) (map[string]uin
 	for _, img := range images {
 		parentImg := img
 		for {
-			next, err := parentImg.GetParent()
+			next, err := parentImg.GetParent(ctx)
 			if err != nil {
 				return nil, errors.Wrapf(err, "error getting parent of image %s", parentImg.ID())
 			}
@@ -246,11 +246,11 @@ func getImageDiskUsage(ctx context.Context, images []*image.Image, imageUsedbyCi
 
 		unreclaimableSize += imageUsedSize(img, imgUniqueSizeMap, imageUsedbyCintainerMap, imageUsedbyActiveContainerMap)
 
-		isParent, err := img.IsParent()
+		isParent, err := img.IsParent(ctx)
 		if err != nil {
 			return imageDiskUsage, err
 		}
-		parent, err := img.GetParent()
+		parent, err := img.GetParent(ctx)
 		if err != nil {
 			return imageDiskUsage, errors.Wrapf(err, "error getting parent of image %s", img.ID())
 		}
@@ -437,11 +437,11 @@ func getImageVerboseDiskUsage(ctx context.Context, images []*image.Image, images
 		return imagesVerboseDiskUsage, errors.Wrapf(err, "error getting unique size of images")
 	}
 	for _, img := range images {
-		isParent, err := img.IsParent()
+		isParent, err := img.IsParent(ctx)
 		if err != nil {
 			return imagesVerboseDiskUsage, errors.Wrapf(err, "error checking if %s is a parent images", img.ID())
 		}
-		parent, err := img.GetParent()
+		parent, err := img.GetParent(ctx)
 		if err != nil {
 			return imagesVerboseDiskUsage, errors.Wrapf(err, "error getting parent of image %s", img.ID())
 		}
diff --git a/cmd/podman/system_prune.go b/cmd/podman/system_prune.go
index 8900e2644..2c1c5607a 100644
--- a/cmd/podman/system_prune.go
+++ b/cmd/podman/system_prune.go
@@ -110,7 +110,7 @@ Are you sure you want to continue? [y/N] `, volumeString)
 
 	// Call prune; if any cids are returned, print them and then
 	// return err in case an error also came up
-	pruneCids, err := runtime.PruneImages(c.All)
+	pruneCids, err := runtime.PruneImages(ctx, c.All)
 	if len(pruneCids) > 0 {
 		fmt.Println("Deleted Images")
 		for _, cid := range pruneCids {
diff --git a/libpod/image/image.go b/libpod/image/image.go
index 757d034a2..0b0002d42 100644
--- a/libpod/image/image.go
+++ b/libpod/image/image.go
@@ -353,8 +353,8 @@ func (i *Image) TopLayer() string {
 // outside the context of images
 // TODO: the force param does nothing as of now. Need to move container
 // handling logic here eventually.
-func (i *Image) Remove(force bool) error {
-	parent, err := i.GetParent()
+func (i *Image) Remove(ctx context.Context, force bool) error {
+	parent, err := i.GetParent(ctx)
 	if err != nil {
 		return err
 	}
@@ -363,11 +363,11 @@ func (i *Image) Remove(force bool) error {
 	}
 	i.newImageEvent(events.Remove)
 	for parent != nil {
-		nextParent, err := parent.GetParent()
+		nextParent, err := parent.GetParent(ctx)
 		if err != nil {
 			return err
 		}
-		children, err := parent.GetChildren()
+		children, err := parent.GetChildren(ctx)
 		if err != nil {
 			return err
 		}
@@ -679,7 +679,8 @@ type History struct {
 	Comment   string     `json:"comment"`
 }
 
-// History gets the history of an image and information about its layers
+// History gets the history of an image and the IDs of images that are part of
+// its history
 func (i *Image) History(ctx context.Context) ([]*History, error) {
 	img, err := i.toImageRef(ctx)
 	if err != nil {
@@ -690,31 +691,92 @@ func (i *Image) History(ctx context.Context) ([]*History, error) {
 		return nil, err
 	}
 
-	// Get the IDs of the images making up the history layers
-	// if the images exist locally in the store
+	// Use our layers list to find images that use one of them as its
+	// topmost layer.
+	interestingLayers := make(map[string]bool)
+	layer, err := i.imageruntime.store.Layer(i.TopLayer())
+	if err != nil {
+		return nil, err
+	}
+	for layer != nil {
+		interestingLayers[layer.ID] = true
+		if layer.Parent == "" {
+			break
+		}
+		layer, err = i.imageruntime.store.Layer(layer.Parent)
+		if err != nil {
+			return nil, err
+		}
+	}
+
+	// Get the IDs of the images that share some of our layers.  Hopefully
+	// this step means that we'll be able to avoid reading the
+	// configuration of every single image in local storage later on.
 	images, err := i.imageruntime.GetImages()
 	if err != nil {
 		return nil, errors.Wrapf(err, "error getting images from store")
 	}
-	imageIDs := []string{i.ID()}
-	if err := i.historyLayerIDs(i.TopLayer(), images, &imageIDs); err != nil {
-		return nil, errors.Wrap(err, "error getting image IDs for layers in history")
+	interestingImages := make([]*Image, 0, len(images))
+	for i := range images {
+		if interestingLayers[images[i].TopLayer()] {
+			interestingImages = append(interestingImages, images[i])
+		}
+	}
+
+	// Build a list of image IDs that correspond to our history entries.
+	historyImages := make([]*Image, len(oci.History))
+	if len(oci.History) > 0 {
+		// The starting image shares its whole history with itself.
+		historyImages[len(historyImages)-1] = i
+		for i := range interestingImages {
+			image, err := images[i].ociv1Image(ctx)
+			if err != nil {
+				return nil, errors.Wrapf(err, "error getting image configuration for image %q", images[i].ID())
+			}
+			// If the candidate has a longer history or no history
+			// at all, then it doesn't share the portion of our
+			// history that we're interested in matching with other
+			// images.
+			if len(image.History) == 0 || len(image.History) > len(historyImages) {
+				continue
+			}
+			// If we don't include all of the layers that the
+			// candidate image does (i.e., our rootfs didn't look
+			// like its rootfs at any point), then it can't be part
+			// of our history.
+			if len(image.RootFS.DiffIDs) > len(oci.RootFS.DiffIDs) {
+				continue
+			}
+			candidateLayersAreUsed := true
+			for i := range image.RootFS.DiffIDs {
+				if image.RootFS.DiffIDs[i] != oci.RootFS.DiffIDs[i] {
+					candidateLayersAreUsed = false
+					break
+				}
+			}
+			if !candidateLayersAreUsed {
+				continue
+			}
+			// If the candidate's entire history is an initial
+			// portion of our history, then we're based on it,
+			// either directly or indirectly.
+			sharedHistory := historiesMatch(oci.History, image.History)
+			if sharedHistory == len(image.History) {
+				historyImages[sharedHistory-1] = images[i]
+			}
+		}
 	}
 
 	var (
-		imageID    string
-		imgIDCount = 0
 		size       int64
 		sizeCount  = 1
 		allHistory []*History
 	)
 
 	for i := len(oci.History) - 1; i >= 0; i-- {
-		if imgIDCount < len(imageIDs) {
-			imageID = imageIDs[imgIDCount]
-			imgIDCount++
-		} else {
-			imageID = "<missing>"
+		imageID := "<missing>"
+		if historyImages[i] != nil {
+			imageID = historyImages[i].ID()
 		}
 		if !oci.History[i].EmptyLayer {
 			size = img.LayerInfos()[len(img.LayerInfos())-sizeCount].Size
@@ -1006,26 +1068,110 @@ func splitString(input string) string {
 // IsParent goes through the layers in the store and checks if i.TopLayer is
 // the parent of any other layer in store. Double check that image with that
 // layer exists as well.
-func (i *Image) IsParent() (bool, error) {
-	children, err := i.GetChildren()
+func (i *Image) IsParent(ctx context.Context) (bool, error) {
+	children, err := i.getChildren(ctx, 1)
 	if err != nil {
 		return false, err
 	}
 	return len(children) > 0, nil
 }
 
+// historiesMatch returns the number of entries in the histories which have the
+// same contents
+func historiesMatch(a, b []imgspecv1.History) int {
+	i := 0
+	for i < len(a) && i < len(b) {
+		if a[i].Created != nil && b[i].Created == nil {
+			return i
+		}
+		if a[i].Created == nil && b[i].Created != nil {
+			return i
+		}
+		if a[i].Created != nil && b[i].Created != nil {
+			if !a[i].Created.Equal(*(b[i].Created)) {
+				return i
+			}
+		}
+		if a[i].CreatedBy != b[i].CreatedBy {
+			return i
+		}
+		if a[i].Author != b[i].Author {
+			return i
+		}
+		if a[i].Comment != b[i].Comment {
+			return i
+		}
+		if a[i].EmptyLayer != b[i].EmptyLayer {
+			return i
+		}
+		i++
+	}
+	return i
+}
+
+// areParentAndChild checks diff ID and history in the two images and return
+// true if the second should be considered to be directly based on the first
+func areParentAndChild(parent, child *imgspecv1.Image) bool {
+	// the child and candidate parent should share all of the
+	// candidate parent's diff IDs, which together would have
+	// controlled which layers were used
+	if len(parent.RootFS.DiffIDs) > len(child.RootFS.DiffIDs) {
+		return false
+	}
+	childUsesCandidateDiffs := true
+	for i := range parent.RootFS.DiffIDs {
+		if child.RootFS.DiffIDs[i] != parent.RootFS.DiffIDs[i] {
+			childUsesCandidateDiffs = false
+			break
+		}
+	}
+	if !childUsesCandidateDiffs {
+		return false
+	}
+	// the child should have the same history as the parent, plus
+	// one more entry
+	if len(parent.History)+1 != len(child.History) {
+		return false
+	}
+	if historiesMatch(parent.History, child.History) != len(parent.History) {
+		return false
+	}
+	return true
+}
+
 // GetParent returns the image ID of the parent. Return nil if a parent is not found.
-func (i *Image) GetParent() (*Image, error) {
+func (i *Image) GetParent(ctx context.Context) (*Image, error) {
 	images, err := i.imageruntime.GetImages()
 	if err != nil {
 		return nil, err
 	}
-	layer, err := i.imageruntime.store.Layer(i.TopLayer())
+	childLayer, err := i.imageruntime.store.Layer(i.TopLayer())
+	if err != nil {
+		return nil, err
+	}
+	// fetch the configuration for the child image
+	child, err := i.ociv1Image(ctx)
 	if err != nil {
 		return nil, err
 	}
 	for _, img := range images {
-		if img.TopLayer() == layer.Parent {
+		if img.ID() == i.ID() {
+			continue
+		}
+		candidateLayer := img.TopLayer()
+		// as a child, our top layer is either the candidate parent's
+		// layer, or one that's derived from it, so skip over any
+		// candidate image where we know that isn't the case
+		if candidateLayer != childLayer.Parent && candidateLayer != childLayer.ID {
+			continue
+		}
+		// fetch the configuration for the candidate image
+		candidate, err := img.ociv1Image(ctx)
+		if err != nil {
+			return nil, err
+		}
+		// compare them
+		if areParentAndChild(candidate, child) {
 			return img, nil
 		}
 	}
@@ -1033,36 +1179,53 @@ func (i *Image) GetParent() (*Image, error) {
 }
 
 // GetChildren returns a list of the imageIDs that depend on the image
-func (i *Image) GetChildren() ([]string, error) {
+func (i *Image) GetChildren(ctx context.Context) ([]string, error) {
+	return i.getChildren(ctx, 0)
+}
+
+// getChildren returns a list of at most "max" imageIDs that depend on the image
+func (i *Image) getChildren(ctx context.Context, max int) ([]string, error) {
 	var children []string
 	images, err := i.imageruntime.GetImages()
 	if err != nil {
 		return nil, err
 	}
-	layers, err := i.imageruntime.store.Layers()
+
+	// fetch the configuration for the parent image
+	parent, err := i.ociv1Image(ctx)
 	if err != nil {
 		return nil, err
 	}
+	parentLayer := i.TopLayer()
 
-	for _, layer := range layers {
-		if layer.Parent == i.TopLayer() {
-			if imageID := getImageOfTopLayer(images, layer.ID); len(imageID) > 0 {
-				children = append(children, imageID...)
-			}
-		}
-	}
-	return children, nil
-}
-
-// getImageOfTopLayer returns the image ID where layer is the top layer of the image
-func getImageOfTopLayer(images []*Image, layer string) []string {
-	var matches []string
 	for _, img := range images {
-		if img.TopLayer() == layer {
-			matches = append(matches, img.ID())
+		if img.ID() == i.ID() {
+			continue
+		}
+		candidateLayer, err := img.Layer()
+		if err != nil {
+			return nil, err
+		}
+		// if this image's top layer is not our top layer, and is not
+		// based on our top layer, we can skip it
+		if candidateLayer.Parent != parentLayer && candidateLayer.ID != parentLayer {
+			continue
+		}
+		// fetch the configuration for the candidate image
+		candidate, err := img.ociv1Image(ctx)
+		if err != nil {
+			return nil, err
+		}
+		// compare them
+		if areParentAndChild(parent, candidate) {
+			children = append(children, img.ID())
+		}
+		// if we're not building an exhaustive list, maybe we're done?
+		if max > 0 && len(children) >= max {
+			break
 		}
 	}
-	return matches
+	return children, nil
 }
 
 // InputIsID returns a bool if the user input for an image
diff --git a/libpod/image/image_test.go b/libpod/image/image_test.go
index 075ba119d..d917e3205 100644
--- a/libpod/image/image_test.go
+++ b/libpod/image/image_test.go
@@ -139,7 +139,7 @@ func TestImage_New(t *testing.T) {
 		newImage, err := ir.New(context.Background(), img, "", "", writer, nil, SigningOptions{}, false, nil)
 		assert.NoError(t, err)
 		assert.NotEqual(t, newImage.ID(), "")
-		err = newImage.Remove(false)
+		err = newImage.Remove(context.Background(), false)
 		assert.NoError(t, err)
 	}
 
diff --git a/libpod/image/prune.go b/libpod/image/prune.go
index 5bd3c2c99..a4f8a0c9f 100644
--- a/libpod/image/prune.go
+++ b/libpod/image/prune.go
@@ -1,6 +1,8 @@
 package image
 
 import (
+	"context"
+
 	"github.com/containers/libpod/libpod/events"
 	"github.com/pkg/errors"
 )
@@ -34,14 +36,14 @@ func (ir *Runtime) GetPruneImages(all bool) ([]*Image, error) {
 
 // PruneImages prunes dangling and optionally all unused images from the local
 // image store
-func (ir *Runtime) PruneImages(all bool) ([]string, error) {
+func (ir *Runtime) PruneImages(ctx context.Context, all bool) ([]string, error) {
 	var prunedCids []string
 	pruneImages, err := ir.GetPruneImages(all)
 	if err != nil {
 		return nil, errors.Wrap(err, "unable to get images to prune")
 	}
 	for _, p := range pruneImages {
-		if err := p.Remove(true); err != nil {
+		if err := p.Remove(ctx, true); err != nil {
 			return nil, errors.Wrap(err, "failed to prune image")
 		}
 		defer p.newImageEvent(events.Prune)
diff --git a/libpod/runtime_img.go b/libpod/runtime_img.go
index 02f925fc6..5e9f65acc 100644
--- a/libpod/runtime_img.go
+++ b/libpod/runtime_img.go
@@ -57,7 +57,7 @@ func (r *Runtime) RemoveImage(ctx context.Context, img *image.Image, force bool)
 		}
 	}
 
-	hasChildren, err := img.IsParent()
+	hasChildren, err := img.IsParent(ctx)
 	if err != nil {
 		return "", err
 	}
@@ -82,12 +82,12 @@ func (r *Runtime) RemoveImage(ctx context.Context, img *image.Image, force bool)
 		// reponames and no force is applied, we error out.
 		return "", fmt.Errorf("unable to delete %s (must force) - image is referred to in multiple tags", img.ID())
 	}
-	err = img.Remove(force)
+	err = img.Remove(ctx, force)
 	if err != nil && errors.Cause(err) == storage.ErrImageUsedByContainer {
 		if errStorage := r.rmStorageContainers(force, img); errStorage == nil {
 			// Containers associated with the image should be deleted now,
 			// let's try removing the image again.
-			err = img.Remove(force)
+			err = img.Remove(ctx, force)
 		} else {
 			err = errStorage
 		}
diff --git a/pkg/adapter/runtime.go b/pkg/adapter/runtime.go
index 753f7c944..ca9678265 100644
--- a/pkg/adapter/runtime.go
+++ b/pkg/adapter/runtime.go
@@ -119,8 +119,8 @@ func (r *LocalRuntime) RemoveImage(ctx context.Context, img *ContainerImage, for
 }
 
 // PruneImages is wrapper into PruneImages within the image pkg
-func (r *LocalRuntime) PruneImages(all bool) ([]string, error) {
-	return r.ImageRuntime().PruneImages(all)
+func (r *LocalRuntime) PruneImages(ctx context.Context, all bool) ([]string, error) {
+	return r.ImageRuntime().PruneImages(ctx, all)
 }
 
 // Export is a wrapper to container export to a tarfile
diff --git a/pkg/adapter/runtime_remote.go b/pkg/adapter/runtime_remote.go
index dcb0924ce..29ee821e0 100644
--- a/pkg/adapter/runtime_remote.go
+++ b/pkg/adapter/runtime_remote.go
@@ -256,7 +256,7 @@ func (r *LocalRuntime) New(ctx context.Context, name, signaturePolicyPath, authf
 // IsParent goes through the layers in the store and checks if i.TopLayer is
 // the parent of any other layer in store. Double check that image with that
 // layer exists as well.
-func (ci *ContainerImage) IsParent() (bool, error) {
+func (ci *ContainerImage) IsParent(context.Context) (bool, error) {
 	return ci.remoteImage.isParent, nil
 }
 
@@ -338,7 +338,7 @@ func (ci *ContainerImage) History(ctx context.Context) ([]*image.History, error)
 }
 
 // PruneImages is the wrapper call for a remote-client to prune images
-func (r *LocalRuntime) PruneImages(all bool) ([]string, error) {
+func (r *LocalRuntime) PruneImages(ctx context.Context, all bool) ([]string, error) {
 	return iopodman.ImagesPrune().Call(r.Conn, all)
 }
 
diff --git a/pkg/varlinkapi/images.go b/pkg/varlinkapi/images.go
index 470eadaeb..cecddf6b3 100644
--- a/pkg/varlinkapi/images.go
+++ b/pkg/varlinkapi/images.go
@@ -4,6 +4,7 @@ package varlinkapi
 
 import (
 	"bytes"
+	"context"
 	"encoding/json"
 	"fmt"
 	"io"
@@ -49,7 +50,7 @@ func (i *LibpodAPI) ListImages(call iopodman.VarlinkCall) error {
 		}
 
 		size, _ := image.Size(getContext())
-		isParent, err := image.IsParent()
+		isParent, err := image.IsParent(context.TODO())
 		if err != nil {
 			return call.ReplyErrorOccurred(err.Error())
 		}
@@ -503,7 +504,7 @@ func (i *LibpodAPI) DeleteUnusedImages(call iopodman.VarlinkCall) error {
 			return call.ReplyErrorOccurred(err.Error())
 		}
 		if len(containers) == 0 {
-			if err := img.Remove(false); err != nil {
+			if err := img.Remove(context.TODO(), false); err != nil {
 				return call.ReplyErrorOccurred(err.Error())
 			}
 			deletedImages = append(deletedImages, img.ID())
@@ -739,7 +740,7 @@ func (i *LibpodAPI) ContainerRunlabel(call iopodman.VarlinkCall, input iopodman.
 
 // ImagesPrune ....
 func (i *LibpodAPI) ImagesPrune(call iopodman.VarlinkCall, all bool) error {
-	prunedImages, err := i.Runtime.ImageRuntime().PruneImages(all)
+	prunedImages, err := i.Runtime.ImageRuntime().PruneImages(context.TODO(), all)
 	if err != nil {
 		return call.ReplyErrorOccurred(err.Error())
 	}