aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMartin Holst Swende <martin@swende.se>2017-10-02 03:07:30 +0800
committerPéter Szilágyi <peterke@gmail.com>2018-03-28 14:29:28 +0800
commit958ed4f3d977b08465915e475e11aaab3d2dc574 (patch)
tree177e7bf727a11cc18237c5299bfceffe56ccee88
parent1a8894b3d59bdf592244b91b6a629f7cf25dcdde (diff)
downloaddexon-958ed4f3d977b08465915e475e11aaab3d2dc574.tar.gz
dexon-958ed4f3d977b08465915e475e11aaab3d2dc574.tar.zst
dexon-958ed4f3d977b08465915e475e11aaab3d2dc574.zip
core/state: rework dirty handling to avoid quadratic overhead
-rw-r--r--core/state/dump.go2
-rw-r--r--core/state/journal.go75
-rw-r--r--core/state/state_object.go51
-rw-r--r--core/state/statedb.go52
-rw-r--r--core/state/statedb_test.go5
-rw-r--r--tests/state_test.go6
6 files changed, 112 insertions, 79 deletions
diff --git a/core/state/dump.go b/core/state/dump.go
index 46e612850..072dbbf05 100644
--- a/core/state/dump.go
+++ b/core/state/dump.go
@@ -53,7 +53,7 @@ func (self *StateDB) RawDump() Dump {
panic(err)
}
- obj := newObject(nil, common.BytesToAddress(addr), data, nil)
+ obj := newObject(nil, common.BytesToAddress(addr), data)
account := DumpAccount{
Balance: data.Balance.String(),
Nonce: data.Nonce,
diff --git a/core/state/journal.go b/core/state/journal.go
index a89bb3d13..b00a46224 100644
--- a/core/state/journal.go
+++ b/core/state/journal.go
@@ -24,9 +24,40 @@ import (
type journalEntry interface {
undo(*StateDB)
+ getAccount() *common.Address
}
-type journal []journalEntry
+type journal struct {
+ entries []journalEntry
+ dirtyOverrides []common.Address
+}
+
+func (j *journal) append(entry journalEntry) {
+ j.entries = append(j.entries, entry)
+}
+
+func (j *journal) flatten() map[common.Address]struct{} {
+
+ dirtyObjects := make(map[common.Address]struct{})
+ for _, journalEntry := range j.entries {
+ if addr := journalEntry.getAccount(); addr != nil {
+ dirtyObjects[*addr] = struct{}{}
+ }
+ }
+ for _, addr := range j.dirtyOverrides {
+ dirtyObjects[addr] = struct{}{}
+ }
+ return dirtyObjects
+}
+
+// Length returns the number of journal entries in the journal
+func (j *journal) Length() int {
+ return len(j.entries)
+}
+
+func (j *journal) dirtyOverride(address common.Address) {
+ j.dirtyOverrides = append(j.dirtyOverrides, address)
+}
type (
// Changes to the account trie.
@@ -82,10 +113,18 @@ func (ch createObjectChange) undo(s *StateDB) {
delete(s.stateObjectsDirty, *ch.account)
}
+func (ch createObjectChange) getAccount() *common.Address {
+ return ch.account
+}
+
func (ch resetObjectChange) undo(s *StateDB) {
s.setStateObject(ch.prev)
}
+func (ch resetObjectChange) getAccount() *common.Address {
+ return nil
+}
+
func (ch suicideChange) undo(s *StateDB) {
obj := s.getStateObject(*ch.account)
if obj != nil {
@@ -93,37 +132,52 @@ func (ch suicideChange) undo(s *StateDB) {
obj.setBalance(ch.prevbalance)
}
}
+func (ch suicideChange) getAccount() *common.Address {
+ return ch.account
+}
var ripemd = common.HexToAddress("0000000000000000000000000000000000000003")
func (ch touchChange) undo(s *StateDB) {
- if !ch.prev && *ch.account != ripemd {
- s.getStateObject(*ch.account).touched = ch.prev
- if !ch.prevDirty {
- delete(s.stateObjectsDirty, *ch.account)
- }
- }
+}
+func (ch touchChange) getAccount() *common.Address {
+ return ch.account
}
func (ch balanceChange) undo(s *StateDB) {
s.getStateObject(*ch.account).setBalance(ch.prev)
}
+func (ch balanceChange) getAccount() *common.Address {
+ return ch.account
+}
func (ch nonceChange) undo(s *StateDB) {
s.getStateObject(*ch.account).setNonce(ch.prev)
}
+func (ch nonceChange) getAccount() *common.Address {
+ return ch.account
+}
func (ch codeChange) undo(s *StateDB) {
s.getStateObject(*ch.account).setCode(common.BytesToHash(ch.prevhash), ch.prevcode)
}
+func (ch codeChange) getAccount() *common.Address {
+ return ch.account
+}
func (ch storageChange) undo(s *StateDB) {
s.getStateObject(*ch.account).setState(ch.key, ch.prevalue)
}
+func (ch storageChange) getAccount() *common.Address {
+ return ch.account
+}
func (ch refundChange) undo(s *StateDB) {
s.refund = ch.prev
}
+func (ch refundChange) getAccount() *common.Address {
+ return nil
+}
func (ch addLogChange) undo(s *StateDB) {
logs := s.logs[ch.txhash]
@@ -134,7 +188,14 @@ func (ch addLogChange) undo(s *StateDB) {
}
s.logSize--
}
+func (ch addLogChange) getAccount() *common.Address {
+ return nil
+}
func (ch addPreimageChange) undo(s *StateDB) {
delete(s.preimages, ch.hash)
}
+
+func (ch addPreimageChange) getAccount() *common.Address {
+ return nil
+}
diff --git a/core/state/state_object.go b/core/state/state_object.go
index b2112bfae..523bb7150 100644
--- a/core/state/state_object.go
+++ b/core/state/state_object.go
@@ -85,9 +85,7 @@ type stateObject struct {
// during the "update" phase of the state transition.
dirtyCode bool // true if the code was updated
suicided bool
- touched bool
deleted bool
- onDirty func(addr common.Address) // Callback method to mark a state object newly dirty
}
// empty returns whether the account is considered empty.
@@ -105,7 +103,7 @@ type Account struct {
}
// newObject creates a state object.
-func newObject(db *StateDB, address common.Address, data Account, onDirty func(addr common.Address)) *stateObject {
+func newObject(db *StateDB, address common.Address, data Account) *stateObject {
if data.Balance == nil {
data.Balance = new(big.Int)
}
@@ -119,7 +117,6 @@ func newObject(db *StateDB, address common.Address, data Account, onDirty func(a
data: data,
cachedStorage: make(Storage),
dirtyStorage: make(Storage),
- onDirty: onDirty,
}
}
@@ -137,23 +134,17 @@ func (self *stateObject) setError(err error) {
func (self *stateObject) markSuicided() {
self.suicided = true
- if self.onDirty != nil {
- self.onDirty(self.Address())
- self.onDirty = nil
- }
}
func (c *stateObject) touch() {
- c.db.journal = append(c.db.journal, touchChange{
- account: &c.address,
- prev: c.touched,
- prevDirty: c.onDirty == nil,
+ c.db.journal.append(touchChange{
+ account: &c.address,
})
- if c.onDirty != nil {
- c.onDirty(c.Address())
- c.onDirty = nil
+ if c.address == ripemd {
+ //Explicitly put it in the dirty-cache, which is otherwise
+ // generated from flattened journals
+ c.db.journal.dirtyOverride(c.address)
}
- c.touched = true
}
func (c *stateObject) getTrie(db Database) Trie {
@@ -195,7 +186,7 @@ func (self *stateObject) GetState(db Database, key common.Hash) common.Hash {
// SetState updates a value in account storage.
func (self *stateObject) SetState(db Database, key, value common.Hash) {
- self.db.journal = append(self.db.journal, storageChange{
+ self.db.journal.append(storageChange{
account: &self.address,
key: key,
prevalue: self.GetState(db, key),
@@ -207,10 +198,6 @@ func (self *stateObject) setState(key, value common.Hash) {
self.cachedStorage[key] = value
self.dirtyStorage[key] = value
- if self.onDirty != nil {
- self.onDirty(self.Address())
- self.onDirty = nil
- }
}
// updateTrie writes cached storage modifications into the object's storage trie.
@@ -274,7 +261,7 @@ func (c *stateObject) SubBalance(amount *big.Int) {
}
func (self *stateObject) SetBalance(amount *big.Int) {
- self.db.journal = append(self.db.journal, balanceChange{
+ self.db.journal.append(balanceChange{
account: &self.address,
prev: new(big.Int).Set(self.data.Balance),
})
@@ -283,17 +270,13 @@ func (self *stateObject) SetBalance(amount *big.Int) {
func (self *stateObject) setBalance(amount *big.Int) {
self.data.Balance = amount
- if self.onDirty != nil {
- self.onDirty(self.Address())
- self.onDirty = nil
- }
}
// Return the gas back to the origin. Used by the Virtual machine or Closures
func (c *stateObject) ReturnGas(gas *big.Int) {}
-func (self *stateObject) deepCopy(db *StateDB, onDirty func(addr common.Address)) *stateObject {
- stateObject := newObject(db, self.address, self.data, onDirty)
+func (self *stateObject) deepCopy(db *StateDB) *stateObject {
+ stateObject := newObject(db, self.address, self.data)
if self.trie != nil {
stateObject.trie = db.db.CopyTrie(self.trie)
}
@@ -333,7 +316,7 @@ func (self *stateObject) Code(db Database) []byte {
func (self *stateObject) SetCode(codeHash common.Hash, code []byte) {
prevcode := self.Code(self.db.db)
- self.db.journal = append(self.db.journal, codeChange{
+ self.db.journal.append(codeChange{
account: &self.address,
prevhash: self.CodeHash(),
prevcode: prevcode,
@@ -345,14 +328,10 @@ func (self *stateObject) setCode(codeHash common.Hash, code []byte) {
self.code = code
self.data.CodeHash = codeHash[:]
self.dirtyCode = true
- if self.onDirty != nil {
- self.onDirty(self.Address())
- self.onDirty = nil
- }
}
func (self *stateObject) SetNonce(nonce uint64) {
- self.db.journal = append(self.db.journal, nonceChange{
+ self.db.journal.append(nonceChange{
account: &self.address,
prev: self.data.Nonce,
})
@@ -361,10 +340,6 @@ func (self *stateObject) SetNonce(nonce uint64) {
func (self *stateObject) setNonce(nonce uint64) {
self.data.Nonce = nonce
- if self.onDirty != nil {
- self.onDirty(self.Address())
- self.onDirty = nil
- }
}
func (self *stateObject) CodeHash() []byte {
diff --git a/core/state/statedb.go b/core/state/statedb.go
index bd67e789d..7a88b3b16 100644
--- a/core/state/statedb.go
+++ b/core/state/statedb.go
@@ -131,7 +131,7 @@ func (self *StateDB) Reset(root common.Hash) error {
}
func (self *StateDB) AddLog(log *types.Log) {
- self.journal = append(self.journal, addLogChange{txhash: self.thash})
+ self.journal.append(addLogChange{txhash: self.thash})
log.TxHash = self.thash
log.BlockHash = self.bhash
@@ -156,7 +156,7 @@ func (self *StateDB) Logs() []*types.Log {
// AddPreimage records a SHA3 preimage seen by the VM.
func (self *StateDB) AddPreimage(hash common.Hash, preimage []byte) {
if _, ok := self.preimages[hash]; !ok {
- self.journal = append(self.journal, addPreimageChange{hash: hash})
+ self.journal.append(addPreimageChange{hash: hash})
pi := make([]byte, len(preimage))
copy(pi, preimage)
self.preimages[hash] = pi
@@ -169,7 +169,7 @@ func (self *StateDB) Preimages() map[common.Hash][]byte {
}
func (self *StateDB) AddRefund(gas uint64) {
- self.journal = append(self.journal, refundChange{prev: self.refund})
+ self.journal.append(refundChange{prev: self.refund})
self.refund += gas
}
@@ -255,7 +255,7 @@ func (self *StateDB) StorageTrie(addr common.Address) Trie {
if stateObject == nil {
return nil
}
- cpy := stateObject.deepCopy(self, nil)
+ cpy := stateObject.deepCopy(self)
return cpy.updateTrie(self.db)
}
@@ -325,7 +325,7 @@ func (self *StateDB) Suicide(addr common.Address) bool {
if stateObject == nil {
return false
}
- self.journal = append(self.journal, suicideChange{
+ self.journal.append(suicideChange{
account: &addr,
prev: stateObject.suicided,
prevbalance: new(big.Int).Set(stateObject.Balance()),
@@ -379,7 +379,7 @@ func (self *StateDB) getStateObject(addr common.Address) (stateObject *stateObje
return nil
}
// Insert into the live set.
- obj := newObject(self, addr, data, self.MarkStateObjectDirty)
+ obj := newObject(self, addr, data)
self.setStateObject(obj)
return obj
}
@@ -397,22 +397,16 @@ func (self *StateDB) GetOrNewStateObject(addr common.Address) *stateObject {
return stateObject
}
-// MarkStateObjectDirty adds the specified object to the dirty map to avoid costly
-// state object cache iteration to find a handful of modified ones.
-func (self *StateDB) MarkStateObjectDirty(addr common.Address) {
- self.stateObjectsDirty[addr] = struct{}{}
-}
-
// createObject creates a new state object. If there is an existing account with
// the given address, it is overwritten and returned as the second return value.
func (self *StateDB) createObject(addr common.Address) (newobj, prev *stateObject) {
prev = self.getStateObject(addr)
- newobj = newObject(self, addr, Account{}, self.MarkStateObjectDirty)
+ newobj = newObject(self, addr, Account{})
newobj.setNonce(0) // sets the object to dirty
if prev == nil {
- self.journal = append(self.journal, createObjectChange{account: &addr})
+ self.journal.append(createObjectChange{account: &addr})
} else {
- self.journal = append(self.journal, resetObjectChange{prev: prev})
+ self.journal.append(resetObjectChange{prev: prev})
}
self.setStateObject(newobj)
return newobj, prev
@@ -462,20 +456,22 @@ func (self *StateDB) Copy() *StateDB {
self.lock.Lock()
defer self.lock.Unlock()
+ dirtyObjects := self.journal.flatten()
+
// Copy all the basic fields, initialize the memory ones
state := &StateDB{
db: self.db,
trie: self.db.CopyTrie(self.trie),
- stateObjects: make(map[common.Address]*stateObject, len(self.stateObjectsDirty)),
- stateObjectsDirty: make(map[common.Address]struct{}, len(self.stateObjectsDirty)),
+ stateObjects: make(map[common.Address]*stateObject, len(dirtyObjects)),
+ stateObjectsDirty: make(map[common.Address]struct{}, len(dirtyObjects)),
refund: self.refund,
logs: make(map[common.Hash][]*types.Log, len(self.logs)),
logSize: self.logSize,
preimages: make(map[common.Hash][]byte),
}
// Copy the dirty states, logs, and preimages
- for addr := range self.stateObjectsDirty {
- state.stateObjects[addr] = self.stateObjects[addr].deepCopy(state, state.MarkStateObjectDirty)
+ for addr := range dirtyObjects {
+ state.stateObjects[addr] = self.stateObjects[addr].deepCopy(state)
state.stateObjectsDirty[addr] = struct{}{}
}
for hash, logs := range self.logs {
@@ -492,7 +488,7 @@ func (self *StateDB) Copy() *StateDB {
func (self *StateDB) Snapshot() int {
id := self.nextRevisionId
self.nextRevisionId++
- self.validRevisions = append(self.validRevisions, revision{id, len(self.journal)})
+ self.validRevisions = append(self.validRevisions, revision{id, self.journal.Length()})
return id
}
@@ -508,10 +504,10 @@ func (self *StateDB) RevertToSnapshot(revid int) {
snapshot := self.validRevisions[idx].journalIndex
// Replay the journal to undo changes.
- for i := len(self.journal) - 1; i >= snapshot; i-- {
- self.journal[i].undo(self)
+ for i := self.journal.Length() - 1; i >= snapshot; i-- {
+ self.journal.entries[i].undo(self)
}
- self.journal = self.journal[:snapshot]
+ self.journal.entries = self.journal.entries[:snapshot]
// Remove invalidated snapshots from the stack.
self.validRevisions = self.validRevisions[:idx]
@@ -525,7 +521,8 @@ func (self *StateDB) GetRefund() uint64 {
// Finalise finalises the state by removing the self destructed objects
// and clears the journal as well as the refunds.
func (s *StateDB) Finalise(deleteEmptyObjects bool) {
- for addr := range s.stateObjectsDirty {
+
+ for addr, v := range s.journal.flatten() {
stateObject := s.stateObjects[addr]
if stateObject.suicided || (deleteEmptyObjects && stateObject.empty()) {
s.deleteStateObject(stateObject)
@@ -533,6 +530,7 @@ func (s *StateDB) Finalise(deleteEmptyObjects bool) {
stateObject.updateRoot(s.db)
s.updateStateObject(stateObject)
}
+ s.stateObjectsDirty[addr] = v
}
// Invalidate journal because reverting across transactions is not allowed.
s.clearJournalAndRefund()
@@ -576,7 +574,7 @@ func (s *StateDB) DeleteSuicides() {
}
func (s *StateDB) clearJournalAndRefund() {
- s.journal = nil
+ s.journal = journal{}
s.validRevisions = s.validRevisions[:0]
s.refund = 0
}
@@ -585,6 +583,10 @@ func (s *StateDB) clearJournalAndRefund() {
func (s *StateDB) Commit(deleteEmptyObjects bool) (root common.Hash, err error) {
defer s.clearJournalAndRefund()
+ for addr, v := range s.journal.flatten() {
+ s.stateObjectsDirty[addr] = v
+ }
+
// Commit objects to the trie.
for addr, stateObject := range s.stateObjects {
_, isDirty := s.stateObjectsDirty[addr]
diff --git a/core/state/statedb_test.go b/core/state/statedb_test.go
index d9e3d9b79..05bc0499b 100644
--- a/core/state/statedb_test.go
+++ b/core/state/statedb_test.go
@@ -413,11 +413,12 @@ func (s *StateSuite) TestTouchDelete(c *check.C) {
snapshot := s.state.Snapshot()
s.state.AddBalance(common.Address{}, new(big.Int))
- if len(s.state.stateObjectsDirty) != 1 {
+
+ if len(s.state.journal.flatten()) != 1 {
c.Fatal("expected one dirty state object")
}
s.state.RevertToSnapshot(snapshot)
- if len(s.state.stateObjectsDirty) != 0 {
+ if len(s.state.journal.flatten()) != 0 {
c.Fatal("expected no dirty state object")
}
}
diff --git a/tests/state_test.go b/tests/state_test.go
index 9ca5f1830..3fd3ce43a 100644
--- a/tests/state_test.go
+++ b/tests/state_test.go
@@ -36,14 +36,8 @@ func TestState(t *testing.T) {
st.skipLoad(`^stTransactionTest/zeroSigTransa[^/]*\.json`) // EIP-86 is not supported yet
// Expected failures:
st.fails(`^stRevertTest/RevertPrecompiledTouch\.json/EIP158`, "bug in test")
- st.fails(`^stRevertTest/RevertPrefoundEmptyOOG\.json/EIP158`, "bug in test")
st.fails(`^stRevertTest/RevertPrecompiledTouch\.json/Byzantium`, "bug in test")
- st.fails(`^stRevertTest/RevertPrefoundEmptyOOG\.json/Byzantium`, "bug in test")
st.fails(`^stRandom2/randomStatetest64[45]\.json/(EIP150|Frontier|Homestead)/.*`, "known bug #15119")
- st.fails(`^stCreateTest/TransactionCollisionToEmpty\.json/EIP158/2`, "known bug ")
- st.fails(`^stCreateTest/TransactionCollisionToEmpty\.json/EIP158/3`, "known bug ")
- st.fails(`^stCreateTest/TransactionCollisionToEmpty\.json/Byzantium/2`, "known bug ")
- st.fails(`^stCreateTest/TransactionCollisionToEmpty\.json/Byzantium/3`, "known bug ")
st.walk(t, stateTestDir, func(t *testing.T, name string, test *StateTest) {
for _, subtest := range test.Subtests() {