1// SPDX-License-Identifier: AGPL-3.0-or-later
2
3package web
4
5import (
6 "container/list"
7 "context"
8 "runtime/debug"
9 "sync"
10
11 "github.com/bnema/zerowrap"
12)
13
14const (
15 // pathCacheBytes is the budget of the cache of path lists.
16 pathCacheBytes = 64 << 20
17 // pathBuilds is how many path lists are built at the same time, for all
18 // commits and repositories: a build walks a whole tree and holds the
19 // list in memory.
20 pathBuilds = 4
21)
22
23// pathCache keeps the gzipped JSON path lists of commits, least recently used
24// out first, within a budget of bytes. A commit id names its content, so an
25// entry is right for every repository and every visitor; who may read it is
26// decided before the cache is asked (Server.paths).
27//
28// Concurrent misses for one commit of one repository share a single build,
29// and only a few builds run at a time.
30//
31// A list over a quarter of the budget is not kept (one big list would push
32// out most of the others): it is built again for each request that needs it.
33type pathCache struct {
34 mu sync.Mutex
35 budget int
36 size int
37 lru *list.List // of *pathEntry, most recently used first
38 byID map[string]*list.Element
39 building map[string]*pathBuild // by repository and commit
40 slots chan struct{} // one token per build running
41}
42
43type pathEntry struct {
44 id string
45 body []byte
46}
47
48// pathBuild is a build in progress; done is closed when body and err are set.
49type pathBuild struct {
50 waiters int // callers that joined it, for the tests; guarded by pathCache.mu
51 done chan struct{}
52 body []byte
53 err error
54}
55
56func newPathCache(budget, builds int) *pathCache {
57 return &pathCache{
58 budget: budget, lru: list.New(),
59 byID: map[string]*list.Element{}, building: map[string]*pathBuild{},
60 slots: make(chan struct{}, builds),
61 }
62}
63
64func (c *pathCache) getLocked(id string) ([]byte, bool) {
65 el, ok := c.byID[id]
66 if !ok {
67 return nil, false
68 }
69 c.lru.MoveToFront(el)
70 return el.Value.(*pathEntry).body, true
71}
72
73// putLocked stores a list, evicting the least recently used ones to stay in
74// budget. A list over a quarter of the budget is not stored.
75func (c *pathCache) putLocked(id string, body []byte) {
76 if len(body) > c.budget/4 {
77 return
78 }
79 if el, ok := c.byID[id]; ok {
80 c.size -= len(el.Value.(*pathEntry).body)
81 el.Value.(*pathEntry).body = body
82 c.size += len(body)
83 c.lru.MoveToFront(el)
84 } else {
85 c.byID[id] = c.lru.PushFront(&pathEntry{id: id, body: body})
86 c.size += len(body)
87 }
88 for c.size > c.budget {
89 el := c.lru.Back()
90 e := el.Value.(*pathEntry)
91 c.lru.Remove(el)
92 delete(c.byID, e.id)
93 c.size -= len(e.body)
94 }
95}
96
97// load returns the list of a commit: from the cache, or from build, which
98// runs once however many callers of a repository ask at the same time. The
99// build runs in its own goroutine, so no caller is held by it: each one,
100// the one that started it included, waits for the build or for its own ctx.
101//
102// Only pathBuilds builds run at a time, whatever their commits: a caller that
103// would start one waits for a free slot, or for its ctx. The build keeps the
104// slot until it ends, even if every caller has left.
105//
106// Builds in progress are keyed by repository and commit, though the cache is
107// keyed by commit only: a failure of one repository (the commit is missing
108// there, its access rule changed) must not be handed to the requests of
109// another one that would have succeeded.
110func (c *pathCache) load(ctx context.Context, repo, id string, build func() ([]byte, error)) ([]byte, error) {
111 key := repo + "\x00" + id // a repository name has no NUL
112 f, body, ok := c.join(key, id)
113 if ok {
114 return body, nil
115 }
116 if f == nil {
117 // Nothing to join: take a slot, then look again, since the commit
118 // may have been built while this caller waited.
119 select {
120 case c.slots <- struct{}{}:
121 case <-ctx.Done():
122 return nil, ctx.Err()
123 }
124 if f, body, ok = c.joinOrStart(ctx, key, id, build); ok {
125 return body, nil
126 }
127 }
128 select {
129 case <-f.done:
130 return f.body, f.err
131 case <-ctx.Done():
132 return nil, ctx.Err()
133 }
134}
135
136// join returns the list of a commit if it is cached, or the build in progress
137// for it.
138func (c *pathCache) join(key, id string) (f *pathBuild, body []byte, ok bool) {
139 c.mu.Lock()
140 defer c.mu.Unlock()
141 if b, ok := c.getLocked(id); ok {
142 return nil, b, true
143 }
144 f = c.building[key]
145 if f != nil {
146 f.waiters++
147 }
148 return f, nil, false
149}
150
151// joinOrStart is join for a caller that holds a slot: it starts the build when
152// there is still none, and gives the slot back when it does not need it.
153func (c *pathCache) joinOrStart(ctx context.Context, key, id string, build func() ([]byte, error)) (f *pathBuild, body []byte, ok bool) {
154 c.mu.Lock()
155 defer c.mu.Unlock()
156 if b, ok := c.getLocked(id); ok {
157 <-c.slots
158 return nil, b, true
159 }
160 if f, ok := c.building[key]; ok {
161 <-c.slots
162 f.waiters++
163 return f, nil, false
164 }
165 f = &pathBuild{done: make(chan struct{}), waiters: 1}
166 c.building[key] = f
167 go c.run(ctx, key, id, f, build)
168 return f, nil, false
169}
170
171// run executes a build and publishes it. A panic of build is logged and
172// handed to the waiters as errBuildPanicked: it cannot propagate, since
173// nobody above this goroutine could recover it and it would end the process.
174func (c *pathCache) run(ctx context.Context, key, id string, f *pathBuild, build func() ([]byte, error)) {
175 defer func() {
176 if r := recover(); r != nil {
177 f.body, f.err = nil, errBuildPanicked
178 zerowrap.Ctx(ctx).Error().Interface("panic", r).Str("stack", string(debug.Stack())).Msg("path list build panicked")
179 }
180 c.finish(key, id, f)
181 }()
182 f.body, f.err = build()
183}
184
185// finish publishes a build: stored when it worked, then released to the waiters.
186func (c *pathCache) finish(key, id string, f *pathBuild) {
187 c.mu.Lock()
188 delete(c.building, key)
189 if f.err == nil {
190 c.putLocked(id, f.body)
191 }
192 c.mu.Unlock()
193 <-c.slots // free before the waiters wake: one of them may start the next build
194 close(f.done)
195}