c8d: Implement prune
- Depends on: https://github.com/moby/moby/pull/45289

Upstreams:
- https://github.com/rumpl/moby/pull/103
- https://github.com/rumpl/moby/pull/20
- https://github.com/rumpl/moby/pull/60

**- What I did**
Implemented prune from fork and adjusted to upstream code.
Also fixed excluding images being used by containers.

Warning: This doesn't handle containers run with `docker run 124c7d2` correctly as it won't exclude their images from being pruned. This doesn't affect the container though, because as long as the snapshot is not deleted, the container will continue to be functional until it's deleted. This may be a correct behavior though?

This is not perfect, but is at least better than not having prune at all.



**- How I did it**

**- How to verify it**
```bash
$ docker run alpine
Unable to find image 'alpine:latest' locally
124c7d270790: Download complete
b5a5b7ce4eab: Download complete
51e60588ff2c: Download complete
c41833b44d91: Download complete
x$ docker run busybox
Unable to find image 'busybox:latest' locally
b5d6fe071263: Download complete
ba7000206594: Download complete
3fbaf71a998b: Download complete
b50100f25006: Download complete
$ docker image prune
WARNING! This will remove all dangling images.
Are you sure you want to continue? [y/N] y
Total reclaimed space: 0B
$ docker ps -a
CONTAINER ID   IMAGE     COMMAND     CREATED          STATUS                      PORTS     NAMES
d8175435dd9b   busybox   "sh"        17 seconds ago   Exited (0) 15 seconds ago             modest_haibt
e735d30840bc   alpine    "/bin/sh"   20 seconds ago   Exited (0) 19 seconds ago             elastic_herschel
$ docker rm d8175435dd9b
d8175435dd9b
$ docker image prune -a
WARNING! This will remove all images without at least one container associated to them.
Are you sure you want to continue? [y/N] y
Deleted Images:
untagged: docker.io/library/busybox:latest
deleted: sha256:b5d6fe0712636ceb7430189de28819e195e8966372edfc2d9409d79402a0dc16
deleted: sha256:ba7000206594c2d72c3ab550453004c0dc50961157e5ebd2fb8ea1890099d02d
deleted: sha256:3fbaf71a998bae6e375be74b999bd418091bf6511e356a129fdc969c4a94a5bc
deleted: sha256:b50100f25006c29bd3a3dd4abacfeb7e9cb61c1a758d07c68fa699a2494fd2df

Total reclaimed space: 2.005MB
$ docker rm e735d30840bc
e735d30840bc
$ docker image prune
WARNING! This will remove all dangling images.
Are you sure you want to continue? [y/N] y
Total reclaimed space: 0B
$ docker image prune -a
WARNING! This will remove all images without at least one container associated to them.
Are you sure you want to continue? [y/N] y
Deleted Images:
untagged: docker.io/library/alpine:latest
deleted: sha256:124c7d2707904eea7431fffe91522a01e5a861a624ee31d03372cc1d138a3126
deleted: sha256:b5a5b7ce4eabc8414bf367761a28f4e8b16952ce5de537c15ed917b71b245f11
deleted: sha256:51e60588ff2cd9f45792b23de89bfface0a7fbd711d17c5f5ce900a4f6b16260
deleted: sha256:c41833b44d910632b415cd89a9cdaa4d62c9725dc56c99a7ddadafd6719960f9

Total reclaimed space: 3.266MB
$ docker images
REPOSITORY   TAG       IMAGE ID   CREATED   SIZE
$ ctr image ls
REF TYPE DIGEST SIZE PLATFORMS LABELS
$ ctr content ls
DIGEST  SIZE    AGE     LABELS
```


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


daemon/containerd/image_prune.go
package containerd

import (
	"context"
	"errors"

	"github.com/docker/docker/api/types"
	"github.com/docker/docker/api/types/filters"
	"github.com/docker/docker/errdefs"
)

// ImagesPrune removes unused images
func (i *ImageService) ImagesPrune(ctx context.Context, pruneFilters filters.Args) (*types.ImagesPruneReport, error) {
	return nil, errdefs.NotImplemented(errors.New("not implemented"))
}

package containerd

import (
	"context"

	cerrdefs "github.com/containerd/containerd/errdefs"
	containerdimages "github.com/containerd/containerd/images"
	"github.com/docker/distribution/reference"
	"github.com/docker/docker/api/types"
	"github.com/docker/docker/api/types/filters"
	"github.com/docker/docker/errdefs"
	"github.com/hashicorp/go-multierror"
	ocispec "github.com/opencontainers/image-spec/specs-go/v1"
	"github.com/pkg/errors"
	"github.com/sirupsen/logrus"
)

var imagesAcceptedFilters = map[string]bool{
	"dangling": true,
	"label":    true,
	"label!":   true,
	"until":    true,
}

// errPruneRunning is returned when a prune request is received while
// one is in progress
var errPruneRunning = errdefs.Conflict(errors.New("a prune operation is already running"))

// ImagesPrune removes unused images
func (i *ImageService) ImagesPrune(ctx context.Context, fltrs filters.Args) (*types.ImagesPruneReport, error) {
	if !i.pruneRunning.CompareAndSwap(false, true) {
		return nil, errPruneRunning
	}
	defer i.pruneRunning.Store(false)

	err := fltrs.Validate(imagesAcceptedFilters)
	if err != nil {
		return nil, err
	}

	danglingOnly, err := fltrs.GetBoolOrDefault("dangling", false)
	if err != nil {
		return nil, err
	}
	// dangling=false will filter out dangling images like in image list.
	// Remove it, because in this context dangling=false means that we're
	// pruning NOT ONLY dangling (`docker image prune -a`) instead of NOT DANGLING.
	// This will be handled by the danglingOnly parameter of pruneUnused.
	for _, v := range fltrs.Get("dangling") {
		fltrs.Del("dangling", v)
	}

	_, filterFunc, err := i.setupFilters(ctx, fltrs)
	if err != nil {
		return nil, err
	}

	return i.pruneUnused(ctx, filterFunc, danglingOnly)
}

func (i *ImageService) pruneUnused(ctx context.Context, filterFunc imageFilterFunc, danglingOnly bool) (*types.ImagesPruneReport, error) {
	report := types.ImagesPruneReport{}
	is := i.client.ImageService()
	store := i.client.ContentStore()

	allImages, err := i.client.ImageService().List(ctx)
	if err != nil {
		return nil, err
	}

	imagesToPrune := map[string]containerdimages.Image{}
	for _, img := range allImages {
		if !danglingOnly || isDanglingImage(img) {
			imagesToPrune[img.Name] = img
		}
	}

	// Apply filters
	for name, img := range imagesToPrune {
		filteredOut := !filterFunc(img)
		logrus.WithField("image", name).WithField("filteredOut", filteredOut).Debug("filtering image")
		if filteredOut {
			delete(imagesToPrune, name)
		}
	}

	containers := i.containers.List()

	var errs error
	// Exclude images used by existing containers
	for _, ctr := range containers {
		// Config.Image is the image reference passed by user.
		// For example: container created by `docker run alpine` will have Image="alpine"
		// Warning: This doesn't handle truncated ids:
		//          `docker run 124c7d2` will have Image="124c7d270790"
		ref, err := reference.ParseNormalizedNamed(ctr.Config.Image)
		logrus.WithFields(logrus.Fields{
			"ctr":          ctr.ID,
			"image":        ref,
			"nameParseErr": err,
		}).Debug("filtering container's image")

		if err == nil {
			name := reference.TagNameOnly(ref)
			delete(imagesToPrune, name.String())
		}
	}

	logrus.WithField("images", imagesToPrune).Debug("pruning")

	for _, img := range imagesToPrune {
		blobs := []ocispec.Descriptor{}

		err = containerdimages.Walk(ctx, presentChildrenHandler(store, containerdimages.HandlerFunc(
			func(_ context.Context, desc ocispec.Descriptor) ([]ocispec.Descriptor, error) {
				blobs = append(blobs, desc)
				return nil, nil
			})),
			img.Target)

		if err != nil {
			errs = multierror.Append(errs, err)
			continue
		}
		err = is.Delete(ctx, img.Name, containerdimages.SynchronousDelete())
		if err != nil && !cerrdefs.IsNotFound(err) {
			errs = multierror.Append(errs, err)
			continue
		}

		report.ImagesDeleted = append(report.ImagesDeleted,
			types.ImageDeleteResponseItem{
				Untagged: img.Name,
			},
		)

		// Check which blobs have been deleted and sum their sizes
		for _, blob := range blobs {
			_, err := store.ReaderAt(ctx, blob)

			if cerrdefs.IsNotFound(err) {
				report.ImagesDeleted = append(report.ImagesDeleted,
					types.ImageDeleteResponseItem{
						Deleted: blob.Digest.String(),
					},
				)
				report.SpaceReclaimed += uint64(blob.Size)
			}
		}
	}
	return &report, errs
}

We need to look if we can fix that (should probably resolve and store what's resolved, instead of storing the truncated ID)