123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572 |
- // Copyright 2014 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 trie implements Merkle Patricia Tries.
- package trie
- import (
- "bytes"
- "errors"
- "fmt"
- "sync"
- "github.com/ethereum/go-ethereum/common"
- "github.com/ethereum/go-ethereum/crypto"
- "github.com/ethereum/go-ethereum/log"
- )
- var (
- // emptyRoot is the known root hash of an empty trie.
- emptyRoot = common.HexToHash("56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421")
- // emptyState is the known hash of an empty state trie entry.
- emptyState = crypto.Keccak256Hash(nil)
- )
- // LeafCallback is a callback type invoked when a trie operation reaches a leaf
- // node.
- //
- // The paths is a path tuple identifying a particular trie node either in a single
- // trie (account) or a layered trie (account -> storage). Each path in the tuple
- // is in the raw format(32 bytes).
- //
- // The hexpath is a composite hexary path identifying the trie node. All the key
- // bytes are converted to the hexary nibbles and composited with the parent path
- // if the trie node is in a layered trie.
- //
- // It's used by state sync and commit to allow handling external references
- // between account and storage tries. And also it's used in the state healing
- // for extracting the raw states(leaf nodes) with corresponding paths.
- type LeafCallback func(paths [][]byte, hexpath []byte, leaf []byte, parent common.Hash) error
- // Trie is a Merkle Patricia Trie.
- // The zero value is an empty trie with no database.
- // Use New to create a trie that sits on top of a database.
- //
- // Trie is not safe for concurrent use.
- type Trie struct {
- db *Database
- root node
- // Keep track of the number leafs which have been inserted since the last
- // hashing operation. This number will not directly map to the number of
- // actually unhashed nodes
- unhashed int
- }
- // newFlag returns the cache flag value for a newly created node.
- func (t *Trie) newFlag() nodeFlag {
- return nodeFlag{dirty: true}
- }
- // New creates a trie with an existing root node from db.
- //
- // If root is the zero hash or the sha3 hash of an empty string, the
- // trie is initially empty and does not require a database. Otherwise,
- // New will panic if db is nil and returns a MissingNodeError if root does
- // not exist in the database. Accessing the trie loads nodes from db on demand.
- func New(root common.Hash, db *Database) (*Trie, error) {
- if db == nil {
- panic("trie.New called without a database")
- }
- trie := &Trie{
- db: db,
- }
- if root != (common.Hash{}) && root != emptyRoot {
- rootnode, err := trie.resolveHash(root[:], nil)
- if err != nil {
- return nil, err
- }
- trie.root = rootnode
- }
- return trie, nil
- }
- // NodeIterator returns an iterator that returns nodes of the trie. Iteration starts at
- // the key after the given start key.
- func (t *Trie) NodeIterator(start []byte) NodeIterator {
- return newNodeIterator(t, start)
- }
- // Get returns the value for key stored in the trie.
- // The value bytes must not be modified by the caller.
- func (t *Trie) Get(key []byte) []byte {
- res, err := t.TryGet(key)
- if err != nil {
- log.Error(fmt.Sprintf("Unhandled trie error: %v", err))
- }
- return res
- }
- // TryGet returns the value for key stored in the trie.
- // The value bytes must not be modified by the caller.
- // If a node was not found in the database, a MissingNodeError is returned.
- func (t *Trie) TryGet(key []byte) ([]byte, error) {
- value, newroot, didResolve, err := t.tryGet(t.root, keybytesToHex(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 = n.copy()
- n.Val = newnode
- }
- return value, n, didResolve, err
- case *fullNode:
- value, newnode, didResolve, err = t.tryGet(n.Children[key[pos]], key, pos+1)
- if err == nil && didResolve {
- n = n.copy()
- n.Children[key[pos]] = newnode
- }
- return value, n, didResolve, err
- case hashNode:
- child, err := t.resolveHash(n, 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))
- }
- }
- // TryGetNode attempts to retrieve a trie node by compact-encoded path. It is not
- // possible to use keybyte-encoding as the path might contain odd nibbles.
- func (t *Trie) TryGetNode(path []byte) ([]byte, int, error) {
- item, newroot, resolved, err := t.tryGetNode(t.root, compactToHex(path), 0)
- if err != nil {
- return nil, resolved, err
- }
- if resolved > 0 {
- t.root = newroot
- }
- if item == nil {
- return nil, resolved, nil
- }
- return item, resolved, err
- }
- func (t *Trie) tryGetNode(origNode node, path []byte, pos int) (item []byte, newnode node, resolved int, err error) {
- // If we reached the requested path, return the current node
- if pos >= len(path) {
- // Although we most probably have the original node expanded, encoding
- // that into consensus form can be nasty (needs to cascade down) and
- // time consuming. Instead, just pull the hash up from disk directly.
- var hash hashNode
- if node, ok := origNode.(hashNode); ok {
- hash = node
- } else {
- hash, _ = origNode.cache()
- }
- if hash == nil {
- return nil, origNode, 0, errors.New("non-consensus node")
- }
- blob, err := t.db.Node(common.BytesToHash(hash))
- return blob, origNode, 1, err
- }
- // Path still needs to be traversed, descend into children
- switch n := (origNode).(type) {
- case nil:
- // Non-existent path requested, abort
- return nil, nil, 0, nil
- case valueNode:
- // Path prematurely ended, abort
- return nil, nil, 0, nil
- case *shortNode:
- if len(path)-pos < len(n.Key) || !bytes.Equal(n.Key, path[pos:pos+len(n.Key)]) {
- // Path branches off from short node
- return nil, n, 0, nil
- }
- item, newnode, resolved, err = t.tryGetNode(n.Val, path, pos+len(n.Key))
- if err == nil && resolved > 0 {
- n = n.copy()
- n.Val = newnode
- }
- return item, n, resolved, err
- case *fullNode:
- item, newnode, resolved, err = t.tryGetNode(n.Children[path[pos]], path, pos+1)
- if err == nil && resolved > 0 {
- n = n.copy()
- n.Children[path[pos]] = newnode
- }
- return item, n, resolved, err
- case hashNode:
- child, err := t.resolveHash(n, path[:pos])
- if err != nil {
- return nil, n, 1, err
- }
- item, newnode, resolved, err := t.tryGetNode(child, path, pos)
- return item, newnode, resolved + 1, err
- default:
- panic(fmt.Sprintf("%T: invalid node: %v", origNode, origNode))
- }
- }
- // Update associates key with value in the trie. Subsequent calls to
- // Get will return value. If value has length zero, any existing value
- // is deleted from the trie and calls to Get will return nil.
- //
- // The value bytes must not be modified by the caller while they are
- // stored in the trie.
- func (t *Trie) Update(key, value []byte) {
- if err := t.TryUpdate(key, value); err != nil {
- log.Error(fmt.Sprintf("Unhandled trie error: %v", err))
- }
- }
- // TryUpdate associates key with value in the trie. Subsequent calls to
- // Get will return value. If value has length zero, any existing value
- // is deleted from the trie and calls to Get will return nil.
- //
- // The value bytes must not be modified by the caller while they are
- // stored in the trie.
- //
- // If a node was not found in the database, a MissingNodeError is returned.
- func (t *Trie) TryUpdate(key, value []byte) error {
- t.unhashed++
- k := keybytesToHex(key)
- if len(value) != 0 {
- _, n, err := t.insert(t.root, nil, k, valueNode(value))
- if err != nil {
- return err
- }
- t.root = n
- } else {
- _, n, err := t.delete(t.root, nil, k)
- if err != nil {
- return err
- }
- t.root = n
- }
- return nil
- }
- func (t *Trie) insert(n node, prefix, key []byte, value node) (bool, node, error) {
- if len(key) == 0 {
- if v, ok := n.(valueNode); ok {
- return !bytes.Equal(v, value.(valueNode)), value, nil
- }
- return true, value, nil
- }
- switch n := n.(type) {
- case *shortNode:
- matchlen := prefixLen(key, n.Key)
- // If the whole key matches, keep this short node as is
- // and only update the value.
- if matchlen == len(n.Key) {
- dirty, nn, err := t.insert(n.Val, append(prefix, key[:matchlen]...), key[matchlen:], value)
- if !dirty || err != nil {
- return false, n, err
- }
- return true, &shortNode{n.Key, nn, t.newFlag()}, nil
- }
- // Otherwise branch out at the index where they differ.
- branch := &fullNode{flags: t.newFlag()}
- var err error
- _, branch.Children[n.Key[matchlen]], err = t.insert(nil, append(prefix, n.Key[:matchlen+1]...), n.Key[matchlen+1:], n.Val)
- if err != nil {
- return false, nil, err
- }
- _, branch.Children[key[matchlen]], err = t.insert(nil, append(prefix, key[:matchlen+1]...), key[matchlen+1:], value)
- if err != nil {
- return false, nil, err
- }
- // Replace this shortNode with the branch if it occurs at index 0.
- if matchlen == 0 {
- return true, branch, nil
- }
- // Otherwise, replace it with a short node leading up to the branch.
- return true, &shortNode{key[:matchlen], branch, t.newFlag()}, nil
- case *fullNode:
- dirty, nn, err := t.insert(n.Children[key[0]], append(prefix, key[0]), key[1:], value)
- if !dirty || err != nil {
- return false, n, err
- }
- n = n.copy()
- n.flags = t.newFlag()
- n.Children[key[0]] = nn
- return true, n, nil
- case nil:
- return true, &shortNode{key, value, t.newFlag()}, nil
- case hashNode:
- // We've hit a part of the trie that isn't loaded yet. Load
- // the node and insert into it. This leaves all child nodes on
- // the path to the value in the trie.
- rn, err := t.resolveHash(n, prefix)
- if err != nil {
- return false, nil, err
- }
- dirty, nn, err := t.insert(rn, prefix, key, value)
- if !dirty || err != nil {
- return false, rn, err
- }
- return true, nn, nil
- default:
- panic(fmt.Sprintf("%T: invalid node: %v", n, n))
- }
- }
- // Delete removes any existing value for key from the trie.
- func (t *Trie) Delete(key []byte) {
- if err := t.TryDelete(key); err != nil {
- log.Error(fmt.Sprintf("Unhandled trie error: %v", err))
- }
- }
- // TryDelete removes any existing value for key from the trie.
- // If a node was not found in the database, a MissingNodeError is returned.
- func (t *Trie) TryDelete(key []byte) error {
- t.unhashed++
- k := keybytesToHex(key)
- _, n, err := t.delete(t.root, nil, k)
- if err != nil {
- return err
- }
- t.root = n
- return nil
- }
- // delete returns the new root of the trie with key deleted.
- // It reduces the trie to minimal form by simplifying
- // nodes on the way up after deleting recursively.
- func (t *Trie) delete(n node, prefix, key []byte) (bool, node, error) {
- switch n := n.(type) {
- case *shortNode:
- matchlen := prefixLen(key, n.Key)
- if matchlen < len(n.Key) {
- return false, n, nil // don't replace n on mismatch
- }
- if matchlen == len(key) {
- return true, nil, nil // remove n entirely for whole matches
- }
- // The key is longer than n.Key. Remove the remaining suffix
- // from the subtrie. Child can never be nil here since the
- // subtrie must contain at least two other values with keys
- // longer than n.Key.
- dirty, child, err := t.delete(n.Val, append(prefix, key[:len(n.Key)]...), key[len(n.Key):])
- if !dirty || err != nil {
- return false, n, err
- }
- switch child := child.(type) {
- case *shortNode:
- // Deleting from the subtrie reduced it to another
- // short node. Merge the nodes to avoid creating a
- // shortNode{..., shortNode{...}}. Use concat (which
- // always creates a new slice) instead of append to
- // avoid modifying n.Key since it might be shared with
- // other nodes.
- return true, &shortNode{concat(n.Key, child.Key...), child.Val, t.newFlag()}, nil
- default:
- return true, &shortNode{n.Key, child, t.newFlag()}, nil
- }
- case *fullNode:
- dirty, nn, err := t.delete(n.Children[key[0]], append(prefix, key[0]), key[1:])
- if !dirty || err != nil {
- return false, n, err
- }
- n = n.copy()
- n.flags = t.newFlag()
- n.Children[key[0]] = nn
- // Check how many non-nil entries are left after deleting and
- // reduce the full node to a short node if only one entry is
- // left. Since n must've contained at least two children
- // before deletion (otherwise it would not be a full node) n
- // can never be reduced to nil.
- //
- // When the loop is done, pos contains the index of the single
- // value that is left in n or -2 if n contains at least two
- // values.
- pos := -1
- for i, cld := range &n.Children {
- if cld != nil {
- if pos == -1 {
- pos = i
- } else {
- pos = -2
- break
- }
- }
- }
- if pos >= 0 {
- if pos != 16 {
- // If the remaining entry is a short node, it replaces
- // n and its key gets the missing nibble tacked to the
- // front. This avoids creating an invalid
- // shortNode{..., shortNode{...}}. Since the entry
- // might not be loaded yet, resolve it just for this
- // check.
- cnode, err := t.resolve(n.Children[pos], prefix)
- if err != nil {
- return false, nil, err
- }
- if cnode, ok := cnode.(*shortNode); ok {
- k := append([]byte{byte(pos)}, cnode.Key...)
- return true, &shortNode{k, cnode.Val, t.newFlag()}, nil
- }
- }
- // Otherwise, n is replaced by a one-nibble short node
- // containing the child.
- return true, &shortNode{[]byte{byte(pos)}, n.Children[pos], t.newFlag()}, nil
- }
- // n still contains at least two values and cannot be reduced.
- return true, n, nil
- case valueNode:
- return true, nil, nil
- case nil:
- return false, nil, nil
- case hashNode:
- // We've hit a part of the trie that isn't loaded yet. Load
- // the node and delete from it. This leaves all child nodes on
- // the path to the value in the trie.
- rn, err := t.resolveHash(n, prefix)
- if err != nil {
- return false, nil, err
- }
- dirty, nn, err := t.delete(rn, prefix, key)
- if !dirty || err != nil {
- return false, rn, err
- }
- return true, nn, nil
- default:
- panic(fmt.Sprintf("%T: invalid node: %v (%v)", n, n, key))
- }
- }
- func concat(s1 []byte, s2 ...byte) []byte {
- r := make([]byte, len(s1)+len(s2))
- copy(r, s1)
- copy(r[len(s1):], s2)
- return r
- }
- func (t *Trie) resolve(n node, prefix []byte) (node, error) {
- if n, ok := n.(hashNode); ok {
- return t.resolveHash(n, prefix)
- }
- return n, nil
- }
- func (t *Trie) resolveHash(n hashNode, prefix []byte) (node, error) {
- hash := common.BytesToHash(n)
- if node := t.db.node(hash); node != nil {
- return node, nil
- }
- return nil, &MissingNodeError{NodeHash: hash, Path: prefix}
- }
- // Hash returns the root hash of the trie. It does not write to the
- // database and can be used even if the trie doesn't have one.
- func (t *Trie) Hash() common.Hash {
- hash, cached, _ := t.hashRoot()
- t.root = cached
- return common.BytesToHash(hash.(hashNode))
- }
- // Commit writes all nodes to the trie's memory database, tracking the internal
- // and external (for account tries) references.
- func (t *Trie) Commit(onleaf LeafCallback) (root common.Hash, err error) {
- if t.db == nil {
- panic("commit called on trie with nil database")
- }
- if t.root == nil {
- return emptyRoot, nil
- }
- // Derive the hash for all dirty nodes first. We hold the assumption
- // in the following procedure that all nodes are hashed.
- rootHash := t.Hash()
- h := newCommitter()
- defer returnCommitterToPool(h)
- // Do a quick check if we really need to commit, before we spin
- // up goroutines. This can happen e.g. if we load a trie for reading storage
- // values, but don't write to it.
- if _, dirty := t.root.cache(); !dirty {
- return rootHash, nil
- }
- var wg sync.WaitGroup
- if onleaf != nil {
- h.onleaf = onleaf
- h.leafCh = make(chan *leaf, leafChanSize)
- wg.Add(1)
- go func() {
- defer wg.Done()
- h.commitLoop(t.db)
- }()
- }
- var newRoot hashNode
- newRoot, err = h.Commit(t.root, t.db)
- if onleaf != nil {
- // The leafch is created in newCommitter if there was an onleaf callback
- // provided. The commitLoop only _reads_ from it, and the commit
- // operation was the sole writer. Therefore, it's safe to close this
- // channel here.
- close(h.leafCh)
- wg.Wait()
- }
- if err != nil {
- return common.Hash{}, err
- }
- t.root = newRoot
- return rootHash, nil
- }
- // hashRoot calculates the root hash of the given trie
- func (t *Trie) hashRoot() (node, node, error) {
- if t.root == nil {
- return hashNode(emptyRoot.Bytes()), nil, nil
- }
- // If the number of changes is below 100, we let one thread handle it
- h := newHasher(t.unhashed >= 100)
- defer returnHasherToPool(h)
- hashed, cached := h.hash(t.root, true)
- t.unhashed = 0
- return hashed, cached, nil
- }
- // Reset drops the referenced root node and cleans all internal state.
- func (t *Trie) Reset() {
- t.root = nil
- t.unhashed = 0
- }
|