go-ethereum
go-ethereum copied to clipboard
ethereum
cmd, core, eth, les, light: track deleted nodes
This PR ports a few changes from PBSS PR, mainly includes:
- track deleted trie nodes
- track previous value of nodes
- add state root for initializing trie
So the trie now takes stateRoot common.Hash, owner common.Hash, root common.Hash -- three hashes. I think we need to document the semantics of these three, I find it pretty difficult to know what should be used when and how, and what (if any) constraints must be met.
In one place, for example:
func getAccount(triedb *trie.Database, root, hash common.Hash) (types.StateAccount, error) {
trie, err := trie.New(root, common.Hash{}, root, triedb)
You invoke stateRoot=root, owner=nil, root=root. That, to me, looks pretty strange (because I don't quite grokk the semantics here).
@holiman yep, will try to make it a bit cleaner.
Essentially, we only need stateRoot for constructing account trie, and need stateRoot + owner + root for storage trie. I am not sure if it's a good idea to separate them out.
Probably too early to check in, but this can be run locally
[user@work trie]$ go test . -fuzz TrieOpera
diff --git a/trie/trie_test.go b/trie/trie_test.go
index 972a4845ad..3433f8ee1e 100644
--- a/trie/trie_test.go
+++ b/trie/trie_test.go
@@ -356,7 +356,7 @@ func TestRandomCases(t *testing.T) {
{op: 1, key: common.Hex2Bytes("980c393656413a15c8da01978ed9f89feb80b502f58f2d640e3a2f5f7a99a7018f1b573befd92053ac6f78fca4a87268"), value: common.Hex2Bytes("")}, // step 24
{op: 1, key: common.Hex2Bytes("fd"), value: common.Hex2Bytes("")}, // step 25
}
- runRandTest(rt)
+ runRandTestSteps(rt)
}
// randTest performs random trie operations.
@@ -411,7 +411,137 @@ func (randTest) Generate(r *rand.Rand, size int) reflect.Value {
return reflect.ValueOf(steps)
}
-func runRandTest(rt randTest) bool {
+type dataSource struct {
+ input []byte
+ reader *bytes.Reader
+}
+
+func newDataSource(input []byte) *dataSource {
+ return &dataSource{
+ input, bytes.NewReader(input),
+ }
+}
+func (ds *dataSource) readByte() byte {
+ if b, err := ds.reader.ReadByte(); err != nil {
+ return 0
+ } else {
+ return b
+ }
+}
+func (ds *dataSource) Read(buf []byte) (int, error) {
+ return ds.reader.Read(buf)
+}
+func (ds *dataSource) Ended() bool {
+ return ds.reader.Len() == 0
+}
+
+func FuzzTrieOperations(f *testing.F) {
+
+ f.Fuzz(func(t *testing.T, data []byte) {
+ r := newDataSource(data)
+ gen := &randomStepsGenerator{
+ source: r,
+ }
+ if !runRandTest(gen) {
+ t.Fatal(gen.getError())
+ //panic(gen.getError())
+ }
+ })
+
+}
+
+// randomSteps is the interface through which we can provide steps for fuzzing.
+type randomSteps interface {
+ setError(int, error)
+ next() (bool, int, randTestStep)
+ hasError(int) bool
+ getError() error
+}
+
+// randomStepsList implements randomSteps using a pre-generated list of steps.
+type randomStepsList struct {
+ index int
+ rt []randTestStep
+}
+
+func (l *randomStepsList) setError(i int, err error) {
+ l.rt[i].err = err
+}
+func (l *randomStepsList) hasError(i int) bool {
+ return l.rt[i].err != nil
+}
+
+func (l *randomStepsList) getError() error {
+ for _, step := range l.rt {
+ if step.err != nil {
+ return step.err
+ }
+ }
+ return nil
+}
+
+func (l *randomStepsList) next() (bool, int, randTestStep) {
+ if idx := l.index; idx < len(l.rt) {
+ l.index++
+ return true, idx, l.rt[idx]
+ }
+ return false, 0, randTestStep{}
+}
+
+func runRandTestSteps(rt randTest) bool {
+ return runRandTest(&randomStepsList{0, rt})
+}
+
+// randomStepsGenerator implements randomSteps using on-the-fly generated steps.
+type randomStepsGenerator struct {
+ source *dataSource
+ index int
+ allKeys [][]byte
+ err error
+}
+
+func (gen *randomStepsGenerator) setError(i int, err error) {
+ gen.err = fmt.Errorf("step %d: %w", i, err)
+}
+func (gen *randomStepsGenerator) hasError(i int) bool {
+ return gen.err != nil
+}
+func (gen *randomStepsGenerator) getError() error {
+ return gen.err
+}
+
+func (gen *randomStepsGenerator) genKey() []byte {
+ if len(gen.allKeys) < 2 || gen.source.readByte() < 0x0f {
+ // new key
+ key := make([]byte, gen.source.readByte()%50)
+ gen.source.Read(key)
+ gen.allKeys = append(gen.allKeys, key)
+ return key
+ }
+ // use existing key
+ return gen.allKeys[int(gen.source.readByte())%len(gen.allKeys)]
+
+}
+
+func (gen *randomStepsGenerator) next() (bool, int, randTestStep) {
+ if gen.source.Ended() {
+ return false, 0, randTestStep{}
+ }
+ step := randTestStep{op: int(gen.source.readByte() % byte(opMax))}
+ i := gen.index
+ gen.index++
+ switch step.op {
+ case opUpdate:
+ step.key = gen.genKey()
+ step.value = make([]byte, 8)
+ binary.BigEndian.PutUint64(step.value, uint64(i))
+ case opGet, opDelete:
+ step.key = gen.genKey()
+ }
+ return true, i, step
+}
+
+func runRandTest(rt randomSteps) bool {
var (
triedb = NewDatabase(memorydb.New())
tr = NewEmpty(triedb)
@@ -420,9 +550,12 @@ func runRandTest(rt randTest) bool {
)
tr.tracer = newTracer()
- for i, step := range rt {
+ for {
+ ok, i, step := rt.next()
+ if !ok {
+ break
+ }
// fmt.Printf("{op: %d, key: common.Hex2Bytes(\"%x\"), value: common.Hex2Bytes(\"%x\")}, // step %d\n",
- // step.op, step.key, step.value, i)
switch step.op {
case opUpdate:
@@ -435,14 +568,14 @@ func runRandTest(rt randTest) bool {
v := tr.Get(step.key)
want := values[string(step.key)]
if string(v) != want {
- rt[i].err = fmt.Errorf("mismatch for key %#x, got %#x want %#x", step.key, v, want)
+ rt.setError(i, fmt.Errorf("mismatch for key %#x, got %#x want %#x", step.key, v, want))
}
case opHash:
tr.Hash()
case opCommit:
root, nodes, err := tr.Commit(true)
if err != nil {
- rt[i].err = err
+ rt.setError(i, err)
return false
}
// Validity the returned nodeset
@@ -451,15 +584,17 @@ func runRandTest(rt randTest) bool {
blob, _, _ := origTrie.TryGetNode(hexToCompact([]byte(path)))
got := node.prev
if !bytes.Equal(blob, got) {
- rt[i].err = fmt.Errorf("prevalue mismatch for 0x%x, got 0x%x want 0x%x", path, got, blob)
- panic(rt[i].err)
+ err := fmt.Errorf("prevalue mismatch for 0x%x, got 0x%x want 0x%x", path, got, blob)
+ rt.setError(i, err)
+ panic(err)
return false
}
}
for path, prev := range nodes.deletes {
blob, _, _ := origTrie.TryGetNode(hexToCompact([]byte(path)))
if !bytes.Equal(blob, prev) {
- rt[i].err = fmt.Errorf("prevalue mismatch for 0x%x, got 0x%x want 0x%x", path, prev, blob)
+ err = fmt.Errorf("prevalue mismatch for 0x%x, got 0x%x want 0x%x", path, prev, blob)
+ rt.setError(i, err)
return false
}
}
@@ -469,7 +604,7 @@ func runRandTest(rt randTest) bool {
}
newtr, err := New(root, common.Hash{}, root, triedb)
if err != nil {
- rt[i].err = err
+ rt.setError(i, err)
return false
}
tr = newtr
@@ -487,7 +622,7 @@ func runRandTest(rt randTest) bool {
checktr.Update(it.Key, it.Value)
}
if tr.Hash() != checktr.Hash() {
- rt[i].err = fmt.Errorf("hash mismatch in opItercheckhash")
+ rt.setError(i, fmt.Errorf("hash mismatch in opItercheckhash"))
}
case opNodeDiff:
var (
@@ -527,24 +662,25 @@ func runRandTest(rt randTest) bool {
}
}
if len(insertExp) != len(inserted) {
- rt[i].err = fmt.Errorf("insert set mismatch")
+ rt.setError(i, fmt.Errorf("insert set mismatch"))
+
}
if len(deleteExp) != len(deleted) {
- rt[i].err = fmt.Errorf("delete set mismatch")
+ rt.setError(i, fmt.Errorf("delete set mismatch"))
}
for _, insert := range inserted {
if _, present := insertExp[string(insert)]; !present {
- rt[i].err = fmt.Errorf("missing inserted node")
+ rt.setError(i, fmt.Errorf("missing inserted node"))
}
}
for _, del := range deleted {
if _, present := deleteExp[string(del)]; !present {
- rt[i].err = fmt.Errorf("missing deleted node")
+ rt.setError(i, fmt.Errorf("missing deleted node"))
}
}
}
// Abort the test on error.
- if rt[i].err != nil {
+ if rt.hasError(i) {
return false
}
}
@@ -552,7 +688,7 @@ func runRandTest(rt randTest) bool {
}
func TestRandom(t *testing.T) {
- if err := quick.Check(runRandTest, nil); err != nil {
+ if err := quick.Check(runRandTestSteps, nil); err != nil {
if cerr, ok := err.(*quick.CheckError); ok {
t.Fatalf("random test iteration %d failed: %s", cerr.Count, spew.Sdump(cerr.In))
}
Something which has confused me quite a bit, but which I now finally think I have grokked..
So this does not actually track deleted nodes, but rather deleted leaves ?
@holiman it tracks the deleted trie node, but not the deleted leaves. Specifically, leaves are the value of the shortNode, and at least in the current codebase, leaves are never the standalone entries in database. It's unnecessary to track them. The goal is to find out the node which are present in the database but now are deleted, so that we can apply the deletion operation in database level.
So, my question was more about delete. This PR tracks explicit deletes.. ?
I made a testcase, which creates a trie, and stores to disk. Then it loads the trie again, and inserts a new key. The new insertion menas that at least the root node (and possibly one shortnode below) are no longer present in the trie. They would be up for removal from database.
However, when I run the test on this PR, the deletion-set is empty.
I added this
func (set *NodeSet) Summary() string {
var out = new(strings.Builder)
if set.updates != nil {
for _, key := range set.updates.order {
updated := set.updates.nodes[key]
fmt.Fprintf(out, "[*]: %x -> %v prev: %x\n", key, updated.hash, updated.prev)
}
}
for _, n := range set.deletes {
fmt.Fprintf(out, "[-]: %x\n", n)
}
for _, n := range set.leaves {
fmt.Fprintf(out, "[leaf]: %v\n", n)
}
return out.String()
}
And running one of my tests:
root 1: 09c889feaafd53779755259beaa0ff41c32512c8cac45152af46fae7ebdef210
root 2: 773c1298ba605b3a05a8e88ef0ae0a2c434047e1253b4b558ef10d952c1f60ac
[*]: 0604060f060706 -> 0x36ddbeef1597fc3e2b5a19c9fec2cfd2d29c181c1ed8245ea76f8fdbafaada01 prev:
[*]: 0604060f0607 -> 0xe87d178131adb69b661a9d31d852c22d3d9b7d59693ef03fada4fa61fa775123 prev:
[*]: 0604060f06 -> 0xf2598e079354369ec38b66cd7907509a07c3a08bc211bcf90cf2be7ad6272317 prev:
[*]: 0604060f -> 0x869047106ae1e547c865463c72726b7c71b7a8dbd74588b4ea25a29767021490 prev: f3808080808080de17dc808080808080c63584636f696e8080808080808080808570757070798080808080808080808476657262
[*]: 0604 -> 0xff4b5edab0561fe667b0c859bd943529c4b09ede1f12466d5c39b478b90aaa00 prev: e482006fa0d43b87fdcd4217013ccc92d04662e12d36e4cc25dc690077cd821a1956fc3e36
[*]: 06 -> 0xe2108ef7630efcf439e2b4f617be619ffc04e130a26701e561864c1f7ebdda37 prev: f85080808080a094a9f95bd89698e4da1812e0518053813b4d5b87caaf6b3c6fa57e9e50c0ff68d085207468657289776f6f6b6965646f6f8080cf85206f727365887374616c6c696f6e8080808080808080
[*]: -> 0x773c1298ba605b3a05a8e88ef0ae0a2c434047e1253b4b558ef10d952c1f60ac prev:
root 3: 09c889feaafd53779755259beaa0ff41c32512c8cac45152af46fae7ebdef210
[*]: 0604060f -> 0xd43b87fdcd4217013ccc92d04662e12d36e4cc25dc690077cd821a1956fc3e36 prev: f5808080808080a0f2598e079354369ec38b66cd7907509a07c3a08bc211bcf90cf2be7ad62723178080808080808080808476657262
[*]: 0604 -> 0x94a9f95bd89698e4da1812e0518053813b4d5b87caaf6b3c6fa57e9e50c0ff68 prev: e482006fa0869047106ae1e547c865463c72726b7c71b7a8dbd74588b4ea25a29767021490
[*]: 06 -> 0x922301237fbbb24c0cf171190666e966fbd99d6d568dfa9a4dffd0f91888c26f prev: f85080808080a0ff4b5edab0561fe667b0c859bd943529c4b09ede1f12466d5c39b478b90aaa00d085207468657289776f6f6b6965646f6f8080cf85206f727365887374616c6c696f6e8080808080808080
[*]: -> 0x09c889feaafd53779755259beaa0ff41c32512c8cac45152af46fae7ebdef210 prev:
[-]: f6808080808080a036ddbeef1597fc3e2b5a19c9fec2cfd2d29c181c1ed8245ea76f8fdbafaada01808080808080808080857075707079
[-]: e217a0e87d178131adb69b661a9d31d852c22d3d9b7d59693ef03fada4fa61fa775123
[-]: e48080808080c62084636f696e80cd8320696588626c61686f6e6761808080808080808080
Which confirms that we don't need to track order explicitly, since the order can be inferred from the key. But you can leave it as is for now, and if we want to we can change it at some point.
Hm. Added path to delete summary too
root 3: 09c889feaafd53779755259beaa0ff41c32512c8cac45152af46fae7ebdef210
[*]: 0604060f -> 0xd43b87fdcd4217013ccc92d04662e12d36e4cc25dc690077cd821a1956fc3e36 prev: f5808080808080a0f2598e079354369ec38b66cd7907509a07c3a08bc211bcf90cf2be7ad62723178080808080808080808476657262
[*]: 0604 -> 0x94a9f95bd89698e4da1812e0518053813b4d5b87caaf6b3c6fa57e9e50c0ff68 prev: e482006fa0869047106ae1e547c865463c72726b7c71b7a8dbd74588b4ea25a29767021490
[*]: 06 -> 0x922301237fbbb24c0cf171190666e966fbd99d6d568dfa9a4dffd0f91888c26f prev: f85080808080a0ff4b5edab0561fe667b0c859bd943529c4b09ede1f12466d5c39b478b90aaa00d085207468657289776f6f6b6965646f6f8080cf85206f727365887374616c6c696f6e8080808080808080
[*]: -> 0x09c889feaafd53779755259beaa0ff41c32512c8cac45152af46fae7ebdef210 prev:
[-]: 0604060f060706 -> e48080808080c62084636f696e80cd8320696588626c61686f6e6761808080808080808080
[-]: 0604060f0607 -> f6808080808080a036ddbeef1597fc3e2b5a19c9fec2cfd2d29c181c1ed8245ea76f8fdbafaada01808080808080808080857075707079
[-]: 0604060f06 -> e217a0e87d178131adb69b661a9d31d852c22d3d9b7d59693ef03fada4fa61fa775123
Question: just like writes, shouldn't deletes also be ordered? But the other way around, so that we delete from top to bottom? (short path first)
Ah, the deletion refers that the node with specific path is removed from the database. In your case, the root node is updated not deleted.
And regarding the deletion order, yep theoretically we should track them and remove nodes from disk based on this order. However in hash-based, we don't do deletion at all, and in path-based, we only flush out all dirty nodes(inserted nodes, updated nodes, deleted nodes) in a single batch atomically, thus the order of deletion is also not required.
In my test:
- have a trie (
root1), - add a thing (
root2), - delete that thing again (
root3==root1).
This is the output:
nodeset owner: 0x0000000000000000000000000000000000000000000000000000000000000000
[+]: 0604060f -> 0xd43b87fdcd4217013ccc92d04662e12d36e4cc25dc690077cd821a1956fc3e36
[+]: 0604 -> 0x94a9f95bd89698e4da1812e0518053813b4d5b87caaf6b3c6fa57e9e50c0ff68
[+]: 06 -> 0x922301237fbbb24c0cf171190666e966fbd99d6d568dfa9a4dffd0f91888c26f
[+]: 0703060f -> 0xdffd2e51427432e4a055acdcf319c1e35ad23c1d657ab7c7e7ad4908284b86f7
[+]: 070306 -> 0x17771d80b3478657f96ef7e103fb6e424eff6e320dc54b584d31c335e525d565
[+]: 07 -> 0xadbfedafc33dc930b9a9f0c6345320b4d57016638332d2fa08fbfbdd01449c45
[+]: -> 0x09c889feaafd53779755259beaa0ff41c32512c8cac45152af46fae7ebdef210
root 1: 09c889feaafd53779755259beaa0ff41c32512c8cac45152af46fae7ebdef210
root 2: 773c1298ba605b3a05a8e88ef0ae0a2c434047e1253b4b558ef10d952c1f60ac
nodeset owner: 0x0000000000000000000000000000000000000000000000000000000000000000
[+]: 0604060f060706 -> 0x36ddbeef1597fc3e2b5a19c9fec2cfd2d29c181c1ed8245ea76f8fdbafaada01
[+]: 0604060f0607 -> 0xe87d178131adb69b661a9d31d852c22d3d9b7d59693ef03fada4fa61fa775123
[+]: 0604060f06 -> 0xf2598e079354369ec38b66cd7907509a07c3a08bc211bcf90cf2be7ad6272317
[*]: 0604060f -> 0x869047106ae1e547c865463c72726b7c71b7a8dbd74588b4ea25a29767021490 prev: f3808080808080de17dc808080808080c63584636f696e8080808080808080808570757070798080808080808080808476657262
[*]: 0604 -> 0xff4b5edab0561fe667b0c859bd943529c4b09ede1f12466d5c39b478b90aaa00 prev: e482006fa0d43b87fdcd4217013ccc92d04662e12d36e4cc25dc690077cd821a1956fc3e36
[*]: 06 -> 0xe2108ef7630efcf439e2b4f617be619ffc04e130a26701e561864c1f7ebdda37 prev: f85080808080a094a9f95bd89698e4da1812e0518053813b4d5b87caaf6b3c6fa57e9e50c0ff68d085207468657289776f6f6b6965646f6f8080cf85206f727365887374616c6c696f6e8080808080808080
[+]: -> 0x773c1298ba605b3a05a8e88ef0ae0a2c434047e1253b4b558ef10d952c1f60ac
root 3: 09c889feaafd53779755259beaa0ff41c32512c8cac45152af46fae7ebdef210
nodeset owner: 0x0000000000000000000000000000000000000000000000000000000000000000
[*]: 0604060f -> 0xd43b87fdcd4217013ccc92d04662e12d36e4cc25dc690077cd821a1956fc3e36 prev: f5808080808080a0f2598e079354369ec38b66cd7907509a07c3a08bc211bcf90cf2be7ad62723178080808080808080808476657262
[*]: 0604 -> 0x94a9f95bd89698e4da1812e0518053813b4d5b87caaf6b3c6fa57e9e50c0ff68 prev: e482006fa0869047106ae1e547c865463c72726b7c71b7a8dbd74588b4ea25a29767021490
[*]: 06 -> 0x922301237fbbb24c0cf171190666e966fbd99d6d568dfa9a4dffd0f91888c26f prev: f85080808080a0ff4b5edab0561fe667b0c859bd943529c4b09ede1f12466d5c39b478b90aaa00d085207468657289776f6f6b6965646f6f8080cf85206f727365887374616c6c696f6e8080808080808080
[+]: -> 0x09c889feaafd53779755259beaa0ff41c32512c8cac45152af46fae7ebdef210
[-]: 0604060f060706 -> e48080808080c62084636f696e80cd8320696588626c61686f6e6761808080808080808080
[-]: 0604060f0607 -> f6808080808080a036ddbeef1597fc3e2b5a19c9fec2cfd2d29c181c1ed8245ea76f8fdbafaada01808080808080808080857075707079
[-]: 0604060f06 -> e217a0e87d178131adb69b661a9d31d852c22d3d9b7d59693ef03fada4fa61fa775123
I denote it as "new", with [+] if it's an update without a previous value, and [*}, for update without previous value, and [-] for deletion.
Early on, root1 is created at ``-path:
[+]: -> 0x09c889feaafd53779755259beaa0ff41c32512c8cac45152af46fae7ebdef210
Then, the root2 is created, over that same path ``:
[+]: -> 0x773c1298ba605b3a05a8e88ef0ae0a2c434047e1253b4b558ef10d952c1f60ac
And eventually, the root3 is created:
[+]: -> 0x09c889feaafd53779755259beaa0ff41c32512c8cac45152af46fae7ebdef210
In all these cases, the prev becomes unset. For other paths, the prev becomes set, but never for the root path.
Is this by design? If not, is there any consequence to this behaviour?
@holiman I will investigate it. root2 and root3 should be updated, not inserted. Thanks for catching it.
~Although I also just found a bug in insertedNode tracking. Not sure if it's the cause or not.~ The code should be correct.