From 958ed4f3d977b08465915e475e11aaab3d2dc574 Mon Sep 17 00:00:00 2001
From: Martin Holst Swende <martin@swende.se>
Date: Sun, 1 Oct 2017 21:07:30 +0200
Subject: core/state: rework dirty handling to avoid quadratic overhead

---
 core/state/dump.go         |  2 +-
 core/state/journal.go      | 75 +++++++++++++++++++++++++++++++++++++++++-----
 core/state/state_object.go | 51 ++++++++-----------------------
 core/state/statedb.go      | 52 ++++++++++++++++----------------
 core/state/statedb_test.go |  5 ++--
 tests/state_test.go        |  6 ----
 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() {
-- 
cgit v1.2.3


From d985b9052ae08f2538e6caa7e6b5ef351a00bc3e Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?P=C3=A9ter=20Szil=C3=A1gyi?= <peterke@gmail.com>
Date: Tue, 27 Mar 2018 15:13:30 +0300
Subject: core/state: avoid linear overhead on journal dirty listing

---
 core/state/journal.go      | 113 +++++++++++++++++++++++++++++----------------
 core/state/state_object.go |   6 +--
 core/state/statedb.go      |  35 ++++++--------
 core/state/statedb_test.go |   4 +-
 4 files changed, 92 insertions(+), 66 deletions(-)

diff --git a/core/state/journal.go b/core/state/journal.go
index b00a46224..a03ca57db 100644
--- a/core/state/journal.go
+++ b/core/state/journal.go
@@ -22,41 +22,66 @@ import (
 	"github.com/ethereum/go-ethereum/common"
 )
 
+// journalEntry is a modification entry in the state change journal that can be
+// reverted on demand.
 type journalEntry interface {
-	undo(*StateDB)
-	getAccount() *common.Address
+	// revert undoes the changes introduced by this journal entry.
+	revert(*StateDB)
+
+	// dirtied returns the Ethereum address modified by this journal entry.
+	dirtied() *common.Address
 }
 
+// journal contains the list of state modifications applied since the last state
+// commit. These are tracked to be able to be reverted in case of an execution
+// exception or revertal request.
 type journal struct {
-	entries        []journalEntry
-	dirtyOverrides []common.Address
+	entries []journalEntry         // Current changes tracked by the journal
+	dirties map[common.Address]int // Dirty accounts and the number of changes
+}
+
+// newJournal create a new initialized journal.
+func newJournal() *journal {
+	return &journal{
+		dirties: make(map[common.Address]int),
+	}
 }
 
+// append inserts a new modification entry to the end of the change journal.
 func (j *journal) append(entry journalEntry) {
 	j.entries = append(j.entries, entry)
+	if addr := entry.dirtied(); addr != nil {
+		j.dirties[*addr]++
+	}
 }
 
-func (j *journal) flatten() map[common.Address]struct{} {
+// revert undoes a batch of journalled modifications along with any reverted
+// dirty handling too.
+func (j *journal) revert(statedb *StateDB, snapshot int) {
+	for i := len(j.entries) - 1; i >= snapshot; i-- {
+		// Undo the changes made by the operation
+		j.entries[i].revert(statedb)
 
-	dirtyObjects := make(map[common.Address]struct{})
-	for _, journalEntry := range j.entries {
-		if addr := journalEntry.getAccount(); addr != nil {
-			dirtyObjects[*addr] = struct{}{}
+		// Drop any dirty tracking induced by the change
+		if addr := j.entries[i].dirtied(); addr != nil {
+			if j.dirties[*addr]--; j.dirties[*addr] == 0 {
+				delete(j.dirties, *addr)
+			}
 		}
 	}
-	for _, addr := range j.dirtyOverrides {
-		dirtyObjects[addr] = struct{}{}
-	}
-	return dirtyObjects
+	j.entries = j.entries[:snapshot]
 }
 
-// Length returns the number of journal entries in the journal
-func (j *journal) Length() int {
-	return len(j.entries)
+// dirty explicitly sets an address to dirty, even if the change entries would
+// otherwise suggest it as clean. This method is an ugly hack to handle the RIPEMD
+// precompile consensus exception.
+func (j *journal) dirty(addr common.Address) {
+	j.dirties[addr]++
 }
 
-func (j *journal) dirtyOverride(address common.Address) {
-	j.dirtyOverrides = append(j.dirtyOverrides, address)
+// length returns the current number of entries in the journal.
+func (j *journal) length() int {
+	return len(j.entries)
 }
 
 type (
@@ -108,78 +133,85 @@ type (
 	}
 )
 
-func (ch createObjectChange) undo(s *StateDB) {
+func (ch createObjectChange) revert(s *StateDB) {
 	delete(s.stateObjects, *ch.account)
 	delete(s.stateObjectsDirty, *ch.account)
 }
 
-func (ch createObjectChange) getAccount() *common.Address {
+func (ch createObjectChange) dirtied() *common.Address {
 	return ch.account
 }
 
-func (ch resetObjectChange) undo(s *StateDB) {
+func (ch resetObjectChange) revert(s *StateDB) {
 	s.setStateObject(ch.prev)
 }
 
-func (ch resetObjectChange) getAccount() *common.Address {
+func (ch resetObjectChange) dirtied() *common.Address {
 	return nil
 }
 
-func (ch suicideChange) undo(s *StateDB) {
+func (ch suicideChange) revert(s *StateDB) {
 	obj := s.getStateObject(*ch.account)
 	if obj != nil {
 		obj.suicided = ch.prev
 		obj.setBalance(ch.prevbalance)
 	}
 }
-func (ch suicideChange) getAccount() *common.Address {
+
+func (ch suicideChange) dirtied() *common.Address {
 	return ch.account
 }
 
 var ripemd = common.HexToAddress("0000000000000000000000000000000000000003")
 
-func (ch touchChange) undo(s *StateDB) {
+func (ch touchChange) revert(s *StateDB) {
 }
-func (ch touchChange) getAccount() *common.Address {
+
+func (ch touchChange) dirtied() *common.Address {
 	return ch.account
 }
 
-func (ch balanceChange) undo(s *StateDB) {
+func (ch balanceChange) revert(s *StateDB) {
 	s.getStateObject(*ch.account).setBalance(ch.prev)
 }
-func (ch balanceChange) getAccount() *common.Address {
+
+func (ch balanceChange) dirtied() *common.Address {
 	return ch.account
 }
 
-func (ch nonceChange) undo(s *StateDB) {
+func (ch nonceChange) revert(s *StateDB) {
 	s.getStateObject(*ch.account).setNonce(ch.prev)
 }
 
-func (ch nonceChange) getAccount() *common.Address {
+func (ch nonceChange) dirtied() *common.Address {
 	return ch.account
 }
-func (ch codeChange) undo(s *StateDB) {
+
+func (ch codeChange) revert(s *StateDB) {
 	s.getStateObject(*ch.account).setCode(common.BytesToHash(ch.prevhash), ch.prevcode)
 }
-func (ch codeChange) getAccount() *common.Address {
+
+func (ch codeChange) dirtied() *common.Address {
 	return ch.account
 }
 
-func (ch storageChange) undo(s *StateDB) {
+func (ch storageChange) revert(s *StateDB) {
 	s.getStateObject(*ch.account).setState(ch.key, ch.prevalue)
 }
-func (ch storageChange) getAccount() *common.Address {
+
+func (ch storageChange) dirtied() *common.Address {
 	return ch.account
 }
 
-func (ch refundChange) undo(s *StateDB) {
+func (ch refundChange) revert(s *StateDB) {
 	s.refund = ch.prev
 }
-func (ch refundChange) getAccount() *common.Address {
+
+func (ch refundChange) dirtied() *common.Address {
 	return nil
 }
 
-func (ch addLogChange) undo(s *StateDB) {
+func (ch addLogChange) revert(s *StateDB) {
 	logs := s.logs[ch.txhash]
 	if len(logs) == 1 {
 		delete(s.logs, ch.txhash)
@@ -188,14 +220,15 @@ func (ch addLogChange) undo(s *StateDB) {
 	}
 	s.logSize--
 }
-func (ch addLogChange) getAccount() *common.Address {
+
+func (ch addLogChange) dirtied() *common.Address {
 	return nil
 }
 
-func (ch addPreimageChange) undo(s *StateDB) {
+func (ch addPreimageChange) revert(s *StateDB) {
 	delete(s.preimages, ch.hash)
 }
 
-func (ch addPreimageChange) getAccount() *common.Address {
+func (ch addPreimageChange) dirtied() *common.Address {
 	return nil
 }
diff --git a/core/state/state_object.go b/core/state/state_object.go
index 523bb7150..3c40c2041 100644
--- a/core/state/state_object.go
+++ b/core/state/state_object.go
@@ -141,9 +141,9 @@ func (c *stateObject) touch() {
 		account: &c.address,
 	})
 	if c.address == ripemd {
-		//Explicitly put it in the dirty-cache, which is otherwise
-		// generated from flattened journals
-		c.db.journal.dirtyOverride(c.address)
+		// Explicitly put it in the dirty-cache, which is otherwise generated from
+		// flattened journals.
+		c.db.journal.dirty(c.address)
 	}
 }
 
diff --git a/core/state/statedb.go b/core/state/statedb.go
index 7a88b3b16..c7ef49f64 100644
--- a/core/state/statedb.go
+++ b/core/state/statedb.go
@@ -76,7 +76,7 @@ type StateDB struct {
 
 	// Journal of state modifications. This is the backbone of
 	// Snapshot and RevertToSnapshot.
-	journal        journal
+	journal        *journal
 	validRevisions []revision
 	nextRevisionId int
 
@@ -96,6 +96,7 @@ func New(root common.Hash, db Database) (*StateDB, error) {
 		stateObjectsDirty: make(map[common.Address]struct{}),
 		logs:              make(map[common.Hash][]*types.Log),
 		preimages:         make(map[common.Hash][]byte),
+		journal:           newJournal(),
 	}, nil
 }
 
@@ -456,21 +457,20 @@ 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(dirtyObjects)),
-		stateObjectsDirty: make(map[common.Address]struct{}, len(dirtyObjects)),
+		stateObjects:      make(map[common.Address]*stateObject, len(self.journal.dirties)),
+		stateObjectsDirty: make(map[common.Address]struct{}, len(self.journal.dirties)),
 		refund:            self.refund,
 		logs:              make(map[common.Hash][]*types.Log, len(self.logs)),
 		logSize:           self.logSize,
 		preimages:         make(map[common.Hash][]byte),
+		journal:           newJournal(),
 	}
 	// Copy the dirty states, logs, and preimages
-	for addr := range dirtyObjects {
+	for addr := range self.journal.dirties {
 		state.stateObjects[addr] = self.stateObjects[addr].deepCopy(state)
 		state.stateObjectsDirty[addr] = struct{}{}
 	}
@@ -488,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, self.journal.Length()})
+	self.validRevisions = append(self.validRevisions, revision{id, self.journal.length()})
 	return id
 }
 
@@ -503,13 +503,8 @@ func (self *StateDB) RevertToSnapshot(revid int) {
 	}
 	snapshot := self.validRevisions[idx].journalIndex
 
-	// Replay the journal to undo changes.
-	for i := self.journal.Length() - 1; i >= snapshot; i-- {
-		self.journal.entries[i].undo(self)
-	}
-	self.journal.entries = self.journal.entries[:snapshot]
-
-	// Remove invalidated snapshots from the stack.
+	// Replay the journal to undo changes and remove invalidated snapshots
+	self.journal.revert(self, snapshot)
 	self.validRevisions = self.validRevisions[:idx]
 }
 
@@ -521,8 +516,7 @@ 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, v := range s.journal.flatten() {
+	for addr := range s.journal.dirties {
 		stateObject := s.stateObjects[addr]
 		if stateObject.suicided || (deleteEmptyObjects && stateObject.empty()) {
 			s.deleteStateObject(stateObject)
@@ -530,7 +524,7 @@ func (s *StateDB) Finalise(deleteEmptyObjects bool) {
 			stateObject.updateRoot(s.db)
 			s.updateStateObject(stateObject)
 		}
-		s.stateObjectsDirty[addr] = v
+		s.stateObjectsDirty[addr] = struct{}{}
 	}
 	// Invalidate journal because reverting across transactions is not allowed.
 	s.clearJournalAndRefund()
@@ -574,7 +568,7 @@ func (s *StateDB) DeleteSuicides() {
 }
 
 func (s *StateDB) clearJournalAndRefund() {
-	s.journal = journal{}
+	s.journal = newJournal()
 	s.validRevisions = s.validRevisions[:0]
 	s.refund = 0
 }
@@ -583,10 +577,9 @@ 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
+	for addr := range s.journal.dirties {
+		s.stateObjectsDirty[addr] = struct{}{}
 	}
-
 	// 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 05bc0499b..340c840f1 100644
--- a/core/state/statedb_test.go
+++ b/core/state/statedb_test.go
@@ -414,11 +414,11 @@ func (s *StateSuite) TestTouchDelete(c *check.C) {
 	snapshot := s.state.Snapshot()
 	s.state.AddBalance(common.Address{}, new(big.Int))
 
-	if len(s.state.journal.flatten()) != 1 {
+	if len(s.state.journal.dirties) != 1 {
 		c.Fatal("expected one dirty state object")
 	}
 	s.state.RevertToSnapshot(snapshot)
-	if len(s.state.journal.flatten()) != 0 {
+	if len(s.state.journal.dirties) != 0 {
 		c.Fatal("expected no dirty state object")
 	}
 }
-- 
cgit v1.2.3


From 14c9215dd3afa7613c768a71baf40224df5e6aca Mon Sep 17 00:00:00 2001
From: Martin Holst Swende <martin@swende.se>
Date: Sat, 7 Apr 2018 19:14:20 +0200
Subject: state: handle nil in journal dirties

---
 core/state/statedb.go | 12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

diff --git a/core/state/statedb.go b/core/state/statedb.go
index c7ef49f64..08f18c2d2 100644
--- a/core/state/statedb.go
+++ b/core/state/statedb.go
@@ -517,7 +517,17 @@ func (self *StateDB) GetRefund() uint64 {
 // and clears the journal as well as the refunds.
 func (s *StateDB) Finalise(deleteEmptyObjects bool) {
 	for addr := range s.journal.dirties {
-		stateObject := s.stateObjects[addr]
+		stateObject, exist := s.stateObjects[addr]
+		if !exist {
+			// ripeMD is 'touched' at block 1714175, in tx 0x1237f737031e40bcde4a8b7e717b2d15e3ecadfe49bb1bbc71ee9deb09c6fcf2
+			// That tx goes out of gas, and although the notion of 'touched' does not exist there, the
+			// touch-event will still be recorded in the journal. Since ripeMD is a special snowflake,
+			// it will persist in the journal even though the journal is reverted. In this special circumstance,
+			// it may exist in `s.journal.dirties` but not in `s.stateObjects`.
+			// Thus, we can safely ignore it here
+			continue
+		}
+
 		if stateObject.suicided || (deleteEmptyObjects && stateObject.empty()) {
 			s.deleteStateObject(stateObject)
 		} else {
-- 
cgit v1.2.3


From 8c31d2897ba6bf32097dffcd1bbe899172396533 Mon Sep 17 00:00:00 2001
From: Martin Holst Swende <martin@swende.se>
Date: Sat, 7 Apr 2018 23:20:57 +0200
Subject: core: add blockchain benchmarks

---
 core/blockchain_test.go | 111 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 111 insertions(+)

diff --git a/core/blockchain_test.go b/core/blockchain_test.go
index 748cdc5c7..375823b57 100644
--- a/core/blockchain_test.go
+++ b/core/blockchain_test.go
@@ -1338,3 +1338,114 @@ func TestLargeReorgTrieGC(t *testing.T) {
 		}
 	}
 }
+
+// Benchmarks large blocks with value transfers to non-existing accounts
+func benchmarkLargeNumberOfValueToNonexisting(b *testing.B, numTxs, numBlocks int, recipientFn func(uint64) common.Address, dataFn func(uint64) []byte) {
+	var (
+		signer          = types.HomesteadSigner{}
+		testBankKey, _  = crypto.HexToECDSA("b71c71a67e1177ad4e901695e1b4b9ee17ae16c6668d313eac2f96dbcda3f291")
+		testBankAddress = crypto.PubkeyToAddress(testBankKey.PublicKey)
+		bankFunds       = big.NewInt(100000000000000000)
+		gspec           = Genesis{
+			Config: params.TestChainConfig,
+			Alloc: GenesisAlloc{
+				testBankAddress: {Balance: bankFunds},
+				common.HexToAddress("0xc0de"): {
+					Code:    []byte{0x60, 0x01, 0x50},
+					Balance: big.NewInt(0),
+				}, // push 1, pop
+			},
+			GasLimit: 100e6, // 100 M
+		}
+	)
+	// Generate the original common chain segment and the two competing forks
+	engine := ethash.NewFaker()
+	db, _ := ethdb.NewMemDatabase()
+	genesis := gspec.MustCommit(db)
+
+	blockGenerator := func(i int, block *BlockGen) {
+		block.SetCoinbase(common.Address{1})
+		for txi := 0; txi < numTxs; txi++ {
+			uniq := uint64(i*numTxs + txi)
+			recipient := recipientFn(uniq)
+			//recipient := common.BigToAddress(big.NewInt(0).SetUint64(1337 + uniq))
+			tx, err := types.SignTx(types.NewTransaction(uniq, recipient, big.NewInt(1), params.TxGas, big.NewInt(1), nil), signer, testBankKey)
+			if err != nil {
+				b.Error(err)
+			}
+			block.AddTx(tx)
+		}
+	}
+
+	shared, _ := GenerateChain(params.TestChainConfig, genesis, engine, db, numBlocks, blockGenerator)
+	b.StopTimer()
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		// Import the shared chain and the original canonical one
+		diskdb, _ := ethdb.NewMemDatabase()
+		gspec.MustCommit(diskdb)
+
+		chain, err := NewBlockChain(diskdb, nil, params.TestChainConfig, engine, vm.Config{})
+		if err != nil {
+			b.Fatalf("failed to create tester chain: %v", err)
+		}
+		b.StartTimer()
+		if _, err := chain.InsertChain(shared); err != nil {
+			b.Fatalf("failed to insert shared chain: %v", err)
+		}
+		b.StopTimer()
+		if got := chain.CurrentBlock().Transactions().Len(); got != numTxs*numBlocks {
+			b.Fatalf("Transactions were not included, expected %d, got %d", (numTxs * numBlocks), got)
+
+		}
+	}
+}
+func BenchmarkBlockChain_1x1000ValueTransferToNonexisting(b *testing.B) {
+	var (
+		numTxs    = 1000
+		numBlocks = 1
+	)
+
+	recipientFn := func(nonce uint64) common.Address {
+		return common.BigToAddress(big.NewInt(0).SetUint64(1337 + nonce))
+	}
+	dataFn := func(nonce uint64) []byte {
+		return nil
+	}
+
+	benchmarkLargeNumberOfValueToNonexisting(b, numTxs, numBlocks, recipientFn, dataFn)
+}
+func BenchmarkBlockChain_1x1000ValueTransferToExisting(b *testing.B) {
+	var (
+		numTxs    = 1000
+		numBlocks = 1
+	)
+	b.StopTimer()
+	b.ResetTimer()
+
+	recipientFn := func(nonce uint64) common.Address {
+		return common.BigToAddress(big.NewInt(0).SetUint64(1337))
+	}
+	dataFn := func(nonce uint64) []byte {
+		return nil
+	}
+
+	benchmarkLargeNumberOfValueToNonexisting(b, numTxs, numBlocks, recipientFn, dataFn)
+}
+func BenchmarkBlockChain_1x1000Executions(b *testing.B) {
+	var (
+		numTxs    = 1000
+		numBlocks = 1
+	)
+	b.StopTimer()
+	b.ResetTimer()
+
+	recipientFn := func(nonce uint64) common.Address {
+		return common.BigToAddress(big.NewInt(0).SetUint64(0xc0de))
+	}
+	dataFn := func(nonce uint64) []byte {
+		return nil
+	}
+
+	benchmarkLargeNumberOfValueToNonexisting(b, numTxs, numBlocks, recipientFn, dataFn)
+}
-- 
cgit v1.2.3