diff options
| -rw-r--r-- | Makefile | 61 | ||||
| -rw-r--r-- | cmd/geth/main.go | 7 | ||||
| -rw-r--r-- | cmd/utils/flags.go | 32 | ||||
| -rw-r--r-- | trie/arc.go | 12 | ||||
| -rw-r--r-- | trie/errors.go | 41 | ||||
| -rw-r--r-- | trie/iterator.go | 19 | ||||
| -rw-r--r-- | trie/proof.go | 11 | ||||
| -rw-r--r-- | trie/secure_trie.go | 49 | ||||
| -rw-r--r-- | trie/trie.go | 204 | ||||
| -rw-r--r-- | trie/trie_test.go | 75 |
10 files changed, 389 insertions, 122 deletions
@@ -3,11 +3,10 @@ # don't need to bother with make. .PHONY: geth geth-cross evm all test travis-test-with-coverage xgo clean -.PHONY: geth-linux geth-linux-arm geth-linux-386 geth-linux-amd64 +.PHONY: geth-linux geth-linux-arm geth-linux-arm-5 geth-linux-arm-6 geth-linux-arm-7 geth-linux-386 geth-linux-amd64 .PHONY: geth-darwin geth-darwin-386 geth-darwin-amd64 .PHONY: geth-windows geth-windows-386 geth-windows-amd64 -.PHONY: geth-android geth-android-16 geth-android-21 -.PHONY: geth-ios geth-ios-5.0 geth-ios-8.1 +.PHONY: geth-android geth-ios GOBIN = build/bin @@ -24,15 +23,10 @@ geth-cross: geth-linux geth-darwin geth-windows geth-android geth-ios @echo "Full cross compilation done:" @ls -l $(GOBIN)/geth-* -geth-linux: xgo geth-linux-arm geth-linux-386 geth-linux-amd64 +geth-linux: geth-linux-386 geth-linux-amd64 geth-linux-arm @echo "Linux cross compilation done:" @ls -l $(GOBIN)/geth-linux-* -geth-linux-arm: xgo - build/env.sh $(GOBIN)/xgo --go=$(GO) --buildmode=$(MODE) --dest=$(GOBIN) --deps=$(CROSSDEPS) --targets=linux/arm -v $(shell build/flags.sh) ./cmd/geth - @echo "Linux ARM cross compilation done:" - @ls -l $(GOBIN)/geth-linux-* | grep arm - geth-linux-386: xgo build/env.sh $(GOBIN)/xgo --go=$(GO) --buildmode=$(MODE) --dest=$(GOBIN) --deps=$(CROSSDEPS) --targets=linux/386 -v $(shell build/flags.sh) ./cmd/geth @echo "Linux 386 cross compilation done:" @@ -43,7 +37,26 @@ geth-linux-amd64: xgo @echo "Linux amd64 cross compilation done:" @ls -l $(GOBIN)/geth-linux-* | grep amd64 -geth-darwin: xgo geth-darwin-386 geth-darwin-amd64 +geth-linux-arm: geth-linux-arm-5 geth-linux-arm-6 geth-linux-arm-7 + @echo "Linux ARM cross compilation done:" + @ls -l $(GOBIN)/geth-linux-* | grep arm + +geth-linux-arm-5: xgo + build/env.sh $(GOBIN)/xgo --go=$(GO) --buildmode=$(MODE) --dest=$(GOBIN) --deps=$(CROSSDEPS) --targets=linux/arm-5 -v $(shell build/flags.sh) ./cmd/geth + @echo "Linux ARMv5 cross compilation done:" + @ls -l $(GOBIN)/geth-linux-* | grep arm-5 + +geth-linux-arm-6: xgo + build/env.sh $(GOBIN)/xgo --go=$(GO) --buildmode=$(MODE) --dest=$(GOBIN) --deps=$(CROSSDEPS) --targets=linux/arm-6 -v $(shell build/flags.sh) ./cmd/geth + @echo "Linux ARMv6 cross compilation done:" + @ls -l $(GOBIN)/geth-linux-* | grep arm-6 + +geth-linux-arm-7: xgo + build/env.sh $(GOBIN)/xgo --go=$(GO) --buildmode=$(MODE) --dest=$(GOBIN) --deps=$(CROSSDEPS) --targets=linux/arm-7 -v $(shell build/flags.sh) ./cmd/geth + @echo "Linux ARMv7 cross compilation done:" + @ls -l $(GOBIN)/geth-linux-* | grep arm-7 + +geth-darwin: geth-darwin-386 geth-darwin-amd64 @echo "Darwin cross compilation done:" @ls -l $(GOBIN)/geth-darwin-* @@ -57,7 +70,7 @@ geth-darwin-amd64: xgo @echo "Darwin amd64 cross compilation done:" @ls -l $(GOBIN)/geth-darwin-* | grep amd64 -geth-windows: xgo geth-windows-386 geth-windows-amd64 +geth-windows: geth-windows-386 geth-windows-amd64 @echo "Windows cross compilation done:" @ls -l $(GOBIN)/geth-windows-* @@ -71,34 +84,16 @@ geth-windows-amd64: xgo @echo "Windows amd64 cross compilation done:" @ls -l $(GOBIN)/geth-windows-* | grep amd64 -geth-android: xgo geth-android-16 geth-android-21 +geth-android: xgo + build/env.sh $(GOBIN)/xgo --go=$(GO) --buildmode=$(MODE) --dest=$(GOBIN) --deps=$(CROSSDEPS) --targets=android/* -v $(shell build/flags.sh) ./cmd/geth @echo "Android cross compilation done:" @ls -l $(GOBIN)/geth-android-* -geth-android-16: xgo - build/env.sh $(GOBIN)/xgo --go=$(GO) --buildmode=$(MODE) --dest=$(GOBIN) --deps=$(CROSSDEPS) --targets=android-16/* -v $(shell build/flags.sh) ./cmd/geth - @echo "Android 16 cross compilation done:" - @ls -l $(GOBIN)/geth-android-16-* - -geth-android-21: xgo - build/env.sh $(GOBIN)/xgo --go=$(GO) --buildmode=$(MODE) --dest=$(GOBIN) --deps=$(CROSSDEPS) --targets=android-21/* -v $(shell build/flags.sh) ./cmd/geth - @echo "Android 21 cross compilation done:" - @ls -l $(GOBIN)/geth-android-21-* - -geth-ios: xgo geth-ios-5.0 geth-ios-8.1 +geth-ios: xgo + build/env.sh $(GOBIN)/xgo --go=$(GO) --buildmode=$(MODE) --dest=$(GOBIN) --deps=$(CROSSDEPS) --depsargs=--disable-assembly --targets=ios/* -v $(shell build/flags.sh) ./cmd/geth @echo "iOS cross compilation done:" @ls -l $(GOBIN)/geth-ios-* -geth-ios-5.0: - build/env.sh $(GOBIN)/xgo --go=$(GO) --buildmode=$(MODE) --dest=$(GOBIN) --deps=$(CROSSDEPS) --depsargs=--disable-assembly --targets=ios-5.0/* -v $(shell build/flags.sh) ./cmd/geth - @echo "iOS 5.0 cross compilation done:" - @ls -l $(GOBIN)/geth-ios-5.0-* - -geth-ios-8.1: - build/env.sh $(GOBIN)/xgo --go=$(GO) --buildmode=$(MODE) --dest=$(GOBIN) --deps=$(CROSSDEPS) --depsargs=--disable-assembly --targets=ios-8.1/* -v $(shell build/flags.sh) ./cmd/geth - @echo "iOS 8.1 cross compilation done:" - @ls -l $(GOBIN)/geth-ios-8.1-* - evm: build/env.sh $(GOROOT)/bin/go install -v $(shell build/flags.sh) ./cmd/evm @echo "Done building." diff --git a/cmd/geth/main.go b/cmd/geth/main.go index 3a5471845..6ec30cebc 100644 --- a/cmd/geth/main.go +++ b/cmd/geth/main.go @@ -464,9 +464,12 @@ func execScripts(ctx *cli.Context) { node.Stop() } +// tries unlocking the specified account a few times. func unlockAccount(ctx *cli.Context, accman *accounts.Manager, address string, i int, passwords []string) (common.Address, string) { - // Try to unlock the specified account a few times - account := utils.MakeAddress(accman, address) + account, err := utils.MakeAddress(accman, address) + if err != nil { + utils.Fatalf("Unlock error: %v", err) + } for trials := 0; trials < 3; trials++ { prompt := fmt.Sprintf("Unlocking account %s | Attempt %d/%d", address, trials+1, 3) diff --git a/cmd/utils/flags.go b/cmd/utils/flags.go index 53126f9e5..839ec3f02 100644 --- a/cmd/utils/flags.go +++ b/cmd/utils/flags.go @@ -518,47 +518,41 @@ func MakeAccountManager(ctx *cli.Context) *accounts.Manager { // MakeAddress converts an account specified directly as a hex encoded string or // a key index in the key store to an internal account representation. -func MakeAddress(accman *accounts.Manager, account string) common.Address { +func MakeAddress(accman *accounts.Manager, account string) (a common.Address, err error) { // If the specified account is a valid address, return it if common.IsHexAddress(account) { - return common.HexToAddress(account) + return common.HexToAddress(account), nil } // Otherwise try to interpret the account as a keystore index index, err := strconv.Atoi(account) if err != nil { - Fatalf("Invalid account address or index: '%s'", account) + return a, fmt.Errorf("invalid account address or index %q", account) } hex, err := accman.AddressByIndex(index) if err != nil { - Fatalf("Failed to retrieve requested account #%d: %v", index, err) + return a, fmt.Errorf("can't get account #%d (%v)", index, err) } - return common.HexToAddress(hex) + return common.HexToAddress(hex), nil } // MakeEtherbase retrieves the etherbase either from the directly specified // command line flags or from the keystore if CLI indexed. func MakeEtherbase(accman *accounts.Manager, ctx *cli.Context) common.Address { - // If the specified etherbase is a valid address, return it - etherbase := ctx.GlobalString(EtherbaseFlag.Name) - if common.IsHexAddress(etherbase) { - return common.HexToAddress(etherbase) - } - // If no etherbase was specified and no accounts are known, bail out accounts, _ := accman.Accounts() - if etherbase == "" && len(accounts) == 0 { + if !ctx.GlobalIsSet(EtherbaseFlag.Name) && len(accounts) == 0 { glog.V(logger.Error).Infoln("WARNING: No etherbase set and no accounts found as default") return common.Address{} } - // Otherwise try to interpret the parameter as a keystore index - index, err := strconv.Atoi(etherbase) - if err != nil { - Fatalf("Invalid account address or index: '%s'", etherbase) + etherbase := ctx.GlobalString(EtherbaseFlag.Name) + if etherbase == "" { + return common.Address{} } - hex, err := accman.AddressByIndex(index) + // If the specified etherbase is a valid address, return it + addr, err := MakeAddress(accman, etherbase) if err != nil { - Fatalf("Failed to set requested account #%d as etherbase: %v", index, err) + Fatalf("Option %q: %v", EtherbaseFlag.Name, err) } - return common.HexToAddress(hex) + return addr } // MakeMinerExtra resolves extradata for the miner from the set command line flags diff --git a/trie/arc.go b/trie/arc.go index 9da012e16..fc7a3259f 100644 --- a/trie/arc.go +++ b/trie/arc.go @@ -62,6 +62,18 @@ func newARC(c int) *arc { } } +// Clear clears the cache +func (a *arc) Clear() { + a.mutex.Lock() + defer a.mutex.Unlock() + a.p = 0 + a.t1 = list.New() + a.b1 = list.New() + a.t2 = list.New() + a.b2 = list.New() + a.cache = make(map[string]*entry, a.c) +} + // Put inserts a new key-value pair into the cache. // This optimizes future access to this entry (side effect). func (a *arc) Put(key hashNode, value node) bool { diff --git a/trie/errors.go b/trie/errors.go new file mode 100644 index 000000000..a0f58f28f --- /dev/null +++ b/trie/errors.go @@ -0,0 +1,41 @@ +// 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 + +import ( + "fmt" + + "github.com/ethereum/go-ethereum/common" +) + +// MissingNodeError is returned by the trie functions (TryGet, TryUpdate, TryDelete) +// in the case where a trie node is not present in the local database. Contains +// information necessary for retrieving the missing node through an ODR service. +// +// NodeHash is the hash of the missing node +// RootHash is the original root of the trie that contains the node +// KeyPrefix is the prefix that leads from the root to the missing node (hex encoded) +// KeySuffix (optional) contains the rest of the key we were looking for, gives a +// hint on which further nodes should also be retrieved (hex encoded) +type MissingNodeError struct { + RootHash, NodeHash common.Hash + KeyPrefix, KeySuffix []byte +} + +func (err *MissingNodeError) Error() string { + return fmt.Sprintf("Missing trie node %064x", err.NodeHash) +} diff --git a/trie/iterator.go b/trie/iterator.go index 38555fe08..5f205e081 100644 --- a/trie/iterator.go +++ b/trie/iterator.go @@ -16,7 +16,12 @@ package trie -import "bytes" +import ( + "bytes" + + "github.com/ethereum/go-ethereum/logger" + "github.com/ethereum/go-ethereum/logger/glog" +) type Iterator struct { trie *Trie @@ -100,7 +105,11 @@ func (self *Iterator) next(node interface{}, key []byte, isIterStart bool) []byt } case hashNode: - return self.next(self.trie.resolveHash(node), key, isIterStart) + rn, err := self.trie.resolveHash(node, nil, nil) + if err != nil && glog.V(logger.Error) { + glog.Errorf("Unhandled trie error: %v", err) + } + return self.next(rn, key, isIterStart) } return nil } @@ -127,7 +136,11 @@ func (self *Iterator) key(node interface{}) []byte { } } case hashNode: - return self.key(self.trie.resolveHash(node)) + rn, err := self.trie.resolveHash(node, nil, nil) + if err != nil && glog.V(logger.Error) { + glog.Errorf("Unhandled trie error: %v", err) + } + return self.key(rn) } return nil diff --git a/trie/proof.go b/trie/proof.go index a705c49db..2e88bb50b 100644 --- a/trie/proof.go +++ b/trie/proof.go @@ -7,6 +7,8 @@ import ( "github.com/ethereum/go-ethereum/common" "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" ) @@ -39,7 +41,14 @@ func (t *Trie) Prove(key []byte) []rlp.RawValue { case nil: return nil case hashNode: - tn = t.resolveHash(n) + var err error + tn, err = t.resolveHash(n, nil, nil) + if err != nil { + if glog.V(logger.Error) { + glog.Errorf("Unhandled trie error: %v", err) + } + return nil + } default: panic(fmt.Sprintf("%T: invalid node: %v", tn, tn)) } diff --git a/trie/secure_trie.go b/trie/secure_trie.go index 47d1934d0..caeef3c3a 100644 --- a/trie/secure_trie.go +++ b/trie/secure_trie.go @@ -21,6 +21,8 @@ import ( "github.com/ethereum/go-ethereum/common" "github.com/ethereum/go-ethereum/crypto/sha3" + "github.com/ethereum/go-ethereum/logger" + "github.com/ethereum/go-ethereum/logger/glog" ) var secureKeyPrefix = []byte("secure-key-") @@ -46,8 +48,8 @@ type SecureTrie struct { // NewSecure 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. Otherwise, New will panics if db is nil -// and returns ErrMissingRoot if the root node cannpt be found. +// trie is initially empty. Otherwise, New will panic if db is nil +// and returns MissingNodeError if the root node cannot be found. // Accessing the trie loads nodes from db on demand. func NewSecure(root common.Hash, db Database) (*SecureTrie, error) { if db == nil { @@ -63,7 +65,18 @@ func NewSecure(root common.Hash, db Database) (*SecureTrie, error) { // Get returns the value for key stored in the trie. // The value bytes must not be modified by the caller. func (t *SecureTrie) Get(key []byte) []byte { - return t.Trie.Get(t.hashKey(key)) + res, err := t.TryGet(key) + if err != nil && glog.V(logger.Error) { + glog.Errorf("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 *SecureTrie) TryGet(key []byte) ([]byte, error) { + return t.Trie.TryGet(t.hashKey(key)) } // Update associates key with value in the trie. Subsequent calls to @@ -73,14 +86,40 @@ func (t *SecureTrie) Get(key []byte) []byte { // The value bytes must not be modified by the caller while they are // stored in the trie. func (t *SecureTrie) Update(key, value []byte) { + if err := t.TryUpdate(key, value); err != nil && glog.V(logger.Error) { + glog.Errorf("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 *SecureTrie) TryUpdate(key, value []byte) error { hk := t.hashKey(key) - t.Trie.Update(hk, value) + err := t.Trie.TryUpdate(hk, value) + if err != nil { + return err + } t.Trie.db.Put(t.secKey(hk), key) + return nil } // Delete removes any existing value for key from the trie. func (t *SecureTrie) Delete(key []byte) { - t.Trie.Delete(t.hashKey(key)) + if err := t.TryDelete(key); err != nil && glog.V(logger.Error) { + glog.Errorf("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 *SecureTrie) TryDelete(key []byte) error { + return t.Trie.TryDelete(t.hashKey(key)) } // GetKey returns the sha3 preimage of a hashed key that was diff --git a/trie/trie.go b/trie/trie.go index a3a383fb5..717296e27 100644 --- a/trie/trie.go +++ b/trie/trie.go @@ -19,7 +19,6 @@ package trie import ( "bytes" - "errors" "fmt" "hash" @@ -44,7 +43,10 @@ var ( emptyState = crypto.Sha3Hash(nil) ) -var ErrMissingRoot = errors.New("missing root node") +// ClearGlobalCache clears the global trie cache +func ClearGlobalCache() { + globalCache.Clear() +} // Database must be implemented by backing stores for the trie. type Database interface { @@ -67,8 +69,9 @@ type DatabaseWriter interface { // // Trie is not safe for concurrent use. type Trie struct { - root node - db Database + root node + db Database + originalRoot common.Hash *hasher } @@ -76,16 +79,19 @@ type Trie struct { // // 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 panics if db is nil or root does not exist in the -// database. Accessing the trie loads nodes from db on demand. +// 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) { - trie := &Trie{db: db} + trie := &Trie{db: db, originalRoot: root} if (root != common.Hash{}) && root != emptyRoot { if db == nil { panic("trie.New: cannot use existing root without a database") } if v, _ := trie.db.Get(root[:]); len(v) == 0 { - return nil, ErrMissingRoot + return nil, &MissingNodeError{ + RootHash: root, + NodeHash: root, + } } trie.root = hashNode(root.Bytes()) } @@ -100,28 +106,44 @@ func (t *Trie) Iterator() *Iterator { // 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 && glog.V(logger.Error) { + glog.Errorf("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) { key = compactHexDecode(key) + pos := 0 tn := t.root - for len(key) > 0 { + for pos < len(key) { switch n := tn.(type) { case shortNode: - if len(key) < len(n.Key) || !bytes.Equal(n.Key, key[:len(n.Key)]) { - return nil + if len(key)-pos < len(n.Key) || !bytes.Equal(n.Key, key[pos:pos+len(n.Key)]) { + return nil, nil } tn = n.Val - key = key[len(n.Key):] + pos += len(n.Key) case fullNode: - tn = n[key[0]] - key = key[1:] + tn = n[key[pos]] + pos++ case nil: - return nil + return nil, nil case hashNode: - tn = t.resolveHash(n) + 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)) } } - return tn.(valueNode) + return tn.(valueNode), nil } // Update associates key with value in the trie. Subsequent calls to @@ -131,17 +153,40 @@ func (t *Trie) Get(key []byte) []byte { // 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 && glog.V(logger.Error) { + glog.Errorf("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 { k := compactHexDecode(key) if len(value) != 0 { - t.root = t.insert(t.root, k, valueNode(value)) + n, err := t.insert(t.root, nil, k, valueNode(value)) + if err != nil { + return err + } + t.root = n } else { - t.root = t.delete(t.root, k) + n, err := t.delete(t.root, nil, k) + if err != nil { + return err + } + t.root = n } + return nil } -func (t *Trie) insert(n node, key []byte, value node) node { +func (t *Trie) insert(n node, prefix, key []byte, value node) (node, error) { if len(key) == 0 { - return value + return value, nil } switch n := n.(type) { case shortNode: @@ -149,25 +194,40 @@ func (t *Trie) insert(n node, key []byte, value node) node { // If the whole key matches, keep this short node as is // and only update the value. if matchlen == len(n.Key) { - return shortNode{n.Key, t.insert(n.Val, key[matchlen:], value)} + nn, err := t.insert(n.Val, append(prefix, key[:matchlen]...), key[matchlen:], value) + if err != nil { + return nil, err + } + return shortNode{n.Key, nn}, nil } // Otherwise branch out at the index where they differ. var branch fullNode - branch[n.Key[matchlen]] = t.insert(nil, n.Key[matchlen+1:], n.Val) - branch[key[matchlen]] = t.insert(nil, key[matchlen+1:], value) + var err error + branch[n.Key[matchlen]], err = t.insert(nil, append(prefix, n.Key[:matchlen+1]...), n.Key[matchlen+1:], n.Val) + if err != nil { + return nil, err + } + branch[key[matchlen]], err = t.insert(nil, append(prefix, key[:matchlen+1]...), key[matchlen+1:], value) + if err != nil { + return nil, err + } // Replace this shortNode with the branch if it occurs at index 0. if matchlen == 0 { - return branch + return branch, nil } // Otherwise, replace it with a short node leading up to the branch. - return shortNode{key[:matchlen], branch} + return shortNode{key[:matchlen], branch}, nil case fullNode: - n[key[0]] = t.insert(n[key[0]], key[1:], value) - return n + nn, err := t.insert(n[key[0]], append(prefix, key[0]), key[1:], value) + if err != nil { + return nil, err + } + n[key[0]] = nn + return n, nil case nil: - return shortNode{key, value} + return shortNode{key, value}, nil case hashNode: // We've hit a part of the trie that isn't loaded yet. Load @@ -176,7 +236,11 @@ func (t *Trie) insert(n node, key []byte, value node) node { // // TODO: track whether insertion changed the value and keep // n as a hash node if it didn't. - return t.insert(t.resolveHash(n), key, value) + rn, err := t.resolveHash(n, prefix, key) + if err != nil { + return nil, err + } + return t.insert(rn, prefix, key, value) default: panic(fmt.Sprintf("%T: invalid node: %v", n, n)) @@ -185,28 +249,44 @@ func (t *Trie) insert(n node, key []byte, value node) node { // Delete removes any existing value for key from the trie. func (t *Trie) Delete(key []byte) { + if err := t.TryDelete(key); err != nil && glog.V(logger.Error) { + glog.Errorf("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 { k := compactHexDecode(key) - t.root = t.delete(t.root, k) + 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, key []byte) node { +func (t *Trie) delete(n node, prefix, key []byte) (node, error) { switch n := n.(type) { case shortNode: matchlen := prefixLen(key, n.Key) if matchlen < len(n.Key) { - return n // don't replace n on mismatch + return n, nil // don't replace n on mismatch } if matchlen == len(key) { - return nil // remove n entirely for whole matches + return 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. - child := t.delete(n.Val, key[len(n.Key):]) + child, err := t.delete(n.Val, append(prefix, key[:len(n.Key)]...), key[len(n.Key):]) + if err != nil { + return nil, err + } switch child := child.(type) { case shortNode: // Deleting from the subtrie reduced it to another @@ -215,13 +295,17 @@ func (t *Trie) delete(n node, key []byte) node { // always creates a new slice) instead of append to // avoid modifying n.Key since it might be shared with // other nodes. - return shortNode{concat(n.Key, child.Key...), child.Val} + return shortNode{concat(n.Key, child.Key...), child.Val}, nil default: - return shortNode{n.Key, child} + return shortNode{n.Key, child}, nil } case fullNode: - n[key[0]] = t.delete(n[key[0]], key[1:]) + nn, err := t.delete(n[key[0]], append(prefix, key[0]), key[1:]) + if err != nil { + return nil, err + } + n[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 @@ -250,21 +334,24 @@ func (t *Trie) delete(n node, key []byte) node { // shortNode{..., shortNode{...}}. Since the entry // might not be loaded yet, resolve it just for this // check. - cnode := t.resolve(n[pos]) + cnode, err := t.resolve(n[pos], prefix, []byte{byte(pos)}) + if err != nil { + return nil, err + } if cnode, ok := cnode.(shortNode); ok { k := append([]byte{byte(pos)}, cnode.Key...) - return shortNode{k, cnode.Val} + return shortNode{k, cnode.Val}, nil } } // Otherwise, n is replaced by a one-nibble short node // containing the child. - return shortNode{[]byte{byte(pos)}, n[pos]} + return shortNode{[]byte{byte(pos)}, n[pos]}, nil } // n still contains at least two values and cannot be reduced. - return n + return n, nil case nil: - return nil + return nil, nil case hashNode: // We've hit a part of the trie that isn't loaded yet. Load @@ -273,7 +360,11 @@ func (t *Trie) delete(n node, key []byte) node { // // TODO: track whether deletion actually hit a key and keep // n as a hash node if it didn't. - return t.delete(t.resolveHash(n), key) + rn, err := t.resolveHash(n, prefix, key) + if err != nil { + return nil, err + } + return t.delete(rn, prefix, key) default: panic(fmt.Sprintf("%T: invalid node: %v (%v)", n, n, key)) @@ -287,34 +378,31 @@ func concat(s1 []byte, s2 ...byte) []byte { return r } -func (t *Trie) resolve(n node) node { +func (t *Trie) resolve(n node, prefix, suffix []byte) (node, error) { if n, ok := n.(hashNode); ok { - return t.resolveHash(n) + return t.resolveHash(n, prefix, suffix) } - return n + return n, nil } -func (t *Trie) resolveHash(n hashNode) node { +func (t *Trie) resolveHash(n hashNode, prefix, suffix []byte) (node, error) { if v, ok := globalCache.Get(n); ok { - return v + return v, nil } enc, err := t.db.Get(n) if err != nil || enc == nil { - // TODO: This needs to be improved to properly distinguish errors. - // Disk I/O errors shouldn't produce nil (and cause a - // consensus failure or weird crash), but it is unclear how - // they could be handled because the entire stack above the trie isn't - // prepared to cope with missing state nodes. - if glog.V(logger.Error) { - glog.Errorf("Dangling hash node ref %x: %v", n, err) + return nil, &MissingNodeError{ + RootHash: t.originalRoot, + NodeHash: common.BytesToHash(n), + KeyPrefix: prefix, + KeySuffix: suffix, } - return nil } dec := mustDecodeNode(n, enc) if dec != nil { globalCache.Put(n, dec) } - return dec + return dec, nil } // Root returns the root hash of the trie. diff --git a/trie/trie_test.go b/trie/trie_test.go index c96861bed..35d043cdf 100644 --- a/trie/trie_test.go +++ b/trie/trie_test.go @@ -64,11 +64,84 @@ func TestMissingRoot(t *testing.T) { if trie != nil { t.Error("New returned non-nil trie for invalid root") } - if err != ErrMissingRoot { + if _, ok := err.(*MissingNodeError); !ok { t.Error("New returned wrong error: %v", err) } } +func TestMissingNode(t *testing.T) { + db, _ := ethdb.NewMemDatabase() + trie, _ := New(common.Hash{}, db) + updateString(trie, "120000", "qwerqwerqwerqwerqwerqwerqwerqwer") + updateString(trie, "123456", "asdfasdfasdfasdfasdfasdfasdfasdf") + root, _ := trie.Commit() + + ClearGlobalCache() + + trie, _ = New(root, db) + _, err := trie.TryGet([]byte("120000")) + if err != nil { + t.Errorf("Unexpected error: %v", err) + } + + trie, _ = New(root, db) + _, err = trie.TryGet([]byte("120099")) + if err != nil { + t.Errorf("Unexpected error: %v", err) + } + + trie, _ = New(root, db) + _, err = trie.TryGet([]byte("123456")) + if err != nil { + t.Errorf("Unexpected error: %v", err) + } + + trie, _ = New(root, db) + err = trie.TryUpdate([]byte("120099"), []byte("zxcvzxcvzxcvzxcvzxcvzxcvzxcvzxcv")) + if err != nil { + t.Errorf("Unexpected error: %v", err) + } + + trie, _ = New(root, db) + err = trie.TryDelete([]byte("123456")) + if err != nil { + t.Errorf("Unexpected error: %v", err) + } + + db.Delete(common.FromHex("e1d943cc8f061a0c0b98162830b970395ac9315654824bf21b73b891365262f9")) + ClearGlobalCache() + + trie, _ = New(root, db) + _, err = trie.TryGet([]byte("120000")) + if _, ok := err.(*MissingNodeError); !ok { + t.Errorf("Wrong error: %v", err) + } + + trie, _ = New(root, db) + _, err = trie.TryGet([]byte("120099")) + if _, ok := err.(*MissingNodeError); !ok { + t.Errorf("Wrong error: %v", err) + } + + trie, _ = New(root, db) + _, err = trie.TryGet([]byte("123456")) + if err != nil { + t.Errorf("Unexpected error: %v", err) + } + + trie, _ = New(root, db) + err = trie.TryUpdate([]byte("120099"), []byte("zxcv")) + if _, ok := err.(*MissingNodeError); !ok { + t.Errorf("Wrong error: %v", err) + } + + trie, _ = New(root, db) + err = trie.TryDelete([]byte("123456")) + if _, ok := err.(*MissingNodeError); !ok { + t.Errorf("Wrong error: %v", err) + } +} + func TestInsert(t *testing.T) { trie := newEmpty() |