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