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_children.go
package containerd

import (
	"context"

	"github.com/containerd/containerd/content"
	cerrdefs "github.com/containerd/containerd/errdefs"
	containerdimages "github.com/containerd/containerd/images"
	"github.com/containerd/containerd/platforms"
	"github.com/docker/docker/errdefs"
	"github.com/docker/docker/image"
	ocispec "github.com/opencontainers/image-spec/specs-go/v1"
	"github.com/pkg/errors"
	"github.com/sirupsen/logrus"
)

// Children returns a slice of image ID which rootfs is a superset of the
// rootfs of the given image ID, excluding images with exactly the same rootfs.
// Called from list.go to filter containers.
func (i *ImageService) Children(ctx context.Context, id image.ID) ([]image.ID, error) {
	target, err := i.resolveDescriptor(ctx, id.String())
	if err != nil {
		return []image.ID{}, errors.Wrap(err, "failed to get parent image")
	}

	cs := i.client.ContentStore()

	allPlatforms, err := containerdimages.Platforms(ctx, cs, target)
	if err != nil {
		return []image.ID{}, errdefs.System(errors.Wrap(err, "failed to list platforms supported by image"))
	}

	parentRootFS := []ocispec.RootFS{}
	for _, platform := range allPlatforms {
		rootfs, err := platformRootfs(ctx, cs, target, platform)
		if err != nil {
			if !cerrdefs.IsNotFound(err) {
				logrus.WithFields(logrus.Fields{
					logrus.ErrorKey: err,
					"image":         target.Digest,
					"platform":      platform,
				}).Warning("failed to get platform-specific rootfs")
			}
			continue
		}

		parentRootFS = append(parentRootFS, rootfs)
	}

	imgs, err := i.client.ImageService().List(ctx)
	if err != nil {
		return []image.ID{}, errdefs.System(errors.Wrap(err, "failed to list all images"))
	}

	children := []image.ID{}
	for _, img := range imgs {
	nextImage:
		for _, platform := range allPlatforms {
			rootfs, err := platformRootfs(ctx, cs, img.Target, platform)
			if err != nil {
				if !cerrdefs.IsNotFound(err) {
					logrus.WithFields(logrus.Fields{
						logrus.ErrorKey: err,
						"image":         img.Target.Digest,
						"platform":      platform,
					}).Warning("failed to get platform-specific rootfs")
				}
				continue
			}

			for _, parentRoot := range parentRootFS {
				if isRootfsChildOf(rootfs, parentRoot) {
					children = append(children, image.ID(img.Target.Digest))
					break nextImage
				}
			}
		}

	}

	return children, nil
}

// platformRootfs returns a rootfs for a specified platform.
func platformRootfs(ctx context.Context, store content.Store, desc ocispec.Descriptor, platform ocispec.Platform) (ocispec.RootFS, error) {
	empty := ocispec.RootFS{}

	configDesc, err := containerdimages.Config(ctx, store, desc, platforms.OnlyStrict(platform))
	if err != nil {
		return empty, errors.Wrapf(err, "failed to get config for platform %s", platforms.Format(platform))
	}

	diffs, err := containerdimages.RootFS(ctx, store, configDesc)
	if err != nil {
		return empty, errors.Wrapf(err, "failed to obtain rootfs")
	}

	return ocispec.RootFS{
		Type:    "layers",
		DiffIDs: diffs,
	}, nil
}

// isRootfsChildOf checks if all layers from parent rootfs are child's first layers
// and child has at least one more layer (to make it not commutative).
// Example:
// A with layers [X, Y],
// B with layers [X, Y, Z]
// C with layers [Y, Z]
//
// Only isRootfsChildOf(B, A) is true.
// Which means that B is considered a children of A. B and C has no children.
// See more examples in TestIsRootfsChildOf.
func isRootfsChildOf(child ocispec.RootFS, parent ocispec.RootFS) bool {
	childLen := len(child.DiffIDs)
	parentLen := len(parent.DiffIDs)

	if childLen <= parentLen {
		return false
	}

	for i := 0; i < parentLen; i++ {
		if child.DiffIDs[i] != parent.DiffIDs[i] {
			return false
		}
	}

	return true
}

package containerd

import (
	"context"

	"github.com/containerd/containerd/content"
	cerrdefs "github.com/containerd/containerd/errdefs"
	containerdimages "github.com/containerd/containerd/images"
	"github.com/containerd/containerd/platforms"
	"github.com/docker/docker/errdefs"
	"github.com/docker/docker/image"
	ocispec "github.com/opencontainers/image-spec/specs-go/v1"
	"github.com/pkg/errors"
	"github.com/sirupsen/logrus"
)

// Children returns a slice of image ID which rootfs is a superset of the
// rootfs of the given image ID, excluding images with exactly the same rootfs.
// Called from list.go to filter containers.
func (i *ImageService) Children(ctx context.Context, id image.ID) ([]image.ID, error) {
	target, err := i.resolveDescriptor(ctx, id.String())
	if err != nil {
		return []image.ID{}, errors.Wrap(err, "failed to get parent image")
	}

	cs := i.client.ContentStore()

	allPlatforms, err := containerdimages.Platforms(ctx, cs, target)
	if err != nil {
		return []image.ID{}, errdefs.System(errors.Wrap(err, "failed to list platforms supported by image"))
	}

	parentRootFS := []ocispec.RootFS{}
	for _, platform := range allPlatforms {
		rootfs, err := platformRootfs(ctx, cs, target, platform)
		if err != nil {
			if !cerrdefs.IsNotFound(err) {
				logrus.WithFields(logrus.Fields{
					logrus.ErrorKey: err,
					"image":         target.Digest,
					"platform":      platform,
				}).Warning("failed to get platform-specific rootfs")
			}
			continue
		}

		parentRootFS = append(parentRootFS, rootfs)
	}

	imgs, err := i.client.ImageService().List(ctx)
	if err != nil {
		return []image.ID{}, errdefs.System(errors.Wrap(err, "failed to list all images"))
	}

	children := []image.ID{}
	for _, img := range imgs {
	nextImage:
		for _, platform := range allPlatforms {
			rootfs, err := platformRootfs(ctx, cs, img.Target, platform)
			if err != nil {
				if !cerrdefs.IsNotFound(err) {
					logrus.WithFields(logrus.Fields{
						logrus.ErrorKey: err,
						"image":         img.Target.Digest,
						"platform":      platform,
					}).Warning("failed to get platform-specific rootfs")
				}
				continue
			}

			for _, parentRoot := range parentRootFS {
				if isRootfsChildOf(rootfs, parentRoot) {
					children = append(children, image.ID(img.Target.Digest))
					break nextImage
				}
			}
		}

	}

	return children, nil
}

// platformRootfs returns a rootfs for a specified platform.
func platformRootfs(ctx context.Context, store content.Store, desc ocispec.Descriptor, platform ocispec.Platform) (ocispec.RootFS, error) {
	empty := ocispec.RootFS{}

	configDesc, err := containerdimages.Config(ctx, store, desc, platforms.OnlyStrict(platform))
	if err != nil {
		return empty, errors.Wrapf(err, "failed to get config for platform %s", platforms.Format(platform))
	}

	diffs, err := containerdimages.RootFS(ctx, store, configDesc)
	if err != nil {
		return empty, errors.Wrapf(err, "failed to obtain rootfs")
	}

	return ocispec.RootFS{
		Type:    "layers",
		DiffIDs: diffs,
	}, nil
}

// isRootfsChildOf checks if all layers from parent rootfs are child's first layers
// and child has at least one more layer (to make it not commutative).
// Example:
// A with layers [X, Y],
// B with layers [X, Y, Z]
// C with layers [Y, Z]
//
// Only isRootfsChildOf(B, A) is true.
// Which means that B is considered a children of A. B and C has no children.
// See more examples in TestIsRootfsChildOf.
func isRootfsChildOf(child ocispec.RootFS, parent ocispec.RootFS) bool {
	childLen := len(child.DiffIDs)
	parentLen := len(parent.DiffIDs)

	if childLen <= parentLen {
		return false
	}

	for i := 0; i < parentLen; i++ {
		if child.DiffIDs[i] != parent.DiffIDs[i] {
			return false
		}
	}

	return true
}

// parents returns a slice of image IDs whose entire rootfs contents match,
// in order, the childs first layers, excluding images with the exact same
// rootfs.
//
// Called from image_delete.go to prune dangling parents.
func (i *ImageService) parents(ctx context.Context, id image.ID) ([]imageWithRootfs, error) {
	target, err := i.resolveDescriptor(ctx, id.String())
	if err != nil {
		return nil, errors.Wrap(err, "failed to get child image")
	}

	cs := i.client.ContentStore()

	allPlatforms, err := containerdimages.Platforms(ctx, cs, target)
	if err != nil {
		return nil, errdefs.System(errors.Wrap(err, "failed to list platforms supported by image"))
	}

	var childRootFS []ocispec.RootFS
	for _, platform := range allPlatforms {
		rootfs, err := platformRootfs(ctx, cs, target, platform)
		if err != nil {
			if cerrdefs.IsNotFound(err) {
				continue
			}
			return nil, errdefs.System(errors.Wrap(err, "failed to get platform-specific rootfs"))
		}

		childRootFS = append(childRootFS, rootfs)
	}

	imgs, err := i.client.ImageService().List(ctx)
	if err != nil {
		return nil, errdefs.System(errors.Wrap(err, "failed to list all images"))
	}

	var parents []imageWithRootfs
	for _, img := range imgs {
	nextImage:
		for _, platform := range allPlatforms {
			rootfs, err := platformRootfs(ctx, cs, img.Target, platform)
			if err != nil {
				if cerrdefs.IsNotFound(err) {
					continue
				}
				return nil, errdefs.System(errors.Wrap(err, "failed to get platform-specific rootfs"))
			}

			for _, childRoot := range childRootFS {
				if isRootfsChildOf(childRoot, rootfs) {
					parents = append(parents, imageWithRootfs{
						img:    img,
						rootfs: rootfs,
					})
					break nextImage
				}
			}
		}
	}

	return parents, nil
}

type imageWithRootfs struct {
	img    containerdimages.Image
	rootfs ocispec.RootFS
}

`err` could also be `context.Canceled` or `context.DeadlineExceeded`, in which case returning early would be a more appropriate course of action. And more generally, shouldn't it return early on any unexpected error? If the image's rootfs for the platform is neither found nor positively confirmed to not exist in the content store, we can't be confident that `parents` will be able to find all the parents. If it's some transient error, say if the containerd process died in the middle of handling the request and was restarted so it could handle the next, `parents` might return with no error but an incomplete list of parents, silently (save for warnings in the daemon log) leaking content.
```suggestion
			if cerrdefs.IsNotFound(err) {
				continue
			}
			return nil, errdefs.System(errors.Wrap(err, "failed to get platform-specific rootfs"))
```