| // Copyright 2015 The Vanadium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| package vsync |
| |
| import ( |
| "fmt" |
| "math/rand" |
| "reflect" |
| "testing" |
| "time" |
| |
| "v.io/syncbase/x/ref/services/syncbase/server/interfaces" |
| "v.io/syncbase/x/ref/services/syncbase/server/watchable" |
| "v.io/v23/naming" |
| "v.io/v23/rpc" |
| "v.io/v23/security" |
| _ "v.io/x/ref/runtime/factories/generic" |
| ) |
| |
| // TestDiffPrefixGenVectors tests diffing prefix gen vectors. |
| func TestDiffPrefixGenVectors(t *testing.T) { |
| svc := createService(t) |
| defer destroyService(t, svc) |
| s := svc.sync |
| s.id = 10 //responder. Initiator is id 11. |
| |
| tests := []struct { |
| respPVec, initPVec interfaces.PrefixGenVector |
| genDiffIn genRangeVector |
| genDiffWant genRangeVector |
| }{ |
| { // responder and initiator are at identical vectors. |
| respPVec: interfaces.PrefixGenVector{10: 1, 11: 10, 12: 20, 13: 2}, |
| initPVec: interfaces.PrefixGenVector{10: 1, 11: 10, 12: 20, 13: 2}, |
| genDiffIn: make(genRangeVector), |
| }, |
| { // responder and initiator are at identical vectors. |
| respPVec: interfaces.PrefixGenVector{10: 0}, |
| initPVec: interfaces.PrefixGenVector{10: 0}, |
| genDiffIn: make(genRangeVector), |
| }, |
| { // responder has no updates. |
| respPVec: interfaces.PrefixGenVector{10: 0}, |
| initPVec: interfaces.PrefixGenVector{10: 5, 11: 10, 12: 20, 13: 8}, |
| genDiffIn: make(genRangeVector), |
| }, |
| { // responder and initiator have no updates. |
| respPVec: interfaces.PrefixGenVector{10: 0}, |
| initPVec: interfaces.PrefixGenVector{11: 0}, |
| genDiffIn: make(genRangeVector), |
| }, |
| { // responder is staler than initiator. |
| respPVec: interfaces.PrefixGenVector{10: 1, 11: 10, 12: 20, 13: 2}, |
| initPVec: interfaces.PrefixGenVector{10: 1, 11: 10, 12: 20, 13: 8, 14: 5}, |
| genDiffIn: make(genRangeVector), |
| }, |
| { // responder is more up-to-date than initiator for local updates. |
| respPVec: interfaces.PrefixGenVector{10: 5, 11: 10, 12: 20, 13: 2}, |
| initPVec: interfaces.PrefixGenVector{10: 1, 11: 10, 12: 20, 13: 2}, |
| genDiffIn: make(genRangeVector), |
| genDiffWant: genRangeVector{10: &genRange{min: 2, max: 5}}, |
| }, |
| { // responder is fresher than initiator for local updates and one device. |
| respPVec: interfaces.PrefixGenVector{10: 5, 11: 10, 12: 22, 13: 2}, |
| initPVec: interfaces.PrefixGenVector{10: 1, 11: 10, 12: 20, 13: 2, 14: 40}, |
| genDiffIn: make(genRangeVector), |
| genDiffWant: genRangeVector{ |
| 10: &genRange{min: 2, max: 5}, |
| 12: &genRange{min: 21, max: 22}, |
| }, |
| }, |
| { // responder is fresher than initiator in all but one device. |
| respPVec: interfaces.PrefixGenVector{10: 1, 11: 2, 12: 3, 13: 4}, |
| initPVec: interfaces.PrefixGenVector{10: 0, 11: 2, 12: 0}, |
| genDiffIn: make(genRangeVector), |
| genDiffWant: genRangeVector{ |
| 10: &genRange{min: 1, max: 1}, |
| 12: &genRange{min: 1, max: 3}, |
| 13: &genRange{min: 1, max: 4}, |
| }, |
| }, |
| { // initiator has no updates. |
| respPVec: interfaces.PrefixGenVector{10: 1, 11: 2, 12: 3, 13: 4}, |
| initPVec: interfaces.PrefixGenVector{}, |
| genDiffIn: make(genRangeVector), |
| genDiffWant: genRangeVector{ |
| 10: &genRange{min: 1, max: 1}, |
| 11: &genRange{min: 1, max: 2}, |
| 12: &genRange{min: 1, max: 3}, |
| 13: &genRange{min: 1, max: 4}, |
| }, |
| }, |
| { // initiator has no updates, pre-existing diff. |
| respPVec: interfaces.PrefixGenVector{10: 1, 11: 2, 12: 3, 13: 4}, |
| initPVec: interfaces.PrefixGenVector{13: 1}, |
| genDiffIn: genRangeVector{ |
| 10: &genRange{min: 5, max: 20}, |
| 13: &genRange{min: 1, max: 3}, |
| }, |
| genDiffWant: genRangeVector{ |
| 10: &genRange{min: 1, max: 20}, |
| 11: &genRange{min: 1, max: 2}, |
| 12: &genRange{min: 1, max: 3}, |
| 13: &genRange{min: 1, max: 4}, |
| }, |
| }, |
| } |
| |
| for _, test := range tests { |
| want := test.genDiffWant |
| got := test.genDiffIn |
| rSt := newResponderState(nil, nil, s, interfaces.DeltaReq{}, "fakeInitiator") |
| rSt.diff = got |
| rSt.diffPrefixGenVectors(test.respPVec, test.initPVec) |
| checkEqualDevRanges(t, got, want) |
| } |
| } |
| |
| // TestSendDeltas tests the computation of the delta bound (computeDeltaBound) |
| // and if the log records on the wire are correctly ordered (phases 2 and 3 of |
| // SendDeltas). |
| func TestSendDeltas(t *testing.T) { |
| appName := "mockapp" |
| dbName := "mockdb" |
| |
| tests := []struct { |
| respVec, initVec, outVec interfaces.GenVector |
| respGen uint64 |
| genDiff genRangeVector |
| keyPfxs []string |
| }{ |
| { // Identical prefixes, local and remote updates. |
| respVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{12: 8}, |
| "foobar": interfaces.PrefixGenVector{12: 10}, |
| }, |
| initVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{11: 5}, |
| "foobar": interfaces.PrefixGenVector{11: 5}, |
| }, |
| respGen: 5, |
| outVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{10: 5, 12: 8}, |
| "foobar": interfaces.PrefixGenVector{10: 5, 12: 10}, |
| }, |
| genDiff: genRangeVector{ |
| 10: &genRange{min: 1, max: 5}, |
| 12: &genRange{min: 1, max: 10}, |
| }, |
| keyPfxs: []string{"baz", "wombat", "f", "foo", "foobar", ""}, |
| }, |
| { // Identical prefixes, local and remote updates. |
| respVec: interfaces.GenVector{ |
| "bar": interfaces.PrefixGenVector{12: 20}, |
| "foo": interfaces.PrefixGenVector{12: 8}, |
| "foobar": interfaces.PrefixGenVector{12: 10}, |
| }, |
| initVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{11: 5}, |
| "foobar": interfaces.PrefixGenVector{11: 5, 12: 10}, |
| "bar": interfaces.PrefixGenVector{10: 5, 11: 5, 12: 5}, |
| }, |
| respGen: 5, |
| outVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{10: 5, 12: 8}, |
| "foobar": interfaces.PrefixGenVector{10: 5, 12: 10}, |
| "bar": interfaces.PrefixGenVector{10: 5, 12: 20}, |
| }, |
| genDiff: genRangeVector{ |
| 10: &genRange{min: 1, max: 5}, |
| 12: &genRange{min: 1, max: 20}, |
| }, |
| keyPfxs: []string{"baz", "wombat", "f", "foo", "foobar", "bar", "barbaz", ""}, |
| }, |
| { // Non-identical prefixes, local only updates. |
| initVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{11: 5}, |
| "foobar": interfaces.PrefixGenVector{11: 5}, |
| }, |
| respGen: 5, |
| outVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{10: 5}, |
| }, |
| genDiff: genRangeVector{ |
| 10: &genRange{min: 1, max: 5}, |
| }, |
| keyPfxs: []string{"baz", "wombat", "f", "foo", "foobar", "", "fo", "fooxyz"}, |
| }, |
| { // Non-identical prefixes, local and remote updates. |
| respVec: interfaces.GenVector{ |
| "f": interfaces.PrefixGenVector{12: 5, 13: 5}, |
| "foo": interfaces.PrefixGenVector{12: 10, 13: 10}, |
| "foobar": interfaces.PrefixGenVector{12: 20, 13: 20}, |
| }, |
| initVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{11: 5, 12: 1}, |
| }, |
| respGen: 5, |
| outVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{10: 5, 12: 10, 13: 10}, |
| "foobar": interfaces.PrefixGenVector{10: 5, 12: 20, 13: 20}, |
| }, |
| genDiff: genRangeVector{ |
| 10: &genRange{min: 1, max: 5}, |
| 12: &genRange{min: 2, max: 20}, |
| 13: &genRange{min: 1, max: 20}, |
| }, |
| keyPfxs: []string{"baz", "wombat", "f", "foo", "foobar", "", "fo", "fooxyz"}, |
| }, |
| { // Non-identical prefixes, local and remote updates. |
| respVec: interfaces.GenVector{ |
| "foobar": interfaces.PrefixGenVector{12: 20, 13: 20}, |
| }, |
| initVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{11: 5, 12: 1}, |
| }, |
| respGen: 5, |
| outVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{10: 5}, |
| "foobar": interfaces.PrefixGenVector{10: 5, 12: 20, 13: 20}, |
| }, |
| genDiff: genRangeVector{ |
| 10: &genRange{min: 1, max: 5}, |
| 12: &genRange{min: 2, max: 20}, |
| 13: &genRange{min: 1, max: 20}, |
| }, |
| keyPfxs: []string{"baz", "wombat", "f", "foo", "foobar", "", "fo", "fooxyz"}, |
| }, |
| { // Non-identical prefixes, local and remote updates. |
| respVec: interfaces.GenVector{ |
| "f": interfaces.PrefixGenVector{12: 20, 13: 20}, |
| }, |
| initVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{11: 5, 12: 1}, |
| }, |
| respGen: 5, |
| outVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{10: 5, 12: 20, 13: 20}, |
| }, |
| genDiff: genRangeVector{ |
| 10: &genRange{min: 1, max: 5}, |
| 12: &genRange{min: 2, max: 20}, |
| 13: &genRange{min: 1, max: 20}, |
| }, |
| keyPfxs: []string{"baz", "wombat", "f", "foo", "foobar", "", "fo", "fooxyz"}, |
| }, |
| { // Non-identical interleaving prefixes. |
| respVec: interfaces.GenVector{ |
| "f": interfaces.PrefixGenVector{12: 20, 13: 10}, |
| "foo": interfaces.PrefixGenVector{12: 30, 13: 20}, |
| "foobar": interfaces.PrefixGenVector{12: 40, 13: 30}, |
| }, |
| initVec: interfaces.GenVector{ |
| "fo": interfaces.PrefixGenVector{11: 5, 12: 1}, |
| "foob": interfaces.PrefixGenVector{11: 5, 12: 10}, |
| "foobarxyz": interfaces.PrefixGenVector{11: 5, 12: 20}, |
| }, |
| respGen: 5, |
| outVec: interfaces.GenVector{ |
| "fo": interfaces.PrefixGenVector{10: 5, 12: 20, 13: 10}, |
| "foo": interfaces.PrefixGenVector{10: 5, 12: 30, 13: 20}, |
| "foobar": interfaces.PrefixGenVector{10: 5, 12: 40, 13: 30}, |
| }, |
| genDiff: genRangeVector{ |
| 10: &genRange{min: 1, max: 5}, |
| 12: &genRange{min: 2, max: 40}, |
| 13: &genRange{min: 1, max: 30}, |
| }, |
| keyPfxs: []string{"baz", "wombat", "f", "foo", "foobar", "", "fo", "foob", "foobarxyz", "fooxyz"}, |
| }, |
| { // Non-identical interleaving prefixes. |
| respVec: interfaces.GenVector{ |
| "fo": interfaces.PrefixGenVector{12: 20, 13: 10}, |
| "foob": interfaces.PrefixGenVector{12: 30, 13: 20}, |
| "foobarxyz": interfaces.PrefixGenVector{12: 40, 13: 30}, |
| }, |
| initVec: interfaces.GenVector{ |
| "f": interfaces.PrefixGenVector{11: 5, 12: 1}, |
| "foo": interfaces.PrefixGenVector{11: 5, 12: 10}, |
| "foobar": interfaces.PrefixGenVector{11: 5, 12: 20}, |
| }, |
| respGen: 5, |
| outVec: interfaces.GenVector{ |
| "f": interfaces.PrefixGenVector{10: 5}, |
| "fo": interfaces.PrefixGenVector{10: 5, 12: 20, 13: 10}, |
| "foob": interfaces.PrefixGenVector{10: 5, 12: 30, 13: 20}, |
| "foobarxyz": interfaces.PrefixGenVector{10: 5, 12: 40, 13: 30}, |
| }, |
| genDiff: genRangeVector{ |
| 10: &genRange{min: 1, max: 5}, |
| 12: &genRange{min: 2, max: 40}, |
| 13: &genRange{min: 1, max: 30}, |
| }, |
| keyPfxs: []string{"baz", "wombat", "f", "foo", "foobar", "", "fo", "foob", "foobarxyz", "fooxyz"}, |
| }, |
| { // Non-identical sibling prefixes. |
| respVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{12: 20, 13: 10}, |
| "foobarabc": interfaces.PrefixGenVector{12: 40, 13: 30}, |
| "foobarxyz": interfaces.PrefixGenVector{12: 30, 13: 20}, |
| }, |
| initVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{11: 5, 12: 1}, |
| }, |
| respGen: 5, |
| outVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{10: 5, 12: 20, 13: 10}, |
| "foobarabc": interfaces.PrefixGenVector{10: 5, 12: 40, 13: 30}, |
| "foobarxyz": interfaces.PrefixGenVector{10: 5, 12: 30, 13: 20}, |
| }, |
| genDiff: genRangeVector{ |
| 10: &genRange{min: 1, max: 5}, |
| 12: &genRange{min: 2, max: 40}, |
| 13: &genRange{min: 1, max: 30}, |
| }, |
| keyPfxs: []string{"baz", "wombat", "f", "foo", "foobar", "", "foobarabc", "foobarxyz", "foobar123", "fooxyz"}, |
| }, |
| { // Non-identical prefixes, local and remote updates. |
| respVec: interfaces.GenVector{ |
| "barbaz": interfaces.PrefixGenVector{12: 18}, |
| "f": interfaces.PrefixGenVector{12: 30, 13: 5}, |
| "foobar": interfaces.PrefixGenVector{12: 30, 13: 8}, |
| }, |
| initVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{11: 5, 12: 5}, |
| "foobar": interfaces.PrefixGenVector{11: 5, 12: 5}, |
| "bar": interfaces.PrefixGenVector{10: 5, 11: 5, 12: 5}, |
| }, |
| respGen: 5, |
| outVec: interfaces.GenVector{ |
| "foo": interfaces.PrefixGenVector{10: 5, 12: 30, 13: 5}, |
| "foobar": interfaces.PrefixGenVector{10: 5, 12: 30, 13: 8}, |
| "bar": interfaces.PrefixGenVector{10: 5}, |
| "barbaz": interfaces.PrefixGenVector{10: 5, 12: 18}, |
| }, |
| genDiff: genRangeVector{ |
| 10: &genRange{min: 1, max: 5}, |
| 12: &genRange{min: 6, max: 30}, |
| 13: &genRange{min: 1, max: 8}, |
| }, |
| keyPfxs: []string{"baz", "wombat", "f", "foo", "foobar", "bar", "barbaz", ""}, |
| }, |
| } |
| |
| for i, test := range tests { |
| svc := createService(t) |
| s := svc.sync |
| s.id = 10 //responder. |
| |
| wantDiff, wantVec := test.genDiff, test.outVec |
| s.syncState[appDbName(appName, dbName)] = &dbSyncStateInMem{gen: test.respGen, checkptGen: test.respGen, genvec: test.respVec} |
| |
| req := interfaces.DeltaReq{AppName: appName, DbName: dbName, InitVec: test.initVec} |
| rSt := newResponderState(nil, nil, s, req, "fakeInitiator") |
| |
| rSt.computeDeltaBound(nil) |
| if rSt.errState != nil || !reflect.DeepEqual(rSt.outVec, wantVec) { |
| t.Fatalf("computeDeltaBound failed (I: %v), (R: %v, %v), got %v, want %v err %v", test.initVec, test.respGen, test.respVec, rSt.outVec, wantVec, rSt.errState) |
| } |
| checkEqualDevRanges(t, rSt.diff, wantDiff) |
| |
| //////////////////////////////////////// |
| // Test sending deltas. |
| |
| // Insert some log records to bootstrap testing below. |
| tRng := rand.New(rand.NewSource(int64(i))) |
| var wantRecs []*localLogRec |
| st := svc.St() |
| tx := st.NewTransaction() |
| objKeyPfxs := test.keyPfxs |
| j := 0 |
| for id, r := range wantDiff { |
| pos := uint64(tRng.Intn(50) + 100*j) |
| for k := r.min; k <= r.max; k++ { |
| opfx := objKeyPfxs[tRng.Intn(len(objKeyPfxs))] |
| // Create holes in the log records. |
| if opfx == "" { |
| continue |
| } |
| okey := makeRowKey(fmt.Sprintf("%s~%x", opfx, tRng.Int())) |
| vers := fmt.Sprintf("%x", tRng.Int()) |
| rec := &localLogRec{ |
| Metadata: interfaces.LogRecMetadata{Id: id, Gen: k, ObjId: okey, CurVers: vers, UpdTime: time.Now().UTC()}, |
| Pos: pos + k, |
| } |
| if err := putLogRec(nil, tx, rec); err != nil { |
| t.Fatalf("putLogRec(%d:%d) failed rec %v err %v", id, k, rec, err) |
| } |
| value := fmt.Sprintf("value_%s", okey) |
| if err := watchable.PutAtVersion(nil, tx, []byte(okey), []byte(value), []byte(vers)); err != nil { |
| t.Fatalf("PutAtVersion(%d:%d) failed rec %v value %s: err %v", id, k, rec, value, err) |
| } |
| |
| initPfxs := extractAndSortPrefixes(test.initVec) |
| if !filterLogRec(rec, test.initVec, initPfxs) { |
| wantRecs = append(wantRecs, rec) |
| } |
| } |
| j++ |
| } |
| if err := tx.Commit(); err != nil { |
| t.Fatalf("cannot commit putting log rec, err %v", err) |
| } |
| |
| d := &dummyResponder{} |
| rSt.call = d |
| rSt.st, rSt.errState = rSt.sync.getDbStore(nil, nil, rSt.req.AppName, rSt.req.DbName) |
| if rSt.errState != nil { |
| t.Fatalf("filterAndSendDeltas failed to get store handle for app/db %v %v", rSt.req.AppName, rSt.req.DbName) |
| } |
| err := rSt.filterAndSendDeltas(nil) |
| if err != nil { |
| t.Fatalf("filterAndSendDeltas failed (I: %v), (R: %v, %v) err %v", test.initVec, test.respGen, test.respVec, err) |
| } |
| d.diffLogRecs(t, wantRecs, wantVec) |
| |
| destroyService(t, svc) |
| } |
| } |
| |
| ////////////////////////////// |
| // Helpers |
| |
| type dummyResponder struct { |
| start, finish int |
| gotRecs []*localLogRec |
| outVec interfaces.GenVector |
| } |
| |
| func (d *dummyResponder) RecvStream() interface { |
| Advance() bool |
| Value() interfaces.DeltaReq |
| Err() error |
| } { |
| return d |
| } |
| |
| func (d *dummyResponder) Advance() bool { |
| return false |
| } |
| |
| func (d *dummyResponder) Value() interfaces.DeltaReq { |
| return interfaces.DeltaReq{} |
| } |
| |
| func (d *dummyResponder) Err() error { return nil } |
| |
| func (d *dummyResponder) SendStream() interface { |
| Send(item interfaces.DeltaResp) error |
| } { |
| return d |
| } |
| |
| func (d *dummyResponder) Send(item interfaces.DeltaResp) error { |
| switch v := item.(type) { |
| case interfaces.DeltaRespStart: |
| d.start++ |
| case interfaces.DeltaRespFinish: |
| d.finish++ |
| case interfaces.DeltaRespRespVec: |
| d.outVec = v.Value |
| case interfaces.DeltaRespRec: |
| d.gotRecs = append(d.gotRecs, &localLogRec{Metadata: v.Value.Metadata}) |
| } |
| return nil |
| } |
| |
| func (d *dummyResponder) Security() security.Call { |
| return nil |
| } |
| |
| func (d *dummyResponder) Suffix() string { |
| return "" |
| } |
| |
| func (d *dummyResponder) LocalEndpoint() naming.Endpoint { |
| return nil |
| } |
| |
| func (d *dummyResponder) RemoteEndpoint() naming.Endpoint { |
| return nil |
| } |
| |
| func (d *dummyResponder) GrantedBlessings() security.Blessings { |
| return security.Blessings{} |
| } |
| |
| func (d *dummyResponder) Server() rpc.Server { |
| return nil |
| } |
| |
| func (d *dummyResponder) diffLogRecs(t *testing.T, wantRecs []*localLogRec, wantVec interfaces.GenVector) { |
| if d.start != 1 || d.finish != 1 { |
| t.Fatalf("diffLogRecs incorrect start/finish records (%v, %v)", d.start, d.finish) |
| } |
| if len(d.gotRecs) != len(wantRecs) { |
| t.Fatalf("diffLogRecs failed, gotLen %v, wantLen %v\n", len(d.gotRecs), len(wantRecs)) |
| } |
| for i, rec := range d.gotRecs { |
| if !reflect.DeepEqual(rec.Metadata, wantRecs[i].Metadata) { |
| t.Fatalf("diffLogRecs failed, i %v, got %v, want %v\n", i, rec.Metadata, wantRecs[i].Metadata) |
| } |
| } |
| if !reflect.DeepEqual(d.outVec, wantVec) { |
| t.Fatalf("diffLogRecs failed genvector, got %v, want %v\n", d.outVec, wantVec) |
| } |
| } |
| |
| func checkEqualDevRanges(t *testing.T, s1, s2 genRangeVector) { |
| if len(s1) != len(s2) { |
| t.Fatalf("len(s1): %v != len(s2): %v", len(s1), len(s2)) |
| } |
| for d1, r1 := range s1 { |
| if r2, ok := s2[d1]; !ok || !reflect.DeepEqual(r1, r2) { |
| t.Fatalf("Dev %v: r1 %v != r2 %v", d1, r1, r2) |
| } |
| } |
| } |
