1// SPDX-License-Identifier: MIT
2
3package git
4
5import (
6 "math"
7 "math/bits"
8 "sync/atomic"
9)
10
11// headerCache remembers the type and the result size of the deltified
12// objects of one pack, by entry offset. Finding that size means inflating the
13// start of the delta, which dominated listing a directory with the size of
14// each file (ObjectHeader per entry).
15//
16// A pack never changes, so an entry never goes stale and nothing invalidates
17// it; the cache goes away with the pack. It is a fixed array of slots in
18// which an offset has two places (a 2-way set: the slot its hash picks and
19// the neighbour), and a newer entry replaces one of the two when both are
20// taken. The memory is bounded by construction (headerSlotBytes per slot, at
21// most maxHeaderSlots slots per pack, allocated at the first deltified
22// header), a hit costs a hash and a few atomic loads and allocates nothing,
23// and there is no lock, no eviction list and no allocation per entry. One way
24// only made two hot offsets that collide evict each other on every lookup:
25// 4,096 deltified headers read in rotation on lazygit (65,536 slots) cost
26// 334 ns each with one way and 55 ns with two. A sync.Map would allocate on every
27// store and would need its own bound and eviction; a mutex-protected map would
28// serialize the readers.
29//
30// Each slot is a seqlock made of atomics (so it is also clean for the race
31// detector): a writer makes seq odd, writes the fields, makes it even again;
32// a reader that sees an odd seq, or a seq that moved, takes a miss. A writer
33// that finds the slot busy gives up: this is a cache.
34type headerCache struct {
35 slots []headerSlot
36 shift uint // 64 - log2(len(slots))
37}
38
39type headerSlot struct {
40 seq atomic.Uint64
41 off atomic.Uint64 // entry offset + 1; 0 is an empty slot
42 val atomic.Uint64 // size<<3 | type
43}
44
45const (
46 headerSlotBytes = 24
47 // maxHeaderSlots bounds a pack to 1.5 MiB of cache. A pack with more
48 // deltified objects than that keeps the most recent ones per slot.
49 maxHeaderSlots = 1 << 16
50 minHeaderSlots = 64 // at least 2, a set is two slots
51 // maxCachedSize is the largest size a slot holds (3 bits go to the type).
52 maxCachedSize = 1 << 60
53)
54
55// newHeaderCache sizes the table for a pack of objects objects: the next
56// power of two, within the bounds.
57func newHeaderCache(objects uint32) *headerCache {
58 n := min(max(int(objects), minHeaderSlots), maxHeaderSlots)
59 n = 1 << bits.Len(uint(n-1)) // round up to a power of two
60 return &headerCache{slots: make([]headerSlot, n), shift: uint(64 - bits.TrailingZeros(uint(n)))}
61}
62
63// index returns the position of the first of the two places of off.
64func (c *headerCache) index(off uint64) (first int, h uint64) {
65 h = off * 0x9e3779b97f4a7c15
66 return int(h >> c.shift), h
67}
68
69func (s *headerSlot) read(off uint64) (v uint64, ok bool) {
70 seq := s.seq.Load()
71 if seq&1 != 0 {
72 return 0, false
73 }
74 o, v := s.off.Load(), s.val.Load()
75 if o != off+1 || s.seq.Load() != seq {
76 return 0, false
77 }
78 return v, true
79}
80
81func (c *headerCache) get(off uint64) (Type, int64, bool) {
82 if off == math.MaxUint64 { // off+1 would wrap to the empty marker
83 return 0, 0, false
84 }
85 i, _ := c.index(off)
86 if v, ok := c.slots[i].read(off); ok {
87 return Type(v & 7), int64(v >> 3), true
88 }
89 if v, ok := c.slots[i^1].read(off); ok {
90 return Type(v & 7), int64(v >> 3), true
91 }
92 return 0, 0, false
93}
94
95func (c *headerCache) put(off uint64, typ Type, size int64) {
96 if size < 0 || size >= maxCachedSize || off == math.MaxUint64 {
97 return
98 }
99 i, h := c.index(off)
100 // An empty place first; else a pseudo-random one of the two.
101 s := &c.slots[i]
102 if s.off.Load() != 0 {
103 if t := &c.slots[i^1]; t.off.Load() == 0 || h&(1<<20) != 0 {
104 s = t
105 }
106 }
107 seq := s.seq.Load()
108 if seq&1 != 0 || !s.seq.CompareAndSwap(seq, seq+1) {
109 return
110 }
111 s.off.Store(off + 1)
112 s.val.Store(uint64(size)<<3 | uint64(typ))
113 s.seq.Store(seq + 2)
114}