parsimony/internal/queue/pacer_test.go
tgiachi c853ae7e61 test(queue): cover a pacer slot given up while a later caller holds its own
- a caller that gives up must not release a slot when another caller reserved after it
- a delivery that did not get its slot is not counted in the run's stats
2026-11-10 12:55:26 +01:00

293 lines
7.9 KiB
Go

package queue
import (
"context"
"errors"
"math"
"sort"
"sync"
"testing"
"time"
)
// fakeTime is a clock and a sleep that never really sleeps. With advance set, a sleep moves the clock
// (a single caller); otherwise the clock stands still and the durations asked for are recorded
// (many callers reserving slots at the same instant).
type fakeTime struct {
mu sync.Mutex
t time.Time
advance bool
slept []time.Duration
err error // returned by sleep when set
}
func (f *fakeTime) now() time.Time {
f.mu.Lock()
defer f.mu.Unlock()
return f.t
}
func (f *fakeTime) move(d time.Duration) {
f.mu.Lock()
f.t = f.t.Add(d)
f.mu.Unlock()
}
func (f *fakeTime) sleep(ctx context.Context, d time.Duration) error {
f.mu.Lock()
defer f.mu.Unlock()
f.slept = append(f.slept, d)
if f.err != nil {
return f.err
}
if f.advance {
f.t = f.t.Add(d)
}
return nil
}
func (f *fakeTime) durations() []time.Duration {
f.mu.Lock()
defer f.mu.Unlock()
d := append([]time.Duration(nil), f.slept...)
sort.Slice(d, func(i, j int) bool { return d[i] < d[j] })
return d
}
func TestPacerSpacesSendsByTheInterval(t *testing.T) {
f := &fakeTime{t: t0, advance: true}
p := newPacer(10, f.now, f.sleep) // one slot every 100 ms
for i := 0; i < 4; i++ {
if err := p.Wait(context.Background()); err != nil {
t.Fatal(err)
}
if want := t0.Add(time.Duration(i) * 100 * time.Millisecond); !f.now().Equal(want) {
t.Fatalf("send %d starts at +%v, want +%v", i, f.now().Sub(t0), want.Sub(t0))
}
}
}
func TestPacerFirstSendDoesNotWait(t *testing.T) {
f := &fakeTime{t: t0, advance: true}
p := newPacer(1, f.now, f.sleep)
p.Wait(context.Background())
if len(f.slept) != 0 {
t.Fatalf("the first send waited: %v", f.slept)
}
}
func TestPacerAllowsNoBurstAfterAnIdlePeriod(t *testing.T) {
f := &fakeTime{t: t0, advance: true}
p := newPacer(10, f.now, f.sleep)
p.Wait(context.Background())
f.move(10 * time.Second) // idle: slots do not pile up
start := f.now()
p.Wait(context.Background())
p.Wait(context.Background())
if got := f.now().Sub(start); got != 100*time.Millisecond {
t.Fatalf("two sends after an idle period took %v, want exactly one interval", got)
}
}
func TestPacerSleepsOnlyWhatIsLeftOfTheInterval(t *testing.T) {
f := &fakeTime{t: t0, advance: true}
p := newPacer(10, f.now, f.sleep)
p.Wait(context.Background())
f.move(30 * time.Millisecond) // the send itself took 30 ms
p.Wait(context.Background())
if len(f.slept) != 1 || f.slept[0] != 70*time.Millisecond {
t.Fatalf("slept %v, want [70ms]", f.slept)
}
}
func TestPacerGivesConcurrentCallersDistinctSlots(t *testing.T) {
const n = 16
f := &fakeTime{t: t0} // the clock stands still: every caller reserves at the same instant
p := newPacer(4, f.now, f.sleep)
var wg sync.WaitGroup
for i := 0; i < n; i++ {
wg.Add(1)
go func() {
defer wg.Done()
if err := p.Wait(context.Background()); err != nil {
t.Error(err)
}
}()
}
wg.Wait()
got := f.durations() // the first caller does not sleep, so n-1 sleeps: 250ms, 500ms...
if len(got) != n-1 {
t.Fatalf("%d sleeps, want %d: %v", len(got), n-1, got)
}
for i, d := range got {
if want := time.Duration(i+1) * 250 * time.Millisecond; d != want {
t.Fatalf("sleeps %v: slot %d is %v, want %v", got, i+1, d, want)
}
}
}
func TestPacerCancelledBeforeWaitingReturnsAtOnceAndTakesNoSlot(t *testing.T) {
f := &fakeTime{t: t0}
p := newPacer(1, f.now, f.sleep)
ctx, cancel := context.WithCancel(context.Background())
cancel()
if err := p.Wait(ctx); !errors.Is(err, context.Canceled) {
t.Fatalf("err = %v", err)
}
if len(f.slept) != 0 {
t.Fatalf("slept %v", f.slept)
}
// No slot was used: the next caller goes first, without waiting.
if err := p.Wait(context.Background()); err != nil || len(f.slept) != 0 {
t.Fatalf("err=%v slept=%v", err, f.slept)
}
}
func TestPacerCancelledWhileWaitingGivesTheSlotBack(t *testing.T) {
f := &fakeTime{t: t0}
p := newPacer(10, f.now, f.sleep)
p.Wait(context.Background()) // takes slot 0; the next free slot is +100ms
f.err = context.Canceled
if err := p.Wait(context.Background()); !errors.Is(err, context.Canceled) {
t.Fatalf("err = %v", err)
}
f.err = nil
f.slept = nil
p.Wait(context.Background())
if len(f.slept) != 1 || f.slept[0] != 100*time.Millisecond {
t.Fatalf("after a cancelled wait the next caller sleeps %v, want [100ms]: the slot was not given back", f.slept)
}
}
func TestPacerCancelledCallerInTheMiddleNeverBlocksTheOthers(t *testing.T) {
f := &fakeTime{t: t0}
p := newPacer(10, f.now, f.sleep)
p.Wait(context.Background())
// B and C reserve +100ms and +200ms; B is cancelled and C still gets out at +200ms at most.
var mu sync.Mutex
first := true
f2 := func(ctx context.Context, d time.Duration) error {
if first {
first = false
return context.Canceled
}
mu.Lock()
defer mu.Unlock()
f.slept = append(f.slept, d)
return nil
}
p.sleep = f2
if err := p.Wait(context.Background()); err == nil {
t.Fatal("B should fail")
}
if err := p.Wait(context.Background()); err != nil {
t.Fatal(err)
}
for _, d := range f.slept {
if d > 200*time.Millisecond {
t.Fatalf("slept %v: later than the slot it reserved", d)
}
}
}
func TestNoPacerForARateOfZeroOrLess(t *testing.T) {
for _, r := range []float64{0, -1, math.NaN(), math.Inf(-1), math.Inf(1)} {
f := &fakeTime{t: t0}
p := newPacer(r, f.now, f.sleep)
for i := 0; i < 5; i++ {
if err := p.Wait(context.Background()); err != nil {
t.Fatalf("rate %v: %v", r, err)
}
}
if len(f.slept) != 0 {
t.Fatalf("rate %v: slept %v", r, f.slept)
}
}
}
func TestNoPacerStillStopsForACancelledContext(t *testing.T) {
var p *pacer
ctx, cancel := context.WithCancel(context.Background())
cancel()
if err := p.Wait(ctx); err == nil {
t.Fatal("a cancelled context must not pass")
}
}
func TestPacerAtAVeryLowRateDoesNotOverflow(t *testing.T) {
f := &fakeTime{t: t0, advance: true}
p := newPacer(1e-300, f.now, f.sleep)
for i := 0; i < 3; i++ {
p.Wait(context.Background())
}
if len(f.slept) != 2 {
t.Fatalf("slept %v", f.slept)
}
for _, d := range f.slept {
if d <= 0 || d > maxInterval {
t.Fatalf("sleep %v out of range (0, %v]", d, maxInterval)
}
}
}
func TestPacerAtAVeryHighRateNeverWaits(t *testing.T) {
for _, r := range []float64{1e10, 1e12, 1e300, math.MaxFloat64} {
f := &fakeTime{t: t0}
p := newPacer(r, f.now, f.sleep)
for i := 0; i < 100; i++ {
if err := p.Wait(context.Background()); err != nil {
t.Fatal(err)
}
}
if len(f.slept) != 0 {
t.Fatalf("rate %v: slept %v", r, f.slept)
}
}
}
func TestSleepCtxStopsWhenTheContextIsCancelled(t *testing.T) {
ctx, cancel := context.WithCancel(context.Background())
cancel()
start := time.Now()
if err := sleepCtx(ctx, time.Hour); !errors.Is(err, context.Canceled) {
t.Fatalf("err = %v", err)
}
if time.Since(start) > time.Second {
t.Fatal("did not return at once")
}
if err := sleepCtx(context.Background(), time.Millisecond); err != nil {
t.Fatal(err)
}
}
func TestPacerKeepsTheSlotsOfLaterCallersWhenAnEarlierOneGivesUp(t *testing.T) {
f := &fakeTime{t: t0}
release := make(chan struct{})
p := newPacer(10, f.now, nil)
p.sleep = func(ctx context.Context, d time.Duration) error {
f.sleep(ctx, d)
if d == 100*time.Millisecond {
<-release // B waits until C has reserved its slot, then gives up
return context.Canceled
}
return nil
}
p.Wait(context.Background()) // A: slot 0
done := make(chan error)
go func() { done <- p.Wait(context.Background()) }() // B: slot +100ms
for len(f.durations()) < 1 {
time.Sleep(time.Millisecond)
}
p.Wait(context.Background()) // C: slot +200ms
close(release)
if err := <-done; err == nil {
t.Fatal("B should have given up")
}
f.mu.Lock()
f.slept = nil
f.mu.Unlock()
p.Wait(context.Background()) // D must come after C, not collide with it
if got := f.durations(); len(got) != 1 || got[0] != 300*time.Millisecond {
t.Fatalf("D sleeps %v, want [300ms]: it took a slot another caller holds", got)
}
}