1// Copyright 2016 Keybase Inc. All rights reserved. 2// Use of this source code is governed by a BSD 3// license that can be found in the LICENSE file. 4 5package libkbfs 6 7import ( 8 "sync" 9 10 lru "github.com/hashicorp/golang-lru" 11 "github.com/keybase/client/go/kbfs/kbfsmd" 12 "github.com/keybase/client/go/kbfs/tlf" 13 "github.com/keybase/client/go/kbfs/tlfhandle" 14 "github.com/keybase/client/go/protocol/keybase1" 15 "github.com/pkg/errors" 16) 17 18// MDCacheStandard implements a simple LRU cache for per-folder 19// metadata objects. 20type MDCacheStandard struct { 21 // lock protects `lru` from atomic operations that need atomicity 22 // across multiple `lru` calls. 23 lock sync.RWMutex 24 lru *lru.Cache 25 idLRU *lru.Cache 26 27 nextMDLRU *lru.Cache 28} 29 30type mdCacheKey struct { 31 tlf tlf.ID 32 rev kbfsmd.Revision 33 bid kbfsmd.BranchID 34} 35 36const ( 37 defaultMDCacheCapacity = 5000 38 defaultNextMDCacheCapacity = 100 39) 40 41// NewMDCacheStandard constructs a new MDCacheStandard using the given 42// cache capacity. 43func NewMDCacheStandard(capacity int) *MDCacheStandard { 44 mdLRU, err := lru.New(capacity) 45 if err != nil { 46 return nil 47 } 48 idLRU, err := lru.New(capacity) 49 if err != nil { 50 return nil 51 } 52 // Hard-code the nextMD cache size to something small, since only 53 // one entry is used for each revoked device we need to verify. 54 nextMDLRU, err := lru.New(defaultNextMDCacheCapacity) 55 if err != nil { 56 return nil 57 } 58 return &MDCacheStandard{lru: mdLRU, idLRU: idLRU, nextMDLRU: nextMDLRU} 59} 60 61// Get implements the MDCache interface for MDCacheStandard. 62func (md *MDCacheStandard) Get(tlf tlf.ID, rev kbfsmd.Revision, bid kbfsmd.BranchID) ( 63 ImmutableRootMetadata, error) { 64 md.lock.RLock() 65 defer md.lock.RUnlock() 66 key := mdCacheKey{tlf, rev, bid} 67 if tmp, ok := md.lru.Get(key); ok { 68 if rmd, ok := tmp.(ImmutableRootMetadata); ok { 69 return rmd, nil 70 } 71 return ImmutableRootMetadata{}, BadMDError{tlf} 72 } 73 return ImmutableRootMetadata{}, NoSuchMDError{tlf, rev, bid} 74} 75 76// Put implements the MDCache interface for MDCacheStandard. 77func (md *MDCacheStandard) Put(rmd ImmutableRootMetadata) error { 78 md.lock.Lock() 79 defer md.lock.Unlock() 80 key := mdCacheKey{rmd.TlfID(), rmd.Revision(), rmd.BID()} 81 if _, ok := md.lru.Get(key); ok { 82 // Don't overwrite the cache. In the case that `rmd` is 83 // different from what's in the cache, we require that upper 84 // layers manage the cache explicitly by deleting or replacing 85 // it explicitly. 86 return nil 87 } 88 md.lru.Add(key, rmd) 89 return nil 90} 91 92// Delete implements the MDCache interface for MDCacheStandard. 93func (md *MDCacheStandard) Delete(tlf tlf.ID, rev kbfsmd.Revision, 94 bid kbfsmd.BranchID) { 95 md.lock.Lock() 96 defer md.lock.Unlock() 97 key := mdCacheKey{tlf, rev, bid} 98 md.lru.Remove(key) 99} 100 101// Replace implements the MDCache interface for MDCacheStandard. 102func (md *MDCacheStandard) Replace(newRmd ImmutableRootMetadata, 103 oldBID kbfsmd.BranchID) error { 104 md.lock.Lock() 105 defer md.lock.Unlock() 106 oldKey := mdCacheKey{newRmd.TlfID(), newRmd.Revision(), oldBID} 107 newKey := mdCacheKey{newRmd.TlfID(), newRmd.Revision(), newRmd.BID()} 108 // TODO: implement our own LRU where we can replace the old data 109 // without affecting the LRU status. 110 md.lru.Remove(oldKey) 111 md.lru.Add(newKey, newRmd) 112 return nil 113} 114 115// MarkPutToServer implements the MDCache interface for 116// MDCacheStandard. 117func (md *MDCacheStandard) MarkPutToServer( 118 tlf tlf.ID, rev kbfsmd.Revision, bid kbfsmd.BranchID) { 119 md.lock.Lock() 120 defer md.lock.Unlock() 121 key := mdCacheKey{tlf, rev, bid} 122 tmp, ok := md.lru.Get(key) 123 if !ok { 124 return 125 } 126 rmd, ok := tmp.(ImmutableRootMetadata) 127 if !ok { 128 return 129 } 130 rmd.putToServer = true 131 md.lru.Add(key, rmd) 132} 133 134// GetIDForHandle implements the MDCache interface for 135// MDCacheStandard. 136func (md *MDCacheStandard) GetIDForHandle(handle *tlfhandle.Handle) (tlf.ID, error) { 137 md.lock.RLock() 138 defer md.lock.RUnlock() 139 key := handle.GetCanonicalPath() 140 tmp, ok := md.idLRU.Get(key) 141 if !ok { 142 return tlf.NullID, NoSuchTlfIDError{handle} 143 } 144 id, ok := tmp.(tlf.ID) 145 if !ok { 146 return tlf.NullID, errors.Errorf("Bad ID for handle %s", key) 147 } 148 return id, nil 149} 150 151// PutIDForHandle implements the MDCache interface for 152// MDCacheStandard. 153func (md *MDCacheStandard) PutIDForHandle(handle *tlfhandle.Handle, id tlf.ID) error { 154 md.lock.RLock() 155 defer md.lock.RUnlock() 156 key := handle.GetCanonicalPath() 157 md.idLRU.Add(key, id) 158 return nil 159} 160 161// ChangeHandleForID implements the MDCache interface for 162// MDCacheStandard. 163func (md *MDCacheStandard) ChangeHandleForID( 164 oldHandle *tlfhandle.Handle, newHandle *tlfhandle.Handle) { 165 md.lock.RLock() 166 defer md.lock.RUnlock() 167 oldKey := oldHandle.GetCanonicalPath() 168 tmp, ok := md.idLRU.Get(oldKey) 169 if !ok { 170 return 171 } 172 md.idLRU.Remove(oldKey) 173 newKey := newHandle.GetCanonicalPath() 174 md.idLRU.Add(newKey, tmp) 175} 176 177type mdcacheNextMDKey struct { 178 tlfID tlf.ID 179 rootSeqno keybase1.Seqno 180} 181 182type mdcacheNextMDVal struct { 183 nextKbfsRoot *kbfsmd.MerkleRoot 184 nextMerkleNodes [][]byte 185 nextRootSeqno keybase1.Seqno 186} 187 188// GetNextMD implements the MDCache interface for MDCacheStandard. 189func (md *MDCacheStandard) GetNextMD(tlfID tlf.ID, rootSeqno keybase1.Seqno) ( 190 nextKbfsRoot *kbfsmd.MerkleRoot, nextMerkleNodes [][]byte, 191 nextRootSeqno keybase1.Seqno, err error) { 192 key := mdcacheNextMDKey{tlfID, rootSeqno} 193 tmp, ok := md.nextMDLRU.Get(key) 194 if !ok { 195 return nil, nil, 0, NextMDNotCachedError{tlfID, rootSeqno} 196 } 197 val, ok := tmp.(mdcacheNextMDVal) 198 if !ok { 199 return nil, nil, 0, errors.Errorf( 200 "Bad next MD for %s, seqno=%d", tlfID, rootSeqno) 201 } 202 return val.nextKbfsRoot, val.nextMerkleNodes, val.nextRootSeqno, nil 203} 204 205// PutNextMD implements the MDCache interface for MDCacheStandard. 206func (md *MDCacheStandard) PutNextMD( 207 tlfID tlf.ID, rootSeqno keybase1.Seqno, nextKbfsRoot *kbfsmd.MerkleRoot, 208 nextMerkleNodes [][]byte, nextRootSeqno keybase1.Seqno) error { 209 key := mdcacheNextMDKey{tlfID, rootSeqno} 210 val := mdcacheNextMDVal{nextKbfsRoot, nextMerkleNodes, nextRootSeqno} 211 md.nextMDLRU.Add(key, val) 212 return nil 213} 214