cleanup: Add RewriteHistory RPC

Historically we have advised users who need to rewrite history to do so
locally and force push their change to Gitlab. However, upcoming changes
may prevent a user from pushing in scenarios where they need to remove a
large blob from their repository's history.

To handle this scenario, we introduce a new `RewriteHistory` RPC which
will invoke git-filer-repo(1) on the target repository. filter-repo
has a large number of options, but we will support only two:

 --strip-blogs-with-ids
   Given a file containing a list of newline-delimited object ids,
   rewrite history to remove them from all commits.
 --replace-text
   Given a file of literals and patterns, replace all matching
   instances in history with '***REMOVED***'.

filter-repo works by fetching the repository contents via
git-fast-export(1), making the requested changes, and writing the
changes back via git-fast-import(1). As filter-repo uses the '--force'
flag[0] the repository must be made read-only before calling this RPC.

filter-repo is currently incompatible with SHA256 repositories.

[0] https://git-scm.com/docs/git-fast-import#_parallel_operation

Changelog: added

7 files changed, 1031 insertions, 31 deletions

diff --git a/internal/gitaly/service/cleanup/rewrite_history.go b/internal/gitaly/service/cleanup/rewrite_history.go
new file mode 100644
index 000000000..7bbdd258e
--- /dev/null
+++ b/internal/gitaly/service/cleanup/rewrite_history.go
@@ -0,0 +1,184 @@
+package cleanup
+
+import (
+	"bytes"
+	"context"
+	"errors"
+	"fmt"
+	"io"
+	"os"
+	"os/exec"
+	"strings"
+
+	"gitlab.com/gitlab-org/gitaly/v16/internal/git"
+	"gitlab.com/gitlab-org/gitaly/v16/internal/git/localrepo"
+	"gitlab.com/gitlab-org/gitaly/v16/internal/structerr"
+	"gitlab.com/gitlab-org/gitaly/v16/internal/tempdir"
+	"gitlab.com/gitlab-org/gitaly/v16/proto/go/gitalypb"
+)
+
+// RewriteHistory uses git-filter-repo(1) to remove specified blobs from commit history and
+// replace blobs to redact specified text patterns. This does not delete the removed blobs from
+// the object database, they must be garbage collected separately.
+func (s *server) RewriteHistory(server gitalypb.CleanupService_RewriteHistoryServer) error {
+	ctx := server.Context()
+
+	request, err := server.Recv()
+	if err != nil {
+		return fmt.Errorf("receiving initial request: %w", err)
+	}
+
+	repoProto := request.GetRepository()
+	if err := s.locator.ValidateRepository(repoProto); err != nil {
+		return structerr.NewInvalidArgument("%w", err)
+	}
+
+	repo := s.localrepo(repoProto)
+
+	objectHash, err := repo.ObjectHash(ctx)
+	if err != nil {
+		return fmt.Errorf("detecting object hash: %w", err)
+	}
+
+	if objectHash.Format == "sha256" {
+		return structerr.NewInvalidArgument("git-filter-repo does not support repositories using the SHA256 object format")
+	}
+
+	// Unset repository so that we can validate that repository is not sent on subsequent requests.
+	request.Repository = nil
+
+	blobsToRemove := make([]string, 0, len(request.GetBlobs()))
+	redactions := make([][]byte, 0, len(request.GetRedactions()))
+
+	for {
+		if request.GetRepository() != nil {
+			return structerr.NewInvalidArgument("subsequent requests must not contain repository")
+		}
+
+		if len(request.GetBlobs()) == 0 && len(request.GetRedactions()) == 0 {
+			return structerr.NewInvalidArgument("no object IDs or text replacements specified")
+		}
+
+		for _, oid := range request.GetBlobs() {
+			if err := objectHash.ValidateHex(oid); err != nil {
+				return structerr.NewInvalidArgument("validating object ID: %w", err).WithMetadata("oid", oid)
+			}
+			blobsToRemove = append(blobsToRemove, oid)
+		}
+
+		for _, pattern := range request.GetRedactions() {
+			if strings.Contains(string(pattern), "\n") {
+				// We deliberately do not log the invalid pattern as this is
+				// likely to contain sensitive information.
+				return structerr.NewInvalidArgument("redaction pattern contains newline")
+			}
+			redactions = append(redactions, pattern)
+		}
+
+		request, err = server.Recv()
+		if err != nil {
+			if errors.Is(err, io.EOF) {
+				break
+			}
+
+			return fmt.Errorf("receiving next request: %w", err)
+		}
+	}
+
+	if err := s.runFilterRepo(ctx, repo, repoProto, blobsToRemove, redactions); err != nil {
+		return fmt.Errorf("rewriting repository history: %w", err)
+	}
+
+	if err := server.SendAndClose(&gitalypb.RewriteHistoryResponse{}); err != nil {
+		return fmt.Errorf("sending RewriteHistoryResponse: %w", err)
+	}
+
+	return nil
+}
+
+func (s *server) runFilterRepo(
+	ctx context.Context,
+	repo *localrepo.Repo,
+	repoProto *gitalypb.Repository,
+	blobsToRemove []string,
+	redactions [][]byte,
+) error {
+	// Place argument files in a tempdir so that cleanup is handled automatically.
+	tmpDir, err := tempdir.New(ctx, repo.GetStorageName(), s.logger, s.locator)
+	if err != nil {
+		return fmt.Errorf("create tempdir: %w", err)
+	}
+
+	flags := make([]git.Option, 0, 2)
+
+	if len(blobsToRemove) > 0 {
+		blobPath, err := writeArgFile("strip-blobs", tmpDir.Path(), []byte(strings.Join(blobsToRemove, "\n")))
+		if err != nil {
+			return err
+		}
+
+		flags = append(flags, git.Flag{Name: "--strip-blobs-with-ids=" + blobPath})
+	}
+
+	if len(redactions) > 0 {
+		replacePath, err := writeArgFile("replace-text", tmpDir.Path(), bytes.Join(redactions, []byte("\n")))
+		if err != nil {
+			return err
+		}
+
+		flags = append(flags, git.Flag{Name: "--replace-text=" + replacePath})
+	}
+
+	var stdout, stderr strings.Builder
+	if err := repo.ExecAndWait(ctx,
+		git.Command{
+			Name: "filter-repo",
+			Flags: append([]git.Option{
+				// Prevent automatic cleanup tasks like deleting 'origin' and running git-gc(1).
+				git.Flag{Name: "--partial"},
+				// Bypass check that repository is not a fresh clone.
+				git.Flag{Name: "--force"},
+				// filter-repo will by default create 'replace' refs for refs it rewrites, but Gitaly
+				// disables this feature. This option will update any existing user-created replace refs,
+				// while preventing the creation of new ones.
+				git.Flag{Name: "--replace-refs=update-no-add"},
+				// Pass '--quiet' to child git processes.
+				git.Flag{Name: "--quiet"},
+			}, flags...),
+		},
+		git.WithRefTxHook(repo),
+		git.WithStdout(&stdout),
+		git.WithStderr(&stderr),
+	); err != nil {
+		var exitErr *exec.ExitError
+		if errors.As(err, &exitErr) {
+			return structerr.New("git-filter-repo failed with exit code %d", exitErr.ExitCode()).WithMetadataItems(
+				structerr.MetadataItem{Key: "stdout", Value: stdout.String()},
+				structerr.MetadataItem{Key: "stderr", Value: stderr.String()},
+			)
+		}
+		return fmt.Errorf("running git-filter-repo: %w", err)
+	}
+
+	return nil
+}
+
+func writeArgFile(name string, dir string, input []byte) (string, error) {
+	f, err := os.CreateTemp(dir, name)
+	if err != nil {
+		return "", fmt.Errorf("creating %q file: %w", name, err)
+	}
+
+	path := f.Name()
+
+	_, err = f.Write(input)
+	if err != nil {
+		return "", fmt.Errorf("writing %q file: %w", name, err)
+	}
+
+	if err := f.Close(); err != nil {
+		return "", fmt.Errorf("closing %q file: %w", name, err)
+	}
+
+	return path, nil
+}
diff --git a/internal/gitaly/service/cleanup/rewrite_history_test.go b/internal/gitaly/service/cleanup/rewrite_history_test.go
new file mode 100644
index 000000000..0d2c4363c
--- /dev/null
+++ b/internal/gitaly/service/cleanup/rewrite_history_test.go
@@ -0,0 +1,518 @@
+package cleanup
+
+import (
+	"strings"
+	"testing"
+
+	"github.com/stretchr/testify/require"
+	"gitlab.com/gitlab-org/gitaly/v16/internal/git"
+	"gitlab.com/gitlab-org/gitaly/v16/internal/git/gittest"
+	"gitlab.com/gitlab-org/gitaly/v16/internal/gitaly/storage"
+	"gitlab.com/gitlab-org/gitaly/v16/internal/structerr"
+	"gitlab.com/gitlab-org/gitaly/v16/internal/testhelper"
+	"gitlab.com/gitlab-org/gitaly/v16/internal/testhelper/testcfg"
+	"gitlab.com/gitlab-org/gitaly/v16/proto/go/gitalypb"
+)
+
+func TestRewriteHistory(t *testing.T) {
+	t.Parallel()
+	gittest.SkipWithSHA256(t)
+
+	ctx := testhelper.Context(t)
+	cfg := testcfg.Build(t)
+	testcfg.BuildGitalyHooks(t, cfg)
+	cfg.SocketPath = runCleanupServiceServer(t, cfg)
+
+	client, conn := newCleanupServiceClient(t, cfg.SocketPath)
+	t.Cleanup(func() { conn.Close() })
+
+	addUnmodifiedRefs := func(repoPath string) []git.Reference {
+		unmodifiedCommit := gittest.WriteCommit(t, cfg, repoPath, gittest.WithBranch("unmodified"), gittest.WithTreeEntries(
+			gittest.TreeEntry{Path: "unmodified-file", Mode: "100644", Content: "can't touch this"},
+		))
+		unmodifiedTag := gittest.WriteTag(t, cfg, repoPath, "unmodified-tag", unmodifiedCommit.Revision(), gittest.WriteTagConfig{
+			Message: "annotated",
+		})
+		keepRef := git.ReferenceName("refs/keeparound/" + unmodifiedCommit.String())
+		gittest.WriteRef(t, cfg, repoPath, keepRef, unmodifiedCommit)
+
+		return []git.Reference{
+			{
+				Name:   "refs/heads/unmodified",
+				Target: unmodifiedCommit.String(),
+			},
+			{
+				Name:   "refs/tags/unmodified-tag",
+				Target: unmodifiedTag.String(),
+			},
+			{
+				Name:   keepRef,
+				Target: unmodifiedCommit.String(),
+			},
+		}
+	}
+
+	type setupData struct {
+		requests         []*gitalypb.RewriteHistoryRequest
+		repoPath         string
+		expectedRefs     []git.Reference
+		expectedErr      error
+		expectedResponse *gitalypb.RewriteHistoryResponse
+	}
+
+	for _, tc := range []struct {
+		desc  string
+		setup func(t *testing.T) setupData
+	}{
+		{
+			desc: "no requests",
+			setup: func(t *testing.T) setupData {
+				return setupData{
+					requests: nil,
+					expectedErr: testhelper.GitalyOrPraefect(
+						structerr.NewInternal("receiving initial request: EOF"),
+						structerr.NewInternal("EOF"),
+					),
+				}
+			},
+		},
+		{
+			desc: "missing repository",
+			setup: func(t *testing.T) setupData {
+				repoPath := gittest.NewRepositoryName(t)
+
+				return setupData{
+					requests: []*gitalypb.RewriteHistoryRequest{
+						{
+							Repository: &gitalypb.Repository{
+								StorageName:  cfg.Storages[0].Name,
+								RelativePath: repoPath,
+							},
+							Redactions: [][]byte{[]byte("hunter2")},
+						},
+					},
+					expectedErr: testhelper.ToInterceptedMetadata(
+						structerr.New("%w", storage.NewRepositoryNotFoundError(cfg.Storages[0].Name, repoPath)),
+					),
+				}
+			},
+		},
+		{
+			desc: "repository in subsequent request",
+			setup: func(t *testing.T) setupData {
+				repo, _ := gittest.CreateRepository(t, ctx, cfg)
+
+				return setupData{
+					requests: []*gitalypb.RewriteHistoryRequest{
+						{
+							Repository: repo,
+							Redactions: [][]byte{[]byte("hunter2")},
+						},
+						{
+							Repository: repo,
+							Redactions: [][]byte{[]byte("secretpassword")},
+						},
+					},
+					expectedErr: structerr.NewInvalidArgument("subsequent requests must not contain repository"),
+				}
+			},
+		},
+		{
+			desc: "empty request",
+			setup: func(t *testing.T) setupData {
+				repo, _ := gittest.CreateRepository(t, ctx, cfg)
+
+				return setupData{
+					requests: []*gitalypb.RewriteHistoryRequest{
+						{
+							Repository: repo,
+						},
+					},
+					expectedErr: structerr.NewInvalidArgument("no object IDs or text replacements specified"),
+				}
+			},
+		},
+		{
+			desc: "remove invalid oid",
+			setup: func(t *testing.T) setupData {
+				repo, repoPath := gittest.CreateRepository(t, ctx, cfg)
+				unmodifiedRefs := addUnmodifiedRefs(repoPath)
+
+				return setupData{
+					requests: []*gitalypb.RewriteHistoryRequest{
+						{
+							Repository: repo,
+							Blobs:      []string{"invalid oid"},
+						},
+					},
+					repoPath:     repoPath,
+					expectedRefs: unmodifiedRefs,
+					expectedErr: testhelper.WithInterceptedMetadata(
+						structerr.NewInvalidArgument("validating object ID: invalid object ID: \"invalid oid\", expected length %v, got 11", gittest.DefaultObjectHash.EncodedLen()),
+						"oid", "invalid oid",
+					),
+				}
+			},
+		},
+		{
+			desc: "redaction pattern with newline",
+			setup: func(t *testing.T) setupData {
+				repo, repoPath := gittest.CreateRepository(t, ctx, cfg)
+				unmodifiedRefs := addUnmodifiedRefs(repoPath)
+
+				return setupData{
+					requests: []*gitalypb.RewriteHistoryRequest{
+						{
+							Repository: repo,
+							Redactions: [][]byte{[]byte("hunter\n2")},
+						},
+					},
+					repoPath:     repoPath,
+					expectedRefs: unmodifiedRefs,
+					expectedErr:  structerr.NewInvalidArgument("redaction pattern contains newline"),
+				}
+			},
+		},
+		{
+			desc: "redaction pattern with escaped newline",
+			setup: func(t *testing.T) setupData {
+				repo, repoPath := gittest.CreateRepository(t, ctx, cfg)
+				unmodifiedRefs := addUnmodifiedRefs(repoPath)
+
+				return setupData{
+					requests: []*gitalypb.RewriteHistoryRequest{
+						{
+							Repository: repo,
+							Redactions: [][]byte{[]byte("hunter\\n2")},
+						},
+					},
+					repoPath:         repoPath,
+					expectedRefs:     unmodifiedRefs,
+					expectedResponse: &gitalypb.RewriteHistoryResponse{},
+				}
+			},
+		},
+		{
+			desc: "remove non-existent oid",
+			setup: func(t *testing.T) setupData {
+				repo, repoPath := gittest.CreateRepository(t, ctx, cfg)
+				unmodifiedRefs := addUnmodifiedRefs(repoPath)
+
+				return setupData{
+					requests: []*gitalypb.RewriteHistoryRequest{
+						{
+							Repository: repo,
+							Blobs:      []string{strings.Repeat("a", gittest.DefaultObjectHash.EncodedLen())},
+						},
+					},
+					repoPath:         repoPath,
+					expectedRefs:     unmodifiedRefs,
+					expectedResponse: &gitalypb.RewriteHistoryResponse{},
+				}
+			},
+		},
+		{
+			desc: "remove blobs",
+			setup: func(t *testing.T) setupData {
+				repo, repoPath := gittest.CreateRepository(t, ctx, cfg)
+				unmodifiedRefs := addUnmodifiedRefs(repoPath)
+
+				blobToRemove := gittest.WriteBlob(t, cfg, repoPath, []byte("big blob"))
+				_ = gittest.WriteCommit(t, cfg, repoPath, gittest.WithBranch("main"), gittest.WithTreeEntries(
+					gittest.TreeEntry{Path: "remove-me", Mode: "100644", OID: blobToRemove},
+					gittest.TreeEntry{Path: "a-file", Mode: "100644", Content: "foobar"},
+				))
+				updatedCommit := gittest.WriteCommit(t, cfg, repoPath, gittest.WithTreeEntries(
+					gittest.TreeEntry{Path: "a-file", Mode: "100644", Content: "foobar"},
+				))
+
+				return setupData{
+					requests: []*gitalypb.RewriteHistoryRequest{
+						{
+							Repository: repo,
+							Blobs:      []string{blobToRemove.String()},
+						},
+					},
+					repoPath: repoPath,
+					expectedRefs: append(unmodifiedRefs, []git.Reference{
+						{
+							Name:   "refs/heads/main",
+							Target: updatedCommit.String(),
+						},
+					}...),
+					expectedResponse: &gitalypb.RewriteHistoryResponse{},
+				}
+			},
+		},
+		{
+			desc: "redact blobs",
+			setup: func(t *testing.T) setupData {
+				repo, repoPath := gittest.CreateRepository(t, ctx, cfg)
+				unmodifiedRefs := addUnmodifiedRefs(repoPath)
+
+				_ = gittest.WriteCommit(t, cfg, repoPath, gittest.WithBranch("main"), gittest.WithTreeEntries(
+					gittest.TreeEntry{Path: "redact-me", Mode: "100644", Content: "my password is hunter2"},
+				))
+				updatedCommit := gittest.WriteCommit(t, cfg, repoPath, gittest.WithTreeEntries(
+					gittest.TreeEntry{Path: "redact-me", Mode: "100644", Content: "my password is ***REMOVED***"},
+				))
+
+				return setupData{
+					requests: []*gitalypb.RewriteHistoryRequest{
+						{
+							Repository: repo,
+							Redactions: [][]byte{
+								[]byte("hunter2"),
+							},
+						},
+					},
+					repoPath: repoPath,
+					expectedRefs: append(unmodifiedRefs, []git.Reference{
+						{
+							Name:   "refs/heads/main",
+							Target: updatedCommit.String(),
+						},
+					}...),
+					expectedResponse: &gitalypb.RewriteHistoryResponse{},
+				}
+			},
+		},
+		{
+			desc: "multiple requests",
+			setup: func(t *testing.T) setupData {
+				repoProto, repoPath := gittest.CreateRepository(t, ctx, cfg)
+				unmodifiedRefs := addUnmodifiedRefs(repoPath)
+
+				blobToRemove := gittest.WriteBlob(t, cfg, repoPath, []byte("big blob"))
+				_ = gittest.WriteCommit(t, cfg, repoPath, gittest.WithBranch("main"), gittest.WithTreeEntries(
+					gittest.TreeEntry{Path: "remove-me", Mode: "100644", OID: blobToRemove},
+					gittest.TreeEntry{Path: "redact-me", Mode: "100644", Content: "my password is hunter2"},
+				))
+				updatedCommit := gittest.WriteCommit(t, cfg, repoPath, gittest.WithTreeEntries(
+					gittest.TreeEntry{Path: "redact-me", Mode: "100644", Content: "my password is ***REMOVED***"},
+				))
+
+				return setupData{
+					requests: []*gitalypb.RewriteHistoryRequest{
+						{
+							Repository: repoProto,
+							Blobs:      []string{blobToRemove.String()},
+						},
+						{
+							Redactions: [][]byte{[]byte("hunter2")},
+						},
+					},
+					repoPath: repoPath,
+					expectedRefs: append(unmodifiedRefs, []git.Reference{
+						{
+							Name:   "refs/heads/main",
+							Target: updatedCommit.String(),
+						},
+					}...),
+					expectedResponse: &gitalypb.RewriteHistoryResponse{},
+				}
+			},
+		},
+		{
+			desc: "empty branch deleted",
+			setup: func(t *testing.T) setupData {
+				repo, repoPath := gittest.CreateRepository(t, ctx, cfg)
+				unmodifiedRefs := addUnmodifiedRefs(repoPath)
+
+				blobToRemove := gittest.WriteBlob(t, cfg, repoPath, []byte("big blob"))
+				_ = gittest.WriteCommit(t, cfg, repoPath, gittest.WithBranch("main"), gittest.WithTreeEntries(
+					gittest.TreeEntry{Path: "remove-me", Mode: "100644", OID: blobToRemove},
+				))
+
+				return setupData{
+					requests: []*gitalypb.RewriteHistoryRequest{
+						{
+							Repository: repo,
+							Blobs:      []string{blobToRemove.String()},
+						},
+					},
+					repoPath:         repoPath,
+					expectedRefs:     unmodifiedRefs,
+					expectedResponse: &gitalypb.RewriteHistoryResponse{},
+				}
+			},
+		},
+		{
+			desc: "tag updated",
+			setup: func(t *testing.T) setupData {
+				repo, repoPath := gittest.CreateRepository(t, ctx, cfg)
+				unmodifiedRefs := addUnmodifiedRefs(repoPath)
+
+				blobToRemove := gittest.WriteBlob(t, cfg, repoPath, []byte("big blob"))
+				commit := gittest.WriteCommit(t, cfg, repoPath, gittest.WithTreeEntries(
+					gittest.TreeEntry{Path: "remove-me", Mode: "100644", OID: blobToRemove},
+					gittest.TreeEntry{Path: "a-file", Mode: "100644", Content: "foobar"},
+				))
+				_ = gittest.WriteTag(t, cfg, repoPath, "updated-tag", commit.Revision())
+
+				updatedCommit := gittest.WriteCommit(t, cfg, repoPath, gittest.WithTreeEntries(
+					gittest.TreeEntry{Path: "a-file", Mode: "100644", Content: "foobar"},
+				))
+
+				return setupData{
+					requests: []*gitalypb.RewriteHistoryRequest{
+						{
+							Repository: repo,
+							Blobs:      []string{blobToRemove.String()},
+						},
+					},
+					repoPath: repoPath,
+					expectedRefs: append(unmodifiedRefs, []git.Reference{
+						{
+							Name:   "refs/tags/updated-tag",
+							Target: updatedCommit.String(),
+						},
+					}...),
+					expectedResponse: &gitalypb.RewriteHistoryResponse{},
+				}
+			},
+		},
+		{
+			desc: "empty tag deleted",
+			setup: func(t *testing.T) setupData {
+				repo, repoPath := gittest.CreateRepository(t, ctx, cfg)
+				unmodifiedRefs := addUnmodifiedRefs(repoPath)
+
+				blobToRemove := gittest.WriteBlob(t, cfg, repoPath, []byte("big blob"))
+				commit := gittest.WriteCommit(t, cfg, repoPath, gittest.WithTreeEntries(
+					gittest.TreeEntry{Path: "a-file", Mode: "100644", OID: blobToRemove},
+				))
+				_ = gittest.WriteTag(t, cfg, repoPath, "deleted-tag", commit.Revision(), gittest.WriteTagConfig{
+					Message: "annotated",
+				})
+
+				return setupData{
+					requests: []*gitalypb.RewriteHistoryRequest{
+						{
+							Repository: repo,
+							Blobs:      []string{blobToRemove.String()},
+						},
+					},
+					repoPath:         repoPath,
+					expectedRefs:     unmodifiedRefs,
+					expectedResponse: &gitalypb.RewriteHistoryResponse{},
+				}
+			},
+		},
+		{
+			desc: "remove blob in pool repo",
+			setup: func(t *testing.T) setupData {
+				testhelper.SkipWithWAL(t, `
+Object pools are not yet supported with transaction management.`)
+
+				repo, repoPath := gittest.CreateRepository(t, ctx, cfg)
+				unmodifiedRefs := addUnmodifiedRefs(repoPath)
+
+				poolBlob := gittest.WriteBlob(t, cfg, repoPath, []byte("pool blob"))
+				parentCommit := gittest.WriteCommit(t, cfg, repoPath,
+					gittest.WithTreeEntries(
+						gittest.TreeEntry{Path: "remove-me", Mode: "100644", OID: poolBlob},
+						gittest.TreeEntry{Path: "other-pool-file", Mode: "100644", Content: "pool blob to retain"},
+					),
+					gittest.WithBranch("main"),
+				)
+
+				gittest.CreateObjectPool(t, ctx, cfg, repo, gittest.CreateObjectPoolConfig{
+					LinkRepositoryToObjectPool: true,
+				})
+
+				_ = gittest.WriteCommit(t, cfg, repoPath,
+					gittest.WithTreeEntries(
+						gittest.TreeEntry{Path: "remove-me", Mode: "100644", OID: poolBlob},
+						gittest.TreeEntry{Path: "a-file", Mode: "100644", Content: "local blob"},
+					),
+					gittest.WithParents(parentCommit),
+					gittest.WithBranch("main"),
+				)
+
+				updatedParent := gittest.WriteCommit(t, cfg, repoPath,
+					gittest.WithTreeEntries(
+						gittest.TreeEntry{Path: "other-pool-file", Mode: "100644", Content: "pool blob to retain"},
+					),
+				)
+				updatedCommit := gittest.WriteCommit(t, cfg, repoPath,
+					gittest.WithTreeEntries(
+						gittest.TreeEntry{Path: "a-file", Mode: "100644", Content: "local blob"},
+					),
+					gittest.WithParents(updatedParent),
+				)
+
+				return setupData{
+					requests: []*gitalypb.RewriteHistoryRequest{
+						{
+							Repository: repo,
+							Blobs:      []string{poolBlob.String()},
+						},
+					},
+					repoPath: repoPath,
+					expectedRefs: append(unmodifiedRefs, []git.Reference{
+						{
+							Name:   "refs/heads/main",
+							Target: updatedCommit.String(),
+						},
+					}...),
+					expectedResponse: &gitalypb.RewriteHistoryResponse{},
+				}
+			},
+		},
+	} {
+		tc := tc
+
+		t.Run(tc.desc, func(t *testing.T) {
+			t.Parallel()
+
+			setup := tc.setup(t)
+
+			stream, err := client.RewriteHistory(ctx)
+			require.NoError(t, err)
+
+			for _, request := range setup.requests {
+				require.NoError(t, stream.Send(request))
+			}
+
+			response, err := stream.CloseAndRecv()
+			testhelper.RequireGrpcError(t, setup.expectedErr, err)
+			testhelper.ProtoEqual(t, setup.expectedResponse, response)
+
+			if setup.repoPath != "" {
+				refs := gittest.GetReferences(t, cfg, setup.repoPath)
+				require.ElementsMatch(t, refs, setup.expectedRefs)
+			}
+		})
+	}
+}
+
+func TestRewriteHistory_SHA256(t *testing.T) {
+	t.Parallel()
+
+	if !gittest.ObjectHashIsSHA256() {
+		t.Skip("test is not compatible with SHA1")
+	}
+
+	ctx := testhelper.Context(t)
+	cfg := testcfg.Build(t)
+	testcfg.BuildGitalyHooks(t, cfg)
+	cfg.SocketPath = runCleanupServiceServer(t, cfg)
+
+	client, conn := newCleanupServiceClient(t, cfg.SocketPath)
+	t.Cleanup(func() { conn.Close() })
+
+	repo, _ := gittest.CreateRepository(t, ctx, cfg)
+
+	stream, err := client.RewriteHistory(ctx)
+	require.NoError(t, err)
+
+	require.NoError(t, stream.Send(&gitalypb.RewriteHistoryRequest{
+		Repository: repo,
+		Redactions: [][]byte{[]byte("hunter2")},
+	}))
+
+	response, err := stream.CloseAndRecv()
+	require.Nil(t, response)
+	testhelper.RequireGrpcError(t, structerr.NewInvalidArgument("git-filter-repo does not support repositories using the SHA256 object format"), err)
+}
diff --git a/internal/gitaly/service/cleanup/server.go b/internal/gitaly/service/cleanup/server.go
index 3fd2d06f6..33058e5a6 100644
--- a/internal/gitaly/service/cleanup/server.go
+++ b/internal/gitaly/service/cleanup/server.go
@@ -6,6 +6,7 @@ import (
 	"gitlab.com/gitlab-org/gitaly/v16/internal/git/localrepo"
 	"gitlab.com/gitlab-org/gitaly/v16/internal/gitaly/service"
 	"gitlab.com/gitlab-org/gitaly/v16/internal/gitaly/storage"
+	"gitlab.com/gitlab-org/gitaly/v16/internal/gitaly/transaction"
 	"gitlab.com/gitlab-org/gitaly/v16/internal/log"
 	"gitlab.com/gitlab-org/gitaly/v16/proto/go/gitalypb"
 )
@@ -16,6 +17,7 @@ type server struct {
 	locator       storage.Locator
 	gitCmdFactory git.CommandFactory
 	catfileCache  catfile.Cache
+	txManager     transaction.Manager
 }
 
 // NewServer creates a new instance of a grpc CleanupServer
@@ -25,6 +27,7 @@ func NewServer(deps *service.Dependencies) gitalypb.CleanupServiceServer {
 		locator:       deps.GetLocator(),
 		gitCmdFactory: deps.GetGitCmdFactory(),
 		catfileCache:  deps.GetCatfileCache(),
+		txManager:     deps.GetTxManager(),
 	}
 }
 
diff --git a/internal/gitaly/service/cleanup/testhelper_test.go b/internal/gitaly/service/cleanup/testhelper_test.go
index 3f488eba8..8dd085f22 100644
--- a/internal/gitaly/service/cleanup/testhelper_test.go
+++ b/internal/gitaly/service/cleanup/testhelper_test.go
@@ -8,6 +8,7 @@ import (
 	"gitlab.com/gitlab-org/gitaly/v16/internal/gitaly/config"
 	"gitlab.com/gitlab-org/gitaly/v16/internal/gitaly/service"
 	hookservice "gitlab.com/gitlab-org/gitaly/v16/internal/gitaly/service/hook"
+	"gitlab.com/gitlab-org/gitaly/v16/internal/gitaly/service/objectpool"
 	"gitlab.com/gitlab-org/gitaly/v16/internal/gitaly/service/repository"
 	"gitlab.com/gitlab-org/gitaly/v16/internal/testhelper"
 	"gitlab.com/gitlab-org/gitaly/v16/internal/testhelper/testcfg"
@@ -38,6 +39,7 @@ func runCleanupServiceServer(t *testing.T, cfg config.Cfg) string {
 		gitalypb.RegisterCleanupServiceServer(srv, NewServer(deps))
 		gitalypb.RegisterHookServiceServer(srv, hookservice.NewServer(deps))
 		gitalypb.RegisterRepositoryServiceServer(srv, repository.NewServer(deps))
+		gitalypb.RegisterObjectPoolServiceServer(srv, objectpool.NewServer(deps))
 	})
 }
 
diff --git a/proto/cleanup.proto b/proto/cleanup.proto
index 511bbff46..77cf6c6a3 100644
--- a/proto/cleanup.proto
+++ b/proto/cleanup.proto
@@ -17,6 +17,26 @@ service CleanupService {
     };
   }
 
+  // RewriteHistory redacts targeted strings and deletes requested blobs in a
+  // repository and updates all references to point to the rewritten commit
+  // history. This is useful for removing inadvertently pushed secrets from your
+  // repository and purging large blobs. This is a dangerous operation.
+  //
+  // The following known error conditions may happen:
+  //
+  // - `InvalidArgument` in the following situations:
+  //    - The provided repository can't be validated.
+  //    - The repository field is set on any request other than the initial one.
+  //    - Any request, including the initial one, does not contain either blobs to
+  //      remove or redaction patterns to redact.
+  //    - A blob object ID is invalid.
+  //    - A redaction pattern contains a newline character.
+  rpc RewriteHistory(stream RewriteHistoryRequest) returns (RewriteHistoryResponse) {
+    option (op_type) = {
+      op : MUTATOR
+    };
+  }
+
 }
 
 // ApplyBfgObjectMapStreamRequest ...
@@ -47,3 +67,22 @@ message ApplyBfgObjectMapStreamResponse {
   // entries ...
   repeated Entry entries = 1;
 }
+
+// RewriteHistoryRequest is a request for the RewriteHistory RPC.
+// Each request must contain blobs, redactions, or both.
+message RewriteHistoryRequest {
+  // repository is the repository that shall be rewritten.
+  // Must be sent on the first request only.
+  Repository repository = 1 [(target_repository)=true];
+  // blobs is the list of blob object ids that will be removed from history.
+  repeated string blobs = 2;
+  // redactions is the list of literals or patterns that will be replaced
+  // with "***REMOVED***". Items cannot contain newline characters.
+  // See https://htmlpreview.github.io/?https://github.com/newren/git-filter-repo/blob/docs/html/git-filter-repo.html
+  // for a full explanation of what patterns are supported.
+  repeated bytes redactions = 3;
+}
+
+// RewriteHistoryResponse a response for the RewriteHistory RPC.
+message RewriteHistoryResponse {
+}
diff --git a/proto/go/gitalypb/cleanup.pb.go b/proto/go/gitalypb/cleanup.pb.go
index b54d5d1e2..028f0f8cc 100644
--- a/proto/go/gitalypb/cleanup.pb.go
+++ b/proto/go/gitalypb/cleanup.pb.go
@@ -130,6 +130,117 @@ func (x *ApplyBfgObjectMapStreamResponse) GetEntries() []*ApplyBfgObjectMapStrea
 	return nil
 }
 
+// RewriteHistoryRequest is a request for the RewriteHistory RPC.
+// Each request must contain blobs, redactions, or both.
+type RewriteHistoryRequest struct {
+	state         protoimpl.MessageState
+	sizeCache     protoimpl.SizeCache
+	unknownFields protoimpl.UnknownFields
+
+	// repository is the repository that shall be rewritten.
+	// Must be sent on the first request only.
+	Repository *Repository `protobuf:"bytes,1,opt,name=repository,proto3" json:"repository,omitempty"`
+	// blobs is the list of blob object ids that will be removed from history.
+	Blobs []string `protobuf:"bytes,2,rep,name=blobs,proto3" json:"blobs,omitempty"`
+	// redactions is the list of literals or patterns that will be replaced
+	// with "***REMOVED***". Items cannot contain newline characters.
+	// See https://htmlpreview.github.io/?https://github.com/newren/git-filter-repo/blob/docs/html/git-filter-repo.html
+	// for a full explanation of what patterns are supported.
+	Redactions [][]byte `protobuf:"bytes,3,rep,name=redactions,proto3" json:"redactions,omitempty"`
+}
+
+func (x *RewriteHistoryRequest) Reset() {
+	*x = RewriteHistoryRequest{}
+	if protoimpl.UnsafeEnabled {
+		mi := &file_cleanup_proto_msgTypes[2]
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		ms.StoreMessageInfo(mi)
+	}
+}
+
+func (x *RewriteHistoryRequest) String() string {
+	return protoimpl.X.MessageStringOf(x)
+}
+
+func (*RewriteHistoryRequest) ProtoMessage() {}
+
+func (x *RewriteHistoryRequest) ProtoReflect() protoreflect.Message {
+	mi := &file_cleanup_proto_msgTypes[2]
+	if protoimpl.UnsafeEnabled && x != nil {
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		if ms.LoadMessageInfo() == nil {
+			ms.StoreMessageInfo(mi)
+		}
+		return ms
+	}
+	return mi.MessageOf(x)
+}
+
+// Deprecated: Use RewriteHistoryRequest.ProtoReflect.Descriptor instead.
+func (*RewriteHistoryRequest) Descriptor() ([]byte, []int) {
+	return file_cleanup_proto_rawDescGZIP(), []int{2}
+}
+
+func (x *RewriteHistoryRequest) GetRepository() *Repository {
+	if x != nil {
+		return x.Repository
+	}
+	return nil
+}
+
+func (x *RewriteHistoryRequest) GetBlobs() []string {
+	if x != nil {
+		return x.Blobs
+	}
+	return nil
+}
+
+func (x *RewriteHistoryRequest) GetRedactions() [][]byte {
+	if x != nil {
+		return x.Redactions
+	}
+	return nil
+}
+
+// RewriteHistoryResponse a response for the RewriteHistory RPC.
+type RewriteHistoryResponse struct {
+	state         protoimpl.MessageState
+	sizeCache     protoimpl.SizeCache
+	unknownFields protoimpl.UnknownFields
+}
+
+func (x *RewriteHistoryResponse) Reset() {
+	*x = RewriteHistoryResponse{}
+	if protoimpl.UnsafeEnabled {
+		mi := &file_cleanup_proto_msgTypes[3]
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		ms.StoreMessageInfo(mi)
+	}
+}
+
+func (x *RewriteHistoryResponse) String() string {
+	return protoimpl.X.MessageStringOf(x)
+}
+
+func (*RewriteHistoryResponse) ProtoMessage() {}
+
+func (x *RewriteHistoryResponse) ProtoReflect() protoreflect.Message {
+	mi := &file_cleanup_proto_msgTypes[3]
+	if protoimpl.UnsafeEnabled && x != nil {
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		if ms.LoadMessageInfo() == nil {
+			ms.StoreMessageInfo(mi)
+		}
+		return ms
+	}
+	return mi.MessageOf(x)
+}
+
+// Deprecated: Use RewriteHistoryResponse.ProtoReflect.Descriptor instead.
+func (*RewriteHistoryResponse) Descriptor() ([]byte, []int) {
+	return file_cleanup_proto_rawDescGZIP(), []int{3}
+}
+
 // Entry refers to each parsed entry in the request's object map so the client
 // can take action.
 type ApplyBfgObjectMapStreamResponse_Entry struct {
@@ -148,7 +259,7 @@ type ApplyBfgObjectMapStreamResponse_Entry struct {
 func (x *ApplyBfgObjectMapStreamResponse_Entry) Reset() {
 	*x = ApplyBfgObjectMapStreamResponse_Entry{}
 	if protoimpl.UnsafeEnabled {
-		mi := &file_cleanup_proto_msgTypes[2]
+		mi := &file_cleanup_proto_msgTypes[4]
 		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
 		ms.StoreMessageInfo(mi)
 	}
@@ -161,7 +272,7 @@ func (x *ApplyBfgObjectMapStreamResponse_Entry) String() string {
 func (*ApplyBfgObjectMapStreamResponse_Entry) ProtoMessage() {}
 
 func (x *ApplyBfgObjectMapStreamResponse_Entry) ProtoReflect() protoreflect.Message {
-	mi := &file_cleanup_proto_msgTypes[2]
+	mi := &file_cleanup_proto_msgTypes[4]
 	if protoimpl.UnsafeEnabled && x != nil {
 		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
 		if ms.LoadMessageInfo() == nil {
@@ -224,20 +335,36 @@ var file_cleanup_proto_rawDesc = []byte{
 	0x54, 0x79, 0x70, 0x65, 0x52, 0x04, 0x74, 0x79, 0x70, 0x65, 0x12, 0x17, 0x0a, 0x07, 0x6f, 0x6c,
 	0x64, 0x5f, 0x6f, 0x69, 0x64, 0x18, 0x02, 0x20, 0x01, 0x28, 0x09, 0x52, 0x06, 0x6f, 0x6c, 0x64,
 	0x4f, 0x69, 0x64, 0x12, 0x17, 0x0a, 0x07, 0x6e, 0x65, 0x77, 0x5f, 0x6f, 0x69, 0x64, 0x18, 0x03,
-	0x20, 0x01, 0x28, 0x09, 0x52, 0x06, 0x6e, 0x65, 0x77, 0x4f, 0x69, 0x64, 0x32, 0x88, 0x01, 0x0a,
-	0x0e, 0x43, 0x6c, 0x65, 0x61, 0x6e, 0x75, 0x70, 0x53, 0x65, 0x72, 0x76, 0x69, 0x63, 0x65, 0x12,
-	0x76, 0x0a, 0x17, 0x41, 0x70, 0x70, 0x6c, 0x79, 0x42, 0x66, 0x67, 0x4f, 0x62, 0x6a, 0x65, 0x63,
-	0x74, 0x4d, 0x61, 0x70, 0x53, 0x74, 0x72, 0x65, 0x61, 0x6d, 0x12, 0x26, 0x2e, 0x67, 0x69, 0x74,
-	0x61, 0x6c, 0x79, 0x2e, 0x41, 0x70, 0x70, 0x6c, 0x79, 0x42, 0x66, 0x67, 0x4f, 0x62, 0x6a, 0x65,
-	0x63, 0x74, 0x4d, 0x61, 0x70, 0x53, 0x74, 0x72, 0x65, 0x61, 0x6d, 0x52, 0x65, 0x71, 0x75, 0x65,
-	0x73, 0x74, 0x1a, 0x27, 0x2e, 0x67, 0x69, 0x74, 0x61, 0x6c, 0x79, 0x2e, 0x41, 0x70, 0x70, 0x6c,
-	0x79, 0x42, 0x66, 0x67, 0x4f, 0x62, 0x6a, 0x65, 0x63, 0x74, 0x4d, 0x61, 0x70, 0x53, 0x74, 0x72,
-	0x65, 0x61, 0x6d, 0x52, 0x65, 0x73, 0x70, 0x6f, 0x6e, 0x73, 0x65, 0x22, 0x06, 0xfa, 0x97, 0x28,
-	0x02, 0x08, 0x01, 0x28, 0x01, 0x30, 0x01, 0x42, 0x34, 0x5a, 0x32, 0x67, 0x69, 0x74, 0x6c, 0x61,
-	0x62, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x67, 0x69, 0x74, 0x6c, 0x61, 0x62, 0x2d, 0x6f, 0x72, 0x67,
-	0x2f, 0x67, 0x69, 0x74, 0x61, 0x6c, 0x79, 0x2f, 0x76, 0x31, 0x36, 0x2f, 0x70, 0x72, 0x6f, 0x74,
-	0x6f, 0x2f, 0x67, 0x6f, 0x2f, 0x67, 0x69, 0x74, 0x61, 0x6c, 0x79, 0x70, 0x62, 0x62, 0x06, 0x70,
-	0x72, 0x6f, 0x74, 0x6f, 0x33,
+	0x20, 0x01, 0x28, 0x09, 0x52, 0x06, 0x6e, 0x65, 0x77, 0x4f, 0x69, 0x64, 0x22, 0x87, 0x01, 0x0a,
+	0x15, 0x52, 0x65, 0x77, 0x72, 0x69, 0x74, 0x65, 0x48, 0x69, 0x73, 0x74, 0x6f, 0x72, 0x79, 0x52,
+	0x65, 0x71, 0x75, 0x65, 0x73, 0x74, 0x12, 0x38, 0x0a, 0x0a, 0x72, 0x65, 0x70, 0x6f, 0x73, 0x69,
+	0x74, 0x6f, 0x72, 0x79, 0x18, 0x01, 0x20, 0x01, 0x28, 0x0b, 0x32, 0x12, 0x2e, 0x67, 0x69, 0x74,
+	0x61, 0x6c, 0x79, 0x2e, 0x52, 0x65, 0x70, 0x6f, 0x73, 0x69, 0x74, 0x6f, 0x72, 0x79, 0x42, 0x04,
+	0x98, 0xc6, 0x2c, 0x01, 0x52, 0x0a, 0x72, 0x65, 0x70, 0x6f, 0x73, 0x69, 0x74, 0x6f, 0x72, 0x79,
+	0x12, 0x14, 0x0a, 0x05, 0x62, 0x6c, 0x6f, 0x62, 0x73, 0x18, 0x02, 0x20, 0x03, 0x28, 0x09, 0x52,
+	0x05, 0x62, 0x6c, 0x6f, 0x62, 0x73, 0x12, 0x1e, 0x0a, 0x0a, 0x72, 0x65, 0x64, 0x61, 0x63, 0x74,
+	0x69, 0x6f, 0x6e, 0x73, 0x18, 0x03, 0x20, 0x03, 0x28, 0x0c, 0x52, 0x0a, 0x72, 0x65, 0x64, 0x61,
+	0x63, 0x74, 0x69, 0x6f, 0x6e, 0x73, 0x22, 0x18, 0x0a, 0x16, 0x52, 0x65, 0x77, 0x72, 0x69, 0x74,
+	0x65, 0x48, 0x69, 0x73, 0x74, 0x6f, 0x72, 0x79, 0x52, 0x65, 0x73, 0x70, 0x6f, 0x6e, 0x73, 0x65,
+	0x32, 0xe3, 0x01, 0x0a, 0x0e, 0x43, 0x6c, 0x65, 0x61, 0x6e, 0x75, 0x70, 0x53, 0x65, 0x72, 0x76,
+	0x69, 0x63, 0x65, 0x12, 0x76, 0x0a, 0x17, 0x41, 0x70, 0x70, 0x6c, 0x79, 0x42, 0x66, 0x67, 0x4f,
+	0x62, 0x6a, 0x65, 0x63, 0x74, 0x4d, 0x61, 0x70, 0x53, 0x74, 0x72, 0x65, 0x61, 0x6d, 0x12, 0x26,
+	0x2e, 0x67, 0x69, 0x74, 0x61, 0x6c, 0x79, 0x2e, 0x41, 0x70, 0x70, 0x6c, 0x79, 0x42, 0x66, 0x67,
+	0x4f, 0x62, 0x6a, 0x65, 0x63, 0x74, 0x4d, 0x61, 0x70, 0x53, 0x74, 0x72, 0x65, 0x61, 0x6d, 0x52,
+	0x65, 0x71, 0x75, 0x65, 0x73, 0x74, 0x1a, 0x27, 0x2e, 0x67, 0x69, 0x74, 0x61, 0x6c, 0x79, 0x2e,
+	0x41, 0x70, 0x70, 0x6c, 0x79, 0x42, 0x66, 0x67, 0x4f, 0x62, 0x6a, 0x65, 0x63, 0x74, 0x4d, 0x61,
+	0x70, 0x53, 0x74, 0x72, 0x65, 0x61, 0x6d, 0x52, 0x65, 0x73, 0x70, 0x6f, 0x6e, 0x73, 0x65, 0x22,
+	0x06, 0xfa, 0x97, 0x28, 0x02, 0x08, 0x01, 0x28, 0x01, 0x30, 0x01, 0x12, 0x59, 0x0a, 0x0e, 0x52,
+	0x65, 0x77, 0x72, 0x69, 0x74, 0x65, 0x48, 0x69, 0x73, 0x74, 0x6f, 0x72, 0x79, 0x12, 0x1d, 0x2e,
+	0x67, 0x69, 0x74, 0x61, 0x6c, 0x79, 0x2e, 0x52, 0x65, 0x77, 0x72, 0x69, 0x74, 0x65, 0x48, 0x69,
+	0x73, 0x74, 0x6f, 0x72, 0x79, 0x52, 0x65, 0x71, 0x75, 0x65, 0x73, 0x74, 0x1a, 0x1e, 0x2e, 0x67,
+	0x69, 0x74, 0x61, 0x6c, 0x79, 0x2e, 0x52, 0x65, 0x77, 0x72, 0x69, 0x74, 0x65, 0x48, 0x69, 0x73,
+	0x74, 0x6f, 0x72, 0x79, 0x52, 0x65, 0x73, 0x70, 0x6f, 0x6e, 0x73, 0x65, 0x22, 0x06, 0xfa, 0x97,
+	0x28, 0x02, 0x08, 0x01, 0x28, 0x01, 0x42, 0x34, 0x5a, 0x32, 0x67, 0x69, 0x74, 0x6c, 0x61, 0x62,
+	0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x67, 0x69, 0x74, 0x6c, 0x61, 0x62, 0x2d, 0x6f, 0x72, 0x67, 0x2f,
+	0x67, 0x69, 0x74, 0x61, 0x6c, 0x79, 0x2f, 0x76, 0x31, 0x36, 0x2f, 0x70, 0x72, 0x6f, 0x74, 0x6f,
+	0x2f, 0x67, 0x6f, 0x2f, 0x67, 0x69, 0x74, 0x61, 0x6c, 0x79, 0x70, 0x62, 0x62, 0x06, 0x70, 0x72,
+	0x6f, 0x74, 0x6f, 0x33,
 }
 
 var (
@@ -252,25 +379,30 @@ func file_cleanup_proto_rawDescGZIP() []byte {
 	return file_cleanup_proto_rawDescData
 }
 
-var file_cleanup_proto_msgTypes = make([]protoimpl.MessageInfo, 3)
+var file_cleanup_proto_msgTypes = make([]protoimpl.MessageInfo, 5)
 var file_cleanup_proto_goTypes = []interface{}{
 	(*ApplyBfgObjectMapStreamRequest)(nil),        // 0: gitaly.ApplyBfgObjectMapStreamRequest
 	(*ApplyBfgObjectMapStreamResponse)(nil),       // 1: gitaly.ApplyBfgObjectMapStreamResponse
-	(*ApplyBfgObjectMapStreamResponse_Entry)(nil), // 2: gitaly.ApplyBfgObjectMapStreamResponse.Entry
-	(*Repository)(nil),                            // 3: gitaly.Repository
-	(ObjectType)(0),                               // 4: gitaly.ObjectType
+	(*RewriteHistoryRequest)(nil),                 // 2: gitaly.RewriteHistoryRequest
+	(*RewriteHistoryResponse)(nil),                // 3: gitaly.RewriteHistoryResponse
+	(*ApplyBfgObjectMapStreamResponse_Entry)(nil), // 4: gitaly.ApplyBfgObjectMapStreamResponse.Entry
+	(*Repository)(nil),                            // 5: gitaly.Repository
+	(ObjectType)(0),                               // 6: gitaly.ObjectType
 }
 var file_cleanup_proto_depIdxs = []int32{
-	3, // 0: gitaly.ApplyBfgObjectMapStreamRequest.repository:type_name -> gitaly.Repository
-	2, // 1: gitaly.ApplyBfgObjectMapStreamResponse.entries:type_name -> gitaly.ApplyBfgObjectMapStreamResponse.Entry
-	4, // 2: gitaly.ApplyBfgObjectMapStreamResponse.Entry.type:type_name -> gitaly.ObjectType
-	0, // 3: gitaly.CleanupService.ApplyBfgObjectMapStream:input_type -> gitaly.ApplyBfgObjectMapStreamRequest
-	1, // 4: gitaly.CleanupService.ApplyBfgObjectMapStream:output_type -> gitaly.ApplyBfgObjectMapStreamResponse
-	4, // [4:5] is the sub-list for method output_type
-	3, // [3:4] is the sub-list for method input_type
-	3, // [3:3] is the sub-list for extension type_name
-	3, // [3:3] is the sub-list for extension extendee
-	0, // [0:3] is the sub-list for field type_name
+	5, // 0: gitaly.ApplyBfgObjectMapStreamRequest.repository:type_name -> gitaly.Repository
+	4, // 1: gitaly.ApplyBfgObjectMapStreamResponse.entries:type_name -> gitaly.ApplyBfgObjectMapStreamResponse.Entry
+	5, // 2: gitaly.RewriteHistoryRequest.repository:type_name -> gitaly.Repository
+	6, // 3: gitaly.ApplyBfgObjectMapStreamResponse.Entry.type:type_name -> gitaly.ObjectType
+	0, // 4: gitaly.CleanupService.ApplyBfgObjectMapStream:input_type -> gitaly.ApplyBfgObjectMapStreamRequest
+	2, // 5: gitaly.CleanupService.RewriteHistory:input_type -> gitaly.RewriteHistoryRequest
+	1, // 6: gitaly.CleanupService.ApplyBfgObjectMapStream:output_type -> gitaly.ApplyBfgObjectMapStreamResponse
+	3, // 7: gitaly.CleanupService.RewriteHistory:output_type -> gitaly.RewriteHistoryResponse
+	6, // [6:8] is the sub-list for method output_type
+	4, // [4:6] is the sub-list for method input_type
+	4, // [4:4] is the sub-list for extension type_name
+	4, // [4:4] is the sub-list for extension extendee
+	0, // [0:4] is the sub-list for field type_name
 }
 
 func init() { file_cleanup_proto_init() }
@@ -306,6 +438,30 @@ func file_cleanup_proto_init() {
 			}
 		}
 		file_cleanup_proto_msgTypes[2].Exporter = func(v interface{}, i int) interface{} {
+			switch v := v.(*RewriteHistoryRequest); i {
+			case 0:
+				return &v.state
+			case 1:
+				return &v.sizeCache
+			case 2:
+				return &v.unknownFields
+			default:
+				return nil
+			}
+		}
+		file_cleanup_proto_msgTypes[3].Exporter = func(v interface{}, i int) interface{} {
+			switch v := v.(*RewriteHistoryResponse); i {
+			case 0:
+				return &v.state
+			case 1:
+				return &v.sizeCache
+			case 2:
+				return &v.unknownFields
+			default:
+				return nil
+			}
+		}
+		file_cleanup_proto_msgTypes[4].Exporter = func(v interface{}, i int) interface{} {
 			switch v := v.(*ApplyBfgObjectMapStreamResponse_Entry); i {
 			case 0:
 				return &v.state
@@ -324,7 +480,7 @@ func file_cleanup_proto_init() {
 			GoPackagePath: reflect.TypeOf(x{}).PkgPath(),
 			RawDescriptor: file_cleanup_proto_rawDesc,
 			NumEnums:      0,
-			NumMessages:   3,
+			NumMessages:   5,
 			NumExtensions: 0,
 			NumServices:   1,
 		},
diff --git a/proto/go/gitalypb/cleanup_grpc.pb.go b/proto/go/gitalypb/cleanup_grpc.pb.go
index 4d42e293e..a9b1d2c62 100644
--- a/proto/go/gitalypb/cleanup_grpc.pb.go
+++ b/proto/go/gitalypb/cleanup_grpc.pb.go
@@ -24,6 +24,21 @@ const _ = grpc.SupportPackageIsVersion7
 type CleanupServiceClient interface {
 	// ApplyBfgObjectMapStream ...
 	ApplyBfgObjectMapStream(ctx context.Context, opts ...grpc.CallOption) (CleanupService_ApplyBfgObjectMapStreamClient, error)
+	// RewriteHistory redacts targeted strings and deletes requested blobs in a
+	// repository and updates all references to point to the rewritten commit
+	// history. This is useful for removing inadvertently pushed secrets from your
+	// repository and purging large blobs. This is a dangerous operation.
+	//
+	// The following known error conditions may happen:
+	//
+	// - `InvalidArgument` in the following situations:
+	//   - The provided repository can't be validated.
+	//   - The repository field is set on any request other than the initial one.
+	//   - Any request, including the initial one, does not contain either blobs to
+	//     remove or redaction patterns to redact.
+	//   - A blob object ID is invalid.
+	//   - A redaction pattern contains a newline character.
+	RewriteHistory(ctx context.Context, opts ...grpc.CallOption) (CleanupService_RewriteHistoryClient, error)
 }
 
 type cleanupServiceClient struct {
@@ -65,12 +80,61 @@ func (x *cleanupServiceApplyBfgObjectMapStreamClient) Recv() (*ApplyBfgObjectMap
 	return m, nil
 }
 
+func (c *cleanupServiceClient) RewriteHistory(ctx context.Context, opts ...grpc.CallOption) (CleanupService_RewriteHistoryClient, error) {
+	stream, err := c.cc.NewStream(ctx, &CleanupService_ServiceDesc.Streams[1], "/gitaly.CleanupService/RewriteHistory", opts...)
+	if err != nil {
+		return nil, err
+	}
+	x := &cleanupServiceRewriteHistoryClient{stream}
+	return x, nil
+}
+
+type CleanupService_RewriteHistoryClient interface {
+	Send(*RewriteHistoryRequest) error
+	CloseAndRecv() (*RewriteHistoryResponse, error)
+	grpc.ClientStream
+}
+
+type cleanupServiceRewriteHistoryClient struct {
+	grpc.ClientStream
+}
+
+func (x *cleanupServiceRewriteHistoryClient) Send(m *RewriteHistoryRequest) error {
+	return x.ClientStream.SendMsg(m)
+}
+
+func (x *cleanupServiceRewriteHistoryClient) CloseAndRecv() (*RewriteHistoryResponse, error) {
+	if err := x.ClientStream.CloseSend(); err != nil {
+		return nil, err
+	}
+	m := new(RewriteHistoryResponse)
+	if err := x.ClientStream.RecvMsg(m); err != nil {
+		return nil, err
+	}
+	return m, nil
+}
+
 // CleanupServiceServer is the server API for CleanupService service.
 // All implementations must embed UnimplementedCleanupServiceServer
 // for forward compatibility
 type CleanupServiceServer interface {
 	// ApplyBfgObjectMapStream ...
 	ApplyBfgObjectMapStream(CleanupService_ApplyBfgObjectMapStreamServer) error
+	// RewriteHistory redacts targeted strings and deletes requested blobs in a
+	// repository and updates all references to point to the rewritten commit
+	// history. This is useful for removing inadvertently pushed secrets from your
+	// repository and purging large blobs. This is a dangerous operation.
+	//
+	// The following known error conditions may happen:
+	//
+	// - `InvalidArgument` in the following situations:
+	//   - The provided repository can't be validated.
+	//   - The repository field is set on any request other than the initial one.
+	//   - Any request, including the initial one, does not contain either blobs to
+	//     remove or redaction patterns to redact.
+	//   - A blob object ID is invalid.
+	//   - A redaction pattern contains a newline character.
+	RewriteHistory(CleanupService_RewriteHistoryServer) error
 	mustEmbedUnimplementedCleanupServiceServer()
 }
 
@@ -81,6 +145,9 @@ type UnimplementedCleanupServiceServer struct {
 func (UnimplementedCleanupServiceServer) ApplyBfgObjectMapStream(CleanupService_ApplyBfgObjectMapStreamServer) error {
 	return status.Errorf(codes.Unimplemented, "method ApplyBfgObjectMapStream not implemented")
 }
+func (UnimplementedCleanupServiceServer) RewriteHistory(CleanupService_RewriteHistoryServer) error {
+	return status.Errorf(codes.Unimplemented, "method RewriteHistory not implemented")
+}
 func (UnimplementedCleanupServiceServer) mustEmbedUnimplementedCleanupServiceServer() {}
 
 // UnsafeCleanupServiceServer may be embedded to opt out of forward compatibility for this service.
@@ -120,6 +187,32 @@ func (x *cleanupServiceApplyBfgObjectMapStreamServer) Recv() (*ApplyBfgObjectMap
 	return m, nil
 }
 
+func _CleanupService_RewriteHistory_Handler(srv interface{}, stream grpc.ServerStream) error {
+	return srv.(CleanupServiceServer).RewriteHistory(&cleanupServiceRewriteHistoryServer{stream})
+}
+
+type CleanupService_RewriteHistoryServer interface {
+	SendAndClose(*RewriteHistoryResponse) error
+	Recv() (*RewriteHistoryRequest, error)
+	grpc.ServerStream
+}
+
+type cleanupServiceRewriteHistoryServer struct {
+	grpc.ServerStream
+}
+
+func (x *cleanupServiceRewriteHistoryServer) SendAndClose(m *RewriteHistoryResponse) error {
+	return x.ServerStream.SendMsg(m)
+}
+
+func (x *cleanupServiceRewriteHistoryServer) Recv() (*RewriteHistoryRequest, error) {
+	m := new(RewriteHistoryRequest)
+	if err := x.ServerStream.RecvMsg(m); err != nil {
+		return nil, err
+	}
+	return m, nil
+}
+
 // CleanupService_ServiceDesc is the grpc.ServiceDesc for CleanupService service.
 // It's only intended for direct use with grpc.RegisterService,
 // and not to be introspected or modified (even as a copy)
@@ -134,6 +227,11 @@ var CleanupService_ServiceDesc = grpc.ServiceDesc{
 			ServerStreams: true,
 			ClientStreams: true,
 		},
+		{
+			StreamName:    "RewriteHistory",
+			Handler:       _CleanupService_RewriteHistory_Handler,
+			ClientStreams: true,
+		},
 	},
 	Metadata: "cleanup.proto",
 }