1// SPDX-License-Identifier: AGPL-3.0-or-later
2
3package web
4
5import (
6 "container/list"
7 "context"
8 "sync"
9)
10
11// hlCacheBytes is the budget of the cache of highlighted diffs: a file of 36
12// KB of code weighs about 50 KB there, so it holds a few hundred of them.
13const hlCacheBytes = 8 << 20
14
15// hlCache keeps the colours of the files of diffs (hlData), least recently
16// used out first, within a budget of bytes. A key names the blobs the colours
17// come from (diffKey), so an entry is right for every visitor and every
18// repository that has the blobs, forever; who may read the diff is decided
19// before the cache is asked, and what is cached is runs of classes, never the
20// text.
21//
22// Concurrent misses for one key share a single lexing: the first caller
23// lexes, the others wait for it (or for their own ctx), as the figures of the
24// home page do (usecase statsCache). A lexing that gave nothing (no free
25// lexing slot, out of time or text, a failed lexer) is not kept: the next
26// request tries again, and the callers that waited show the file plain.
27//
28// An entry over a quarter of the budget is not kept (one big file would push
29// out most of the others).
30//
31// A nil *hlCache is a valid one that keeps nothing.
32type hlCache struct {
33 mu sync.Mutex
34 budget int
35 size int
36 lru *list.List // of *hlEntry, most recently used first
37 byKey map[string]*list.Element
38 flight map[string]*hlFlight
39}
40
41type hlEntry struct {
42 key string
43 data *hlData
44 size int
45}
46
47// hlFlight is a lexing in progress; done is closed when data is set.
48type hlFlight struct {
49 done chan struct{}
50 data *hlData
51 waiters int // callers that joined it, for the tests; guarded by hlCache.mu
52}
53
54func newHLCache(budget int) *hlCache {
55 return &hlCache{
56 budget: budget, lru: list.New(),
57 byKey: map[string]*list.Element{}, flight: map[string]*hlFlight{},
58 }
59}
60
61// entrySize is what an entry weighs against the budget: its data and its key.
62func entrySize(key string, d *hlData) int { return d.size() + len(key) + 64 }
63
64// load returns the colours under key: cached, or from build, which runs once
65// however many callers ask at the same time, in the goroutine of the first.
66// build returns nil for no colours. An empty key is not cached: build runs.
67func (c *hlCache) load(ctx context.Context, key string, build func() *hlData) *hlData {
68 if c == nil || key == "" {
69 return build()
70 }
71 c.mu.Lock()
72 if el, ok := c.byKey[key]; ok {
73 c.lru.MoveToFront(el)
74 d := el.Value.(*hlEntry).data
75 c.mu.Unlock()
76 return d
77 }
78 if f, ok := c.flight[key]; ok {
79 f.waiters++
80 c.mu.Unlock()
81 select {
82 case <-f.done:
83 return f.data
84 case <-ctx.Done():
85 return nil
86 }
87 }
88 f := &hlFlight{done: make(chan struct{})}
89 c.flight[key] = f
90 c.mu.Unlock()
91
92 // Whatever build does, the flight ends: the callers that wait are freed,
93 // by a panic too (which then goes on up to the server's recovery).
94 defer func() {
95 c.mu.Lock()
96 delete(c.flight, key)
97 if f.data != nil {
98 c.putLocked(key, f.data)
99 }
100 c.mu.Unlock()
101 close(f.done)
102 }()
103 f.data = build()
104 return f.data
105}
106
107// putLocked stores colours, evicting the least recently used ones to stay in
108// budget. Colours over a quarter of the budget are not stored.
109func (c *hlCache) putLocked(key string, d *hlData) {
110 n := entrySize(key, d)
111 if n > c.budget/4 {
112 return
113 }
114 if el, ok := c.byKey[key]; ok {
115 e := el.Value.(*hlEntry)
116 c.size += n - e.size
117 e.data, e.size = d, n
118 c.lru.MoveToFront(el)
119 } else {
120 c.byKey[key] = c.lru.PushFront(&hlEntry{key: key, data: d, size: n})
121 c.size += n
122 }
123 for c.size > c.budget {
124 el := c.lru.Back()
125 e := el.Value.(*hlEntry)
126 c.lru.Remove(el)
127 delete(c.byKey, e.key)
128 c.size -= e.size
129 }
130}