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// entryOverhead is what an entry costs besides its id and body: the list
74// element, the entry and the map slot. Counted so that tiny bodies (a cached
75// "no license") cannot pile up far past the budget.
76const entryOverhead = 128
77
78// cost is what an entry counts against the budget.
79func (e *pathEntry) cost() int { return len(e.id) + len(e.body) + entryOverhead }
80
81// putLocked stores a list, evicting the least recently used ones to stay in
82// budget. A list over a quarter of the budget is not stored.
83func (c *pathCache) putLocked(id string, body []byte) {
84 if len(body) > c.budget/4 {
85 return
86 }
87 if el, ok := c.byID[id]; ok {
88 e := el.Value.(*pathEntry)
89 c.size -= e.cost()
90 e.body = body
91 c.size += e.cost()
92 c.lru.MoveToFront(el)
93 } else {
94 e := &pathEntry{id: id, body: body}
95 c.byID[id] = c.lru.PushFront(e)
96 c.size += e.cost()
97 }
98 for c.size > c.budget {
99 el := c.lru.Back()
100 e := el.Value.(*pathEntry)
101 c.lru.Remove(el)
102 delete(c.byID, e.id)
103 c.size -= e.cost()
104 }
105}
106
107// load returns the list of a commit: from the cache, or from build, which
108// runs once however many callers of a repository ask at the same time. The
109// build runs in its own goroutine, so no caller is held by it: each one,
110// the one that started it included, waits for the build or for its own ctx.
111//
112// Only pathBuilds builds run at a time, whatever their commits: a caller that
113// would start one waits for a free slot, or for its ctx. The build keeps the
114// slot until it ends, even if every caller has left.
115//
116// Builds in progress are keyed by repository and commit, though the cache is
117// keyed by commit only: a failure of one repository (the commit is missing
118// there, its access rule changed) must not be handed to the requests of
119// another one that would have succeeded.
120func (c *pathCache) load(ctx context.Context, repo, id string, build func() ([]byte, error)) ([]byte, error) {
121 key := repo + "\x00" + id // a repository name has no NUL
122 f, body, ok := c.join(key, id)
123 if ok {
124 return body, nil
125 }
126 if f == nil {
127 // Nothing to join: take a slot, then look again, since the commit
128 // may have been built while this caller waited.
129 select {
130 case c.slots <- struct{}{}:
131 case <-ctx.Done():
132 return nil, ctx.Err()
133 }
134 if f, body, ok = c.joinOrStart(ctx, key, id, build); ok {
135 return body, nil
136 }
137 }
138 select {
139 case <-f.done:
140 return f.body, f.err
141 case <-ctx.Done():
142 return nil, ctx.Err()
143 }
144}
145
146// join returns the list of a commit if it is cached, or the build in progress
147// for it.
148func (c *pathCache) join(key, id string) (f *pathBuild, body []byte, ok bool) {
149 c.mu.Lock()
150 defer c.mu.Unlock()
151 if b, ok := c.getLocked(id); ok {
152 return nil, b, true
153 }
154 f = c.building[key]
155 if f != nil {
156 f.waiters++
157 }
158 return f, nil, false
159}
160
161// joinOrStart is join for a caller that holds a slot: it starts the build when
162// there is still none, and gives the slot back when it does not need it.
163func (c *pathCache) joinOrStart(ctx context.Context, key, id string, build func() ([]byte, error)) (f *pathBuild, body []byte, ok bool) {
164 c.mu.Lock()
165 defer c.mu.Unlock()
166 if b, ok := c.getLocked(id); ok {
167 <-c.slots
168 return nil, b, true
169 }
170 if f, ok := c.building[key]; ok {
171 <-c.slots
172 f.waiters++
173 return f, nil, false
174 }
175 f = &pathBuild{done: make(chan struct{}), waiters: 1}
176 c.building[key] = f
177 go c.run(ctx, key, id, f, build)
178 return f, nil, false
179}
180
181// run executes a build and publishes it. A panic of build is logged and
182// handed to the waiters as errBuildPanicked: it cannot propagate, since
183// nobody above this goroutine could recover it and it would end the process.
184func (c *pathCache) run(ctx context.Context, key, id string, f *pathBuild, build func() ([]byte, error)) {
185 defer func() {
186 if r := recover(); r != nil {
187 f.body, f.err = nil, errBuildPanicked
188 zerowrap.Ctx(ctx).Error().Interface("panic", r).Str("stack", string(debug.Stack())).Msg("path list build panicked")
189 }
190 c.finish(key, id, f)
191 }()
192 f.body, f.err = build()
193}
194
195// finish publishes a build: stored when it worked, then released to the waiters.
196func (c *pathCache) finish(key, id string, f *pathBuild) {
197 c.mu.Lock()
198 delete(c.building, key)
199 if f.err == nil {
200 c.putLocked(id, f.body)
201 }
202 c.mu.Unlock()
203 <-c.slots // free before the waiters wake: one of them may start the next build
204 close(f.done)
205}