core, trie: replace state caches with trie journal

1 files changed, 45 insertions, 167 deletions

diff --git a/trie/trie.go b/trie/trie.go
index a530e7b2a..93e189e2e 100644
--- a/trie/trie.go
+++ b/trie/trie.go
@@ -20,22 +20,14 @@ package trie
 import (
 	"bytes"
 	"fmt"
-	"hash"
 
 	"github.com/ethereum/go-ethereum/common"
 	"github.com/ethereum/go-ethereum/crypto"
-	"github.com/ethereum/go-ethereum/crypto/sha3"
 	"github.com/ethereum/go-ethereum/logger"
 	"github.com/ethereum/go-ethereum/logger/glog"
-	"github.com/ethereum/go-ethereum/rlp"
 )
 
-const defaultCacheCapacity = 800
-
 var (
-	// The global cache stores decoded trie nodes by hash as they get loaded.
-	globalCache = newARC(defaultCacheCapacity)
-
 	// This is the known root hash of an empty trie.
 	emptyRoot = common.HexToHash("56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421")
 
@@ -43,11 +35,6 @@ var (
 	emptyState = crypto.Keccak256Hash(nil)
 )
 
-// ClearGlobalCache clears the global trie cache
-func ClearGlobalCache() {
-	globalCache.Clear()
-}
-
 // Database must be implemented by backing stores for the trie.
 type Database interface {
 	DatabaseWriter
@@ -72,7 +59,6 @@ type Trie struct {
 	root         node
 	db           Database
 	originalRoot common.Hash
-	*hasher
 }
 
 // New creates a trie with an existing root node from db.
@@ -118,32 +104,50 @@ func (t *Trie) Get(key []byte) []byte {
 // If a node was not found in the database, a MissingNodeError is returned.
 func (t *Trie) TryGet(key []byte) ([]byte, error) {
 	key = compactHexDecode(key)
-	pos := 0
-	tn := t.root
-	for pos < len(key) {
-		switch n := tn.(type) {
-		case shortNode:
-			if len(key)-pos < len(n.Key) || !bytes.Equal(n.Key, key[pos:pos+len(n.Key)]) {
-				return nil, nil
-			}
-			tn = n.Val
-			pos += len(n.Key)
-		case fullNode:
-			tn = n.Children[key[pos]]
-			pos++
-		case nil:
-			return nil, nil
-		case hashNode:
-			var err error
-			tn, err = t.resolveHash(n, key[:pos], key[pos:])
-			if err != nil {
-				return nil, err
-			}
-		default:
-			panic(fmt.Sprintf("%T: invalid node: %v", tn, tn))
+	value, newroot, didResolve, err := t.tryGet(t.root, key, 0)
+	if err == nil && didResolve {
+		t.root = newroot
+	}
+	return value, err
+}
+
+func (t *Trie) tryGet(origNode node, key []byte, pos int) (value []byte, newnode node, didResolve bool, err error) {
+	switch n := (origNode).(type) {
+	case nil:
+		return nil, nil, false, nil
+	case valueNode:
+		return n, n, false, nil
+	case shortNode:
+		if len(key)-pos < len(n.Key) || !bytes.Equal(n.Key, key[pos:pos+len(n.Key)]) {
+			// key not found in trie
+			return nil, n, false, nil
+		}
+		value, newnode, didResolve, err = t.tryGet(n.Val, key, pos+len(n.Key))
+		if err == nil && didResolve {
+			n.Val = newnode
+			return value, n, didResolve, err
+		} else {
+			return value, origNode, didResolve, err
+		}
+	case fullNode:
+		child := n.Children[key[pos]]
+		value, newnode, didResolve, err = t.tryGet(child, key, pos+1)
+		if err == nil && didResolve {
+			n.Children[key[pos]] = newnode
+			return value, n, didResolve, err
+		} else {
+			return value, origNode, didResolve, err
+		}
+	case hashNode:
+		child, err := t.resolveHash(n, key[:pos], key[pos:])
+		if err != nil {
+			return nil, n, true, err
 		}
+		value, newnode, _, err := t.tryGet(child, key, pos)
+		return value, newnode, true, err
+	default:
+		panic(fmt.Sprintf("%T: invalid node: %v", origNode, origNode))
 	}
-	return tn.(valueNode), nil
 }
 
 // Update associates key with value in the trie. Subsequent calls to
@@ -410,9 +414,6 @@ func (t *Trie) resolve(n node, prefix, suffix []byte) (node, error) {
 }
 
 func (t *Trie) resolveHash(n hashNode, prefix, suffix []byte) (node, error) {
-	if v, ok := globalCache.Get(n); ok {
-		return v, nil
-	}
 	enc, err := t.db.Get(n)
 	if err != nil || enc == nil {
 		return nil, &MissingNodeError{
@@ -424,9 +425,6 @@ func (t *Trie) resolveHash(n hashNode, prefix, suffix []byte) (node, error) {
 		}
 	}
 	dec := mustDecodeNode(n, enc)
-	if dec != nil {
-		globalCache.Put(n, dec)
-	}
 	return dec, nil
 }
 
@@ -474,127 +472,7 @@ func (t *Trie) hashRoot(db DatabaseWriter) (node, node, error) {
 	if t.root == nil {
 		return hashNode(emptyRoot.Bytes()), nil, nil
 	}
-	if t.hasher == nil {
-		t.hasher = newHasher()
-	}
-	return t.hasher.hash(t.root, db, true)
-}
-
-type hasher struct {
-	tmp *bytes.Buffer
-	sha hash.Hash
-}
-
-func newHasher() *hasher {
-	return &hasher{tmp: new(bytes.Buffer), sha: sha3.NewKeccak256()}
-}
-
-// hash collapses a node down into a hash node, also returning a copy of the
-// original node initialzied with the computed hash to replace the original one.
-func (h *hasher) hash(n node, db DatabaseWriter, force bool) (node, node, error) {
-	// If we're not storing the node, just hashing, use avaialble cached data
-	if hash, dirty := n.cache(); hash != nil && (db == nil || !dirty) {
-		return hash, n, nil
-	}
-	// Trie not processed yet or needs storage, walk the children
-	collapsed, cached, err := h.hashChildren(n, db)
-	if err != nil {
-		return hashNode{}, n, err
-	}
-	hashed, err := h.store(collapsed, db, force)
-	if err != nil {
-		return hashNode{}, n, err
-	}
-	// Cache the hash and RLP blob of the ndoe for later reuse
-	if hash, ok := hashed.(hashNode); ok && !force {
-		switch cached := cached.(type) {
-		case shortNode:
-			cached.hash = hash
-			if db != nil {
-				cached.dirty = false
-			}
-			return hashed, cached, nil
-		case fullNode:
-			cached.hash = hash
-			if db != nil {
-				cached.dirty = false
-			}
-			return hashed, cached, nil
-		}
-	}
-	return hashed, cached, nil
-}
-
-// hashChildren replaces the children of a node with their hashes if the encoded
-// size of the child is larger than a hash, returning the collapsed node as well
-// as a replacement for the original node with the child hashes cached in.
-func (h *hasher) hashChildren(original node, db DatabaseWriter) (node, node, error) {
-	var err error
-
-	switch n := original.(type) {
-	case shortNode:
-		// Hash the short node's child, caching the newly hashed subtree
-		cached := n
-		cached.Key = common.CopyBytes(cached.Key)
-
-		n.Key = compactEncode(n.Key)
-		if _, ok := n.Val.(valueNode); !ok {
-			if n.Val, cached.Val, err = h.hash(n.Val, db, false); err != nil {
-				return n, original, err
-			}
-		}
-		if n.Val == nil {
-			n.Val = valueNode(nil) // Ensure that nil children are encoded as empty strings.
-		}
-		return n, cached, nil
-
-	case fullNode:
-		// Hash the full node's children, caching the newly hashed subtrees
-		cached := fullNode{dirty: n.dirty}
-
-		for i := 0; i < 16; i++ {
-			if n.Children[i] != nil {
-				if n.Children[i], cached.Children[i], err = h.hash(n.Children[i], db, false); err != nil {
-					return n, original, err
-				}
-			} else {
-				n.Children[i] = valueNode(nil) // Ensure that nil children are encoded as empty strings.
-			}
-		}
-		cached.Children[16] = n.Children[16]
-		if n.Children[16] == nil {
-			n.Children[16] = valueNode(nil)
-		}
-		return n, cached, nil
-
-	default:
-		// Value and hash nodes don't have children so they're left as were
-		return n, original, nil
-	}
-}
-
-func (h *hasher) store(n node, db DatabaseWriter, force bool) (node, error) {
-	// Don't store hashes or empty nodes.
-	if _, isHash := n.(hashNode); n == nil || isHash {
-		return n, nil
-	}
-	// Generate the RLP encoding of the node
-	h.tmp.Reset()
-	if err := rlp.Encode(h.tmp, n); err != nil {
-		panic("encode error: " + err.Error())
-	}
-	if h.tmp.Len() < 32 && !force {
-		return n, nil // Nodes smaller than 32 bytes are stored inside their parent
-	}
-	// Larger nodes are replaced by their hash and stored in the database.
-	hash, _ := n.cache()
-	if hash == nil {
-		h.sha.Reset()
-		h.sha.Write(h.tmp.Bytes())
-		hash = hashNode(h.sha.Sum(nil))
-	}
-	if db != nil {
-		return hash, db.Put(hash, h.tmp.Bytes())
-	}
-	return hash, nil
+	h := newHasher()
+	defer returnHasherToPool(h)
+	return h.hash(t.root, db, true)
 }