From cd791bd855b55b95afc8a5c8f56b8bf67863d099 Mon Sep 17 00:00:00 2001 From: Felix Lange Date: Sun, 25 Sep 2016 20:49:02 +0200 Subject: core, trie: replace state caches with trie journal --- trie/trie.go | 212 +++++++++++++---------------------------------------------- 1 file changed, 45 insertions(+), 167 deletions(-) (limited to 'trie/trie.go') 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) } -- cgit