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