ThothII/tools/tht/internal/authprojection/projection_linux.go

//go:build linux

package authprojection

import (
	"context"
	"crypto/rand"
	"encoding/hex"
	"errors"
	"path/filepath"
	"sync"
	"syscall"
	"time"

	"golang.org/x/sys/unix"
)

const maximumDirectoryEntries = 16

type testHooks struct {
	beforeFlock         func(int)
	beforeStageWrite    func() error
	beforeStageFsync    func() error
	beforeStageRename   func() error
	beforeCurrentRename func() error
	beforeFinalVerify   func() error
	beforeRetention     func() error
}

var hookState struct {
	sync.Mutex
	hooks testHooks
}

func setTestHooksForTest(hooks testHooks) func() {
	hookState.Lock()
	previous := hookState.hooks
	hookState.hooks = hooks
	hookState.Unlock()
	return func() {
		hookState.Lock()
		hookState.hooks = previous
		hookState.Unlock()
	}
}

func hook(selectHook func(testHooks) func() error) error {
	hookState.Lock()
	callback := selectHook(hookState.hooks)
	hookState.Unlock()
	if callback != nil && callback() != nil {
		return ErrIntegrity
	}
	return nil
}

func rendezvousBeforeFlock(root int) {
	hookState.Lock()
	callback := hookState.hooks.beforeFlock
	hookState.Unlock()
	if callback != nil {
		callback(root)
	}
}

func Inspect(spec Spec) (Status, error) {
	root, err := openRoot(spec)
	if err != nil {
		return Status{}, err
	}
	defer unix.Close(root)
	return inspectFD(root, spec)
}

func Begin(spec Spec, before *Snapshot, requireReadyMatch bool) (*Transaction, error) {
	return BeginContext(context.Background(), spec, before, requireReadyMatch)
}

func BeginContext(ctx context.Context, spec Spec, before *Snapshot, requireReadyMatch bool) (*Transaction, error) {
	if ctx == nil {
		return nil, ErrIntegrity
	}
	if err := ctx.Err(); err != nil {
		return nil, err
	}
	root, err := openRoot(spec)
	if err != nil {
		return nil, err
	}
	rendezvousBeforeFlock(root)
	if err := flockContext(ctx, root); err != nil {
		unix.Close(root)
		return nil, err
	}
	transaction := &Transaction{spec: spec, before: before, rootFD: root, lockFD: root}
	selector, selectorErr := readSelector(root, spec)
	switch {
	case selectorErr == nil && selector.State == "blocked":
		if requireReadyMatch || recoverTemporary(root, spec, selector) != nil {
			_ = transaction.Close()
			return nil, ErrIntegrity
		}
	case selectorErr == nil:
		if recoverCurrentTemporaries(root, spec) != nil || validateRootEntries(root, spec) != nil {
			_ = transaction.Close()
			return nil, ErrIntegrity
		}
		status, inspectErr := inspectSelectedGeneration(root, spec, selector)
		if inspectErr != nil {
			_ = transaction.Close()
			return nil, ErrIntegrity
		}
		if validateReadyGenerationHistory(root, spec, selector) != nil || retain(root, spec, selector) != nil {
			_ = transaction.Close()
			return nil, ErrIntegrity
		}
		status, inspectErr = inspectCapturedSelector(root, spec, selector)
		if inspectErr != nil {
			_ = transaction.Close()
			return nil, ErrIntegrity
		}
		transaction.prior = &status
		if requireReadyMatch && (before == nil || before.Generation != status.Snapshot.Generation) {
			_ = transaction.Close()
			return nil, ErrIntegrity
		}
	case currentExists(root):
		_ = transaction.Close()
		return nil, ErrIntegrity
	case requireReadyMatch || validateEmptyRootEntries(root, spec) != nil:
		_ = transaction.Close()
		return nil, ErrIntegrity
	case ensureGenerations(root, spec) != nil:
		_ = transaction.Close()
		return nil, ErrIntegrity
	}

	transaction.transactionID, err = randomID()
	if err != nil || writeSelector(root, spec, Selector{Version: SchemaVersion, State: "blocked", Transaction: transaction.transactionID}) != nil {
		_ = transaction.Close()
		return nil, ErrIntegrity
	}
	transaction.blocked = true
	return transaction, nil
}

func flockContext(ctx context.Context, descriptor int) error {
	for {
		if err := ctx.Err(); err != nil {
			return err
		}
		err := unix.Flock(descriptor, unix.LOCK_EX|unix.LOCK_NB)
		if err == nil {
			return nil
		}
		if !errors.Is(err, unix.EWOULDBLOCK) {
			return ErrIntegrity
		}
		timer := time.NewTimer(10 * time.Millisecond)
		select {
		case <-ctx.Done():
			if !timer.Stop() {
				<-timer.C
			}
			return ctx.Err()
		case <-timer.C:
		}
	}
}

func (transaction *Transaction) Commit(after Snapshot) (Status, error) {
	if transaction == nil || transaction.closed || !transaction.blocked || validateSnapshot(after) != nil {
		return Status{}, ErrIntegrity
	}
	if stageGeneration(transaction.rootFD, transaction.spec, transaction.transactionID, after) != nil {
		return Status{}, ErrIntegrity
	}
	if err := hook(func(h testHooks) func() error { return h.beforeFinalVerify }); err != nil {
		return Status{}, err
	}
	previous := make([]string, 0, retainedPredecessors)
	if transaction.prior != nil {
		previous = append(previous, transaction.prior.Selector.Generation)
		previous = append(previous, transaction.prior.Selector.PreviousGenerations...)
	}
	previous = uniqueGenerations(previous, after.Generation)
	if len(previous) > retainedPredecessors {
		previous = previous[:retainedPredecessors]
	}
	selector := Selector{Version: SchemaVersion, State: "ready", Transaction: transaction.transactionID, Generation: after.Generation, PreviousGenerations: previous}
	if writeSelector(transaction.rootFD, transaction.spec, selector) != nil {
		return Status{}, ErrIntegrity
	}
	status, err := inspectSelectedGeneration(transaction.rootFD, transaction.spec, selector)
	if err != nil || status.Snapshot.Generation != after.Generation {
		return Status{}, ErrIntegrity
	}
	transaction.blocked = false
	if err := hook(func(h testHooks) func() error { return h.beforeRetention }); err != nil {
		return Status{}, err
	}
	if retain(transaction.rootFD, transaction.spec, selector) != nil {
		return Status{}, ErrIntegrity
	}
	status, err = inspectFD(transaction.rootFD, transaction.spec)
	if err != nil || status.Snapshot.Generation != after.Generation {
		return Status{}, ErrIntegrity
	}
	return status, nil
}

func (transaction *Transaction) RestoreIfUnchanged(current Snapshot) error {
	if transaction == nil || transaction.closed || !transaction.blocked || transaction.before == nil || transaction.prior == nil || validateSnapshot(current) != nil || current.Generation != transaction.before.Generation {
		return ErrIntegrity
	}
	if writeSelector(transaction.rootFD, transaction.spec, transaction.prior.Selector) != nil {
		return ErrIntegrity
	}
	status, err := inspectFD(transaction.rootFD, transaction.spec)
	if err != nil || status.Snapshot.Generation != transaction.before.Generation {
		return ErrIntegrity
	}
	transaction.blocked = false
	return nil
}

func (transaction *Transaction) Close() error {
	if transaction == nil || transaction.closed {
		return nil
	}
	transaction.closed = true
	err := unix.Flock(transaction.lockFD, unix.LOCK_UN)
	if closeErr := unix.Close(transaction.rootFD); err == nil {
		err = closeErr
	}
	if err != nil {
		return ErrIntegrity
	}
	return nil
}

func openRoot(spec Spec) (int, error) {
	if !filepath.IsAbs(spec.RuntimeRoot) || filepath.Clean(spec.RuntimeRoot) != spec.RuntimeRoot {
		return -1, ErrIntegrity
	}
	fd, err := unix.Open(spec.RuntimeRoot, unix.O_RDONLY|unix.O_CLOEXEC|unix.O_DIRECTORY|unix.O_NOFOLLOW, 0)
	if err != nil {
		return -1, ErrIntegrity
	}
	if validateDirectoryFD(fd, spec) != nil {
		unix.Close(fd)
		return -1, ErrIntegrity
	}
	return fd, nil
}

func validDirectoryStat(stat unix.Stat_t, spec Spec) bool {
	return stat.Mode&unix.S_IFMT == unix.S_IFDIR && stat.Uid == spec.UID && stat.Gid == spec.GID && stat.Mode&0o7777 == runtimeDirectoryMode
}
func validFileStat(stat unix.Stat_t, spec Spec) bool {
	return stat.Mode&unix.S_IFMT == unix.S_IFREG && stat.Nlink == 1 && stat.Uid == spec.UID && stat.Gid == spec.GID && stat.Mode&0o7777 == runtimeFileMode
}
func sameStat(left, right unix.Stat_t) bool {
	return left.Dev == right.Dev && left.Ino == right.Ino && left.Mode == right.Mode && left.Nlink == right.Nlink && left.Uid == right.Uid && left.Gid == right.Gid && left.Size == right.Size && left.Mtim.Sec == right.Mtim.Sec && left.Mtim.Nsec == right.Mtim.Nsec && left.Ctim.Sec == right.Ctim.Sec && left.Ctim.Nsec == right.Ctim.Nsec
}
func validateDirectoryFD(fd int, spec Spec) error {
	var stat unix.Stat_t
	if unix.Fstat(fd, &stat) != nil || !validDirectoryStat(stat, spec) {
		return ErrIntegrity
	}
	return nil
}
func validateFileFD(fd int, spec Spec) error {
	var stat unix.Stat_t
	if unix.Fstat(fd, &stat) != nil || !validFileStat(stat, spec) {
		return ErrIntegrity
	}
	return nil
}
func statAt(directory int, name string) (unix.Stat_t, error) {
	var stat unix.Stat_t
	if unix.Fstatat(directory, name, &stat, unix.AT_SYMLINK_NOFOLLOW) != nil {
		return unix.Stat_t{}, ErrIntegrity
	}
	return stat, nil
}
func currentExists(root int) bool {
	var stat unix.Stat_t
	return unix.Fstatat(root, "CURRENT", &stat, unix.AT_SYMLINK_NOFOLLOW) == nil
}

func ensureGenerations(root int, spec Spec) error {
	var stat unix.Stat_t
	err := unix.Fstatat(root, "generations", &stat, unix.AT_SYMLINK_NOFOLLOW)
	if errors.Is(err, unix.ENOENT) {
		if unix.Mkdirat(root, "generations", runtimeDirectoryMode) != nil {
			return ErrIntegrity
		}
		fd, openErr := unix.Openat(root, "generations", unix.O_RDONLY|unix.O_CLOEXEC|unix.O_DIRECTORY|unix.O_NOFOLLOW, 0)
		if openErr != nil {
			return ErrIntegrity
		}
		defer unix.Close(fd)
		if unix.Fchown(fd, int(spec.UID), int(spec.GID)) != nil || unix.Fchmod(fd, runtimeDirectoryMode) != nil || validateDirectoryFD(fd, spec) != nil || unix.Fsync(fd) != nil || unix.Fsync(root) != nil {
			return ErrIntegrity
		}
		return nil
	}
	if err != nil || !validDirectoryStat(stat, spec) {
		return ErrIntegrity
	}
	return nil
}

func openDirectoryAt(parent int, name string, spec Spec) (int, error) {
	before, err := statAt(parent, name)
	if err != nil || !validDirectoryStat(before, spec) {
		return -1, ErrIntegrity
	}
	fd, err := unix.Openat(parent, name, unix.O_RDONLY|unix.O_CLOEXEC|unix.O_DIRECTORY|unix.O_NOFOLLOW, 0)
	if err != nil {
		return -1, ErrIntegrity
	}
	var opened unix.Stat_t
	if unix.Fstat(fd, &opened) != nil || !sameStat(before, opened) || !validDirectoryStat(opened, spec) {
		unix.Close(fd)
		return -1, ErrIntegrity
	}
	return fd, nil
}

func scanDirectoryNames(directory int, spec Spec) (map[string]bool, error) {
	var original unix.Stat_t
	if unix.Fstat(directory, &original) != nil || !validDirectoryStat(original, spec) {
		return nil, ErrIntegrity
	}
	copyFD, err := unix.Openat(directory, ".", unix.O_RDONLY|unix.O_CLOEXEC|unix.O_DIRECTORY|unix.O_NOFOLLOW, 0)
	if err != nil {
		return nil, ErrIntegrity
	}
	defer unix.Close(copyFD)
	var copied unix.Stat_t
	if unix.Fstat(copyFD, &copied) != nil || !sameStat(original, copied) || !validDirectoryStat(copied, spec) {
		return nil, ErrIntegrity
	}
	names := make(map[string]bool)
	buffer := make([]byte, 4096)
	for {
		read, err := syscall.ReadDirent(copyFD, buffer)
		if err != nil {
			return nil, ErrIntegrity
		}
		if read == 0 {
			return names, nil
		}
		_, count, parsed := syscall.ParseDirent(buffer[:read], maximumDirectoryEntries+1, nil)
		if count != len(parsed) || len(names)+len(parsed) > maximumDirectoryEntries {
			return nil, ErrIntegrity
		}
		for _, name := range parsed {
			if name == "" || name == "." || name == ".." || names[name] {
				return nil, ErrIntegrity
			}
			names[name] = true
		}
	}
}

func validateRootEntries(root int, spec Spec) error {
	names, err := scanDirectoryNames(root, spec)
	if err != nil || len(names) != 2 || !names["CURRENT"] || !names["generations"] {
		return ErrIntegrity
	}
	return nil
}
func validateEmptyRootEntries(root int, spec Spec) error {
	names, err := scanDirectoryNames(root, spec)
	if err != nil || len(names) != 0 {
		return ErrIntegrity
	}
	return nil
}

func inspectFD(root int, spec Spec) (Status, error) {
	if validateRootEntries(root, spec) != nil {
		return Status{}, ErrIntegrity
	}
	selector, err := readSelector(root, spec)
	if err != nil {
		return Status{}, err
	}
	return inspectCapturedSelector(root, spec, selector)
}
func inspectCapturedSelector(root int, spec Spec, selector Selector) (Status, error) {
	if selector.State == "blocked" {
		return Status{Selector: selector}, ErrBlocked
	}
	status, err := inspectSelectedGeneration(root, spec, selector)
	if err != nil {
		return Status{}, err
	}
	if validateReadyGenerationNamespace(root, spec, selector) != nil {
		return Status{}, ErrIntegrity
	}
	return status, nil
}

func inspectSelectedGeneration(root int, spec Spec, selector Selector) (Status, error) {
	if selector.State == "blocked" {
		return Status{Selector: selector}, ErrBlocked
	}
	snapshot, err := readGeneration(root, spec, selector.Generation)
	if err != nil {
		return Status{}, err
	}
	return Status{Selector: selector, Snapshot: snapshot}, nil
}

func validateReadyGenerationNamespace(root int, spec Spec, selector Selector) error {
	if validateReadyGenerationHistory(root, spec, selector) != nil {
		return ErrIntegrity
	}
	generations, err := openDirectoryAt(root, "generations", spec)
	if err != nil {
		return ErrIntegrity
	}
	defer unix.Close(generations)
	names, err := scanDirectoryNames(generations, spec)
	if err != nil {
		return ErrIntegrity
	}
	keep := map[string]bool{selector.Generation: true}
	for _, generation := range selector.PreviousGenerations {
		keep[generation] = true
	}
	if len(names) != len(keep) {
		return ErrIntegrity
	}
	for name := range names {
		if !validHex(name, 64) || !keep[name] {
			return ErrIntegrity
		}
	}
	return nil
}

func validateReadyGenerationHistory(root int, spec Spec, selector Selector) error {
	if selector.State != "ready" {
		return ErrIntegrity
	}
	for _, generation := range append([]string{selector.Generation}, selector.PreviousGenerations...) {
		if _, err := readGeneration(root, spec, generation); err != nil {
			return ErrIntegrity
		}
	}
	return nil
}

func readSelector(root int, spec Spec) (Selector, error) {
	data, err := readRegularAt(root, "CURRENT", spec, maximumSelectorBytes)
	if err != nil {
		return Selector{}, err
	}
	return decodeSelector(data)
}
func readGeneration(root int, spec Spec, generation string) (Snapshot, error) {
	if !validHex(generation, 64) {
		return Snapshot{}, ErrIntegrity
	}
	generations, err := openDirectoryAt(root, "generations", spec)
	if err != nil {
		return Snapshot{}, err
	}
	defer unix.Close(generations)
	directory, err := openDirectoryAt(generations, generation, spec)
	if err != nil {
		return Snapshot{}, err
	}
	defer unix.Close(directory)
	manifestData, err := readRegularAt(directory, "manifest.json", spec, maximumManifestBytes)
	if err != nil {
		return Snapshot{}, err
	}
	manifest, err := decodeManifest(manifestData)
	if err != nil {
		return Snapshot{}, err
	}
	if !expectedGenerationEntries(directory, spec, manifest.Mode) {
		return Snapshot{}, ErrIntegrity
	}
	auth, err := readRegularAt(directory, "auth.yaml", spec, maximumAuthBytes)
	if err != nil {
		return Snapshot{}, err
	}
	var users []byte
	if manifest.Mode == "local" {
		users, err = readRegularAt(directory, "users.yaml", spec, maximumUsersBytes)
		if err != nil {
			return Snapshot{}, err
		}
	}
	snapshot, err := NewSnapshot(manifest.Mode, auth, users)
	if err != nil || snapshot.Generation != generation || validateManifest(manifest, snapshot) != nil {
		return Snapshot{}, ErrIntegrity
	}
	return snapshot, nil
}
func expectedGenerationEntries(directory int, spec Spec, mode string) bool {
	names, err := scanDirectoryNames(directory, spec)
	if err != nil {
		return false
	}
	want := map[string]bool{"auth.yaml": true, "manifest.json": true}
	if mode == "local" {
		want["users.yaml"] = true
	}
	if len(names) != len(want) {
		return false
	}
	for name := range want {
		if !names[name] {
			return false
		}
	}
	return true
}

func readRegularAt(directory int, name string, spec Spec, limit int) ([]byte, error) {
	before, err := statAt(directory, name)
	if err != nil || !validFileStat(before, spec) {
		return nil, ErrIntegrity
	}
	fd, err := unix.Openat(directory, name, unix.O_RDONLY|unix.O_CLOEXEC|unix.O_NOFOLLOW|unix.O_NONBLOCK, 0)
	if err != nil {
		return nil, ErrIntegrity
	}
	defer unix.Close(fd)
	var opened unix.Stat_t
	if unix.Fstat(fd, &opened) != nil || !sameStat(before, opened) || !validFileStat(opened, spec) {
		return nil, ErrIntegrity
	}
	data, err := readBounded(fd, limit)
	if err != nil {
		return nil, ErrIntegrity
	}
	var after unix.Stat_t
	namedAfter, statErr := statAt(directory, name)
	if unix.Fstat(fd, &after) != nil || statErr != nil || !sameStat(opened, after) || !sameStat(before, namedAfter) || !validFileStat(after, spec) {
		return nil, ErrIntegrity
	}
	return data, nil
}
func readBounded(fd, limit int) ([]byte, error) {
	data, buffer := make([]byte, 0, limit), make([]byte, 32*1024)
	for {
		read, err := unix.Read(fd, buffer)
		if read > 0 {
			if len(data)+read > limit {
				return nil, ErrIntegrity
			}
			data = append(data, buffer[:read]...)
		}
		if err == nil {
			if read == 0 {
				return data, nil
			}
			continue
		}
		if errors.Is(err, unix.EINTR) {
			continue
		}
		return nil, ErrIntegrity
	}
}

func writeSelector(root int, spec Spec, selector Selector) error {
	data, err := encodeSelector(selector)
	if err != nil {
		return ErrIntegrity
	}
	name := ".current-" + selector.Transaction + ".tmp"
	if writeRegularAt(root, name, spec, data) != nil {
		return ErrIntegrity
	}
	if err := hook(func(h testHooks) func() error { return h.beforeCurrentRename }); err != nil {
		_ = unix.Unlinkat(root, name, 0)
		return err
	}
	if unix.Renameat(root, name, root, "CURRENT") != nil || unix.Fsync(root) != nil {
		return ErrIntegrity
	}
	return nil
}
func writeRegularAt(directory int, name string, spec Spec, data []byte) error {
	fd, err := unix.Openat(directory, name, unix.O_WRONLY|unix.O_CREAT|unix.O_EXCL|unix.O_CLOEXEC|unix.O_NOFOLLOW, runtimeFileMode)
	if err != nil {
		return ErrIntegrity
	}
	defer unix.Close(fd)
	if unix.Fchown(fd, int(spec.UID), int(spec.GID)) != nil || unix.Fchmod(fd, runtimeFileMode) != nil || validateFileFD(fd, spec) != nil || writeAll(fd, data) != nil || unix.Fsync(fd) != nil || validateFileFD(fd, spec) != nil {
		return ErrIntegrity
	}
	return nil
}
func writeAll(fd int, data []byte) error {
	for len(data) > 0 {
		written, err := unix.Write(fd, data)
		if err != nil {
			if errors.Is(err, unix.EINTR) {
				continue
			}
			return ErrIntegrity
		}
		if written == 0 {
			return ErrIntegrity
		}
		data = data[written:]
	}
	return nil
}

func stageGeneration(root int, spec Spec, transactionID string, snapshot Snapshot) error {
	generations, err := openDirectoryAt(root, "generations", spec)
	if err != nil {
		return err
	}
	defer unix.Close(generations)
	var existing unix.Stat_t
	if err := unix.Fstatat(generations, snapshot.Generation, &existing, unix.AT_SYMLINK_NOFOLLOW); err == nil {
		if found, readErr := readGeneration(root, spec, snapshot.Generation); readErr == nil && found.Generation == snapshot.Generation {
			return nil
		}
		if !currentMatchesBlockedTransaction(root, spec, transactionID) || removeConfinedDirectory(generations, snapshot.Generation, spec, false) != nil {
			return ErrIntegrity
		}
	} else if !errors.Is(err, unix.ENOENT) {
		return ErrIntegrity
	}
	stageName := ".stage-" + transactionID + "-" + snapshot.Generation
	if unix.Mkdirat(generations, stageName, runtimeDirectoryMode) != nil {
		return ErrIntegrity
	}
	stage, err := unix.Openat(generations, stageName, unix.O_RDONLY|unix.O_CLOEXEC|unix.O_DIRECTORY|unix.O_NOFOLLOW, 0)
	if err != nil {
		return ErrIntegrity
	}
	defer unix.Close(stage)
	if unix.Fchown(stage, int(spec.UID), int(spec.GID)) != nil || unix.Fchmod(stage, runtimeDirectoryMode) != nil || validateDirectoryFD(stage, spec) != nil || unix.Fsync(stage) != nil || unix.Fsync(generations) != nil {
		return ErrIntegrity
	}
	var namedStage, openedStage unix.Stat_t
	if unix.Fstatat(generations, stageName, &namedStage, unix.AT_SYMLINK_NOFOLLOW) != nil || unix.Fstat(stage, &openedStage) != nil || !sameStat(namedStage, openedStage) || !validDirectoryStat(namedStage, spec) {
		return ErrIntegrity
	}
	manifest, err := newManifest(snapshot)
	if err != nil {
		return ErrIntegrity
	}
	manifestData, err := encodeManifest(manifest)
	if err != nil {
		return ErrIntegrity
	}
	if err := hook(func(h testHooks) func() error { return h.beforeStageWrite }); err != nil {
		return err
	}
	if writeRegularAt(stage, "auth.yaml", spec, snapshot.Auth) != nil || (snapshot.Mode == "local" && writeRegularAt(stage, "users.yaml", spec, snapshot.Users) != nil) || writeRegularAt(stage, "manifest.json", spec, manifestData) != nil {
		return ErrIntegrity
	}
	if err := hook(func(h testHooks) func() error { return h.beforeStageFsync }); err != nil {
		return err
	}
	if unix.Fsync(stage) != nil {
		return ErrIntegrity
	}
	if err := hook(func(h testHooks) func() error { return h.beforeStageRename }); err != nil {
		return err
	}
	if unix.Renameat(generations, stageName, generations, snapshot.Generation) != nil || unix.Fsync(generations) != nil {
		return ErrIntegrity
	}
	verified, err := readGeneration(root, spec, snapshot.Generation)
	if err != nil || verified.Generation != snapshot.Generation {
		return ErrIntegrity
	}
	return nil
}

func retain(root int, spec Spec, selector Selector) error {
	generations, err := openDirectoryAt(root, "generations", spec)
	if err != nil {
		return err
	}
	defer unix.Close(generations)
	names, err := scanDirectoryNames(generations, spec)
	if err != nil {
		return ErrIntegrity
	}
	keep := map[string]bool{selector.Generation: true}
	for _, generation := range selector.PreviousGenerations {
		keep[generation] = true
	}
	for name := range names {
		if !validHex(name, 64) {
			return ErrIntegrity
		}
		if keep[name] {
			if _, err := readGeneration(root, spec, name); err != nil {
				return ErrIntegrity
			}
			continue
		}
		if _, err := readGeneration(root, spec, name); err != nil {
			return ErrIntegrity
		}
		if removeConfinedDirectory(generations, name, spec, false) != nil {
			return ErrIntegrity
		}
	}
	if unix.Fsync(generations) != nil || unix.Fsync(root) != nil {
		return ErrIntegrity
	}
	return nil
}

func recoverTemporary(root int, spec Spec, blocked Selector) error {
	if blocked.State != "blocked" || !validHex(blocked.Transaction, 32) {
		return ErrIntegrity
	}
	generations, err := openDirectoryAt(root, "generations", spec)
	if err != nil {
		return err
	}
	defer unix.Close(generations)
	names, err := scanDirectoryNames(generations, spec)
	if err != nil {
		return ErrIntegrity
	}
	for name := range names {
		if validHex(name, 64) {
			directory, openErr := openDirectoryAt(generations, name, spec)
			if openErr != nil || unix.Close(directory) != nil {
				return ErrIntegrity
			}
			continue
		}
		generation, ok := stageGenerationName(name, blocked.Transaction)
		if !ok || !validHex(generation, 64) || removeConfinedDirectory(generations, name, spec, true) != nil {
			return ErrIntegrity
		}
	}
	if unix.Fsync(generations) != nil {
		return ErrIntegrity
	}
	return recoverCurrentTemporaries(root, spec)
}

func recoverCurrentTemporaries(root int, spec Spec) error {
	rootNames, err := scanDirectoryNames(root, spec)
	if err != nil || !rootNames["CURRENT"] || !rootNames["generations"] {
		return ErrIntegrity
	}
	for name := range rootNames {
		if name == "CURRENT" || name == "generations" {
			continue
		}
		transactionID, ok := currentTemporaryName(name)
		if !ok {
			return ErrIntegrity
		}
		data, readErr := readRegularAt(root, name, spec, maximumSelectorBytes)
		if readErr != nil {
			return ErrIntegrity
		}
		selector, decodeErr := decodeSelector(data)
		if decodeErr != nil || selector.Transaction != transactionID || unix.Unlinkat(root, name, 0) != nil {
			return ErrIntegrity
		}
	}
	if unix.Fsync(root) != nil {
		return ErrIntegrity
	}
	return nil
}

func currentMatchesBlockedTransaction(root int, spec Spec, transactionID string) bool {
	selector, err := readSelector(root, spec)
	return err == nil && selector.State == "blocked" && selector.Transaction == transactionID
}
func stageGenerationName(name, transactionID string) (string, bool) {
	prefix := ".stage-" + transactionID + "-"
	if len(name) != len(prefix)+64 || name[:len(prefix)] != prefix {
		return "", false
	}
	return name[len(prefix):], true
}
func currentTemporaryName(name string) (string, bool) {
	const prefix, suffix = ".current-", ".tmp"
	if len(name) != len(prefix)+32+len(suffix) || name[:len(prefix)] != prefix || name[len(name)-len(suffix):] != suffix {
		return "", false
	}
	id := name[len(prefix) : len(prefix)+32]
	return id, validHex(id, 32)
}

func removeConfinedDirectory(parent int, name string, spec Spec, partial bool) error {
	directory, err := openDirectoryAt(parent, name, spec)
	if err != nil {
		return ErrIntegrity
	}
	defer unix.Close(directory)
	names, err := scanDirectoryNames(directory, spec)
	if err != nil || len(names) > 3 {
		return ErrIntegrity
	}
	allowed := map[string]bool{"auth.yaml": true, "users.yaml": true, "manifest.json": true}
	if !partial && !completeGenerationNames(names) {
		return ErrIntegrity
	}
	for entry := range names {
		if !allowed[entry] || verifyRegularAt(directory, entry, spec) != nil || unix.Unlinkat(directory, entry, 0) != nil {
			return ErrIntegrity
		}
	}
	if unix.Fsync(directory) != nil || unix.Unlinkat(parent, name, unix.AT_REMOVEDIR) != nil || unix.Fsync(parent) != nil {
		return ErrIntegrity
	}
	return nil
}
func completeGenerationNames(names map[string]bool) bool {
	if len(names) == 2 {
		return names["auth.yaml"] && names["manifest.json"]
	}
	return len(names) == 3 && names["auth.yaml"] && names["users.yaml"] && names["manifest.json"]
}
func verifyRegularAt(directory int, name string, spec Spec) error {
	before, err := statAt(directory, name)
	if err != nil || !validFileStat(before, spec) {
		return ErrIntegrity
	}
	fd, err := unix.Openat(directory, name, unix.O_RDONLY|unix.O_CLOEXEC|unix.O_NOFOLLOW|unix.O_NONBLOCK, 0)
	if err != nil {
		return ErrIntegrity
	}
	defer unix.Close(fd)
	var after unix.Stat_t
	if unix.Fstat(fd, &after) != nil || !sameStat(before, after) || !validFileStat(after, spec) {
		return ErrIntegrity
	}
	return nil
}
func uniqueGenerations(values []string, current string) []string {
	seen := map[string]bool{current: true}
	result := make([]string, 0, retainedPredecessors)
	for _, value := range values {
		if validHex(value, 64) && !seen[value] {
			seen[value] = true
			result = append(result, value)
		}
	}
	return result
}
func randomID() (string, error) {
	value := make([]byte, 16)
	if _, err := rand.Read(value); err != nil {
		return "", ErrIntegrity
	}
	return hex.EncodeToString(value), nil
}