1 // Copyright 2020 The gVisor Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 15 package tcpip
16 17 import (
18 "time"
19 20 "gvisor.dev/gvisor/pkg/sync"
21 )
22 23 // jobInstance is a specific instance of Job.
24 //
25 // Different instances are created each time Job is scheduled so each timer has
26 // its own earlyReturn signal. This is to address a bug when a Job is stopped
27 // and reset in quick succession resulting in a timer instance's earlyReturn
28 // signal being affected or seen by another timer instance.
29 //
30 // Consider the following sceneario where timer instances share a common
31 // earlyReturn signal (T1 creates, stops and resets a Cancellable timer under a
32 // lock L; T2, T3, T4 and T5 are goroutines that handle the first (A), second
33 // (B), third (C), and fourth (D) instance of the timer firing, respectively):
34 //
35 // T1: Obtain L
36 // T1: Create a new Job w/ lock L (create instance A)
37 // T2: instance A fires, blocked trying to obtain L.
38 // T1: Attempt to stop instance A (set earlyReturn = true)
39 // T1: Schedule timer (create instance B)
40 // T3: instance B fires, blocked trying to obtain L.
41 // T1: Attempt to stop instance B (set earlyReturn = true)
42 // T1: Schedule timer (create instance C)
43 // T4: instance C fires, blocked trying to obtain L.
44 // T1: Attempt to stop instance C (set earlyReturn = true)
45 // T1: Schedule timer (create instance D)
46 // T5: instance D fires, blocked trying to obtain L.
47 // T1: Release L
48 //
49 // Now that T1 has released L, any of the 4 timer instances can take L and
50 // check earlyReturn. If the timers simply check earlyReturn and then do
51 // nothing further, then instance D will never early return even though it was
52 // not requested to stop. If the timers reset earlyReturn before early
53 // returning, then all but one of the timers will do work when only one was
54 // expected to. If Job resets earlyReturn when resetting, then all the timers
55 // will fire (again, when only one was expected to).
56 //
57 // To address the above concerns the simplest solution was to give each timer
58 // its own earlyReturn signal.
59 //
60 // +stateify savable
61 type jobInstance struct {
62 timer Timer
63 64 // Used to inform the timer to early return when it gets stopped while the
65 // lock the timer tries to obtain when fired is held (T1 is a goroutine that
66 // tries to cancel the timer and T2 is the goroutine that handles the timer
67 // firing):
68 // T1: Obtain the lock, then call Cancel()
69 // T2: timer fires, and gets blocked on obtaining the lock
70 // T1: Releases lock
71 // T2: Obtains lock does unintended work
72 //
73 // To resolve this, T1 will check to see if the timer already fired, and
74 // inform the timer using earlyReturn to return early so that once T2 obtains
75 // the lock, it will see that it is set to true and do nothing further.
76 earlyReturn *bool
77 }
78 79 // stop stops the job instance j from firing if it hasn't fired already. If it
80 // has fired and is blocked at obtaining the lock, earlyReturn will be set to
81 // true so that it will early return when it obtains the lock.
82 func (j *jobInstance) stop() {
83 if j.timer != nil {
84 j.timer.Stop()
85 *j.earlyReturn = true
86 }
87 }
88 89 // Job represents some work that can be scheduled for execution. The work can
90 // be safely cancelled when it fires at the same time some "related work" is
91 // being done.
92 //
93 // The term "related work" is defined as some work that needs to be done while
94 // holding some lock that the timer must also hold while doing some work.
95 //
96 // Note, it is not safe to copy a Job as its timer instance creates
97 // a closure over the address of the Job.
98 //
99 // +stateify savable
100 type Job struct {
101 _ sync.NoCopy
102 103 // The clock used to schedule the backing timer
104 clock Clock
105 106 // The active instance of a cancellable timer.
107 instance jobInstance
108 109 // locker is the lock taken by the timer immediately after it fires and must
110 // be held when attempting to stop the timer.
111 //
112 // Must never change after being assigned.
113 locker sync.Locker `state:"nosave"`
114 115 // fn is the function that will be called when a timer fires and has not been
116 // signaled to early return.
117 //
118 // fn MUST NOT attempt to lock locker.
119 //
120 // Must never change after being assigned.
121 // TODO(b/341946753): Restore when netstack is savable.
122 fn func() `state:"nosave"`
123 }
124 125 // Cancel prevents the Job from executing if it has not executed already.
126 //
127 // Cancel requires appropriate locking to be in place for any resources managed
128 // by the Job. If the Job is blocked on obtaining the lock when Cancel is
129 // called, it will early return.
130 //
131 // Note, t will be modified.
132 //
133 // j.locker MUST be locked.
134 func (j *Job) Cancel() {
135 j.instance.stop()
136 137 // Nothing to do with the stopped instance anymore.
138 j.instance = jobInstance{}
139 }
140 141 // Schedule schedules the Job for execution after duration d. This can be
142 // called on cancelled or completed Jobs to schedule them again.
143 //
144 // Schedule should be invoked only on unscheduled, cancelled, or completed
145 // Jobs. To be safe, callers should always call Cancel before calling Schedule.
146 //
147 // Note, j will be modified.
148 func (j *Job) Schedule(d time.Duration) {
149 // Create a new instance.
150 earlyReturn := false
151 152 // Capture the locker so that updating the timer does not cause a data race
153 // when a timer fires and tries to obtain the lock (read the timer's locker).
154 locker := j.locker
155 j.instance = jobInstance{
156 timer: j.clock.AfterFunc(d, func() {
157 locker.Lock()
158 defer locker.Unlock()
159 160 if earlyReturn {
161 // If we reach this point, it means that the timer fired while another
162 // goroutine called Cancel while it had the lock. Simply return here
163 // and do nothing further.
164 earlyReturn = false
165 return
166 }
167 168 j.fn()
169 }),
170 earlyReturn: &earlyReturn,
171 }
172 }
173 174 // NewJob returns a new Job that can be used to schedule f to run in its own
175 // gorountine. l will be locked before calling f then unlocked after f returns.
176 //
177 // var clock tcpip.StdClock
178 // var mu sync.Mutex
179 // message := "foo"
180 // job := tcpip.NewJob(&clock, &mu, func() {
181 // fmt.Println(message)
182 // })
183 // job.Schedule(time.Second)
184 //
185 // mu.Lock()
186 // message = "bar"
187 // mu.Unlock()
188 //
189 // // Output: bar
190 //
191 // f MUST NOT attempt to lock l.
192 //
193 // l MUST be locked prior to calling the returned job's Cancel().
194 //
195 // var clock tcpip.StdClock
196 // var mu sync.Mutex
197 // message := "foo"
198 // job := tcpip.NewJob(&clock, &mu, func() {
199 // fmt.Println(message)
200 // })
201 // job.Schedule(time.Second)
202 //
203 // mu.Lock()
204 // job.Cancel()
205 // mu.Unlock()
206 func NewJob(c Clock, l sync.Locker, f func()) *Job {
207 return &Job{
208 clock: c,
209 locker: l,
210 fn: f,
211 }
212 }
213