1// SPDX-License-Identifier: AGPL-3.0-or-later
2
3package web
4
5import (
6 "context"
7 "errors"
8 "fmt"
9 "sync"
10 "sync/atomic"
11 "testing"
12 "time"
13
14 "github.com/stretchr/testify/assert"
15 "github.com/stretchr/testify/require"
16)
17
18// store puts a list in the cache the way a finished build does.
19func (c *pathCache) store(id string, body []byte) {
20 c.mu.Lock()
21 defer c.mu.Unlock()
22 c.putLocked(id, body)
23}
24
25// has says whether a list is cached, marking it as used.
26func (c *pathCache) has(id string) bool {
27 c.mu.Lock()
28 defer c.mu.Unlock()
29 _, ok := c.getLocked(id)
30 return ok
31}
32
33func TestPathCacheEvictsLeastRecentlyUsed(t *testing.T) {
34 t.Parallel()
35 c := newPathCache(100, 1)
36 blob := func(n int) []byte { return make([]byte, n) }
37 c.store("a", blob(25))
38 c.store("b", blob(25))
39 c.store("e", blob(25))
40 require.True(t, c.has("a")) // a is now the most recent
41 c.store("c", blob(25)) // 100 fit
42 c.store("d", blob(10)) // 110 > 100: b, the least recent, goes
43 assert.False(t, c.has("b"), "b was evicted")
44 assert.True(t, c.has("a") && c.has("c") && c.has("d") && c.has("e"))
45 assert.Equal(t, 85, c.size)
46
47 // Replacing an entry accounts for the old size.
48 c.store("a", blob(10))
49 assert.Equal(t, 70, c.size)
50
51 // A big one pushes out as many as needed.
52 c.store("f", blob(25))
53 c.store("g", blob(25))
54 assert.LessOrEqual(t, c.size, 100)
55 assert.True(t, c.has("g"))
56}
57
58// A list over a quarter of the budget is not kept, since it would push out the
59// others; one at the limit is.
60func TestPathCacheSkipsOversizedEntries(t *testing.T) {
61 t.Parallel()
62 c := newPathCache(100, 1)
63 var builds atomic.Int32
64 big := func(n int) func() ([]byte, error) {
65 return func() ([]byte, error) { builds.Add(1); return make([]byte, n), nil }
66 }
67 for range 2 {
68 b, err := c.load(context.Background(), "r", "big", big(26))
69 require.NoError(t, err)
70 assert.Len(t, b, 26, "the caller still gets the list")
71 }
72 assert.EqualValues(t, 2, builds.Load(), "not cached, so built again")
73 assert.False(t, c.has("big"))
74 assert.Zero(t, c.size)
75
76 for range 2 {
77 _, err := c.load(context.Background(), "r", "fits", big(25))
78 require.NoError(t, err)
79 }
80 assert.EqualValues(t, 3, builds.Load(), "at a quarter: kept")
81 assert.Equal(t, 25, c.size)
82}
83
84func TestPathCacheConcurrent(t *testing.T) {
85 t.Parallel()
86 c := newPathCache(1000, 1)
87 var wg sync.WaitGroup
88 for g := range 8 {
89 wg.Add(1)
90 go func() {
91 defer wg.Done()
92 for i := range 500 {
93 c.store(fmt.Sprint((g+i)%17), make([]byte, 10+i%90))
94 c.has(fmt.Sprint(i % 17))
95 }
96 }()
97 }
98 wg.Wait()
99 assert.LessOrEqual(t, c.size, 1000)
100 sum := 0
101 for _, el := range c.byID {
102 sum += len(el.Value.(*pathEntry).body)
103 }
104 assert.Equal(t, sum, c.size, "the size is the sum of the entries")
105 assert.Equal(t, len(c.byID), c.lru.Len())
106}
107
108// waiters is the number of callers waiting for the build of a key, -1 when
109// none is in flight.
110func waiters(c *pathCache, repo, id string) int {
111 c.mu.Lock()
112 defer c.mu.Unlock()
113 if f := c.building[repo+"\x00"+id]; f != nil {
114 return f.waiters
115 }
116 return -1
117}
118
119func building(c *pathCache, n int) bool {
120 c.mu.Lock()
121 defer c.mu.Unlock()
122 return len(c.building) == n
123}
124
125// Concurrent misses for one commit build once; a failure is shared and not
126// stored; a waiter that gives up leaves the build running.
127func TestPathCacheLoadBuildsOnce(t *testing.T) {
128 t.Parallel()
129 c := newPathCache(1000, 4)
130 var builds atomic.Int32
131 release := make(chan struct{})
132 build := func() ([]byte, error) {
133 builds.Add(1)
134 <-release
135 return []byte("list"), nil
136 }
137 const callers = 10
138 var wg sync.WaitGroup
139 got := make([][]byte, callers)
140 for i := range got {
141 wg.Add(1)
142 go func() {
143 defer wg.Done()
144 b, err := c.load(context.Background(), "r", "x", build)
145 assert.NoError(t, err)
146 got[i] = b
147 }()
148 }
149 // Every caller waits for the one build before it is released: none can
150 // find the list cached, so one build serving all ten shows they joined it.
151 require.Eventually(t, func() bool { return waiters(c, "r", "x") == callers }, 5*time.Second, time.Millisecond)
152 // A waiter whose context ends does not stop the others.
153 ctx, cancel := context.WithCancel(context.Background())
154 cancel()
155 _, err := c.load(ctx, "r", "x", build)
156 assert.ErrorIs(t, err, context.Canceled)
157 close(release)
158 wg.Wait()
159 assert.EqualValues(t, 1, builds.Load())
160 for _, b := range got {
161 assert.Equal(t, "list", string(b))
162 }
163 assert.True(t, c.has("x"))
164
165 boom := errors.New("boom")
166 _, err = c.load(context.Background(), "r", "y", func() ([]byte, error) { return nil, boom })
167 assert.ErrorIs(t, err, boom)
168 assert.False(t, c.has("y"), "a failure is not cached")
169 b, err := c.load(context.Background(), "r", "y", func() ([]byte, error) { return []byte("ok"), nil })
170 require.NoError(t, err)
171 assert.Equal(t, "ok", string(b), "the next request builds again")
172 assert.Empty(t, c.building)
173}
174
175// The builds of all commits share the slots: with one slot, a load of another
176// commit waits for the running build, and leaves with its ctx if it is
177// cancelled first. The slot is the build's, not the caller's.
178func TestPathCacheLoadBoundsBuilds(t *testing.T) {
179 t.Parallel()
180 c := newPathCache(1000, 1)
181 started, release := make(chan struct{}), make(chan struct{})
182 first := make(chan error, 1)
183 go func() {
184 _, err := c.load(context.Background(), "r", "a", func() ([]byte, error) { close(started); <-release; return []byte("a"), nil })
185 first <- err
186 }()
187 <-started
188
189 // A second commit waits for the slot...
190 var secondBuilt atomic.Bool
191 second := make(chan error, 1)
192 go func() {
193 _, err := c.load(context.Background(), "r", "b", func() ([]byte, error) { secondBuilt.Store(true); return []byte("b"), nil })
194 second <- err
195 }()
196 time.Sleep(30 * time.Millisecond)
197 assert.False(t, secondBuilt.Load(), "no slot, no build")
198 select {
199 case <-second:
200 t.Fatal("the second load did not wait for a slot")
201 default:
202 }
203
204 // ...or leaves with its ctx.
205 ctx, cancel := context.WithTimeout(context.Background(), 20*time.Millisecond)
206 defer cancel()
207 _, err := c.load(ctx, "r", "c", func() ([]byte, error) { t.Error("built without a slot"); return nil, nil })
208 assert.ErrorIs(t, err, context.DeadlineExceeded)
209
210 // A caller of the running build is not held by the slots.
211 _, err = c.load(ctx, "r", "a", nil)
212 assert.ErrorIs(t, err, context.DeadlineExceeded, "it joins the build and leaves with its ctx")
213
214 close(release)
215 require.NoError(t, <-first)
216 require.NoError(t, <-second)
217 assert.True(t, secondBuilt.Load())
218 assert.True(t, c.has("a") && c.has("b"))
219 assert.Empty(t, c.building)
220 assert.Empty(t, c.slots, "every slot is back")
221}
222
223// The slot of a build is kept after its callers leave, and given back when it
224// ends, whether it fails or panics.
225func TestPathCacheSlotOutlivesCallers(t *testing.T) {
226 t.Parallel()
227 c := newPathCache(1000, 1)
228 started, release := make(chan struct{}), make(chan struct{})
229 ctx, cancel := context.WithCancel(context.Background())
230 done := make(chan error, 1)
231 go func() {
232 _, err := c.load(ctx, "r", "a", func() ([]byte, error) { close(started); <-release; panic("boom") })
233 done <- err
234 }()
235 <-started
236 cancel()
237 assert.ErrorIs(t, <-done, context.Canceled)
238 assert.Len(t, c.slots, 1, "the build still holds its slot")
239 close(release)
240 require.Eventually(t, func() bool { return len(c.slots) == 0 && building(c, 0) }, time.Second, time.Millisecond)
241 b, err := c.load(context.Background(), "r", "b", func() ([]byte, error) { return []byte("ok"), nil })
242 require.NoError(t, err)
243 assert.Equal(t, "ok", string(b))
244}
245
246// A build that panics is handed to its waiters as an error, leaves nothing
247// in flight or cached, and does not take the process down.
248func TestPathCacheLoadPanic(t *testing.T) {
249 t.Parallel()
250 c := newPathCache(1000, 4)
251 started, release := make(chan struct{}), make(chan struct{})
252 var once sync.Once
253 build := func() ([]byte, error) {
254 once.Do(func() { close(started) })
255 <-release
256 panic("boom")
257 }
258 errs := make(chan error, 2)
259 for range 2 {
260 go func() {
261 _, err := c.load(context.Background(), "r", "x", build)
262 errs <- err
263 }()
264 }
265 <-started
266 require.Eventually(t, func() bool { c.mu.Lock(); defer c.mu.Unlock(); return len(c.building) == 1 }, time.Second, time.Millisecond)
267 close(release)
268 for range 2 {
269 assert.ErrorIs(t, <-errs, errBuildPanicked)
270 }
271 assert.Empty(t, c.building)
272 assert.False(t, c.has("x"), "a panic is not cached")
273
274 b, err := c.load(context.Background(), "r", "x", func() ([]byte, error) { return []byte("ok"), nil })
275 require.NoError(t, err)
276 assert.Equal(t, "ok", string(b), "the next request builds again")
277}
278
279// The caller that starts a build is released with its context too, and the
280// build goes on for the others.
281func TestPathCacheLoadStarterLeaves(t *testing.T) {
282 t.Parallel()
283 c := newPathCache(1000, 4)
284 release := make(chan struct{})
285 build := func() ([]byte, error) { <-release; return []byte("list"), nil }
286 ctx, cancel := context.WithCancel(context.Background())
287 done := make(chan error, 1)
288 go func() { _, err := c.load(ctx, "r", "x", build); done <- err }()
289 require.Eventually(t, func() bool { c.mu.Lock(); defer c.mu.Unlock(); return len(c.building) == 1 }, time.Second, time.Millisecond)
290 cancel()
291 select {
292 case err := <-done:
293 assert.ErrorIs(t, err, context.Canceled)
294 case <-time.After(time.Second):
295 t.Fatal("the starter is held by its build")
296 }
297 close(release)
298 require.Eventually(t, func() bool { return c.has("x") }, time.Second, time.Millisecond)
299 assert.Empty(t, c.building)
300}
301
302// A failure belongs to the repository that built it: another repository
303// asking for the same commit builds its own.
304func TestPathCacheLoadFailureStaysInRepo(t *testing.T) {
305 t.Parallel()
306 c := newPathCache(1000, 4)
307 started, release := make(chan struct{}), make(chan struct{})
308 boom := errors.New("boom")
309 failing := make(chan error, 1)
310 go func() {
311 _, err := c.load(context.Background(), "a", "x", func() ([]byte, error) { close(started); <-release; return nil, boom })
312 failing <- err
313 }()
314 <-started
315 b, err := c.load(context.Background(), "b", "x", func() ([]byte, error) { return []byte("list"), nil })
316 require.NoError(t, err)
317 assert.Equal(t, "list", string(b))
318 close(release)
319 assert.ErrorIs(t, <-failing, boom)
320}