aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorPéter Szilágyi <peterke@gmail.com>2016-09-30 21:44:00 +0800
committerGitHub <noreply@github.com>2016-09-30 21:44:00 +0800
commitd8715fba1a366944a069397775fc52a30358eff3 (patch)
treebc21aad9b6de1db5f6d4264f2449745078d3a3ed
parentb4cc8cbac4c1756c179e497c53ee83515669fe13 (diff)
parentc3a77d626831b4ffe37ed4f8640e67e70ad5b220 (diff)
downloaddexon-d8715fba1a366944a069397775fc52a30358eff3.tar.gz
dexon-d8715fba1a366944a069397775fc52a30358eff3.tar.zst
dexon-d8715fba1a366944a069397775fc52a30358eff3.zip
Merge pull request #3062 from fjl/trie-delete-bug
trie: fix delete bug for values contained in fullNode
-rw-r--r--trie/trie.go12
-rw-r--r--trie/trie_test.go159
2 files changed, 133 insertions, 38 deletions
diff --git a/trie/trie.go b/trie/trie.go
index 93e189e2e..55598af98 100644
--- a/trie/trie.go
+++ b/trie/trie.go
@@ -22,7 +22,7 @@ import (
"fmt"
"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"
)
@@ -30,11 +30,14 @@ import (
var (
// This is the known root hash of an empty trie.
emptyRoot = common.HexToHash("56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421")
-
// This is the known hash of an empty state trie entry.
- emptyState = crypto.Keccak256Hash(nil)
+ emptyState common.Hash
)
+func init() {
+ sha3.NewKeccak256().Sum(emptyState[:0])
+}
+
// Database must be implemented by backing stores for the trie.
type Database interface {
DatabaseWriter
@@ -374,6 +377,9 @@ func (t *Trie) delete(n node, prefix, key []byte) (bool, node, error) {
// 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
diff --git a/trie/trie_test.go b/trie/trie_test.go
index 5a3ea1be9..87a7ec258 100644
--- a/trie/trie_test.go
+++ b/trie/trie_test.go
@@ -21,8 +21,11 @@ import (
"encoding/binary"
"fmt"
"io/ioutil"
+ "math/rand"
"os"
+ "reflect"
"testing"
+ "testing/quick"
"github.com/davecgh/go-spew/spew"
"github.com/ethereum/go-ethereum/common"
@@ -297,41 +300,6 @@ func TestReplication(t *testing.T) {
}
}
-func paranoiaCheck(t1 *Trie) (bool, *Trie) {
- t2 := new(Trie)
- it := NewIterator(t1)
- for it.Next() {
- t2.Update(it.Key, it.Value)
- }
- return t2.Hash() == t1.Hash(), t2
-}
-
-func TestParanoia(t *testing.T) {
- t.Skip()
- trie := newEmpty()
-
- vals := []struct{ k, v string }{
- {"do", "verb"},
- {"ether", "wookiedoo"},
- {"horse", "stallion"},
- {"shaman", "horse"},
- {"doge", "coin"},
- {"ether", ""},
- {"dog", "puppy"},
- {"shaman", ""},
- {"somethingveryoddindeedthis is", "myothernodedata"},
- }
- for _, val := range vals {
- updateString(trie, val.k, val.v)
- }
- trie.Commit()
-
- ok, t2 := paranoiaCheck(trie)
- if !ok {
- t.Errorf("trie paranoia check failed %x %x", trie.Hash(), t2.Hash())
- }
-}
-
// Not an actual test
func TestOutput(t *testing.T) {
t.Skip()
@@ -356,7 +324,128 @@ func TestLargeValue(t *testing.T) {
trie.Update([]byte("key1"), []byte{99, 99, 99, 99})
trie.Update([]byte("key2"), bytes.Repeat([]byte{1}, 32))
trie.Hash()
+}
+
+type randTestStep struct {
+ op int
+ key []byte // for opUpdate, opDelete, opGet
+ value []byte // for opUpdate
+}
+
+type randTest []randTestStep
+
+const (
+ opUpdate = iota
+ opDelete
+ opGet
+ opCommit
+ opHash
+ opReset
+ opItercheckhash
+ opMax // boundary value, not an actual op
+)
+
+func (randTest) Generate(r *rand.Rand, size int) reflect.Value {
+ var allKeys [][]byte
+ genKey := func() []byte {
+ if len(allKeys) < 2 || r.Intn(100) < 10 {
+ // new key
+ key := make([]byte, r.Intn(50))
+ randRead(r, key)
+ allKeys = append(allKeys, key)
+ return key
+ }
+ // use existing key
+ return allKeys[r.Intn(len(allKeys))]
+ }
+
+ var steps randTest
+ for i := 0; i < size; i++ {
+ step := randTestStep{op: r.Intn(opMax)}
+ switch step.op {
+ case opUpdate:
+ step.key = genKey()
+ step.value = make([]byte, 8)
+ binary.BigEndian.PutUint64(step.value, uint64(i))
+ case opGet, opDelete:
+ step.key = genKey()
+ }
+ steps = append(steps, step)
+ }
+ return reflect.ValueOf(steps)
+}
+
+// rand.Rand provides a Read method in Go 1.7 and later, but
+// we can't use it yet.
+func randRead(r *rand.Rand, b []byte) {
+ pos := 0
+ val := 0
+ for n := 0; n < len(b); n++ {
+ if pos == 0 {
+ val = r.Int()
+ pos = 7
+ }
+ b[n] = byte(val)
+ val >>= 8
+ pos--
+ }
+}
+func runRandTest(rt randTest) bool {
+ db, _ := ethdb.NewMemDatabase()
+ tr, _ := New(common.Hash{}, db)
+ values := make(map[string]string) // tracks content of the trie
+
+ for _, step := range rt {
+ switch step.op {
+ case opUpdate:
+ tr.Update(step.key, step.value)
+ values[string(step.key)] = string(step.value)
+ case opDelete:
+ tr.Delete(step.key)
+ delete(values, string(step.key))
+ case opGet:
+ v := tr.Get(step.key)
+ want := values[string(step.key)]
+ if string(v) != want {
+ fmt.Printf("mismatch for key 0x%x, got 0x%x want 0x%x", step.key, v, want)
+ return false
+ }
+ case opCommit:
+ if _, err := tr.Commit(); err != nil {
+ panic(err)
+ }
+ case opHash:
+ tr.Hash()
+ case opReset:
+ hash, err := tr.Commit()
+ if err != nil {
+ panic(err)
+ }
+ newtr, err := New(hash, db)
+ if err != nil {
+ panic(err)
+ }
+ tr = newtr
+ case opItercheckhash:
+ checktr, _ := New(common.Hash{}, nil)
+ it := tr.Iterator()
+ for it.Next() {
+ checktr.Update(it.Key, it.Value)
+ }
+ if tr.Hash() != checktr.Hash() {
+ fmt.Println("hashes not equal")
+ return false
+ }
+ }
+ }
+ return true
+}
+
+func TestRandom(t *testing.T) {
+ if err := quick.Check(runRandTest, nil); err != nil {
+ t.Fatal(err)
+ }
}
func BenchmarkGet(b *testing.B) { benchGet(b, false) }