diff options
-rw-r--r-- | cache/cache.go | 58 | ||||
-rw-r--r-- | cache/cache_test.go | 80 | ||||
-rw-r--r-- | repo.go | 18 |
3 files changed, 156 insertions, 0 deletions
diff --git a/cache/cache.go b/cache/cache.go new file mode 100644 index 0000000..ff2c279 --- /dev/null +++ b/cache/cache.go @@ -0,0 +1,58 @@ +package cache + +import "sync" + +type Cacher interface { + Get(key interface{}) (value []byte, exists bool) + Set(key interface{}, value []byte) + Len() int +} + +type FifoCache struct { + head, tail *fifoCacheEntry + data map[interface{}][]byte + capacity int + mutex sync.RWMutex +} + +type fifoCacheEntry struct { + Key interface{} + Next *fifoCacheEntry +} + +func NewFifoCache(capacity int) *FifoCache { + return &FifoCache{data: make(map[interface{}][]byte, capacity), capacity: capacity} +} + +func (c *FifoCache) Get(key interface{}) (value []byte, exists bool) { + c.mutex.RLock() + defer c.mutex.RUnlock() + value, exists = c.data[key] + return +} + +func (c *FifoCache) Set(key interface{}, value []byte) { + c.mutex.Lock() + defer c.mutex.Unlock() + if len(c.data) == c.capacity { + // Evict first entry + evicted := c.head + c.head = evicted.Next + delete(c.data, evicted.Key) + } + entry := &fifoCacheEntry{Key: key} + if c.head == nil { + c.head = entry + } + if c.tail == nil { + c.tail = entry + } else { + c.tail.Next = entry + c.tail = entry + } + c.data[key] = value +} + +func (c *FifoCache) Len() int { + return len(c.data) +} diff --git a/cache/cache_test.go b/cache/cache_test.go new file mode 100644 index 0000000..6b84b79 --- /dev/null +++ b/cache/cache_test.go @@ -0,0 +1,80 @@ +package cache + +import ( + "bytes" + "testing" +) + +func TestFifoChunkCache(t *testing.T) { + var v []byte + var e bool + var cache Cacher = NewFifoCache(3) + k0 := 0 + k1 := 1 + k2 := 2 + k3 := 3 + v0 := []byte{'0'} + v1 := []byte{'1'} + v2 := []byte{'2'} + v3 := []byte{'3'} + + if cache.Len() != 0 { + t.Fatal("Cache should be of size 0") + } + + v, e = cache.Get(k0) + if e { + t.Fatal("There should not be any value") + } + + cache.Set(k0, v0) + cache.Set(k1, v1) + cache.Set(k2, v2) + + if cache.Len() != 3 { + t.Fatal("Cache should be of size 3") + } + + v, e = cache.Get(k0) + if !e { + t.Fatal("Value should exist for k0") + } + if bytes.Compare(v, v0) != 0 { + t.Fatal("Value for k0 does not match") + } + + cache.Set(k3, v3) + + if cache.Len() != 3 { + t.Fatal("Cache should still be of size 3") + } + + v, e = cache.Get(k0) + if e { + t.Fatal("Value should not exist for k0") + } + + v, e = cache.Get(k1) + if !e { + t.Fatal("Value should exist for k1") + } + if bytes.Compare(v, v1) != 0 { + t.Fatal("Value for k1 does not match") + } + + v, e = cache.Get(k2) + if !e { + t.Fatal("Value should exist for k2") + } + if bytes.Compare(v, v2) != 0 { + t.Fatal("Value for k2 does not match") + } + + v, e = cache.Get(k3) + if !e { + t.Fatal("Value should exist for k3") + } + if bytes.Compare(v, v3) != 0 { + t.Fatal("Value for k3 does not match") + } +} @@ -39,6 +39,7 @@ import ( "reflect" "github.com/chmduquesne/rollinghash/rabinkarp64" + "github.com/n-peugnet/dna-backup/cache" ) type FingerprintMap map[uint64]*ChunkId @@ -55,6 +56,7 @@ type Repo struct { patcher Patcher fingerprints FingerprintMap sketches SketchMap + chunkCache cache.Cacher } type File struct { @@ -83,6 +85,7 @@ func NewRepo(path string) *Repo { patcher: &Bsdiff{}, fingerprints: make(FingerprintMap), sketches: make(SketchMap), + chunkCache: cache.NewFifoCache(1000), } } @@ -222,6 +225,21 @@ func loadFileList(path string) []File { return files } +// GetChunk loads a chunk from the repo. +// If the chunk is in cache, get it from cache, else read it from drive. +func (r *Repo) GetChunk(id *ChunkId) *LoadedChunk { + var err error + value, exists := r.chunkCache.Get(id) + if !exists { + value, err = io.ReadAll(id.Reader(r)) + if err != nil { + log.Panicf("Could not read from chunk %d: %s", id, err) + } + r.chunkCache.Set(id, value) + } + return NewLoadedChunk(id, value) +} + func storeChunks(dest string, chunks <-chan []byte) { i := 0 for c := range chunks { |