the directory lock is the kernel's, not a pid we believe

flock(2) on the lock file's descriptor replaces "write my pid, and
decide whether the pid in the file is still alive". The kernel drops
the lock when the process ends, however it ends, so there is no stale
krino lock to detect and no takeover to race over.

What that fixes:

- Two runs that both judged a lock stale could remove and recreate it
  and both believe they held it. Remove-then-create cannot be made
  atomic; there is nothing to make atomic now. Pinned by a test with
  eight callers over twenty rounds.
- A pid reused after a crash made the lock live for ever, and the
  message named neither the file nor the pid, so there was nothing to
  act on. The message now names both.
- Signal(0) reads EPERM as "not running", so a lock held by another
  user was taken over. There is no such judgement left to get wrong.

A run that waits for a held lock now says so first. Waiting is what
the spec asks for, but the wait has no timeout, and in silence it is
indistinguishable from a hang - I spent two minutes on one myself
today, waiting on a lock the window was holding.

Tests that faked a held lock by writing a file now hold a real one.

2 files changed, 208 insertions, 100 deletions

diff --git a/internal/lock/lock.go b/internal/lock/lock.go
index 76a2b71..c59aab0 100644
--- a/internal/lock/lock.go
+++ b/internal/lock/lock.go
@@ -1,8 +1,21 @@
 // SPDX-License-Identifier: GPL-3.0-or-later
 
 // Package lock keeps two krino runs from acting on the same directory at
-// once: Acquire takes an exclusive lock file, waiting or failing depending
-// on the caller, and Release lets it go. See docs/design.md §3, §11.
+// once: Acquire takes an exclusive lock on a lock file, waiting or failing
+// depending on the caller, and Release lets it go. See docs/design.md §3,
+// §11.
+//
+// The lock is the kernel's, taken with flock(2) on an open file descriptor,
+// not a pid written into a file and believed. The difference is what
+// happens when a run dies: the kernel drops the lock when the last
+// descriptor closes, however the process ended, so there is no such thing
+// as a stale krino lock and nothing has to guess whether a recorded pid is
+// still the run that wrote it. A pid whose number has since been reused
+// would make that guess wrong for ever, and two runs reaching the same
+// "this one is stale" conclusion at the same moment could both take the
+// lock over.
+//
+// The file itself still names the holder, for a human reading it.
 package lock
 
 import (
@@ -10,7 +23,6 @@ import (
 	"errors"
 	"fmt"
 	"io/fs"
-	"math"
 	"os"
 	"path/filepath"
 	"strconv"
@@ -19,45 +31,32 @@ import (
 	"time"
 )
 
-// ErrHeld is returned by Acquire when the lock is already held by a running
-// krino and wait is false.
+// ErrHeld is returned by Acquire when another krino holds the lock and wait
+// is false.
 var ErrHeld = errors.New("another krino is working in this directory")
 
 // pollInterval is how often a waiting Acquire retries the lock.
 const pollInterval = 100 * time.Millisecond
 
-// Lock is a held lock file. The zero Lock holds nothing; Release on it, or
-// on a nil *Lock, is a no-op.
+// Lock is a held lock: the open descriptor whose flock the kernel is
+// keeping for us. The zero Lock holds nothing; Release on it, or on a nil
+// *Lock, is a no-op.
 type Lock struct {
 	// Path is where the lock file lives.
 	Path string
 
-	// TookOverStale reports whether Acquire found a lock naming a pid that
-	// was no longer running, and took the lock over. The caller should
-	// mention this rather than stay silent about it.
-	TookOverStale bool
-
-	held bool
+	f *os.File
 }
 
-// Acquire takes the lock at path: an O_CREATE|O_EXCL file naming the
-// holder's pid and start time, so a human can see who holds it. Parent
-// directories are created as needed.
-//
-// When wait is false, Acquire fails immediately with ErrHeld if the lock is
-// already held, so a cron job never piles up behind a stuck run. When wait
-// is true, Acquire polls every 100ms, with no fixed timeout - but it does
-// not poll forever regardless of ctx: a cancelled or expired ctx makes a
-// waiting Acquire return ctx.Err() promptly instead of ignoring it - a run
-// blocked waiting for a held lock must still notice Ctrl-C. ctx is not
-// consulted at all when wait is false or the lock is free on the first
-// try, so -y's non-waiting callers are unaffected.
+// Acquire takes the lock at path. Parent directories are created as needed.
 //
-// A lock naming a pid that is not running is stale — the machine may have
-// lost power mid-run. Acquire removes a stale lock and retries the O_EXCL
-// create once; if that retry also loses, another process has reached the
-// same conclusion first and Acquire treats the lock as held. A takeover is
-// reported via the returned Lock's TookOverStale field.
+// When wait is false, Acquire fails immediately with ErrHeld if another
+// process holds it, so a cron job never piles up behind a stuck run. When
+// wait is true, Acquire polls every 100ms, with no fixed timeout - but it
+// does not poll forever regardless of ctx: a cancelled or expired ctx makes
+// a waiting Acquire return ctx.Err() promptly, so a run blocked on a lock
+// still notices Ctrl-C. ctx is not consulted when wait is false or the lock
+// is free on the first try.
 func Acquire(ctx context.Context, path string, wait bool) (*Lock, error) {
 	for {
 		l, err := tryAcquire(path)
@@ -75,60 +74,83 @@ func Acquire(ctx context.Context, path string, wait bool) (*Lock, error) {
 	}
 }
 
-// tryAcquire makes one attempt at the lock: create it, or if it is held,
-// decide whether the holder is stale and take it over.
+// tryAcquire makes one attempt: open the lock file, take the kernel's lock
+// on it, and make sure the file we locked is still the one at path.
+//
+// That last check is the one subtlety. Release unlinks the file before
+// closing it, so a process that opened the file just beforehand can end up
+// holding a lock on an inode that no longer has a name, while another
+// process creates a fresh file at path and locks that. Comparing the
+// descriptor's identity with what path now names catches exactly that case,
+// and the retry then races for the new file like everyone else.
 func tryAcquire(path string) (*Lock, error) {
 	if err := os.MkdirAll(filepath.Dir(path), 0o755); err != nil {
 		return nil, fmt.Errorf("lock %s: %w", path, err)
 	}
-
-	if err := create(path); err == nil {
-		return &Lock{Path: path, held: true}, nil
-	} else if !errors.Is(err, fs.ErrExist) {
-		return nil, fmt.Errorf("lock %s: %w", path, err)
+	for {
+		f, err := os.OpenFile(path, os.O_CREATE|os.O_RDWR, 0o644)
+		if err != nil {
+			return nil, fmt.Errorf("lock %s: %w", path, err)
+		}
+		if err := syscall.Flock(int(f.Fd()), syscall.LOCK_EX|syscall.LOCK_NB); err != nil {
+			f.Close()
+			if errors.Is(err, syscall.EWOULDBLOCK) {
+				return nil, heldBy(path)
+			}
+			return nil, fmt.Errorf("lock %s: %w", path, err)
+		}
+		same, err := stillAtPath(f, path)
+		if err != nil {
+			f.Close()
+			return nil, fmt.Errorf("lock %s: %w", path, err)
+		}
+		if !same {
+			// The holder unlinked it between our open and our flock.
+			f.Close()
+			continue
+		}
+		if err := writeHolder(f); err != nil {
+			f.Close()
+			return nil, fmt.Errorf("lock %s: %w", path, err)
+		}
+		return &Lock{Path: path, f: f}, nil
 	}
+}
 
-	pid, ok := readHolderPid(path)
-	if !ok || running(pid) {
-		return nil, ErrHeld
+// stillAtPath reports whether f is the file path names now. A path that has
+// gone missing is not an error here: it means the previous holder unlinked
+// it, which the caller handles by retrying.
+func stillAtPath(f *os.File, path string) (bool, error) {
+	fi, err := f.Stat()
+	if err != nil {
+		return false, err
 	}
-
-	// Stale: the recorded pid is not running. Take the lock over by
-	// removing it and retrying the create once. If that retry also loses,
-	// another process beat us to the same conclusion — treat it as held.
-	os.Remove(path)
-	if err := create(path); err != nil {
-		if errors.Is(err, fs.ErrExist) {
-			return nil, ErrHeld
+	on, err := os.Stat(path)
+	if err != nil {
+		if errors.Is(err, fs.ErrNotExist) {
+			return false, nil
 		}
-		return nil, fmt.Errorf("lock %s: %w", path, err)
+		return false, err
 	}
-	return &Lock{Path: path, held: true, TookOverStale: true}, nil
+	return os.SameFile(fi, on), nil
 }
 
-// create makes path with O_CREATE|O_EXCL and writes the holder's pid and
-// start time into it. If the write or close fails after the file was
-// created, the file is removed so no half-written lock is left behind.
-func create(path string) error {
-	f, err := os.OpenFile(path, os.O_CREATE|os.O_EXCL|os.O_WRONLY, 0o644)
-	if err != nil {
+// writeHolder records who holds the lock, for a human who finds the file
+// and wants to know which process to look at. Nothing reads it back: the
+// kernel, not this text, is what keeps two runs apart.
+func writeHolder(f *os.File) error {
+	if err := f.Truncate(0); err != nil {
 		return err
 	}
-	_, werr := fmt.Fprintf(f, "pid %d\nstarted %s\n", os.Getpid(), time.Now().UTC().Format(time.RFC3339))
-	cerr := f.Close()
-	if werr != nil || cerr != nil {
-		os.Remove(path)
-		if werr != nil {
-			return werr
-		}
-		return cerr
+	if _, err := f.Seek(0, 0); err != nil {
+		return err
 	}
-	return nil
+	_, err := fmt.Fprintf(f, "pid %d\nstarted %s\n", os.Getpid(), time.Now().UTC().Format(time.RFC3339))
+	return err
 }
 
-// readHolderPid reads the pid recorded in the lock file at path. ok is
-// false when the file cannot be read or does not name a pid — in which
-// case the caller must not treat the lock as stale.
+// readHolderPid reads the pid recorded in the lock file at path, for the
+// message only. ok is false when the file cannot be read or names none.
 func readHolderPid(path string) (pid int, ok bool) {
 	b, err := os.ReadFile(path)
 	if err != nil {
@@ -155,29 +177,36 @@ func parsePid(s string) (int, bool) {
 	return n, true
 }
 
-// running reports whether pid names a process that is currently running.
-// A pid outside the kernel's 32-bit range names no process: kill(2) would
-// cut it to its low bits and ask about another one.
-func running(pid int) bool {
-	if pid <= 0 || pid > math.MaxInt32 {
-		return false
-	}
-	proc, err := os.FindProcess(pid)
-	if err != nil {
-		return false
+// heldBy is ErrHeld naming the file, so a user who wants to know what is
+// holding a directory has somewhere to look.
+func heldBy(path string) error {
+	if pid, ok := readHolderPid(path); ok {
+		return fmt.Errorf("%w (pid %d; lock %s)", ErrHeld, pid, path)
 	}
-	return proc.Signal(syscall.Signal(0)) == nil
+	return fmt.Errorf("%w (lock %s)", ErrHeld, path)
 }
 
-// Release removes the lock file. Release on a Lock that was never acquired
+// Release unlinks the lock file and closes the descriptor, which is what
+// drops the kernel's lock. Unlinking first means a process waiting on this
+// file sees it disappear and retries for the new one rather than holding a
+// lock on an inode with no name. Release on a Lock that was never acquired
 // (the zero Lock, a nil *Lock, or one already released) is harmless.
 func (l *Lock) Release() error {
-	if l == nil || !l.held {
+	if l == nil || l.f == nil {
 		return nil
 	}
-	l.held = false
-	if err := os.Remove(l.Path); err != nil && !errors.Is(err, fs.ErrNotExist) {
-		return fmt.Errorf("release lock %s: %w", l.Path, err)
+	f := l.f
+	l.f = nil
+	rmErr := os.Remove(l.Path)
+	if rmErr != nil && errors.Is(rmErr, fs.ErrNotExist) {
+		rmErr = nil
+	}
+	closeErr := f.Close()
+	if rmErr != nil {
+		return fmt.Errorf("release lock %s: %w", l.Path, rmErr)
+	}
+	if closeErr != nil {
+		return fmt.Errorf("release lock %s: %w", l.Path, closeErr)
 	}
 	return nil
 }
diff --git a/internal/lock/lock_test.go b/internal/lock/lock_test.go
index 04023aa..c756bb2 100644
--- a/internal/lock/lock_test.go
+++ b/internal/lock/lock_test.go
@@ -9,6 +9,7 @@ import (
 	"os"
 	"path/filepath"
 	"strings"
+	"sync"
 	"testing"
 	"time"
 )
@@ -106,32 +107,110 @@ func TestAcquireRespectsContextCancellation(t *testing.T) {
 	}
 }
 
-// TestStaleLockIsTakenOver: a lock naming a pid that is not running must not
-// wedge krino - a machine that lost power mid-run would need manual cleanup.
-func TestStaleLockIsTakenOver(t *testing.T) {
+// TestALockFileWithoutAHolderIsFree: a machine that lost power mid-run
+// leaves the lock file behind, but nothing holding it. The text in that
+// file is for a human; it must not wedge the next run, whatever it says.
+func TestALockFileWithoutAHolderIsFree(t *testing.T) {
 	path := filepath.Join(t.TempDir(), "dl.lock")
-	if err := os.WriteFile(path, []byte("pid 4294967000\nstarted 2020-01-01T00:00:00Z\n"), 0o644); err != nil {
+	if err := os.WriteFile(path, []byte("pid 1\nstarted 2020-01-01T00:00:00Z\n"), 0o644); err != nil {
 		t.Fatal(err)
 	}
 	l, err := Acquire(context.Background(), path, false)
 	if err != nil {
-		t.Fatalf("a stale lock blocked Acquire: %v", err)
+		t.Fatalf("a lock file nobody holds blocked Acquire: %v", err)
 	}
 	defer l.Release()
-	if !l.TookOverStale {
-		t.Error("the takeover was not reported to the caller")
+	if b, _ := os.ReadFile(path); !strings.Contains(string(b), fmt.Sprint(os.Getpid())) {
+		t.Errorf("the lock file still names the old holder: %q", b)
+	}
+}
+
+// TestALockDiesWithItsProcess: the kernel drops an flock when the last
+// descriptor closes, however the process ended. A holder that vanishes
+// without unlinking - a crash, a kill -9 - must leave the directory usable
+// at once. This is the reason the lock is the kernel's rather than a pid
+// written into a file and believed.
+func TestALockDiesWithItsProcess(t *testing.T) {
+	path := filepath.Join(t.TempDir(), "dl.lock")
+	l, err := Acquire(context.Background(), path, false)
+	if err != nil {
+		t.Fatal(err)
+	}
+	if _, err := Acquire(context.Background(), path, false); !errors.Is(err, ErrHeld) {
+		t.Fatalf("while held, Acquire err = %v, want ErrHeld", err)
+	}
+	// Close the descriptor without unlinking, as a crash would leave it.
+	if err := l.f.Close(); err != nil {
+		t.Fatal(err)
+	}
+	l.f = nil
+	if _, err := os.Stat(path); err != nil {
+		t.Fatalf("the lock file should still be there: %v", err)
+	}
+	second, err := Acquire(context.Background(), path, false)
+	if err != nil {
+		t.Fatalf("a lock file left by a dead holder still blocks Acquire: %v", err)
 	}
+	second.Release()
 }
 
-// TestRunningRejectsPidsBeyondTheKernelsRange: a pid wider than 32 bits in a
-// damaged lock file is cut to its low bits by kill(2), so without a range
-// check it names some other process - here this very one - and a stale lock
-// would never be taken over.
-func TestRunningRejectsPidsBeyondTheKernelsRange(t *testing.T) {
-	if running(os.Getpid() + 1<<32) {
-		t.Error("running(pid + 2^32) is true: the pid was truncated to this process")
+// TestOnlyOneAcquireWinsAtOnce: the promise is that a directory is locked
+// while krino works in it. Judging a lock stale and recreating it cannot be
+// made atomic, so two runs reaching that conclusion together could both
+// believe they held it; the kernel's lock has one winner by construction.
+func TestOnlyOneAcquireWinsAtOnce(t *testing.T) {
+	path := filepath.Join(t.TempDir(), "dl.lock")
+	for round := 0; round < 20; round++ {
+		const n = 8
+		start := make(chan struct{})
+		var mu sync.Mutex
+		var won []*Lock
+		var wg sync.WaitGroup
+		for i := 0; i < n; i++ {
+			wg.Add(1)
+			go func() {
+				defer wg.Done()
+				<-start
+				if l, err := Acquire(context.Background(), path, false); err == nil {
+					mu.Lock()
+					won = append(won, l)
+					mu.Unlock()
+				}
+			}()
+		}
+		close(start)
+		wg.Wait()
+		if len(won) != 1 {
+			t.Fatalf("round %d: %d callers hold the same lock at once, want 1", round, len(won))
+		}
+		for _, l := range won {
+			if err := l.Release(); err != nil {
+				t.Fatal(err)
+			}
+		}
+	}
+}
+
+// TestHeldErrorNamesTheLockAndHolder: "another krino is working in this
+// directory" leaves nothing to act on when the holder is a pid that was
+// reused after a crash - the lock is then live for ever as far as krino can
+// tell. The error must name the file to remove and the pid it blames.
+func TestHeldErrorNamesTheLockAndHolder(t *testing.T) {
+	path := filepath.Join(t.TempDir(), "dl.lock")
+	first, err := Acquire(context.Background(), path, false)
+	if err != nil {
+		t.Fatal(err)
+	}
+	defer first.Release()
+
+	_, err = Acquire(context.Background(), path, false)
+	if !errors.Is(err, ErrHeld) {
+		t.Fatalf("second Acquire err = %v, want ErrHeld", err)
+	}
+	if got := err.Error(); !strings.Contains(got, path) {
+		t.Errorf("the error does not name the lock file %q: %s", path, got)
 	}
-	if !running(os.Getpid()) {
-		t.Error("running(own pid) is false")
+	if got := err.Error(); !strings.Contains(got, fmt.Sprint(os.Getpid())) {
+		t.Errorf("the error does not name the holder's pid %d: %s", os.Getpid(), got)
 	}
 }