1package regexp2
  2
  3import (
  4	"sync"
  5	"sync/atomic"
  6	"time"
  7)
  8
  9// fasttime holds a time value (ticks since clock initialization)
 10type fasttime int64
 11
 12// fastclock provides a fast clock implementation.
 13//
 14// A background goroutine periodically stores the current time
 15// into an atomic variable.
 16//
 17// A deadline can be quickly checked for expiration by comparing
 18// its value to the clock stored in the atomic variable.
 19//
 20// The goroutine automatically stops once clockEnd is reached.
 21// (clockEnd covers the largest deadline seen so far + some
 22// extra time). This ensures that if regexp2 with timeouts
 23// stops being used we will stop background work.
 24type fastclock struct {
 25	// instances of atomicTime must be at the start of the struct (or at least 64-bit aligned)
 26	// otherwise 32-bit architectures will panic
 27
 28	current  atomicTime // Current time (approximate)
 29	clockEnd atomicTime // When clock updater is supposed to stop (>= any existing deadline)
 30
 31	// current and clockEnd can be read via atomic loads.
 32	// Reads and writes of other fields require mu to be held.
 33	mu      sync.Mutex
 34	start   time.Time // Time corresponding to fasttime(0)
 35	running bool      // Is a clock updater running?
 36}
 37
 38var fast fastclock
 39
 40// reached returns true if current time is at or past t.
 41func (t fasttime) reached() bool {
 42	return fast.current.read() >= t
 43}
 44
 45// makeDeadline returns a time that is approximately time.Now().Add(d)
 46func makeDeadline(d time.Duration) fasttime {
 47	// Increase the deadline since the clock we are reading may be
 48	// just about to tick forwards.
 49	end := fast.current.read() + durationToTicks(d+clockPeriod)
 50
 51	// Start or extend clock if necessary.
 52	if end > fast.clockEnd.read() {
 53		// If time.Since(last use) > timeout, there's a chance that
 54		// fast.current will no longer be updated, which can lead to
 55		// incorrect 'end' calculations that can trigger a false timeout
 56		fast.mu.Lock()
 57		if !fast.running && !fast.start.IsZero() {
 58			// update fast.current
 59			fast.current.write(durationToTicks(time.Since(fast.start)))
 60			// recalculate our end value
 61			end = fast.current.read() + durationToTicks(d+clockPeriod)
 62		}
 63		fast.mu.Unlock()
 64		extendClock(end)
 65	}
 66
 67	return end
 68}
 69
 70// extendClock ensures that clock is live and will run until at least end.
 71func extendClock(end fasttime) {
 72	fast.mu.Lock()
 73	defer fast.mu.Unlock()
 74
 75	if fast.start.IsZero() {
 76		fast.start = time.Now()
 77	}
 78
 79	// Extend the running time to cover end as well as a bit of slop.
 80	if shutdown := end + durationToTicks(time.Second); shutdown > fast.clockEnd.read() {
 81		fast.clockEnd.write(shutdown)
 82	}
 83
 84	// Start clock if necessary
 85	if !fast.running {
 86		fast.running = true
 87		go runClock()
 88	}
 89}
 90
 91// stop the timeout clock in the background
 92// should only used for unit tests to abandon the background goroutine
 93func stopClock() {
 94	fast.mu.Lock()
 95	if fast.running {
 96		fast.clockEnd.write(fasttime(0))
 97	}
 98	fast.mu.Unlock()
 99
100	// pause until not running
101	// get and release the lock
102	isRunning := true
103	for isRunning {
104		time.Sleep(clockPeriod / 2)
105		fast.mu.Lock()
106		isRunning = fast.running
107		fast.mu.Unlock()
108	}
109}
110
111func durationToTicks(d time.Duration) fasttime {
112	// Downscale nanoseconds to approximately a millisecond so that we can avoid
113	// overflow even if the caller passes in math.MaxInt64.
114	return fasttime(d) >> 20
115}
116
117const DefaultClockPeriod = 100 * time.Millisecond
118
119// clockPeriod is the approximate interval between updates of approximateClock.
120var clockPeriod = DefaultClockPeriod
121
122func runClock() {
123	fast.mu.Lock()
124	defer fast.mu.Unlock()
125
126	for fast.current.read() <= fast.clockEnd.read() {
127		// Unlock while sleeping.
128		fast.mu.Unlock()
129		time.Sleep(clockPeriod)
130		fast.mu.Lock()
131
132		newTime := durationToTicks(time.Since(fast.start))
133		fast.current.write(newTime)
134	}
135	fast.running = false
136}
137
138type atomicTime struct{ v int64 } // Should change to atomic.Int64 when we can use go 1.19
139
140func (t *atomicTime) read() fasttime   { return fasttime(atomic.LoadInt64(&t.v)) }
141func (t *atomicTime) write(v fasttime) { atomic.StoreInt64(&t.v, int64(v)) }