1// Copyright 2015 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// it under the terms of the GNU Lesser General Public License as published by 6// the Free Software Foundation, either version 3 of the License, or 7// (at your option) any later version. 8// 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// GNU Lesser General Public License for more details. 13// 14// 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 17package trie 18 19import ( 20 "bytes" 21 "testing" 22 23 "github.com/ethereum/go-ethereum/common" 24 "github.com/ethereum/go-ethereum/crypto" 25 "github.com/ethereum/go-ethereum/ethdb/memorydb" 26) 27 28// makeTestTrie create a sample test trie to test node-wise reconstruction. 29func makeTestTrie() (*Database, *SecureTrie, map[string][]byte) { 30 // Create an empty trie 31 triedb := NewDatabase(memorydb.New()) 32 trie, _ := NewSecure(common.Hash{}, triedb) 33 34 // Fill it with some arbitrary data 35 content := make(map[string][]byte) 36 for i := byte(0); i < 255; i++ { 37 // Map the same data under multiple keys 38 key, val := common.LeftPadBytes([]byte{1, i}, 32), []byte{i} 39 content[string(key)] = val 40 trie.Update(key, val) 41 42 key, val = common.LeftPadBytes([]byte{2, i}, 32), []byte{i} 43 content[string(key)] = val 44 trie.Update(key, val) 45 46 // Add some other data to inflate the trie 47 for j := byte(3); j < 13; j++ { 48 key, val = common.LeftPadBytes([]byte{j, i}, 32), []byte{j, i} 49 content[string(key)] = val 50 trie.Update(key, val) 51 } 52 } 53 trie.Commit(nil) 54 55 // Return the generated trie 56 return triedb, trie, content 57} 58 59// checkTrieContents cross references a reconstructed trie with an expected data 60// content map. 61func checkTrieContents(t *testing.T, db *Database, root []byte, content map[string][]byte) { 62 // Check root availability and trie contents 63 trie, err := NewSecure(common.BytesToHash(root), db) 64 if err != nil { 65 t.Fatalf("failed to create trie at %x: %v", root, err) 66 } 67 if err := checkTrieConsistency(db, common.BytesToHash(root)); err != nil { 68 t.Fatalf("inconsistent trie at %x: %v", root, err) 69 } 70 for key, val := range content { 71 if have := trie.Get([]byte(key)); !bytes.Equal(have, val) { 72 t.Errorf("entry %x: content mismatch: have %x, want %x", key, have, val) 73 } 74 } 75} 76 77// checkTrieConsistency checks that all nodes in a trie are indeed present. 78func checkTrieConsistency(db *Database, root common.Hash) error { 79 // Create and iterate a trie rooted in a subnode 80 trie, err := NewSecure(root, db) 81 if err != nil { 82 return nil // Consider a non existent state consistent 83 } 84 it := trie.NodeIterator(nil) 85 for it.Next(true) { 86 } 87 return it.Error() 88} 89 90// Tests that an empty trie is not scheduled for syncing. 91func TestEmptySync(t *testing.T) { 92 dbA := NewDatabase(memorydb.New()) 93 dbB := NewDatabase(memorydb.New()) 94 emptyA, _ := New(common.Hash{}, dbA) 95 emptyB, _ := New(emptyRoot, dbB) 96 97 for i, trie := range []*Trie{emptyA, emptyB} { 98 sync := NewSync(trie.Hash(), memorydb.New(), nil) 99 if nodes, paths, codes := sync.Missing(1); len(nodes) != 0 || len(paths) != 0 || len(codes) != 0 { 100 t.Errorf("test %d: content requested for empty trie: %v, %v, %v", i, nodes, paths, codes) 101 } 102 } 103} 104 105// Tests that given a root hash, a trie can sync iteratively on a single thread, 106// requesting retrieval tasks and returning all of them in one go. 107func TestIterativeSyncIndividual(t *testing.T) { testIterativeSync(t, 1, false) } 108func TestIterativeSyncBatched(t *testing.T) { testIterativeSync(t, 100, false) } 109func TestIterativeSyncIndividualByPath(t *testing.T) { testIterativeSync(t, 1, true) } 110func TestIterativeSyncBatchedByPath(t *testing.T) { testIterativeSync(t, 100, true) } 111 112func testIterativeSync(t *testing.T, count int, bypath bool) { 113 // Create a random trie to copy 114 srcDb, srcTrie, srcData := makeTestTrie() 115 116 // Create a destination trie and sync with the scheduler 117 diskdb := memorydb.New() 118 triedb := NewDatabase(diskdb) 119 sched := NewSync(srcTrie.Hash(), diskdb, nil) 120 121 nodes, paths, codes := sched.Missing(count) 122 var ( 123 hashQueue []common.Hash 124 pathQueue []SyncPath 125 ) 126 if !bypath { 127 hashQueue = append(append(hashQueue[:0], nodes...), codes...) 128 } else { 129 hashQueue = append(hashQueue[:0], codes...) 130 pathQueue = append(pathQueue[:0], paths...) 131 } 132 for len(hashQueue)+len(pathQueue) > 0 { 133 results := make([]SyncResult, len(hashQueue)+len(pathQueue)) 134 for i, hash := range hashQueue { 135 data, err := srcDb.Node(hash) 136 if err != nil { 137 t.Fatalf("failed to retrieve node data for hash %x: %v", hash, err) 138 } 139 results[i] = SyncResult{hash, data} 140 } 141 for i, path := range pathQueue { 142 data, _, err := srcTrie.TryGetNode(path[0]) 143 if err != nil { 144 t.Fatalf("failed to retrieve node data for path %x: %v", path, err) 145 } 146 results[len(hashQueue)+i] = SyncResult{crypto.Keccak256Hash(data), data} 147 } 148 for _, result := range results { 149 if err := sched.Process(result); err != nil { 150 t.Fatalf("failed to process result %v", err) 151 } 152 } 153 batch := diskdb.NewBatch() 154 if err := sched.Commit(batch); err != nil { 155 t.Fatalf("failed to commit data: %v", err) 156 } 157 batch.Write() 158 159 nodes, paths, codes = sched.Missing(count) 160 if !bypath { 161 hashQueue = append(append(hashQueue[:0], nodes...), codes...) 162 } else { 163 hashQueue = append(hashQueue[:0], codes...) 164 pathQueue = append(pathQueue[:0], paths...) 165 } 166 } 167 // Cross check that the two tries are in sync 168 checkTrieContents(t, triedb, srcTrie.Hash().Bytes(), srcData) 169} 170 171// Tests that the trie scheduler can correctly reconstruct the state even if only 172// partial results are returned, and the others sent only later. 173func TestIterativeDelayedSync(t *testing.T) { 174 // Create a random trie to copy 175 srcDb, srcTrie, srcData := makeTestTrie() 176 177 // Create a destination trie and sync with the scheduler 178 diskdb := memorydb.New() 179 triedb := NewDatabase(diskdb) 180 sched := NewSync(srcTrie.Hash(), diskdb, nil) 181 182 nodes, _, codes := sched.Missing(10000) 183 queue := append(append([]common.Hash{}, nodes...), codes...) 184 185 for len(queue) > 0 { 186 // Sync only half of the scheduled nodes 187 results := make([]SyncResult, len(queue)/2+1) 188 for i, hash := range queue[:len(results)] { 189 data, err := srcDb.Node(hash) 190 if err != nil { 191 t.Fatalf("failed to retrieve node data for %x: %v", hash, err) 192 } 193 results[i] = SyncResult{hash, data} 194 } 195 for _, result := range results { 196 if err := sched.Process(result); err != nil { 197 t.Fatalf("failed to process result %v", err) 198 } 199 } 200 batch := diskdb.NewBatch() 201 if err := sched.Commit(batch); err != nil { 202 t.Fatalf("failed to commit data: %v", err) 203 } 204 batch.Write() 205 206 nodes, _, codes = sched.Missing(10000) 207 queue = append(append(queue[len(results):], nodes...), codes...) 208 } 209 // Cross check that the two tries are in sync 210 checkTrieContents(t, triedb, srcTrie.Hash().Bytes(), srcData) 211} 212 213// Tests that given a root hash, a trie can sync iteratively on a single thread, 214// requesting retrieval tasks and returning all of them in one go, however in a 215// random order. 216func TestIterativeRandomSyncIndividual(t *testing.T) { testIterativeRandomSync(t, 1) } 217func TestIterativeRandomSyncBatched(t *testing.T) { testIterativeRandomSync(t, 100) } 218 219func testIterativeRandomSync(t *testing.T, count int) { 220 // Create a random trie to copy 221 srcDb, srcTrie, srcData := makeTestTrie() 222 223 // Create a destination trie and sync with the scheduler 224 diskdb := memorydb.New() 225 triedb := NewDatabase(diskdb) 226 sched := NewSync(srcTrie.Hash(), diskdb, nil) 227 228 queue := make(map[common.Hash]struct{}) 229 nodes, _, codes := sched.Missing(count) 230 for _, hash := range append(nodes, codes...) { 231 queue[hash] = struct{}{} 232 } 233 for len(queue) > 0 { 234 // Fetch all the queued nodes in a random order 235 results := make([]SyncResult, 0, len(queue)) 236 for hash := range queue { 237 data, err := srcDb.Node(hash) 238 if err != nil { 239 t.Fatalf("failed to retrieve node data for %x: %v", hash, err) 240 } 241 results = append(results, SyncResult{hash, data}) 242 } 243 // Feed the retrieved results back and queue new tasks 244 for _, result := range results { 245 if err := sched.Process(result); err != nil { 246 t.Fatalf("failed to process result %v", err) 247 } 248 } 249 batch := diskdb.NewBatch() 250 if err := sched.Commit(batch); err != nil { 251 t.Fatalf("failed to commit data: %v", err) 252 } 253 batch.Write() 254 255 queue = make(map[common.Hash]struct{}) 256 nodes, _, codes = sched.Missing(count) 257 for _, hash := range append(nodes, codes...) { 258 queue[hash] = struct{}{} 259 } 260 } 261 // Cross check that the two tries are in sync 262 checkTrieContents(t, triedb, srcTrie.Hash().Bytes(), srcData) 263} 264 265// Tests that the trie scheduler can correctly reconstruct the state even if only 266// partial results are returned (Even those randomly), others sent only later. 267func TestIterativeRandomDelayedSync(t *testing.T) { 268 // Create a random trie to copy 269 srcDb, srcTrie, srcData := makeTestTrie() 270 271 // Create a destination trie and sync with the scheduler 272 diskdb := memorydb.New() 273 triedb := NewDatabase(diskdb) 274 sched := NewSync(srcTrie.Hash(), diskdb, nil) 275 276 queue := make(map[common.Hash]struct{}) 277 nodes, _, codes := sched.Missing(10000) 278 for _, hash := range append(nodes, codes...) { 279 queue[hash] = struct{}{} 280 } 281 for len(queue) > 0 { 282 // Sync only half of the scheduled nodes, even those in random order 283 results := make([]SyncResult, 0, len(queue)/2+1) 284 for hash := range queue { 285 data, err := srcDb.Node(hash) 286 if err != nil { 287 t.Fatalf("failed to retrieve node data for %x: %v", hash, err) 288 } 289 results = append(results, SyncResult{hash, data}) 290 291 if len(results) >= cap(results) { 292 break 293 } 294 } 295 // Feed the retrieved results back and queue new tasks 296 for _, result := range results { 297 if err := sched.Process(result); err != nil { 298 t.Fatalf("failed to process result %v", err) 299 } 300 } 301 batch := diskdb.NewBatch() 302 if err := sched.Commit(batch); err != nil { 303 t.Fatalf("failed to commit data: %v", err) 304 } 305 batch.Write() 306 for _, result := range results { 307 delete(queue, result.Hash) 308 } 309 nodes, _, codes = sched.Missing(10000) 310 for _, hash := range append(nodes, codes...) { 311 queue[hash] = struct{}{} 312 } 313 } 314 // Cross check that the two tries are in sync 315 checkTrieContents(t, triedb, srcTrie.Hash().Bytes(), srcData) 316} 317 318// Tests that a trie sync will not request nodes multiple times, even if they 319// have such references. 320func TestDuplicateAvoidanceSync(t *testing.T) { 321 // Create a random trie to copy 322 srcDb, srcTrie, srcData := makeTestTrie() 323 324 // Create a destination trie and sync with the scheduler 325 diskdb := memorydb.New() 326 triedb := NewDatabase(diskdb) 327 sched := NewSync(srcTrie.Hash(), diskdb, nil) 328 329 nodes, _, codes := sched.Missing(0) 330 queue := append(append([]common.Hash{}, nodes...), codes...) 331 requested := make(map[common.Hash]struct{}) 332 333 for len(queue) > 0 { 334 results := make([]SyncResult, len(queue)) 335 for i, hash := range queue { 336 data, err := srcDb.Node(hash) 337 if err != nil { 338 t.Fatalf("failed to retrieve node data for %x: %v", hash, err) 339 } 340 if _, ok := requested[hash]; ok { 341 t.Errorf("hash %x already requested once", hash) 342 } 343 requested[hash] = struct{}{} 344 345 results[i] = SyncResult{hash, data} 346 } 347 for _, result := range results { 348 if err := sched.Process(result); err != nil { 349 t.Fatalf("failed to process result %v", err) 350 } 351 } 352 batch := diskdb.NewBatch() 353 if err := sched.Commit(batch); err != nil { 354 t.Fatalf("failed to commit data: %v", err) 355 } 356 batch.Write() 357 358 nodes, _, codes = sched.Missing(0) 359 queue = append(append(queue[:0], nodes...), codes...) 360 } 361 // Cross check that the two tries are in sync 362 checkTrieContents(t, triedb, srcTrie.Hash().Bytes(), srcData) 363} 364 365// Tests that at any point in time during a sync, only complete sub-tries are in 366// the database. 367func TestIncompleteSync(t *testing.T) { 368 // Create a random trie to copy 369 srcDb, srcTrie, _ := makeTestTrie() 370 371 // Create a destination trie and sync with the scheduler 372 diskdb := memorydb.New() 373 triedb := NewDatabase(diskdb) 374 sched := NewSync(srcTrie.Hash(), diskdb, nil) 375 376 var added []common.Hash 377 378 nodes, _, codes := sched.Missing(1) 379 queue := append(append([]common.Hash{}, nodes...), codes...) 380 for len(queue) > 0 { 381 // Fetch a batch of trie nodes 382 results := make([]SyncResult, len(queue)) 383 for i, hash := range queue { 384 data, err := srcDb.Node(hash) 385 if err != nil { 386 t.Fatalf("failed to retrieve node data for %x: %v", hash, err) 387 } 388 results[i] = SyncResult{hash, data} 389 } 390 // Process each of the trie nodes 391 for _, result := range results { 392 if err := sched.Process(result); err != nil { 393 t.Fatalf("failed to process result %v", err) 394 } 395 } 396 batch := diskdb.NewBatch() 397 if err := sched.Commit(batch); err != nil { 398 t.Fatalf("failed to commit data: %v", err) 399 } 400 batch.Write() 401 for _, result := range results { 402 added = append(added, result.Hash) 403 // Check that all known sub-tries in the synced trie are complete 404 if err := checkTrieConsistency(triedb, result.Hash); err != nil { 405 t.Fatalf("trie inconsistent: %v", err) 406 } 407 } 408 // Fetch the next batch to retrieve 409 nodes, _, codes = sched.Missing(1) 410 queue = append(append(queue[:0], nodes...), codes...) 411 } 412 // Sanity check that removing any node from the database is detected 413 for _, node := range added[1:] { 414 key := node.Bytes() 415 value, _ := diskdb.Get(key) 416 417 diskdb.Delete(key) 418 if err := checkTrieConsistency(triedb, added[0]); err == nil { 419 t.Fatalf("trie inconsistency not caught, missing: %x", key) 420 } 421 diskdb.Put(key, value) 422 } 423} 424 425// Tests that trie nodes get scheduled lexicographically when having the same 426// depth. 427func TestSyncOrdering(t *testing.T) { 428 // Create a random trie to copy 429 srcDb, srcTrie, srcData := makeTestTrie() 430 431 // Create a destination trie and sync with the scheduler, tracking the requests 432 diskdb := memorydb.New() 433 triedb := NewDatabase(diskdb) 434 sched := NewSync(srcTrie.Hash(), diskdb, nil) 435 436 nodes, paths, _ := sched.Missing(1) 437 queue := append([]common.Hash{}, nodes...) 438 reqs := append([]SyncPath{}, paths...) 439 440 for len(queue) > 0 { 441 results := make([]SyncResult, len(queue)) 442 for i, hash := range queue { 443 data, err := srcDb.Node(hash) 444 if err != nil { 445 t.Fatalf("failed to retrieve node data for %x: %v", hash, err) 446 } 447 results[i] = SyncResult{hash, data} 448 } 449 for _, result := range results { 450 if err := sched.Process(result); err != nil { 451 t.Fatalf("failed to process result %v", err) 452 } 453 } 454 batch := diskdb.NewBatch() 455 if err := sched.Commit(batch); err != nil { 456 t.Fatalf("failed to commit data: %v", err) 457 } 458 batch.Write() 459 460 nodes, paths, _ = sched.Missing(1) 461 queue = append(queue[:0], nodes...) 462 reqs = append(reqs, paths...) 463 } 464 // Cross check that the two tries are in sync 465 checkTrieContents(t, triedb, srcTrie.Hash().Bytes(), srcData) 466 467 // Check that the trie nodes have been requested path-ordered 468 for i := 0; i < len(reqs)-1; i++ { 469 if len(reqs[i]) > 1 || len(reqs[i+1]) > 1 { 470 // In the case of the trie tests, there's no storage so the tuples 471 // must always be single items. 2-tuples should be tested in state. 472 t.Errorf("Invalid request tuples: len(%v) or len(%v) > 1", reqs[i], reqs[i+1]) 473 } 474 if bytes.Compare(compactToHex(reqs[i][0]), compactToHex(reqs[i+1][0])) > 0 { 475 t.Errorf("Invalid request order: %v before %v", compactToHex(reqs[i][0]), compactToHex(reqs[i+1][0])) 476 } 477 } 478} 479