aboutsummaryrefslogtreecommitdiffstats
path: root/trie
Commit message (Collapse)AuthorAgeFilesLines
* core/state: access trie through Database interface, track errors (#14589)Felix Lange2017-06-272-2/+8
| | | | | | | | | With this commit, core/state's access to the underlying key/value database is mediated through an interface. Database errors are tracked in StateDB and returned by CommitTo or the new Error method. Motivation for this change: We can remove the light client's duplicated copy of core/state. The light client now supports node iteration, so tracing and storage enumeration can work with the light client (not implemented in this commit).
* eth/downloader: separate state sync from queue (#14460)Felix Lange2017-06-222-18/+86
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * eth/downloader: separate state sync from queue Scheduling of state node downloads hogged the downloader queue lock when new requests were scheduled. This caused timeouts for other requests. With this change, state sync is fully independent of all other downloads and doesn't involve the queue at all. State sync is started and checked on in processContent. This is slightly awkward because processContent doesn't have a select loop. Instead, the queue is closed by an auxiliary goroutine when state sync fails. We tried several alternatives to this but settled on the current approach because it's the least amount of change overall. Handling of the pivot block has changed slightly: the queue previously prevented import of pivot block receipts before the state of the pivot block was available. In this commit, the receipt will be imported before the state. This causes an annoyance where the pivot block is committed as fast block head even when state downloads fail. Stay tuned for more updates in this area ;) * eth/downloader: remove cancelTimeout channel * eth/downloader: retry state requests on timeout * eth/downloader: improve comment * eth/downloader: mark peers idle when state sync is done * eth/downloader: move pivot block splitting to processContent This change also ensures that pivot block receipts aren't imported before the pivot block itself. * eth/downloader: limit state node retries * eth/downloader: improve state node error handling and retry check * eth/downloader: remove maxStateNodeRetries It fails the sync too much. * eth/downloader: remove last use of cancelCh in statesync.go Fixes TestDeliverHeadersHang*Fast and (hopefully) the weird cancellation behaviour at the end of fast sync. * eth/downloader: fix leak in runStateSync * eth/downloader: don't run processFullSyncContent in LightSync mode * eth/downloader: improve comments * eth/downloader: fix vet, megacheck * eth/downloader: remove unrequested tasks anyway * eth/downloader, trie: various polishes around duplicate items This commit explicitly tracks duplicate and unexpected state delieveries done against a trie Sync structure, also adding there to import info logs. The commit moves the db batch used to commit trie changes one level deeper so its flushed after every node insertion. This is needed to avoid a lot of duplicate retrievals caused by inconsistencies between Sync internals and database. A better approach is to track not-yet-written states in trie.Sync and flush on commit, but I'm focuing on correctness first now. The commit fixes a regression around pivot block fail count. The counter previously was reset to 1 if and only if a sync cycle progressed (inserted at least 1 entry to the database). The current code reset it already if a node was delivered, which is not stong enough, because unless it ends up written to disk, an attacker can just loop and attack ad infinitum. The commit also fixes a regression around state deliveries and timeouts. The old downloader tracked if a delivery is stale (none of the deliveries were requestedt), in which case it didn't mark the node idle and did not send further requests, since it signals a past timeout. The current code did mark it idle even on stale deliveries, which eventually caused two requests to be in flight at the same time, making the deliveries always stale and mass duplicating retrievals between multiple peers. * eth/downloader: fix state request leak This commit fixes the hang seen sometimes while doing the state sync. The cause of the hang was a rare combination of events: request state data from peer, peer drops and reconnects almost immediately. This caused a new download task to be assigned to the peer, overwriting the old one still waiting for a timeout, which in turned leaked the requests out, never to be retried. The fix is to ensure that a task assignment moves any pending one back into the retry queue. The commit also fixes a regression with peer dropping due to stalls. The current code considered a peer stalling if they timed out delivering 1 item. However, the downloader never requests only one, the minimum is 2 (attempt to fine tune estimated latency/bandwidth). The fix is simply to drop if a timeout is detected at 2 items. Apart from the above bugfixes, the commit contains some code polishes I made while debugging the hang. * core, eth, trie: support batched trie sync db writes * trie: rename SyncMemCache to syncMemBatch
* trie: more node iterator improvements (#14615)Felix Lange2017-06-216-165/+288
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * ethdb: remove Set Set deadlocks immediately and isn't part of the Database interface. * trie: add Err to Iterator This is useful for testing because the underlying NodeIterator doesn't need to be kept in a separate variable just to get the error. * trie: add LeafKey to iterator, panic when not at leaf LeafKey is useful for callers that can't interpret Path. * trie: retry failed seek/peek in iterator Next Instead of failing iteration irrecoverably, make it so Next retries the pending seek or peek every time. Smaller changes in this commit make this easier to test: * The iterator previously returned from Next on encountering a hash node. This caused it to visit the same path twice. * Path returned nibbles with terminator symbol for valueNode attached to fullNode, but removed it for valueNode attached to shortNode. Now the terminator is always present. This makes Path unique to each node and simplifies Leaf. * trie: add Path to MissingNodeError The light client trie iterator needs to know the path of the node that's missing so it can retrieve a proof for it. NodeIterator.Path is not sufficient because it is updated when the node is resolved and actually visited by the iterator. Also remove unused fields. They were added a long time ago before we knew which fields would be needed for the light client.
* rlp, trie, contracts, compression, consensus: improve comments (#14580)S. Matthew English2017-06-124-8/+8
|
* trie: add start key to NodeIterator constructorsFelix Lange2017-04-256-68/+141
| | | | | | | | | The 'step' method is split into two parts, 'peek' and 'push'. peek returns the next state but doesn't make it current. The end of iteration was previously tracked by setting 'trie' to nil. End of iteration is now tracked using the 'iteratorEnd' error, which is slightly cleaner and requires less code.
* trie: clean up iterator constructorsFelix Lange2017-04-256-27/+16
| | | | | | | Make it so each iterator has exactly one public constructor: - NodeIterators can be created through a method. - Iterators can be created through NewIterator on any NodeIterator.
* trie: rework and document key encodingFelix Lange2017-04-257-159/+121
| | | | | 'encode' and 'decode' are meaningless because the code deals with three encodings. Document the encodings and give a name to each one.
* trie: remove Key in MissingNodeErrorFelix Lange2017-04-182-6/+0
| | | | | | The key was constructed from nibbles, which isn't possible for all nodes. Remove the only use of Key in LightTrie by always retrying with the original key that was looked up.
* trie: implement unionIterator (#14312)Nick Johnson2017-04-132-36/+199
|
* core, consensus: pluggable consensus engines (#3817)Péter Szilágyi2017-04-051-0/+1
| | | | | This commit adds pluggable consensus engines to go-ethereum. In short, it introduces a generic consensus interface, and refactors the entire codebase to use this interface.
* trie, whisper/whisperv5: use math/rand Read functionFelix Lange2017-03-231-17/+1
|
* all: blidly swap out glog to our log15, logs need reworkPéter Szilágyi2017-02-233-21/+18
|
* trie: add difference iterator (#3637)Nick Johnson2017-02-234-113/+311
| | | | | This PR implements a differenceIterator, which allows iterating over trie nodes that exist in one trie but not in another. This is a prerequisite for most GC strategies, in order to find obsolete nodes.
* all: fix ineffectual assignments and remove uses of crypto.Sha3Felix Lange2017-01-091-2/+4
| | | | | go get github.com/gordonklaus/ineffassign ineffassign .
* all: fix spelling errorsPéter Szilágyi2017-01-071-1/+1
|
* all: fix issues reported by honnef.co/go/simple/cmd/gosimpleFelix Lange2017-01-071-1/+1
|
* all: gofmt -w -sFelix Lange2017-01-063-4/+4
|
* trie: remove dependency on ethdbFelix Lange2017-01-063-23/+19
| | | | This removes the core/types -> leveldb dependency.
* core/state, eth/downloader, trie: reset fast-failure on progressPéter Szilágyi2016-10-312-12/+18
|
* trie: while fast syncing, don't keep trie nodes in memory (#3186)Péter Szilágyi2016-10-211-19/+13
|
* cmd/geth, trie: report on trie cache unloads, also add debug logPéter Szilágyi2016-10-191-0/+7
|
* trie: add metric to track cache unloading (#3175)Felix Lange2016-10-192-1/+5
|
* trie: make the cache miss counter a real metricFelix Lange2016-10-191-7/+5
|
* Merge pull request #3153 from fjl/trie-unload-fixJeffrey Wilcke2016-10-196-66/+126
|\ | | | | trie: improve cache unloading mechanism
| * trie: ensure dirty flag is unset for embedded child nodesFelix Lange2016-10-182-32/+42
| | | | | | | | This was caught by the new invariant check.
| * trie: ensure resolved nodes stay loadedFelix Lange2016-10-186-43/+95
| | | | | | | | | | | | | | | | Commit 40cdcf1183 broke the optimisation which kept nodes resolved during Get in the trie. The decoder assigned cache generation 0 unconditionally, causing resolved nodes to get flushed on Commit. This commit fixes it and adds two tests.
| * trie: avoid loading the root node twiceFelix Lange2016-10-181-6/+4
| | | | | | | | | | New checks whether the root node is present by loading it from the database. Keep the node around instead of discarding it.
* | cmd/geth, trie: track and report trie cache missesPéter Szilágyi2016-10-191-0/+14
|/
* trie: fix regression that linked all downloaded nodes togetherFelix Lange2016-10-151-0/+2
| | | | | | | The trie sync code links subtries using pointers into node structs. Since commit 40cdcf1183 nodes are no longer copied when unpacking from an interface value, causing all nodes to get linked up as the sync progresses. Fix it by breaking the pointer chain with an explicit copy.
* trie, core/state: improve memory usage and performance (#3135)Felix Lange2016-10-1510-131/+235
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * trie: store nodes as pointers This avoids memory copies when unwrapping node interface values. name old time/op new time/op delta Get 388ns ± 8% 215ns ± 2% -44.56% (p=0.000 n=15+15) GetDB 363ns ± 3% 202ns ± 2% -44.21% (p=0.000 n=15+15) UpdateBE 1.57µs ± 2% 1.29µs ± 3% -17.80% (p=0.000 n=13+15) UpdateLE 1.92µs ± 2% 1.61µs ± 2% -16.25% (p=0.000 n=14+14) HashBE 2.16µs ± 6% 2.18µs ± 6% ~ (p=0.436 n=15+15) HashLE 7.43µs ± 3% 7.21µs ± 3% -2.96% (p=0.000 n=15+13) * trie: close temporary databases in GetDB benchmark * trie: don't keep []byte from DB load around Nodes decoded from a DB load kept hashes and values as sub-slices of the DB value. This can be a problem because loading from leveldb often returns []byte with a cap that's larger than necessary, increasing memory usage. * trie: unload old cached nodes * trie, core/state: use cache unloading for account trie * trie: use explicit private flags (fixes Go 1.5 reflection issue). * trie: fixup cachegen overflow at request of nick * core/state: rename journal size constant
* trie: fix delete bug for values contained in fullNodeFelix Lange2016-09-302-35/+127
| | | | | | | | | Delete crashed if a fullNode contained a valueNode directly. This bug is very unlikely to occur with SecureTrie, but can happen with regular tries. This commit also introduces a randomised test which triggers all trie operations, which should prevent such bugs in the future. Credit for finding this bug goes to Github user @rjl493456442.
* trie: remove dependency on package cryptoFelix Lange2016-09-301-3/+6
| | | | | Package crypto needs cgo, which is inconvenient for some build configurations.
* core, eth, trie: reuse trie journals in all our codePéter Szilágyi2016-09-282-10/+94
|
* core, trie: replace state caches with trie journalFelix Lange2016-09-289-586/+350
|
* Merge pull request #2627 from karalabe/concurrent-head-syncPéter Szilágyi2016-05-311-1/+6
|\ | | | | eth/downloader, trie: pull head state concurrently with chain
| * eth/downloader, trie: pull head state concurrently with chainPéter Szilágyi2016-05-271-1/+6
| |
* | core, core/state, trie: enterprise hand-tuned multi-level cachingPéter Szilágyi2016-05-267-132/+216
|/
* all: fix go vet warningsFelix Lange2016-04-152-2/+2
|
* all: update license informationFelix Lange2016-04-153-1/+33
|
* cmd, eth, ethdb, node: prioritise chaindata for resources, bump cachePéter Szilágyi2016-03-091-1/+1
|
* Merge pull request #2242 from jimenezrick/upstream-cryptoJeffrey Wilcke2016-02-242-2/+2
|\ | | | | Closes #2241: Use Keccak-256 from golang.org/x/crypto/sha3 and mention explicitly
| * all: Rename crypto.Sha3{,Hash}() to crypto.Keccak256{,Hash}()Ricardo Catalinas Jiménez2016-02-222-2/+2
| | | | | | | | As we aren't really using the standarized SHA-3
* | core/state, trie: switch iterator panics to error fieldsPéter Szilágyi2016-02-162-19/+25
| |
* | core/state, trie: node iterator reports parent hashes tooPéter Szilágyi2016-02-161-8/+14
| |
* | core/state, trie: surface iterator entry hashesPéter Szilágyi2016-02-163-13/+47
| |
* | core/state, trie: add node iterator, test state/trie sync consistencyPéter Szilágyi2016-02-162-8/+214
|/
* core/state, ethdb, trie: test intermediate secure key leak, fix memdb bugPéter Szilágyi2016-01-201-2/+4
|
* core/state, trie: don't leak database writes before commitPéter Szilágyi2016-01-201-5/+44
|
* light: implemented odr-capable trie and state structureszsfelfoldi2015-12-175-15/+59
|
* trie: added error handlingzsfelfoldi2015-12-017-68/+343
| | | | Created alternate versions of Trie and SecureTrie functions that can return a MissingNodeError (used by ODR services)
* core, eth, trie: fix data races and merge/review issuesPéter Szilágyi2015-10-211-1/+1
|
* eth/downloader: concurrent receipt and state processingPéter Szilágyi2015-10-192-8/+65
|
* core, eth, trie: direct state trie synchronizationPéter Szilágyi2015-10-192-0/+490
|
* trie: add merkle proof functionsFelix Lange2015-09-232-0/+261
|
* core, trie: new trieFelix Lange2015-09-2316-931/+1075
|
* trie: improve benchmarksFelix Lange2015-09-231-34/+72
|
* eth, trie: removed key prefixing from state entries & merge db fixJeffrey Wilcke2015-08-142-6/+0
| | | | | | | | | Fixed database merge strategy to use the correct database. Due to a copy paste fail when doing type evaluation the same database was being iterated (chain), all others were ignored. Removed state prefixing because {H(code): code} is stored in the same database as the rest of the state.
* core, eth, trie, xeth: merged state, chain, extra databases in oneJeffrey Wilcke2015-08-082-2/+6
|
* trie: run codec tests, add benchmarks, fasterEthan Buchman2015-08-072-24/+70
|
* faster hex-prefix codec and string -> []byteEthan Buchman2015-08-065-39/+30
|
* Merge pull request #1515 from fjl/license-fixesJeffrey Wilcke2015-07-2814-14/+14
|\ | | | | all: fix license headers one more time
| * all: fix license headers one more timeFelix Lange2015-07-2414-14/+14
| | | | | | | | I forgot to update one instance of "go-ethereum" in commit 3f047be5a.
* | ethdb, trie: removed RLE compressionJeffrey Wilcke2015-07-231-2/+2
|/
* all: update license headers to distiguish GPL/LGPLFelix Lange2015-07-2314-56/+56
| | | | | All code outside of cmd/ is licensed as LGPL. The headers now reflect this by calling the whole work "the go-ethereum library".
* all: add some godoc synopsis commentsFelix Lange2015-07-071-0/+1
|
* all: update license informationFelix Lange2015-07-0714-0/+224
|
* trie: removed shallow copies (thanks to @fjl)Jeffrey Wilcke2015-07-041-1/+1
|
* trie: dirty trackingJeffrey Wilcke2015-07-047-28/+73
|
* trie: Implemented a batch write approach for flushingobscuren2015-06-301-8/+18
|
* trie: fixed testsobscuren2015-06-211-1/+1
|
* core, ethdb, trie: validate database errorsobscuren2015-06-211-2/+6
|
* Secure trie shakey / key matchingobscuren2015-03-241-1/+10
|
* fixed testsobscuren2015-03-191-2/+7
|
* Fixed mkdnode & added some testsobscuren2015-03-192-6/+17
|
* Moved ethutil => commonobscuren2015-03-165-25/+25
|
* Merge branch 'develop' into poc-9obscuren2015-03-062-8/+22
|\
| * Start at 0obscuren2015-03-061-2/+1
| |
| * Fixed iterator bug which skips the 0x000...000 key=2015-03-051-7/+21
| |
* | Trie => SecureTrieobscuren2015-03-031-0/+4
| |
* | Delet => Deleteobscuren2015-03-032-1/+33
| |
* | Secure trieobscuren2015-03-012-1/+32
|/
* Fixed iteratorobscuren2015-02-082-2/+40
|
* Fixed a copy issue in the trie which could cause a consensus failureobscuren2015-02-037-19/+53
|
* debug err removedobscuren2015-01-301-1/+1
|
* default values removedobscuren2015-01-302-4/+4
|
* Moved ptrie => trie. Removed old trieobscuren2015-01-0811-909/+692
|
* Refactored ethutil.Config.Db outobscuren2015-01-073-62/+9
|
* Fixed tests for 'types'obscuren2014-11-191-0/+2
|
* Merge branch 'tests' into poc8obscuren2014-11-193-211/+154
|\
| * update imports order per goimportsTaylor Gerring2014-11-162-2/+4
| |
| * Merge branch 'develop' of https://github.com/tgerring/go-ethereum into testsTaylor Gerring2014-11-151-7/+4
| |\ | | | | | | | | | | | | | | | Conflicts: p2p/messenger_test.go trie/trie_test.go
| | * convert trie encoding tests to checkerTaylor Gerring2014-11-131-38/+29
| | |
| | * Convert trie tests to gocheckTaylor Gerring2014-11-132-164/+119
| | |
| * | Merge branch 'develop' of https://github.com/tgerring/go-ethereumTaylor Gerring2014-11-153-204/+148
| | |
* | | j => iobscuren2014-11-181-1/+0
| | |
* | | added output testobscuren2014-11-181-1/+2
| | |
* | | Added some comparison tests for the new ptrieobscuren2014-11-182-1/+62
|/ /
* / Transaction execution fixesobscuren2014-11-122-14/+32
|/
* Added storage root to dumpobscuren2014-11-041-1/+1
|
* ethtrie => trieobscuren2014-10-316-0/+1394