cache.go RawHistoryFolder

1// SPDX-License-Identifier: MIT
2
3package git
4
5import "sync"
6
7// cacheShards is the number of independently locked LRU lists.
8const cacheShards = 8
9
10type cacheKey struct {
11	pack uint32
12	off  uint64
13}
14
15type cacheEntry struct {
16	key        cacheKey
17	typ        Type
18	data       []byte // immutable once cached
19	prev, next *cacheEntry
20}
21
22// deltaCache is an LRU cache of delta bases bounded in bytes. Cached slices
23// are never modified or recycled, so a reader may keep using one after it is
24// evicted.
25type deltaCache struct {
26	shards [cacheShards]cacheShard
27}
28
29type cacheShard struct {
30	mu         sync.Mutex
31	m          map[cacheKey]*cacheEntry
32	head, tail *cacheEntry // head is the most recently used
33	bytes      int64
34	budget     int64
35}
36
37func newDeltaCache(budget int64) *deltaCache {
38	c := &deltaCache{}
39	for i := range c.shards {
40		c.shards[i].budget = budget / cacheShards
41		c.shards[i].m = make(map[cacheKey]*cacheEntry)
42	}
43	return c
44}
45
46func (c *deltaCache) shard(k cacheKey) *cacheShard {
47	h := uint64(k.pack)*0x9e3779b97f4a7c15 ^ k.off*0xff51afd7ed558ccd
48	return &c.shards[(h>>32)%cacheShards]
49}
50
51func (c *deltaCache) get(k cacheKey) (Type, []byte, bool) {
52	s := c.shard(k)
53	if s.budget <= 0 {
54		return 0, nil, false
55	}
56	s.mu.Lock()
57	e := s.m[k]
58	if e == nil {
59		s.mu.Unlock()
60		return 0, nil, false
61	}
62	s.moveFront(e)
63	typ, data := e.typ, e.data
64	s.mu.Unlock()
65	return typ, data, true
66}
67
68// fits reports whether an object of n bytes can be cached.
69func (c *deltaCache) fits(n int) bool {
70	return int64(n)+64 <= c.shards[0].budget
71}
72
73// putOwned stores data, which the caller must not modify afterwards.
74func (c *deltaCache) putOwned(k cacheKey, typ Type, data []byte) {
75	s := c.shard(k)
76	n := int64(len(data)) + 64
77	if n > s.budget {
78		return
79	}
80	cp := data
81	s.mu.Lock()
82	defer s.mu.Unlock()
83	if e := s.m[k]; e != nil {
84		s.moveFront(e)
85		return
86	}
87	e := &cacheEntry{key: k, typ: typ, data: cp}
88	s.m[k] = e
89	s.pushFront(e)
90	s.bytes += n
91	for s.bytes > s.budget && s.tail != nil {
92		old := s.tail
93		s.unlink(old)
94		delete(s.m, old.key)
95		s.bytes -= int64(len(old.data)) + 64
96	}
97}
98
99func (s *cacheShard) unlink(e *cacheEntry) {
100	if e.prev != nil {
101		e.prev.next = e.next
102	} else {
103		s.head = e.next
104	}
105	if e.next != nil {
106		e.next.prev = e.prev
107	} else {
108		s.tail = e.prev
109	}
110	e.prev, e.next = nil, nil
111}
112
113func (s *cacheShard) pushFront(e *cacheEntry) {
114	e.next = s.head
115	if s.head != nil {
116		s.head.prev = e
117	}
118	s.head = e
119	if s.tail == nil {
120		s.tail = e
121	}
122}
123
124func (s *cacheShard) moveFront(e *cacheEntry) {
125	if s.head == e {
126		return
127	}
128	s.unlink(e)
129	s.pushFront(e)
130}