trie_test.go 13.6 KB
Newer Older
1
// Copyright 2014 The go-ethereum Authors
2
// This file is part of the go-ethereum library.
3
//
4
// The go-ethereum library is free software: you can redistribute it and/or modify
5 6 7 8
// 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.
//
9
// The go-ethereum library is distributed in the hope that it will be useful,
10
// but WITHOUT ANY WARRANTY; without even the implied warranty of
11
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 13 14
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
15
// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
16

obscuren's avatar
obscuren committed
17
package trie
obscuren's avatar
obscuren committed
18 19

import (
obscuren's avatar
obscuren committed
20
	"bytes"
Felix Lange's avatar
Felix Lange committed
21
	"encoding/binary"
obscuren's avatar
obscuren committed
22
	"fmt"
Felix Lange's avatar
Felix Lange committed
23
	"io/ioutil"
24
	"math/rand"
Felix Lange's avatar
Felix Lange committed
25
	"os"
26
	"reflect"
obscuren's avatar
obscuren committed
27
	"testing"
28
	"testing/quick"
29

Felix Lange's avatar
Felix Lange committed
30
	"github.com/davecgh/go-spew/spew"
obscuren's avatar
obscuren committed
31
	"github.com/ethereum/go-ethereum/common"
Felix Lange's avatar
Felix Lange committed
32
	"github.com/ethereum/go-ethereum/ethdb"
obscuren's avatar
obscuren committed
33 34
)

Felix Lange's avatar
Felix Lange committed
35 36 37
func init() {
	spew.Config.Indent = "    "
	spew.Config.DisableMethods = true
obscuren's avatar
obscuren committed
38 39
}

Felix Lange's avatar
Felix Lange committed
40 41 42 43 44
// Used for testing
func newEmpty() *Trie {
	db, _ := ethdb.NewMemDatabase()
	trie, _ := New(common.Hash{}, db)
	return trie
obscuren's avatar
obscuren committed
45 46
}

47
func TestEmptyTrie(t *testing.T) {
Felix Lange's avatar
Felix Lange committed
48
	var trie Trie
49
	res := trie.Hash()
Felix Lange's avatar
Felix Lange committed
50 51
	exp := emptyRoot
	if res != common.Hash(exp) {
52 53
		t.Errorf("expected %x got %x", exp, res)
	}
obscuren's avatar
obscuren committed
54 55
}

56
func TestNull(t *testing.T) {
Felix Lange's avatar
Felix Lange committed
57
	var trie Trie
58
	key := make([]byte, 32)
59
	value := []byte("test")
60
	trie.Update(key, value)
61 62 63
	if !bytes.Equal(trie.Get(key), value) {
		t.Fatal("wrong value")
	}
64 65
}

Felix Lange's avatar
Felix Lange committed
66 67 68 69 70 71
func TestMissingRoot(t *testing.T) {
	db, _ := ethdb.NewMemDatabase()
	trie, err := New(common.HexToHash("0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33"), db)
	if trie != nil {
		t.Error("New returned non-nil trie for invalid root")
	}
72
	if _, ok := err.(*MissingNodeError); !ok {
Felix Lange's avatar
Felix Lange committed
73
		t.Errorf("New returned wrong error: %v", err)
Felix Lange's avatar
Felix Lange committed
74 75 76
	}
}

77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146
func TestMissingNode(t *testing.T) {
	db, _ := ethdb.NewMemDatabase()
	trie, _ := New(common.Hash{}, db)
	updateString(trie, "120000", "qwerqwerqwerqwerqwerqwerqwerqwer")
	updateString(trie, "123456", "asdfasdfasdfasdfasdfasdfasdfasdf")
	root, _ := trie.Commit()

	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"))

	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)
	}
}

147
func TestInsert(t *testing.T) {
Felix Lange's avatar
Felix Lange committed
148
	trie := newEmpty()
obscuren's avatar
obscuren committed
149

Felix Lange's avatar
Felix Lange committed
150 151 152
	updateString(trie, "doe", "reindeer")
	updateString(trie, "dog", "puppy")
	updateString(trie, "dogglesworth", "cat")
obscuren's avatar
obscuren committed
153

Felix Lange's avatar
Felix Lange committed
154
	exp := common.HexToHash("8aad789dff2f538bca5d8ea56e8abe10f4c7ba3a5dea95fea4cd6e7c3a1168d3")
155
	root := trie.Hash()
Felix Lange's avatar
Felix Lange committed
156
	if root != exp {
157 158
		t.Errorf("exp %x got %x", exp, root)
	}
159

Felix Lange's avatar
Felix Lange committed
160 161
	trie = newEmpty()
	updateString(trie, "A", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
162

Felix Lange's avatar
Felix Lange committed
163 164 165 166 167 168
	exp = common.HexToHash("d23786fb4a010da3ce639d66d5e904a11dbc02746d1ce25029e53290cabf28ab")
	root, err := trie.Commit()
	if err != nil {
		t.Fatalf("commit error: %v", err)
	}
	if root != exp {
169 170
		t.Errorf("exp %x got %x", exp, root)
	}
171
}
obscuren's avatar
obscuren committed
172

173
func TestGet(t *testing.T) {
Felix Lange's avatar
Felix Lange committed
174 175 176 177 178 179 180 181 182 183
	trie := newEmpty()
	updateString(trie, "doe", "reindeer")
	updateString(trie, "dog", "puppy")
	updateString(trie, "dogglesworth", "cat")

	for i := 0; i < 2; i++ {
		res := getString(trie, "dog")
		if !bytes.Equal(res, []byte("puppy")) {
			t.Errorf("expected puppy got %x", res)
		}
obscuren's avatar
obscuren committed
184

Felix Lange's avatar
Felix Lange committed
185 186 187 188
		unknown := getString(trie, "unknown")
		if unknown != nil {
			t.Errorf("expected nil got %x", unknown)
		}
obscuren's avatar
obscuren committed
189

Felix Lange's avatar
Felix Lange committed
190 191 192 193
		if i == 1 {
			return
		}
		trie.Commit()
194
	}
obscuren's avatar
obscuren committed
195 196
}

197
func TestDelete(t *testing.T) {
Felix Lange's avatar
Felix Lange committed
198
	trie := newEmpty()
199 200 201 202 203 204 205 206 207
	vals := []struct{ k, v string }{
		{"do", "verb"},
		{"ether", "wookiedoo"},
		{"horse", "stallion"},
		{"shaman", "horse"},
		{"doge", "coin"},
		{"ether", ""},
		{"dog", "puppy"},
		{"shaman", ""},
208
	}
209 210
	for _, val := range vals {
		if val.v != "" {
Felix Lange's avatar
Felix Lange committed
211
			updateString(trie, val.k, val.v)
212
		} else {
Felix Lange's avatar
Felix Lange committed
213
			deleteString(trie, val.k)
214
		}
obscuren's avatar
obscuren committed
215 216
	}

217
	hash := trie.Hash()
Felix Lange's avatar
Felix Lange committed
218 219
	exp := common.HexToHash("5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84")
	if hash != exp {
220
		t.Errorf("expected %x got %x", exp, hash)
obscuren's avatar
obscuren committed
221
	}
222
}
obscuren's avatar
obscuren committed
223

224
func TestEmptyValues(t *testing.T) {
Felix Lange's avatar
Felix Lange committed
225
	trie := newEmpty()
obscuren's avatar
obscuren committed
226

227 228 229 230 231 232 233 234 235
	vals := []struct{ k, v string }{
		{"do", "verb"},
		{"ether", "wookiedoo"},
		{"horse", "stallion"},
		{"shaman", "horse"},
		{"doge", "coin"},
		{"ether", ""},
		{"dog", "puppy"},
		{"shaman", ""},
obscuren's avatar
obscuren committed
236
	}
237
	for _, val := range vals {
Felix Lange's avatar
Felix Lange committed
238
		updateString(trie, val.k, val.v)
obscuren's avatar
obscuren committed
239 240
	}

241
	hash := trie.Hash()
Felix Lange's avatar
Felix Lange committed
242 243
	exp := common.HexToHash("5991bb8c6514148a29db676a14ac506cd2cd5775ace63c30a4fe457715e9ac84")
	if hash != exp {
244
		t.Errorf("expected %x got %x", exp, hash)
245
	}
obscuren's avatar
obscuren committed
246 247
}

248
func TestReplication(t *testing.T) {
Felix Lange's avatar
Felix Lange committed
249
	trie := newEmpty()
250 251 252 253 254 255 256 257
	vals := []struct{ k, v string }{
		{"do", "verb"},
		{"ether", "wookiedoo"},
		{"horse", "stallion"},
		{"shaman", "horse"},
		{"doge", "coin"},
		{"dog", "puppy"},
		{"somethingveryoddindeedthis is", "myothernodedata"},
258
	}
259
	for _, val := range vals {
Felix Lange's avatar
Felix Lange committed
260
		updateString(trie, val.k, val.v)
261
	}
Felix Lange's avatar
Felix Lange committed
262 263 264
	exp, err := trie.Commit()
	if err != nil {
		t.Fatalf("commit error: %v", err)
265
	}
266

Felix Lange's avatar
Felix Lange committed
267 268 269 270 271 272 273 274 275 276 277 278 279 280 281
	// create a new trie on top of the database and check that lookups work.
	trie2, err := New(exp, trie.db)
	if err != nil {
		t.Fatalf("can't recreate trie at %x: %v", exp, err)
	}
	for _, kv := range vals {
		if string(getString(trie2, kv.k)) != kv.v {
			t.Errorf("trie2 doesn't have %q => %q", kv.k, kv.v)
		}
	}
	hash, err := trie2.Commit()
	if err != nil {
		t.Fatalf("commit error: %v", err)
	}
	if hash != exp {
282 283
		t.Errorf("root failure. expected %x got %x", exp, hash)
	}
obscuren's avatar
obscuren committed
284

Felix Lange's avatar
Felix Lange committed
285 286
	// perform some insertions on the new trie.
	vals2 := []struct{ k, v string }{
287 288 289
		{"do", "verb"},
		{"ether", "wookiedoo"},
		{"horse", "stallion"},
Felix Lange's avatar
Felix Lange committed
290 291 292 293 294 295
		// {"shaman", "horse"},
		// {"doge", "coin"},
		// {"ether", ""},
		// {"dog", "puppy"},
		// {"somethingveryoddindeedthis is", "myothernodedata"},
		// {"shaman", ""},
296
	}
Felix Lange's avatar
Felix Lange committed
297 298
	for _, val := range vals2 {
		updateString(trie2, val.k, val.v)
299
	}
300
	if hash := trie2.Hash(); hash != exp {
Felix Lange's avatar
Felix Lange committed
301 302 303
		t.Errorf("root failure. expected %x got %x", exp, hash)
	}
}
304

Felix Lange's avatar
Felix Lange committed
305 306 307 308 309
func TestLargeValue(t *testing.T) {
	trie := newEmpty()
	trie.Update([]byte("key1"), []byte{99, 99, 99, 99})
	trie.Update([]byte("key2"), bytes.Repeat([]byte{1}, 32))
	trie.Hash()
310 311
}

312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355
type countingDB struct {
	Database
	gets map[string]int
}

func (db *countingDB) Get(key []byte) ([]byte, error) {
	db.gets[string(key)]++
	return db.Database.Get(key)
}

// TestCacheUnload checks that decoded nodes are unloaded after a
// certain number of commit operations.
func TestCacheUnload(t *testing.T) {
	// Create test trie with two branches.
	trie := newEmpty()
	key1 := "---------------------------------"
	key2 := "---some other branch"
	updateString(trie, key1, "this is the branch of key1.")
	updateString(trie, key2, "this is the branch of key2.")
	root, _ := trie.Commit()

	// Commit the trie repeatedly and access key1.
	// The branch containing it is loaded from DB exactly two times:
	// in the 0th and 6th iteration.
	db := &countingDB{Database: trie.db, gets: make(map[string]int)}
	trie, _ = New(root, db)
	trie.SetCacheLimit(5)
	for i := 0; i < 12; i++ {
		getString(trie, key1)
		trie.Commit()
	}

	// Check that it got loaded two times.
	for dbkey, count := range db.gets {
		if count != 2 {
			t.Errorf("db key %x loaded %d times, want %d times", []byte(dbkey), count, 2)
		}
	}
}

// randTest performs random trie operations.
// Instances of this test are created by Generate.
type randTest []randTestStep

356 357 358 359 360 361 362 363 364 365 366 367 368 369
type randTestStep struct {
	op    int
	key   []byte // for opUpdate, opDelete, opGet
	value []byte // for opUpdate
}

const (
	opUpdate = iota
	opDelete
	opGet
	opCommit
	opHash
	opReset
	opItercheckhash
370
	opCheckCacheInvariant
371 372 373 374 375 376 377 378 379
	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))
380
			r.Read(key)
381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441
			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)
}

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)
442
			it := NewIterator(tr.NodeIterator(nil))
443 444 445 446 447 448 449
			for it.Next() {
				checktr.Update(it.Key, it.Value)
			}
			if tr.Hash() != checktr.Hash() {
				fmt.Println("hashes not equal")
				return false
			}
450
		case opCheckCacheInvariant:
451
			return checkCacheInvariant(tr.root, nil, tr.cachegen, false, 0)
452 453 454 455 456
		}
	}
	return true
}

457 458 459
func checkCacheInvariant(n, parent node, parentCachegen uint16, parentDirty bool, depth int) bool {
	var children []node
	var flag nodeFlag
460 461
	switch n := n.(type) {
	case *shortNode:
462 463
		flag = n.flags
		children = []node{n.Val}
464
	case *fullNode:
465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486
		flag = n.flags
		children = n.Children[:]
	default:
		return true
	}

	showerror := func() {
		fmt.Printf("at depth %d node %s", depth, spew.Sdump(n))
		fmt.Printf("parent: %s", spew.Sdump(parent))
	}
	if flag.gen > parentCachegen {
		fmt.Printf("cache invariant violation: %d > %d\n", flag.gen, parentCachegen)
		showerror()
		return false
	}
	if depth > 0 && !parentDirty && flag.dirty {
		fmt.Printf("cache invariant violation: child is dirty but parent isn't\n")
		showerror()
		return false
	}
	for _, child := range children {
		if !checkCacheInvariant(child, n, flag.gen, flag.dirty, depth+1) {
487 488
			return false
		}
489 490 491 492 493 494 495 496
	}
	return true
}

func TestRandom(t *testing.T) {
	if err := quick.Check(runRandTest, nil); err != nil {
		t.Fatal(err)
	}
Felix Lange's avatar
Felix Lange committed
497 498
}

Felix Lange's avatar
Felix Lange committed
499 500 501 502 503 504 505 506 507 508
func BenchmarkGet(b *testing.B)      { benchGet(b, false) }
func BenchmarkGetDB(b *testing.B)    { benchGet(b, true) }
func BenchmarkUpdateBE(b *testing.B) { benchUpdate(b, binary.BigEndian) }
func BenchmarkUpdateLE(b *testing.B) { benchUpdate(b, binary.LittleEndian) }
func BenchmarkHashBE(b *testing.B)   { benchHash(b, binary.BigEndian) }
func BenchmarkHashLE(b *testing.B)   { benchHash(b, binary.LittleEndian) }

const benchElemCount = 20000

func benchGet(b *testing.B, commit bool) {
Felix Lange's avatar
Felix Lange committed
509
	trie := new(Trie)
Felix Lange's avatar
Felix Lange committed
510
	if commit {
511
		_, tmpdb := tempDB()
Felix Lange's avatar
Felix Lange committed
512
		trie, _ = New(common.Hash{}, tmpdb)
Felix Lange's avatar
Felix Lange committed
513 514 515 516 517 518 519 520 521 522 523 524 525 526 527
	}
	k := make([]byte, 32)
	for i := 0; i < benchElemCount; i++ {
		binary.LittleEndian.PutUint64(k, uint64(i))
		trie.Update(k, k)
	}
	binary.LittleEndian.PutUint64(k, benchElemCount/2)
	if commit {
		trie.Commit()
	}

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		trie.Get(k)
	}
528 529 530 531 532 533 534
	b.StopTimer()

	if commit {
		ldb := trie.db.(*ethdb.LDBDatabase)
		ldb.Close()
		os.RemoveAll(ldb.Path())
	}
Felix Lange's avatar
Felix Lange committed
535 536 537
}

func benchUpdate(b *testing.B, e binary.ByteOrder) *Trie {
Felix Lange's avatar
Felix Lange committed
538
	trie := newEmpty()
Felix Lange's avatar
Felix Lange committed
539 540 541 542 543 544 545 546 547
	k := make([]byte, 32)
	for i := 0; i < b.N; i++ {
		e.PutUint64(k, uint64(i))
		trie.Update(k, k)
	}
	return trie
}

func benchHash(b *testing.B, e binary.ByteOrder) {
Felix Lange's avatar
Felix Lange committed
548
	trie := newEmpty()
Felix Lange's avatar
Felix Lange committed
549 550 551 552 553 554 555 556 557 558 559 560
	k := make([]byte, 32)
	for i := 0; i < benchElemCount; i++ {
		e.PutUint64(k, uint64(i))
		trie.Update(k, k)
	}

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		trie.Hash()
	}
}

Felix Lange's avatar
Felix Lange committed
561
func tempDB() (string, Database) {
Felix Lange's avatar
Felix Lange committed
562 563 564 565
	dir, err := ioutil.TempDir("", "trie-bench")
	if err != nil {
		panic(fmt.Sprintf("can't create temporary directory: %v", err))
	}
566
	db, err := ethdb.NewLDBDatabase(dir, 256, 0)
Felix Lange's avatar
Felix Lange committed
567 568 569 570 571
	if err != nil {
		panic(fmt.Sprintf("can't create temporary database: %v", err))
	}
	return dir, db
}
Felix Lange's avatar
Felix Lange committed
572 573 574 575 576 577 578 579 580 581 582 583

func getString(trie *Trie, k string) []byte {
	return trie.Get([]byte(k))
}

func updateString(trie *Trie, k, v string) {
	trie.Update([]byte(k), []byte(v))
}

func deleteString(trie *Trie, k string) {
	trie.Delete([]byte(k))
}