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
}

Since we're pruning parents recursively, wouldn't it be more efficient to collect up all the parents just once for each image? The parent-of-parent is also a parent of img, after all.