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	"path/filepath"
9	"sync"
10	"time"
11
12	"github.com/keybase/client/go/kbfs/ioutil"
13	"github.com/keybase/client/go/kbfs/kbfscodec"
14	"github.com/keybase/client/go/kbfs/kbfscrypto"
15	"github.com/keybase/client/go/kbfs/kbfsmd"
16	"github.com/keybase/client/go/kbfs/tlf"
17	"github.com/keybase/client/go/protocol/keybase1"
18	"github.com/pkg/errors"
19	"golang.org/x/net/context"
20)
21
22// mdServerTlfStorage stores an ordered list of metadata IDs for each
23// branch of a single TLF, along with the associated metadata objects,
24// in flat files on disk.
25//
26// The directory layout looks like:
27//
28// dir/md_branch_journals/00..00/EARLIEST
29// dir/md_branch_journals/00..00/LATEST
30// dir/md_branch_journals/00..00/0...001
31// dir/md_branch_journals/00..00/0...002
32// dir/md_branch_journals/00..00/0...fff
33// dir/md_branch_journals/5f..3d/EARLIEST
34// dir/md_branch_journals/5f..3d/LATEST
35// dir/md_branch_journals/5f..3d/0...0ff
36// dir/md_branch_journals/5f..3d/0...100
37// dir/md_branch_journals/5f..3d/0...fff
38// dir/mds/0100/0...01
39// ...
40// dir/mds/01ff/f...ff
41// dir/wkbv3/0100...01
42// ...
43// dir/wkbv3/0100...ff
44// dir/rkbv3/0100...01
45// ...
46// dir/rkbv3/0100...ff
47//
48// Each branch has its own subdirectory with a journal; the journal
49// ordinals are just Revisions, and the journal entries are
50// just MdIDs. (Branches are usually temporary, so no need to splay
51// them.)
52//
53// The Metadata objects are stored separately in dir/mds. Each block
54// has its own subdirectory with its ID as a name. The MD
55// subdirectories are splayed over (# of possible hash types) * 256
56// subdirectories -- one byte for the hash type (currently only one)
57// plus the first byte of the hash data -- using the first four
58// characters of the name to keep the number of directories in dir
59// itself to a manageable number, similar to git.
60//
61// Writer (reader) key bundles for V3 metadata objects are stored
62// separately in dir/wkbv3 (dir/rkbv3). The number of bundles is
63// small, so no need to splay them.
64type mdServerTlfStorage struct {
65	tlfID          tlf.ID
66	codec          kbfscodec.Codec
67	clock          Clock
68	teamMemChecker kbfsmd.TeamMembershipChecker
69	mdVer          kbfsmd.MetadataVer
70	dir            string
71
72	// Protects any IO operations in dir or any of its children,
73	// as well as branchJournals and its contents.
74	lock           sync.RWMutex
75	branchJournals map[kbfsmd.BranchID]mdIDJournal
76}
77
78func makeMDServerTlfStorage(tlfID tlf.ID, codec kbfscodec.Codec,
79	clock Clock, teamMemChecker kbfsmd.TeamMembershipChecker,
80	mdVer kbfsmd.MetadataVer, dir string) *mdServerTlfStorage {
81	journal := &mdServerTlfStorage{
82		tlfID:          tlfID,
83		codec:          codec,
84		clock:          clock,
85		teamMemChecker: teamMemChecker,
86		mdVer:          mdVer,
87		dir:            dir,
88		branchJournals: make(map[kbfsmd.BranchID]mdIDJournal),
89	}
90	return journal
91}
92
93// The functions below are for building various paths.
94
95func (s *mdServerTlfStorage) branchJournalsPath() string {
96	return filepath.Join(s.dir, "md_branch_journals")
97}
98
99func (s *mdServerTlfStorage) mdsPath() string {
100	return filepath.Join(s.dir, "mds")
101}
102
103func (s *mdServerTlfStorage) writerKeyBundleV3Path(
104	id kbfsmd.TLFWriterKeyBundleID) string {
105	return filepath.Join(s.dir, "wkbv3", id.String())
106}
107
108func (s *mdServerTlfStorage) readerKeyBundleV3Path(
109	id kbfsmd.TLFReaderKeyBundleID) string {
110	return filepath.Join(s.dir, "rkbv3", id.String())
111}
112
113func (s *mdServerTlfStorage) mdPath(id kbfsmd.ID) string {
114	idStr := id.String()
115	return filepath.Join(s.mdsPath(), idStr[:4], idStr[4:])
116}
117
118// serializedRMDS is the structure stored in mdPath(id).
119type serializedRMDS struct {
120	EncodedRMDS []byte
121	Timestamp   time.Time
122	Version     kbfsmd.MetadataVer
123}
124
125// getMDReadLocked verifies the MD data (but not the signature) for
126// the given ID and returns it.
127//
128// TODO: Verify signature?
129func (s *mdServerTlfStorage) getMDReadLocked(id kbfsmd.ID) (
130	*RootMetadataSigned, error) {
131	// Read file.
132
133	var srmds serializedRMDS
134	err := kbfscodec.DeserializeFromFile(s.codec, s.mdPath(id), &srmds)
135	if err != nil {
136		return nil, err
137	}
138
139	rmds, err := DecodeRootMetadataSigned(
140		s.codec, s.tlfID, srmds.Version, s.mdVer, srmds.EncodedRMDS,
141		srmds.Timestamp)
142	if err != nil {
143		return nil, err
144	}
145
146	// Check integrity.
147
148	mdID, err := kbfsmd.MakeID(s.codec, rmds.MD)
149	if err != nil {
150		return nil, err
151	}
152
153	if id != mdID {
154		return nil, errors.Errorf(
155			"Metadata ID mismatch: expected %s, got %s",
156			id, mdID)
157	}
158
159	return rmds, nil
160}
161
162func (s *mdServerTlfStorage) putMDLocked(
163	rmds *RootMetadataSigned) (kbfsmd.ID, error) {
164	id, err := kbfsmd.MakeID(s.codec, rmds.MD)
165	if err != nil {
166		return kbfsmd.ID{}, err
167	}
168
169	_, err = s.getMDReadLocked(id)
170	switch {
171	case ioutil.IsNotExist(err):
172		// Continue on.
173	case err != nil:
174		return kbfsmd.ID{}, err
175	default:
176		// Entry exists, so nothing else to do.
177		return id, nil
178	}
179
180	encodedRMDS, err := kbfsmd.EncodeRootMetadataSigned(s.codec, &rmds.RootMetadataSigned)
181	if err != nil {
182		return kbfsmd.ID{}, err
183	}
184
185	srmds := serializedRMDS{
186		EncodedRMDS: encodedRMDS,
187		// Pretend the timestamp went over RPC, so we get the same
188		// resolution level as a real server.
189		Timestamp: keybase1.FromTime(keybase1.ToTime(s.clock.Now())),
190		Version:   rmds.MD.Version(),
191	}
192
193	err = kbfscodec.SerializeToFileIfNotExist(s.codec, srmds, s.mdPath(id))
194	if err != nil {
195		return kbfsmd.ID{}, err
196	}
197
198	return id, nil
199}
200
201func (s *mdServerTlfStorage) getOrCreateBranchJournalLocked(
202	bid kbfsmd.BranchID) (mdIDJournal, error) {
203	j, ok := s.branchJournals[bid]
204	if ok {
205		return j, nil
206	}
207
208	dir := filepath.Join(s.branchJournalsPath(), bid.String())
209	err := ioutil.MkdirAll(dir, 0700)
210	if err != nil {
211		return mdIDJournal{}, err
212	}
213
214	j, err = makeMdIDJournal(s.codec, dir)
215	if err != nil {
216		return mdIDJournal{}, err
217	}
218	s.branchJournals[bid] = j
219	return j, nil
220}
221
222func (s *mdServerTlfStorage) getHeadForTLFReadLocked(bid kbfsmd.BranchID) (
223	rmds *RootMetadataSigned, err error) {
224	j, err := s.getOrCreateBranchJournalLocked(bid)
225	if err != nil {
226		return nil, err
227	}
228	entry, exists, err := j.getLatestEntry()
229	if err != nil {
230		return nil, err
231	}
232	if !exists {
233		return nil, nil
234	}
235	return s.getMDReadLocked(entry.ID)
236}
237
238func (s *mdServerTlfStorage) checkGetParamsReadLocked(
239	ctx context.Context, currentUID keybase1.UID, bid kbfsmd.BranchID) error {
240	mergedMasterHead, err := s.getHeadForTLFReadLocked(kbfsmd.NullBranchID)
241	if err != nil {
242		return kbfsmd.ServerError{Err: err}
243	}
244
245	if mergedMasterHead != nil {
246		extra, err := getExtraMetadata(
247			s.getKeyBundlesReadLocked, mergedMasterHead.MD)
248		if err != nil {
249			return kbfsmd.ServerError{Err: err}
250		}
251		ok, err := isReader(
252			ctx, s.teamMemChecker, currentUID, mergedMasterHead.MD, extra)
253		if err != nil {
254			return kbfsmd.ServerError{Err: err}
255		}
256		if !ok {
257			return kbfsmd.ServerErrorUnauthorized{}
258		}
259	}
260
261	return nil
262}
263
264func (s *mdServerTlfStorage) getRangeReadLocked(
265	ctx context.Context, currentUID keybase1.UID, bid kbfsmd.BranchID,
266	start, stop kbfsmd.Revision) (
267	[]*RootMetadataSigned, error) {
268	err := s.checkGetParamsReadLocked(ctx, currentUID, bid)
269	if err != nil {
270		return nil, err
271	}
272
273	j, ok := s.branchJournals[bid]
274	if !ok {
275		return nil, nil
276	}
277
278	realStart, entries, err := j.getEntryRange(start, stop)
279	if err != nil {
280		return nil, err
281	}
282	var rmdses []*RootMetadataSigned
283	for i, entry := range entries {
284		expectedRevision := realStart + kbfsmd.Revision(i)
285		rmds, err := s.getMDReadLocked(entry.ID)
286		if err != nil {
287			return nil, kbfsmd.ServerError{Err: err}
288		}
289		if expectedRevision != rmds.MD.RevisionNumber() {
290			panic(errors.Errorf("expected revision %v, got %v",
291				expectedRevision, rmds.MD.RevisionNumber()))
292		}
293		rmdses = append(rmdses, rmds)
294	}
295
296	return rmdses, nil
297}
298
299func (s *mdServerTlfStorage) putExtraMetadataLocked(rmds *RootMetadataSigned,
300	extra kbfsmd.ExtraMetadata) error {
301	if extra == nil {
302		return nil
303	}
304
305	extraV3, ok := extra.(*kbfsmd.ExtraMetadataV3)
306	if !ok {
307		return errors.New("Invalid extra metadata")
308	}
309
310	if extraV3.IsWriterKeyBundleNew() {
311		wkbID := rmds.MD.GetTLFWriterKeyBundleID()
312		if wkbID == (kbfsmd.TLFWriterKeyBundleID{}) {
313			panic("writer key bundle ID is empty")
314		}
315		err := kbfscodec.SerializeToFileIfNotExist(
316			s.codec, extraV3.GetWriterKeyBundle(), s.writerKeyBundleV3Path(wkbID))
317		if err != nil {
318			return err
319		}
320	}
321
322	if extraV3.IsReaderKeyBundleNew() {
323		rkbID := rmds.MD.GetTLFReaderKeyBundleID()
324		if rkbID == (kbfsmd.TLFReaderKeyBundleID{}) {
325			panic("reader key bundle ID is empty")
326		}
327		err := kbfscodec.SerializeToFileIfNotExist(
328			s.codec, extraV3.GetReaderKeyBundle(), s.readerKeyBundleV3Path(rkbID))
329		if err != nil {
330			return err
331		}
332	}
333	return nil
334}
335
336type errMDServerTlfStorageShutdown struct{}
337
338func (e errMDServerTlfStorageShutdown) Error() string {
339	return "mdServerTlfStorage is shutdown"
340}
341
342func (s *mdServerTlfStorage) checkShutdownReadLocked() error {
343	if s.branchJournals == nil {
344		return errors.WithStack(errMDServerTlfStorageShutdown{})
345	}
346	return nil
347}
348
349// All functions below are public functions.
350
351func (s *mdServerTlfStorage) journalLength(bid kbfsmd.BranchID) (uint64, error) {
352	s.lock.RLock()
353	defer s.lock.RUnlock()
354	err := s.checkShutdownReadLocked()
355	if err != nil {
356		return 0, err
357	}
358
359	j, ok := s.branchJournals[bid]
360	if !ok {
361		return 0, nil
362	}
363
364	return j.length(), nil
365}
366
367func (s *mdServerTlfStorage) getForTLF(
368	ctx context.Context, currentUID keybase1.UID, bid kbfsmd.BranchID) (
369	*RootMetadataSigned, error) {
370	s.lock.RLock()
371	defer s.lock.RUnlock()
372	err := s.checkShutdownReadLocked()
373	if err != nil {
374		return nil, err
375	}
376
377	err = s.checkGetParamsReadLocked(ctx, currentUID, bid)
378	if err != nil {
379		return nil, err
380	}
381
382	rmds, err := s.getHeadForTLFReadLocked(bid)
383	if err != nil {
384		return nil, kbfsmd.ServerError{Err: err}
385	}
386	return rmds, nil
387}
388
389func (s *mdServerTlfStorage) getRange(
390	ctx context.Context, currentUID keybase1.UID, bid kbfsmd.BranchID,
391	start, stop kbfsmd.Revision) (
392	[]*RootMetadataSigned, error) {
393	s.lock.RLock()
394	defer s.lock.RUnlock()
395	err := s.checkShutdownReadLocked()
396	if err != nil {
397		return nil, err
398	}
399
400	return s.getRangeReadLocked(ctx, currentUID, bid, start, stop)
401}
402
403func (s *mdServerTlfStorage) put(ctx context.Context,
404	currentUID keybase1.UID, currentVerifyingKey kbfscrypto.VerifyingKey,
405	rmds *RootMetadataSigned, extra kbfsmd.ExtraMetadata) (
406	recordBranchID bool, err error) {
407	s.lock.Lock()
408	defer s.lock.Unlock()
409	err = s.checkShutdownReadLocked()
410	if err != nil {
411		return false, err
412	}
413
414	err = rmds.IsValidAndSigned(
415		ctx, s.codec, s.teamMemChecker, extra,
416		keybase1.OfflineAvailability_NONE)
417	if err != nil {
418		return false, kbfsmd.ServerErrorBadRequest{Reason: err.Error()}
419	}
420
421	err = rmds.IsLastModifiedBy(currentUID, currentVerifyingKey)
422	if err != nil {
423		return false, kbfsmd.ServerErrorBadRequest{Reason: err.Error()}
424	}
425
426	// Check permissions
427
428	mergedMasterHead, err := s.getHeadForTLFReadLocked(kbfsmd.NullBranchID)
429	if err != nil {
430		return false, kbfsmd.ServerError{Err: err}
431	}
432
433	// TODO: Figure out nil case.
434	if mergedMasterHead != nil {
435		prevExtra, err := getExtraMetadata(
436			s.getKeyBundlesReadLocked, mergedMasterHead.MD)
437		if err != nil {
438			return false, kbfsmd.ServerError{Err: err}
439		}
440		ok, err := isWriterOrValidRekey(
441			ctx, s.teamMemChecker, s.codec, currentUID, currentVerifyingKey,
442			mergedMasterHead.MD, rmds.MD,
443			prevExtra, extra)
444		if err != nil {
445			return false, kbfsmd.ServerError{Err: err}
446		}
447		if !ok {
448			return false, kbfsmd.ServerErrorUnauthorized{}
449		}
450	}
451
452	bid := rmds.MD.BID()
453	mStatus := rmds.MD.MergedStatus()
454
455	head, err := s.getHeadForTLFReadLocked(bid)
456	if err != nil {
457		return false, kbfsmd.ServerError{Err: err}
458	}
459
460	if mStatus == kbfsmd.Unmerged && head == nil {
461		// currHead for unmerged history might be on the main branch
462		prevRev := rmds.MD.RevisionNumber() - 1
463		rmdses, err := s.getRangeReadLocked(
464			ctx, currentUID, kbfsmd.NullBranchID, prevRev, prevRev)
465		if err != nil {
466			return false, kbfsmd.ServerError{Err: err}
467		}
468		if len(rmdses) != 1 {
469			return false, kbfsmd.ServerError{
470				Err: errors.Errorf("Expected 1 MD block got %d", len(rmdses)),
471			}
472		}
473		head = rmdses[0]
474		recordBranchID = true
475	}
476
477	// Consistency checks
478	if head != nil {
479		headID, err := kbfsmd.MakeID(s.codec, head.MD)
480		if err != nil {
481			return false, kbfsmd.ServerError{Err: err}
482		}
483
484		err = head.MD.CheckValidSuccessorForServer(headID, rmds.MD)
485		if err != nil {
486			return false, err
487		}
488	}
489
490	id, err := s.putMDLocked(rmds)
491	if err != nil {
492		return false, kbfsmd.ServerError{Err: err}
493	}
494
495	err = s.putExtraMetadataLocked(rmds, extra)
496	if err != nil {
497		return false, kbfsmd.ServerError{Err: err}
498	}
499
500	j, err := s.getOrCreateBranchJournalLocked(bid)
501	if err != nil {
502		return false, err
503	}
504
505	err = j.append(rmds.MD.RevisionNumber(), mdIDJournalEntry{ID: id})
506	if err != nil {
507		return false, kbfsmd.ServerError{Err: err}
508	}
509
510	return recordBranchID, nil
511}
512
513func (s *mdServerTlfStorage) getKeyBundlesReadLocked(tlfID tlf.ID,
514	wkbID kbfsmd.TLFWriterKeyBundleID, rkbID kbfsmd.TLFReaderKeyBundleID) (
515	*kbfsmd.TLFWriterKeyBundleV3, *kbfsmd.TLFReaderKeyBundleV3, error) {
516	err := s.checkShutdownReadLocked()
517	if err != nil {
518		return nil, nil, err
519	}
520
521	var wkb *kbfsmd.TLFWriterKeyBundleV3
522	if wkbID != (kbfsmd.TLFWriterKeyBundleID{}) {
523		foundWKB, err := kbfsmd.DeserializeTLFWriterKeyBundleV3(
524			s.codec, s.writerKeyBundleV3Path(wkbID))
525		if err != nil {
526			return nil, nil, err
527		}
528
529		err = kbfsmd.CheckWKBID(s.codec, wkbID, foundWKB)
530		if err != nil {
531			return nil, nil, err
532		}
533		wkb = &foundWKB
534	}
535
536	var rkb *kbfsmd.TLFReaderKeyBundleV3
537	if rkbID != (kbfsmd.TLFReaderKeyBundleID{}) {
538		foundRKB, err := kbfsmd.DeserializeTLFReaderKeyBundleV3(
539			s.codec, s.readerKeyBundleV3Path(rkbID))
540		if err != nil {
541			return nil, nil, err
542		}
543
544		err = kbfsmd.CheckRKBID(s.codec, rkbID, foundRKB)
545		if err != nil {
546			return nil, nil, err
547		}
548		rkb = &foundRKB
549	}
550
551	return wkb, rkb, nil
552}
553
554func (s *mdServerTlfStorage) getKeyBundles(tlfID tlf.ID,
555	wkbID kbfsmd.TLFWriterKeyBundleID, rkbID kbfsmd.TLFReaderKeyBundleID) (
556	*kbfsmd.TLFWriterKeyBundleV3, *kbfsmd.TLFReaderKeyBundleV3, error) {
557	s.lock.RLock()
558	defer s.lock.RUnlock()
559	return s.getKeyBundlesReadLocked(tlfID, wkbID, rkbID)
560
561}
562
563func (s *mdServerTlfStorage) shutdown() {
564	s.lock.Lock()
565	defer s.lock.Unlock()
566	s.branchJournals = nil
567}
568