diff options
author | Péter Szilágyi <peterke@gmail.com> | 2016-02-23 16:26:25 +0800 |
---|---|---|
committer | Péter Szilágyi <peterke@gmail.com> | 2016-02-23 16:26:25 +0800 |
commit | 3dca9cc550ff2b972815008e45b6a2ff1cf74af1 (patch) | |
tree | e562e5095a7b76bd3b8241ad319094cf052f6109 /core | |
parent | f8d98f7fcd08bd2eff36d5366ac2a14b52255d57 (diff) | |
parent | b8d59d9c985feed9ec1d8851f65517c7e5c09deb (diff) | |
download | dexon-3dca9cc550ff2b972815008e45b6a2ff1cf74af1.tar dexon-3dca9cc550ff2b972815008e45b6a2ff1cf74af1.tar.gz dexon-3dca9cc550ff2b972815008e45b6a2ff1cf74af1.tar.bz2 dexon-3dca9cc550ff2b972815008e45b6a2ff1cf74af1.tar.lz dexon-3dca9cc550ff2b972815008e45b6a2ff1cf74af1.tar.xz dexon-3dca9cc550ff2b972815008e45b6a2ff1cf74af1.tar.zst dexon-3dca9cc550ff2b972815008e45b6a2ff1cf74af1.zip |
Merge pull request #2095 from karalabe/trie-node-iterator
core/state, trie: add node iterator, test state/trie sync consistency
Diffstat (limited to 'core')
-rw-r--r-- | core/state/iterator.go | 160 | ||||
-rw-r--r-- | core/state/iterator_test.go | 57 | ||||
-rw-r--r-- | core/state/sync_test.go | 100 |
3 files changed, 314 insertions, 3 deletions
diff --git a/core/state/iterator.go b/core/state/iterator.go new file mode 100644 index 000000000..9d8a69b7c --- /dev/null +++ b/core/state/iterator.go @@ -0,0 +1,160 @@ +// Copyright 2015 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 <http://www.gnu.org/licenses/>. + +package state + +import ( + "bytes" + "fmt" + "math/big" + + "github.com/ethereum/go-ethereum/common" + "github.com/ethereum/go-ethereum/rlp" + "github.com/ethereum/go-ethereum/trie" +) + +// NodeIterator is an iterator to traverse the entire state trie post-order, +// including all of the contract code and contract state tries. +type NodeIterator struct { + state *StateDB // State being iterated + + stateIt *trie.NodeIterator // Primary iterator for the global state trie + dataIt *trie.NodeIterator // Secondary iterator for the data trie of a contract + + accountHash common.Hash // Hash of the node containing the account + codeHash common.Hash // Hash of the contract source code + code []byte // Source code associated with a contract + + Hash common.Hash // Hash of the current entry being iterated (nil if not standalone) + Entry interface{} // Current state entry being iterated (internal representation) + Parent common.Hash // Hash of the first full ancestor node (nil if current is the root) + + Error error // Failure set in case of an internal error in the iterator +} + +// NewNodeIterator creates an post-order state node iterator. +func NewNodeIterator(state *StateDB) *NodeIterator { + return &NodeIterator{ + state: state, + } +} + +// Next moves the iterator to the next node, returning whether there are any +// further nodes. In case of an internal error this method returns false and +// sets the Error field to the encountered failure. +func (it *NodeIterator) Next() bool { + // If the iterator failed previously, don't do anything + if it.Error != nil { + return false + } + // Otherwise step forward with the iterator and report any errors + if err := it.step(); err != nil { + it.Error = err + return false + } + return it.retrieve() +} + +// step moves the iterator to the next entry of the state trie. +func (it *NodeIterator) step() error { + // Abort if we reached the end of the iteration + if it.state == nil { + return nil + } + // Initialize the iterator if we've just started + if it.stateIt == nil { + it.stateIt = trie.NewNodeIterator(it.state.trie.Trie) + } + // If we had data nodes previously, we surely have at least state nodes + if it.dataIt != nil { + if cont := it.dataIt.Next(); !cont { + if it.dataIt.Error != nil { + return it.dataIt.Error + } + it.dataIt = nil + } + return nil + } + // If we had source code previously, discard that + if it.code != nil { + it.code = nil + return nil + } + // Step to the next state trie node, terminating if we're out of nodes + if cont := it.stateIt.Next(); !cont { + if it.stateIt.Error != nil { + return it.stateIt.Error + } + it.state, it.stateIt = nil, nil + return nil + } + // If the state trie node is an internal entry, leave as is + if !it.stateIt.Leaf { + return nil + } + // Otherwise we've reached an account node, initiate data iteration + var account struct { + Nonce uint64 + Balance *big.Int + Root common.Hash + CodeHash []byte + } + if err := rlp.Decode(bytes.NewReader(it.stateIt.LeafBlob), &account); err != nil { + return err + } + dataTrie, err := trie.New(account.Root, it.state.db) + if err != nil { + return err + } + it.dataIt = trie.NewNodeIterator(dataTrie) + if !it.dataIt.Next() { + it.dataIt = nil + } + if bytes.Compare(account.CodeHash, emptyCodeHash) != 0 { + it.codeHash = common.BytesToHash(account.CodeHash) + it.code, err = it.state.db.Get(account.CodeHash) + if err != nil { + return fmt.Errorf("code %x: %v", account.CodeHash, err) + } + } + it.accountHash = it.stateIt.Parent + return nil +} + +// retrieve pulls and caches the current state entry the iterator is traversing. +// The method returns whether there are any more data left for inspection. +func (it *NodeIterator) retrieve() bool { + // Clear out any previously set values + it.Hash, it.Entry = common.Hash{}, nil + + // If the iteration's done, return no available data + if it.state == nil { + return false + } + // Otherwise retrieve the current entry + switch { + case it.dataIt != nil: + it.Hash, it.Entry, it.Parent = it.dataIt.Hash, it.dataIt.Node, it.dataIt.Parent + if it.Parent == (common.Hash{}) { + it.Parent = it.accountHash + } + case it.code != nil: + it.Hash, it.Entry, it.Parent = it.codeHash, it.code, it.accountHash + case it.stateIt != nil: + it.Hash, it.Entry, it.Parent = it.stateIt.Hash, it.stateIt.Node, it.stateIt.Parent + } + return true +} diff --git a/core/state/iterator_test.go b/core/state/iterator_test.go new file mode 100644 index 000000000..8b68870c6 --- /dev/null +++ b/core/state/iterator_test.go @@ -0,0 +1,57 @@ +// Copyright 2015 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 <http://www.gnu.org/licenses/>. + +package state + +import ( + "bytes" + "testing" + + "github.com/ethereum/go-ethereum/common" + "github.com/ethereum/go-ethereum/ethdb" +) + +// Tests that the node iterator indeed walks over the entire database contents. +func TestNodeIteratorCoverage(t *testing.T) { + // Create some arbitrary test state to iterate + db, root, _ := makeTestState() + + state, err := New(root, db) + if err != nil { + t.Fatalf("failed to create state trie at %x: %v", root, err) + } + // Gather all the node hashes found by the iterator + hashes := make(map[common.Hash]struct{}) + for it := NewNodeIterator(state); it.Next(); { + if it.Hash != (common.Hash{}) { + hashes[it.Hash] = struct{}{} + } + } + // Cross check the hashes and the database itself + for hash, _ := range hashes { + if _, err := db.Get(hash.Bytes()); err != nil { + t.Errorf("failed to retrieve reported node %x: %v", hash, err) + } + } + for _, key := range db.(*ethdb.MemDatabase).Keys() { + if bytes.HasPrefix(key, []byte("secure-key-")) { + continue + } + if _, ok := hashes[common.BytesToHash(key)]; !ok { + t.Errorf("state entry not reported %x", key) + } + } +} diff --git a/core/state/sync_test.go b/core/state/sync_test.go index 0dab372ba..a2a1edbdb 100644 --- a/core/state/sync_test.go +++ b/core/state/sync_test.go @@ -22,6 +22,7 @@ import ( "testing" "github.com/ethereum/go-ethereum/common" + "github.com/ethereum/go-ethereum/crypto" "github.com/ethereum/go-ethereum/ethdb" "github.com/ethereum/go-ethereum/trie" ) @@ -42,7 +43,7 @@ func makeTestState() (ethdb.Database, common.Hash, []*testAccount) { // Fill it with some arbitrary data accounts := []*testAccount{} - for i := byte(0); i < 255; i++ { + for i := byte(0); i < 96; i++ { obj := state.GetOrNewStateObject(common.BytesToAddress([]byte{i})) acc := &testAccount{address: common.BytesToAddress([]byte{i})} @@ -61,6 +62,9 @@ func makeTestState() (ethdb.Database, common.Hash, []*testAccount) { } root, _ := state.Commit() + // Remove any potentially cached data from the test state creation + trie.ClearGlobalCache() + // Return the generated state return db, root, accounts } @@ -68,9 +72,18 @@ func makeTestState() (ethdb.Database, common.Hash, []*testAccount) { // checkStateAccounts cross references a reconstructed state with an expected // account array. func checkStateAccounts(t *testing.T, db ethdb.Database, root common.Hash, accounts []*testAccount) { - state, _ := New(root, db) - for i, acc := range accounts { + // Remove any potentially cached data from the state synchronisation + trie.ClearGlobalCache() + // Check root availability and state contents + state, err := New(root, db) + if err != nil { + t.Fatalf("failed to create state trie at %x: %v", root, err) + } + if err := checkStateConsistency(db, root); err != nil { + t.Fatalf("inconsistent state trie at %x: %v", root, err) + } + for i, acc := range accounts { if balance := state.GetBalance(acc.address); balance.Cmp(acc.balance) != 0 { t.Errorf("account %d: balance mismatch: have %v, want %v", i, balance, acc.balance) } @@ -83,6 +96,25 @@ func checkStateAccounts(t *testing.T, db ethdb.Database, root common.Hash, accou } } +// checkStateConsistency checks that all nodes in a state trie are indeed present. +func checkStateConsistency(db ethdb.Database, root common.Hash) error { + // Remove any potentially cached data from the test state creation or previous checks + trie.ClearGlobalCache() + + // Create and iterate a state trie rooted in a sub-node + if _, err := db.Get(root.Bytes()); err != nil { + return nil // Consider a non existent state consistent + } + state, err := New(root, db) + if err != nil { + return err + } + it := NewNodeIterator(state) + for it.Next() { + } + return it.Error +} + // Tests that an empty state is not scheduled for syncing. func TestEmptyStateSync(t *testing.T) { empty := common.HexToHash("56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421") @@ -236,3 +268,65 @@ func TestIterativeRandomDelayedStateSync(t *testing.T) { // Cross check that the two states are in sync checkStateAccounts(t, dstDb, srcRoot, srcAccounts) } + +// Tests that at any point in time during a sync, only complete sub-tries are in +// the database. +func TestIncompleteStateSync(t *testing.T) { + // Create a random state to copy + srcDb, srcRoot, srcAccounts := makeTestState() + + // Create a destination state and sync with the scheduler + dstDb, _ := ethdb.NewMemDatabase() + sched := NewStateSync(srcRoot, dstDb) + + added := []common.Hash{} + queue := append([]common.Hash{}, sched.Missing(1)...) + for len(queue) > 0 { + // Fetch a batch of state nodes + results := make([]trie.SyncResult, len(queue)) + for i, hash := range queue { + data, err := srcDb.Get(hash.Bytes()) + if err != nil { + t.Fatalf("failed to retrieve node data for %x: %v", hash, err) + } + results[i] = trie.SyncResult{hash, data} + } + // Process each of the state nodes + if index, err := sched.Process(results); err != nil { + t.Fatalf("failed to process result #%d: %v", index, err) + } + for _, result := range results { + added = append(added, result.Hash) + } + // Check that all known sub-tries in the synced state is complete + for _, root := range added { + // Skim through the accounts and make sure the root hash is not a code node + codeHash := false + for _, acc := range srcAccounts { + if bytes.Compare(root.Bytes(), crypto.Sha3(acc.code)) == 0 { + codeHash = true + break + } + } + // If the root is a real trie node, check consistency + if !codeHash { + if err := checkStateConsistency(dstDb, root); err != nil { + t.Fatalf("state inconsistent: %v", err) + } + } + } + // Fetch the next batch to retrieve + queue = append(queue[:0], sched.Missing(1)...) + } + // Sanity check that removing any node from the database is detected + for _, node := range added[1:] { + key := node.Bytes() + value, _ := dstDb.Get(key) + + dstDb.Delete(key) + if err := checkStateConsistency(dstDb, added[0]); err == nil { + t.Fatalf("trie inconsistency not caught, missing: %x", key) + } + dstDb.Put(key, value) + } +} |