aboutsummaryrefslogtreecommitdiffstats
path: root/plumbing/cache
diff options
context:
space:
mode:
Diffstat (limited to 'plumbing/cache')
-rw-r--r--plumbing/cache/buffer_lru.go98
-rw-r--r--plumbing/cache/buffer_test.go151
-rw-r--r--plumbing/cache/common.go13
-rw-r--r--plumbing/cache/object_lru.go24
-rw-r--r--plumbing/cache/object_test.go19
5 files changed, 293 insertions, 12 deletions
diff --git a/plumbing/cache/buffer_lru.go b/plumbing/cache/buffer_lru.go
new file mode 100644
index 0000000..acaf195
--- /dev/null
+++ b/plumbing/cache/buffer_lru.go
@@ -0,0 +1,98 @@
+package cache
+
+import (
+ "container/list"
+ "sync"
+)
+
+// BufferLRU implements an object cache with an LRU eviction policy and a
+// maximum size (measured in object size).
+type BufferLRU struct {
+ MaxSize FileSize
+
+ actualSize FileSize
+ ll *list.List
+ cache map[int64]*list.Element
+ mut sync.Mutex
+}
+
+// NewBufferLRU creates a new BufferLRU with the given maximum size. The maximum
+// size will never be exceeded.
+func NewBufferLRU(maxSize FileSize) *BufferLRU {
+ return &BufferLRU{MaxSize: maxSize}
+}
+
+// NewBufferLRUDefault creates a new BufferLRU with the default cache size.
+func NewBufferLRUDefault() *BufferLRU {
+ return &BufferLRU{MaxSize: DefaultMaxSize}
+}
+
+type buffer struct {
+ Key int64
+ Slice []byte
+}
+
+// Put puts a buffer into the cache. If the buffer is already in the cache, it
+// will be marked as used. Otherwise, it will be inserted. A buffers might
+// be evicted to make room for the new one.
+func (c *BufferLRU) Put(key int64, slice []byte) {
+ c.mut.Lock()
+ defer c.mut.Unlock()
+
+ if c.cache == nil {
+ c.actualSize = 0
+ c.cache = make(map[int64]*list.Element, 1000)
+ c.ll = list.New()
+ }
+
+ bufSize := FileSize(len(slice))
+ if ee, ok := c.cache[key]; ok {
+ oldBuf := ee.Value.(buffer)
+ // in this case bufSize is a delta: new size - old size
+ bufSize -= FileSize(len(oldBuf.Slice))
+ c.ll.MoveToFront(ee)
+ ee.Value = buffer{key, slice}
+ } else {
+ if bufSize > c.MaxSize {
+ return
+ }
+ ee := c.ll.PushFront(buffer{key, slice})
+ c.cache[key] = ee
+ }
+
+ c.actualSize += bufSize
+ for c.actualSize > c.MaxSize {
+ last := c.ll.Back()
+ lastObj := last.Value.(buffer)
+ lastSize := FileSize(len(lastObj.Slice))
+
+ c.ll.Remove(last)
+ delete(c.cache, lastObj.Key)
+ c.actualSize -= lastSize
+ }
+}
+
+// Get returns a buffer by its key. It marks the buffer as used. If the buffer
+// is not in the cache, (nil, false) will be returned.
+func (c *BufferLRU) Get(key int64) ([]byte, bool) {
+ c.mut.Lock()
+ defer c.mut.Unlock()
+
+ ee, ok := c.cache[key]
+ if !ok {
+ return nil, false
+ }
+
+ c.ll.MoveToFront(ee)
+ return ee.Value.(buffer).Slice, true
+}
+
+// Clear the content of this buffer cache.
+func (c *BufferLRU) Clear() {
+ c.mut.Lock()
+ defer c.mut.Unlock()
+
+ c.ll = nil
+ c.cache = nil
+ c.actualSize = 0
+}
diff --git a/plumbing/cache/buffer_test.go b/plumbing/cache/buffer_test.go
new file mode 100644
index 0000000..3e3adc2
--- /dev/null
+++ b/plumbing/cache/buffer_test.go
@@ -0,0 +1,151 @@
+package cache
+
+import (
+ "bytes"
+ "sync"
+
+ . "gopkg.in/check.v1"
+)
+
+type BufferSuite struct {
+ c map[string]Buffer
+ aBuffer []byte
+ bBuffer []byte
+ cBuffer []byte
+ dBuffer []byte
+ eBuffer []byte
+}
+
+var _ = Suite(&BufferSuite{})
+
+func (s *BufferSuite) SetUpTest(c *C) {
+ s.aBuffer = []byte("a")
+ s.bBuffer = []byte("bbb")
+ s.cBuffer = []byte("c")
+ s.dBuffer = []byte("d")
+ s.eBuffer = []byte("ee")
+
+ s.c = make(map[string]Buffer)
+ s.c["two_bytes"] = NewBufferLRU(2 * Byte)
+ s.c["default_lru"] = NewBufferLRUDefault()
+}
+
+func (s *BufferSuite) TestPutSameBuffer(c *C) {
+ for _, o := range s.c {
+ o.Put(1, s.aBuffer)
+ o.Put(1, s.aBuffer)
+ _, ok := o.Get(1)
+ c.Assert(ok, Equals, true)
+ }
+}
+
+func (s *ObjectSuite) TestPutSameBufferWithDifferentSize(c *C) {
+ aBuffer := []byte("a")
+ bBuffer := []byte("bbb")
+ cBuffer := []byte("ccccc")
+ dBuffer := []byte("ddddddd")
+
+ cache := NewBufferLRU(7 * Byte)
+ cache.Put(1, aBuffer)
+ cache.Put(1, bBuffer)
+ cache.Put(1, cBuffer)
+ cache.Put(1, dBuffer)
+
+ c.Assert(cache.MaxSize, Equals, 7*Byte)
+ c.Assert(cache.actualSize, Equals, 7*Byte)
+ c.Assert(cache.ll.Len(), Equals, 1)
+
+ buf, ok := cache.Get(1)
+ c.Assert(bytes.Equal(buf, dBuffer), Equals, true)
+ c.Assert(FileSize(len(buf)), Equals, 7*Byte)
+ c.Assert(ok, Equals, true)
+}
+
+func (s *BufferSuite) TestPutBigBuffer(c *C) {
+ for _, o := range s.c {
+ o.Put(1, s.bBuffer)
+ _, ok := o.Get(2)
+ c.Assert(ok, Equals, false)
+ }
+}
+
+func (s *BufferSuite) TestPutCacheOverflow(c *C) {
+ // this test only works with an specific size
+ o := s.c["two_bytes"]
+
+ o.Put(1, s.aBuffer)
+ o.Put(2, s.cBuffer)
+ o.Put(3, s.dBuffer)
+
+ obj, ok := o.Get(1)
+ c.Assert(ok, Equals, false)
+ c.Assert(obj, IsNil)
+ obj, ok = o.Get(2)
+ c.Assert(ok, Equals, true)
+ c.Assert(obj, NotNil)
+ obj, ok = o.Get(3)
+ c.Assert(ok, Equals, true)
+ c.Assert(obj, NotNil)
+}
+
+func (s *BufferSuite) TestEvictMultipleBuffers(c *C) {
+ o := s.c["two_bytes"]
+
+ o.Put(1, s.cBuffer)
+ o.Put(2, s.dBuffer) // now cache is full with two objects
+ o.Put(3, s.eBuffer) // this put should evict all previous objects
+
+ obj, ok := o.Get(1)
+ c.Assert(ok, Equals, false)
+ c.Assert(obj, IsNil)
+ obj, ok = o.Get(2)
+ c.Assert(ok, Equals, false)
+ c.Assert(obj, IsNil)
+ obj, ok = o.Get(3)
+ c.Assert(ok, Equals, true)
+ c.Assert(obj, NotNil)
+}
+
+func (s *BufferSuite) TestClear(c *C) {
+ for _, o := range s.c {
+ o.Put(1, s.aBuffer)
+ o.Clear()
+ obj, ok := o.Get(1)
+ c.Assert(ok, Equals, false)
+ c.Assert(obj, IsNil)
+ }
+}
+
+func (s *BufferSuite) TestConcurrentAccess(c *C) {
+ for _, o := range s.c {
+ var wg sync.WaitGroup
+
+ for i := 0; i < 1000; i++ {
+ wg.Add(3)
+ go func(i int) {
+ o.Put(int64(i), []byte{00})
+ wg.Done()
+ }(i)
+
+ go func(i int) {
+ if i%30 == 0 {
+ o.Clear()
+ }
+ wg.Done()
+ }(i)
+
+ go func(i int) {
+ o.Get(int64(i))
+ wg.Done()
+ }(i)
+ }
+
+ wg.Wait()
+ }
+}
+
+func (s *BufferSuite) TestDefaultLRU(c *C) {
+ defaultLRU := s.c["default_lru"].(*BufferLRU)
+
+ c.Assert(defaultLRU.MaxSize, Equals, DefaultMaxSize)
+}
diff --git a/plumbing/cache/common.go b/plumbing/cache/common.go
index e77baf0..2b7f36a 100644
--- a/plumbing/cache/common.go
+++ b/plumbing/cache/common.go
@@ -24,3 +24,16 @@ type Object interface {
// Clear clears every object from the cache.
Clear()
}
+
+// Buffer is an interface to a buffer cache.
+type Buffer interface {
+ // Put puts a buffer into the cache. If the buffer is already in the cache,
+ // it will be marked as used. Otherwise, it will be inserted. Buffer might
+ // be evicted to make room for the new one.
+ Put(key int64, slice []byte)
+ // Get returns a buffer by its key. It marks the buffer as used. If the
+ // buffer is not in the cache, (nil, false) will be returned.
+ Get(key int64) ([]byte, bool)
+ // Clear clears every object from the cache.
+ Clear()
+}
diff --git a/plumbing/cache/object_lru.go b/plumbing/cache/object_lru.go
index 0494539..53d8b02 100644
--- a/plumbing/cache/object_lru.go
+++ b/plumbing/cache/object_lru.go
@@ -42,20 +42,24 @@ func (c *ObjectLRU) Put(obj plumbing.EncodedObject) {
c.ll = list.New()
}
+ objSize := FileSize(obj.Size())
key := obj.Hash()
if ee, ok := c.cache[key]; ok {
+ oldObj := ee.Value.(plumbing.EncodedObject)
+ // in this case objSize is a delta: new size - old size
+ objSize -= FileSize(oldObj.Size())
c.ll.MoveToFront(ee)
ee.Value = obj
- return
- }
-
- objSize := FileSize(obj.Size())
-
- if objSize > c.MaxSize {
- return
+ } else {
+ if objSize > c.MaxSize {
+ return
+ }
+ ee := c.ll.PushFront(obj)
+ c.cache[key] = ee
}
- for c.actualSize+objSize > c.MaxSize {
+ c.actualSize += objSize
+ for c.actualSize > c.MaxSize {
last := c.ll.Back()
lastObj := last.Value.(plumbing.EncodedObject)
lastSize := FileSize(lastObj.Size())
@@ -64,10 +68,6 @@ func (c *ObjectLRU) Put(obj plumbing.EncodedObject) {
delete(c.cache, lastObj.Hash())
c.actualSize -= lastSize
}
-
- ee := c.ll.PushFront(obj)
- c.cache[key] = ee
- c.actualSize += objSize
}
// Get returns an object by its hash. It marks the object as used. If the object
diff --git a/plumbing/cache/object_test.go b/plumbing/cache/object_test.go
index ac3f0a3..b3e5f79 100644
--- a/plumbing/cache/object_test.go
+++ b/plumbing/cache/object_test.go
@@ -45,6 +45,25 @@ func (s *ObjectSuite) TestPutSameObject(c *C) {
}
}
+func (s *ObjectSuite) TestPutSameObjectWithDifferentSize(c *C) {
+ const hash = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+
+ cache := NewObjectLRU(7 * Byte)
+ cache.Put(newObject(hash, 1*Byte))
+ cache.Put(newObject(hash, 3*Byte))
+ cache.Put(newObject(hash, 5*Byte))
+ cache.Put(newObject(hash, 7*Byte))
+
+ c.Assert(cache.MaxSize, Equals, 7*Byte)
+ c.Assert(cache.actualSize, Equals, 7*Byte)
+ c.Assert(cache.ll.Len(), Equals, 1)
+
+ obj, ok := cache.Get(plumbing.NewHash(hash))
+ c.Assert(obj.Hash(), Equals, plumbing.NewHash(hash))
+ c.Assert(FileSize(obj.Size()), Equals, 7*Byte)
+ c.Assert(ok, Equals, true)
+}
+
func (s *ObjectSuite) TestPutBigObject(c *C) {
for _, o := range s.c {
o.Put(s.bObject)
generated by cgit (git 2.34.1) at 2024-11-10 21:29:55 +0000