1// Copyright 2018 The go-ethereum Authors
2// This file is part of the go-ethereum library.
3//
4// The go-ethereum library is free software: you can redistribute it and/or modify
5// it under the terms of the GNU Lesser General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8//
9// The go-ethereum library is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12// GNU Lesser General Public License for more details.
13//
14// You should have received a copy of the GNU Lesser General Public License
15// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
16
17package mclock
18
19import (
20	"sync"
21	"time"
22)
23
24// Simulated implements a virtual Clock for reproducible time-sensitive tests. It
25// simulates a scheduler on a virtual timescale where actual processing takes zero time.
26//
27// The virtual clock doesn't advance on its own, call Run to advance it and execute timers.
28// Since there is no way to influence the Go scheduler, testing timeout behaviour involving
29// goroutines needs special care. A good way to test such timeouts is as follows: First
30// perform the action that is supposed to time out. Ensure that the timer you want to test
31// is created. Then run the clock until after the timeout. Finally observe the effect of
32// the timeout using a channel or semaphore.
33type Simulated struct {
34	now       AbsTime
35	scheduled []event
36	mu        sync.RWMutex
37	cond      *sync.Cond
38}
39
40type event struct {
41	do func()
42	at AbsTime
43}
44
45// Run moves the clock by the given duration, executing all timers before that duration.
46func (s *Simulated) Run(d time.Duration) {
47	s.mu.Lock()
48	defer s.mu.Unlock()
49	s.init()
50
51	end := s.now + AbsTime(d)
52	for len(s.scheduled) > 0 {
53		ev := s.scheduled[0]
54		if ev.at > end {
55			break
56		}
57		s.now = ev.at
58		ev.do()
59		s.scheduled = s.scheduled[1:]
60	}
61	s.now = end
62}
63
64func (s *Simulated) ActiveTimers() int {
65	s.mu.RLock()
66	defer s.mu.RUnlock()
67
68	return len(s.scheduled)
69}
70
71func (s *Simulated) WaitForTimers(n int) {
72	s.mu.Lock()
73	defer s.mu.Unlock()
74	s.init()
75
76	for len(s.scheduled) < n {
77		s.cond.Wait()
78	}
79}
80
81// Now implements Clock.
82func (s *Simulated) Now() AbsTime {
83	s.mu.RLock()
84	defer s.mu.RUnlock()
85
86	return s.now
87}
88
89// Sleep implements Clock.
90func (s *Simulated) Sleep(d time.Duration) {
91	<-s.After(d)
92}
93
94// After implements Clock.
95func (s *Simulated) After(d time.Duration) <-chan time.Time {
96	after := make(chan time.Time, 1)
97	s.insert(d, func() {
98		after <- (time.Time{}).Add(time.Duration(s.now))
99	})
100	return after
101}
102
103func (s *Simulated) insert(d time.Duration, do func()) {
104	s.mu.Lock()
105	defer s.mu.Unlock()
106	s.init()
107
108	at := s.now + AbsTime(d)
109	l, h := 0, len(s.scheduled)
110	ll := h
111	for l != h {
112		m := (l + h) / 2
113		if at < s.scheduled[m].at {
114			h = m
115		} else {
116			l = m + 1
117		}
118	}
119	s.scheduled = append(s.scheduled, event{})
120	copy(s.scheduled[l+1:], s.scheduled[l:ll])
121	s.scheduled[l] = event{do: do, at: at}
122	s.cond.Broadcast()
123}
124
125func (s *Simulated) init() {
126	if s.cond == nil {
127		s.cond = sync.NewCond(&s.mu)
128	}
129}
130