c8d: implement missing image delete logic
<!--
Please make sure you've read and understood our contributing guidelines;
https://github.com/moby/moby/blob/master/CONTRIBUTING.md

** Make sure all your commits include a signature generated with `git commit -s` **

For additional information on our contributing process, read our contributing
guide https://docs.docker.com/opensource/code/

If this is a bug fix, make sure your description includes "fixes #xxxx", or
"closes #xxxx"

Please provide the following information:
-->

**- Related**
- closes https://github.com/moby/moby/issues/43850
- closes https://github.com/moby/moby/issues/43849
- also related to: https://github.com/moby/moby/pull/45362

**- What I did**

Ports over all the previous image delete logic, such as:
- Implement `prune` and `force` flags
- Implement hard and soft image delete conflics, which represent:
  - image referenced in multiple tags (soft conflict)
  - image being used by a stopped container (soft conflict)
  - image being used by a running container (hard conflict)
- Implement delete logic such as:
  - if deleting by reference, and there are other references to the same image, just
    delete the passed reference
  - if deleting by reference, and there is only 1 reference and the image is being used
    by a running container, throw an error if !force, or delete the reference and create
    a dangling reference otherwise
  - if deleting by imageID, and force is true, remove all tags (otherwise soft conflict)
  - if imageID, check if stopped container is using the image (soft conflict), and
    delete anyway if force
  - if imageID was passed in, check if running container is using the image (hard conflict)
  - if `prune` is true, and the image being deleted has dangling parents, remove them

Also implements logic to get image parents in c8d by comparing shared layers, like what @vvoland did in https://github.com/moby/moby/pull/45265, so that we can prune dangling parents on image delete.

**- How I did it**

With neovim! 👀 

**- How to verify it**

Pull and delete a ton of different images, tag them and use them and try to delete them 😅 
Compare the results, and see if they make sense.

Some examples from me:
```bash
root@d7ded31152c0:/go/src/github.com/docker/docker# docker pull bash
Using default tag: latest
e0acf0b8fb59: Download complete
13bc69df1e93: Download complete
0e841167f105: Download complete
c41833b44d91: Download complete
dc061c8e5140: Download complete
c8c412e0d7ad: Download complete
docker.io/library/bash:latest
root@d7ded31152c0:/go/src/github.com/docker/docker# docker run -dit --name foo bash
847ac95823ef2efb8839345cca85ca28f4b6cefcd32af4d37b5ebe4d16f0b624
root@d7ded31152c0:/go/src/github.com/docker/docker# docker rmi bash
Error response from daemon: conflict: unable to remove repository reference "bash:latest" (must force) - container 847ac95823ef is using its referenced image e0acf0b8fb59
root@d7ded31152c0:/go/src/github.com/docker/docker# docker tag bash bar
root@d7ded31152c0:/go/src/github.com/docker/docker# docker images
REPOSITORY   TAG       IMAGE ID       CREATED          SIZE
bar          latest    e0acf0b8fb59   2 seconds ago    24.8MB
bash         latest    e0acf0b8fb59   19 seconds ago   24.8MB
root@d7ded31152c0:/go/src/github.com/docker/docker# docker rmi e0ac
Error response from daemon: conflict: unable to delete e0acf0b8fb59 (cannot be forced) - image is being used by running container 847ac95823ef
root@d7ded31152c0:/go/src/github.com/docker/docker# docker rmi bash
Untagged: bash:latest
root@d7ded31152c0:/go/src/github.com/docker/docker# docker images
REPOSITORY   TAG       IMAGE ID       CREATED          SIZE
bar          latest    e0acf0b8fb59   35 seconds ago   24.8MB
root@d7ded31152c0:/go/src/github.com/docker/docker# docker rmi -f bar
Untagged: bar:latest
root@d7ded31152c0:/go/src/github.com/docker/docker# docker images
REPOSITORY   TAG       IMAGE ID       CREATED         SIZE
<none>       <none>    e0acf0b8fb59   4 seconds ago   24.8MB
root@d7ded31152c0:/go/src/github.com/docker/docker# docker kill foo
foo
root@d7ded31152c0:/go/src/github.com/docker/docker# docker rm foo
foo
root@d7ded31152c0:/go/src/github.com/docker/docker# docker rmi e0ac
Untagged: moby-dangling@sha256:e0acf0b8fb59c01b6a2b66de360c86bcad5c3cd114db325155970e6bab9663a0
Deleted: sha256:e0acf0b8fb59c01b6a2b66de360c86bcad5c3cd114db325155970e6bab9663a0
root@d7ded31152c0:/go/src/github.com/docker/docker#
```
(complains if it's the only reference and a container is using it, allows deleting if there is another reference, forcing leaves dangling image)

```bash
root@d7ded31152c0:/go/src/github.com/docker/docker# docker pull bash
Using default tag: latest
e0acf0b8fb59: Download complete
13bc69df1e93: Download complete
0e841167f105: Download complete
c8c412e0d7ad: Download complete
c41833b44d91: Download complete
dc061c8e5140: Download complete
docker.io/library/bash:latest
root@d7ded31152c0:/go/src/github.com/docker/docker# docker tag bash bar
root@d7ded31152c0:/go/src/github.com/docker/docker# docker images
REPOSITORY   TAG       IMAGE ID       CREATED         SIZE
bar          latest    e0acf0b8fb59   1 second ago    24.8MB
bash         latest    e0acf0b8fb59   6 seconds ago   24.8MB
root@d7ded31152c0:/go/src/github.com/docker/docker# docker rmi e0ac
Error response from daemon: conflict: unable to delete e0acf0b8fb59 (must be forced) - image is referenced in multiple repositories
root@d7ded31152c0:/go/src/github.com/docker/docker# docker rmi -f e0ac
Untagged: bar:latest
Untagged: bash:latest
Deleted: sha256:e0acf0b8fb59c01b6a2b66de360c86bcad5c3cd114db325155970e6bab9663a0
root@d7ded31152c0:/go/src/github.com/docker/docker# docker images
REPOSITORY   TAG       IMAGE ID   CREATED   SIZE
root@d7ded31152c0:/go/src/github.com/docker/docker#
```
(complains if image referenced in multiple repos, removes all and deletes with force)

**- Description for the changelog**
<!--
Write a short (one line) summary that describes the changes in this
pull request for inclusion in the changelog:
-->

**- A picture of a cute animal (not mandatory but encouraged)**

![image](https://user-images.githubusercontent.com/70572044/235108154-2a0cba9b-50e8-4e4c-8861-63b7ced89e06.png)


daemon/containerd/image_delete.go
package containerd

import (
	"context"

	"github.com/containerd/containerd/images"
	"github.com/docker/distribution/reference"
	"github.com/docker/docker/api/types"
	"github.com/opencontainers/go-digest"
	ocispec "github.com/opencontainers/image-spec/specs-go/v1"
	"github.com/sirupsen/logrus"
)

// ImageDelete deletes the image referenced by the given imageRef from this
// daemon. The given imageRef can be an image ID, ID prefix, or a repository
// reference (with an optional tag or digest, defaulting to the tag name
// "latest"). There is differing behavior depending on whether the given
// imageRef is a repository reference or not.
//
// If the given imageRef is a repository reference then that repository
// reference will be removed. However, if there exists any containers which
// were created using the same image reference then the repository reference
// cannot be removed unless either there are other repository references to the
// same image or force is true. Following removal of the repository reference,
// the referenced image itself will attempt to be deleted as described below
// but quietly, meaning any image delete conflicts will cause the image to not
// be deleted and the conflict will not be reported.
//
// There may be conflicts preventing deletion of an image and these conflicts
// are divided into two categories grouped by their severity:
//
// Hard Conflict:
//   - a pull or build using the image.
//   - any descendant image.
//   - any running container using the image.
//
// Soft Conflict:
//   - any stopped container using the image.
//   - any repository tag or digest references to the image.
//
// The image cannot be removed if there are any hard conflicts and can be
// removed if there are soft conflicts only if force is true.
//
// If prune is true, ancestor images will each attempt to be deleted quietly,
// meaning any delete conflicts will cause the image to not be deleted and the
// conflict will not be reported.
//
// TODO(thaJeztah): implement ImageDelete "force" options; see https://github.com/moby/moby/issues/43850
// TODO(thaJeztah): implement ImageDelete "prune" options; see https://github.com/moby/moby/issues/43849
// TODO(thaJeztah): image delete should send prometheus counters; see https://github.com/moby/moby/issues/45268
func (i *ImageService) ImageDelete(ctx context.Context, imageRef string, force, prune bool) ([]types.ImageDeleteResponseItem, error) {
	parsedRef, err := reference.ParseNormalizedNamed(imageRef)
	if err != nil {
		return nil, err
	}

	img, err := i.resolveImage(ctx, imageRef)
	if err != nil {
		return nil, err
	}

	possiblyDeletedConfigs := map[digest.Digest]struct{}{}
	if err := i.walkPresentChildren(ctx, img.Target, func(_ context.Context, d ocispec.Descriptor) {
		if images.IsConfigType(d.MediaType) {
			possiblyDeletedConfigs[d.Digest] = struct{}{}
		}
	}); err != nil {
		return nil, err
	}

	err = i.client.ImageService().Delete(ctx, img.Name, images.SynchronousDelete())
	if err != nil {
		return nil, err
	}

	// Workaround for: https://github.com/moby/buildkit/issues/3797
	if err := i.unleaseSnapshotsFromDeletedConfigs(context.Background(), possiblyDeletedConfigs); err != nil {
		logrus.WithError(err).Warn("failed to unlease snapshots")
	}

	imgID := string(img.Target.Digest)
	i.LogImageEvent(imgID, imgID, "untag")
	i.LogImageEvent(imgID, imgID, "delete")

	return []types.ImageDeleteResponseItem{{Untagged: reference.FamiliarString(parsedRef)}}, nil
}

package containerd

import (
	"context"
	"fmt"
	"sort"
	"strings"

	"github.com/containerd/containerd/images"
	"github.com/docker/distribution/reference"
	"github.com/docker/docker/api/types"
	"github.com/docker/docker/container"
	"github.com/docker/docker/image"
	"github.com/docker/docker/pkg/stringid"
	"github.com/opencontainers/go-digest"
	ocispec "github.com/opencontainers/image-spec/specs-go/v1"
	"github.com/sirupsen/logrus"
)

// ImageDelete deletes the image referenced by the given imageRef from this
// daemon. The given imageRef can be an image ID, ID prefix, or a repository
// reference (with an optional tag or digest, defaulting to the tag name
// "latest"). There is differing behavior depending on whether the given
// imageRef is a repository reference or not.
//
// If the given imageRef is a repository reference then that repository
// reference will be removed. However, if there exists any containers which
// were created using the same image reference then the repository reference
// cannot be removed unless either there are other repository references to the
// same image or force is true. Following removal of the repository reference,
// the referenced image itself will attempt to be deleted as described below
// but quietly, meaning any image delete conflicts will cause the image to not
// be deleted and the conflict will not be reported.
//
// There may be conflicts preventing deletion of an image and these conflicts
// are divided into two categories grouped by their severity:
//
// Hard Conflict:
//   - any running container using the image.
//
// Soft Conflict:
//   - any stopped container using the image.
//   - any repository tag or digest references to the image.
//
// The image cannot be removed if there are any hard conflicts and can be
// removed if there are soft conflicts only if force is true.
//
// If prune is true, ancestor images will each attempt to be deleted quietly,
// meaning any delete conflicts will cause the image to not be deleted and the
// conflict will not be reported.
//
// TODO(thaJeztah): image delete should send prometheus counters; see https://github.com/moby/moby/issues/45268
func (i *ImageService) ImageDelete(ctx context.Context, imageRef string, force, prune bool) ([]types.ImageDeleteResponseItem, error) {
	parsedRef, err := reference.ParseNormalizedNamed(imageRef)
	if err != nil {
		return nil, err
	}

	img, err := i.resolveImage(ctx, imageRef)
	if err != nil {
		return nil, err
	}

	imgID := image.ID(img.Target.Digest)

	if isImageIDPrefix(imgID.String(), imageRef) {
		return i.deleteAll(ctx, img, force, prune)
	}

	singleRef, err := i.isSingleReference(ctx, img)
	if err != nil {
		return nil, err
	}
	if !singleRef {
		err := i.client.ImageService().Delete(ctx, img.Name)
		if err != nil {
			return nil, err
		}
		i.LogImageEvent(imgID.String(), imgID.String(), "untag")
		records := []types.ImageDeleteResponseItem{{Untagged: reference.FamiliarString(reference.TagNameOnly(parsedRef))}}
		return records, nil
	}

	using := func(c *container.Container) bool {
		return c.ImageID == imgID
	}
	ctr := i.containers.First(using)
	if ctr != nil {
		if !force {
			// If we removed the repository reference then
			// this image would remain "dangling" and since
			// we really want to avoid that the client must
			// explicitly force its removal.
			refString := reference.FamiliarString(reference.TagNameOnly(parsedRef))
			err := &imageDeleteConflict{
				reference: refString,
				used:      true,
				message: fmt.Sprintf("container %s is using its referenced image %s",
					stringid.TruncateID(ctr.ID),
					stringid.TruncateID(imgID.String())),
			}
			return nil, err
		}

		err := i.softImageDelete(ctx, img)
		if err != nil {
			return nil, err
		}

		i.LogImageEvent(imgID.String(), imgID.String(), "untag")
		records := []types.ImageDeleteResponseItem{{Untagged: reference.FamiliarString(reference.TagNameOnly(parsedRef))}}
		return records, nil
	}

	return i.deleteAll(ctx, img, force, prune)
}

// deleteAll deletes the image from the daemon, and if prune is true,
// also deletes dangling parents if there is no conflict in doing so.
// Parent images are removed quietly, and if there is any issue/conflict
// it is logged but does not halt execution/an error is not returned.
func (i *ImageService) deleteAll(ctx context.Context, img images.Image, force, prune bool) ([]types.ImageDeleteResponseItem, error) {
	var records []types.ImageDeleteResponseItem

	// Workaround for: https://github.com/moby/buildkit/issues/3797
	possiblyDeletedConfigs := map[digest.Digest]struct{}{}
	err := i.walkPresentChildren(ctx, img.Target, func(_ context.Context, d ocispec.Descriptor) {
		if images.IsConfigType(d.MediaType) {
			possiblyDeletedConfigs[d.Digest] = struct{}{}
		}
	})
	if err != nil {
		return nil, err
	}
	defer func() {
		if err := i.unleaseSnapshotsFromDeletedConfigs(context.Background(), possiblyDeletedConfigs); err != nil {
			logrus.WithError(err).Warn("failed to unlease snapshots")
		}
	}()

	imgID := img.Target.Digest.String()

	var parents []imageWithRootfs
	if prune {
		parents, err = i.parents(ctx, image.ID(imgID))
		if err != nil {
			logrus.WithError(err).Warn("failed to get image parents")
		}
		sortParentsByAffinity(parents)
	}

	imageRefs, err := i.client.ImageService().List(ctx, "target.digest=="+imgID)
	if err != nil {
		return nil, err
	}
	for _, imageRef := range imageRefs {
		if err := i.imageDeleteHelper(ctx, imageRef, &records, force); err != nil {
			return records, err
		}
	}
	i.LogImageEvent(imgID, imgID, "delete")
	records = append(records, types.ImageDeleteResponseItem{Deleted: imgID})

	for _, parent := range parents {
		if !isDanglingImage(parent.img) {
			break
		}
		err = i.imageDeleteHelper(ctx, parent.img, &records, false)
		if err != nil {
			logrus.WithError(err).Warn("failed to remove image parent")
			break
		}
		parentID := parent.img.Target.Digest.String()
		i.LogImageEvent(parentID, parentID, "delete")
		records = append(records, types.ImageDeleteResponseItem{Deleted: parentID})
	}

	return records, nil
}

// isImageIDPrefix returns whether the given
// possiblePrefix is a prefix of the given imageID.
func isImageIDPrefix(imageID, possiblePrefix string) bool {
	if strings.HasPrefix(imageID, possiblePrefix) {
		return true
	}
	if i := strings.IndexRune(imageID, ':'); i >= 0 {
		return strings.HasPrefix(imageID[i+1:], possiblePrefix)
	}
	return false
}

func sortParentsByAffinity(parents []imageWithRootfs) {
	sort.Slice(parents, func(i, j int) bool {
		lenRootfsI := len(parents[i].rootfs.DiffIDs)
		lenRootfsJ := len(parents[j].rootfs.DiffIDs)
		if lenRootfsI == lenRootfsJ {
			return isDanglingImage(parents[i].img)
		}
		return lenRootfsI > lenRootfsJ
	})
}

// isSingleReference returns true if there are no other images in the
// daemon targeting the same content as `img` that are not dangling.
func (i *ImageService) isSingleReference(ctx context.Context, img images.Image) (bool, error) {
	refs, err := i.client.ImageService().List(ctx, "target.digest=="+img.Target.Digest.String())
	if err != nil {
		return false, err
	}
	for _, ref := range refs {
		if !isDanglingImage(ref) && ref.Name != img.Name {
			return false, nil
		}
	}
	return true, nil
}

type conflictType int

const (
	conflictRunningContainer conflictType = 1 << iota
	conflictActiveReference
	conflictStoppedContainer
	conflictHard = conflictRunningContainer
	conflictSoft = conflictActiveReference | conflictStoppedContainer
)

// imageDeleteHelper attempts to delete the given image from this daemon.
// If the image has any hard delete conflicts (running containers using
// the image) then it cannot be deleted. If the image has any soft delete
// conflicts (any tags/digests referencing the image or any stopped container
// using the image) then it can only be deleted if force is true. Any deleted
// images and untagged references are appended to the given records. If any
// error or conflict is encountered, it will be returned immediately without
// deleting the image.
func (i *ImageService) imageDeleteHelper(ctx context.Context, img images.Image, records *[]types.ImageDeleteResponseItem, force bool) error {
	// First, determine if this image has any conflicts. Ignore soft conflicts
	// if force is true.
	c := conflictHard
	if !force {
		c |= conflictSoft
	}

	imgID := image.ID(img.Target.Digest)

	err := i.checkImageDeleteConflict(ctx, imgID, c)
	if err != nil {
		return err
	}

	untaggedRef, err := reference.ParseAnyReference(img.Name)
	if err != nil {
		return err
	}
	err = i.client.ImageService().Delete(ctx, img.Name, images.SynchronousDelete())
	if err != nil {
		return err
	}

	i.LogImageEvent(imgID.String(), imgID.String(), "untag")
	*records = append(*records, types.ImageDeleteResponseItem{Untagged: reference.FamiliarString(untaggedRef)})

	return nil
}

// ImageDeleteConflict holds a soft or hard conflict and associated
// error. A hard conflict represents a running container using the
// image, while a soft conflict is any tags/digests referencing the
// given image or any stopped container using the image.
// Implements the error interface.
type imageDeleteConflict struct {
	hard      bool
	used      bool
	reference string
	message   string
}

func (idc *imageDeleteConflict) Error() string {
	var forceMsg string
	if idc.hard {
		forceMsg = "cannot be forced"
	} else {
		forceMsg = "must be forced"
	}
	return fmt.Sprintf("conflict: unable to delete %s (%s) - %s", idc.reference, forceMsg, idc.message)
}

func (imageDeleteConflict) Conflict() {}

// checkImageDeleteConflict returns a conflict representing
// any issue preventing deletion of the given image ID, and
// nil if there are none. It takes a bitmask representing a
// filter for which conflict types the caller cares about,
// and will only check for these conflict types.
func (i *ImageService) checkImageDeleteConflict(ctx context.Context, imgID image.ID, mask conflictType) error {
	if mask&conflictRunningContainer != 0 {
		running := func(c *container.Container) bool {
			return c.ImageID == imgID && c.IsRunning()
		}
		if ctr := i.containers.First(running); ctr != nil {
			return &imageDeleteConflict{
				reference: stringid.TruncateID(imgID.String()),
				hard:      true,
				used:      true,
				message:   fmt.Sprintf("image is being used by running container %s", stringid.TruncateID(ctr.ID)),
			}
		}
	}

	if mask&conflictStoppedContainer != 0 {
		stopped := func(c *container.Container) bool {
			return !c.IsRunning() && c.ImageID == imgID
		}
		if ctr := i.containers.First(stopped); ctr != nil {
			return &imageDeleteConflict{
				reference: stringid.TruncateID(imgID.String()),
				used:      true,
				message:   fmt.Sprintf("image is being used by stopped container %s", stringid.TruncateID(ctr.ID)),
			}
		}
	}

	if mask&conflictActiveReference != 0 {
		refs, err := i.client.ImageService().List(ctx, "target.digest=="+imgID.String())
		if err != nil {
			return err
		}
		if len(refs) > 1 {
			return &imageDeleteConflict{
				reference: stringid.TruncateID(imgID.String()),
				message:   "image is referenced in multiple repositories",
			}
		}
	}

	return nil
}

Not a blocker, because this is something we need to look at in a wider scope; this would return a containerd error; we may have to translate those to one of our `errdefs` definitions.