Repository navigation
Expand file tree
/
Copy pathcache.go
More file actions
256 lines (230 loc) · 8.4 KB
/
Copy pathcache.go
File metadata and controls
256 lines (230 loc) · 8.4 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
package starlet
import (
"context"
"errors"
"fmt"
"io/fs"
"sync"
"sync/atomic"
"unsafe"
"go.starlark.net/starlark"
"go.starlark.net/syntax"
)
// The following code is copied and modified from the starlark-go repo,
// https://go.starlark.net/starlark and is Copyright 2017 the Bazel authors,
// with a BSD 3-clause license (see the LICENSE file in that repo).
// Original source code: https://github.com/google/starlark-go/blob/master/starlark/example_test.go#L211
// machineState keeps optional print configuration with the runtime load state.
// Runtime initialization reuses state created by SetMaxPrintBytes, keeping
// optional configuration out of the Machine value.
type machineState struct {
loads cache
maxPrintBytes uint64
}
// cache is a concurrency-safe, duplicate-suppressing,
// non-blocking cache of the doLoad function.
// See Section 9.7 of gopl.io for an explanation of this structure.
// It also features online deadlock (load cycle) detection.
type cache struct {
cacheMu sync.Mutex
cache map[string]*entry
globals starlark.StringDict
execOpts *syntax.FileOptions
loadMod func(s string) (starlark.StringDict, error) // load from built-in module first
readFile func(s string) ([]byte, error) // and then from file system
// Both load-thread construction and cancellation belong to the same Machine.
// Keep one owner instead of allocating two bound method values. A standalone
// cache with no owner retains its bare-thread, uncancelled fallback.
machine *Machine
}
type entry struct {
owner unsafe.Pointer // a *cycleChecker; see cycleCheck
globals starlark.StringDict
err error
ready chan struct{}
}
func (c *cache) Load(module string) (starlark.StringDict, error) {
return c.get(new(cycleChecker), module)
}
func (c *cache) remove(module string) {
c.cacheMu.Lock()
delete(c.cache, module)
c.cacheMu.Unlock()
}
func (c *cache) reset() {
c.cacheMu.Lock()
c.cache = make(map[string]*entry)
c.cacheMu.Unlock()
}
// get loads and returns an entry (if not already loaded).
func (c *cache) get(cc *cycleChecker, module string) (starlark.StringDict, error) {
c.cacheMu.Lock()
e := c.cache[module]
if e != nil {
c.cacheMu.Unlock()
// Some other goroutine is getting this module.
// Wait for it to become ready.
// Detect load cycles to avoid deadlocks.
if err := cycleCheck(e, cc); err != nil {
return nil, err
}
cc.setWaitsFor(e)
<-e.ready
cc.setWaitsFor(nil)
} else {
// First request for this module.
e = &entry{ready: make(chan struct{})}
c.cache[module] = e
c.cacheMu.Unlock()
e.setOwner(cc)
// doLoad can panic: a loaded module can exhaust the step budget, which
// OnMaxSteps raises as a panic. Without recovery the half-built entry
// would never be readied or removed, so every later load of the same
// module blocks forever on <-e.ready. Ready the entry (with the error),
// drop it so a retry re-executes, then re-raise so runInternal maps it
// to a typed error. A `loaded` sentinel — not `recover() != nil` —
// decides whether doLoad panicked, because under the go 1.19 floor
// recover() returns nil for panic(nil), which would skip the cleanup.
loaded := false
defer func() {
if loaded {
return
}
r := recover()
if e.err == nil {
if err, ok := r.(error); ok {
e.err = err
} else {
e.err = fmt.Errorf("panic loading module %q: %v", module, r)
}
}
e.setOwner(nil)
close(e.ready)
c.remove(module)
panic(r)
}()
var loadThread *starlark.Thread
e.globals, e.err = c.doLoad(cc, module, &loadThread)
loaded = true
e.setOwner(nil)
// Broadcast that the entry is now ready.
close(e.ready)
// A load aborted because the run's context was cancelled is transient
// (run-scoped), not a property of the module: evict it so a later run
// reusing this machine without Reset re-executes instead of replaying
// the stale cancellation error. Mirrors the step-budget panic eviction.
// Waiters already blocked on e.ready still observe this run's error; only
// fresh loads after eviction re-execute.
if e.err != nil && loadContextCancelled(loadThread) {
c.remove(module)
}
}
return e.globals, e.err
}
// doLoad loads module. It publishes the thread the module executes on through
// *loadThread so the caller can tell whether a failure was a transient
// run-context cancellation (see get) without re-indenting the load body.
func (c *cache) doLoad(cc *cycleChecker, module string, loadThread **starlark.Thread) (starlark.StringDict, error) {
// Tunnel the cycle-checker state for this "thread of loading".
loadFn := func(_ *starlark.Thread, module string) (starlark.StringDict, error) {
return c.get(cc, module)
}
var thread *starlark.Thread
if c.machine != nil {
// inherit the Machine's print func, step budget, and run context so a
// loaded module cannot bypass them (e.g. a top-level loop escaping the
// DoS guard, or print() going to stdout instead of the print func)
thread = c.machine.newLoadThread(loadFn)
} else {
thread = &starlark.Thread{
Print: func(_ *starlark.Thread, msg string) { fmt.Println(msg) },
Load: loadFn,
}
}
*loadThread = thread
// Cancel this load thread when the run's context fires, so a long
// computation inside a loaded module honours the run timeout rather than
// running to completion on its own thread. Disarmed once loading finishes.
if c.machine != nil {
defer c.machine.watchLoadThread(thread)()
}
// 1: load from built-in module, the first field returns nil if not found
m, err := c.loadMod(module)
if err != nil {
// fail to load module
return nil, err
}
if m != nil {
// module found and loaded
return m, nil
}
// 2: load from source file
b, err := c.readFile(module)
if err != nil {
// A missing file or an absent filesystem means the name was found
// nowhere; report a typed error that names the module instead of
// surfacing the misleading filesystem message ("no file system
// given"). A name that matches a known builtin must have been
// deliberately left out of this machine's module set — withheld —
// which is different from a misspelled or unknown name.
if errors.Is(err, errNoFS) || errors.Is(err, fs.ErrNotExist) {
if _, known := allBuiltinModules[module]; known {
return nil, ModuleWithheldError{Name: module}
}
return nil, ModuleNotFoundError{Name: module}
}
return nil, err
}
// 3. execute the source file
if c.execOpts == nil {
return starlark.ExecFile(thread, module, b, c.globals)
}
return starlark.ExecFileOptions(c.execOpts, thread, module, b, c.globals)
}
// loadContextCancelled reports whether the given load thread's run context
// (carried as the "context" thread-local by newLoadThread) has been cancelled.
// A single expression so it is fully covered by any load, cancelled or not.
func loadContextCancelled(thread *starlark.Thread) bool {
ctx, ok := thread.Local("context").(context.Context)
return ok && ctx != nil && ctx.Err() != nil
}
// -- concurrent cycle checking --
// A cycleChecker is used for concurrent deadlock detection.
// Each top-level call to Load creates its own cycleChecker,
// which is passed to all recursive calls it makes.
// It corresponds to a logical thread in the deadlock detection literature.
type cycleChecker struct {
waitsFor unsafe.Pointer // an *entry; see cycleCheck
}
func (cc *cycleChecker) setWaitsFor(e *entry) {
atomic.StorePointer(&cc.waitsFor, unsafe.Pointer(e))
}
func (e *entry) setOwner(cc *cycleChecker) {
atomic.StorePointer(&e.owner, unsafe.Pointer(cc))
}
// cycleCheck reports whether there is a path in the waits-for graph
// from resource 'e' to thread 'me'.
//
// The waits-for graph (WFG) is a bipartite graph whose nodes are
// alternately of type entry and cycleChecker. Each node has at most
// one outgoing edge. An entry has an "owner" edge to a cycleChecker
// while it is being readied by that cycleChecker, and a cycleChecker
// has a "waits-for" edge to an entry while it is waiting for that entry
// to become ready.
//
// Before adding a waits-for edge, the cache checks whether the new edge
// would form a cycle. If so, this indicates that the load graph is
// cyclic and that the following wait operation would deadlock.
func cycleCheck(e *entry, me *cycleChecker) error {
for e != nil {
cc := (*cycleChecker)(atomic.LoadPointer(&e.owner))
if cc == nil {
break
}
if cc == me {
return errors.New("cycle in load graph")
}
e = (*entry)(atomic.LoadPointer(&cc.waitsFor))
}
return nil
}