1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
/*
Copyright The containerd Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
package cacheutil
import (
"sync"
"github.com/golang/groupcache/lru"
)
// LRUCache is "groupcache/lru"-like cache. The difference is that "groupcache/lru" immediately
// finalizes theevicted contents using OnEvicted callback but our version strictly tracks the
// reference counts of contents and calls OnEvicted when nobody refers to the evicted contents.
type LRUCache struct {
cache *lru.Cache
mu sync.Mutex
// OnEvicted optionally specifies a callback function to be
// executed when an entry is purged from the cache.
OnEvicted func(key string, value interface{})
}
// NewLRUCache creates new lru cache.
func NewLRUCache(maxEntries int) *LRUCache {
inner := lru.New(maxEntries)
inner.OnEvicted = func(key lru.Key, value interface{}) {
// Decrease the ref count incremented in Add().
// When nobody refers to this value, this value will be finalized via refCounter.
value.(*refCounter).finalize()
}
return &LRUCache{
cache: inner,
}
}
// Get retrieves the specified object from the cache and increments the reference counter of the
// target content. Client must call `done` callback to decrease the reference count when the value
// will no longer be used.
func (c *LRUCache) Get(key string) (value interface{}, done func(), ok bool) {
c.mu.Lock()
defer c.mu.Unlock()
o, ok := c.cache.Get(key)
if !ok {
return nil, nil, false
}
rc := o.(*refCounter)
rc.inc()
return rc.v, c.decreaseOnceFunc(rc), true
}
// Add adds object to the cache and returns the cached contents with incrementing the reference count.
// If the specified content already exists in the cache, this sets `added` to false and returns
// "already cached" content (i.e. doesn't replace the content with the new one). Client must call
// `done` callback to decrease the counter when the value will no longer be used.
func (c *LRUCache) Add(key string, value interface{}) (cachedValue interface{}, done func(), added bool) {
c.mu.Lock()
defer c.mu.Unlock()
if o, ok := c.cache.Get(key); ok {
rc := o.(*refCounter)
rc.inc()
return rc.v, c.decreaseOnceFunc(rc), false
}
rc := &refCounter{
key: key,
v: value,
onEvicted: c.OnEvicted,
}
rc.initialize() // Keep this object having at least 1 ref count (will be decreased in OnEviction)
rc.inc() // The client references this object (will be decreased on "done")
c.cache.Add(key, rc)
return rc.v, c.decreaseOnceFunc(rc), true
}
// Remove removes the specified contents from the cache. OnEvicted callback will be called when
// nobody refers to the removed content.
func (c *LRUCache) Remove(key string) {
c.mu.Lock()
defer c.mu.Unlock()
c.cache.Remove(key)
}
func (c *LRUCache) decreaseOnceFunc(rc *refCounter) func() {
var once sync.Once
return func() {
c.mu.Lock()
defer c.mu.Unlock()
once.Do(func() { rc.dec() })
}
}
type refCounter struct {
onEvicted func(key string, value interface{})
key string
v interface{}
refCounts int64
mu sync.Mutex
initializeOnce sync.Once
finalizeOnce sync.Once
}
func (r *refCounter) inc() {
r.mu.Lock()
defer r.mu.Unlock()
r.refCounts++
}
func (r *refCounter) dec() {
r.mu.Lock()
defer r.mu.Unlock()
r.refCounts--
if r.refCounts <= 0 && r.onEvicted != nil {
// nobody will refer this object
r.onEvicted(r.key, r.v)
}
}
func (r *refCounter) initialize() {
r.initializeOnce.Do(func() { r.inc() })
}
func (r *refCounter) finalize() {
r.finalizeOnce.Do(func() { r.dec() })
}
|
