// Copyright 2019 The go-ethereum Authors // This file is part of the go-ethereum library. // // The go-ethereum library is free software: you can redistribute it and/or modify // it under the terms of the GNU Lesser General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // // The go-ethereum library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU Lesser General Public License for more details. // // You should have received a copy of the GNU Lesser General Public License // along with the go-ethereum library. If not, see . package snapshot import ( "bytes" "io/ioutil" "os" "testing" "github.com/VictoriaMetrics/fastcache" "github.com/ava-labs/coreth/core/rawdb" "github.com/ethereum/go-ethereum/common" "github.com/ethereum/go-ethereum/ethdb" "github.com/ethereum/go-ethereum/ethdb/leveldb" "github.com/ethereum/go-ethereum/ethdb/memorydb" ) // reverse reverses the contents of a byte slice. It's used to update random accs // with deterministic changes. func reverse(blob []byte) []byte { res := make([]byte, len(blob)) for i, b := range blob { res[len(blob)-1-i] = b } return res } // Tests that merging something into a disk layer persists it into the database // and invalidates any previously written and cached values. func TestDiskMerge(t *testing.T) { // Create some accounts in the disk layer db := memorydb.New() var ( accNoModNoCache = common.Hash{0x1} accNoModCache = common.Hash{0x2} accModNoCache = common.Hash{0x3} accModCache = common.Hash{0x4} accDelNoCache = common.Hash{0x5} accDelCache = common.Hash{0x6} conNoModNoCache = common.Hash{0x7} conNoModNoCacheSlot = common.Hash{0x70} conNoModCache = common.Hash{0x8} conNoModCacheSlot = common.Hash{0x80} conModNoCache = common.Hash{0x9} conModNoCacheSlot = common.Hash{0x90} conModCache = common.Hash{0xa} conModCacheSlot = common.Hash{0xa0} conDelNoCache = common.Hash{0xb} conDelNoCacheSlot = common.Hash{0xb0} conDelCache = common.Hash{0xc} conDelCacheSlot = common.Hash{0xc0} conNukeNoCache = common.Hash{0xd} conNukeNoCacheSlot = common.Hash{0xd0} conNukeCache = common.Hash{0xe} conNukeCacheSlot = common.Hash{0xe0} baseRoot = randomHash() diffRoot = randomHash() ) rawdb.WriteAccountSnapshot(db, accNoModNoCache, accNoModNoCache[:]) rawdb.WriteAccountSnapshot(db, accNoModCache, accNoModCache[:]) rawdb.WriteAccountSnapshot(db, accModNoCache, accModNoCache[:]) rawdb.WriteAccountSnapshot(db, accModCache, accModCache[:]) rawdb.WriteAccountSnapshot(db, accDelNoCache, accDelNoCache[:]) rawdb.WriteAccountSnapshot(db, accDelCache, accDelCache[:]) rawdb.WriteAccountSnapshot(db, conNoModNoCache, conNoModNoCache[:]) rawdb.WriteStorageSnapshot(db, conNoModNoCache, conNoModNoCacheSlot, conNoModNoCacheSlot[:]) rawdb.WriteAccountSnapshot(db, conNoModCache, conNoModCache[:]) rawdb.WriteStorageSnapshot(db, conNoModCache, conNoModCacheSlot, conNoModCacheSlot[:]) rawdb.WriteAccountSnapshot(db, conModNoCache, conModNoCache[:]) rawdb.WriteStorageSnapshot(db, conModNoCache, conModNoCacheSlot, conModNoCacheSlot[:]) rawdb.WriteAccountSnapshot(db, conModCache, conModCache[:]) rawdb.WriteStorageSnapshot(db, conModCache, conModCacheSlot, conModCacheSlot[:]) rawdb.WriteAccountSnapshot(db, conDelNoCache, conDelNoCache[:]) rawdb.WriteStorageSnapshot(db, conDelNoCache, conDelNoCacheSlot, conDelNoCacheSlot[:]) rawdb.WriteAccountSnapshot(db, conDelCache, conDelCache[:]) rawdb.WriteStorageSnapshot(db, conDelCache, conDelCacheSlot, conDelCacheSlot[:]) rawdb.WriteAccountSnapshot(db, conNukeNoCache, conNukeNoCache[:]) rawdb.WriteStorageSnapshot(db, conNukeNoCache, conNukeNoCacheSlot, conNukeNoCacheSlot[:]) rawdb.WriteAccountSnapshot(db, conNukeCache, conNukeCache[:]) rawdb.WriteStorageSnapshot(db, conNukeCache, conNukeCacheSlot, conNukeCacheSlot[:]) rawdb.WriteSnapshotRoot(db, baseRoot) // Create a disk layer based on the above and cache in some data snaps := &Tree{ layers: map[common.Hash]snapshot{ baseRoot: &diskLayer{ diskdb: db, cache: fastcache.New(500 * 1024), root: baseRoot, }, }, } base := snaps.Snapshot(baseRoot) base.AccountRLP(accNoModCache) base.AccountRLP(accModCache) base.AccountRLP(accDelCache) base.Storage(conNoModCache, conNoModCacheSlot) base.Storage(conModCache, conModCacheSlot) base.Storage(conDelCache, conDelCacheSlot) base.Storage(conNukeCache, conNukeCacheSlot) // Modify or delete some accounts, flatten everything onto disk if err := snaps.Update(diffRoot, baseRoot, map[common.Hash]struct{}{ accDelNoCache: {}, accDelCache: {}, conNukeNoCache: {}, conNukeCache: {}, }, map[common.Hash][]byte{ accModNoCache: reverse(accModNoCache[:]), accModCache: reverse(accModCache[:]), }, map[common.Hash]map[common.Hash][]byte{ conModNoCache: {conModNoCacheSlot: reverse(conModNoCacheSlot[:])}, conModCache: {conModCacheSlot: reverse(conModCacheSlot[:])}, conDelNoCache: {conDelNoCacheSlot: nil}, conDelCache: {conDelCacheSlot: nil}, }); err != nil { t.Fatalf("failed to update snapshot tree: %v", err) } if err := snaps.Cap(diffRoot, 0); err != nil { t.Fatalf("failed to flatten snapshot tree: %v", err) } // Retrieve all the data through the disk layer and validate it base = snaps.Snapshot(diffRoot) if _, ok := base.(*diskLayer); !ok { t.Fatalf("update not flattend into the disk layer") } // assertAccount ensures that an account matches the given blob. assertAccount := func(account common.Hash, data []byte) { t.Helper() blob, err := base.AccountRLP(account) if err != nil { t.Errorf("account access (%x) failed: %v", account, err) } else if !bytes.Equal(blob, data) { t.Errorf("account access (%x) mismatch: have %x, want %x", account, blob, data) } } assertAccount(accNoModNoCache, accNoModNoCache[:]) assertAccount(accNoModCache, accNoModCache[:]) assertAccount(accModNoCache, reverse(accModNoCache[:])) assertAccount(accModCache, reverse(accModCache[:])) assertAccount(accDelNoCache, nil) assertAccount(accDelCache, nil) // assertStorage ensures that a storage slot matches the given blob. assertStorage := func(account common.Hash, slot common.Hash, data []byte) { t.Helper() blob, err := base.Storage(account, slot) if err != nil { t.Errorf("storage access (%x:%x) failed: %v", account, slot, err) } else if !bytes.Equal(blob, data) { t.Errorf("storage access (%x:%x) mismatch: have %x, want %x", account, slot, blob, data) } } assertStorage(conNoModNoCache, conNoModNoCacheSlot, conNoModNoCacheSlot[:]) assertStorage(conNoModCache, conNoModCacheSlot, conNoModCacheSlot[:]) assertStorage(conModNoCache, conModNoCacheSlot, reverse(conModNoCacheSlot[:])) assertStorage(conModCache, conModCacheSlot, reverse(conModCacheSlot[:])) assertStorage(conDelNoCache, conDelNoCacheSlot, nil) assertStorage(conDelCache, conDelCacheSlot, nil) assertStorage(conNukeNoCache, conNukeNoCacheSlot, nil) assertStorage(conNukeCache, conNukeCacheSlot, nil) // Retrieve all the data directly from the database and validate it // assertDatabaseAccount ensures that an account from the database matches the given blob. assertDatabaseAccount := func(account common.Hash, data []byte) { t.Helper() if blob := rawdb.ReadAccountSnapshot(db, account); !bytes.Equal(blob, data) { t.Errorf("account database access (%x) mismatch: have %x, want %x", account, blob, data) } } assertDatabaseAccount(accNoModNoCache, accNoModNoCache[:]) assertDatabaseAccount(accNoModCache, accNoModCache[:]) assertDatabaseAccount(accModNoCache, reverse(accModNoCache[:])) assertDatabaseAccount(accModCache, reverse(accModCache[:])) assertDatabaseAccount(accDelNoCache, nil) assertDatabaseAccount(accDelCache, nil) // assertDatabaseStorage ensures that a storage slot from the database matches the given blob. assertDatabaseStorage := func(account common.Hash, slot common.Hash, data []byte) { t.Helper() if blob := rawdb.ReadStorageSnapshot(db, account, slot); !bytes.Equal(blob, data) { t.Errorf("storage database access (%x:%x) mismatch: have %x, want %x", account, slot, blob, data) } } assertDatabaseStorage(conNoModNoCache, conNoModNoCacheSlot, conNoModNoCacheSlot[:]) assertDatabaseStorage(conNoModCache, conNoModCacheSlot, conNoModCacheSlot[:]) assertDatabaseStorage(conModNoCache, conModNoCacheSlot, reverse(conModNoCacheSlot[:])) assertDatabaseStorage(conModCache, conModCacheSlot, reverse(conModCacheSlot[:])) assertDatabaseStorage(conDelNoCache, conDelNoCacheSlot, nil) assertDatabaseStorage(conDelCache, conDelCacheSlot, nil) assertDatabaseStorage(conNukeNoCache, conNukeNoCacheSlot, nil) assertDatabaseStorage(conNukeCache, conNukeCacheSlot, nil) } // Tests that merging something into a disk layer persists it into the database // and invalidates any previously written and cached values, discarding anything // after the in-progress generation marker. func TestDiskPartialMerge(t *testing.T) { // Iterate the test a few times to ensure we pick various internal orderings // for the data slots as well as the progress marker. for i := 0; i < 1024; i++ { // Create some accounts in the disk layer db := memorydb.New() var ( accNoModNoCache = randomHash() accNoModCache = randomHash() accModNoCache = randomHash() accModCache = randomHash() accDelNoCache = randomHash() accDelCache = randomHash() conNoModNoCache = randomHash() conNoModNoCacheSlot = randomHash() conNoModCache = randomHash() conNoModCacheSlot = randomHash() conModNoCache = randomHash() conModNoCacheSlot = randomHash() conModCache = randomHash() conModCacheSlot = randomHash() conDelNoCache = randomHash() conDelNoCacheSlot = randomHash() conDelCache = randomHash() conDelCacheSlot = randomHash() conNukeNoCache = randomHash() conNukeNoCacheSlot = randomHash() conNukeCache = randomHash() conNukeCacheSlot = randomHash() baseRoot = randomHash() diffRoot = randomHash() genMarker = append(randomHash().Bytes(), randomHash().Bytes()...) ) // insertAccount injects an account into the database if it's after the // generator marker, drops the op otherwise. This is needed to seed the // database with a valid starting snapshot. insertAccount := func(account common.Hash, data []byte) { if bytes.Compare(account[:], genMarker) <= 0 { rawdb.WriteAccountSnapshot(db, account, data[:]) } } insertAccount(accNoModNoCache, accNoModNoCache[:]) insertAccount(accNoModCache, accNoModCache[:]) insertAccount(accModNoCache, accModNoCache[:]) insertAccount(accModCache, accModCache[:]) insertAccount(accDelNoCache, accDelNoCache[:]) insertAccount(accDelCache, accDelCache[:]) // insertStorage injects a storage slot into the database if it's after // the generator marker, drops the op otherwise. This is needed to seed // the database with a valid starting snapshot. insertStorage := func(account common.Hash, slot common.Hash, data []byte) { if bytes.Compare(append(account[:], slot[:]...), genMarker) <= 0 { rawdb.WriteStorageSnapshot(db, account, slot, data[:]) } } insertAccount(conNoModNoCache, conNoModNoCache[:]) insertStorage(conNoModNoCache, conNoModNoCacheSlot, conNoModNoCacheSlot[:]) insertAccount(conNoModCache, conNoModCache[:]) insertStorage(conNoModCache, conNoModCacheSlot, conNoModCacheSlot[:]) insertAccount(conModNoCache, conModNoCache[:]) insertStorage(conModNoCache, conModNoCacheSlot, conModNoCacheSlot[:]) insertAccount(conModCache, conModCache[:]) insertStorage(conModCache, conModCacheSlot, conModCacheSlot[:]) insertAccount(conDelNoCache, conDelNoCache[:]) insertStorage(conDelNoCache, conDelNoCacheSlot, conDelNoCacheSlot[:]) insertAccount(conDelCache, conDelCache[:]) insertStorage(conDelCache, conDelCacheSlot, conDelCacheSlot[:]) insertAccount(conNukeNoCache, conNukeNoCache[:]) insertStorage(conNukeNoCache, conNukeNoCacheSlot, conNukeNoCacheSlot[:]) insertAccount(conNukeCache, conNukeCache[:]) insertStorage(conNukeCache, conNukeCacheSlot, conNukeCacheSlot[:]) rawdb.WriteSnapshotRoot(db, baseRoot) // Create a disk layer based on the above using a random progress marker // and cache in some data. snaps := &Tree{ layers: map[common.Hash]snapshot{ baseRoot: &diskLayer{ diskdb: db, cache: fastcache.New(500 * 1024), root: baseRoot, }, }, } snaps.layers[baseRoot].(*diskLayer).genMarker = genMarker base := snaps.Snapshot(baseRoot) // assertAccount ensures that an account matches the given blob if it's // already covered by the disk snapshot, and errors out otherwise. assertAccount := func(account common.Hash, data []byte) { t.Helper() blob, err := base.AccountRLP(account) if bytes.Compare(account[:], genMarker) > 0 && err != ErrNotCoveredYet { t.Fatalf("test %d: post-marker (%x) account access (%x) succeeded: %x", i, genMarker, account, blob) } if bytes.Compare(account[:], genMarker) <= 0 && !bytes.Equal(blob, data) { t.Fatalf("test %d: pre-marker (%x) account access (%x) mismatch: have %x, want %x", i, genMarker, account, blob, data) } } assertAccount(accNoModCache, accNoModCache[:]) assertAccount(accModCache, accModCache[:]) assertAccount(accDelCache, accDelCache[:]) // assertStorage ensures that a storage slot matches the given blob if // it's already covered by the disk snapshot, and errors out otherwise. assertStorage := func(account common.Hash, slot common.Hash, data []byte) { t.Helper() blob, err := base.Storage(account, slot) if bytes.Compare(append(account[:], slot[:]...), genMarker) > 0 && err != ErrNotCoveredYet { t.Fatalf("test %d: post-marker (%x) storage access (%x:%x) succeeded: %x", i, genMarker, account, slot, blob) } if bytes.Compare(append(account[:], slot[:]...), genMarker) <= 0 && !bytes.Equal(blob, data) { t.Fatalf("test %d: pre-marker (%x) storage access (%x:%x) mismatch: have %x, want %x", i, genMarker, account, slot, blob, data) } } assertStorage(conNoModCache, conNoModCacheSlot, conNoModCacheSlot[:]) assertStorage(conModCache, conModCacheSlot, conModCacheSlot[:]) assertStorage(conDelCache, conDelCacheSlot, conDelCacheSlot[:]) assertStorage(conNukeCache, conNukeCacheSlot, conNukeCacheSlot[:]) // Modify or delete some accounts, flatten everything onto disk if err := snaps.Update(diffRoot, baseRoot, map[common.Hash]struct{}{ accDelNoCache: {}, accDelCache: {}, conNukeNoCache: {}, conNukeCache: {}, }, map[common.Hash][]byte{ accModNoCache: reverse(accModNoCache[:]), accModCache: reverse(accModCache[:]), }, map[common.Hash]map[common.Hash][]byte{ conModNoCache: {conModNoCacheSlot: reverse(conModNoCacheSlot[:])}, conModCache: {conModCacheSlot: reverse(conModCacheSlot[:])}, conDelNoCache: {conDelNoCacheSlot: nil}, conDelCache: {conDelCacheSlot: nil}, }); err != nil { t.Fatalf("test %d: failed to update snapshot tree: %v", i, err) } if err := snaps.Cap(diffRoot, 0); err != nil { t.Fatalf("test %d: failed to flatten snapshot tree: %v", i, err) } // Retrieve all the data through the disk layer and validate it base = snaps.Snapshot(diffRoot) if _, ok := base.(*diskLayer); !ok { t.Fatalf("test %d: update not flattend into the disk layer", i) } assertAccount(accNoModNoCache, accNoModNoCache[:]) assertAccount(accNoModCache, accNoModCache[:]) assertAccount(accModNoCache, reverse(accModNoCache[:])) assertAccount(accModCache, reverse(accModCache[:])) assertAccount(accDelNoCache, nil) assertAccount(accDelCache, nil) assertStorage(conNoModNoCache, conNoModNoCacheSlot, conNoModNoCacheSlot[:]) assertStorage(conNoModCache, conNoModCacheSlot, conNoModCacheSlot[:]) assertStorage(conModNoCache, conModNoCacheSlot, reverse(conModNoCacheSlot[:])) assertStorage(conModCache, conModCacheSlot, reverse(conModCacheSlot[:])) assertStorage(conDelNoCache, conDelNoCacheSlot, nil) assertStorage(conDelCache, conDelCacheSlot, nil) assertStorage(conNukeNoCache, conNukeNoCacheSlot, nil) assertStorage(conNukeCache, conNukeCacheSlot, nil) // Retrieve all the data directly from the database and validate it // assertDatabaseAccount ensures that an account inside the database matches // the given blob if it's already covered by the disk snapshot, and does not // exist otherwise. assertDatabaseAccount := func(account common.Hash, data []byte) { t.Helper() blob := rawdb.ReadAccountSnapshot(db, account) if bytes.Compare(account[:], genMarker) > 0 && blob != nil { t.Fatalf("test %d: post-marker (%x) account database access (%x) succeeded: %x", i, genMarker, account, blob) } if bytes.Compare(account[:], genMarker) <= 0 && !bytes.Equal(blob, data) { t.Fatalf("test %d: pre-marker (%x) account database access (%x) mismatch: have %x, want %x", i, genMarker, account, blob, data) } } assertDatabaseAccount(accNoModNoCache, accNoModNoCache[:]) assertDatabaseAccount(accNoModCache, accNoModCache[:]) assertDatabaseAccount(accModNoCache, reverse(accModNoCache[:])) assertDatabaseAccount(accModCache, reverse(accModCache[:])) assertDatabaseAccount(accDelNoCache, nil) assertDatabaseAccount(accDelCache, nil) // assertDatabaseStorage ensures that a storage slot inside the database // matches the given blob if it's already covered by the disk snapshot, // and does not exist otherwise. assertDatabaseStorage := func(account common.Hash, slot common.Hash, data []byte) { t.Helper() blob := rawdb.ReadStorageSnapshot(db, account, slot) if bytes.Compare(append(account[:], slot[:]...), genMarker) > 0 && blob != nil { t.Fatalf("test %d: post-marker (%x) storage database access (%x:%x) succeeded: %x", i, genMarker, account, slot, blob) } if bytes.Compare(append(account[:], slot[:]...), genMarker) <= 0 && !bytes.Equal(blob, data) { t.Fatalf("test %d: pre-marker (%x) storage database access (%x:%x) mismatch: have %x, want %x", i, genMarker, account, slot, blob, data) } } assertDatabaseStorage(conNoModNoCache, conNoModNoCacheSlot, conNoModNoCacheSlot[:]) assertDatabaseStorage(conNoModCache, conNoModCacheSlot, conNoModCacheSlot[:]) assertDatabaseStorage(conModNoCache, conModNoCacheSlot, reverse(conModNoCacheSlot[:])) assertDatabaseStorage(conModCache, conModCacheSlot, reverse(conModCacheSlot[:])) assertDatabaseStorage(conDelNoCache, conDelNoCacheSlot, nil) assertDatabaseStorage(conDelCache, conDelCacheSlot, nil) assertDatabaseStorage(conNukeNoCache, conNukeNoCacheSlot, nil) assertDatabaseStorage(conNukeCache, conNukeCacheSlot, nil) } } // Tests that merging something into a disk layer persists it into the database // and invalidates any previously written and cached values, discarding anything // after the in-progress generation marker. // // This test case is a tiny specialized case of TestDiskPartialMerge, which tests // some very specific cornercases that random tests won't ever trigger. func TestDiskMidAccountPartialMerge(t *testing.T) { // TODO(@karalabe) ? } // TestDiskSeek tests that seek-operations work on the disk layer func TestDiskSeek(t *testing.T) { // Create some accounts in the disk layer var db ethdb.Database if dir, err := ioutil.TempDir("", "disklayer-test"); err != nil { t.Fatal(err) } else { defer os.RemoveAll(dir) diskdb, err := leveldb.New(dir, 256, 0, "") if err != nil { t.Fatal(err) } db = rawdb.NewDatabase(diskdb) } // Fill even keys [0,2,4...] for i := 0; i < 0xff; i += 2 { acc := common.Hash{byte(i)} rawdb.WriteAccountSnapshot(db, acc, acc[:]) } // Add an 'higher' key, with incorrect (higher) prefix highKey := []byte{rawdb.SnapshotAccountPrefix[0] + 1} db.Put(highKey, []byte{0xff, 0xff}) baseRoot := randomHash() rawdb.WriteSnapshotRoot(db, baseRoot) snaps := &Tree{ layers: map[common.Hash]snapshot{ baseRoot: &diskLayer{ diskdb: db, cache: fastcache.New(500 * 1024), root: baseRoot, }, }, } // Test some different seek positions type testcase struct { pos byte expkey byte } var cases = []testcase{ {0xff, 0x55}, // this should exit immediately without checking key {0x01, 0x02}, {0xfe, 0xfe}, {0xfd, 0xfe}, {0x00, 0x00}, } for i, tc := range cases { it, err := snaps.AccountIterator(baseRoot, common.Hash{tc.pos}) if err != nil { t.Fatalf("case %d, error: %v", i, err) } count := 0 for it.Next() { k, v, err := it.Hash()[0], it.Account()[0], it.Error() if err != nil { t.Fatalf("test %d, item %d, error: %v", i, count, err) } // First item in iterator should have the expected key if count == 0 && k != tc.expkey { t.Fatalf("test %d, item %d, got %v exp %v", i, count, k, tc.expkey) } count++ if v != k { t.Fatalf("test %d, item %d, value wrong, got %v exp %v", i, count, v, k) } } } }